// TypeScript
function isValidSudoku(board: string[][]): boolean {
  // examine the rows
  for (let r = 0; r < 9; r++) {
    const set = new Set<string>();
    for (let c = 0; c < 9; c++) {
      const cell = board[r][c];
      if (cell === '.') {
        continue;
      }
      if (set.has(cell)) {
        return false;
      }
      set.add(cell);
    }
  }

  // examine the cols
  for (let c = 0; c < 9; c++) {
    const set = new Set<string>();
    for (let r = 0; r < 9; r++) {
      const cell = board[r][c];
      if (cell === '.') {
        continue;
      }
      if (set.has(cell)) {
        return false;
      }
      set.add(cell);
    }
  }

  // examine the subgrids
  for (let k = 0; k < 9; k++) {
    const set = new Set<string>();
    for (let i = 0; i < 3; i++) {
      for (let j = 0; j < 3; j++) {
        const r = (Math.floor(k / 3) * 3) + i;
        const c = ((k % 3) * 3)+ j;
        const cell = board[r][c];
        if (cell === '.') {
          continue;
        }
        if (set.has(cell)) {
          return false;
        }
        set.add(cell);
      }
    }
  }

  return true;
};

function isValidSudoku2(board: string[][]): boolean {
  const rows = Array(9).fill(null).map(() => new Set<string>);
  const cols = Array(9).fill(null).map(() => new Set<string>);
  const subgrids = Array(9).fill(null).map(() => new Set<string>);

  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      const cell = board[r][c];
      if (cell === '.') {
        continue;
      }

      const idx = Math.floor(r / 3) * 3 + Math.floor(c / 3);
      if (rows[r].has(cell) || cols[c].has(cell) || subgrids[idx].has(cell)) {
        return false;
      }

      rows[r].add(cell);
      cols[c].add(cell);
      subgrids[idx].add(cell);
    }
  }

  return true;
}

-- Haskell
isValidSudoku :: [[Char]] -> Bool
isValidSudoku board =
  (all isValid board)
  && (all isValid (transpose board))
  && (all isValid (mapSubgrids board))

isValid :: [Char] -> Bool
isValid cs =
  let
    digits = filter (\c -> c /= '.') cs
  in
    length digits == length (distinct digits)

distinct :: Eq a => [a] -> [a]
distinct [] = []
distinct (x:xs) = x : distinct (filter (/= x) xs)

transpose :: [[Char]] -> [[Char]]
transpose [] = []
transpose ([]:_) = []
transpose board = map head board : transpose (map tail board)

mapSubgrids :: [[Char]] -> [[Char]]
mapSubgrids board = [mapSubgrid board r c | r <- [0, 3, 6], c <- [0, 3, 6]]

mapSubgrid :: [[Char]] -> Int -> Int -> [Char]
mapSubgrid board r c = concat [take 3 (drop c (board !! (r + i))) | i <- [0..2]]

// Rust
impl Solution {
    pub fn is_valid_sudoku(board: Vec<Vec<char>>) -> bool {
        let mut rows    = [[false; 9]; 9];
        let mut columns = [[false; 9]; 9];
        let mut boxes   = [[false; 9]; 9];

        for i in 0..9 {
            for j in 0..9 {
                if let Some(d) = board[i][j].to_digit(10) {
                    let d = (d - 1) as usize;
                    let box_id = (i / 3) * 3 + j / 3;
                    if rows[i][d] || columns[j][d] || boxes[box_id][d] {
                        return false;
                    }

                    rows[i][d] = true;
                    columns[j][d] = true;
                    boxes[box_id][d] = true;
                }
            }
        }

        true
    }
}

// --- --- --- ---

impl Solution {
    pub fn is_valid_sudoku(board: Vec<Vec<char>>) -> bool {
        use std::collections::HashSet;

        for row in 0..9 {
            let mut set = HashSet::new();
            for col in 0..9 {
                let cell = board[row][col];
                if cell == '.' {
                    continue;
                }
                if set.contains(&cell) {
                    return false;
                }
                set.insert(cell);
            }
        }

        for col in 0..9 {
            let mut set = HashSet::new();
            for row in 0..9 {
                let cell = board[row][col];
                if cell == '.' {
                    continue;
                }
                if set.contains(&cell) {
                    return false;
                }
                set.insert(cell);
            }
        }

        for k in 0..9 {
            let mut set = HashSet::new();
            for i in 0..3 {
                for j in 0..3 {
                    let row = (k / 3) * 3 + i;
                    let col = (k % 3) * 3 + j;
                    let cell = board[row][col];
                    if cell == '.' {
                        continue;
                    }
                    if set.contains(&cell) {
                        return false;
                    }
                    set.insert(cell);
                }
            }
        }

        true
    }
}

// --- --- --- ---

impl Solution {
    pub fn is_valid_sudoku(board: Vec<Vec<char>>) -> bool {
        use std::collections::HashSet;

        let mut rows: Vec<HashSet<char>> = (0..9).map(|_| HashSet::new()).collect();
        let mut cols: Vec<HashSet<char>> = (0..9).map(|_| HashSet::new()).collect();
        let mut subgrids: Vec<HashSet<char>> = (0..9).map(|_| HashSet::new()).collect();

        for r in 0..9 {
            for c in 0..9 {
                let cell = board[r][c];
                if cell == '.' {
                    continue;
                }
                let idx = (r / 3) * 3 + c / 3;
                if rows[r].contains(&cell) || cols[c].contains(&cell) || subgrids[idx].contains(&cell) {
                    return false;
                }

                rows[r].insert(cell);
                cols[c].insert(cell);
                subgrids[idx].insert(cell);
            }
        }

        true
    }
}