<commit_before>module Sudoku where

import Test.QuickCheck 
import Test.Hspec

import Data.Array
import Data.Char (isDigit)
import Data.Maybe
import Data.List

data Cell = Unknown [Int]
          | Known Int
            deriving (Show,Eq)

knownValue :: Cell -> Maybe Int
knownValue (Known n) = Just n
knownValue _         = Nothing

type Grid = Array (Int,Int) Cell

buildGrid :: String -> Grid
buildGrid s = listArray bounds (map toCell s)
  where
    bounds :: ((Int,Int),(Int,Int))
    bounds = ((0,0),(8,8))

at :: Grid -> (Int,Int) -> Cell
at g p = g ! p

toCell :: Char -> Cell
toCell c
  | isDigit c = Known (read [c])
  | otherwise = Unknown [1..9]

row :: Grid -> Int -> [Cell]
row g r = map snd (filter (\((x,y),e) -> x == r) (assocs g))

col :: Grid -> Int -> [Cell]
col g c = map snd (filter (\((x,y),e) -> y == c) (assocs g))

subgrid :: Grid -> (Int,Int) -> [Cell]
subgrid g (r,c) = map snd (filter isInSubGrid (assocs g))
  where
    isInSubGrid ((x,y),_) = r `div` 3 == x `div` 3 &&
                            c `div` 3 == y `div` 3 

stepCell :: Grid -> (Int,Int) -> Cell
stepCell g p@(r,c) = stepCell' (g ! p) surroundingCells
  where
    surroundingCells = known $ row g r ++ col g c ++ subgrid g p
    
stepCell' :: Cell -> [Int] -> Cell
stepCell' (Known x) _     = Known x
stepCell' (Unknown ys) xs
  | length rest == 1  = Known (head rest)
  | otherwise         = Unknown rest
  where
    rest = ys \\ xs

stepGrid :: Grid -> Grid
stepGrid grid = array bounds (map (\(x,e) -> (x,stepCell grid x)) (assocs grid))
  where
    bounds = ((0,0),(8,8))

solve :: Grid -> Grid
solve = undefined

known :: [Cell] -> [Int]
known = mapMaybe knownValue

solved :: Grid -> Bool
solved g = all isKnown (elems g)
  where
    isKnown (Known _) = True
    isKnown _         = False

veryEasy :: String
veryEasy = "6185___2_" ++
           "_5__17_63" ++
           "__326__95" ++
           "8_1_5_74_" ++
           "5__6_13_9" ++
           "_9782_5__" ++<commit_msg>scaffolding<commit_after>module Sudoku where

import Test.QuickCheck 
import Test.Hspec

import Data.Array
import Data.Char (isDigit)
import Data.Maybe
import Data.List

import Data.List.Split

data Cell = Unknown [Int]
          | Known Int
            deriving (Eq)

instance Show Cell where
  show (Known n)   = show n
  show (Unknown _) = "_"

knownValue :: Cell -> Maybe Int
knownValue (Known n) = Just n
knownValue _         = Nothing

type Grid = Array (Int,Int) Cell

buildGrid :: String -> Grid
buildGrid s = listArray bounds (map toCell s)
  where
    bounds :: ((Int,Int),(Int,Int))
    bounds = ((0,0),(8,8))

display :: Grid -> String
display g = unlines $ chunksOf 9 $ concatMap show (elems g)

at :: Grid -> (Int,Int) -> Cell
at g p = g ! p

toCell :: Char -> Cell
toCell c
  | isDigit c = Known (read [c])
  | otherwise = Unknown [1..9]

row :: Grid -> Int -> [Cell]
row g r = map snd (filter (\((x,y),e) -> x == r) (assocs g))

col :: Grid -> Int -> [Cell]
col g c = map snd (filter (\((x,y),e) -> y == c) (assocs g))

subgrid :: Grid -> (Int,Int) -> [Cell]
subgrid g (r,c) = map snd (filter isInSubGrid (assocs g))
  where
    isInSubGrid ((x,y),_) = r `div` 3 == x `div` 3 &&
                            c `div` 3 == y `div` 3 

stepCell :: Grid -> (Int,Int) -> Cell
stepCell g p@(r,c) = stepCell' (g ! p) surroundingCells
  where
    surroundingCells = known $ row g r ++ col g c ++ subgrid g p
    
stepCell' :: Cell -> [Int] -> Cell
stepCell' (Known x) _     = Known x
stepCell' (Unknown ys) xs
  | length rest == 1  = Known (head rest)
  | otherwise         = Unknown rest
  where
    rest = ys \\ xs

stepGrid :: Grid -> Grid
stepGrid grid = array bounds (map (\(x,e) -> (x,stepCell grid x)) (assocs grid))
  where
    bounds = ((0,0),(8,8))

solve :: Grid -> Grid
solve g = head $ dropWhile (not . solved) (iterate stepGrid g)

known :: [Cell] -> [Int]
known = mapMaybe knownValue

solved :: Grid -> Bool
solved g = all isKnown (elems g)
  where
    isKnown (Known _) = True
    isKnown _         = False

veryEasy :: String
veryEasy = "6185___2_" ++
           "_5__17_63" ++
           "__326__95" ++
           "8_1_5_74_" ++
           "5__6_13_9" ++
           "_9782_5__" ++
{'fraction_non_alphanumeric': 0.15399330463892874, 'fraction_numerical': 0.021759923481587756, 'mean_word_length': 2.488740617180984, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 48, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '183181', 'n_tokens_mistral': 1577, 'n_tokens_neox': 1487, 'n_words': 504}