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
)
```

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)