[ / / / / / / / / / / / / / ] [ dir / agatha2 / animu / eris / hdi8 / sonyeon / vg / vietnam / voros ]

/tech/ - Technology

Winner of the 62rd Attention-Hungry Games
/eris/ - Wherein Is Explained Absolutely Everything Worth Knowing About Absolutely Anything.

November 2018 - 8chan Transparency Report
Email
Comment *
File
Password (Randomized for file and post deletion; you may also set your own.)
* = required field[▶ Show post options & limits]
Confused? See the FAQ.
Flag
Oekaki
Show oekaki applet
(replaces files and can be used instead)
Options

Allowed file types:jpg, jpeg, gif, png, webm, mp4, pdf
Max filesize is 16 MB.
Max image dimensions are 15000 x 15000.
You may upload 3 per post.


File: f6e07a659f8ef6d⋯.png (105.37 KB, 1079x777, 1079:777, advent.png)

 No.1001333

https://adventofcode.com/

It's near to that time of year again, people, and the reddit competition will soon start up again. Are you going to let those twitter trannies win? Or are you going to prove your compsci degree was worth something?

(protip: it wasn't, watch as some jap codes the whole thing in assembly naked atop mt. Fuji)

What is it?

Advent of code's a programming advent calendar. 2 problems a day for every day of advent, you paste the output data into a text box. You need to register via one of a few 3rd-party websites, because there's a leaderboard: first person to complete a day's challenges get 100 points to his total, second 99, so on. If I remember correctly, someone from 4chan came first last year, but don't quote me on that.

The site's a bit cancerous, especially the sign-up thing, but it's still pretty fun. Try out a new language, or have some fun getting back to basics with one you already know.

I'll be doing it in C, with a little helper library for quickly reading files. How about you, anon?

 No.1007129

>>1006982

I didn't know if some /g/ nigger just posted it here, or if it went the other way around.

>I'm randomly deleting a couple of users

Heh. Truly random, or just users that are inactive?

verax needs to be kicked for making us look bad... but it's his board. Hopefully he'll resurrect himself.


 No.1007132

File: 9499acb13168bc5⋯.gif (357.17 KB, 420x360, 7:6, pol faggot.gif)

>>1007100


 No.1007134

>>1007132

Shut it down.


 No.1007135

>>1007129

Anyone can make a leaderboard but with 10 people do we really need to think about starting another?


 No.1007138


 No.1007179

File: 560310b92fd9eaf⋯.png (111.35 KB, 1196x764, 299:191, idiot.png)

File: 415bfae1303ab51⋯.png (170.38 KB, 1194x602, 597:301, whatafag.png)

File: c0fc06dac00e967⋯.png (179.77 KB, 1196x848, 299:212, muhstress.png)

Roundup of reddit faggotry.


 No.1007181

>>1007179

I don't get it, how does one manage to print them upside down?


 No.1007185

>>1007132

I was waiting for this guy.


 No.1007187

>>1007179

>it's supposed to be fun

lol


 No.1007194

>>1007187

Well are you doing it for pajeet points?


 No.1007197

>>1007181

You would if you assumed the coordinates were cartesian


 No.1007198

>>1007181

Well it depends if you say positive coordinates grow up or down.


 No.1007204

>>1007198

Related: I have always visualized my matrices as an array of rows, but for this one specifically I wrote it as an array of columns because I always thought everyone else thought of it that way, turns out that made my input sideways and it was supposed to be an array of rows from the start.


 No.1007227

>>1007181

The shock isn't that it is rendered upside down, rather that he couldn't figure that out himself.


 No.1007228

I may genuinely be retarded. Spent hours trying out different ways of looking for the fucking letters in the output, counting lines, total neighboring dots. Then I read the hint about all of them converging. And then the least squares method posted above. Also 20 minutes gone because I forgot how retarded copy is in Python.


 No.1007229

>>1007204

Arrays of rows is the usual convention, and that also how matrices are expressed in mathematics. I think OpenGL might use the inverted order though, it's been a while since I've looked at it though.


 No.1007232

>>1007228

>I may genuinely be retarded.

That's a more general solution, as we mentioned above, if there were any sort of noise in the image, it would have made the all the converging bounding box solutions fail. The rule with AoC problems is that they all lend themselves to simple clean solutions, something a fast programer could complete in 5 minutes.


 No.1007250

>>1007110

Could just go for one of those "pooled" burner accounts. Not posting the one I use, just search for them.

>>1007179

>Picture 1

Ha ha ha, how funny!

I got X and Y mixed up at first, and got the result of picture 1 rotated 90° AND mirrored, so the characters weren't even readable no matter how you tilted your head.


 No.1007252

>>1007232

there could've been tons of noise and it wouldn't've broken the Ada solution of looking for high rates of touching locations.

the noise would've just made it even slower


 No.1007254

In C because I was bored


#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>

#define NLINES 328

typedef struct {
int x, y, vx, vy;
} point;

int minx(const point *ps, size_t sz) {
int mx = INT_MAX;
for (size_t i = 1; i < sz; ++i)
if (mx > ps[i].x)
mx = ps[i].x;
return mx;
}

int maxx(const point *ps, size_t sz) {
int mX = INT_MIN;
for (size_t i = 1; i < sz; ++i)
if (mX < ps[i].x)
mX = ps[i].x;
return mX;
}

int miny(const point *ps, size_t sz) {
int my = INT_MAX;
for (size_t i = 1; i < sz; ++i)
if (my > ps[i].y)
my = ps[i].y;
return my;
}

int maxy(const point *ps, size_t sz) {
int mY = INT_MIN;
for (size_t i = 1; i < sz; ++i)
if (mY < ps[i].y)
mY = ps[i].y;
return mY;
}

void tick(point *ps, size_t sz, int mul)
{
for (size_t i = 0; i < sz; ++i) {
ps[i].x += ps[i].vx * mul;
ps[i].y += ps[i].vy * mul;
}
}

unsigned reduce(point *ps, size_t sz)
{
int time = 0;
int msqr = INT_MAX;

while (1) {
int mx = minx(ps, sz);
int mX = maxx(ps, sz);
int my = miny(ps, sz);
int mY = maxy(ps, sz);

int w = abs(mX - mx);
int h = abs(mY - my);

if (w+h > msqr)
break;

msqr = w+h;
tick(ps, sz, 1);
time++;
}
tick(ps, sz, -1);

return msqr;
}

void draw(const point *ps, size_t sz)
{
char **grid;

int mx = minx(ps, sz);
int mX = maxx(ps, sz);
int my = miny(ps, sz);
int mY = maxy(ps, sz);

int w = abs(mX - mx) + 1;
int h = abs(mY - my) + 1;

grid = calloc(h, sizeof(char*));
for (int i = 0; i < h; ++i) {
grid[i] = calloc(w, sizeof(char));
memset(grid[i], ' ', w);
}

for (int i = 0; i < sz; ++i) {
grid[ps[i].y-my][ps[i].x-mx] = '#';
}

for (int y = 0; y < h; ++y) {
for (int x = 0; x < w; ++x) {
putchar(grid[y][x]);
}
putchar('\n');
}
}

int main(void)
{
unsigned time;
size_t sz = NLINES;
point ps[sz];

size_t i = 0;
while (scanf("%*[^0-9-]%d%*[^0-9-]%d%*[^0-9-]%d%*[^0-9-]%d>\n",
&ps[i].x, &ps[i].y, &ps[i].vx, &ps[i].vy) == 4) ++i;

time = reduce(ps, sz);

puts("part 1:");
draw(ps, sz);
printf("part 2: %d", time);

return 0;
}

>all these max functions

Is there a better way?, how would a true C nigger do it?


 No.1007258

>>1007254

Oh wait I didn't even need to use malloc (which I also didn't free), I could've just

char grid[h][w];


 No.1007271

>Is there a better way?, how would a true C nigger do it?

Use a switch case? Or use a int[4] instead of a struct? Both sound like nigger retard ways of doing it.

Also, exactly how long did it take for this program to execute for you? It's still running for me.


 No.1007272

>>1007271

You need to define NLINES at the top to the number of lines in your input.


 No.1007274

>>1007272

Well you could also change the draw(ps, sz) and reduce(ps, sz) calls in main to draw(ps, i) and reduce(ps, i). But you should still increase NLINES to at least 500 or more to make sure it's bigger than your input lines.


 No.1007289

>>1007272

>You need to define NLINES at the top to the number of lines in your input.

<yfw beyond brainlet

Why do I do this to myself?

It's getting my part 2 wrong, though. It gives the very low value of 70.

Also, my python solution runs twice as fast. It relies on shifting time by 10^X, where X == int(log10(h))-1. It would be easy to implement this into the C solution as well.


 No.1007294

>>1007289

>very low value of 70

Your IQ

Put it out of your mind for now though, the next one is about to begin. I've got a feeling it'll be a travelling salesman or postman tour problem. He's been pretty light with the graph theory so far.


 No.1007295

>>1007289

>>>You need to define NLINES at the top to the number of lines in your input.

See >>1007274

>It's getting my part 2 wrong, though. It gives the very low value of 70.

You're right, it's getting my part 2 wrong as well, I didn't notice as I pretty much rushed it, it's because reduce() is supposed to return time-1 but it's returning something else.

>Also, my python solution runs twice as fast. It relies on shifting time by 10^X, where X == int(log10(h))-1. It would be easy to implement this into the C solution as well.

I wanted to use your solution but I didn't because I'm a brainlet and couldn't figure out what you were doing (like I don't even know what starmap is), thanks for putting it into mathematical terms I guess, maybe I'll try it after day11.


 No.1007298

>>1007295

>couldn't figure out what you were doing

I'm not that guy. I don't know shit about statistics; regression analysis makes as much sense to me as it does to you. My solution is much more simple, I might post it later.


 No.1007299

File: 3b0457ebbb216f9⋯.jpg (93.86 KB, 655x650, 131:130, nomore.jpg)

One of us has to beat the facebook tranny!

>pic unrelated


 No.1007301

What a horrible problem. This doesn't even look fun.


 No.1007302

>>1007301

Patience anon.


 No.1007303

WHERE"S THE GRID?


 No.1007304

Finally a brainlet-friendly puzzle.


 No.1007311

>Answer is wrong

fuc


 No.1007312

>>1007304

Part 2 is slightly less brainlet friendly


 No.1007314

>Actually got on the leaderboard with C++


 No.1007315

>>1007311

pay attention to the question


 No.1007316

>You got rank 256 on this star's leaderboard.

secret first place.

lesser power of 2s suck anyway.


 No.1007317

>spend several minutes testing the input

>yfw you realise you're OFF BY ONE

AHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH


 No.1007318

why are people so slow at getting the second? I just brute-forced it. slow languages?


 No.1007320

>>1007318

Yeah think so, seems to be my issue.


 No.1007321

File: ee6508360141476⋯.png (400.74 KB, 1408x2618, 64:119, day11-ada.png)

Ada for day 11, ultra slow at 52s. Which is why the "trying size" output's there.


 No.1007324

>>1007321

bug in that: it doesn't count the size=300 case, and the fix isn't as simple as removing the -1 from the loop over sizes.

probably easier to get the size=300 case as you're assigning the power levels anyway.


 No.1007325

>>1007318

You didn't even use memoization? Impressive if it brute forced without it.


 No.1007326

>>1007325

not unless you consider building the grid memoization, vs. recalculating each cell's power each time.

that part of the program takes about 1ms.

I don't see anything special about the math so far...

P'= y(x + 10)
P''= (P' + Z)(x + 10)
= xP' + Zx + 10P' + 10Z
= yx(x + 10) + Zx + 10y(x + 10) + 10Z
= yx^2 + 10xy + Zx + 10yx + 100y + 10Z
= yx^2 + 20yx + Zx + 100y + 10Z
= (yx^2 + 20yx + 100y) + (Zx + 10Z)
P = (P''/100)%10 - 5
except that your serial number is only involved in X-coordinate calculation; the rest you could perform at compile-time.

maybe there's more if you go further and calculate all of the P' ' values needed to satisfy a grid.


 No.1007327

>>1007326

I'll look at what you did after I complete this. Don't know what's wrong with me today, cannot really focus.

Brainlet status: confirmed


 No.1007329

Well shit part 2 takes longer than a minute, is there some secret optimization technique or is that just how it is?, I'm currently calculating the result again because I forgot to print the 3rd parameter.


 No.1007330

Also here is my C++ bruteforce.


#include <iostream>
#include <string>
#include <vector>
#include <limits>

int serial = 5177;

struct point {
int x, y, d;
};

int d3(int n) {
if (n / 100 > 1) {
return std::to_string(n/100).back() - '0';
} else {
return 0;
}
}

int main()
{
std::vector<std::vector<int>> grid(300, std::vector<int>(300));

for (size_t y = 0; y < 300; ++y) {
for (size_t x = 0; x < 300; ++x) {
int rackid = (x+11);
int power = rackid * (y+1);
power += serial;
power *= rackid;
power = d3(power);
power -= 5;
grid[y][x] = power;
}
}

std::pair<point, int> max(point(), std::numeric_limits<int>::min());
for (int d = 1; d < 301; ++d) {
for (int y = 0; y < 300-d+1; ++y) {
for (int x = 0; x < 300-d+1; ++x) {
int power = 0;
for (int dy = 0; dy < d; ++dy) {
for (int dx = 0; dx < d; ++dx) {
power += grid[y+dy][x+dx];
}
}
if (power > max.second) {
max.first.x = x+1;
max.first.y = y+1;
max.first.d = d;
max.second = power;
}
}
}
}

std::cout << max.first.x << ',' << max.first.y << ',' << max.first.d << '\n';
return 0;
}


 No.1007331

>yfw your power grid was initialized to index as [y][x] instead of [x][y] because [[0 for _ in range(300)] for _ in range(300)] initializes shit backwards

It feels cucked to be a pythonfag. Especially when I'm having to fuck around with optimizing the searches when someone got 8th globally by brute force C code.

I fucking give up today. I don't know why shit's broke.


 No.1007332

>>1007329

> secret optimization technique

Still computing mine. The only trick I've used (which I hope works) is to reuse the partial sums (growing each square a row/column at a time)


 No.1007334

>>1007329

Mine processed in about 4min using brute force C++ but to be fair I am doing this from a Chromebook.

>>1007332

That's pretty smart anon


 No.1007335

>>1007334

>That's pretty smart anon

It didn't seem to help. Trying other stuff too. Why wasn't I just born in Africa? My mind is clearly better suited for it.


 No.1007336

>>1007335

I know that feel anon. I had a few ideas as well but I don't have time to test them.


 No.1007337

>>1007336

My only other idea is to store regions, and use them when an enclosing region is being run... but if people are brute forcing this, it can't be that difficult.


 No.1007338

>>1007337

Just do it normally and have some patience, it takes a while, make sure you're compiling with optimizations (and may god have pity on you if you're using an interpreted language).

Also you could print the dimensions of the square every time it changes to measure how long it's taking, it shouldn't slow your program down much since it only happens 300 times.


 No.1007340

>>1007318

Well for one I stopped my program a few times because I thought "It can't take THAT long", at some point I just let it running in the background and forgot about it to realized it was finished after checking this thread.


 No.1007341

>heh I did pretty good, guess I'll go to bed early

>wait, this should parallize pretty well

<deadlock

<deadlock

<deadlock

<deadlock

...

are there gods of programming?

is this punishment for my hubris?


 No.1007343

>>1007338

Finally got it in Mathematica using the partial sums technique. Whereas Mathematica was fantastic yesterday, it was brutal today. I'll optimize it later. Took forever to return the answer.


 No.1007344

File: 504b6fdc2603ccd⋯.webm (10.03 MB, 107x80, 107:80, terry_manifesto.webm)

>>1007337

If it's any help: I had the program print out the coordinates of its box every single time it found a new maximum power level, and after a certain point (pretty early on) it never found a new one.

I think it a visualization of the distribution of power levels would be helpful.

>>1007341

You of all people should know there is one God, and one King.


 No.1007352

Nothing I do works. Everything I copy works. I want to die.


 No.1007353

>>1007352

Using partial sums resulted in >10x speedup for me, try that.


 No.1007356

>>1007353

>Using partial sums resulted in >10x speedup for me, try that.

You don't get it. That IS what I was trying. That was the method I was trying from the beginning, because I was the pythonfag from >>1007331 and I knew damn well before I had even wrote the first line for part 2 that mass calculation of the area every time wasn't going to cut it.

After fumbling with test inputs for an hour, I realised that my X and Y were inverted. Okay, just swap the assignment of the power levels initially. The test input grid looked okay, so I tried with the full deal. Wrong answer. Eventually, I come to the realization that my entire partial sum method was broken. Okay, let's just dump the shit and brute force, right? WRONG! My entire area_power_sum function was faulty as well, even for counting squares of 3x3, and I came to understand that the only reason my answer was correct for Part 1 was sheer dumb luck in my choice. I concluded that python was a fucked language for this from the start, and hopped over to C to do a brute force partial sum. Cue another hour of fucking troubleshooting until I realize that I've fucked myself in the ass with uints. And even after that, my code STILL didn't FUCKING work.

I gave up. I shreded my C file and copied C bruteforce code from /g/. Immediately worked.

I belong on reddit. Fuck me.


 No.1007358

>>1007356

>copied

Shameful nigger/poo/chink behavior. Today was certainly brutal to the interpreted languages.


 No.1007359

File: a19cebf78446b49⋯.png (338.04 KB, 737x652, 737:652, day11.png)


 No.1007360

>>1007356

Talking of /g/, was there any good salt?


 No.1007361

>>1007359

That looks clean, but it timed out when I tried to run it. How long did it take locally?


 No.1007362

>>1007361

over 60 seconds


 No.1007363

>>1007356

They gave you many examples anon; should have taken advantage of that and tested against all of them before going ahead with something so processing-intensive.


 No.1007364

File: 72eb1b2efb980ea⋯.png (600.87 KB, 1312x4284, 328:1071, day11-ada-caveman-threadin….png)

>>1007341

<deadlock

<deadlock

<deadlock

>sit down to read about tasking

>tasking for babies, page 1, example 1: here's an example of just starting some tasks and letting them do their thing with no coordination at all

>hug it let's go with that

Ada, 20s with four threads, but you have to pick the right answer yourself.


 No.1007365


 No.1007366

File: 4504ee2b969d28b⋯.webm (3.59 MB, 640x360, 16:9, SkyKing.webm)

My goal is to get a sub 10sec mathematica solution, and if that goes good, I'm just going to nose down and call it a night.


 No.1007367

Poothon code for both parts, PyPy solves it in ~11-11.5 seconds. There's got to be better ways to store data for Part 2 than a 2D array with a dictionary inside, right?

#!/usr/bin/python

# Function for calculating single power levels
def power_singular(x, y, serial):
rack_id = x + 1 + 10
power_level = rack_id * (y + 1)
power_level += serial
power_level *= rack_id
power_level = power_level // 100 % 10
power_level -= 5
return power_level

# Part 1 power calculation
def get_power(x, y, serial, grid):
power_size = 3
power_total = 0
# Iterate through a 3x3 grid and just sum to power_total
for i in range(0, power_size):
for j in range(0, power_size):
new_x = x + i
new_y = y + j
if not grid[new_x][new_y] is None:
power_total += grid[new_x][new_y]
continue
# Power level calculation
power_level = power_singular(new_x, new_y, serial)
# Insert into main grid
grid[new_x][new_y] = power_level
# Sum up
power_total += power_level
return power_total

def part1(serial, grid, grid_size):
top_coord = None
top_power = None

# Iterate using 3x3 blocks
for i in range(0, grid_size - 3):
for j in range(0, grid_size - 3):
new_power = get_power(i, j, serial, grid)
if (top_power is None) or \
(new_power > top_power):
top_power = new_power
top_coord = [i, j]

# Poo hack because of (0,0) start
print('Part 1: {0},{1}'.format(
top_coord[0] + 1,
top_coord[1] + 1))

def part2(serial, grid_size):
top_size = None
top_coord = None
top_power = None
# 2D array with a dictionary entry
# Holds data for every X by X block's power level
memo = [[{} for x in range(0, 300)] for y in range(0, 300)]
_min = min
for i in range(0, grid_size):
for j in range(0, grid_size):
current_sum = 0
# Maximum available block
max_diag = _min(grid_size - i, grid_size - j)
for diag in range(0, max_diag):
for arg in range(0, diag + 1):
# Walk in a mirrored L formation around previous block
alt = _min(diag, arg)
current_sum += power_singular(i + diag, j + alt, serial)
# Check for when X=Y
if diag != arg:
current_sum += power_singular(i + alt, j + diag, serial)
# Add current block's sum to dictionary
memo[i][j][diag] = current_sum

# Iterate over the dictionary again, find max power level
for i in range(0, grid_size):
for j in range(0, grid_size):
current_dic = memo[i][j]
for k, v in current_dic.items():
if (top_power is None) or \
(v > top_power):
top_power = v
top_size = k
top_coord = [i, j]
# More poo hacks
print('Part 2: {0},{1},{2}'.format(
top_coord[0] + 1, top_coord[1] + 1,
top_size + 1))

def main():
grid_size = 300
serial = 7989
grid = [[None for x in range(0, grid_size)] for y in range(0, grid_size)]
part1(serial, grid, grid_size)
part2(serial, grid_size)

main()

Fiddling with edge cases and stupid bugs once again. Spent 10 minutes scratching my head because I forgot how copy works and initialized the array as [ [None] * X ] * X and kept wondering why my value are getting overwritten.


 No.1007368

hmm.

with my code that checks sizes thru 1 .. 75, then 76 .. 150 in separate threads and reports the max power, it seems to be very reliable that the max power is negative for the wrong ranges.

$ for x in $(seq 1 4000|shuf); do ./day11 $x; echo; echo; done
max power at: 2, 64 of size 226 with power: -26723
max power at: 231, 225 of size 14 with power: 101
max power at: 39, 100 of size 151 with power: -11137
max power at: 74, 96 of size 76 with power: -2458


max power at: 65, 55 of size 226 with power: -24371
max power at: 230, 284 of size 14 with power: 123
max power at: 140, 147 of size 151 with power: -9930
max power at: 222, 224 of size 76 with power: -2182


max power at: 74, 63 of size 226 with power: -24285
max power at: 233, 87 of size 13 with power: 97
max power at: 140, 64 of size 151 with power: -10415
max power at: 85, 120 of size 76 with power: -2196


max power at: 14, 74 of size 226 with power: -26350
max power at: 236, 50 of size 12 with power: 105
max power at: 36, 4 of size 151 with power: -11117
max power at: 224, 8 of size 76 with power: -2199
and that works with my real input as well as the meme input.

So there might be something to exploit there. Too many negative values? skip.


 No.1007369

I'm confused about part 2. Is there really no fast way, besides partial sums? Even with partial sums you still need to scan along the bottom/right edges so it seems like an O(n^3) algo.

If I'm not mistaken there's there's n^2 sums to evaluate and every sum requires adding at least 2n numbers. So we need 2n^3 numbers for each size. That adds up to 2 billion operations. On Python simply doing 1+1 that many times is already fairly slow. Granted Python is not known for speed but this algorithm took 263 secs to finish on Ryzen, yet the about page claims:

>every problem has a solution that completes in at most 15 seconds on ten-year-old hardware.

So what is the fast solution here?


 No.1007370

>>1007367

As I posted this, I realized that I don't even need the 2D array. Just checking for top power level where the current sum is being appended to memo is enough. I blame day 10 for fucking with my brain so much. Still no difference in execution time, sadly.


 No.1007371

>>1007368

>Too many negative values? skip

Sounds like a decent idea. The actual power values are actually pretty low, so I think at some point you can tell certain sums are beyond hope of reaching the maximum and drop them. Not sure if maintaining that list would be less work than the problem itself though.

Another idea I had was to start with areas with high density of large values.


 No.1007372

>>1007371

Amazing idea, actually. Checking for hopeless diagonals in a single place cut down my execution in >>1007367 from 11 seconds to 2.7


 No.1007392

On reddit someone mentioned https://en.wikipedia.org/wiki/Summed-area_table

And of course it's built into mathematica


 No.1007408

>>1007369

I'm at work, running jruby via powershell because that's all I can get working on this blocked off machine, as web-based IDE's like tutorialpoint's don't allow me long running executions.

Anyway, I noticed a clear trend in my output that after a square size of 9x9 the max total sum steadily dropped. Then I skipped a bit further and the higher the square, the lower the total. Optimisation isn't even necessary, the answer is probably in the beginning (or end, depending on your direction)


 No.1007450

>>1007392

Well shit now I feel bad, this runs in an instant.


#include <iostream>
#include <vector>
#include <limits>

int serial = 5177;

int main()
{
std::vector<std::vector<int>> grid {301, std::vector<int>(301)};
std::vector<std::vector<int>> sat {301, std::vector<int>(301, 0)};

for (size_t y = 1; y <= 300; ++y) {
for (size_t x = 1; x <= 300; ++x) {
int rackid = (x+10);
int power = (((((rackid * y) + serial) * rackid)/100)%10)-5;
grid[y][x] = power;
}
}

// make summed-area table
for (size_t y = 1; y <= 300; ++y) {
for (size_t x = 1; x <= 300; ++x) {
sat[y][x] = grid[y][x] + sat[y-1][x] + sat[y][x-1] - sat[y-1][x-1];
}
}

int mx, my, md, mp;

mp = std::numeric_limits<int>::min();
for (int d = 2; d <= 300; ++d) {
for (int y = d; y <= 300; ++y) {
for (int x = d; x <= 300; ++x) {
int p = sat[y][x] - sat[y-d][x] - sat[y][x-d] + sat[y-d][x-d];

if (p > mp) {
mx = x-d+1;
my = y-d+1;
md = d;
mp = p;
}
}
}
}

std::cout << mx << ',' << my << ',' << md << '\n';
return 0;
}


 No.1007458

>>1007450

>The summed-area table can be computed efficiently in a single pass over the image

why don't you do it efficiently ?


 No.1007466

>>1007458

What are you talking about?, that's a single pass.


 No.1007467

>>1007466

for (size_t y = 1; y <= 300; ++y) {
for (size_t x = 1; x <= 300; ++x) {
int rackid = (x+10);
int power = (((((rackid * y) + serial) * rackid)/100)%10)-5;
sat[y][x] = power + sat[y-1][x] + sat[y][x-1] - sat[y-1][x-1];
}
}


 No.1007468

>>1007467

Not him, but I doubt that'll make much of a difference.


 No.1007470

>>1007467

Right, we don't need the grid anymore, could've said that from the start.


 No.1007472

>>1007392

That... really helped.

#!/usr/bin/env ruby
start = Time.now
ID = 1788
$sumgrid = Array.new(300){Array.new(300){0}}

def calcPowerLevel(x,y)
power_lvl = (y*(x+10)+ID)*(x+10)
power_lvl.to_s[-3].to_i - 5
end

def calcSum(x,y,r)
sum = $sumgrid[x+r][y+r]
sum -= $sumgrid[x-1][y+r] if x>0
sum -= $sumgrid[x+r][y-1] if y>0
sum += $sumgrid[x-1][y-1] if y>0 && x>0
sum
end

300.times {|x| 300.times {|y| $sumgrid[x][y] = calcPowerLevel(x,y)-calcSum(x,y,0)}}

max = [-100000, -1, -1, 0]
300.times do |r|
stepmax = [-100000, -1, -1, r+1]
(300-r).times do |x|
(300-r).times do |y|
sum = calcSum(x,y,r)
stepmax = [sum, x, y, r+1] if sum > stepmax[0]
end
end
puts "Step: -squaresize: #{r+1} -maxpower: #{stepmax[0]} (#{stepmax[1]},#{stepmax[2]})"
max = stepmax if stepmax[0] > max[0]
end

puts "------------------------------------------------------------"
puts "Best: -squaresize: #{max[3]}, -maxpower: #{max[0]} (#{max[1]}, #{max[2]}, #{max[3]})"
puts "-- Run time: #{Time.now - start} seconds --"


 No.1007475

File: 59df514b4a9804d⋯.jpg (424.1 KB, 1243x1143, 1243:1143, 1524767730253.jpg)

>>1007470

You can always keep it for a small speedup for just the 1x1 square size run.


 No.1007506

File: 3dcb7af101826b0⋯.png (124.11 KB, 888x936, 37:39, day11.png)

Finally had time to actually try the summed area table method, and I am pleased. Good problem, very frustrating to find the correct approach, but satisfying to see it in the end.


 No.1007581

Summed areas are definitely the way to go. I went from 263 sec to 8 sec. This was a pain in the ass to implement and debug, especially because the problem uses special snowflake coordinates instead of starting at 0,0.

Funnily enough, though, it took me about 2 hours total to implement the summed areas, and even if I was familiar with the algo it would have been at least 30 min to do it properly. In terms of getting a high score, I was better off waiting 4 mins for the suboptimal solution to finish. What's the lesson here, that elegant algorithms aren't worth it?

Anyway, here's my shit Python code.


from datetime import datetime


class FuelCellGrid():
w = 3000

def __init__(self, grid_serial_number):
self._grid = {}

for x in range(1, self.w+1):
for y in range(1, self.w+1):
rack_id = x + 10
times_y = rack_id * y
plus_serial = times_y + grid_serial_number
times_rack_id = plus_serial * rack_id
hundreds_digit = (times_rack_id // 100) % 10
p = hundreds_digit - 5

self._grid[x, y] = p

self._totals = {}
self._summed_area_table = {}

def _calculate_summed_areas(self):
# Scan right and down to fill in summed areas
for x in range(1, self.w + 1):
for y in range(1, self.w + 1):
# Coordinates of neighboring areas
pa = (x-1, y-1)
pb = (x, y-1)
pc = (x-1, y)
pd = (x, y)

# Neighboring area values
a = self._summed_area_table.get(pa, 0)
b = self._summed_area_table.get(pb, 0)
c = self._summed_area_table.get(pc, 0)

# Based on https://en.wikipedia.org/wiki/Summed-area_table
corner = self._grid[pd]
d = corner + b + c - a

self._summed_area_table[pd] = d

def _calculate_totals(self, size):
for x in range(1, self.w-size+2):
for y in range(1, self.w-size+2):
# Algorithm: https://en.wikipedia.org/wiki/Summed-area_table

# horizontal and vertical line passing through a, b, c, d
x_ab = x - 1
y_ac = y - 1
x_cd = x + size - 1
y_bd = y + size - 1

# coordinated of a, b, c, d
pa = (x_ab, y_ac)
pb = (x_ab, y_bd)
pc = (x_cd, y_ac)
pd = (x_cd, y_bd)

# actual areas
a = self._summed_area_table.get(pa, 0)
b = self._summed_area_table.get(pb, 0)
c = self._summed_area_table.get(pc, 0)
d = self._summed_area_table.get(pd, 0)

# Algorithm: https://en.wikipedia.org/wiki/Summed-area_table
self._totals[x, y, size] = d - b - c + a

def all_totals(self):
t_0 = datetime.now()
t_1 = t_0

self._calculate_summed_areas()

for s in range(1, self.w+1):
self._calculate_totals(s)

t = datetime.now()
delta_t = (t - t_1).total_seconds()
if delta_t > 1:
delta_t_overall = (t - t_0).total_seconds()
print('{:.0%} done and {:.0f} sec elapsed.'.format(s/self.w, delta_t_overall))
t_1 = t

def get_best(self):
highest_total = -1
best_coords = None

for k, v in self._totals.items():
if v > highest_total:
highest_total = v
best_coords = k

return best_coords, highest_total


# The actual problem
print('Creating grid.')
g = FuelCellGrid(8141)

print('Calculating totals.')
g.all_totals()

print('Getting maximum.')
c, s = g.get_best()

print('{}: {}'.format(c, s))


 No.1007585

>>1007581

So this is how a pajeet would do it


 No.1007591

>>1007581

>What's the lesson here, that elegant algorithms aren't worth it?

That one-and-done solutions don't necessarily require elegant algorithms. If you had to run this every day, it would get annoying really fast. Also, if this wasn't AoC but an actual programming competition, I assume the real input size would be so large that a suboptimal solution would take centuries to produce a result.

>w = 3000

Does it have something to do with the algorithm that I missed speedreading or is there an extra zero?


 No.1007592

>>1007581

> elegant algorithms

Finding the most elegant algorithm is the most enjoyable part of these puzzles. I learn more in trying to optimize my solution than I do from hacking together something quickly to solve the challenge.


 No.1007639

Today is the day that a /tech/nician gains global #1!


 No.1007640

>yfw you've only gotten less-than-4-digit ranks for 3 of the past 11 days

>yfw you're the dumbest person in /tech/

Ready as ever for today's LARPfest.


 No.1007641

>>1007640

Hey I might be one of the slowests but I'm proud that there is fast people /tech/, also it's not really LARPing if you're not pretending to be good.


 No.1007642

Automata!


 No.1007644

>still trying to figure out how I'm supposed to know which pots are negative


 No.1007645

oh nevermind, they start at -3, this should be easy enough


 No.1007646

wait no, 0 is at the front, the rest I just have to derive from that.


 No.1007652

>answer is wrong for part 1

>assume that the value summing is wrong

<manually count and find out it's correct

What do you even do, in a situation like this?


 No.1007655

>FIFTY BILLION

FUCK

Python can't even COUNT to fifty billion in a reasonable amount of time. HolyC can only count to 4 million in one second. What the fuck's the pattern?


 No.1007656

>>1007655

Oh, nevermind, the pattern shows rather quick.


 No.1007658

>>1006581

Day 7, still in C++

#include <type_traits>

struct step_node { vector<uint8_t> to; uint8_t n_from = 0; };

auto prepare_steps(string_view input)
{
array<step_node, 26> graph;
for (size_t i = 0, sz = input.size(); i < sz; i += 49){
uint8_t from = input[i + 5] - 'A', to = input[i + 36] - 'A';
graph[from].to.push_back(to);
++graph[to].n_from;
}
priority_queue<uint8_t, vector<uint8_t>, greater<uint8_t>> work;
for (uint8_t i = 0; i < graph.size(); ++i)
if (graph[i].n_from == 0)
work.push(i);
return pair(move(graph), move(work));
}

void day7a(string_view input)
{
auto [graph, work] = prepare_steps(input);
string res; res.reserve(26);
do {
uint8_t node = work.top(); work.pop();
res.push_back('A' + node);
for (uint8_t next : graph[node].to)
if (--graph[next].n_from == 0)
work.push(next);
} while (!work.empty());
cout << res;
}

struct step_worker { uint8_t node, time = 0; };

void day7b(string_view input)
{
auto [graph, work] = prepare_steps(input);
array<step_worker, 5> workers;
size_t time_taken = 0;
const auto schedule_next = [&](auto tag, step_worker curw){
time_taken += curw.time;
for (auto& w : workers)
if constexpr (is_same_v<decay_t<decltype(tag)>, int>){
if (w.time != 0)
w.time -= curw.time;
} else w.time -= curw.time;
for (uint8_t next : graph[curw.node].to)
if (--graph[next].n_from == 0)
work.push(next);
};
for (;;){
uint8_t node = work.top(); work.pop();
if (auto it = find_if(workers.begin(), workers.end(), [](auto w){ return w.time == 0; }); it != workers.end()){
it->node = node;
it->time = 61 + node;
} else {
auto& nextw = *min_element(workers.begin(), workers.end(), [](auto a, auto b){ return a.time < b.time; });
schedule_next(.0, nextw);
nextw.node = node;
nextw.time = 61 + node;
}
while (work.empty()){
auto& nextw = *min_element(workers.begin(), workers.end(), [](auto a, auto b){ return --a.time < --b.time; });
if (nextw.time == 0)
goto end;
schedule_next(0, nextw);
}
} end:;
cout << time_taken;
}


 No.1007664

>>1007655

Holy shit, thank fuck it converges to something simple.


 No.1007665

>>1007658

Day 8. Seeing the benefit of my helper functions here.

template<typename Iter> void day8a_rec(Iter& source, int& result)
{
int n_children = to_int(next(source)), n_metadata = to_int(next(source));
while (n_children --> 0)
day8a_rec(source, result);
while (n_metadata --> 0)
result += to_int(next(source));
}

void day8a(string_view input)
{
auto source = split(input, ::isspace).begin();
int result = 0;
day8a_rec(source, result);
cout << result;
}

template<typename Iter> int day8b_rec(Iter& source)
{
int n_children = to_int(next(source)), n_metadata = to_int(next(source));
if (n_children == 0){
int value = 0;
while (n_metadata --> 0)
value += to_int(next(source));
return value;
}
vector<int> children_values; children_values.reserve(n_children);
for (int i = n_children; i --> 0;)
children_values.push_back(day8b_rec(source));
int value = 0;
while (n_metadata --> 0){
int index = to_int(next(source));
if (index > 0 && index <= n_children)
value += children_values[index - 1];
}
return value;
}

void day8b(string_view input)
{
auto source = split(input, ::isspace).begin();
cout << day8b_rec(source);
}


 No.1007667

>>1007666

It's ok Satan you can do it.


 No.1007669

Well, here's the C++.


#include <iostream>
#include <fstream>
#include <bitset>
#include <vector>

constexpr uint16_t rule_size = 5u;
//this value may need to be adjusted if plants start falling off the edge of the bitset
constexpr uint16_t num_pots = 700u;
//this value may need to be adjusted if no linear pattern emerges within 500 generations
constexpr uint32_t gens_to_use = 500u;

struct rule {
//search pattern
std::bitset<rule_size> pattern;
//whether to output # or . in the center if match
bool output = false;
};

//apply rules to a bitset for a new plant generation
std::bitset<num_pots> transform(
std::bitset<num_pots> const& b,
std::vector<rule> const& v) {
std::bitset<num_pots> new_set;
for (auto const& r : v) {
uint16_t ctr = 0u;
for (; ctr <= (num_pots - rule_size); ++ctr) { //scan position
bool bb = true;
for (uint16_t ctr2 = 0u; ctr2 < rule_size; ++ctr2) { //scan rule set (starting from left end)
bb &= (r.pattern[ctr2] == b[ctr + ctr2]);
}
if (bb) {
new_set[ctr + 2] = r.output; //modify center if fit
}
}
}
return new_set;
}

//sum up the pot values
int32_t sumBitset(std::bitset<num_pots> const& bs) {
int32_t ctri = -rule_size;
int32_t sum = 0;
for (; ctri < static_cast<int32_t>(num_pots); ++ctri) {
sum += (ctri * bs[ctri + rule_size]);
}
return sum;
}

//print out the bitset as formatted in the challenge, if desired
template <typename T>
void printBitset(T bs) {
for (uint8_t b = 0; b < bs.size(); ++b) {
std::cout << (bs[b] ? '#' : '.');
}
std::cout << '\n';
}

int main(int argc, char* argv[]) {
if (argc == 1) {
return 1;
}
std::fstream fs(argv[1]);
std::bitset<num_pots> set;
std::vector<rule> rules;
if (!fs) {
return 1;
}

//PARSE INPUT
std::string buffer;
std::getline(fs, buffer, ':');
std::getline(fs, buffer, ' ');
std::getline(fs, buffer, '\n');
uint8_t ctr = 0u;
for (char c : buffer) {
set[ctr + rule_size] = (c == '#');
++ctr;
}
std::getline(fs, buffer, '\n');
while (true) {
rule r;
std::getline(fs, buffer, ' ');
uint8_t ctr2 = 0u;
for (char c : buffer) {
r.pattern[ctr2] = (c == '#');
++ctr2;
}
if (fs.eof()) {
break;
}
std::getline(fs, buffer, '>');
std::getline(fs, buffer, ' ');
std::getline(fs, buffer, '\n');
r.output = (buffer[0] == '#');
rules.push_back(r);
}
//END PARSE

ctr = 0u;
uint32_t ctr2 = 0u;
int32_t last_diff = -1;
int32_t diff = 0;
int32_t last_val = 0;
int32_t stop_idx = 0;
for (; ctr2 < gens_to_use; ++ctr2) {
last_diff = diff;
set = transform(set, rules);

int32_t score = sumBitset(set);
diff = score - last_val;
last_val = score;
if (ctr2 == 19) {
std::cout << "Part 1: " << score << '\n';
}
if (diff == last_diff) {
//this is a pretty touchy heuristic; idk if it works for all datasets
std::cout << "diffs are constant: " << diff << '\n';
stop_idx = ctr2;
break;
}
}

int64_t part2 = last_val + ((5e10 - stop_idx - 1) * 23);
std::cout << "Part 2: " << part2 << '\n';

return 0;
}


 No.1007673

my code sucks, so I'll just show how I did the rules:

procedure Day12 is
type Rule_Part is (Far_Left, Left, Current, Right, Far_Right, Result);
subtype Rule_Input_Part is Rule_Part range Far_Left .. Far_Right;
type Rule is array (Rule_Part) of Character;
type Pattern is array (Rule_Input_Part) of Character;
type Rules_Type is array (Positive range <>) of Rule;
type Pot_State is record
Center : Positive;
Pot_String : Unbounded_String;
end record;

Input : constant Rules_Type (1 .. N) :=
("#.....", "#.##.#", "..#...", "#.#.#.", ".#.###", "...###", "##...#",
...

function Apply (Pat : in Pattern; Rules : in Rules_Type) return Character is
begin
for R of Rules loop
if Pat = Pattern (R (Far_Left .. Far_Right)) then
return R (Result);
end if;
end loop;
return '.';
end Apply;


 No.1007678

File: 0e665d78e292497⋯.png (10.77 KB, 1000x587, 1000:587, ca.png)

Since Wolfram wrote a very big book on CelluarAutomata, it's no surprising that this was all built into mathematica. I had to spend some time to learn how that worked. Then it was a matter of feeding their rules directly into the CellularAutomaton[...].


 No.1007679

>>1007678

>a very big book

that's a rather disrespectful way to reference

A NEW KIND OF SCIENCE


 No.1007680

>>1007679

Apologies 100% my good sir, I forget how well read this subsection of /tech/ is.


 No.1007692

>>1007665

Day 9.

no arrays allowed

t. computational complexity

struct marble_t
{
marble_t* insert(size_t i)
{
marble_t* m = new marble_t{prev, this, i};
prev->next = m;
prev = m;
return m;
}
marble_t* erase()
{
marble_t* mnext = next;
prev->next = mnext;
next->prev = prev;
delete this;
return mnext;
}
static marble_t* create(size_t val)
{
marble_t* m = new marble_t{};
m->prev = m->next = m;
m->val = val;
return m;
}
static void destroy(marble_t* m)
{
marble_t* mnext = m->next;
delete m;
for (marble_t* cur = mnext; cur != m; m = m->next)
delete cur;
}
marble_t* prev, * next;
size_t val;
};

void day9(size_t n_players, size_t last_marble)
{
vector<size_t> scores(n_players, 0);
marble_t* cur = marble_t::create(0);
for (size_t i = 1; i <= last_marble; ++i)
if (i % 23 != 0){
for (uint8_t i = 0; i < 2; ++i) cur = cur->next;
cur = cur->insert(i);
} else {
for (uint8_t i = 0; i < 7; ++i) cur = cur->prev;
scores[(i - 1) % n_players] += i + cur->val;
cur = cur->erase();
}
marble_t::destroy(cur);
cout << *max_element(scores.begin(), scores.end());
}


 No.1007696

File: b101c09449de4cd⋯.png (184.5 KB, 992x1282, 496:641, day12.png)

>>1007691


 No.1007700

I find it amazing that someone managed to complete both parts in 9 minutes.


 No.1007704

>>1007585

deleet this

>>1007591

Should be w=300, I was playing around and forgot to change back before pasting. Incidentally, what you say is true in principle, but funnily enough in *this* problem there's a very small range of interesting parameters. If w was a bit smaller, the problem would be so trivial that optimization is a waste of time. If it was much bigger (like 3000) even the optimal algorithm cannot solve it with reasonable resources.

>>1007592

I also enjoy that, but with this I get discouraged because I feel like since it's timed and also late at night, you're expected to write quick solutions.

>>1007655

Dead giveaway that it's a pattern tbh. Like you say, you couldn't even keep a counter going for 50G iterations so of course they wouldn't ask it if there wasn't a pattern. What's more the pattern must be analytically soluble, because even if you knew the pattern you still couldn't numerically evaluate it through every iteration. In this case the relation is just y=mx+n

>>1007700

The problem is literally just search&replace, so I can see how they would. The bigger obstacles for me were to figure out how to trim extra dots while keeping track of pot numbers, and figuring out a way to debug it. But if you're used to this sort of code, and your language makes dealing with the indexing easy, it's pretty doable.


 No.1007707

>>1007704

>trim extra dots while keeping track of pot numbers

Right, but it's these minor details which force you to have to read the instructions carefully and can easily slow you down. I suppose the top ranked guys practise in coding competitions quite frequently so they can outline a general solution after a very quick skim. Perhaps they even have pre-written general routines, and then they just fill in the rest. Impressive nonetheless. Of course the real reason is these guys do it so fast is that the beta testers leak, or have their GMAIL read by the competing Googlers, 100%


 No.1007724

File: 3838fd96c16d94f⋯.png (547.98 KB, 680x1155, 136:231, day12.png)

https://play.rust-lang.org/?gist=575b6cd752c3c8b6172303c8daad3dc7

Today was reddit as fuck

>cellular automata XD

>DAE game of life???????????????????????? XDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD

fucking cancer


 No.1007732

>>1007641

All of my days are 4-digits there's even a 5-digit one, so you're never the slowest.

>>1007652

A brainlet wave hit me again and I thought you're supposed to count all the flowers between generations, looked at the thread and got spoiled by reading >>1007655 , really mad at myself now.

Day 12, Python wall edition:

#!/usr/bin/python

class Plants():
def __init__(self, name):
self.name = name
self.field = set()
self.rules = {}
self._read_data()
self._solve()

def _solve(self):
initial = self.field
self._part1()
# Reset data
self.field = initial
self._part2()

def _part1(self):
for i in range(0, 20):
self._generation_iter()
print('Part 1: {0}'.format(
sum(self.field)))

def _part2(self):
_sum = sum
# Comparison data
control = _sum(self.field)
diff = 0
times = 0
# 50 repeats should be enough?
should_repeat = 50
# Generation for answer completion
generation = 0
while times < should_repeat:
self._generation_iter()
new_control = _sum(self.field)
new_diff = new_control - control
if (new_control - control) == diff:
times += 1
else:
times = 0
# Iterate
diff = new_diff
control = new_control
generation += 1

print('Part 2: {0}'.format(
control + (50000000000 - generation) * diff))

def _check_rules(self, query):
if query in self.rules:
key = self.rules[query]
if key == '#':
return True
# Everything else returns False
return False

def _generation_iter(self):
surviving = []
for i in range(min(self.field), max(self.field) + 1):
look_behind = ''
look_ahead = ''
for j in range(0, 5):
if (i - j) in self.field:
look_behind += '#'
else:
look_behind += '.'
if (i + j) in self.field:
look_ahead += '#'
else:
look_ahead += '.'
# Reverse behind string for proper lookup
look_behind = look_behind[::-1]
# Check both for new pots
if self._check_rules(look_behind):
surviving.append(i - 2)
if self._check_rules(look_ahead):
surviving.append(i + 2)
# Replace old plant pots with new
self.field = set(surviving)

def _read_data(self):
with open(self.name, 'r') as f:
for line in f:
tokens = line.replace('\n', '').split(' ')
if len(tokens) < 2:
continue
# Rules into rule dictionary
if tokens[1] == '=>':
self.rules[ tokens[0] ] = tokens[2]
else: # Only pot positions go into field dictionary
for i in range(0, len(tokens[2])):
if tokens[2][i] == '#':
self.field.add(i)

Plants("input")


 No.1007735

>>1007707

>spoiler

That'd be real funny if true, considering a ni/g/ger beat every last one of them last year.

>>1007732

>spoiler

I've got one too, actually, although probably not for the same reasons as you (I started day 1 late).

I'm not really disappointed about being brainlet, the disappointment stems from the fact that I'm only sometimes a brainlet. The fact that I've gotten global points before just drills in the shame all the more when I'm struggling through a Part 1 and people on /tech/ are posting, "An easy one today."

Today's was easy, though. the 50Bil was really a giveway that the solution was simplistic.


 No.1007780

File: 72f8334c4431cc0⋯.png (123.75 KB, 1764x362, 882:181, threedays.png)

>>1007735

>>1007732

You'll never reach levels of brainlet greater than this idiot though.

>rather unoptimized


 No.1007795

>>1007780

<rather unoptimized

>look at my own code for the day

>optimization #1: use a data structure with fast insertion and removal

>--- the end ---

>code is more than 200 thousand times faster

I always knew I was a genius, but I am starting to feel that I have an obligation to take over the world.


 No.1007796

File: c91965f7dc677a4⋯.png (156.2 KB, 1678x652, 839:326, idiots on parade.png)

>>1007795

It's one thing to make mistakes and ask for help, but for them to brag about their retardation is on a different level.


 No.1007797

These instructions are terrible.

>number starts at 0

>adds in 3 empty pots for some reason

>at the end the first pot is -2

wtf?


 No.1007798

>>1007797

They are pure garbage. It took me longer than I'd like to admit to realize what the number on the top meant. I thought it was showing the shifting positions of 0, but it's actually just top to bottom, 0, 10, 20 ...

>adds in 3 empty pots for some reason

The example is trash. He didn't include the rule that if it wasn't specified, the plant died.


 No.1007804

>>1007798

jesus fuck I spent an hour on the example. lmao fuck this.


 No.1007806

>>1007655

kek, like many of the other challenges so far I just end up doing the second part mostly manually. I like to program because I love creating quick solutions, so when the answer is easily found manually I do the opposite.

486: 25475
487: 25525
488: 25575
489: 25625
490: 25675
491: 25725

...hmmm.. I wonder if I couldn't simply do...

(50000000000-500)*50 + 26175

Done!


 No.1007876

Day 12 just kill me edition.


#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

std::map<std::string, bool> rules;
std::string gen;
unsigned ngen = 0;
bool stable = false;
int mi = 0;

void advgen(int n = 1)
{
for (int j = 0; j < n; ++j) {
std::string newgen;

for (auto i: {4, 3, 2, 1}) {
auto s = std::string(i, '.') + gen.substr(0, 5 - i);
newgen += rules[s] ? '#' : '.';
}
mi += 2;

for (int i = 0; i < gen.length()-4; ++i) {
auto s = gen.substr(i, 5);
newgen += rules[s] ? '#' : '.';
}

for (auto i: {4, 3, 2, 1}) {
auto s = gen.substr(gen.length() - i, i) + std::string(5 - i, '.');
newgen += rules[s] ? '#' : '.';
}

// trim dots
auto f1 = newgen.find_first_of('#');
auto f2 = newgen.find_last_not_of('.');
newgen = newgen.substr(f1, f2-f1+1);
mi -= f1;

ngen++;
if (gen == newgen) {
stable = true;
break;
}
gen = newgen;
}
}

int genval()
{
int n = 0;
for (int i = 0; i < gen.size(); ++i)
if (gen[i] == '#')
n += i - mi;
return n;
}

void read_input()
{
std::string s1, s2;

std::cin >> s1 >> s1 >> gen;
while (std::cin >> s1 >> s2 >> s2)
rules[s1] = s2 == "#" ? true : false;
}

int main(int argc, char const *argv[])
{
read_input();

while (!stable)
advgen();

int inc = genval();
advgen();
inc = abs(genval() - inc);

signed long long result = (genval() + (inc * (50000000000 - ngen)));
std::cout << result << '\n';

return 0;
}

Today was truly the gayest day.


 No.1007894

>kicked from the first private board

YOU'LL RUE THE DAY, RUSTFAG


 No.1007908

File: 3e4091941d2ec7f⋯.png (150.38 KB, 1570x598, 785:299, triggered.png)

Fix this you nigger 365713.


 No.1007911

>>1007908

I blew five+ hours on that day and have nothing to show for it. I'm convinced that the instructions as provided do not work, and that people only solved it at all because the way you're supposed to solve it introduces additional constraints on the answer. Like a "provide the answer in alphabetical order" question that actually relies on ASCIIbetical ordering.

I want to do the thing the way he wants, and then use that to figure out why exactly my approach didn't work, and that'll take time.

besides it makes the board look like an roguelike @, it's cute.


 No.1007912

>>1007911

>If more than one step is ready, choose the step which is first alphabetically

See the topological sort here. Whenever it's time to grab a new node, take the first after sorting 'S' alphabetically.

https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm


 No.1007913

>>1007912

My approach picked the first available step in an alphabetical loop, each time. Every single iteration started at A and said, are you ready and not already complete or something? no? OK, how about B? If I got anything it right it was doing things alphabetically. That's why I think there are additional constraints that aren't in the instructions but that are naturally come along with that algorithm.

Maybe I'm completely hugging wrong. I won't look again before the weekend.


 No.1007916

>>1007913

Alright. Perhaps the issue is marking things as ready before ALL of their dependencies are met, but that's just a guess from a common mistake.


 No.1007929

alright, finally have my solution for day 12, just in time for day 13. Bit of a slow one today, has a twelve minute runtime. Works well enough though.

#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>

typedef int64_t i64;
typedef uint32_t u32;
typedef uint16_t u16;
typedef uint8_t u8;

#define LEN(a) (sizeof(a) / sizeof(*a))
#define SWAP(a, b) do{ \
typeof(a) c = a; \
a = b; \
b = c; \
}while(0)

char init[] = "#........#.#.#...###..###..###.#..#....###.###.#.#...####..##..##.#####..##...#.#.....#...###.#.####";
char * change[] = { "#..##", ".", "##..#", "#", "..##.", ".",
".##.#", "#", ".....", ".", "..###", "#",
"###.#", "#", "#....", ".", "#.##.", "#",
".#.##", "#", "#...#", ".", "...##", ".",
"###..", "#", ".#..#", ".", "####.", ".",
"....#", ".", "#####", "#", ".###.", ".",
"#..#.", ".", "##...", "#", ".#...", "#",
"#.#.#", ".", "..#..", "#", "...#.", "#",
"##.#.", ".", ".##..", "#", ".#.#.", ".",
"#.#..", ".", "..#.#", "#", "#.###", ".",
"##.##", ".", ".####", "#",};

#define IND(k) ((k)/16)
#define BIT(k) ((k)%16)
#define NUM(k) (IND(k)+(BIT(k)?1:0))

#define SLICE(num, c, d) ((num & ~((~0)<<(d))) >> (c))

#define L 2
#define R 1000
#define C 50000000000

u8 T[32];
u16 GT[1<<(16+4)];

int main(void){
for (int i=0; i<LEN(change)/2; i++){
u8 val = 0;
for(int k=0; k<5; k++)
if(change[i*2][k]=='#')
val |= (1<<k);
T[val] = *change[i*2+1]=='#';
}
for(int i=0; i<LEN(GT); i++)
for(int k=0; k<16; k++)
GT[i] |= T[SLICE(i, k, k+5)]<<k;

u16 * st = malloc(NUM(L+R) * sizeof(u16));
u16 * nx = malloc(NUM(L+R) * sizeof(u16));

int i;
for(i=0; init[i]; i++){
if(!BIT(i+L))
st[IND(i+L)] = 0;
if(init[i] == '#')
st[IND(i+L)] |= (1<<BIT(i+L));
}

i64 l = IND(L),
r = IND((i-1)+L);
i64 shift = 0;

for(i64 i=0; i<C; i++){
i64 s = l-IND(L);
shift += s;
for(i64 k=l-1; k<=r+1; k++)
nx[k-s] = GT[SLICE(*(u32*)((u8*)(st+k)-1), 8-2, 24+2)];
l = nx[l-1] ? l-1 : nx[l] ? l : l+1;
r = nx[r+1] ? r+1 : nx[r] ? r : r-1;
SWAP(st, nx);
}

i64 S = 0;
for(i64 i=l-1; i<=r+1; i++)
for(int k=0; k<16; k++)
if(st[i] & (1<<k))
S += ((i+shift)*16 + k) - L;
printf("%ld\n", S);
}


 No.1007938

>>1007913

>My approach picked the first available step in an alphabetical loop, each time.

Dumb question, but did you restart the loop every time you completed a step?


 No.1007942

>>1007938

Mine did. Complete a step, mark it complete, queue any further steps, go look for more complete steps.


 No.1007943

>tfw won't be able to complete the challenge tomorrow


 No.1007945

>looks at the input

The hell?


 No.1007946

oh boy today looks fun


 No.1007948

>FIRE ALARM IN MY BUILDING GOES OFF RIGHT AS IT STARTS

Fuck. What do I do /tech/?


 No.1007949

>>1007948

you weren't going to finish it anyways


 No.1007951

>>1007949

It was some chucklefuck stuffing shit in a microwave apparently


 No.1007953

>twitter trannies

Show...


 No.1007956

>>1006716

I like how the anon perfecfully cut the video so it shows such thumbnail


 No.1007961

Brainlet here. How do you do part 1 without fucking writing a thousand lines of if else?


 No.1007965

>>1007961

here's my solution. Only a couple lines of if else. The trick was to use dicts instead, when it could be helped.

data = open("13.txt").read().split("\n")
carts = []
rails = []
rots = []
count = 0
for l in data:
carts.append([])
rails.append([])
rots.append([])
for i in l:
if i in "><^v":
count += 1
carts[-1].append(i)
if i in "<>":
rails[-1].append("-")
else:
rails[-1].append("|")
else:
carts[-1].append(" ")
rails[-1].append(i)
rots[-1].append(0)

def find(l):
for i in range(len(data)):
for j in range(len(data[i])):
if l[i][j] != ' ':
print(j, i)
exit(0)

p1 = False

while 1:
new_carts = [[" "] * len(data[0]) for i in range(len(data))]
for i in range(len(data)):
for j in range(len(data[i])):
if carts[i][j] != ' ':
a = { '>': (0, 1), '<': (0, -1), '^': (-1, 0), 'v': (1, 0) }[carts[i][j]]
ni, nj = i+a[0], j+a[1]
if carts[ni][nj] != ' ' or new_carts[ni][nj] != ' ':
if not p1:
print(nj, ni)
p1 = True
count -= 2
carts[i][j] = ' '
carts[ni][nj] = ' '
new_carts[ni][nj] = ' '
continue
r = rails[ni][nj]
if r in "|-":
c = carts[i][j]
elif r == '/':
c = {'>': "^", "<": "v", "v": '<', "^": ">"}[carts[i][j]]
elif r == '\\':
c = {'>': "v", "<": "^", "v": '>', "^": "<"}[carts[i][j]]
elif r == '+':
turn = rots[i][j]
c = {">": "^>v", "<": "v<^", "^": "<^>", "v": ">v<"}[carts[i][j]][turn]
rots[i][j] += 1
rots[i][j] %= 3
else:
exit(12)
carts[i][j] = " "
new_carts[ni][nj] = c
rots[i][j], rots[ni][nj] = 0, rots[i][j]
carts = new_carts
if count == 1:
find(carts)


 No.1007966

>adds a 'moved' boolean to cart_type

enough of moving carts, then getting around to the new coordinate, an then moving the cart again


 No.1007975

>>1007966

>sets 'moved' boolean to false on tick

enough with moving the carts once and then waiting minutes for nothing to ever happen ever again


 No.1007978

File: 4cd90a8e054fb12⋯.png (1.52 MB, 1408x10744, 176:1343, day13-forgive-me-ada.png)

Ada, 1s. This code is awful, just awful. I took a few wrong turns, like going with a hashmap to begin with.

This code is so bad that after I tried to view the screenshot I'd just made of the code, this computer crashed.


 No.1007982

>>1007978

Don't feel bad, I don't think there is non-pajeet code for this.


 No.1007983

>>1007982

nah, the case-nest in step is very regular. You can definitely math it down.


 No.1007984

I wanted easier output of the Maze so I used Character as the type of each char in the maze. With an enumerated type, I could've put a lot of Step's logic into arrays, using '-' '/' etc as indexes, the same way >>1007965 is using dictionaries in Python


 No.1007988

File: 2cb8a6e760c4fbd⋯.png (408.87 KB, 1408x2312, 176:289, day13-ada-nonpajeet.png)


 No.1008004

File: 6f257dabec3e6db⋯.png (613.84 KB, 709x1154, 709:1154, day13.png)


 No.1008019

First time in 13 days that I ended up before the 2000th place. But it was at the cost of writing Pajeet-tier nested If/Else loops.

>>1007780

>Javascript

This is why he should have written it in C, even 50 billion pot generations from day 12 only take twelve minutes: >>1007929


 No.1008026

I've been hacking at today's problem for 5 hours. I don't think I'm going to get a right answer. Frankly, I'm not too disappointed, just tired of everything not working. I think my code's broken because it isn't going by left-to-right up-to-down properly, but I can't be sure.[code]#include <stdio.h>

#include <stdlib.h>

#include <stdint.h>

#include <string.h>

#define LINEMAX 152

#define CHARMAX 1<<15

#define TURNCHR "\\/+"

#define CARTCHR "^<v>"

#define is_change_dir(c) track[c->y][c->x] != (cart->dir > 1<<6 ?'|':'-')

typedef struct Cart {

uint16_t x;

uint16_t y;

char dir;

uint16_t turns;

} Cart;

Cart *cart_ls[17];

char *lines[LINEMAX], track[LINEMAX][LINEMAX];

uint8_t cart_c = 0;

uint16_t tick = 0;

uint16_t readlns(FILE *f, char *lines[], char *buf, _Bool newline) { ... } //stores contents of file *f into *buf, with *lines[] pointing to the start of each line. Returns number of lines read.

char find_track(uint16_t x, uint16_t y) //from the ascii map, get the type of rail that's underneath a cart

{

_Bool up, left, down, right;

up = y && strchr("|" TURNCHR, lines[y-1][x]);

down = y < 150 && strchr("|" TURNCHR, lines[y+1][x]);

left = x && strchr("-" TURNCHR, lines[y][x-1]);

right = x < 150 && strchr("-" TURNCHR, lines[y][x+1]);

if (up && down && left && right)return '+';

if (up && down) return '|';

if (left && right) return '-';

if (left && up || down && right)return '/';

return '\\';

}

void move_cart(Cart *cart) //move the cart a tick

{

switch (cart->dir){ //move the cart

case '^':

cart->y--;

break;

case '<':

cart->x--;

break;

case 'v':

cart->y++;

break;

case '>':

cart->x++;

break;

}

for (uint8_t c = 0; c < cart_c; c++) if (cart_ls[c] != cart && cart_ls[c]->x == cart->x && cart_ls[c]->y == cart->y){ //check all remaining carts for collisions

for (uint8_t n = 0; n < cart_c; n++) printf(cart_ls[n]==cart||n==c?"*%d[%p]: (%d,%d) %c\n":"%d[%p]: (%d,%d) %c\n", n, (void*)cart_ls[n], cart_ls[n]->x, cart_ls[n]->y, cart_ls[n]->dir);

printf("COLLISION AT (%d,%d), TICK %d\n", cart->x, cart->y, tick);

for (uint8_t m = 0, n = 0; m < cart_c; m++) if (m != c && cart_ls[m] != cart) cart_ls[n++] = cart_ls[m];

cart_c -= 2;

break;

}

if (is_change_dir(cart)) if (track[cart->y][cart->x] == '+') switch (cart->turns % 3){ //change the direction of the cart if necessary

case 0: //turnleft

case 2: //turnright

cart->dir = CARTCHR[(strchr(CARTCHR, cart->dir)-CARTCHR+1+(cart->turns%3))%4];

default:cart->turns++;

} else cart->dir = CARTCHR[(strchr(CARTCHR, cart->dir)-CARTCHR+1+(track[cart->y][cart->x] == '/'&&cart->dir>1<<6||track[cart->y][cart->x]=='\\'&&cart->dir<1<<6?2:0))%4]; //The great horror of our time

}

void swp(Cart *carts[], int i, int j){ ... } //swap the carts at index i and j

void r_qsort(Cart *carts[], int left, int right) //quicksort the carts by their y-axis

{

int i, last;

if (left >= right) return; // do nothing if array contains less than 2 elements

swp(carts, left, (left + right)/2); // move partition element

last = left; // to v[0]

for (i = left+1; i <= right; i++) if (carts[i]->y < carts[left]->y) swp(carts, ++last, i); //partition

swp(carts, left, last); // restore partition element

r_qsort(carts, left, last-1);

r_qsort(carts, last+1, right);

}

int main(void){

FILE *in = fopen("input", "r");

char buf[CHARMAX];

uint16_t i = readlns(in, lines, buf, 0);

for (uint16_t k = 0; k < i; track[k++][150] = '\0') for (uint16_t j = 0; j < 150; j++) if (strchr(CARTCHR, lines[k][j])){ //parse input lines (note that strchr indexes '\0's as well, so j < 150 instead of <=.)

track[k][j] = find_track(j,k);

cart_ls[cart_c] = malloc(sizeof(Cart));

cart_ls[cart_c]->dir = lines[k][j];

cart_ls[cart_c]->x = j;

cart_ls[cart_c++]->y = k;

} else track[k][j] = lines[k][j];

for (uint8_t count; cart_c > 1;tick++){ //while there are many uncollided carts

for (uint8_t n = 0; n < cart_c; n++) move_cart(cart_ls[n]); //move the cart forward

r_qsort(cart_ls, 0, cart_c-1); //sort the carts by y-axis //set back the order of the carts properly

do for (uint8_t n = 0; n < cart_c-1; n++) if (cart_ls[n]->y == cart_ls[1+n]->y) if (cart_ls[n]->x > cart_ls[n+1]->x){ //attempt to sort the X-axis

count++;

swp(cart_ls, n, n+1); //sort the x part

}

while (count&&!(count = 0));

}

printf("Last cart standing: (%d, %d) at tick %d\n", cart_ls[0]->x, cart_ls[0]->y, tick);

}[code]


 No.1008027

>>1008026

>failed to close [code] tag

Confirmed brainlet status


 No.1008032

>>1008026

You can always just delete your post, unless you're a torpedo. I can tell you where I've fucked up while trying to make it work. One was checking unupdated cart positions for collisions, meaning a cart would collide with the "shadow" of another cart. Second was a faulty looparound for the intersection check, it was stuck going right over and over. Third was a bad cart position sort - I thought my function sorted by Y, then X, but I found out X wasn't really being accounted for. The challenge calls to start from smaller Y and smaller X.


 No.1008041

File: 25f1910e4a5fb86⋯.png (597.99 KB, 800x600, 4:3, gentoo-ubermensch.png)

>>1007929

Here is my test run of your code. Muh ancient bulldozer did a bit slower than anticipated, the memory usage was a tiny bit smaller with the optimizations but the time difference is yuge.

[no optimization]

4000000000866

real 89m1.141s

user 88m56.205s

sys 0m0.624s

[march=native -O2]

4000000000866

real 21m27.190s

user 21m24.722s

sys 0m0.208s


 No.1008054

>>1008032

>unless you're a torpedo

Yeah. I don't even know where the delete button is.

>One was checking unupdated cart positions for collisions

That problem isn't really possible with my method. Cart positions are updated when they move; I didn't even bother with modifying the rail map; not when you can just keep a list of the positions of the carts. I'm assuming you're the python guy then?

>Second was a faulty looparound for the intersection check

Also unlikely. I had to troubleshoot the turning mechanism a million times, to the point that I spent half an hour pouring over printed info to check for errors.

>Third was a bad cart position sort

I actually already know that the last one is the problem to my program. My quicksort for the carts specifically only sorts by Y, and then attempts to sort the equal Y-coords by X but doesn't really succeed, although I don't know why.

Still, the ordering of the movements doesn't explain why my answer is so far from the right one. My program ends at tick 16k+; the correct one ends at 22k+. Surely there cannot be so many near-misses to the point that the collision times are so far off?


 No.1008077

Here's last night's spaghetti.


#include <iostream>
#include <vector>
#include <algorithm>

#define ISCART(x) (x == '>' || x == '<' || x == '^' || x == 'v')

struct cart {
unsigned x, y;
uint8_t turn = 0;
char rail;
};

std::vector<std::string> track;
std::vector<cart> carts;

void read_input()
{
std::string s;
int y = 0;

while (std::getline(std::cin, s)) {
for (int x = 0; x < s.size(); ++x) {
if (s[x] == '>' || s[x] == '<' || s[x] == '^' || s[x] == 'v') {
cart crt;
crt.x = x;
crt.y = y;
if (s[x] == '>' || s[x] == '<')
crt.rail = '-';
else
crt.rail = '|';
carts.push_back(crt);
}
}
track.push_back(s);
++y;
}
}

char turn(char c, uint8_t r)
{
switch (c) {
case '>': return r == 0 ? '^' : r == 2 ? 'v' : '>';
case '^': return r == 0 ? '<' : r == 2 ? '>' : '^';
case '<': return r == 0 ? 'v' : r == 2 ? '^' : '<';
case 'v': return r == 0 ? '>' : r == 2 ? '<' : 'v';
default: return '?';
}
}
char curve(char r, char c)
{
switch (c) {
case '>': return r == '/' ? '^' : 'v';
case '^': return r == '/' ? '>' : '<';
case '<': return r == '/' ? 'v' : '^';
case 'v': return r == '/' ? '<' : '>';
default: return '?';
}
}
int main(int argc, char const *argv[])
{
read_input();

while (carts.size() > 1) {
std::sort(carts.begin(), carts.end(),
[](const cart &a, const cart &b) {
return a.y == b.y ? a.x < b.x : a.y < b.y;
});
for (auto c = carts.begin(); c < carts.end();) {
int x = c->x, // current cart position (to be modified)
y = c->y;
char cchar = track[c->y][c->x]; // current cart character

// determine next cart position
switch (track[y][x]) {
case '>':
x += 1;
break;
case '<':
x -= 1;
break;
case '^':
y -= 1;
break;
case 'v':
y += 1;
break;
}

// restore track where cart is currently standing on
track[c->y][c->x] = c->rail;

// check if there is a cart on the next rail (CRASH)
if (ISCART(track[y][x])) {
auto c2 = find_if(carts.begin(), carts.end(),
[x,y](const cart &a) {
return a.x == x && a.y == y;
});
track[y][x] = c2->rail;

// I don'r know if there is a better way but all this iterator fuckery is
// the result of the vector shifting when I erase an element
carts.erase(c2);
if (c > c2)
--c;
carts.erase(c);
continue;
}

// set current cart position to next rail position
c->rail = track[y][x];
c->x = x;
c->y = y;

// convert next track to car and do shit or something idk fam
if (track[y][x] == '+') {
track[y][x] = turn(cchar, c->turn);
c->turn = (c->turn+1) % 3;
} else if (track[y][x] == '/' || track[y][x] == '\\') {
track[y][x] = curve(track[y][x], cchar);
} else {
track[y][x] = cchar;
}

++c;
}
}

std::cout << carts[0].x << ',' << carts[0].y << '\n';
return 0;
}


 No.1008110

>>1008054

>Still, the ordering of the movements doesn't explain why my answer is so far from the right one.

Depends on how the carts move. I had two at adjacent coordinates, but with different X parts. Because the one with the larger coordinate moved first, they collided at the intersection. And that answer wasn't even close to the real one. In one of the previous days, I had a two-parter boolean for something similar: (Y1 < Y2 or (X1 == X2 and X1 < X2)).

>I'm assuming you're the python guy then?

There are multiple Pyjeets in this thread. Speaking of which, here's Day 13. Didn't want to post until I got rid of my 40+ If/Else coordinate checks, among other things.

#!/usr/bin/python

def solve():
road, carts = read_data("input")
# For Part 1
first_collision = True
while len(carts) > 1:
# List of keys (coords), sorted first by Y then by X
sorted_keys = sorted(
list(carts.keys()), key=lambda x: (x[1], x[0]))
for key in sorted_keys:
# If it's been removed due to collision
if key not in carts:
continue
# Key data
increment = carts[key][0]
mode = carts[key][1]
# Move current cart
new_coord = ( key[0] + increment[0], key[1] + increment[1] )
carts.pop(key)
# Check for collisions
if new_coord in carts:
# Part 1
if first_collision:
print('First collision at {0}'.format(new_coord))
first_collision = False
# Delete the second cart for Part 2
carts.pop(new_coord)
else:
# Data for road rules
# Flip coordinates because of how it's stored in road array
sign = road[ new_coord[1] ][ new_coord[0] ]
new_increment = road_rules(increment, sign, mode)
# Iterate mode
if sign == '+':
mode = iter_mode(mode)

carts[new_coord] = [new_increment, mode]
# Part 2
if not len(carts) == 0:
print('Last remaining cart at {0}'.format(
list(carts.items())[0][0]))
else:
print('No carts remaining')

def read_data(filename):
f = open(filename, 'r')
# Replacement dictionary
replace = { '<': [(-1, 0), '-'],
'>': [(1, 0), '-'],
'^': [(0, -1), '|'],
'v': [(0, 1), '|']
}
# Slabs store coordinates in a (Y, X) format
road_slabs = []
# Key - tuple, Value - array of [coords tuple, intersection mode]
# For the latter: -1 - left, 0 - straight, 1 - right
carts = {}
# For coords insertion
y = 0
for line in f:
chars = list(line)
for x in range(0, len(chars)):
if chars[x] in replace:
carts[ (x, y) ] = [replace[ chars[x] ][0], -1]
chars[x] = replace[ chars[x] ][1]
road_slabs.append(chars)
y += 1

return road_slabs, carts

# Iter intersection mode (-1 -> 0 -> 1 -> -1 e.t.c.)
def iter_mode(mode):
if mode == 1:
return -1
else:
return mode + 1

def flip_coords(coords):
return [ coords[1], coords[0] ]

# Process road rules
def road_rules(coords, sign, mode):
if sign == '/':
return tuple( i * (-1) for i in flip_coords(coords) )
elif sign == '\\':
return tuple( flip_coords(coords) )
elif sign == '+':
if mode == 0:
return coords
else:
# Y, X now
new_coords = flip_coords(coords)
return ( new_coords[0] * (-mode), new_coords[1] * mode )
else: # Everything else
return coords

solve()


 No.1008144

Did Part1 pretty quickly, but it was pajeet code and was too tried to fix it. Rewrote a nicer version, but it still does not work argh. Do we have to handle three way collisions? The instructions are very unclear.

v

>+

^


 No.1008145

>>1008144

According to the rules given, the top and left cart would collide and then be IMMEDIATELY REMOVED... but the carts are also said to be moving instantaneously, so really, all three should be destroyed.

Perhaps that edge case isn't even occurring.


 No.1008146

>>1008144

>>1008145

Learn to read.

>Carts all move at the same speed; they take turns moving a single step at a time. They do this based on their current location: carts on the top row move first (acting from left to right), then carts on the second row move (again from left to right), then carts on the third row, and so on. Once each cart has moved one step, the process repeats; each of these loops is called a tick.


 No.1008149

>>1008146

That's what I'm doing, bug must be elsewhere.


 No.1008151

>>1008144

Three way collisions are impossible. Carts move one at a time per tick. When a cart moves into another cart, both are removed. The third cart flies through the space unimpaired.


 No.1008152

>>1008151

unimpeded.


 No.1008153

>>1008149

Then you shouldn't have to worry about collisions involving >2 carts.

Try printing it out and compare it with the provided example.


 No.1008156

>>1008153

Finally got it, for some reason I was stuck on the idea that everything moved simultaneously. I had an exception to ignore crashes like > > (no space), because the one on the right would move out the way etc..


 No.1008157

>>1008156

That would've made for a fun part 2.


 No.1008171

>>1008157

And it would have placed me on the correct side of the brainlet filter.


 No.1008172

Another day done. Slow today but at least the end result of watching little carts zoom around was kinda fun.


 No.1008186

>>1008026

>char find_track(uint16_t x, uint16_t y) //from the ascii map, get the type of rail that's underneath a cart

Just store what's under the cart in the cart node itself, remember to also store what's under it when you're reading the file for the first time.

>I think my code's broken because it isn't going by left-to-right up-to-down properly, but I can't be sure.

Doesn't C already have a quicksort?, just use that, to compare the carts compare their Y position, if their Y position is equal compare their X instead.


 No.1008189

>>1008026

Also

>but I can't be sure

You can tho?, just print it to the terminal and see for yourself which one moves first.


 No.1008192

>>1007929

>50000000000

Nigger, you weren't supposed to do that! Just find out where the automata stabilizes see >>1007678.


 No.1008199

>>1008192

That seems like cheating to me. Didn't Turing prove that the automata won't stabilize in the general case? Much more general to sit down and compute the value.

>>1007929

here's day 12 again, this time for 3.5 minutes at -O2. Doing four steps at once speeds it up ~4x, and using u8s instead of u16s slows it down ~2x. But before I was compiling at -O3, so I got a free speedup by not doing that anymore.

#define IND(k) ((k)/8)
#define BIT(k) ((k)%8)
#define NUM(k) (IND(k)+(BIT(k)?1:0))

u8 T[32];
u8 GT[1<<12];
u8 GGT[1<<16];
u8 GGGT[1<<20];
u8 GGGGT[1<<24];

int main(void){
for (int i=0; i<LEN(change)/2; i++){
u8 val = 0;
for(int k=0; k<5; k++)
if(change[i*2][k]=='#')
val |= (1<<k);
T[val] = *change[i*2+1]=='#';
}
for(int i=0; i<LEN(GT); i++)
for(int k=0; k<8; k++) GT[i] |= T[SLICE(i, k, k+5)]<<k;
for(int i=0; i<LEN(GGT); i++){
int v = 0;
for(int k=0; k<12; k++) v |= T[SLICE(i, k, k+5)]<<k;
for(int k=0; k<8; k++) GGT[i] |= T[SLICE(v, k, k+5)]<<k;
}
for(int i=0; i<LEN(GGGT); i++){
int v = 0, w = 0;
for(int k=0; k<16; k++) v |= T[SLICE(i, k, k+5)]<<k;
for(int k=0; k<12; k++) w |= T[SLICE(v, k, k+5)]<<k;
for(int k=0; k<8; k++) GGGT[i] |= T[SLICE(w, k, k+5)]<<k;
}
for(int i=0; i<LEN(GGGGT); i++){
int v = 0, w = 0, x = 0;
for(int k=0; k<20; k++) v |= T[SLICE(i, k, k+5)]<<k;
for(int k=0; k<16; k++) w |= T[SLICE(v, k, k+5)]<<k;
for(int k=0; k<12; k++) x |= T[SLICE(w, k, k+5)]<<k;
for(int k=0; k<8; k++) GGGGT[i] |= T[SLICE(x, k, k+5)]<<k;
}

u8 * st = malloc(NUM(L+R) * sizeof(u8));
u8 * nx = malloc(NUM(L+R) * sizeof(u8));

int i;
for(i=0; init[i]; i++){
if(!BIT(i+L))
st[IND(i+L)] = 0;
if(init[i] == '#')
st[IND(i+L)] |= (1<<BIT(i+L));
}

i64 l = IND(L),
r = IND((i-1)+L),
shift = 0;

for(i64 i=0; i<C/4; i++){
i64 s = l-IND(L);
shift += s;
for(i64 k=l-1; k<=r+1; k++)
nx[k-s] = GGGGT[SLICE(*(u32*)(st+k-1), 0, 24)];
l = nx[l-1] ? l-1 : nx[l] ? l : l+1;
r = nx[r+1] ? r+1 : nx[r] ? r : r-1;
SWAP(st, nx);
}

i64 S = 0;
for(i64 i=l-1; i<=r+1; i++)
for(int k=0; k<8; k++)
if(st[i] & (1<<k))
S += ((i+shift)*8 + k) - L;
printf("%ld\n", S);
}


 No.1008202

>>1008199

It's true you cannot before running the input, but you can detect stabilization when it does occur.

I am very impressed that you got it down to 3.5 minutes though. That's probably quicker than it took most people to figure out the pattern.


 No.1008278

>>1008186

>remember to also store what's under it when you're reading the file for the first time.

That's what find_track() is for, fam. It gets the tracks under the carts at the init map. Then I don't need to store what track's under the carts at all.

>Doesn't C already have a quicksort?

Yeah, I just remembered. Hopeless tbh.

>>1008189

>You can tho?, just print it to the terminal and see for yourself which one moves first.

God forbid I have to spend another hour looking through the print statements of every tick, like I did yesterday. I know I could just print when cart_a.y == cart_b.y, but shit, it's the next day already.

>>1008199

>using u8s instead of u16s slows it down ~2x.

C brainlet here. Why does it slow it down?


 No.1008283

Wait, what? Are we not supposed to use the 3 and 7 from the beginning for part 1?


 No.1008284

WTF is part b? anyone understand it?

>>1008278

>>using u8s instead of u16s slows it down ~2x.

>C brainlet here. Why does it slow it down?

There half as big, so you need to use twice as many of them. Simple math.


 No.1008286

>>1008284

Check at what index the first occurrence of your input number appears in the scoreboard.

Like the test

 3  7  1  0  1  0  1  2  4  5 

"01245" appears after the first 5 numbers. Hence, ans is 5.


 No.1008289

>>1008286

Thanks, I think I got it. Confusing examples though, they should have used 2018 as the input, not the output.


 No.1008290

>>1008286

...although it's starting to seem like bruteforce isn't going to work out well for part 2. Hrmn.


 No.1008291

>>1008290

Who used brute force? Just calculate all the scores, until you find some that match.


 No.1008294

>>1008291

Bruteforcing part 2 right now. And working on a better version, because this is slow lol.


 No.1008295

>>1008291

Uh, isn't that brute force?

Worked for all the test inputs in a few hundred ms. Haven't the answer for part 2 in minutes. I've tested with 6 digit numbers as well.


 No.1008296

>>1008291

Hmm, I can probably just test the last N and last N+1 digits for matches.


 No.1008297

>>1008295

Is this like an off-by-one error or something? No more than two recipes can be appended at once, right? If I check the last 7 characters, it'll always be able to match a 6 character input?


 No.1008298

>>1008295

That's how I did it, and mine finishes in 30 seconds. Maybe your memelang's implementation of lists has some quadratic appends or something.


 No.1008299

>>1008296

>he wasn't doing this already

The fuck? How long did the test input take you?


 No.1008301

>>1008298

n = 147061+10
#n = 5+10
scoreboard = [3, 7]
elf1 = 0
elf2 = 1
recip = '147061'
last = '0'
while recip not in last:
add = str(scoreboard[elf1] + scoreboard[elf2])
scoreboard.append(int(add[0]))
if len(add) > 1: scoreboard.append(int(add[1]))
s_len = len(scoreboard)
elf1 = (elf1 + 1 + scoreboard[elf1])%s_len
elf2 = (elf2 + 1 + scoreboard[elf2])%s_len
last = ''.join(str(d) for d in scoreboard[-7:])
print scoreboard[-10:]
print s_len-6 #+- 1, but doesn't matter

Where's the expensive part? Do python lists take 10000 years to read the end of a list?


 No.1008302

>>1008298

What was your index? I'm using blists now and it's gotten to 2million in a minute.


 No.1008303

>>1008301

Maybe making new strings constantly is expensive?

>>1008302

final answer part b was 20203532


 No.1008304

>Works for all of the examples

>Doesn't work for part 1

wot in tarnation


 No.1008305

>>1008304

make sure to append a zero if thats the sum of the scores.


 No.1008306

>>1008305

Oh FUCK we're supposed to USE 3 and 7 and the input is the number to step through.

Fucking kill me.


 No.1008307

>>1008303

Oh, the more unoptimized (yes, there was a worse one) one that I'd been running for 20 minutes just completed. Neato, an actual easy day for me.

>Maybe making new strings constantly is expensive?

Changed it. Not much of a difference. Maybe 10% faster.


 No.1008308

>part2

ACCEPT

MY

INPUT


 No.1008309

>>1008308

hug I get it, I'm only checking the tail but it can advance 2


 No.1008310

>>1008307

Just ran the code you posted: 57 seconds. The difference turned out to be a slow computer I think.


 No.1008311

>>1008309

>please wait 5 minutes before trying again.

and if it advances 2 and you catch it just before the last one, don't forget the off by one error

god fucking damnit


 No.1008312

>>1008311

>>please wait 5 minutes before trying again.

Is that the backoff strategy? I've only gotten it up to 1 minute.


 No.1008313

>>1008307

Oh wait never mind wew. blists are actually slower for this, my "unoptimized" version was the optimized version.

List version took 6 mins. Not terrible for python tbh, considering you're running a string check 15.6 million times.


 No.1008314

>>1008312

well I tried really hard to shove the "look I found an answer 25s past the correct answer" into the slot


 No.1008315

>>1008313

try an ASCII string compare (and ASCII getting-the-last-part-of-the-string).


 No.1008316

>>1008310

>57 seconds.

And that reminds me, the creator assured that no challenge, written optimally, should take more than 15 seconds on 10-year old hardware (i.e. mine).

What's the optimal solution, then? I don't see how you'd do it without some math predictions or something.

>>1008312

>Is that the backoff strategy? I've only gotten it up to 1 minute.

<he hasn't gotten it to 10 minutes before

Lucky bastard you are.


 No.1008319

>>1008313

List being faster is expected, given the main jobs are appending and arbitrary indexing.

>>1008315

hes using python2, so ascii is given. Python3 also uses ascii, so long as the string has no chars above ^?.

>>1008316

python is well known to be very slow. I think you could get 100x speedup just by using c++ instead.


 No.1008320

File: 53a085064699f85⋯.png (352.25 KB, 1408x2584, 176:323, day14-ada.png)

Ada, 5.8s. Probably the obvious optimization is to cache the last ten chars in Mix.


 No.1008321

>>1008320

oops, cut it off. the last bit is just

   use Ada.Command_Line;
begin
Reset;
Part1 (Natural'Value (Argument (1)));
Reset;
Part2 (Argument (1));
end Day14;


 No.1008325

C++. After getting over my initial misconception of the problem >>1008306 part 2 was comparatively easy. 0.614s compiling with -Os.


#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <deque>

std::vector<uint16_t> digit_list {3u, 7u};
const std::vector<uint16_t> match_pattern {5u, 8u, 0u, 7u, 4u, 1u};
std::deque<uint16_t> last_n_digits(match_pattern.size());

struct elf {
uint32_t current_index = 0u;
void step() {
current_index += digit_list[current_index];
++current_index;
current_index %= digit_list.size();
}
};

elf elf1{0u}, elf2{1u};
uint32_t match_index = 0u;
bool match_index_lock = false;

void matchQueueCheck() {
if (match_index_lock) {
return;
}
uint16_t idx_ctr = 0u;
bool r = true;
for (uint16_t u : last_n_digits) {
r &= (match_pattern[idx_ctr] == u);
++idx_ctr;
}
if (r) {
match_index = digit_list.size();
match_index_lock = true;
}
}

void createNewRecipes() {
uint32_t sum =
digit_list[elf1.current_index] +
digit_list[elf2.current_index];
if (sum >= 10) {
last_n_digits.pop_front();
digit_list.push_back(sum / 10);
last_n_digits.push_back(sum / 10);
matchQueueCheck();
last_n_digits.pop_front();
digit_list.push_back(sum % 10);
last_n_digits.push_back(sum % 10);
matchQueueCheck();
} else {
last_n_digits.pop_front();
digit_list.push_back(sum);
last_n_digits.push_back(sum);
matchQueueCheck();
}
}

int main(int argc, char* argv[]) {
uint32_t init_size = digit_list.size();
uint32_t desired = 580741u; //desired offset
while (digit_list.size() < (desired + init_size + 10u)) {
createNewRecipes();
elf1.step();
elf2.step();
}
while (!match_index) {
createNewRecipes();
elf1.step();
elf2.step();
}
std::cout << "Part1: \n";
std::for_each(
digit_list.begin() + desired,
digit_list.begin() + desired + 10u,
[&](uint16_t u){
std::cout << static_cast<uint16_t>(u);
});
std::cout << '\n';
std::cout << "Part2: \n";
std::cout << match_index - match_pattern.size() << '\n';
return 0;
}


 No.1008332

>>1008325

>compiling with -Os.

Why? Why does doing this make code almost as fast as -O2?


 No.1008337

>>1008332

http://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html

>-Os

>Optimize for size. -Os enables all -O2 optimizations except those that often increase code size


 No.1008339

File: efb26e47a2fb7df⋯.webm (3.75 MB, 853x480, 853:480, miata_drift.webm)

>>1008337

As for why, I could LARP and say I was trying to save L1i but actually I just did it because I felt like it.


 No.1008341

>len() is always an O(1) for python lists

fug I'm retarded, I used variables for nothing. Ah well. My memecode is still slow as shit anyway.

I think replacing shit with lambdas and list comprehensions actually managed to slow down my script. It was 5 minutes at some point; now it's back to 6. C version eventually, maybe.

def do(part, test, show):      #part 1 & 2 are similar, and using a function increases program speed
scoreboard = [3, 7] #start scoreboard with given numbers
elf1, elf2 = [0, 1] #list of 0,1
while test(''.join(str(d) for d in scoreboard[-7:]) if part else len(scoreboard)): #if part 2, give the last 7 recipes, else give the number of recipes
add = scoreboard[elf1] + scoreboard[elf2] #sum of the elves score
if add > 9: scoreboard.append(add/10) #if the sum has a tens part, add it
scoreboard.append(add%10) #add the ones
elf1, elf2 = [(scoreboard[elf]+elf+1)%len(scoreboard) for elf in (elf1,elf2)] #move elf1&2 to where they should be
print show(scoreboard)

with open('input') as f: input = f.read()[:-1]
given = int(input)

do(0, #do part 1
lambda s_len: s_len < given+10, #while the number of recipes are lower than the given input +10
lambda sb: ''.join(str(d) for d in sb[-11:-1]) if len(sb)-1 == given+10 else ''.join(str(d) for d in sb[-10:])) #print the last 10 recipes, with off-by-one checking
do(1, #do part 2
lambda s: input not in s, #while no matching recipe has been found
lambda sb: len(sb)-6 if input == ''.join(str(d) for d in sb[-6:]) else len(sb)-7) #print the number of recipes -6, with off-by-one checking

>>1008319

>python is well known to be very slow. I think you could get 100x speedup just by using c++ instead.

Guess today is really a brainlet challenge, then.


 No.1008347

I'm really confused about this challenge. Part 1 was ezpz. Doing examples for part 2 was also very easy and all run very fast.

But for the actual input (6 digits) it seems to be taking forever. I'm at 75,000,000 recipes now and still nothing found.

It looks like there's a pattern but it's not simple. Are you really supposed to just brute force it or is there some fast way? How many steps does it even take? Millions or billions?


 No.1008348

>>1008347

you're passing the answer.


 No.1008349

>>1008325

Wait, 9 + 9 = 18.

>Changing modulo to subtract barely changes performance

Well, it's not compute-bound.

>>1008347

Mine was at around 20 million.


 No.1008350

>>1008349

Ah, I'm at 400 million now, guess I fucked up after all. Funny, the examples work fine...


 No.1008351

>>1008347

Answer is ~20mil. >>1008347 and >>1008349 are right. Are you off-by-one in your string comparison? Did you adjust your string checking to be for 6 characters instead of 5 (as in the test inputs)?


 No.1008353

>>1008351

I wasn't even using strings, I was using a list of int. But I switched it to strings now.

>examples all run correctly

>input=765071 at 67 million and counting

dafuq

>Did you adjust your string checking to be for 6 characters instead of 5 (as in the test inputs)?

Well, Python has string.endswith(). But I was measuring the number of digits with my previous list implementation too.

Also why the sage?


 No.1008354

File: 0cae21708eb7a73⋯.png (435.16 KB, 702x842, 351:421, day14.png)


 No.1008355

>>1008353

Oh fuck I know what it is, I bet it's something like ...5432, and then the step adds 10, so I get 543210 and endswith returns false.


 No.1008356

>>1008353

you're not testing the end of the string every time you extend it, so you're passing the answer.


 No.1008357

Mathematica anon where are you?? Post code for today and yesterday.


 No.1008359

>>1008284

>There half as big, so you need to use twice as many of them. Simple math.

Then why is >>1008325 slower when you replace the u16 vectors with u8 ones? I'm a supreme data structure brainlet.

Also, why doesn't the vector run out of memory? Doesn't the digit list ends up holding nearly 1<<31 == 2G values? I have no idea how any data structure works.

>>1008353

sage because it's a small reply similar to the 2 others above it. Kinda pointless to bump anyway if the board only gets a few posts every hour.

>>1008355

>and then the step adds 10

Yeah, that's what I meant by off-by-one. I didn't actually know about endswith, so I just spliced [-7:] and checked if the input string was in.


 No.1008361

>>1008355

>>1008356

>>1008359

Yeah, that was it basically, solved it now. I was just doing recipes += str(sum) and then checking with recipes.endswith(input).

For a lot of these puzzles lately the hardest part was finding some subtle-ish corner case that's not shown in the examples. I keep wasting time because I assume examples cover all the obvious corner cases. I'm used to other non-puzzle exercises I guess. Really wish there were more algorithm design/optimization/pattern finding problems than find the bug.

Oh well, no point in whining. Thanks for the hints guys.


 No.1008363

File: db766bc7afe4971⋯.png (133.01 KB, 922x1112, 461:556, day13-1.png)

File: 224cbb34e9cf017⋯.png (237.5 KB, 934x1430, 467:715, day13-2.png)

>>1008357

I still want to optimize my solution for today. Here's p2 of yesterday.


 No.1008364

File: 4cd2346808a7e1d⋯.png (221 KB, 1038x1470, 173:245, pajeet.png)

>>1008357

Today's. It looks pajeet tier at the moment.


 No.1008367

>>1008359

>why is >>1008325 slower when you replace the u16 vectors with u8 ones?

I would like to know this as well. Drawing off my highly limited knowledge I would speculate it has something to do with cache line alignment or CPU instructions but it's probably simpler than that; I don't know jack shit about computers

>>1008363

I think unless your language has a nice way of working with strings you're going to be writing spaghetti. I don't even want to post my C++ for that day.


 No.1008369

>>1008367

You have to face the bullying anon. I had the courage to post my pajeet style day14 (it's actually done that way to experiment with something), then you can too.


 No.1008371

>>1008359

>why is >>1008325 slower when you replace the u16 vectors with u8 ones?

I couldn't say. My c version for day14 uses u8s, and it runs twice as fast as the c++ version.

In the day 12 solution, the u8 versus u16 doesn't change how they're stored. It changes how many pots you update in a single step. Changing twice as many pots per step is bound to make your code twice as fast.


 No.1008376

>>1008186

I took your advice to use the builtin qsort():

int compare(const void **p1, const void **p2){
Cart *c1 = (Cart*)*p1;
Cart *c2 = (Cart*)*p2;
if (c1->y == c2->y) return c1->x-c2->x;
/*else*/return c1->y-c2->y;}
...move_cart(cart_ls[n]);
qsort(cart_ls, cart_c, sizeof(Cart*), compare);
Turns out, my shady r_qsort() actually worked completely correctly. The program still gives the wrong answer; I can't believe this shit. If part 1 has the right answer, how can part 2 give the wrong one?

>>1008371

>My c version for day14 uses u8s

Mind posting it? Or is it too spaghetti?

>day 12 solution

I got that part, I just didn't read the code at first.


 No.1008389

I kept testing Part 2 against the fist half of my answer from Part 1. Those fucking circular test cases weren't helping, who though that was a good idea? Used linked lists for Day 14, I doubt they make that much of a difference today in comparison to the marble puzzle. CPython does both parts in ~1m43s, PyPy takes about 9.5s-10s.

#!/usr/bin/python

class Node():
def __init__(self, before, after, cargo):
self.before = before
self.after = after
self.cargo = cargo

class DoubleLinkedList():
def __init__(self, total_recipes):
# Construct head & tail
self.head = Node(None, None, 3)
self.tail = Node(None, None, 7)
self.head.before = self.tail
self.head.after = self.tail
self.tail.before = self.head
self.tail.after = self.head
# Part 2
# Puzzle input into a list of digits
self.comparison = [int(x) for x in str(total_recipes)]
self.comp_len = len(self.comparison)
self.matches = 0
self.part_two = True
# Part 1
self.total_recipes = total_recipes
self.size = 2
self.part_one = True
# Positions
self.first_current = self.head
self.second_current = self.tail

self.solve()

def solve(self):
while self.part_one or self.part_two:
# Part 1 inside IF
if (self.size >= self.total_recipes + 10) and self.part_one:
self.part_one = False
self.print_part_one()
self.new_recipe()
self.move()

def print_part_one(self):
result = ''
current = self.head.before
score_size = self.size - self.total_recipes
for i in range(0, score_size):
result += str(current.cargo)
current = current.before
if score_size == 10:
print('Part 1: {0}'.format(result[::-1]))
else:
print('Part 1: {0}'.format(result[1:][::-1]))

# Move current positions of the two elves
def move(self):
for i in range(0, self.first_current.cargo + 1):
self.first_current = self.first_current.after
for j in range(0, self.second_current.cargo + 1):
self.second_current = self.second_current.after

# Append to tail
def new_tail(self, score):
new_node = Node(None, None, score)
self.tail.after = new_node
self.head.before = new_node
new_node.before = self.tail
new_node.after = self.head
self.tail = new_node
self.size += 1

# Adding a new recipe
def new_recipe(self):
score = self.first_current.cargo + self.second_current.cargo
# Check each digit against Part 2
if score // 10 > 0:
new_score = score // 10
self.new_tail(new_score)
self.check_matches(new_score)
new_score = score % 10
self.new_tail(new_score)
self.check_matches(new_score)

# Part 2 checker
def check_matches(self, new_score):
if not self.part_two:
return
if new_score == self.comparison[self.matches]:
self.matches += 1
else:
self.matches = 0

if self.matches == self.comp_len:
self.part_two = False
print('Part 2: {0}'.format(self.size - self.comp_len))

DoubleLinkedList(2018)


 No.1008390

Fell asleep last night, this one was pretty easy tho.


#include <iostream>
#include <vector>
#include <algorithm>

int recs = 84601;
int e1 = 0, e2 = 1;
std::vector<uint16_t> seq = { 0, 8, 4, 6, 0, 1 };
std::vector<uint16_t> recipes { 3, 7 };

void tick(int c = 1)
{
for (int i = 0; i < c; ++i) {
uint16_t n = recipes[e1] + recipes[e2];
if (n/10) {
recipes.push_back(n/10);
recipes.push_back(n%10);
} else {
recipes.push_back(n);
}
e1 = (recipes[e1] + e1 + 1) % recipes.size();
e2 = (recipes[e2] + e2 + 1) % recipes.size();
}
}

int main(int argc, char const *argv[])
{
// part 1
std::cout << "part 1: ";
while (recipes.size()+10 < recs)
tick();
for_each(recipes.end()-10, recipes.end(),
[](uint16_t n) {
std::cout << n;
});
std::cout << '\n';

// part 2
std::cout << "part 2: ";
while (!std::equal(seq.begin(), seq.end(), recipes.end()-10))
tick();
std::cout << recipes.size()-10 << '\n';

return 0;
}


 No.1008394

>>1008376

Okay, I decided to be a man and actually try to... gulp, read your code, I'm not actually reading everything mind you, I'd probably die if I did that so sorry if I'm not understanding something, but this is what I was able to find, I think I deleted something and moved stuff around to make it easier on my eyes but it's still your code:


for (uint8_t c = 0; c < cart_c; c++)
if (cart_ls[c] != cart && cart_ls[c]->x == cart->x && cart_ls[c]->y == cart->y) { //check all remaining carts for collisions
printf("COLLISION AT (%d,%d), TICK %d\n", cart->x, cart->y, tick);
for (uint8_t m = 0, n = 0; m < cart_c; m++)
if (m != c && cart_ls[m] != cart)
cart_ls[n++] = cart_ls[m];
cart_c -= 2;
break;
}

Here you are removing the cars that just crashed, but you also continue on with the function move_cart after that, even when `cart` is now pointing to some other random cart (since you just shifted the whole array).


 No.1008398

>>1008394

Oh thanks anon, that totally worked. Just set move_cart() to return a _Bool and to break on collision.

>italics

I did warn that I was a brainlet anon. You can't fault me for not listening.

Also, you should've seen the python version I attempted before going to C. 200 lines of IndexError and elif c == '[char]'.

Although I'd argue that it looks ugly partially because it isn't [code] formatted


 No.1008404

>>1008394

That wouldn't have happend with Rust. Thanks for proving me right, /tech/ <3<3<3


 No.1008413

>>1008404

>That wouldn't have happend with Rust.

...I'll bite. Why? I don't think that any memelang can cure pajeetness.


 No.1008414

>>1008413

And speaking of pajeetness,

#define is_change_dir(c)	track[c->y][c->x] != (cart->dir > 1<<6 ?'|':'-')
#define coords_eq(c1, c2) c1->x == c2->x && c1->y == c2->y
#define is_leftright(dir) (dir < 1<<6)
#define dir_index(dir) strchr(CARTCHR, dir)-CARTCHR+1
#define below(cart) track[cart->y][cart->x]
#define for_cart_c for (uint8_t c = 0; c < cart_c; c++)

Should I give up while I'm ahead?


 No.1008419

>>1008394

>>1008398

No wait a second, that doesn't make any sense.

- void move_cart(Cart *cart)
+ _Bool move_cart(Cart *cart)
{ ...
cart_c -= 2
- break;
+ return 1;
...}
...
- for (uint8_t n = 0; n < cart_c; n++) move_cart(cart_ls[n]);
+ for (uint8_t n = 0; n < cart_c; n++)
+ if (move_cart(cart_ls[n])) break;

If you do this, then when two carts crash, the rest of the remaining carts have their tick skipped.

At the same time, when I do this, I get the correct answer off-by-2, instead of it being wildly off course.

>>1008404

Do you really believe your memelang can save someone like this?


 No.1008442

>>1008419

You can't skip the other carts' turn yeah, honestly the best thing you could do is delete your program, but if you just want it to work, even though there is nothing useful to learn from this with such a shitty solution, you could return an int instead of a bool.

- return 0 if no crashes

- return 1 if a crash happened AND the cart you just crashed with (not the one you just called move_cart with) was after the cart you just moved (the one you called move_cart with).

- return 2 if a crash happened AND the cart you just crashed with (not the one you just called move_cart with) was before the cart you just moved (the one you called move_cart with).

then you take that int and subtract it from n, instead of breaking, this is to adjust n depending on how much the array was shifted, also make n a signed int in case the first crash happens at index 0.

but then again, it'd be better if you delete your program.


 No.1008470

>>1008419

c.f. Ada >>1007978 when we find a cart to move, first get the location it'd move to. If that location contains a cart, pass both carts to a crash procedure so that it can

1. log that this happened

2. remove both carts from your data structure(s)

if you're looping over indices of a fixed array instead of carts themselves, you're done. If you're looping over carts, then just mark both carts as crashed and free them / ignore them when you find them.

if you can't add a field to your cart, just keep a crashed_carts that you can check during the loop.


 No.1008472

File: 3e80e0d4b973314⋯.jpg (88.32 KB, 1240x775, 8:5, pfff.jpg)

This is driving me nuts. It calculates the first crash correctly, but part 2 just doesn't get accepted.

At first I got a different result because I didn't sort the carts movement by top->bottom and left-> right, which apparently mattered more than I thought, but now I'm at a loss.. No idea what could cause the answer to be wrong.

#!/usr/bin/env ruby
class Cart
attr_reader :x, :y, :collided_with, :id
@@ids = 0

def initialize(x, y, dir)
@id = (@@ids += 1)
@x=x; @y=y
@dir = ['<','^','>','v'].index(dir)
@switch = [-1,0,1]
@collided_with = []
end

def move()
[-> {@x -= 1},-> {@y -= 1},-> {@x += 1},-> {@y += 1}][@dir].call
case $map[@y][@x]
when '+'
@dir = (@dir+@switch[0])%4
@switch.rotate!
when '\\'
@dir = [1,0,3,2][@dir]
when '/'
@dir = [3,2,1,0][@dir]
end
end

def collided_with?(carts)
carts.each do |cart|
@collided_with << cart if cart.id != @id && cart.x == @x && cart.y == @y
end
@collided_with.length > 0
end

def dir
['left','up','right','down'][@dir]
end
end

# Read map and extract carts
$map = []; carts = []
input = File.readlines("d13input.txt")
input.each_with_index do |line, y|
x = -1
while !(x = line.index(/[\^<>v]/, x+1)).nil?
carts << Cart.new(x, y, line[x])
end
$map << line.tr('<>^v','\-\-||')
end

# Print info
$map.each {|l| puts l}
puts "\nInitial cart positions:"
carts.each {|c| puts "#{c.id}: #{c.x},#{c.y} - moving: #{c.dir}"}
puts "\nReady.. set.. go!"

# main loop
while carts.length > 1
remove = []
carts.each do |cart|
cart.move()
if cart.collided_with?(carts)
remove += cart.collided_with
remove.each {|r| puts "Boom! Cart #{cart.id} (going #{cart.dir}) and #{r.id} (going #{r.dir}) @ (#{cart.x}, #{cart.y}) are no more.."}
remove << cart
end
end
carts -= remove
carts.sort_by! {|v| [v.y, v.x]}
end

puts "Final Cart: #{carts[0].id} (#{carts[0].x}, #{carts[0].y}) #{carts[0].dir}" if carts.length > 0
puts "Done!"


 No.1008478

>>1008472

looks you don't remove carts until after the loop where you move them and check for collisions. So instead of immediately removing a cart, you move it and allow another cart to then collide with it.


 No.1008484

File: 13c03fa45d03693⋯.png (1.34 KB, 166x57, 166:57, ffs.png)

>>1008478

Indeed, I put it in there that way as one of my earlier attempts at a fix. Didn't seem to matter though. I've restored it to the old version:

# main loop
while carts.length > 1
carts.each do |cart|
cart.move()
if cart.collided_with?(carts)
cart.collided_with.each {|r| puts "Boom! Cart #{cart.id} (going #{cart.dir}) and #{r.id} (going #{r.dir}) @ (#{cart.x}, #{cart.y}) are no more.."}
carts -= cart.collided_with
carts.delete(cart)
end
end
carts.sort_by! {|v| [v.y, v.x]}
end

But I get the same result still.

Even weirder, I put my input against >>1008004 's code and got the same result there. Somehow his routine has worked for him, not for me.

Final Cart: 1 (16, 134) up


 No.1008485

File: c76db1c59ab13eb⋯.jpg (384.3 KB, 1400x933, 1400:933, steve klabnik.jpg)

>>1008484

Time to rewrite it in Rust. Rust's borrow checker prevents a variety of bugs, not all of which are memory safety related.


 No.1008486

>>1008485

..but I said I matched the input against a rust solution and got the same result.


 No.1008487

File: 275286846288e05⋯.jpg (119.92 KB, 1024x683, 1024:683, steve klabnik 7.jpg)

>>1008486

Then the result is correct. My Rust solution doesn't have any bugs. You probably failed to properly submit the solution. That is outside of Rust's scope to handle, I'm afraid.


 No.1008489

>>1008487

not all inputs suss out all bugs.


 No.1008490

>>1008489

Post your input please. I will check if your preposterous claim has any truth to it. (it doesn't. If it compiles, it is correct. Rust statically guarantees this.)


 No.1008491

File: 1a6fe107f62687f⋯.png (12.78 KB, 860x166, 430:83, AARGH.png)

>>1008487

I think it's the 3rd time I inputted these numbers because I'm that frustrated.


 No.1008492

>>1008491

you've tried it without the space, right?

or did you definitely input a space in part1?


 No.1008493

>>1008491

>he put a space after the comma

Rust is perfect


 No.1008494

>>1008491

>7 times

btw you only have 10 tries It think. After that you'll be locked out.


 No.1008497

File: 286c689b2f1d7f8⋯.gif (1.17 MB, 245x165, 49:33, mad.gif)

>>1008492

>>1008493

If it's that fucking space I'm going to kill the developer of AOC.


 No.1008499

>>1008497

post the input please


 No.1008500


 No.1008501

Just tested this: >>1008472 on my input. Everything works.

>>1008492

Better question - what kind of a fucking brainlet does not remove whitespace from answers server-side before checking them (if that's the case)?


 No.1008502


 No.1008504

>>1008491

I get the same answer with Ada. It's the space.


 No.1008505

>>1008504

or everyone has the same bug and only your input catches it


 No.1008506

File: 8981c38b97fdb01⋯.png (12.35 KB, 831x138, 277:46, AAAAAAAAAAAAAAAAAAAAAAAAAA….png)

File: 2e6c2089b8320ce⋯.jpg (29.08 KB, 620x347, 620:347, raaaage.jpg)

>>1008504

>without space

I'm going out for a walk..


 No.1008507

File: ecc5ffc69aaa0ba⋯.jpg (51.53 KB, 1280x720, 16:9, steve klabnik 9.jpg)

>>1008506

PRAISE OUR LORD AND SAVIOUR, STEVE KLABNIK!


 No.1008532

>>1008491

You'd think the system would trim spaces. You could argue that example formats were given without the space, but still, that's pretty pathetic. Glad I didn't fall down that trap.


 No.1008533

>>1008494

Forever? Or does it just lock you out for an hour or so? There's no point locking a person for too long, as they've clearly missed any chance of getting a good score.


 No.1008538


 No.1008619

>>1008532

>inb4 this space thing becomes a meme in cuckchan's AOC calendar


 No.1008626

>>1008619

lmao cuckchan are too busy kicking people from their leaderboard so they can climb the e-programmer rankings and get top 20.

meanwhile tech has all the stars.


 No.1008644

>>1008442

I fixed it and then deleted it, under your advice. I only wanted to figure out why it was broken, I have 0 intention to peddle this around as readable code.

>>1008470

That's nearly what I did. I'm presuming the, "you're done," is pejorative/a misunderstanding; my assumption of the procedure being done and done was what caused it to fail this entire time.


 No.1008649

>>1008644

>"you're done" is a pejorative

No. If you're looping over 2d indices, then you don't have to worry that removing a cart will affect the loop that you're in.


 No.1008672

>>1008649

Oh. I'm retarded, I didn't read the Ada.

I'm glad I didn't choose to loop over 2d indices. My 'code' would have been even longer.


 No.1008701

LARP in 5 minutes.


 No.1008703


 No.1008704

guess

>take your cart code from the other day and make it into a programming language by adding a bunch of extra tiles

>debug this program


 No.1008705

>>1008704

close!

it's a roguelike game


 No.1008706

long one.


 No.1008710

>mapping paths, collision detection, closest distance

uh

Brainlet here, I can't do any of this.


 No.1008711

in the time you spent on these jewish puzzles you could have found a gf


 No.1008712

>15 minutes

>not a single person has even done part 1

Thank god. I thought there was some easy mode way to do this.


 No.1008713

so who here is familiar with A* ?

not me


 No.1008717

>>1008710

break it up. lots small functs.


 No.1008721

someone is done p1... fuck.


 No.1008727

>>1008717

Actually, I'm kinda at a loss at how to find shortest path without collisions. The only time I've ever needed to do this kind of thing, I'd already had helper functions to do all the work.


 No.1008728

>>1008727

dijkstras.


 No.1008733

>>1008728

>dijkstras

Shit. I searched and implemented Lee algorithm. Surely it won't be too slow.


 No.1008744

Fuck this; I'm doing this tomorrow.


 No.1008749

>python list assignments are only ever shallow copies

Kill me. And I spent nearly 30 minutes trying to fix this. How the fuck was I supposed to know that copy = s[:] still created a shallow copy?


 No.1008754

>>1008733

Lee's might be faster for all I know. I did dijkstras cause its easy.

you suckers wanna borrow my code? still slots left in the top 100.


 No.1008756

>>1008744

Kinda my attitude. I'm going to do it tonight, but I'm going to take my time.


 No.1008759

>100 minutes have passed

>not even as-many stars have been distributed for the day, combined

So, how's your progress anons? I've only just gotten movement to finally work; haven't even started on attacking.


 No.1008765

>>1008759

Just about to do attacking. Added all the HP stuff.


 No.1008766

>>1008759

still working out pathfinding, brute force recursion with some state tracking and using a job list as a stack since real recursion would blow it.

don't even know if this will work.


 No.1008767

Does anyone have a link to the site showing the distributions of time on each day? It was posted upthread, but it's been deleted. Alternatively, does anyone know how to look at old posts in cyclical threads on 8ch?


 No.1008768

>>1008766

... holy shit. looks like it works.

let's hope it's still working after I remember what the rest of this task even was.


 No.1008769

Just starting on this now as I had to miss when the challenge started. It looks like it's another dumb problem that favors imperative over functional programming.


 No.1008773

And of course I pass all the examples and fail on my input.


 No.1008775

>>1008768

>3 hours into puzzle

>"hit points"

oh they have hitpoints.

good to know.


 No.1008776

>test input 4 answer is wrong

>mfw final answer still correct

get fucked testfags


 No.1008778

I need hints on what to do for part 2. Is the best method just to bruteforce +X attack power by increments of 20/10/5/2/1? Surely this is a violation of 15 seconds.

>>1008767

>old posts

Can't. 8archive died a long ass time ago.


 No.1008781

>>1008778

>Is the best method just to bruteforce +X attack power by increments of 20/10/5/2/1? Surely this is a violation of 15 seconds.

I did increments of 1 on my extremely naive python code, and got it in 11 seconds.

>8archive died a long ass time ago.

Found it on archive.org. Turns out someone faithfully archives this thread twice a day.

http://www.maurits.vdschee.nl/scatterplot/

Too bad today isn't up yet


 No.1008784

>>1008781

>I did increments of 1 on my extremely naive python code, and got it in 11 seconds.

Note the 10-year-old hardware (>>1008310), your code might take 3+ minutes on my setup. Nonetheless, my python code is still certainly worse than yours, considering it takes 3 entire seconds to finish a single turn (not to increment the power by 1. To complete a single turn).


 No.1008786

>the units teleport right next to their target, instead of walking

>everyone does this and frags the previous unit

>once next to an enemy, everyone forgets they can kill with teleportation and starts duking it out

>somehow this answer is wrong

bugged day.


 No.1008791

>>1008786

>every time a unit is injured, the damage is taken, and hit points are lost

>but in a moment the wound heals

>goblins and elves will fight forever in darkness, and receive injuries forever

>somehow this answer is wrong


 No.1008792

Alright, took a break and back to fixing the bug in part 1 :(.


 No.1008800

see, the real problem here, is that I'm too smart for AoC's silly standards on how precisely one must traverse some kind of decision tree. Gestalt thinking vs. rule thinking. If you're comfortably with this "reading order" shit then you basically have slave mindset.

god damnit


 No.1008801

>>1008800

>I'm too smart

found the LARPer. Post code of GFTO


 No.1008805

>To play, please identify yourself via one of these services:

> [GitHub] [Google] [Twitter] [Reddit]

yeah you can go fuck yourself


 No.1008806

File: b1d42675da2827d⋯.png (490.77 KB, 1408x3392, 22:53, day15-ada.png)

>>1008801

pic related is the pathfinding, populating a 4d array of every coordinate's cost of travel to every other coordinate + the first direction that you'd have to set off from.

that array is rebuilt every time a unit moves.

elsewhere, Best_Advance looks at every adjacent square of a prospective target and picks the lowest cost one - or the uppermost/leftmost one on a tie.

but this happens:

round:  0
#########
#G..G..G#
#.......#
#.......#
#G..E..G#
#.......#
#.......#
#G..G..G#
#########

moving from 8, 5 to LEFT: 7, 5
picking score 6
done

round: 1
#########
#.G...G.#
#...G...#
#...E...#
#.G...G.#
#.......#
#...G...#
#.G...G.#
#########
the goblins win. I'm going to bed.


 No.1008825

def do_turn(race, coord): [...]
#part 1
s = getInput() #list of list()ed lines
gobs = defaultdict(lambda: None)
elves = defaultdict(lambda: None)
for y in range(len(s)):
for x in range(len(s[y])):
if s[y][x] == 'E': elves[(y,x)] = 200
if s[y][x] == 'G': gobs[(y,x)] = 200
turn = 0
copy = [l[:] for l in s]
while gobs.keys() and elves.keys():
copy = [l[:] for l in s]
turn += 1
for y,x in sorted(gobs.keys() + elves.keys()):
if do_turn(s[y][x], (y,x)):
turn -= 1
break
s = copy
if gobs.keys(): race_d = gobs
else: race_d = elves
print "FINAL: %d" % (turn*sum(race_d.values()))

The code above works out fine. If anyone is willing to help, I need to know, why does doing this:

...
while ...:
- copy = [l[:] for l in s]
...
give an off-by-(3*turn) error? (I can post the rest of the script)

I cannot think of a single reason as to why omitting that single line would create a difference. `copy` is assigned to a deep copy of s. This should change nothing, because at the end of the loop, s itself is reassigned to point to copy.


 No.1008835

>every solution can be done within 15 seconds on 10 year old hardware.

I pulled the old Java out of the dust and re-made Day14 in pajeet as well as I could, being rusty as fuck and all. The code is atrocious to say the least, even for Java standards, but the god damn thing finished part 2 in 3 seconds.

Pleasantly surprised.


 No.1008836

>>1008835

Read the advice not to use bytes (/u8) and changed the stupid byte arrays to plain int arrays and now it's just 600ms, while I still have plenty of ideas to optimize.

I love using scripting languages and all, but I never expected the difference to be this big, especially with Java.


 No.1008838

Somehow I'm out on hitpoints on the test case. Fucking hell.


 No.1008842

>10 hours in

>less than 800 people solved part 2

lol


 No.1008845

>>1008842

Looking forward to that one... Having serious focus problems with part 1 already.

I like short problems.


 No.1008855

>>1008845

Forget about it anon. It's large and the actualy input will probably fail anyway like most people who gave up.


 No.1008859

python is the big brain language for this as it has a mature stdlib and is hackable


 No.1008860

>>1008845

>I like short problems.

This.

At least for me, it reached a point where puzzles aren't fun anymore.

I was already having issues comprehending them, but now even implementing a solution would be massive work.


 No.1008864

>>1008845

Part 2 is Day10-tier tbh. If you can solve part 1, you need to have some severe brainlet insanity to be unable to do 2. At worst, you can just bruteforce part 2 once you finish 1.


 No.1008910

You know what a good way to waste many hours is? Note the starting positions of all units, and when it is time to move a unit whose position is now '.', assume it is dead and continue. Great bug, recommend you all try that one.

It fails pathologically. If a unit was killed, and another unit moved into the space of the one that was killed, in that round, the unit ended up receiving another turn.


 No.1008925

>First input fails because of the counter, but everything else, including the solutions, works

Also bruteforced the shit out of Part 2, what a day. Wasted a couple of hours trying to do some shit with trees, just ended up expanding the dots around the player until I found the closest enemy. Either I'm leaving code cleanup for tomorrow, or it's gonna take the entire fucking night.


 No.1008926

>247 LOC

>haven't even tried compiling yet

I will make part 1 because I don't like quitting without notice, but if part 2 has to do with diagonal moves (I haven't been spoiled yet) I'm quitting there.


 No.1008927

>>1008926

No diagonal moves. You can actually get part2 quite quickly from part1. Going to do tonight's challenge tomorrow though, need a break.


 No.1008928

Christ, finally got a functioning "game". Elves and Goblins are path seeking, attacking, killing each other. Watching it all happen on the terminal looks like it works perfectly well, yet the final numbers aren't right... of course...

There's just no fun in fixing that. I know I probably don't do the pathseeking exactly as expected, because I calculate it in reverse (from the target instead of towards), but the result it perfectly fine.

Meh.


 No.1008929

>>1008928

Did you remember to attack after completing a move?


 No.1008930

>>1008929

I'll check that. I understood the rules were like most turn based games. Either move or attack, not both. But it's easy to overlook the little details in all the rules.


 No.1008934

>>1008930

It really is. I went to bed, woke up and realized what I'd done, and fixed it in the night, still got position 555. Just shows you how many people quit this one early.


 No.1008938

>>1008934

Or they're still working on it, like me, kek.

Changing the attack to instantly after a move helped, but the result is still "too low". I'll rewrite the pathfinding later, pretty sure that's it. Not quitting yet though, just taking a break.


 No.1008940

>>1008925

>>First input fails because of the counter, but everything else, including the solutions, works

Same here. You think he fucked up the example? I wouldn't put it past him.


 No.1008947

Alright lads, my program is theoretically complete, time to compile, I haven't tried to compile even once, time to suffer, wish me luck.


 No.1008962

Why are you still doing this?


 No.1008965

>>1008962

That's not a bad question.


 No.1008966

>>1008962

Because I'm so fucking close.


 No.1008968

File: 03dff11cbb2afe0⋯.jpg (258.39 KB, 1200x720, 5:3, 01923.jpg)

>>1008947

I need all the luck myself, but you can have my sympathy.


 No.1008975

>Todays challenge write the exact program I wrote to come up with this challenge.

How much $$$ can I get for this idea?


 No.1008982

>>1008926

In part2, it's the same but instead of a 2D grid, it's played on the surface of a 4d sphere, in which you can control the time element to stop things occurring before they happen. True story, would never lie to you.


 No.1008998

>>1008975

I have a better one

>Today's challenge is to take this issue I assign to you and you have to resolve it

>Instead of paying your for your work in memory, I'll just give you a gold star for being a good boy


 No.1009011

>>1008998

>better

your theory is retarded; you're probably just a nocoder. other anon's theory is literally what I've thought for a few of these challenges.


 No.1009015

>>1008982

>What is the sha-256 hash of the program to find the correct answer?


 No.1009037

3 minutes to LARP. Maybe we should all just stop doing this?


 No.1009038

.

day #1 : 54232
day #2 : 42911 is only 79.12% of previous day's 54232
day #3 : 32679 is only 76.16% of previous day's 42911
day #4 : 23633 is only 72.32% of previous day's 32679
day #5 : 23813 is only 100.76% of previous day's 23633
day #6 : 16295 is only 68.43% of previous day's 23813
day #7 : 13161 is only 80.77% of previous day's 16295
day #8 : 12682 is only 96.36% of previous day's 13161
day #9 : 10834 is only 85.43% of previous day's 12682
day #10 : 10994 is only 101.48% of previous day's 10834
day #11 : 10044 is only 91.36% of previous day's 10994
day #12 : 8060 is only 80.25% of previous day's 10044
day #13 : 6422 is only 79.68% of previous day's 8060
day #14 : 6188 is only 96.36% of previous day's 6422
day #15 : 1876 is only 30.32% of previous day's 6188

>>1009037

I just hope it's easy so that I can get back to pathfinding.


 No.1009039

4174 lines of input


 No.1009040

>the first section of your puzzle input

So that's why my parsing failed.


 No.1009048

>how many SAMPLES behave like 3 or more-

FUCK

I THOUGHT IT SAID OPCODES, NOT SAMPLES

AHHHHHHHHHHHHHHHHHHHHHHHHHH


 No.1009049

>>1009048

This means samples that could have had 3 or more different opcodes and the same before and after would work. Right now my count of that isn't right.

I forgot to add banr bani, but it turns out that it doesn't even effect my count


 No.1009055

fucking hell

$ ./day16|grep 'opcode # 2 '|awk '{print $NF}'|sort|uniq -c|sort -n
44 Bani
44 Banr
44 Bori
44 Borr
44 Eqri
44 Eqrr
44 Gtir
44 Muli
44 Mulr
44 Setr

may as well randomly sort the list of opcodes and run 16 * 16 versions against the input.


 No.1009061

Day 15 part 1 as promised: https://pastebin.com/gTDHS4gt.

Now I quit, goodbye.


 No.1009064

>staring at printed outputs for over 30 minutes, wondering how the fuck add(1,1) == 1

>fuck it, I'll try putting in the answer anyway

<You are one gold star closer to fixing the time stream.

Turns out, I was just printing my outputs in the wrong order. Kill me.


 No.1009067

yep, today's easy. with a logic table it's obvious that opcodes can be assigned deterministically. since there's no control flow instructions, there are no shenanigans with the code once you run it.


 No.1009069

>>1009067

Is there supposed to be two opcodes that do the same thing?


 No.1009070

File: 965ff0b37741742⋯.png (284.34 KB, 1408x2040, 176:255, day16-ada.png)

Ada. the Time_Machine and Aoc_Input code is just drudgery, a whole bunch of

   procedure Borr (A, B : in Int; C : in Register) is
begin
Registers (C) := Registers (A) or Registers (B);
end Borr;
procedure Bori (A, B : in Int; C : in Register) is
begin
Registers (C) := Registers (A) or B;
end Bori;


 No.1009071

>>1009069

nope. What I did in >>1009055 was backwards.

I figured it out in this manner:

1. get a list of all possible op(##, Instr) combinations

2. notice that one ## only has a single possible Instr

3. assign the singleton ## to its instruction, then remove that instruction from the rest of the list.

4. goto 2


 No.1009072

>>1009071

with the list from #1 I noticed

A. Eqir only appeared once in the list -- it can only possibly be that opcode

B. opcode 10 only appears once in the list -- it can only be this one instruction

that, before removing anything. Once you remove all occurrences of the two instructions you find in this manner, there are now more singletons that can only be one thing, repeat.


 No.1009088

File: bbb618164540e66⋯.jpg (41.63 KB, 299x275, 299:275, 1411523232298.jpg)

When did the puzzles stop being fun?


 No.1009092

>>1009015

now that's a spicy puzzle


 No.1009100

Day16 was a really nice puzzle. Started on it late, but it was fun.


 No.1009125

>>1009088

Still fun for me, Hitler. Or maybe that's just because Day 15 was such a shitshow that anything is more fun. Did today with a wall register lambdas and a dictionary that translates opcodes into those registers.

#!/usr/bin/python

import re
sample_data = re.compile('\[(\d)+, (\d)+, (\d)+, (\d)+\]')

def main():
# Dictionary of lambda functions
registers = {}
registers['addr'] = lambda inp, cmd: inp[cmd[1]] + inp[cmd[2]]
registers['addi'] = lambda inp, cmd: inp[cmd[1]] + cmd[2]
registers['mulr'] = lambda inp, cmd: inp[cmd[1]] * inp[cmd[2]]
registers['muli'] = lambda inp, cmd: inp[cmd[1]] * cmd[2]
registers['banr'] = lambda inp, cmd: inp[cmd[1]] & inp[cmd[2]]
registers['bani'] = lambda inp, cmd: inp[cmd[1]] & cmd[2]
registers['borr'] = lambda inp, cmd: inp[cmd[1]] | inp[cmd[2]]
registers['bori'] = lambda inp, cmd: inp[cmd[1]] | cmd[2]
registers['setr'] = lambda inp, cmd: inp[cmd[1]]
registers['seti'] = lambda inp, cmd: cmd[1]
registers['gtir'] = lambda inp, cmd: 1 if cmd[1] > inp[cmd[2]] else 0
registers['gtri'] = lambda inp, cmd: 1 if inp[cmd[1]] > cmd[2] else 0
registers['gtrr'] = lambda inp, cmd: 1 if inp[cmd[1]] > inp[cmd[2]] else 0
registers['eqir'] = lambda inp, cmd: 1 if cmd[1] == inp[cmd[2]] else 0
registers['eqri'] = lambda inp, cmd: 1 if inp[cmd[1]] == cmd[2] else 0
registers['eqrr'] = lambda inp, cmd: 1 if inp[cmd[1]] == inp[cmd[2]] else 0

part_one, part_two = read_file("input")
opcodes = match_opcodes(part_one, registers) # Part 1 & Part 2 prep
run_program(part_two, opcodes, registers) # Part 2

def run_program(instructions, opcodes, registers):
state = [0, 0, 0, 0]
for cmd in instructions:
code = opcodes[cmd[0]] # Match opcode with register
result = registers[code](state, cmd)
state[ cmd[3] ] = result # Last index of cmd contains write register
print('Part 2: {0}'.format(state[0]))

def match_opcodes(samples, registers):
# 0 is the input, 1 is the command, 2 is the result
count = 0 # Part 1 variable
cmd_dict = {}
for sample in samples:
values = set()
# If command matches, add to set
for k, v in registers.items():
result = v(sample[0], sample[1])
if result == sample[2][ sample[1][3] ]:
values.add(k)
num_values = len(values)
if num_values >= 3: # Add to Part 1 count if gt 3
count += 1
# Find the least ambiguous instruction set for each opcode
if not sample[1][0] in cmd_dict:
cmd_dict[ sample[1][0] ] = values
elif num_values < len(cmd_dict[ sample[1][0] ]):
cmd_dict[ sample[1][0] ] = values
print('Part 1: {0}'.format(count))
results = {}
# Remove registers that match only one opcode until nothing remains
while len(cmd_dict) > 0:
next_opcode = min(cmd_dict.values(), key=lambda x: len(x))
cmd_keys = list(cmd_dict.keys())
for k in cmd_keys:
if cmd_dict[k] == next_opcode: # Add key to results
results[k] = list(cmd_dict[k])[0]
cmd_dict.pop(k, None)
else: # Subtract it from every other set
cmd_dict[k] -= next_opcode
return results

def read_file(filename):
f = open(filename, 'r')
samples = [] # Part 1 dataset (array of 2D arrays)
instructions = [] # Part 2 dataset (2D array)
# Variables for Part 1
cmd = False
after = False
sample = []
for line in f:
# Part 1 reading
tokens = line.split(':')
if len(tokens) > 1:
if after:
after = False
sample.append([int(x) for x in sample_data.findall(line)[0]])
samples.append(sample)
sample = []
elif tokens[0] == "Before":
cmd = True
sample.append([int(x) for x in sample_data.findall(line)[0]])
elif cmd:
after = True
cmd = False
sample.append([int(x) for x in line.split(' ')])
else: # Part 2 reading
tokens = line.split(' ')
if len(tokens) > 1:
instructions.append([int(x) for x in tokens])
return samples, instructions

main()


 No.1009126

>people still dump their code that no one reads

Why?


 No.1009127

>>1009126

Why not?


 No.1009128

File: 90669522dc3b9c8⋯.png (1.47 MB, 767x2697, 767:2697, day16.png)


 No.1009130

File: 6819b3f5c9492f4⋯.png (8.8 KB, 822x78, 137:13, Cyberfox_2018-12-16_13-44-….png)

File: f8ca0ef701511a8⋯.jpg (53.07 KB, 800x577, 800:577, wtf.jpg)

>program works at first try


 No.1009164

File: 4a23bf12a5db62d⋯.png (826.02 KB, 876x1328, 219:332, day16.png)


 No.1009166

>>1009164

Nice. I did the code matching manually in a texteditor. You're clearly less lazy.

#!/usr/bin/env ruby
ops = {11 => :addr, 5 => :addi, 1 => :mulr, 8=> :muli, 4 => :banr, 12 => :bani, 13 => :borr, 9 => :bori, 10 => :setr, 6 => :seti, 7 => :gtir, 2 => :gtri, 3 => :gtrr, 14 => :eqir, 0 => :eqri, 15 => :eqrr}

funcs = {
:addr => ->(a,b,c) {$reg[c]=$reg[a]+$reg[b]}, # (add register) stores into register C the result of adding register A and register B.
:addi => ->(a,b,c) {$reg[c]=$reg[a]+b}, # (add immediate) stores into register C the result of adding register A and value B.
:mulr => ->(a,b,c) {$reg[c]=$reg[a]*$reg[b]}, # (multiply register) stores into register C the result of multiplying register A and register B.
:muli => ->(a,b,c) {$reg[c]=$reg[a]*b}, # (multiply immediate) stores into register C the result of multiplying register A and value B.
:banr => ->(a,b,c) {$reg[c]=$reg[a]&$reg[b]}, # (bitwise AND register) stores into register C the result of the bitwise AND of register A and register B.
:bani => ->(a,b,c) {$reg[c]=$reg[a]&b}, # (bitwise AND immediate) stores into register C the result of the bitwise AND of register A and value B.
:borr => ->(a,b,c) {$reg[c]=$reg[a]|$reg[b]}, # (bitwise OR register) stores into register C the result of the bitwise OR of register A and register B.
:bori => ->(a,b,c) {$reg[c]=$reg[a]|b}, # (bitwise OR immediate) stores into register C the result of the bitwise OR of register A and value B.
:setr => ->(a,b,c) {$reg[c]=$reg[a]}, # (set register) copies the contents of register A into register C. (Input B is ignored.)
:seti => ->(a,b,c) {$reg[c]=a}, # (set immediate) stores value A into register C. (Input B is ignored.)
:gtir => ->(a,b,c) {$reg[c]=(a>$reg[b])?1:0}, # (greater-than immediate/register) sets register C to 1 if value A is greater than register B. Otherwise, register C is set to 0.
:gtri => ->(a,b,c) {$reg[c]=($reg[a]>b)?1:0}, # (greater-than register/immediate) sets register C to 1 if register A is greater than value B. Otherwise, register C is set to 0.
:gtrr => ->(a,b,c) {$reg[c]=($reg[a]>$reg[b])?1:0}, # (greater-than register/register) sets register C to 1 if register A is greater than register B. Otherwise, register C is set to 0.
:eqir => ->(a,b,c) {$reg[c]=(a==$reg[b])?1:0}, # (equal immediate/register) sets register C to 1 if value A is equal to register B. Otherwise, register C is set to 0.
:eqri => ->(a,b,c) {$reg[c]=($reg[a]==b)?1:0}, # (equal register/immediate) sets register C to 1 if register A is equal to value B. Otherwise, register C is set to 0.
:eqrr => ->(a,b,c) {$reg[c]=($reg[a]==$reg[b])?1:0}, # (equal register/register) sets register C to 1 if register A is equal to register B. Otherwise, register C is set to 0.
}

$reg = [0,0,0,0]
IO.readlines("d16inputb.txt").each do |entry|
cmd = entry.chomp.split(' ').map {|e|e.to_i}
funcs[ops[cmd[0]]].call(cmd[1], cmd[2], cmd[3])
end
p $reg


 No.1009195

>>1009126

>S-stop it! Stop writing code.

>Stop reminding me of what I cannot do.

Admit it, you're the LARP.


 No.1009196


 No.1009203

File: bad9c9a0616de6c⋯.png (23.07 KB, 286x700, 143:350, shit.png)

FUCK

I found why my day15 code has these small occasional differences in outcome. I was sure I could delete an element of an array which was doing a for-each loop with it automatically adjusting for it. Apparently not. Apparently it skips one element if the deleted element happened to be before the current one. Probably doesn't even happen all the time, because only one test fails..

Pfff.. more rewriting to be done.. this time hopefully the last time..


 No.1009206

File: 720b38b14eeac4a⋯.mp4 (937.55 KB, 1024x1024, 1:1, day15.mp4)

>>1009203

Meanwhile, people are showing off on reddit with visualizations.


 No.1009208


 No.1009227

>>1009206

>goblins are brown

Based


 No.1009228

File: d5d9b86a8d321e5⋯.png (277.34 KB, 1532x1048, 383:262, day16a.png)

File: 92710d330ca36ae⋯.png (284.17 KB, 1722x1396, 861:698, day16b.png)

>>1009126

For your viewing pleasure. I solved the opcode assignments in part2 last night manually by just deleting more and more from the constraints.

To make it a bit fancier (and automated), I turned into a SAT (https://en.wikipedia.org/wiki/Boolean_satisfiability_problem), and let the solver do all the work.


 No.1009244

>>1007894

Just happened to #MeToo. I feel violated. I no longer feel safe. I am very shaken right now, still processing what has happened.


 No.1009248

>>1009244

kek, I seem to have been kicked off one too.

No idea why. Don't really care either. Hardly see the point of 'm.


 No.1009288

>>1009126

The kikes that run the competition harvest the optimal solutions that the useful idiots post 4free.


 No.1009308

File: 6f632df14bda930⋯.png (208.38 KB, 450x433, 450:433, 3.png)

God damned, I did that fucking day 15.. Christ what a pile of shit.

>choose enemies based on distance first, then reading order.

>when just one step away from enemy, move and attack

>when next to multiple enemies, attack the one with the lowest HP

There I made the mistake. When I selected a one-step away enemy, I moved and attacked. but I didn't check after that one step if I had gotten in range of another enemy too. I had to recheck, apply the HP rule and switch if necessary.

God damned.. The one case where that was the deciding factor was somewhere 2/3 in of 103 rounds.

Thank god part 2 was a joke.


 No.1009311

File: 29864a5834c9f78⋯.jpg (27.08 KB, 500x500, 1:1, 1453838786235.jpg)

>>1009288

>he's against free and open software


 No.1009312

>>1009311

He's probably just against open sores. You are literally devaluing yourself if you sell what you make for $0 than what it is actually worth. Since it's free others can exploit the work you've done an unlimited amount of times.


 No.1009313

File: 0cdcd1f353d894e⋯.png (82.77 KB, 247x247, 1:1, jr4fo6dr4tj01.png)

>>1009308

>When I selected a one-step away enemy, I moved and attacked. but I didn't check after that one step if I had gotten in range of another enemy too. I had to recheck, apply the HP rule and switch if necessary.

What the fuck?, why would you ever do it like that?, why not just:

attack (end turn if successful) > move > attack

I'm sorry for bullying (I'm not) but I'm genuinely confused at what went through your mind when you though it was a good idea to look for an enemy 2 tiles away to "move and attack" instead of just moving then trying to attack.


 No.1009321

>>1009313

Huh? Seems simple to me also your example makes no sense. A one tile away enemy is a special situation. This is about the only turn based game where you can move AND attack in ONE turn. When moving, the choice of enemies has a different rule set then when in range of enemies.

I don't know about you, but selecting an enemy at the start of a turn, then attacking another during that turn isn't something I'd expect to be doing in a turn based game.


 No.1009322

File: 59e2378d96821f1⋯.png (19.5 KB, 779x49, 779:49, ClipboardImage.png)

>>1009321

>A one tile away enemy is a special situation.

No, it's not a special situation, it's always the same.

To move, you find all tiles in the map that are directly adjacent to an enemy, out of those tiles, you move towards the one with the cheapest path, you never "select an enemy" to move to, pic related is literally what the puzzle says, moving is separate from attacking.


 No.1009323

File: 34430b6f45c7d53⋯.png (18.29 KB, 842x96, 421:48, ClipboardImage.png)

>>1009322

Wrong pic


 No.1009333

File: 603174a23b6ba38⋯.mp4 (6.29 MB, 1788x1080, 149:90, Day 15 - Unity Visualizati….mp4)

>>1009206

And now some guy dumped his into Unity.


 No.1009335

>>1009323

>>1009322

>then the unit identifies all numbers that are in range of the largest number. This is all the numbers that are below the largest number without having another number larger than them.

>it says you have to find the second largest number

<no it doesn't it says something more verbose but that means the exact same thing


 No.1009344

>>1009335

>>then the unit identifies all numbers that are in range of the largest number. This is all the numbers that are below the largest number without having another number larger than them.

...the fuck? What the hell are you even talking about?


 No.1009350

>today

oh god it's day 15 all over again


 No.1009357

>answer's wrong

>I can draw the answer and look at it and it's completely hugging fine


 No.1009358

>you have to mess with creating multiple concurrent streams of water at once

Well, there goes my entire water flow code; it's useless now.


 No.1009359

>>1009357

ok the problem was that I had to ignore the first few lines of the output because my smallest y was > than the location THE WATER STARTS FROM

>>1009358

there's none of that in my input. just one +. Or do you mean where the stream splits?

it's easy to just loop over every single character in the input and apply logic based on the next char down, with a 'contained' check that looks left and right for paths down.


 No.1009360

File: 8041b22eb77501c⋯.png (589.32 KB, 1408x4828, 352:1207, day17-ada.png)

Ada, 552ms without Draw.


 No.1009361

today's not so bad. it's not day 15.

today benefits from it being very easy to visually check your work.


 No.1009364

>loop over every single character in the input

I think that's what I was doing? (I can't read Ada)

I was just keeping track of the coordinates of the tail end of the water stream, and keeping a list of every split to return to once the current stream hits a dead end.

There's something wrong with my dead end checking though, it almost always works, but certain edge cases seem to break it. I'm currently trying to fix an error at the ~3000th tick.


 No.1009365

>>1009364

>can't read Ada

phwah, what. It's super readable. I've never written any code so readable.

what you want to do with dead ends is set things up so that on the next tick you'll raise the water level. What the Ada's doing is

<if I'm looking at a | ...

<is the next character down a # or ~ ?

<if so, and if | is 'contained', then draw a line of static water

<if so, and if | isn't 'contained', then overflow '|' to the left and right

meanwhile, the contained check is just: starting at a coord and going right/left, do I find a # before I find a . below


 No.1009366

>>1009365

'|' overflow is just one char.

the '~' line drawing I do all at once.


 No.1009374

>>1009365

>phwah, what. It's super readable. I've never written any code so readable.

Yeah, it is. My own code is many times uglier than yours, I'm just low IQ.

><if so, and if | is 'contained', then draw a line of static water

><if so, and if | isn't 'contained', then overflow '|' to the left and right

Ah. That would make a lot more sense. I just had a fill_water() function that did containment checking on it's own and decided which to draw. Stuffing everything into one function has caused quite literally all of my problems.

On the bright side, I've gotten fill_water() to work. Or at least, I thought I did. Had no errors, but answer is too high anyway.


 No.1009378

>>1009374

>answer is too high

remember to ignore water outside the min/max coordinates in your input. Especially the Y min.


 No.1009382

>ignore tiles with a y coordinate smaller than the smallest y coordinate in your scan data

>my answer was off by 4 the whole time

Allah fucking kill me.


 No.1009383

>>1009378

Yeah, thanks, I'm retarded holy shit

I'm failing part 2 though, my answer is apparently too low. Anything I should note? My part 2 answer is around 29292, and my part 1 is 35707


 No.1009388

>>1009383

Oh never mind, I'm beyond retarded, I accidentally removed my check for the minimum y, so I was >off by one


 No.1009389

>>1009383

draw your data and look at it. if you've got the wrong kind of water in a place, it should be pretty easy to see.

the y range is huge but the x range is small enough that you can view it in a terminal well enough, after shrinking the font


 No.1009425

File: 263615aa27d75c7⋯.png (110.61 KB, 2222x10423, 2222:10423, cave.png)

Pajeet would have loved my code today.


 No.1009427

>>1009322

>he still doesn't understand it

Are you literally retarded?




[Return][Go to top][Catalog][Nerve Center][Cancer][Post a Reply]
Delete Post [ ]
[]
[ / / / / / / / / / / / / / ] [ dir / agatha2 / animu / eris / hdi8 / sonyeon / vg / vietnam / voros ]