/aocg/ - Advent of Code 2018 General #40

I implemented my solution and so far it seems to do great. (even though it is quite slow)
it solved my own input and correctly.
Can you guys give me some more test inputs?

It's generally faster to write programs and thus make the leaderboard with scripting languages, but if you're not trying for the leaderboard c++ is fine.
It's not made for any language in particular.

That's exactly what led to said install error.
It sounded extremely slow, I've been trying to avoid that because I sometimes have hundreds of tied solutions on a step, each of which will have even more tied solutions on the next iteration. How is yours running fast enough?

>That's exactly what led to said install error.
Then I guess you need the sudo apt-get install z3

I caved in and copied a Z3 solution this morning just to pass, but gonna try again to solve this with LP, assuming I can remember shit

They don't want you to use GNU tools on windows. MINGW build fails with the error you mentioned. MSYS build succeeds but it looks for the lib with extension .so. After patching it to use the extension .dll, the build succeeds but segfaults.
I just ended up using a Z3Py binary release for win64 with mingw64-python. The release version segfaults as well, but the nightly build didn't.

pastebin.com/p8hbRzRU
297/126233088
My solution was complete bullshit, so I'm not going to bother checking it with anything else

Meant to be a reply to and

I sort by intersection count first and then by manhattan distance as second criterion to break ties.
then I work from the best candidates downwards. The solution converges quite quickly to the correct result (which I knew before ), but then I also get issues with tied results, since I cannot actually exclude them to be certain my solution is actually 100% correct.
I cannot prune them, because I do not know exactly where they will end up when scaling them. :/

>So is the solution for part 2 really to learn how to use z3? This is bullshit.
No, you can do recursive subdivision instead
Z3 might be easier though, I don't know what those solutions look like

LMAO these ppl got filtered xD

Attached: DvJZ2etUcAAs_L3.jpg (672x580, 61K)

They threw an NP-hard problem at us with a respectably sized data set and unless someone comes up with some way to exploit some quirk of the way the inputs were generated (or prove that P = NP lol), the best way any of us have come up with to solve this problem are with generally unreliable approximation algorithms (most of the last thread), or to bring out the heavy artillery by reducing the problem to a version of the maximum satisfiability problem, then feed that into a generic solver (Z3).

Some of us got inputs that shitty approximation algorithms work on and got their answer pretty quickly, but others (like me) got unlucky and had to take the latter approach. It's pretty bullshit desu

pastebin.com/j3UxJVSQ
P2: (45591145, 26525958, 51239070) len 123356173

They're like 20 lines
from z3 import *

def z3_abs(n):
return If(n >= 0,n,-n)

def z3_dist(a, b):
return z3_abs(a[0] - b[0]) + z3_abs(a[1] - b[1]) + z3_abs(a[2] - b[2])

x, y, z = Int("x"), Int("y"), Int("z")
tuplized = [((tuple(b[0:-1]), b[3])) for b in parsed]

orig = (x, y, z)
cost_expr = x * 0
for pos, range in tuplized:
cost_expr += If(z3_dist(orig, pos)

>P2: (45591145, 26525958, 51239070) len 123356173
Fuck, my program fails on that one :(

This shit was fun last year and the threads were way more active.. I'm pretty salty about today

Is that X,Y,Z ? If I check 45591145, 26525958, 51239070 specifically, my program says there are only 190 bots in range. Doesn't seem right, but I don't think I fucked up checking a solution either.

>pastebin.com/p8hbRzRU
yup, can reproduce (about 3 minutes till it converges, remaining elements to check (to be 100% certain) probably some hours, lul
but this can be optimized.
but for now I am happy with the algorithm. Much better than the guess and guess again method I had before.
(-943, 88346877)
(23175670, 25455557, 39715650)

is what my program is stuck on right now, I will let it run, in theory it should at some (reasonable) point in time reach the solution.

Good question, it's just what the program I posted along with it spit out. You might have to try different permutations to figure out if the order got mangled somehow. I don't understand this z3 shit, it filtered me pretty fucking good.

My program instantly says the answer is
Distance = 88894457,
Coords = [23449460, 25729347, 39715650],
Bot Count = 977

No idea if it's right though.

>P2: (45591145, 26525958, 51239070) len 123356173
Is this an answer to a different input or something? Because this point only has 190 bots in range on the input in that pastebin, while point (23449460, 25729347, 39715650) has 977

Fuck, yes, it is.
P2: (23449460, 25729347, 39715650) len 88894457
I accidentally copy/pasted the output from a different input and never double checked. Sorry, I'm retarded.

>but others (like me) got unlucky and had to take the latter approach. It's pretty bullshit desu
You should demand a refund.

> NP-hard
Nothing about this problem is NP-Hard, as far as I can tell. Brute force should be polynomial; it's just polynomial with a huge n.

it is polynomial in the size of the coordinates. but this means it is exponential in the size of the input. (which is log(n))
so it only pseudo-polynomial.
Someone earlier mentioned some reduction, so it might as well be NP-hard.

The input size (as in the literal byte size of the input file), depends on the size of the coordinates.
It's obvious that you can reduce this to MAX-SAT. It's not obvious to me that you can reduce MAX-SAT to this problem.

Day 23 is fucked up or it's me?

It took this for valid:
10615635,41145430,30249331 = 82010396 (981 bots)

But I found a point with more bots

10615635,41145430,30249333 = 82010398( 983 bots)

What the fuck is going on.

input: pastebin.com/VA69C0ya

yes, but brute forcing in 3-d is O(n^3), but writing down huge numbers takes only O(log(n)) space.
so it is O(e^3*n).

python advent23.new.py
(-983, 82010396)
(10615635, 41145430, 30249331)

it seems the correct spot has indeed 983 bots.

It's really common on this problem to get entirely incorrect coordinates and still get the right answer, probably something to do with the input generation algorithm or some shit.

The one with Z ending 331 actually has 983 bots (not 981)
The one ending 333 only has 973 (not 983)

This succeeded where my fucking around with divided radii in hopes of grabbing the right hitcounts while excluding false positives failed. I still don't really get how z3 works with somehow recursively running through references but it's cool.

wew, thought my approximiation algorithm finally failed on one

I refined the idea of solving the problem iteratively at different scales and using this heuristic to converge quickly.
I now rescale by a factor of 2.
and so far it works pretty quickly (

>Someone earlier mentioned some reduction, so it might as well be NP-hard.
I would like to see a reduction from MAX-Sat to 23 part 2, but if one exists it certainly isn't obvious.
We may as well consider 2-MAX-SAT which is also NP-Hard. Thus we want to take a formula that is a conjunction where every conjunct is a disjunct of two variables, and map it to a list of nanobots.
If the formula has n variables, then there are 2^n possible assignments. How on earth would you map these 2^n possible assignments into the 3d space of the problem, and map each disjunction of the form (p OR q) to a nanobot whose range contains every point corresponding to an assignments with p true or q true?
It sounds utterly impossible to me. That's not to say there isn't some reduction, but if there is, it's not as simple as people are assuming.

>How on earth would you map these
using perl or sed ;^)

there's binaries, use the nightly one because the legacy and "release" ones are super outdated github.com/Z3Prover/bin

It's just super lame when you're trying to do a skill-based programming challenge and many people including most who got on the top 100 leaderboard got to use much less skill

I've gotten it working, thanks.

Attached: orca.jpg (800x600, 55K)

>mom they're cheating on the internet again

I STILL BELIEVE

Probably not going to bother with AOC next year, this one has been a real drag. I'm gonna finish it though because I can't let Eric Wastl get the better of me.

The "lucky"/rigged inputs are okay when they're obvious, like when you can just glance at the input or write 1-2 lines of code and see that it has some useful property you can exploit. But here, checking the property is at least as hard as solving the actual problem, so basically the only way to take advantage is to guess and commit to a possibly-wrong solution up front.

It's still lame when one portion of people get an easier problem to solve than the rest

All the inputs are at least rigged to have a unique point with max bots, as far as I can tell
Also, there aren't a lot of near-miss overlaps, which is the reason the resolution scaling solution (mostly) works
I'm not sure any input is actually strictly easier. I think resolution scaling should work on every input, but not necessarily with the exact same parameters.

I don't think the inputs were of different difficulty. it was just that for each input only some of the heuristics worked. So it was much more of a gamble. (maybe apart from the SAT-solver problem killer, but it doesn't feel like this was the intended way to do it)

My first attempt at an algorithm would've gotten me rank 50 or so on the part 2 leaderboard if I had gotten an easy input, which I only found out later after going back and running it on some other anons' inputs after giving up and doing z3 shit this afternoon. I really wouldn't have deserved it though, my best rank for the entire year is 500ish on today's part 1, though I guess that's partly because that was only the third or fourth time I looked at the puzzle when it released, but mostly because I'm a slow, mediocre programmer.

>maybe apart from the SAT-solver problem killer
Recursive subdivision works too if you compute the upper bound precisely. ("Upper bound" for a region R being a number N such that num_bots_in_range(P)

>I really wouldn't have deserved it though
You would've deserved it as much as any of the people who got lucky

lol i usually spend an hour deciding if i should parse the input with streams or scanf, then another hour debugging the parsing

>slow, mediocre programmer
Doesn't matter so much on problems like 23b that rely much more heavily on coming up with a good algorithm than on the actual programming

>Tfw forgot how to do abs formulas in LP
Fug

i can come up with a million good algorithms in my head, but it somehow has to become machine readable

That's just silly
There's no reason you couldn't have written a bunch of text parsing helper functions by now
Since almost every question starts with parsing the input text

I just realized that scaling () is exactly the same idea as subdivision (here into sets of size of powers of 2) and your "upper bound" is the heuristic of adding a small bit to the radius.
I missed that completly up till now.

>t. hasn't used scanf and it's gorillion flags or std::cin's quirks

>not using a good language

I absolutely have to leave at 7AM if I want to see my family for christmas so I hope today's problem won't be too long

>caring about the leaderboard

youtube.com/watch?v=hjGZLnja1o8

TWO DAYS REMAIN

Attached: rs.jpg (480x360, 24K)

>Solve this modified grid recursive halting problem written in elfcode that is somehow SAT solvable

>I'm still back on day 20
Damn.
I also insist on doing them in order, too.

>your "upper bound" is the heuristic of adding a small bit to the radius
Not sure what your heuristic is but that doesn't sound right to me. Upper bound in my approach is literally the exact number of bots whose octahedron overlaps the region R in at least one point. Being able to compute this exactly means you can stop the search as soon as you've found a point and all remaining regions have smaller upper bounds (for me this is usually within 5-10s).

Today had better not be more asm reverse engineering bullshit

but it's the only thing I'm good for

Do you think Eric will have mercy on us? It's almost Christmas...

stop posting this shitty song

here's some REAL tunes as we close in on our final challenges
youtube.com/watch?v=re1IjZsUGtU

Last year, day 23 was the hardest, and 24 and 25 were quite easy

>4 days of asm
If he does that I fucking swear

The only "mercy" we get is that day 25 only has one part

youtu.be/ESx_hy1n7HA
Time again to spam the same 4 songs!

ok, the heuristics are not the 100% the same.
but if I scale down the problem by 2**n and increase all radii a bit this has almost the same effect as considering boxes of side length 2**n and looking for intersections with these boxes.
since "scaling down" the coordinates effectively "scales up" the "unit boxes"

Never, I'm going to post it every day next year too

TWO MINUTES

time for NP-hard 4d elf assembly problems!

Oh shit, I just realized I've been up for 24+ hours
I'm the user who missed the last puzzle because I was playing sudoku on the shitter and lost track of time

OH SHIT I GOTTA FUCK

FUCK

FUCK!
second to last chance to redeem myself!!

FUCK

WALL OF FUCKING TEST
I'M OUT

ugh fuck this

IT'S JUST BUILD A FUCKING ROGUELIKE COMPLETE WITH MAGIC SYSTEM

>more fighting shit

Attached: 1444699428422.jpg (206x212, 6K)

WTF IS THIS SHOT LMAO
Immune System:
2991 units each with 8084 hit points (weak to fire) with an attack that does 19 radiation damage at initiative 11
4513 units each with 3901 hit points (weak to slashing; immune to bludgeoning, radiation) with an attack that does 7 bludgeoning damage at initiative 12
5007 units each with 9502 hit points (immune to bludgeoning; weak to fire) with an attack that does 16 fire damage at initiative 2
2007 units each with 5188 hit points (weak to radiation) with an attack that does 23 cold damage at initiative 9
1680 units each with 1873 hit points (immune to bludgeoning; weak to radiation) with an attack that does 10 bludgeoning damage at initiative 10
1344 units each with 9093 hit points (immune to bludgeoning, cold; weak to radiation) with an attack that does 63 cold damage at initiative 16
498 units each with 2425 hit points (immune to fire, bludgeoning, cold) with an attack that does 44 slashing damage at initiative 3
1166 units each with 7295 hit points with an attack that does 56 bludgeoning damage at initiative 8
613 units each with 13254 hit points (immune to radiation, cold, fire) with an attack that does 162 radiation damage at initiative 15
1431 units each with 2848 hit points (weak to radiation) with an attack that does 19 cold damage at initiative 1

Infection:
700 units each with 47055 hit points (weak to fire; immune to slashing) with an attack that does 116 fire damage at initiative 14
2654 units each with 13093 hit points (weak to radiation) with an attack that does 8 radiation damage at initiative 19
5513 units each with 18026 hit points (immune to radiation; weak to slashing) with an attack that does 6 slashing damage at initiative 20
89 units each with 48412 hit points (weak to cold) with an attack that does 815 radiation damage at initiative 17
2995 units each with 51205 hit points (weak to cold) with an attack that does 28 slashing damage at initiative 7

Also, merry christmas fuckers

Jesus christ is this happening again? The last time I did AoC prior to this year was in 2016 when I took one look at day 11 and couldn't be bothered to untangle that shit, this looks even worse.

gonna hand-convert this input to my code because fuck parsing this

someone doesn't seem to like a peaceful christmas.

>It's another implement Dwarf Fortress problem

Attached: disgust.jpg (800x999, 92K)

FUCKING JEWS

Oh I overreacted, it's not that bad. I had a very similar problem solved in Google Sheets once for a Pathfinder game.