model

package
v0.0.0-...-90161da Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Oct 1, 2024 License: MIT Imports: 15 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	// DifficultyUnknown represents unknown difficulty.
	DifficultyUnknown = iota
	// DifficultyEasy represents "easy" puzzles.
	DifficultyEasy
	// DifficultyMedium represents "medium" puzzles.
	DifficultyMedium
	// DifficultyHard represents "hard" puzzles.
	DifficultyHard
	// DifficultyBrutal represents "brutal" puzzles (only solvable using brute force).
	DifficultyBrutal
)

Variables

View Source 
var AllFields = []Square{
	SquareUndefined,
	SquareAir,
	SquareFire,
	SquareDragon,
	SquareOut,
}

AllFields are a list of all possible field values.

Functions

func GetAvgOptions 

func GetAvgOptions(g *Grid, difficulty Difficulty) float64

GetAvgOptions gets the average options of possible solve techniques that can be applied per square.

func IsDistinct 

func IsDistinct(g *Grid) bool

IsDistinct returns true if there is exactly one solution to the given grid.

func Render 

func Render(g *Grid, activeSquare int) string

Render returns the string representation of a grid and shows some extra information.

func Validate 

func Validate(g *Grid) bool

Validate validates, if a grid is in a valid state. This applies all validation rules to the grid state. A valid state does not necessarily mean, that it can lead to a solution.

func ValidateFast 

func ValidateFast(g *Grid) bool

ValidateFast validates the grid using a lookup table to be more performant than Validate.

func ValidateIncr 

func ValidateIncr(g *Grid, i int, border int) bool

ValidateIncr validates only the changed squares and the squares around it. The goal is to optimize performance by validating only squares that were changed. This function is therefore best used when validating incrementally.

func ValidatePartial 

func ValidatePartial(g *Grid, ixs []int) bool

ValidatePartial validates only some squares (ixs) of the whole grid. The goal is to optimize performance by validating only squares that were changed. This function is therefore best used when validating incrementally.

Types

type Difficulty 

type Difficulty int

Difficulty represents possible difficulty levels.

func GetDifficulty 

func GetDifficulty(g *Grid) Difficulty

GetDifficulty gets the difficulty of a puzzle.

func ParseDifficulty 

func ParseDifficulty(str string) Difficulty

ParseDifficulty takes a string and returns its Difficulty value.

func (Difficulty) String 

func (difficulty Difficulty) String() string

type Grid 

type Grid struct {
	Width   int
	Height  int
	Squares []Square
}

Grid represents the puzzles state.

func Enumerate 

func Enumerate(g *Grid) []*Grid

Enumerate enumerates all possible successors from a given grid.

func EnumerateFilter 

func EnumerateFilter(g *Grid, filter gridPredicate) []*Grid

EnumerateFilter enumerates all possible successors from a given grid and allows to filter only the wanted grids.

func EnumerateLimited 

func EnumerateLimited(g *Grid) []*Grid

EnumerateLimited enumerates all possible successors from a given grid but stops as soon as there are more than one solution.

func EnumerateSquare 

func EnumerateSquare(g *Grid, i int) []*Grid

EnumerateSquare enumerates all possible grids if a specified square is undefined. Otherwise, the given grid is returned as single possible solution.

func Generate 

func Generate(width int, height int, duration time.Duration) *Grid

Generate generates a random but solved grid with the given dimensions. The duration parameter controls the time that is invested in generating the best or most interesting grid possible.

func New 

func New(width int, height int) *Grid

New creates a new grid struct.

func Obfuscate 

func Obfuscate(g *Grid, difficulty Difficulty, duration time.Duration) *Grid

Obfuscate creates a puzzle from a given solved or partially solved puzzle. The difficulty parameter controls how hard the puzzle would be to solve for a human.

The algorithm works like this: It takes a grid state and incrementally sets random squares to "undefined". After every step, it verifies if the puzzle is still solvable (i.e. has a distinct solution).

func Parse 

func Parse(s string) *Grid

Parse parses a string that represents a grid.

func Solve 

func Solve(g *Grid) *Grid

Solve solves a puzzle using multiple algorithms if necessary. it returns the only possible solution or "nil" otherwise.

func SolveBruteForce 

func SolveBruteForce(g *Grid) *Grid

SolveBruteForce solves a puzzle using a brute force strategy (enumerating all possible states). It's the only algorithm that finds solutions to the hardest puzzles. It returns the only possible solution or "nil" otherwise.

func SolveIterative 

func SolveIterative(g *Grid, difficulty Difficulty) *Grid

SolveIterative solves a puzzle by iteratively checking possible options for a given square. It only uses the validation rules of the game - no domain knowledge required. Can be tuned by the maximum number of possible permutations that can exist in order to exclude a option. It returns the only possible solution or "nil" otherwise.

func SolveTechnically 

func SolveTechnically(g *Grid, difficulty Difficulty) *Grid

SolveTechnically solves a puzzle applying fix techniques (using domain knowledge). It returns the only possible solution or "nil" otherwise.

func (*Grid) Clone 

func (g *Grid) Clone() *Grid

Clone creates an exact deep copy of a grid.

func (*Grid) Coords 

func (g *Grid) Coords(i int) (x int, y int)

Coords gets the coordinates of a quare given the squares index.

func (*Grid) CountSquares 

func (g *Grid) CountSquares(s Square) (count int)

CountSquares counts all squares with a specified value.

func (*Grid) FillUndefined 

func (g *Grid) FillUndefined(s Square) *Grid

FillUndefined fills all undefined squares of a grid with the specified value.

TODO: move to Builder type

func (*Grid) HasSquare 

func (g *Grid) HasSquare(val Square) bool

HasSquare returns "true" if at least one square with the specified value exists.

func (*Grid) ID 

func (g *Grid) ID() *big.Int

ID creates a unique identifier for a puzzle. This helps when we want to normalize puzzles.

Code is constructed as follows:

most significant bit <------------------------------- least significant bit [ last square ] ... [ square 0 (2bits) ][ height (5bits) ][ width (5bits) ]

func (*Grid) Index 

func (g *Grid) Index(x int, y int) (int, bool)

Index returns the square index from its coordinates.

func (*Grid) IsUndefined 

func (g *Grid) IsUndefined() bool

IsUndefined return true if all squares are undefined

func (*Grid) Mirror 

func (g *Grid) Mirror(horizontal bool) *Grid

Mirror creates a mirrored copy of a grid.

func (*Grid) NeighborCount 

func (g *Grid) NeighborCount(i int, square Square, adjacentOnly bool, includeUndefined bool) (count int)

NeighborCount counts the neighboured squares (all 8 or the 4 adjacent) that match the given type. If the 'includeUndefined' flag is set, also undefined squares are counted.

func (*Grid) NeighborCount4 

func (g *Grid) NeighborCount4(i int, square Square) int

NeighborCount4 counts the adacent neighboured squares that match the given type.

func (*Grid) NeighborCount8 

func (g *Grid) NeighborCount8(i int, square Square) int

NeighborCount8 counts the 8 neighboured squares that match the given type.

func (*Grid) NeighborIndicesi 

func (g *Grid) NeighborIndicesi(i int, adjacentOnly bool) []int

NeighborIndicesi gets the indices of all neighbor squares.

func (*Grid) Normalize 

func (g *Grid) Normalize() *Grid

Normalize normalizes a grid to prevent duplicates (rotated and mirrored grids).

func (*Grid) PuzzleRating 

func (g *Grid) PuzzleRating() float64

PuzzleRating is used to generate puzzles from solutions. This value is used to find the best obfuscated puzzle among others.

TODO: use a sigmoid function or similar to clamp the value always between 0.0 and 1.0

func (*Grid) Rotate 

func (g *Grid) Rotate(left bool) *Grid

Rotate creates a rotated copy of a grid.

func (*Grid) SetDragon 

func (g *Grid) SetDragon(i int) *Grid

SetDragon sets a dragon to a specific square and computes where fire must be.

TODO: move this into a Builder type

func (*Grid) SetSquare 

func (g *Grid) SetSquare(x int, y int, val Square) *Grid

SetSquare sets the squares value at coordinates x, y.

func (*Grid) SetSquarei 

func (g *Grid) SetSquarei(i int, val Square) *Grid

SetSquarei sets the squares value at the specified index.

func (*Grid) SetSquareiAndValidate 

func (g *Grid) SetSquareiAndValidate(i int, val Square) bool

SetSquareiAndValidate sets a square to the specified value and validates the grid partially (only the changed square and its neighbors).

TODO: move to builde type

func (*Grid) Size 

func (g *Grid) Size() int

Size returns a grids number of squares.

func (*Grid) SolutionRating 

func (g *Grid) SolutionRating() float64

SolutionRating returns the interestingness of a grid. This is useful if we want to sort possible solved grids. Density returns the density of a grid (number of dragons percentually).

func (*Grid) Square 

func (g *Grid) Square(x int, y int) Square

Square gets the field value at coordinates x, y.

func (*Grid) Squarei 

func (g *Grid) Squarei(i int) Square

Squarei gets the field value at the specified index.

func (*Grid) String 

func (g *Grid) String() string

String returns the string representation of a puzzle.

func (*Grid) Undefinedness 

func (g *Grid) Undefinedness() float64

Undefinedness returns the undefinedness of a unsolved puzzle grid. This is especially useful to find "interesting" puzzle.

type Square 

type Square uint8

Square represents possible cell values. 

const (
	// SquareUndefined represents undefined squares.
	SquareUndefined Square = iota
	// SquareAir represents squares with air.
	SquareAir
	// SquareFire represents squares with fire.
	SquareFire
	// SquareDragon represents squares with dragons.
	SquareDragon
	// SquareOut represents squares that are outside of the grid.
	SquareOut
	// SquareNoDragon represents squares that can not be dragons.
	SquareNoDragon
)

func (Square) Code 

func (val Square) Code() rune

Code is the squares representation in when serializing grids.

func (Square) Symbol 

func (val Square) Symbol() rune

Symbol is the squares representation in the console output and logs.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.