#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

char *
destCity(char*** paths, int pathsSize, int* pathsColSize) {
    struct {
        char **data;
        unsigned long size;
        unsigned long cap;
    } froms = {0};
    struct {
        char **data;
        unsigned long size;
        unsigned long cap;
    } tos = {0};

    froms.cap = pathsSize;
    froms.data = calloc(froms.cap, sizeof(*froms.data));

    tos.cap = pathsSize;
    tos.data = calloc(tos.cap, sizeof(*tos.data));

    for ( int i = 0; i < pathsSize; ++i ) {
        froms.data[froms.size++] = paths[i][0];
        tos.data[tos.size++] = paths[i][1];
    }

    char *ret = NULL;
    for ( unsigned long i = 0; i < tos.size; ++i ) {
        bool found = false;
        for ( unsigned long j = 0; j < froms.size; ++j ) {
            if ( strcmp(tos.data[i], froms.data[j]) == 0 ) {
                found = true;
                break;
            }
        }
        if ( ! found ) { ret = tos.data[i]; break; }
    }

    (void) pathsColSize;

    free(tos.data);
    free(froms.data);

    return ret;
}

char *
paths_to_cstr_temp(char ***paths, int pathsSize) {
    static char *data = NULL;
    static unsigned long size = 0;
    static unsigned long cap = 1024;

    if ( data == NULL ) { data = malloc(sizeof(char) * (cap + 1)); }
    size = 0;
    memset(data, 0, cap);

    data[size++] = '[';
    for ( int i = 0; i < pathsSize; ++i ) {
        if ( size + 32 >= cap ) { cap = cap*2; data = realloc(data, cap*2); }

        if ( i > 0 ) { data[size++] = ','; }
        data[size++] = '[';
        char *from = paths[i][0];
        while ( *from != '\0' ) { data[size++] = *from++; }
        data[size++] = ',';
        char *to = paths[i][1];
        while ( *to != '\0' ) { data[size++] = *to++; }
        data[size++] = ']';
    }
    data[size++] = ']';
    data[size++] = '\0';

    return data;
}

void
r(char ***paths, int pathsSize, char *exp)
{
    printf("destCity(%s, %d) = %s | exp: %s\n",
           paths_to_cstr_temp(paths, pathsSize),
           pathsSize,
           destCity(paths, pathsSize, NULL),
           exp);
}

int
main(void)
{

    char *paths11[2] = {"London","New York"};
    char *paths12[2] = {"New York","Lima"};
    char *paths13[2] = {"Lima","Sao Paulo"};
    char **paths1[] = {paths11, paths12, paths13};
    r(paths1, 3, "Sao Paulo");

    char *paths21[2] = {"B","C"};
    char *paths22[2] = {"D","B"};
    char *paths23[2] = {"C","A"};
    char **paths2[] = {paths21, paths22, paths23};
    r(paths2, 3, "A");

    char *paths31[2] = {"A","Z"};
    char **paths3[] = {paths31};
    r(paths3, 1, "Z");

    return 0;
}