Day 17: Set and Forget

#!/usr/bin/env crystal
require "readline"
require "colorize"
require "../lib/vm2.cr"
require "../lib/disasm.cr"

class Debugger
  property vm : VM2::VM

  property watchlist : Hash(String, Int32)
  property breakpoints : Hash(Int32, String)

  property output_log : Array(Int64)

  property io_mode : Symbol

  def initialize()
    @vm = VM2::VM.new([0_i64])
    @watchlist = {} of String => Int32
    @breakpoints = {} of Int32 => String
    @output_log = [] of Int64
    @io_mode = :int
  end

  def print_vm_summary
    puts "%s:%s] PC: %s  BASE: %s" % [@vm.name, @vm.status, format_addr_val(@vm.pc), format_addr_val(@vm.rel_base)]
    puts "IN: #{@vm.input}" if @vm.input.size > 0
    puts "ERR: %s" % @vm.error if @vm.error
    print_watches
    print_disasm(@vm.pc, @vm.pc+25) if @vm.mem.size > 1
  end

  def print_watches
    puts @watchlist.map { |name, a| "%s (%05i) = %05i" % {name, a, @vm.read_mem(a)} }.join(", ")
  end

  def print_breaks
    puts "BREAKPOINTS:"
    puts @breakpoints.join("\n")
  end

  def print_disasm(start,stop)
    segment = @vm.mem[start..stop]
    log "showing #{start}..#{stop}"

    dis = Disasm.intcode_to_str(segment, start)
    log "\n%s\n" % dis
  end

  def prompt
    if @vm.mem.size > 1
      "%s:%s] " % [@vm.name, @vm.status, format_addr_val(@vm.pc), format_addr_val(@vm.rel_base)]
    else
      "> "
    end
  end

  def format_addr_val(addr)
    "%05i (%05i)" % [addr, @vm.read_mem(addr)]
  end

  def log(msg)
    puts msg
  end

  def run_vm
    log "running...\n"
    start = @vm.cycles
    while @vm.status == :ok && ! @breakpoints[@vm.pc]?
      @vm.exec
    end
    log "\nstopped after %s cycles" % [@vm.cycles - start]
    log " BREAKPOINT: %s" % @breakpoints[@vm.pc] if @breakpoints[@vm.pc]?
    print_vm_summary
  end

  def load_program(filename)
    @vm = VM2.from_file(filename)
    @vm.output_fn = ->(x: Int64) {
      @output_log << x;
      case @io_mode
      when :int then log "VM OUTPUT: %5i   (%s)" % [x,x.chr.ascii_control? ? ' ' : x.chr]
      when :text then print (x >= 0 ? x.chr : "{chr: %i}" % x)
      end
    }
    log "loaded VM (%i)" % @vm.mem.size
  end

  def step(n,verbose=false)
    c = @vm.cycles
    while n > 0 && @vm.status == :ok
      n -= 1
      @vm.exec
      print_vm_summary if verbose
    end
    log "stopped after #{@vm.cycles - c} cycles"
    print_vm_summary
  end

  def add_breakpoint(name, address)
    @breakpoints[address] = name
  end

  def rm_breakpoint(name)
    @breakpoints.each do |k,v|
      if v == name
        @breakpoints[k] = nil
      end
    end
  end

  def add_watch(name, address)
    @watchlist[name] = address
  end

  def rm_watch(name)
    @watchlist[name] = nil
  end

  def run

    log "Intcode Debugger Ready"

    if ARGV[0]?
      load_program ARGV[0]
      log "Loaded Program: %s" % ARGV[0]
    end

    while input = Readline.readline(prompt,true)
      line = input.strip

      if line == "" && @vm.mem.size > 1
        @vm.exec
        print_vm_summary
      end

      next unless line.match(/.+/)

      args = line.split(' ')
      command = args.shift

      case command

      when "load" # load program
        next if args.size < 1
        load_program(args[0])
        print_vm_summary

      when "run" # run the machine until it stops, or the pc hits a breakpoint
        run_vm

      when "step" # step foward n steps, ignoring breakpoints
        n = (args[0]? || "1").to_i
        puts "running #{n} steps"
        step(n)

      when "stepv" # step forward n steps, ignoring breakpoints, print state on each step
        n = (args[0]? || "1").to_i
        puts "running #{n} steps"
        step(n, true)

      when "breakpoint"
        if args.size > 0
          addrs = args.in_groups_of(2,"0").map { |a| {a[0], a[1].to_i} }
          addrs.each do |n,a|
            add_breakpoint(n,a)
          end
          log "added #{addrs.size} breakpoints"
        else
          print_breaks
        end

      when "watch" # add an address to the watchlist
        if args.size > 1
          addrs = args.in_groups_of(2,"0").map { |a| {a[0], a[1].to_i} }
          addrs.each do |n,a|
            add_watch(n,a)
          end
          log "added #{addrs.size} addresses to the watchlist"
        else
          print_watches
        end

      when "show" # show the state and watchlist, show n...: show a list of addresses
        if args.size > 0
          args.each do |a|
            puts "(%s) %05i" % [a, @vm.read_mem(a.to_i)]
          end
        else
          print_vm_summary
        end

      when "set"
        next if args.size < 2

        if args[0].match /\d+/
          a = args[0].to_i64
          v = args[1].to_i64
          @vm.write_mem(a,v)
        else case args[0].downcase
             when "pc"
               @vm.pc = args[1].to_i64
             when "base"
               @vm.rel_base = args[1].to_i64
             when "status", "state"
               case args[1]
               when "ok"
                 @vm.status = :ok
               when "halted"
                 @vm.status = :halted
               when "needs_input"
                 @vm.status = :needs_input
               else log "invalid status"
               end
             when "io"
               case args[1]
               when "int", "num"
                 @io_mode = :int
               when "text", "ascii"
                 @io_mode = :text
               else log "invalid io mode"
               end
             else log "can't set that"
             end
        end

      when "disasm"
        start = args[0]? ? args[0].to_i : @vm.pc
        stop = args[1]? ? args[1].to_i : start+10

        print_disasm(start,stop)

      when "dump"
        File.write(args[0]? || "dump.txt", vm.mem.map{ |v| v.to_s }.join(","))

      when "input" # feed input to the machine
        next unless args.size > 0
        case @io_mode
        when :int
          args.each do |a|
            vm.send_input(a.to_i64)
          end
        when :text
          str = args.join(" ")
          str.chars.map { |c| c.ord.to_i64 }.each { |ascii| vm.send_input(ascii) }
        end

      when "line"
        str = "%s\n" % args.join(" ")
        str.chars.map { |c| c.ord.to_i64 }.each { |ascii| vm.send_input(ascii) }

      when "output" # show the machine's output
        log @output_log

      when "otext"
        log @output_log.map{ |v| v.unsafe_chr }.join

      when "exit"
        log "goodbye"
        break
      end

    end

  end

end

Debugger.new.run

Once I had the map, it wasn't difficult to just look for the intersections and manually compute the answer from their positions.

Part 2 is a kind of simple compression problem: you have a single long string (the full path the robot needs to traverse), and you must break it down into three different repeated chunks.

Once again I was able to work out the path manually, and if you write out the steps it's not too difficult to find the repeating patterns. My editor helped a bit here since it was easy to try out substitutions by using the interactive search/replace feature.

I did get stuck here for a while because of a transcription error that meant that the path I was working with didn't break down into chunks the way it should've; if you take the manual approach be sure to double check your work!

Once I realized my error and could compress the path the way the robot wanted, I was able to just feed that back into the program in my debugger and get the answer.

#!/usr/bin/env crystal

require "../lib/vm2.cr"
require "../lib/utils.cr"

prog = Utils.get_input_file(Utils.cli_param_or_default(0,"day17/input.txt"))

vm = VM2.from_string(prog)
vm.run

map = vm.output.map(&.chr).join.split('\n').map { |l| l.chars.to_a }
def safe_get_xy(map,pos : Tuple(Int32,Int32))
  x,y = pos
  if map.size > y && y >= 0
    if map[y].size > x && x >= 0
      return map[y][x]
    end
  end
  return '.'
end

DIRS = [{0,-1},{1,0},{0,1},{-1,0}]
def safe_get_dir_from_loc(map,loc,dir)
  safe_get_xy(map, {loc[0]+DIRS[dir][0],loc[1]+DIRS[dir][1]})
end

# find intersections and robot
facings = ['^','>','v','<']
robot = { {-1,-1}, 0}
intersections = Hash(Tuple(Int32,Int32), Bool).new(false)
map.each_with_index do |row,y|
  row.each_with_index do |tile,x|
    facings.index(tile).try { |f| robot = { {x,y}, f} }

    # check each direction to see if all 4 are #s
    up = safe_get_xy(map, {x, y-1})
    down = safe_get_xy(map, {x, y+1})
    left = safe_get_xy(map, {x-1, y})
    right = safe_get_xy(map, {x+1, y})

    if [tile, up,down,left,right].all?('#')
      intersections[{x,y}] = true
    end

  end
end

puts "Part 1: %i" % intersections.keys.map { |i| i[0] * i[1] }.sum

path = [] of String
dir_count = 0
while true
  # from robot pos, find direction left or right
  forward = safe_get_dir_from_loc(map,robot[0], (robot[1]))
  right = safe_get_dir_from_loc(map,robot[0], ((robot[1] + 1) % DIRS.size))
  left = safe_get_dir_from_loc(map,robot[0], ((robot[1] - 1) % DIRS.size))

  if forward == '#'
    dir_count += 1
    robot = { {robot[0][0] + DIRS[robot[1]][0], robot[0][1] + DIRS[robot[1]][1]}, robot[1] }
  else
    path << dir_count.to_s if dir_count != 0
    dir_count = 0
    if left == '#'
      path << "L"
      robot = { robot[0], (robot[1] - 1) % DIRS.size }
    elsif right == '#'
      path << "R"
      robot = { robot[0], (robot[1] + 1) % DIRS.size }
    else
      break
    end
  end
end
puts "Path: %s" % path.join(',')