Tutorial for Advent of Code 2019 day 22 part 2

Правка en4, от Spheniscine, 2019-12-29 05:45:09

Advent of Code is a website that releases programming puzzles every December from the 1st to the 25th. The puzzles have two parts, and the second part isn't revealed until you solve the first part.

This year, there have been many questions regarding part 2 of day 22, as it involves modular arithmetic in a way that hasn't been seen in previous puzzles there. I have been asked for a tutorial for it on Reddit, but I'm posting it here due to better support for mathematical notation.

Part 2 summary

First off, if you are unfamiliar with modular arithmetic, I encourage you to read my other blog post, Modular Arithmetic for Beginners. The most important thing to understand from there is how the four basic operations (addition, subtraction, multiplication, division) can be redefined to work in modular ($$$\mathbb Z / p \mathbb Z$$$ field) arithmetic. I also recommend you try some of the puzzles linked. The terminology and notations I'll use will also be similar.

It is possible to solve this without explicitly invoking modular arithmetic (see this post for an example) but they basically amount to rediscovering certain properties of modular arithmetic anyway, as such that's the "language" I'll use for this tutorial.

The first thing to notice is that each of the given instructions amount to a transformation on the position of each card. Let $$$m$$$ represent the number of cards in the deck.

  • "deal into new stack" moves cards from position $$$x$$$ to position $$$m - x - 1$$$. We can write this as $$$f(x) = m - x - 1$$$.
  • "cut $$$n$$$" moves cards from position $$$x$$$ to position $$$x - n\ \text{ mod } m$$$ (note how indices "wrap around" to the other side), Thus $$$f(x) = x - n\ \text{ mod } m$$$. Note this also works for the version with negative $$$n$$$.
  • "deal with increment $$$n$$$" moves cards from position $$$x$$$ to position $$$n \cdot x\ \text{ mod } m$$$. Thus, $$$f(x) = n \cdot x\ \text{ mod } m$$$

The next thing to notice is that each transformation can be rewritten in the form of $$$f(x) = ax + b\ \text{ mod } m$$$. This is called a linear congruential function, and forms the basis for linear congruential generators, a simple type of pseudorandom number generator.

  • "deal into new stack": $$$f(x) = -x - 1\ \text{ mod } m$$$, so $$$a = -1, b = -1$$$
  • "cut $$$n$$$: $$$f(x) = x - n\ \text{ mod } m$$$, so $$$a = 1, b = -n$$$
  • "deal with increment $$$n$$$: $$$f(x) = n \cdot x\ \text{ mod } m$$$, so $$$a = n, b = 0$$$

The next step is to see what happens when you compose two arbitrary linear congruential functions $$$f(x) = ax + b\ \text{ mod } m$$$ and $$$g(x) = cx + d\ \text{ mod } m$$$. So what do you get if you evaluate $$$g(f(x))$$$? By substitution:

$$$g(f(x)) = c(ax + b) + d\ \text{ mod } m$$$

As I established in Modular Arithmetic for Beginners, algebra works with modular residues similarly to real numbers, so let's expand:

$$$g(f(x)) = acx + bc + d\ \text{ mod } m$$$

An alternate notation for $$$g(f(x))$$$ is

Теги advent of code, modular arithmetic

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en23 Английский Spheniscine 2020-05-20 05:05:16 327
en22 Английский Spheniscine 2020-04-12 04:35:52 15
en21 Английский Spheniscine 2020-04-12 04:34:21 118
en20 Английский Spheniscine 2020-02-17 14:09:00 2
en19 Английский Spheniscine 2020-02-17 10:08:50 28
en18 Английский Spheniscine 2020-02-17 10:05:52 13
en17 Английский Spheniscine 2020-02-17 10:04:48 333
en16 Английский Spheniscine 2020-02-17 09:54:21 386
en15 Английский Spheniscine 2019-12-31 06:17:05 22
en14 Английский Spheniscine 2019-12-31 06:00:21 58
en13 Английский Spheniscine 2019-12-31 05:32:53 66
en12 Английский Spheniscine 2019-12-31 05:29:35 539 Added an addendum for the matrix interpretation / representation of LCFs
en11 Английский Spheniscine 2019-12-29 12:51:45 92
en10 Английский Spheniscine 2019-12-29 12:47:54 28
en9 Английский Spheniscine 2019-12-29 07:11:55 4844 Tiny change: 'k x + b \Sigma_{i=0}^{k-' -> 'k x + b \Sum_{i=0}^{k-' (published)
en8 Английский Spheniscine 2019-12-29 06:13:37 2
en7 Английский Spheniscine 2019-12-29 06:12:26 41 Tiny change: ' ($f_1\ ; $f_2\ ; $f_3\ ;...$' -> ' ($f_1\ ; f_2\ ; f_3\ ;...$'
en6 Английский Spheniscine 2019-12-29 06:09:41 92 Tiny change: 't compose F into itse' -> 't compose $F$ into itse'
en5 Английский Spheniscine 2019-12-29 06:06:19 1608 Tiny change: 'wo LCFs:\n$(a, b) ' -> 'wo LCFs:\n\n$(a, b) '
en4 Английский Spheniscine 2019-12-29 05:45:09 1667 Tiny change: ' a simple form of a pseudoran' -> ' a simple type of pseudoran'
en3 Английский Spheniscine 2019-12-29 05:21:03 57
en2 Английский Spheniscine 2019-12-29 05:18:49 1026 Tiny change: 'position* 2020.\n</spoil' -> 'position* $2020$.\n</spoil'
en1 Английский Spheniscine 2019-12-29 05:08:56 605 Initial revision (saved to drafts)