Logo

dev-resources.site

for different kinds of informations.

Advent of code Day 21

Published at
12/21/2021
Categories
adventofcode
adventofcode2021
caching
memoization
Author
marcoservetto
Author
13 person written this
marcoservetto
open
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.

memoization Article's
30 articles in total
Favicon
The intricacies of implementing memoization in Ruby
Favicon
Memorização em JavaScript
Favicon
When do (and don’t) children re-render in React?
Favicon
Memoization in React: When It Helps and When It Hurts
Favicon
Never call the same function twice (with memoization)
Favicon
Optimizing React Performance with Memoization and React.memo
Favicon
Optimizing React Component Performance with Memoization and React.memo
Favicon
Optimizing React Performance with memoization and React.memo
Favicon
Optimizing React Performance with Memoization and React.memo
Favicon
Optimizing React Component Performance with Memoization
Favicon
Кеширования в React - все ли так однозначно?
Favicon
Understanding and Implementing Memoization in React
Favicon
Caching & Memoization with state variables
Favicon
How to implement Memoization in your React projects
Favicon
Memoization in JavaScript
Favicon
Mastering React: A Deep Dive into Memoization and Component Optimization
Favicon
How to Use Memoization in React for Better Performance
Favicon
Deep Dive into Functional Programming in Javascript
Favicon
Demystifying React Memoization: Understanding React.memo() and the useMemo hook
Favicon
JavaScript Memoization
Favicon
Maximizing Performance: How to Memoize Async Functions in JavaScript
Favicon
Retos JS. Calculando factoriales muy grandes con JS.
Favicon
Memoizing DataFrame Functions: Using Hashable DataFrames and Message Digests to Optimize Repeated Calculations
Favicon
Memoize a React component
Favicon
Memoization in JavaScript and React
Favicon
Memoization in Ruby
Favicon
Advent of code Day 21
Favicon
Understanding Memoization in Javascript
Favicon
Reselect, but in OCaml
Favicon
Memoization in Javascript

Featured ones: