DEV Community

Marco Servetto
Marco Servetto

Posted on

Advent of code Day 15

Ok, also today is sorted.
We just had to implement AStar.
I'm not that happy with the result, but to make part 1 and part 2 both work I had to make two different matrix types, since they have different sizes. Below I show the code for part 2.

SmallMatrix = (
  input = Fs.Real.#$of().read(\"input")
  row=0I.acc()(for e in input.split(S.nl()) \addOne) 
  col=0I.acc()(for e in input.split(S.nl())().split() \addOne)
  Collection.matrix(I.List, row=row col=col)
  )
Matrix = (
  input = Fs.Real.#$of().read(\"input")
  row=0I.acc()(for e in input.split(S.nl()) \addOne) *5I
  col=0I.acc()(for e in input.split(S.nl())().split() \addOne) *5I
  Collection.matrix(I.List, row=row col=col)
  )
Coords = Collection.list(Matrix.Coord)
Near = {class method Coords (Matrix.Coord that) = Coords()((
  (new=that.with(row=\row-1\) catch error Any _ void \add(new))
  (new=that.with(row=\row+1\) catch error Any _ void \add(new))
  (new=that.with(col=\col-1\) catch error Any _ void \add(new))
  (new=that.with(col=\col+1\) catch error Any _ void \add(new))
  ))}
Path = Data.AddList:Data:{ //here it is crucial to use Cache.Lazy!
  Coords that
  Matrix matrix
  @Cache.Lazy method I cost() = 
    0I.acc()(for c in this.that().vals(1I to=\size) \add(this.matrix().val(c)))
  }
PopMin ={class method Path (mut Path.List that)=(
  res = that.right()
  that.removeRight()
  res //assuming the list is kept sorted
  )}
SortedPush ={class method Void (mut Path.List that, Path path) = {
  for e in that, i in Range(that.size()) //as soon as smaller cost
    if e.cost()<=path.cost() return that.add(i,val=path)
  return that.add(right=path)
  }}
Map = Collection.map(key=Matrix.Coord val=Path)

AStar={ //can probably remove some fields
  Matrix.Coord source
  Matrix.Coord dest
  Matrix matrix
  mut Path.List fringe
  mut Map map
  class method mut This(
  ,,Matrix.Coord source,Matrix.Coord dest,Matrix matrix,
  ,,mut Path.List fringe,mut Map map)
  class method mut This(
  ,,Matrix.Coord source,Matrix.Coord dest,Matrix matrix) = (
    left = Path(\[source],matrix=matrix)
    This(source=source, dest=dest,
    ,,matrix=matrix,fringe=\[left], map=\[key=source,val=left])
    )
  mut method I () = {loop(
    //invariant: if it is in the fringe, it is in the map
    fringe = \#fringe
    map    = \#map
    imm best   = PopMin(fringe)
    (cost) = best
    (right) = best.that()
    oPath=map.val(key=right)
    X[oPath.isPresent() && oPath.val()==best]
    if right==\dest return cost
    for c in Near(right) (
      bestC = best.with(\that.withAlso(right=c))
      o = map.val(key=c)
      win = !o.isPresent() || o.val().cost()>bestC.cost()
      if win (
        map.put(key=c, val=bestC)
        SortedPush(fringe,path=bestC)
        if o fringe.removeAll(val=o.val())
        )
      )
    )}
  }
Grow={class method I (I that, I val)=val.acc()(
  for i in Range(that) (
    if \val==9I \val(1I)
    else \addOne
    )
  )}
Main=(
  input = Fs.Real.#$of().read(\"input")
  row=0I.acc()(for e in input.split(S.nl()) \addOne) 
  col=0I.acc()(for e in input.split(S.nl())().split() \addOne)
  imm sm = SmallMatrix(\()(for line in input.split(S.nl()) for e in line.split() (
    \add(I(string=e))
    )))
  imm m =(//this block is needed to promote the mut mm to imm m
    mm = Matrix(\()(for r in Range(row*5I), for c in Range(col*5I) \add(0I)))
    for r in Range(5I), for c in Range(5I) (
      for ri in Range(row), for ci in Range(col) (
        val = Grow(r+c,val=sm.val(row=ri,col=ci))
        mm.set(row=(r*row)+ri col=(c*col)+ci val=val)
        )
      )
    mm
    )
  res = AStar(source=\(row=0I,col=0I),
  ,,dest=\(row=(row*5I)-1I,col=(col*5I)-1I),matrix=m)()
  Debug(S"Hello world %res")//part1:366, part2: 2829
  )
Enter fullscreen mode Exit fullscreen mode

Ultimately, I would like to revisit this code, and see if I can use my traits and meta-programming features to make an abstract version of A* that can be used on any kind of navigable datatype with costly paths..

Discussion (0)