Day 8: Seven Segment Search
Today's problem description: https://adventofcode.com/2021/day/8
Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace
python with any of the "short names" listed in this page of supported languages):
<details> <summary>Part 1</summary> ```python Your code here. ``` </details>
Part 1 was trivial once you notice that the inputs are aligned.
Part 1, Unix
Still working on making part 2 in Rust look nice, but it's pretty damn ugly.
Python golf, day 8. Tips/improvements always welcome.
Here I converted strings to 7-bit binary numbers (e.g.
'abc' -> 1110000,
'cf' -> 0010010) then did some bit twiddling.
This could probably be golfed better but I need to get on with my day.
sorted()in part 2 was unnecessary, so I removed it and saved some bytes!
the key trick here is that I canonicalize both the patterns and the outputs by sorting them character-wise using
then comparing output digits to seeing if they match any of the 1, 4, 7, 8 patterns can be done as a simple string comparison of the canonical strings.
this was fun.
instead of character-sorted strings, I'm now representing the patterns as
sets of individual characters. then set operations can be used to do comparisons of segments.
I added some inline comments explaining the thought process / rationale going into each deduction
Neat! I also thought about set but I dunno why my dumb mind was just repeating me «keep strings sorted, keep…».
I freaked out a bit when I read the problem description, especially for part B. But after working at it for a bit I was able to chip away at it and eventually get to a solution.
Day 8 Part A - Python
This one wasn't too bad. I ended up using regular expressions to ID the lettering segments based on their length.
Day 8 Part B - Python
Holy fuck that escalated. Using the segments I knew from the previous portion, I was able to slowly figure out which letter combinations were which symbols. Once I had all the different letter combinations identified, I built a quick decoder and got my answer. And holy fuck, sets came in handy for this part. They were today's MVP.
It's a big problem, you might need to break it down into smaller portions and take it on one segment at a time (no pun intended)
Python's sets were extremely helpful for me, since they let you compare similar or different elements within groups of letters regardless of order. If your language has something similar, it may be helpful
Try drawing out each of the numbers with which segments are active and look for differences and similarities between them. Start with what you know and work from there.
The '9' option has 6 segments active. Not 5.
part 2? no thanks! I was close a few times, but just not there.
Part 1 was a breeze. G2:G has a list of the segments
Part 1``` =ARRAYFORMULA( IF(C3=FALSE,, QUERY( QUERY( FLATTEN( LEN( IFERROR( SPLIT( IF(ISBLANK(A2:A),, INDEX( TRIM( SPLIT(A2:A,"|")), 0,2)), " ")))), "select Col1, Count(Col1) where Col1 > 0 group by Col1 label Count(Col1) ''"), "select Sum(Col2) where Col1 matches '"&JOIN("|",FILTER(LEN(G2:G11),COUNTIF(LEN(G2:G11),LEN(G2:G11))=1))&"' label Sum(Col2) ''"))) ```
edit: I got part 2. Its brutal. You can check it out here
SPOILERI spent so much time trying to figure out the individual wire mapping before realizing I didn't need to. Deleted 75% of my code in the end.
Matching against how many segments are shared between the signal in question and a couple of the known ones is so smart! (And concise!)
This was interesting. Part 1 was pretty simple, although there's quite a bit of info to take in.
Part 2 was very open-ended, I ended up commenting my code for once in case anyone is curious on my solution. It's a bit of a process but I'm quite happy with it overall.
Part 2I deemed comparisons too messy for POSIX AWK, so my solution hinges on the number of occurrences of a segment:
The number 4 has segments c and d and not a or g, meaning that we can get those out of the way and map all the letters in a single clean pass.
First part was straightforward, just compute the length of each output string and check it against the known lengths.
This part stumped me for a while, but I eventually saw the need to use sets for the patterns. In Python, sets are well supported and include many useful operations such as
God. This took all day... but I finally managed to do it. (Rust)
Setup and Data structures
The code could probably be nicer, but I spent enough time on this today. :(
I chose to represent a digit as a set of letters.
I verified every line of input had 10 distinct sets because I was worried I'd need to think much harder about unscrambling the letter.
I made a hash-table of segment count -> set of (set of letters) - since there are repeated digits.
d1, d4, d7, and d8 all have unique segment counts (thank you Part 01!) so they were easy to find.
Using set subtraction:
Out of the 6-segment digits:
Once I have the digits I made another hash-table to map dn -> number to calculate the output value.
I can't tell you how frustrating it is (and how much time I lost) assuming that decoding the scrambled segments was broken - and not the fact I just forgot to add d9 to the lookup table once I'd unscrambled it.
Yesterday I gained 1974 places between solving part 1 and part 2 and today I lost 5052.
I spent so much time trying to figure out the math with set differences, it didn't even occur to me that I could also use set intersections!
Solutions in Go:
This one was annoying, not because the problem was hard but because I had to write a lot of functions that would exist in other languages, like comparing the contents of two arrays. The snippet bellow only contains the code that deals with the problem, you can see the rest of the code here.
Theory for solution 2Like everyone else I also used set theory, and since it seems there are multiple ways to solve it, here are the rules I used:
I got completely nerdsniped by this and was up until 1:30 AM trying to solve it (new days drop at 10 PM for me). It wasn't working so I went to bed and in the morning I realized one of my predicates was wrong!
Rust on sourcehut
It's real ugly, I like the way some other Rust users made theirs easier to read!
Little bit late to this, but I'm proud of my solution for Part 2. The basic idea I went for was trying to identify the minimum amount of information needed to distinguish each of the digits. The four factors I narrowed it down to were the length of the combination and the number of segments in common with the displays for 1, 4, and 7.
Part 1: 80 bytes
Part 2: 328 bytes
Holy crap this one took me a while. "After some careful analysis" indeed. :P
So I was able to get straight to my core tactic of looking at intersections and differences between sets of lit segments for known/possible digits to build up a set of known segments.
Unfortunately, trying to work out the exact process for narrowing things down from first principles was hard enough on its own, and then it took me a while to realize that the two given examples (the full set of lines, and the separate single line) were completely unrelated. So debugging my code on the first line of the sample input kept outputting what looked like garbage because the diagrams and discussion on the page no longer matched what I'd been looking at.
Then, after sorting that out and thinking I had the right flow, I was able to solve the single line example and the first line of the bigger example, but the second was wrong and I had to track down some problem in my set logic for specific digits/segments.
Going back and forth between the running logic in my debugger, the two different samples on the page, and trying to keep straight all the different segment/signal identifiers proved to be quite taxing (I'm going to put some of the blame on me being up late and starting to feel the effects of the booster shot I got earlier today; I swear I'm usually smarter than this :P)
All together, this is some of the worst/ugliest code I've written in quite a while. I may or may not come back and clean it up later, or try implementing some other persons more elegant solution (I'm sure there's got to be at least a couple, and there might be some properties of the input that can be leaned on).
Part 1 Ruby
Part 1 is pretty easy, since we only need to care about the length of the items, not do any real figuring.
Part 2 RubySince each line is entirely separate from the others, I've split out the core problem into its own function `decode` which just takes a single line and works out the output value. The real `compute_p2` function just maps that over the input lines and sums up the outputs.
Oh boy here we go...
This one was fun, once I finally understood what it was asking for. A few features of Elixir saved me some time—mainly the ability to use basically any value as a map key and have it compare correctly in lookups, thanks to persistent data structures. This meant I could parse each group of characters as a set, and keep them as sets throughout the rest of the code rather than converting to strings or something for lookups. I also didn't have to deal with converting the list of digits to a single integer, thanks to the goofily named
I really liked wycy's solution, so I stole it. 😏
Substantially shorter code, and it runs faster too!
Both parts, with a cleaner approach for part 2
Real life is starting to catch up to me, but I'm going to keep chugging! This one was not too bad, just a small copy paste problem kept it from passing muster last night and getting posted. I am proud of myself for reasoning out part 2, and I'm interested to see how others did it. My data structures overall and my efficiency with loops in part 2 may leave something to be desired, I was so focused on getting the logic correct that any concern for code quality went right out the window.
Part 2 Diff
I'm so glad to see I'm not the only one who struggled through this one. I went through three different "mental models" of what the final code would look like, and at one point modeled out a SevenSegmentDisplay and SevenSegmentConsole object, and started implementing wire to display connections for each display to figure out what number it was... Before I realized that none of these numbers can figure it out themselves, they all need the information from each other to tell which number is which!
My solution to part 2 is definitely not optimized, but I don't see anyone else using my same logic! I just implemented the exact steps I took as I was puzzling out the example on paper, with comments to keep my thoughts straight :)