AoC 2021 - Day 08 Solutions (Spoilers!)

[Tim Cooke]

Oh boy this is a post of shame if ever there was one. Brace yourselves......
Part 1

    int part1() throws IOException {
        BufferedReader reader = getInput("InputDay08");
        int countOfEasyDigits = 0;
        for (String line; (line = reader.readLine()) != null;) {
            String[] digits = line.split("\\|")[1].trim().split(" ");
            for (String digit : digits) {
                if (digit.length() == 2 || digit.length() == 4 || digit.length() == 3 || digit.length() == 7) {
                    countOfEasyDigits++;
                }
            }

        }
        return countOfEasyDigits;
    }

Part 2

    int part2() throws IOException {
        BufferedReader reader = getInput("InputDay08");
        List<Integer> outputValues = new ArrayList<>();
        for (String line; (line = reader.readLine()) != null;) {
            List<String> patternStrings = Arrays.asList(line.split("\\|")[0].trim().split(" "));
            List<Set<String>> patterns = patternStrings.stream().map(p -> Set.of(p.split(""))).collect(Collectors.toList());
            String[] digitStrings = line.split("\\|")[1].trim().split(" ");
            List<Set<String>> digits = Arrays.stream(digitStrings).map(d -> Set.of(d.split(""))).collect(Collectors.toList());
            Map<String, Set<String>> knownPatterns = new HashMap<>();
            Map<Set<String>, String> decoded = new HashMap<>();
            for (Iterator<Set<String>> iterator = patterns.iterator(); iterator.hasNext(); ) {
                Set<String> pattern = iterator.next();
                switch (pattern.size()) {
                    case 2:
                        knownPatterns.put("1", pattern);
                        decoded.put(pattern, "1");
                        iterator.remove();
                        break;
                    case 3:
                        knownPatterns.put("7", pattern);
                        decoded.put(pattern, "7");
                        iterator.remove();
                        break;
                    case 4:
                        knownPatterns.put("4", pattern);
                        decoded.put(pattern, "4");
                        iterator.remove();
                        break;
                    case 7:
                        knownPatterns.put("8", pattern);
                        decoded.put(pattern, "8");
                        iterator.remove();
                        break;
                }
            }
            for (Set<String> pattern : patterns) {
                if (pattern.size() == 6
                        && pattern.containsAll(knownPatterns.get("1"))
                        && pattern.containsAll(knownPatterns.get("7"))
                        && !pattern.containsAll(knownPatterns.get("4"))) {
                    decoded.put(pattern, "0");
                } else if (pattern.size() == 6
                        && pattern.containsAll(knownPatterns.get("4"))) {
                    decoded.put(pattern, "9");
                } else if (pattern.size() == 6) {
                    decoded.put(pattern, "6");
                } else if (pattern.size() == 5
                        && pattern.containsAll(knownPatterns.get("7"))) {
                    decoded.put(pattern, "3");
                } else if (pattern.size() == 5) {
                    Set<String> tmpPattern = new HashSet<>(pattern);
                    tmpPattern.removeAll(knownPatterns.get("4"));
                    if (tmpPattern.size() == 3) {
                        decoded.put(pattern, "2");
                    } else {
                        decoded.put(pattern, "5");
                    }
                } else {
                    System.out.println("Missed!");
                }
            }
            String numberString = "";
            for (Set<String> digit : digits) {
                numberString += decoded.get(digit);
            }
            outputValues.add(Integer.parseInt(numberString));
        }
        return outputValues.stream().mapToInt(outputValue -> outputValue).sum();
    }

[Tim Cooke]

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.

[Stephan van Hulst]

I think my solution is almost identical to yours Tim, except I used more types:

  static enum Segment {

    A, B, C, D, E, F, G;

  }

  static enum Wire {

    A, B, C, D, E, F, G;

    static Wire parse(int codePoint) {
      if (codePoint < 'a' || codePoint > 'g')
        throw new IllegalArgumentException();

      return Wire.values()[codePoint - 'a'];
    }
  }

  static final class Signal {

    private final EnumSet<Wire> wires;

    private Signal(EnumSet<Wire> wires) {
      this.wires = wires;
    }

    int size() {
      return wires.size();
    }

    Set<Wire> wires() {
      return unmodifiableSet(wires);
    }

    Signal subtract(Signal other) {
      var copy = EnumSet.copyOf(wires);
      copy.removeAll(other.wires);
      return new Signal(copy);
    }

    static Signal parse(String signal) {
      return new Signal(
        signal.toLowerCase(Locale.ROOT).codePoints()
          .mapToObj(Wire::parse)
          .collect(toCollection(() -> EnumSet.noneOf(Wire.class)))
      );
    }
  }

  private static final class SegmentDisplay {

    private static final Map<Integer, Set<Segment>> SEGMENTS_BY_DIGIT = Map.of(
      0, Set.of(A, B, C,    E, F, G),
      1, Set.of(      C,       F   ),
      2, Set.of(A,    C, D, E,    G),
      3, Set.of(A,    C, D,    F, G),
      4, Set.of(   B, C, D,    F   ),
      5, Set.of(A, B,    D,    F, G),
      6, Set.of(A, B,    D, E, F, G),
      7, Set.of(A,    C,       F   ),
      8, Set.of(A, B, C, D, E, F, G),
      9, Set.of(A, B, C, D,    F, G)
    );

    private static final Map<Set<Segment>, Integer> DIGITS_BY_SEGMENTS = unmodifiableMap(SEGMENTS_BY_DIGIT
      .entrySet().stream()
      .collect(toMap(
        Entry::getValue,
        Entry::getKey
      ))
    );

    private final Map<Wire, Set<Segment>> possibleSegmentsPerWire = new EnumMap<>(
      Arrays.stream(Wire.values()).collect(toMap(
        identity(),
        wire -> EnumSet.allOf(Segment.class)
      ))
    );

    void eliminatePossibilities(Wire wire, int digit) {
      possibleSegmentsPerWire.get(wire).removeAll(SEGMENTS_BY_DIGIT.get(digit));
    }

    void associateSignalWithDigit(Signal signal, int digit) {
      var segmentsToRetain = SEGMENTS_BY_DIGIT.get(digit);
      signal.wires().forEach(wire -> possibleSegmentsPerWire.get(wire).retainAll(segmentsToRetain));
    }

    void uncrossWires(Stream<Signal> signals) {
      var signalsBySize = signals.collect(groupingBy(Signal::size));

      var signalsByDigit = new HashMap<Integer, Signal>();

      Map.of(
        1, 2,
        4, 4,
        7, 3,
        8, 7
      ).forEach((digit, signalSize) -> {
        var signal = signalsBySize.get(signalSize).get(0);
        associateSignalWithDigit(signal, digit);
        signalsByDigit.put(digit, signal);
      });

      signalsBySize.get(5).forEach(twoThreeOrFive -> {
        var remainder = twoThreeOrFive.subtract(signalsByDigit.get(1));

        if (remainder.size() == 3) {
          associateSignalWithDigit(twoThreeOrFive, 3);
          signalsByDigit.put(3, twoThreeOrFive);
        }

        else {
          remainder = remainder.subtract(signalsByDigit.get(4));

          if (remainder.size() == 3) {
            associateSignalWithDigit(twoThreeOrFive, 2);
            signalsByDigit.put(2, twoThreeOrFive);
          }

          else {
            associateSignalWithDigit(twoThreeOrFive, 5);
            signalsByDigit.put(5, twoThreeOrFive);
          }
        }
      });

      signalsBySize.get(6).forEach(zeroSixOrNine -> {
        var remainder = zeroSixOrNine.subtract(signalsByDigit.get(1));

        if (remainder.size() == 5) {
          associateSignalWithDigit(zeroSixOrNine, 6);
          signalsByDigit.put(6, zeroSixOrNine);
        }

        else {
          remainder = remainder.subtract(signalsByDigit.get(4));

          if (remainder.size() == 3) {
            associateSignalWithDigit(zeroSixOrNine, 0);
            signalsByDigit.put(0, zeroSixOrNine);
          }

          else {
            associateSignalWithDigit(zeroSixOrNine, 9);
            signalsByDigit.put(9, zeroSixOrNine);
          }
        }
      });

      while (!areWiresUncrossed()) {
        possibleSegmentsPerWire.forEach((wire, possibleSegments) -> {
          if (possibleSegments.size() == 1) {
            possibleSegmentsPerWire.values().forEach(possibleSegmentsForOtherWires -> {
              if (possibleSegmentsForOtherWires != possibleSegments)
                possibleSegmentsForOtherWires.removeAll(possibleSegments);
            });
          }
        });
      }
    }

    boolean areWiresUncrossed() {
      return possibleSegmentsPerWire.values().stream().allMatch(possibilities -> possibilities.size() == 1);
    }

    int getDigit(Signal signal) {
      if (!areWiresUncrossed())
        throw new IllegalStateException();

      var segments = signal.wires().stream()
        .map(possibleSegmentsPerWire::get)
        .flatMap(Set::stream)
        .collect(toSet());

      return DIGITS_BY_SEGMENTS.get(segments);
    }
  }

  public static void main(String... args) throws IOException {
    try (
      var stream = Day8.class.getResourceAsStream("day8.txt");
      var reader = new BufferedReader(new InputStreamReader(stream, StandardCharsets.UTF_8));
    ) {
      Map<SegmentDisplay, List<Signal>> entries = reader.lines()
        .map(Day8::parseSignals)
        .collect(toMap(
          signals -> {
            var display = new SegmentDisplay();
            display.uncrossWires(signals.stream().limit(10));
            return display;
          },

          signals -> signals.stream().skip(10).collect(toList()),

          (a, b) -> { throw new AssertionError(); },

          LinkedHashMap::new
        ));

      var sum = new AtomicLong();

      entries.forEach((display, signals) -> {
        var number = signals.stream().mapToInt(display::getDigit).mapToObj(Integer::toString).collect(joining(""));
        sum.accumulateAndGet(Long.parseLong(number), Long::sum);
      });

      System.out.println(sum);
    }
  }

  private static List<Signal> parseSignals(String line) {
    return Arrays.stream(line.split("[\\s|]+"))
      .map(Signal::parse)
      .collect(toList());
  }

[Stephan van Hulst]

I feel that I can greatly simplify my code, but this was the final result upon submitting my answer.

[Liutauras Vilda]

Horrible puzzle.

[Junilu Lacar]

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.

    val lengthsOfDigits1478= listOf(2, 3, 4, 7)

    fun part1(input: List<String>): Int = input
            .flatMap { it.split(" | ").last().split(" ") }
            .count { it.length in lengthsOfDigits1478 }
    }

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:

    fun part1(input: List<String>): Int = input
            .flatMap { it.split(" | ").last().split(" ") }
            .filter { it.length in lengthsOfDigits1478 }   // IDEA: call chain on collection type may be simplified
            .count()
    }

[Junilu Lacar]

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]

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!

[Piet Souris]

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:

<T> Map<T, Long> frequencyMap(Stream<T> elements) {
return elements.collect(
  Collectors.groupingBy(
    Function.identity(),
    HashMap::new, // can be skipped
    Collectors.counting()
  )
);
}

(badly indented!    
but you can also write

<T> Map<T, Long> frequencyMap(Stream<T> elements) {
    return elements.collect(groupingBy(i -> i, counting());
}

or

<T> Map<R, Long> frequencyMap(Stream<T> elements, Function<T, R> keyExtractor) {
    return elements.collect(groupingBy(keyExtractor, counting());
}

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:

println(frequencyMap2(listOf(3,5,15,7,30,12,10,25,45,20,18,7,50,11,9))
        { when {
            it % 15 == 0 -> "fizzbuzz"
            it % 5 == 0 -> "buzz"
            it % 3 == 0 -> "fizz"
            else -> it.toString()
        } } )

[Liutauras Vilda]

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]

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]

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]

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:

println(frequencyMap2(listOf(3,5,15,7,30,12,10,25,45,20,18,7,50,11,9))
        { when {
            it % 15 == 0 -> "fizzbuzz"
            it % 5 == 0 -> "buzz"
            it % 3 == 0 -> "fizz"
            else -> it.toString()
        } } )

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:

frequencyMap2(listOf(3,5,15,7,30,12,10,25,45,20,18,7,50,11,9)) 
    { fizzBuzz(it) }.also(::println)

* 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]

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]

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:

    fun translateLine(input: List<String>, decoder: List<Set<Char>>) = input
            .map { it.toSet() }.map { decoder.indexOf(it) }

    fun translateSegment(input: String): List<Int> {
        val digits = input.split(" | ").first().split(" ")
        val codes = digits.map { it.toSet() }

        val decoder = buildList<Set<Char>>(10) {
            repeat(10) { add(emptySet()) }
            set(1, digits.first { it.length == 2 }!!.toSet())
            set(4, digits.first { it.length == 4 }!!.toSet())
            set(7, digits.first { it.length == 3 }!!.toSet())
            set(8, digits.first { it.length == 7 }!!.toSet())
            set(2, find2(codes, this[4]))
            set(3, find3(codes, this[4] subtract this[2]))
            set(5, find5(codes, listOf(this[2], this[3])))
            set(6, find6(codes, this[7]) )
            set(9, find9(codes, this[4] union this[7]) )
            set(0, find0(codes, this[6], this[4] union this[7]) )
        }
        return translateLine(input.split(" | ").last().split(" "), decoder)
    }

    fun result(input: List<String>): Int {
        return input
            .map {
                translateSegment(it).fold(0, { acc, n -> acc * 10 + n })
            }.also(::println)
            .sum()
    }

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]

Ok, couldn't resist just making the code a little more symmetric:
       val decoder = buildList<Set<Char>>(10) {            repeat(10) { add(emptySet()) }            set(1, digits.first { it.length == 2 }!!.toSet())            set(4, digits.first { it.length == 4 }!!.toSet())            set(7, digits.first { it.length == 3 }!!.toSet())            set(8, digits.first { it.length == 7 }!!.toSet())            set(2, find2(codes, this[4]))            set(6, find6(codes, this[7]) )            set(3, find3(codes, this[4] subtract this[2]))            set(9, find9(codes, this[4] union this[7]))            set(5, find5(codes, listOf(this[2], this[3])))            set(0, find0(codes, listOf(this[6], this[9])))        }
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]

Here are the supporting functions for finding each digit using set operations:

   fun find9(codes: List<Set<Char>>, c4andc7: Set<Char>): Set<Char> = codes
        .first { it.size == 6 && (it subtract c4andc7).size == 1 }

    fun find6(codes: List<Set<Char>>, c7: Set<Char>): Set<Char> = codes
        .first { it.size == 6 && (it subtract c7).size == 4 }

    fun find0(codes: List<Set<Char>>, c69: List<Set<Char>>) = codes
        .first { it.size == 6 && it !in c69 }

    fun find5(codes: List<Set<Char>>, c23: List<Set<Char>>) = codes
        .first { it.size == 5 && it !in c23 }

    fun find3(codes: List<Set<Char>>, c4sub2: Set<Char>) = codes
        .first { it.size == 5 && (c4sub2 subtract it).size == 1 }

    fun find2(codes: List<Set<Char>>, c4: Set<Char>) = codes
        .first { it.size == 5 && (c4 - it).size == 2 }

[Junilu Lacar]

What can I say... I'm OCD when it comes to refactoring:

/**
 * Day 8: Seven Segment Search
 */
fun main() {

    val lengthsOfDigits1478 = listOf(2, 4, 3, 7)

    /* digits with code.size == 5 : (2, 3, 5) */

    fun find2(codes: List<Set<Char>>, c4: Set<Char>) = codes
        .first { it.size == 5 && (c4 subtract it).size == 2 }

    fun find3(codes: List<Set<Char>>, c4sub2: Set<Char>) = codes
        .first { it.size == 5 && (c4sub2 subtract it).size == 1 }

    fun find5(codes: List<Set<Char>>, c23: List<Set<Char>>) = codes
        .first { it.size == 5 && it !in c23 }

    /* digits with code.size == 6 : (6, 9, 0) */

    fun find6(codes: List<Set<Char>>, c7: Set<Char>): Set<Char> = codes
        .first { it.size == 6 && (it subtract c7).size == 4 }

    fun find9(codes: List<Set<Char>>, c4andc7: Set<Char>): Set<Char> = codes
        .first { it.size == 6 && (it subtract c4andc7).size == 1 }

    fun find0(codes: List<Set<Char>>, c69: List<Set<Char>>) = codes
        .first { it.size == 6 && it !in c69 }

    /* other stuff */

    fun signalPatternsIn(entry: String) = entry
            .split(" | ").first().split(" ")

    fun outputValuesIn(entry: String) = entry
            .split(" | ").last().split(" ")

    fun decoderFor(signals: List<Set<Char>>): List<Set<Char>> =
        buildList<Set<Char>>(10) {
            repeat(10) { add(emptySet()) }
            set(1, signals.first { it.size == 2 })
            set(4, signals.first { it.size == 4 })
            set(7, signals.first { it.size == 3 })
            set(8, signals.first { it.size == 7 })
            set(2, find2(signals, this[4]))
            set(6, find6(signals, this[7]))
            set(3, find3(signals, this[4] subtract this[2]))
            set(9, find9(signals, this[4] union this[7]))
            set(5, find5(signals, listOf(this[2], this[3])))
            set(0, find0(signals, listOf(this[6], this[9])))
        }

    fun decode(outputValues: List<String>, decoder: List<Set<Char>>) = outputValues
            .map { it.toSet() }.map { decoder.indexOf(it) }

    fun digitsInOutputDisplay(entry: String): List<Int> =
        decode(outputValuesIn(entry), decoderFor(signalPatternsIn(entry).map { it.toSet() }))

    fun part1(input: List<String>): Int = input
        .flatMap { outputValuesIn(it) }
        .count { it.length in lengthsOfDigits1478 }

    fun part2(input: List<String>): Int = input
            .map { digitsInOutputDisplay(it).fold(0, { acc, n -> acc * 10 + n }) }.sum()

    // test if implementation meets criteria from the description, like:
    val testInput = readInput("Day08_test")
    part1(testInput).also(::println).also { check(it == 26) }

    part2(listOf("acedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab | cdfeb fcadb cdfeb cdbaf"))
        .also(::println).also { check(it == 5353) }

    part2(testInput).also(::println).also { check(it == 61229)}

    val input = readInput("Day08")
    part1(input).also(::println).also { check(it == 421) } // gold star
    part2(input).also(::println).also { check(it == 986163) } // gold star
}

[Junilu Lacar]

Refactored one more time:
   /* signals with size == 5 : (2, 3, 5) */    fun find2(signals: List<Set<Char>>, decoder: List<Set<Char>>) = signals        .first { it.size == 5 && (decoder[4] subtract it).size == 2 }    fun find3(signals: List<Set<Char>>, decoder: List<Set<Char>>) = signals        .first { it.size == 5 && (decoder[4] - decoder[2] - it).size == 1 }    fun find5(signals: List<Set<Char>>, decoder: List<Set<Char>>) = signals        .first { it.size == 5 && it !in decoder.slice(setOf(2,3)) }    /* signals with size == 6 : (6, 9, 0) */    fun find6(signals: List<Set<Char>>, decoder: List<Set<Char>>): Set<Char> = signals        .first { it.size == 6 && (it subtract decoder[7]).size == 4 }    fun find9(signals: List<Set<Char>>, decoder: List<Set<Char>>): Set<Char> = signals        .first { it.size == 6 && (it - (decoder[4] union decoder[7])).size == 1 }    fun find0(signals: List<Set<Char>>, decoder: List<Set<Char>>) = signals        .first { it.size == 6 && it !in decoder.slice(setOf(6,9)) }    /* other stuff */    fun signalPatternsIn(entry: String) = entry            .split(" | ").first().split(" ")    fun outputValuesIn(entry: String) = entry            .split(" | ").last().split(" ")    fun decoderFor(signals: List<Set<Char>>): List<Set<Char>> =        buildList<Set<Char>>(10) {            repeat(10) { add(emptySet()) }            set(1, signals.first { it.size == 2 })            set(4, signals.first { it.size == 4 })            set(7, signals.first { it.size == 3 })            set(8, signals.first { it.size == 7 })            set(2, find2(signals, this))            set(6, find6(signals, this))            set(3, find3(signals, this))            set(9, find9(signals, this))            set(5, find5(signals, this))            set(0, find0(signals, this))        }
OCD for symmetry is appeased (for now)

[Junilu Lacar]

I will write another blog post to explain this refactoring:
   fun MutableList<Set<Char>>.set1_4_7_8(signals: List<Set<Char>>) {        set(1, signals.first { it.size == 2 })        set(4, signals.first { it.size == 4 })        set(7, signals.first { it.size == 3 })        set(8, signals.first { it.size == 7 })    }    fun MutableList<Set<Char>>.deduce2_3_5(signals: List<Set<Char>>) {        this[2] = find2(signals, this)        this[3] = find3(signals, this)        this[5] = find5(signals, this) // must be called last!    }    fun MutableList<Set<Char>>.deduce6_9_0(signals: List<Set<Char>>) {        this[6] = find6(signals, this)        this[9] = find9(signals, this)        this[0] = find0(signals, this) // must be called last!    }    fun decoderFor(signals: List<Set<Char>>): List<Set<Char>> =        buildList<Set<Char>>(10) {            repeat(10) { add(emptySet()) }            set1_4_7_8(signals)  // must be called first!            deduce2_3_5(signals)            deduce6_9_0(signals)        }
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]

Here's another way to initialize the list:
   fun decoderFor(signals: List<Set<Char>>): List<Set<Char>> =        buildList<Set<Char>>() {            addAll(List(10) { emptySet() })            set1_4_7_8(signals)  // must be called first!            deduce2_3_5(signals)            deduce6_9_0(signals)        }
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]

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:

    fun MutableList<Set<Char>>.set1_4_7_8(signals: List<Set<Char>>) {
        this[1] = signals.first { it.size == 2 }
        this[4] = signals.first { it.size == 4 }
        this[7] = signals.first { it.size == 3 }
        this[8] = signals.first { it.size == 7 }
    }

    fun decoderFor(signals: List<Set<Char>>): List<Set<Char>> = buildList() {
        addAll(List(10) { emptySet() })
        set1_4_7_8(signals)  // must be called first!
        deduce2_3_5(signals)
        deduce6_9_0(signals)
    }

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.

    val knownSignalLengths = mapOf(1 to 2, 4 to 4, 7 to 3, 8 to 7)

    fun MutableList<Set<Char>>.setKnownSignalPatterns(signals: List<Set<Char>>) {
        knownSignalLengths.forEach { (digit, length) ->
            this[digit] = signals.first { it.size == length } }
    }

    fun decoderFor(signals: List<Set<Char>>): List<Set<Char>> = buildList() {
         addAll(List(10) { emptySet() })
         setKnownSignalPatterns(signals)  // must be called first!
         deduce2_3_5(signals)
         deduce6_9_0(signals)
    }

[Junilu Lacar]

Liu, check this fully de-mechanicalized decoding version out:

    val knownSignalLengths = mapOf(1 to 2, 4 to 4, 7 to 3, 8 to 7)

    fun MutableList<Set<Char>>.setKnownSignalPatterns(signals: List<Set<Char>>) {
        knownSignalLengths.forEach { (digit, length) ->
            this[digit] = signals.first { it.size == length } }
    }

    fun MutableList<Set<Char>>.deduce5segmentSignals(signals: List<Set<Char>>) {
        val selectors = mapOf<Int, (Set<Char>) -> Boolean> (
            2 to { segments -> (this[4] - segments).size == 2},
            3 to { segments -> (this[4] - this[2] - segments).size == 1},
            5 to { segments -> segments !in this.slice(listOf(2,3)) }
        )
        selectors.forEach { (digit, deduce) ->
            this[digit] = signals.first { it.size == 5 && deduce(it) } }
    }

    fun MutableList<Set<Char>>.deduce6segmentSignals(signals: List<Set<Char>>) {
        val selectors = mapOf<Int, (Set<Char>) -> Boolean> (
            6 to { segments -> (segments - this[7]).size == 4 },
            9 to { segments -> (segments - (this[4] union this[7])).size == 1},
            0 to { segments -> segments !in this.slice(setOf(6,9)) }
        )
        selectors.forEach { (digit, deduce) ->
            this[digit] = signals.first { it.size == 6 && deduce(it) } }
    }

    fun decoderFor(signals: List<Set<Char>>): List<Set<Char>> = buildList() {
        addAll(List(10) { emptySet() })
        setKnownSignalPatterns(signals)  // must be called first!
        deduce5segmentSignals(signals)
        deduce6segmentSignals(signals)
    }

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

[Junilu Lacar]

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]

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:

val decoder: List<Set<Char>> = buildList() {
    addAll(List(10) { emptySet() }) // add placeholders
    this[1] = "cf".toSet()
    this[4] = "bcdf".toSet()
    this[7] = "acf".toSet()
    this[8] = "abcdefg".toSet()
}

with (decoder) {
   check(indexOf("fc".toSet()) == 1)
   check(indexOf("fdcb".toSet()) == 4)
   check(indexOf("fac".toSet()) == 7)
   check(indexOf("agfecdb".toSet() == 8)
}

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:

// true iff signal == 2
decoder[2] = signals.first { it.size == 5 && (decoder[4] - it).size == 2 }.toSet()

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

// true iff signal == 3
decoder[3] = signals.first { it.size == 5 && (decoder[4] - decoder[2] - it) == 1}  

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:

// true iff signal == 5, assuming decoder[2] and decoder[3] have been assigned
decoder[5] = signals.first { it.size == 5 && it !in decoder.slice(listOf(2,3)) }

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

        val selectors = mapOf<Int, (Set<Char>) -> Boolean> (
            6 to { signal -> (signal - this[7]).size == 4 },
            9 to { signal -> (signal - (this[4] union this[7])).size == 1},
            0 to { signal -> signal !in this.slice(setOf(6,9)) }
        )

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]

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]

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:

fun main() {
    fun nested1() ...

    fun nested2() {
        nested1()
        mainlevel()
    }
}
fun mainlevel() ...

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]

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]

   

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]

I think there was about a decade between the specialized and the general theory of relativity.

[Junilu Lacar]

Speaking of refactoring-induced dopamine rush, here's some code that has great potential for a high (five):
for (Iterator<Set<String>> iterator = patterns.iterator(); iterator.hasNext(); ) {               Set<String> pattern = iterator.next();               switch (pattern.size()) {                   case 2:                       knownPatterns.put("1", pattern);                       decoded.put(pattern, "1");                       iterator.remove();                       break;                   case 3:                       knownPatterns.put("7", pattern);                       decoded.put(pattern, "7");                       iterator.remove();                       break;                   case 4:                       knownPatterns.put("4", pattern);                       decoded.put(pattern, "4");                       iterator.remove();                       break;                   case 7:                       knownPatterns.put("8", pattern);                       decoded.put(pattern, "8");                       iterator.remove();                       break;               }           }
That can be boiled down to one case label. Are you able to see the pattern? Here's a hint:
     case 2, 3, 4, 7:
But you're going to have to add something outside of the switch statement to be able to do that.

[Stephan van Hulst]

I think I did that in this snippet of code:

Map.of(
  1, 2,
  4, 4,
  7, 3,
  8, 7
).forEach((digit, signalSize) -> {
  var signal = signalsBySize.get(signalSize).get(0);
  associateSignalWithDigit(signal, digit);
  signalsByDigit.put(digit, signal);
});

[Junilu Lacar]

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

Map.of(
  1, 2,
  4, 4,
  7, 3,
  8, 7
).forEach((digit, signalSize) -> {
  var signal = signalsBySize.get(signalSize).get(0);
  associateSignalWithDigit(signal, digit);
  signalsByDigit.put(digit, signal);
});

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

mapOf(
   2 to 1, 
   4 to 4, 
   3 to 7, 
   7 to 8
).forEach { (size, digit) -> 
... }

[Junilu Lacar]

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]

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:
   val knownSignalLengths = mapOf(1 to 2, 4 to 4, 7 to 3, 8 to 7)    fun MutableList<Set<Char>>.setKnownSignalPatterns(signals: List<Set<Char>>) {        knownSignalLengths.forEach { (digit, length) ->            this[digit] = signals.first { it.size == length } }    }    fun MutableList<Set<Char>>.deduceSegments(signals: List<Set<Char>>, selectors: Map<Int, (Set<Char>) -> Boolean>) =        selectors.forEach { (digit, deduce) -> this[digit] = signals.first { deduce(it) } }    fun MutableList<Set<Char>>.deduce5and6Segment(signals: List<Set<Char>>) {        deduceSegments(signals, selectors = mapOf<Int, (Set<Char>) -> Boolean>(            2 to { signal -> signal.size == 5 && (this[4] - signal).size == 2 },            3 to { signal -> signal.size == 5 && (this[7] - signal).isEmpty() },            6 to { signal -> signal.size == 6 && (signal - this[7]).size == 4 },            9 to { signal -> signal.size == 6 && (this[4] - signal).isEmpty() }        ))    }    fun MutableList<Set<Char>>.deduceRemaining(signals: List<Set<Char>>) {        deduceSegments(signals, selectors = mapOf<Int, (Set<Char>) -> Boolean>(            5 to { signal -> signal.size == 5 && signal !in this.slice(listOf(2, 3)) },            0 to { signal -> signal.size == 6 && signal !in this.slice(setOf(6, 9)) }        ))    }    fun decoderFor(signals: List<Set<Char>>): List<Set<Char>> = buildList() {        addAll(List(10) { emptySet() })        setKnownSignalPatterns(signals)        deduce5and6Segment(signals)        deduceRemaining(signals)    }
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]

OCD: Just had to find an incantation that was more symmetrical:
   fun MutableList<Set<Char>>.deduce5and6Segment(signals: List<Set<Char>>) {        deduceSegments(signals, selectors = mapOf<Int, (Set<Char>) -> Boolean>(            2 to { signal -> signal.size == 5 && (this[4] - signal).size == 2 },            3 to { signal -> signal.size == 5 && (this[7] - signal).isEmpty() },            6 to { signal -> signal.size == 6 && (this[7] - signal).size == 1 },            9 to { signal -> signal.size == 6 && (this[4] - signal).isEmpty() },        ))    }
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):
  fun MutableList<Set<Char>>.deduceRemaining(signals: List<Set<Char>>) {       deduceSegments(signals, selectors = mapOf<Int, (Set<Char>) -> Boolean>(           5 to { signal -> signal.size == 5 && signal !in this.slice(setOf(2, 3)) },           0 to { signal -> signal.size == 6 && signal !in this.slice(setOf(6, 9)) },       ))   }
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.