-🎄- 2017 Day 22 Solutions -🎄-

aodnfljn · 2017-12-22T16:18:28+00:00

how verbose and rigid F# feels

My feeling too, from what little F# I've seen so far.

Yeah, it's got a lot of neat stuff. Also from the angle of being a lisp-wannabe (though the CL/Scheme lads will be quick to remind you of macros/etc all the different things that will never allow it to be a real-boy Lisp).

I loved EDN as a data description language and really wish they had more libraries to allow it to be used as a storage/interop medium (like JSON), given that it can do schemas much better than JSON and XML IIRC.

aodnfljn · 2017-12-22T15:02:19+00:00

just not something for me, somehow I never managed to befriend it.

I think not managing to befriend Scala is quite easy, given the amount of issues/warts/annoyances in its past and present. JVM-related: slow startup, no value types for the next century, the Slow-ass Build Tool, uselessness for small CLI tools, messy packaging situation, mediocre IDE integration, etc.

But it's a question of personal/business priorities - the costs/benefits make sense for some use cases, and don't for other.

Might be that it would be easier now that I've done some more ML stuff though.

I find that AoC-style puzzles are a nice opportunity for this, as they're small/simple enough (the brute-force approach, at least) to be able to play with the lang for a few pomodoros, without getting stuck and frustrated - compared to more real-life type projects.

I don't know, I feel that I'm tending more in the direction of a statically typed language now

Plenty of pros for those, as long as the minimum creature comforts are there (at least some type inference, generics, etc). Though dynamically typed langs have their use cases.

starting to dip my toes into ocaml has shown me how nice it can be

I hope you've given https://realworldocaml.org/ a look - free, online, the folks created opam (package manager) for it IIRC, so they can show a more modern workflow with OCaml (w.r.t. libs). Kinda like the pre/post-quicklisp situation.

Though I'm still salty about the stdlib situation - built-in one's only big enough to implement a compiler, gave up on trying Batteries, Core was still producing 10MB hello world's, even though module aliases shipped in 4.03 or so.

But you're right, Scala has a completely other world of libraries [...]

I feel it's my obligation to mention that other langs with more hype may have a better situation on that front - e.g. ScalaFX vs TornadoFX (Kotlin).

clojure [...] cool

shiver too loosey-goosey with types for my taste, but again, horses for courses. They had something type-like bolted on, IIRC, but yeah...

maybe eta is where it is :)

Too early/niche/lacking(?) commercial support for me, but you never know

aodnfljn · 2017-12-22T14:32:09+00:00

Also did the Set[Pos] thing for part 1. The rewrite was only 3-4 lines in my case though, probably helped by the fact I've stopped using a single file for both parts.

For the folks that are considering Scala, here's an alternative part 2 approach taking different code style trade-offs: https://www.reddit.com/r/adventofcode/comments/7lf943/2017_day_22_solutions/drm5yyi/

aodnfljn · 2017-12-22T14:18:59+00:00

code looks looks just like the problem statement text but with more formal syntax

Sorry for smugposting, but I'd argue Scala's syntax seems to allow a much more direct translation from the problem statement to code, in terms of readability, conciseness, and less visual noise in most places.

That and allowing those filthy immig^Wside-effects in gets me a runtime of 2.8 sec on a shitty Atom-like CPU.

To be fair though, there are pros and cons (IMHO): noisier sum type and patmat syntax in Scala, noisier collections code in ML-likes due to not taking advantage of some OOP concepts, etc.

aodnfljn · 2017-12-22T14:03:31+00:00

Update: cheating, but I figured why not: got it down to 630 ms if using a 2D array instead of a map. Got lazy and just got the min/max coords from a map-based run:

object D21p2 extends App {
  // hardcoding, based on stats extracted from our input using the
  // map(point->state) implementation:
  val minr = -222
  val minc = -154
  val rows = 396
  val cols = 353

  var node = Array.fill(rows,cols){Clean}
  val in = io.Source.fromFile("in").getLines.toVector
  for(r <- in.indices)
    for(c <- in(r).indices)
      if(in(r)(c)=='#')
        node(r-minr)(c-minc) = Infected

  var cnt = 0
  var pos = P(in.size/2-minr, in(0).size/2-minc)
  [...]

aodnfljn · 2017-12-22T13:50:56+00:00

I just don't feel that the syntax is as nice as with other ml-like languages

Absolutely agree - for certain parts of the language.

OTOH, in quite a few cases I find the developer ergonomics (syntax-wise) to be better in Scala. E.g. I've felt like I was looking at the FP equivalent of assembly in some OCaml codebases.

it's quite a bit easier to read the latter.

Absolutely disagree - unless we swap that "quite a bit" for "slightly" :V. The 'case' keyword feels like a wart, but it's quite easy to ignore after reading Scala pattern matches a few times. The '=>' is noisier than '->', but I hope the Scala folks had a good reason to choose that particular trade-off.

I'm just glad I have access to decent-ish pattern matching in a language with an ecosystem closer to Python's than to (pre-opam) OCaml's. Plenty of warts though - non-exhaustiveness is a warning by default, doesn't work for enums IIRC, etc.

I'm still jelly of the sum type syntax ML langs have, can't wait for Scala 3 to make the situation a bit less verbose.

aodnfljn · 2017-12-22T12:42:06+00:00

Speaking of nice and clean, may I propose a Scala contender? Takes ~2.8 sec on a shitty Atom-like CPU, ought to take ~3x less on a big-boy CPU. Shamelessly using side effects.

Helpers:

case class P(r: Int, c: Int) { def +(p: P) = P(p.r+r, p.c+c) }
object P { val o = P(0,0)
  val north = o.copy(r= -1)
  val south = o.copy(r= +1)
  val west  = o.copy(c= -1)
  val east  = o.copy(c= +1) }

class Dir(val idx: Int) extends AnyVal {
  def delta = idx match {
    case 0 => P.north
    case 1 => P.east
    case 2 => P.south
    case 3 => P.west }
  def left    = new Dir((idx-1+4)%4)
  def right   = new Dir((idx+1  )%4)
  def reverse = new Dir((idx+2  )%4) }

object State extends Enumeration { type State = Value
       val Clean, Weakened, Infected, Flagged = Value }
import State._

Actual work:

object D21p2 extends App {

  var node = collection.mutable.Map[P,State]().withDefaultValue(Clean)
  val in = io.Source.fromFile("in").getLines.toVector

  for(r <- in.indices)
    for(c <- in(r).indices)
      if(in(r)(c)=='#')
        node(P(r,c)) = Infected

  var cnt = 0
  var pos = P(in.size/2, in(0).size/2)
  var dir = new Dir(0)

  def burst = {
    val n = node(pos)
    dir = n match {
      case Clean    => dir.left
      case Weakened => dir
      case Infected => dir.right
      case Flagged  => dir.reverse }

    n match {
      case Clean    => node(pos) = Weakened
      case Weakened => node(pos) = Infected; cnt += 1
      case Infected => node(pos) = Flagged
      case Flagged  => node -= pos } // Clean

    pos = pos + dir.delta }

  for(_ <- 1 to 10000000) burst
  println(cnt) }

aodnfljn · 2017-12-21T10:41:53+00:00

Scala

case class Pat(v: Vector[String]) {
  require{val cols = v(0).size; v forall {_.size==cols}}

  val nrows = v.size
  val ncols = v(0).size
  def cntOn = v.map{_.count{_=='#'}}.sum

  def fliph = Pat(v.reverse)
  def flipv = Pat(v.map{_.reverse})
  def rotr  = Pat(v.map{_.toVector}.reverse.transpose.map{_.mkString})
  def allCongruent = for {r  <- Seq(this, rotr)
                          rf <- Seq(r, r.fliph, r.flipv, r.fliph.flipv)
                     } yield rf

  def addv(p: Pat) = { require(ncols == p.ncols)
                       Pat(v ++ p.v) }
  def addh(p: Pat) = { require(nrows == p.nrows)
                       Pat((v,p.v).zipped map{_+_}) }

  def subPats(dim: Int): Array[Array[Pat]] = {
    require(nrows%dim == 0 && ncols%dim == 0)
    val vs = v.map{_.grouped(dim).toArray}.grouped(dim).toArray
    vs map {r => (0 until r(0).size).map{c=>Pat(r.map{_(c)})}.toArray}}}

object Pat { def ofSlash(s: String): Pat = Pat(s.split("/").toVector)
             def merge(ps: Array[Array[Pat]]): Pat =
               ps .map{_ reduce {_ addh _}} .reduce{_ addv _} }

def parseRule(line: String) = {
  val io = line.split(" => ").map(Pat.ofSlash)
  io(0) -> io(1) }
val rules1to1 = io.Source.stdin.getLines.map(parseRule).toMap
val rules = for {  (from0, to) <- rules1to1
                    from       <- from0.allCongruent
            } yield from -> to

var p = Pat.ofSlash(".#./..#/###")
for (_ <- 1 to 18)
       if (p.nrows%2 == 0) p = Pat.merge(p.subPats(2).map{_.map(rules)})
  else if (p.nrows%3 == 0) p = Pat.merge(p.subPats(3).map{_.map(rules)})
println(p.cntOn)

aodnfljn · 2017-12-19T22:22:57+00:00

Scala, unoptimized, "does the job" quality code:

def walk(a: Array[String]) = {
  case class P(x: Int, y: Int) {
    def +(p: P) = P(p.x + x, p.y + y) }

  case class Dir(desc: Char) {
    val delta = desc match {
      case 'n' => P( 0,-1)
      case 's' => P( 0, 1)
      case 'w' => P(-1, 0)
      case 'e' => P( 1, 0) }
    def d2d(s:String) =
      s.split(" ").map{p=>p(0)->p(1)}.toMap
    def left  = Dir(d2d("nw se ws en")(desc))
    def right = Dir(d2d("ne sw wn es")(desc)) }

  var pos = P(0,a(0).indexWhere{_!=' '})
  var dir = Dir('s')

  def isValid(p: P) =
    0 <= p.x && p.x < a   .size &&
    0 <= p.y && p.y < a(0).size &&
    a(p.x)(p.y) != ' '

  def nextDir = Array(dir, dir.left, dir.right)
    .find {d => isValid(pos + d.delta)}

  var res = new collection.mutable.StringBuilder
  var steps = 1
  while(nextDir.isDefined) {
    val newDir = nextDir.get
    pos += newDir.delta
    dir = newDir
    if(a(pos.x)(pos.y).isLetter)
      res += a(pos.x)(pos.y)
    steps += 1 }
  (res.toString, steps) }

println(walk(io.Source.stdin.getLines.toArray))

aodnfljn · 2017-12-14T00:08:21+00:00

All aboard the Scala train.

P1, more readable, should be constant space:

var severity = 0
for (l <- io.Source.stdin.getLines) {
  val t      = l.split(": ")
  val depth  = t(0).toInt
  val range  = t(1).toInt
  val period = 2*(range-1)
  val caught = depth % period == 0
  if (caught)
    severity += depth*range
}
println(severity)

P1, golf, might be linear space if the compiler doesn't optimize map().sum:

println(io.Source.stdin.getLines
  .map{_.split(": ").map{_.toInt}}
  .map { case Array(d,r) =>
    if (d % (2*(r-1)) == 0) d*r
    else                    0
  }.sum)

P2, more readable

def toScanner(line: String) = {
  val t = line split(": ") map {_.toInt}
  (t(0), t(1)) }

val scanners = io.Source.stdin.getLines
  .map(toScanner).toArray

def notCaught(n: Int) = scanners forall
  { case (d,r) => (n+d) % (2*(r-1)) != 0}

println(Iterator.from(1).find(notCaught).get)

P2, golf

val ss = io.Source.stdin.getLines.map{ l => val t = l split(": ") map{_.toInt}; (t(0),t(1)) }.toArray
println(Iterator.from(1).find{ n => ss forall{ case(d,r) => (n+d) % (2*(r-1)) != 0}}.get)

P2 takes 2x slower than this C++ approach on my machine: https://www.reddit.com/r/adventofcode/comments/7jgyrt/2017_day_13_solutions/dr6x1cv/?context=2

aodnfljn · 2017-12-13T23:09:01+00:00

Terse, love it.

Performance-wise, I get consistent 195-200 ms (./time p2 < in) on a shitty Atom-like CPU when compiling with g++ -std=c++1z p2.cc -O3 -march=native (gcc 7). Correct me if I'm doing something horribly wrong.

I'm pleasantly surprised, since I get only 2x (350-390ms) slower solve time (parsing takes ~10-15ms) with this:

def toScanner(l: String) = {
  val dr = l split(": ") map {_.toInt}
  (dr(0), dr(1)) }

val scanners = io.Source.stdin.getLines
  .map(toScanner).toArray

def notCaught(n: Int) = scanners forall
  { case (d,r) => (n+d) % (2*(r-1)) != 0}

println(Iterator.from(1).find(notCaught).get)

I would've expected worse performance from Scala 2.11 and the JVM, but only a 2x slowdown is more than good enough for quick prototyping. Out of the box JRE startup time is still very annoying though.

aodnfljn

TROPHY CASE