Advent of Code 2022: Day 9

This challenge offered the chance to use one new piece of syntax, and also better understand the set data structure.

Case Expressions

The new piece of syntax is the case expression. It is used here to update the rope position based on the value of a direction:

    case direction of {
      "R": state.rope[1].x +:= 1
      "L": state.rope[1].x -:= 1
      "U": state.rope[1].y +:= 1
      "D": state.rope[1].y -:= 1
    }

Depending on the value of the direction variable, the rope's x or y coordinate will be increased or decreased.

Case expressions evaluate their expression ("direction" in this case), and then compare the result against each of the branch values using === until one matches. An interesting property is that the branches can be generators:

procedure main(inputs)
  num := 39

  case num of {
    1: write("first number")                        # <1>
    (2 | 4 | 6 | 8): write("small even number")     # <2>
    odd_nums(): write("odd number")                 # <3>
    default: write("unknown type")
  }
end

procedure odd_nums()
  i := 1
  while i < 100 do {
    i +:= 2
    suspend i
  }
end

1. This line matches a single value.
2. This line uses a generator to match one of several different values for this branch.
3. This lines does the same, but calls a function which repeatedly generates odd numbers until one matches: it's important this generator stops, else num=10 would not terminate.

Set Membership

I wanted to store members of a record in a set, relying on the set to remove duplicates. For example, with the following:

record posn(x, y)

procedure main()
  positions := set()
  insert(positions, posn(0, 0))
  insert(positions, posn(1, 1))
  insert(positions, posn(1, 1))
  if member(positions, posn(1, 1)) then write("Has (1, 1)") else write("Not member")

  every p := !positions do 
    write ("posn: ", p.x, " ", p.y)
  write("Number: ", *positions)
end

However, the output from this is:

Not member
posn: 1 1
posn: 1 1
posn: 0 0
Number: 3

Notice that the set contains the record entry for (1, 1) twice. The reason is that sets use ===, value equality, and two different record instances cannot be the same value:

  if posn(1,1) === posn(1,1) then 
    write("yes") 
  else 
    write("no")

This also applies to keys of tables.

There are two solutions to this:

1. Convert the posn to a value type, by using a factory procedure to return the same instance for the same parameters: this is used in the solution to Day 12.
2. Convert the posn to a string (or integer), and store the string in the set. This is the solution used here, because all we need to know is the number of unique positions encountered.

When placing posn instances into the set of encountered positions, convert each posn to a string:

  insert(positions, string(posn.x) || " " || string(posn.y))

Final Program

procedure main(inputs)
  local filename
  
  if *inputs = 1 then {
    filename := inputs[1]

    # Part 1 solution
    write("Part 1: ", count_moves(filename, 2))
    # Part 2 solution
    write("Part 2: ", count_moves(filename, 10))
  } else {
    write("Provide a filename of data")
  }
end

procedure count_moves(filename, rope_length)
  local current_state, file, line

  file := open(filename) | stop("Cannot open ", filename)
  current_state := initial_state(rope_length)                       # <1>
  every line := !file do
    make_move(current_state, line[1], integer(line[3:0]))           # <2>
  close(file)
  
  return *current_state.history                                     # <3>
end

record posn(x, y)
record state(rope, history)

# Initial state has Head covering T in bottom-left corner
procedure initial_state(rope_length)
  local rope
  
  rope := list()
  every 1 to rope_length do # make a rope of given length
    put(rope, posn(0,0)) 

  return state(rope, set())
end

procedure make_move(state, direction, num_steps)
  local delta_x, delta_y, i

  every 1 to num_steps do {
    # head moves depending on direction
    case direction of {
      "R": state.rope[1].x +:= 1
      "L": state.rope[1].x -:= 1
      "U": state.rope[1].y +:= 1
      "D": state.rope[1].y -:= 1
    }
    # tail moves to catch up
    every i := 1 to *state.rope-1 do {
      delta_x := state.rope[i].x - state.rope[i+1].x                  # <4>
      delta_y := state.rope[i].y - state.rope[i+1].y
      if abs(delta_x) = 2 then {                                      # <5>
        state.rope[i+1].x +:= sign(delta_x)                           # <6>
        state.rope[i+1].y +:= sign(delta_y)
      } else if abs(delta_y) = 2 then {
        state.rope[i+1].x +:= sign(delta_x)
        state.rope[i+1].y +:= sign(delta_y)
      }
    }
    # save record of tail moves - these are strings, to store in set    <7>
    insert(state.history, string(state.rope[*state.rope].x) || " " || string(state.rope[*state.rope].y))
  }
end

procedure sign(x)
  if x > 0 then
    return +1
  else if x < 0 then
    return -1
  else
    return 0
end

1. The rope length is used to construct the initial state, with a rope of the right size.
2. Every line is read in, and processed into a move.
3. Finally, the number of moves made by the tail is returned.
4. To calculate each move, we need the difference between the two link positions.
5. If there is a gap of 2 places, then we need to move the second link.
6. The sign procedure gives the appropriate step in each direction (1, -1 or 0)
7. The tail's position is placed into the history - this is converted into a string, for the set uniqueness property to work.