module Exercise03 where

import Text.Printf (printf)
import Data.List (intercalate, nub, (\\))
-- HA 3.1a) i
selectRow :: [[Int]] -> Int -> [Int]
selectRow xss i = xss !! i

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

-- 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 =  helper2 xss (helper xss i) i

calculateRoot :: [[Int]] -> Int
calculateRoot xss = intRoot (length xss)

helper :: [[Int]] -> Int -> [[Int]]
helper xss i = [selectRow xss j  | j <- [n..n + root - 1]] 
  where 
  root = calculateRoot xss
  n = div i root * root

helper2 :: [[Int]] -> [[Int]] -> Int -> [Int]
helper2 xss xs i = [x !! j | x <- xs ,j <- [n..n + root - 1]]
  where
  root = calculateRoot xss
  n = mod i root * root



-- HA 3.1b)
isValidSubsection :: [Int] -> Bool
isValidSubsection xs = length (nub xsWithoutZero) == length xsWithoutZero   
  where
  xsWithoutZero = filter (/= 0) xs

isValidSudoku :: [[Int]] -> Bool
isValidSudoku xss = and (validHelper xss)

validHelper :: [[Int]] -> [Bool]
validHelper xss = [isValidSubsection (selectRow xss i) && isValidSubsection (selectColumn xss i) && isValidSubsection (selectSquare xss i) | i <- [0..length xss - 1]]
-- HA 3.1c)
setCell :: [[Int]] -> (Int,Int) -> Int -> [[Int]]
setCell xss (j, k) x = do 
  if j == 0 && k == 0 then (x : drop 1 (selectRow xss 0)) : drop 1 xss 
  else if j == 0 && k /= 0 then  (take k (selectRow xss 0) ++ [x] ++ drop (k + 1) (selectRow xss 0)) : drop 1 xss
  else if j /= 0 && k == 0 then take j xss ++ (x : drop 1 (selectRow xss j)) : drop (j + 1) xss  
  else take j xss ++ (take k (selectRow xss j) ++ [x] ++ drop (k + 1) (selectRow xss j)) : drop (j + 1) xss
  

-- HA 3.1d)
{-WETT-}

solveSudoku :: [[Int]] -> [[Int]]
solveSudoku xss = 
  if not (isValidSudoku xss) then []
  else solve xss

solve :: [[Int]] -> [[Int]]
solve xss =
  let
    zeros = findZero xss
    posValues = possibleValues xss (head zeros)
    tryValues :: [Int] -> [[Int]]
    tryValues [] = []
    tryValues pos = 
      let
        modifiedSudoku = setCell xss (head zeros) (head pos)
        attempt = solve modifiedSudoku
        in if isValidSudoku attempt && not(null(attempt)) then attempt else tryValues (pos\\(take 1 pos))
    in if null zeros then xss else tryValues posValues
    
possibleValues :: [[Int]] -> (Int, Int) -> [Int]
possibleValues xss (x,y) = [i | i <- [1..length xss], i `notElem` selectRow xss x, i `notElem` selectColumn xss y, i `notElem` selectSquare xss (x - (mod x (intRoot(length xss))) + div y (intRoot(length xss)))] 

findZero :: [[Int]] -> [(Int,Int)]
findZero xss = nub( [(i,j) | xs <- xss, i <- [0..length xss - 1], j <- [0..length xss - 1], (selectRow xss i !! j) == 0])
{-TTEW-}

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)