Advent of Code - Day 9

JEG2 · December 9, 2018, 11:29pm

Note: This topic is to talk about Day 9 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.

JEG2 · December 9, 2018, 11:36pm

Here’s my solution to Day 9:

JEG2/advent_of_code_2018/blob/master/day_09/marble_mania.exs

defmodule MarbleMania do
  defstruct players: nil,
            last_play: nil,
            circle: %{0 => {0, 0}},
            turn: 1,
            current_marble: 0,
            player: 1,
            scores: Map.new

  def init(stream) do
    {Enum.to_list(stream), %__MODULE__{ }}
  end

  def process(game, state) do
    state
    |> define_game(game)
    |> play_game
  end

  defp define_game(state, game) do

This file has been truncated. show original

Inspired by @josevalim, I live streamed the creation of it for the first time. You can watch the video here (until it falls off Twitch 14 days from now):

The main idea is just that I hand-rolled a doubly linked list and used that to solve both problems. It does part two in a little under a minute. I’m looking forward to seeing how others do it faster.

sasajuric · December 10, 2018, 5:56am

This is my solution to day 9. On my machine it takes some 3.5 sec for the second part. The key idea in my solution is to use zippers to implement a circular list.

davydog187 · December 10, 2018, 12:59pm

Here’s my naive solution use a single list. The implementation was too slow to solve the second part. https://github.com/davydog187/advent_of_code/blob/master/advent_elixir/lib/advent_elixir/day_9.ex

sfusato · December 10, 2018, 4:46pm

I liked your implementation of a linked-list as a Map structure. Also, the way you’ve found the 7th marble counter clockwise from the current one using Stream.iterate was awesome. I need to get acquainted with the Stream module more that’s for sure. I’ve enjoyed your stream. Thank you!

My very naive implementation wouldn’t complete Part 2 within the time I was willing to wait for it to do so. I got Part 1 and the given tests passing, so I’m cool with that.

poligen · December 12, 2018, 9:41am

Thank you so much to reply here !!@sasajuric. It is the most important key to solve this problem using your zipper list. I learn a lot from this zippers.

simon · December 29, 2018, 4:32pm

My solution is here and it calculates the part 2 solution in about 30 seconds.

I need to now look at what others have done but I think I was on roughly the right track by creating a map where the key is the turn number and the value is a struct containing the previous and next keys so that you can step forwards and backwards from the current marble.

My code to update the struct isn’t terribly concise and that may be a good place for performance improvements but @sasajuric’s solution seems to be the one I need to look at in depth as well as the aforementioned zippers.