From 207febef9924c8fa5391185e75d42a7ea480bb38 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 10 Aug 2026 11:11:18 -0700 Subject: Chapter 31: Software Drawing, Time, and Graphical Games Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: Jun Kawasaki Co-authored-by: Claude Opus 5 --- docs/chapter31/examples/Dijkstra.smp | 71 ++++++++++++++++++++++++++++++++++++ 1 file changed, 71 insertions(+) create mode 100644 docs/chapter31/examples/Dijkstra.smp (limited to 'docs/chapter31/examples/Dijkstra.smp') diff --git a/docs/chapter31/examples/Dijkstra.smp b/docs/chapter31/examples/Dijkstra.smp new file mode 100644 index 00000000..6591b310 --- /dev/null +++ b/docs/chapter31/examples/Dijkstra.smp @@ -0,0 +1,71 @@ + +// An implementation of +// https://sampleprograms.io/projects/dijkstra/ + +val shortestPath = { !sys.aryi64 matrix, int nodes, int src, int dst -> + i64 infinity = sys.integer.MAX_I64; + var visited = new sys.adt.bitset(); + // All nodes are infinitely far from each other, except the starting point + var dist = new i64[nodes]{ int i -> i == src ? 0 : infinity; }; + + i64 result = -1; + int count = 0; + while( count < nodes && result < 0 ) { + int nearest = -1; + i64 best = infinity; + for( int node = 0; node < nodes; node++ ) + if( !visited.get(node) && dist[node] < best ) { + nearest = node; + best = dist[node]; + } + if( nearest < 0 ) count = nodes; + else { + if( nearest == dst ) return best; + visited.set(nearest); + for( int node = 0; node < nodes; node++ ) { + u32 index = nearest*nodes + node; + i64 weight = matrix.get(index); + if( weight > 0 && !visited.get(node) && best+weight < dist[node] ) + dist[node] = best+weight; + } + } + count++; + } + return result; +}; + +val usage = { -> + sys.io.p("Usage: please provide three inputs: a serialized matrix, a source node and a destination node\n"); + return 0; +}; + +val main = { u8[~][] args -> + // Exactly 3 args + if( args# != 4 ) return usage(); + // First is a serialized square matrix of positive numbers + var matrix = sys.aryi64.parseAryI64(args[1]); + if( !matrix ) return usage(); + if( !matrix.len ) return usage(); + // All numbers are positive + for( u32 i = 0; i < matrix.len; i++ ) + if( matrix.get(i) < 0 ) return usage(); + // Matrix is square + int nodes = 0; + while( nodes*nodes < matrix.len ) nodes++; + if( nodes*nodes != matrix.len ) + return usage(); // Not a square matrix + + // src,dst are values within the matrix + i64 src = sys.aryu8.atoi(args[2]); + i64 dst = sys.aryu8.atoi(args[3]); + if( src < 0 || src >= nodes || dst < 0 || dst >= nodes ) + return usage(); // Source and destination land within the graph + + int source = src, destination = dst; + i64 cost = shortestPath(matrix,nodes,source,destination); + if( cost >= 0 ) { + new sys.aryu8().num(cost).add('\n').write(1); + return 0; + } + return usage(); +}; -- cgit v1.2.3