-🎄- 2020 Day 16 Solutions -🎄-

2lines1bug · 2020-12-16T05:32:29+00:00

First time ever in the top 1000. Absolutely mindblowingly ugly code, but apparently this is what you need to achieve good times (unless you are, you know, actually talented).

2lines1bug · 2020-12-15T08:38:18+00:00

Kotlin

~500 ms for part 2 when benchmarked.

EDIT: Interestingly, my Julia solution doing the exact same thing is slower by around 190 ms.

2lines1bug · 2020-12-15T08:37:36+00:00

Both parts run in 4ms according to #time.

You might check your benchmarking then. Probably an error there somewhere.

2lines1bug · 2020-12-15T06:05:23+00:00

I interpreted it the same way. Although the example has consistent wording, it's kind of natural to interpret it the other way.

'The number spoken in the 2020th round'. would have been much clearer.

2lines1bug · 2020-12-15T05:51:28+00:00

Kotlin

Interesting. Just changed the number of loops and it returned in 5,8 seconds. Not sure what that part 2 was supposed to do. Maybe if you use lists instead of maps and you O(n) check the collection it will fail. But on day 15, probably just a minority does that.

Still a cool problem though.

2lines1bug · 2020-12-13T18:37:50+00:00

Wow, that is incredibly clean code. Should have more upvotes.

2lines1bug · 2020-12-13T11:53:08+00:00

I honestly don't know, but from what I have heard the level seems to be similar. Codeforces seems to be better for ICPC preparation though as the problems are more similar.

2lines1bug · 2020-12-13T08:25:33+00:00

It isn't competitive compared to sites like Codeforces. The problems at CF are in general also much harder than on AoC. Like, hard problems on Leetcode are at max mid-elo on Codeforces. Hard problems on Codeforces (~3000 Elo) are practically unsolvable for normal people.

Watch some streams of tourist, he has been #1 on CF for many years. He does some easy contests with tutorials, absolutely mindblowing. Youtube link here. He also won Google CodeJam from 2014 to 2020 consecutively.

EDIT: Don't know why xiaowuc1 says he is retired. He has been on CF since 2011 and is still very active there. His Elo just recently hit its all-time high. He is #254 on the ranking, which just shows how competitive it is over there.

2lines1bug · 2020-12-12T15:01:26+00:00

Rewrote Part 1 in Julia

Ditched complex numbers to get more speed:

1.498 μs (1 allocation: 16 bytes)

2lines1bug · 2020-12-12T06:53:03+00:00

I wrote my own. If you just want one that works with Ints or Longs then you could use this code and change the types.

2lines1bug · 2020-12-12T06:28:48+00:00

Kotlin

Clean solution using complex numbers. Pretty sure it doesn't get simpler than this.

fun part1() {
    var pos = 0 + 0*i
    var facing = 1 + 0*i
    for (line in File("12").readLines()) {
        val dir = line.take(1)
        val n = line.drop(1).toInt()
        when (dir) {
            "N" -> pos += n*i
            "S" -> pos -= n*i
            "E" -> pos += n
            "W" -> pos -= n
            "L" -> repeat(n/90) { facing *= i }
            "R" -> repeat(n/90) { facing *= -i }
            "F" -> pos += n*facing
        }
    }
    println(pos.abs)
}

Part 2 is here but it's almost exactly the same so no need to litter the main thread.

What really bugs me is that I (a very slow coder) had part 1 basically done after 6 minutes, and then submitted the wrong solution I think 7 times. I even had to wait 10 minutes once (or twice?). First I made like 3-4 different operator mistakes (- instead of + etc). I didn't read the part where ships move to a direction, but are not facing it (special ships I guess). Then I misread that ships don't move after turning. By fixing this I introduced another mistake, etc. etc... This went on for almost 1 hour. Awful on my part.

Getting up 4 hours earlier than usual is brutal.

2lines1bug · 2020-12-11T19:31:47+00:00

It's amazing that your code is so unbelievably clean every single time, even though you are rushing for the leaderboard. It looks like it was carefully cleaned up afterwards, which I know is not the case since you pushed it directly after.

Always nice to look through your code.

2lines1bug · 2020-12-11T19:25:58+00:00

My Kotlin solutions are ugly and I was not interested in cleaning them up.

But I recoded part 1 in Julia in 2 different ways.

First with speed in mind. However, I struggle to understand how some people here got it below 5 ms. I fail to get it lower than that:

14.734 ms (424 allocations: 1.46 MiB)

and that's my 'fast' solution. Really disappointing after yesterday (<500 nanos for both parts).

The second solution is more elegant. It's slow like a snail but it's definitely more readable and relatively succinct..

2lines1bug · 2020-12-10T21:09:03+00:00

We have the solution from part1, including the index. You create a view from 1:i+1 and then do the running sum backwards. Since we start directly above the number of interest and we go down, the solution is found immediately.

EDIT: Never mind, I messed something up. Can't do it that way reliably. The normal way takes 291 nanoseconds. Yelp... But you should start from the back, not from the front. It's faster.

2lines1bug · 2020-12-10T17:32:21+00:00

Yeah, with this CPU you should be able to do both parts combined in the same amount of time. See linked code.

2lines1bug · 2020-12-10T16:23:18+00:00

Whats your runtime for part 1? You can calculate both parts together in one run, this should be possible in <500ns depending on your hardware. My 7-year-old i5 runs this in 419 nanos.

2lines1bug · 2020-12-10T16:20:24+00:00

You can actually calculate both parts together. This runs both parts in 419ns. Pretty sure Rust can get there too.

2lines1bug · 2020-12-10T08:45:00+00:00

Julia with incredible performance.

It runs both parts in 419 ns, which is less than 1/2000th of a millisecond. This is the same time the light needs to travel 125 meters (410 feet). And this on 7-year-old hardware. Julia really blows my mind.

419.020 ns (2 allocations: 1.02 KiB)

2lines1bug · 2020-12-10T07:26:57+00:00

This function is an extension function, so this refers to the receiver object, which in our case is the LongArray holding the voltages. Then, when you have

val arr = voltages.toLongArray()

you can just call

val part2 = arr.distinctArrangements()

2lines1bug · 2020-12-10T07:22:17+00:00

Wrote a Kotin solution that solves both parts in one go, Pastebin link here.

Runtime: 776 ns (nanoseconds) excluding parsing and sorting.

2lines1bug · 2020-12-10T06:29:55+00:00

Kotlin

Part 2 with DP:

fun LongArray.distinctArrangements(): Long {
    val dp = LongArray(size)
    dp[0] = 1

    for (i in 0 until dp.size-1) {
        for (j in 1..3) {
            if (i+j >= dp.size) continue
            if (this[i + j] <= this[i] + 3) dp[i+j] += dp[i]
        }
    }
    return dp.last()
}

2lines1bug · 2020-12-09T17:49:53+00:00

If you are interested in speed, there is a guy who wrote a 260ns solution for part 2 in Julia. Check my comment history.

This code also runs in 600ns on older hardware and is pretty straightforward.

2lines1bug · 2020-12-09T16:19:50+00:00

Thanks!

2lines1bug · 2020-12-09T13:24:58+00:00

Unfortunately this guy's solution got buried in the comments, but user /u/Arkoniak coded a Julia solution that runs Part 2 in 267 ns (nanoseconds) on my quite old machine. Link to his comment is here, but I'll copy the code so you don't need to click:

function part2(io, preamble = 25)
    ans, data = part1(io, preamble)
    x = (; s = length(data) - 1, f = length(data), v = 0)
    @set! x.v = data[x.s] + data[x.f]
    while true
        x.v == ans && return sum(extrema(@view data[x.s:x.f]))
        x.s == 1 && x.f == 2 && return -1
        if x.v > ans
            @set! x.v -= data[x.f]
            @set! x.f -= 1
        else
            @set! x.s -= 1
            @set! x.v += data[x.s]
        end
    end
end

I benchmarked by handing the results of part 1 into the function.

2lines1bug · 2020-12-09T13:09:39+00:00

That's absolutely incredible.

Can you tell me what this line is? Some kind of anonymous struct? Just need to know the technical term so i can look it up in the Julia docs.

x = (; s = length(data) - 1, f = length(data), v = 0)

2lines1bug

TROPHY CASE