Skip to content
loading...

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

FULL DISCUSSION
 

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));
}
 

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 of n in the formula :) .

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

code of conduct - report abuse