~/bend-docscommunity

board.bend checks

raw source on the hub · import 0x3b876eed3a748ea7fba8a7834d3c610b/board.bend as Board

Board: the rules of Minesweeper, written as parallel grid passes. =================================================================

Every rule here is one pass over the whole board. A pass reads the old board and writes a new one, so the four quadrants never race and Bend can fork them onto four cores. The board is Data, so each leaf of a pass holds its own reference to the old board and reads any cell it likes.

Mine layout is the one part that is not obvious. A cell is a mine when fewer than mines other cells sort before it, under a strict total order on (hash, index). Exactly mines cells can win that race, so the count is exact without a shuffle, and each cell decides on its own with no coordination.

3 imports
import Base
import ./grid.bend as G
import ./cell.bend as C

Types

type Conf source · line 23 · raw

Data

depth: the quadtree depth. side: 2^depth. bits: 2*depth, the index width. sx, sy: the first click. That cell and its eight neighbours never get a mine, so the first click always opens a region.

type Phase source · line 26 · raw

Data

type Layout source · line 50 · raw

Data

The payload of a mine-layout pass.

type Field source · line 54 · raw

Data

The payload of a flood pass.

type Chord source · line 58 · raw

Data

The payload of a chord pass. cx, cy is the cell that was chorded.

Definitions

def Phase.is_playing source · line 31 · raw

@p:Phase -> Bool

def Phase.is_lost source · line 40 · raw

@p:Phase -> Bool

def Conf.depth source · line 61 · raw

@cf:Conf -> Nat

def Conf.side source · line 66 · raw

@cf:Conf -> U32

def Conf.bits source · line 71 · raw

@cf:Conf -> Nat

def Conf.mines source · line 76 · raw

@cf:Conf -> U32

def Conf.seed source · line 81 · raw

@cf:Conf -> U32

def Conf.sx source · line 86 · raw

@cf:Conf -> U32

def Conf.sy source · line 91 · raw

@cf:Conf -> U32

def Conf.cells source · line 96 · raw

@+cf:Conf -> U32

def Conf.new source · line 100 · raw

@+d:Nat -> @mines:U32 -> @seed:U32 -> @sx:U32 -> @sy:U32 -> Conf

Builds a config. mines must leave room for the nine safe cells.

def Conf.aim source · line 104 · raw

@cf:Conf -> @sx:U32 -> @sy:U32 -> Conf

Moves the safe cell. The first click calls this, then lays the board out.

def Layout.conf source · line 109 · raw

@ly:Layout -> Conf

def Layout.mines source · line 114 · raw

@ly:Layout -> 0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, Bool>

def Field.conf source · line 119 · raw

@fd:Field -> Conf

def Field.cells source · line 124 · raw

@fd:Field -> 0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell>

def Chord.conf source · line 129 · raw

@ch:Chord -> Conf

def Chord.cells source · line 134 · raw

@ch:Chord -> 0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell>

def Chord.cx source · line 139 · raw

@ch:Chord -> U32

def Chord.cy source · line 144 · raw

@ch:Chord -> U32

def Board.hash source · line 150 · raw

@+s:U32 -> @i:U32 -> U32

A 32-bit avalanche hash. Two cells one apart land far apart.

def Board.within1 source · line 160 · raw

@a:U32 -> @b:U32 -> Bool

True when a is within one step of b. The subtraction wraps, so a single unsigned test covers both sides and the edge of the board.

def Board.in_board source · line 163 · raw

@+cf:Conf -> @x:U32 -> @y:U32 -> Bool

def Board.in_safe source · line 168 · raw

@+cf:Conf -> @x:U32 -> @y:U32 -> Bool

The nine cells around the first click.

def Board.key.pick source · line 174 · raw

@+cf:Conf -> @idx:U32 -> @safe:Bool -> U32

A safe cell keeps the largest odd key; every other key is even. The two ranges cannot tie, so no safe cell is ever picked while mines leaves at least that many cells outside the safe block.

def Board.key source · line 181 · raw

@+cf:Conf -> @+idx:U32 -> U32

def Board.before source · line 188 · raw

@+cf:Conf -> @+j:U32 -> @+ki:U32 -> @ii:U32 -> Bool

The strict total order. The index breaks a tie between equal keys.

def Board.rank source · line 194 · raw

@bits:Nat -> @+cf:Conf -> @+ki:U32 -> @+ii:U32 -> @+base:U32 -> U32

Counts the cells that sort before (ki, ii). The index range splits in two at every step, so the whole count is a parallel reduction.

def Board.mine_at source · line 206 · raw

@+cf:Conf -> @+x:U32 -> @+y:U32 -> Bool

True when the cell at (x, y) hides a mine.

def Board.one_mine.pick source · line 212 · raw

@d:Nat -> @mg:0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, Bool> -> @x:U32 -> @y:U32 -> @ok:Bool -> U32

Reads one neighbour of a Bool grid. Off the board counts as 0.

def Board.one_mine source · line 219 · raw

@+cf:Conf -> @mg:0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, Bool> -> @+x:U32 -> @+y:U32 -> U32

def Board.one_blank.pick source · line 224 · raw

@d:Nat -> @cg:0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell> -> @x:U32 -> @y:U32 -> @ok:Bool -> U32

Reads one neighbour of a Cell grid and asks whether the flood may cross it: a shown cell with no mine next to it.

def Board.one_blank source · line 231 · raw

@+cf:Conf -> @cg:0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell> -> @+x:U32 -> @+y:U32 -> U32

def Board.one_flag.pick source · line 235 · raw

@d:Nat -> @cg:0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell> -> @x:U32 -> @y:U32 -> @ok:Bool -> U32

Reads one neighbour of a Cell grid and asks whether it carries a flag.

def Board.one_flag source · line 242 · raw

@+cf:Conf -> @cg:0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell> -> @+x:U32 -> @+y:U32 -> U32

def Board.cell_at source · line 269 · raw

@+ly:Layout -> @+x:U32 -> @+y:U32 -> 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell

Lays out one cell: its own mine bit, and the count of mines touching it.

def Board.make source · line 277 · raw

@+cf:Conf -> 0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell>

Lays out the whole board. Two parallel passes: mines, then counts.

def Board.spread_at.pick source · line 281 · raw

@c:0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell -> @go:Bool -> 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell

def Board.spread_at source · line 289 · raw

@+fd:Field -> @+x:U32 -> @+y:U32 -> 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell

One round of the flood: a hidden cell next to an open blank opens.

def Board.spread source · line 296 · raw

@+fd:Field -> 0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell>

def Board.shown source · line 299 · raw

@+cg:0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell> -> U32

def Board.flags source · line 302 · raw

@+cg:0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell> -> U32

def Board.booms source · line 305 · raw

@+cg:0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell> -> U32

def Board.flood source · line 312 · raw

@fuel:Nat -> @alive:Bool -> @+cf:Conf -> @cg:0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell> -> @before:U32 -> 0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell>

Runs rounds until nothing more opens. Every round that keeps going opens at least one cell, so the cell count is fuel enough. alive is a parameter, not a test on a computed value, because a match may only scrutinise a parameter.

def Board.flood_all source · line 325 · raw

@+cf:Conf -> @+cg:0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell> -> 0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell>

def Board.open_at source · line 329 · raw

@+cf:Conf -> @+cg:0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell> -> @x:U32 -> @y:U32 -> 0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell>

Left-click: open the cell, then let the flood run out of it.

def Board.flag_at source · line 335 · raw

@+cf:Conf -> @+cg:0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell> -> @x:U32 -> @y:U32 -> 0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell>

Right-click: turn a flag on or off.

def Board.chord_cell.pick source · line 340 · raw

@c:0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell -> @go:Bool -> 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell

def Board.chord_cell source · line 348 · raw

@+ch:Chord -> @+x:U32 -> @+y:U32 -> 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell

The chord pass: every hidden cell touching (cx, cy) opens.

def Board.chord_go source · line 355 · raw

@+cf:Conf -> @+cg:0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell> -> @x:U32 -> @y:U32 -> @ok:Bool -> 0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell>

def Board.chord_at source · line 368 · raw

@+cf:Conf -> @+cg:0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell> -> @+x:U32 -> @+y:U32 -> 0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell>

Middle-click, or a left-click on a number that already has its flags. It opens every hidden neighbour at once. That is how a player clears a board fast, and it is how a careless player loses one.

def Board.expose source · line 375 · raw

@cg:0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell> -> 0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell>

The end of a lost game: every mine that is not flagged comes up.

def Board.mines_of source · line 380 · raw

@cg:0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell> -> 0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, Bool>

Where the mines are, with every move the player made stripped off. LAWS.bend uses this to say that no move ever shifts a mine.

def Board.status.pick source · line 383 · raw

@lost:Bool -> @won:Bool -> Phase

def Board.status source · line 393 · raw

@+cf:Conf -> @+cg:0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, 0x3b876eed3a748ea7fba8a7834d3c610b/cell.Cell> -> Phase

A shown mine loses. Every other cell shown wins.

Templates

template Board.around source · line 248 · raw

@-T:Data -> @-f:(@+a:Conf -> @b:0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, T> -> @+u:U32 -> @+v:U32 -> U32) -> @+cf:Conf -> @+cg:0x3b876eed3a748ea7fba8a7834d3c610b/grid.Grid<&2, T> -> @+x:U32 -> @+y:U32 -> U32

Adds a per-cell number over the eight neighbours of (x, y). The eight reads are the same depth, so they finish together, which is what a fork-join scheduler needs to stay busy.