p17.c

//
//  main.c
//  p17
//
//  Created by Erik Aderstedt on 2019-12-16.
//  Copyright © 2019 Aderstedt Software AB-> All rights reserved.
//
#include <stdio.h>
#include "intcode.h"

enum Direction {
    kNorth = 0,
    kEast = 1,
    kSouth = 2,
    kWest = 3
};

struct segment {
    int *moves;
    size_t nmoves;
};

size_t bytes_in_ascii_representation(struct segment *segment) {
    size_t n = 0;
    for (size_t i = 0; i < segment->nmoves; i++) {
        if (segment->moves[i] >= 10) n += 4; else n += 3;
    }
    return n;
}

bool segments_match(struct segment *s1, struct segment *s2) {
    if (s2->nmoves > s1->nmoves) return false;
    for (size_t i = 0; i < s2->nmoves; i++) {
        if (s1->moves[i] != s2->moves[i]) return false;
    }
    return true;
}

struct segment *shortest_segment_among(struct segment *segments, size_t nsegments) {
    if (nsegments == 0) return NULL;
    size_t mlen = SIZE_MAX;
    size_t shortest;
    for (size_t i = 0; i < nsegments; i++) {
        if (segments[i].nmoves < mlen) {
            mlen = segments[i].nmoves;
            shortest = i;
        }
    }
    return segments + shortest;
}

void display_segment(struct segment *s) {
    for (size_t i = 0; i < s->nmoves; i++) {
        printf("%s,%d%s", (s->moves[i] > 0) ? "R" : "L", abs(s->moves[i]), (i == s->nmoves - 1) ? "\n" : ",");
    }
}

char *segment_as_buffer(struct segment *s) {
    char *buf = (char *)calloc(100, 1); size_t j = 0;
    for (size_t i = 0; i < s->nmoves; i++) {
        j += sprintf(buf + j, "%s,%d%s", (s->moves[i] > 0) ? "R" : "L", abs(s->moves[i]), (i == s->nmoves - 1) ? "\n" : ",");
    }
    return buf;
}

struct segment *split_by_subsegment(struct segment *segment, struct segment *subsegment, size_t *nsegments_out) {

    size_t x = 0;
    size_t nsegs = 0, nallocated = 20;
    struct segment *out = (struct segment *)calloc(nallocated, sizeof(struct segment));
    struct segment test;
    test.nmoves = segment->nmoves;
    
    out[nsegs].moves = (int *)calloc(segment->nmoves, sizeof(int));
    int nout = 0;
    while (x < segment->nmoves) {

        test.moves = segment->moves + x;
        test.nmoves = segment->nmoves - x;
        if (segments_match(&test, subsegment)) {
            if (out[nsegs].nmoves != 0) {
                nsegs++;
                out[nsegs].moves = (int *)calloc(segment->nmoves, sizeof(int));
            }
            x += subsegment->nmoves;
        } else {
            out[nsegs].moves[out[nsegs].nmoves] = segment->moves[x];
            x++;
            out[nsegs].nmoves++;
        }
    }
    nsegs++;
    if (out[nsegs-1].nmoves == 0) { 
        free(out[nsegs-1].moves);
        nsegs--;
    } 
    *nsegments_out = nsegs;
    return out;
}

struct segment *find_segment_types(int *all_segments, size_t nsegments) {
    struct segment main;
    struct segment *results = (struct segment *)calloc(3, sizeof(struct segment));
    struct segment *A = results + 0;
    struct segment *B = results + 1;
    struct segment *C = results + 2;

    main.moves = all_segments;
    main.nmoves = nsegments;
    A->moves = all_segments;
 
    for (A->nmoves = 1; (A->nmoves <= main.nmoves - 2) && (bytes_in_ascii_representation(A) <= 20); A->nmoves++) {
        struct segment *p1 = split_by_subsegment(&main, A, &nsegments);
        struct segment *shortest = shortest_segment_among(p1, nsegments);

        B->moves = shortest->moves;
        for (B->nmoves = 1; (B->nmoves <= shortest->nmoves) && (bytes_in_ascii_representation(B) <= 20); B->nmoves++) {
            struct segment *remaining = (struct segment *)calloc(main.nmoves, sizeof(struct segment));
            size_t nremaining = 0;
            size_t nout;
            for (size_t pi = 0; pi < nsegments; pi++) {
                struct segment *p2 = split_by_subsegment(p1 + pi, B, &nout);
                memcpy(remaining + nremaining, p2, sizeof(struct segment) * nout);
                nremaining += nout;
                free(p2);
            }
            struct segment *C_candidate = shortest_segment_among(remaining, nremaining);
            // Handle the special case where the shortest segment is the true C, but repeated.
            for (size_t sequencelength = 1; sequencelength < C_candidate->nmoves - 1; sequencelength++) {
                
                if (C_candidate->nmoves % sequencelength != 0) continue;

                size_t reps = C_candidate->nmoves / sequencelength, j;
                bool success = true;
                for (size_t k = 0; k < sequencelength; k++) {
                    int value = C_candidate->moves[k];
                    for (j = 1; j < reps && C_candidate->moves[j*sequencelength + k] == value; j++);
                    success = success && (j == reps);
                }
                if (success) C_candidate->nmoves = sequencelength;
            }

            if (bytes_in_ascii_representation(C_candidate) <= 20) {
                bool works = true;
                for (size_t i = 0; i < nremaining; i++) {
                    size_t n;
                    struct segment *o = split_by_subsegment(remaining+i, C_candidate, &n);
                    works = works && (n == 0);
                    free(o);
                }

                C->moves = C_candidate->moves;
                C->nmoves = C_candidate->nmoves;
                free(remaining);
                if (works) {
                    free(p1);
                    return results;
                }
            } else {
                free(remaining);
            }
        }
        free(p1);
    }
    free(results);
    return NULL;
}

char *find_subsegment_sequence(int *all_segments, size_t nsegments, struct segment *subsequences) {
    size_t i = 0;
    char *buffer = (char *)calloc(100,1);
    int n = 0;

    while (i < nsegments) {
        if (n != 0) buffer[n++] = ',';
        for (size_t j = 0; j < 3; j++) {
            struct segment test;
            test.moves = all_segments + i;
            test.nmoves = nsegments - i;
            if (subsequences[j].nmoves <= nsegments - i && segments_match(&test, subsequences + j)) {
                buffer[n++] = 'A' + j;
                i += subsequences[j].nmoves;
                break;
            }
        }
    }
    buffer[n++] = 10;
    buffer[n++] = 0;
    return buffer;
}

#define MAX_NUM_OUTPUTS (100000)
int main(int argc, const char * argv[]) {
    int64_t output[MAX_NUM_OUTPUTS];
//    char *grid[WIDTH*HEIGHT];
    size_t length;
    int64_t *source = load_source_code_from_file(argv[1], &length, 1000);
    struct program *p = init_program_instance(source, length, output);
    p->remaining_inputs = 0;
    run_program_instance_until_halted(p);
    size_t w = 54, h = 65;
    size_t s = 0;
    int64_t x = 0, y = 0;
    enum Direction d = 1;
    for (size_t r = 1; r < (h-1); r++) {
        for (size_t c = 1; c < (w-1); c++) {
            switch ((char)(p->output[r*w+c])) {
                case '#':
                if (((char)(p->output[r*w+c+1])) == '#' &&
                    ((char)(p->output[r*w+c-1])) == '#' &&
                    ((char)(p->output[r*w+c+w])) == '#' &&
                    ((char)(p->output[r*w+c-w])) == '#') {
                    size_t alignment_parameter = r*c;
                    s += alignment_parameter;
                }
                break;
                case '^': x = c; y = r; d = kNorth; break;
                case '>': x = c; y = r; d = kEast; break;
                case 'v': x = c; y = r; d = kSouth; break;
                case '<': x = c; y = r; d = kWest; break;
            }
        }
    }
    printf("Pt 1: %zu\n", s);
    p->output[y*w + x] = '#';
    
    int segments[500];
    size_t nsegments = 0;
    while (1) {
        bool turnleft, turnright;
        switch (d) {
            case kNorth: turnleft = p->output[y*w + x - 1] == '#'; break;
            case kSouth: turnleft = p->output[y*w + x + 1] == '#'; break;
            case kEast: turnleft = p->output[y*w + x - w] == '#'; break;
            case kWest: turnleft = p->output[y*w + x + w] == '#'; break;
        }
        switch (d) {
            case kNorth: turnright = p->output[y*w + x + 1] == '#'; break;
            case kSouth: turnright = p->output[y*w + x - 1] == '#'; break;
            case kEast: turnright = p->output[y*w + x + w] == '#'; break;
            case kWest: turnright = p->output[y*w + x - w] == '#'; break;
        }
        if (!turnleft && !turnright) break;
        d = (d + 1 + (turnleft ? 2 : 0)) % 4;
        size_t l = 0;
        while (p->output[y*w + x] == '#' && (x >= 0 && y >= 0 && x < w && y < h)) {
            switch (d) {
                case kNorth: y--; break;
                case kWest: x--; break;
                case kEast: x++; break;
                case kSouth: y++; break;
            }
            l++;
        }
        switch (d) {
            case kNorth: y++; break;
            case kWest: x++; break;
            case kEast: x--; break;
            case kSouth: y--; break;
        }
        segments[nsegments++] = (turnleft ? -1 : 1) * ((int)(l-1));
    }
    
    struct segment *r = find_segment_types(segments, nsegments);
    char *b = find_subsegment_sequence(segments, nsegments, r);
    int64_t inp[1000];
    size_t aa;
    for (aa = 0; b[aa]; aa++) {
        inp[aa] = b[aa];
    }
    free(b);
    for (size_t j = 0; j < 3; j++) {
        char *b2 = segment_as_buffer(r + j);
        size_t n = strlen(b2);
        for (size_t k = 0; k < n; k++) {
            inp[aa+k] = b2[k];
        }
        aa+=n;
        free(b2);
    }
    inp[aa++] = (int)('n');
    inp[aa++] = 10;
    free_program_instance(p);
    p = init_program_instance(source, length, output);
    p->code[0] = 2;
    p->input = inp;
    p->remaining_inputs = aa;

    run_program_instance_until_halted(p);
    // for (size_t t = 0; t < p->num_outputs; t++) {
    //     printf("%c", (char)(p->output[t]));
    // }

    printf("Pt 2: %lld\n", p->output[p->num_outputs - 1]);
    free_program_instance(p);
    free(source);
    exit(0);
}