// Cuenta las islas de un mapa: grupos de # unidos por arriba, abajo, izquierda o derecha.
#include <stdio.h>

#define ROWS 6
#define COLS 14

// Hunde toda la isla que contiene a (row, col): cada # visitado pasa a ser ~.
void sink(char map[][COLS + 1], int row, int col) {
    if (row < 0 || row >= ROWS || col < 0 || col >= COLS) {
        return;
    }
    if (map[row][col] != '#') {
        return;
    }
    map[row][col] = '~';
    sink(map, row - 1, col);
    sink(map, row + 1, col);
    sink(map, row, col - 1);
    sink(map, row, col + 1);
}

// Cuidado: destruye el mapa que recibe. Al terminar, ya no queda ningún #.
int count_islands(char map[][COLS + 1]) {
    int islands = 0;
    for (int row = 0; row < ROWS; row++) {
        for (int col = 0; col < COLS; col++) {
            if (map[row][col] == '#') {
                islands++;
                sink(map, row, col);
            }
        }
    }
    return islands;
}

int main(void) {
    char map[ROWS][COLS + 1] = {
        "##......#.....",
        "##.....###..#.",
        "........#...#.",
        "...#........#.",
        "....#...##....",
        ".........##...",
    };

    for (int row = 0; row < ROWS; row++) {
        printf("%s\n", map[row]);
    }
    printf("islas: %d\n", count_islands(map));
    return 0;
}

// Flood fill recursivo sobre una cuadrícula de N x N vacía: mide cuántos marcos se apilan.
// Uso: deep_fill N
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int size;
    char *cells;
    long long painted;
    long long depth;
    long long max_depth;
} Canvas;

void fill(Canvas *canvas, int row, int col) {
    canvas->depth++;
    if (canvas->depth > canvas->max_depth) {
        canvas->max_depth = canvas->depth;
    }
    int size = canvas->size;
    if (row >= 0 && row < size && col >= 0 && col < size && canvas->cells[row * size + col] == 0) {
        canvas->cells[row * size + col] = 1;
        canvas->painted++;
        fill(canvas, row - 1, col);
        fill(canvas, row + 1, col);
        fill(canvas, row, col - 1);
        fill(canvas, row, col + 1);
    }
    canvas->depth--;
}

int main(int argc, char *argv[]) {
    int size = 0;
    char extra = 0;
    if (argc != 2 || sscanf(argv[1], "%5d%c", &size, &extra) != 1 || size < 1) {
        printf("uso: deep_fill N, con N de 1 a 99999\n");
        return 1;
    }

    Canvas canvas = {size, calloc((size_t) size * size, 1), 0, 0, 0};
    if (canvas.cells == NULL) {
        printf("no hay memoria\n");
        return 1;
    }

    fill(&canvas, 0, 0);
    printf("N = %d: %lld celdas pintadas, %lld marcos apilados como máximo\n",
           size, canvas.painted, canvas.max_depth);
    free(canvas.cells);
    return 0;
}

// Fibonacci recursivo que cuenta sus llamadas. El contador llega por puntero: no hay globales.
#include <stdio.h>

long long fib(int n, long long *calls) {
    (*calls)++;
    if (n < 2) {
        return n;
    }
    return fib(n - 1, calls) + fib(n - 2, calls);
}

int main(void) {
    const int sizes[] = {1, 2, 3, 4, 5, 10, 20, 30, 35, 36, 37, 40};
    int count = (int) (sizeof(sizes) / sizeof(sizes[0]));

    printf("%4s %12s %12s\n", "n", "fib(n)", "llamadas");
    for (int i = 0; i < count; i++) {
        long long calls = 0;
        long long value = fib(sizes[i], &calls);
        printf("%4d %12lld %12lld\n", sizes[i], value, calls);
    }
    return 0;
}

// Fibonacci con memoización: compara las llamadas con y sin la tabla de resultados.
#include <stdio.h>
#include <stdlib.h>

#define NOT_KNOWN (-1)

long long fib(int n, long long *calls) {
    (*calls)++;
    if (n < 2) {
        return n;
    }
    return fib(n - 1, calls) + fib(n - 2, calls);
}

// memo[n] guarda fib(n), o NOT_KNOWN si todavía no se calculó.
long long fib_memo(int n, long long memo[], long long *calls) {
    (*calls)++;
    if (n < 2) {
        return n;
    }
    if (memo[n] != NOT_KNOWN) {
        return memo[n];
    }
    memo[n] = fib_memo(n - 1, memo, calls) + fib_memo(n - 2, memo, calls);
    return memo[n];
}

// Calcula fib(n) con una tabla nueva. Devuelve -1 si no hay memoria.
long long fib_with_table(int n, long long *calls) {
    long long *memo = malloc((n + 1) * sizeof(long long));
    if (memo == NULL) {
        return -1;
    }
    for (int i = 0; i <= n; i++) {
        memo[i] = NOT_KNOWN;
    }
    long long value = fib_memo(n, memo, calls);
    free(memo);
    return value;
}

int main(void) {
    const int sizes[] = {5, 10, 20, 30, 35};
    int count = (int) (sizeof(sizes) / sizeof(sizes[0]));

    printf("%4s %12s %12s %12s\n", "n", "fib(n)", "sin tabla", "con tabla");
    for (int i = 0; i < count; i++) {
        long long plain_calls = 0;
        long long memo_calls = 0;
        long long value = fib(sizes[i], &plain_calls);
        if (fib_with_table(sizes[i], &memo_calls) != value) {
            printf("no hay memoria o los resultados no coinciden\n");
            return 1;
        }
        printf("%4d %12lld %12lld %12lld\n", sizes[i], value, plain_calls, memo_calls);
    }

    long long calls = 0;
    long long value = fib_with_table(90, &calls);
    if (value < 0) {
        printf("no hay memoria\n");
        return 1;
    }
    printf("fib(90) = %lld, con %lld llamadas\n", value, calls);
    return 0;
}

// Escribe el árbol de llamadas de fib: cada nivel de sangría es un marco más en la pila.
#include <stdio.h>

int fib(int n, int depth) {
    printf("%*sfib(%d)\n", depth * 4, "", n);
    if (n < 2) {
        return n;
    }
    return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);
}

int main(void) {
    int value = fib(4, 0);
    printf("resultado: %d\n", value);
    return 0;
}

// El mismo flood fill de deep_fill.c, sin recursión: las celdas pendientes van en una pila propia.
// Uso: fill_stack N
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int row;
    int col;
} Cell;

// Pinta (row, col) y la apila, si está dentro y sin pintar. Cada celda se apila una sola vez,
// así que la pila nunca pasa de size * size celdas.
void push_if_free(char *cells, int size, Cell *stack, long long *top, int row, int col) {
    if (row >= 0 && row < size && col >= 0 && col < size && cells[row * size + col] == 0) {
        cells[row * size + col] = 1;
        stack[*top].row = row;
        stack[*top].col = col;
        (*top)++;
    }
}

int main(int argc, char *argv[]) {
    int size = 0;
    char extra = 0;
    if (argc != 2 || sscanf(argv[1], "%5d%c", &size, &extra) != 1 || size < 1) {
        printf("uso: fill_stack N, con N de 1 a 99999\n");
        return 1;
    }

    size_t total = (size_t) size * size;
    char *cells = calloc(total, 1);
    Cell *stack = malloc(total * sizeof(Cell));
    if (cells == NULL || stack == NULL) {
        printf("no hay memoria\n");
        free(cells);
        free(stack);
        return 1;
    }

    long long top = 0;
    long long max_top = 0;
    long long painted = 0;
    push_if_free(cells, size, stack, &top, 0, 0);
    while (top > 0) {
        if (top > max_top) {
            max_top = top;
        }
        top--;
        Cell cell = stack[top];
        painted++;
        push_if_free(cells, size, stack, &top, cell.row - 1, cell.col);
        push_if_free(cells, size, stack, &top, cell.row + 1, cell.col);
        push_if_free(cells, size, stack, &top, cell.row, cell.col - 1);
        push_if_free(cells, size, stack, &top, cell.row, cell.col + 1);
    }

    printf("N = %d: %lld celdas pintadas, %lld pendientes como máximo\n", size, painted, max_top);
    free(cells);
    free(stack);
    return 0;
}

// El flood fill de una cuadrícula pequeña, con un rastro de cada llamada que pinta.
#include <stdio.h>

#define ROWS 3
#define COLS 3

typedef struct {
    int calls;
    int painted;
} Tally;

void fill(char grid[][COLS + 1], int row, int col, int depth, Tally *tally) {
    tally->calls++;
    if (row < 0 || row >= ROWS || col < 0 || col >= COLS) {
        return;
    }
    if (grid[row][col] != '.') {
        return;
    }
    grid[row][col] = 'o';
    tally->painted++;
    printf("%*spinta (%d, %d)\n", depth * 2, "", row, col);
    fill(grid, row - 1, col, depth + 1, tally);
    fill(grid, row + 1, col, depth + 1, tally);
    fill(grid, row, col - 1, depth + 1, tally);
    fill(grid, row, col + 1, depth + 1, tally);
}

int main(void) {
    char grid[ROWS][COLS + 1] = {
        "..#",
        ".##",
        "..#",
    };
    Tally tally = {0, 0};

    fill(grid, 0, 1, 0, &tally);
    for (int row = 0; row < ROWS; row++) {
        printf("%s\n", grid[row]);
    }
    printf("%d celdas pintadas, %d llamadas\n", tally.painted, tally.calls);
    return 0;
}

// Flood fill sobre una cuadrícula de caracteres: se pinta la región que contiene una celda.
#include <stdio.h>

#define ROWS 6
#define COLS 12

void print_grid(char grid[][COLS + 1]) {
    for (int row = 0; row < ROWS; row++) {
        printf("%s\n", grid[row]);
    }
}

// Pinta con new_mark la región de celdas old_mark que contiene a (row, col).
// Exige: new_mark != old_mark.
void fill(char grid[][COLS + 1], int row, int col, char old_mark, char new_mark) {
    if (row < 0 || row >= ROWS || col < 0 || col >= COLS) {
        return;
    }
    if (grid[row][col] != old_mark) {
        return;
    }
    grid[row][col] = new_mark;
    fill(grid, row - 1, col, old_mark, new_mark);
    fill(grid, row + 1, col, old_mark, new_mark);
    fill(grid, row, col - 1, old_mark, new_mark);
    fill(grid, row, col + 1, old_mark, new_mark);
}

int main(void) {
    char grid[ROWS][COLS + 1] = {
        "....#.......",
        "....#..###..",
        "#####..#.#..",
        "..#....###..",
        "..#.........",
        "..#.........",
    };

    print_grid(grid);
    printf("\n");
    fill(grid, 4, 8, '.', 'o');
    print_grid(grid);
    return 0;
}

// Busca un camino en un laberinto: # es pared, E es la salida.
// Al terminar, + marca el camino encontrado y x las celdas de donde hubo que volver.
#include <stdio.h>

#define ROWS 7
#define COLS 11

void print_maze(char maze[][COLS + 1]) {
    for (int row = 0; row < ROWS; row++) {
        printf("%s\n", maze[row]);
    }
}

// Devuelve 1 si desde (row, col) se puede llegar a la salida.
int find_path(char maze[][COLS + 1], int row, int col) {
    if (row < 0 || row >= ROWS || col < 0 || col >= COLS) {
        return 0;
    }
    if (maze[row][col] == 'E') {
        return 1;
    }
    if (maze[row][col] != ' ') {
        return 0;
    }
    maze[row][col] = '+';
    if (find_path(maze, row - 1, col) || find_path(maze, row + 1, col)
        || find_path(maze, row, col - 1) || find_path(maze, row, col + 1)) {
        return 1;
    }
    maze[row][col] = 'x';
    return 0;
}

int main(void) {
    char open_maze[ROWS][COLS + 1] = {
        "###########",
        "#   #     #",
        "# # # ### #",
        "# #   #   #",
        "# ##### # #",
        "#       #E#",
        "###########",
    };
    char closed_maze[ROWS][COLS + 1] = {
        "###########",
        "#   #     #",
        "# # # ### #",
        "# #   #   #",
        "# #########",
        "#       #E#",
        "###########",
    };

    printf("hay camino: %d\n", find_path(open_maze, 1, 1));
    print_maze(open_maze);
    printf("hay camino: %d\n", find_path(closed_maze, 1, 1));
    print_maze(closed_maze);
    return 0;
}

// Tiene un error a propósito: pinta la celda después de las llamadas, no antes.
#include <stdio.h>

#define ROWS 3
#define COLS 3

void fill(char grid[][COLS + 1], int row, int col) {
    if (row < 0 || row >= ROWS || col < 0 || col >= COLS) {
        return;
    }
    if (grid[row][col] != '.') {
        return;
    }
    fill(grid, row - 1, col);
    fill(grid, row + 1, col);
    fill(grid, row, col - 1);
    fill(grid, row, col + 1);
    grid[row][col] = 'o';
}

int main(void) {
    char grid[ROWS][COLS + 1] = {
        "...",
        ".#.",
        "...",
    };

    fill(grid, 0, 0);
    printf("%s\n%s\n%s\n", grid[0], grid[1], grid[2]);
    return 0;
}

// Tiene un error a propósito: pinta del mismo color que ya tenía la región.
#include <stdio.h>

#define ROWS 3
#define COLS 3

void fill(char grid[][COLS + 1], int row, int col, char old_mark, char new_mark) {
    if (row < 0 || row >= ROWS || col < 0 || col >= COLS) {
        return;
    }
    if (grid[row][col] != old_mark) {
        return;
    }
    grid[row][col] = new_mark;
    fill(grid, row - 1, col, old_mark, new_mark);
    fill(grid, row + 1, col, old_mark, new_mark);
    fill(grid, row, col - 1, old_mark, new_mark);
    fill(grid, row, col + 1, old_mark, new_mark);
}

int main(void) {
    char grid[ROWS][COLS + 1] = {
        "...",
        ".#.",
        "...",
    };

    fill(grid, 0, 0, grid[0][0], '.');
    printf("%s\n%s\n%s\n", grid[0], grid[1], grid[2]);
    return 0;
}

"""Comprueba los programas de la clase y lo que los apuntes dicen de ellos."""
import pathlib
import subprocess
import tempfile
import unittest

HERE = pathlib.Path(__file__).parent
BUILD = HERE / "build"
SOLUTION = BUILD / "solution"
BASE = ["-Wall", "-Wextra", "-std=c17"]
FLAGS = [*BASE, "-g", "-fsanitize=address,undefined"]
PROGRAMS = ["fib_count", "fib_trace", "fib_memo", "grid_fill", "fill_trace", "count_islands", "maze",
            "deep_fill", "fill_stack"]
# El mismo tamaño de pila que tiene el entorno del curso, para no depender de cómo se abrió la terminal.
STACK_KB = 8192


def run(program, *args):
    done = subprocess.run(
        [str(program), *args], cwd=HERE, text=True, encoding="utf-8", errors="replace",
        stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=60,
    )
    return done.stdout, done.returncode


def run_with_stack(kilobytes, program, *args):
    """Corre el programa con esa pila. Devuelve (salida, código de salida de bash)."""
    command = f"ulimit -s {kilobytes} && exec {program} " + " ".join(args)
    done = subprocess.run(
        ["bash", "-c", command], cwd=HERE, text=True, encoding="utf-8", errors="replace",
        stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=60,
    )
    return done.stdout, done.returncode


def can_raise_stack(kilobytes):
    done = subprocess.run(["bash", "-c", f"ulimit -s {kilobytes}"], stdout=subprocess.DEVNULL, stderr=subprocess.DEVNULL)
    return done.returncode == 0


def rows_of(text):
    return [line.split() for line in text.splitlines()[1:]]


class Programs(unittest.TestCase):
    def test_every_program_compiles_without_warnings(self):
        for name in PROGRAMS:
            with self.subTest(program=name):
                subprocess.run(["gcc", *FLAGS, "-Werror", "-c", f"{name}.c", "-o", "/dev/null"], cwd=HERE, check=True,
                               stdout=subprocess.PIPE, stderr=subprocess.STDOUT)

    def test_errors_compile_without_warnings(self):
        # Los errores de esta semana no los ve el compilador: aparecen al correr.
        for name in ("fill_no_mark", "fill_same_mark"):
            with self.subTest(program=name):
                subprocess.run(["gcc", *FLAGS, "-Werror", "-c", f"errors/{name}.c", "-o", "/dev/null"], cwd=HERE,
                               check=True, stdout=subprocess.PIPE, stderr=subprocess.STDOUT)

    def test_the_lab_compiles_without_warnings(self):
        for name in ("image", "regions", "board", "fill_demo", "minesweeper", "big_board", "regions_tests", "board_tests"):
            with self.subTest(file=name):
                subprocess.run(["gcc", *FLAGS, "-Werror", "-Ilab", "-c", f"lab/{name}.c", "-o", "/dev/null"], cwd=HERE,
                               check=True, stdout=subprocess.PIPE, stderr=subprocess.STDOUT)

    def test_no_program_leaks(self):
        for name in PROGRAMS:
            args = ("20",) if name in ("deep_fill", "fill_stack") else ()
            with self.subTest(program=name):
                out, code = run(BUILD / name, *args)
                self.assertEqual(code, 0, out)
                self.assertNotIn("LeakSanitizer", out)


class Fibonacci(unittest.TestCase):
    def test_calls_follow_the_formula(self):
        # llamadas(n) = 2 * fib(n + 1) - 1
        fib = [0, 1]
        for _ in range(50):
            fib.append(fib[-1] + fib[-2])
        out, _ = run(BUILD / "fib_count")
        for n, value, calls in rows_of(out):
            with self.subTest(n=n):
                self.assertEqual(int(value), fib[int(n)])
                self.assertEqual(int(calls), 2 * fib[int(n) + 1] - 1)

    def test_fib_5_makes_15_calls(self):
        out, _ = run(BUILD / "fib_count")
        self.assertIn(["5", "5", "15"], rows_of(out))

    def test_trace_has_one_line_per_call(self):
        out, _ = run(BUILD / "fib_trace")
        self.assertEqual(sum(line.strip().startswith("fib(") for line in out.splitlines()), 9)

    def test_memo_calls_are_2n_minus_1(self):
        out, _ = run(BUILD / "fib_memo")
        for row in rows_of(out):
            if len(row) == 4:
                n, _, plain, memo = row
                with self.subTest(n=n):
                    self.assertEqual(int(memo), 2 * int(n) - 1)
                    self.assertGreaterEqual(int(plain), int(memo))
        self.assertIn("fib(90) = 2880067194370816120, con 179 llamadas", out)


class Depth(unittest.TestCase):
    def test_the_depth_is_n_squared_plus_one(self):
        for size in (1, 3, 10, 100):
            with self.subTest(size=size):
                out, code = run(BUILD / "deep_fill", str(size))
                self.assertEqual(code, 0, out)
                self.assertIn(f"{size * size} celdas pintadas, {size * size + 1} marcos", out)

    def test_recursion_breaks_at_1000_with_8_mb(self):
        # Vale en cualquier arquitectura: un millón de marcos no cabe en 8 MB.
        for name in ("deep_fill", "deep_fill_plain", "deep_fill_o2"):
            with self.subTest(program=name):
                out, code = run_with_stack(STACK_KB, BUILD / name, "1000")
                self.assertNotEqual(code, 0, out)
                self.assertNotIn("celdas pintadas", out)

    def test_asan_names_the_stack_overflow(self):
        # En x86-64 emulado, ASan a veces cae sin escribir el informe: eso se acepta como caída.
        out, code = run_with_stack(STACK_KB, BUILD / "deep_fill", "1000")
        self.assertNotEqual(code, 0)
        if code == 1:
            self.assertIn("stack-overflow", out)
            self.assertIn("in fill", out)

    def test_plain_build_dies_with_a_signal(self):
        out, code = run_with_stack(STACK_KB, BUILD / "deep_fill_plain", "1000")
        self.assertEqual(code, -11, out)

    @unittest.skipUnless(can_raise_stack(200000), "este sistema no deja agrandar la pila")
    def test_with_more_stack_it_works(self):
        out, code = run_with_stack(200000, BUILD / "deep_fill_plain", "1000")
        self.assertEqual(code, 0, out)
        self.assertIn("1000000 celdas pintadas, 1000001 marcos", out)

    def test_own_stack_needs_no_big_stack(self):
        out, code = run_with_stack(STACK_KB, BUILD / "fill_stack", "1000")
        self.assertEqual(code, 0, out)
        self.assertIn("1000000 celdas pintadas", out)
        self.assertNotIn("LeakSanitizer", out)


class MarkErrors(unittest.TestCase):
    def crash_of(self, name):
        with tempfile.TemporaryDirectory() as folder:
            binary = pathlib.Path(folder) / name
            subprocess.run(["gcc", *FLAGS, f"errors/{name}.c", "-o", str(binary)], cwd=HERE, check=True)
            return run_with_stack(STACK_KB, binary)

    def test_marking_after_the_calls_never_ends(self):
        out, code = self.crash_of("fill_no_mark")
        self.assertNotEqual(code, 0, out)
        if code == 1:
            self.assertIn("stack-overflow", out)

    def test_painting_with_the_same_mark_never_ends(self):
        out, code = self.crash_of("fill_same_mark")
        self.assertNotEqual(code, 0, out)
        if code == 1:
            self.assertIn("stack-overflow", out)


@unittest.skipUnless((HERE / "solution").exists(), "falta la solución")
class BigBoard(unittest.TestCase):
    def test_small_boards_work(self):
        for name in ("big_board", "big_board_plain", "big_board_o2"):
            with self.subTest(program=name):
                out, code = run_with_stack(STACK_KB, SOLUTION / name, "100", "100")
                self.assertEqual(code, 0, out)
                self.assertIn("10000 celdas abiertas, juego ganado", out)

    def test_1000_by_1000_breaks_the_recursive_reveal(self):
        for name in ("big_board", "big_board_plain", "big_board_o2"):
            with self.subTest(program=name):
                out, code = run_with_stack(STACK_KB, SOLUTION / name, "1000", "1000")
                self.assertNotEqual(code, 0, out)
                self.assertNotIn("celdas abiertas", out)

    @unittest.skipUnless(can_raise_stack(400000), "este sistema no deja agrandar la pila")
    def test_with_more_stack_the_big_board_works(self):
        out, code = run_with_stack(400000, SOLUTION / "big_board_plain", "1000", "1000")
        self.assertEqual(code, 0, out)
        self.assertIn("1000000 celdas abiertas, juego ganado", out)


if __name__ == "__main__":
    unittest.main()

"""Pruebas del laboratorio. LAB_DIR dice dónde está el código: lab o solution.

Cada prueba compila un main propio con regions.c o board.c de esa carpeta, por separado de
las pruebas de ustedes. Corren con ASan, así que una fuga también hace fallar la prueba.
"""
import os
import pathlib
import subprocess
import tempfile
import unittest

HERE = pathlib.Path(__file__).parent
LAB = HERE / "lab"
LAB_DIR = os.environ.get("LAB_DIR", "solution")
SOURCE = HERE / LAB_DIR
FLAGS = ["-Wall", "-Wextra", "-std=c17", "-g", "-fsanitize=address,undefined"]


def setUpModule():
    if not (SOURCE / "board.c").exists():
        raise unittest.SkipTest(f"no está {LAB_DIR}/board.c")


def compile_and_run(sources, args=(), stdin="", files=None):
    """Devuelve (salida, código de salida) de un programa, en una carpeta temporal."""
    with tempfile.TemporaryDirectory() as name:
        folder = pathlib.Path(name)
        binary = folder / "program"
        built = subprocess.run(
            ["gcc", *FLAGS, f"-I{LAB}", *map(str, sources), "-o", str(binary)],
            text=True, stdout=subprocess.PIPE, stderr=subprocess.STDOUT,
        )
        if built.returncode != 0:
            raise AssertionError(f"No compila:\n{built.stdout}")
        for file_name, content in (files or {}).items():
            (folder / file_name).write_text(content, encoding="utf-8")
        done = subprocess.run(
            [str(binary), *args], cwd=folder, input=stdin, text=True, encoding="utf-8",
            errors="replace", stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=30,
        )
        return done.stdout, done.returncode


def run_driver(includes, body, sources, files=None):
    with tempfile.TemporaryDirectory() as name:
        driver = pathlib.Path(name) / "driver.c"
        driver.write_text(includes + "int main(void) {\n" + body + "\nreturn 0;\n}\n", encoding="utf-8")
        return compile_and_run([driver, *sources], files=files)


IMAGE_HELPERS = """#include <stdio.h>
#include "image.h"
#include "regions.h"
static Image *from_text(const char *text, int width, int height) {
    Image *img = image_new(width, height, IMAGE_MAX_VALUE, 0);
    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            image_set(img, x, y, text[y * width + x] - '0');
        }
    }
    return img;
}
static void print_rows(const Image *img) {
    for (int y = 0; y < image_height(img); y++) {
        for (int x = 0; x < image_width(img); x++) {
            printf("%d", image_get(img, x, y));
        }
        printf(" ");
    }
    printf("\\n");
}
"""

BOARD_HELPERS = """#include <stdio.h>
#include "board.h"
static void show(const Board *b) {
    for (int r = 0; r < board_rows(b); r++) {
        for (int c = 0; c < board_cols(b); c++) {
            printf("%c", board_cell_char(b, r, c));
        }
        printf(" ");
    }
    printf("\\n");
}
"""


def c_rows(rows):
    return "const char *rows[] = {" + ", ".join(f'"{row}"' for row in rows) + "};\n" \
        + f"Board *b = board_from_rows(rows, {len(rows)});\n" \
        + 'if (b == NULL) { printf("NULL\\n"); return 0; }\n'


class LabCase(unittest.TestCase):
    longMessage = False

    def check(self, result, wanted, what):
        out, code = result
        if code != 0:
            self.fail(f"{what}: el programa terminó con error.\n{out}")
        got = "\n".join(line.rstrip() for line in out.strip().splitlines())
        if got != wanted:
            self.fail(f"{what}\n  se esperaba: {wanted}\n  se obtuvo:   {got}")

    def fill(self, text, width, height, x, y, value):
        body = (f'Image *img = from_text("{text}", {width}, {height});\n'
                f"flood_fill(img, {x}, {y}, {value});\nprint_rows(img);\nimage_free(img);")
        return run_driver(IMAGE_HELPERS, body, [SOURCE / "regions.c", LAB / "image.c"])

    def regions(self, text, width, height):
        body = (f'Image *img = from_text("{text}", {width}, {height});\n'
                'printf("%d ", count_regions(img));\nprint_rows(img);\nimage_free(img);')
        return run_driver(IMAGE_HELPERS, body, [SOURCE / "regions.c", LAB / "image.c"])

    def board(self, rows, body):
        return run_driver(BOARD_HELPERS, c_rows(rows) + body + "\nboard_free(b);", [SOURCE / "board.c"])


class FloodFill(LabCase):
    def test_paints_only_the_region(self):
        self.check(self.fill("110" "010" "100", 3, 3, 0, 0, 9), "990 090 100",
                   "flood_fill en (0, 0): la celda de abajo a la izquierda solo toca por una diagonal")

    def test_diagonals_do_not_join(self):
        self.check(self.fill("10" "01", 2, 2, 0, 0, 9), "90 01", "flood_fill no pasa por una diagonal")

    def test_starts_anywhere_in_the_region(self):
        self.check(self.fill("110" "010" "100", 3, 3, 1, 1, 9), "990 090 100",
                   "flood_fill en (1, 1) pinta la misma región que en (0, 0)")

    def test_goes_around_corners(self):
        self.check(self.fill("11111" "00001" "11101" "10001" "11111", 5, 5, 0, 0, 7),
                   "77777 00007 77707 70007 77777", "flood_fill en un camino con curvas")

    def test_whole_image(self):
        self.check(self.fill("000000", 3, 2, 2, 1, 5), "555 555", "flood_fill en una imagen de un solo valor")

    def test_same_value_ends_and_changes_nothing(self):
        self.check(self.fill("110" "010", 3, 2, 0, 0, 1), "110 010",
                   "flood_fill con el valor que la región ya tiene: debe terminar sin cambiar nada")

    def test_large_region(self):
        body = ("Image *img = image_new(100, 100, IMAGE_MAX_VALUE, 3);\n"
                "flood_fill(img, 50, 50, 8);\nint painted = 0;\n"
                "for (int y = 0; y < 100; y++) { for (int x = 0; x < 100; x++) {"
                " painted += image_get(img, x, y) == 8; } }\n"
                'printf("%d\\n", painted);\nimage_free(img);')
        self.check(run_driver(IMAGE_HELPERS, body, [SOURCE / "regions.c", LAB / "image.c"]), "10000",
                   "flood_fill en una imagen de 100 x 100")


class CountRegions(LabCase):
    def test_one_region(self):
        self.check(self.regions("000000", 3, 2), "1 000 000", "count_regions con un solo valor")

    def test_single_pixel(self):
        self.check(self.regions("5", 1, 1), "1 5", "count_regions en una imagen de 1 x 1")

    def test_diagonals_do_not_join(self):
        self.check(self.regions("10" "01", 2, 2), "4 10 01", "count_regions: las diagonales no unen")

    def test_checkerboard(self):
        self.check(self.regions("0101" "1010" "0101" "1010", 4, 4), "16 0101 1010 0101 1010",
                   "count_regions en un tablero de ajedrez")

    def test_same_value_far_apart_counts_twice(self):
        self.check(self.regions("10201", 5, 1), "5 10201",
                   "count_regions: dos regiones con el mismo valor son dos regiones")

    def test_region_with_a_hole(self):
        self.check(self.regions("111" "101" "111", 3, 3), "2 111 101 111", "count_regions con un hueco adentro")

    def test_files_of_the_lab(self):
        for name, wanted in (("sun.pgm", 3), ("islands.pgm", 5), ("tiny.pgm", 6)):
            body = (f'Image *img = image_load("{LAB / "images" / name}");\n'
                    'if (img == NULL) { printf("NULL\\n"); return 0; }\n'
                    'printf("%d\\n", count_regions(img));\nimage_free(img);')
            with self.subTest(file=name):
                self.check(run_driver(IMAGE_HELPERS, body, [SOURCE / "regions.c", LAB / "image.c"]),
                           str(wanted), f"count_regions de {name}")

    def test_called_twice_gives_the_same(self):
        body = ('Image *img = from_text("1100", 2, 2);\n'
                'printf("%d %d\\n", count_regions(img), count_regions(img));\nimage_free(img);')
        self.check(run_driver(IMAGE_HELPERS, body, [SOURCE / "regions.c", LAB / "image.c"]), "2 2",
                   "count_regions dos veces: cada llamada empieza sin marcas")


class BoardNew(LabCase):
    def driver(self, body):
        return run_driver(BOARD_HELPERS, body, [SOURCE / "board.c"])

    def test_new_board(self):
        body = ('Board *b = board_new(2, 3);\nif (b == NULL) { printf("NULL\\n"); return 0; }\n'
                'printf("%d %d %d %d ", board_rows(b), board_cols(b), board_mines(b), board_opened(b));\n'
                "show(b);\nboard_free(b);")
        self.check(self.driver(body), "2 3 0 0 ### ###", "board_new(2, 3)")

    def test_bad_sizes_return_null(self):
        for rows, cols in ((0, 3), (3, 0), (-1, 3), (3, -1), (100000, 100000)):
            body = (f"Board *b = board_new({rows}, {cols});\n"
                    'printf("%s\\n", b == NULL ? "NULL" : "tablero");\nboard_free(b);')
            with self.subTest(rows=rows, cols=cols):
                self.check(self.driver(body), "NULL", f"board_new({rows}, {cols}) debe devolver NULL")

    def test_free_accepts_null(self):
        self.check(self.driver('board_free(NULL);\nprintf("ok\\n");'), "ok", "board_free(NULL)")

    def test_rejects_bad_rows_without_leaks(self):
        body = ('const char *rows[] = {"..", "..."};\nconst char *other[] = {"x"};\n'
                'printf("%d %d\\n", board_from_rows(rows, 2) == NULL, board_from_rows(other, 1) == NULL);')
        self.check(self.driver(body), "1 1", "board_from_rows con datos malos")


class NeighborCounts(LabCase):
    def around(self, rows):
        body = ('for (int r = 0; r < board_rows(b); r++) {\n'
                '    for (int c = 0; c < board_cols(b); c++) { printf("%d", board_mines_around(b, r, c)); }\n'
                '    printf(" ");\n}\nprintf("\\n");')
        return self.board(rows, body)

    def test_mine_in_the_center_has_eight_neighbors(self):
        self.check(self.around(["...", ".*.", "..."]), "111 101 111",
                   "minas vecinas alrededor del centro: la mina no se cuenta a sí misma")

    def test_corners_and_borders(self):
        self.check(self.around(["*..", "...", "..*"]), "010 121 010", "minas vecinas con minas en las esquinas")

    def test_full_board(self):
        self.check(self.around(["***", "***", "***"]), "353 585 353", "minas vecinas en un tablero lleno")

    def test_not_square(self):
        self.check(self.around(["*...", "...*"]), "0111 1110",
                   "minas vecinas en un tablero de 2 x 4")


class Reveal(LabCase):
    def test_number_opens_only_itself(self):
        self.check(self.board(["*..", "...", "..."], 'board_reveal(b, 0, 1);\nshow(b);\nprintf("%d\\n", board_opened(b));'),
                   "#1# ### ###\n1", "abrir una celda con número solo abre esa celda")

    def test_zero_opens_the_region_and_its_border(self):
        rows = ["*.......", "..*.....", "........", "......*.", "........"]
        self.check(self.board(rows, "board_reveal(b, 2, 0);\nshow(b);"),
                   "###1.... 12#1.... .111.111 .....1## .....1##",
                   "abrir una celda sin minas vecinas abre su zona y el borde con números")

    def test_opens_through_diagonals(self):
        # Las dos zonas sin minas solo se tocan por una diagonal: (1, 1) y (2, 2).
        rows = ["...*.", ".....", ".....", "*....", "....."]
        self.check(self.board(rows, "board_reveal(b, 0, 0);\nshow(b);"), "..1## ..111 11... #1... #1...",
                   "la apertura sigue a las ocho vecinas, también por las diagonales")

    def test_a_number_stops_the_opening(self):
        rows = ["......", "..*...", "......", "....*.", "......"]
        body = 'board_reveal(b, 0, 5);\nprintf("%d %d\\n", board_opened(b), board_state(b) == GAME_LOST);'
        self.check(self.board(rows, body), "9 0", "la apertura se detiene en los números y no abre ninguna mina")

    def test_flag_is_not_opened(self):
        rows = ["...", "...", "..*"]
        body = 'board_toggle_flag(b, 0, 2);\nboard_reveal(b, 0, 0);\nshow(b);\nboard_reveal(b, 0, 2);\nshow(b);'
        self.check(self.board(rows, body), "..F .11 .1#\n..F .11 .1#",
                   "una celda con bandera no se abre, ni directa ni de forma recursiva")

    def test_flag_can_be_removed(self):
        rows = ["*.", ".."]
        body = 'board_toggle_flag(b, 0, 1);\nboard_toggle_flag(b, 0, 1);\nboard_reveal(b, 0, 1);\nshow(b);'
        self.check(self.board(rows, body), "#1 ##", "una bandera quitada ya no protege la celda")

    def test_outside_is_ignored(self):
        rows = ["..", ".*"]
        body = ("board_reveal(b, -1, 0);\nboard_reveal(b, 0, -1);\nboard_reveal(b, 2, 0);\nboard_reveal(b, 0, 2);\n"
                'show(b);\nprintf("%d\\n", board_opened(b));')
        self.check(self.board(rows, body), "## ##\n0", "board_reveal fuera del tablero no hace nada")

    def test_open_twice_counts_once(self):
        rows = ["*.", ".."]
        body = 'board_reveal(b, 0, 1);\nboard_reveal(b, 0, 1);\nprintf("%d\\n", board_opened(b));'
        self.check(self.board(rows, body), "1", "abrir dos veces la misma celda cuenta una vez")

    def test_big_enough_board_with_recursion(self):
        body = ('Board *b = board_new(60, 60);\nif (b == NULL) { printf("NULL\\n"); return 0; }\n'
                'board_reveal(b, 30, 30);\nprintf("%d\\n", board_opened(b));\nboard_free(b);')
        self.check(run_driver(BOARD_HELPERS, body, [SOURCE / "board.c"]), "3600", "abrir un tablero de 60 x 60 sin minas")


class WinAndLose(LabCase):
    def test_starts_playing(self):
        self.check(self.board(["*."], 'printf("%d\\n", board_state(b) == GAME_PLAYING);'), "1", "al inicio se está jugando")

    def test_opening_a_mine_loses(self):
        rows = ["*.", ".*"]
        body = 'board_reveal(b, 0, 0);\nprintf("%d %d ", board_state(b) == GAME_LOST, board_opened(b));\nshow(b);'
        self.check(self.board(rows, body), "1 0 *# #*", "abrir una mina pierde y muestra todas las minas")

    def test_all_safe_cells_win(self):
        rows = ["*.", ".."]
        body = ('board_reveal(b, 0, 1);\nprintf("%d ", board_state(b) == GAME_PLAYING);\nboard_reveal(b, 1, 0);\n'
                'printf("%d ", board_state(b) == GAME_PLAYING);\nboard_reveal(b, 1, 1);\n'
                'printf("%d\\n", board_state(b) == GAME_WON);')
        self.check(self.board(rows, body), "1 1 1", "se gana solo al abrir la última celda sin mina")

    def test_win_without_flagging_the_mines(self):
        rows = ["...", "...", "..*"]
        self.check(self.board(rows, 'board_reveal(b, 0, 0);\nprintf("%d\\n", board_state(b) == GAME_WON);'), "1",
                   "no hace falta poner banderas para ganar")

    def test_flag_on_safe_cell_blocks_the_win(self):
        rows = ["*.", ".."]
        body = ('board_toggle_flag(b, 1, 1);\nboard_reveal(b, 0, 1);\nboard_reveal(b, 1, 0);\n'
                'printf("%d\\n", board_state(b) == GAME_PLAYING);')
        self.check(self.board(rows, body), "1", "una celda sin mina con bandera sigue sin abrir")

    def test_nothing_changes_after_losing(self):
        rows = ["*.", ".."]
        body = 'board_reveal(b, 0, 0);\nboard_reveal(b, 1, 1);\nprintf("%d %d\\n", board_opened(b), board_state(b) == GAME_LOST);'
        self.check(self.board(rows, body), "0 1", "después de perder, board_reveal no hace nada")

    def test_nothing_changes_after_winning(self):
        rows = ["*.", ".."]
        body = ('board_reveal(b, 0, 1);\nboard_reveal(b, 1, 0);\nboard_reveal(b, 1, 1);\nboard_reveal(b, 0, 0);\n'
                'printf("%d %d\\n", board_opened(b), board_state(b) == GAME_WON);')
        self.check(self.board(rows, body), "3 1", "después de ganar, board_reveal no hace nada")


class RandomBoards(LabCase):
    def driver(self, body):
        return run_driver(BOARD_HELPERS, body, [SOURCE / "board.c"])

    LAYOUT = """
    static void layout(const Board *b) {
        for (int r = 0; r < board_rows(b); r++) {
            for (int c = 0; c < board_cols(b); c++) { printf("%d", board_mines_around(b, r, c)); }
            printf(" ");
        }
        printf("\\n");
    }
    """

    def test_same_seed_same_board(self):
        body = ('Board *a = board_random(6, 6, 8, 42);\nBoard *b = board_random(6, 6, 8, 42);\n'
                'if (a == NULL || b == NULL) { printf("NULL\\n"); board_free(a); board_free(b); return 0; }\n'
                "layout(a);\nlayout(b);\nboard_free(a);\nboard_free(b);")
        out, code = run_driver(BOARD_HELPERS + self.LAYOUT, body, [SOURCE / "board.c"])
        self.assertEqual(code, 0, out)
        lines = [line.rstrip() for line in out.strip().splitlines()]
        self.assertEqual(len(lines), 2, out)
        self.assertEqual(lines[0], lines[1], "la misma semilla debe dar el mismo tablero")
        self.assertNotEqual(set(lines[0]) - {" "}, {"0"}, "con 8 minas, algunas celdas deben tener minas vecinas")

    def test_exact_mine_count(self):
        for mines in (0, 1, 8, 36):
            body = (f'Board *b = board_random(6, 6, {mines}, 7);\nif (b == NULL) {{ printf("NULL\\n"); return 0; }}\n'
                    'printf("%d\\n", board_mines(b));\nboard_free(b);')
            with self.subTest(mines=mines):
                self.check(self.driver(body), str(mines), f"board_random con {mines} minas")

    def test_impossible_counts(self):
        for mines in (-1, 37):
            body = (f"Board *b = board_random(6, 6, {mines}, 7);\n"
                    'printf("%s\\n", b == NULL ? "NULL" : "tablero");\nboard_free(b);')
            with self.subTest(mines=mines):
                self.check(self.driver(body), "NULL", f"board_random con {mines} minas no se puede")

    def test_game_with_a_known_seed(self):
        out, code = compile_and_run([LAB / "minesweeper.c", SOURCE / "board.c"], args=("5", "5", "3", "7"),
                                    stdin=(LAB / "game_seed7_input.txt").read_text(encoding="utf-8"))
        self.assertEqual(code, 0, out)
        wanted = (LAB / "game_seed7_output.txt").read_text(encoding="utf-8")
        if out != wanted:
            self.fail("La partida de la semilla 7 no coincide con lab/game_seed7_output.txt.\n"
                      f"Se obtuvo:\n{out}")


class TheirOwnTests(LabCase):
    def test_regions_tests_pass(self):
        out, code = compile_and_run([SOURCE / "regions.c", LAB / "image.c", LAB / "regions_tests.c"])
        self.assertEqual(code, 0, out)

    def test_board_tests_pass(self):
        out, code = compile_and_run([SOURCE / "board.c", LAB / "board_tests.c"])
        self.assertEqual(code, 0, out)

    def test_no_warnings(self):
        for name in ("regions.c", "board.c"):
            with self.subTest(file=name):
                done = subprocess.run(
                    ["gcc", "-Wall", "-Wextra", "-std=c17", f"-I{LAB}", "-c", str(SOURCE / name), "-o", os.devnull],
                    text=True, stdout=subprocess.PIPE, stderr=subprocess.STDOUT,
                )
                self.assertEqual(done.stdout, "", f"{name} da advertencias:\n{done.stdout}")


if __name__ == "__main__":
    unittest.main()