aoc/year2015/
day25.rs

1//! # Let It Snow
2//!
3//! There are two parts to solving this problem.
4//!
5//! The first is converting the row and column to an *zero based* index. Using the example of
6//! the 12th code at row 4 column 2:
7//!
8//! ```none
9//!        | 1   2   3   4   5   6
10//!     ---+---+---+---+---+---+---+
11//!      1 |  1   3   6  10  15  21
12//!      2 |  2   5   9  14  20
13//!      3 |  4   8  13  19
14//!      4 |  7  12  18
15//!      5 | 11  17
16//!      6 | 16
17//! ```
18//!
19//! First we observe that the numbers on the top row are the
20//! [triangular numbers](https://en.wikipedia.org/wiki/Triangular_number) that can be calculated
21//! with the formula `(n * (n + 1)) / 2` for the `nth` number.
22//!
23//! Starting at the chosen number 12 and moving diagonally upwards to the right we intersect
24//! the top row at column `column + row - 1 = 2 + 4 - 1 = 5`. This gives the triangular number
25//! `5 * (5 + 1) / 2 = 15`. Then we count backwards by `row` elements to get the one less
26//! zero based based index `15 - 4 = 11`.
27//!
28//! The second part is realizing that the description of the code generation is
29//! [modular exponentiation](https://en.wikipedia.org/wiki/Modular_exponentiation). The exponent
30//! of the first code is zero, which is the reason for using a zero based index.
31use crate::util::iter::*;
32use crate::util::math::*;
33use crate::util::parse::*;
34
35type Input = [u64; 2];
36
37pub fn parse(input: &str) -> Input {
38    input.iter_unsigned().chunk::<2>().next().unwrap()
39}
40
41pub fn part1(input: &Input) -> u64 {
42    let [row, column] = *input;
43
44    let n = column + row - 1;
45    let triangle = (n * (n + 1)) / 2;
46    let index = triangle - row;
47
48    (20151125 * 252533.mod_pow(index, 33554393)) % 33554393
49}
50
51pub fn part2(_input: &Input) -> &'static str {
52    "n/a"
53}