Advent of Code - Day 10

I find today’s task a bit fuzzy. I first considered shrinking the universe to the smallest possible perimeter. However, I wasn’t happy with that idea, because it’s possible that the universe expands (rather than shrinks) to the desired message (e.g. if all points are originally at (0, 0) and in the next step they expand to the message).

Therefore I opted for an approach where I look for the first occurrence of horizontally aligned clusters. In each step I compute the clusters, where each cluster consists of all neighbouring points. The algorithm stops when all the clusters have exactly the same vertical bounds (ymin, ymax).

Solution is available here and it finishes in about 4.5s.

After a weekend away from my computer I need to catch-up on the previous few puzzles but I decided to tackle today’s because it looked interesting (and involved outputting more than just an answer.

Unlike @sasajuric I decided to take a chance and assumed that the universe would contract to form the word and then expand so I check for when the next layout’s bounds are bigger to get the word (I really didn’t consider it expanding!). I suppose that the safe compromise might be to do the first adjustment and see if the universe expands or contracts and then follow that pattern.

Anyway, my code is here.

I think that a scenario could be constructed where the universe first has to fully shrink, and the message appears in some subsequent expansion (probably 1-2 steps after shrinking).

I also think my algorithm is not bulletproof. Even if all the clusters are perfectly aligned, it doesn’t necessarily means that they represent letters (e.g. perhaps the clusters are rectangles which will in the next step all morph into the letter I). Maybe a better way would be to try to decode each group into a letter (e.g. by summing horizontal points), but for that we’d need to know the exact dimensions of each letter.

As can be seen, the task leaves some questions open, which is why I said that I find it somewhat fuzzy.

I’m going for an initial naive solution to the puzzle, but it keeps crashing when using the test input:

eheap_alloc: Cannot allocate 3280272216 bytes of memory (of type "heap").

Crash dump is being written to: erl_crash.dump...done

My approach is as naive as can be: take the input, and draw a “window” of the grid. The idea being that I can initially move the window around to frame the message before implementing a more automated solution.

I have no idea why it’s running out of memory, as the only recursive function (animate/2) is tail recursive. As I said, the solution is extremely naive (e.g. should probably use IOLists), but I don’t see why it would be crashing with the minimal test input.

Here is what I’m executing in iex:

iex(1)> string = """                                              
...(1)> position=< 9,  1> velocity=< 0,  2>
...(1)> position=< 7,  0> velocity=<-1,  0>
...(1)> position=< 3, -2> velocity=<-1,  1>
...(1)> position=< 6, 10> velocity=<-2, -1>
...(1)> position=< 2, -4> velocity=< 2,  2>
...(1)> position=<-6, 10> velocity=< 2, -2>
...(1)> position=< 1,  8> velocity=< 1, -1>
...(1)> position=< 1,  7> velocity=< 1,  0>
...(1)> position=<-3, 11> velocity=< 1, -2>
...(1)> position=< 7,  6> velocity=<-1, -1>
...(1)> position=<-2,  3> velocity=< 1,  0>
...(1)> position=<-4,  3> velocity=< 2,  0>
...(1)> position=<10, -3> velocity=<-1,  1>
...(1)> position=< 5, 11> velocity=< 1, -2>
...(1)> position=< 4,  7> velocity=< 0, -1>
...(1)> position=< 8, -2> velocity=< 0,  1>
...(1)> position=<15,  0> velocity=<-2,  0>
...(1)> position=< 1,  6> velocity=< 1,  0>
...(1)> position=< 8,  9> velocity=< 0, -1>
...(1)> position=< 3,  3> velocity=<-1,  1>
...(1)> position=< 0,  5> velocity=< 0, -1>
...(1)> position=<-2,  2> velocity=< 2,  0>
...(1)> position=< 5, -2> velocity=< 1,  2>
...(1)> position=< 1,  4> velocity=< 2,  1>
...(1)> position=<-2,  7> velocity=< 2, -2>
...(1)> position=< 3,  6> velocity=<-1, -1>
...(1)> position=< 5,  0> velocity=< 1,  0>
...(1)> position=<-6,  0> velocity=< 2,  0>
...(1)> position=< 5,  9> velocity=< 1, -2>
...(1)> position=<14,  7> velocity=<-2,  0>
...(1)> position=<-3,  6> velocity=< 2, -1>
...(1)> """

iex(2)> Advent.run(string, {60, 60})

Where 60 x 60 is the size of the section of grid to render.

Here’s the code:

defmodule Advent do
  @moduledoc """
  Documentation for Advent.
  """

  defmodule Parser do
    import NimbleParsec

    value =
      ignore(optional(string(" ")))
      |> optional(string("-"))
      |> integer(min: 1)

    defparsec :line,
      ignore(string("position=<"))
      |> concat(value)
      |> ignore(string(", "))
      |> concat(value)
      |> ignore(string("> velocity=<"))
      |> concat(value)
      |> ignore(string(", "))
      |> concat(value)
  end

  def run(input \\ input(), {grid_width, grid_height}, {offset_x, offset_y} \\ {0, 0}) do
    input
    |> parse_input()
    |> shift_grid_center(grid_width, grid_height, offset_x, offset_y)
    |> animate({grid_width, grid_height})
  end

  defp animate(lights, grid_dimensions) do
    render(lights, grid_dimensions)

    IO.gets "\n\nPress enter to tick once"

    lights
    |> tick()
    |> animate(grid_dimensions)
  end

  def tick(lights, count \\ 1) do
    Enum.map(lights, fn %{coord: {x, y}, velocity: {vx, vy}} = l ->
      %{l | coord: {x + count * vx, y + count * vy}}
    end)
  end

  defp input(), do: File.read!("./lib/input.txt")

  # shift all coords so that the top left corner will be refered to a 0,0 but
  # the "real" 0,0 will be in center of grid
  defp shift_grid_center(lights, x, y, offset_x, offset_y) do
    x_shift = div(x, 2) + offset_x
    y_shift = div(y, 2) + offset_y

    Enum.map(lights, fn %{coord: {x, y}} = l -> %{l | coord: {x + x_shift, y + y_shift}} end)
  end

  def parse_input(string) when is_binary(string) do
    string
    |> String.split("\n", trim: true)
    |> Enum.map(&parse/1)
  end

  def parse(string) when is_binary(string) do
    {:ok, results, _, _, _, _} = Advent.Parser.line(string)

    {coord, rest} = get_coordinate_pair(results, [])
    {velocity, _} = get_coordinate_pair(rest, [])

    %{coord: coord, velocity: velocity}
  end

  def render(lights, {grid_x, grid_y}) do
    lights = crop(lights, grid_x, grid_y)

    for y <- 0..grid_y - 1 do
      lights
      |> get_coords_for_line(y)
      |> render_line(grid_x)
      |> IO.inspect()
    end
  end

  defp crop(lights, grid_x, grid_y) do
    Enum.filter(lights, fn %{coord: {x, y}} ->
      x >= 0 && x <= grid_x - 1 && y >= 0 && y <= grid_y - 1
    end)
  end

  defp get_coords_for_line(lights, line) do
    lights
    |> Enum.filter(fn %{coord: {_x, y}} -> y == line end)
    |> Enum.map(fn %{coord: c} -> c end)
  end

  defp render_line(coords, line_width) do
    coords
    |> Enum.map(fn {x, _} -> x end)
    |> Enum.sort()
    |> generate_points(line_width - 1, {[], 0})
    |> Enum.join("")
  end

  defp generate_points([], max_x, {points, current_position}) when current_position > max_x, do: Enum.reverse(points)

  defp generate_points([x_coord | rest], max_x, {points, x_coord}) do
    generate_points(rest, max_x, {["#" | points], x_coord + 1})
  end

  defp generate_points(x_coords, max_x, {points, current_position}) do
    generate_points(x_coords, max_x, {["." | points], current_position + 1})
  end

  defp get_coordinate_pair(rest, [y, x | []]), do: {{x, y}, rest}

  defp get_coordinate_pair([i | t], acc) when is_integer(i), do: get_coordinate_pair(t, [i | acc])

  defp get_coordinate_pair(["-", i | t], acc) when is_integer(i), do: get_coordinate_pair(t, [i * (-1) | acc])
end

This will render the first frame, but after pressing “enter” at the prompt, it will freeze in the middle of rendering the 2nd frame, then run out of memory…

For me a few of the tasks have been like that but I’ve been treating some of them as I would with unit tests and just working towards a solution rather than trying to cover all possibilities.

However, despite the grumbles, it’s an astonishing achievement for someone to put the project together for us all.

Here’s my solution to Day 10:

https://github.com/JEG2/advent_of_code_2018/blob/master/day_10/the_stars_align.exs

I live streamed the creation of this. You can watch the video here (until it falls off Twitch 14 days from now):

This was my approach as well. Assume the word is formed right before the first universe expansion.

My solution is here (~2.8s).

Lots of tests, but turned out pretty good with the help of James!

https://github.com/snewcomer/advent-of-code-elixir/blob/master/day10/lib/day10.ex