scrabble-solver/scrabble/gen_dawg.go

package scrabble

import (
	dawg "github.com/iliadenisov/dafsa"

	"gitea.iliadenisov.ru/developer/scrabble-solver/board"
	"gitea.iliadenisov.ru/developer/scrabble-solver/internal/encoding"
	"gitea.iliadenisov.ru/developer/scrabble-solver/rack"
	"gitea.iliadenisov.ru/developer/scrabble-solver/rules"
)

// DAWGGenerator generates moves with the Appel-Jacobson two-phase algorithm
// (LeftPart then ExtendRight) over a plain left-to-right DAWG.
type DAWGGenerator struct {
	rules  *rules.Ruleset
	finder dawg.Finder
}

// NewDAWGGenerator builds a DAWG generator for the ruleset over the dictionary finder.
func NewDAWGGenerator(rs *rules.Ruleset, finder dawg.Finder) *DAWGGenerator {
	return &DAWGGenerator{rules: rs, finder: finder}
}

// Name identifies the generator.
func (g *DAWGGenerator) Name() string { return "dawg" }

// GenerateMoves returns every legal play for rk on b in the modes' orientations.
func (g *DAWGGenerator) GenerateMoves(b *board.Board, rk rack.Rack, mode Mode) []Move {
	return generateBoth(b, g.rules, rk, mode, g.runAcross)
}

// tileInfo is a tentatively placed left-part tile (its column is fixed only once the
// left part's length is known, at record time).
type tileInfo struct {
	letter byte
	blank  bool
}

// acrossGen carries the state of one across-generation pass over a board.
type acrossGen struct {
	bd    *board.Board
	cur   *dawg.Cursor
	rs    *rules.Ruleset
	rk    rack.Rack
	size  int
	cross func(r, c int) letterSet
	emit  func(placements []Placement) // placements in bd's coordinates

	row   int
	left  []tileInfo  // left-part tiles, in word (left-to-right) order
	right []Placement // right-part tiles, with their columns
}

// runAcross generates all across plays on bd (cross-sets are computed as vertical words
// on bd) and reports each via emit in bd's coordinates.
func (g *DAWGGenerator) runAcross(bd *board.Board, rk rack.Rack, emit func([]Placement)) {
	cur, err := dawg.NewCursor(g.finder)
	if err != nil {
		return
	}
	size := g.rules.Size()

	cross := make([]letterSet, bd.Rows()*bd.Cols())
	known := make([]bool, bd.Rows()*bd.Cols())
	crossFn := func(r, c int) letterSet {
		i := r*bd.Cols() + c
		if !known[i] {
			above, below := columnContext(bd, r, c)
			cross[i] = dawgCrossSet(cur, above, below, size)
			known[i] = true
		}
		return cross[i]
	}

	ag := &acrossGen{bd: bd, cur: cur, rs: g.rules, rk: rk, size: size, cross: crossFn, emit: emit}

	firstMove := bd.IsEmpty()
	centerRow, centerCol := centerFor(bd, g.rules)
	for row := range bd.Rows() {
		ag.generateRow(row, firstMove, centerRow, centerCol)
	}
}

func (g *acrossGen) generateRow(row int, firstMove bool, centerRow, centerCol int) {
	g.row = row
	limit := 0
	for col := range g.bd.Cols() {
		if !g.bd.Empty(row, col) {
			limit = 0
			continue
		}
		anchor := false
		if firstMove {
			anchor = row == centerRow && col == centerCol
		} else {
			anchor = g.hasFilledNeighbor(row, col)
		}
		if !anchor {
			limit++
			continue
		}
		g.left = g.left[:0]
		g.right = g.right[:0]
		if col > 0 && g.bd.Filled(row, col-1) {
			if node, ok := g.walkPrefix(row, col); ok {
				g.extendRight(node, col, col)
			}
		} else {
			g.leftPart(g.cur.Root(), col, limit)
		}
		limit = 0
	}
}

func (g *acrossGen) hasFilledNeighbor(r, c int) bool {
	return g.bd.Filled(r-1, c) || g.bd.Filled(r+1, c) || g.bd.Filled(r, c-1) || g.bd.Filled(r, c+1)
}

// walkPrefix walks the DAWG through the contiguous filled run ending at col-1, returning
// the node reached and whether that prefix exists in the dictionary.
func (g *acrossGen) walkPrefix(row, col int) (dawg.Node, bool) {
	start := col - 1
	for start-1 >= 0 && g.bd.Filled(row, start-1) {
		start--
	}
	node := g.cur.Root()
	for c := start; c < col; c++ {
		var ok bool
		node, _, ok = g.cur.Next(node, encoding.Letter(g.bd.At(row, c)))
		if !ok {
			return node, false
		}
	}
	return node, true
}

// leftPart places left-part tiles from the rack (up to limit, on the empty squares left
// of the anchor), calling extendRight after each prefix.
func (g *acrossGen) leftPart(node dawg.Node, anchorCol, limit int) {
	g.extendRight(node, anchorCol, anchorCol)
	if limit == 0 {
		return
	}
	g.cur.Arcs(node, func(a dawg.Arc) bool {
		l := a.Label
		if g.rk.Has(l) {
			g.rk.Remove(l)
			g.left = append(g.left, tileInfo{letter: l})
			g.leftPart(a.Dest, anchorCol, limit-1)
			g.left = g.left[:len(g.left)-1]
			g.rk.Add(l)
		}
		if g.rk.Blanks() > 0 {
			g.rk.RemoveBlank()
			g.left = append(g.left, tileInfo{letter: l, blank: true})
			g.leftPart(a.Dest, anchorCol, limit-1)
			g.left = g.left[:len(g.left)-1]
			g.rk.AddBlank()
		}
		return true
	})
}

// extendRight extends the word rightward from col, placing rack tiles on empty squares
// (constrained by cross-sets) and following tiles already on the board. A word is
// recorded only past the anchor, so the play covers the anchor square.
func (g *acrossGen) extendRight(node dawg.Node, col, anchorCol int) {
	if col >= g.bd.Cols() {
		if col > anchorCol && g.cur.Final(node) {
			g.record(anchorCol)
		}
		return
	}
	if !g.bd.Empty(g.row, col) {
		if dest, _, ok := g.cur.Next(node, encoding.Letter(g.bd.At(g.row, col))); ok {
			g.extendRight(dest, col+1, anchorCol)
		}
		return
	}

	if col > anchorCol && g.cur.Final(node) {
		g.record(anchorCol)
	}
	cross := g.cross(g.row, col)
	g.cur.Arcs(node, func(a dawg.Arc) bool {
		l := a.Label
		if !cross.has(l) {
			return true
		}
		if g.rk.Has(l) {
			g.rk.Remove(l)
			g.right = append(g.right, Placement{Row: g.row, Col: col, Letter: l})
			g.extendRight(a.Dest, col+1, anchorCol)
			g.right = g.right[:len(g.right)-1]
			g.rk.Add(l)
		}
		if g.rk.Blanks() > 0 {
			g.rk.RemoveBlank()
			g.right = append(g.right, Placement{Row: g.row, Col: col, Letter: l, Blank: true})
			g.extendRight(a.Dest, col+1, anchorCol)
			g.right = g.right[:len(g.right)-1]
			g.rk.AddBlank()
		}
		return true
	})
}

// record assembles the play's placements (left part at fixed columns, then the right
// part) and reports it. It skips plays that lay no new tile.
func (g *acrossGen) record(anchorCol int) {
	if len(g.left)+len(g.right) == 0 {
		return
	}
	placements := make([]Placement, 0, len(g.left)+len(g.right))
	leftStart := anchorCol - len(g.left)
	for i, t := range g.left {
		placements = append(placements, Placement{Row: g.row, Col: leftStart + i, Letter: t.letter, Blank: t.blank})
	}
	placements = append(placements, g.right...)
	g.emit(placements)
}