[SPOILER ALERT] Advent of Code: Day 6 solutions

[Junilu Lacar]

SPOILER ALERT This thread contains solution code for Day 6 of Advent of Code 2022.







 -- This space intentionally left blank --








SPOILER ALERT This thread contains solution code for Day 6 of Advent of Code 2022.

[Junilu Lacar]

Finished a couple of hours ago but just woke up and realized there was a more OO way to organize the (Kotlin) code:

class Day6(val packetSize: Int) {
  fun solution(datastream: String) = datastream
     .windowed(packetSize, 1)
     .indexOfFirst { isMarker(it) } + packetSize

  private fun isMarker(packet: String) = packet.toSet().size == packet.length
}

object Input {
  const val puzzle = "..."
  const val test1a = "..."
  const val test2a = "..."
}

fun main() {
   println("Part 1: ${Day6(4).solution(Input.puzzle)}")
   println("Part 2: ${Day6(14).solution(Input.puzzle)}")
}

[Mike Simmons]

I did something pretty similar:  [re-edited to improve names]

fun main() {
    val file = File("src/year2022/day06/input.txt")
    val line = file.readLines().first()

    println("\nPart 1:")
    println(findEndOfMarker(line, 4))

    println("\nPart 2:")
    println(findEndOfMarker(line, 14))
}

private fun findEndOfMarker(line: String, markerLength: Int): Int =
    (markerLength..line.length)
        .first { line.substring(it - markerLength, it).toSet().size == markerLength }

[Junilu Lacar]

The key idea for me was s.toSet().size == s.length. Once I saw that, it was just a matter of iterating through the string to get the right substrings.

[Liutauras Vilda]

Racket doesn't have sliding window function, but I achieved a similar effect with this code:

(define input (string->list (car (file->lines "input/day06.txt"))))

(define (solve input slice count)
  (if (not (check-duplicates (take input slice))) (+ slice count)
      (solve (cdr input) slice (add1 count))))

(solve input 4 0)
(solve input 14 0)

[Mike Simmons]

Junilu Lacar wrote:The key idea for me was s.toSet().size == s.length

Yup!  I had other ideas about more performant solutions that are O(input.length) rather than O(input.length * markerLength), because I reflexively dislike the latter.  Knowing it's going over the same data repeatedly is annoying to me (Sets of mostly the same data each time) - I want a single pass.  But it's just too easy to code the way we did.

Still, in discussing it now, I felt compelled to code my alternate solution anyway.

private fun findEndOfMarker(line: String, markerLength: Int): Int {
    val charLastIndexMap = mutableMapOf<Char,Int>()
    var markerStart = 0
    return line.indices.find { index ->
        val charLastIndex = charLastIndexMap.put(line[index], index) ?: -1
        if (charLastIndex >= markerStart)
            markerStart = charLastIndex + 1
        index >= markerStart + markerLength - 1
    }!! + 1
}

[Junilu Lacar]

You just gave me an idea. What do you think about using a mutable set? You remove the last letter of the sequence and then add the new letter that is going to come in, then check if the set size changed. This way, you're not creating a new set every time.

Then again, this could be just an exercise in premature optimization. And the code will probably be less terse.

[Mike Simmons]

I considered a mutable set.  But, how do you know when it's safe to remove an element?  You may know that one "x" has just left your region of interest... but there may be another 'x' in there, in between the two endpoints.  Or more than one.  So, you could use a mutable Map to keep the count of each element.  But I thought using a mutable Map to just keep track of the last position seen would be easier, or at least, no worse.  Either way, you need to keep track of something that tells you whether there's another 'x' within the region of interest, or whether the last one is too far back, or never been seen.

[Junilu Lacar]

Where there's a will, there's a kludge:

fun altSolution(dataStream: String, packetSize: Int): Int {
  val packet: MutableSet<Char> = mutableSetOf()
  packet.addAll(dataStream.substring(0, packetSize).toSet())
  return dataStream
    .windowed(packetSize, 1).indexOfFirst { chunk ->
      packet.add(chunk.last())
      val isMarker = packet.size == packetSize
      if (chunk.first() != chunk.last())
        packet.remove(chunk.first())
      isMarker
    } + packetSize
}

It ain't pretty. For me, the optimization isn't worth the price of elegance.

[Junilu Lacar]

I just checked and the kludgey solution I had using mutableSet didn't work for part 2 when I changed the size from 4 to 14.  Turns out it was just by chance that it seemed to work with the data I used to test with a packetSize of 4.

[Junilu Lacar]

Mike Simmons wrote:more performant solutions that are O(input.length) rather than O(input.length * markerLength)

If I remember my Big O correctly, since markerLength is a constant, doesn't that make O(input.length * markerLength) the same as O(input.length) anyway?

[Junilu Lacar]

Seems I program best when I'm on the can. I figured out my mistake

fun altSolution(dataStream: String, packetSize: Int): Int {
  val packet: MutableSet<Char> = mutableSetOf()
  packet.addAll(dataStream.substring(0, packetSize).toSet())
  return dataStream
    .windowed(packetSize, 1).indexOfFirst { chunk ->
      packet.add(chunk.last())
      val isMarker = packet.size == packetSize
      if (chunk.count { it == chunk.first() } == 1)
        packet.remove(chunk.first())
      isMarker
    } + packetSize
}

It still ain't pretty, but at least this time it works.

[Stephan van Hulst]

I did it with this one-liner:

new Scanner(input).findAll(PATTERN).map(MatchResult::end).findFirst().ifPresent(System.out::println);

Of course, the value of PATTERN is left as an exercise to the reader.

[Mike Simmons]

Nice!  I imagine you used something like

        var PATTERN = Pattern.compile("(.)(?!\\1)(.)(?!\\1|\\2)(.)(?!\\1|\\2|\\3)(.)");

Though the one for part 2 is... longer.

[Mike Simmons]

Junilu Lacar wrote:If I remember my Big O correctly, since markerLength is a constant, doesn't that make O(input.length * markerLength) the same as O(input.length) anyway?

Yes, if you treat markerLength as constant.  But they do change the markerLength between part 1 and 2.   The new value isn't that big, really - but in some of their problems, they make part 2 a much more performance-intensive version of part 1, so you never know if one of the values you thought was constant actually turns out to matter quite a bit.  This is a more general issue with big-O notation - people don't always realize (or agree) which parameters might become significant later.  

Note that for Stephan's regex solution, the length of the regex you need is O(markerLength ^ 2).  Still manageable for markerLength=14, but it's growing.

        var PATTERN2 = Pattern.compile(
                "(.)" +
                "(?!\\1)(.)" +
                "(?!\\1|\\2)(.)" +
                "(?!\\1|\\2|\\3)(.)" +
                "(?!\\1|\\2|\\3|\\4)(.)" +
                "(?!\\1|\\2|\\3|\\4|\\5)(.)" +
                "(?!\\1|\\2|\\3|\\4|\\5|\\6)(.)" +
                "(?!\\1|\\2|\\3|\\4|\\5|\\6|\\7)(.)" +
                "(?!\\1|\\2|\\3|\\4|\\5|\\6|\\7|\\8)(.)" +
                "(?!\\1|\\2|\\3|\\4|\\5|\\6|\\7|\\8|\\9)(.)" +
                "(?!\\1|\\2|\\3|\\4|\\5|\\6|\\7|\\8|\\9|\\10)(.)" +
                "(?!\\1|\\2|\\3|\\4|\\5|\\6|\\7|\\8|\\9|\\10|\\11)(.)" +
                "(?!\\1|\\2|\\3|\\4|\\5|\\6|\\7|\\8|\\9|\\10|\\11|\\12)(.)" +
                "(?!\\1|\\2|\\3|\\4|\\5|\\6|\\7|\\8|\\9|\\10|\\11|\\12|\\13)(.)");

Though I may be missing a way to simplify.

[Piet Souris]

I don't use regex much, and if I do I always have to read a tutorial first. Can you explain what that regex means?

[Piet Souris]

Don't bother, found it out

[Mike Simmons]

Ah, too late.  Well, here's a commented version anyway, for posterity:

        var PATTERN = Pattern.compile(
                "(.)" + // look for a character (group 1)
                        "(?!\\1)" + // not followed by another of group 1
                        "(.)" + // and another character (group 2)
                        "(?!\\1|\\2)" + // not followed by another of group 1 or 2
                        "(.)" + // and another character (group 3)
                        "(?!\\1|\\2|\\3)" + // not followed by another of group 1 or 2 or 3
                        "(.)"); // and another character (group 4)

[Stephan van Hulst]

That's the exact regex I used Mike, nice work!

Aye, it's not elegant, but after part 1 I was committed to it.