// Búsqueda binaria: en datos ordenados, descarta la mitad en cada paso.
#include <assert.h>
#include <stdio.h>

#define N 10

// a debe estar ordenado de menor a mayor.
int binary_search(const int a[], int n, int value) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == value) {
            return mid;
        } else if (a[mid] < value) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

int main(void) {
    int codes[N] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};

    assert(binary_search(codes, N, 2) == 0);     // el primero
    assert(binary_search(codes, N, 91) == 9);    // el último
    assert(binary_search(codes, N, 23) == 5);    // uno del medio
    assert(binary_search(codes, N, 1) == -1);    // menor que todos
    assert(binary_search(codes, N, 100) == -1);  // mayor que todos
    assert(binary_search(codes, N, 40) == -1);   // entre dos valores
    assert(binary_search(codes, 0, 2) == -1);    // arreglo vacío
    assert(binary_search(codes, 1, 2) == 0);     // un solo elemento

    printf("Todas las pruebas pasaron\n");
    return 0;
}

// Muestra los índices de cada paso de la búsqueda binaria.
#include <stdio.h>

#define N 10

int binary_search_trace(const int a[], int n, int value) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        printf("low = %d, high = %d, mid = %d, a[mid] = %d\n", low, high, mid, a[mid]);
        if (a[mid] == value) {
            return mid;
        } else if (a[mid] < value) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    printf("low = %d, high = %d: ya no queda nada\n", low, high);
    return -1;
}

int main(void) {
    int codes[N] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};

    int value;
    if (scanf("%d", &value) != 1) {
        printf("Entrada inválida\n");
        return 1;
    }
    printf("Resultado: %d\n", binary_search_trace(codes, N, value));
    return 0;
}

// Parte de las pruebas del laboratorio: test_lab.py corre esto con sus funciones.
// No hace falta leerlo. Usa argumentos de la línea de comandos, que no vemos en el curso.
#include <stdio.h>
#include <string.h>

#define CAP 300

struct search_result {
    int index;
    int comparisons;
};

int linear_search(const int a[], int n, int value);
int binary_search(const int a[], int n, int value);
struct search_result linear_count(const int a[], int n, int value);
struct search_result binary_count(const int a[], int n, int value);

static int max_halvings(int n) {
    int count = 0;
    while (n > 0) {
        n = n / 2;
        count++;
    }
    return count;
}

// Lleno con pares; los que siguen a n también son pares, para detectar si se pasan de n.
static void fill(int a[], int size) {
    for (int i = 0; i < size; i++) {
        a[i] = 2 * i;
    }
}

static int check_linear(void) {
    int a[CAP];
    fill(a, CAP);
    for (int n = 0; n < CAP; n++) {
        for (int i = 0; i < n; i++) {
            if (linear_search(a, n, a[i]) != i) {
                printf("linear_search: n=%d, no encuentra el índice %d\n", n, i);
                return 1;
            }
        }
        // a[n] existe pero no es parte de los n elementos.
        if (linear_search(a, n, a[n]) != -1 || linear_search(a, n, -1) != -1) {
            printf("linear_search: n=%d, debía devolver -1\n", n);
            return 1;
        }
    }
    int repeated[5] = {7, 3, 7, 3, 7};
    if (linear_search(repeated, 5, 3) != 1) {
        printf("linear_search: con repetidos debe devolver el primero\n");
        return 1;
    }
    int unsorted[5] = {5, 1, 9, 3, 7};
    if (linear_search(unsorted, 5, 1) != 1) {
        printf("linear_search: debe funcionar sin orden\n");
        return 1;
    }
    return 0;
}

static int check_binary(void) {
    int a[CAP];
    fill(a, CAP);
    for (int n = 0; n < CAP; n++) {
        for (int i = 0; i < n; i++) {
            if (binary_search(a, n, a[i]) != i) {
                printf("binary_search: n=%d, no encuentra el índice %d\n", n, i);
                return 1;
            }
            if (binary_search(a, n, a[i] + 1) != -1) {
                printf("binary_search: n=%d, encontró un valor que no está\n", n);
                return 1;
            }
        }
        if (binary_search(a, n, a[n]) != -1 || binary_search(a, n, -1) != -1) {
            printf("binary_search: n=%d, debía devolver -1\n", n);
            return 1;
        }
    }
    int repeated[5] = {1, 3, 3, 3, 9};
    int found = binary_search(repeated, 5, 3);
    if (found < 1 || found > 3) {
        printf("binary_search: con repetidos debe dar uno de los índices\n");
        return 1;
    }
    // Sin orden, una búsqueda binaria no encuentra este 1. Una lineal disfrazada sí.
    int unsorted[5] = {5, 1, 9, 3, 7};
    if (binary_search(unsorted, 5, 1) != -1) {
        printf("binary_search: encontró un valor mirando más de lo que parte a la mitad\n");
        return 1;
    }
    return 0;
}

static int check_linear_count(void) {
    int a[CAP];
    fill(a, CAP);
    for (int n = 0; n < CAP; n++) {
        for (int i = 0; i < n; i++) {
            struct search_result r = linear_count(a, n, a[i]);
            if (r.index != i || r.comparisons != i + 1) {
                printf("linear_count: n=%d, valor en %d: da índice %d y %d comparaciones\n",
                       n, i, r.index, r.comparisons);
                return 1;
            }
        }
        struct search_result r = linear_count(a, n, a[n]);
        if (r.index != -1 || r.comparisons != n) {
            printf("linear_count: n=%d, valor ausente: da índice %d y %d comparaciones\n",
                   n, r.index, r.comparisons);
            return 1;
        }
    }
    return 0;
}

static int check_binary_count(void) {
    int a[CAP];
    fill(a, CAP);
    for (int n = 1; n < CAP; n++) {
        int worst = 0;
        for (int value = -1; value <= 2 * n; value++) {
            struct search_result r = binary_count(a, n, value);
            int expected = (value >= 0 && value < 2 * n && value % 2 == 0) ? value / 2 : -1;
            if (r.index != expected) {
                printf("binary_count: n=%d, valor %d: da índice %d\n", n, value, r.index);
                return 1;
            }
            if (r.comparisons < 1) {
                printf("binary_count: n=%d, valor %d: no contó\n", n, value);
                return 1;
            }
            if (r.comparisons > worst) {
                worst = r.comparisons;
            }
        }
        if (worst != max_halvings(n)) {
            printf("binary_count: n=%d, el peor caso da %d y debe ser %d\n", n, worst,
                   max_halvings(n));
            return 1;
        }
    }
    // Pasos exactos en 0, 2, ..., 18: para el 2 se miran a[4] y a[1], y ahí está.
    struct search_result r = binary_count(a, 10, 2);
    if (r.index != 1 || r.comparisons != 2) {
        printf("binary_count: n=10, valor 2: da índice %d y %d comparaciones; deben ser 1 y 2\n",
               r.index, r.comparisons);
        return 1;
    }
    r = binary_count(a, 0, 2);
    if (r.index != -1 || r.comparisons != 0) {
        printf("binary_count: n=0 debe dar -1 y 0 comparaciones\n");
        return 1;
    }
    // Dos búsquedas seguidas no deben sumar sus cuentas.
    struct search_result again = binary_count(a, 10, 2);
    if (again.comparisons != 2) {
        printf("binary_count: la segunda llamada da %d; cada una debe contar desde 0\n",
               again.comparisons);
        return 1;
    }
    return 0;
}

int main(int argc, char *argv[]) {
    if (argc < 2) {
        return 2;
    }
    if (strcmp(argv[1], "linear") == 0) {
        return check_linear();
    }
    if (strcmp(argv[1], "binary") == 0) {
        return check_binary();
    }
    if (strcmp(argv[1], "linear_count") == 0) {
        return check_linear_count();
    }
    if (strcmp(argv[1], "binary_count") == 0) {
        return check_binary_count();
    }
    return 2;
}

// Parte de las pruebas del laboratorio: test_lab.py corre esto con sus funciones.
// No hace falta leerlo. Reemplaza a clock por un reloj de prueba, con un valor conocido,
// para comprobar la medición sin depender de la máquina, y a qsort por una versión que
// se deja contar. Por eso usa variables globales, que en el resto del curso no se usan.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

long long selection_sort(int a[], int n);
int is_sorted(const int a[], int n);
double seconds_selection(int a[], int n);
double seconds_qsort(int a[], int n);

#define N 50
#define BIG 70000

static int *watched;
static int clock_calls;
static int sorted_at_call[8];
static int qsort_calls;

static int really_sorted(const int a[], int n) {
    for (int i = 1; i < n; i++) {
        if (a[i - 1] > a[i]) {
            return 0;
        }
    }
    return 1;
}

// Reloj de prueba: cada llamada avanza medio segundo y anota si el arreglo ya estaba ordenado.
clock_t clock(void) {
    if (clock_calls < 8 && watched != NULL) {
        sorted_at_call[clock_calls] = really_sorted(watched, N);
    }
    clock_calls++;
    return (clock_t) (clock_calls * (CLOCKS_PER_SEC / 2));
}

// Reemplazo de qsort: ordena por inserción con la función que recibe, y cuenta la llamada.
void qsort(void *base, size_t count, size_t size, int (*compare)(const void *, const void *)) {
    qsort_calls++;
    char *bytes = base;
    char saved[64];
    if (size > sizeof(saved)) {
        abort();
    }
    for (size_t i = 1; i < count; i++) {
        memcpy(saved, bytes + i * size, size);
        size_t j = i;
        while (j > 0 && compare(bytes + (j - 1) * size, saved) > 0) {
            memcpy(bytes + j * size, bytes + (j - 1) * size, size);
            j--;
        }
        memcpy(bytes + j * size, saved, size);
    }
}

static void fill_shuffled(int a[], int n) {
    // Una permutación fija de 0..n-1, sin rand.
    for (int i = 0; i < n; i++) {
        a[i] = (i * 37 + 11) % n;
    }
}

static int check_sort(void) {
    int cases[][6] = {{3, 1, 2, 0, 0, 0}, {1, 1, 1, 1, 1, 1}, {6, 5, 4, 3, 2, 1},
                      {1, 2, 3, 4, 5, 6}, {-5, 2000000000, -2000000000, 0, 7, -5}};
    int sizes[] = {3, 6, 6, 6, 6};
    for (int c = 0; c < 5; c++) {
        int n = sizes[c];
        int a[8];
        int reference[8];
        for (int i = 0; i < n; i++) {
            a[i] = cases[c][i];
            reference[i] = cases[c][i];
        }
        // Dos casillas de más que no se deben tocar.
        a[n] = -999;
        a[n + 1] = 999;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (reference[j] < reference[i]) {
                    int s = reference[i];
                    reference[i] = reference[j];
                    reference[j] = s;
                }
            }
        }
        long long count = selection_sort(a, n);
        for (int i = 0; i < n; i++) {
            if (a[i] != reference[i]) {
                printf("selection_sort: caso %d, posición %d: da %d y debe ser %d\n", c, i, a[i],
                       reference[i]);
                return 1;
            }
        }
        if (a[n] != -999 || a[n + 1] != 999) {
            printf("selection_sort: caso %d, escribió después de n\n", c);
            return 1;
        }
        if (count != (long long) n * (n - 1) / 2) {
            printf("selection_sort: caso %d, %lld comparaciones; deben ser %d\n", c, count,
                   n * (n - 1) / 2);
            return 1;
        }
    }
    int one[1] = {4};
    if (selection_sort(one, 1) != 0 || one[0] != 4) {
        printf("selection_sort: con un elemento debe dar 0 comparaciones\n");
        return 1;
    }
    if (selection_sort(one, 0) != 0) {
        printf("selection_sort: con n = 0 debe dar 0 comparaciones\n");
        return 1;
    }
    return 0;
}

static int check_is_sorted(void) {
    int up[4] = {1, 2, 2, 3};
    int last_bad[4] = {1, 2, 3, 0};
    int first_bad[4] = {5, 1, 2, 3};
    if (is_sorted(up, 4) != 1 || is_sorted(up, 1) != 1 || is_sorted(up, 0) != 1) {
        printf("is_sorted: dice que no a un arreglo ordenado\n");
        return 1;
    }
    if (is_sorted(last_bad, 4) != 0 || is_sorted(first_bad, 4) != 0) {
        printf("is_sorted: dice que sí a un arreglo desordenado\n");
        return 1;
    }
    if (is_sorted(last_bad, 3) != 1) {
        printf("is_sorted: miró más allá de n\n");
        return 1;
    }
    return 0;
}

static int check_seconds(double (*measure)(int[], int), const char *name, int expected_qsort) {
    int a[N];
    fill_shuffled(a, N);
    if (really_sorted(a, N)) {
        return 2;
    }
    watched = a;
    clock_calls = 0;
    qsort_calls = 0;
    double seconds = measure(a, N);
    watched = NULL;
    if (qsort_calls != expected_qsort) {
        printf("%s: llamó a qsort %d veces; debe ser %d\n", name, qsort_calls, expected_qsort);
        return 1;
    }
    if (clock_calls != 2) {
        printf("%s: llamó a clock %d veces; deben ser 2\n", name, clock_calls);
        return 1;
    }
    if (sorted_at_call[0]) {
        printf("%s: ordenó antes de empezar a medir\n", name);
        return 1;
    }
    if (!sorted_at_call[1]) {
        printf("%s: la segunda medición llegó antes de terminar de ordenar\n", name);
        return 1;
    }
    if (seconds < 0.499 || seconds > 0.501) {
        printf("%s: con un reloj que avanza 0.5 s da %f\n", name, seconds);
        return 1;
    }
    return 0;
}

static int check_big_count(void) {
    // No cabe en un int. Se compila con -O2 y sin sanitizers para que tarde poco.
    static int a[BIG];
    fill_shuffled(a, BIG);
    long long count = selection_sort(a, BIG);
    long long expected = (long long) BIG * (BIG - 1) / 2;
    if (count != expected) {
        printf("selection_sort: con %d elementos da %lld y debe ser %lld\n", BIG, count, expected);
        return 1;
    }
    return 0;
}

int main(int argc, char *argv[]) {
    if (argc < 2) {
        return 2;
    }
    if (strcmp(argv[1], "sort") == 0) {
        return check_sort();
    }
    if (strcmp(argv[1], "is_sorted") == 0) {
        return check_is_sorted();
    }
    if (strcmp(argv[1], "seconds_selection") == 0) {
        return check_seconds(seconds_selection, "seconds_selection", 0);
    }
    if (strcmp(argv[1], "seconds_qsort") == 0) {
        return check_seconds(seconds_qsort, "seconds_qsort", 1);
    }
    if (strcmp(argv[1], "big_count") == 0) {
        return check_big_count();
    }
    return 2;
}

// Cuenta las comparaciones de cada búsqueda, en tres tamaños.
// Una comparación es mirar un elemento del arreglo y compararlo con el valor buscado.
#include <assert.h>
#include <stdio.h>

#define MAX_N 100000
#define SIZES 3

struct search_result {
    int index;         // dónde está, o -1
    int comparisons;   // cuántos elementos se miraron
};

struct search_result linear_count(const int a[], int n, int value) {
    struct search_result result = {-1, 0};
    for (int i = 0; i < n; i++) {
        result.comparisons++;
        if (a[i] == value) {
            result.index = i;
            return result;
        }
    }
    return result;
}

struct search_result binary_count(const int a[], int n, int value) {
    struct search_result result = {-1, 0};
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        result.comparisons++;
        if (a[mid] == value) {
            result.index = mid;
            return result;
        } else if (a[mid] < value) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

// Prueba todos los valores: los pares están en el arreglo y los impares no.
int binary_worst_case(const int a[], int n) {
    int worst = 0;
    for (int value = -1; value <= 2 * n; value++) {
        struct search_result result = binary_count(a, n, value);
        if (result.comparisons > worst) {
            worst = result.comparisons;
        }
    }
    return worst;
}

// Promedio de comparaciones si el valor sí está, probando cada posición una vez.
double linear_average(const int a[], int n) {
    long long total = 0;
    for (int i = 0; i < n; i++) {
        total = total + linear_count(a, n, a[i]).comparisons;
    }
    return (double) total / n;
}

double binary_average(const int a[], int n) {
    long long total = 0;
    for (int i = 0; i < n; i++) {
        total = total + binary_count(a, n, a[i]).comparisons;
    }
    return (double) total / n;
}

int main(void) {
    int sizes[SIZES] = {1000, 10000, 100000};
    int data[MAX_N];
    for (int i = 0; i < MAX_N; i++) {
        data[i] = 2 * i;   // ordenado, y solo con pares
    }

    assert(linear_count(data, 5, 4).index == 2);
    assert(linear_count(data, 5, 4).comparisons == 3);
    assert(binary_count(data, 5, 4).index == 2);
    assert(binary_count(data, 5, 4).comparisons == 1);

    printf("%8s %8s %8s %8s\n", "N", "lineal", "binaria", "peor");
    for (int s = 0; s < SIZES; s++) {
        int n = sizes[s];
        int missing = 2 * n;   // mayor que todos: no está
        printf("%8d %8d %8d %8d\n", n, linear_count(data, n, missing).comparisons,
               binary_count(data, n, missing).comparisons, binary_worst_case(data, n));
    }
    printf("Promedio con N = 1000, si el valor está: lineal %.2f, binaria %.2f\n",
           linear_average(data, 1000), binary_average(data, 1000));
    return 0;
}

// Factorial recursivo, con un rastro de cada llamada.
#include <assert.h>
#include <stdio.h>

// n debe ser 0 o más, y a lo sumo 20: 21! ya no cabe en 64 bits.
long long factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

long long factorial_trace(int n) {
    printf("entra factorial(%d)\n", n);
    if (n <= 1) {
        printf("caso base: factorial(%d) devuelve 1\n", n);
        return 1;
    }
    long long result = n * factorial_trace(n - 1);
    printf("factorial(%d) devuelve %lld\n", n, result);
    return result;
}

int main(void) {
    assert(factorial(0) == 1);
    assert(factorial(1) == 1);
    assert(factorial(5) == 120);
    assert(factorial(20) == 2432902008176640000);

    factorial_trace(4);
    printf("factorial(20) = %lld\n", factorial(20));
    return 0;
}

// Cómo crecen N, log N y N²: tablas de números exactos.
#include <assert.h>
#include <stdio.h>

// Cuántas veces se puede partir n a la mitad, sin decimales, hasta llegar a 0.
// Es el máximo de comparaciones de la búsqueda binaria en n elementos.
int halvings(int n) {
    int count = 0;
    while (n > 0) {
        n = n / 2;
        count++;
    }
    return count;
}

void print_row(int n) {
    long long square = (long long) n * n;
    printf("%9d %5d %9d %14lld\n", n, halvings(n), n, square);
}

int main(void) {
    assert(halvings(0) == 0);
    assert(halvings(1) == 1);
    assert(halvings(2) == 2);
    assert(halvings(3) == 2);

    printf("%9s %5s %9s %14s\n", "N", "log", "N", "N*N");
    for (int n = 1000; n <= 8000; n = n * 2) {
        print_row(n);
    }
    printf("\n");
    for (int n = 1000; n <= 1000000; n = n * 10) {
        print_row(n);
    }
    return 0;
}

// Búsqueda lineal: mira los elementos uno por uno, en cualquier orden.
#include <assert.h>
#include <stdio.h>

#define N 6

int linear_search(const int a[], int n, int value) {
    for (int i = 0; i < n; i++) {
        if (a[i] == value) {
            return i;
        }
    }
    return -1;
}

int main(void) {
    int grades[N] = {14, 9, 17, 11, 20, 9};

    assert(linear_search(grades, N, 14) == 0);   // el primero
    assert(linear_search(grades, N, 9) == 1);    // repetido: da el primero que encuentra
    assert(linear_search(grades, N, 13) == -1);  // no está
    assert(linear_search(grades, 0, 14) == -1);  // arreglo vacío

    printf("Buscar 17 devuelve %d\n", linear_search(grades, N, 17));
    printf("Buscar 13 devuelve %d\n", linear_search(grades, N, 13));
    return 0;
}

// qsort ordena un arreglo: le decimos qué tamaño tiene y cómo comparar dos elementos.
#include <stdio.h>
#include <stdlib.h>

#define N 6

// La forma de esta función la pide qsort. Devuelve un número negativo si el primero
// va antes, positivo si va después, y 0 si da igual.
int compare_ints(const void *first, const void *second) {
    int x = *(const int *) first;
    int y = *(const int *) second;
    if (x < y) {
        return -1;
    } else if (x > y) {
        return 1;
    }
    return 0;
}

int main(void) {
    int grades[N] = {14, 9, 17, 11, 20, 9};

    qsort(grades, N, sizeof(grades[0]), compare_ints);

    for (int i = 0; i < N; i++) {
        printf(" %d", grades[i]);
    }
    printf("\n");
    return 0;
}

// Ordenamiento por selección: muestra cada pasada y cuenta las comparaciones.
#include <assert.h>
#include <stdio.h>

#define N 5

void print_array(const int a[], int n) {
    for (int i = 0; i < n; i++) {
        printf(" %d", a[i]);
    }
    printf("\n");
}

void swap_at(int a[], int i, int j) {
    int saved = a[i];
    a[i] = a[j];
    a[j] = saved;
}

// Ordena de menor a mayor y devuelve cuántas comparaciones hizo.
long long selection_sort(int a[], int n) {
    long long comparisons = 0;
    for (int i = 0; i < n - 1; i++) {
        int smallest = i;
        for (int j = i + 1; j < n; j++) {
            comparisons++;
            if (a[j] < a[smallest]) {
                smallest = j;
            }
        }
        swap_at(a, i, smallest);
        printf("i = %d, menor en %d:", i, smallest);
        print_array(a, n);
    }
    return comparisons;
}

int main(void) {
    int unsorted[N] = {29, 10, 14, 37, 13};
    int sorted[N] = {10, 13, 14, 29, 37};

    printf("Inicio:");
    print_array(unsorted, N);
    printf("Comparaciones: %lld\n", selection_sort(unsorted, N));

    printf("Inicio:");
    print_array(sorted, N);
    printf("Comparaciones: %lld\n", selection_sort(sorted, N));

    assert(selection_sort(sorted, 0) == 0);
    return 0;
}

// ¿Conviene ordenar antes de buscar? Hace k búsquedas de valores que no están, de dos
// formas. Lee N y después los valores de k. Se compila con -O2 y sin sanitizers.
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_N 100000

struct search_result {
    int index;
    int comparisons;
};

int compare_ints(const void *first, const void *second) {
    int x = *(const int *) first;
    int y = *(const int *) second;
    if (x < y) {
        return -1;
    } else if (x > y) {
        return 1;
    }
    return 0;
}

struct search_result linear_count(const int a[], int n, int value) {
    struct search_result result = {-1, 0};
    for (int i = 0; i < n; i++) {
        result.comparisons++;
        if (a[i] == value) {
            result.index = i;
            return result;
        }
    }
    return result;
}

struct search_result binary_count(const int a[], int n, int value) {
    struct search_result result = {-1, 0};
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        result.comparisons++;
        if (a[mid] == value) {
            result.index = mid;
            return result;
        } else if (a[mid] < value) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

int main(void) {
    int original[MAX_N];
    int work[MAX_N];

    int n;
    if (scanf("%d", &n) != 1 || n < 1 || n > MAX_N) {
        printf("Entrada inválida\n");
        return 1;
    }

    // Los pares de 0 a 2n - 2, desordenados. Los impares no están en el arreglo.
    srand(2026);
    for (int i = 0; i < n; i++) {
        original[i] = 2 * i;
    }
    for (int i = n - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        int saved = original[i];
        original[i] = original[j];
        original[j] = saved;
    }

    printf("%7s %15s %12s %10s %10s\n", "k", "lineal", "binaria", "t lineal", "t ordenar");
    int k;
    while (scanf("%d", &k) == 1) {
        long long linear_total = 0;
        clock_t start = clock();
        for (int t = 0; t < k; t++) {
            struct search_result r = linear_count(original, n, 2 * (t % n) + 1);
            assert(r.index == -1);
            linear_total = linear_total + r.comparisons;
        }
        clock_t end = clock();
        double linear_seconds = (double) (end - start) / CLOCKS_PER_SEC;

        for (int i = 0; i < n; i++) {
            work[i] = original[i];
        }
        long long binary_total = 0;
        start = clock();
        qsort(work, n, sizeof(work[0]), compare_ints);
        for (int t = 0; t < k; t++) {
            struct search_result r = binary_count(work, n, 2 * (t % n) + 1);
            assert(r.index == -1);
            binary_total = binary_total + r.comparisons;
        }
        end = clock();
        double sorted_seconds = (double) (end - start) / CLOCKS_PER_SEC;

        printf("%7d %15lld %12lld %9.4fs %9.4fs\n", k, linear_total, binary_total,
               linear_seconds, sorted_seconds);
    }
    return 0;
}

// Mide selección y qsort con clock. Lee los tamaños de la entrada, hasta que se acabe.
// Para medir se compila con -O2 y sin sanitizers: make build/fast/sort_times
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_N 100000

int compare_ints(const void *first, const void *second) {
    int x = *(const int *) first;
    int y = *(const int *) second;
    if (x < y) {
        return -1;
    } else if (x > y) {
        return 1;
    }
    return 0;
}

long long selection_sort(int a[], int n) {
    long long comparisons = 0;
    for (int i = 0; i < n - 1; i++) {
        int smallest = i;
        for (int j = i + 1; j < n; j++) {
            comparisons++;
            if (a[j] < a[smallest]) {
                smallest = j;
            }
        }
        int saved = a[i];
        a[i] = a[smallest];
        a[smallest] = saved;
    }
    return comparisons;
}

int is_sorted(const int a[], int n) {
    for (int i = 1; i < n; i++) {
        if (a[i - 1] > a[i]) {
            return 0;
        }
    }
    return 1;
}

int main(void) {
    int original[MAX_N];
    int work[MAX_N];
    srand(2026);
    for (int i = 0; i < MAX_N; i++) {
        original[i] = rand();
    }

    int n;
    printf("%7s %12s %10s %10s  %s\n", "N", "comparac.", "selección", "qsort", "ordenado");
    while (scanf("%d", &n) == 1) {
        if (n < 1 || n > MAX_N) {
            printf("Tamaño inválido: %d\n", n);
            return 1;
        }

        for (int i = 0; i < n; i++) {
            work[i] = original[i];
        }
        clock_t start = clock();
        long long comparisons = selection_sort(work, n);
        clock_t end = clock();
        double selection_seconds = (double) (end - start) / CLOCKS_PER_SEC;
        int ok = is_sorted(work, n);

        for (int i = 0; i < n; i++) {
            work[i] = original[i];
        }
        start = clock();
        qsort(work, n, sizeof(work[0]), compare_ints);
        end = clock();
        double qsort_seconds = (double) (end - start) / CLOCKS_PER_SEC;
        ok = ok && is_sorted(work, n);

        printf("%7d %12lld %9.4fs %9.4fs  ", n, comparisons, selection_seconds, qsort_seconds);
        if (ok) {
            printf("sí\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

// Error a propósito: búsqueda binaria en un arreglo que no está ordenado.
#include <stdio.h>

#define N 5

int binary_search(const int a[], int n, int value) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == value) {
            return mid;
        } else if (a[mid] < value) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

int main(void) {
    int a[N] = {5, 1, 9, 3, 7};
    for (int i = 0; i < N; i++) {
        printf("El %d está en el índice %d; binaria responde %d\n", a[i], i,
               binary_search(a, N, a[i]));
    }
    return 0;
}

// Error a propósito: restar para comparar parece cómodo, pero la resta puede no caber.
#include <stdio.h>
#include <stdlib.h>

#define N 3

int compare_subtract(const void *first, const void *second) {
    int x = *(const int *) first;
    int y = *(const int *) second;
    return x - y;
}

int main(void) {
    int a[N] = {2000000000, -2000000000, 5};

    qsort(a, N, sizeof(a[0]), compare_subtract);

    for (int i = 0; i < N; i++) {
        printf(" %d", a[i]);
    }
    printf("\n");
    return 0;
}

// Tiene caso base, pero con un n muy grande la pila no alcanza.
#include <stdio.h>

long long sum_down(int n) {
    if (n <= 0) {
        return 0;
    }
    return n + sum_down(n - 1);
}

int main(void) {
    int n;
    if (scanf("%d", &n) != 1) {
        printf("Entrada inválida\n");
        return 1;
    }
    printf("%lld\n", sum_down(n));
    return 0;
}

// Error a propósito: el ciclo se detiene cuando aún queda un elemento por mirar.
#include <stdio.h>

#define N 3

int binary_search_wrong(const int a[], int n, int value) {
    int low = 0;
    int high = n - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == value) {
            return mid;
        } else if (a[mid] < value) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

int main(void) {
    int a[N] = {10, 20, 30};
    for (int i = 0; i < N; i++) {
        printf("El %d está en el índice %d; responde %d\n", a[i], i,
               binary_search_wrong(a, N, a[i]));
    }
    return 0;
}

// Error a propósito: low + high puede no caber en un int, aunque el resultado sí cabría.
#include <stdio.h>

int main(void) {
    int low;
    int high;
    if (scanf("%d %d", &low, &high) != 2) {
        printf("Entrada inválida\n");
        return 1;
    }
    printf("Fórmula segura: %d\n", low + (high - low) / 2);
    printf("Fórmula con la suma: %d\n", (low + high) / 2);
    return 0;
}

// Error a propósito: una función recursiva sin caso base.
#include <stdio.h>

long long sum_down(int n) {
    return n + sum_down(n - 1);
}

int main(void) {
    printf("%lld\n", sum_down(3));
    return 0;
}

"""Comprueba lo que los apuntes afirman sobre los programas de la semana 13.
Los tiempos dependen de la máquina: aquí se comparan cuentas, nunca segundos."""
import pathlib
import re
import subprocess
import tempfile
import unittest

HERE = pathlib.Path(__file__).parent
BUILD = HERE / "build"
FLAGS = ["-Wall", "-Wextra", "-std=c17"]
SANITIZE = ["-g", "-fsanitize=address,undefined"]


def execute(command, stdin=""):
    done = subprocess.run(
        command, input=stdin, encoding="utf-8", errors="replace",
        stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=60,
    )
    return done.stdout, done.returncode


def run(program, stdin=""):
    """Ejecuta un programa de build/; devuelve su salida (con errores) y su estado."""
    return execute([str(BUILD / program)], stdin)


def build_source(source, *extra):
    """Compila un archivo; devuelve los mensajes, el estado y el ejecutable."""
    out = pathlib.Path(tempfile.mkdtemp()) / pathlib.Path(source).stem
    done = subprocess.run(
        ["gcc", *FLAGS, *extra, source, "-o", str(out)], cwd=HERE, encoding="utf-8",
        stdout=subprocess.PIPE, stderr=subprocess.STDOUT,
    )
    return done.stdout, done.returncode, out


def binary_probes(n, value):
    """La misma búsqueda binaria en Python, sobre los pares 0, 2, ..., 2n - 2."""
    low, high, probes = 0, n - 1, 0
    while low <= high:
        mid = low + (high - low) // 2
        probes += 1
        if 2 * mid == value:
            return probes
        if 2 * mid < value:
            low = mid + 1
        else:
            high = mid - 1
    return probes


class CleanCompile(unittest.TestCase):
    def test_examples_have_no_warnings(self):
        for source in sorted(HERE.glob("*.c")):
            with self.subTest(source=source.name):
                done = subprocess.run(
                    ["gcc", *FLAGS, "-Werror", "-fsyntax-only", str(source)],
                    text=True, stdout=subprocess.PIPE, stderr=subprocess.STDOUT,
                )
                self.assertEqual(done.returncode, 0, done.stdout)

    def test_no_malloc_in_the_course(self):
        for source in list(HERE.glob("*.c")) + list((HERE / "errors").glob("*.c")):
            with self.subTest(source=source.name):
                self.assertNotIn("malloc", source.read_text(encoding="utf-8"))

    def test_timing_programs_have_no_sanitizers(self):
        for program in ["sort_times", "sort_then_search"]:
            with self.subTest(program=program):
                self.assertNotIn(b"__asan", (BUILD / "fast" / program).read_bytes())
        self.assertIn(b"__asan", (BUILD / "selection_sort").read_bytes())


class Searches(unittest.TestCase):
    def test_linear_search(self):
        self.assertEqual(run("linear_search"), (
            "Buscar 17 devuelve 2\nBuscar 13 devuelve -1\n", 0))

    def test_binary_search_asserts(self):
        self.assertEqual(run("binary_search"), ("Todas las pruebas pasaron\n", 0))

    def test_trace_of_a_value_that_is_there(self):
        self.assertEqual(run("binary_trace", "23\n"), (
            "low = 0, high = 9, mid = 4, a[mid] = 16\n"
            "low = 5, high = 9, mid = 7, a[mid] = 56\n"
            "low = 5, high = 6, mid = 5, a[mid] = 23\n"
            "Resultado: 5\n", 0))

    def test_trace_of_a_value_that_is_not_there(self):
        output, code = run("binary_trace", "40\n")
        self.assertEqual(code, 0)
        self.assertEqual(output.splitlines()[-2:], [
            "low = 7, high = 6: ya no queda nada", "Resultado: -1"])

    def test_trace_rejects_bad_input(self):
        self.assertEqual(run("binary_trace", "abc\n"), ("Entrada inválida\n", 1))

    def test_unsorted_data_breaks_binary_search(self):
        _, status, binary = build_source("errors/binary_unsorted.c")
        self.assertEqual(status, 0)
        self.assertEqual(execute([str(binary)]), (
            "El 5 está en el índice 0; binaria responde 0\n"
            "El 1 está en el índice 1; binaria responde -1\n"
            "El 9 está en el índice 2; binaria responde 2\n"
            "El 3 está en el índice 3; binaria responde -1\n"
            "El 7 está en el índice 4; binaria responde -1\n", 0))

    def test_low_less_than_high_misses_values(self):
        _, status, binary = build_source("errors/low_less_high.c")
        self.assertEqual(status, 0)
        self.assertEqual(execute([str(binary)]), (
            "El 10 está en el índice 0; responde -1\n"
            "El 20 está en el índice 1; responde 1\n"
            "El 30 está en el índice 2; responde -1\n", 0))

    def test_sum_of_low_and_high_overflows(self):
        _, status, binary = build_source("errors/mid_overflow.c", *SANITIZE)
        self.assertEqual(status, 0)
        output, _ = execute([str(binary)], "2000000000 2100000000\n")
        self.assertIn("signed integer overflow", output)
        self.assertIn("Fórmula segura: 2050000000", output)

    def test_safe_formula_is_silent_when_nothing_overflows(self):
        _, status, binary = build_source("errors/mid_overflow.c", *SANITIZE)
        self.assertEqual(status, 0)
        output, _ = execute([str(binary)], "4 9\n")
        self.assertNotIn("runtime error", output)
        self.assertEqual(output, "Fórmula segura: 6\nFórmula con la suma: 6\n")


class Counting(unittest.TestCase):
    def test_table_matches_an_independent_simulation(self):
        output, code = run("count_search")
        self.assertEqual(code, 0, output)
        rows = [line.split() for line in output.splitlines()[1:4]]
        for row in rows:
            n, linear, binary, worst = map(int, row)
            with self.subTest(n=n):
                self.assertEqual(linear, n)
                self.assertEqual(binary, binary_probes(n, 2 * n))
                self.assertEqual(worst, max(binary_probes(n, v) for v in range(-1, 2 * n + 1)))
        self.assertEqual([row[0] for row in rows], ["1000", "10000", "100000"])

    def test_averages_with_1000_elements(self):
        output, _ = run("count_search")
        average = sum(binary_probes(1000, 2 * i) for i in range(1000)) / 1000
        self.assertIn(f"lineal {(1000 + 1) / 2:.2f}, binaria {average:.2f}", output)

    def test_one_million_needs_twenty(self):
        output, _ = run("growth")
        self.assertRegex(output, r"1000000\s+20\s+1000000\s+1000000000000\n")
        self.assertEqual(binary_probes(1000000, 2 * 1000000), 20)

    def test_growth_doubling_rows(self):
        output, _ = run("growth")
        first = [list(map(int, line.split())) for line in output.splitlines()[1:5]]
        self.assertEqual([row[0] for row in first], [1000, 2000, 4000, 8000])
        for before, after in zip(first, first[1:]):
            self.assertEqual(after[1], before[1] + 1)      # log suma 1
            self.assertEqual(after[2], before[2] * 2)      # N se duplica
            self.assertEqual(after[3], before[3] * 4)      # N*N se multiplica por 4


class Sorting(unittest.TestCase):
    def test_selection_sort_trace(self):
        self.assertEqual(run("selection_sort"), (
            "Inicio: 29 10 14 37 13\n"
            "i = 0, menor en 1: 10 29 14 37 13\n"
            "i = 1, menor en 4: 10 13 14 37 29\n"
            "i = 2, menor en 2: 10 13 14 37 29\n"
            "i = 3, menor en 4: 10 13 14 29 37\n"
            "Comparaciones: 10\n"
            "Inicio: 10 13 14 29 37\n"
            "i = 0, menor en 0: 10 13 14 29 37\n"
            "i = 1, menor en 1: 10 13 14 29 37\n"
            "i = 2, menor en 2: 10 13 14 29 37\n"
            "i = 3, menor en 3: 10 13 14 29 37\n"
            "Comparaciones: 10\n", 0))

    def test_exact_comparisons_and_real_sorting(self):
        output, code = run("fast/sort_times", "1 2 1000 5000\n")
        self.assertEqual(code, 0, output)
        rows = [line.split() for line in output.splitlines()[1:]]
        self.assertEqual(len(rows), 4)
        for row in rows:
            n = int(row[0])
            with self.subTest(n=n):
                self.assertEqual(int(row[1]), n * (n - 1) // 2)
                self.assertRegex(row[2], r"^\d+\.\d{4}s$")
                self.assertRegex(row[3], r"^\d+\.\d{4}s$")
                self.assertEqual(row[4], "sí")

    def test_sizes_are_checked(self):
        output, code = run("fast/sort_times", "100001\n")
        self.assertEqual(code, 1)
        self.assertIn("Tamaño inválido", output)

    def test_qsort_demo(self):
        self.assertEqual(run("qsort_demo"), (" 9 9 11 14 17 20\n", 0))

    def test_subtracting_to_compare_overflows(self):
        _, status, binary = build_source("errors/compare_subtract.c", *SANITIZE)
        self.assertEqual(status, 0)
        output, _ = execute([str(binary)])
        self.assertIn("signed integer overflow", output)

    def test_sort_then_search_counts(self):
        output, code = run("fast/sort_then_search", "1000 1 10 1000\n")
        self.assertEqual(code, 0, output)
        rows = [line.split() for line in output.splitlines()[1:]]
        for row in rows:
            k = int(row[0])
            with self.subTest(k=k):
                self.assertEqual(int(row[1]), k * 1000)
                expected = sum(binary_probes(1000, 2 * (t % 1000) + 1) for t in range(k))
                self.assertEqual(int(row[2]), expected)


class Recursion(unittest.TestCase):
    def test_factorial_trace(self):
        self.assertEqual(run("factorial"), (
            "entra factorial(4)\nentra factorial(3)\nentra factorial(2)\nentra factorial(1)\n"
            "caso base: factorial(1) devuelve 1\n"
            "factorial(2) devuelve 2\nfactorial(3) devuelve 6\nfactorial(4) devuelve 24\n"
            "factorial(20) = 2432902008176640000\n", 0))

    def test_no_base_case_warns_and_dies(self):
        messages, status, binary = build_source("errors/no_base_case.c")
        self.assertEqual(status, 0)
        self.assertIn("-Winfinite-recursion", messages)
        _, code = execute(["bash", "-c", f"ulimit -s 8192; {binary}"])
        self.assertNotEqual(code, 0)

    def test_no_base_case_with_the_sanitizer(self):
        _, status, binary = build_source("errors/no_base_case.c", *SANITIZE)
        self.assertEqual(status, 0)
        # Siempre muere, pero en x86-64 emulado a veces no alcanza a escribir el informe.
        outputs = []
        for _ in range(12):
            output, code = execute(["bash", "-c", f"ulimit -s 8192; {binary}"])
            self.assertNotEqual(code, 0)
            outputs.append(output)
            if "AddressSanitizer: stack-overflow" in output:
                break
        self.assertRegex(outputs[-1], "AddressSanitizer: stack-overflow")

    def test_deep_recursion(self):
        _, status, binary = build_source("errors/deep_recursion.c")
        self.assertEqual(status, 0)
        self.assertEqual(execute([str(binary)], "1000\n"), ("500500\n", 0))
        _, code = execute(["bash", "-c", f"ulimit -s 8192; echo 10000000 | {binary}"])
        self.assertNotEqual(code, 0)


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