module Exercise03 where

import Text.Printf (printf)
import Data.List (intercalate, transpose, nubBy, intersect)

-- HA 3.1a) i
selectRow :: [[Int]] -> Int -> [Int]
selectRow xss i = xss !! i

-- HA 3.1a) ii
selectColumn :: [[Int]] -> Int -> [Int]
selectColumn xss i = transpose xss !! 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]
-- let m = [[8, 9, 6, 7, 5, 2, 4, 1, 3], [5, 2, 3, 6, 1, 4, 9, 8, 7], [4, 7,1,8,9,3,2,6,5],[9,5,4,3,6,7,8,2,1],[3,1,8,2,4,5,7,9,6],[7,6,2,1,8,9,5,3,4],[6,8,9,5,7,1,3,4,2],[2,4,7,9,3,6,1,5,8],[1,3,5,4,2,8,6,7,9]]
-- let m = [[3,1,0,0],[0,0,0,0],[0,0,0,4],[4,0,0,0]]
-- let m = [[0,0,0,0,1,0,0,5,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,6,0,0,0,0,0,0,0],[6,0,0,0,0,0,0,0,0]]
-- let m = [[0,0,0,0],[1,3,0,0],[0,0,2,3],[0,0,0,0]]
-- let m = [[0,0,0,0],[3,0,0,0],[0,0,0,0],[0,4,0,0]]
-- let m = [[2,4,0,0],[1,3,4,2],[4,1,2,3],[3,2,0,0]]
selectSquare :: [[Int]] -> Int -> [Int]
selectSquare xss i = concat [drop startColumn . take endColumn $ (xss !! j) | j <- [0..length xss - 1], j >= startRow && j <= endRow]
  where 
    rootN = intRoot (length xss)
    startRow = i `div` rootN * rootN
    endRow = startRow + rootN - 1
    startColumn = i `mod` rootN * rootN
    endColumn = startColumn + rootN

-- HA 3.1b)
isValidSubsection :: [Int] -> Bool
isValidSubsection xs = xs == nubBy (\x y -> x > 0 && x == y) xs

isValidSudoku :: [[Int]] -> Bool
isValidSudoku xss = and [isValidSubsection (selectRow xss n) && isValidSubsection (selectColumn xss n) | n <- nl] && and [isValidSubsection (selectSquare xss n) | n <- nl]
  where 
    nl = [0..length xss - 1]

-- HA 3.1c)
setCell :: [[Int]] -> (Int,Int) -> Int -> [[Int]]
setCell xss (j, k) x = [replaceInRow (xss !! i) i (j, k) x | i <- nl]
  where 
    nl = [0..length xss - 1]
    replaceInRow xs i (j, k) x
      | i /= j = xs
      | otherwise = let (z,_:ys) = splitAt k xs in z ++ x : ys

getCell :: [[Int]] -> (Int, Int) -> Int
getCell xss (r, c) = selectRow xss r !! c

-- HA 3.1d)
{-WETT-}
solveSudoku :: [[Int]] -> [[Int]]
solveSudoku xss = solveNext xss 0

solveNext :: [[Int]] -> Int -> [[Int]]
solveNext xss i
  | not (isValidSudoku xss) = [] -- Nicht valide
  | i == n * n = xss -- Am Ende angelangt (Alle Zellen durchlaufen)
  | getCell xss (rowI, columnI) /= 0 = solveNext xss (i + 1) -- Zelle ist nicht 0 -> Nächste Zelle lösen
  | otherwise = let ysss = [yss | yss <- [solveNext (setCell xss (rowI, columnI) x) (i + 1) | x <- poss], not (null yss)] in
      if null ysss then [] else head ysss
  where
    n = length xss
    poss = getPossibilities xss (rowI, columnI)
    rowI = i `div` n
    columnI = i `mod` n

getPossibilities :: [[Int]] -> (Int, Int) -> [Int]
getPossibilities xss (r, c)
  | getCell xss (r, c) /= 0 = []
  | otherwise = getMissing (selectRow xss r) `intersect` getMissing (selectColumn xss c) `intersect` getMissing (selectSquare xss getSquare)
  where
    rootN = intRoot (length xss)
    getMissing xs = [a | a <- [1..length xss], a `notElem` xs]
    getSquare = r `div` rootN * rootN + c `div` rootN

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