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:
Friendly reminder that if you don't produce the output in under a second you haven't finished the challenge.
Leo Miller
but user, an hour is 3600 seconds you could've learned summed-area tables, implement the solution in 5 different languages, masturbate, fall asleep, get a gf and walk 500 miles before that program was done
Chase Hernandez
Under 100ms, more like. Doable even in Python using as long as you don't abuse bloated, slow structures like dicts that people love using for some reason.
Juan Diaz
Or not used Python and brute forced it in C instead which would complete in under a minute anyway.
Blake Gomez
my memory is a bit fuzzy, but you should be able to fetch the newest commit, then either merge with or reset to that commit, and then commit and push your changes
Connor Cruz
>no convoluted input parsing >easy logic allowing a brute force solution even for brainlets (provided you're not using Python) >trivial but brilliant two-part algorithm that coexists with your existing brute-force code allows you to educate yourself and learn something afterwards I wish all problems were like this.
Cameron Martinez
I did. At least the masturbate part. But I just wanted to see how long it took for my first version to run.
main :: IO () main = do let xvs = yield 8141 let (keys, value) = findMax xvs [3] let (keys', value') = findMax xvs [1..300] putStrLn$ "Silver: " ++ show keys ++ " with " ++ show value putStrLn$ "Gold: " ++ show keys' ++ " with " ++ show value'
areaSum :: Points -> Int -> [Int] -> Int areaSum xvs i [x,y] = sum [(if u == v then id else negate) $ Map.findWithDefault 0 (x+u,y+v) xvs | v Points -> [Int] -> Points apply grid xvs [x,y] = Map.insert (x,y) value xvs where value = point + get (x-1, y) + get (x, y-1) - get (x-1, y-1) point = digit $ (10 + x) * (grid + (x + 10) * y) get k = Map.findWithDefault 0 k xvs digit n = mod (div n 100) 10 - 5
def gen_grid(size, num): return [[power_level(x+1,y+1,num) for x in range(size)] for y in range(size)]
def find_max3(grid): maximum = 0 pos = None for y in range(len(grid) - 2): for x in range(len(grid) - 2): s = 0 for r in range(3): for c in range(3): s += grid[y+r][x+c] if s > maximum: maximum = s pos = (x+1,y+1) return pos
def find_max(grid): maximum = 0 pos = None for y in range(len(grid)): for x in range(len(grid)): s = 0 for size in range(1, len(grid) + 1 - max(x,y)): for coord in range(size-1): s += grid[y+coord][x+size-1] + grid[y+size-1][x+coord] s += grid[y+size-1][x+size-1] if s > maximum: maximum = s pos = (x+1,y+1,size) return pos
time was with those 2 big asserts, so 3 times as big
Tyler Davis
Why does GHC depend on BSD cancer? I don't want 600MiB of BSD bloat pollution my disk and pure GNU system just so I can compile Haskell. What a horrid language - at least post your runtime.
Because i solved the first part, failed to figure out why the right answer fails and peeked at the other solutions. i know i have the right answer, just not why it fails.
why don't you tell us what you think the first answer should be?
Jackson Perez
Why is the thread moving so slowly lately? Have the brainlets really given up because they failed to solve one of the problems?
Elijah Baker
Post code. I read on SO that the summed-table algorithm isn't vectorizable, shows how retarded I am believing some random unsubstantiated post
Brody Robinson
Different user here Ill be back home in a bit but I have a simd enabled version of day 11 using a derived integration of the power level function. Implemented up to AVX2 on my skylake Stay tuned
the code's right there m8, or do you want to run it yourself? I think you can't vectorize building the table, since every element depends on the elements immediately before it but for finding the biggest square it works
Lucas Rogers
correction: you can vectorize the table building partially, but not entirely. i tried it and it didn't net me any noticeable speedup
Tyler Brown
>tfw looking at GeeksforGeeks for algos instead of coming up with them Is this wrong?
What algorithm are you looking up anyway? Most of this is entry level highschool math applied o puzzles except maybe if the golden ratio is involved fuck if I'll ever understand how that even happens
Josiah Phillips
It just means you have to use a data structure with a good enough O() that it'll be done before the heat death of the universe.
Nathaniel Sanders
Just today's problem. I wanted to get an efficient solution for it and I sure as hell wasn't going to find it myself
Only other one I had some issue with was the marble one.
Carter Nguyen
You really just need to search this thread and the last one.
Matthew Rivera
where's your intermediate truncation? so that e.g. values of 560 and 690 become a powerlevel of 5-5+6-5 = 1 and not 5.6-5+6.9-5 = 2.x
Isaac Parker
I figured each iteration would take about the same time, and it's memory that's troublesome. Here's hoping I don't melt my SSD like that other guy.
That's just a quick wolfram alpha I wrote up on my phone without putting floor()everywhere. The continuous versions should work fine for the discrete integer math up until some functions I believe. Also I use the floor definition of the modulo function to allow it to be integrated and vectorized easier in case I have to use intermediate floats when porting it to SIMD code. Unless I'm dumb and doing something terribly wrong but it should still work even with truncated integer arithmetic without me having to type floor() everywhere on wolfram Should be able to at least verify it with the original serial method if you implement it plainly with c1 and c0 being (0,0) and do the modulo 10 and - 5 with what I have there. Again, I'll type up more once I get home
>do you want to run it yourself? Yeah, I'd like to compare against my own implementation. My code has 3 instances of automatic loop vectorization on -03, so I'd like to learn how far you can go just by relying on the compiler to do its job provided you help make code vectorizable - there is a lot of missed vectorization, so I'm wondering when, if ever, is it worthwhile to address that and get a payoff without having to manually vectorize. >college math Jow Forums told me you only needed arithmetic to program
Owen Roberts
pastebin.com/3LDcvjCL change the #defines SER_ID, GSIZE and VECSIZE for serial id, grid size and simd vector size respectively can I have a look at your code as well?
James Wright
Still took 4 seconds in cpython with a summed area table and a list. Would probably be faster with a numpy array but I enjoy just using built-ins.
You just gave me a great idea for mine. Since 23 items are removed from the front of the queue and 7 items added back every 23 cycles, once the queue has more than (cycles_left / 23) * 16 + 23 marbles in it, I can stop adding marbles to the back since it will never get to them. Long story short, the code is twice as fast now and I can finally calculate a 4 billion marble game. Thanks.
please tell me that python variables/arrays are stored in ram and I didn't just spend an hour and a half yesterday killing my ssd
Nicholas Walker
Python data structures are stored in memory. Memory can get swapped out.
Luke Stewart
>powershell
Joseph Wright
Powershell best shell.
Gavin Wilson
Probably doesn't look as disgusting as my solution function f2 (players, last) { let target = { val: 0 } target.next = target target.prev = target let scores = Array(players).fill(0) console.time(last) for (let i = 1; i
A sliding window approach is three times faster than using a summed-area table for my Python solution. Just something to keep in mind if you want to rice your implementation.
Justin Fisher
what about korn?
Jayden Flores
When will aoc have a problem that requires a complicated algorithm instead of allowing you to cheese it? So far only the bigboys have forced me to really activate the synapses.
Elijah Richardson
dead thread
Colton Kelly
k not sure what I'm doing wrong here...finding the max in a 3x3 square takes miliseconds but finding the max in a 100x100 square square takes forever.
Logan White
Fuck, I think I might not be able to be up tonight, I'm fuckin' swamped, and need to actually be on time tomorrow morning.
summed table algorithm
Charles Diaz
is the answer for day 10 supposed to be backwards or I am doing something (horribly) wrong?
there are 3*3*(301-3)*(301-3) = 8e5 samples for the 3*3 squares, but 100*100*(301-100)*(301-100) = 4e8 samples for 100*100 squares, so it's not weird if your unoptimized solution is 1000x as slow for that single size. If it's even slower than that, you might have an iterator or range problem.
Brody Richardson
dead thread is Jow Forums giving up on aoc?
Daniel Morales
Ah thanks. Math checks out. I figured since the box was larger it would be easier to find the placement that gives the largest sum. Got my star in about 15 minutes. Too arsed to optimize.
Joshua Cox
brainlets are getting filtered and they were the main source of content
Christopher Gray
I feel like it depends on the challenge and time of day and such. It's the beginning of the week and I'm sure a lot of people got home to see a really math heavy and overall uninteresting challenge. It was nothing beyond "follow these steps to generate a matrix and now find the submatrix with the highest sum".
Weekend threads and days with interesting or funny challenges usually get more action. Those are the ones you see people making and posting memes about.
Jace Reyes
Staying up late to do these as they're released is starting to get old. Last 4 have all been easy problems where I've blown tons of time screwing up secondary shit. It's past time for me to start going to sleep on time again and doing these when I'm rested.
>matrix based and redpilled >grid cringe and probably a tranny
Brandon Collins
same desu if i didn't have work i'd stay up
Austin Morris
Would /ourguy/ kindly prove that he's our guy by posting his input* and output immediately after getting the stars?
*It's fine to post the input a bit later considering it's probably too big and uploading it somewhere takes precious proof seconds. And it's usually much harder to generate an input for a certain output than the other way around.
Kevin Thomas
seconding this
Most people either got filtered or found out after two days that they aren't interested in doing this for a whole month.
Joseph Harris
he doesn't need to prove anything to anyone.
Benjamin Young
>h-he doesn't need to prove himself! I-I believe in him anyway go cry me a river faggot
Lincoln Thomas
There's no way this is true. I'm 22 stars and a mega brainlet programlet. The filter has yet to come.
Brandon Collins
What exactly do you want proof of? Are you worried that I'm merely pretending to be -354? Because I've been posting working code within 5-10 mins of finishing every night this year, and I'm pretty sure a few of those went up before anyone else on the Jow Forumsderboard had a second star yet