scrabble-solver/scrabble/oracle_test.go

package scrabble

import (
	"gitea.iliadenisov.ru/developer/scrabble-solver/board"
	"gitea.iliadenisov.ru/developer/scrabble-solver/rack"
	"gitea.iliadenisov.ru/developer/scrabble-solver/rules"
)

// dict is a membership set of words (alphabet-index strings) for the oracle.
type dict map[string]bool

func makeDict(words [][]byte) dict {
	d := make(dict, len(words))
	for _, w := range words {
		d[string(w)] = true
	}
	return d
}

func (d dict) has(letters []byte) bool { return d[string(letters)] }

func lineCoord(dir Direction, line, axis int) (r, c int) {
	if dir == Horizontal {
		return line, axis
	}
	return axis, line
}

func cellFilled(b *board.Board, dir Direction, line, axis int) bool {
	r, c := lineCoord(dir, line, axis)
	return b.Filled(r, c)
}

func coversCenter(dir Direction, line, start, end, cr, cc int) bool {
	if dir == Horizontal {
		return line == cr && start <= cc && cc <= end
	}
	return line == cc && start <= cr && cr <= end
}

// bruteForce returns every legal play for the position, keyed by moveKey, found by
// exhaustively trying every maximal window and every rack assignment, then validating
// against the dictionary, connectivity and the first-move centre rule. It is the slow,
// obviously-correct oracle for checking the generators on small inputs.
func bruteForce(b *board.Board, rs *rules.Ruleset, d dict, rk rack.Rack, mode Mode) map[string]Move {
	out := map[string]Move{}
	var dirs []Direction
	if mode.Includes(Horizontal) {
		dirs = append(dirs, Horizontal)
	}
	if mode.Includes(Vertical) {
		dirs = append(dirs, Vertical)
	}
	firstMove := b.IsEmpty()
	cr, cc := rs.Center/rs.Cols, rs.Center%rs.Cols

	for _, dir := range dirs {
		lines, span := b.Rows(), b.Cols()
		if dir == Vertical {
			lines, span = b.Cols(), b.Rows()
		}
		for line := range lines {
			for start := range span {
				for end := start + 1; end < span; end++ {
					if cellFilled(b, dir, line, start-1) || cellFilled(b, dir, line, end+1) {
						continue // not a maximal window
					}
					var empties []int
					for a := start; a <= end; a++ {
						if !cellFilled(b, dir, line, a) {
							empties = append(empties, a)
						}
					}
					if len(empties) == 0 {
						continue
					}
					assign(b, rs, d, rk.Clone(), dir, line, start, end, empties, 0, nil,
						firstMove, cr, cc, out)
				}
			}
		}
	}
	return out
}

func assign(b *board.Board, rs *rules.Ruleset, d dict, rk rack.Rack, dir Direction,
	line, start, end int, empties []int, idx int, placed []Placement,
	firstMove bool, cr, cc int, out map[string]Move) {

	if idx == len(empties) {
		validate(b, rs, d, dir, line, start, end, placed, firstMove, cr, cc, out)
		return
	}
	r, c := lineCoord(dir, line, empties[idx])
	next := placed[:len(placed):len(placed)] // avoid aliasing across siblings

	for l := byte(0); l < byte(rs.Size()); l++ {
		if rk.Has(l) {
			rk.Remove(l)
			assign(b, rs, d, rk, dir, line, start, end, empties, idx+1,
				append(next, Placement{Row: r, Col: c, Letter: l}), firstMove, cr, cc, out)
			rk.Add(l)
		}
	}
	if rk.Blanks() > 0 {
		rk.RemoveBlank()
		for l := byte(0); l < byte(rs.Size()); l++ {
			assign(b, rs, d, rk, dir, line, start, end, empties, idx+1,
				append(next, Placement{Row: r, Col: c, Letter: l, Blank: true}), firstMove, cr, cc, out)
		}
		rk.AddBlank()
	}
}

func validate(b *board.Board, rs *rules.Ruleset, d dict, dir Direction,
	line, start, end int, placed []Placement, firstMove bool, cr, cc int, out map[string]Move) {

	m, err := Evaluate(b, rs, dir, placed)
	if err != nil {
		return
	}
	if !d.has(m.Main.Letters) {
		return
	}
	for _, cw := range m.Cross {
		if !d.has(cw.Letters) {
			return
		}
	}
	if firstMove {
		if !coversCenter(dir, line, start, end, cr, cc) {
			return
		}
	} else {
		existing := false
		for a := start; a <= end; a++ {
			if cellFilled(b, dir, line, a) {
				existing = true
				break
			}
		}
		if !existing && len(m.Cross) == 0 {
			return // disconnected
		}
	}
	out[moveKey(dir, placed)] = m
}