/aocg/ - Advent of Code 2018 General #39

thred's ded baby edition

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:

208834-4a1a9383

Attached: 1515205231959.jpg (962x451, 216K)

Other urls found in this thread:

pastebin.com/sHj1nJ7q
pastebin.com/cjErGuRT
youtube.com/watch?v=hjGZLnja1o8
twitter.com/NSFWRedditImage

You'd think with all the shortest path finding we've had this wouldn't be such a problem

Attached: file.png (270x27, 2K)

Is the second leader boars broken or am I banned from it somehow

>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

I literally didn't implement A* once and now i'm screwed

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?

I get 944

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.

I get 944 for that input. I extend to (2000, 2000).

Did I fuck up my A* if it's taking over 5 minutes to run and my TYPE computer is memoized?

I was keeping track of closed_set in array, so my "Has this node been visited already?" checks got slower and slower.. oops.

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

@lru_cache(maxsize=10**8)
def g(x,y):
return ((f(x,y)+DEPTH)%M)

def region(x,y):
return g(x,y)%3
#%%
res=0
for x in range(TAR[0]+1):
for y in range(TAR[1]+1):
res+=region(x,y)

print(res)

#%%
#third number encodes tool
# 0=None
# 1=climbing gear
# 2=torch
def getVertices(x,y):
reg=region(x,y)
#print(reg)
if reg==0:
return [(x,y,1),(x,y,2)]
if reg==1:
return [(x,y,0),(x,y,1)]
if reg==2:
return [(x,y,0),(x,y,2)]
raise

def getEdges(x,y):
v1s=getVertices(x,y)
res=[]
for dx,dy in (1,0),(0,1):
nx,ny=x+dx,y+dy
if nx

ok, found the mistake. I allowed for movement between zone1 and zone2 even if the gear equipped in zone2 was not equipable in zone1.

day 21 part 1 in verilog, requires an external assembler
I'm not sure how to do part 2 though

Attached: file.png (716x998, 327K)

Ah, I see. I'm surprised that only saves 2 minutes.

>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

Attached: Screenshot_2018-12-22_10-53-18.png (533x427, 40K)

this is the face of a man that has been thoroughly defeated by himself

Attached: file.png (262x28, 1K)

Time to brush up on your graph algos

>verilog
fucking kek

That is what I'm here for. Tapeout when?

How would I determine which tool to use when I have the choice? That's the one part I can't figure out.

How are they going to try to fuck us in the last 3 days? I didn't come this far to get filtered

Attached: firefox_2018-12-22_14-52-09.png (187x589, 6K)

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)

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.

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.

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

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.

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

I ended up using a bloomfilter
It takes about a minute to solve both parts, using the verilator simulator

Made something that works for the test input, but takes forever on the actual input. Let's see how long this takes.

>part 2
>correct answer on test input
>off by 14 on real input
Every. Time.

>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.

Attached: 1416058956153.jpg (480x360, 14K)

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?

I want to do A* on a three dimentional graph, but I dont have enough battery left.

>coding on a phone

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.

Implying he is not a coding-cyborg, whose batteries are about to run out.

Recharge with a Monster energy drink!

Attached: IDShot_540x540.jpg (540x540, 32K)

>If they allowed phones during exams,
As if you couldn't simply fill the graphing calculators memory full of notes and cheatsheets

Day 22, 6 seconds in pypy

from itertools import product, count
from collections import defaultdict
import re

def memoize(f):
memo = dict()
return lambda *X: memo[X] if X in memo else memo.setdefault(X, f(*X))

def AOC22(file):
depth = int(re.findall('[0-9]+', file.readline())[0])
target = tuple(map(int, re.findall('[0-9]+', file.readline())))

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)

erosion = memoize(lambda x,y: (geo_index(x,y) + depth) % 20183)
rock_type = lambda x,y: erosion(x,y) % 3

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)))

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)

so, what should we do?

Attached: cal_lower.png (10000x5000, 2.08M)

and the upper part

Attached: cal_upper.png (10000x5000, 2.24M)

Did you write your own astar code or is it from a package?

I'm medium-brain on day 22 but I need to learn to do small-brain A*

he probably wrote it for the previous years and keeps it in a module to call if needed

A reference to day 16 and 19 for day 21 is needed

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.

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

it should just be a page layout on some site with the image for each individual day

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.

>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

>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.

Attached: my shame.png (612x68, 4K)

I skipped day 15 because I couldn't be bothered so part 2 fucked me today

I feel very similarly

Attached: chrome_nhfvf7Lqlo.png (260x29, 918)

pathfinding elfcode cellular automata

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

My vision is augmented.

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?

>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.

You might be overthinking it.
Only pay attention to the minutes, and build a few hashtables counting.

>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.

I think I over complicated it
pls no bully but constructive criticism would be nice

pastebin.com/sHj1nJ7q

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

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

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?

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

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?

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

here my puzzle input
pastebin.com/cjErGuRT

Attached: output.png (296x825, 32K)

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

A* can actually give wrong outputs if your heuristic is sufficiently shitty. Read the wikipedia page and make sure your heuristic is "admissible".

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.

part1
guard:
73
hour:
44
3212
4966
part2
guard:
191
hour:
26
4966

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]

It's wild how much filtering has happened, how dead this thread is compared to how the first few days were

welp back to the drawing board I guess

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.

Only 33 anons have even completed everything so far.

I was using the Manhattan distance from the point to the goal.. what's a better one for this problem?

youtube.com/watch?v=hjGZLnja1o8

Attached: rs.jpg (480x360, 23K)

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.

That's what I used and is definitely admissible. Must be a bug somewhere else then.

get Hype. only 3 to go!
let's enjoy them

TWO MINUTES

preemptive FUCK

Today my bowels are clean

FUCK I GOT A CRAP ON DECK THAT COULD CHOKE A DONKEY

Yea I must have fucked something else up then thanks

OH NO
I FEEL THE FECES ESCAPING

FUCK

>Manhatten distance again

ENOUGH, TAKE SOME DAMN LAXATIVES AND STAY ON THE TOILET.

This is the third time.

> 1) Dec 23 00:01:18
That's how long it took me to understand the problem.

Attached: 1429860167902.png (400x400, 22K)

dunno what to do with part2

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.

Attached: filtered.jpg (694x480, 44K)

>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

i have my "brute force" method running for part 2 now while i try and think of a more clever solution

FUCK I missed the puzzle release because I was playing sudoku on the shitter

For some reason my part 1 is wrong but it works for the example???

Rank 8
Get wrecked scrubs

Attached: day_23.png (802x880, 166K)

>only 10 posts in half hour after puzzle release
Is everyone busy with the puzzle or has activity really died down that much?