rpl.py

   1 #!/usr/bin/env python
   2
   3 import math
   4
   5 import torch, torchvision
   6
   7 from torch import nn
   8 from torch.nn import functional as F
   9
  10 ######################################################################
  11
  12
  13 def rpl_exec(program, stack):
  14     stack = stack.copy()
  15     for op in program:
  16         if op == "add":
  17             if len(stack) > 1:
  18                 a, b = stack.pop(), stack.pop()
  19                 stack.append(a + b)
  20         elif op == "min":
  21             if len(stack) > 1:
  22                 a, b = stack.pop(), stack.pop()
  23                 stack.append(min(a, b))
  24         elif op == "max":
  25             if len(stack) > 1:
  26                 a, b = stack.pop(), stack.pop()
  27                 stack.append(max(a, b))
  28         elif op == "swp":
  29             if len(stack) > 1:
  30                 a, b = stack.pop(), stack.pop()
  31                 stack.append(a)
  32                 stack.append(b)
  33         elif op == "rep":
  34             if len(stack) > 1:
  35                 a, b = stack.pop(), stack.pop()
  36                 stack += [b] * a
  37         elif op == "dup":
  38             if len(stack) > 0:
  39                 a = stack.pop()
  40                 stack.append(a)
  41                 stack.append(a)
  42         elif op == "del":
  43             if len(stack) > 0:
  44                 a = stack.pop()
  45         else:
  46             raise ValueError(f"Unknown instruction {op}")
  47
  48     return stack
  49
  50
  51 rpl_ops = ["add", "min", "max", "swp", "rep", "dup", "del"]
  52
  53 ######################################################################
  54
  55
  56 def generate(nb_starting_values=3, max_input=9, prog_len=6, nb_runs=5):
  57     prog_len = (1 + torch.randint(2 * prog_len, (1,))).clamp(max=prog_len).item()
  58
  59     while True:
  60         no_empty_stack = True
  61         prog = [rpl_ops[k] for k in torch.randint(len(rpl_ops), (prog_len,))]
  62
  63         result = []
  64         for _ in range(nb_runs):
  65             stack = [
  66                 x.item() for x in torch.randint(max_input + 1, (nb_starting_values,))
  67             ]
  68             result_stack = rpl_exec(prog, stack)
  69             if len(result_stack) == 0:
  70                 no_empty_stack = False
  71             result = result + ["<input>"] + stack + ["<output>"] + result_stack
  72
  73         result = result + ["<prog>"] + prog
  74         result = result + ["<end>"]
  75         if no_empty_stack:
  76             break
  77
  78     return result
  79
  80
  81 def next_marker(seq, tokens, start=0):
  82     pos = None
  83     for t in tokens:
  84         try:
  85             i = seq.index(t, start)
  86             if pos is None or i < pos:
  87                 pos = i
  88         except ValueError:
  89             pass
  90     return pos
  91
  92
  93 def decompose(seq):
  94     io = []
  95     k = 0
  96     while seq[k] == "<input>":
  97         o = next_marker(seq, ["<output>"], start=k + 1)
  98         e = next_marker(seq, ["<input>", "<prog>"], start=o)
  99         if o is None or e is None:
 100             raise ValueError("Invalid input/output")
 101         try:
 102             io.append(
 103                 ([int(x) for x in seq[k + 1 : o]], [int(x) for x in seq[o + 1 : e]])
 104             )
 105         except ValueError:
 106             raise ValueError("Invalid input/output")
 107
 108         k = e
 109
 110     if seq[k] == "<prog>":
 111         e = next_marker(seq, ["<end>"], start=k)
 112         if e is None:
 113             prog = []
 114         else:
 115             prog = seq[k + 1 : e]
 116     return prog, io
 117
 118
 119 def compute_nb_errors(seq):
 120     prog, io = decompose(seq)
 121
 122     nb_total, nb_errors = 0, 0
 123
 124     stacks = []
 125
 126     if len(set(prog) - set(rpl_ops)) > 0:
 127         # Program is not valid, we count 100% error
 128         for start_stack, target_stack in io:
 129             stacks.append((start_stack, target_stack, ["N/A"], False))
 130             nb_total += len(target_stack)
 131             nb_errors += len(target_stack)
 132
 133     else:
 134         # Program is valid
 135         for start_stack, target_stack in io:
 136             result_stack = rpl_exec(prog, start_stack)
 137             nb_total += len(target_stack)
 138             e = abs(len(result_stack) - len(target_stack)) + sum(
 139                 [0 if x == y else 1 for x, y in zip(result_stack, target_stack)]
 140             )
 141             nb_errors += e
 142             stacks.append((start_stack, target_stack, result_stack, e == 0))
 143
 144     return nb_total, nb_errors, prog, stacks
 145
 146
 147 ######################################################################
 148
 149 if __name__ == "__main__":
 150     seq = generate()
 151     print(seq)
 152     seq[3] = 7
 153     print(seq)
 154     print(compute_nb_errors(seq))