Author Topic: Advent of Code  (Read 57209 times)

Re: Advent of Code
« Reply #1100 on: December 26, 2020, 10:29:59 am »
Not sure what optimisations are required if you implement it as it says. Mine completes in ~5 seconds even with a relatively naive perl implementation. The only caching I do is to prevent it repeating a hand-state as per the instructions, and that's just per game.

My input meant I processed somewhere under 20,000 games and 2.1 million rounds in total.

Early on I forgot to truncate the decks for the sub-games and that meant it had no chance of returning before the heat death of the universe. Sure you aren't doing the same?

initially, yes, but have changed it to truncate now and doesn't seem any faster.
It seems to get more 'repeats' per 1,000 games than when it didn't truncate.
It's actually a lot slower per 1,000 games but I was hoping that it would mean there would be fewer to go through in total.
My only thought is it could be the list copying in order to keep the state after a sub game as it was when the subgame started that's slowing it down every time.
I did have another optimisation that gave an answer in fractions of a second. Unfortunately the wrong answer. It is has been bothering me why it didn’t work and I just realised so I now have a solution that only takes a few seconds.

hmm, weird. Rewrote it in c++ and it gets the correct answer in under a second, with about 14,000 games. No idea what the previous program was doing.
It is what it is. It's not what it's not, so it must be what it is.

Re: Advent of Code
« Reply #1101 on: December 26, 2020, 10:51:39 am »
Not sure what optimisations are required if you implement it as it says. Mine completes in ~5 seconds even with a relatively naive perl implementation. The only caching I do is to prevent it repeating a hand-state as per the instructions, and that's just per game.

My input meant I processed somewhere under 20,000 games and 2.1 million rounds in total.

Early on I forgot to truncate the decks for the sub-games and that meant it had no chance of returning before the heat death of the universe. Sure you aren't doing the same?

initially, yes, but have changed it to truncate now and doesn't seem any faster.
It seems to get more 'repeats' per 1,000 games than when it didn't truncate.
It's actually a lot slower per 1,000 games but I was hoping that it would mean there would be fewer to go through in total.
My only thought is it could be the list copying in order to keep the state after a sub game as it was when the subgame started that's slowing it down every time.
I did have another optimisation that gave an answer in fractions of a second. Unfortunately the wrong answer. It is has been bothering me why it didn’t work and I just realised so I now have a solution that only takes a few seconds.

hmm, weird. Rewrote it in c++ and it gets the correct answer in under a second, with about 14,000 games. No idea what the previous program was doing.
Your computer is faster than my old laptop.

Advent of Code
« Reply #1102 on: December 26, 2020, 10:55:17 am »
My day 23 part b cups speedy solution minimal version which after initialisation is technically one line of c (no curly brackets). It s about as fast as it can be too


(click to show/hide)

Re: Advent of Code
« Reply #1103 on: December 26, 2020, 04:21:14 pm »
(click to show/hide)
"Yes please" said Squirrel "biscuits are our favourite things."

Re: Advent of Code
« Reply #1104 on: December 26, 2020, 07:42:22 pm »
Done. Not helped by the fact that the dot net debugger crashes on the Apple M1 chip when stepping off a break point. Had to go back to old school debugging by print statements.

Now to go back to 2019 - I stopped at day 15. This year's seems tamer than previous years, or perhaps it's just easier with practice.
Quote from: tiermat
that's not science, it's semantics.

Re: Advent of Code
« Reply #1105 on: December 27, 2020, 09:43:28 pm »
For day 23 part 2 my program produces the right numbers for the example input 389125467 => (934001 x 159792 = 149245887792)
but wrong for my actual input.
Bloody annoying.
Definitely not overflown as I've converted to 64 bit numbers before making the product.
Struggling to see how it would be right for the example but wrong for my actual.
Would anyone who's got it right mind posting their input and the two numbers clockwise from 1 please and the product?
Runs in a second or two so easy for me to check

It is what it is. It's not what it's not, so it must be what it is.

Advent of Code
« Reply #1106 on: December 27, 2020, 10:03:05 pm »
For day 23 part 2 my program produces the right numbers for the example input 389125467 => (934001 x 159792 = 149245887792)
but wrong for my actual input.
Bloody annoying.
Definitely not overflown as I've converted to 64 bit numbers before making the product.
Struggling to see how it would be right for the example but wrong for my actual.
Would anyone who's got it right mind posting their input and the two numbers clockwise from 1 please and the product?
Runs in a second or two so easy for me to check
Your puzzle answer was 412990492266.

Both parts of this puzzle are complete! They provide two gold stars: **

At this point, all that is left is for you to admire your Advent calendar.

Your puzzle input was 963275481.


You could also test your input against my code posted a few posts above #1103

The only bit that needed 64 bit was the final multiply

Re: Advent of Code
« Reply #1107 on: December 28, 2020, 09:41:41 am »
For day 23 part 2 my program produces the right numbers for the example input 389125467 => (934001 x 159792 = 149245887792)
but wrong for my actual input.
Bloody annoying.
Definitely not overflown as I've converted to 64 bit numbers before making the product.
Struggling to see how it would be right for the example but wrong for my actual.
Would anyone who's got it right mind posting their input and the two numbers clockwise from 1 please and the product?
Runs in a second or two so easy for me to check
Your puzzle answer was 412990492266.

Both parts of this puzzle are complete! They provide two gold stars: **

At this point, all that is left is for you to admire your Advent calendar.

Your puzzle input was 963275481.


You could also test your input against my code posted a few posts above #1103

The only bit that needed 64 bit was the final multiply
Weird. My code gets the right answer for your input.

But still claims to be wrong for my own. Oh well, I'll give your code a compile and see what it gets...
It is what it is. It's not what it's not, so it must be what it is.

Re: Advent of Code
« Reply #1108 on: December 28, 2020, 12:11:32 pm »
Your puzzle answer was 412990492266.

Both parts of this puzzle are complete! They provide two gold stars: **

At this point, all that is left is for you to admire your Advent calendar.

Your puzzle input was 963275481.


You could also test your input against my code posted a few posts above #1103

The only bit that needed 64 bit was the final multiply
Weird. My code gets the right answer for your input.

But still claims to be wrong for my own. Oh well, I'll give your code a compile and see what it gets...
[/quote]
Got it now, thanks davef - was a bug in setting up the initial data.
Was using a linked list and wasn't setting up the initial data correctly, so if the input was 315679824, I was setting e.g. 2.next = 4, and 4.prev = 2, and setting 4's next to 10.... but forgot to set 10's prev to 4.
Might try and create a generic linked list class, as the code is a bit of a mess and a pita to debug.
It is what it is. It's not what it's not, so it must be what it is.

Re: Advent of Code
« Reply #1109 on: December 28, 2020, 12:16:23 pm »
Quote
Your puzzle answer was 412990492266.

Both parts of this puzzle are complete! They provide two gold stars: **

At this point, all that is left is for you to admire your Advent calendar.

Your puzzle input was 963275481.


You could also test your input against my code posted a few posts above #1103

The only bit that needed 64 bit was the final multiply
Weird. My code gets the right answer for your input.

But still claims to be wrong for my own. Oh well, I'll give your code a compile and see what it gets...
Got it now, thanks davef - was a bug in setting up the initial data.
Was using a linked list and wasn't setting up the initial data correctly, so if the input was 315679824, I was setting e.g. 2.next = 4, and 4.prev = 2, and setting 4's next to 10.... but forgot to set 10's prev to 4.
Might try and create a generic linked list class, as the code is a bit of a mess and a pita to debug.

My somewhat more verbose than your code:
(click to show/hide)
It is what it is. It's not what it's not, so it must be what it is.

Re: Advent of Code
« Reply #1110 on: December 28, 2020, 05:52:16 pm »
Implemented day 25 properly and got the time down to 1189usec for my input.

It finds the answer for the example input in 102usec.

(Note usec not msec. 1189usec is ~1.2msec.)
"Yes please" said Squirrel "biscuits are our favourite things."

Re: Advent of Code
« Reply #1111 on: December 28, 2020, 06:27:59 pm »
Implemented day 25 properly and got the time down to 1189usec for my input.

It finds the answer for the example input in 102usec.

(Note usec not msec. 1189usec is ~1.2msec.)
It is a flawed security system if it can be broken by some arithmetic !

Re: Advent of Code
« Reply #1112 on: December 28, 2020, 07:55:08 pm »
(day 15 2019)

Late to it today as I'd been out all day at a family party. Chased a few silly bugs in a dreadful implementation but got it done.

The way I'd implemented meant it was only a very small change required to do part 2.

Loving the use of IntCode computers to provide inputs (i.e. the maze) that can't be analysed directly.

(click to show/hide)

Bah! Mapped out the route to the Oxygen by finding the walls and marking any dead-ends on backtrack. This gave all the map that was needed and the route back to origin was then the only one left.

Now for part two I need the whole map!  :facepalm:
Quote from: tiermat
that's not science, it's semantics.

Re: Advent of Code
« Reply #1113 on: December 28, 2020, 09:25:08 pm »
Implemented day 25 properly and got the time down to 1189usec for my input.

It finds the answer for the example input in 102usec.

(Note usec not msec. 1189usec is ~1.2msec.)
It is a flawed security system if it can be broken by some arithmetic !

And I hadn't bothered optimising it. Down to 240usec now.

It's not just arithmetic, it's searching the full search space to solve a^e = x mod m (i.e. finding e for a given a, x and m). It just does it in a more efficient way with a lot fewer calculations.

(In this example 7^e = x mod 20201227)

The security system is a little better if you use much bigger primes. 20201227 is a tad on the small size.

If I give you even a 256-bit prime such as 90903494037702082433862493857994179414185677901950849383197625766750833066817 then it's not so quick or easy.
"Yes please" said Squirrel "biscuits are our favourite things."

Advent of Code
« Reply #1114 on: December 29, 2020, 09:28:47 am »
Here is my day 25. I think it is quite efficient both in terms of performance and typing and is surprisingly readable. With the exception of the sea monster I have them all down to a handful of lines of code. Just fine tuning my 4d life.

(click to show/hide)

Or if you were happy to take a punt on which key was easier to find you could remove f and g but if one was much easier than the other it could be much slower

(click to show/hide)

Re: Advent of Code
« Reply #1115 on: January 01, 2021, 05:27:29 pm »
Can't see it mentioned anywhere but there's Project Euler too, for anyone wanting to continue with problems throughout the year.

I've made a thread for it here: https://yacf.co.uk/forum/index.php?topic=117960.0 so not to clutter up this one (which we can save for AoC).
"Yes please" said Squirrel "biscuits are our favourite things."

Re: Advent of Code
« Reply #1116 on: January 01, 2021, 06:27:25 pm »
Can't see it mentioned anywhere but there's Project Euler too, for anyone wanting to continue with problems throughout the year.

I've made a thread for it here: https://yacf.co.uk/forum/index.php?topic=117960.0 so not to clutter up this one (which we can save for AoC).

Thanks, but I think I'm going to be busy going over the previous years' ones I gave up on at the time. :-)
Quote from: tiermat
that's not science, it's semantics.

Re: Advent of Code
« Reply #1117 on: January 02, 2021, 09:06:51 pm »
Day 17 (2019). Another example of READ THE TEXT, then READ IT AGAIN.

The "obvious" route, of going straight across each intersection, might have led to a final set of instructions that could not be compressed to fit the input instruction rules.

Having to then go back and make the first part of part 2 output every possible permutation until one that could be compressed adequately would have been less fun.

A transcription error meant I missed the obvious route (and didn't look for spoilers). So I implemented the "every permutation" with linked lists and recursion. It was a rather laborious, but popped out the answer very quickly.
Quote from: tiermat
that's not science, it's semantics.