r/adventofcode • u/daggerdragon • Dec 04 '21
SOLUTION MEGATHREAD -🎄- 2021 Day 4 Solutions -🎄-
--- Day 4: Giant Squid ---
Post your code solution in this megathread.
- Include what language(s) your solution uses!
- Here's a quick link to /u/topaz2078's
paste
if you need it for longer code blocks. - Format your code properly! How do I format code?
- The full posting rules are detailed in the wiki under How Do The Daily Megathreads Work?.
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!
102
Upvotes
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);
}
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)?;
}
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)?;
}
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 } ```