Advent of code Day 21
Marco Servetto
Posted on December 21, 2021
The two parts for the problem of today are well divided, so I will present them one at a time.
Or, if you prefer, you can just look to my comments on you tube:
(https://www.youtube.com/watch?v=61v1SNA79V0)
Part 1 is really trivial.
Note the trick with the modulo arithmetic, where we store a position that is 1 less than the intended position of the player.
D100 = Data:{
var I rolled = 0I
var I seed = 0I
mut method I roll()=(
\rolled(\rolled+1I)
\seed((if \seed>=100I 0I else \seed)+1I)
\seed
)
}
Player = Data:{
var I pos
var I points = 0I
mut method Void turn(mut D100 that) =(
tot = that.roll()+that.roll()+that.roll()
\pos((\pos+tot).mod(10I)) //pos from 0--10, real pos is +1
\points(\points+\pos+1I)
)
read method Bool won() = \points>=1000I
}
Main=(
p1 = Player(pos=0I) //1-1
p2 = Player(pos=2I) //3-1
dice = D100()
while !p1.won() && !p2.won() (
p1.turn(dice)
if !p1.won() (p2.turn(dice))
)
if p1.won() (
Debug(S"p2 loses for %p2.points(), %dice.rolled(), %(p2.points()*dice.rolled())")
)
if p2.won() (
Debug(S"p1 loses for %p1.points(), %dice.rolled(), %(p1.points()*dice.rolled())")
)
//p1 loses for 671, 1338, 897798
)
Part 2 is much more interesting, and it was feasible thanks to @Cache.Lazy; in this way our 'recursive' call may simply return a pre-computed value.
Report = Data:{
Num p1Wins
Num p2Wins
method Bool open() = \p1Wins+\p2Wins==0Num
method This +(This that) = This(
p1Wins=this.p1Wins()+that.p1Wins(),
p2Wins=this.p2Wins()+that.p2Wins()
)
}
State = Data:{
I p1Pos
I p2Pos
I p1Score = 0I
I p2Score = 0I
method This turn(I p1Roll) = (
(p1Pos0,p2Pos0,p1Score0,p2Score0) = this
p1Pos = (p1Pos0+p1Roll).mod(10I) //from 0--10, real pos is +1
p1Score = p1Score0+p1Pos+1I
This(p1Pos=p1Pos,p2Pos=p2Pos0,
p1Score=p1Score,p2Score=p2Score0)
)
method This turn(I p2Roll) = (
(p1Pos0,p2Pos0,p1Score0,p2Score0) = this
p2Pos = (p2Pos0+p2Roll).mod(10I) //from 0--10, real pos is +1
p2Score = p2Score0+p2Pos+1I
This(p1Pos=p1Pos0,p2Pos=p2Pos,
p1Score=p1Score0,p2Score=p2Score)
)
method Report directWin() = {
(p1Pos,p2Pos,p1Score,p2Score) = this
X[p1Score<21I || p2Score<21I]
if p1Score>=21I return \(p1Wins=1\ p2Wins=0\)
if p2Score>=21I return \(p1Wins=0\ p2Wins=1\)
return \(p1Wins=0\ p2Wins=0\)
}
@Cache.Lazy method Report wins() = {
Debug(this)
var res = this.directWin()
if !res.open() return res
r = Range(1I to=4I)
for a1 in r,for a2 in r,for a3 in r {
stateA = this.turn(p1Roll=a1+a2+a3)
resA = stateA.directWin()
if !resA.open() return res+=resA
return for b1 in r,for b2 in r,for b3 in r {
stateB = stateA.turn(p2Roll=b1+b2+b3)
resB = stateB.directWin()
if !resB.open() return res+=resB
return res+=stateB.wins()
}
}
return res
}
}
Main = (
s = State(p1Pos=0I,p2Pos=2I)
Debug(s.wins())
//Report(p1Wins=48868319769358,p2Wins=22432440913119)
)
}
What do you think? with minor modifications I could combine automatic parallelism and automatic caching for an even faster version.
💖 💪 🙅 🚩
Marco Servetto
Posted on December 21, 2021
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.