https://kotlinlang.org logo
Join Slack
Powered by
:space_invader:*Day 14 solution thread*:kotlin:
# advent-of-code
b
👾*Day 14 solution thread*K
Yay Rank 276 \o/
it is so ugly 😄
a
Rank 559
👍 2
I didn’t read closely and thought the 0 and 1 mask for part 2 were the same as in part 1
@bjonnh ha our code looks so similar
b
there was another way to do it
with double masking
a
what?
b
you transform the ternary mask into two masks
a
oh
b
I was almost going for that and then realized it was really just strings mangling
a
i just wrote this to transform the masked strings
Copy code
fun rec(currString: String, currIndex: Int): List<String> {
    if (currIndex == addt.lastIndex + 1) return listOf(currString)
    return if (currString[currIndex] != 'X') rec(currString, currIndex + 1)
    else {
        rec(
            currString.toMutableList().apply { this[currIndex] = '1' }.joinToString(""),
            currIndex + 1
        ) + rec(
            currString.toMutableList().apply { this[currIndex] = '0' }.joinToString(""),
            currIndex + 1
        )
    }
}
b
oh
yeah that's a way too
a
dw ik your way is a lot better 😂
😎 1
b
That's good there are less and less people doing it so maybe we can get in the leaderboard 😄
🤣 1
that's also probably the bests that stay
I can see how frustrating it can become if it takes hours every day
n
Did you guys brute force part 2
j
nope. also - after each "mask = " line I precalculated all possible masks, so the next "mem[addr] =" didn't have to recalculate it over and over
n
Yeah. By brute force I mean avoiding inserting all the possible memory values
Avoiding the solution being exponential in the number of Xs
t
@Nir I kept the masks with the Xs and did not insert all memory values. It just needed a way to remove overlapping masks and that turned out to be quite easy (relatively speaking). Not sure about the complexity though, because the more Xs are in the input the more overlap there is. Should still be better than generating all memory locations. https://github.com/TimothyEarley/advent-of-code-2020/blob/master/src/main/kotlin/de/earley/adventofcode/day14/Day14.kt
n
Yeah I thought about doing something like that, it seems quadratic in the number of instructions
Which is arguably still better than exponential in Xs
e
very easy part 1 with two masks
bit manipulation to generate the addresses for part 2 in O(popcount) time, without branches
n
what's popcount?
e
population count, e.g. number of 1's in the bit representation
std::popcount
in C++, 
popCount
in Haskell, ... popcount is the name I know it by in most languages, but for some reason it's 
.countOneBits()
in Kotlin
n
it still seems exponential in the number of X's though, unless I'm misunderstanding
e
yes, it's run 2^popcount times
at least in my input, there's no more than 9 X's so I am not super concerned. the bithacks only save a little bit of time anyhow
in the general case I don't think you can do better than exponential either
n
I spent a bunch of time last night thinking about this; I think it may be possible to have something that is quadratic in instructions, but no longer exponential in the number of X's
When i first read part 2 my first thought was that there's no way you can just insert all those entries into memory, a single instruction with 32 X's would blow you up
then I saw it seems to keep the number of X's down to make that approach ok
My idea though was to go through the instructions in reverse order; when processing a new instruction compare to all previous, and if there is overlap caused by the X's, then restrict the new instruction to eliminate the overlap
i'm just too lazy to code it though 🙂 It's rather tricky to get fully correct but I believe it can be made to work
e
I thought about it. it seemed to me that it could require splitting a instruction into multiple ones covering different ranges, and at that point you're potentially exponential
but I didn't think about it very hard so I could be wrong
n
yeah I see what you mean. It's possible for sure. Ah well, just need to buckle down and implement the standard way
b
@Nir if you have non overlapping memory regions, you could simply multiply the value by 2^numberofX for each address
n
Yes, but obviously you cannot assume you do
b
you could probably filter the regions that are non overlapping (different start)
n
yes but ultimately to use this approach you'll need to mediate regions that conflict
b
sure you revert to the other algorithm for that
n
well, if you revertto the other algo then you're just bck to exponential in X and then it's not that exciting 🙂
b
and in the case they did non overlapping regions (no idea what they did didn't look) it would be solved even faster
you could also submask the overlapping regions
to remove the things that would be overwritten anyway
j
for any 
mask=
entry you need to calculate possible floats anyway, so what's the gain here?
n
floats?
j
the "floating bit" possibilities, however you want to call that
n
If you could reasonably quickly reduce it to disjoint reasons, then you would save exponential behavior in X
right now the behavior in the number of X's is exponential, which is obviously really bad
if there was a single mask with 33 X's for example all the solutions I've seen posted so far, would break in Kotlin
if you reduce it to disjoint reasons then you don't need to iterate over all X's any more, you just as bjonnh said do 2^numberOfX
j
of course, I wonder if anyone had more than 10X in their puzzle input. Mine was 14 masks with 9X, 21 with 8X, the rest was smaller. Still done pretty quick (way quicker than the "game of seats" puzzle).
t
My solution that I posted above handles 33 X's fine. In fact it helps, since that many X's override loads of other memory locations and we are left with fewer saved masks. The way to break my implementation is to somehow fragment the address space so the masks become useless
n
cool I'll check it out
b
I wonder if someone is going to do an electronic version of that puzzle 😄
that would be pretty easy with a few counters and gates
well you still have to get the memory somehow, that's probably less fun with a 36bits address space…
n
e
instead of 
2.0.pow(index)
just use 
1 shl index
👍 1
(or do some char replacement and use 
String.toInt(base)
)
n
yeah, 2.0.pow(index) felt pretty suboptimal I admit
thanks for the tip
don't know how to bitshift without my >> and << 🙂
e
n
Eh I mean I kind of agree, I don't see any compelling reason for it
bit manipulation is hardly the most common code to write in kotlin, and writing 
shl
or 
and
isn't that big of a deal
e
the lack of precedence is really jarring
0 until 1 shl n
parses as 
0.until(1).shl(n)
which is obvious nonsense
n
Yeah, I personally tend to use parens pretty heavily when I write this kind of code anyway though
it's nice for "write only" code if you're very familiar with precedence but it's a lot more fragile in a real codebase
b
Just voted and advertised a bit for that issue
bitwise operations are ridiculous in kotlin
as much as I don't really agree having overloadable bitwise operators because people will write stupid DSLs with it that makes everything impossible to understand
n
I don't think the ridiculous overloading argument is very strong. People used to complain about endlessly about that in C++ in like, the 90's
25 years later and we see that this just isn't a real issue. Yes you will probably find horrible code somewhere that overloads operators in silly ways but it's pretty rare.
C#, C++, and python all allow overloading bitwise operators, can ask all three communities if there are any regrets
b
n
don't think I understood that "as well"; this is a bit set class, it's not a bitwise operator nor overloading for it, neither of which kotlin has
t
b
oh meaning: we could have done it with that too instead of using strings
cool I didn't know about substringBefore and substringAfter
that's nice, I'll make a substringBetween in my helper functions
13 Views
Open in Slack
PreviousNext
Powered by