#include int main(int argc, char *argv[]) { /* The Elves play this game by taking turns arranging the marbles in * a circle according to very particular rules. */ #define MAX_ELVES 1000 static long score[MAX_ELVES] = {0}; long winning_score = 0; int elf, num_elves, winner; #define MAX_MARBLES 10000000 static struct marble { struct marble *ccw, *cw; int value; } stock[MAX_MARBLES]; struct marble *current; int next, last; if ( argc < 3 || sscanf(argv[1], "%d", &num_elves) != 1 || num_elves > MAX_ELVES || sscanf(argv[2], "%d", &last) != 1 || last >= MAX_MARBLES ) return 1; /* The marbles are numbered starting with 0 and increasing by 1 * until every marble has a number. */ for (int i = 0; i <= last; ++i) { stock[i].value = i; } next = 0; /* First, the marble numbered 0 is placed in the circle. * At this point, while it contains only a single marble, it is * still a circle: the marble is both clockwise from itself and * counter-clockwise from itself. This marble is designated the * current marble. */ current = &stock[next++]; current->ccw = current->cw = current; /* Then, each Elf takes a turn... */ for (;;) for (elf = 0; elf < num_elves; ++elf) { if (0) { struct marble *p = current; printf("%d: ", elf); do { printf("%d ", p->value); p = p->cw; } while (p != current); putchar('\n'); } /* ...placing the lowest-numbered remaining marble * into the circle between the marbles that are 1 and * 2 marbles clockwise of the current marble. (When * the circle is large enough, this means that there * is one marble between the marble that was just * placed and the current marble.) The marble that * was just placed then becomes the current marble. * * However, if the marble that is about to be placed * has a number which is a multiple of 23, something * entirely different happens. */ if (stock[next].value % 23) { struct marble *ccw, *cw, *placed = &stock[next++]; ccw = current->cw; cw = ccw->cw; placed->ccw = ccw; placed->cw = cw; ccw->cw = cw->ccw = current = placed; } else { /* First, the current player keeps the marble * they would have placed, adding it to their * score. */ score[elf] += stock[next++].value; /* In addition, the marble 7 marbles counter- * clockwise from the current marble is removed * from the circle and also added to the * current player's score. The marble located * immediately clockwise of the marble that was * removed becomes the new current marble. */ { struct marble *ccw, *removed; current = current->ccw->ccw->ccw->ccw->ccw->ccw; removed = current->ccw; score[elf] += removed->value; ccw = removed->ccw; ccw->cw = current; current->ccw = ccw; } /* The goal is to be the player with the highest score... */ if (score[elf] > winning_score) { winning_score = score[winner = elf]; if (0) { printf("%d: %ld\n", winner, winning_score); } } } /* ...after the last marble is used up. */ if (next > last) { printf("%ld\n", winning_score); return 0; } } }