marcoservetto

Marco Servetto

Posted on December 21, 2021

Advent of code Day 21

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
  )
Enter fullscreen mode Exit fullscreen mode

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)
  )
}
Enter fullscreen mode Exit fullscreen mode

What do you think? with minor modifications I could combine automatic parallelism and automatic caching for an even faster version.

💖 💪 🙅 🚩
marcoservetto
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.

Related

Advent of code Day 21
adventofcode Advent of code Day 21

December 21, 2021