#include <ctype.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "aocdailies.h"
#include "aocutils.h"

/* === aoc202409 =======================================================
   WOW! input consists of a 20,000 long string of numbers!
   Make an array of blocks, each with either -1 or the fileid
   For Part Two: make an array of blocks with the encoded value of
(fileid * 10) + length, or, when empty, the negative length
===================================================================== */

void aoc202409(char *data, size_t len) {
    (void)len; // unused argument
    int *disk = malloc(512 * sizeof *disk);
    size_t rdisk = 512;
    size_t ndisk = 0;
    int fileid = 0;
    while (*data) {
        for (int k = 0; k < *data - '0'; k++) {
            if (ndisk == rdisk) {
                // assume it works
                rdisk = (13*rdisk)/8;
                disk = realloc(disk, rdisk * sizeof *disk);
            }
            disk[ndisk++] = (fileid * 10) + (*data - '0'); // encoded
        }
        fileid++;
        data++;
        if (*data) {
            for (int k = 0; k < *data - '0'; k++) {
                if (ndisk == rdisk) {
                    // assume it works
                    rdisk = (13*rdisk)/8;
                    disk = realloc(disk, rdisk * sizeof *disk);
                }
                disk[ndisk++] = -1 * (*data - '0'); // negative length
            }
            data++;
        }
    }
    // copy disk for Part Two
    int *diskcopy = malloc(ndisk * sizeof *disk);
    memcpy(diskcopy, disk, ndisk * sizeof *disk);

    int *left = disk, *right = disk + ndisk;
    for (;;) {
        while (*left >= 0) left++;
        if (left >= right) break;
        while (right[-1] < 0) right--;
        if (left >= right) break;
        // swap *left and right[-1]
        int tmp = *--right;
        *right = *left;
        *left++ = tmp;
    }
    unsigned long long chksum = 0;
    size_t index = 0;
    while (disk[index] >= 0) {
        chksum += ((size_t)disk[index]/10) * index;
        index++;
    }
    printf("%llu\n", chksum);
    free(disk);

    // part 2
    for (int filetomove = fileid - 1; filetomove > 0; filetomove--) {
        int *startoffile = diskcopy;
        while (*startoffile / 10 != filetomove) {
            if (*startoffile < 0) startoffile += -*startoffile;
            else startoffile += *startoffile % 10;
        }
        int blocksneeded = *startoffile % 10;
        int *bigblock = diskcopy;
        while (bigblock < startoffile) {
            if (*bigblock < 0) {
                if (-*bigblock < blocksneeded) {
                    bigblock += -*bigblock;
                } else {
                    // found a suitable block: move and quit tightest loop
                    int bbsize = -*bigblock;
                    int k;
                    for (k = 0; k < blocksneeded; k++) {
                        int tmp = startoffile[k];
                        startoffile[k] = bigblock[k];
                        bigblock[k] = tmp;
                    }
                    for (; k < bbsize; k++) {
                        bigblock[k] += blocksneeded;
                    }
                    break;
                }
            } else {
                bigblock += *bigblock % 10;
            }
        }
    }

    unsigned long long chksum2 = 0;
    index = 0;
    for (index = 0; index < ndisk; index++) {
        if (diskcopy[index] > 0) {
            chksum2 += ((size_t)diskcopy[index]/10) * index;
        }
    }
    printf("%llu\n", chksum2);
    free(diskcopy);
}

/* === aoc202408 =======================================================
   Oh! another square of text!
   Idea: for all points p with an antenna find all points q>p with
a corresponding frequency. For each such pair calculate the 2 antinodes