• Ever wanted an RSS feed of all your favorite gaming news sites? Go check out our new Gaming Headlines feed! Read more about it here.

RiOrius

Member
Oct 27, 2017
6,073
No way we'll have to write intcode ourselves. We might be done with it, but my money is on one more problem involving multiple IntCode computers running simultaneously. Like Day 7, except that could be done most easily by suspending one computer when it outputs and starting up the second. I'm thinking we'll get a problem where that won't work, you need to run each computer in lockstep. Possibly with different timings for different lengths of instructions.
 

Randdalf

Member
Oct 28, 2017
4,167
Day 10 done: https://github.com/Randdalf/aoc19/blob/master/d10.py

Definitely the trickiest one so far!

My thought process was that if you map the points onto a circle, then the ones blocking each other will have the same angle. I used atan2 to calculate the angle of each asteroid from the station, then rounded the numbers to deal with floating point error. I put the angles into a set and counted the length of the set to get the number of visible asteroids (aka number of unique angles). I have a feeling there's an integer-only way to solve this one with rationals and lowest common multiples, but using angles was helpful for part 2.

Part 2 I initially got wrong because I always forget that up is (0, -1) and not (0, 1) in advent of code puzzles. I bucketed the asteroids by angle, and sorted the buckets by angle. Inside each bucket I sorted the asteroids by reverse distance from the station. After finding the index of the first bucket which is >= the angle of up, I looped through the list of buckets, popping asteroids from non-empty buckets until I had popped 200.
 
Last edited:

Lafazar

Member
Oct 25, 2017
1,579
Bern, Switzerland
This would have been so much easier by using atan2. But I'm trying to solve these without using any libraries. Let's see how long I can hold this up.

I just sorted them clockwise around the center by calculating the ratio of the coordinate differences (and some additional criteria) and then looped through them while avoiding using the same angle twice. To avoid floating point error, I reduced the fractions by their gcd before calculating the ratio. This way asteroids on the same angle should have a numerically identical floating point ratio.

Hidden content
You need to reply to this thread in order to see this content.
 
OP
OP
ElFly

ElFly

Member
Oct 27, 2017
2,734
used numpy and still got the cross product wrong? eventually got it right but it was v embarrassing

then in part 2 I used a hash map that had floats as keys

this is fine
 

Qronicle

Member
Oct 27, 2017
718
Belgium
Just read the instructions, don't have the time to do the implementation today, are we however sure "advanced" math is necessary?
For example if there is an asteroid on relative x: 5, y: 7, then you only have to check whether there are asteroids with their relative coordinates being dividable by 5 and 7 for x and y respectively. Idk
 

malus

Member
Oct 30, 2017
2,947
Just read the instructions, don't have the time to do the implementation today, are we however sure "advanced" math is necessary?
For example if there is an asteroid on relative x: 5, y: 7, then you only have to check whether there are asteroids with their relative coordinates being dividable by 5 and 7 for x and y respectively. Idk
That's what I did for part 1. Part 2 however is a bit more involved than that but could probably still be solved without "advanced" math.
You just need a function that maps the two values correctly to a space that let's you sort them. I guess you could just check which quadrant they are in and then do some simple ratios or something but I ended up saying fuck it and used atan2 instead.

Edit: lol, basically what Lafazar did.
 
Last edited:

iapetus

Member
Oct 26, 2017
3,078
Have just done day ten part one the easy way. Trying to come up with an easy way to do part 2 as well, and failing. Guessing that sorting the asteroids by angle and distance is the sane way to do it, though I'd still like something clever...

Edit: That said, does the angle matter? Surely you can just go by the X:Y ratio?
 
Last edited:

Zevenberge

Member
Oct 27, 2017
570
You might not need all of the assignment. A bunch of my coworkers didn't realize the second part could be reduced to
a filtering of all astroids that are visible (which is part 1) ordered by angle, then take the 200th astroid, as long as the answer to part one is over 200. Technically, the angle is just a representation of the x:y ratio.
 

iapetus

Member
Oct 26, 2017
3,078
Stupid bug in sorting by distance and a brain fart with Y-axis orientation caused me some problems on this one, but no need to do any trigonometry at all.
 

Min

Member
Oct 25, 2017
4,068
Okay so I'm behind and a novice... I finished day 1 pretty easily. Day 2 however has me stumped and the example problems also don't make sense to me:

1,0,0,0,99 becomes 2,0,0,0,99 (1 + 1 = 2).
I don't know how this is the case because
1,0,0,0 --> (0+0 = 0 ) --> 0,0,0,0,99

I'm coding in java. After importing the input file into a single dimension array, I did a for loop incrementing every 4

opcode is the array with the data

opcode[1]=12
opcode[2]=2

for(int i=0;i<opcode.length;i++){
if(i%4==0){
if(i==1)
opcode[opcode[i+3]] = opcode[i+1]+opcode[i+2];
else if(i==2)
opcode[opcode[i+3]] = opcode[i+1]*opcode[i+2];
else
break;
}
}

Should I be using arrayLists?

EDIT: NVM I MISREAD 🤦 They're all coordinate positions.
 
Last edited:

Lafazar

Member
Oct 25, 2017
1,579
Bern, Switzerland
I knew it would pay off to spend the time to clean up my Intcode interpreter. This one went quite well. I just hope we won't have to do multithreading at one point (*shivers*).

I didn't want to spend the time to dynamically expand my panels array once the robot reached the edge, so I just increased the size if the program crashed due to index out of bounds and reran. Not the most elegant solution, but it worked.

Hidden content
You need to reply to this thread in order to see this content.
 
Last edited:

Randdalf

Member
Oct 28, 2017
4,167
I knew it would pay off to spend the time to clean up my Intcode interpreter. This one went quite well. I just hope we won't have to do multithreading at one point (*shivers*).

I didn't want to spend the time to dynamically expand my panels array once the robot reached the edge, so I just increased the size if the program crashed due to index out of bounds and reran. Not the most elegant solution, but it worked.

[Hidden content]

Python has a really handy defaultdict collection which I use quite a lot in the "unbounded" AoC puzzles.

Day 11: https://github.com/Randdalf/aoc19/blob/master/d11.py

I messed up the second part when I remembered, but then forgot I remembered, that python's range generator does not include the upper bound. So that wasted five minutes.
 

iapetus

Member
Oct 26, 2017
3,078
I knew it would pay off to spend the time to clean up my Intcode interpreter. This one went quite well. I just hope we won't have to do multithreading at one point (*shivers*).

My solution to the amplifier problem part 2 used multiple threads, just waiting on input. Wasn't painful at all. If a threading task comes up, though, I'll probably switch to executing one instruction at a time and swapping control between VMs each instruction.
 

malus

Member
Oct 30, 2017
2,947
I could see them making a problem using multiple intcode instances using a shared memory or something.
 
OP
OP
ElFly

ElFly

Member
Oct 27, 2017
2,734
day 11 looks cool, but I don't really have the time today

may incur in some advent debt. will give it a try tonight but I may fall asleep
 

Zevenberge

Member
Oct 27, 2017
570
So today was in Clojure. I was struggling a lot trying to get a Java process spawned that booted my Intcode interpreter of day 9. I'm kind of split on Clojure though. Once it works, it's really elegant. It's just...

> Clojure: Your program is broken.
> Me: What's wrong?
> Clojure: Yes.

Error messages including the trace logs are not helpful at all. I could have solved the puzzle in two hours less if the output was just a little helpful.
Code:
(let [x 0] (
    (print x)
    (println "")
))
(println "It's dead Jim")
The last line is not printed. Eventually I figured that I needed to add a do to the first line.
 

Qronicle

Member
Oct 27, 2017
718
Belgium
Today was pretty fun. I like that instead of giving us the instructions for the robot, they had to come from the intcode application. I also made a string-to-image converter, so I don't have to decipher my console output anymore :D

Had an 'interesting' memory-leak issue though. In my IntCode computer, I throw a custom Exception when the code requests input that is not available. For this day, I then got the intcode output in the exception handler, moved my robot, and called Robot::run again, all in the exception handler. Because I made it recursive like this, the exceptions were never garbage collected, resulting in me being out of memory very soon in part 1. (Instead of rewriting IntCode and make separate application states, I just deleted the exception object in it's handler, maybe I'll rewrite that one day...)
 
OP
OP
ElFly

ElFly

Member
Oct 27, 2017
2,734
gave it a try during a slow morning at the office and the goddamn thing loops a lot and then tries to read the program from the index -1

I am profoundly fucked
 

iapetus

Member
Oct 26, 2017
3,078
Yeah, nice fun one today. Pretty simple, though I hit some confusion when I forgot that you can't use an array as a key to a map in Java. :D
 

iapetus

Member
Oct 26, 2017
3,078
gave it a try during a slow morning at the office and the goddamn thing loops a lot and then tries to read the program from the index -1

I am profoundly fucked

Which version of your IntCode interpreter did you use? I figure it needs to be the one from the end of day 9, which should have been fairly thoroughly tested (including by day 9 part 1)... Had to modify my code for handling input/output programmatically to support long values, but that didn't take long. :)
 

Lafazar

Member
Oct 25, 2017
1,579
Bern, Switzerland
Python has a really handy defaultdict collection which I use quite a lot in the "unbounded" AoC puzzles.
Neat, thanks a lot. I'm definitly going to use that in the future. For this Advent of Code I'm trying to use no additional libraries, though (which is admittedly not much of a challenge since vanilla Python is already so damn powerful).

My solution to the amplifier problem part 2 used multiple threads, just waiting on input. Wasn't painful at all. If a threading task comes up, though, I'll probably switch to executing one instruction at a time and swapping control between VMs each instruction.

That's pretty cool. I just hope multi-threading is not going to be required.
 

Randdalf

Member
Oct 28, 2017
4,167
I don't think it's even possible to write a puzzle which requires multithreading, I wouldn't worry on that front.

Now a superscalar intcode computer, that would be fun.
 
OP
OP
ElFly

ElFly

Member
Oct 27, 2017
2,734
Which version of your IntCode interpreter did you use? I figure it needs to be the one from the end of day 9, which should have fairly thoroughly tested (including by day 9 part 1)... Had to modify my code for handling input/output programmatically to support long values, but that didn't take long. :)
it is indeed day s 9 but i fear a few things:

-i dunno if i handle input blocking correctly. i know i do output suspending correctly

-dunno if my reads handle all cases of running out of space

may need more testing, dunno. on my way to a restaurant now so cannot work

will skip this day prolly
 

iapetus

Member
Oct 26, 2017
3,078
I don't think it's even possible to write a puzzle which requires multithreading, I wouldn't worry on that front.

Sure it is. Multiple interpreters with shared memory, or add a fork operator, and specify that all interpreters operate at the same number of operations per second and have a specified priority.
 

Randdalf

Member
Oct 28, 2017
4,167
There are still cases of UB there.

Part B actually has me stumped today.

Yeah me too, need to think about it some more.

Edit: I've had an idea but won't be able to test it until later:
look for cycle lengths in the moons individually, then find the lowest common multiple of all the individual cycles
 
Last edited:

malus

Member
Oct 30, 2017
2,947
I see we're skipping the three body problem in favor of going directly for the four body problem.
 

iapetus

Member
Oct 26, 2017
3,078
In each step you compare each body to each other body, and along each dimension it accelerates 1 unit towards the other body.

So let's say I have a body A at <0, 0, 0>, and the others are at B <1, 2, 3>, C <-1, 4, 8> and D <7, 3, -2>. It's the first tick, so all velocities are 0.

Comparing x-coordinates:

A's x is less than B's (0 < 1), so we add one to its x velocity. A's x is greater than C's (0 > -1) so we subtract one from its x velocity. A's x is less than D's (0 < 7) so we add another one to its x velocity. Which leaves us with an x velocity for A of 0 + 1 - 1 + 1, or 1.
 

Qronicle

Member
Oct 27, 2017
718
Belgium
I decided to let part 2 just run, but after 10 minutes it's becoming clear I should probably really try something else :D
I'm probably gonna make a visual representation of the positions in the first 10 steps and see if I can find anything resembling a pattern ¯\_(ツ)_/¯

I don't get it, how is velocity determined in each step?

For one moon, you loop through all other moons and then just add to the current velocity of that moon as described
moon.vel.x += moon.pos.x < otherMoon.pos.x ? 1 : (moon.pos.x > otherMoon.pos.x ? -1 : 0)

Edit: Couldn't help myself and looked at the idea of Randdalf - that could very well be the solution indeed
 
Last edited:

iapetus

Member
Oct 26, 2017
3,078
I decided to let part 2 just run, but after 10 minutes it's becoming clear I should probably really try something else :D
I'm probably gonna make a visual representation of the positions in the first 10 steps and see if I can find anything resembling a pattern ¯\_(ツ)_/¯

Yeah, it's pretty clear that just letting it run won't work. I can see optimisations to the simulation, but they're useless - they won't bring things down enough.

Might start by focussing on a single value - I suspect they all run in some sort of cycle, and the intersection point of all cycles is where they reach the initial state again.
 
Last edited:
OP
OP
ElFly

ElFly

Member
Oct 27, 2017
2,734
oh so the velocity is the position diff from the previous tick... and then it's added again in the next tick?

edit: oh I get it now. didn't have a good sleep last night
 

Qronicle

Member
Oct 27, 2017
718
Belgium
Since iapetus is on the same track, no more spoiler tags: I've written out the code that first searches for the amount of steps for one moon to make a full cycle, but that doesn't seem to work either. The example that goes to 2772 had two moons needing 924 steps, and two moons needing 2772 steps. (Lowest common multiple between those two is 2772)
But should the results of the real input follow the same kind of result, this method would take about 3 times longer -_-
Anyway, I'll keep it running for a few minutes, I should see at least see some output when it found the first moon's cycle.
 
Last edited:

iapetus

Member
Oct 26, 2017
3,078
Qronicle: I just spoilered out my thoughts, because they worked. :D You might want to do likewise.

Lesser spoilers:
If history repeats once, it will repeat again.

Slight spoilers:
Looking for patterns in smaller sets of data is easier than looking for patterns in the whole universe.

Big spoilers - from here on in they basically tell you how to do it, so don't look if you don't want that:
Tracking each coordinate independently you hit the cycles pretty quickly. Then it's just a case of calculating the LCM, which there are simple enough methods for. :) Since there's no interaction between movement on different axes, it's fine to treat these as entirely independent.

Even bigger spoilers:
So here's my approach:

First I capture the initial x, y and z coordinates of all 4 bodies. Then I run the simulation (for an unbounded number of ticks).

Each tick I check whether all bodies have reached their original x position with x velocities of 0. If they have, that's the length of the x cycle.
I do likewise for y and z. Once I have cycle lengths for all three, the loop terminates.

Once that's done, I find the LCM of the x, y and z cycles and Bob's your uncle.
 
Last edited:

iapetus

Member
Oct 26, 2017
3,078
The example that goes to 2772
had two moons needing 924 steps, and two moons needing 2772 steps. (Lowest common multiple between those two is 2772)

You can't track cycles in individual moons. Firstly they'll likely take the full duration as you discovered, and secondly they won't necessarily repeat - if a moon hits its initial state but the other moons are in different states, then the cycle won't repeat.
 

Qronicle

Member
Oct 27, 2017
718
Belgium
Qronicle: I just spoilered out my thoughts, because they worked. :D You might want to do likewise.

I thought that was what I'm doing (in 4 loops instead of 1, but shouldn't make a big difference), but apparently I'm failing hard then. Weird because it works for the example.
I hope I'll have an Aha-moment in the coming minutes xD

Edit: And there it is. I would have never ever found that by myself, though.
 

iapetus

Member
Oct 26, 2017
3,078
I thought that was what I'm doing (in 4 loops instead of 1, but shouldn't make a big difference), but apparently I'm failing hard then. Weird because it works for the example.
I hope I'll have an Aha-moment in the coming minutes xD

If you're doing it in 4 loops, you're doing it wrong (not just because of inefficiency - there's no reason not to track all the things together - but because you're looking at the wrong subset of the data).
 

Qronicle

Member
Oct 27, 2017
718
Belgium
Yeah, I need to give up for now as well. Thought I had it (again, the 2772 example works), but I really need to get on with my real job :)

PHP:
$moons = [
    new SpaceObject(-1, 0, 2),
    new SpaceObject(2, -10, -7),
    new SpaceObject(4, -8, 8),
    new SpaceObject(3, 5, -1),
];

$simulation = new SpaceSimulation();
$startPoints = [];
$moonAxis = []; // All axis of all moons we'll need to find the steps for
foreach ($moons as $m => $moon) {
    $simulation->addSpaceObject($moon);
    $startPoints[] = clone $moon->position;
    $moonAxis[] = ['x', 'y', 'z'];
}
$steps = [];
$step = 0;
while (++$step) {
    $simulation->step();
    $stop = true;
    foreach ($moonAxis as $m => $axis) {
        foreach ($axis as $a => $axel) { // That's probably non-English
            $stop = false;
            if ($startPoints[$m]->$axel == $moons[$m]->position->$axel && $moons[$m]->velocity->$axel == 0) {
                $steps[] = $step;
                unset($moonAxis[$m][$a]);
            }
        }
    }
    if ($stop) {
        break;
    }
}

echo 'Steps: ' . lowestCommonMultiple($steps);
 

iapetus

Member
Oct 26, 2017
3,078
Yeah, I need to give up for now as well. Thought I had it (again, the 2772 example works), but I really need to get on with my real job :)

If it helps, my results for the tests:

x hits original state at tick 18
y hits original state at tick 28
z hits original state at tick 44

x hits original state at tick 2028
z hits original state at tick 4702
y hits original state at tick 5898
 

Qronicle

Member
Oct 27, 2017
718
Belgium
If it helps, my results for the tests
After seeing you only have three values, I read your biggest spoiler again, and it finally clicked.

I was saving the steps for each of the moons when they got back to their original position, not when they all got back to the same position (for that axis). This also makes sense in my brain now, finally.
I had 12 points to look for the lowest common multiple (example 2): 21,57,60,232,857,1824,2028,2028,2670,4702,5898,5898 (which gives a *very* large number.)

Thanks for feeding it to me, will implement the corrections later. At least I wrote the function to calculate the LCM myself :')
 

RiOrius

Member
Oct 27, 2017
6,073
Yeah, that was a tricky one. A lot so far had been kind of paint-by-numbers, "here's a thing, write code to do it," including 12A, but part B really made you think.