This week's book giveaway is in the Jobs Discussion forum.We're giving away four copies of Developer Career Masterplan: Build your path to senior level and beyond with practical insights from industry experts and have Heather VanCura and Bruno Souza on-line!See this thread for details.
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Ron McLeod
• Paul Clapham
• Tim Cooke
• Jeanne Boyarsky
Sheriffs:
• Rob Spoor
• Devaka Cooray
• Liutauras Vilda
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Carey Brown
• Tim Moores
• Mikalai Zaikin
Bartenders:
• Piet Souris

# AoC 2021 - Day 08 Solutions (Spoilers!)

Marshal
Posts: 5541
326
• Number of slices to send:
Optional 'thank-you' note:
Oh boy this is a post of shame if ever there was one. Brace yourselves......
Part 1

Part 2

Tim Cooke
Marshal
Posts: 5541
326
• Number of slices to send:
Optional 'thank-you' note:
Part 1 was straight forward, just counting patterns that have length of one of the unique digits.

Part 2 is a pattern matching exercise. Given the sets of segments that make up the known digits, you can derive the others by segment length and whether one of the known digits is a subset of it.

e.g.
Digit 0 has 6 segments, contains all segments of 1, and contains all segments of 7, and does not contain all segments of 4.
Digit 9 has 6 segments, contains all segments of 1, and contains all segments of 7, and contains all segments of 4.

You can continue with this idea to decode all segment sets into digits. The only snag is 2 and 5 which required some set operation wrangling with the 4 digit segments.

The code reads horribly and very much in the spirit of git-er-done.

Saloon Keeper
Posts: 15110
344
• 1
• Number of slices to send:
Optional 'thank-you' note:
I think my solution is almost identical to yours Tim, except I used more types:

Stephan van Hulst
Saloon Keeper
Posts: 15110
344
• Number of slices to send:
Optional 'thank-you' note:
I feel that I can greatly simplify my code, but this was the final result upon submitting my answer.

Sheriff
Posts: 8783
629
• Number of slices to send:
Optional 'thank-you' note:
Horrible puzzle.

Sheriff
Posts: 17616
300
• Number of slices to send:
Optional 'thank-you' note:
I feel like I keep Kot-flexing on you guys. My apologies, but it's Kotlin's fault.

Been busy this week and only just now got around to solving Day 8. But Part 1 was done in less than 5 minutes and the hardest part of it was looking through the API for flatMap.

Looks like I have another example to add to my blog post on Kotlin one-liners.

Sorry, but some IntelliJ IDEA-flexing as well: the only refactoring I did from my first cut was to remove an unnecessary call to `filter()` that IDEA called out:

Junilu Lacar
Sheriff
Posts: 17616
300
• 1
• Number of slices to send:
Optional 'thank-you' note:
I have written a follow-up article that includes the lessons learned from solving Part 1 of Day 8: https://jlacar.github.io/kotlin/kotlin-oneliners.html

and another one to detail the process I used to solve it: https://jlacar.github.io/kotlin/0to1in5.html -- If you read the first few versions of that article, it was pretty bad. Sorry if you had to suffer through that first version. After a lot of edits, I think it's much better now. If you re-read it, you're a saint; and thank you.

Junilu Lacar
Sheriff
Posts: 17616
300
• 1
• Number of slices to send:
Optional 'thank-you' note:

Liutauras Vilda wrote:Horrible puzzle.

Why do you say so, Liu? I think it's a very interesting and challenging puzzle, actually. Especially part 2. I'm still working out the decoding of the segments but I'm thinking once I have a breakthrough insight, it's going to be pretty easy to solve it. I haven't looked at any of the shared solutions yet; won't do that until I come up with my own approach and algorithm. I know I'm going to be using sets of chars for this, and differences of sets, and then it's a process of elimination, kind of like the game Mastermind. Deductive puzzles are fun!

Bartender
Posts: 5443
212
• Number of slices to send:
Optional 'thank-you' note:

Junilu Lacar wrote:I have written a follow-up article that includes the lessons learned from solving Part 1 of Day 8: https://jlacar.github.io/kotlin/kotlin-oneliners.html

and another one to detail the process I used to solve it: https://jlacar.github.io/kotlin/0to1in5.html -- If you read the first few versions of that article, it was pretty bad. Sorry if you had to suffer through that first version. After a lot of edits, I think it's much better now. If you re-read it, you're a saint; and thank you.

Thanks, Junilu, very interesting!

I have two remarks for now:

1) yes, Kotlin has some powerful shortcuts compared to Java, when reading your website I get the same feeling I had when doing Scala and Python. But you show a Java snippet using the longest form possible. For instance, you have this example:
(badly indented!
but you can also write

or

2) You are this sites Master of Refactoring and Master of Code that reads like a train.
With respect to this, what is your opinion on, for instance:

Liutauras Vilda
Sheriff
Posts: 8783
629
• Number of slices to send:
Optional 'thank-you' note:

Junilu Lacar wrote:Why do you say so, Liu? I think it's a very interesting and challenging puzzle, actually. Especially part 2.

It is challenging, but at the same time I found it very mechanical and the solution itself required more of a human input with IFs, as opposed to some more elegant approach to the problem.
To most extent issue might be because the solution I came up with. Stephan it seems landed to a nicer approach..

Anyway, I'll be interested to see your solution.

Moving fast forward, Day 8 I found equally uninteresting to me as a Day 10, while Day 9 and Day 11 were brilliant, found few areas to improve and at the end was quite happy with the result, code's expressiveness and conciseness.

But part of the fun I guess, you deal with whatever you get, and try to get best out of it.

Junilu Lacar
Sheriff
Posts: 17616
300
• Number of slices to send:
Optional 'thank-you' note:

Piet Souris wrote:yes, Kotlin has some powerful shortcuts compared to Java, when reading your website I get the same feeling I had when doing Scala and Python. But you show a Java snippet using the longest form possible. For instance, you have this example:
...
but you can also write
...

You are absolutely right, Piet. I think I let my growing bias show. I will update the article (with an attribution to you, of course). Thanks for the call out.

Junilu Lacar
Sheriff
Posts: 17616
300
• 1
• Number of slices to send:
Optional 'thank-you' note:

Liutauras Vilda wrote:
Anyway, I'll be interested to see your solution.

Still working on it right now. I'm having to juggle it with multiple things at work. I have an early morning presentation I need to give on Wednesday about user story points, I'm calling it "What's the story with story points?" in which I go over their history and discuss the challenges in using them. I still don't have my slide deck compiled at this point. I can't help messing with these problems though and coming up with the decoding for Part 2 is still in the works as of this writing.

Moving fast forward, Day 8 I found equally uninteresting to me as a Day 10, while Day 9 and Day 11 were brilliant, found few areas to improve and at the end was quite happy with the result, code's expressiveness and conciseness.

But part of the fun I guess, you deal with whatever you get, and try to get best out of it.

Yup, the fun is wherever there's learning. Have fun!

Junilu Lacar
Sheriff
Posts: 17616
300
• Number of slices to send:
Optional 'thank-you' note:

Piet Souris wrote:
2) You are this sites Master of Refactoring and Master of Code that reads like a train.
With respect to this, what is your opinion on, for instance:

It's kind of diyahe* for me to be called "Master" of anything but thank you for your kind words. IMO, it's a cute example of a quick-and-dirty thing. If I were to refactor it for clarity in the context of a larger program, I'd probably do something like this:

* diyahe a Filipino term that has many uses in expressing embarrassment, the exact meaning of which is very contextual. In this context, it's an awkward embarrassment when a friend praises you in a way you don't really think is deserved, most appropriately answered by "Pshaw, you're really too kind, but thank you."

Junilu Lacar
Sheriff
Posts: 17616
300
• Number of slices to send:
Optional 'thank-you' note:

I wrote:I will update the article (with an attribution to you, of course). Thanks for the call out.

Done. Thanks again for the call out.

I trust that you tested that code, right? Because I only copy-pasted what you provided.

BTW, just search for your name in the article to see where I put the note.

Junilu Lacar
Sheriff
Posts: 17616
300
• Number of slices to send:
Optional 'thank-you' note:
I just got my 2nd gold star for Day 8. It's ugly right now but here's the heart of the Get Er Done solution in Kotlin:

Took me three dang hours to figure out the set math on how to deduce which code mapped to each digit. Sheesh. It's certainly not a one-liner but I'm pooped and I have to start work in a few hours so will refactor later.

Junilu Lacar
Sheriff
Posts: 17616
300
• Number of slices to send:
Optional 'thank-you' note:
Ok, couldn't resist just making the code a little more symmetric:

This will help me see some patterns in the code and start generalizing it down to fewer lines.

Seriously, I need to get to bed. Bye for now.

Junilu Lacar
Sheriff
Posts: 17616
300
• Number of slices to send:
Optional 'thank-you' note:
Here are the supporting functions for finding each digit using set operations:

Junilu Lacar
Sheriff
Posts: 17616
300
• Number of slices to send:
Optional 'thank-you' note:
What can I say... I'm OCD when it comes to refactoring:

Junilu Lacar
Sheriff
Posts: 17616
300
• Number of slices to send:
Optional 'thank-you' note:
Refactored one more time:

OCD for symmetry is appeased (for now)

Junilu Lacar
Sheriff
Posts: 17616
300
• Number of slices to send:
Optional 'thank-you' note:
I will write another blog post to explain this refactoring:

I had some really awesome learning about Kotlin from this refactoring exercise. See more in an upcoming blog post. The beauty of it was that all I had to do was create some symmetry in the program and ask IDEA to extract some functions for me. IDEA surprised me by performing the refactoring in a way I didn't expect but was of course better than what I would have done manually (and naively).

Junilu Lacar
Sheriff
Posts: 17616
300
• Number of slices to send:
Optional 'thank-you' note:
Here's another way to initialize the list:

I also removed the redundant 10 between capacity and size.

EDIT: Ah, heck, if you're interested in seeing the latest revision of this code, just go to the source: https://github.com/jlacar/aoc2021-kotlin/blob/main/src/Day08.kt

Junilu Lacar
Sheriff
Posts: 17616
300
• Number of slices to send:
Optional 'thank-you' note:

Liutauras Vilda wrote:I found it very mechanical and the solution itself required more of a human input with IFs, as opposed to some more elegant approach to the problem.

Ok, since you asked for it, Liu, I think I've found a better way.

I think this is what you describe as a "very mechanical" way of decoding the digits with known unique lengths:

This didn't look too bad to me but then after giving it some thought, I agree, it is indeed very mechanical. I thought to myself, "There must be some way we can do it better in Kotlin."

And sure enough, there is. Check this out.

Junilu Lacar
Sheriff
Posts: 17616
300
• Number of slices to send:
Optional 'thank-you' note:
Liu, check this fully de-mechanicalized decoding version out:

See the github repo for the full listing: https://github.com/jlacar/aoc2021-kotlin/blob/main/src/Day08.kt

Junilu Lacar
Sheriff
Posts: 17616
300
• Number of slices to send:
Optional 'thank-you' note:

Stephan van Hulst wrote:I feel that I can greatly simplify my code, but this was the final result upon submitting my answer.

Just quickly going over your code, I think yes, you could simplify it. I do, however, think we're thinking along the same lines. I'm seeing some names in your code that resonate with what I was thinking as I was building out my solution. I have to say though that I'm really happy with how my refactoring turned out.

Junilu Lacar
Sheriff
Posts: 17616
300
• Number of slices to send:
Optional 'thank-you' note:
I'm looking through the different versions shared and see that there might be some interesting differences in the approaches we've taken to deduce what the other digits map to. I'll describe my algorithm first and then take a shot at Tim's and Stephan's for comparison.

My approach for decoding starts with a List<Set<Char>> as the lookup table. I started out with an Array<Set<Char>> but found that a List is easier to work with and inspect on the fly using the .also(::println) incantation I blogged about. With arrays, I have to use .joinToString() to see what the contents were or use Arrays.toString() which was just a little much for me. Kotlin is nice in that it overloads the List accessors so you can use array index notation to access specific List elements.

The idea is to be able to simply do decoder.indexOf(signal.toSet()) and get back the corresponding digit that the segments map to. So with the standard mapping of segments, you'd have a list like this after populating it with the mapping for the digits with known signal lengths: [ {}, {c,f}, {}, {}, {b,c,d,f}, {}, {}, {a,c,f}, {a,b,c,d,e,f,g}, {} ]. Note that in Kotlin, if you have a String signal, then signal.toSet() is a Set<Char> of the characters in signal. This means that the following would work:

The hardest part of this was figuring out how to deduce the other digits from the information you had so far. In retrospect, it seems logical but it's really an Egg of Columbus type thing. It only seems easy when you already know the solution.

So the remaining digits are neatly divided into two groups: the first group are the digits that have 5 segments (2, 3, and 5) and the second group of digits having 6 segments each (6, 9, and 0). Here's how I came up with my set logic:

4 - 2 ==> bf
4 - 3 ==> b
4 - 5 ==> c

Where 4 - 2 means "bcdf" - "acdeg" ==> "bf". This allows you to deduce that of all the signals, the one where 4 - X(5) ==> Y(2) corresponds to the digit 2, where X(5) is any signal with 5 characters in it and Y(2) is a set with 2 characters in it.

Hence, my selector logic was essentially this:

Now that I know the signal for 2, I can deduce the signal for 3:

From here, deducing the signal for 5 is straightforward, it's the one that's not 2 or 3. We can use slice() to easily get the signals we need for this:

For the group of (6, 9, 0), I go through a similar deductive process. The conditions being embodied in this mapping:

Luckily, it seems that in Kotlin, iterating over a Map preserves the keys' addition order. That's good because my deductive logic required the assignments to be done in the order that I added the map entries. Otherwise, there would be missing information.

Liutauras Vilda
Sheriff
Posts: 8783
629
• Number of slices to send:
Optional 'thank-you' note:

Junilu Lacar wrote: Seriously, I need to get to bed. Bye for now.

Junilu Lacar not long enough after... wrote:I'm OCD when it comes to refactoring

When I open up my email client and get dozen of emails about the posts from the same thread, that usually means just one thing, Junilu has been on the refactoring hunt. Man, I read them with smile and am mesmerized about your dedication to the quality. Exemplary!

That's a nice piece of refactored version. Way more functional. Now, that requires some mind bending, to parse everything, but that's because it's been a while since I touched Kotlin. You also seem to write functions down->top, as opposed to more habitual way top->down.

I think top->down is a bit easier to read, because from the top functions you get introduced to the context WHAT is going to happen, then you gradually get introduced to HOW part.

I'm going to spend a bit more time reading your refactoring chunks. That's certainly interesting!

I'm a bit behind now, still couldn't find enough time to sit down and try to catch up. But trying to, so far the backlog is for days: 12, 13, 14.

Junilu Lacar
Sheriff
Posts: 17616
300
• Number of slices to send:
Optional 'thank-you' note:

Liutauras Vilda wrote:[You also seem to write functions down->top, as opposed to more habitual way top->down.

I think top->down is a bit easier to read, because from the top functions you get introduced to the context WHAT is going to happen, then you gradually get introduced to HOW part.

You'd think that but it seems that IDEA extracts upwards because a function has to be already seen (by the compiler, that is) before it can be used, at least in the way it has been structured in the template I'm using. There are typically no classes in the programs I'm writing, with only a few exceptions. When there is a class involved, the behavior we're used to in Java is there, where it appears the compiler does at least two passes, the first to build out a symbol table, then a second pass to resolve references.

When it's all functions, therefore, it behaves like a one-pass compiler where any symbol used must have already been seen before it can be used. That's why extracted functions are put above their origin. At least that's what I've observed. I just rolled with it. I hope that makes sense. If anything, it's better/easier to understand if you read the code from the bottom up.

Edit: Maybe the behavior I described is when it's structured like this:

That will only work if nested1() is above nested2(), not below. The call to mainlevel() works because it is a top-level function. I haven't tested this to verify but if I remember correctly, what I'm saying is true. Will come back here and correct myself if I find out otherwise.

Junilu Lacar
Sheriff
Posts: 17616
300
• Number of slices to send:
Optional 'thank-you' note:

Liutauras Vilda wrote:so far the backlog is for days: 12, 13, 14.

I'm even more behind. We are 1.5hrs into Day 15 and I haven't even started on Day 9 yet. I doubt I can catch up before Christmas. Maybe by the New Year. I'm going on a long road trip though (3K miles total, with a ten-day break in the middle). Hopefully, I'll be able to make up some time over the break.

Junilu Lacar
Sheriff
Posts: 17616
300
• Number of slices to send:
Optional 'thank-you' note:

Tim Cooke wrote:Oh boy this is a post of shame if ever there was one. Brace yourselves......

There is no shame in being a normal human being. I applaud you for your courage in sharing work you know is not the best that you can do.

Thank you, Tim, for being willing to share your thoughts, in all its glorious ugliness—and yes, it is quite ugly. Every baby is beautiful though, no matter how ugly. This one is no different. Shameful? Nah, GTFO!  It works, doesn't it? You learned something from it, didn't you? I certainly did.

And here's what I learned (or relearned, if you will): That the (normal) developer—no, human—brain thinks in specifics before it thinks about generalizations. Our brains are advanced pattern recognition machines, but we need to see things repeat at least three times before we can recognize a pattern. Unless you have very sharply-honed precognitive skills, you can't see the forest for the trees until we actually have a few trees to make a forest. We're all like that, except for maybe a few fortunate souls. I might even venture to say they're not actually as fortunate as we are because if those precogs do in fact exist, then they're missing out on the joy of discovery, that satisfying rush you get when you find a better way to say or write something. Maybe that's why I'm so passionate about refactoring. I'm a refactoring-induced dopamine addict.

Hmmm... I feel another blog post coming on.

Stephan van Hulst
Saloon Keeper
Posts: 15110
344
• 1
• Number of slices to send:
Optional 'thank-you' note:
I think there was about a decade between the specialized and the general theory of relativity.

Junilu Lacar
Sheriff
Posts: 17616
300
• Number of slices to send:
Optional 'thank-you' note:
Speaking of refactoring-induced dopamine rush, here's some code that has great potential for a high (five):

That can be boiled down to one case label. Are you able to see the pattern? Here's a hint:

But you're going to have to add something outside of the switch statement to be able to do that.

Stephan van Hulst
Saloon Keeper
Posts: 15110
344
• 1
• Number of slices to send:
Optional 'thank-you' note:
I think I did that in this snippet of code:

Junilu Lacar
Sheriff
Posts: 17616
300
• Number of slices to send:
Optional 'thank-you' note:

Stephan van Hulst wrote:I think I did that in this snippet of code:

Yes, you did. Java's Map.of() threw me for a loop there for a second. A little less expressive than Kotlin's way:

Junilu Lacar
Sheriff
Posts: 17616
300
• Number of slices to send:
Optional 'thank-you' note:

Tim Cooke wrote:
e.g.
Digit 0 has 6 segments, contains all segments of 1, and contains all segments of 7, and does not contain all segments of 4.
Digit 9 has 6 segments, contains all segments of 1, and contains all segments of 7, and contains all segments of 4.

Yes, that sounds correct. Also, that logic relies on only the digits that you know for sure so it has an advantage over the algorithm I came up with in that mine had to deduce 2 before it could deduce 3 before it could deduce 5. Likewise for 6, 9, 0, they had to be deduced in that order for my set math to work.

Cool. I will give this a shot with my code and let you know how it goes.

Junilu Lacar
Sheriff
Posts: 17616
300
• Number of slices to send:
Optional 'thank-you' note:

I wrote:Cool. I will give this a shot with my code and let you know how it goes.

I'm back to report how it went and it went quite well. I tried implementing some of Tim's logic and found yet another way to refactor my solution:

This latest refactoring has achieved the following:

1. Clarity in the sequential dependencies of the deductive logic. The required sequence is expressed in the buildList() initialization in the decoderFor() function. For the deductive logic to work, the known signal patterns must first be mapped, then the 5- and 6-segment digits deduced, and then only the remain digits can be deduced. Within each of the subservient functions, the sequence doesn't matter any more.

2. More symmetry and less duplication of the control structures used. It's clearer to me as I read the code how things are related to each other and where the abstractions are done to eliminate duplication.

Junilu Lacar
Sheriff
Posts: 17616
300
• Number of slices to send:
Optional 'thank-you' note:
OCD: Just had to find an incantation that was more symmetrical:

The nice thing about these conditions is that they uniquely decode their corresponding signal digit. The order doesn't matter.

Same thing with this (tweaked for symmetry):

Also notice that the extra "," at after the last item in the mapOf() constructor doesn't produce a compiler error. This is the same behavior as in Go.

 With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply