Advent of Code 2019 Day 02 - Solution in Pyret

aoc19-02.arr

provide {
    day-02 : day-02
}
end

include my-gdrive("aoc19-02-input.arr")
include string-dict

data Opcode:
  | add
  | mul
  | halt
  | udf
end

opcode-table = [string-dict: "1", add, "2", mul, "99", halt]

disasm-opcode :: NumInteger -> Opcode
examples:
  disasm-opcode(56) is udf
  disasm-opcode(1) is add
  disasm-opcode(2) is mul
  disasm-opcode(99) is halt
end

fun disasm-opcode(opcode):
  cases(Option<Opcode>) opcode-table.get(num-to-string(opcode)):
    | some(o) => o
    | none => udf
  end
end


data State:
  | state(instruction-pointer :: NumInteger, memory :: Array<NumInteger>)
sharing:
  method ip-opcode(self):
    ip = self.instruction-pointer
    if ip > (self.memory.length() - 1):
      udf
    else:
      disasm-opcode(self.memory.get-now(ip))
    end
  end,
  method ip-params(self):
    ip = self.instruction-pointer
    mem = self.memory
    { mem.get-now(ip + 1); mem.get-now(ip + 2); mem.get-now(ip + 3) } 
  end
where:
  state(0, [array: 1,0,0,0,99]).instruction-pointer is 0
  state(0, [array: 1,0,0,0,99]).ip-opcode() is add
  state(2, [array: 1,0,0,0,99]).ip-opcode() is udf
  state(4, [array: 1,0,0,0,99]).ip-opcode() is halt
  state(5, [array: 1,0,0,0,99]).ip-opcode() is udf
  state(0, [array: 1,0,0,0,99]).ip-params() is%(equal-now) {0; 0; 0}
end


run :: State -> State
examples:
  run(state(0, [array: 1,0,0,0,99])) =~ state(4, [array: 2,0,0,0,99]) is true
  run(state(0, [array: 2,3,0,3,99])) =~ state(4, [array: 2,3,0,6,99]) is true
  run(state(0, [array: 2,4,4,5,99,0])) =~ state(4, [array: 2,4,4,5,99,9801]) is true
  run(state(0, [array: 1,1,1,4,99,5,6,0,99])) =~ state(8, [array: 30,1,1,4,2,5,6,0,99]) is true    
end

fun run(s) block:
  cases(Opcode) s.ip-opcode():
    | halt => s
    | udf => s
    | else => block:
        new-state = exec(s)
        run(new-state)
      end
  end
end

exec :: State -> State
examples:
  exec(state(0, [array: 1,9,10,3,2,3,11,0,99,30,40,50])) =~
  state(4, [array: 1,9,10,70,2,3,11,0,99,30,40,50]) is true
  exec(state(4, [array: 1,9,10,70,2,3,11,0,99,30,40,50])) =~
  state(8, [array: 3500,9,10,70,2,3,11,0,99,30,40,50]) is true
end

fun exec(s) block:
  mem = s.memory
  cases(Opcode) s.ip-opcode():
    | add => block:
        {p1; p2; p3} = s.ip-params()
        val1 = mem.get-now(p1)
        val2 = mem.get-now(p2)
        mem.set-now(p3, val1 + val2)
        state(s.instruction-pointer + 4, mem)
      end
    | mul => block:
        {p1; p2; p3} = s.ip-params()
        val1 = mem.get-now(p1)
        val2 = mem.get-now(p2)
        mem.set-now(p3, val1 * val2)
        state(s.instruction-pointer + 4, mem)
      end
    | else => s
  end
end


prepare-state :: List<NumInteger>, NumInteger, NumInteger -> State
fun prepare-state(in, noun, verb) block:
  mem = array-from-list(in)
  mem.set-now(1, noun)
  mem.set-now(2, verb)
  state(0, mem)
where:
  prepare-state([list: 1,0,0,0,99], 12, 2) =~ state(0, [array: 1,12,2,0,99]) is true
end


fun solution-1() -> NumInteger:
  run(prepare-state(input, 12, 2)).memory.get-now(0)
end

fun solution-2() -> NumInteger:
  #| 
     The only operations in the code are sums and multiplications of integers, then necessarily
     the code is a linear form of the noun and verb variables:
     
     run(prepare-state(input, noun, verb)) = n0 + n1 * noun + n2 * verb, 
     
     but
     
     run(prepare-state(input, 0, 0)) = 797908
     run(prepare-state(input, 1, 0)) = 797908 + 460800
     run(prepare-state(input, 0, 1)) = 797908 + 1,
     
     then n0 = 797908, n1 = 460800, n2 = 1.     
          
     Therfore the costraint that puzzle impose, 
     
     run(prepare-state(input, noun, verb)) = 19690720
 
     is the same that
     
     797908 + 460800 * noun + verb = 19690720
     
     But noun and verb are addresses so is also required:
     
     0 <= noun < lists.length(input) and 
     0 <= verb < lists.length(input)
     
     So the only solution of the diofantean system of equations is noun = 41 and verb = 12.
     
     https://www.wolframalpha.com/input/?i=797908+%2B+460800+*+n+%2B+v+%3D+19690720%2C+0+%3C%3D+n+%3C+165%2C+0+%3C%3D+v+%3C165
     
     The puzzle ask the value, with the constraints above, of 100 * noun + verb
  |#
  (100 * 41) + 12
end

fun solution-2-brutal() -> NumInteger block:
  min-address = 0
  max-address = lists.length(input) - 1
  adresses = lists.range(min-address, max-address)
  var noun = 0
  var verb = 0
  for map(n from adresses):
    for map(v from adresses):
      when run(prepare-state(input, n, v)).memory.get-now(0) == 19690720 block:
        noun := n
        verb := v
      end
    end
  end
  (100 * noun) + verb      
end



day-02 :: { solution-1 :: Function, solution-2 :: Function } = 
  { solution-1: solution-1, solution-2: solution-2 }