puzzle_test.go

package sudoku

import (
	"fmt"
	"reflect"
	"sync"
	"testing"
	"time"
)

func runWithCompletionRate(input []int, sleepTime time.Duration) func(t *testing.T) {
	return func(t *testing.T) {
		// create the puzzle
		p, err := NewPuzzle(input)
		if err != nil {
			fmt.Printf("could not create puzzle: %s\n", err)
			return
		}

		wg := &sync.WaitGroup{}
		wg.Add(2)

		// solve the puzzle in a routine
		go func() {
			defer wg.Done()
			err := p.Solve()
			if err != nil {
				fmt.Printf("solve failed: %s\n", err)
				return
			}
		}()

		// periodically fetch the puzzle completion rate and print it
		go func() {
			defer wg.Done()
			for {
				completionRate, err := p.CompletionRate()
				if err != nil {
					fmt.Printf("could not get completion rate: %s\n", err)
				}

				// default to 0 percent
				progress := float64(0)
				if completionRate.TotalCells > 0 {
					// get the number of non-fixed cells
					total := float64(completionRate.TotalCells - completionRate.FixedCells)
					// get the number of non-fixed cells that have a value
					filled := float64(completionRate.FilledCells - completionRate.FixedCells)
					// work out the progress percentage
					progress = filled / total * 100
				}

				fmt.Printf("progress: %.1f\tattempted iterations: %d\tcell index: %d\tmin value: %d\n",
					progress, completionRate.AttemptedIterations,
					completionRate.CellIndex, completionRate.MinValueAtCell)

				switch {
				case completionRate.Completed:
					fmt.Printf("puzzle completed in %s\n", completionRate.CompletedAt.Sub(completionRate.StartedAt))
					return
				case completionRate.Failed:
					fmt.Printf("puzzle failed in %s: %v\n", completionRate.FailedAt.Sub(completionRate.StartedAt), completionRate.Error)
					return
				default:
					// still in progress.
					time.Sleep(sleepTime)
				}
			}
		}()

		// wait for the routines to finish
		wg.Wait()
	}
}

func TestPuzzle_CompletionRate(t *testing.T) {
	t.Run("4x4", runWithCompletionRate([]int{
		0, 0, 0, 3,
		0, 0, 0, 2,
		3, 0, 0, 0,
		4, 0, 0, 0,
	}, time.Millisecond*200))
	t.Run("9x9", runWithCompletionRate([]int{
		6, 0, 0, 0, 0, 0, 1, 5, 0,
		9, 5, 4, 7, 1, 0, 0, 8, 0,
		0, 0, 0, 5, 0, 2, 6, 0, 0,
		8, 0, 0, 0, 9, 4, 0, 0, 6,
		0, 0, 3, 8, 0, 5, 4, 0, 0,
		4, 0, 0, 3, 7, 0, 0, 0, 8,
		0, 0, 6, 9, 0, 3, 0, 0, 0,
		0, 2, 0, 0, 4, 7, 8, 9, 3,
		0, 4, 9, 0, 0, 0, 0, 0, 5,
	}, time.Millisecond*400))
	/* Skip this test because it takes a long time
	t.Run("16x16", runWithCompletionRate([]int{
		8, 0, 9, 0, 10, 0, 0, 12, 16, 0, 15, 0, 0, 0, 0, 4,
		0, 0, 15, 0, 0, 0, 5, 0, 0, 7, 0, 10, 0, 0, 13, 0,
		2, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 16, 0, 14,
		0, 6, 0, 3, 0, 0, 14, 0, 0, 0, 11, 0, 9, 0, 0, 0,
		0, 0, 0, 0, 0, 9, 0, 0, 1, 0, 0, 2, 0, 0, 0, 7,
		11, 0, 0, 0, 14, 0, 0, 6, 0, 0, 0, 0, 0, 13, 0, 0,
		0, 7, 0, 16, 0, 2, 0, 0, 12, 0, 0, 0, 0, 0, 1, 0,
		0, 0, 0, 5, 8, 0, 0, 13, 0, 3, 0, 0, 0, 0, 0, 9,
		12, 0, 4, 0, 0, 0, 7, 0, 13, 0, 8, 0, 11, 0, 0, 0,
		0, 5, 0, 8, 0, 13, 0, 10, 0, 16, 0, 4, 0, 0, 0, 0,
		0, 0, 14, 0, 0, 0, 9, 0, 6, 0, 0, 11, 0, 1, 0, 3,
		1, 0, 0, 0, 3, 0, 0, 5, 0, 0, 0, 0, 6, 0, 16, 0,
		14, 0, 7, 0, 0, 0, 10, 0, 0, 12, 0, 9, 0, 8, 2, 0,
		0, 16, 0, 12, 0, 14, 0, 3, 0, 0, 0, 0, 13, 0, 0, 11,
		5, 10, 0, 0, 6, 0, 11, 0, 0, 0, 14, 0, 0, 7, 0, 0,
		15, 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 5, 0, 0, 0, 12,
	}, time.Second*2))*/
	/* Skip this test because it takes a long time
	t.Run("25x25", runWithCompletionRate([]int{
		0, 0, 16, 12, 0, 22, 21, 0, 0, 0, 0, 4, 0, 6, 0, 0, 19, 1, 0, 7, 0, 2, 15, 0, 0,
		0, 17, 1, 9, 0, 23, 0, 0, 0, 6, 5, 0, 14, 0, 0, 15, 21, 0, 0, 0, 0, 16, 0, 20, 0,
		10, 0, 0, 0, 19, 15, 0, 0, 0, 3, 0, 1, 21, 16, 8, 0, 0, 0, 5, 0, 9, 0, 0, 11, 7,
		23, 2, 0, 7, 22, 12, 18, 0, 11, 5, 13, 0, 15, 0, 10, 16, 6, 0, 25, 24, 4, 14, 0, 1, 19,
		0, 0, 5, 21, 25, 0, 0, 16, 0, 9, 19, 0, 0, 0, 0, 0, 0, 12, 0, 0, 6, 10, 24, 0, 0,
		1, 0, 0, 16, 0, 0, 0, 0, 10, 12, 24, 0, 19, 0, 13, 0, 5, 0, 2, 0, 0, 15, 22, 8, 25,
		0, 0, 7, 2, 0, 14, 0, 0, 22, 20, 0, 8, 0, 25, 0, 0, 17, 19, 0, 0, 0, 1, 0, 0, 16,
		25, 0, 0, 0, 17, 0, 6, 5, 18, 0, 1, 14, 2, 4, 0, 12, 16, 23, 0, 0, 11, 0, 0, 0, 0,
		24, 21, 0, 23, 0, 13, 19, 1, 0, 15, 0, 12, 0, 20, 22, 0, 0, 25, 11, 18, 0, 5, 0, 0, 0,
		0, 3, 0, 15, 0, 0, 0, 2, 0, 16, 0, 0, 11, 0, 9, 1, 8, 0, 22, 13, 21, 23, 20, 12, 0,
		0, 0, 24, 25, 0, 11, 0, 0, 9, 14, 0, 0, 0, 13, 0, 0, 0, 4, 0, 2, 15, 6, 0, 21, 0,
		13, 0, 12, 0, 0, 0, 5, 15, 2, 0, 16, 21, 0, 14, 0, 0, 10, 9, 20, 0, 0, 0, 1, 0, 18,
		0, 14, 23, 18, 0, 6, 0, 25, 0, 22, 0, 0, 10, 0, 0, 13, 0, 16, 0, 15, 0, 7, 5, 3, 0,
		7, 0, 15, 0, 0, 0, 8, 18, 13, 0, 0, 9, 0, 2, 6, 0, 12, 24, 19, 0, 0, 0, 23, 0, 20,
		0, 19, 0, 22, 2, 1, 0, 20, 0, 0, 0, 15, 0, 0, 0, 5, 25, 0, 0, 21, 0, 9, 11, 0, 0,
		0, 18, 11, 1, 7, 5, 13, 0, 14, 4, 6, 0, 23, 0, 0, 9, 0, 2, 0, 0, 0, 12, 0, 22, 0,
		0, 0, 0, 13, 0, 24, 25, 8, 0, 0, 10, 7, 0, 1, 0, 4, 0, 22, 23, 5, 0, 3, 0, 6, 11,
		0, 0, 0, 0, 21, 0, 0, 12, 23, 19, 0, 24, 20, 3, 4, 0, 15, 13, 17, 0, 10, 0, 0, 0, 9,
		22, 0, 0, 19, 0, 0, 0, 10, 20, 0, 0, 25, 0, 17, 0, 6, 18, 0, 0, 16, 0, 21, 8, 0, 0,
		17, 8, 20, 10, 0, 0, 1, 0, 15, 0, 9, 0, 5, 0, 16, 19, 11, 0, 0, 0, 0, 4, 0, 0, 13,
		0, 0, 14, 24, 16, 0, 0, 22, 0, 0, 0, 0, 0, 0, 23, 17, 0, 11, 0, 0, 19, 8, 7, 0, 0,
		19, 4, 0, 8, 11, 10, 9, 0, 3, 18, 17, 0, 1, 0, 20, 2, 7, 0, 24, 6, 25, 22, 0, 14, 5,
		15, 20, 0, 0, 23, 0, 12, 0, 0, 0, 14, 13, 9, 11, 0, 18, 0, 0, 0, 8, 1, 0, 0, 0, 2,
		0, 1, 0, 3, 0, 0, 0, 0, 7, 11, 0, 0, 8, 0, 19, 25, 0, 0, 0, 23, 0, 20, 9, 17, 0,
		0, 0, 9, 6, 0, 17, 0, 4, 8, 0, 0, 18, 0, 12, 0, 0, 0, 0, 1, 19, 0, 11, 16, 0, 0,
	}, time.Second*5))*/
}

func benchmarkPuzzle(input []int) func(b *testing.B) {
	return func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			p, err := NewPuzzle(input)
			if err != nil {
				b.Errorf("could not create puzzle: %s", err)
				return
			}
			if err = p.Solve(); err != nil {
				b.Errorf("could not create puzzle: %s", err)
				return
			}
		}
	}
}

func BenchmarkPuzzle_Solve(b *testing.B) {
	b.Run("4x4", benchmarkPuzzle([]int{
		0, 0, 0, 3,
		0, 0, 0, 2,
		3, 0, 0, 0,
		4, 0, 0, 0,
	}))
	b.Run("9x9", benchmarkPuzzle([]int{
		6, 0, 0, 0, 0, 0, 1, 5, 0,
		9, 5, 4, 7, 1, 0, 0, 8, 0,
		0, 0, 0, 5, 0, 2, 6, 0, 0,
		8, 0, 0, 0, 9, 4, 0, 0, 6,
		0, 0, 3, 8, 0, 5, 4, 0, 0,
		4, 0, 0, 3, 7, 0, 0, 0, 8,
		0, 0, 6, 9, 0, 3, 0, 0, 0,
		0, 2, 0, 0, 4, 7, 8, 9, 3,
		0, 4, 9, 0, 0, 0, 0, 0, 5,
	}))
}

func ExamplePuzzle_Solve() {
	input := []int{
		0, 0, 0, 3,
		0, 0, 0, 2,
		3, 0, 0, 0,
		4, 0, 0, 0,
	}
	p, _ := NewPuzzle(input)
	_ = p.Solve()
	res, _ := p.Result()

	printItems := func(data []int) {
		formatted, _ := FormatPuzzle(data)
		for _, line := range formatted {
			for k, cell := range line {
				fmt.Printf("%d", cell)
				if k != len(line)-1 {
					fmt.Printf(" ")
				}
			}
			fmt.Printf("\n")
		}
	}
	printItems(input)
	fmt.Println("-------")
	printItems(res)

	// Output:
	// 0 0 0 3
	// 0 0 0 2
	// 3 0 0 0
	// 4 0 0 0
	// -------
	// 2 4 1 3
	// 1 3 4 2
	// 3 1 2 4
	// 4 2 3 1
}

func TestPuzzle_Solve(t *testing.T) {
	run := func(in []int, exp []int) func(*testing.T) {
		return func(t *testing.T) {
			p, err := NewPuzzle(in)
			if err != nil {
				t.Errorf("could not create new puzzle: %s", err)
				return
			}

			if err := p.Solve(); err != nil {
				t.Errorf("could not solve puzzle: %s", err)
				return
			}

			got, err := p.Result()
			if err != nil {
				t.Errorf("could not get result: %s", err)
				return
			}

			if !reflect.DeepEqual(exp, got) {
				t.Errorf("expected %v, got %v", exp, got)
				return
			}
		}
	}

	type def struct {
		Exp []int
		In  []int
	}

	t.Run("4x4", func(t *testing.T) {
		tests := []def{
			{
				Exp: []int{
					2, 4, 1, 3,
					1, 3, 4, 2,
					3, 1, 2, 4,
					4, 2, 3, 1,
				},
				In: []int{
					0, 0, 0, 3,
					0, 0, 0, 2,
					3, 0, 0, 0,
					4, 0, 0, 0,
				},
			},
		}
		for k, tc := range tests {
			t.Run(fmt.Sprint(k), run(tc.In, tc.Exp))
		}
	})

	t.Run("9x9", func(t *testing.T) {
		tests := []def{
			{
				Exp: []int{
					4, 8, 3, 9, 2, 1, 6, 5, 7,
					9, 6, 7, 3, 4, 5, 8, 2, 1,
					2, 5, 1, 8, 7, 6, 4, 9, 3,
					5, 4, 8, 1, 3, 2, 9, 7, 6,
					7, 2, 9, 5, 6, 4, 1, 3, 8,
					1, 3, 6, 7, 9, 8, 2, 4, 5,
					3, 7, 2, 6, 8, 9, 5, 1, 4,
					8, 1, 4, 2, 5, 3, 7, 6, 9,
					6, 9, 5, 4, 1, 7, 3, 8, 2,
				},
				In: []int{
					4, 8, 3, 9, 2, 1, 6, 5, 7,
					9, 6, 7, 3, 4, 5, 8, 2, 1,
					2, 5, 1, 8, 7, 6, 4, 9, 3,
					5, 4, 8, 1, 3, 2, 9, 7, 6,
					7, 2, 9, 5, 6, 0, 1, 3, 8,
					1, 3, 6, 7, 9, 8, 2, 4, 5,
					3, 7, 2, 6, 8, 9, 5, 1, 4,
					8, 1, 4, 2, 5, 3, 7, 6, 9,
					6, 9, 5, 4, 1, 7, 3, 8, 2,
				},
			},
			{
				Exp: []int{
					4, 8, 3, 9, 2, 1, 6, 5, 7,
					9, 6, 7, 3, 4, 5, 8, 2, 1,
					2, 5, 1, 8, 7, 6, 4, 9, 3,
					5, 4, 8, 1, 3, 2, 9, 7, 6,
					7, 2, 9, 5, 6, 4, 1, 3, 8,
					1, 3, 6, 7, 9, 8, 2, 4, 5,
					3, 7, 2, 6, 8, 9, 5, 1, 4,
					8, 1, 4, 2, 5, 3, 7, 6, 9,
					6, 9, 5, 4, 1, 7, 3, 8, 2,
				},
				In: []int{
					4, 8, 3, 9, 2, 1, 6, 5, 7,
					9, 6, 7, 3, 4, 5, 8, 2, 1,
					2, 5, 1, 8, 7, 0, 4, 9, 3,
					5, 4, 8, 1, 3, 2, 9, 7, 6,
					7, 2, 9, 5, 6, 0, 1, 3, 8,
					1, 3, 6, 7, 9, 8, 2, 4, 5,
					3, 7, 2, 6, 8, 9, 5, 1, 4,
					8, 1, 4, 2, 5, 3, 7, 6, 9,
					6, 9, 5, 4, 1, 7, 3, 8, 2,
				},
			},
			{
				Exp: []int{
					4, 8, 3, 9, 2, 1, 6, 5, 7,
					9, 6, 7, 3, 4, 5, 8, 2, 1,
					2, 5, 1, 8, 7, 6, 4, 9, 3,
					5, 4, 8, 1, 3, 2, 9, 7, 6,
					7, 2, 9, 5, 6, 4, 1, 3, 8,
					1, 3, 6, 7, 9, 8, 2, 4, 5,
					3, 7, 2, 6, 8, 9, 5, 1, 4,
					8, 1, 4, 2, 5, 3, 7, 6, 9,
					6, 9, 5, 4, 1, 7, 3, 8, 2,
				},
				In: []int{
					4, 8, 3, 9, 2, 1, 6, 5, 7,
					9, 6, 7, 0, 4, 5, 8, 2, 1,
					2, 5, 1, 0, 0, 0, 4, 9, 3,
					5, 4, 8, 1, 3, 2, 9, 7, 6,
					7, 2, 9, 5, 6, 0, 1, 3, 8,
					1, 3, 6, 7, 9, 8, 2, 4, 5,
					3, 7, 2, 6, 8, 9, 5, 1, 4,
					8, 1, 4, 2, 5, 3, 7, 6, 9,
					6, 9, 5, 4, 1, 7, 3, 8, 2,
				},
			},
			{
				Exp: []int{
					4, 8, 3, 9, 2, 1, 6, 5, 7,
					9, 6, 7, 3, 4, 5, 8, 2, 1,
					2, 5, 1, 8, 7, 6, 4, 9, 3,
					5, 4, 8, 1, 3, 2, 9, 7, 6,
					7, 2, 9, 5, 6, 4, 1, 3, 8,
					1, 3, 6, 7, 9, 8, 2, 4, 5,
					3, 7, 2, 6, 8, 9, 5, 1, 4,
					8, 1, 4, 2, 5, 3, 7, 6, 9,
					6, 9, 5, 4, 1, 7, 3, 8, 2,
				},
				In: []int{
					0, 0, 3, 0, 2, 0, 6, 0, 0,
					9, 0, 0, 3, 0, 5, 0, 0, 1,
					0, 0, 1, 8, 0, 6, 4, 0, 0,
					0, 0, 8, 1, 0, 2, 9, 0, 0,
					7, 0, 0, 0, 0, 0, 0, 0, 8,
					0, 0, 6, 7, 0, 8, 2, 0, 0,
					0, 0, 2, 6, 0, 9, 5, 0, 0,
					8, 0, 0, 2, 0, 3, 0, 0, 9,
					0, 0, 5, 0, 1, 0, 3, 0, 0,
				},
			},
			{
				Exp: []int{
					6, 3, 2, 4, 8, 9, 1, 5, 7,
					9, 5, 4, 7, 1, 6, 3, 8, 2,
					1, 7, 8, 5, 3, 2, 6, 4, 9,
					8, 1, 7, 2, 9, 4, 5, 3, 6,
					2, 9, 3, 8, 6, 5, 4, 7, 1,
					4, 6, 5, 3, 7, 1, 9, 2, 8,
					7, 8, 6, 9, 5, 3, 2, 1, 4,
					5, 2, 1, 6, 4, 7, 8, 9, 3,
					3, 4, 9, 1, 2, 8, 7, 6, 5,
				},
				In: []int{
					6, 0, 0, 0, 0, 0, 1, 5, 0,
					9, 5, 4, 7, 1, 0, 0, 8, 0,
					0, 0, 0, 5, 0, 2, 6, 0, 0,
					8, 0, 0, 0, 9, 4, 0, 0, 6,
					0, 0, 3, 8, 0, 5, 4, 0, 0,
					4, 0, 0, 3, 7, 0, 0, 0, 8,
					0, 0, 6, 9, 0, 3, 0, 0, 0,
					0, 2, 0, 0, 4, 7, 8, 9, 3,
					0, 4, 9, 0, 0, 0, 0, 0, 5,
				},
			},
		}
		for k, tc := range tests {
			t.Run(fmt.Sprint(k), run(tc.In, tc.Exp))
		}
	})
}

func testCalculatePuzzleSize(input []int, exp int) func(t *testing.T) {
	return func(t *testing.T) {
		got, err := CalculatePuzzleSize(input)
		if err != nil {
			t.Errorf("unexpected error: %s", err)
			return
		}
		if exp != got {
			t.Errorf("expected %d, got %d", exp, got)
			return
		}
	}
}

func TestCalculatePuzzleSize(t *testing.T) {
	t.Run("4", testCalculatePuzzleSize([]int{
		0, 0, 0, 0,
		0, 0, 0, 0,
		0, 0, 0, 0,
		0, 0, 0, 0,
	}, 4))
	t.Run("9", testCalculatePuzzleSize([]int{
		0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0,
	}, 9))
	t.Run("16", testCalculatePuzzleSize([]int{
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	}, 16))

	t.Run("25", testCalculatePuzzleSize([]int{
		0, 0, 16, 12, 0, 22, 21, 0, 0, 0, 0, 4, 0, 6, 0, 0, 19, 1, 0, 7, 0, 2, 15, 0, 0,
		0, 17, 1, 9, 0, 23, 0, 0, 0, 6, 5, 0, 14, 0, 0, 15, 21, 0, 0, 0, 0, 16, 0, 20, 0,
		10, 0, 0, 0, 19, 15, 0, 0, 0, 3, 0, 1, 21, 16, 8, 0, 0, 0, 5, 0, 9, 0, 0, 11, 7,
		23, 2, 0, 7, 22, 12, 18, 0, 11, 5, 13, 0, 15, 0, 10, 16, 6, 0, 25, 24, 4, 14, 0, 1, 19,
		0, 0, 5, 21, 25, 0, 0, 16, 0, 9, 19, 0, 0, 0, 0, 0, 0, 12, 0, 0, 6, 10, 24, 0, 0,

		1, 0, 0, 16, 0, 0, 0, 0, 10, 12, 24, 0, 19, 0, 13, 0, 5, 0, 2, 0, 0, 15, 22, 8, 25,
		0, 0, 7, 2, 0, 14, 0, 0, 22, 20, 0, 8, 0, 25, 0, 0, 17, 19, 0, 0, 0, 1, 0, 0, 16,
		25, 0, 0, 0, 17, 0, 6, 5, 18, 0, 1, 14, 2, 4, 0, 12, 16, 23, 0, 0, 11, 0, 0, 0, 0,
		24, 21, 0, 23, 0, 13, 19, 1, 0, 15, 0, 12, 0, 20, 22, 0, 0, 25, 11, 18, 0, 5, 0, 0, 0,
		0, 3, 0, 15, 0, 0, 0, 2, 0, 16, 0, 0, 11, 0, 9, 1, 8, 0, 22, 13, 21, 23, 20, 12, 0,

		0, 0, 24, 25, 0, 11, 0, 0, 9, 14, 0, 0, 0, 13, 0, 0, 0, 4, 0, 2, 15, 6, 0, 21, 0,
		13, 0, 12, 0, 0, 0, 5, 15, 2, 0, 16, 21, 0, 14, 0, 0, 10, 9, 20, 0, 0, 0, 1, 0, 18,
		0, 14, 23, 18, 0, 6, 0, 25, 0, 22, 0, 0, 10, 0, 0, 13, 0, 16, 0, 15, 0, 7, 5, 3, 0,
		7, 0, 15, 0, 0, 0, 8, 18, 13, 0, 0, 9, 0, 2, 6, 0, 12, 24, 19, 0, 0, 0, 23, 0, 20,
		0, 19, 0, 22, 2, 1, 0, 20, 0, 0, 0, 15, 0, 0, 0, 5, 25, 0, 0, 21, 0, 9, 11, 0, 0,

		0, 18, 11, 1, 7, 5, 13, 0, 14, 4, 6, 0, 23, 0, 0, 9, 0, 2, 0, 0, 0, 12, 0, 22, 0,
		0, 0, 0, 13, 0, 24, 25, 8, 0, 0, 10, 7, 0, 1, 0, 4, 0, 22, 23, 5, 0, 3, 0, 6, 11,
		0, 0, 0, 0, 21, 0, 0, 12, 23, 19, 0, 24, 20, 3, 4, 0, 15, 13, 17, 0, 10, 0, 0, 0, 9,
		22, 0, 0, 19, 0, 0, 0, 10, 20, 0, 0, 25, 0, 17, 0, 6, 18, 0, 0, 16, 0, 21, 8, 0, 0,
		17, 8, 20, 10, 0, 0, 1, 0, 15, 0, 9, 0, 5, 0, 16, 19, 11, 0, 0, 0, 0, 4, 0, 0, 13,

		0, 0, 14, 24, 16, 0, 0, 22, 0, 0, 0, 0, 0, 0, 23, 17, 0, 11, 0, 0, 19, 8, 7, 0, 0,
		19, 4, 0, 8, 11, 10, 9, 0, 3, 18, 17, 0, 1, 0, 20, 2, 7, 0, 24, 6, 25, 22, 0, 14, 5,
		15, 20, 0, 0, 23, 0, 12, 0, 0, 0, 14, 13, 9, 11, 0, 18, 0, 0, 0, 8, 1, 0, 0, 0, 2,
		0, 1, 0, 3, 0, 0, 0, 0, 7, 11, 0, 0, 8, 0, 19, 25, 0, 0, 0, 23, 0, 20, 9, 17, 0,
		0, 0, 9, 6, 0, 17, 0, 4, 8, 0, 0, 18, 0, 12, 0, 0, 0, 0, 1, 19, 0, 11, 16, 0, 0,
	}, 25))
}

func testCalculateSectionSize(input []int, exp int) func(t *testing.T) {
	return func(t *testing.T) {
		got, err := CalculateSectionSize(input, 0)
		if err != nil {
			t.Errorf("unexpected error: %s", err)
			return
		}
		if exp != got {
			t.Errorf("expected %d, got %d", exp, got)
			return
		}
	}
}

func TestSectionPuzzleSize(t *testing.T) {
	t.Run("2", testCalculateSectionSize([]int{
		0, 0, 0, 0,
		0, 0, 0, 0,
		0, 0, 0, 0,
		0, 0, 0, 0,
	}, 2))
	t.Run("3", testCalculateSectionSize([]int{
		0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0,
	}, 3))
	t.Run("4", testCalculateSectionSize([]int{
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	}, 4))
	t.Run("4", testCalculateSectionSize([]int{
		0, 0, 16, 12, 0, 22, 21, 0, 0, 0, 0, 4, 0, 6, 0, 0, 19, 1, 0, 7, 0, 2, 15, 0, 0,
		0, 17, 1, 9, 0, 23, 0, 0, 0, 6, 5, 0, 14, 0, 0, 15, 21, 0, 0, 0, 0, 16, 0, 20, 0,
		10, 0, 0, 0, 19, 15, 0, 0, 0, 3, 0, 1, 21, 16, 8, 0, 0, 0, 5, 0, 9, 0, 0, 11, 7,
		23, 2, 0, 7, 22, 12, 18, 0, 11, 5, 13, 0, 15, 0, 10, 16, 6, 0, 25, 24, 4, 14, 0, 1, 19,
		0, 0, 5, 21, 25, 0, 0, 16, 0, 9, 19, 0, 0, 0, 0, 0, 0, 12, 0, 0, 6, 10, 24, 0, 0,

		1, 0, 0, 16, 0, 0, 0, 0, 10, 12, 24, 0, 19, 0, 13, 0, 5, 0, 2, 0, 0, 15, 22, 8, 25,
		0, 0, 7, 2, 0, 14, 0, 0, 22, 20, 0, 8, 0, 25, 0, 0, 17, 19, 0, 0, 0, 1, 0, 0, 16,
		25, 0, 0, 0, 17, 0, 6, 5, 18, 0, 1, 14, 2, 4, 0, 12, 16, 23, 0, 0, 11, 0, 0, 0, 0,
		24, 21, 0, 23, 0, 13, 19, 1, 0, 15, 0, 12, 0, 20, 22, 0, 0, 25, 11, 18, 0, 5, 0, 0, 0,
		0, 3, 0, 15, 0, 0, 0, 2, 0, 16, 0, 0, 11, 0, 9, 1, 8, 0, 22, 13, 21, 23, 20, 12, 0,

		0, 0, 24, 25, 0, 11, 0, 0, 9, 14, 0, 0, 0, 13, 0, 0, 0, 4, 0, 2, 15, 6, 0, 21, 0,
		13, 0, 12, 0, 0, 0, 5, 15, 2, 0, 16, 21, 0, 14, 0, 0, 10, 9, 20, 0, 0, 0, 1, 0, 18,
		0, 14, 23, 18, 0, 6, 0, 25, 0, 22, 0, 0, 10, 0, 0, 13, 0, 16, 0, 15, 0, 7, 5, 3, 0,
		7, 0, 15, 0, 0, 0, 8, 18, 13, 0, 0, 9, 0, 2, 6, 0, 12, 24, 19, 0, 0, 0, 23, 0, 20,
		0, 19, 0, 22, 2, 1, 0, 20, 0, 0, 0, 15, 0, 0, 0, 5, 25, 0, 0, 21, 0, 9, 11, 0, 0,

		0, 18, 11, 1, 7, 5, 13, 0, 14, 4, 6, 0, 23, 0, 0, 9, 0, 2, 0, 0, 0, 12, 0, 22, 0,
		0, 0, 0, 13, 0, 24, 25, 8, 0, 0, 10, 7, 0, 1, 0, 4, 0, 22, 23, 5, 0, 3, 0, 6, 11,
		0, 0, 0, 0, 21, 0, 0, 12, 23, 19, 0, 24, 20, 3, 4, 0, 15, 13, 17, 0, 10, 0, 0, 0, 9,
		22, 0, 0, 19, 0, 0, 0, 10, 20, 0, 0, 25, 0, 17, 0, 6, 18, 0, 0, 16, 0, 21, 8, 0, 0,
		17, 8, 20, 10, 0, 0, 1, 0, 15, 0, 9, 0, 5, 0, 16, 19, 11, 0, 0, 0, 0, 4, 0, 0, 13,

		0, 0, 14, 24, 16, 0, 0, 22, 0, 0, 0, 0, 0, 0, 23, 17, 0, 11, 0, 0, 19, 8, 7, 0, 0,
		19, 4, 0, 8, 11, 10, 9, 0, 3, 18, 17, 0, 1, 0, 20, 2, 7, 0, 24, 6, 25, 22, 0, 14, 5,
		15, 20, 0, 0, 23, 0, 12, 0, 0, 0, 14, 13, 9, 11, 0, 18, 0, 0, 0, 8, 1, 0, 0, 0, 2,
		0, 1, 0, 3, 0, 0, 0, 0, 7, 11, 0, 0, 8, 0, 19, 25, 0, 0, 0, 23, 0, 20, 9, 17, 0,
		0, 0, 9, 6, 0, 17, 0, 4, 8, 0, 0, 18, 0, 12, 0, 0, 0, 0, 1, 19, 0, 11, 16, 0, 0,
	}, 5))
}

func TestFormatPuzzle(t *testing.T) {
	input := []int{
		1, 2, 3, 4,
		5, 6, 7, 8,
		9, 10, 11, 12,
		13, 14, 15, 16,
	}
	exp := [][]int{
		{1, 2, 3, 4},
		{5, 6, 7, 8},
		{9, 10, 11, 12},
		{13, 14, 15, 16},
	}
	got, err := FormatPuzzle(input)
	if err != nil {
		t.Errorf("unexpected error: %s", err)
	}
	if !reflect.DeepEqual(exp, got) {
		t.Errorf("exp: %v, got %v", exp, got)
		return
	}
}