3 # Any copyright is dedicated to the Public Domain.
4 # https://creativecommons.org/publicdomain/zero/1.0/
6 # Written by Francois Fleuret <francois@fleuret.org>
10 import torch, torchvision
13 from torch.nn import functional as F
15 ######################################################################
18 def rpl_exec(program, stack):
23 a, b = stack.pop(), stack.pop()
27 a, b = stack.pop(), stack.pop()
28 stack.append(min(a, b))
31 a, b = stack.pop(), stack.pop()
32 stack.append(max(a, b))
35 a, b = stack.pop(), stack.pop()
40 a, b = stack.pop(), stack.pop()
51 raise ValueError(f"Unknown instruction {op}")
56 rpl_ops = ["add", "min", "max", "swp", "rep", "dup", "del"]
58 ######################################################################
62 nb_starting_values=3, nb_result_values_max=None, max_input=9, prog_len=6, nb_runs=5
64 prog_len = (1 + torch.randint(2 * prog_len, (1,))).clamp(max=prog_len).item()
68 prog = [rpl_ops[k] for k in torch.randint(len(rpl_ops), (prog_len,))]
71 for _ in range(nb_runs):
73 x.item() for x in torch.randint(max_input + 1, (nb_starting_values,))
75 result_stack = rpl_exec(prog, stack)
76 if len(result_stack) == 0:
77 no_empty_stack = False
78 result = result + ["<in>"] + stack + ["<out>"] + result_stack
80 result = result + ["<prg>"] + prog
81 result = result + ["<end>"]
83 if no_empty_stack and (
84 nb_result_values_max is None or len(result_stack) <= nb_result_values_max
91 def next_marker(seq, tokens, start=0):
95 i = seq.index(t, start)
96 if pos is None or i < pos:
106 while seq[k] == "<in>":
107 o = next_marker(seq, ["<out>"], start=k + 1)
109 raise ValueError("Missing output markers (should be correct in the prompt)")
110 e = next_marker(seq, ["<in>", "<prg>"], start=o)
113 "Missing input/output markers (should be correct in the prompt)"
117 ([int(x) for x in seq[k + 1 : o]], [int(x) for x in seq[o + 1 : e]])
121 "Invalid input/output value (should be correct in the prompt)"
126 if seq[k] == "<prg>":
127 e = next_marker(seq, ["<end>"], start=k)
131 prog = seq[k + 1 : e]
133 raise ValueError("Missing <prg> (it should be in the prompt)")
138 def stack_distance(target_stack, result_stack):
139 return abs(len(result_stack) - len(target_stack)) + sum(
140 [0 if x == y else 1 for x, y in zip(result_stack, target_stack)]
144 def compute_nb_errors(seq):
145 prog, io = decompose(seq)
147 nb_total, nb_errors = 0, 0
151 if len(set(prog) - set(rpl_ops)) > 0:
152 # Program is not valid, we count 100% error
153 for start_stack, target_stack in io:
154 stacks.append((start_stack, target_stack, ["N/A"], False))
155 nb_total += len(target_stack)
156 nb_errors += len(target_stack)
160 for start_stack, target_stack in io:
161 result_stack = rpl_exec(prog, start_stack)
162 nb_total += len(target_stack)
163 e = stack_distance(target_stack, result_stack)
165 stacks.append((start_stack, target_stack, result_stack, e == 0))
167 return nb_total, nb_errors, prog, stacks
170 ######################################################################
172 if __name__ == "__main__":
177 print(compute_nb_errors(seq))