This Scala solution of <adventofcode.com/2024/day/...

# language-evolution

[Edgar Avuzi]

This Scala solution of adventofcode.com/2024/day/4 makes me want to have
for comprehension in Kotlin

[Edgar Avuzi]

import scala.io.Source

object Main

val XMAS = "XMAS"

val directions: List[(Int, Int)] = List(
  (0, 1), // Right (horizontal)
  (1, 0), // Down (vertical)
  (1, 1), // Diagonal down-right
  (1, -1), // Diagonal down-left
  (0, -1), // Left (reverse horizontal)
  (-1, 0), // Up (reverse vertical)
  (-1, -1), // Diagonal up-left
  (-1, 1) // Diagonal up-right
)

@main def run(): Unit = {
  val grid =
    Option(Main.getClass.getClassLoader.getResourceAsStream("input4.txt"))
      .map(Source.fromInputStream)
      .map(_.getLines().toList)
      .getOrElse(List.empty)
  val count = for {
    i <- grid.indices
    j <- grid(i).indices
    (dx, dy) <- directions
    if isMatch(grid, i, j, dx, dy)
  } yield 1
  println(s"Total occurrences of XMAS: ${count.sum}")
}

def isMatch(grid: List[String], i: Int, j: Int, dx: Int, dy: Int): Boolean = {
  val endX = i + (XMAS.length - 1) * dx
  val endY = j + (XMAS.length - 1) * dy
  (grid.isDefinedAt(endX) && grid.isDefinedAt(endY)) &&
    XMAS.indices.forall { k =>
      grid(i + k * dx)(j + k * dy) == XMAS(k)
    }
}

[Edgar Avuzi]

At the moment, I can't see a denested Kotlin implementation comparable to this Scala solution.
In Kotlin, it would require 4 nested loops.
The only alternative seems to involve denesting with functions, but that’s a different approach altogether.
If I’m not mistaken

[ephemient]

not this example but Scala definitely abuses their for-notation for some very non-for-like things 😛

[ephemient]

it wouldn't take that much nesting in Kotlin though:

val count = grid.indices
    .flatMap { i -> grid[i].indices.map(i::to) }
    .flatMap { ij -> directions.map(ij::to) }
    .count { (ij, dxdy) -> isMatch(grid, ij.first, ij.second, dxdy.first, dxdy.second) }

[ephemient]

Scala's for comprehensions desugar into a chain of flatMap calls somewhat like that

[Edgar Avuzi]

Thanks! Now the Kotlin code looks like this. It's fine. It's just my programming incompetence—I didn't even think of desugaring it like this.
Perfect

const val XMAS = "XMAS"

val directions: List<Pair<Int, Int>> = listOf(
    Pair(0, 1),    // Right (horizontal)
    Pair(1, 0),    // Down (vertical)
    Pair(1, 1),    // Diagonal down-right
    Pair(1, -1),   // Diagonal down-left
    Pair(0, -1),   // Left (reverse horizontal)
    Pair(-1, 0),   // Up (reverse vertical)
    Pair(-1, -1),  // Diagonal up-left
    Pair(-1, 1)    // Diagonal up-right
)

fun main() {
    val grid =
        ({}.javaClass.classLoader.getResourceAsStream("input4.txt") ?: return)
            .reader()
            .use { it.readLines() }
    
    val count = grid.indices
        .flatMap { i -> grid[i].indices.map(i::to) }
        .flatMap { ij -> directions.map(ij::to) }
        .count { (ij, dxdy) -> isMatch(grid, ij.first, ij.second, dxdy.first, dxdy.second) }

    println("Total occurrences of XMAS: $count")
}

fun isMatch(grid: List<String>, i: Int, j: Int, dx: Int, dy: Int): Boolean {
    val endX = i + (XMAS.length - 1) * dx
    val endY = j + (XMAS.length - 1) * dy
    return (endX in grid.indices && endY in grid[0].indices)
            &&
            XMAS.indices.all { k ->
                grid[i + k * dx][j + k * dy] == XMAS[k]
            }
}

[CLOVIS]

Hey! Look at what you can do with Parameterize (#C06083PAKEK):

val count = sequence {
    parameterize {
        val i by parameterOf(grid.indices)
        val ij by parameterOf(grid[i].indices.map(i::to))
        
        yield(directions.map(ij::to))
    }
}.count [ (ij, dxdy) -> isMatch(grid, ij.first, ij.second, dxdy.first, dxdy.second) }

That looks fairly close to the Scala example 🤔

[Edgar Avuzi]

Would be cool if they put it into Kotlin Arrow lib

[ephemient]

yeah these things aren't honestly that hard to write, I made one for our internal test use before I heard of Parameterize which seems to have a similar origin https://kotlinlang.slack.com/archives/C0BJ0GTE2/p1709272607955079?thread_ts=1709271304.876229&amp;cid=C0BJ0GTE2

[CLOVIS]

yeah, I had one as well. I found out about Parameterize when I was wondering whether I should make it a public lib

[ephemient]

I suppose one thing mine has going for it is that it works in suspend, so we have tests that do

@get:Rule
val errorCollector = ErrorCollector()

@Test
fun test() = runTest {
    chooseAll(errorCollector::addError) {
        coroutineScope {
            val foo = choose(...)
            val bar = choose(...)

but I have been thinking that longer-term it's probably better to build this on top of the Compose machinery instead, so that we get to have the benefits of skipping (which is more likely what a user would expect)

Untitled.kt

[CLOVIS]

oh wow yours is very different internally

[Youssef Shoaib [MOD]]

With Kontinuity you can do this! It'd look roughly like:

var sum = 0
runChoose {
  val i = grid.indices.bind()
  val j = grid[i].indices.bind()
  val (dx, dy) = directions.bind()
  ensure(isMatch(grid, i, j, dx, dy))
  sum++
}

and it implements the "skipping" mentioned earlier in this thread. It uses multishot continuations, and so it's able to resume this coroutine multiple times. I even have a PR for Parameterize that uses Kontinuity to make it no longer finicky (e.g. you can do side effects safely in here, while in Parameterize, they get repeated).
It's even better that Scala's for comprehensions, actually. You can extract functions!

context(_: Choose)
fun List[String].someCoord(): Pair<Int, Int> {
  val i = this.indices.bind()
  return i to this[i].indices.bind()
}
var sum = 0
runChoose {
  val (i, j) = grid.someCoord()
  val (dx, dy) = directions.bind()
  ensure(isMatch(grid, i, j, dx, dy))
  sum++
}

You can't do that in Scala! I need to add some docs and helpful examples to the library eventually, but in the meantime, you can have a look around the tests!

[Edgar Avuzi]

Youssef, thanks a lot for looking into it. I’ll take a look and see if I can wrap my head around it 😄

[Youssef Shoaib [MOD]]

Don't hesitate to reach out if you need any help!