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!

Property Testing a Permutation Generator

Written by Pete Corey on Nov 19, 2018.

Last time we spent some time writing a function to generate permutations of length k of a given list. Our final solution was fairly concise, but there are quite a few places where we could have made a mistake in our implementation.

Our first instinct might be to check our work using unit tests. Unfortunately using unit tests to check the correctness of a permutation generator leaves something to be desired. The length of our resulting set of permutations grows rapidly when k and list increase in size, making it feasible to only manually calculate and test the smallest possible permutations.

Thankfully there’s another way. We can use property testing to test the underlying properties of our solution and the permutations we’re generating. This will give us quite a bit more variation on the inputs we test and might uncover some hidden bugs!

Our Permutation Generator

The permutation generator that we’ll be testing looks like this:


defmodule Permutation do
  def generate(list, k \\ nil, repetitions \\ false)
  def generate([], _k, _repetitions), do: [[]]
  def generate(_list, 0, _repetitions), do: [[]]

  def generate(list, k, repetitions) do
    for head <- list,
        tail <- generate(next_list(list, head, repetitions), next_k(k)),
        do: [head | tail]
  end

  defp next_k(k) when is_number(k),
    do: k - 1

  defp next_k(k),
    do: k

  defp next_list(list, _head, true),
    do: list

  defp next_list(list, head, false),
    do: list -- [head]
end

You’ll notice that it’s a little different than the generator we built last time. This generator supports the creation of permutations both with and without repetitions of elements from list, and lets you optionally pass in the length of the final permutations, k.

We can use our Permutation.generate/3 function like so:


iex(1)> Permutation.generate([1, 2, 3])
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

We can also specify a value for k:


iex(2)> Permutation.generate([1, 2, 3], 2)
[[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]

And we can tell our generator to allow repetitions in the final permutations:


iex(3)> Permutation.generate([1, 2, 3], 2, true)
[[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]]

All looks good so far, but dragons hide in the depths. Let’s dig deeper.

List of Lists

Permutations have some fairly well-known and easily testable properties. For example, we know that the results of our calls to Permutation.generate/3 should always have the structure of a list of lists.

Using Elixir’s StreamData package, we can easily model and check that this property holds for our Permuatation.generate/3 function across a wide range of inputs. Let’s start by creating a new property test to verify this for us:


property "returns a list of lists" do
end

We start by telling StreamData that we want it to generate lists of, at most, @max_length (which we’ll define at 5 for now) integers.


property "returns a list of lists" do
+  check all list <- list_of(integer(), max_length: @max_length) do
+  end
end

Next, we call our Permutation.generate/3 function to create the permutations of the list that was just generated for us:


  property "returns a list of lists" do
    check all list <- list_of(integer(), max_length: @max_length) do
+      permutations = Permutation.generate(list)
    end
  end

Finally we’ll make assertions about the structure of our resulting permutations. We want to assert that the result of our call to Permutation.generate/3 is a list, but also that every element in that result is a list as well:


property "returns a list of lists" do
  check all list <- list_of(integer(), max_length: @max_length) do
    permutations = Permutation.generate(list)
+    assert permutations |> is_list
+    Enum.map(permutations, &assert(&1 |> is_list))
  end
end

And that’s all there is to it. Running out test suite, we’ll see that our first property test passed with flying colors (well, mostly green).

.

Finished in 0.06 seconds
1 property, 0 failures

Correct Number of Permutations

Now that we know that the structure of our resulting list of permutations is correct, the next obvious property that we can test is that the number of permutations returned by our Permutation.generate/3 function is what we’d expect.

Permutations are a well-defined mathematical concept, and so a nice equation exists to determine how many k-length permutations exist for a list of n elements:


P(n, k) = n! / (n - k)!

Let’s write a quick factorial function to help calculate this value:


defp factorial(n) when n <= 0,
  do: 1

defp factorial(n),
  do: n * factorial(n - 1)

Let’s also rewrite our P(n, k) calculation as an Elixir helper function:


  defp pnk(list, k),
    do: div(factorial(length(list)), factorial(length(list) - k))

Great!

Now we’re set up to test that our Permutation.generate/3 function is giving us the correct number of permutations for a given list and value of k.


property "returns the correct number of permutations" do
end

This time we’ll generate our list, along with a value for k that ranges from 0 to the length of list:


property "returns the correct number of permutations" do
+  check all list <- list_of(integer(), max_length: @max_length),
+            k <- integer(0..length(list)) do
  end
end

Once we have values for list and k, we can generate our set of permutations and make an assertion about its length:


property "returns the correct number of permutations" do
  check all list <- list_of(integer(), max_length: @max_length),
            k <- integer(0..length(list)) do
+    assert pnk(list, k) ==
+            list
+            |> Permutation.generate(k)
+            |> length
  end
end

Once again, our tests pass.

..

Finished in 0.06 seconds
2 properties, 0 failures

Only Include Elements From the List

Another neatly testable property of the permutations we’re generating is that they should only contain values from the list being permutated. Once again, we’ll start by defining the property we’ll be testing and generate our values for list and k:


property "permutations only include elements from list" do
  check all list <- list_of(integer(), max_length: @max_length),
            k <- integer(0..length(list)) do
  end
end

Next, we’ll want to generate our set of permutations for list and k, and reject any permutations from that set that include values not found in list:


property "permutations only include elements from list" do
  check all list <- list_of(integer(), max_length: @max_length),
            k <- integer(0..length(list)) do
+    assert [] ==
+              list
+             |> Permutation.generate(k)
+             |> Enum.reject(fn permutation ->
+                [] ==
+                  permutation
+                 |> Enum.reject(&Enum.member?(list, &1))
+              end)
  end
end

We’re asserting that the resulting list of permutations should be an empty list ([]). There should be no permutations left that contain elements not found in list!

And, as expected, our suite still passes.

...

Finished in 0.08 seconds
3 properties, 0 failures

Use Each Item Once

Our current implementation of Permutation.generate/3 allows for duplicate items to be passed in through list. When we generate each possible permutation, it’s important that each of these duplicate items, and more generally any item in the list, only be used once.

That is, if list is [1, 2, 2], our set of possible permutations should look like this:


[[1, 2, 2], [1, 2, 2], [2, 1, 2], [2, 2, 1], [2, 1, 2], [2, 2, 1]]

Note that 2 is used twice in each permutation, but never more than twice.

At first, it seems like we might need a new test to verify this property of our permutation generator. It’s conceivable that we could group each set of equal elements, count them, and verify that the resulting permutation have the correct count of each element group. But that sounds complicated, and an added test just introduces more code into our codebase that we need to maintain.

It turns out that we can tweak our previous property test to verify this new property.

Instead of identifying duplicates, counting them, and verifying the correct counts in the final set of permutations, let’s take a simpler approach. Let’s ensure that each element in list is unique by using Elixir’s Enum.with_index/1 function to bundle the element with its index value.

For example, our previous [1, 2, 2] value for list would be transformed into:


[{1, 0}, {2, 1}, {2, 2}]

Now both of our 2 elements are unique. The first is {2, 1}, and the second is {2, 2}. Using this technique, we can recycle our “permutations only include elements from list” with a few slight tweaks:


  property "permutations only include elements from list" do
    check all list <- list_of(integer(), max_length: @max_length),
              k <- integer(0..length(list)) do
      assert [] ==
               list
+              |> Enum.with_index()
               |> Permutation.generate(k)
               |> Enum.reject(fn permutation ->
                 [] ==
                   permutation
-                  |> Enum.reject(&Enum.member?(list, &1))
+                  |> Enum.reject(&Enum.member?(list |> Enum.with_index(), &1))
               end)
    end
  end

And once again, our suite passes:


...

Finished in 0.08 seconds
3 properties, 0 failures

Final Thoughts

The current version of our property tests currently only test values of list composed entirely of integers. This doesn’t necessarily need to be the case. The list being permutated can contain literally anything, in theory. Expanding our property tests to support a wider range of types might be a great opportunity to try out writing a custom generator function!

Our current test suite also defines @max_length as 5. While testing, I noticed that values of @max_length up to 8 were very performant and finished in under a second on my machine. Running the suite with a @max_length of 9 took several seconds to complete, and using a value of 10 took nearly two minutes to come back green. I’m not sure if these performance problems can easily be improved, but I’m happy about how obvious they became through property testing.

You’ll also note that none of this testing covers generating permutations that allow infinite repetitions of elements from list. The properties for these sets of permutations are completely different, so I’m going to leave this as an exercise for the truly motivated reader.

I’m enjoying my experiences with property testing so far. Hopefully you find these write-ups useful as well. If so, let me know on Twitter!