diff options
Diffstat (limited to 'examples')
| -rw-r--r-- | examples/numbers.aup | 62 | ||||
| -rw-r--r-- | examples/routes.aup | 120 |
2 files changed, 182 insertions, 0 deletions
diff --git a/examples/numbers.aup b/examples/numbers.aup new file mode 100644 index 0000000..3352993 --- /dev/null +++ b/examples/numbers.aup @@ -0,0 +1,62 @@ +# Numbers worked out in one event (Pure 018): a square root by Newton's +# steps, stopping when they stop shrinking, and the best a knapsack holds, +# its table an event's list. +record Item { + id = 0 + weight = 0 + worth = 0 +} +record Cell { + at = 0 + best = 0 +} +state items: list of Item by id +state root = 0 +state steps = 0 +state packed = 0 +input stock = message { + id: u32 + weight: u32 + worth: u32 +} +input sqrt = message { + x: number +} +input pack = message { + capacity: u32 +} + +on stock { + items.add(Item { id: stock.id, weight: stock.weight, worth: stock.worth }) +} + +on sqrt { + let r = if sqrt.x > 1 { sqrt.x } else { 1 } + steps = 0 + for i in 0 .. 200 { + let next = (r + sqrt.x / r) / 2 + if next >= r { break } + r = next + steps = steps + 1 + } + root = r +} + +on pack { + let table: list of Cell by at + for c in 0 .. pack.capacity + 1 { + table.add(Cell { at: c }) + } + for it in items { + for k in 0 .. pack.capacity + 1 { + let c = pack.capacity - k + if c >= it.weight { + let with = table[c - it.weight].best + it.worth + if with > table[c].best { table[c].best = with } + } + } + } + packed = table[pack.capacity].best +} + +view answer = "root {root} in {steps} steps, packed {packed}" diff --git a/examples/routes.aup b/examples/routes.aup new file mode 100644 index 0000000..6656947 --- /dev/null +++ b/examples/routes.aup @@ -0,0 +1,120 @@ +# Routes over a graph in one event each (Pure 018): breadth first, depth +# first and the nearest by weight. A node's edges are a slice of the edges +# list (keyed by from * 1048576 + to); the searches keep their queues and +# what they have seen in the event's own lists, gone when it ends. +record Node { + id = 0 +} +record Edge { + link = 0 + to = 0 + w = 1 +} +record Seen { + node = 0 + depth = 0 +} +record Step { + node = 0 +} +record Pending { + rank = 0 +} +state nodes: list of Node by id +state edges: list of Edge by link +state hops = -1 +state visited = 0 +state order = 0 +state shortest = -1 +input link = message { + from: u32 + to: u32 + w: u32 +} +input route = message { + from: u32 + to: u32 +} +input walk = message { + from: u32 +} +input path = message { + from: u32 + to: u32 +} + +on link { + if !nodes.has(link.from) { nodes.add(Node { id: link.from }) } + if !nodes.has(link.to) { nodes.add(Node { id: link.to }) } + edges.add(Edge { link: link.from * 1048576 + link.to, to: link.to, w: link.w }) +} + +# Breadth first: the queue is read by position, every node enters it once. +on route { + let seen: list of Seen by node + let queue: list of Step + queue.append(Step { node: route.from }) + seen.add(Seen { node: route.from }) + for i in 0 .. nodes.count { + if i >= queue.count { break } + let q = queue.first + i + for e in edges[q.node * 1048576 .. q.node * 1048576 + 1048576] { + if !seen.has(e.to) { + seen.add(Seen { node: e.to, depth: seen[q.node].depth + 1 }) + queue.append(Step { node: e.to }) + } + } + } + hops = if seen.has(route.to) { seen[route.to].depth } else { -1 } +} + +# Depth first: a stack, each edge pushed once at most; depth is the order a node was reached in. +on walk { + let seen: list of Seen by node + let stack: list of Step + stack.append(Step { node: walk.from }) + let reached = 0 + for i in 0 .. edges.count + 1 { + if stack.count == 0 { break } + let v = stack.last.node + stack.remove(stack.last) + if !seen.has(v) { + seen.add(Seen { node: v, depth: reached }) + reached = reached + 1 + for e in edges[v * 1048576 .. v * 1048576 + 1048576] { + if !seen.has(e.to) { stack.append(Step { node: e.to }) } + } + } + } + visited = seen.count + order = sum(s.depth * (s.node + 1) for s in seen) +} + +# The nearest by weight (Dijkstra): pending ranks by dist * 1048576 + node, the nearest first. +on path { + let best: list of Seen by node + let pending: list of Pending by rank + best.add(Seen { node: path.from }) + pending.add(Pending { rank: path.from }) + for i in 0 .. edges.count + 1 { + if pending.count == 0 { break } + let d = floor(pending.first.rank / 1048576) + let v = pending.first.rank - d * 1048576 + pending.remove(pending.first) + if best[v].depth == d { + for e in edges[v * 1048576 .. v * 1048576 + 1048576] { + let far = d + e.w + if !best.has(e.to) { + best.add(Seen { node: e.to, depth: far }) + pending.add(Pending { rank: far * 1048576 + e.to }) + } else if far < best[e.to].depth { + best[e.to].depth = far + pending.add(Pending { rank: far * 1048576 + e.to }) + } + } + } + } + shortest = if best.has(path.to) { best[path.to].depth } else { -1 } +} + +view graph = "{nodes.count} nodes, {edges.count} edges" |