Advent of Code 2022: Day 13

This problem requires some recursive processing, to compare the nested lists, and a sort routine.

From a language perspective, this solution introduces some more scanning procedures, and type checking.

More Scanning Procedures

This solution uses the bal procedure, which finds balanced strings according to given delimiters. This procedure takes three arguments:

For example:

  line := "[[123],x456y]"
  line ? {
    ="["
    write("In brackets: ", tab(bal(',','[',']')))
    =","
    write("In letters: ", tab(bal(']','x','y')))
    ="]"
  }

outputs:

In brackets: [123]
In letters: x456y

Here, bal is used to help parse the input packets into lists of lists. The final packet parsing function is quite succinct, using a simple recursive structure on nested lists:

procedure parse_packet(packet)
  local result

  result := list()                                          # <1>
  packet ? {
    ="["                                                    # <2>
    until any(']') do {                                     # <3>
      if any(&digits) then {                                # <4>
        put(result, integer(tab(many(&digits))))
      } else if any('[') then {                             # <5>
        put(result, parse_packet(tab(bal(',]','[',']'))))   # <6>
      }
      =","                                                  # <7>
    }
    ="]"                                                    # <8>
  }
  return result
end
  1. The result will be a list of values
  2. The packet must begin with an open bracket
  3. Scan through the packet until we reach the close bracket
  4. If the next item is a digit, then read the number and add it to the result
  5. If instead we see the next item starts a list, then
  6. ... use the bal procedure to extract the part of the list with a matching pair of brackets, up to the ending comma or bracket
  7. Match any separating comma
  8. Match the closing bracket

type checking

The type of a value can be obtained using the type procedure. This returns a string, which can be one of "integer", "string", "list", etc.

Here, it is used to decide if part of the packet is a single number or a sublist:

    if "integer" == type(left_list[index]) then {
      if "integer" == type(right_list[index]) then { # both are integers
        # compare two integers
      } else { # other value must be a list
        # up-grade the left-value to a list, and repeat the comparison
      }
    } else if "list" == type(left_list[index]) then {
      if "list" == type(right_list[index]) then { # both are lists
        # compare two lists
      } else { # other value must be an integer
        # up-grade the right-hand value to a list, and repeat the comparison
      }
    }

Final Program

procedure main(inputs)
  local filename

  if *inputs = 1 then {
    filename := inputs[1]

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

procedure part_1(filename)
  local i, packets, sum_indices

  packets := read_data(filename)
  sum_indices := 0
  every i := 1 to *packets do {
    if is_right_order(packets[i]) then
      sum_indices +:= i
  }

  return sum_indices
end

procedure part_2(filename)
  local packets, packet_pair, packet_pairs
  local divider_a, divider_b, divider_a_index, divider_b_index
  local i, j

  packet_pairs := read_data(filename)
  packets := list()

  # add the two divider packets
  divider_a := [[2]]
  divider_b := [[6]]
  put(packets, divider_a)
  put(packets, divider_b)

  # add all the other packets
  every packet_pair := !packet_pairs do {
    put(packets, packet_pair.a)
    put(packets, packet_pair.b)
  }

  # bubble sort the packets
  every i := 1 to *packets-1 do
    every j := 2 to *packets-i+1 do
      if compare_packets(packets[j], packets[j-1]) < 0 then
        packets[j] :=: packets[j-1]

  # locate the divider indices
  divider_a_index := 0
  divider_b_index := 0
  every i := 1 to *packets do {
    if packets[i] === divider_a then divider_a_index := i                 # <1>
    if packets[i] === divider_b then divider_b_index := i
  }

  return divider_a_index * divider_b_index
end

procedure is_right_order(packet)
  return compare_packets(packet.a, packet.b) < 0
end

# Returns -1 if left_list is "less than" right_list, 0 if equal, else +1
procedure compare_packets(left_list, right_list)
  local comparison, index

  every index := 1 to *left_list do {
    if index > *right_list then { # right list is shorter
      return 1
    } else if "integer" == type(left_list[index]) then {                  # <2>
      if "integer" == type(right_list[index]) then { # both are integers
        if left_list[index] < right_list[index] then {
          return -1
        } else if left_list[index] > right_list[index] then {
          return 1
        }
      } else { # other value must be a list
        left_list := copy(left_list)                                      # <3>
        left_list[index] := [left_list[index]]                            # <4>
        return compare_packets(left_list, right_list)
      }
    } else if "list" == type(left_list[index]) then {
      if "list" == type(right_list[index]) then { # both are lists
        comparison := compare_packets(left_list[index], right_list[index])
        if 0 ~= comparison then return comparison
      } else { # other value must be an integer
        right_list := copy(right_list)
        right_list[index] := [right_list[index]]
        return compare_packets(left_list, right_list)
      }
    }
  }
  # equal so far, so result depends on if lists are equal size or right list longer
  if *left_list = *right_list then
    return 0
  else
    return -1 # left list is shorter
end

procedure read_data(filename)
  local current_packet, file, line, packets

  packets := list()
  file := open(filename, "r") | stop("Cannot open ", filename)
  current_packet := packet_pair()
  every line := !file do {
    if /current_packet.a then # first line                                # <5>
      current_packet.a := parse_packet(line)
    else if /current_packet.b then { # second line
      current_packet.b := parse_packet(line)
      put(packets, current_packet)
    } else { # blank line
      current_packet := packet_pair()
    }
  }

  close(file)

  return packets
end

# Holds a pair of inputs
record packet_pair(a, b)

# Parses a packet as a string into a list of lists
procedure parse_packet(packet)
  local result

  result := list()
  packet ? {
    ="["
    until any(']') do {
      if any(&digits) then {
        put(result, integer(tab(many(&digits))))
      } else if any('[') then {
        put(result, parse_packet(tab(bal(',]','[',']'))))
      }
      =","
    }
    ="]"
  }
  return result
end
  1. We can use ===, value identity, for finding the divider.
  2. type returns the type of an object, as a string.
  3. The list is copied before modification, so the original value does not change.
  4. Promote the integer value into a list, for the comparison.
  5. The '/' operator checks if the given value is null: we use this to complete parts of the packet in turn.

Page from Peter's Scrapbook, output from a VimWiki on 2024-01-29.