Struct arc_acreage::fast::Generator

pub struct Generator {

    target: Area,
    max_inner_cells: u8,
    max_length: u8,
    grid: Grid,
    placed: [[bool; 7]; 7],
    placed_cnt: u8,
    moves: Vec<((u8, u8), (u8, u8))>,
    start: (u8, u8),
    head: (u8, u8),
    valid_grids: Vec<Grid>,
    valid_cnt: usize,
    calls: usize,
    inner_cells: usize,
}

A data structure for generating closed loops of a target area, using a back-tracking algorithm.

Fields

target: Area

The target area we are aiming for.

max_inner_cells: u8

The maximum number of inner cells (i.e. not part of the outer boundary of the grid) we can have forming part of the curve. This constraint is useful to prune a very large number of search paths, assuming we can prove it rigorously for our desired target area.

max_length: u8

The maximum length of the loop (in segments). This constraint is useful to prune some search paths, assuming we can prove it rigorously for our target area.

grid: Grid

The current state of the grid.

placed: [[bool; 7]; 7]

Whether we have placed something in each cell of the grid so far during the backtracking algorithm.

placed_cnt: u8

Tracks the number of placed cells; used to ensure backtracking doesn’t recurse forever.

moves: Vec<((u8, u8), (u8, u8))>

The order of placements made in the grid. When we backtrack, we pop off elements and undo those moves. The first tuple is the coordinate of the cell being placed. The second element is the coordinates of the head before we placed this move (for undoing).

start: (u8, u8)

The coordinates of the loop’s starting point, used to determine when we have closed the loop. Coordinates are on the grid lines, zero-indexed from the top-left of the grid.

head: (u8, u8)

The location of the head of the loop we are generating. Coordinates are on the grid lines.

valid_grids: Vec<Grid>

Storage for all the valid grids we find.

valid_cnt: usize

Counter of all valid grids, capturing the multiplicity. This algorithm will find valid layouts using forward/backward strokes. Each of these has associated with it a large number of grids drawn with quarter circle arcs. In fact, if the path length is 2n (it must be even), then there are (2n choose n) arc-segment paths for each path we find.

calls: usize

inner_cells: usize

The number of cells we have placed not on the outer rim of the grid. This constraint is useful to prune a large number of search paths, assuming we can prove it rigorously for our target area.

Implementations

impl Generator

pub fn new(target: Area, max_inner_cells: u8, max_length: u8) -> Self

Create a new Generator.

pub fn generate(self) -> (usize, Vec<Grid>)

Generate the total count of valid grids (including multiplicity), and a vec of all the grid layouts.

fn next_cell(&mut self)

fn place(&mut self, row: u8, col: u8, c: Cell, headr: u8, headc: u8)

fn unplace(&mut self)

Trait Implementations

impl Debug for Generator

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.