:warning: Day 5 Solution Thread  :warning:
a
⚠️ Day 5 Solution Thread  ⚠️
k
It didn't explicitly stated my id wasn't on my list. Little salty rn
d
What do you mean? "your seat should be the only missing boarding pass in your list."
👆 1
happy for
``.sort()``
here - made the second part super easy!
❤️ 1
a
My internet went out at the absolute worst time
😠 1
Copy code
``````private val input = readInput("input5.txt")

fun main() {
val numbers = input.split("\n").map { line ->
var lowRange = 0
var highRange = 127
(0..6).forEach { if (line[it] == 'F') highRange -= (highRange - lowRange + 1) /2 else lowRange += (highRange - lowRange + 1) / 2 }
val rowNum = highRange
lowRange = 0
highRange = 7
(0..2).forEach { if (line.takeLast(3)[it] == 'L') highRange -= (highRange - lowRange + 1) /2 else lowRange += (highRange - lowRange + 1) / 2 }
val col = highRange
rowNum * 8 + col to rowNum
}
numbers.map { it.first }.maxOrNull()!!.let { println("Part 1: \$it") }

val filtered = numbers.filter { it.second != 0 && it.second != 127 }.map { it.first }
filtered.forEach { one ->
filtered.forEach { two ->
if (one - two == 2) {
if ((one - 1) !in filtered) println("Part 2: \${one - 1}")
}
}
}
}``````
k
I literally reread both parts and didn't see that mentioned =p
oh you actually did like a binary search
a
wait did you not
please tell me there wasn’t a much easier way
d
that's what I did but used
``when``
again 🙂
😁 1
k
``it.map { if (it == 'B' || it == 'R') '1' else '0' }.joinToString("").toInt(2)``
it does still look ugly
d
clever!!
k
and not what I typed during the puzzle
I got this during the puzzle
``val x = it.substring(0, 7).mapIndexed { a, b -> if (b == 'B') 2.0.pow(6 - a) else 0.0 }.sumBy { it.toInt() }``
and then the same for y and then
``x * 8 + y``
d
still you had the idea to think in binary...
k
yeah
a
very clever!
@David Whittaker how many conditions did you have in
``when``
?
d
four: 'F', 'B', 'L', 'R' - looping over the entire boarding pass
Copy code
``````line.forEach {
when (it) {
'F' -> rowH = (rowL + rowH )/2
'B' -> rowL = (rowL + rowH + 1)/2
'L' -> colH = (colL + colH)/2
'R' -> colL = (colL + colH +1)/2
}
}``````
where
``var (rowL, rowH, colL, colH) = listOf(0, 127, 0, 8)``
a
Updated:
Copy code
``````private val input = readInput("input5.txt")

fun main() {
val numbers = input.split("\n").map { line ->
val row = line.take(7).map { if (it == 'F') 0 else 1 }.joinToString("").toInt(2)
val col =  line.takeLast(3).map { if (it == 'L') 0 else 1 }.joinToString("").toInt(2)
row * 8 + col to row
}
numbers.map { it.first }.maxOrNull()!!.let { println("Part 1: \$it") }

val filtered = numbers.filter { it.second != 0 && it.second != 127 }.map { it.first }
filtered.forEach { one ->
filtered.forEach { two ->
if (one - two == 2 && (one - 1) !in filtered) println("Part 2: \${one - 1}")
}
}
}``````
@David Whittaker smart! I like it
j
Arrgh I was quite pleased with my solution until I saw the ones in this thread and I realized how much simpler it could have been. I implemented a binary search tree because I convinced myself it was necessary for effective searching... Anyway, it works! 🙂 Code here: https://github.com/jorispz/aoc-2020/blob/master/src/commonMain/kotlin/day05/p05.kt The basic parts (without the ugly binary tree bits):
Copy code
``````val p05 = suspend {
val seating = SeatNode()
input.lines().forEach {
it.fold(seating) { node, ch -> node.insert(ch) }
}

seating.seats.maxOrNull().print { "Part 1: \$it" }

(0..1023).toList()
.filter { it !in seating }
.single { (it - 1) in seating && (it + 1) in seating }
.print { "Part 2: \$it" }
}``````
And the timings:
Copy code
``````| Platform         | Average (ms)  | Measurements (ms) |
| -----------------| -------------:|------------------:|
| JVM (OpenJDK 11) | 3.9±6.0       | `29, 5, 2, 2, 2, 2, 4, 3, 2, 2, 2, 1, 1, 1, 2, 1, 1, 1, 5, 1` |
| Node JS          | 8.8±8.1       | `35, 24, 13, 17, 8, 9, 4, 4, 4, 5, 3, 5, 4, 5, 5, 3, 4, 3, 4, 5` |
| Native           | 18.9±2.6      | `18, 18, 16, 19, 18, 18, 27, 18, 18, 16, 18, 16, 19, 17, 22, 16, 18, 17, 22, 17` |``````
a
Copy code
``````fun String.toSeatId(): Int = this.fold(0){acc,c -> 2 * acc + if ( c=='B'||c=='R') 1 else 0}

fun main() {
val seatIds = boardingPasses.map { it.toSeatId() }
println(seatIds.maxOrNull())
println((seatIds.minOrNull()!!..seatIds.maxOrNull()!!).dropWhile { it in seatIds }.first())
}``````
e
who needs
``F|B|L|R``
constants in their code anyway ;)
m
I had unboken sequences both at the start and the end - did not expect that given some of the seats at the very front and back of the plane don't exist on this aircraft. Like, my list of missing boarding passes in the range
``0..1023``
is
``0..12``
,
``727``
``979..1023``
. I would've expected gaps at both ends as well. According to a colleague he has those front and end gaps so I was wondering if I just got a very generous puzzle input out of luck... EDIT: I may have misunderstood him.
The key being some here, that's why I didn't expect unbroken ranges
n
Copy code
``````fun String.asBinary(one: Char) = reversed()
.withIndex()
.map { 2.0.pow(it.index) * if(it.value == one) 1 else 0 }
.sum().toInt()

fun toId(row: Int, col: Int) = row * 8 + col

fun getInput() = (aocDataDir / "day5.txt").useLines { lines ->
lines.map { line ->
toId(line.substring(0,7).asBinary('B'), line.substring(7).asBinary('R'))
}.toList()
}

fun part1() = getInput().max().also { println(it) }

fun part2(): Int {
val ids = getInput().toSet()
return (0..toId(127, 7)).asSequence().filter {
it !in ids && (it+1) in ids && (it-1) in ids
}.single().also { println(it) }
}``````
t
I got up late, and then had to run errands with my wife. But I'm happy with what I ended up with.
Copy code
``````class Day05(private val input: List<String>) {

fun solvePart1(): Int =
input.map { seatId(it) }.maxOrNull() ?: throw IllegalStateException("No answer")

fun solvePart2(): Int =
input.map { seatId(it) }.sorted().run {
(((first()+last())/2.0) * (size+1)).toInt() - sum()
}

private fun seatId(pattern: String): Int =
pattern.map { if(it in setOf('B', 'R')) '1' else '0' }.joinToString("").toInt(2)

}``````
I want to clean up Part 2. But essentially I'm figuring out what the total should be and then figuring out what it actually is, and the missing one is my seat. That took me a while to get right, but I knew what the answer was because I did a manual loop over the sorted list to find the missing one to get the star and the right answer before I rewrote that bit.
Maybe I got lucky with my input for part 2?
Probably less efficient (somebody is looping over the whole thing to get
``sum()``
) but it looks cleaner (to me). I might change it though.
Might just go with this, it seems easier to explain:
Copy code
``````fun solvePart2(): Int =
input.map { seatId(it) }.sorted().run {
(first()..last()).zip(this).first { it.first != it.second }.first
}``````
e
I just did
``zipWithNext``
on a sorted list and find the first pair that doesn't fit. Might be a bit more easier to explain than zipping with the range, but idk. Link.
t
Oh, that makes sense too. Nice.
I'm stealing that, I like that one. I have six one-liner solutions to part 2 now to pick from. 🙂
e
And if you do it while parsing the input, you can just take the last element for Part 1. 🙂
t
Yeah, true. I run all these from unit tests and have a class per day, so each part is calculated independently. But yeah, we could just make part 1 and part 2 one big expression today! 🙂
m
Since we're all open with the stealing part...let it be known that I steal a lot from your solutions in this channel 😊
t
I don't steal until I've taken a crack at it. And then I'll come here or go on reddit and find some optimization I missed. 🙂
m
Yeah exactly, was about to edit my answer. I kinda go solve, refactor myself, check here/with colleagues/Reddit, refactor again
e
I feel kinda bad about myself, because I didn't figure out that you don't need to do a binary search sort of a thing, but just parse it as binary. I got my answers and then changed it, because I prefer that solution. Need to think outside the box more often. 🙂
m
I think that's kinda the beauty of AoC though, and IMO that's how you get the most out of it!
t
FWIW I got about half way done with following the method on the puzzle before I realized I could do that. And I fully implemented it as binary before I realized I didn't have to split the string or multiply. And judging by the reddit thread, we're not alone.
b
Copy code
``````import helpers.linesFile
import helpers.rFindGroupsDestructured

fun main() {
val seats = linesFile("data/2020/05_input.txt").map { line ->
val (valRaw) = line.rFindGroupsDestructured("([FB]{7}[LR]{3})")
val value = valRaw.map { if (it in setOf('B', 'R')) 1 else 0 }.joinToString("").toInt(2)
value.shr(3) * 8 + (value.and(7))
}
println("Part 1: \${seats.maxOf { it }}")
val ids = seats.map { it }.toSet()
println("Part 2: \${((ids.minOrNull() ?: 0)..(ids.maxOrNull() ?: 1023)).toSet() - ids}")
}``````
oh I just saw I can simplify that
I have remnants of "I don't know what they are going to do next
n
yeah. i had a dataclass for the seats initially
then in part 2 i realized you didn't need that all at all and could just work 100% with ids, which I didn't expect
b
Copy code
``````fun main() {
val seats = linesFile("data/2020/05_input.txt").map { line ->
val value = line.map { if (it in setOf('B', 'R')) 1 else 0 }.joinToString("").toInt(2)
value.shr(3) * 8 + (value.and(7))
}
println("Part 1: \${seats.maxOf { it }}")
val ids = seats.sorted()
println("Part 2: \${((ids.first()..ids.last()).toSet() - ids.toSet()).first()}")
}``````
yes same here for the data class, and I started to write a binary partitioning function and then realized it was simply binary…
I'm glad I can exploit what I learned to do in assembly 😄
👏 1
j
😲 1
a
jakub pls keep going with the animations
j
Only as long as they're doable in Kotlin 🙂
e
b
haha neat
is it involving kotlin in any way?
oh my you generated the animations
j
@ephemient - i love it. Beautiful.
a
that hits different