ubongo_trigo_solver/src/main.rs

use std::collections::HashMap;


/* 
 * The basic element is a single Triangle.
 * It can be with a wide base (upright) or on its tip:
 *
 *      /\     +--------+
 *     /  \     \      /
 *    /    \     \    /
 *   /      \     \  /
 *  +--------+     \/
 *
 *  We number its edges accordingly:
 *                                       1
 *              /\                   +--------+
 *          3  /  \  2                \      /
 *            /    \                   \    /
 *           /      \               3   \  /  2
 *          +--------+                   \/
 *              1
 *
 */

type Edge = u8;


/* Numbers 1..7 are used to identify a given part */
type PartID = u8;

/* Parts are described by a given upright triangle and a sequence of edges that are extended */
type Part = Vec<Edge>;



/* For example, the brown part (1) could be described by starting at the lower right triangle and
 * traversing edges in the following order: 3, 3, 1, 1, 2, 1, 3
 *      ____
 *      \  /\
 *       \/__\
 *       /\  /\
 *      /__\/__\ <--
 *      \  /
 *       \/
 *
 *
 *
 */
fn generate_parts() -> HashMap<PartID, Part> {
    HashMap::from([
        (1, vec![3, 3, 1, 1, 2, 1, 3]),
        (2, vec![2, 1, 2, 2, 1]),
        (3, vec![2, 1, 3, 1, 2]),
    ])
}

/*
 * A map has two sides (left and right) and is not neccesarily convex.
 * We specify each side by a list of lines.
 * Each line is represented by yet another list of skip entries:
 * a two-tuple, where the first number designates the cells that are "skipped" (a.k.a inaccessible)
 * and the second number which specifies the number of valid fields.
 */
type SkipEntryIO = (u8, u8);
type MapSideIO = Vec<Vec<SkipEntryIO>>;
type MapIO = (MapSideIO, MapSideIO);

/*
 * For in-memory representation however, we simply use a two-dimensional array of cells.
 * Each cell can be a Barrier (meaning no part may be placed on the cell), Empty (meaning at the
 * current time, it is not occupied by a part) or Occupied.
 */
enum Cell {
    Barrier,
    Empty,
    Occupied(PartID)
}

/*
 * A triangular grid looks like this:
 *       __  __
 *     /\  /\  /\
 *    /__\/__\/__\
 *    \  /\  /\  /
 *     \/__\/__\/
 *     /\  /\  /\
 *    /__\/__\/__\
 * 
 * We require by definition that the left upper-most triangle is upright.
 * A map is then represented by a two-dimensional row-major (meaning the outer array represents the
 * different rows) two-dimensional array with a maximum
 * size of 16x16.
 * Since there are two sides, we store both of them in a tuple.
 */
type MapSide = [[Cell; 16]; 16];
type Map = (MapSide, MapSide);


fn main() {
    println!("Hello, world!");
}