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]
-- map f x with x as list -> f x1, f x2, fx3 ... 
selectColumn xss i = map (!!(i)) 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 =  [ xss!!(x_start + x)!!(y_start + y) | x <- [0 .. length_adjusted], y <- [0 .. length_adjusted] ] 
  where
    -- depends on the size of the sudoku
    rootVal = intRoot (length xss)

    -- indices start at 0
    length_adjusted = rootVal - 1

    -- corner start points
    -- y -> increases every rootVal Steps by 1 rootVal
    y_start = mod (i * rootVal) (length xss)
    -- y -> increases in mod rootVal group
    x_start = rootVal * div i rootVal

-- readable squars for test usage
testSudoku :: [[Int]]
testSudoku = [[1,1,1,2,2,2,3,3,3],
              [1,1,1,2,2,2,3,3,3],
              [1,1,1,2,2,2,3,3,3],
              [4,4,4,5,5,5,6,6,6],
              [4,4,4,5,5,5,6,6,6],
              [4,4,4,5,5,5,6,6,6],
              [7,7,7,8,8,8,9,9,9],
              [7,7,7,8,8,8,9,9,9],
              [7,7,7,8,8,8,9,9,9]]

testSudoku2 :: [[Int]]
testSudoku2 = [[1,2,3,4,5,6,7,8,9],
              [10,11,12,13,14,15,16,17,18],
              [19,20,21,22,23,24,25,26,27],
              [4,4,4,5,5,5,6,6,6],
              [4,4,4,5,5,5,6,6,6],
              [4,4,4,5,5,5,6,6,6],
              [7,7,7,8,8,8,9,9,9],
              [7,7,7,8,8,8,9,9,9],
              [7,7,7,8,8,8,9,9,9]]

testSudoku3 :: [[Int]]
testSudoku3 = [[0,0,0,0,0,0,0,6,0],
               [0,0,0,0,0,0,0,7,0],
               [0,0,0,0,0,0,0,0,0],
               [0,4,0,0,0,0,0,0,0],
               [0,0,0,0,2,0,0,0,0],
               [0,0,0,0,0,0,0,0,0],
               [8,0,0,0,0,4,1,0,0],
               [0,0,0,0,0,0,0,0,0],
               [8,0,0,0,2,0,6,0,0]]


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

isValidSudoku :: [[Int]] -> Bool
isValidSudoku xss = and([isValidSubsection (selectRow xss (b-1)) | b <- [1..len]] ++ [isValidSubsection (selectColumn xss (b-1)) | b <- [1..len]] ++ [isValidSubsection (selectSquare xss (b -1)) | b <- [1..len]])
  where
    len = length xss

-- HA 3.1c)
-- Helper method to set x at position i
replaceElement :: [Int] -> Int -> Int -> [Int]
replaceElement xs x i = take i xs ++ [x] ++ drop (i + 1) xs

setCell :: [[Int]] -> (Int,Int) -> Int -> [[Int]]
setCell xss (j, k) x = take j xss ++ [replaceElement (xss!!j) x k] ++ drop (j + 1) xss

-- HA 3.1d)
{-WETT-}

-- yield solutions, slow and ugly 
generateSolutions :: [[Int]] -> [[[Int]]]
generateSolutions xss = if isFinished xss then [xss] else if not (isValidSudoku xss) then [] else concatMap generateSolutions (stepFurther xss)
  where
    -- doing another step filling burte force style with 1 to max num and checking if valid num
    stepFurther :: [[Int]] -> [[[Int]]]
    stepFurther xss = [setCell xss (proceedToEmpty xss) v | v <- [1..length xss], isValidSudoku (setCell xss (proceedToEmpty xss) v)]
      where
        -- get next cell to work on
        proceedToEmpty :: [[Int]] -> (Int, Int)
        proceedToEmpty xss = head [(i, j) | i <- [0.. (length xss - 1)], j <- [0.. (length xss - 1)], (xss!!i)!!j == 0]

    -- check if all spaces are filled
    isFinished :: [[Int]] -> Bool
    isFinished xss = null [b | b <- xss, 0 `elem` b]

{- 
  search for 0 -> try to place numbers (best: just possible or burteforce all .__. )
  check if valid
    TRUE: continue on this set
    FALSE: path not valid set it to null
-}

solveSudoku :: [[Int]] -> [[Int]]
solveSudoku xss = if null solution then [] else head solution where solution = generateSolutions xss

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