Norvig_sudoku

sudoku.go

package main

import (
	"fmt"
	"log"
	"sort"
	"strings"
)

func cross(a []string, b []string) []string {
	var result []string
	for _, i := range a {
		for _, j := range b {
			result = append(result, i+j)
		}
	}
	return result
}

var digits = []string{"1", "2", "3", "4", "5", "6", "7", "8", "9"}
var rows = []string{"A", "B", "C", "D", "E", "F", "G", "H", "I"}
var cols = digits
var squares = cross(rows, cols)

func createUnitList() [][]string {
	var result [][]string

	for _, c := range cols {
		result = append(result, cross(rows, []string{c}))
	}

	for _, r := range rows {
		result = append(result, cross([]string{r}, cols))
	}

	rs := [][]string{
		{"A", "B", "C"},
		{"D", "E", "F"},
		{"G", "H", "I"},
	}

	cs := [][]string{
		{"1", "2", "3"},
		{"4", "5", "6"},
		{"7", "8", "9"},
	}
	for _, r := range rs {
		for _, c := range cs {
			result = append(result, cross(r, c))
		}
	}
	return result
}

func contains(arr []string, target string) bool {
	for _, v := range arr {
		if v == target {
			return true
		}
	}
	return false
}

func compareArray(a, b []string) bool {
	if len(a) != len(b) {
		return false
	}

	for i := 0; i < len(a); i++ {
		if a[i] != b[i] {
			return false
		}
	}
	return true
}

func createUnits() map[string][][]string {
	result := make(map[string][][]string)
	for _, s := range squares {
		for _, u := range unitlist {
			if contains(u, s) {
				r := result[s]
				r = append(r, u)
				result[s] = r
			}
		}
	}
	return result
}

var unitlist = createUnitList()
var units = createUnits()

var unitsC2 = [][]string{
	{"A2", "B2", "C2", "D2", "E2", "F2", "G2", "H2", "I2"},
	{"C1", "C2", "C3", "C4", "C5", "C6", "C7", "C8", "C9"},
	{"A1", "A2", "A3", "B1", "B2", "B3", "C1", "C2", "C3"},
}

type set map[string]struct{}

func createSet(inputs ...[]string) set {
	result := make(map[string]struct{})

	for _, input := range inputs {
		for _, v := range input {
			result[v] = struct{}{}
		}
	}
	return set(result)
}

func (s set) subtract(b set) set {
	result := make(map[string]struct{})
	for k, _ := range s {
		_, ok := b[k]
		if !ok {
			result[k] = struct{}{}
		}
	}
	return set(result)
}

func createPeers() map[string]set {
	result := make(map[string]set)
	for _, s := range squares {
		unitList := units[s]
		rSet := createSet(unitList...)
		result[s] = rSet.subtract(createSet([]string{s}))
	}
	return result
}

func (s set) equals(b set) bool {
	if len(s) != len(b) {
		return false
	}
	for k := range s {
		_, ok := b[k]
		if !ok {
			return false
		}
	}
	return true
}

func (s set) String() string {
	var arr []string
	for k := range s {
		arr = append(arr, k)
	}
	sort.Strings(arr)
	return strings.Join(arr, ",")
}

var peers = createPeers()
var peersC2 = createSet([]string{
	"A2", "B2", "D2", "E2", "F2", "G2", "H2", "I2",
	"C1", "C3", "C4", "C5", "C6", "C7", "C8", "C9",
	"A1", "A3", "B1", "B3"})

func assertSetup() {
	if len(squares) != 81 {
		log.Fatalf("len squares is %d", len(squares))
	}
	if len(unitlist) != 27 {
		log.Fatalf("len unitlist is %d", len(unitlist))
	}
	i := 0
	for _, ulist := range units["C2"] {
		if !compareArray(unitsC2[i], ulist) {
			log.Fatalf("unitList test fail")
		}
		i++
	}
	if i != 3 {
		log.Fatalf("i expected to be 3 got %d", i)
	}
	if !peers["C2"].equals(peersC2) {
		fmt.Println(peers["C2"])
		log.Fatalf("peers incorrect")
	}
	fmt.Println("ok")
}

func main() {
	assertSetup()
}