Posted in:

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.