module Exercise03 where

import Text.Printf (printf)
import Data.List (intercalate,nub)
--import Debug.Trace (trace)

-- 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 = [x !! z| x <- [xss !! y | y <- indices_y] , z <- indices_x]
  where size_ = (intRoot $ length xss) 
        indices_x = [(mod i size_) * size_ .. ((mod i size_) * size_) + size_ - 1]
        indices_y = [(div i size_) * size_ .. ((div i size_) * size_) + size_ - 1]

-- HA 3.1b)s
isValidSubsection :: [Int] -> Bool
isValidSubsection xs = length liste == length (nub liste) where liste = filter (\n -> n > 0) xs

isValidSudoku :: [[Int]] -> Bool
isValidSudoku [] = False
isValidSudoku xss = let indices_ = [0 .. length xss -1] in and $ [isValidSubsection ( selectRow xss i)| i <- indices_ ]
                    ++ [isValidSubsection ( selectColumn xss i)| i <- indices_ ] 
                    ++ [isValidSubsection ( selectSquare xss i)| i <- indices_ ]

-- HA 3.1c)
setCell :: [[Int]] -> (Int,Int) -> Int -> [[Int]]
setCell xss (j, k) x = chunkOf (length xss) (y ++ [x] ++ zs)
  where (y,_:zs) = splitAt (j* (length xss) + k) (concat xss)

chunkOf :: Int -> [Int] -> [[Int]]
chunkOf _ [] = []
chunkOf n xs = ys : chunkOf n zs where (ys, zs) = splitAt n xs

-- HA 3.1d) 
{-WETT-}  
solveSudoku :: [[Int]] -> [[Int]]
solveSudoku xss = if isValidSudoku xss then solveSudoku_ xss (findEmptyCells xss) 1 else []

solveSudoku_ :: [[Int]] -> [(Int,Int)] -> Int -> [[Int]]
--solveSudoku_ xss _ i | trace (show i ++ "\n" ++ showSudoku xss) False = undefined
solveSudoku_ xss [] index = xss
solveSudoku_ xss ((x,y) : ys) index = if index > (length xss) then [] else if isValidSudoku sudo_ && not (null sudo) 
  then sudo else solveSudoku_ xss ((x,y):ys) (index + 1)
  where sudo = solveSudoku_ sudo_ ys 1
        sudo_ = setCell xss (y,x) index
{-TTEW-}

getPossibleNumbers :: [Int] -> [Int]
getPossibleNumbers xs = [ x | x <- xs, not (x `elem` [1..9])] 

findEmptyCells :: [[Int]] -> [(Int, Int)]
findEmptyCells xss = [ (x,y) | y <- shortlist , x <- shortlist, (getCell xss (x,y)) == 0 ] where shortlist = [0..(length xss - 1)] 

-- gets value of cell at certain index
getCell :: [[Int]] -> (Int, Int) -> Int
getCell xss (x,y) = (xss !! y) !! x

--recursiveSolve :: [[Int]] -> (Bool, [[Int]])
--recursiveSolve xss = where possibilities = []

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]]

harderSudoku :: [[Int]]
harderSudoku = 
              [[0,2,3,4],
               [4,3,0,1],
               [3,0,4,2],
               [0,4,1,3]]

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

-- 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)