Advent of Code

[David Martin]

For Diver300:

(click to show/hide)

I did the same - a dictionary containing all the 'first triple' indexes and then check that for valid hashes on finding a pentuple.

Carry on the loop until number of distinct indices is >64 and the current index is > max index+1000.

More than the required number of indices are found so sorted(set(indices))[63] works

part 2 - processor cycles are cheap.

For Jo:

(click to show/hide)

Silly bugs, many silly bugs. Took 4x longer to debug than write the code.

1. Increment the counter at the start and the end of the loop so I was going up in steps of 2 instead of 1.
2. When I checked the cache for valid triples on finding a pentuple  I wasn't discounting the current index (which contains a triple)
3. Assuming I had just found 64 indices

[Oaky]

(click to show/hide)

2. When I checked the cache for valid triples on finding a pentuple  I wasn't discounting the current index (which contains a triple)

I did that one too.

(click to show/hide)

I also didn't think to check the next 1000 indices after I'd collected at least 64 keys.

My script still got the right answers without doing this, but that's a bit of luck, I guess.  I felt the need to go back afterwards and fix that.

[Ben T]

Day 14....
Hint:

(click to show/hide)

hash-cache (for part two at least)

(click to show/hide)

Another option is retrospectively mark indexes as being valid keys.

When I found one that's repeated 3 times, mark that index as such.
When I found one that's repeated 5 times, look at the previous 1000, and if any have already been marked as having that character repeating 3 times, add them to a list of valid indexes.
When there are 64 indexes, stop after the next 1000 iterations (as although we have 64, they may not necessarily be the lowest 64... there might be more that have been marked as 3 but not yet marked as having a 5 in the next 1000)
Sort the indexes, and pick the 64th one.

(edit: looking at spoilers I see i'm not the first to do this method)

I vaguely recalled an algorithm to find prime numbers is similar, e.g. 2 marks 2, 4, 6, 8 etc as not being prime, 3 marks 3, 6, 9, and 12 etc as not being prime ... or something like that....
(Of course using a cache may look simpler/nicer)

[Oaky]

Day 14....
Hint:

(click to show/hide)

hash-cache (for part two at least)

(click to show/hide)

You don't need one if you retrospectively mark indexes as being valid keys.

(click to show/hide)

I didn't cache mine.  Part 2 takes ~30 seconds for my input.


oaky@camembert ~/Dropbox/AdventOfCode/16/14 $ time ./s14.py -p 2 -s zpqevtbw
Part 2 answer for salt 'zpqevtbw': key 22423

real  0m33.976s
user  0m32.676s
sys   0m0.300s

[red marley]

Day 14 continued...

(click to show/hide)

Using Oaky's input, and caching (which only ever stores 1001 hashes at any one time), my perhaps simplistic, approach takes ~15 seconds for part 2.

Create a FIFO queue of 1001 hex hashes; pop the first one check it for a triplet; If found scan through the remaining 1000 for a quintuplet; push the next hex hash and repeat until 64 found.

[Diver300]

Day 14

(click to show/hide)

You don't even need to store the whole hash, just the number and the character(s) in the repeating triplet(s).

[Oaky]

Day 14

(click to show/hide)

You don't even need to store the whole hash, just the number and the character(s) in the repeating triplet(s).

(click to show/hide)

That's what I do... I maintain a dict for the triples, indexed by the char that repeats, each entry of which is a list of index numbers that generate a triple of that char.  I do the same for the quintuplets.

I only ever call the md5 or stretched_md5 function once for a given input, then test the result against the triplet and the quintuplet regexps and store the integers corresponding to the matches in my dicts, so I was puzzled by all the talk of caching.

The quintuplets dict looks like this after my part 2 run:

Code: [Select]

0: []
1: []
2: []
3: []
4: []
5: []
6: [9698]
7: [6268, 8518]
8: []
9: [19069]
a: [22467]
b: [12058]
c: []
d: []
e: []
f: [12014, 17867]

The triples dict is similar except it has about 160 entries in each list

[Diver300]

Managed day 12 with only pencil and paper. 

I've just belatedly solved day 11 similarly.

(click to show/hide)

The method of getting the stuff to the top floor doesn't need to be found.

Each up movement of the lift takes two things up, and each down one has to take one thing down. At least for my puzzle, I never found any solutions but I guessed that a solution exists that never needs to take two things down or just one thing up.

Then the number of movements only depends on the sum of the floors that each object has to be raised.

[David Martin]

Mine sounds very much like Oaky's using a dict of arrays to store candidate indices which can then be reviewed if pentuples are found.

[tom_e]

Managed day 12 with only pencil and paper. 

I've just belatedly solved day 11 similarly.

It's an interesting question - I have some sympathy for Oaky's point of view above.  Any question where the input is quite small is potentially vulnerable to a more pure mathematical approach.  Particularly something like day 11 where the answer is relatively small and you get more than one attempt.

In this case, I'd argue you've crossed that fine line to guessing.  But since I am myself putting the first answer produced by code into the box and only going back to check for bugs if it fails (and suspect I am not alone in this), I'm not sure how clear-cut the "guessing is cheating" argument is.

Also, note.

[Oaky]

Managed day 12 with only pencil and paper. 

I've just belatedly solved day 11 similarly.

(click to show/hide)

The method of getting the stuff to the top floor doesn't need to be found.

Each up movement of the lift takes two things up, and each down one has to take one thing down. At least for my puzzle, I never found any solutions but I guessed that a solution exists that never needs to take two things down or just one thing up.

Then the number of movements only depends on the sum of the floors that each object has to be raised.

(click to show/hide)

Whilst your method gets the right answer for my input, I can't convince myself that it's anything other than a lower bound, with no reason to believe that it can be achieved for all inputs.

If I understand your argument correctly, then the position given in here would take 6 moves where in fact I think 11 is the minimum.

Code: [Select]

F4 .   ...   HM   ...  HeM   ...  ...   
F3 E   ...  ...   ...  ...    LG   LM   
F2 .    HG  ...   HeG  ...   ...  ...   
F1 .   ...  ...   ...  ...   ...  ...   


[Diver300]

Managed day 12 with only pencil and paper. 

I've just belatedly solved day 11 similarly.

(click to show/hide)

The method of getting the stuff to the top floor doesn't need to be found.

Each up movement of the lift takes two things up, and each down one has to take one thing down. At least for my puzzle, I never found any solutions but I guessed that a solution exists that never needs to take two things down or just one thing up.

Then the number of movements only depends on the sum of the floors that each object has to be raised.

(click to show/hide)

Whilst your method gets the right answer for my input, I can't convince myself that it's anything other than a lower bound, with no reason to believe that it can be achieved for all inputs.

If I understand your argument correctly, then the position given in here would take 6 moves where in fact I think 11 is the minimum.

Code: [Select]

F4 .   ...   HM   ...  HeM   ...  ...   
F3 E   ...  ...   ...  ...    LG   LM   
F2 .    HG  ...   HeG  ...   ...  ...   
F1 .   ...  ...   ...  ...   ...  ...   


I agree.

I am not arguing that my solution is in any way robust. The example that you give is intentionally awkward, and I think that the puzzle always starts with the elevator on the ground floor, and it has to be soluble, so I don't think that real puzzles can be quite as awkward as yours, but I am sure there are some that have to start with less efficient moves.

I suspect that once the initial awkwardness is sorted, the  bulk of a solution is perfectly efficient, but I haven't proved it.

We shall see if later puzzles leave me lost due to my lack of rigor in day 11

[Oaky]

Managed day 12 with only pencil and paper. 

I've just belatedly solved day 11 similarly.

(click to show/hide)

The method of getting the stuff to the top floor doesn't need to be found.

Each up movement of the lift takes two things up, and each down one has to take one thing down. At least for my puzzle, I never found any solutions but I guessed that a solution exists that never needs to take two things down or just one thing up.

Then the number of movements only depends on the sum of the floors that each object has to be raised.

(click to show/hide)

Whilst your method gets the right answer for my input, I can't convince myself that it's anything other than a lower bound, with no reason to believe that it can be achieved for all inputs.

If I understand your argument correctly, then the position given in here would take 6 moves where in fact I think 11 is the minimum.

Code: [Select]

F4 .   ...   HM   ...  HeM   ...  ...   
F3 E   ...  ...   ...  ...    LG   LM   
F2 .    HG  ...   HeG  ...   ...  ...   
F1 .   ...  ...   ...  ...   ...  ...   


I agree.

I am not arguing that my solution is in any way robust. The example that you give is intentionally awkward, and I think that the puzzle always starts with the elevator on the ground floor, and it has to be soluble, so I don't think that real puzzles can be quite as awkward as yours, but I am sure there are some that have to start with less efficient moves.

I suspect that once the initial awkwardness is sorted, the  bulk of a solution is perfectly efficient, but I haven't proved it.

We shall see if later puzzles leave me lost due to my lack of rigor in day 11

 

BTW - I gather that the position I quoted (from p_tseng's reddit post), is a subset of a position that occurs during the optimal solution of an actual input that somebody was given.

[red marley]

Day 14 speed of calculation.

Given the various ways of finding a solution seemed to result in quite different times taken to calculate, I thought I'd have a look at where the bottleneck was when using Java.

(click to show/hide)

My approach was finding answer to part two in around 12 seconds using a simple caching of 1000 hex hashes (i.e. without the dictionary optimisation described by Oaky and David Martin).

In Java using MessageDigest, the MD5 hash calculation is fast. So even adding uncached hashes (i.e. freshly finding the next MD5 hash for every triplet and quintuplet search), this only added about 6 seconds in total for part two.

I was searching for triplets and quintuplets using simple character comparison. Replacing this with a regex (.)\1{2} (triplet) and (.)\1{4} (quintuplet) was slower, but only a little - adding 2 seconds for part 2.

The real saving/bottlneck was in converting the MD5 hash byte array into hex. Using Java's String.format - String.format("%0" + (bytes.length << 1) + "x", new BigInteger(1, bytes)) added approximately 1 minute to the calculation time. (ETA: removed needless generation of uppercase and then conversion to lowercase)

Instead, I used this optimised bit shifting and array lookup to keep calculation below 12 seconds:


private final static char[] HEX_ARRAY = "0123456789abcdef".toCharArray();

static String toHex(byte[] bytes)
{
   char[] hexChars = new char[bytes.length*2];
   for (int j=0; j<bytes.length; j++)
   {
      int byteValue   = bytes[j] & 0xFF;
      hexChars[j*2]   = HEX_ARRAY[byteValue >>> 4];
      hexChars[j*2+1] = HEX_ARRAY[byteValue & 0x0F];
   }
   return new String(hexChars);
}

[David Martin]

(click to show/hide)

Why do you need to convert to lower case? It isn't material to the problem. You could split it into 8 bit bytes and compare those (lots of bitshift and bitmask could be very quick)

Day 15:
Straightforward.

(click to show/hide)

Modulo (time+offset+startposition) == 0 when it is in the optimal position.
Optimisations I haven't done:
If the first n discs are aligned at point t, the step size to the next aligned point will be the cumulative product of the disc sizes.

[red marley]

Why do you need to convert to lower case? It isn't material to the problem.

Because...

(click to show/hide)

The stretched hash for part two requires a lower case hex as input to the MD5. Upper case would give a different result. However, I realise I have made stupid mistake #65 for the day as String.format() can create lower-case hex directly with "x" rather than "X", which knocks off nearly two minutes from part B (but still way slower than bit shifting/masking).

[Diver300]

Day 15:
Straightforward.

(click to show/hide)

Modulo (time+offset+startposition) == 0 when it is in the optimal position.
Optimisations I haven't done:
If the first n discs are aligned at point t, the step size to the next aligned point will be the cumulative product of the disc sizes.

(click to show/hide)

Only because the disk sizes are distinct prime numbers

As is often the case, part 1 could be solved by brute force, but the seemingly small addition of part 2 made brute force impractical so thinking was needed. My first solution to part 2 depended on the brute force solution to part 1, which made me realise that a far faster and more elegant solution was possible to part 1.

[David Martin]

Smartish brute force.. in my case, though it should be possible to describe the equation analytically.

[Oaky]

Dumb brute force for both parts (Python 2).

Part 1 runs in ~0.6 sec and Part 2 in ~2.1 sec.

I had a feeling when I set it away using the same brute force that part 2 was going to take too long that way and that I'd have to go back and recode it to be smarter, and was surprised when that wasn't the case.

I did go back and apply a couple of optimisations to my discStack class:-

(click to show/hide)

namely

1. pre-add the 1 second delays for the capsule dropping between discs to the starting positions for the discs.
2. reorder the discs to test the one with the most positions first.  My test checks each disc in order and always returns as soon as it finds a disc that blocks the capsule.

Those two items speed my part 2 up by approx 20%

[Ben T]

Day 15 really easy. No optimizations even remotely necessary. Both parts run instantaneously

(click to show/hide)

Code: [Select]

int positions[] =  { 0, 0, 0,  2, 2,  0,  7    /* part 2:*/, 0 };
int positionCount[]{ 0, 7, 13, 3, 5, 17, 19    /* part 2: */,11 };


const bool allAligned(const int t)
{
for (int t0 = 1; t0 < sizeof(positions) / sizeof(int); t0++)
{
const int posAtt0 = (positions[t0] + t + t0) % positionCount[t0];
if (posAtt0 != 0) return false;
}
return true;
}

const int getFirstTimeAllAligned()
{
for (int t = 0; t < 0x7fffffff; t++)
{
if (allAligned(t))
return t;
}
return -1;
}

int main()
{
std::cout << getFirstTimeAllAligned() << std::endl;
    return 0;
}


[Ben T]

Day 15 one liner

(click to show/hide)

Code: [Select]

    class Program
    {
        static int Main()
        {
            Console.Out.WriteLine(Enumerable.Repeat(0, 0xffffff).Select((d, i) => i).ToArray().First(t => new[]
            {
                new[] {0, 0},
                new[] {0, 7},
                new[] {0, 13},
                new[] {2, 3},
                new[] {2, 5},
                new[] {0, 17},
                new[] {7, 19}
                /* part 2: */, new [] {0,11}
            }.Select((p, i) => new {p, i}).Skip(1).All(a => (a.p[0] + a.i + t)%a.p[1] == 0)));
            return 0;
        }
    }


[Oaky]

After day 15's relatively easy problem, what's the betting day 16 is going to be a stinker?

[Oaky]

After day 15's relatively easy problem, what's the betting day 16 is going to be a stinker?

Apparently not.

(click to show/hide)

I woke up early and couldn't get back to sleep so started almost immediately after 05:00.

Simplistic brute force in string-slice-tastic Python.  The unit tests and argument parsing comprise more than three times as many lines as the actual logic

oaky@camembert ~/Dropbox/AdventOfCode/16/16 $ time ./s16.py -p 1
Checksum for disk of length 272, from pattern '10001001100000001' is '10101001010100001'

real   0m0.311s
user   0m0.024s
sys   0m0.060s
oaky@camembert ~/Dropbox/AdventOfCode/16/16 $ time ./s16.py -p 2
Checksum for disk of length 35651584, from pattern '10001001100000001' is '10100001110101001'

real   0m6.665s
user   0m5.556s
sys   0m0.804s

What am I going to do with the rest of my morning?  Might have to do some work!

[red marley]

I didn't really dig today's (Day 16). Just grinding though some standard string manipulation, which is more or less tedious depending on your language of choice.

Yesterday's was more interesting because of there was plenty of scope for optimisation and was good practice for taking a functional approach (and unlike Day 11, could be done before breakfast).

[Diver300]

After day 15's relatively easy problem, what's the betting day 16 is going to be a stinker?

Apparently not.

(click to show/hide)

I woke up early and couldn't get back to sleep so started almost immediately after 05:00.

Simplistic brute force in string-slice-tastic Python.  The unit tests and argument parsing comprise more than three times as many lines as the actual logic

oaky@camembert ~/Dropbox/AdventOfCode/16/16 $ time ./s16.py -p 1
Checksum for disk of length 272, from pattern '10001001100000001' is '10101001010100001'

real   0m0.311s
user   0m0.024s
sys   0m0.060s
oaky@camembert ~/Dropbox/AdventOfCode/16/16 $ time ./s16.py -p 2
Checksum for disk of length 35651584, from pattern '10001001100000001' is '10100001110101001'

real   0m6.665s
user   0m5.556s
sys   0m0.804s

What am I going to do with the rest of my morning?  Might have to do some work!

(click to show/hide)

I set part 2 going (in javascript) while I got breakfast and contemplated cunning solutions than didn't need 35 million characters stored, but when I got back to the computer, it had finished.
I will also end up doing work today!