/aocg/ - Advent of Code 2018 General #17

I write code like a drunken Pajeet and I'm still in

Why is this so slow?

import string as s

def remainslen(units):
change = -1
while change:
change = len(units)
for cl, cu in zip(s.ascii_lowercase, s.ascii_uppercase):
units = units.replace(cl + cu, '')
units = units.replace(cu + cl, '')
change -= len(units)
return len(units)

print(remainslen(units))

lengths = []
for cl, cu in zip(s.ascii_lowercase, s.ascii_uppercase):
candidate = units.replace(cl, '')
lengths.append(remainslen(candidate.replace(cu, '')))
print(min(lengths))

$ time python3 5.py

It's clearly not, you've invoked FOUR function calls (each of which likely contains a branch condition) while the linked code is just arithmetic.

>it was the hardest puzzle for now
No, it wasn't. Literally 4 LoC in Python after parsing.

Guards wasn’t even that bad.

Because your algorithm is N^2 or worse

Show me your code.

Having to cover the cases with or just made me feel dumb because I knew there had to be a better solution (which you provided).

Wrangling the data into a usable form was the hard part, after you did that
is right

I’m too busy with finals QQ. Won’t be on any leaderboards but soon there’ll be one less person with just 1 star!

zip(s.ascii_lowercase, s.ascii_uppercase)
Instead of building this every time why don't you assign its result to a variable and use that?

Question: how confident would you be in your answers if the page didn't tell you whether they were right/wrong, and instead just accepted either silently? Say you only had once chance to get it right, what steps would you take to verify the logic of your code?

I would write a lot of test cases, and think twice about my code, like at do at work.

the interpreter will do that for him

>Have we reached the brainlet filter?
Depends on how you define brainlet but I'm not a professional and have never taken any courses in programming and I was able to solve all these problems within an hour just by programming the first idea that came into my head. It's of course terribly inefficient but I was still able to do it.

I saw today people using a stack-based approach to solving this issue and just felt like an idiot, but my idiotic solution still worked fine (with a 4 minute run time)

import lib
import re

def day_4(lines: sorted):
lines = iter(lines)
guards = {}
minutes = [0]*60 + [0]
for s in lines:
match = re.search(r'Guard #(\d+) begins', s)
if match:
id = int(match.group(1))
if id not in guards:
guards[id] = minutes[:]
elif 'falls' in s:
m = int(s[15:17]) # minutes
s = next(lines) # assume 'wakes' is next
m2 = int(s[15:17])
guards[id][-1] += m2 - m
for i in range(m, m2):
guards[id][i] += 1

id = max(guards.keys(), key=lambda x: guards[x][-1])
part1 = id * max(range(60), key=lambda x: guards[id][x])

id = max(guards.keys(), key=lambda x: max(guards[x][:60]))
part2 = id * max(range(60), key=lambda x: guards[id][x])

return part1, part2

if __name__ == "__main__":
print(day_4(sorted(lib.inpt_s())))
"lib" supplies my own input function.

You have the test input. 90% of the time, if you get the correct test output, the real output is correct.

This. I'd make some more test cases if the provided ones didn't seem to cover everything.

Will it though? better not to rely on it.

What do you suppose the end image is going to be? Random Christmas themed stuff with stars on? More hats? Something to do with shrinking Santa?

Attached: Calendar.png (722x622, 12K)

>[0]*60 + [0]
>Literally 4 LoC in Python after parsing.
What you call parsing, is not just parsing, you're already processing the data.

And by the way what will you do if a guards doesn't wake up?

Still harder than today. I don't say that day 4 was hard, I say it's the hardest.

>"dude, python is great for its first-class string support"
>use said string features and they turn out to be completely useless in practice performance wise
Brilliant. So what do I need, some kind of stack?
It will not, CPython is dumb as shit and doesn't optimize anything beyond some duplicate strings pointing to the same memory.

>>[0]*60 + [0]
I mean. What does it mean?

>And by the way what will you do if a guards doesn't wake up?
Different guy, but this is a puzzle, there's no choice building a bulletproof solution when you know edge cases like that don't occur in the input

This was not fun

Attached: what language even is this.png (1101x621, 29K)

Santa's cybersuit

I use OCaml, so I specify all the cases, I handled a guard that doesn't wake up.

A stack is best, yes.

What the fuck am I looking at

Oh god what the fuck?

>A stack is best
We're talking about an array used as a stack?

I am using this to learn C and I am still in the first puzzle lol

oh my days...

>What you call parsing, is not just parsing, you're already processing the data.
That is parsing. It would be stupid to parse twice, or multiple times. I'm parsing the relevant data. The 4 LoC that follow search the parsed data for the answer.
>And by the way what will you do if a guards doesn't wake up?
A guard has to wake up to come off of duty. So you can parse falls,wakes lines in groups of two.

>Have we reached the brainlet filter?
you do realize there are soln's all over the internet right? people just lose interest i think

list has append and pop already so.....

Use whatever you want as a stack. I used a linked list.

How do I optimize this? It itrrates more than 120 times through the input liat before it finds a match, and it takes something like 5 minutes to complete. Help.
lines = []
r = 0
res = []
done = False
cnt = 0
with open('aoc/day1/aoc.txt','r') as f:
lines = f.read().splitlines()

while not done:
for line in lines:
r += int(line)
if r in res:
print(r)
done = True
break
res.append(r)
cnt+=1

print(cnt)

Especially this. I use the test case and then I add a few more complications to it to ensure I got all the edge cases. For example today instead of using
dabAcCaCBAcCcaDA
I used
aAdabAcCaCBAcCcaDzZZAbBcCdDDddDabB
which has units that react at the start and end of the string and also has several nested reactions. The same units right next to each other, some reacting some not. included a few 'Z's in there too to ensure I was checking over the whole alphabet.

I am still in so no we haven't reach it.

res = set()
res.add(r)

use a set for res
don't parse it everytime, map int over the lines before the loop

>That is parsing.
You parsed, yes, but you also process the data. That's fact.
>It would be stupid to parse twice, or multiple times.
I have separated the parsing from the processing, but I parse the data only once.
>The 4 LoC that follow search the parsed data for the answer.
No it search the precomputed data got the answer. I have also a small code that do that, because the main code is done in my processing step, that you hide in parsing and refuse to count as data processing.

>A guard has to wake up to come off of duty.
Yes, but if he wakes up at 1:02, is it in the data?
Where is it written adventofcode.com/2018/day/4
>So you can parse falls,wakes lines in groups of two.
Hypothesis only in your mind. At least you could have written a test to assert that the next line is a woke up line, like this if your hypothesis is wrong you would have an immediate diagnostic.

I'm going to assume you're a beginner. There are two big things I would recommend you change.
First: you're converting each line to an integer each time you use it. When you're programming one of the things you should try to do is avoid duplicating work. So convert all the lines to integers at the start of the program instead, and work with those.
Second: you're testing if "r" is in "res" where "res" is a list. lists have terrible time complexity (how the time to preform an operation changes with relation to how big the object is), you potentially have to look through the WHOLE LIST in order to decide if "r" is in there. This gets very, very slow. You should use a set instead like the other user suggested.

I'm new to python, figured I would start learning it like this; what is a set/what does set() do?

Do you mean convert them when I read them from the file, or can I convert the whole list to int at once? I'm used to statically typed variables.

read
en.wikipedia.org/wiki/Hash_table
basically a set() is an implementation of the above.

The major difference is that a set is unordered and can only contain one of each element. If it doesn't matter what order your data is in then using a set makes lookups far more efficient. A fair few people made the same mistake on the first day so I wouldn't worry too much.

Part 2

real 0m0.034s
user 0m0.030s
sys 0m0.003s

For default input? Which language?

A dictionary would do pretty much the same thing if you used
res = {}
res.update({r: True})

holy fuck no. a set is not a hash table.
en.wikipedia.org/wiki/Set_(abstract_data_type)

>No, it wasn't. Literally 4 LoC in Python after parsing.
by that rationale day 5 was 0 lines of code after parsing. also i saw that code on plebbit.

Using stack implementation in C
pastebin.com/r8dVLLvH

I do 3ms for the 2 parts with a stack implementation in C. You can improve user.

I thought that was a dict in python.
How exactly do I check if the data doesn't repeat itself if the whole set doesn't contain duplicate data?

Sets are very commonly implemented as hash tables.

I never said they were. I said they can be implemented with a hash table.

what time do you get on the 500MB input?

fastest i could go on the 500mb file.

Attached: the end.png (174x164, 3K)

so a beginner asked what a set is, and you gave him a link about hashtables and told him that's what sets are implemented as underneath? wow dude so helpful

Parsing is processing. You can than process this processed data. As it happens, you only need to parse once here. By your logic, reading lines of input is processing and not parsing, because you're selectively reading the data based on one character, the newline. So is everything except a raw chunk of bytes "processing"?
>Yes, but if he wakes up at 1:02, is it in the data?
"Because all asleep/awake times are during the midnight hour (00:00 - 00:59), only the minute portion (00 - 59)"
>Hypothesis only in your mind
The first thing I checked in Vim was the count of lines matching "falls" and "wakes", and they were equal. The sorted input's last line ends on "wakes". So such an assumption is correct at least for this data.

a set is a hash table

If you've seen the value before (if it's in your set) then you found the first repetition, otherwise you add it to the set.

>also i saw that code on plebbit.
Are redditfags stealing Jow Forums's code? How pathetic.

a set can also be a tree where update makes sure there are no duplicates
but the underlying implementation doesn't matter to a beginner at all, who only cares how to use them

>How exactly do I check if the data doesn't repeat itself if the whole set doesn't contain duplicate data?
In Python you don't have to worry as if you try to add duplicates to a set it just ignores it. Other languages will give errors and such. It depends on implementation.
It is very common in Python to convert lists to sets in order to get the unique elements of a list.
a = [0, 1, 2, 3, 2, 3, 0, 1]
b = set(a)
print(b)
>{0, 1, 2, 3}

I still don't exactly understand how a set is faster than a list, they are both mutable. Essentially I would do the same operation on a set as I currently do with my list; only the set is faster, why?

It is helpful, one has to know why you'd even use a set instead of a list in Python. It's essential to first learn about fundamental data structures and their pros/cons.

user's C version takes more time than my haskal one, he can definitely fix something

Yes because the magic of the hash table EXPLAINS why the look up is faster than lists.

std::swap(reddit, Jow Forums);

Internally a list is, well, a list while a set is a tree or a hashtable

Lookup on a hash table backed set ("is this value here?") is constant time. Lookup on a list requires an iteration until you find it.

4.353s
Intel(R) Core(TM) i7-4600U CPU @ 2.10GHz

>"Because all asleep/awake times are during the midnight hour (00:00 - 00:59), only the minute portion (00 - 59)"
fair enough

Less than 3ms for default input? Really? I just retest, and I have a run of 2ms.

what language?

>what is a set/what does set() do?
way to ignore the guy's actual question so you can jerk yourselves off over implementation, faggots

>implying you can "steal" code

no no no, the user with the 32ms runtime is about the same speed as my haskell

nice speed
also I'm guessing the other guy meant that his haskell solution is faster than

a better answer is "a set is a container that doesn't allow duplicate elements. it's faster to insert/lookup than a list, because the underlying implementation is often a hashtable"

>constant time
on average though. since collisions can occur on buckets, more so with shitty hash functions, then you get linear time just like a list

Can someone post their Go solution? My is way too slow and I want an inspiration.
As an exchange I'm reposting my regexp Perl solution for part 1.
perl -nlE 'for(;s;(.)(??{uc$1eq$1?lc$1:uc$1});;g;){}say length' advent05_input.txt

I thought had to optimize 5.1 in order to my computer give me the answer for 5.2 today. Here is the new iteration, more than 30 times faster:
import Data.Char

main :: IO ()
main = do
--filename [Char]
reducer [] = []
reducer (x:xs)
|((fst x)/=(snd x))&&(((Data.Char.toUpper (fst x))==(snd x))||((Data.Char.toLower (fst x))==(snd x))) = reducer (tail xs)
|otherwise = [(fst x)] ++ reducer xs

Accrediting code you didn't write to yourself is some form of stealing, at least as intellectual theft is concerned.

I just tried it and it reduced my time from 50s to 26ms.
Can you explain why there is a difference of factor 2000 between set and list?

(hashtablefags, here's your chance)

Don't worry about implementation details

The direction of traversal is... unorthodox, but it still works. I still don't know why reduce boxes if the result is nonscalar though. Is it required by the standard to always return a rank-0?

ghostbin.com/paste/9d6oc

Attached: aoc 2018 day 5.png (872x172, 5K)

indubitably

Attached: giphy.gif (275x252, 1.39M)

Thanks for the help, so the optimized code should look something like this?
lines = []
r = 0
res = set()
done = False
cnt = 0
with open('aoc/day1/aoc.txt','r') as f:
lines = int(f.read().splitlines())

while not done:
for line in lines:
r += line
if r in res:
print(r)
done = True
break
res.add(r)
cnt+=1

print(cnt)
Not at the computer right now, but this should work, correct?

>intellectual theft
not a real thing