module Exercise03 where

import Text.Printf (printf)
import Data.List (sort, intercalate)

-- HA 3.1a) i
selectRow :: [[Int]] -> Int -> [Int]
selectRow [] _          = []
selectRow ((x:xs):_) 0  = x:xs
selectRow (_:xs) i      = selectRow xs (i-1)

-- HA 3.1a) ii
selectColumn :: [[Int]] -> Int -> [Int]
selectColumn xss i = [xs !! i | xs <- xss, length xs > i]

-- HA 3.1a) iii
intRoot :: Int -> Int
intRoot = floor . sqrt . fromIntegral

--return numbers in square as a list. squares are numbered  from left to right and top to bottom
--e.g. :
--[0,1,2]
--[3,4,5]
--[6,7,8]
selectSquare :: [[Int]] -> Int -> [Int]
selectSquare xss i 
  | i < length xss && i>=0 =  [ xss !! x !! y | x <- [a..c], y <- [b..d]]
  | otherwise              = []
      where (a, b) = firstIndeces (length xss) i
            (c, d) = lastIndeces (length xss) i

squareFromIndex :: [[Int]] -> (Int, Int) -> Int
squareFromIndex xss (j, k) = (j `div` x) * x + (k `div` x)
  where x = intRoot (length xss)
  

firstIndeces :: Int -> Int -> (Int, Int)
firstIndeces sudokuSize squareNumber = ((squareNumber `div` x) * x, (squareNumber `mod` x) * x) 
  where x = intRoot sudokuSize

lastIndeces :: Int -> Int -> (Int, Int)
lastIndeces sudokuSize squareNumber = (a+x-1, b+x-1) 
  where (a, b) = firstIndeces sudokuSize squareNumber
        x = intRoot sudokuSize

-- HA 3.1b)
isValidSubsection :: [Int] -> Bool
isValidSubsection xs = isStrictAscending (sort [x | x <- xs, x/=0] )

isStrictAscending :: Ord a => [a] -> Bool
isStrictAscending []  = True
isStrictAscending [_] = True
isStrictAscending (x:y:ys) = x < y && isStrictAscending (y:ys)

isValidSudoku :: [[Int]] -> Bool
isValidSudoku xss = and [isValidSubsection row && length row == size && isValidSubsection(selectColumn xss a) && isValidSubsection(selectSquare xss a) | a <- [0..size-1], let row = selectRow xss a]
  where size = length xss

-- HA 3.1c)
setCell :: [[Int]] -> (Int,Int) -> Int -> [[Int]]
setCell xss (j, k) x  
  | j<s && k<s =  filter (not . null) ([selectRow xss i | i <- [0..j-1]] ++
                  [[row !! i | let row = selectRow xss j, i <- [0..k-1]] ++ [x] ++ [row !! i |let row = selectRow xss j, i <- [k+1..s-1]]] ++ 
                  [selectRow xss i | i <- [j+1..s]])
  | otherwise  = xss
  where s = length xss

-- HA 3.1d)
{-WETT-}
solveSudoku :: [[Int]] -> [[Int]]
solveSudoku []  = []
solveSudoku xss 
  | isValidSudoku xss = solveCell xss (nextCell xss (0,0))
  | otherwise         = []

solveCell :: [[Int]] -> (Int, Int) -> [[Int]]
solveCell xss (j, k)
  | j<0 || k<0 || j>=size || k>=size = xss
  | null results = []
  | otherwise    = head results
  where size = length xss
        invalidNumbers = usedNumbers xss (j,k)
        results = [finalSudoku | 
          x <- [1..size], 
          x `notElem` invalidNumbers, 
          let newSudoku =  setCell xss (j, k) x, 
          let newCell = nextCell newSudoku (j,k), 
          let finalSudoku = if newCell /= (-1,-1) then solveCell newSudoku newCell else newSudoku, 
          finalSudoku /= []]


--for a cell (j, k) this gives all numbers that are already used in the row, column and square where (j, k) is a part of
usedNumbers :: [[Int]] -> (Int, Int) -> [Int]
usedNumbers xss (j, k) = [x | x <- selectRow xss j ++ selectColumn xss k ++ selectSquare xss (squareFromIndex xss (j, k)), x /= 0]

nextCell :: [[Int]] -> (Int, Int) -> (Int, Int)
nextCell xss (j, k)
  | null i = (-1, -1)
  | otherwise = (head i, head [a | let row = selectRow xss (head i), a <- [0..s-1], head i>j || a>=k, row !! a == 0])
  where s = length xss
        i = [i | i <- [j..s-1], let z = selectRow xss i, 0 `elem` z]
{-TTEW-}


sudokuOne :: [[Int]]
sudokuOne = [[5,3,4,6,7,8,9,1,2],[6,7,2,1,9,5,3,4,8],[1,9,8,3,4,2,5,6,7],[8,5,9,7,6,1,4,2,3],[4,2,6,8,5,3,7,9,1],[7,1,3,9,2,4,8,5,6],[9,6,1,5,3,7,2,8,4],[2,8,7,4,1,9,6,3,5],[3,4,5,2,8,6,1,7,0]]

hardSudoku :: [[Int]]
hardSudoku = [[8,0,0,0,0,0,0,0,0],
              [0,0,3,6,0,0,0,0,0],
              [0,7,0,0,9,0,2,0,0],
              [0,5,0,0,0,7,0,0,0],
              [0,0,0,0,4,5,7,0,0],
              [0,0,0,1,0,0,0,3,0],
              [0,0,1,0,0,0,0,6,8],
              [0,0,8,5,0,0,0,1,0],
              [0,9,0,0,0,0,4,0,0]]

-- Utility method to show a sudoku
-- show sudoku with
-- >>> putStr (showSudoku sudoku)
showSudoku :: [[Int]] -> String
showSudoku xss = unlines $ intercalate [showDivider] $ chunksOf squareSize $ map showRow xss
  where
    size = length xss
    squareSize = intRoot size 
    numberSize = size `div` 10 + 1

    showRowSection xs = unwords $ map (printf ("%0" ++ show numberSize ++ "d")) xs
    showRow xs = intercalate "|" $ map showRowSection $ chunksOf squareSize xs
    showDivider = intercalate "+" $ replicate squareSize $ replicate ((numberSize + 1) * squareSize - 1) '-'

    chunksOf :: Int -> [e] -> [[e]]
    chunksOf i [] = []
    chunksOf i ls = take i ls : chunksOf i (drop i ls)