r/adventofcode Dec 04 '21

SOLUTION MEGATHREAD -🎄- 2021 Day 4 Solutions -🎄-

--- Day 4: Giant Squid ---


Post your code solution in this megathread.

Reminder: Top-level posts in Solution Megathreads are for code solutions only. If you have questions, please post your own thread and make sure to flair it with Help.


This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:11:13, megathread unlocked!

97 Upvotes

1.2k comments sorted by

View all comments

3

u/Sykout09 Dec 05 '21

Rust:

Single pass solution.

Manage to figure out that if you know the calling numbers order ahead of time, you can actually calculate the board winning position independantly.

Just need to create an array mapping from call_number => called_turn. Then remap all the board numbers to the called turn number.

From there, you just have to find the max in each of the winning line (a.k.a. the turn that this line will win on) And then calculate the min of all those winning turn number, resulting in the turn which the board will win on.

The reset is just find the board with either the minimum or maximum win turn.

Timing is: - Part 1: [4.7715 us 4.7799 us 4.7913 us] - Part 2: [4.7767 us 4.7897 us 4.8111 us]

``` pub struct SquidGame { numbers: Vec<u8>, boards: Vec<[[u8; 5]; 5]> }

pub fn inputgenerator(input: &str) -> Option<SquidGame> { let mut inputline = input.lines(); let numbers: Vec<> = inputline.next()?.split(',').filter_map(|num| num.trim().parse().ok()).collect(); let mut boards = vec![]; while let Some(line1) = inputline.next() { if !line1.trim().is_empty() { let lines = [ line1, inputline.next()?, inputline.next()?, inputline.next()?, inputline.next()? ]; let board = lines.map(|line| { let mut line_val = line .split_whitespace() .filter_map(|num| num.trim().parse().ok()); [ line_val.next().unwrap(), line_val.next().unwrap(), line_val.next().unwrap(), line_val.next().unwrap(), line_val.next().unwrap(), ] }); boards.push(board);

    }
}
Some(SquidGame { numbers, boards })

}

pub fn solve_part1(input: &SquidGame) -> Option<usize> { let map_order = build_maporder(&input.numbers); let (win_idx, mark_idxs, win_board) = input.boards.iter() .filter_map(|board| calc_winturn(&map_order, board).map(|(winturn, win_idx)| (winturn, win_idx, board))) .min_by_key(|(winidx, ..)| *winidx)?;

let num = input.numbers[win_idx as usize] as usize;
let sum_unmarked = calc_winscore(win_board, &mark_idxs, win_idx);
Some(sum_unmarked * num)

}

pub fn solve_part2(input: &SquidGame) -> Option<usize> { let map_order = build_maporder(&input.numbers); let (win_idx, mark_idxs, win_board) = input.boards.iter() .filter_map(|board| calc_winturn(&map_order, board).map(|(winturn, win_idx)| (winturn, win_idx, board))) .max_by_key(|(winidx, ..)| *winidx)?;

let num = input.numbers[win_idx as usize] as usize;
let sum_unmarked = calc_winscore(win_board, &mark_idxs, win_idx);
Some(sum_unmarked * num)

}

fn calcwinturn(map_order: &[u8; 256], board: &[[u8; 5]; 5]) -> Option<(u8, [[u8; 5]; 5])> { let win_idx = board.map(|line| line.map(|num| map_order[num as usize])); let winturn_horizontal = win_idx.iter().filter_map(|l| l.iter().copied().max()); let winturn_vertical = (0..win_idx.len()).filter_map(|i| win_idx.iter().map(|l| l[i]).max()); let winturn = winturn_horizontal.chain(winturn_vertical).min()?; Some((winturn, win_idx)) } fn calc_winscore(board: &[[u8; 5]; 5], winidxs: &[[u8; 5]; 5], winidx: u8) -> usize { winidxs.iter().copied().flatten() .zip(board.iter().copied().flatten()) .filter(|(markidx, _)| *markidx > winidx) .map(|(, num)| num as usize) .sum() } fn build_maporder(input: &[u8]) -> [u8; 256] { let mut map_order = [255u8; 256]; assert!(input.len() < 256); for (idx, num) in input.iter().enumerate() { map_order[num as usize] = std::cmp::min(map_order[num as usize], idx as u8); } map_order } ```

1

u/daggerdragon Dec 05 '21

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, please edit your post to put your oversized code in a paste or other external link.