Advent of Code: Inventory Management System

Written by Pete Corey on Dec 2, 2018.

Today’s Advent of Code challenge asks us to scan through a list of IDs, looking for IDs that two and three repeated letters. Once we have the total number of words with two repeated characters and three repeated characters, we’re asked to multiple them together to get a pseudo-checksum of our list of IDs.

At first I had no idea about how I would tackle this problem in J. After digging through the vocabulary sheet, I stumbled upon the monadic form of e. and I was shown the light.

The e.y verb iterates over every element of y, building a boolean map of where that element exists in y. We can use that result to group together each element from y. Once we’ve grouped each element, we can count the length of each group. Because J pads extra 0/' ' values at the end of arrays to guarantee filled matricies, we’ll measure the length of each group by finding the index of this padding character in every group. Finally, we can see if 2 and 3 exists in each set of character counts, and sum and multiply the results.

    read_lines =. >@:cutopen@:(1!:1) <
    lines =. read_lines '/Users/pcorey/advent_of_code_2018/day_02/input'

    group =. ([: ~. e.) # ]
    count =. [: i."1&' ' group"1
    twos_and_threes =. [: (2 3)&e."1 count

    */ +/ twos_and_threes lines

I’ve been trying to make more use of forks, hooks, and verb trains after reading through Forks, Hooks, and Compound Adverbs and Trains on the J website.

Part Two

Part two asks us the find two IDs that differ by only a single letter. Once we’ve found those two IDs, we’re to return the set of letters they have in common.

My basic idea here was to compare every possible word combination and pack up the two compared words with the number of differences between them:

    compare =. 4 : 0
      differences =. x ([: +/ [: -. =) y
      differences;x;y
    )

    comparisons =. ,/ input compare"1/ input

Using that, we could pick out the set of word pairs that have one difference between them:

    ones =. 1&= 0&{::"1 comparisons

Unbox the word pairs from that set:

    words =. > }."1 ones # comparisons

And then use an inverted nub sieve to find the letters those words share in common, using another nub to filter out the duplicate caused by the inverse comparison:

    ([: . (-.@:: # ])"1/) words

I’ll admit, I found myself getting lost in what felt like a sea of boxes and arrays while working on this solution. I found it difficult to keep track of where I was in my data, and found myself building intermediate solutions in the REPL before moving them over to my project. I need to get better at inspecting my data and getting a feel for how to manipulate these structures in J.

I also found myself heavily relying on the REPL for building my verb chains. I constantly found myself building chains by trail and error.

Does this work? No? Maybe if I add a cap at the end? Yes!

I can handle single hooks and forks, but when things expand beyond that I find myself getting lost. I’m hoping I get better with that over time.

Notes

  • Trying to open a box that holds numbers and string will throw a domain error, because the two types can’t live together in an array.

Advent of Code: Chronal Calibration

Written by Pete Corey on Dec 1, 2018.

I’ve been a huge fan of the Advent of Code challenges since I first stumbled across them a few years ago. Last year, I completed all of the 2017 challenges using Elixir. This year, I decided to challenge myself and use a much more esoteric language that’s held my interest for the past year or so.

It’s my goal to complete all of this year’s Advent of Code challenges using the J programming language.

Before we get into this, I should make it clear that I’m no J expert. In fact, I wouldn’t even say that I’m a J beginner. I’ve used J a handful of times, and repeatedly struggled under the strangeness of the language. That being said, there’s something about it that keeps pulling me back. My hope is that after a month of daily exposure, I’ll surmount the learning curve and get something valuable out of the experience and the language itself.


The first Advent of Code challenge of 2018 asks us to read in a series of “changes” as input, and apply those changes, in order, to a starting value of zero. The solution to the challenge is the value we land on after applying all of our changes. Put simply, we need to parse and add a list of numbers.

The first thing I wanted to do was read my input from a file. It turns out that I do know one or two things about J, and one of the things I know is that you can use foreigns to read files. In particular, the 1!:1 foreign reads and returns the contents of a file.

Or does it?

    1!:1 'input'
file name error

Apparently 1!:1 doesn’t read relative to the current script. I’m guessing it reads relative to the path of the jconsole executable? Either way, using an absolute path fixes the issue.

    input =. 1!:1 < '/Users/pcorey/advent_of_code_2018/day_01/input'

Now input is a string with multiple lines. Each line represents one of our frequency changes. We could use ". to convert each of those lines into a number, but because input is a single string, and not an array of lines, can’t map ". over input:

    0 "./ input
0

After scrambling for ways of splitting a string into an array of lines, I stumbled across cutopen, which takes a string and puts each line into a box. That’s helpful.

    boxed =. cutopen input
┌──┬──┬──┬──┐
│+1│-2│+3│+1│
└──┴──┴──┴──┘

Now if we open boxed, we’ll have our array of lines:

    lines =. > boxed
+1
-2
+3
+1

And now we can map ". over that array to get our array of numbers.

    numbers =. 0 "./ lines
1 _2 3 1

And the answer to our problem is the sum of numbers.

    +/ numbers
3

Here’s my first working solution:

    input =. 1!:1 < '/Users/pcorey/advent_of_code_2018/day_01/input'
    boxed =. cutopen input
    lines =. > boxed
    numbers =. 0 "./ lines
    +/ numbers

Part Two

My first instinct for solving this problem is to do it recursively. I might be able to define a dyadic verb that accepts my current list of frequencies and a list of changes. If the last frequency in my array exists earlier in the array, I’ll return that frequency. Otherwise, I’ll append the last frequency plus the first change to my frequencies array, rotate my changes array, and recurse.

After many struggles, I finally landed on this solution:

    input =. 1!:1 < '/Users/pcorey/advent_of_code_2018/day_01/sample'
    boxed =. cutopen input
    lines =. > boxed
    numbers =. 0 "./ lines

    change_frequency =. 4 : 0
      frequency =. {: x
      change =. {. y
      frequency_repeated =. frequency e. (}: x)
      next_x =. x , (frequency + change)
      nexy_y =. 1 |. y
      next =. change_frequency ` ({:@}:@[) @. frequency_repeated
      next_x next next_y
    )

    0 change_frequency numbers

This works great for example inputs, but blows the top off my stack for larger inputs. It looks like J’s max stack size is relatively small. Recursion might not be the best approach for these problems.

Looking into other techniques for working without loops, I learned that you can use the ^:_ verb to “converge” on a result. It will repeatedly apply the modified verb until the same result is returned.

I refactored my verb to take and return my frequencies array and my changes array as a boxed tuple, and converge on that verb until I get a repeated result. That repeated result holds my repeated frequency:

    input =. 1!:1 < '/Users/pcorey/advent_of_code_2018/day_01/sample'
    boxed =. cutopen input
    lines =. > boxed
    numbers =. 0 "./ lines

    package_next =. 4 : 0
      (x,({:x)+({.y));(1|.y)
    )

    package_result =. 4 : 0
      x;y
    )

    change =. 3 : 0
      frequencies =. >@{. y
      changes =. >@{: y
      frequency =. {: frequencies
      change =. {. changes
      repeated =. frequency e. (}: frequencies)
      next =. package_next ` package_result @. repeated
      frequencies next changes
    )

    result =. change^:_ (0;numbers)
    echo 'Repeated frequency:'
    {:@:{.@:> result

Notes

  • $: doesn’t seem to refer to the outermost named verb. Recursion wasn’t working as I expected with $:. Replacing it with the named verb worked perfectly.
  • J seems to have a short stack. Note to self: avoid deep recursion.
  • J doesn’t support tail call optimization.
  • ^:_ and variants can be used as an iterative alternative to recursion.
  • Use boxes like tuples.
  • Use echo for debug printing.

Elixir Mix

Written by Pete Corey on Nov 19, 2018.

I was lucky enough, recently, to be given the opportunity to speak with Mark Ericksen and Josh Adams on an episode of Elixir Mix. We covered a wide range of Elixir-related topics like binary manipulation and pattern matching, Erlang’s extensive standard library, and property-based testing.

A good portion of our time together was spent going over the progress I’ve made implementing my in-progress Bitcoin full node. I think the fact that we had so much to talk about in the context of that project goes to show that it’s a fantastic platform to show off many of Elixir’s strengths. Discussing it with Mark and Josh rekindled my fire for the project, and I’m hoping to make more progress soon!

We also talked a bit about playing guitar and Chord, my current Elixir-based passion project.

I highly recommend you check out the podcast, and sign up to hear more from Mark, Josh, and the entire Elixir Mix crew. Also, be sure to check out my “pick”, The Sparrow by Mary Doria Russell, if you’re into science fiction and you’re looking for a new book to read. I’m still thinking about the book weeks after finishing it.

Thanks again for having me on!