README
¶
Water Sort Puzzle Solver
This code can solve a game called "Water Sort Puzzle" available on APPStore and PlayMarket.
Start Guide
Firstly, you have to install Golang. See https://go.dev/doc/install
Then with go1.16+ you're able to install a program via command:
go install github.com/pkositsyn/water-sort-puzzle-solver/cmd/watersortsolver@latest
This will install the program into $GOPATH/bin.
To find out where $GOPATH is, run go env GOPATH.
Instead of @latest, you can also use a specific version, such as @1.0.0
Running program
After executing the program you have to provide starting position of the game.
Position string representation
The position consists of letters, according to colors, and ; separating different flasks.
One letter maps to one color, and actually you can use any letter for any color (just make sure that one color is represented by one letter)
In this game one flask consists of 4 water tiles. If we say H = blue, Z = red, D = yellow,
then a flask of (yellow, yellow, red, blue) - colors from bottom to the top - is represented like this: DDZH
3 exact same flasks like above and 2 empty flasks at the end are written in this way: DDZH;DDZH;DDZH;;
Let P = pink, F = dark blue, O = orange, G = green and B = blue
Then the position for these 3 flasks is: GOFP;GOOB;
Program output
For example above the solution doesn't exist, so we get:
Input initial puzzle state
GOFP;GOOB;
Cannot solve puzzle: solution doesn't exist
If we consider position O;OOO (which means one orange in first flask and 3 in another)
then we get the following:
Input initial puzzle state
O;OOO
Puzzle solved in 1 steps!
1 2
Which means that we need to move orange from 1st flask to the 2nd.
Eventually, this gives position ;OOOO which ends the game round.
Program flags
Via --algorithm command line flag you can choose the algorithm used to search for solution.
Possible choices are currently A*, IDA*, Dijkstra (default A*). Example: watersortsolver --algorithm idastar.
See watersortsolver --help for correct names for algorithms
Notes
The solution produced by the program is minimal in number of steps needed to solve the puzzle.
Implementation uses A*/IDA*/Dijkstra graph algorithms to solve puzzles efficiently.
I also wrote tests for the first 50 rounds of the game, so the code is kind of stable.
Documentation
¶
Index ¶
- Variables
- type AStarOption
- type AStarSolver
- type Color
- type Flask
- func (f *Flask) BottomColor() Color
- func (f *Flask) ColorTowers() int
- func (f *Flask) FromString(s string) error
- func (f *Flask) IsEmpty() bool
- func (f *Flask) IsFinished() bool
- func (f *Flask) IsFull() bool
- func (f *Flask) Left() int
- func (f *Flask) PopTop() (clr Color, height int)
- func (f *Flask) Pour(c Color, height int) error
- func (f *Flask) Size() int
- func (f *Flask) String() string
- func (f *Flask) Top() (clr Color, height int)
- type IDAStarOption
- type IDAStarSolver
- type Solver
- type SolverWithStats
- type State
- func (s State) Copy() State
- func (s State) EquivalentString() string
- func (s *State) FromString(str string) error
- func (s State) GetStepTo(child State) (Step, error)
- func (s State) Heuristic() int
- func (s State) IsTerminal() bool
- func (s State) ReachableStates() []State
- func (s State) Step(step Step) (State, error)
- func (s State) String() string
- type Stats
- type Step
Constants ¶
This section is empty.
Variables ¶
var ErrNotExist = errors.New("solution doesn't exist")
Functions ¶
This section is empty.
Types ¶
type AStarOption ¶
type AStarOption func(solver *AStarSolver)
func AStarWithHeuristic ¶
func AStarWithHeuristic(heuristic func(State) int) AStarOption
type AStarSolver ¶
type AStarSolver struct {
// contains filtered or unexported fields
}
func NewAStarSolver ¶
func NewAStarSolver(opts ...AStarOption) *AStarSolver
func NewDijkstraSolver ¶
func NewDijkstraSolver() *AStarSolver
func (*AStarSolver) Stats ¶
func (s *AStarSolver) Stats() Stats
type Color ¶
type Color rune
Color of water piece. Actually it doesn't matter what exact colors there are. Just need to be able to compare them by ==. Zero-value rune is reserved for absence of Color.
type Flask ¶
type Flask [waterPiecesPerFlask]Color
func (*Flask) BottomColor ¶
BottomColor of flask. For empty flask returns colorNone.
func (*Flask) ColorTowers ¶
ColorTowers returns number of color towers in flask.
func (*Flask) FromString ¶
FromString initializes flask from string. String mustn't contain ';' and empty rune.
func (*Flask) IsFinished ¶
type IDAStarOption ¶ added in v0.2.0
type IDAStarOption func(solver *IDAStarSolver)
func IDAStarWithHeuristic ¶ added in v0.2.0
func IDAStarWithHeuristic(heuristic func(State) int) IDAStarOption
type IDAStarSolver ¶ added in v0.2.0
type IDAStarSolver struct {
// contains filtered or unexported fields
}
func NewIDAStarSolver ¶ added in v0.2.0
func NewIDAStarSolver(opts ...IDAStarOption) *IDAStarSolver
func (*IDAStarSolver) Solve ¶ added in v0.2.0
func (s *IDAStarSolver) Solve(initialState State) ([]Step, error)
func (*IDAStarSolver) Stats ¶ added in v0.2.0
func (s *IDAStarSolver) Stats() Stats
type SolverWithStats ¶ added in v0.2.0
type State ¶
type State []Flask
State of the game field. It is represented as ordered array of flasks.
func (State) EquivalentString ¶
EquivalentString is a string representation of game state. This differs from String method by omitting information about order. Essentially for solving order doesn't matter.
func (*State) FromString ¶
FromString fills the state from String representation of the board.
func (State) Heuristic ¶
Heuristic is a monotonic lower estimate of number of steps to reach terminal state. Monotonic means h(currentState) >= h(currentState with one step forward).
func (State) IsTerminal ¶
IsTerminal state. In this state game ends.
func (State) ReachableStates ¶
ReachableStates from current one in one step.
Source Files
Directories