Today’s Advent of Code challenge was another seemingly simple algorithm, but in practice (for part b at least) an efficient algorithm was needed if you didn’t want to wait a long time.
The puzzle involves elves sat in a circle exchanging gifts, each time eliminating one elf until one remains with all the gifts. It’s not hard to work out which elf takes which gift, but the challenge is making a data structure that makes sense.
I felt a linked list would be a good idea, but implemented it as a
Map<int,int> – each elf number knows the index of the elf to his left.
This way we can create a simple recursive function to return a new map with the eliminated elf taken out until we have one left:
let rec solve (state:Map<int,int>) pos = let left = state.[pos] //printfn "Elf %d takes from %d: %A" pos left state if left = pos then pos else solve (state.Add(pos, state.[left]).Remove(left)) state.[left]
Now we just need to set up the initial starting state from our puzzle input, and part a is solved:
let generateStartState elves = Seq.init elves (fun n -> n+1, (n+1)%elves+1 ) |> Map.ofSeq solve (generateStartState 3014387) 1 |> printfn "Part a: %d"
However, part b causes big problems. The eliminated elf is no longer the neighbour but the elf opposite in the circle. A linked list doesn’t enable us to work that out quickly, and my simple code to follow the list round by
count/2 places was just way too slow.
So I switched to an array, containing the elf numbers in the circle. And to make that faster, rather than allocating new arrays, we’d shuffle the elves down one by one.
let rec solveB2 (state:int) len pos = let elf = state.[pos] if len = 1 then elf else let oppositeIndex = (pos + len / 2) % len let eliminateElf = state.[oppositeIndex] let newLen = len-1 for n in oppositeIndex..newLen-1 do state.[n] <- state.[n+1] let leftPos = if oppositeIndex > pos then (pos+1)% (newLen) else pos% (newLen) solveB2 state newLen leftPos
And this works, but it is pretty slow (many minutes). Turns out I missed an obvious trick with the linked list. Had we tracked not only the current elf whose turn it is, but also the position of the opposite elf, we would not have needed to re-work out the opposite elf each time.
And in fact there was an even cleverer trick, which perhaps was not in the spirit of this puzzle, but several clever people on the reddit group worked out a simple equation to get directly to the number of the winning elf without simulating the exchange of gifts at all. Obviously solutions like that fall down if the rules of gift exchange are modified such that a simulation becomes necessary again.
So today served as a good reminder that often my first instinct for solving a problem may work, but is far from optimal. I doubt I’ll have time to refactor my solution for today, but here’s my code if you’re interested.