Avent of Code 2020 - Day 23

Learning Questions & Discussions Coding Challenges
,
1

This topic is about Day 23 of the Advent of Code 2020 .

Thanks to @egze, we have a private leaderboard:
https://adventofcode.com/2020/leaderboard/private/view/39276

The join code is:
39276-eeb74f9a

2

For this one I’ll go for a good old pen and paper to run the algorithm in order to find how the pieces fits together

A geat day to work with Stream !

3

Part 1 is simple with list but that would take forever to run part 2. I also tried paper and pencil to calculate as it seems to have some pattern, failed to this. Then I tried to speed up code of part 1,end up implementing a fast linked list.

1 Like
4

Bruteforce is the key !

5

I spent most of the day trying to find patterns in the input and also trying to optimize my solution. I found several ways to speed up the moves up to 250000 moves, but whatever I did after that, the solver slowed down to a crawl. I then scrapped my code and implemented a double linked list using a map.

Here is my solution.

UPDATE: I realized that there is no need to use a doubly-linked list. I have updated my code.

6

Really enjoyed today, learnt a lot from trying to figure out how to represent a linked list with immutable data structures without having to recreate large parts of the list when moving data.

Thanks @hvnsweeting for the perfect cut off in your post above that got me unstuck!

Ended up rewriting part 1 on the new code as it turned out more readable than my initial implementation, as well as being faster.

My code for today

7

Fell asleep last night. Here’s how I did the first part:

I think I missed a chance to apply some Stream-fu.

defmodule AdventOfCode.Y2020.Day23 do
  @input "467528193"
  @part_1_limit 100

  def run_1, do: process() |> play() |> labels_after(1)
  def run_2, do: {:not_implemented, 2}
  def process, do: Enum.map(String.graphemes(@input), &String.to_integer/1)

  def play(cups), do: play(cups, hd(cups), 1)
  def play(cups, _, @part_1_limit), do: cups

  def play(cups, current, move) do
    pick_ups = pick_up(cups, current)
    destination = destination(cups, pick_ups, current - 1)

    {init, [head | tail]} = Enum.split_while(cups -- pick_ups, &(&1 != destination))
    new_cups = init ++ [head | pick_ups] ++ tail

    play(new_cups, next(new_cups, current), move + 1)
  end

  def pick_up(cups, current) do
    {a, [_ | b]} = Enum.split_while(cups, &(&1 != current))
    Enum.take(b ++ a, 3)
  end

  def next(cups, current) do
    case Enum.split_while(cups, &(&1 != current)) do
      {[next | _], [_]} -> next
      {_, [_ | [next | _]]} -> next
    end
  end

  def destination(cups, pick_ups, from) do
    if from in pick_ups do
      destination(cups, pick_ups, from - 1)
    else
      {min, max} = Enum.min_max(cups)
      (from < min && destination(cups, pick_ups, max)) || from
    end
  end

  def labels_after(cups, label) do
    {a, [_ | b]} = Enum.split_while(cups, &(&1 != label))
    Enum.join(b ++ a)
  end
end
8

Still playing catch-up so just got around to this one. This was great, especially Part 2.

I’d be very interested to know people’s running times for Part 2.

I also did Part 1 using lists and Stream, which was elegant enough but completely unworkable for Part 2.

For Part 2, I felt we were sort of working around the immutable environment. I used :ets to implement a doubly-linked list to represent the circle (storing the previous and next elements). My implementation takes 22 seconds on my machine, so I’m interested if anyone got good performance without resorting to native code.

I used :ets because wanted to use something with constant insert time compared to map, which has log(n) insert time. I also considered :array, but the docs didn’t say anything about performance, whereas :ets promised constant time insert/retrieve operations, so I went with that. This was my first time using ETS :hugs:.

Day 23 Notes.

Sounds nice, but I ran your answer and it takes 40s on my machine, compared to 22s for my answer using :ets instead of maps. I think you’re right though, there’s no need to be able to traverse the list backwards so I over-engineered that too.

9

Solution using atomics: https://gist.github.com/bossek/c78d095ad9eab8192c508b3ee6d3afde

4 Likes
10

Getting rid of the back links reduced the running time from 80 seconds to 40 seconds on my computer as well as simplifying the code. I didn’t bother doing any more optimizations.

My implementation takes 22 seconds on my machine, so I’m interested if anyone got good performance without resorting to native code.

I have not tried it myself, but I would expect that using the atomics module would give a nice speedup.

3 Likes
11

That is 2.7 seconds on my computer. Nice! :+1: :rocket:

2 Likes
12

Well done @bossek, I had an impressive performance bump when switching from Map to :atomics (from 40sec to 2sec)

Here is my refactoring commit. Impressed on how such a few line change can make a big difference.

1 Like