Previous Thread adventofcode.com/ >Advent of Code is a series of small programming puzzles for a variety of skill levels. They are self-contained and are just as appropriate for an expert who wants to stay sharp as they are for a beginner who is just learning to code. Each puzzle calls upon different skills and has two parts that build on a theme. You need to register with an account but you can appear as anonymous.
Private leaderboard join code:
368748-e33dcae3
People who are inactive for 5 days will be kicked, but other leaderboards can be made if desired.
Alternative leaderboard for those waiting for inactives to be kicked from the first:
>Go back to my day 17 solution to see if I can optimize it from the current 30s it takes >Actually find some more edge cases and now it takes 70 seconds Fucking hell
Adam Nguyen
can someone test out my input for part 1? pastebin.com/9QmEnidy I get "free, tree, yard" for each elapsed minute 1298 750 452 1076 1005 419 884 1171 445 736 1285 479 648 1325 527 603 1318 579 640 1226 634 713 1091 696 885 954 661 1084 803 613
Ian Russell
Post your biggest brainlet moments this year.
>spend a long time on day 9 part 2 trying to find some perfect marble state because I didn't think there was anything wrong with constantly resizing multi-megabyte arrays in Python >completely skipping over minecart movement rules and also somehow forgetting that you can hit carts which already moved on a tick >absolutely shitting myself on day 17, as in like a fully workday and then some (I thought it was harder than 15 in terms of grasping what you needed to do), in part because I got into trying to do a "pure" solution that couldn't handle certain cases
Day 13, my carts kept on overwriting the tracks with their direction characters because I didn't understand python references until a few days later. Ended up writing the same algorithm in C++ that day and finished at around 4hours instead of 15minutes.
Adam Turner
On day 8, where you get a recursive definition of a tree, how do I actually parse it into a tree? The solution I've seen just don't bother making a tree, which is fine. But I don't like being too dumb to make a simple recursive function.
Joshua Hernandez
aaahhh fuck my surronding check is wrapping around the other side of the array
Sebastian Allen
Recursive simply means calling yourself to perform the same function again.
William Sanders
>tfw someone else made the same visualization already
>12949 frames/s Try swapping between 2 buffers. Make sure to break out of your check early if it succeeds. It's probably faster to check all 9 squares than to special case the test square. You only have to modify your lumbermill test and require 2 instead of 1 If you surround the active area with '.', you don't have to check for grid edges
Or you can figure out how to not literally iterate a billion times
Seven more days. Seven more days and I can go back to sleeping 40 minutes longer and then using the other 30 minutes to fap in bed.
Brayden Perez
That number was taken on a 1.60GHz CPU. I don't have much better available at this moment.
>Try swapping between 2 buffers. memcpy is done once per loop and takes a tiny-ass fraction of the time (memcpy is really fast, and the buffer is pitiably small). You'll have to make sure both buffers match at the end of each iteration anyway.
>Make sure to break out of your check early if it succeeds. The time it takes to compare the tallies while looping is more than simply letting it run out the loop of 8 iterations [spoiler]also the compiler can unroll it[/spoiler].
>If you surround the active area with '.', you don't have to check for grid edges Same with this, I really doubt that'll be noticeably faster. Maybe it'll save me 10 mins in the "grand scheme of things" but that doesn't mean much for 21 hours.
>It's probably faster to check all 9 squares than to special case the test square. You only have to modify your lumbermill test and require 2 instead of 1 This is probably what'd save the most but I have no clue how I'd do that...
I'll probably just try to visually figure out where the animation starts looping and calculate the nearest frame that should have the same state as frame 1000000000.
Thomas Martinez
(Me) Now that I think about it, maybe a checksum of each frame would let me figure out when it starts looping...
Zachary Ward
it's what I did, store the number of wood and lumber tiles along with a hash of the grid, when you see a hash for the second time you got a loop
Brandon Butler
Really underwhelming so far, lets be honest.
Cameron Lewis
kek mine is the same
im still doing the elf battle thing though, eventually
David Wright
i just put the whole thing inside a dict in python and wait for duplicates to show up.
Matthew Anderson
why did I write such a convoluted mess of a code? It isn't even efficient...
>day17, ignored the minY statement, spent 2h debugging non existing bug. this one hit a lot of people, myself included
Justin Thomas
Didn't know what a linked list was and made a shitty slow solution once
Luke Turner
>Python It's easy to code in, but difficult to make it look nice
Jaxson Gutierrez
day18 code
Especially "proud" of my brainlet-tier part 2. I originally did the modulo thing but got the wrong answer. I figured I had gotten the math wrong somehow, so I replaced it with these stupid loops since I figured that would be impossible to fuck up. Then I got the same wrong answer again, because the problem was never with the modulo, it was an off-by-one in the cycle check.
I solved it in excel. Printed 100k lines to a file, found the cycle with ctrl+f and just did it manually pretty sure this method could be used by anyone to do part 2 in under a minute
Chase Jenkins
>tfw inexperienced/brainlet so implemented day 9 (the marble game) with an array >O(n) deletions instead of O(1) with linked lists >part 2 with the *100 turns is taking 30 minutes so far on naive python implementation >too lazy to terminate it and reimplement
Alright, I seem to have gotten it. Thanks for the tips.
pastebin.com/raw/2gnz3ijr $ time ./main 1000000000 Loop starting frame: 417 (length 28) Resource value: 169234 ./main 1000000000 0,05s user 0,00s system 95% cpu 0,054 total
Noah Lopez
I saw you got some points over SP today, congrats!
Gavin Collins
I forgot, you also have to set FREETYPE_PROPERTIES=truetype:interpreter-version=35
in the environment, because a freetype update a year or two ago fucked up the rendering and made it look shitty. Also you need to set the freetype hinting mode to "full" due to the other freetype update a year before that.
the calendar should stay bare cuz it's already a grid
Owen Garcia
Alright I implemented my loop checker for part two. Wish me luck anons.
Nathaniel Johnson
It seems like too many people got filtered after day 10. There isn't any good content of note in the threads anymore, let alone activity. We're reaching dead days.
William Thomas
Well forty minutes later and still no result so that's fun.
i implemented a hashset. now it detectes the cycle. how do i calculate which step is the last step?
Grayson Jenkins
Yeah I thought so I just left it running while I ate thinking it would finish a while ago.
Christopher Bell
Love me some numpy.
import numpy as np
with open("I:\\2018d18.txt") as f: arr = 1 + np.char.index('.|#', [list(line.strip()) for line in f])
def tick(arr): ear = np.pad(arr, 1, 'constant') amt = np.equal.outer(np.dstack([ear[i:i-2 or None, j:j-2 or None] for i in range(3) for j in range(3)]), np.arange(1, 4)).sum(-2) msk = arr < 3 np.copyto(arr, np.where(np.take_along_axis(amt, arr[..., np.newaxis] % 3, -1).squeeze() >= 3, arr + 1, arr), where=msk) np.copyto(arr, np.where((amt[..., 2] >= 2) & (amt[..., 1] >= 1), 3, 1), where=~msk) return arr
def findcyc(func, start): pow2 = 1 cyl = 1
lastp2 = start.copy() fast = func(start.copy())
while (lastp2 != fast).any(): if pow2 == cyl: lastp2 = fast.copy() pow2
Ryan James
Let's say that at step b you find a grid that you already saw at step a For me, a = 550 and b = 578
So the program is going to run up to step a, then enter the cycle Basically, you have: 1000000000 = a + (b-a)*number_of_cycles + left_over
You can compute the left_over with a simple modulo: left_over = (1000000000 - a) % (b-a)
You want the state of the grid after all the iterations, so you can pass over all the cycles and just compute left_over iterations
Elijah Campbell
>hardcoding your input file >not reading from stdin always, which is more extensible in that it allows you to paste in test input or redirect from file
James Thomas
hardcoding the filepath is superior for this it's something you can do before the challenge is open and it's one less thing you need to do to run your program
Levi Brooks
Or you can just redirect your input file to stdin with the benefits I listed. It's just $ myprog < input_file
Angel White
Day 15 really needs that "The hard problems haven't started yet" quote from the creator
Just wait until the maximum vertical distance between the dots is small enough, and only start rendering then. I checked for a vertical distance of 200 and got 15 frames rendered, one of which had the message.
Brandon Campbell
Since the input converges to a minimum only once before it begins to diverge once again, you can keep track of a box of corners representing your minimum and highest points respectively, and once the current box is bigger than the previous box (the answer), you can just print out the range of the previous, smallest box. The only downside to this is you have to find the new corners each iteration, but it finds the correct answer instead of the hacky way of visual inspection.
I've checked last year's leaderboard and only 30 people had both stars on day 18 (and less onwards), while this year 38 of us already has 36 stars. The problem might be that everyone seems to be doing a different challenge, and I've seen more post about day15 than the current problem. Last year these threads were also dying at day 22-23, and that's natural considering the increasing difficulty.
>ded thread the problem is there's not really much to talk about today but i'll try anyway - since today was so similar to conway's game of life, does anyone knows of or have experience with optimizing things like this? I did just the straightforward scanning every tile thing and it werked, but I know people are crazy about finding efficient algos for conways for big and long simulations and for finding specific patterns
Landon Ortiz
try using two arrays that are swapped each iteration instead of needlessly copying the entire grid every time
Nolan Myers
this You can use an array of size two and just use modulo to swap between them.
Juan Gutierrez
I've had a quick look at hashlife, which is usually used to do the big conway simulations. as far as i can tell it also uses the recurring patterns to speed things up, basically what we did today, but I think it can be more fine grained about it, ie if you get different regions oscillating at different periods it can deal with that and so on
Gavin Lopez
you can also extend the array by one each side to avoid unnecessary bound checks
Brandon Adams
nice
Anthony Sanders
what can we expect up next?
Cooper Parker
binary trees
Daniel Myers
Keep in mind that there was only one thread per day last year, the threads are still just as active as last year. Unfortunately, the puzzles generally have less to say about them, and as said, progress on them has become more fragmented as people skip or delay doing them, only catching up now (I myself am about to start 16, and have done all in order).
While I haven't done any real optimization on it, when there was an attempt to bring back regular themed programming challenges last year, I made an infinitely expanding game of life implementation. Since it's performance is so shit (written in python, too), I was going to implement hash-based acceleration without even realizing that what I was going to make was similar to hashlife. As is, it has basic functionality of drawing, saving (compressed), loading, and reverting generations. Webm very related.
Could you post your function? Have been trying to debug mine for at least an hour now
Carson Carter
My approach was just to print an array of stars whenever they're all within a certain X and Y distance, and leaving it to the user to check that it forms letters. It's a hacky solution and the X and Y bounds were hard-coded, but it worked and I'm not implementing fully automated text reading for this.
More like day 9, 10's only hard if you're trying to do some quasi-computer vision shit. Mostly I'm surprised at how wild the difficulty swings are this year.
Brandon Torres
2016 day 11 wasn't that much better. To compare to last year, 2017 days 10 and 11 were considered filters, and day 16 was classically "hard" (permutation groups).
Matthew Cook
Started a bit late, and I'm working on day 3 in C++.
Why does this not populate my vector correctly at all? I only get a bunch of duplicate IDs, and everything else is garbage
Adam Wilson
Thanks. I think I'm just going to accept that I got filtered on this one. My python code just inexplicably stops bothering once it gets to about y=200
Mason Fisher
use getline(cin, input) instead. also, its always a good idea to print out the input string when debugging. pretty sure that only places a single word into the string.
Lincoln Brooks
Holy shit you're right and now I feel retarded. thanks based user