Not only was part 2 annoying today, but I got paged in the middle of solving it :cry:
@popa.bogdanp first-where is the same as findf
Also, that’s good. Mine’s so ugly. I just wrote down whatever I deduced in my head. And it’s so messy.
> first-where is the same as findf I know, but findf takes the list argument last and that would ruin the aesthetics of that block :stuck_out_tongue:
My first solution was also very messy: https://github.com/Bogdanp/aoc2021/blob/60cb280e94ab1ecbd1d66447034967c527420e07/day08.rkt
Haha fair enough
Didn’t get to part to until this morning… holy ugh. I - like everyone else I’m sure - dislike my solution, but here it is: https://github.com/massung/advent2021/blob/main/day8/day8.lisp
@popa.bogdanp - that’s a good solution. There’s a part of me that wanted to go down that road (not the same code, but the idea that I - as a human - know how the digits work, so I can hard-wire deductive solutions in there).
Instead, I feel like I went down more of a sudoku solution. I basically said…
> for each character, given what length patterns it’s in, what possible positions could it fill? Then I sorted the characters by fewest # of positions first and removed those positions from the “larger” character position maps in order. This left me with a very small set where - except for 1 character - all of them were in pairs. Ex. “ab” could be ‘(2 5) and “gf” could be ’(1 3), etc.
Then it was a matter of creating the small permutations of all those combinations (which is small given that no duplicates are allowed) and finding the first map in the permutations for which every input pattern string could map to a valid digit.
I quite liked mine. (But also it’s clear that there’s a better version lurking somewhere, I just can’t see it.) The main observation is that the count of the number of segments common to two given digits is invariant under permutation of the segments. As a special case, if the two digits are the same, you get the count of the number of segments: that was part 1, but isn’t enough to uniquely identify the others. However, it does identify 1, 4, 7, and 8 — and that gives you four numbers for each digit and those are unique to that digit. https://github.com/alan-turing-institute/advent-of-code-2021/blob/main/day-08/racket_triangle-man/day08.rkt
Can anyone see a way to automate the whole thing?
Really enjoyed this one. Part2 doesn’t require anything fancy if you work with sets and discover the deterministic algorithm. Major spoilers in the comments in mine: https://github.com/benknoble/advent2021/blob/main/day8/solution.rkt
@james I found a deterministic solution that manipulates sets to discover the mapping between wires and segments. Developed it by working with one of the samples. Basically, if you look at subsets and subtractions, you can spot patterns that get you from the original known digits (1,4,7,8) to all the digits and the mappings in a constant number of steps.
So my part2 is Theta(n) in number of entries, but each entry is Theta(1) :slightly_smiling_face:
Looks like mine is similar to most here (<https://github.com/otherjoel/advent-of-code/blob/2dd56509a39d0400ae7beac0c8040aeb6372d7ea/2021/day08.rkt#L36-L51|relevant bit>). Looks like my checks to identify the top, bottom, middle and upper left segments weren’t necessary!
Day 8 really kicked my butt!!! Glancing at a comment about sets from @ben.knoble salvaged the day somewhat, but wow. Here’s my <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2021/solutions/day08/day08-part2.rkt|Part 2>
Nice @jgeddes - I’m quite dissatisfied with mine :)
I thought for sure this was a case for maximum-bipartite-matching, but I spent a lot of time trying to get that to work, and failed. If anyone comes across a solution using that, please post here!