/tech/ - Technology and Computing

Technology, computing, and related topics (like anime)

Server and LynxChan upgrade done. Canary update and a general address soon. -r

Max message length: 6144

Drag files to upload or
click here to select them

Maximum 5 files / Maximum size: 20.00 MB

More

(used to delete files and postings)


Open file (36.33 KB 642x418 adventofshame2018.png)
Advent of Code is coming Anonymous 11/13/2019 (Wed) 01:06:13 No.698
https://adventofcode.com/2019/about
We're 20 days out, which is clearly not enough time for 8kun/tech/ to come back.
20 days out is also about as much preparation as you'd need to use Advent of Code to learn a new language. So:
1. are you competing this year?
2. what language(s) are you going to use?
3. where are you going to talk about the puzzles?
>>1052
>Got school sucking up all I've got.
You know that's a lie.
Start with days 1, 8 and 4. They're pretty much trivial if you know anything about programming. And once you've solved those, you can try the intcode days (2, 5, 7, 9) if you want to learn about machine code or try one of the upcoming puzzles.
Fucked up today's challenge. I didn't know of any good vector manipulation libraries to deal with either parts.

>>1052
School shouldn't stop you, especially if you have weekends free.
Although hitting the leaderboard will be mostly impossible, you should still be able to finish all the challenges day-by-day. Even 30 minutes of free time is usually enough to complete 1 AoC puzzle.
And hell, you have enough time to post here, no?
>>1057
>vector manipulation libraries
drugs are bad mkay
All you need is atan2 or phase to convert a pair of numbers to an angle. Actually you don't even need that, you can compare vectors directly.
Other than that it's just bruteforcing each asteroid. Or using some parameter space to quickly get asteroids along a line, like a Hough transform, but I'm not sure that's possible.
>process state value = ("produce state' ", "just get the current cell")
>input = mapAccumL process start output
>output = runMachine input
<*** Exception: <<loop>>
>output = runMachine (0:tail input)
<runs normally

Fuck me sideways. The head of input literally only depends on the initial state.
Today was F U N. When the problem asks you to think for yourself, suddenly the whole leaderboard is up for grabs.
I don't even know why I stored all states in a set when my answer is only valid assuming it first repeats the initial state.

Who's going to do all 500 trillion simulation steps? It should only take you a day or so on an optimized program.
>>1067
>Who's going to do all 500 trillion simulation steps?
4chan
The retardation is strong with me today. It took me only 2 hours to realize all you have to do is keep track of the pad and the ball while parsing every triple of the output, and send an input whenever you get a new ball position. There's still absolutely no reason to make a machine that returns control on input let alone make an interactive terminal program.
Had >fun with today's challenge once I figured out how the fuck the game's i/o worked.
>>1075
>let alone make an interactive terminal program.
I imagine most people did precisely that. How else would you even figure out what the running 'game' is?>>1075
>>1076
>How else would you even figure out what the running 'game' is?
I read the description. And I outputted the board a couple of times to check if I parsed it right and looked like breakout.
Open file (4.45 KB 261x78 still_not_11.png)
Finally
I was really scared that part 2 would change the reactions to allow for multiple paths (e.g. A+B->C, A+2B->2C, find optimal path...). Instead, part 2 was just as simple as part 1 + bruteforce binary search.
Open file (164.92 KB 1002x718 nkeoKb7.jpg)
>>1079
Congrats, now join our leaderboard >>801 :^)

I should've prepared better for graph problems. Now it was a shitfest of manual processing and copy-pasting intermediate results between languages, because of course >javascript doesn't have a quick&dirty graph library.
And I did the fucking binary search BY HAND. That should NEVER happen.
>see Day 15
>"heh, it's just BFS"
<tfw off-by-one
<tfw had the right answer for half-an-hour
<tfw would've solved it even faster if I'd copied last year's code
Today is probably one of the last chances I have at actually hitting leaderboard speed. A fucking shame, since I've not done as well as I did last year.
>>1085
>"heh, it's just BFS"
Yeah except for the fucking turtle.
I've just wasted an hour reverse engineering the machine because I'm starting to hate intcode puzzles.
>>1087
>muh intcode
lol
>The first seven digits of your initial input signal also represent the message offset.
>The first seven digits of your initial input
>initial input
>mfw


PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
14971 user 20 1024.7g 1.8g 3.7m R 390.1 5.6 55:25.35 day16

Also I feel like I should optimize it.
Although I wasn't fully filtered for today, my method's still highly sub-optimal: I just used a summed-array to bring down my run-time speed to a workable ~5 minutes.
>>1091
>55:25.35
<he only read the question statement 1 hour after finishing his shitcode
>Also I feel like I should optimize it.
wew. My solution doesn't look as bad now.
>>1092
><he only read the question statement 1 hour after finishing his shitcode
>assuming you didn't read the question correctly rather than having a bug in your code
And it made proper use of 4 cores, so it was running for only 15 minutes by that time.


Funny I realize only now that, because the offset is given and the matrix has such a neat shape, that should've given me a hint. It makes for a slight improvement over 70 minutes of CPU time:

$ time ./day16
real 0m0.463s
user 0m0.459s
sys 0m0.004s

Still, I'm happy with the nlogn algorithm that got me the star (it runs for about 2 minutes or 2 seconds if you keep i>=offset):

step() {
int total = 0;

for (int i = len; i--;) {
total += state[i];
sum[i] = total;
}

for (int i = 1; i <= len; i++) {
total = 0;
for (int j = 1; j*i <= len; j++) {
total += ((j%4) < 2 ? 1 : -1) * sum[j*i-1];
}
state[i-1] = abs(total%10);
}
}
Today was tedious and had literally no programming.
I counted the intersections by hand and I constructed the path by hand, even making branches at every intersection, which turned out to be completely wasted effort.
Now I really want to make a big boy with straight pieces split across functions and turns at intersections. Because that does require programming.
>>1101
Your bigboy is fucking bugged.

..............#######....................
..............#.....#....................
..............#.#######..................
..............#.#...#.#..................
..............#########..................
..............#.....#....................
..............#.#########................
..............#.#.....#.#................
..............#.#.....#.#................
..............#.#.....#.#................
..............###...#####................
................#...#.#..................
..............########?..................
..............#.#...#.#..................
............#########.#..................
............#.#.#.#.#.#..................
............#.###########................
............#.#...#.#...#................
............#########...#................
..............#...#.....#................
..........####^######...#................
..........#...#...#.#...#................
..........#...#####.#...#................
..........#.......#.#...#................
..........#########.#####................

There are two possible direction I can take at the '?'.
????
>>1103
>There are two possible direction I can take at the '?'.
>the absolute state of namefags
Yes. Now activate your head spaghetti to conclude that you have to traverse at least one of those scaffolds more than once.

The only sense in which it's "bugged" is that 3-way intersections are not explicitly stated in part one where they matter, but no one cares about part one.

I forgot to give solutions to >>1101 by the way:
md5sum of a valid input: b72a21be600c0ab2f43b4c17530fff95
md5sum of the output: 31e3c1625c87b911f8fc377fb2b0857c
>>1104
No, m8. 3-way intersections are not part of the puzzle specification.
>>1106
Sure they are faggot.
>>1108
same place it specifies corners.
>>1109
>ctrl + f corner
>Phrase not found
Ok, retard. How about you provide a quotation?
>>1106
There are no 3-way intersections and the robot never takes a turn at an intersection and it never follows the same segment twice in the examples and inputs, but nowhere does it say these things are disallowed.
If you can't handle the bigboy, that's fine, but stop crying that it's somehow wrong.

Be glad I didn't put L,L or R,R in the path. That resulted in eldritch abominations like
#########........
#.....#.#........
#########........
......#.#........
#########........
#.#.#.#.#........
#.#.#.#.#.#.#....
#.#.#.#.#.#.#....
#################
#.#.#.....#.#....
#.#.#########....
#.#.#.....#.#....
^#######?####....

Nevermind the three tentacles, those are comparatively easy to deal with, but at some point the robot stops at the ? and turns around. In the middle of a segment. Good luck finding that out.
>>1113
>hurr durr the puzzle description doesn't say that it isn't allowed
>that means that it could happen even though in the entirety of AoC this was never the case
I'm not crying, I'm just telling you that you're bigboy input doesn't follow the specification.
Today was easy, but I'm not very proud of my O(x) solution of following the 2 edges of the tractor beam.
Or actually, I don't feel proud because I'm still filtered by yesterday. After BFS failed, I was convinced to learn how to reinvent Dijkstra, but my solution isn't running fast enough.
>>1134
BFS does work.
>>1134
It was a good idea to take a break yesterday, given how few people have solved it. Guess I'll do it tonight or during the weekend.

>>1136
Thanks, I'll keep that in mind.
>THREE HOURS I just HAD to hardcode the area that has inner portals and the maximum depth and forget to change them when switching between test input and real input. Also I had an off-by-one for part 2 for some reason.
Today's part 1 was a copy-paste because of what I did in >>1134. Haven't done part 2 yet; Dickstra runs out of memory despite working swiftly on the test input. >>1136 I don't get how. My BFS for day 18 creates a new "state" (i.e. starts a concurrent BFS from the key, forgetting the tiles it's been to for backtracking) for every key it finds, and that quickly balloons to a million items in the queue. Same thing happens if I take each key as an edge and run BFS With Priority Queue. In-between the two, I also tried a recursive DFS to see if I'd luck out in finding an optimal minima at the start. It unsurprisingly failed. I'll be re-looking the problem eventually, but I'll remain >filtered till then.
>>1139 I don't know if your approach is correct but yes it get's huge. Takes like 3 mins for mine to run.
>>1113 ah nice the code-tag double spacing is finally fixed.
Compared to Day 17, this was a cakewalk. --------Part 2-------- Day Time Rank Score 21 00:35:56 119 0 My rank is surprisingly high up for the brainlet solution I made, which boiled down to Trial and Error with Pen and Paper
>>1145 >tfw you think the jump bot cycles through the instructions executing ONE instruction per step, so you have to blindly try loads of instruction combinations I haven't even checked, but do the registers start at 0 every step? I just assume they keep their values. With part 2 I was struggling with how to flatten the tree of conditions so I could just NOT, OR and AND the temp register all the way through, totally ignoring that the jump register can be used at any point. By the way, day 17 part 1 is a cakewalk too and part 2 is pretty easy when you assume that the problem is easy. The robot never turns at an intersection, so there's only a single path [spoiler]that you can trace by hand and then put in any editor that highlights selections to quickly find the functions[/spoiler]
>>1146 >can't even nest spoilers lynxchan a shit
>>1146 >I haven't even checked, but do the registers start at 0 every step? I think they do. I proved it on my end by trying RUN ................. ................. ................. #####@########### ^ crashes here and NOT A T OR T J RUN ................. ................. @................ #####..#.######## ^ bot does not repeatedly jump v ................. ................. .@............... #####..#.######## The 2nd one is equivalent to T = !A; J |= T; RUN; If J retained its value, the bot would continuously jump after it meets its first empty hole, because (true |= bool) == 1. Instead, the bot stops jumping after the first jump (at the hole from the first RUN), which means that J was reset at some point. >spoiler I eyeballed the thing manually with Pen&Paper. Text selection would've been extremely helpful.
>what is the position of card 2019 >position of >not "which card is at position 2019" fuck my reading comprehension
Reversing the shuffle operation for 2020 was simple enough, but how do you compute that 101741582076661 times in a row? I'm at about a couple million iterations right now, but every card position thus far has been unique.
Does anyone have a proof of the period of an iterated polynomial in a field? I know x+b (b>0) has period p and a*x (a>0,x>1 or a>1,x>0) has period p-1, but for a*x+b I could only assume that it has period p or, in the end, p-1 because I was off by one. ...Which makes sense because when a>1 there's exactly one identity e=ae+b --> b=e(1-a) --> e=b/(1-a)=b*c for any b because every non-zero element (1-a) has a unique inverse. >>1154 Same. It would've actually been better if he did ask for position 2019, because now part 1 is just a trivial case of part 2. Today is definitely big brain time, unless you cheat yourself and look up the algorithms. I know my finite fields and still it took 4 hours to get the right answer. That includes lots of off-by-one errors and I-have-no-fucking-clue-because-it's-all-opaque-numbers errors. I highly recommend you keep printing the output of part 1 using your part 1 algorithm AND using your part 2 algorithm the whole time. >>1155 Protip 1: you get back to the original deck after 119315717514046 shuffles, so why shuffle backwards a lot when you can shuffle forwards slighty less? Protip 2: write the shuffle operations as functions from the old position to the new position, e.g. restacking is new = -old-1 (mod length). 2.1: When your shuffle operations all look like new=a*old+b you can compose them and turn all the operations in your input into a single one, e.g. r=p+7, s=3*r+0 --> s=3*(p+7)+0=3*p+21.2.2: Put differently, cut -7 turns any [a,b] into [a,b+7] and restacking turns [a,b] into [-a,-1-b], with [a,b] starting at [1,0] because no operation must mean p=1*p+0 of course. Protip 3: Find a shortcut for applying a linear function a trillion times. :^)
>>1156 >Does anyone have a proof of the period of an iterated polynomial in a field? This sounds very similar to the wanting to know the period of a LCG. This is only for polynomials of degree 1 though. https://en.wikipedia.org/wiki/Linear_congruential_generator#Period_length
>>1157 Fuck, how could I forget about LCGs? Unfortunately it's just as hard to find anything about LCGs with m prime and c>0.
>>1156 >a*x (a>0,x>1 or a>1,x>0) has period p-1 Fuck, there are only totient(n-1) primitive elements in a field, like 2^k only cycles through 1->2->4->1 in GF(7). So I'm lucky totient(119315717514046)=59657858757022 means a >50% chance of 2020 being primitive. Not that it really matters, because any cycle length has to divide 119315717514046, so worst case I'm just going through a small cycle a couple of times too many.
7 hours remaining. You better have completed all of days 1-24 or you're not getting your last star tomorrow!
10 more minutes, and I'll be free from this LARPfest
>Unrecognized command My intcode machine is fucking broken.
Do you really solve day 18 with dumb BFS on the grid? I feel like there should be an elegant solution involving graph transformations or straight up linear programming, but I'm just too brainlet to see it.
>>1180 >dumb BFS At the very least, you can preprocess the grid and add a few heuristics to get a pseudo-A* running far faster than plain BFS. There shouldn't be a faster solution than that, since the problem statement boils down to a modified Traveling Salesman.

Report/Delete/Moderation Forms
Delete
Report