462 lines
12 KiB
Go
462 lines
12 KiB
Go
package field
|
|
|
|
import (
|
|
"fmt"
|
|
"slices"
|
|
"strconv"
|
|
"strings"
|
|
)
|
|
|
|
type Properties struct {
|
|
Rows int
|
|
Columns int
|
|
BlockRows int
|
|
BlockColumns int
|
|
BlockSizeRow int
|
|
BlockSizeColumn int
|
|
Rating float64
|
|
}
|
|
|
|
type Field struct {
|
|
props *Properties
|
|
cells [][]Cell
|
|
changes []Change
|
|
}
|
|
|
|
type fieldSnapshot struct {
|
|
numbers [][]int
|
|
notes [][][]int
|
|
changes []Change
|
|
}
|
|
|
|
func New(props Properties, cells [][]Cell) (*Field, error) {
|
|
if err := validateProperties(props); err != nil {
|
|
return nil, err
|
|
}
|
|
if len(cells) != props.Rows {
|
|
return nil, fmt.Errorf("%w: expected %d rows, got %d", ErrInvalidField, props.Rows, len(cells))
|
|
}
|
|
|
|
cloned := make([][]Cell, props.Rows)
|
|
for row := 0; row < props.Rows; row++ {
|
|
if len(cells[row]) != props.Columns {
|
|
return nil, fmt.Errorf("%w: row %d has %d cells, expected %d", ErrInvalidField, row, len(cells[row]), props.Columns)
|
|
}
|
|
cloned[row] = make([]Cell, props.Columns)
|
|
for column := 0; column < props.Columns; column++ {
|
|
source := &cells[row][column]
|
|
if source.pos == nil {
|
|
return nil, fmt.Errorf("%w: cell %d/%d has no position", ErrInvalidField, row, column)
|
|
}
|
|
if !positionMatches(source.pos, props, row, column) {
|
|
return nil, fmt.Errorf("%w: cell %d/%d has inconsistent position", ErrInvalidField, row, column)
|
|
}
|
|
if source.number < 0 || source.number > props.Rows {
|
|
return nil, fmt.Errorf("%w: cell %d/%d contains %d", ErrInvalidField, row, column, source.number)
|
|
}
|
|
if source.notes == nil {
|
|
return nil, fmt.Errorf("%w: cell %d/%d has no notes", ErrInvalidField, row, column)
|
|
}
|
|
notes, err := normalizeNotes(source.notes.numbers, props.Rows, source.number)
|
|
if err != nil {
|
|
return nil, fmt.Errorf("%w: cell %d/%d: %w", ErrInvalidField, row, column, err)
|
|
}
|
|
cloned[row][column] = Cell{
|
|
number: source.number,
|
|
notes: &Notes{numbers: notes},
|
|
pos: NewPosition(row, column, row/props.BlockSizeRow, column/props.BlockSizeColumn, row%props.BlockSizeRow, column%props.BlockSizeColumn),
|
|
}
|
|
}
|
|
}
|
|
|
|
result := &Field{props: &props, cells: cloned}
|
|
if !result.hasValidNumbers() || !result.hasValidNotes() {
|
|
return nil, fmt.Errorf("%w: duplicate values or invalid candidates", ErrInvalidField)
|
|
}
|
|
return result, nil
|
|
}
|
|
|
|
func validateProperties(props Properties) error {
|
|
if props.Rows <= 0 || props.Columns <= 0 || props.Rows != props.Columns {
|
|
return fmt.Errorf("%w: rows and columns must be equal and positive", ErrInvalidField)
|
|
}
|
|
if props.BlockRows <= 0 || props.BlockColumns <= 0 || props.BlockSizeRow <= 0 || props.BlockSizeColumn <= 0 {
|
|
return fmt.Errorf("%w: block dimensions must be positive", ErrInvalidField)
|
|
}
|
|
if props.BlockRows*props.BlockSizeRow != props.Rows || props.BlockColumns*props.BlockSizeColumn != props.Columns {
|
|
return fmt.Errorf("%w: block dimensions do not cover the field", ErrInvalidField)
|
|
}
|
|
if props.BlockSizeRow*props.BlockSizeColumn != props.Rows {
|
|
return fmt.Errorf("%w: each block must contain %d cells", ErrInvalidField, props.Rows)
|
|
}
|
|
return nil
|
|
}
|
|
|
|
func normalizeNotes(notes []int, max, cellNumber int) ([]int, error) {
|
|
if cellNumber != 0 && len(notes) != 0 {
|
|
return nil, fmt.Errorf("filled cells cannot contain notes")
|
|
}
|
|
result := slices.Clone(notes)
|
|
slices.Sort(result)
|
|
result = slices.Compact(result)
|
|
for _, note := range result {
|
|
if note < 1 || note > max {
|
|
return nil, fmt.Errorf("note %d is out of range", note)
|
|
}
|
|
}
|
|
return result, nil
|
|
}
|
|
|
|
func positionMatches(pos *Position, props Properties, row, column int) bool {
|
|
return pos.row == row && pos.column == column &&
|
|
pos.blockRow == row/props.BlockSizeRow && pos.blockColumn == column/props.BlockSizeColumn &&
|
|
pos.inBlockRow == row%props.BlockSizeRow && pos.inBlockColumn == column%props.BlockSizeColumn
|
|
}
|
|
|
|
func (f *Field) GetRow(row int) (*Row, error) {
|
|
if !f.hasStructure() || row < 0 || row >= f.props.Rows {
|
|
return nil, ErrOutOfBounds
|
|
}
|
|
cells := make([]*Cell, f.props.Columns)
|
|
for column := range f.cells[row] {
|
|
cells[column] = &f.cells[row][column]
|
|
}
|
|
return &Row{Line: Line{cells: cells}}, nil
|
|
}
|
|
|
|
func (f *Field) GetColumn(column int) (*Column, error) {
|
|
if !f.hasStructure() || column < 0 || column >= f.props.Columns {
|
|
return nil, ErrOutOfBounds
|
|
}
|
|
cells := make([]*Cell, f.props.Rows)
|
|
for row := range f.cells {
|
|
cells[row] = &f.cells[row][column]
|
|
}
|
|
return &Column{Line: Line{cells: cells}}, nil
|
|
}
|
|
|
|
func (f *Field) GetBlock(row, column int) (*Block, error) {
|
|
if !f.hasStructure() || row < 0 || row >= f.props.BlockRows || column < 0 || column >= f.props.BlockColumns {
|
|
return nil, ErrOutOfBounds
|
|
}
|
|
startRow := row * f.props.BlockSizeRow
|
|
startColumn := column * f.props.BlockSizeColumn
|
|
cells := make([][]*Cell, f.props.BlockSizeRow)
|
|
for blockRow := range cells {
|
|
cells[blockRow] = make([]*Cell, f.props.BlockSizeColumn)
|
|
for blockColumn := range cells[blockRow] {
|
|
cells[blockRow][blockColumn] = &f.cells[startRow+blockRow][startColumn+blockColumn]
|
|
}
|
|
}
|
|
return &Block{cells: cells}, nil
|
|
}
|
|
|
|
func (f *Field) GetEachPartAtPos(pos *Position) ([]Part, error) {
|
|
if pos == nil {
|
|
return nil, ErrOutOfBounds
|
|
}
|
|
row, err := f.GetRow(pos.row)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
column, err := f.GetColumn(pos.column)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
block, err := f.GetBlock(pos.blockRow, pos.blockColumn)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
return []Part{row, column, block}, nil
|
|
}
|
|
|
|
func (f *Field) GetCell(row, column int) (*Cell, error) {
|
|
if !f.hasStructure() || row < 0 || row >= f.props.Rows || column < 0 || column >= f.props.Columns {
|
|
return nil, ErrOutOfBounds
|
|
}
|
|
return &f.cells[row][column], nil
|
|
}
|
|
|
|
func (f *Field) GetProperties() (Properties, error) {
|
|
if !f.hasStructure() {
|
|
return Properties{}, ErrInvalidField
|
|
}
|
|
return *f.props, nil
|
|
}
|
|
|
|
func (f *Field) GetRating() float64 {
|
|
if !f.hasStructure() {
|
|
return 0
|
|
}
|
|
return f.props.Rating
|
|
}
|
|
|
|
func (f *Field) ForEachPart(fn func(Part)) {
|
|
if !f.hasStructure() || fn == nil {
|
|
return
|
|
}
|
|
f.ForEachRow(func(row *Row) { fn(row) })
|
|
f.ForEachColumn(func(column *Column) { fn(column) })
|
|
f.ForEachBlock(func(block *Block) { fn(block) })
|
|
}
|
|
|
|
func (f *Field) ForEachPartAtPos(pos *Position, fn func(Part)) error {
|
|
if fn == nil {
|
|
return nil
|
|
}
|
|
parts, err := f.GetEachPartAtPos(pos)
|
|
if err != nil {
|
|
return err
|
|
}
|
|
for _, part := range parts {
|
|
fn(part)
|
|
}
|
|
return nil
|
|
}
|
|
|
|
func (f *Field) ForEachRow(fn func(*Row)) {
|
|
if !f.hasStructure() || fn == nil {
|
|
return
|
|
}
|
|
for row := 0; row < f.props.Rows; row++ {
|
|
part, _ := f.GetRow(row)
|
|
fn(part)
|
|
}
|
|
}
|
|
|
|
func (f *Field) ForEachColumn(fn func(*Column)) {
|
|
if !f.hasStructure() || fn == nil {
|
|
return
|
|
}
|
|
for column := 0; column < f.props.Columns; column++ {
|
|
part, _ := f.GetColumn(column)
|
|
fn(part)
|
|
}
|
|
}
|
|
|
|
func (f *Field) ForEachBlock(fn func(*Block)) {
|
|
if !f.hasStructure() || fn == nil {
|
|
return
|
|
}
|
|
for row := 0; row < f.props.BlockRows; row++ {
|
|
for column := 0; column < f.props.BlockColumns; column++ {
|
|
part, _ := f.GetBlock(row, column)
|
|
fn(part)
|
|
}
|
|
}
|
|
}
|
|
|
|
func (f *Field) ForEachCell(fn func(*Cell)) {
|
|
if !f.hasStructure() || fn == nil {
|
|
return
|
|
}
|
|
for row := range f.cells {
|
|
for column := range f.cells[row] {
|
|
fn(&f.cells[row][column])
|
|
}
|
|
}
|
|
}
|
|
|
|
func (f *Field) SetRating(rating float64) {
|
|
if f != nil && f.props != nil {
|
|
f.props.Rating = rating
|
|
}
|
|
}
|
|
|
|
func (f *Field) String() string {
|
|
if !f.hasStructure() {
|
|
return "<invalid field>"
|
|
}
|
|
var result strings.Builder
|
|
for row := 0; row < f.props.Rows; row++ {
|
|
if row > 0 && row%f.props.BlockSizeRow == 0 {
|
|
result.WriteByte('\n')
|
|
}
|
|
for column := 0; column < f.props.Columns; column++ {
|
|
if column > 0 {
|
|
if column%f.props.BlockSizeColumn == 0 {
|
|
result.WriteString(" | ")
|
|
} else {
|
|
result.WriteByte(' ')
|
|
}
|
|
}
|
|
value := f.cells[row][column].number
|
|
if value == 0 {
|
|
result.WriteRune('·')
|
|
} else {
|
|
result.WriteString(strconv.Itoa(value))
|
|
}
|
|
}
|
|
if row+1 < f.props.Rows {
|
|
result.WriteByte('\n')
|
|
}
|
|
}
|
|
return result.String()
|
|
}
|
|
|
|
func (f *Field) StringNotesForNumber(number int) string {
|
|
if !f.hasStructure() || number < 1 || number > f.props.Rows {
|
|
return ""
|
|
}
|
|
var result strings.Builder
|
|
f.ForEachCell(func(cell *Cell) {
|
|
if cell.notes.Has(number) {
|
|
fmt.Fprintf(&result, "%d/%d\n", cell.pos.row, cell.pos.column)
|
|
}
|
|
})
|
|
return strings.TrimSuffix(result.String(), "\n")
|
|
}
|
|
|
|
func (f *Field) StringNotes() string {
|
|
if !f.hasStructure() {
|
|
return "Notes:"
|
|
}
|
|
var result strings.Builder
|
|
result.WriteString("Notes:\n")
|
|
f.ForEachCell(func(cell *Cell) {
|
|
fmt.Fprintf(&result, "Pos: %d/%d - Notes: %v\n", cell.pos.row, cell.pos.column, cell.notes.numbers)
|
|
})
|
|
return strings.TrimSuffix(result.String(), "\n")
|
|
}
|
|
|
|
func (f *Field) IsSolved() bool {
|
|
if !f.IsValid() {
|
|
return false
|
|
}
|
|
for row := range f.cells {
|
|
for column := range f.cells[row] {
|
|
if f.cells[row][column].number == 0 {
|
|
return false
|
|
}
|
|
}
|
|
}
|
|
return true
|
|
}
|
|
|
|
func (f *Field) IsValid() bool {
|
|
return f.hasStructure() && f.hasValidNumbers() && f.hasValidNotes()
|
|
}
|
|
|
|
func (f *Field) hasStructure() bool {
|
|
if f == nil || f.props == nil || validateProperties(*f.props) != nil || len(f.cells) != f.props.Rows {
|
|
return false
|
|
}
|
|
for row := range f.cells {
|
|
if len(f.cells[row]) != f.props.Columns {
|
|
return false
|
|
}
|
|
for column := range f.cells[row] {
|
|
cell := &f.cells[row][column]
|
|
if cell.notes == nil || cell.pos == nil || !positionMatches(cell.pos, *f.props, row, column) || cell.number < 0 || cell.number > f.props.Rows {
|
|
return false
|
|
}
|
|
}
|
|
}
|
|
return true
|
|
}
|
|
|
|
func (f *Field) hasValidNumbers() bool {
|
|
if !f.hasStructure() {
|
|
return false
|
|
}
|
|
valid := true
|
|
f.ForEachPart(func(part Part) {
|
|
seen := make(map[int]struct{}, f.props.Rows)
|
|
part.ForEachCell(func(cell *Cell) {
|
|
if cell.number == 0 || !valid {
|
|
return
|
|
}
|
|
if _, exists := seen[cell.number]; exists {
|
|
valid = false
|
|
return
|
|
}
|
|
seen[cell.number] = struct{}{}
|
|
})
|
|
})
|
|
return valid
|
|
}
|
|
|
|
func (f *Field) hasValidNotes() bool {
|
|
if !f.hasStructure() {
|
|
return false
|
|
}
|
|
valid := true
|
|
f.ForEachCell(func(cell *Cell) {
|
|
if !valid {
|
|
return
|
|
}
|
|
if cell.number != 0 && len(cell.notes.numbers) != 0 {
|
|
valid = false
|
|
return
|
|
}
|
|
previous := 0
|
|
for _, note := range cell.notes.numbers {
|
|
if note <= previous || note > f.props.Rows || f.hasPeerNumber(cell, note) {
|
|
valid = false
|
|
return
|
|
}
|
|
previous = note
|
|
}
|
|
})
|
|
return valid
|
|
}
|
|
|
|
func (f *Field) ownsCell(cell *Cell) bool {
|
|
if !f.hasStructure() || cell == nil || cell.pos == nil {
|
|
return false
|
|
}
|
|
row, column := cell.pos.row, cell.pos.column
|
|
return row >= 0 && row < f.props.Rows && column >= 0 && column < f.props.Columns && &f.cells[row][column] == cell
|
|
}
|
|
|
|
func (f *Field) hasPeerNumber(cell *Cell, number int) bool {
|
|
if !f.ownsCell(cell) {
|
|
return false
|
|
}
|
|
row, column := cell.pos.row, cell.pos.column
|
|
for index := 0; index < f.props.Columns; index++ {
|
|
if index != column && f.cells[row][index].number == number {
|
|
return true
|
|
}
|
|
}
|
|
for index := 0; index < f.props.Rows; index++ {
|
|
if index != row && f.cells[index][column].number == number {
|
|
return true
|
|
}
|
|
}
|
|
startRow := cell.pos.blockRow * f.props.BlockSizeRow
|
|
startColumn := cell.pos.blockColumn * f.props.BlockSizeColumn
|
|
for blockRow := 0; blockRow < f.props.BlockSizeRow; blockRow++ {
|
|
for blockColumn := 0; blockColumn < f.props.BlockSizeColumn; blockColumn++ {
|
|
peer := &f.cells[startRow+blockRow][startColumn+blockColumn]
|
|
if peer != cell && peer.number == number {
|
|
return true
|
|
}
|
|
}
|
|
}
|
|
return false
|
|
}
|
|
|
|
func (f *Field) snapshot() fieldSnapshot {
|
|
state := fieldSnapshot{numbers: make([][]int, len(f.cells)), notes: make([][][]int, len(f.cells)), changes: slices.Clone(f.changes)}
|
|
for row := range f.cells {
|
|
state.numbers[row] = make([]int, len(f.cells[row]))
|
|
state.notes[row] = make([][]int, len(f.cells[row]))
|
|
for column := range f.cells[row] {
|
|
state.numbers[row][column] = f.cells[row][column].number
|
|
state.notes[row][column] = slices.Clone(f.cells[row][column].notes.numbers)
|
|
}
|
|
}
|
|
return state
|
|
}
|
|
|
|
func (f *Field) restore(state fieldSnapshot) {
|
|
for row := range f.cells {
|
|
for column := range f.cells[row] {
|
|
f.cells[row][column].number = state.numbers[row][column]
|
|
f.cells[row][column].notes.numbers = slices.Clone(state.notes[row][column])
|
|
}
|
|
}
|
|
f.changes = slices.Clone(state.changes)
|
|
}
|