Well now isn’t day 10 a pickle. I got the first part working in straight order, I spent time unit testing my approach on the small examples before trying the larger input. My natural approach to tackling the part 2 was recursive, and it worked fine on the toy example. On the big input, there wasn’t enough time left in the universe for a recursive solution, but at least I knew I understood the problem. I thought I saw an approach using combinatorics, but I wasn’t sure. There was clearly some pattern there. I coded something up based on my intuition, and the answer was too large. In the end I admitted defeat, assuming the trick was something I just didn’t know about. It also turns out I was testing my approach with some made up data that didn’t have the same restrictions as the actual input data, so that was really what kept me from seeing the pattern. In the end, when looking on Reddit, I found the piece I was missing, that I was indeed unaware of.
These are implementation notes for part 2:
When I was looking at the small example, I saw there were two sub-sequences with numbers in sequence. One was size 4 and one was size 3 and to me it felt significant that the expected answer was 8 and (4-2)^2 * (3-2)^2 = 8. This was what I coded up that gave me too large of an answer… Still it felt like I was close. I was thinking it must be some special value nCr and that got me thinking of the binomial coefficients. Turns out I was in the right ballpark, but it wasn’t until I looked on Reddit I learned about the Tribonacci Sequence–I had never heard of it before. I retrofitted it into what I had, and it worked for the given example, and for many of the examples I had crafted. It didn’t work for all of them, because I had not noticed that there were no differences of 2 in the supplied input, and I had mistakenly created examples with differences of 2. If you allow differences of two, the Tribonacci Sequence will not work for the input. As there are no differences of two, the Tribonacci Sequence works. I’m a bit ashamed to say I don’t understand what’s going on here… :-/
Key code for part 1:
public void doPart1Calculations()
{
int currentJoltage = 0;
int currentAdapterJoltage = -1;
while (joltageAdapterEnumerator.canGetNextJoltageAdapter())
{
currentAdapterJoltage = joltageAdapterEnumerator.getNextJoltageAdapter();
final int diff = currentAdapterJoltage-currentJoltage;
switch(diff)
{
case 1: num1Diffs++; break;
case 3: num3Diffs++; break;
default: throw new IllegalStateException("Couldn't work with joltage diff:" + diff);
}
currentJoltage = currentAdapterJoltage;
}
num3Diffs++; // For the device
}
Key code for part 2:
private static final int[] tribonacci = {0, 1, 1, 2, 4, 7, 13, 24, 44};
public long doPart2Calculations()
{
joltageAdapterEnumerator.reset();
long result = 1;
int currentJoltage = 0;
int count = 1;
while (joltageAdapterEnumerator.canGetNextJoltageAdapter())
{
final int nextJoltage = joltageAdapterEnumerator.getNextJoltageAdapter();
if (currentJoltage+1 == nextJoltage)
{
count++;
}
else
{
result*=tribonacci[count];
count = 1;
}
currentJoltage = nextJoltage;
}
return result;
}