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     for op in program:
  15         if op == "add":
  16             if len(stack) > 1:
  17                 a, b = stack.pop(), stack.pop()
  18                 stack.append(a + b)
  19         elif op == "min":
  20             if len(stack) > 1:
  21                 a, b = stack.pop(), stack.pop()
  22                 stack.append(min(a, b))
  23         elif op == "max":
  24             if len(stack) > 1:
  25                 a, b = stack.pop(), stack.pop()
  26                 stack.append(max(a, b))
  27         elif op == "swp":
  28             if len(stack) > 1:
  29                 a, b = stack.pop(), stack.pop()
  30                 stack.append(a)
  31                 stack.append(b)
  32         elif op == "rep":
  33             if len(stack) > 1:
  34                 a, b = stack.pop(), stack.pop()
  35                 stack += [b] * a
  36         elif op == "dup":
  37             if len(stack) > 0:
  38                 a = stack.pop()
  39                 stack.append(a)
  40                 stack.append(a)
  41         elif op == "del":
  42             if len(stack) > 0:
  43                 a = stack.pop()
  44         else:
  45             raise ValueError(f"Unknown instruction {op}")
  46
  47
  48 rpl_ops = ["add", "min", "max", "swp", "rep", "dup", "del"]
  49
  50 ######################################################################
  51
  52
  53 def generate(nb_values=3, max_input=9, prog_len=6, nb_runs=5):
  54     prog_len = 1 + torch.randint(prog_len - 1, (1,)).item()
  55     prog = [rpl_ops[k] for k in torch.randint(len(rpl_ops), (prog_len,))]
  56
  57     result = []
  58     for _ in range(nb_runs):
  59         stack = [x.item() for x in torch.randint(max_input + 1, (nb_values,))]
  60         result = result + ["<input>"] + stack
  61         rpl_exec(prog, stack)
  62         result = result + ["<output>"] + stack
  63
  64     result = result + ["<prog>"] + prog
  65     result = result + ["<end>"]
  66     return result
  67
  68
  69 def next_marker(seq, tokens, start=0):
  70     pos = None
  71     for t in tokens:
  72         try:
  73             i = seq.index(t, start)
  74             if pos is None or i < pos:
  75                 pos = i
  76         except ValueError:
  77             pass
  78     return pos
  79
  80
  81 def check(seq):
  82     io = []
  83     k = 0
  84     while seq[k] == "<input>":
  85         o = next_marker(seq, ["<output>"], start=k + 1)
  86         e = next_marker(seq, ["<input>", "<prog>"], start=o)
  87         if o is None or e is None:
  88             raise ValueError("Invalid input/output")
  89         io.append((seq[k + 1 : o], seq[o + 1 : e]))
  90         k = e
  91
  92     if seq[k] == "<prog>":
  93         e = next_marker(seq, ["<end>"], start=k)
  94         if e is None:
  95             prog = []
  96         else:
  97             prog = seq[k + 1 : e]
  98
  99     nb_total, nb_errors = 0, 0
 100
 101     if len(set(prog) - set(rpl_ops)) > 0:
 102         for stack, target_stack in io:
 103             nb_total += len(target_stack)
 104             nb_errors += len(target_stack)
 105
 106     else:
 107         for stack, target_stack in io:
 108             # print(f"INIT {stack} PROG {prog}")
 109             rpl_exec(prog, stack)
 110             # print(f"CHECK {stack} REF {target_stack} NB_ERROR {abs(len(stack) - len(target_stack))+sum([0 if x == y else 1 for x, y in zip(stack, target_stack)])}")
 111             nb_total += len(target_stack)
 112             nb_errors += abs(len(stack) - len(target_stack))
 113             nb_errors += sum([0 if x == y else 1 for x, y in zip(stack, target_stack)])
 114
 115     return nb_total, nb_errors
 116
 117
 118 ######################################################################
 119
 120 if __name__ == "__main__":
 121     seq = generate()
 122     print(seq)
 123     seq[3] = 7
 124     print(seq)
 125     print(check(seq))