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:
Is the second leader boars broken or am I banned from it somehow
Chase Long
>write part 1 as a line by line summation to save memory in case they make part2 doing a much further target >turns out I need to calculate the full grid anyway for part 2 >just a basic shortest path algorithm >should I just write a simple dijkstra's algo or use this shiny networkx graph library I found out about back on day 7 or so >shiny graph library ftw >oh shit, I need to make my graph huge to account for all the possible paths outside the target range >start adding extra manually >for some reason library is giving longer shortest paths as I add more area to check >can't use pypy3 because I just installed that recently and have no idea how to add custom modules to it >finally give up and write simple dijkstra myself after wasting a solid hour >now I can just add the neighboring paths as I visit nodes instead of pre-filling a huge array and it runs ridiculously fast >gives me the right answer on the first try >probably was a way to do this in the shiny library, but fuck if I know how
Dominic Reyes
I literally didn't implement A* once and now i'm screwed
Caleb James
OH lawd, now he fucked up again... The fastest route might involve entering regions beyond the X or Y coordinate of the target.
my input is depth: 9465 target: 13,704
my if I extend the grid to (20,800) I get the "correct" result of 944. but if i extend my grid to (200,900) I get a shorter path of length 942. WTF can anyone please confirm this?
Ryan Cooper
I get 944
Carson Bailey
you do not need any fancy A* shit (though it helps with runtime) simple dijkstra is good enough. your nodes are the product of coordinates and valid tool choices and your edges are 1 or 8 depending on if you need a tool change between nodes. for python networkx (fucking inefficient) does this in 10 seconds runtime.
William Phillips
I get 944 for that input. I extend to (2000, 2000).
Jack Collins
Did I fuck up my A* if it's taking over 5 minutes to run and my TYPE computer is memoized?
Matthew Young
I was keeping track of closed_set in array, so my "Has this node been visited already?" checks got slower and slower.. oops.
Liam Murphy
I still cannot find an error in the path of weight 942 it seems legit. from functools import lru_cache TAR=(13,704) DEPTH=9465 M=20183 #%% @lru_cache(maxsize=10**8) def f(x,y): if (x,y) in [TAR,(0,0)]: return 0 if y==0: return (x*16807) %M if x==0: return (y*48271) %M return (g(x-1,y)*g(x,y-1))%M
Ah, I see. I'm surprised that only saves 2 minutes.
Ian Peterson
>think "heh, that's easy" (minus goofing up and debugging runtime before finally putting in memoization) >part 2 FUCK. I've been filtered on half of the problems now, just terrible
you cannot know that. Instead you just have nodes for all valid combinations and edges for all valid transitions. so nodes are (x,y,tool) e.g. (0,0,torch). and edges are weighted and go from (x1,y1,tool1) to (x2,y2,tool2) e.g. (0,0,torch) to (0,1,climbing-gear) has weight 8 and (0,0,torch) to (0,1,torch) has weight 1. you have to be careful about what edges are actually allowed and there are cases where you can only travel across an edge in one direction (this is where I messed up ) So you need a directed graph. then it's only the case of finding the shortest path from (0,0,torch) to (target_x,target_y,torch)
Ryder Gray
Thanks. I think I can just treat this as if I have "both" tool options available to me when I can choose, and then choose the better one for each node I'm looking at.
Levi Moore
what happens if 2 edges are equally good? for example current is (0, 0, torch). (0, 1, torch) and (1, 0, torch) are both valid moves.
Gavin Murphy
you could also make an undirected graph where you can either go from (x,y,tool1) to (x,y,tool2) for 7; or from (x1,y1,tool) to (x2,y2,tool) for 1 imo that's a bit simpler because you're not moving and changing gear at the same time
Nathaniel Smith
you cannot know which piece is better at the moment the edge is treated, since it also depends on where you will move in the future. is maybe more intuitive, but you have to treat the tool as an extra dimension in your nodes.
Joshua Morris
maybe I missunderstood. how to treat nodes of equal distance is not related to the problem, but to graph algorithms in general. you should look up the dijkstra-algorithm for example
Luis Jenkins
I ended up using a bloomfilter It takes about a minute to solve both parts, using the verilator simulator
Nathaniel Lee
Made something that works for the test input, but takes forever on the actual input. Let's see how long this takes.
Adam Ramirez
>part 2 >correct answer on test input >off by 14 on real input Every. Time.
Dominic Harris
>Scrape through with something that took far to long to run and caused a stack overflow first attempt. I may get filtered some day, but today is not that day.
what I do not understand is why so many people had trouble with part2. It is the first time I could actually use library graph-algorithms and didn't have to re-implement some kind of BFS. Is the abstraction to view the tools as part of the state and therefore encode them in the nodes really that groundbreaking?
Asher Evans
I want to do A* on a three dimentional graph, but I dont have enough battery left.
Blake Morris
>coding on a phone
Angel Mitchell
I'm in my second year of CS and have yet to find a reason to use a computer. If they allowed phones during exams, I wouldn't even use a graphing calculator. Times are a-changing, grandpa.
Samuel Bailey
Implying he is not a coding-cyborg, whose batteries are about to run out.
def geo_index(x,y): if (x,y) in ((0,0), target): return 0 elif x == 0: return 48271 * y elif y == 0: return 16807 * x else: return erosion(x-1,y) * erosion(x,y-1)
yield sum(rock_type(x,y) for x,y in product(*[range(v+1) for v in target]))
init = ((0,0),1) states_at_time = defaultdict(set, { 0: {init} }) time_of_states = {init: 0} for t in count(): if (target, 1) in states_at_time[t]: yield t break for pos, tool in states_at_time[t]: changed_states = [] #change tool for tool_ in set(range(3)) - {tool, rock_type(*pos)}: changed_states.append( ((pos, tool_), t+7) ) #change position x,y = pos for x_,y_ in (x-1,y),(x+1,y),(x,y-1),(x,y+1): if x_ < 0 or y_ < 0: continue if tool != rock_type(x_,y_): pos_ = (x_,y_) changed_states.append( ((pos_, tool), t+1) )
for state, t_ in changed_states: if state in time_of_states: _t_ = time_of_states[state] if t_ >= _t_: continue states_at_time[_t_].remove(state) states_at_time[t_].add(state) time_of_states[state] = t_
with open('test_cases/22.txt') as file: print(tuple(AOC22(file)))
Andrew Nelson
over 4MB edition regarding the image limit, there are a few solutions: a) going into lossy even further (i think with this 256 color limit, it already looks ugly enough) b) split it into two 10000x5000 images, since only the lower one will be updated anyways (thats what I did for now, and reassembling shouldn't be hard, but this way it looks less cohesive now) c) host it somewhere else (if there are reliable hosts)
Did you write your own astar code or is it from a package?
Jonathan Barnes
I'm medium-brain on day 22 but I need to learn to do small-brain A*
Aaron Torres
he probably wrote it for the previous years and keeps it in a module to call if needed
Robert Adams
A reference to day 16 and 19 for day 21 is needed
Bentley Thompson
I doubt it would make a huge difference, but day 6 has quite a lot of dithering when it doesn't need to. I thought the size might be a problem when I first saw the template resolution, probably should be smaller next year. I would suggest optimizing the lossy compression where possible (such as day 6), or if absolutely necessary, downscaling the image slightly (not enough to make text unreadable though). I don't think it's very good to either host it elsewhere or split it, since it makes it much more of a pain to post/view, especially in threads after this year's AoC ends.
James Lopez
imho just cut the resolution, when the memeographers see that their 6 million screencaps can't be legible at a reasonable filesize then they'll change their ways
Ian Johnson
it should just be a page layout on some site with the image for each individual day
Jason Campbell
I feel like that would introduce more problems than it would solve. The inability to post it directly, and having to trust some central source to hold and maintain it are pretty big downsides.
Brayden Torres
>I feel like that would introduce more problems than it would solve. Put that on my tombstone On the other hand, giving anyone the ability to make their own calendar is exactly as likely to cause issues of similar kind, where the thread has 3 or 4 different branches of the calendar
Nolan Perry
>read p2 >FUCK >spend 15 minutes on a stupid bfs solution just because I already have the code >fuck it, can't think how to make this work >maybe A* will work (note: I have never used A* before) >spend like 8 hours defiling the corpse of an A* algorithm only to get it sort of working on the example, but nothing else >give up, look at Jow Forums >"just include the tool in the node" >FUCK why couldn't I think of that >go back to bfs >still too much of a brainlet to get that working after an hour >try A* again >tweak it the same way I did the bfs algorithm, takes 20 minutes >try running it, 1.5s runtime in cpython >right answer on the first try And with that, I consider myself filtered. At least I made it this far on my own, that's not so bad for someone with zero formal CS education.
I don't have any graph libraries, so I had to check again how to Implement Dijkstra. Also took me quite a while to realize I had to make a node per tool, and missread the part about how changing tools works. Then had the bug with the graph size. A shitshow all around for me really, was surprised I ranked ~500 with how long it took me
Austin Hernandez
My vision is augmented.
Easton Johnson
Jow Forumsuys I need advice, I have sent days on day 4 and wrote multiple hundred line class files (java) and still after multiple days cant get it correct. How do I improve or am I always stuck as a brainlet?
Jordan Torres
>day 4 >multiple hundred line class files The absolute state of java
Being serious though, you're going to need to be more specific on how it works, or what parts you're having trouble with if you want advice to improve. I do recommend sticking with it though, it's good practice and far too many people gave up early.
Nathan Gutierrez
You might be overthinking it. Only pay attention to the minutes, and build a few hashtables counting.
David Butler
>Is the abstraction to view the tools as part of the state and therefore encode them in the nodes really that groundbreaking? It might be if your only exposure to shortest-path search is from games, where the labels are basically always some kind of position. In fact I think the only time I've ever done A* on a graph labeled with more general states was for an assignment in an AI class in college.
Luke Martinez
I think I over complicated it pls no bully but constructive criticism would be nice
You can just put the input into a list line by line and sort it It doesnt need to be any more complicated than that
Jaxson Sullivan
If I import a* I get the wrong answer.. if I import Dijkstra I get the right answer. :( I might have to actually learn graph traversal
Alexander Ramirez
what does/ doesn't work? what test cases have you tried? which step do you think is the problematic one? what is the general idea of your algorithm?
Joseph Rivera
I read line by line from a file that contains puzzle input, each line I create a event obj which stores the the string and parse out the date of the string and place all of them into a arraylist. then i sort it from least to highest based on the date for each evetn obj. after that i look i loop through and look at each event to see if it has "guard in it, if it does a create a guard object and then since all events tire in chronological order after the sorting i add the events to guards schedule. then I compute the guard with the most time asleep, and then i find the minute with the most consecutive sleeping periods on it. The probelm is I get multiple minutes that say they are to most used. idk if any of this makes sense
Alexander Martinez
ok, have you tried the test input, i.e. the one from the problem description and did it work? > and then i find the minute with the most consecutive sleeping periods on it. do you actually look for consecutive periods? the problem doesn't talk about consecutive, but only about which minute the chosen guard is asleep most. Can you reproduce the result given in the problem description? i.e. minute 25 being the (unique) minute the guard was asleep on the most often?
Xavier Myers
I am getting multiple minutes the guard was asleep on the most often, which doesnt make sense. plus I dont know if I got the right guard, I got #709
to those anons who started doing the problems on the following day thanks for letting me feel smart by allowing me to move into the top 20
Cooper Hill
A* can actually give wrong outputs if your heuristic is sufficiently shitty. Read the wikipedia page and make sure your heuristic is "admissible".
Adrian Stewart
I feel like there haven't really been any breaks in difficulty this year. Last year it was every 4 or 5 days like clockwork but this year it seems like the difficulty has been a continual ramp up.
is what I get. 709 only has 415 minutes asleep total but that guard would indeed have multiple hours, on which he was asleep most often: [ 1 1 1 2 2 4 5 4 4 4 4 7 7 7 9 9 10 11 11 11 11 12 12 11 11 12 12 11 11 11 10 10 10 10 9 10 8 8 8 7 7 6 6 7 7 7 7 5 5 5 5 6 6 5 4 4 3 2 0 0]
Jose Robinson
It's wild how much filtering has happened, how dead this thread is compared to how the first few days were
Oliver Jenkins
welp back to the drawing board I guess
Carter Long
I don't really get how people get filtered, none of the problems have been ridiculously hard and multiple hints get posted often. Only one I'm still tihnking about is the water one, because my implementation was shitty but I'm not sure how to make it better.
William Cook
Only 33 anons have even completed everything so far.
Xavier Jackson
I was using the Manhattan distance from the point to the goal.. what's a better one for this problem?
I'd have dropped out already if I weren't a stubborn bastard trying to prove to myself I'm not a complete brainlet. It gets fatiguing after three weeks.
Austin Morris
That's what I used and is definitely admissible. Must be a bug somewhere else then.
Christopher Adams
get Hype. only 3 to go! let's enjoy them
Thomas Lewis
TWO MINUTES
Jayden Campbell
preemptive FUCK
Samuel Howard
Today my bowels are clean
Ryan Long
FUCK I GOT A CRAP ON DECK THAT COULD CHOKE A DONKEY
Juan Rogers
Yea I must have fucked something else up then thanks
Kevin Wood
OH NO I FEEL THE FECES ESCAPING
Charles Campbell
FUCK
Angel Moore
>Manhatten distance again
Anthony Phillips
ENOUGH, TAKE SOME DAMN LAXATIVES AND STAY ON THE TOILET.
Juan Parker
This is the third time.
Henry Parker
> 1) Dec 23 00:01:18 That's how long it took me to understand the problem.
If this was in 2d maybe I could do the intersections, and then intersect the rectangles, etc. until I'm left with nothing. But there's no way I'm going to write that correctly for pic related. I guess I'm filtered. First AoC problem I can't finish in 4 years.
>Implying 3d makes it different My issue is that the numbers are so big you can't just do a stupid grid solution, so I have to implement something that doesn't suck
Julian Ramirez
i have my "brute force" method running for part 2 now while i try and think of a more clever solution
Wyatt White
FUCK I missed the puzzle release because I was playing sudoku on the shitter
Michael Miller
For some reason my part 1 is wrong but it works for the example???