Software Architect at Genzeon Corporation in Malvern, Pennsylvania, Microsoft .NET MVP, Husband, Dad and Geek.
18069 stories
·
21 followers

Advent of Code Day 16–The Eternal Dance

1 Share

The difficulty level has been slowly ramping up in this year’s Advent of Code challenge, and today’s puzzle initially sent me off down a dead end.

Part 1 was simple enough. We’re given a series of “dance moves”, involving rearranging the order of a line of dancers. First of all I needed to parse the instructions, which I did with a regex:

let instructions = input[0].split(',')
     .map(i => i.match(/x(\d+)\/(\d+)|s(\d+)|p([a-z])\/([a-z])/))
     .map(([x,a,b,c,d,e]) => ({move:x[0],exA:Number(a),exB:Number(b),spin:Number(c),pA:d,pB:e}))

We needed two helpers to implement the three dance moves. “Exchange” swaps the position of two dancers, while “spin” moves a group of dancers from the end of the line to the front:

let exchange = (state,a,b) => {
    let tmp = state[a]
    state[a] = state[b]
    state[b] = tmp
    return state;
}
let spin = (state,n) => {
    return state.slice(state.length - n).concat(state.slice(0,state.length - n))
}

We can now simply iterate through the instructions and apply them, turning the final state back into a string:

function dance(instructions, start) {
    let s = [...start]
    for(let i of instructions) {
        switch(i.move) {
            case "x": s = exchange(s,i.exA,i.exB); break;
            case "s": s = spin(s,i.spin); break;
            case "p": s = exchange(s,s.indexOf(i.pA), s.indexOf(i.pB)); break;
        }
    }
    return s.join('')
}

So far so good. But for part 2 we were asked to repeat the dance 1 billion times. A quick calculation from the time taken to solve part 1 revealed this would take 2117 years! So I knew I couldn’t just optimise my part 1 solution – even a hundredfold speedup would be way too slow.

I realised there must be a way to short-circuit the problem. My first idea was that maybe after a certain number of dances, we would get back to the starting point. So if after 7 dances we are back to the starting position then after 7 million dances we will be in the same position again. However, when I considered how many possible orderings of dancers there were (16 factorial by my calculation), I abandoned this idea.

My second idea was that maybe the instructions for one dance could be collapsed into a simple reordering. Maybe at the end of the dance the dancer who started in position 1 always ends up in position 6, and so on for each dancer.

So I took the answer for part 1 and generated a lookup of starting to end position for each dancer. And then I reapplied it one billion times:

let m = new Map()
let part1 = "pkgnhomelfdibjac"
for(let n = 0; n < state.length; n++) {
    m.set(n, part1.indexOf(state[n]))
}
state = [..."abcdefghijklmnop"]
for(let n = 0; n < 1000000000; n++) {
    let next = []
    for (let i = 0; i < 16; i++) {
        next[m.get(i)] = state[i]
    }
    state = next;
}
return state.join('')

This took three minutes to run, but it generated the wrong answer. And on reflection, it wasn’t hard to see why this was never going to work. The “partner” dance move swapped dancers based on their original position, not their current position, so this optimization is way too simplistic.

So it was back to the drawing board, and it turns out that my first idea was the better one. If we repeatedly perform the dance, and wait until we see the starting state again, we’ve found the cycle length. From the cycle length we know how many additional dances are needed to make it up to one billion:

let cur = start;
let repetitions = 1000000000;
for(let n = 0; n < repetitions; n++) {
    cur = dance(instructions,cur);
    if (cur === start)
    {
        let cycle = n+1;
        let extras = repetitions % cycle;
        n = 0;
        repetitions = extras+1;
    }
}
return cur

With this optimization in place, I get the solution in a very respectable 300ms. The cycle size for my input was just 60 meaning only 40 extra repetitions were required. However, we could speed that up even further by storing the output for each dance, so that once we’d found the cycle, we could just return the answer we calculated from the first time through the cycle. That shaves it down to 200ms and looks like this (although I have just left my solution for part 2 as is):

let cur = start;
let solutions = []
let repetitions = 1000000000;
for(let n = 0; n < repetitions; n++) {
    cur = dance(instructions,cur);
    solutions.push(cur)
    if (cur === start)
    {
        let cycle = n+1;
        let extras = repetitions % cycle;
        return solutions[extras-1]
    }
}

So today’s challenge was a good lesson in optimization techniques, and a reminder not to be too quick to dismiss your initial ideas. I was wrong about the total number of possible orderings of dancers – its not 16 factorial (20,922,789,888,000), its a more reasonable 140 squared (19,600) – courtesy of the mathematical geniuses on the AoC reddit. And in any case just because the number of possible orderings is high, doesn’t mean the cycle size was high. If I’d started off by searching for a cycle, with an upper bound of say 10,000 repetitions I would have wound up at the answer much quicker.

Read the whole story
alvinashcraft
42 minutes ago
reply
West Grove, PA
Share this story
Delete

Xamarin.Forms - Rounded BoxView Using Custom BoxRenderer

1 Share
In this article you will learn how to Create Rounded BoxView Using BoxRenderer in Xamarin forms.
Read the whole story
alvinashcraft
42 minutes ago
reply
West Grove, PA
Share this story
Delete

Xamarin Android - Working with Existing DB

1 Share
In this article, I shall show you how to retrieve user data from existing SQLite Database.
Read the whole story
alvinashcraft
42 minutes ago
reply
West Grove, PA
Share this story
Delete

MVVM Lite For Data Binding In Xamarin.Form

1 Share
We are using MVVM light that will provide the facility to implement Model-View-ViewModel. This is the quick way for development of an application and also provides a user the facility to customize and design the application.
Read the whole story
alvinashcraft
42 minutes ago
reply
West Grove, PA
Share this story
Delete

How Google Develops New Managers

1 Share

Alex Langshur, host of Google Partners Podcasts, has organized the podcast Google HR secrets: identifying & developing great managers, interviewing Sarah Calderon, People Development at Google, on how Google selects, trains, and develops their managers.

By Abel Avram
Read the whole story
alvinashcraft
42 minutes ago
reply
West Grove, PA
Share this story
Delete

JetBrains Launches GoLand Go IDE

1 Share

JetBrains has moved its Go IDE from its early access programme to market. Now branded as GoLand, the IDE extends the IntelliJ platform making its core functionality specific to Go. This follows suit with their other language-specific tools such as PyCharm for Python and RubyMine for Ruby.

By Andrew Morgan
Read the whole story
alvinashcraft
43 minutes ago
reply
West Grove, PA
Share this story
Delete
Next Page of Stories