~quf/computers-are-fast-2020

computers-are-fast-2020/src/23.c -rw-r--r-- 2.7 KiB
6f56515eLukas Himbert Draw the rest of the fine owl. 1 year, 7 months ago
                                                                                
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <stdio.h>
#include <ctype.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

void prep(uint_least32_t **next, const uint_least32_t *numbers, size_t n_numbers, size_t pad) {
  *next = calloc((pad > n_numbers)? pad : n_numbers, sizeof **next);
  if (*next == NULL) {
    fprintf(stderr, "Allocation Error: %s\n", strerror(errno));
    exit(EXIT_FAILURE);
  }
  for (size_t i = 0; i < n_numbers; ++i) {
    (*next)[numbers[i] - 1] = numbers[(i + 1) % n_numbers] - 1;
  }
  if (pad > n_numbers) {
    (*next)[numbers[n_numbers - 1] - 1] = n_numbers;
    for (size_t i = n_numbers; i < pad - 1; ++i) {
      (*next)[i] = i + 1;
    }
    (*next)[pad - 1] = numbers[0] - 1;
  }
}

void run(uint_least32_t *next, size_t next_len, size_t current_cup, size_t runs) {
  for (size_t i = 0; i < runs; ++i) {
    /* pick up cards */
    uint_least32_t p1 = next[current_cup];
    uint_least32_t p2 = next[p1];
    uint_least32_t p3 = next[p2];
    next[current_cup] = next[p3];
    /* find target cup */
    size_t target = current_cup;
    do {
      target = (target > 0) ? target - 1 : next_len - 1;
    } while ((target == p1) || (target == p2) || (target == p3));
    /* insert cups */
    next[p3] = next[target];
    next[target] = p1;
    current_cup = next[current_cup];
  }
}

void get_first(const uint_least32_t *next, uint_least32_t *ret, size_t n) {
  size_t cur = 0;
  for (size_t i = 0; i < n; ++i) {
    cur = (size_t) next[cur];
    ret[i] = (uint_least32_t) cur + 1;
  }
}

void part1(const uint_least32_t *numbers, size_t n_numbers) {
  uint_least32_t *next;
  prep(&next, numbers, n_numbers, 0);
  run(next, n_numbers, numbers[0]-1, 100);
  uint_least32_t x[8];
  get_first(next, x, sizeof x / sizeof *x);
  for (size_t i = 0; i < sizeof x / sizeof *x; ++i) {
    putchar(x[i] + '0');
  }
  putchar('\n');
  free(next);
}

void part2(const uint_least32_t *numbers, size_t n_numbers) {
  uint_least32_t *next;
  size_t pad = 1000000;
  prep(&next, numbers, n_numbers, pad);
  run(next, pad, numbers[0]-1, 10000000);
  uint_least32_t x[2];
  get_first(next, x, sizeof x / sizeof *x);
  unsigned long long res = 1;
  for (size_t i = 0; i < sizeof x / sizeof *x; ++i) {
    res *= (unsigned long long) x[i];
  }
  printf("%llu\n", res);
  free(next);
}

int main(void) {
  uint_least32_t numbers[20] = { 0, };
  size_t n_numbers = 0;
  int c;
  while ((c = getchar()) != EOF) {
    if (isdigit(c) && n_numbers < sizeof numbers / sizeof *numbers) {
      numbers[n_numbers++] = (int_least32_t) (c - '0');
    }
  }
  if (ferror(stdin) || !feof(stdin)) {
    fprintf(stderr, "Input error: %s.\n", strerror(errno));
    return 1;
  }

  part1(numbers, n_numbers);
  part2(numbers, n_numbers);
  return 0;
}