Fork me on GitHub
#adventofcode
<
2020-12-22
>
markw05:12:17

tonight’s puzzle… reading comprehension

3
Vincent Cantin06:12:01

I was convinced that I was at my disadvantage, reading a very long text while having ADHD, but it turned out that I was not slower than others.

Charles Fourdrignier10:12:17

On this one, I miss a detail which costs me at least 20 minutes. 😄

Vincent Cantin05:12:06

Day 22 answers thread - Post your answers here

peterc06:12:47

Nice! What was the run time for part2 for you?

Vincent Cantin06:12:16

4.5 seconds on my computer, about half of anybody else’s computer. The code could me improved, I am sure.

rjray06:12:27

Finally, a pair for which Clojure is wonderfully suited… https://github.com/rjray/advent-2020-clojure/blob/master/src/advent_of_code/day22.clj

👍 15
rjray06:12:44

Pretty sure I can get that shorter. Tomorrow.

rjray06:12:13

Also, the title of this thread is “Day 21 answers…” 🙂.

😝 3
👌 3
peterc06:12:25

ahh I didnt look at your code yet, my part-2 answer was chugging along, so its probably not correct

markw06:12:25

waiting for part 2 to finish.. must have bug somewhere

markw06:12:43

sample input worked as usual. I hope this isn’t another “Find the math trick” problem

Vincent Cantin06:12:26

@markw no trick, it’s a pure “understand the question” problem.

Average-user06:12:46

For me the bug was that I was finishing the round when seeing a repeated configuration, but it has to be the game. Which, if one thinks about it, makes much more sense.

Vincent Cantin06:12:38

This rules of avoiding repeating configuration is similar in the game of Go.

12
12
Average-user06:12:28

Mine runs in 4sec. But probably changing lists to double-queueshould improve that. I missed clojure's queues

peterc06:12:10

@markw did you check the infinite loop test case?

Average-user06:12:45

I see some queues there, nice

Vincent Cantin07:12:40

I avoided using a queue when I realized that it would not display its values in my REPL, I chose a vector instead.

⏱️ 3
alekszelark07:12:25

I firstly went with vectors, but after the part 1 had been solved I changed my mind.

Vincent Cantin07:12:21

What made you change your mind? Worry of performances regarding recursion?

alekszelark07:12:27

Lots of subvecs, with pop it looks a bit nicer and simpler.

alekszelark07:12:35

To be honest, they did scare me. Because last year at the same day was the hardest puzzle with a deck of cards as well.

3
markw07:12:20

@U1NLKFVC4 yeah i checked for that… I thought I had found the problem when I realized I misread the rules for how many cards to include in a subgame (which insidiously gave the correct answer on test input even with the bug). But I fixed that, and also verified the infinite loop case is handled.. and it’s still running. I’ll try again tomm

3
nbardiuk07:12:52

Today was even fun, I was afraid of complex combinatorics part 2 https://github.com/nbardiuk/adventofcode/blob/master/2020/src/day22.clj

👍 9
Charles Fourdrignier10:12:45

I should definitely look to queues ! Better performance and neater syntax.

nbardiuk14:12:19

today problem is hard to compare, different inputs have very different number of steps. Using the same code on my machine my input runs 1s, @U051HUZLD's750ms and @U1EP3BZ3Q’s 150ms

👍 9
3
euccastro14:12:51

today my daughter was definitely rooting for the crab! my solution runs in half a second 8-10sec (that's with me being lazy and using lists/sequences instead of vectors/queues) https://github.com/euccastro/advent-of-code-2020/blob/master/src/advent/day22.clj

👍 3
euccastro14:12:01

runs in a little under 10s without memoization, so memoization seems to have a bigger impact on performance than picking the optimal data structures, and it only involves a one word change 🙂 wait, I lie... my solution takes 8-10 seconds. memoization made it finish in half a ms... the second time I run it! 😄. it's pretty useless because when we recur we take a different number of cards each time. I added memoization when I had missed that detail

euccastro14:12:07

@U076FM90B you seem to interpret that a game should end when the deck of either player has already been seen? https://github.com/nbardiuk/adventofcode/blob/master/2020/src/day22.clj#L40

euccastro14:12:46

my interpretation is that the game ends only when both decks have been seen in a given round. it's curious that both approaches work?

genmeblog14:12:53

> if there was a previous round in this game that had exactly the same cards in the same order in the same players' decks

genmeblog15:12:51

if any of the player has been seen game stops

nbardiuk15:12:01

I have trouble interpreting this statement. I guess it does not make a difference in the end because player 1 wins regardless of what deck is repeated

euccastro15:12:28

see where the apostrophe is placed. I think that basically means you bail if you see a previous game state again

euccastro15:12:29

yes, but maybe player 2 would have won if the game hadn't been aborted?

euccastro15:12:59

(obvs. that isn't happening in your input, so who knows)

3
misha15:12:38

seen deck of only one player is enough to end game, not both players' decks at the same time.

(or (seen1 deck1) (seen2 deck2))
not
(and (seen1 deck1) (seen2 deck2))

misha15:12:17

regardless, you might want to run or option (as it terminates faster), and see whether you'll get a star

benoit15:12:39

My solution https://github.com/benfle/advent-of-code-2020/blob/main/day22.clj Why would you put this very important sentence in parenthesis 🙂 Wasted so much time. (the quantity of cards copied is equal to the number on the card they drew to trigger the sub-game)

👍 12
👆 3
euccastro17:12:15

yes, I've just checked that the or version works in my data, and runs in under 1/3 of the time

euccastro17:12:25

my interpretation is not even (and (seen1 deck1) (seen2 deck2)), but an even stricter (seen [deck1 deck2]) (e.g., bail out only if both decks have been seen together in the same turn)

alekszelark17:12:24

my interpretation is the same

peterc17:12:37

yeah I implemented the stricter condition as well, though it is interesting to consider if the other player's deck will also be the same in the less strict case

peterc17:12:59

I get the same result as well using the less restrictive case, and my time goes from ~8s to under 1s

alekszelark19:12:36

Also a good one 🙂 My first attempt to refact the function looked exactly the same. iterate dec is a bit more natural for me here, cause there is no need for some extra numbers.

👍 3
rjray20:12:33

I must be learning from this experience, because my algorithm isn’t that much different than zelark’s (though I just used lists instead of queues or even vectors).

Vincent Cantin07:12:59

The funniest part of today’s puzzle is that the crab won the card game. Twice.

🦀 12
rjray20:12:02

Must have been your data. For my data, I won the second game 🙂.

Vincent Cantin02:12:28

... based on the sample data.

Vincent Cantin08:12:17

Yeah, you know what? We should celebrate on the last day of the AoC. How about a Post-AoC online meetup party?

👍 9
alekszelark08:12:34

That’s a good idea. I also thought about something like that.

bananadance 6
nbardiuk08:12:27

I am not big fan of parties but it would be nice to see everybody and say hi

nbardiuk08:12:09

We could make a watch party of r/adventofcode visualisations and jokes

markw16:12:57

Well after running all night my program did the honorable thing and committed seppuku

markw16:12:47

I’m actually a bit stumped.. I track seen states, verified that on the test loop game, fixed the bug with taking n cards in the subgames, works on sample, hangs forever on actual input

markw16:12:53

Only other thing I can think of is that the confusion around or for seeing prior games. I interpreted that line as you need to see the entire game state (both decks) again

euccastro17:12:38

maybe post your current code? or try someone else's solution on your input data? to double check you haven't been given something broken

markw17:12:06

so bizarre.. so after changing to the interpretation of “seeing” a game as meaning either deck, it terminates… with the wrong answer. I’ll post what I’ve got, apologies for the mess as I’ve hacked it apart trying to fix it and it’s now pretty messy

markw17:12:40

my input is hard coded up top

alekszelark17:12:33

@markw ran my solution with your input, got 36463 with a strict condition

markw17:12:05

ok yeah i figured it was a bug in my solution

markw17:12:19

probably something obvious that i’m just not getting, but it doesn’t help that the test input works perfectly, line-by line

alekszelark17:12:55

I guess this condition in a wrong place (if (= winner :player1) , the game should instantly end if there was a previous round in this game that had exactly the same cards.

alekszelark17:12:13

the test input doesn’t trigger that condition, that’s why it works.

markw18:12:08

Ugh… well that was dumb. Wins the game not the round… oops.

AC19:12:00

I was thrown by (what seemed to me) as inconsistent use of “game” and “sub-game”

rjray20:12:02

Must have been your data. For my data, I won the second game 🙂.