/aocg/ - Advent of Code 2018 General #8

Wrong
labels = get1()
seen = [set() for _ in range(len(labels[0]))]

for label in labels:
for j in range(len(label)):
sub_label = label[:j] + label[j + 1:]
if sub_label in seen[j]:
print(sub_label)
seen[j].add(sub_label)

1.6 seconds on the big-boy input The idea here is that seen[0] is the set of all inputs seen so far with character 0 removed, seen[1] is with char 1 removed, and so on. When you go to add the current label (minus char j) to seen[j], if that value is already present in the set, itmeans there's a previous label that's identical to the current label except at position j.

nice
also nice to see cunninghamslaw still works

There's a very simple linlog one, and a harder supposedly linear one using suffix trees.

Also, here's my own (quadratic!) solution. The Hamming distance as an inner product wasn't unexpected, but was nice nonetheless.
ghostbin.com/paste/drchn

Attached: aoc 2018 day 2.png (794x135, 6K)

WTF am I reading here?

mojibake

5m 17s for my shitty quadratic solution lol

9.8s in C++. Though, that's on a 9 year old cpu and in a VM..

Code here: raw.githubusercontent.com/DuSTman31/AoC2018/master/Day2.cpp

Got fucking savaged for longwinded code in last years threads..

my js solution has been running for about a minute on big boy set and it hasn't finished... how do I into speed? Are there simple optimisations I'm missing, I just want to learn what the first steps would be given what I've written.

const fs = require('fs');

const ids = fs
// .readFileSync('input.txt')
.readFileSync('input-big.txt')
.toString()
.split('\n');

console.time('Day 2 Pt 2');

let common = '';
let idLen = ids[0].length;

for (let index = 0; index < ids.length; index++) {
let found = false;
let idOneChars = [...ids[index]];

for (let subIndex = index + 1; subIndex < ids.length; subIndex++) {
let idTwoChars = [...ids[subIndex]];
let diffs = 0;
let diffIndex = 0;
let char = '';

for (let charIndex = 0; charIndex < idLen; charIndex++) {
char = idOneChars[charIndex];
if (char !== idTwoChars[charIndex]) {
diffs++;
diffIndex = charIndex;
}
}

if (diffs === 1) {
idTwoChars.splice(diffIndex, 1);
common = idTwoChars.join('');
found = true;
console.log(`index ${index} is similar to ${subIndex}`);
break;
}
}

if (found) break;
}

console.timeEnd('Day 2 Pt 2');

console.log('Common', common);

def p2(data):
data = sorted(data)
n = 0
for i in range(1, len(data[0])):
for comb in zip(data, data[-i:]+data[:-i]):
n+=1
mm = list(map( lambda x: x[0]!=x[1], zip(*comb)))
if sum(mm) == 1:
print(n)
return ''.join(c for m,c in zip(mm, comb[0]) if not m)

If i'm reading this right, you're checking the first line against the second line in the first iteration, then checking the second against the first in the second iteration. Wasted effort.

My python code has shit bricks on the big boy set though so that alone won't fix it

from time import *
def main():
new_list = []
file = open("bigboy_input.txt", 'r')
for line in file:
new_list.append(line.rstrip("\n"))

for i in range(len(new_list[0])):
table = set()
for item in new_list:
new_item = item[0:i] + item[i+1:]
if new_item in table:
return new_item
table.add(new_item)

start = time()
print(main())
print(time() - start)

gives me 115ms on a shitty old 2.33GHz Xeon (10 years old)

Attached: __kinomoto_sakura_cardcaptor_sakura_drawn_by_cangkong__9463207a2ecd00152ea71559fb7b2079.jpg (807x1400, 500K)

>every pair of two boxes
The comparison of every two boxes is not O(n^2), it's O(n!/2(n-2)!), which is to say smaller than O(n^2).
If you're a brainlet and didn't set int j=i+1 then you're running a lot of iterations for no good reason.

Attached: Annotation 2018-12-02 180742.jpg (491x481, 19K)

13.8 seconds for me. Down from 3 minutes after realizing I could stop the string comparison after finding that more than one char differs.

Why is C so beautiful and fast?
$ time ./a.out

Attached: Screenshot_2018-12-02_15-05-48.png (835x1097, 122K)

asymptotically O(n!/2(n-2)!) is equal to O(n^2)

>The comparison of every two boxes is not O(n^2), it's O(n!/2(n-2)!), which is to say smaller than O(n^2).
???
O(n!/(2(n-2)!)) = O(n(n-1)/2) = O(n^2/2-n/2) = O(n^2/2) = O(n^2)
this is because
(n!/(2(n-2)!)) / n^2 = n(n-1)/(2n^2) = n-1/(2n) = 1/2 - 1/(2n) which goes to 1/2 as n goes to infinity

def part_two_alt(ids):
min_len = min(map(len, ids))
for i in range(min_len):
seen = set()
for x in ids:
spliced = x[:i] + x[i + 1:]
if spliced in seen:
return spliced
seen.add(spliced)
34ms on the big-boy input.

>size = 1024
ebin

See
Every pair of two boxes most certainly is O(n^2).

Attached: 2018-12-02-151415_97x144_scrot.png (97x144, 3K)

Where did you get n!/2(n-2)! ?
Using j=i+1 gets you n(n+1)/2 pairs which is still O(n^2) retard.

holy shit, after writing it like this i went down from 5 minutes to 1.5 seconds

Something tells me a good locality sensitive hashing function could make this a lot cheaper...

Huh?

That's the power of nlogn.

are you niggas real, the graph is right there
The ratio of n^2 to n!/2(n-2)! is bigger than 2:1

You can't just autistically hide away details like that and """pretend""" that int j=0 isn't a crime against performance.

What is mathematical combination with no repeats

the first loop loops through all ids, the second loop only loops through all id's after current one, and the third loop is just the char comparrison. I don't think it does what you say but I'll double check, maybe I musunderstand

Maybe reduce the expected constant factors, but you won't go below O(n).

functionalfags btfo
must be fun using a language without dictionaries built in

i was gonna shitpost but i noticed you grow it

i don't have a brainlet image good enough for this

Stay in school kid.

>compsci majors obsessed with their concise O(faggot) notation

It's true that n^2 > n!/2(n-2)! (aka n choose 2).
It's false that n!/2(n-2)! = o(n^2).

24 seconds in C on a Sandy-Bridge dual core. Guess I need to optimize.

The point is that overly concise notation like O(n^2) hides details.
Algorithms professors who understand the difference between quicksort and mergesort (it's a constant time difference, but everyone uses quicksort) don't ignore constants.

Technically if the first statement is true, the second definition of it being O(n^2) must be true. We're using Big O, not Big Theta.

for all x in O(n^2), x is also in O(n^3), etc...

very nice idea with the chevrons for tabs, I tried and gave up on it with shitty plain '>'s

Very elegant.

Ah apologies I misread

Take that up with the definition of big O notations, brainlet.

I think that a prefix tree would be smarter, but you'd waste a lot of time just building the tree.

>It's false that n!/2(n-2)! = o(n^2).
n!/2(n-2)! = 1/2 n*(n-1)*(n-2)....*1 / (n-2)*...*1
= 1/2 * n * (n-1)
= (n^2 - n)/2

That's O(n^2).

Is it possible to avoid comparing strings twice in part 2 without a hash table?

Math is a tool, not the holy grail.
Go back to your useless pure math.

Yes, but in this case O(n^2) is exactly equal to O(n!/2(n-2)!).
Big-O notation is useful in a theoretical context. In a practical context, constant factors are also very important. The only thing I've been arguing against is 's claim that O(n^2) != O(n!/2(n-2)!), which is false.

>The ratio of n^2 to n!/2(n-2)! is bigger than 2:1
The ratio is literally 2n/(n-1).
2n/(n-1)1+2/x. Therefore for n > 100, the ratio is lower than ~2.02.
>You can't just autistically hide away details like that and """pretend""" that int j=0 isn't a crime against performance.
No one is pretending they're the same thing. Obviously, reading every element of a symmetric matrix is slower than reading only the upper right half (and the diagonal).
However, O notation has a meaning, and you can't arbitrarily redefine it as "goes as fast as."

I think that user meant o, not O.

When people talk about time complexity, it's rarely about getting an exact growth curve because machine instructions/interrupters/compilers/code will vary too much for these types of analysis to be of any practical use. Instead people talk about upper bounds and growth rates, because these things are largely independent of hardware or translation efficiency. Think about it like first year calculus, when you learned about limits, the most important thing when finding the limit of a function is the rate of growth of the fastest growing term, everything else can basically be considered 0 as the entire function approaches infinity.

>comparing strings twice in part 2
That never happens if you set your for loop to prevent repeats.
Hash tables aren't even a part of the problem.

Yes. In fact it's Θ(n^2), which proves it's not o(n^2).

I've already graduated, you don't need to throw the book at me.
The point of the graph is because people are stupid and won't read a wall of text.
Don't look too deeply into a post.
"Look, the ratio is right in front of you! You can SEE it!"

Nobody talks about little-o. He's just an armchair programmer who has no idea about the mathematics about growth rates and why they are so important, but things he intuited the gist it and that it his intuition is wrong then the notation must be wrong.

>I've already graduated
from a school in india?

Attached: 6b0.jpg (337x404, 29K)

Has anyone given up because it's too hard yet?

Attached: chio_taunting.png (543x518, 438K)

Can I have a code review for my part two solution?
I feel like I over complicated it some
but it did get the answer
I'm not really used to writing python

pls no bully
def find_string(stringA,stringB):
differences = 0;
diff_pos = 0;

for x in range(len(stringA)):
in_diff_pos = stringA[x] != stringB[x]
if (in_diff_pos):
diff_pos = x
differences += 1

if differences > 1:
return ""
return stringA[:diff_pos] + stringB[diff_pos+1::]

def part2():
strings = util.read_input('day2_input')
for i in range(len(strings)):
string = strings[i]
for cmp_string in strings[i+1::]:
correct_string = find_string(string, cmp_string)
if len(correct_string):
return correct_string

>ptpb.pw/WCXh.in
My Haskell O(n2) brapped itself trying to do this one.

By definition, every function in Θ(g(x)) MUST also be in O(g(x)) and Ω(g(x)). It might not be o(g(x)) (little o and Big O are different), but NO ONE IS TALKING ABOUT THAT CLASS.

>this is the nth thread with anons obsessed with marking algorithms with loose time complexity bounds
>jumps at anyone who dares use stricter time complexity bounds
Your 'tism must be pretty severe if you don't allow people to dare use unsimplified O-notation.

Attached: 1537039854626.jpg (1282x720, 174K)

>takes exactly 100000 loops to find it
Spooky.

How? I don't mean when strings equal, of course you can avoid that, but I mean avoiding inverse comparisons, e.g. compare(sx, sy) and then later again compare(sy, sx). You would have to hash the strings and check if seen, no?

stay assblasted Ranjeet Poopta

>compare (sx, sy) vs (sy, sx)
Never happens if you set int j = i + 1
Why do you keep mentioning hashing?
Hashing can be a valid solution but it's ostensibly a poor one.

For one thing, why are you using an entire helper function to load the input?

strings = open("day2_input").readlines()

Unless it fetches it from the website?

ok, I hope you get a grant for your research into the optimal microwave time curve for frozen tendies

I (), the first person that brought up o, am talking about little-o. Lol.

I did not know about that function thanks user.
what I'm more worried about here is having lower space and time complexity

but again thanks user

1.4s seconds with both part1 and part2 on a mid 2015 macshitbook retina in go
doesn't all fit in a post since it's a lot of unoptimized spaghetti,
pastebin.com/a1MpfAsr
also I know I'm not terminating shit nicely but you get what you get, if anyone has a many cores processor give it a try
it reads lines one by ones and starts processing them right away, one goroutine for the checksum and one for the other thing

So is tonight gonna be another 30 second python one liner while the rest of us with real programming languages take at least 5-10 min?

itertools is comfy. i think another user posted a similar Rust solution earlier (?)

Attached: part2_v2.png (497x328, 8K)

python can do that elegantly in 3 lines
which is why a string-building solution like that would be forgivable

if you're going to use so many lines then why bother with string building?

>if you're going to use so many lines
because this isn't python, also saving lines isn't as important as saving execution time (not that my solution is *that* optimized)

Have we lost any fellow brainlets yet? I'm feeling good about the challenges so far but still fear the wall when it comes.

You'll know when it happens.
You can't miss it.
Imagine the pink fields of Jow Forums

I have no idea what that means, minerman.

0.762s in Haskell using Sets

youtube.com/watch?v=BkX2NAKFM5Q

>be new to C
>program is done in 10 minutes
>file handling takes 3 hours of trying to allocate memory correctly, and making a hodgepodge library using BSD repos to get the getline function working on windows

Attached: 1323707437522.gif (250x141, 2.58M)

the one for day 2 runs at like 20ms, why does this one not seem to want to finish

>Never happens if you set int j = i + 1
Only if you assume there aren't duplicate strings.

And if you hash the string pointers, you can use random lookup without looping, potentially finding the correct answer on the first comparison. E.g.:
>step 1: call getrandomstr()
>2: if string/string pointer has been hashed, repeat step 1
>3: hash string, compare
>4: continue until answer is found
Worst case time complexity is exactly the same plus some hash table overhead, while theoretical is O(1). In fact, I'm going to implement this right now, because deterministic algorithms are so boring.

There is no wall.

I'm sure some dropped out, but it's going well so far.
The main early brainlet filters last year were day 3 (spirals) and day 7 (recursion). With the puzzles being so varied, some inevitably run into roadblocks with certain topics, but if you already missed the leaderboard, there's no shame in research as long as you work it out yourself.
Basically, don't worry about it.

>only if you assume there aren't duplicate strings
But there aren't duplicate strings.
I think you're operating on another plane of existence because I'm pretty sure no one else here is trying to invent problems

What file handling? Take a look at it's literally 4 LoC for getline() + realloc. Just redirect file to stdin via your shell or cat. Why doesn't Windows have getline, isn't it part of libc since 2008?

Converted this to Rust. Got 0.581s in total.
const BOX_ID_SIZE : usize = 26;
fn find_similar(v: Vec) {
let mut seen = Vec::::with_capacity(BOX_ID_SIZE);
for _ in 0..BOX_ID_SIZE {
seen.push(HashSet::::new());
}

let mut substr = String::with_capacity(BOX_ID_SIZE);
for s in v.iter() {
for j in 0..BOX_ID_SIZE {
let s1 = s.get(0..j).unwrap();
let s2 = s.get(j+1..).unwrap();
substr.push_str(s1);
substr.push_str(s2);

if seen[j].contains(&substr) {
println!("Common string: {}", substr);
return;
}

seen[j].insert(substr.clone());
substr.clear();
}
}
}

Thanks for the insight, user.

th-thirty seconds in nim :(

Attached: grad.png (407x446, 27K)

don't feel bad user, I'm rewriting my code after this happened real 2m55.095s

#include //for output
#include //for reading
using namespace std;
int main() {
int sum = 0; //integer for sum
int j; //integer for array
int array[1014]; //array of leength 1014 for lines of integers
ifstream reader; //initialize
reader.open("data"); //same directory as program
if (!reader) { //if can't open terminate
cout > array[j]) { //while reading populate array
sum += array[j]; //sum = sum + array compounding sum
}
reader.close(); //close
cout

Day 2 Part 2 is too hard I'm already out I'm stupid

All I can think of is going line by line checking every other line and I know that's complete trash.

You said hashing was a poor solution and I just told you how it's a better solution than a deterministic loop.

If you need to do something quickly in C, let the OS handle your memory and resource cleanup.

Try to understand the code in .

>isn't it part of libc since 2008
It's been part of POSIX since 2008. It is NOT a part of the ISO C99 or ISO C11 standards.