Note: This topic is to talk about Day 10 of the Advent of Code.
For general discussion about the Advent of Code 2018 and links to topics of the other days, see this topic.
1 Like
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.
2 Likes
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.
1 Like
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:
I live streamed the creation of this. You can watch the video here (until it falls off Twitch 14 days from now):
2 Likes
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!
