Advent of Code 2019 Solution Megathread - Day 22: Slam Shuffle

Time to relax a little with enormous decks of space cards.

Day 22 - The Problem

Now that our droids are happily fixing our hull problems, we've got some time on our hands. Luckily, we're able to indulge in our favorite hobby: shuffling space cards.

Part 1 has us implementing a basic solution for shuffling 10007 cards in our fine-tuned method.

Unfortunately, we aren't happy with just shuffling the standard deck of cards. No, we need to deal with a very large number of cards being shuffled a very large number of times. Part 2 will probably require we find a way to cheat our way through!

Ongoing Meta

Dev.to List of Leaderboards

• 120635-5c140b9a - provided by Linda Thompson

If you were part of Ryan Palo's leaderboard last year, you're still a member of that!

If you want me to add your leaderboard code to this page, reply to one of these posts and/or send me a DM containing your code and any theming or notes you’d like me to add. (You can find your private leaderboard code on your "Private Leaderboard" page.)

I'll edit in any leaderboards that people want to post, along with any description for the kinds of people you want to have on it. (My leaderboard is being used as my office's leaderboard.) And if I get something wrong, please call me out or message me and I’ll fix it ASAP.

There's no limit to the number of leaderboards you can join, so there's no problem belonging to a "Beginner" and a language specific one if you want.

Comments

[Shaurya]

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.

extern crate regex;
extern crate utils;
use regex::Regex;
use utils::utils::read_input;

// 119_315_717_514_047

#[derive(Debug, Clone, Copy)]
enum Change {
    Reverse,
    Cut(isize),
    Deal(usize),
}

fn parse_input(raw: String) -> Vec<Change> {
    let REVERSE_RE: Regex = Regex::new(r"deal into new stack").unwrap();
    let CUT_RE: Regex = Regex::new(r"cut\s([-01234567890]+)").unwrap();
    let DEAL_RE: Regex = Regex::new(r"deal with increment\s([01234567890]+)").unwrap();

    raw.lines()
        .map(|val| {
            if REVERSE_RE.is_match(val) {
                Change::Reverse
            } else if CUT_RE.is_match(val) {
                let caps = CUT_RE.captures(val).unwrap();
                let num = caps[1].parse::<isize>().unwrap();
                Change::Cut(num)
            } else {
                let caps = DEAL_RE.captures(val).unwrap();
                let num = caps[1].parse::<usize>().unwrap();
                Change::Deal(num)
            }
        })
        .collect()
}

fn shuffle_position(process: &Vec<Change>, cards_len: usize, mut card_position: usize) -> usize {
    for change in process {
        match change {
            Change::Reverse => {
                card_position = cards_len - 1 - card_position;
            }
            Change::Cut(num) => {
                if num > &0 {
                    let num = *num as usize;
                    if num < card_position {
                        card_position -= num;
                    } else {
                        card_position = cards_len - (num - card_position);
                    }
                } else {
                    let num = num.abs() as usize;
                    if num < cards_len - card_position {
                        card_position += num
                    } else {
                        card_position = num - (cards_len - card_position);
                    }
                }
            }
            Change::Deal(num) => {
                card_position = (card_position * num) % cards_len;
            }
        }
    }

    card_position
}

fn part_a(input: Vec<Change>) -> usize {
    const cards_len: usize = 10_007;
    let mut cards = (0_usize..cards_len).collect::<Vec<usize>>();

    for change in input {
        match change {
            Change::Reverse => {
                cards.reverse();
            }
            Change::Cut(num) => {
                if num > 0 {
                    let num = num as usize;
                    let mut cut_cards: Vec<usize> = cards.drain(..num).collect();
                    cards.append(&mut cut_cards);
                } else {
                    let num = num.abs() as usize;
                    let mut cut_cards: Vec<usize> = cards.drain(cards.len() - num..).collect();
                    cut_cards.append(&mut cards);
                    cards = cut_cards;
                }
            }
            Change::Deal(num) => {
                let mut new_cards: Vec<usize> =
                    [0_usize; cards_len].iter().map(|val| *val).collect();
                for index in 0..cards_len {
                    new_cards[(index * num) % cards_len] = cards[index];
                }
                cards = new_cards;
            }
        }
    }

    for index in 0..cards_len {
        if cards[index] == 2019 {
            return index;
        }
    }

    0_0
}

fn part_b(shuffle: Vec<Change>) -> usize {
    const cards_len: usize = 119_315_717_514_047;
    const shuffle_times: usize = 101_741_582_076_661;
    let mut card_position: usize = 2020;

    let mut crazy : Vec<usize> = vec![];

    for time in 0..1_000_000{
        card_position = shuffle_position(&shuffle, cards_len, card_position);
        if crazy.contains(&card_position) {
            println!("whoa {} | {}", card_position, time);
        }
        crazy.push(card_position);
    }

    card_position
}

fn main() {
    let input = read_input().unwrap();
    let processed_input = parse_input(input);

    println!("{:?}", part_a(processed_input));
}

[Jon Bristow]

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

[Shaurya]

Didn't know about this equation. Also you may have accidentally written m instead of n in the formula :) .

[Jon Bristow]

Whoops! The notes I have it in mark it as ‘partial sum(n²⁾ for 1 to m = ...` (copied from wolfram alpha)

[Jon Bristow]

Kotlin solution for part 1.

Fairly straightforward, but completely useless for part 2.

import arrow.core.getOrElse
import arrow.core.toOption
import java.nio.file.Files
import java.nio.file.Paths

sealed class ShuffleMethods : (List<Int>) -> List<Int> {
    object DealIntoStack : ShuffleMethods() {
        override fun invoke(p1: List<Int>) = p1.reversed()
    }

    class Cut(val n: Int) : ShuffleMethods() {
        override fun invoke(p1: List<Int>): List<Int> {
            return if (n >= 0) {
                p1.drop(n) + p1.take(n)
            } else {
                p1.takeLast(-1 * n) + p1.dropLast(-1 * n)
            }
        }
    }

    class DealIncrement(val n: Int) : ShuffleMethods() {
        override fun invoke(p1: List<Int>): List<Int> {
            return p1.withIndex().sortedBy { (it.index * n) % p1.size }.map { it.value }
        }
    }

}


val regexIncrement = """deal with increment (\d+)""".toRegex()
const val dealIntoStack = "deal into new stack"
val regexCut = """cut (-?\d+)""".toRegex()


fun String.toShuffleMethod(): ShuffleMethods {
    if (this == dealIntoStack) {
        return ShuffleMethods.DealIntoStack
    }
    return when (val incrementMatch = regexIncrement.matchEntire(this)) {
        null -> {
            val cutMatch = regexCut.matchEntire(this).toOption()
            ShuffleMethods.Cut(cutMatch.getOrElse { throw error("unknown style: $this") }.groupValues[1].toInt())
        }
        else -> ShuffleMethods.DealIncrement(incrementMatch.groupValues[1].toInt())
    }
}


object Day22 {
    private const val FILENAME = "src/main/resources/day22.txt"
    val fileData get() = Files.readAllLines(Paths.get(FILENAME))

    fun part1(input: List<String>, deck: List<Int> = (0 until 10007).toList()): List<Int> {
        val methods = input.map { it.toShuffleMethod() }
        return shuffle(methods, deck)
    }



    private fun shuffle(
        methods: List<ShuffleMethods>,
        deck: List<Int>
    ): List<Int> {
        return methods.fold(deck) { acc, curr -> curr(acc) }
    }

}

fun main() {
    println(Day22.part1(Day22.fileData).withIndex().first { (i, v) -> v == 2019 })
}

[Jon Bristow]

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:

    object SingleShuffleMethods {
        fun dealIntoStack() = (BigInteger.ONE.negate() to BigInteger.ONE.negate())
        fun cut(n: BigInteger) = BigInteger.ONE to n.negate()
        fun dealIncrement(n: BigInteger) = n to BigInteger.ZERO
    }

    private fun power(
        applyShuffle: (Pair<BigInteger, BigInteger>, Pair<BigInteger, BigInteger>) -> Pair<BigInteger, BigInteger>,
        x: Pair<BigInteger, BigInteger>,
        n: BigInteger
    ): Pair<BigInteger, BigInteger> {
        return when {
            n == BigInteger.ONE -> x
            n % BigInteger.TWO == BigInteger.ZERO -> power(applyShuffle, applyShuffle(x, x), (n / BigInteger.TWO))
            else -> applyShuffle(x, power(applyShuffle, applyShuffle(x, x), (n / BigInteger.TWO)))
        }
    }

    fun part2(input: List<String>): BigInteger {
        val numberOfCards = BigInteger.valueOf(119315717514047)
        val shuffleCount = BigInteger.valueOf(101741582076661)
        val positionToCheck = BigInteger.valueOf(2020)

        val comp = { f: Pair<BigInteger, BigInteger>, g: Pair<BigInteger, BigInteger> ->
            (g.first * f.first) % numberOfCards to (g.first * f.second + g.second) % numberOfCards
        }
        val oneShuffle = input.map { it.toModOffsetPair() }.reduce(comp)
        val finalModOffset = power(comp, oneShuffle, shuffleCount).second
        val inverseModValue =
            oneShuffle.first.modPow(shuffleCount, numberOfCards).modInverse(numberOfCards)

        return (inverseModValue * positionToCheck + (inverseModValue.negate() * finalModOffset) % numberOfCards) % numberOfCards
    }

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 by i*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.