In case anybody hasn't seen it, the relevant Oglaf (NSFW)
I'm not fluent in Rust, but is this something like the C++ placement new? Presumably just declaring a table of Vecs won't automatically call the default constructor? (Sorry for my total ignorance -- pointers to appropriate reading material appreciated)
Nice use of foldMap!
Yep, that's it. (A totally scientific and non-fakeable measurement! /s)
I probably should have made it clearer this is a somewhat tongue-in-cheek proposal :)
You're quite right - pretty much any program can be golfed into a single line.
It isn't mentioned in the problem text but I suspect it's forced. (Argument by hand-waving ahead!)
In general, we have several paths that (at some point, but not necessarily the start) enter a cycle of length n~i~, with a goal state at offset a~i~. (There could be more than one goal state in a cycle, which would make the problem more complex, but this wasn't the case for my input).
If the cycle lengths were coprime (no common factor greater than 1), then this would simply be a case of applying the Chinese Remainder Theorem. This came up in 2016 day 15. However in this case, all paths use the same steps, so the cycle lengths share a factor with the number of steps in the input (in my case a prime number).
This pretty much (handwave!) forces the offsets a~i~ to be 0 (mod n~i~), otherwise we'd skip over some of the goal states however long the combined "big" cycle is. In other words, the goal states are in the "last" position of each cycle. If you assume that this is the case, then the problem becomes finding some t such that n~i~ = 0 (mod t) -- that is, the least common multiple.
So, yes, in a sense we were both "lucky" with our inputs, but it seems to be necessary for a solution to exist. That kind of proof seems a bit much for an Advent problem, though!
Haskell
A rather opaque parser, but much shorter than I could manage with Parsec.
import Data.Bifunctor
import Data.List.Split
import Data.Map.Strict (Map)
import qualified Data.Map.Strict as Map
import Data.Tuple
readGame :: String -> (Int, [Map String Int])
readGame = bimap (read . drop 5) (map readPull . splitOn "; " . drop 2) . break (== ':')
where
readPull = Map.fromList . map (swap . bimap read tail . break (== ' ')) . splitOn ", "
possibleWith limit = and . Map.intersectionWith (>=) limit
main = do
games <- map (fmap (Map.unionsWith max) . readGame) . lines <$> readFile "input02"
let limit = Map.fromList [("red", 12), ("green", 13), ("blue", 14)]
print $ sum $ map fst $ filter (possibleWith limit . snd) games
print $ sum $ map (product . snd) games
Got my first programming experience on the BBC Micro at school! (We never had anything as fancy as a Master though). Those heavy cube monitors and the "beep-boop" startup sound are iconic.
Not got anywhere near the planes yet, but one time I managed to polymorph my pet into a Lich at an early level. Oh, what luck! Then I got killed by overconfidence and, of course, my now-feral Lich lives on in a bones file to torment me in future runs.
Yes, CTEs are awesome. Especially when you don't force materialization and the optimizer can work its magic.
I've had a lot of fun with window functions as well.
It's fascinating to read these in-depth retrospectives from the people who were actually involved.
Oh, that's fun! (And looks like an easy way to lose track of a few hours as well...)