https://kotlinlang.org logo
Join Slack
Powered by
:christmas_tree: Day 22 : Solutions Thread
# advent-of-code
a
🎄 Day 22 : Solutions Thread
Quite a straightforward puzzle today. Just handling cards as queues & a bit of recursion.
Crab Cards
f
@andyb I have a similar variant, only I pass on 
true
as 
recurse
when called recursive (line 25 in your code above)
I tried your variant - not playing recursive on multiple levels and the tests pass (runtime of ≈6ms compared to ≈50ms on the recursive variant), but I don’t understand why…
is this just by chance?
a
Hi @Fredrik Rødland not sure I understand your question. Are you comparing the timings of my version compared to yours or between non-recursive vs recursive runs of my code?
f
no - I don’t understand why we get the correct answer when you call 
playGame(hand1.take(player1), hand2.take(player2))
instead of 
playGame(hand1.take(player1), hand2.take(player2), true)
in line 25 of your code.
a
That's because of the guard condition in this when statement. It ignores the first branch if the recurse flag is false and so only compares the cards held by each player (i.e. it always uses the 'else'. branch.
Copy code
val player1Wins = when {
    (recurse && player1 <= hand1.size && player2 <= hand2.size) -> playGame(hand1.take(player1), hand2.take(player2)).first
    else -> player1 > player2
}
f
isn’t that the same as only recurse one level?
so if you’re recursing, you’re calling playGame with recurse == false, and it will only recurse one level
a
The whole game is the top-level of the recursion
f
in the example of https://adventofcode.com/2020/day/22 Game 4 is a recursive call from game 3, which is recursive call from game 1
a
I see what you are saying, it looks like I messed up & it will only recurse 1 level down. I will change my code. Bizarre that my answer was correct
f
if you call playGame(hand1.take(player1), hand2.take(player2), false) in your line 25 - you never end up in game 4
so - I find it strange that it’s working (gives the correct answerr) anyway
you’re code is quite a lot faster though 😉
and gives the correct answer both for the example, my input and obviously your input
so I’m starting to think there could be more to it?
a
If the sub-recursions didn't matter then I'd expect to get the same answer for both Part 1 & Part 2. I can't see any reason this works
f
neither can I… bizarre
n
a
It's beyond my maths this afternoon to see if it would always work
n
Regardless of whether it ultimately is correct, tbh I feel like it's a bit confusing
to pass a boolean flag "recurse" into a recursive call
a
I could have named it better 🙂
n
I am biased of course, but I think my version is clearer. The function looks at the top 2 cards each round, and decides on the spot if recursion is necessary. If yes, it makes the copy and calls, otherwise decides the round by larger card
f
also a thought: I think it might be enough to check for one of the players hands in 
seen
a
I have been debating this on another forum, I can't see a reason why the order of the 2nd hand should be the same for a specific 1st hand
f
1. does it matter?
2. if it’s and endless loop any player’s hand will be recurring at some time or another
a
Yep, because you are not necessarily in a loop if you haven't encounter the same pair of 1st numbers before
f
but the description does not say that it applies to both hands:
Copy code
Before *either* player ... same players' decks ...
so it’s really either imo
so checking one of them is enough
for my input checking player 1 is faster, checking player 2 is slower, but still works
a
It's about detecting sequences of plays that will repeat. If player 1 has [5,4,1] & player 2 has [6,3,2] next hands -> [4,1] & [3,2,6,5] but player 1 has [5,4,1] & player 2 has [3,2,6] next hand -> [4,1,5,3] & [3,2} Therefore this is not a loop (yet) It does seem that just checking 1 hand works though but I can't see why
f
I agree that it’s not a loop yet. But the description does not say “detect a loop”. i says if either player encounters the same hand, player 1 wins. furthermore it says that this will prevent an infinite game (which it will)
at least to my understanding
a
I understand it differently as the apostrophe is after the 's' in players which indicates both players. It is a bit ambiguous though
Copy code
same players' decks
f
hm - I agree….
😉
n
I was also in a discussion of whether something better than storing a copy of both players hands can be done
As it's very expensive
The score actually hints at the idea of a hashing function
The question is, is the score, or a similar function, a perfect hash, on the input data
t
I spent about 30 minutes debugging something because I didn't read the recursion bit properly (passing not the whole deck). So that was fun. Otherwise, pretty easy and I think my code is nice and clean. I dunno, I'll write it up later.
👏 1
p
only checking one hand doesn't work in every case, e.g. this input that a colleague received. accepted answer was 33745
input.txt
using the score as a hashing function gives the right answer for the four inputs i've got access to...
IMHO the instructions unambiguously say that player 1 wins if there was a single previous round where the two players had the same cards, in the same order 😁
n
yeah, I agree with the latter. As for using score as a hash, it seems like an interesting point, I'd have to put the mental effort in to convince myself though. It doesn't seem obviously true that its a perfect hash, if you have say integers 1 to N as cards
f
@Paul Martin thanks for the input above
this input also verifies that @andyb needs to call his recursive function with 
true
for recursion
changing the code to check the scores yields the same result, but doesn’t run significantly quicker…
n
i guess not much of the time is being spent there
it doesn't change the complexity
hmm, that seems strange though, I would expect it to make a significant difference
Here's the innermost loop where all the work is being done:
Copy code
if (Pair(player1, player2) in seen) return player1 to true
        seen += Pair(Deck(player1), Deck(player2))
        val player1Won = if (player1.first() < player1.size && player2.first() < player2.size) {
            recursiveCombat(
                Deck(player1.subList(1, 1 + player1.first().toInt())),
                Deck(player2.subList(1, 1 + player2.first().toInt()))
            ).second
        } else player1.first() > player2.first()

        val (winDeck, loseDeck) = if (player1Won) player1 to player2 else player2 to player1
        winDeck.addLast(winDeck.removeFirst())
        winDeck.addLast(loseDeck.removeFirst())
So, the first line is hashing, which yes does involve looking at every value in both decks
The second line is making a deep copy to insert into the container
Other than those two things, the only thing we do which is significant work (other than the recursive call itself which doesn't count), are the partial deep copies for the recursion
So it really seems like making the full deep copies has to be significant
just realize I should be able to at least improve this so that I don't have to hash twice
e
https://github.com/ephemient/aoc2020/blob/main/kt/src/main/kotlin/io/github/ephemient/aoc2020/Day22.kt very late because I spent almost a whole day attempting failing to optimize based on a misunderstanding of the requirements (I was recursing on deck[:-1] instead of deck[:card])
p
there were some questions about the interpretation of the rule which breaks out of infinite loops. for most inputs the two different interpretations give the same answer, but someone i know got one which gives different answers for the different interpretations of that rule. the accepted answer for this input was 32054. does your solution give the right answer? 🙂
day-22-input.txt
b
That's post clean up. Spent some time trying to deal with the fact that it is deck 1 AND deck 2 that have to be the same in the history
also I stole @todd.ginsberg idea of Objects.hash, I was using .hash and pairs and hash his way is shorter
👍🏻 1
@Paul Martin Yep that was my exact problem initially
t
@bjonnh
Game doesn't care who wins, but I'm going for the crab
Now we know where your loyalties are... 🦀
glitch crab 1
🦀 1
e
the game is rigged… player 2 has card 50, which will never lose
player 1 loses the non-recursive game (and given the text, we must be player 1); the only way player 1 can win the top-level recursive game is if it loops
I used `setOf("$deck1|$deck2")`; reducing to a single Int means there's potential collisions. although I did test that and didn't run into any collisions on my input, so it's probably fine
there's 51! possible states for the top-level game (50! permutations of the cards, and 51 ways to divide that into player1/player2), which is about 2^220. clearly our simulation doesn't actually hit that many game states; I count 35154 for my input. if we assume equal distribution for a 32-bit hash, I think we have about a 2^-158 chance of collision. so it's very probably fine.
4 Views
Open in Slack
PreviousNext
Powered by