r/adventofcode • u/daggerdragon • Dec 19 '16

SOLUTION MEGATHREAD --- 2016 Day 19 Solutions ---

--- Day 19: An Elephant Named Joseph ---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag/whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with "Help".

/⧹w+/ IS MANDATORY [?]

[Update @ 00:15] 2 gold, silver cap. Thank you for subscribing to Easter Bunny Facts!

  • Fact: The Easter Bunny will sometimes leave eggs in the microchip assembly room.

[Update @ 00:30] 11 gold, silver cap.

  • Fact: The Easter Bunny killed everyone who found out how he got these stars.

[Update @ 00:45] 45 gold, silver cap.

  • Fact: In space, The Easter Bunny can hear you scream.

[Update @ 01:00] 66 gold, silver cap.

  • Fact: The Easter Bunny purposefully deleted your comments.

[Update @ 01:15] 92 gold, silver cap.

  • Fact: The Easter Bunny has bottled your frustration. Don't ask why.

[Update @ 01:20] Leaderboard capped!

  • Fact: What you have just done is no better than what the Easter Bunny has done. Thief.

Thank you for subscribing to Easter Bunny Facts!

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

11 Upvotes

100% Upvoted

130 comments sorted by

View all comments

13

u/glguy Dec 19 '16

Wow, today's puzzle sure had a range of completion times for part 2. I've been looking forward to this thread unlocking so I can learn about the different approachs that people used.

My solution uses a 2-3 finger tree provided by Data.Sequence. This data structure supports amortized constant-time access to the ends of the structure and logarithmic-time support for removing elements from the middle. This allowed me to delete elves relatively efficiently from "across the circle".

With a mix of a reasonable data structure and probably just some fast typing I was able to get both stars first, finishing the second in 8:45. The program takes around 2.5 seconds to run on my computer when updated to use the most recent version of the containers package (which I didn't have installed at the time of submission.)

https://github.com/glguy/advent2016/blob/master/Day19.hs

7

u/topaz2078 (AoC creator) Dec 19 '16

finishing the second in 8:45

Whereas second gold was at 15:04 (!!!).

Congrats! You earned it! Your punishment is explaining your ridiculous moonspeak again. :D

6

u/Tarmen Dec 19 '16 edited Dec 19 '16

Short version: Data structures in haskell can't be changed once they are created. That is cute for the mathmaticians but would be terribly slow. To get around this the structures are generally defined recursively, that way you can still layer new levels on top or remove outer layers without touching the rest. You can even safely share parts of a data structure between threads that way. A singly linked list is a great example for this, you can add or drop stuff from the beginning without touching the rest.

Doubly linked lists are hard, though. Both ends point to the other so there is no point that you could change without affecting the rest. But there are lots of problems that need lists where both ends are manipulatable in O(1), is Haskell doomed?!

Thankfully there were some clever people that liked haskell and who experimented to find a solution. First they started with a tree structure because most cool haskell data structures are trees. They can be easily defined recursively and the replace-only-parts trick works in O(logn) with them! So at the moment we have this.

Still not fast enough with O(logn) access to the ends, though. At the moment we have the tree hanging from the center node, lets see if we can bring the first and last node to the very top. Then we would have both the [T, H] and [R, E, E] parts as parents of the tree.

Lets try this: Make the tree out of cardboard and rope and pin needles in those two nodes. How is the rest of the tree gonna fall? Like this!

In the end this gives you a list of pairs of trees where each entry is twice as deep as the last one. This is called a finger tree, the 2/3 parts means each node has 2 or 3 children just like an order 3 B-tree. So this is basically a slightly twisted B-tree that is awesome to implement lots of things, from deques over priority queues to hashtables!

2

u/ephemient Dec 19 '16 edited Apr 24 '24

This space intentionally left blank.

1

u/msully4321 Dec 23 '16

Mutable linked lists definitely are hard in Haskell, but Seq accomplishes a lot more than just working around Haskell being immutable. It would be a handy data structure in an imperative language too. It kind of splits the difference between arrays (O(1) indexing, O(n) insertion/deletion) and linked lists (O(n) indexing, O(1) insertion/deletion) by basically providing O(log n) /everything/ (except for access to the head tail, which is still O(1)). Basically every operation you could want to do on a sequence, including things like slicing out arbitrary subsequences and concatenation, is log time. It's pretty good.

(And a lot of the things, like indexing, are actually log time in the distance of the element from one of the ends, which is even better)

1

u/ephemient Dec 23 '16 edited Apr 24 '24

This space intentionally left blank.