Author Topic: Advent of Code  (Read 109958 times)

Re: Advent of Code
« Reply #1075 on: 22 December, 2020, 02:35:10 pm »
Day 22 part 1 was nice and straightforward and satisfying. Part 2 just makes my eyes glaze over.

Re: Advent of Code
« Reply #1076 on: 22 December, 2020, 02:37:21 pm »
I purposely put in just one (although the other bits of rough sea are placed at random so it another could easily appear by random) in order to be underwhelming for people who aren't printing out the final map.

Writing something to fake the whole input is an interesting exercise. One thing I didn't think about is that not only do the edges of adjacent tiles need to match but the 4 tiles in an inner corner all need to have the same symbol ( . or # ) at that corner, which means there's some careful selection of edge "numbers" that need to be done. Ho hum.
"Yes please" said Squirrel "biscuits are our favourite things."

Re: Advent of Code
« Reply #1077 on: 22 December, 2020, 02:39:14 pm »
Day 22 part 1 was nice and straightforward and satisfying. Part 2 just makes my eyes glaze over.

(click to show/hide)
"Yes please" said Squirrel "biscuits are our favourite things."

Davef

Re: Advent of Code
« Reply #1078 on: 22 December, 2020, 02:51:42 pm »
I purposely put in just one (although the other bits of rough sea are placed at random so it another could easily appear by random) in order to be underwhelming for people who aren't printing out the final map.

Writing something to fake the whole input is an interesting exercise. One thing I didn't think about is that not only do the edges of adjacent tiles need to match but the 4 tiles in an inner corner all need to have the same symbol ( . or # ) at that corner, which means there's some careful selection of edge "numbers" that need to be done. Ho hum.
To make a puzzle you just start at the top left with a couple of random 10 bit numbers and then work across from there, setting the first bit of the next to be the last bit of the previous and making sure you don’t reuse a number or it’s reverse

That sets the edges for all the tiles. Then throw them up in the air and see how they land.

Davef

Re: Advent of Code
« Reply #1079 on: 22 December, 2020, 04:19:55 pm »
Day 22 part 1 was nice and straightforward and satisfying. Part 2 just makes my eyes glaze over.
To see what was going on, for printing purposes I replaced the 50 odd numbers with letters A-ZA-z and ran part 1 again.

If I had a bigger screen I would have used the proper names of the tanks from top trumps.

This led to a better understanding of how to store the data and work efficiently. Then a few optimisations such as caching previous results and looking for simple cases (if there is no recursion you can see straightaway which player will win) and I left it to run on my grindingly slow laptop. It took 20 minutes which is probably 5 minutes on a decent pc. I still feel I am missing something.

Re: Advent of Code
« Reply #1080 on: 22 December, 2020, 04:24:18 pm »
Day 22 part 1 was nice and straightforward and satisfying. Part 2 just makes my eyes glaze over.

It definitely took me longer to understand the instructions for part 2 than to implement it, given a tidy implementation of part 1.

Day 20 was too much code for very little satisfaction. It looks like a lot of people just couldn't be bothered as I just got round to it today and still < 10,000
Quote from: tiermat
that's not science, it's semantics.

Re: Advent of Code
« Reply #1081 on: 22 December, 2020, 09:29:52 pm »
If I had a bigger screen I would have used the proper names of the tanks from top trumps.

With my usual settings (10 point Ubuntu Mono font) I can have a 546x131 char terminal window open on this monitor and, yes, it's completely readable without needing any scaling.
"Yes please" said Squirrel "biscuits are our favourite things."

Re: Advent of Code
« Reply #1082 on: 22 December, 2020, 09:47:07 pm »
Day 22 here, sort of:
https://docs.google.com/spreadsheets/d/1hMM1Uort-P4v3FoS3QETp7VmuIbxFlj6gUOzQknQLW8/edit?usp=sharing

(click to show/hide)

Davef

Re: Advent of Code
« Reply #1083 on: 23 December, 2020, 02:50:38 pm »
Day 23 is now chugging away in the background and will take a few hours despite my fine tuning.

There is obviously a better way but I suspect the computer will find the answer before I come up with a better way of doing it.

Re: Advent of Code
« Reply #1084 on: 23 December, 2020, 04:00:14 pm »
Day 23 runs in a second for me. The really naive solution in perl I knocked up for part 1 was never going to perform well enough for part 2 so I did it properly in C.

(click to show/hide)

3 stars to go (day 25 part 2 is usually just having the other 49 stars).
"Yes please" said Squirrel "biscuits are our favourite things."

Davef

Re: Advent of Code
« Reply #1085 on: 24 December, 2020, 09:12:11 am »
Day 24 was nice and easy.

Re: Advent of Code
« Reply #1086 on: 24 December, 2020, 10:58:36 am »
(click to show/hide)
"Yes please" said Squirrel "biscuits are our favourite things."

Davef

Advent of Code
« Reply #1087 on: 24 December, 2020, 12:28:42 pm »
(click to show/hide)

Ben T

Re: Advent of Code
« Reply #1088 on: 24 December, 2020, 04:19:34 pm »
Day 22 part 1 was nice and straightforward and satisfying. Part 2 just makes my eyes glaze over.
To see what was going on, for printing purposes I replaced the 50 odd numbers with letters A-ZA-z and ran part 1 again.

If I had a bigger screen I would have used the proper names of the tanks from top trumps.

This led to a better understanding of how to store the data and work efficiently. Then a few optimisations such as caching previous results and looking for simple cases (if there is no recursion you can see straightaway which player will win) and I left it to run on my grindingly slow laptop. It took 20 minutes which is probably 5 minutes on a decent pc. I still feel I am missing something.

not seeing what the optimisation is.
Are you actually getting any cache hits?
I've implemented a cache but not getting any hits. I've checked the equality comparison and made it so that it mirrors, i.e. if player 1 won with a hand that player 2's now got, that it returns player 2 winning. But still grinding away with no cache hits.



Re: Advent of Code
« Reply #1089 on: 24 December, 2020, 06:43:17 pm »
(click to show/hide)

(click to show/hide)
Quote from: Kim
Paging Diver300.  Diver300 to the GSM Trimphone, please...

Davef

Re: Advent of Code
« Reply #1090 on: 24 December, 2020, 07:12:17 pm »
Day 22 part 1 was nice and straightforward and satisfying. Part 2 just makes my eyes glaze over.
To see what was going on, for printing purposes I replaced the 50 odd numbers with letters A-ZA-z and ran part 1 again.

If I had a bigger screen I would have used the proper names of the tanks from top trumps.

This led to a better understanding of how to store the data and work efficiently. Then a few optimisations such as caching previous results and looking for simple cases (if there is no recursion you can see straightaway which player will win) and I left it to run on my grindingly slow laptop. It took 20 minutes which is probably 5 minutes on a decent pc. I still feel I am missing something.

not seeing what the optimisation is.
Are you actually getting any cache hits?
I've implemented a cache but not getting any hits. I've checked the equality comparison and made it so that it mirrors, i.e. if player 1 won with a hand that player 2's now got, that it returns player 2 winning. But still grinding away with no cache hits.
I get a lot of cache hits but I suppose it could vary with  input could vary but it seems unlikely.
The other optimisation is based on the top trump killer card theorem I just made up. There are scenarios where you can see who will win without actually playing. The other optimisation was how to store the data so that each iteration was very efficient.

Davef

Re: Advent of Code
« Reply #1091 on: 24 December, 2020, 07:41:19 pm »
(click to show/hide)

(click to show/hide)
(click to show/hide)

Re: Advent of Code
« Reply #1092 on: 24 December, 2020, 09:14:31 pm »
Day 22 part 1 was nice and straightforward and satisfying. Part 2 just makes my eyes glaze over.
To see what was going on, for printing purposes I replaced the 50 odd numbers with letters A-ZA-z and ran part 1 again.

If I had a bigger screen I would have used the proper names of the tanks from top trumps.

This led to a better understanding of how to store the data and work efficiently. Then a few optimisations such as caching previous results and looking for simple cases (if there is no recursion you can see straightaway which player will win) and I left it to run on my grindingly slow laptop. It took 20 minutes which is probably 5 minutes on a decent pc. I still feel I am missing something.

not seeing what the optimisation is.
Are you actually getting any cache hits?
I've implemented a cache but not getting any hits. I've checked the equality comparison and made it so that it mirrors, i.e. if player 1 won with a hand that player 2's now got, that it returns player 2 winning. But still grinding away with no cache hits.
I get a lot of cache hits but I suppose it could vary with  input could vary but it seems unlikely.
The other optimisation is based on the top trump killer card theorem I just made up. There are scenarios where you can see who will win without actually playing. The other optimisation was how to store the data so that each iteration was very efficient.

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?
"Yes please" said Squirrel "biscuits are our favourite things."

Re: Advent of Code
« Reply #1093 on: 25 December, 2020, 09:55:49 am »
Day 25.  I get an answer which passes the test case and meets all the criteria but its not the correct answer!!


(click to show/hide)

Ben T

Re: Advent of Code
« Reply #1094 on: 25 December, 2020, 10:07:29 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.

Re: Advent of Code
« Reply #1095 on: 25 December, 2020, 11:53:31 am »
Day 25.  I get an answer which passes the test case and meets all the criteria but its not the correct answer!!


(click to show/hide)

Yes, 2020 day 25 took more time reading and re-reading than it did actually writing the code.

(click to show/hide)
"Yes please" said Squirrel "biscuits are our favourite things."

Davef

Re: Advent of Code
« Reply #1096 on: 25 December, 2020, 04:12:03 pm »
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.
My list copying is minimal as I have each players hand as string. The game state is the two strings concatenated with an * in between.

For efficiency each player is actually slightly more than a string - it also has a number of characters to ignore off the beginning which makes for less work but that is thrown away when I save.

I actually misunderstood the instructions about repeated states in a game and had implemented it globally before I reread and added it locally too.

Davef

Re: Advent of Code
« Reply #1097 on: 25 December, 2020, 04:18:44 pm »
Day 25.  I get an answer which passes the test case and meets all the criteria but its not the correct answer!!


(click to show/hide)
If you look at the Wikipedia articule on modular arithmetic https://en.wikipedia.org/wiki/Modular_arithmetic there is an efficient c routine for raising a to the power of b.  I still had a copy from last year. That said it would would be relatively quick without it.

Today was my best ranking - in the 2000s because I was on early morning turkey duty.

I also woke up knowing the correct way to do day 23. Problem solving whilst asleep is not something I have done since an undergraduate decades ago.

Davef

Re: Advent of Code
« Reply #1098 on: 25 December, 2020, 09:24:45 pm »
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.

Re: Advent of Code
« Reply #1099 on: 26 December, 2020, 08:07:12 am »
(click to show/hide)