commit 9c4f72ce260acc6398632cd9e396a54b0e494151
parent 49318906acb244e5ca4038d75ff383941efef9d4
Author: Louis Burda <quent.burda@gmail.com>
Date: Mon, 3 Apr 2023 10:19:35 -0400
Add day 22
Diffstat:
| A | 22/info.mk | | | 3 | +++ |
| A | 22/input | | | 101 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 22/part1 | | | 166 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 22/part1.c | | | 130 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 22/part2 | | | 22 | ++++++++++++++++++++++ |
| A | 22/part2.c | | | 100 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 22/test1 | | | 3 | +++ |
| A | 22/test2 | | | 3 | +++ |
| A | 22/test3 | | | 3 | +++ |
| A | 22/test4 | | | 10 | ++++++++++ |
| A | 22/test5 | | | 6 | ++++++ |
11 files changed, 547 insertions(+), 0 deletions(-)
diff --git a/22/info.mk b/22/info.mk
@@ -0,0 +1,3 @@
+22_SRC = 22/part1.c 22/part2.c common/main.c common/aoc.c common/util.c
+22_SRC += lib/liballoc/build/liballoc.a lib/libdvec/build/libdvec.a
+22_HDR = common/aoc.h common/util.h
diff --git a/22/input b/22/input
@@ -0,0 +1,101 @@
+deal with increment 13
+cut 5485
+deal with increment 50
+cut 9877
+deal with increment 8
+cut 4323
+deal with increment 6
+cut 2478
+deal with increment 32
+cut 299
+deal with increment 72
+cut 5108
+deal with increment 10
+cut -1774
+deal with increment 24
+cut -8840
+deal with increment 34
+cut 7488
+deal with increment 74
+cut 1851
+deal into new stack
+deal with increment 60
+cut -6016
+deal into new stack
+deal with increment 49
+cut -8082
+deal with increment 54
+deal into new stack
+deal with increment 15
+deal into new stack
+deal with increment 38
+cut -4112
+deal with increment 13
+deal into new stack
+cut 4372
+deal into new stack
+deal with increment 75
+cut -5702
+deal with increment 65
+cut 4979
+deal with increment 39
+cut 1967
+deal with increment 55
+cut 8554
+deal with increment 50
+deal into new stack
+cut 1337
+deal with increment 53
+cut 426
+deal with increment 7
+cut 8947
+deal with increment 58
+cut 8826
+deal with increment 52
+cut 6167
+deal with increment 18
+cut -4305
+deal with increment 20
+cut 7168
+deal with increment 10
+cut 422
+deal with increment 41
+cut -1601
+deal with increment 72
+deal into new stack
+deal with increment 27
+cut -3921
+deal with increment 47
+cut 4024
+deal into new stack
+cut 7800
+deal with increment 10
+cut -3742
+deal with increment 35
+deal into new stack
+deal with increment 72
+cut 7456
+deal with increment 29
+cut -6731
+deal with increment 57
+cut -6162
+deal into new stack
+deal with increment 26
+cut -4817
+deal with increment 48
+cut 9420
+deal into new stack
+deal with increment 8
+cut -7408
+deal into new stack
+cut -3479
+deal with increment 31
+cut 5246
+deal with increment 12
+cut -9275
+deal with increment 37
+cut -4512
+deal with increment 15
+cut -8511
+deal with increment 8
+
diff --git a/22/part1 b/22/part1
@@ -0,0 +1,166 @@
+--- Day 22: Slam Shuffle ---
+
+There isn't much to do while you wait for the droids to repair your ship. At least you're drifting
+in the right direction. You decide to practice a new card shuffle you've been working on.
+
+Digging through the ship's storage, you find a deck of space cards! Just like any deck of space
+cards, there are 10007 cards in the deck numbered 0 through 10006. The deck must be new - they're
+still in factory order, with 0 on the top, then 1, then 2, and so on, all the way through to 10006
+on the bottom.
+
+You've been practicing three different techniques that you use while shuffling. Suppose you have a
+deck of only 10 cards (numbered 0 through 9):
+
+To deal into new stack, create a new stack of cards by dealing the top card of the deck onto the top
+of the new stack repeatedly until you run out of cards:
+
+Top Bottom
+0 1 2 3 4 5 6 7 8 9 Your deck
+ New stack
+
+ 1 2 3 4 5 6 7 8 9 Your deck
+ 0 New stack
+
+ 2 3 4 5 6 7 8 9 Your deck
+ 1 0 New stack
+
+ 3 4 5 6 7 8 9 Your deck
+ 2 1 0 New stack
+
+Several steps later...
+
+ 9 Your deck
+ 8 7 6 5 4 3 2 1 0 New stack
+
+ Your deck
+9 8 7 6 5 4 3 2 1 0 New stack
+
+Finally, pick up the new stack you've just created and use it as the deck for the next technique.
+
+To cut N cards, take the top N cards off the top of the deck and move them as a single unit to the
+bottom of the deck, retaining their order. For example, to cut 3:
+
+Top Bottom
+0 1 2 3 4 5 6 7 8 9 Your deck
+
+ 3 4 5 6 7 8 9 Your deck
+0 1 2 Cut cards
+
+3 4 5 6 7 8 9 Your deck
+ 0 1 2 Cut cards
+
+3 4 5 6 7 8 9 0 1 2 Your deck
+
+You've also been getting pretty good at a version of this technique where N is negative! In that
+case, cut (the absolute value of) N cards from the bottom of the deck onto the top. For example, to
+cut -4:
+
+Top Bottom
+0 1 2 3 4 5 6 7 8 9 Your deck
+
+0 1 2 3 4 5 Your deck
+ 6 7 8 9 Cut cards
+
+ 0 1 2 3 4 5 Your deck
+6 7 8 9 Cut cards
+
+6 7 8 9 0 1 2 3 4 5 Your deck
+
+To deal with increment N, start by clearing enough space on your table to lay out all of the cards
+individually in a long line. Deal the top card into the leftmost position. Then, move N positions
+to the right and deal the next card there. If you would move into a position past the end of the
+space on your table, wrap around and keep counting from the leftmost card again. Continue this
+process until you run out of cards.
+
+For example, to deal with increment 3:
+
+
+0 1 2 3 4 5 6 7 8 9 Your deck
+. . . . . . . . . . Space on table
+^ Current position
+
+Deal the top card to the current position:
+
+ 1 2 3 4 5 6 7 8 9 Your deck
+0 . . . . . . . . . Space on table
+^ Current position
+
+Move the current position right 3:
+
+ 1 2 3 4 5 6 7 8 9 Your deck
+0 . . . . . . . . . Space on table
+ ^ Current position
+
+Deal the top card:
+
+ 2 3 4 5 6 7 8 9 Your deck
+0 . . 1 . . . . . . Space on table
+ ^ Current position
+
+Move right 3 and deal:
+
+ 3 4 5 6 7 8 9 Your deck
+0 . . 1 . . 2 . . . Space on table
+ ^ Current position
+
+Move right 3 and deal:
+
+ 4 5 6 7 8 9 Your deck
+0 . . 1 . . 2 . . 3 Space on table
+ ^ Current position
+
+Move right 3, wrapping around, and deal:
+
+ 5 6 7 8 9 Your deck
+0 . 4 1 . . 2 . . 3 Space on table
+ ^ Current position
+
+And so on:
+
+0 7 4 1 8 5 2 9 6 3 Space on table
+
+Positions on the table which already contain cards are still counted; they're not skipped. Of
+course, this technique is carefully designed so it will never put two cards in the same position or
+leave a position empty.
+
+Finally, collect the cards on the table so that the leftmost card ends up at the top of your deck,
+the card to its right ends up just below the top card, and so on, until the rightmost card ends up
+at the bottom of the deck.
+
+The complete shuffle process (your puzzle input) consists of applying many of these techniques.
+Here are some examples that combine techniques; they all start with a factory order deck of 10
+cards:
+
+deal with increment 7
+deal into new stack
+deal into new stack
+Result: 0 3 6 9 2 5 8 1 4 7
+
+cut 6
+deal with increment 7
+deal into new stack
+Result: 3 0 7 4 1 8 5 2 9 6
+
+deal with increment 7
+deal with increment 9
+cut -2
+Result: 6 3 0 7 4 1 8 5 2 9
+
+deal into new stack
+cut -2
+deal with increment 7
+cut 8
+cut -4
+deal with increment 7
+cut 3
+deal with increment 9
+deal with increment 3
+cut -1
+Result: 9 2 5 8 1 4 7 0 3 6
+
+Positions within the deck count from 0 at the top, then 1 for the card immediately below the top
+card, and so on to the bottom. (That is, cards start in the position matching their number.)
+
+After shuffling your factory order deck of 10007 cards, what is the position of card 2019?
+
+
diff --git a/22/part1.c b/22/part1.c
@@ -0,0 +1,130 @@
+#include "allocator.h"
+#include "aoc.h"
+#include "dvec_s.h"
+#include "util.h"
+
+#include <assert.h>
+#include <stdlib.h>
+
+static void
+deck_cut(struct dvec *deck, struct dvec *table, ssize_t in)
+{
+ int *src, *dst;
+ size_t i, split, n;
+
+ n = deck->len;
+ split = in < 0 ? (size_t) ((ssize_t) deck->len + in) : (size_t) in;
+ src = deck->data;
+ dst = table->data;
+
+ for (i = 0; i < split; i++)
+ dst[i + n - split] = src[i];
+ for (i = split; i < n; i++)
+ dst[i - split] = src[i];
+
+ dvec_swap(deck, table);
+}
+
+static void
+deal_increment(struct dvec *deck, struct dvec *table, size_t inc)
+{
+ int *src, *dst;
+ size_t i, n, p;
+
+ n = deck->len;
+ src = deck->data;
+ dst = table->data;
+
+ p = 0;
+ for (i = 0; i < n; i++) {
+ dst[p] = src[i];
+ p = (p + inc) % n;
+ }
+
+ dvec_swap(deck, table);
+}
+
+static void
+deal_new_stack(struct dvec *deck, struct dvec *table)
+{
+ int *src, *dst;
+ size_t i, n;
+
+ n = deck->len - 1;
+ src = deck->data;
+ dst = table->data;
+
+ for (i = 0; i <= n; i++)
+ dst[n - i] = src[i];
+
+ dvec_swap(deck, table);
+}
+
+static size_t
+find_card(struct dvec *deck, int card)
+{
+ int *data;
+ size_t i, n;
+
+ n = deck->len;
+ data = deck->data;
+ for (i = 0; i < n; i++) {
+ if (data[i] == card)
+ return i;
+ }
+ return 0;
+}
+
+void
+part1(void)
+{
+ char line[256];
+ const char *lpos, *lend;
+ struct dvec deck, table;
+ size_t i, count;
+ size_t answer;
+ ssize_t val;
+ int target;
+ int *data;
+
+ if (!strcmp(aoc.inputfile, "input")) {
+ count = 10007;
+ target = 2019;
+ } else {
+ count = 10;
+ target = 9;
+ }
+
+ dvec_init(&deck, sizeof(int), count, &stdlib_strict_heap_allocator);
+ dvec_init(&table, sizeof(int), count, &stdlib_strict_heap_allocator);
+
+ dvec_add_slots(&deck, count);
+ dvec_add_slots(&table, count);
+ data = deck.data;
+ for (i = 0; i < count; i++)
+ data[i] = (int) i;
+
+ lpos = aoc.input;
+ lend = lpos + aoc.input_size;
+ while (readtok(line, sizeof(line), '\n', &lpos, lend)) {
+ if (sscanf(line, "deal with increment %li", &val) == 1) {
+ deal_increment(&deck, &table, (size_t) val);
+ } else if (sscanf(line, "cut %li", &val) == 1) {
+ deck_cut(&deck, &table, val);
+ } else if (!strcmp(line, "deal into new stack")) {
+ deal_new_stack(&deck, &table);
+ } else if (strspn(line, " \n\r\t\v") == strlen(line)) {
+ continue;
+ } else {
+ assert(false);
+ }
+ aoc_debug("%i pos: %lu\n", target, find_card(&deck, target));
+ }
+
+ answer = find_card(&deck, target);
+ aoc.answer = aprintf("%lu", answer);
+ aoc.solution = "7171";
+
+ dvec_deinit(&table);
+ dvec_deinit(&deck);
+}
diff --git a/22/part2 b/22/part2
@@ -0,0 +1,22 @@
+--- Part Two ---
+
+After a while, you realize your shuffling skill won't improve much more with merely a single deck of
+cards. You ask every 3D printer on the ship to make you some more cards while you check on the ship
+repairs. While reviewing the work the droids have finished so far, you think you see Halley's Comet
+fly past!
+
+When you get back, you discover that the 3D printers have combined their power to create for you a
+single, giant, brand new, factory order deck of 119315717514047 space cards.
+
+Finally, a deck of cards worthy of shuffling!
+
+You decide to apply your complete shuffle process (your puzzle input) to the deck 101741582076661
+times in a row.
+
+You'll need to be careful, though - one wrong move with this many cards and you might overflow your
+entire ship!
+
+After shuffling your new, giant, factory order deck that many times, what number is on the card that
+ends up in position 2020?
+
+
diff --git a/22/part2.c b/22/part2.c
@@ -0,0 +1,100 @@
+#include "allocator.h"
+#include "aoc.h"
+#include "dvec_s.h"
+#include "util.h"
+
+#include <assert.h>
+#include <stddef.h>
+#include <stdlib.h>
+
+size_t
+imul(size_t a, size_t b, size_t n)
+{
+ size_t i, out;
+
+ out = 0;
+ for (i = 0; i < sizeof(size_t) * 8; i++, b <<= 1) {
+ out = (2 * out) % n;
+ if (b & (1ULL << 63))
+ out = (out + a) % n;
+ }
+
+ return out;
+}
+
+size_t
+ipow(size_t a, size_t b, size_t n)
+{
+ size_t i, out;
+
+ out = 1;
+ for (i = 0; i < sizeof(size_t) * 8; i++, b <<= 1) {
+ out = imul(out, out, n);
+ if (b & (1ULL << 63))
+ out = imul(out, a, n);
+ }
+
+ return out;
+}
+
+size_t
+modinv(size_t a, size_t n)
+{
+ return ipow(a, n - 2, n);
+}
+
+void
+part2(void)
+{
+ char line[256];
+ const char *lpos, *lend;
+ size_t answer;
+ size_t count;
+ size_t times;
+ size_t target;
+ ssize_t sval;
+ size_t mul, off;
+ size_t _mul, _off;
+ size_t val;
+
+ times = 101741582076661;
+ count = 119315717514047;
+ target = 2020;
+
+ /* reduce operations to a single multiplication and
+ * addition under modulus 'count' */
+ mul = 1;
+ off = 0;
+ lpos = aoc.input;
+ lend = lpos + aoc.input_size;
+ while (readtok(line, sizeof(line), '\n', &lpos, lend)) {
+ if (sscanf(line, "deal with increment %lu", &val) == 1) {
+ /* multiplication : pos = val * pos */
+ _mul = val;
+ _off = 0;
+ } else if (sscanf(line, "cut %li", &sval) == 1) {
+ /* addition : pos = pos + val */
+ _mul = 1;
+ _off = ((size_t) ((ssize_t) count - sval)) % count;
+ } else if (!strcmp(line, "deal into new stack")) {
+ /* invert : pos = - pos + n - 1 */
+ _mul = count - 1;
+ _off = count - 1;
+ } else if (strspn(line, " \n\r\t\v") == strlen(line)) {
+ continue;
+ } else {
+ assert(false);
+ }
+ mul = imul(mul, _mul, count);
+ off = (imul(off, _mul, count) + _off) % count;
+ }
+
+ /* apply multiplication and addition 'times' times.. */
+ val = (ipow(mul, times, count) + count - 1) % count;
+ val = imul(val, modinv(mul + count - 1, count), count);
+ off = imul(off, val, count); /* b' = b * ((a^n - 1) / (a - 1)) */
+ mul = ipow(mul, times, count); /* a' = a^n */
+
+ answer = imul((target + count - off) % count, modinv(mul, count), count);
+ aoc.answer = aprintf("%lu", answer);
+}
diff --git a/22/test1 b/22/test1
@@ -0,0 +1,3 @@
+deal with increment 7
+deal into new stack
+deal into new stack
diff --git a/22/test2 b/22/test2
@@ -0,0 +1,3 @@
+cut 6
+deal with increment 7
+deal into new stack
diff --git a/22/test3 b/22/test3
@@ -0,0 +1,3 @@
+deal with increment 7
+deal with increment 9
+cut -2
diff --git a/22/test4 b/22/test4
@@ -0,0 +1,10 @@
+deal into new stack
+cut -2
+deal with increment 7
+cut 8
+cut -4
+deal with increment 7
+cut 3
+deal with increment 9
+deal with increment 3
+cut -1
diff --git a/22/test5 b/22/test5
@@ -0,0 +1,6 @@
+cut 6
+deal with increment 7
+deal into new stack
+cut 6
+deal with increment 7
+deal into new stack
