7 votes

Day 17: Set and Forget

Today's problem description: https://adventofcode.com/2019/day/17


Join the Tildes private leaderboard! You can do that on this page, by entering join code 730956-de85ce0c.

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace python with any of the "short names" listed in this page of supported languages):

<details>
<summary>Part 1</summary>

```python
Your code here.
```

</details>

1 comment

  1. Crespyl
    (edited )
    Link
    This was a funny one in that I almost ended up writing no new code to solve it. I already had a debugger that could handle ASCII input and output, I just had to tweak it a bit to make feeding...

    This was a funny one in that I almost ended up writing no new code to solve it. I already had a debugger that could handle ASCII input and output, I just had to tweak it a bit to make feeding lines with the newline character easier.

    Since I didn't write much new code, I'll just share the bare-bones debugger I'm using:

    Intcode Debugger - Crystal
    #!/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
    
    Part 1 As mentioned, this was quite simple: I just loaded the program into my debugger, enabled ASCII output, and ran the program to get the map.

    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

    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.


    Edit:
    I still had an itch to write some more code, so I worked out an automated solution to P1 (edit-edit, also extracting the uncompressed path for p2):

    Part 1 - Crystal
    #!/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(',')
    
    1 vote