Time to relax a little with enormous decks of space cards.
Day 22 - The Problem
Now that our droids are happily fixing our hull problem...
For further actions, you may consider blocking this person and/or reporting abuse
My solution in Rust
github : github.com/coolshaurya/advent_of_c...
In part 2, I tried to only change the index while shuffling, but even with Rust and doing that its impossible to shuffle it some 15-digit number of times. Well, not impossible, but it will take 1000+ hours = 42+ days of continuous running and may even cause your computer to hang/freeze.
Can't see any other way to do it so seeing @jbristow 's spoilers and solution.
I take no shame in reading a few lisp solutions to spoil my answer. With every year, I find a new way of looking at data that uncovers new possible "cheats".
Just like my favorite solution to the sum of squares problem (the sum of the squares from 1 to n):
m * (m + 1) * (2*m + 1) / 6
Didn't know about this equation. Also you may have accidentally written
m
instead ofn
in the formula :) .Whoops! The notes I have it in mark it as ‘partial sum(n2) for 1 to m = ...` (copied from wolfram alpha)
Kotlin solution for part 1.
Fairly straightforward, but completely useless for part 2.
Ok, this is the first one I thought was unfair.
The answer to part 2 requires you to know (or to be able to find) a lot of set theory.
Spoilers after my kotlin code:
Ok, so... There's a thing called an "inverse mod" that only works on relatively prime numbers.
Additionally, all of the three shuffling techniques can be expressed as an index offset and the number of mod actions performed.
A cut adds an offset and a single mod (think of applying the size of the cut to the indexes and then just pulling the new list from x = 0... offset of n, mod of 1)
A deal into n stacks shuffle just multiplies the index by n and then you scoop up the values in order. This is a mod shift of n. Trust me.
A deal into new stack goes backwards one, and flips the mod direction of our stack. (-1,-1)
so, any given index can be extracted.
Sample 1:
(7,0)->(-1,-1)->(-1,-1)
becomes(-7,-7)->(-1,-1)
which becomes(7,0)
=> Every time through, the value of a given starting index changes byi*7%cards
.Sample 2:
(1,-6),(7,0),(-1,-1)
->(7,-6),(-1,-1)
->(-7,-3)
->(-7i-3) % cards
Now, the problem here is going backwards, unrolling this. That's where inverse mod comes in, and makes this problem not actually work with non-relatively prime numbers. After n shuffles of c cards, that multiplier will be
(-7^n % c)
... unfortunately, the addition part is(mod_a * offset_b + offset_a) % c
, which is hard to write here as it's kind of a series of functions.Anyway, I'm not 100% sure I really understand it, but maybe someone mathier can correct what I'm saying.