Advent of code 2021: Day 8
This article is part of a series where I'll be diving head first into the Advent of code 2021. I'll be documenting the challenge of solving such a puzzle and how I got to the answer. I want to prefix this by stating that I can't cheat for any of these challenges; with that, I mean I can't look up any other implementations online.
In this article I'll be solving: Advent of code 2021: Day #8.
Part 1
A whale is giving our little submarine a bad time and while escaping, our four-digit seven segment display breaks down. The puzzle explains how to render the numbers and what exactly is wrong (see description by following the link, it’s quite a lot to chew on). The input we’ll be receiving looks like this:
cedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab | cdfeb fcadb cdfeb cdbaf
The first part of the code problem is simple enough, how many instances of 1, 4, 7 and 8 are in the final part, so after the |.
Those are the numbers that can be formed with a unique length of letters (1 takes 2 letters, 4 takes 4 letters, 7 takes 3 letters and 8 takes 7 letters). Resolving this is fairly simple:
fn unique_segments(input: &Vec<&str>) -> u32 {
let valid_lengths = vec![2, 3, 4, 7];
let mut count = 0;
for measurement in input {
let parsed: Vec<&str> = measurement.split(" | ").collect();
let digits: Vec<&str> = parsed[1].split(" ").collect();
for d in &digits {
if valid_lengths.contains(&d.len()) {
count += 1
}
}
}
count
}
Part 2: The juicy bit
Through deduction, you can determine the layout of the broken seven segment display. In the example above, the puzzle reasons that it should return deafgbc as the layout. With that, you can resolve that the digits behind the | equal to 5353. The puzzle asks to take your input of 200 measurements and sum the 200 4-digit numbers behind the |. The way I approached it is as follows:
- Make a list of all possible permutations of the group
{a,b,c,d,e,f,g}. - Reduce that group down by testing if each possible number can be formed on the display.
If everything is okay, we should only get 1 valid permutation. The first thing I thought of was to assume the display is a single array, which looks like this:
0
1 2
3
4 5
6
To form a number on the display, these would be the sections:
const POS: &'static [&'static[usize]] = &[
&[0,1,2,4,5,6], // 0
&[2,5], // 1
&[0,2,3,4,6], // 2
&[0,2,3,5,6], // 3
&[1,2,3,5], // 4
&[0,1,3,5,6], // 5
&[0,1,3,4,5,6], // 6
&[0,2,5], // 7
&[0,1,2,3,4,5,6], // 8
&[0,1,2,3,5,6] // 9
];
We can use Heap’s algorithm (like we used in many Euler puzzles before) to generate all possible permutations of {a,b,c,d,e,f,g}. The way to reduce them down is by using the retain()-method on these permutations with a certain predicate. The way I test if a permutation is valid, is by doing:
fn valid_perm(chars: &Vec<char>, val: &str) -> bool {
let map: Vec<Vec<usize>> = vec![
vec![1],
vec![7],
vec![4],
vec![2,3,5],
vec![0,6,9],
];
let ind = val.len() - 2;
// in case an 8 is present
if ind == 5 {
return true
}
match map.get(ind) {
Some(positions) => {
positions.iter().any(|p| {
let perms = heap(POS[*p].to_vec());
perms.iter().any(|c| {
let string: String = c
.into_iter()
.map(|n| chars[*n])
.collect();
&string == val
})
})
},
None => false
}
}
It’s not the nicest looking method, but it gets me to the correct permutation. The reason I use heap() again here, is because we can receive the “digits” in any possible order, and we need to be aware of that. Perhaps this can be done better with some sorting?
To parse the actual four-digit number:
for (i, d) in digits.iter().enumerate() {
let mut pos: Vec<usize> = d
.chars()
.map(|n| final_perm.iter().position(|t| *t == n).unwrap()).
collect();
pos.sort();
match POS.iter().position(|t| *t == pos) {
Some(n) => sum += (n as u64 * 10_u64.pow((3 - i) as u32)),
None => panic!("Also a bug")
}
}
… and solved! This one was rough for sure, but challenging enough. Got my 2 stars! ⭐️⭐️
Improvements for part 1
The code for Part 1 can be heavily reduced, with some counts and folds here and there:
let valid_lengths = vec![2, 3, 4, 7];
input.iter().fold(0, |acc, measurement| {
let parsed: Vec<&str> = measurement.split(" | ").collect();
acc + parsed[1]
.split(" ")
.filter(|d| valid_lengths.contains(&d.len()))
.count()
})
Improvements for part 2
The code for Part 2 is pretty poor, the performance is pretty bad, and I would like to see if this can be improved. The first thing I did notice while penning this problem down is that the position of the first letter in the display can be found by taking the letters from 7 and removing the letters from 1:
7:
A
B
C
1:
B
C
We know the top character will be A. This will make my initial permutations count 6! (720) instead of 7! (5040).
Increase in performance:
Old situation 7!
cargo run 6.17s user 0.06s system 103% cpu 6.043 total
New situation 6!
cargo run 2.88s user 0.07s system 107% cpu 2.758 total
That’s almost twice as fast! The next bit to try is to see if I can get rid of the other heap algorithm that’s now locked in the valid_perm predicate. A part of me thinks that this can be solved by simply sorting the letters that we get, but another part thinks that this is not going to result in any correct answers. Luckily, we have tests, so we can figure out very quickly if this will work or not.
After some fiddling with sort(), it turns out that valid_perm can be written without the heap-method! The speed increase is quite significant:
New situation 6! + sorting the chars in valid_perm()
cargo run 0.66s user 0.05s system 102% cpu 0.696 total
I’ll call this “performant enough”.
The full solution is available on GitHub.
