Advent of Code

[Greenbank]

Still stuck on day 17, havent' tried any subsequent ones - have had to go out to the shops for new jelly and nails as I keep running out, and start again in a new room with a fresh ceiling.

Ooh. What's the problem? Wrong answer, not fast enough or just can't get it to work properly at all?

I had a bug in mine where it wouldn't accept my answer for part (b), when I eventually fixed it I got the right answer for part (b) but the answer it gave for part (a) changed as well but my original (now incorrect) answer for part (a) was accepted.

[Ben T]

Still stuck on day 17, havent' tried any subsequent ones - have had to go out to the shops for new jelly and nails as I keep running out, and start again in a new room with a fresh ceiling.

Ooh. What's the problem? Wrong answer, not fast enough or just can't get it to work properly at all?

I had a bug in mine where it wouldn't accept my answer for part (b), when I eventually fixed it I got the right answer for part (b) but the answer it gave for part (a) changed as well but my original (now incorrect) answer for part (a) was accepted.

I've come up with an answer but it doesn't accept it at all.
I have produced a pretty picture of what it looks like: https://1drv.ms/u/s!AtNSfl0sxZVlgZIQQ8xv9FsIru8Jww

I have got a loop which I can't figure out how to exit, but at the point where it is not finding any new tiles the situation is as the picture above (should open in paint or simple bmp editor), and it gets to that situation in under a second.
I guessed

(click to show/hide)

38026, and it said that was too high. So there must be some tiles in the above pic that are wet, but shouldn't be??  but can't see which. (I  then guessed 38025 as I thought the tap itself might give an off by one error, but it just said 'incorrect' and to wait 5 minutes, so I guess that must be too high as well.
My input is
https://1drv.ms/t/s!AtNSfl0sxZVlgZIRXFxaCnxLRvnHNg

code is https://github.com/bjtaylor1/AoC2018/blob/day17try2/Day17Vis/Program.cs but wouldn't try and read it, it's pretty indecipherable tbh! 

I could rewrite it but at the moment, either the puzzle's wrong, or there's something I'm fundamentally not understanding about the spec.

[Greenbank]

FWIW, my program agrees with yours for your input. I get the same answer and I can't see anything wrong in the output.

My previous version the program also gives the same answer (even though it exhibits a bug with my input).

I'd move on.

[Ben T]

FWIW, my program agrees with yours for your input. I get the same answer and I can't see anything wrong in the output.

My previous version the program also gives the same answer (even though it exhibits a bug with my input).

I'd move on.

Groan............... found it,

(click to show/hide)

the crucial bit is "To prevent counting forever, ignore tiles with a y coordinate smaller than the smallest y coordinate in your scan data or larger than the largest one."

This bit is misleading I think.
It's only counting larger than the largest y coordinate that prevents counting forever, but you also need to exclude tiles that are wet that are shallower than the shallowest bit of clay.

My shallowest bit of clay is at y coordinate 6, so my answer is 38021 and it has accepted that.

Must admit I did look on the subreddit for that. Can move on now, can't leave it incomplete!

[Ben T]

Ah - part 2 was easy for my algorithm.

(click to show/hide)

I had feared it was going to say "now, you suddenly realise that water pressure does matter ..." 

[Greenbank]

Groan............... found it,

(click to show/hide)

the crucial bit is "To prevent counting forever, ignore tiles with a y coordinate smaller than the smallest y coordinate in your scan data or larger than the largest one."

This bit is misleading I think.
It's only counting larger than the largest y coordinate that prevents counting forever, but you also need to exclude tiles that are wet that are shallower than the shallowest bit of clay.

My shallowest bit of clay is at y coordinate 6, so my answer is 38021 and it has accepted that.

Must admit I did look on the subreddit for that. Can move on now, can't leave it incomplete!

(click to show/hide)

Ah, that explains it, and my problem too, thanks!

As noted above I had a section where a little 1x3 section wasn't filled in properly:-

Code: [Select]

................|......................|............|...........
................|......................|............|...........
..#|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||..
..#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#|..
..#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#|..
..#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#|..
..#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#|..
..#~~~~~~~~~~~~~~#.#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#|..
..#~~~~~~~~~~~~~~#.#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#|..
..#~~~~~~~~~~~~~~#.#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#|..
..#~~~~~~~~~~~~~~###~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#|..
..#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#|..
..#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#|..
..#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#|..
..#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#|..
..#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#|..
..###########################################################|..
.............................................................|..

but I still got the correct answer for part (a). That was due to my input having the highest part of clay at y=4:-

$ grep "y=[0-5]\.\." inp.final
x=608, y=4..6
x=584, y=4..6

so that would mean I wouldn't count the 3 vertical bits of water.

Which is why my incorrect answer for part (a) was actually correct, the 3 missing bits of water were balanced by the 3 extra bits I was counting at the top. That was very lucky!

When I fixed the unfilled in bit it for part (b) I was only counting the standing water so my miscounting of flowing water didn't affect the answer.

[Greenbank]

(click to show/hide)

BFS with a little twist, didn't have to consider items too far out of the original area (14 to the right of the target, nothing below the target, but everyone's input will be different obvs).

I kept track of 3-tuples ( x, y, current_equip -> min_time ) in a hash(map) pushing new items onto the end of a 'todo' list if I found a way to get to that tuple quicker. i.e.

initial item: 0,0,T -> 0

Then tries:-
* 0,0,C -> 7
* 0,0,N -> 7 can't do this as we can't have 'neither' equipment on a rocky square
* If 1,0 is wet then can't go from 0,0,T to 1,0,T.
* If 0,1 is rocky then we add 0,1,T -> 1
...etc...

Pulls 0,0,C -> 7 off list:-
* 0,0,T -> 14 is worse than existing 0,0,T -> 0
* Can't change to 0,0,N because 0,0 is rocky and you need either T or C equipment for rocky.
Try moving left, right, up, down, etc
...etc...

When pulling stuff off the 'todo' list I'd skip it if the current time taken was greater than my current record for getting to the target (if it had been reached). [Spent a bit of time getting the wrong answer as I wasn't ensuring the Torch was in use at the end, so I'd get a score of 38 for the example input at first.)

With an extra buffer of 20x20 onto my map past the target my perl script takes ~8s to get the answer. Can't be bothered to optimise it.
Adding an extra buffer of 1000x1000 onto my map makes it take 84s.

[Greenbank]

Ooh, day 23 part b looks like a stinker, have ideas and not going to look anywhere for hints. Might take a while!

[EDIT] Got the answer for part b but not satisfied with my method at all. It doesn't work at all on the simple example given in the problem.

Some details in this spoiler.

(click to show/hide)

I'd assumed it was going to be a relatively straightforward rather than a contrived solution that was really difficult to locate, based on this I did:-

Found the co-ordinate of a nanobot that is in range of the most number of other nanobots. This was my starting x,y,z and was in range of 825 nanobots.

With my 'current' x,y,z I tried two things:-

a) Testing whether nearby points were in range of more nanobots and, if not,
b) trying to reduce x, y or z as much as possible (in terms of manhattan distance from the 0,0,0 origin) without letting the number of nanobots in range drop.

At first 'nearby' was 5000 points, i.e. I'd test:-
* x+5000,y,z
* x-5000,y,z
* x,y+5000,z
* x,y-5000,z
* x,y,z+5000
* x,y,z-5000

If any of those produced a higher number of nanobots in range then that was my new x,y,z for the next iteration.
If none of those produced a new higher number of nanobots in range I'd pick any of x-5000,y,z or x,y-5000,z or x,y,z-5000 for the next iteration as long as the number of robots in range didn't decrease.

And, as that found a local maxima I reduced it from 5000 to 500, then 50, then 10 and finally 1 to hone in on the final spot which was in range of 860 nanobots (for my input data).

(Oddly, starting it again at 0,0,0 with an initial diff of 1024*1024*1024 and halving that each time to hone in on the final solution, has me end up at a quite different set of x,y,z co-ords but with the same total manhattan distance as my original answer but in range of 914 nanobots. I guess there's something about the placing/sizes of the octohedrons described by each nanobots range that I'm just not able to visualise.)

All in all, I'm surprised this worked and gave me the right answer.

It doesn't work for the example given as it moves from 12,14,12 (3) to 11,14,12 (3) to 10,14,12 (4) and never finds 12,12,12 although 10,14,12 does have the same answer (in terms of manhattan distance of 36) as the proper answer.

[Ben T]

Quite enjoyed day 19.

(click to show/hide)

Once I had a certain amount of information a quick search on OEIS yielded the answer to what the algorithm was trying to do, but probably wouldn't have taken long to spot it without.

[Ben T]

(click to show/hide)

Oof, chased a parser bug for far too long (especially when I'd assumed the parser was fine and I was looking in some other code).

Absolutely lovely feeling when I finally found the last bug and out popped the map for my input. Going from there to the answer for part (a) was a few minutes, and then under a minute to get part (b).

Did wonder about the wording, had thought it was asking for the longest path that didn't repeat rooms rather than the longest shortest path.

But, far too long to get to from the input to a map. Ugh.

Code (perl) runs in under half a second.

(click to show/hide)

Nice use of a recursive algorithm for Day 20.

Didn't take too long at all, would have been even quicker if I'd realised that std::map::insert doesn't throw an exception if you try and insert a duplicate key, despite the fact that std::map::insert_or_assign exists  that had me thinking that because it hadn't thrown an exception, there must only be 1 possible route to each room.
Seems it behaves like std::set::insert, and just doesn't do anything if the key already exists.
Runs instantly https://github.com/bjtaylor1/AoC2018/blob/master/Day20/Day20.cpp.

[Ben T]

Done day 21... dog alone knows what the algorithm is trying to do, unlike 19 that there actually seems to be a point to it.

(click to show/hide)

Just seemed to be a case of short-cirtuiting the loop of lines 18-26, then noting the value of r4 whenever r0 is accessed, because r4 comparing to r0 is what causes the program to exit.
https://github.com/bjtaylor1/AoC2018/blob/master/Day21/Day21.cpp

[Pickled Onion]

Ooh, day 23 part b looks like a stinker, have ideas and not going to look anywhere for hints. Might take a while!
[EDIT] Got the answer for part b but not satisfied with my method at all. It doesn't work at all on the simple example given in the problem.

My method was something similar but opposite results - it worked for the example but unfortunately not the real data 

[Ben T]

Ooh, day 23 part b looks like a stinker, have ideas and not going to look anywhere for hints. Might take a while!

[EDIT] Got the answer for part b but not satisfied with my method at all. It doesn't work at all on the simple example given in the problem.

Some details in this spoiler.

(click to show/hide)

I'd assumed it was going to be a relatively straightforward rather than a contrived solution that was really difficult to locate, based on this I did:-

Found the co-ordinate of a nanobot that is in range of the most number of other nanobots. This was my starting x,y,z and was in range of 825 nanobots.

With my 'current' x,y,z I tried two things:-

a) Testing whether nearby points were in range of more nanobots and, if not,
b) trying to reduce x, y or z as much as possible (in terms of manhattan distance from the 0,0,0 origin) without letting the number of nanobots in range drop.

At first 'nearby' was 5000 points, i.e. I'd test:-
* x+5000,y,z
* x-5000,y,z
* x,y+5000,z
* x,y-5000,z
* x,y,z+5000
* x,y,z-5000

If any of those produced a higher number of nanobots in range then that was my new x,y,z for the next iteration.
If none of those produced a new higher number of nanobots in range I'd pick any of x-5000,y,z or x,y-5000,z or x,y,z-5000 for the next iteration as long as the number of robots in range didn't decrease.

And, as that found a local maxima I reduced it from 5000 to 500, then 50, then 10 and finally 1 to hone in on the final spot which was in range of 860 nanobots (for my input data).

(Oddly, starting it again at 0,0,0 with an initial diff of 1024*1024*1024 and halving that each time to hone in on the final solution, has me end up at a quite different set of x,y,z co-ords but with the same total manhattan distance as my original answer but in range of 914 nanobots. I guess there's something about the placing/sizes of the octohedrons described by each nanobots range that I'm just not able to visualise.)

All in all, I'm surprised this worked and gave me the right answer.

It doesn't work for the example given as it moves from 12,14,12 (3) to 11,14,12 (3) to 10,14,12 (4) and never finds 12,12,12 although 10,14,12 does have the same answer (in terms of manhattan distance of 36) as the proper answer.

To be honest I had absolutely no idea.
However if you read this (contains spoiler), the methodology makes perfect sense and from the description of the method, I was able to code it in C++ purely from my understanding of the method, and without looking at his algorithm. But I've got to admit, I'm not sure I would have come up with that idea on my own.

(click to show/hide)

I guess it is a type of depth first search?

What slightly foxed me is the equivalence of a single point, to a cube of unit size.
The number of nanobots within reach of a any point in* a cube of side 2^n is the same as the number in reach of a single point (i.e., the answer) when n = 0 (i.e. cube is of size 1).

* where 'in' the cube means x >= cx and x < cx + size, with the "size -1" in https://github.com/bjtaylor1/AoC2018/blob/ccd4080553df5593c385a1b2605c8225ca00f320/Day23/Day23.cpp#L32-L34 bringing about the exclusive upper bound of the cube.

Would be quite interesting to genericize the algorithm to n dimensions.

Well done to anybody who got the answer without looking up a method.

[Pickled Onion]

Ooh, day 23 part b looks like a stinker, have ideas and not going to look anywhere for hints. Might take a while!
[EDIT] Got the answer for part b but not satisfied with my method at all. It doesn't work at all on the simple example given in the problem.

My method was something similar but opposite results - it worked for the example but unfortunately not the real data 

Finally got it.

(click to show/hide)

My method for homing in landed me in in an area in range of 936 nanobots which appeared to be small. It turned out to be a very thin and very long region. 1 x 1 x millions. At one end of the region it overlapped with a few more bots. My initial search had landed me at the opposite end 

[Greenbank]

Finished now (didn't get a chance to do more than a few minutes during the last 3 days).

Wasted a bit of time with a misreading of the 24th but got it in 10 minutes this morning and part 2 followed on simply. Not a big fan of big wordy plods like this, but they're quite representative of real world coding with slightly imprecise specs and long slogs of boring programming!

[Ben T]

Finished now (didn't get a chance to do more than a few minutes during the last 3 days).

Wasted a bit of time with a misreading of the 24th but got it in 10 minutes this morning and part 2 followed on simply. Not a big fan of big wordy plods like this, but they're quite representative of real world coding with slightly imprecise specs and long slogs of boring programming!

  Not sure where you work - but can I have a job there?!

Whilst I think it's nice that AoC has presented a dimension of difficulty in terms of having a verbose, complicated spec - I would disagree that they're representative - I would say that AoC specs are far, far better written and more concise than real world specs.
 

e.g. AoC
Spec: "During the target selection phase, each group attempts to choose one target. In decreasing order of effective power, groups choose their targets; in a tie, the group with the higher initiative chooses first. The attacking group chooses to target the group in the enemy army to which it would deal the most damage (after accounting for weaknesses and immunities, but not accounting for whether the defending group has enough units to actually receive all of that damage)."

Real world would be:
Spec: "The strongest [sic] attack first."
Dev: " 'Strongest' meaning? The one with the most power, or the most units?"
Sponsor: "Oh, er... the one with the most power."
Dev: "Ok."
Later:
Sponsor: "This is a BUG! Unit C has attacked before unit D!"
Dev: "Yes, well, they've both got the same power. As designed."
Sponsor: "Yes but D has got higher initiative!"
Dev: "You didn't say anything about higher initiative attacking first in the event of a tie."
Sponsor: "Well, that should have been obvious!"

Recent AoC problems like Day 24 test the skill of data modelling, as well as just procedural logic.

I don't think any of the specs have been ambiguous. Some have been confusing, particularly Day 17, which required reading every single bit of it very very carefully, with crucial detail being in the letter rather than the spirit of the rules, but I don't think any have actually required a leap of faith or reading between the lines, or been noticeably ambiguous.

Clarifications like 'not accounting for whether the defending group has enough units to actually receive all of that damage' are the exact sort of things that are missing from real world specs as it is the sort of thing only a developer would think about.
In reality, if you were programming a real army, some devs might decide that the sponsor wouldn't want to see a powerful unit "waste" an attack on one that is already nearly dead, and insert that into the logic, even though the sponsor didn't specify that - but other devs might not. Here, he's thought about it from the programmer's point of view and clarified it.

[Ben T]

What was a bit sneaky though was

(click to show/hide)

putting "immune" and "weakness" in a different order on some input data to others 

[SoreTween]

(click to show/hide)

Print out the totals at the end of each iteration for the first few hundred iterations

It's not the answer but it will lead you in the right direction, up to you whether you read it obviously.

(click to show/hide)

Oh ffs  Why didn't I think to look for a pattern there? I was on the point of giving up. Thanks Greenbank

[Greenbank]

"271 people have gotten all 200 stars over the four years of #AdventOfCode."

https://twitter.com/ericwastl/status/1082420178510667781

[Greenbank]

9 days to go until #AdventOfCode 2019

(Already donated so I have my AOC++ badge for 2019).

[Greenbank]

Day 1 2019.

Didn't read part b properly (as usual) and made the expected mistake, easily fixed though.

Find the first few days a bit underwhelming after the anticipation, looking forward to a nice meaty problem.

[Greenbank]

Day 2 2019 (no need for spoiler tags yet).

"Good, the new computer seems to be working correctly! Keep it nearby during this mission - you'll probably use it again. Real Intcode computers support many more features than your new one, but we'll let you know what they are as you need them."

I guess this is going to be one of the themes for this year. I'll spend a bit of time making sure it's nicely cleaned up and ready for inclusion in the aoc/2019 directory rather than buried in a specific day's directory.

[Greenbank]

Day 3 2019 (no spoiler tags required)

Today's small delay was caused by a typo in some regex. I initially had /^U(\d)+$/ instead of /^U(\d+)$/ when extracting the number of steps on each instruction (and copy-pasta'd for the other directions). Thankfully the basic test cases provided made it very easy to spot that there was a problem.

[vorsprung]

ICBA this year.  I am interviewing at the moment and have various "tech tasks" to do of random IT puzzles

"no, we don't mind what skills you have.  We are looking for a good attitude and general grasp.  Here's the tech task, should take 4-5 hours"  Yeah right 4-5 hours if I had EXACTLY the same experience as your inhouse staff

[Pickled Onion]

This year I'm doing them in C# instead of Perl. The gains from a nice test framework and intellisense are more than cancelled out by the sheer wordiness of it all.

Delay today caused by trying to dump all the points into Lists and do a Linq intersect to pop out all the crossings. Great for the tests, way too slow for the full puzzle - didn't expect to get hit by that on day 3. So had to go back and do it again properly. 174 lines of code + tests, would probably have been about ten in Perl.