/aocg/ - Advent of Code 2018 General #34

Fancy wristwatch 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: hqdefault.jpg (480x360, 18K)

Other urls found in this thread:

anonfile.com/QdI3O9n9ba/bigboi.txt_zip
pastebin.com/raw/6q9fm0Jv
pastebin.com/raw/6EGmGPjB
pastebin.com/XZkmHFh6
pastebin.com/WEN8CQ1h
twitter.com/AnonBabble

That was easy.
Also did someone end up updating the calendar?

Attached: 1521279275589.png (10000x10000, 2.89M)

>mfw goblins can attack and move in the same turn
no fucking way are you kidding me. that's totally unintuitive

Attached: 1524387244515.jpg (640x427, 46K)

It's the only part that was immediately clear to me in that whole wall of text.

so my mapping is correct actually, I guess it's just how i'm interpreting the input

i don't like 13's at all desu

That's just because you didn't notice 13's drawing is distributed throughout the whole image

Next year we can't constantly antagonize the brainlets for getting filtered. We need the brainlets to stick around and make calendar memes

I think it's clever

BIGBOI INPUT:
anonfile.com/QdI3O9n9ba/bigboi.txt_zip

Today wasn't the filter because I made it.

I think it's safe to say that yesterday was the filter.

Yesterday wasn't the filter because I made it.

Rock on based bigboi generator

Attached: 1535355446536.png (577x387, 62K)

>part 1 answer is wrong
>i dont know where to start debugging

ughh

what should i do if the input is invalid for part 1 i.e. trying to access register 7

don't try to access register 7

Recycled this for yesterday's image. Feel free to add stuff relevant to elves and goblins if you feel like it.

Make sure your input parsing is correct.

Attached: 1515133237928.png (10000x10000, 2.91M)

pretty sure my solution for the goblin problem part 1 works properly, the issue is it isn't running fast enough (and consumes all my memory and cpu, freezing my machine). any advices?

Attached: 1522990292913.jpg (580x773, 93K)

>Make sure your input parsing is correct.

do you mean no input should try to access >3 register? or do you mean i should handle this error?

fix your memory leak

>do you mean no input should try to access >3 register
yes

im using java

Don't store unnecessary data? How's your pathfinding/bfs implementation?

I mean you're probably parsing your input wrong and assigning a number to the wrong variable. Or sending the wrong variable to your opcode function.

maybe you're continually storing more and more data to the end of a container instead of reusing the space that's available?

If done properly problem 15 shouldn't take much memory at all. Before each turn you need to have in memory:
- The position of each unit
- The hitpoints of each unit
- The position of each wall

During the pathfinding portion, if you're using bfs (which is the way to go) then you need to have in memory:
- each of up to four movement candidate squares
- each of enemy target squares
- a list of visited nodes for bfs

What else do you have in memory?
>I'm using Java
Java doesn't fix user-generated memory leaks. It's probably. At some point in one of you're loops you're probably extending or appending something instead of overwriting.

>consumes all memory
Your solution really should store more than the units, the map, and maybe an extra map to do pathfinding on.

Shouldn't

oh yeah, that's probably it since i made a stack weirdly using a list without clearing the old values. thank you

no actually i did, i just think it looks like shit

>last week
>haha fucking brainlets will be gone soon, leaving only us true programmers(TM)

>past few days
>dude these threads are dead, fuck this

the brainlets make this shit fun desu. i find the threads much more interesting when people are freaking out/asking for help as opposed to the threads where everybody just dumps their own code that nobody reads

so does 11 not have an image or is it being empty part of some sort of joke?

several images were posted in the thread
dunno why none are on the calendar

>mfw it took me almost 2 hours of printing out everything over and over to realize that my functions were all correct except for the fact that I missed that it's not always the last register thats being assigned to

Attached: Screenshot from 2018-12-10 19-18-28.png (907x539, 330K)

ok i fixed it. my regular expression was wrong.

but now my answer is still wrong REEEEEE

maybe somebody can point out what I got wrong. i have no leads at this point.

r = [0,0,0,0]

def set_r(c, val):
global r
r[c] = val
return 'heh'

OPCODES = {
'addr': (lambda a,b,c: set_r(c, r[a] + r[b])),
'addi': (lambda a,b,c: set_r(c, r[a] + b)),
'mulr': (lambda a,b,c: set_r(c, r[a] * r[b])),
'muli': (lambda a,b,c: set_r(c, r[a] * b)),
'banr': (lambda a,b,c: set_r(c, r[a] & r[b])),
'bani': (lambda a,b,c: set_r(c, r[a] & b)),
'borr': (lambda a,b,c: set_r(c, r[a] | r[b])),
'bori': (lambda a,b,c: set_r(c, r[a] | b)),
'setr': (lambda a,b,c: set_r(c, r[a])),
'seti': (lambda a,b,c: set_r(c, a)),
'gtir': (lambda a,b,c: set_r(c, 1 if a > r[b] else 0)),
'gtri': (lambda a,b,c: set_r(c, 1 if r[a] > b else 0)),
'gtrr': (lambda a,b,c: set_r(c, 1 if r[a] > r[b] else 0)),
'eqir': (lambda a,b,c: set_r(c, 1 if a == r[b] else 0)),
'eqri': (lambda a,b,c: set_r(c, 1 if r[a] == b else 0)),
'eqrr': (lambda a,b,c: set_r(c, 1 if r[a] == r[b] else 0)),
}

class Sample:
def __init__(s, before, instr, after):
s.before = before
s.instr = instr
s.after = after

def __str__(s):
return str(s.before) + str(s.instr) + str(s.after)

with open('input16.txt') as f:
lines = f.read()
part1, part2 = lines.split('\n\n\n')

samples = []
data = part1.split('\n\n')
for datum in data:
num = re.findall(r'\d+', datum)
num = list(map(int, num))
sample = Sample(num[0:4],num[4:8],num[8:12])
samples.append(sample)

three_count = 0
for sample in samples:
same_count = 0
for op in OPCODES.values():
r = sample.before
op(*sample.instr[1:4])

if r == sample.after:
same_count += 1

if same_count >= 3:
three_count += 1

print(len(samples))
print(three_count)

Don't you know how to take a fucking screenshot? This is Jow Forums and most retards from other boards are better at taking screenshots than you.

>Look up how to turn a string back to a list in python
>Stack overflow: Just use eval breh!
>Me: Ok
>Cleaning up my solution after finishing I realize it was as simple as map(int, string[1:-1].split(","))
I really need to up my list processing game

gnome screenshot -> "grab the current window" defaults to including the window border and nobody so far seemed disturbed about it

What's a register? How do I access a register in Python? This problem was outdated and made for the cnile age.

mpv has a screenshot shortcut. RTFM

>map
But that's not Pythonic™

>eval
Jesus and I thought my parsing was ugly.
def parse(in_file='input.txt'):
state = []
instructions = []
temp = None
with open(in_file, 'r') as f:
for l in f:
l = l.strip()
if l.startswith('Before:'):
s=l.split('Before:')
if len(s) != 2: raise Exception("Parse error")
temp = list(map(int,s[1].strip(' []').split(',')))
elif l.startswith('After:'):
s = l.split('After:')
if len(s) != 2: raise Exception("Parse error")
state.append((temp, list(map(int,s[1].strip(' []').split(',')))))
else:
s = l.split(' ')
if len(s)

>Just use eval breh!
Does stackoverflow have no basic concept of security vulnerabilities?
Last year some user was tricked into running an rm -rf from a malicious input posted here, because they used eval.
Didn't do shit due to permissions, but still a lesson learned.
Fuck the "pythonic" way, security comes first.

replace the word "register" with "index", voila!

hah i figured it out. i need to copy the list before modifying it.

thx for nothing Jow Forums

>>> a_fucking_string = "A fucking string"
>>> a_fucking_list = list(a_fucking_string)
>>> print(a_fucking_list)
['A', ' ', 'f', 'u', 'c', 'k', 'i', 'n', 'g', ' ', 's', 't', 'r', 'i', 'n', 'g']

did you guys write code to figure out which opcodes were which or did you do it by hand like a sudoku puzzle? took me probably 45 by hand

Attached: drapersmoke.jpg (285x298, 10K)

Nah, someone give this user some shellcode so he can access his real registers straight from python.

Messy haskell solution

Attached: Code_fxfIJcocnq.png (1701x998, 257K)

why do you have global r when it doesn't actually do anything

That's not the question
Input = "[1,2,3,4]"
output = [1,2,3,4]

wrote code to print which functions were which
then I hardcoded the calls in to get the answer
I've since updated the code to do it automatically

>he didn't make a magic parsing function

def get_numbers(arg):
if type(arg) == str:
line = arg.replace(',', ' ')
for char in string.punctuation.replace('-', '') + string.ascii_lowercase + string.ascii_uppercase:
line = line.replace(char, ' ')
t = tuple()
for e in line.split(' '):
if e:
t += (int(e),)
return t
elif type(arg) == list:
L = []
for line in arg:
L.append(get_numbers(line))
return L

>>>c = 'Before: [1, 1, 0, 3]\n3 0 2 0\nAfter: [0, 1, 0, 3]'.splitlines()
>>>get_numbers(c)
[(1, 1, 0, 3), (3, 0, 2, 0), (0, 1, 0, 3)]

registers don't even exist because of pipelining

Wrote some code, too lazy to do manual labor

from deduceOpMap :: Map Int (Set OpCode) -> Map Int (Set OpCode) -> Map Int OpCode
deduceOpMap opCandidates opMap
| Map.size opMap == Map.size opCandidates =
Map.map (head . Set.elems) opMap
| otherwise =
let opMap' = Map.union opMap
. Map.filter ((==1) . length)
. Map.map (`Set.difference` fold opMap)
$ opCandidates
in deduceOpMap opCandidates opMap'

It works fine with that though. If you want something to be a list, all you have to do is put it inside a list()
a_fucking_string = "[0,1,2,3]"
a_fucking_list = list(int(char) for char in a_fucking_string.strip('[]').replace(',',''))
print(a_fucking_list)

do it with more than one digit per integer

Here's your homework.
a_fucking_string = "[00,11,22,33]"
a_fucking_list = list(int(char) for char in a_fucking_string.strip('[]').split(','))
print(a_fucking_list)

def get_numbers(arg):
return tuple(int(e) for e in arg if e.isdigit()) if type(arg) == str else [get_numbers(n) for n in arg]

>>>c = 'Before: [1, 1, 0, 3]\n3 0 2 0\nAfter: [0, 1, 0, 3]'.splitlines()
>>>get_numbers(c)
[(1, 1, 0, 3), (3, 0, 2, 0), (0, 1, 0, 3)]

>It works fine with that though
>Posts completely different code
U wot

Might be an overkill, but I performed a Maximum Bipartite Matching to find the mapping.
You don't to do network flow to find it though.
First, I build array of sets Adj[i], where Adj[i] is a set of possible operations for the opcode i.

Then,
bool mark[200];
int match[200];

// returns true if and only if
// there exists augmenting path
// starting from v

bool dfs(int v){
if(mark[v])
return false;
mark[v] = true;
for(auto &u : Adj[v])
if(match[u] == -1 or dfs(match[u]))
return match[v] = u, match[u] = v, true;
return false;
}

Then to find the matching:
memset(match,-1,sizeof match);

while(true){
memset(mark, false, sizeof mark);
bool fnd = false;
for(int i = 0;i < 16;i ++)
if(match[i] == -1 && !mark[i])
fnd |= dfs(i);
if(!fnd)
break;
}

After that, match[i] contains the mapped operation of opcode i.

aocg died a lot faster than last year huh

I appreciate the advice, but
>>>d = "11 52 98 5 -4"
>>>tuple(int(e) for e in d if e.isdigit())
(1, 1, 5, 2, 9, 8, 5, 4)
>>>get_numbers(d)
(11, 52, 98, 5, -4)

Day 15 definitely killed it

>can't even find an easy to run python solution for day 15 so i can cheat

that's how you know it's bad

I found a way to solve this with an entirely finite amount of memory and utilizing 16-bit integers and integer arithmetic to reduce the "possible" set down to its proper equivalences(C++)

pastebin.com/raw/6q9fm0Jv

this is the fastest implementation i can think of right now

g++ main.cpp -Ofast -march=native -std=c++17 && time ( ./a.out < Input.txt )
Part 1: 563
Part 2: 629
( ./a.out < Input.txt; ) 0.00s user 0.00s system 48% cpu 0.008 total

gets through bigboi in 7 seconds

./a.out < bigboi.txt
Part 1: 529
Part 2: 9
./a.out < bigboi.txt 7.68s user 0.17s system 99% cpu 7.918 total

inxi -CI
CPU: Topology: Dual Core model: Intel Core i3-6100 bits: 64 type: MT MCP L2 cache: 3072 KiB
Speed: 3700 MHz min/max: 800/3700 MHz Core speeds (MHz): 1: 3700 2: 3700 3: 3700 4: 3700
Info: Processes: 138 Uptime: 2d 4h 53m Memory: 7.70 GiB used: 374.4 MiB (4.7%) Init: systemd Shell: zsh
inxi: 3.0.29

yeah im gonna keep going as long as i can but i dont think im getting day 15 solved ever desu

some times it does, when i change things around.

i built up everything but the pathfinding function for part one, and then when i finally got to that, i just lost the will to keep going

I'm retarded. Can somebody please post their dat 4 p1 input and answer?

there's just so much bullshit requirements and edge cases. i got close to getting a good pathfinding function but im fairly certain you're not supposed to do it in the step-by-step way it shows in the problem description.

pastebin.com/raw/6EGmGPjB
part 1 answer: 26281
part 2 answer: 73001

Are you sure? I get 10778 for p1

I completely cheated on day 15.
For both parts
Part 1: someone's python code spit out the right answer (but not for the second half)
Part 2: someone's c++ code spit out the right answer
Because i'm not spending 24 hours debugging my semi nonworking code and getting filtered after guessing 10 times.

>but im fairly certain you're not supposed to do it in the step-by-step way it shows in the problem description.
Worked for me, although I skipped finding the reachable and just find the nearest.

that's from the website, so yes.

well in order to find whether or not a point is reachable you have to find a path there. if you're generating all the optimal paths to every in range point (which i was doing at one point), it uses way too many resources. i think you have to do it greedily and just return the first path you find

WTF man I did p2 while trying to do p1. Oh well I got my answers

I got my code working on all examples, even on weird edge case examples that I found on the subreddit but not for my input, so after that I also cheated. I'm gonna try it again later with something else than BFS + reverse BFS, just in case, but since I checked the results (in the examples) multiple times already, I'm not quite sure whether that will fix it

here is an idea
you could make up your own test cases and see if your code works on it

day 15 completely defeated me so I kinda lost interest in learning shit today

Attached: i have given up.png (319x252, 17K)

>return(reg[A],+B)

>it uses way too many resources
Not really, if you do bfs all values asigned on the first try are minimal and it's O(n) (with n being the amount of free cells)

today was pretty fun since i was always too scared to learn assembly

>finds the code typo
>doesn't find the logic typo

wait yeah you're right i was also implementing bfs really inefficiently i think. maybe i'll give it another go tomorrow, blegh

i only spoonfeed a little

careful with your copypastes user

Good luck. I implemented my bfs more like a dijkstra at first and waste a ton of time rewalking paths that were already minimal.
Made a function that prints the current map with the pathfinding values overlayed and realized my mistake. Quite fun since the example cases were so tiny that the O(n^2) actually worked without issues.

thanks but this was one of the easiest part 1 so far
what the fuck