// Copyright (C) 2016 Mikael Berthe <mikael@lilotux.net>. All rights reserved.

// Use of this source code is governed by the MIT license,

// which can be found in the LICENSE file.

package takuzu

// This file contains the functions and methods used to build a new takuzu

// puzzle.

import (

	"fmt"

	"log"

	"math/rand"

	"time"

	"github.com/pkg/errors"

)

func init() {

	rand.Seed(time.Now().UTC().UnixNano())

}

type buildTakuzuOptions struct {

	size                                  int

	minRatio, maxRatio                    int

	simple                                bool

	buildBoardTimeout, reduceBoardTimeout time.Duration

}

// ReduceBoard randomly removes as many numbers as possible from the

// takuzu board and returns a pointer to the new board.

// The initial takuzu might be modified.

func (tak Takuzu) ReduceBoard(trivial bool, wid string, buildBoardTimeout, reduceBoardTimeout time.Duration) (*Takuzu, error) {

	size := tak.Size

	// First check if the board is correct

	if verbosity > 0 {

		log.Printf("[%v]ReduceBoard: Checking for all grid solutions...", wid)

	}

	allSol := &[]Takuzu{}

	_, err := tak.Clone().TrySolveRecurse(allSol, buildBoardTimeout)

	ns := len(*allSol)

	if err != nil && errors.Cause(err).Error() == "timeout" {

		if verbosity > 0 {

			log.Printf("[%v]ReduceBoard: There was a timeout (%d resolution(s) found).", wid, ns)

		}

		if ns == 0 {

			return nil, err

		}

		//if ns < 10 { return nil, err }

		if verbosity > 0 {

			log.Printf("[%v]ReduceBoard: Going on anyway...", wid)

		}

	}

	if verbosity > 0 {

		log.Printf("[%v]ReduceBoard: %d solution(s) found.", wid, ns)

	}

	if ns == 0 {

		return nil, err

	} else if ns > 1 {

		tak = (*allSol)[rand.Intn(ns)]

		if verbosity > 0 {

			log.Printf("[%v]ReduceBoard: Warning: there are %d solutions.", wid, ns)

			log.Printf("[%v]ReduceBoard: Picking one randomly.", wid)

			if verbosity > 1 {

				tak.DumpBoard()

				fmt.Println()

			}

		}

		allSol = nil

	} else {

		// 1 and only 1 solution

		if verbosity > 1 {

			tak.DumpBoard()

			fmt.Println()

		}

	}

	if verbosity > 0 {

		log.Printf("[%v]ReduceBoard: Grid reduction...", wid)

	}

	fields := make([]*Cell, size*size)

	n := 0

	for l := range tak.Board {

		for c := range tak.Board[l] {

			if tak.Board[l][c].Defined {

				fields[n] = &tak.Board[l][c]

				n++

			}

		}

	}

	nDigits := 0

	initialDigits := n

	ratio := 0

	if verbosity > 0 {

		log.Printf("[%v]ReduceBoard: %d%%", wid, ratio)

	}

	for ; n > 0; n-- {

		var rollback bool

		i := rand.Intn(n)

		fields[i].Defined = false

		if trivial {

			full, err := tak.Clone().TrySolveTrivial()

			if err != nil || !full {

				rollback = true

			}

		} else {

			allSol = &[]Takuzu{}

			_, err := tak.Clone().TrySolveRecurse(allSol, reduceBoardTimeout)

			if err != nil || len(*allSol) != 1 {

				rollback = true

			}

		}

		if rollback {

			if verbosity > 1 {

				log.Printf("[%v]ReduceBoard: Backing out", wid)

			}

			fields[i].Defined = true // Back out!

			nDigits++

		}

		fields = append(fields[:i], fields[i+1:]...)

		if verbosity > 0 {

			nr := (initialDigits - n) * 100 / initialDigits

			if nr > ratio {

				ratio = nr

				log.Printf("[%v]ReduceBoard: %d%%", wid, ratio)

			}

		}

	}

	if verbosity > 0 {

		log.Printf("[%v]ReduceBoard: I have left %d digits.", wid, nDigits)

	}

	return &tak, nil

}

// newRandomTakuzu creates a new Takuzu board with a given size

// It is intended to be called by NewRandomTakuzu only.

func newRandomTakuzu(wid string, buildOpts buildTakuzuOptions) (*Takuzu, error) {

	size := buildOpts.size

	easy := buildOpts.simple

	buildBoardTimeout := buildOpts.buildBoardTimeout

	reduceBoardTimeout := buildOpts.reduceBoardTimeout

	minRatio := buildOpts.minRatio

	maxRatio := buildOpts.maxRatio

	tak := New(size)

	n := size * size

	fields := make([]*Cell, n)

	i := 0

	for l := range tak.Board {

		for c := range tak.Board[l] {

			fields[i] = &tak.Board[l][c]

			i++

		}

	}

	if verbosity > 0 {

		log.Printf("[%v]NewRandomTakuzu: Filling new board (%dx%[2]d)...", wid, size)

	}

	nop := 0

	// #1. Loop until the ratio of empty cells is less than minRatio% (e.g. 55%)

	for n > size*size*minRatio/100 {

		i := rand.Intn(n)

		fields[i].Defined = true

		fields[i].Value = rand.Intn(2)

		var err error

		if _, err = tak.Validate(); err != nil {

			if verbosity > 1 {

				log.Printf("[%v]NewRandomTakuzu: Could not set cell value to %v", wid, fields[i].Value)

			}

		} else if _, err = tak.Clone().TrySolveTrivial(); err != nil {

			if verbosity > 1 {

				log.Printf("[%v]NewRandomTakuzu: Trivial checks: Could not set cell value to %v", wid, fields[i].Value)

			}

		}

		if err == nil {

			fields = append(fields[:i], fields[i+1:]...)

			n--

			continue

		}

		// If any of the above checks fails, we roll back

		fields[i].Defined = false

		fields[i].Value = 0 // Let's reset but it is useless

		// Safety check to avoid deadlock on bad boards

		nop++

		if nop > 2*size*size {

			log.Printf("[%v]NewRandomTakuzu: Could not fill up board!", wid)

			// Givin up on this board

			return nil, errors.New("could not fill up board") // Try again

		}

	}

	var ptak *Takuzu

	var removed int

	// #2. Try to solve the current board; try to remove some cells if it fails

	// Initial empty cells count

	iecc := n

	for {

		// Current count of empty (i.e. undefined) cells

		ec := iecc + removed

		ecpc := ec * 100 / (size * size)

		if verbosity > 0 {

			log.Printf("[%v]NewRandomTakuzu: Empty cells: %d (%d%%)", wid, ec, ecpc)

		}

		if ecpc > maxRatio {

			if verbosity > 0 {

				log.Printf("[%v]NewRandomTakuzu: Too many empty cells (%d); giving up on this board", wid, ec)

			}

			break

		}

		var err error

		ptak, err = tak.ReduceBoard(easy, wid, buildBoardTimeout, reduceBoardTimeout)

		if err != nil && errors.Cause(err).Error() == "timeout" {

			break

		}

		if err == nil && ptak != nil {

			break

		}

		if verbosity > 0 {

			log.Printf("[%v]NewRandomTakuzu: Could not use this grid", wid)

		}

		inc := size * size / 150

		if inc == 0 {

			inc = 1

		}

		tak.removeRandomCell(inc)

		removed += inc

		if verbosity > 1 {

			log.Printf("[%v]NewRandomTakuzu: Removed %d numbers", wid, removed)

			if verbosity > 1 {

				tak.DumpBoard()

			}

		}

	}

	if ptak == nil {

		if verbosity > 0 {

			log.Printf("[%v]NewRandomTakuzu: Couldn't use this board, restarting from scratch...", wid)

		}

		return nil, errors.New("could not use current board") // Try again

	}

	return ptak, nil

}

// NewRandomTakuzu creates a new Takuzu board with a given size

func NewRandomTakuzu(size int, simple bool, wid string, buildBoardTimeout, reduceBoardTimeout time.Duration, minRatio, maxRatio int) (*Takuzu, error) {

	if size%2 != 0 {

		return nil, errors.New("board size should be an even value")

	}

	if size < 4 {

		return nil, errors.New("board size is too small")

	}

	// minRatio : percentage (1-100) of empty cells when creating a new board

	// If the board is wrong the cells will be removed until we reach maxRatio

	if minRatio < 40 {

		minRatio = 40

	}

	if minRatio > maxRatio {

		return nil, errors.New("minRatio/maxRatio incorrect")

	}

	if maxRatio > 99 {

		maxRatio = 99

	}

	buildOptions := buildTakuzuOptions{

		size:               size,

		minRatio:           minRatio,

		maxRatio:           maxRatio,

		simple:             simple,

		buildBoardTimeout:  buildBoardTimeout,

		reduceBoardTimeout: reduceBoardTimeout,

	}

	var takP *Takuzu

	for {

		var err error

		takP, err = newRandomTakuzu(wid, buildOptions)

		if err == nil {

			break

		}

	}

	return takP, nil

}

func (tak Takuzu) removeRandomCell(number int) {

	size := tak.Size

	fields := make([]*Cell, size*size)

	n := 0

	for l := range tak.Board {

		for c := range tak.Board[l] {

			if tak.Board[l][c].Defined {

				fields[n] = &tak.Board[l][c]

				n++

			}

		}

	}

	for i := 0; i < number; i++ {

		if n == 0 {

			return

		}

		fields[rand.Intn(n)].Defined = false

		fields = append(fields[:i], fields[i+1:]...)

		n--

	}

}