Day seven of this year’s Advent of Code asks us to find the order in which we must complete a set of steps in a directed graph. Let’s see how well we can do with this task using the J programming language!

My high level plan of attack for this task is to keep each pair of dependencies in their current structure. I’ll build a verb that takes a list of “completed” steps, and the list of pairs relating to uncompleted steps. My verb will find the first (alphabetically) step that doesn’t have an unmet dependency in our list, append that step to our list of completed steps, and remove all pairs that are waiting for that step being completed.

Thankfully, parsing our input is easy today:

    parse =. (5 36)&{"1
    pairs =. |."1 parse input
AC
FC
BA
DA
EB
ED
EF

We can write a helper that takes our list of pairs and returns all of the steps referenced in them in a raveled list:

    steps =. [: /: [: . ,
    steps pairs
ABCDEF

Now we can write our verb that completes each step of our instructions:

    next =. 3 : 0
      done =. 0 {:: y
      pairs =. 1 {:: y
      steps =. steps pairs
      left =. {."1 pairs
      right =. {:"1 pairs
      next_step =. {. steps #~ -. steps e. ~. left
      next_pairs =. pairs #~ -. right e. next_step
      remaining_pairs =. pairs #~ right e. next_step

      append =. (done,next_step)"_
      return =. (done)"_
      next_step =. (append ` return @. (0 = # remaining_pairs)"_) _

      next_step;next_pairs
    )

I’m trying to be more explicit here, and rely less on tacit verbs. Last time I found myself getting lost and hacking together solutions that I didn’t fully understand. I’m trying to pull back and bit and do things more intentionally.

We can converge on the result of repeatedly applying next to our list of pairs and an empty starting set of completed steps:

    0{:: next^:_ '' ; pairs
CABDF

An unfortunate side effect of our algorithm is that our last step in our graph is never appended to our list. We need to find this step and append it ourselves:

    append_last =. 4 : 0
      steps =. steps x
      missing =. steps #~ -. steps e. ~. y
      y,missing
    )
    echo pairs append_last 0{:: next^:_ '' ; pairs
CABDFE

And that’s all there is to it!

Part Two

Part two was much more complicated than part one. Each step takes a specified amount of time to complete, and we’re allowed to work on each step with up to four workers, concurrently.

This was the hardest problem I’ve solved so far throughout this year’s Advent of Code. My general strategy was to modify my next verb (now called tick) to additionally keep track of steps that were actively being worked on by concurrent workers.

Every tick, I check if there are any available steps and any space in the worker queue. If there are, I move the step over. Next, I go through each step being worked on by each worker and subtract 1. If a step being worked on reaches 0 seconds of work remaining, I add it to the done list.

Eventually, this solution converges on my answer.

I’m not at all happy with my code. I found myself getting deeply lost in the shape of my data. After much struggling, I started to make heavy use of $ to inspect the shape of nearly everything, and I peppered my code with echo debug statements. The final solution is a nasty blob of code that I only just barely understand.

Enjoy.

Notes