Trait and enums instead of lots of nested if statements

I'm working through advent of code 2021 and coming from python aim to learn leverage typing with enums.

I'm stuck on day08 part 2 (see below for questions).

I want to avoid writing loads of if statements to perform deduction. using strings of length 2 and 3 (numbers 1 and 7) allow decoding top segment for example.

I'm going in circles trying to define the type structure and impl blocks. I've started with below but don't understand how to proceed:

#[derive(Debug, Clone, Copy)]
enum SevenSegmentDisplay {
    Top,
    TopLeft,
    TopRight,
    Middle,
    BottomLeft,
    BottomRight,
    Bottom,
}


enum LetterMap {
    A(HashMap<char, SevenSegmentDisplay>),
    B(HashMap<char, SevenSegmentDisplay>),
    C(HashMap<char, SevenSegmentDisplay>),
    D(HashMap<char, SevenSegmentDisplay>),
    E(HashMap<char, SevenSegmentDisplay>),
    F(HashMap<char, SevenSegmentDisplay>),
    G(HashMap<char, SevenSegmentDisplay>),
}
}

Below are both part one and two questions:

# Day 8: Seven Segment Search

## Part One
You barely reach the safety of the cave when the whale smashes into the cave mouth, collapsing it. Sensors indicate another exit to this cave at a much greater depth, so you have no choice but to press on.

As your submarine slowly makes its way through the cave system, you notice that the four-digit seven-segment displays in your submarine are malfunctioning; they must have been damaged during the escape. You'll be in a lot of trouble without them, so you'd better figure out what's wrong.

Each digit of a seven-segment display is rendered by turning on or off any of seven segments named a through g:

  0:      1:      2:      3:      4:
 aaaa    ....    aaaa    aaaa    ....
b    c  .    c  .    c  .    c  b    c
b    c  .    c  .    c  .    c  b    c
 ....    ....    dddd    dddd    dddd
e    f  .    f  e    .  .    f  .    f
e    f  .    f  e    .  .    f  .    f
 gggg    ....    gggg    gggg    ....

  5:      6:      7:      8:      9:
 aaaa    aaaa    aaaa    aaaa    aaaa
b    .  b    .  .    c  b    c  b    c
b    .  b    .  .    c  b    c  b    c
 dddd    dddd    ....    dddd    dddd
.    f  e    f  .    f  e    f  .    f
.    f  e    f  .    f  e    f  .    f
 gggg    gggg    ....    gggg    gggg
So, to render a 1, only segments c and f would be turned on; the rest would be off. To render a 7, only segments a, c, and f would be turned on.

The problem is that the signals which control the segments have been mixed up on each display. The submarine is still trying to display numbers by producing output on signal wires a through g, but those wires are connected to segments randomly. Worse, the wire/segment connections are mixed up separately for each four-digit display! (All of the digits within a display use the same connections, though.)

So, you might know that only signal wires b and g are turned on, but that doesn't mean segments b and g are turned on: the only digit that uses two segments is 1, so it must mean segments c and f are meant to be on. With just that information, you still can't tell which wire (b/g) goes to which segment (c/f). For that, you'll need to collect more information.

For each display, you watch the changing signals for a while, make a note of all ten unique signal patterns you see, and then write down a single four digit output value (your puzzle input). Using the signal patterns, you should be able to work out which pattern corresponds to which digit.

For example, here is what you might see in a single entry in your notes:

acedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab |
cdfeb fcadb cdfeb cdbaf
(The entry is wrapped here to two lines so it fits; in your notes, it will all be on a single line.)

Each entry consists of ten unique signal patterns, a | delimiter, and finally the four digit output value. Within an entry, the same wire/segment connections are used (but you don't know what the connections actually are). The unique signal patterns correspond to the ten different ways the submarine tries to render a digit using the current wire/segment connections. Because 7 is the only digit that uses three segments, dab in the above example means that to render a 7, signal lines d, a, and b are on. Because 4 is the only digit that uses four segments, eafb means that to render a 4, signal lines e, a, f, and b are on.

Using this information, you should be able to work out which combination of signal wires corresponds to each of the ten digits. Then, you can decode the four digit output value. Unfortunately, in the above example, all of the digits in the output value (cdfeb fcadb cdfeb cdbaf) use five segments and are more difficult to deduce.

For now, focus on the easy digits. Consider this larger example:

be cfbegad cbdgef fgaecd cgeb fdcge agebfd fecdb fabcd edb |
fdgacbe cefdb cefbgd gcbe
edbfga begcd cbg gc gcadebf fbgde acbgfd abcde gfcbed gfec |
fcgedb cgb dgebacf gc
fgaebd cg bdaec gdafb agbcfd gdcbef bgcad gfac gcb cdgabef |
cg cg fdcagb cbg
fbegcd cbd adcefb dageb afcb bc aefdc ecdab fgdeca fcdbega |
efabcd cedba gadfec cb
aecbfdg fbg gf bafeg dbefa fcge gcbea fcaegb dgceab fcbdga |
gecf egdcabf bgf bfgea
fgeab ca afcebg bdacfeg cfaedg gcfdb baec bfadeg bafgc acf |
gebdcfa ecba ca fadegcb
dbcfg fgd bdegcaf fgec aegbdf ecdfab fbedc dacgb gdcebf gf |
cefg dcbef fcge gbcadfe
bdfegc cbegaf gecbf dfcage bdacg ed bedf ced adcbefg gebcd |
ed bcgafe cdgba cbgef
egadfb cdbfeg cegd fecab cgb gbdefca cg fgcdab egfdb bfceg |
gbdfcae bgc cg cgb
gcafb gcf dcaebfg ecagb gf abcdeg gaef cafbge fdbac fegbdc |
fgae cfgab fg bagce
Because the digits 1, 4, 7, and 8 each use a unique number of segments, you should be able to tell which combinations of signals correspond to those digits. Counting only digits in the output values (the part after | on each line), in the above example, there are 26 instances of digits that use a unique number of segments (highlighted above).

In the output values, how many times do digits 1, 4, 7, or 8 appear?

## Part Two

Through a little deduction, you should now be able to determine the remaining digits. Consider again the first example above:

acedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab |
cdfeb fcadb cdfeb cdbaf
After some careful analysis, the mapping between signal wires and segments only make sense in the following configuration:

 dddd
e    a
e    a
 ffff
g    b
g    b
 cccc
So, the unique signal patterns would correspond to the following digits:

acedgfb: 8
cdfbe: 5
gcdfa: 2
fbcad: 3
dab: 7
cefabd: 9
cdfgeb: 6
eafb: 4
cagedb: 0
ab: 1
Then, the four digits of the output value can be decoded:

cdfeb: 5
fcadb: 3
cdfeb: 5
cdbaf: 3
Therefore, the output value for this entry is 5353.

Following this same process for each entry in the second, larger example above, the output value of each entry can be determined:

fdgacbe cefdb cefbgd gcbe: 8394
fcgedb cgb dgebacf gc: 9781
cg cg fdcagb cbg: 1197
efabcd cedba gadfec cb: 9361
gecf egdcabf bgf bfgea: 4873
gebdcfa ecba ca fadegcb: 8418
cefg dcbef fcge gbcadfe: 4548
ed bcgafe cdgba cbgef: 1625
gbdfcae bgc cg cgb: 8717
fgae cfgab fg bagce: 4315
Adding all of the output values in this larger example produces 61229.

For each entry, determine all of the wire/segment connections and decode the four-digit output values. What do you get if you add up all of the output values?

Can you try to ask more concrete questions? Is the code you provided everything you have so far? How did you solve part 1, that should maybe include some input-output handling already, for instance.

I’d generally start with the input, not the result. Find a way to represent the input as a data structure that makes sense and is easy to work with. Then you could also think about how to represent the output; and how to represent the knowledge that you must obtain to derive the output from the input easily. For representing these things, what do all these have in common? What details of how the input or output is presented textually does or doesn’t matter? Also make sure to not have your representation be unnecessarily close to the textual representation you’re working with. No Strings in your abstract representation; maybe no chars either, the letters a through g are maybe most easily represented as some simple enum Letter { A, B, C, D, E, F, G } (and add sensible derives like #[derive(PartialEq, Eq, PartialOrd, Ord, Hash, Copy, Clone, Debug)]). Your SevenSegmentDisplay enum seems sensible, too (though maybe call it a segment, not a display).

Defining traits should be entirely unnecessary for your solution.

Ultimately, this is an interesting puzzle with probably dozens of completely different algorithmic approaches one could take. The things you present so far are so little fleshed out that any more concrete hint would feel like arbitrarily picking a way of solving this out for you, eliminating the chance for you to be creative.

If you cannot come up with a good algorithm so easily, try doing the decoding by hand a few times, learn how its done manually, maybe first describe the procedure in English (or other natural language), and only once you have a good way of describing an approach that isn’t overly complex go back to writing a program that does it.

Insofar as this relates to difficulties with Rust, feel free to share English descriptions of what concrete algorithm / procedure you want to follow with us if you’re unsure how such a thing should be written out in Rust.

1 Like

Thanks Steffahn, This is what I had for part one:

use std::fs::File;
use std::io::{self, BufRead, BufReader};

#[derive(Debug)]
pub struct EncodedSegments {
    pub strings: Vec<String>,
    pub output: Vec<String>,
}

pub fn read_file_to_segments(path: &str) -> io::Result<Vec<EncodedSegments>> {
    let file = File::open(path)?;
    let reader = BufReader::new(file);

    let segments = reader
        .lines()
        .map_while(Result::ok)
        .map(|line| {
            let parts: Vec<&str> = line.split('|').collect();
            if parts.len() == 2 {
                Some((
                    parts[0].split_whitespace().map(|s| s.to_string()).collect(),
                    parts[1].split_whitespace().map(|s| s.to_string()).collect(),
                ))
            } else {
                None
            }
        })
        .filter_map(|opt| {
            if let Some((strings, output)) = opt {
                Some(EncodedSegments { strings, output })
            } else {
                None
            }
        })
        .collect::<Vec<_>>();

    Ok(segments)
}

fn main() {
    let encoded_segments = read_file_to_segments("data/data1.txt").unwrap();
    println!("{:?}", encoded_segments);
    let total_count = encoded_segments
        .iter()
        .flat_map(|segment| segment.output.iter())
        .filter(|letters| {
            letters.len() == 2 || letters.len() == 3 || letters.len() == 4 || letters.len() == 7
        })
        .count();

    println!("Total Count: {}", total_count);
}

// Outputs 449

For part 2 I'm not sure how to implement enums with a method using HashSet symmetric_difference. I want to define a few deduction conditions used to map easy segments. For example if the output contains strings with length 2 and 3, find symmetric_difference char and update the insert into LetterMap.

I guess my revised simple form question might be:

If I have two strings vec![String::from("ab"), String::from("abc")] how would I implement symmetric_difference or match logic to update LetterMap::Top with c?

So one representation I could come up with is to use a Letter enum as described above, convert all the words in the input into BTreeSet<Letter> (which one could give a name via type Word = BTreeSet<Letter>; because order doesn't really matter. So the 10 words on the left form something like a Vec<Word>. Then the overall goal is to create a mapping from words to digits, like a HashMap<Word, u8>. The main procedure is thus to build up this HashMap<Word, u8>.

I’m not quite sure what your approach with the LetterMap type is supposed to look like. Here’s some alternative solution framework I could come up with:

#[derive(PartialEq, Eq, PartialOrd, Ord, Hash, Copy, Clone, Debug)]
enum Letter {
    A,
    B,
    C,
    D,
    E,
    F,
    G,
}

type Word = BTreeSet<Letter>;

// somehow create a `Vec<Word>` for the left half, and a `Vec<Word>` for the right half, for each line

As for how that’s then up to you. Maybe handwire the steps that lead to each number being discovered. Or perhaps even try a general approach, I don’t know. The nice thing is that set methods are then readily available.

E.g. your main job would be to write something like

// receives the vec of 10 words on the left of the "|"
// returns the desired translation map
fn main_logic(mut words: Vec<Word>) -> HashMap<Word, u8> {
    let one: Word = todo!(); // 1, 4, 7, 8 probably easiest to extract first
    // let seven = …;
    // let four = …;
    // let eight = …;

    // etc…

    HashMap::from_iter([
        (one, 1),
        // …,
        (four, 4),
        // …,
        // etc
    ])
}

Afterwards, connect this up to actually translate the right-hand-side words to get the answer.

Also, make sure to deduplicate stuff properly, e.g.

// extracts the word with exactly n letters
// panics if there's more or less than one such word (<- just a suggestion to avoid bugs)
// afterwards, the returned word is removed from `words`
fn get_by_unique_number(n: usize, words: &mut Vec<Word>) -> Word { todo!() }
fn main_logic(mut words: Vec<Word>) -> HashMap<Word, u8> {
    let one = get_by_unique_number(2, &mut words);
    // let seven = …;
    // let four = …;
    // let eight = …;

    // etc…

    HashMap::from_iter([/* … */])
}

As for how to find numbers now, maybe with set operations that happen to do the right thing. You seems to have suggested something with symmetric difference; I could come up with a concrete example involving an intersection, anyways, any approach you like shouldn’t be too hard to implement, either though.

Here’s some example set operation I could come up with: six seems (AFAICT) to be the only 6-segment number that overlaps only in 1 segment with one. That’s another case of finding something with a unique property, so maybe generalize your get_by_unique_number to something like

// extracts the word with the given property
// panics if there's more or less than one such word (<- just a suggestion to avoid bugs)
// afterwards, the returned word is removed from `words`
fn get_by_unique_property(prop: impl Fn(&Word) -> bool, words: &mut Vec<Word>) -> Word { todo!() }

(and then also refactor so that get_by_unique_number is defined in terms of calling get_by_unique_property). Here’s the relevant set operation in action then:

let six = get_by_unique_property(
    |w| w.len() == 6 && w.intersection(&one).count() == 1,
    &mut words,
);
3 Likes

Wow I want to learn to think and write like this. I sincerely appreciate your time and honesty!

In case you get it all working, here’s a fun refactor you could do afterwards for higher efficiency: Change your representation of Word to use the enumset - Rust crate instead of BTreeSet.

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.