aoc_2021_day12_fast.c

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <sys/time.h>

/*
 * Maximum number of nodes in the graph, may need to be increased for
 * more complex maps
 */
#define MAXMAP 20

/*
 * Setup:-
 * 1. Read in the input, storing the node names in the `names` array.
 *      The index to the `names` array is how that node is referenced from here on in
 *      Also store the start and end node indices in the corresponding variable names
 *      `namect` holds the next free `names` slot (and therefore the number of nodes)
 * 2. For each route A->B we store this in the `newmap` array.
 *      The array slice corresponding to node A contains a list of destinations that
 *      can be reached from that node, these are stored sequentially in the array.
 *      The number of destinations for each node is stored in the `newnos` array.
 *      All routes are bi-directional except those that have `start` as a destination.
 * This all keeps the number of iterations at each recursion to a minimum
 * 3. We also populate a `small` array if the node is a small cave (i.e. one that can
 *      not be visited an unlimited number of times.
 */
char *names[MAXMAP];
uint8_t newmap[MAXMAP][MAXMAP];
uint8_t newnos[MAXMAP];
uint32_t namect=0;
uint8_t small[MAXMAP];
uint32_t start=999;
uint32_t end=999;
uint8_t visited[MAXMAP];
uint32_t p1=0,p2=0;

uint8_t nos( char *s ) {
        uint32_t ct=0;
        /* Check if we haven't already added this name, return index if we have */
        while( ct < namect ) {
                if( strcmp( s, names[ct] ) == 0 ) {
                        return( ct );
                }
                ct++;
        }
        /* Not already added, this will be a new one */
        if( namect == MAXMAP ) {
                printf( "ARGH, increase MAXMAP\n" );
                exit(0);
        }
        if( strcmp( s, "start" ) == 0 ) {
                start=namect; /* Keep track of start */
        }
        if( strcmp( s, "end" ) == 0 ) {
                end=namect; /* Keep track of end */
        }
        names[namect]=strdup( s );      /* ASSUME it never fails */
        if( islower( s[0] ) ) {         /* ASSUME small cave if just the first character is lower case */
                small[namect]=1;        /* Keep track of smaller caves */
        }
        namect++;
        /* Return the last added namect value */
        return( namect-1 );
}

void addroute( uint8_t f, uint8_t t ) {
        if( t != start ) {      /* Don't allow revisiting the start */
                newmap[f][ newnos[f] ]=t;
                newnos[f]++;
        }
        if( f != start ) {      /* Don't allow revisiting the start */
                newmap[t][ newnos[t] ]=f;
                newnos[t]++;
        }
}

/*
 * Main algorithm:-
 *
 * We use a small `visited` array to keep track of how many times we have visited
 * any of the small caves.
 *
 * 1. Given a current location `where` and a flag to say whether we have used our
 *      one chance of visiting a small cave twice.
 * 2. If this is a small cave then increment the number of times we have visited it
 *      This is undone later in step 4 
 * 3. Loop through the possible destinations from current node.
 *      If the possible destination is the end then:
 *              Increment the score for part1 if we haven't visited a small node twice to get here
 *              Increment the score for part2 regardless
 *              Continue the loop of destinations
 *      If we have visited this possible destination before and we have already used
 *              our visit twice chance then skip this one and loop again
 *      Otherwise we know we're allowed to try `poss` as the next hop
 *      If we've visited it before then recurse with `poss` as the new destination and also set
 *              the `vtwice` flag
 *      If we haven't viisted it before we can recurse with `poss` and the existing `vtwice` flag value
 * 4. If this was a small cave then decrement the number of times we have visited it.
 *      This undoes the increment from step 2.
 *
 * Note that this algorithm obtains the answers for both parts 1 and 2 at the same time. Getting
 * the answer for part 2 will cover all of the routes for part1 and we can easily keep track of
 * whether a node has been visited twice in order to know whether the route satifies the stricter
 * requirements for part 1.
 */

void go( uint32_t where, uint32_t vtwice ) {
        uint32_t tmp;
        if( small[where] ) {
                visited[where]++;
        }
        tmp=0;
        while( tmp < newnos[where] ) {
                uint32_t poss;
                poss=newmap[where][tmp];
                if( poss == end ) {
                        if( !vtwice ) {
                                p1++;
                        }
                        p2++;
                        tmp++;
                        continue;
                }
                if( visited[poss] && vtwice ) {
                        tmp++;
                        continue;
                }
                if( visited[poss] ) {
                        go( poss, 1 );
                } else {
                        go( poss, vtwice );
                }
                tmp++;
        }
        if( small[where] ) {
                visited[where]--;
        }
}


int main( void )
{
        uint32_t tmp;
        char lbuf[512];
        struct timeval tv_s, tv_e;      /* Timing */

        gettimeofday( &tv_s, NULL);     /* Timing */

        bzero( visited, sizeof(visited) );
        bzero( names, sizeof(names) );
        bzero( small, sizeof(small) );
        bzero( newmap, sizeof(newmap) );
        bzero( newnos, sizeof(newnos) );

        /*
         * Parse input:-
         *      Read a line, strip off CR, find and NUL hyphen
         *      Find (or create) `names` indices for start/dest
         *      Add a route between the two
         */
        while( 1 ) {
                uint32_t nf,nt;
                char *hyp,*crlf,*s;
                s=fgets( lbuf, 511, stdin );
                if( s == NULL ) {       /* End of input */
                        break;
                }
                crlf=strchr( lbuf, '\n' );
                if( crlf ) { *crlf=0; }
                hyp=strchr( lbuf, '-' );
                if( !hyp ) {
                        printf( "ARGH - no hyp\n" );
                        return(1);
                }
                *hyp=0;
                hyp++;
                nf=nos( lbuf );
                nt=nos( hyp );
                addroute( nf, nt );
        }

        gettimeofday( &tv_e, NULL);     /* Timing */
        printf( "setup: %luusec\n", (1000000*(tv_e.tv_sec-tv_s.tv_sec))+tv_e.tv_usec-tv_s.tv_usec );

        /*
         * For each possible destination from the start recurse with that option
         * `vtwice` argument is 0 to begin with as we haven't visited a small node twice yet
         */
        tmp=0;
        while( tmp < newnos[start] ) {
                go( newmap[start][tmp], 0 );
                tmp++;
        }
        printf( "part1: %u\n", p1 );
        printf( "part2: %u\n", p2 );

        gettimeofday( &tv_e, NULL);     /* Timing */
        printf( "end: %luusec\n", (1000000*(tv_e.tv_sec-tv_s.tv_sec))+tv_e.tv_usec-tv_s.tv_usec );

        return( 0 );
}