Advent of Code

[David Martin]

As is part 2 but slightly different as it is not continuous as a quick simulation of the first 45 parties shows (from 5-99 elves)

(click to show/hide)

It is 3**n instead of 2**n that is the key.

(click to show/hide)

The maxima are at 3**n, and between 3**n and 2*3**n (where n is floor(log(number,3)) ) the elf is number - 3**n (even) and between 2*3**n and 3**n+1 it is 3**(n+1) -2*(3**(n+1) - number)

Very pleased to have solved it elegantly without needing to brute force it.

[Ben T]

day 19 part 1:

(click to show/hide)

int get_answer(int numElves)
{
   int hpt_pow = (int)log2(numElves);
   int hpt = pow(2, hpt_pow);
   int ans = (numElves - hpt) * 2 + 1;
   return ans;
}

[Ben T]

day 19 part 2:

(click to show/hide)

int get_answer_part2(int numElves)
{
   if (numElves == 1) return 1;
   int b = (int)(log(numElves - 1) / log(3));
   int c = pow(3, b);
   int d = numElves - c;
   if (d > c) return c + (d - c) * 2;
   else return d;
}

[Ben T]

generic iterator template for branch style problems
https://github.com/bjtaylor1/AoC_2016/blob/master/puzzle_iterator.h
used in day 17: https://github.com/bjtaylor1/AoC_2016/blob/master/Day17b/Day17b.cpp
part 2 runs in sub-10s in release mode with /Ox.

also works for 2015 day 19 1+2.

[Oaky]

(click to show/hide)

it's (almost) another Christmas tree

[David Martin]

That wasn't particularly challenging - or maybe I am missing something

(click to show/hide)

like an elegant way to do it other than iterating through the list keeping track of the overlapping range so far..

[red marley]

I agree.

(click to show/hide)

I assume you sorted the list before scanning for the range gaps. The only thing that caught me out was I forgot to account for the fact that the upper bound of a given range pair could overlap more than one of the next sorted range pairs. This made no difference to part one and the test case, but meant my first attempt at part two had too many valid IP addresses.

I suppose an interesting variant of the problem might be to find an efficient inline solution for 64 bit addresses (i.e. potentially too many to store in memory and sort).

[David Martin]

(click to show/hide)

Yes, with just a few hundred it was fine to sort first.

My first attempt at part 1 had missed that ranges could be non-overlaping but adjacent (simple error and failure to check output properly) but then went on till the maximum found so far was more than 1 below the next start in the sorted list.

Easy to adapt to then add the gap sizes to get the total.

[tom_e]

(click to show/hide)

I thought about merging, but didn't bother in the end.  Just did a search based on splitting the space in half repeatedly.

So look for firewall rules overlapping the current search range.  If one covers the range entirely, every IP in the range is blocked.  If none are overlapping, every IP in the range is allowed.  If there are overlapping rules, cut the space in half and search both (but start from the already overlapping rules, not the full set).  Sort of like a cube-splitting thing for spatial searching / indexing.  I forget the name.

Fast enough.  I assume merging would help, but I didn't actually check how "mergy" the input data was.

[red marley]

(click to show/hide)

How mergey? This mergey for my input...



(and a larger version)

where IP addresses are from left to right, blacklist ranges are horizontal black lines and valid IP addresses as vertical blue lines. The degree of redness indicates how many overlapping blacklists cover any one IP address.

BTW: There is no need to actually merge ranges; simply keep track of the current maximum blacklist address as you process each sorted range looking for any lower range bound that is at least one greater than the current maximum (takes less than 10 milliseconds to compute both parts on my machine).

[Oaky]

(click to show/hide)

I used numpy and pandas to get both parts pretty easily.  I managed to take into account one of the two gotchas mentioned below (non-overlapping but adjacent ranges) but missed the other.  It turned out not to affect my answer for either part though.

I also didn't originally allow for the possibility of any allowed IPs above the top of the final blacklist block (my input had the final blacklist block ending at MAXINT, so this didn't matter for me either).

I then went back and recalculated it without the first_gap function, using pandas alone (and numpy to do the initial sort).

Here's my Jupyter Notebook with both methods in it

[Ben T]

That wasn't particularly challenging - or maybe I am missing something

(click to show/hide)

like an elegant way to do it other than iterating through the list keeping track of the overlapping range so far..

(click to show/hide)

No, that is the elegant way to do it. The agricultural way is: https://github.com/bjtaylor1/AoC_2016/blob/master/Day20cpp/Day20cpp.cpp#L1195  
runs in under a second though

[David Martin]

I was looking at the problem and thinking that it maps onto a typical biological problem 'which parts of my gene have no sequence coverage?'

I'm not sure there is a specific tool for that - I'd probably write a similar script +/- the parsing of appropriate formats.

[Ben T]

Day 21 relies on realising the fact that

(click to show/hide)

"rotate based on position of letter X" is only one-to-one, and thus has an inverse, if the total number of letters is even. Which it is in the puzzle input ( 8 ), but not in the examples (5)

[David Martin]

Not done it yet. Broadband outage at home so I have sneaked into the office to get it onto the PC. Will look at it tonight, but it doesn't seem so hard.
Not looked at the spoilers either.

[R_nger]

What's happening to Jo"s leader board ? Some mischievous anonymous user(s) having fun ?

[tom_e]

   <tries to look innocent and not childish>

[R_nger]

  <tries to look innocent and not childish>

LOL... I just popped over to the CDC thread...and you've beaten me to it !!

[red marley]

Anonymous user 107436 needs to get their act together and get a nice silver star for Day 14.

[tom_e]

Yeah, I couldn't decide about that pixel.  A spurt would take too many rows, and I'm already norty flagged on github now.

Just for you, jo.

[red marley]

Day 21 relies on realising the fact that

(click to show/hide)

"rotate based on position of letter X" is only one-to-one, and thus has an inverse, if the total number of letters is even. Which it is in the puzzle input ( 8 ), but not in the examples (5)

Or

(click to show/hide)

Any forward rotation function, however convoluted the rules, can only ever result in 8 possible new arrangements. So it is a simple matter of testing up to 8 standard rotations of the encrypted password to see which one would be generated by the original forward 'rotation based on position' function.

I only realised this after I spent the best part of an hour defining the inverse rotation based on position function.
 

[Oaky]

(click to show/hide)

I somehow convinced myself that the rotate based on position would have no inverse, and so thought I'd have to do some sort of forwards brute force on it.  I also convinced myself (through running time on my part 1) that I'd have to make my forward mapping more efficient to finish in reasonable time.

I spent an hour writing something that would automatically try to compose certain subsequent lines of the input into quicker single step permutations, before working out that that wasn't going to work.

I decided just to code up the naive brute force "run each permutation through the forward scrambler" loop that I originally thought of doing and set it away to keep my machine warm while I thought about another approach.

1.6 seconds later it returned with the answer!  d'oh!

[Oaky]

Day 21 relies on realising the fact that

(click to show/hide)

"rotate based on position of letter X" is only one-to-one, and thus has an inverse, if the total number of letters is even. Which it is in the puzzle input ( 8 ), but not in the examples (5)

(click to show/hide)

I'm not sure the bit in bold is true.  As far as I can see, only strings of length 1, 3 and 8 will generate a one-to-one mapping based on the "rotate based on position of letter X" rule.

Code: [Select]

Results of 'rotate based on position of letter f'
Input length is 1

In   Out

f -> f

IS one-to-one

----------------------------------------
Results of 'rotate based on position of letter f'
Input length is 2

In    Out

f. -> .f
.f -> .f

IS NOT one-to-one

----------------------------------------
Results of 'rotate based on position of letter f'
Input length is 3

In     Out

f.. -> .f.
.f. -> f..
..f -> ..f

IS one-to-one

----------------------------------------
Results of 'rotate based on position of letter f'
Input length is 4

In      Out 

f... -> .f..
.f.. -> ...f
..f. -> .f..
...f -> ...f

IS NOT one-to-one

----------------------------------------
Results of 'rotate based on position of letter f'
Input length is 5

In       Out   

f.... -> .f...
.f... -> ...f.
..f.. -> f....
...f. -> ..f..
....f -> f....

IS NOT one-to-one

----------------------------------------
Results of 'rotate based on position of letter f'
Input length is 6

In        Out   

f..... -> .f....
.f.... -> ...f..
..f... -> .....f
...f.. -> .f....
....f. -> ....f.
.....f -> f.....

IS NOT one-to-one

----------------------------------------
Results of 'rotate based on position of letter f'
Input length is 7

In         Out     

f...... -> .f.....
.f..... -> ...f...
..f.... -> .....f.
...f... -> f......
....f.. -> ...f...
.....f. -> .....f.
......f -> f......

IS NOT one-to-one

----------------------------------------
Results of 'rotate based on position of letter f'
Input length is 8

In          Out     

f....... -> .f......
.f...... -> ...f....
..f..... -> .....f..
...f.... -> .......f
....f... -> ..f.....
.....f.. -> ....f...
......f. -> ......f.
.......f -> f.......

IS one-to-one

----------------------------------------
Results of 'rotate based on position of letter f'
Input length is 9

In           Out       

f........ -> .f.......
.f....... -> ...f.....
..f...... -> .....f...
...f..... -> .......f.
....f.... -> .f.......
.....f... -> ...f.....
......f.. -> .....f...
.......f. -> .......f.
........f -> f........

IS NOT one-to-one

----------------------------------------
Results of 'rotate based on position of letter f'
Input length is 10

In            Out       

f......... -> .f........
.f........ -> ...f......
..f....... -> .....f....
...f...... -> .......f..
....f..... -> f.........
.....f.... -> ..f.......
......f... -> ....f.....
.......f.. -> ......f...
........f. -> ........f.
.........f -> f.........

IS NOT one-to-one

----------------------------------------


[David Martin]

Day 21 relies on realising the fact that

(click to show/hide)

"rotate based on position of letter X" is only one-to-one, and thus has an inverse, if the total number of letters is even. Which it is in the puzzle input ( 8 ), but not in the examples (5)

(click to show/hide)

I'm not sure the bit in bold is true.  As far as I can see, only strings of length 1, 3 and 8 will generate a one-to-one mapping based on the "rotate based on position of letter X" rule.

Code: [Select]

Results of 'rotate based on position of letter f'
Input length is 1

In   Out

f -> f

IS one-to-one

----------------------------------------
Results of 'rotate based on position of letter f'
Input length is 2

In    Out

f. -> .f
.f -> .f

IS NOT one-to-one

----------------------------------------
Results of 'rotate based on position of letter f'
Input length is 3

In     Out

f.. -> .f.
.f. -> f..
..f -> ..f

IS one-to-one

----------------------------------------
Results of 'rotate based on position of letter f'
Input length is 4

In      Out 

f... -> .f..
.f.. -> ...f
..f. -> .f..
...f -> ...f

IS NOT one-to-one

----------------------------------------
Results of 'rotate based on position of letter f'
Input length is 5

In       Out   

f.... -> .f...
.f... -> ...f.
..f.. -> f....
...f. -> ..f..
....f -> f....

IS NOT one-to-one

----------------------------------------
Results of 'rotate based on position of letter f'
Input length is 6

In        Out   

f..... -> .f....
.f.... -> ...f..
..f... -> .....f
...f.. -> .f....
....f. -> ....f.
.....f -> f.....

IS NOT one-to-one

----------------------------------------
Results of 'rotate based on position of letter f'
Input length is 7

In         Out     

f...... -> .f.....
.f..... -> ...f...
..f.... -> .....f.
...f... -> f......
....f.. -> ...f...
.....f. -> .....f.
......f -> f......

IS NOT one-to-one

----------------------------------------
Results of 'rotate based on position of letter f'
Input length is 8

In          Out     

f....... -> .f......
.f...... -> ...f....
..f..... -> .....f..
...f.... -> .......f
....f... -> ..f.....
.....f.. -> ....f...
......f. -> ......f.
.......f -> f.......

IS one-to-one

----------------------------------------
Results of 'rotate based on position of letter f'
Input length is 9

In           Out       

f........ -> .f.......
.f....... -> ...f.....
..f...... -> .....f...
...f..... -> .......f.
....f.... -> .f.......
.....f... -> ...f.....
......f.. -> .....f...
.......f. -> .......f.
........f -> f........

IS NOT one-to-one

----------------------------------------
Results of 'rotate based on position of letter f'
Input length is 10

In            Out       

f......... -> .f........
.f........ -> ...f......
..f....... -> .....f....
...f...... -> .......f..
....f..... -> f.........
.....f.... -> ..f.......
......f... -> ....f.....
.......f.. -> ......f...
........f. -> ........f.
.........f -> f.........

IS NOT one-to-one

----------------------------------------


From 5 onwards your rotation is wrong. 

Sent from my SM-G920F using Tapatalk

[David Martin]

Ok, guilty of not reading the instructions. Fortunately I could grab the data at work today but have to enter the answers with the phone as I currently have no broadband. So slightly delayed but now there.

Sent from my SM-G920F using Tapatalk