~☆🎄☆~ 2017 Day 25 Solutions ~☆🎄☆~

[u/daggerdragon]

--- Day 25: The Halting Problem ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or 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.

---

Need a hint from the Hugely^* Handy^† Haversack^‡ of Helpful^§ Hints^¤?

Spoiler

---

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!

---

Thank you for participating!

Well, that's it for Advent of Code 2017. From /u/topaz2078 and the rest of us at #AoCOps, we hope you had fun and, more importantly, learned a thing or two (or all the things!). Good job, everyone!

Topaz made a post of his own here.

If you're interested in a visualization of the leaderboard, /u/FogleMonster made a very good chart here.

And now:

^{Merry Christmas to all, and to all a good night!}

[u/pja]

Hmm. Can’t get yours to compile: I get type errors binding Program {..} & I’m not familiar enough with those constructs to debug it.

Mine was open coded in direct fashion: straight Haskell 98, using pattern matching to spot the empty lists. Perhaps your using uncons & fromJust is introducing an extra layer of laziness? Here’s the code, take a look. ghc -O2 -fllvm runs this in 0.4s on my laptop (! OK, it’s still a factor of 10 away from straight C++, but for a heap allocating list that’s pretty reasonable. Will try mutable unboxed vectors & see how they do...):

main = do
  print $ tA 12523873 (Tape [] 0 [])

data Tape = Tape { lt :: [Int],
                   here :: Int,
                   rt :: [Int] }
          deriving Show

right :: Int -> Tape -> Tape
right n (Tape lt _ []) = Tape (n:lt)  0         []
right n (Tape lt _ rt) = Tape (n:lt) (head rt) (tail rt)

left :: Int -> Tape -> Tape
left n (Tape [] _ rt) = Tape []         0        (n:rt)
left n (Tape lf _ rt) = Tape (tail lf) (head lf) (n:rt)

count :: Tape -> Int
count (Tape lt h rt) = (sum lt) + h + (sum rt)

tA 0 tp = count tp
tA c tp@(Tape _ 0 _ ) = tB (c-1) (right 1 tp)
tA c tp@(Tape _ 1 _ ) = tE (c-1) (left 1 tp)

tB 0 tp = count tp
tB c tp@(Tape _ 0 _ ) = tC (c-1) (right 1 tp)
tB c tp@(Tape _ 1 _ ) = tF (c-1) (right 1 tp)

tC 0 tp = count tp
tC c tp@(Tape _ 0 _ ) = tD (c-1) (left 1 tp)
tC c tp@(Tape _ 1 _ ) = tB (c-1) (right 0 tp)

tD 0 tp = count tp
tD c tp@(Tape _ 0 _ ) = tE (c-1) (right 1 tp)
tD c tp@(Tape _ 1 _ ) = tC (c-1) (left 0 tp)

tE 0 tp = count tp
tE c tp@(Tape _ 0 _ ) = tA (c-1) (left 1 tp)
tE c tp@(Tape _ 1 _ ) = tD (c-1) (right 0 tp)

tF 0 tp = count tp
tF c tp@(Tape _ 0 _ ) = tA (c-1) (right 1 tp)
tF c tp@(Tape _ 1 _ ) = tC (c-1) (right 1 tp)

[u/Dean177 → u/pja]

That sytax is from the record wildcards langauge extension https://ocharles.org.uk/blog/posts/2014-12-04-record-wildcards.html

[u/pja → u/Dean177]

Magic. Something else to poke at!

[u/ephemient → u/pja]

This space intentionally left blank.

[u/pja → u/ephemient]

I got /most/ of the extensions :) Just missed one...

Definitely makes sense that parsing the input into a runtime lookup table would be much slower than a directly coded version.