Another fun day. As usual part 2 could not be brute forced so needed some lateral thinking.

Day 8 - Haunted Wasteland

See Day 8 for a detailed description of the problem.

To run the Jactl shown here save the code into a file (e.g. advent08.jactl) and run it like this (where advent08.txt is your input file from the Advent of Code site for Day 8):

$ cat advent08.txt | java -jar jactl-2.0.0.jar advent08.jactl 

Part 1

For day 8 we are given input that has the first line as a list of right/left moves (a series of R and L) followed by a list of nodes where each node describes which of the neighbours is their left neighbour and which is their right one.

For example:

RLLRRRLRL

AAA = (BBB,CCC)
BBB = (DDD,EEE)
CCC = (EEE,FFF)
...

The idea is to use the moves to move through the nodes from the staring node AAA until we get to node ZZZ and then output how many steps it took. If we run out of moves before we have reached ZZZ we cycle back to the start of the moves list.

The code looks like this:

def m = nextLine(); nextLine();
def nodes = stream(nextLine).map{ /(...) = .(...), (...)./r; [$1, [L:$2,R:$3]] } as Map
def cnt = 0
for (def n = 'AAA'; n != 'ZZZ'; n = nodes[n][m[cnt++ % m.size()]]) {}
cnt

At line 1 we read in the moves as a string and advance past the blank line.

Line 2 reads all the nodes and uses a regex to split out the neighbours. We generate a map of maps where each submap has two members keyed on 'L' and 'R'.

Line 4 then iterates from AAA until we get to ZZZ by looking up the neighbour of the current node based on the current move, incrementing cnt each time. We look up which move using the current cnt as an index after using % to make sure it wraps around if we get past the end of the moves string. Since node[n] is a map keyed on L and R we use the move as the key to look up which neighbour to move to and assign that to n.

Line 5 returns the cnt value.

Part 2

In part 2 there are multiple “ghosts” moving through the nodes. There is on ghost per starting node (which is now any node ending in A) and each ghosts moves until it reaches a node ending in Z.

We need to work out how many moves it will take for all ghosts to simultaneously be at a terminating node.

Since the number of moves it takes is different for each ghost we need to work out what the cycle length is for each ghost and then determine the least common multiple for these cycle lengths since at that point they will all be at a terminating node.

Note we assume that the cycle length for a ghost is not how many steps it takes to reach the first terminating node. In general, this does not have to be the case since the next node after the first terminating node could lead to another sequence finishing at yet another terminating node, and so forth. This would make the challenge much harder. Luckily the input we are given matches this assumption so we don’t have to deal with the more complex general problem.

Here is the code:

def m = nextLine(); nextLine();
def nodes = stream(nextLine).map{ /(...) = .(...), (...)./r; [$1, [L:$2,R:$3]] } as Map
03
def count(n) {
  def cnt = 0
  while (n !~ /Z$/) { n = nodes[n][m[cnt++ % m.size()]] }
  cnt
}
09
def pfactors(n, long start=2, factors=[]) {
  def p = (n.sqrt()-start+1).map{it+start}.filter{ n % it == 0 }.limit(1)[0]
  p ? pfactors(n/p,p,factors << p) : factors << n
}
14
def lcm(nums) {
  nums.map{ pfactors(it).reduce([:]){ m,it -> m[it as String]++; m } }
      .reduce([:]){ m,facts -> facts.each{ f,c -> m[f] = [m[f]?:0,c].max() }; m }
      .flatMap{ f,c -> c.map{ f as long } }
      .reduce(1L){ p,it -> p * it }
}
21
lcm(nodes.map{ it[0] }.filter{ /A$/r }.map{ count(it) })

We read in the input as per part 1 at lines 1 and 2.

At line 4 we have a function that counts the steps from a given starting node to any terminating node.

Line 10 declares a recursive function that determines the prime factors for a given number n, excluding 1, and excluding n unless n is itself prime. It iterates from the given starting number up until the square root of n looking for the first number p by which n is divisible. If we find such a number we add it to a list of factors and then add all factors of n/p by recursively calling ourselves. If there were no number p then we must be prime, so we add ourselves to the list and return that.

Line 15 declares the lcm(nums) function for finding the lowest common multiple of a list of numbers. It finds the prime factors of each number at line 16 and turns the list into a map of counts for each factor.

Then, at line 17 we combine the maps by finding, for each factor, the maximum count needed for each of the input numbers.

At line 18 we turn the map of these counts back into a list of factors where each factor appears the number of times corresponding to the maximum count calculated at line 17.

Then line 19 multiplies them altogether to get the least common multiple.

Line 22 finds all nodes ending in A and finds the cycle length for that node by invokeing count(it). Then this list of counts is passed to our lcm() function to calculate the least common multiple.