/aocg/ - Advent of Code General

Join us in solving a new puzzle every day of advent!

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

adventofcode.com/

Sup Forums has it's own private leaderboard:
join code: 194764-c554ff91
(You need to register with an account but you can appear as anonymous)

>Previous thread:

Other urls found in this thread:

youtube.com/watch?v=ZJuuatPU60g
twitter.com/SFWRedditGifs

3 threads makes this a general now?

but 25 could

(anonymous user #194764), please delete the the users with no stars off your leaderboard, you're gonna max out real soon.

I don't want to stay up to 5AM to get a good score

this

No because I am feeling rather irritable today and the slightest thing is throwing me into a rage and really pissing me off... Im just gonna go to bed and watch netflix. Fuck my life everything is shit.

No one really cares about the leaderboard rankings. We're all just having fun solving them and discussing different solutions so it doesn't matter if you're a few hours late or not.

then do it for pleasure of completing a task

I am

Here's mine for the day 2 part 2.

First time using generators in Javascript because I felt like using some library to get permutations was a bit dirty.

What do you want then?

>irritable today
1. drink decent amount of water
2. go outside for a walk(excercise would be even better)
3. go back and eat something

You'll feel much better.

wake up at 5AM, faggot

wew

Why not going full functional and use only reduce, map and filter? Or do we count them as "some libraries"?
I get that it's the same in the end, but I hate seeing nested loops.

I know man, I hate nested loops too.
How would you do permutations with any of the methods you named? map result always has the same number of results as input, filter the same or less. Reduce could be an array i guess, so i could add to it, but it really seems to me liken something like permutations should really be done by a generator.

I made in the previous thread. I have to admit that it took me a while to get a hang of stuff like that, and it could be better. But once you get into it it's almost impossible to think differently.
>something like permutations should really be done by a generator.
I don't know, maybe because I never really used generators, but it's the last thing I think of usually.

Confy font user. A lil more bourder round and would be supb

Generators are pretty important concept. And permutations are one of the best examples of it's uses. Since number of permutations of a list grows almost exponentially, especially when you increase the number of element in the permutation, your resulting list could be HUGE. So instead of creating the whole list and puttingit into memory we just go one by one, and get them on-demand.

Also, often you don't need everything that a generator creates for you, sometimes you abandon it after a few lements were checked. If you created the whole list of permutations in advance that wouldn't be just wasted memory space, but also wasted cpu cycles.

I also saw your solution in previous thread but I'm still not sure how to do permutations without loops. I'll think about it.

It's only Terminus, one of the greatest fonts in the pantheon of programming fonts.

Also, scrot seems to be taking colors out of my screenshots. I think it's the low default quality setting.

>Generators are pretty important concept.
Yeah, it's on my stuff-you-should-look-into.txt

>pleasure of solving utterly retarded tasks
lol no

i wonna be #1

>tfw full time job
>tfw can't stay up until 12am to program like the old days

Oh well
Is there any other better way to do part 2 that doesn't involve looping through all the numbers?
Part 1 was easy, though

>for for for
you should be fired

>he thinks filter reduce reduce is any better

I have recently gotten into C and would like to know on what to focus on improving.

I know the struct isnt necessary, but i did it anyways.
#include
#include

#define ROWLENGTH 16
#define COLNUM 16

struct DynamicArray {
int arrayLength;
int* data;
};
struct DynamicArray readFile();
int calculateRow(int*);
int calculateRowDividing(int*);

int main(){
int colNum = 0;
int sum = 0;
struct DynamicArray dataArray = readFile();

int *temp = malloc(sizeof(int) * ROWLENGTH);

while(colNum < COLNUM){
memcpy(temp,dataArray.data + (colNum * ROWLENGTH),sizeof(int) * ROWLENGTH);
sum+= calculateRowDividing(temp);
//sum+= calculateRow(temp);
rowNum++;
free(temp);
}
printf("Checksum: %d", sum);
return 0;
}
int calculateRowDividing(int* data){ //Day2, task 2
int i,y = 0;
while(i < ROWLENGTH){
y = 0;
while(y < ROWLENGTH){
if(data[i] % data[y] == 0 && i != y){
return abs(data[i] / data[y]);
}
y++;
}
i++;
}
}
int calculateRow(int* data){// Day2, task 1
int i = 0;
int smallest = 999999;
int largest = 0;

while(i < ROWLENGTH){
if(data[i] > largest){
largest = data[i];
}
if(data[i] < smallest){
smallest = data[i];
}
i++;
}
return (largest - smallest);
}

I forgot the readFile function.
struct DynamicArray readFile(){
struct DynamicArray array;

FILE *file = fopen("input.txt","r");

int i = 0;
int temp;

while(!feof(file)){
fscanf(file,"%d ",&temp);
i++;
}
rewind(file);

array.data = malloc(sizeof(int) * i);
array.arrayLength = i;

int pointer = 0;
while(pointer

Hey man. I'm just trying to find a better algorithm than n^2. And there needs to be at least 1 loop to go through the outer vector

My C solution is like 150 lines of code because I ended up writing a vector for slurping up stdin, and the input tokenizer takes up more loc than the actual logic.

>join leaderboard
>99% of people are anonymous user #4352

c'mon people, that's no fun

>How would you do permutations with any of the methods you named?
This should generate the same output as your implementation if I'm reading it right.
let perms = arr => arr.reduce((a,b,c,d)=>a.concat(d.map(x=>[b,x])),[])

> perms([1,2,3])
[ [ 1, 1 ],
[ 1, 2 ],
[ 1, 3 ],
[ 2, 1 ],
[ 2, 2 ],
[ 2, 3 ],
[ 3, 1 ],
[ 3, 2 ],
[ 3, 3 ] ]

r8/h8/appric8

If I'm anonymous here, I'm anonymous there.

NICE! I really like that. Thanks dude!

Although I still think things like permutations should be done by generators. But I appreciate the example anyway.

you have a unique numerical id, you're not anonymous there you just picked a boring name

and yes, i know using built in sort is a cuck move

If you need any more stupid disgusting ways to write a functional one-liner to do something in javascript, I'm your man.

These are all my AoC solutions so far, where s is the input

d1p1: s.filter((a,b,c)=>a==c[(+b+1)%s.length]).reduce((a,b)=>a+(+b),0)
d1p2: s.filter((a,b,c)=>a==c[(+b+(s.length/2))%s.length]).reduce((a,b)=>a+(+b),0)

d2p1: s.map(a=>a.sort((a,b)=>a-b)).map(a=>+a[a.length-1]-a[0]).reduce((a,b)=>a+b,0)
d2p2: s.map(w=>w.map((a,i,x)=>x.map(b=>(b==a||b%a)?0:b/a).reduce((a,b)=>a+b,0)).reduce((a,b)=>a+b,0)).reduce((a,b)=>a+b,0)

permutations should absolutely be done by generators if you want clean and performant code. But who wants that?

>Fourth of the people gave up without even trying
>Half of the people didn't bother to solve the second day puzzle
Whoah, so this is the power of Sup Forums

Oh yeah, here's my vectorize implementation

Maybe that's the small handful of people on Sup Forums who have better things to do with their time

I don't really know any programming languages properly anymore...

What should I learn/pick up by doing this event/challenge?

lol shuuuuuure

Pascal.

Haskel

Do it faggot.

>mfw I'm bellow people who solved only 1 day challenge

>join thread
>99% of people are Anonymous

c'mon people, that's no fun

bonus challenge: is there a way to do day 2 part 2 in less than O(n^2) time?

>all these people doing IO and not using the appropriate language for the job

lol

>O(n^2)
the fuck is this even means

hello pajeet

the absolute state of Sup Forums

I’ve peeped at maybe 15 solutions from the top 100 board. Everyone has n^2 algorithms

COBOL?

Stop posting until you’ve read an algorithms textbook ty

is this a joke?

Poorly structured, hard to read.

leave

There is no reason to implement a more efficient than necessary solution if you're just trying to top the leaderboards. It'd be a waste of time trying to be smart about things.

but... the form only accepts answers, not code...

ur full of shit my friend

fucking nigger sclick on the username, some of them liked their github account and actually upload their code to their git repo

You can link your github to your account, anons

brainlet solution inc

import csv

with open('input.txt', 'r') as f:
input = [list(map(int, line)) for line in csv.reader(f, delimiter="\t")]

#day1 solution
# res = sum([(max(x) - min(x)) for x in input])

res = 0
for row in input:
for i,x in enumerate(row):
for y in row:
if x % y == 0 and x != y:
res+=(x/y)
print(res)

if you assume some constant upper bound on the size of the numbers themselves, this allows for constant time factorization as well as constant time iteration over those factors and you can can get O(n) with something like

def factors(n):
result = []
for i in range(1, int(n**0.5) + 1):
if n % i == 0:
result.append(i)
if i**2 != n and i != 1: result.append(n // i)
return result

result = 0
for line in s.split("\n"):
number_by_factors = {}
numbers = set()

for num in [int(n) for n in line.split()]:
if num in number_by_factors:
result += number_by_factors[num] // num

facts = factors(num)
for f in facts:
if f in numbers:
result += num // f
number_by_factors[f] = num
numbers.add(num)

print(result)


which happens to be horribly impractical for arrays this small

With the tiny input sizes they use, it's far better to bang out the O(n^2) algorithm than to sit for a few minutes and think up the O(n log n) or O(n) approach. Reminder: the cutoff time for top 100 today was 06:13.

So I might just be a brainlet, but how do I use filter with a binary conditional on the NEXT value of the array? I tried doing the same one-liner in Python but I cannot remember the syntax. Something like lambda x, y: x if x == y else None.

that's not linear time, though

>same chink bastard keeps finishing in 1:15 for BOTH STARS

I just did three with (m)awk just now. I'm not seeing why y'all wasting your time with these full blown languages with basic line/space delimited inputs.

Unless I'm mistaken, it is if you assume constant upper bound on element sizes, the factorization and iteration over factors would itself be constant.

The fuck is he writing in? I wanna see his solution, but no github available.

With any algorithm if you assume an upper bound, it is constant time. You just gotta shrink the upperbound so that there's only one possibility

That doesn't mean the algorithm is constant time

real question

with that logic every single solution here is constant time since we know exactly how many time we iterate

probably he has a REPL open and copy pastes into it
that's what i did and it was pretty fast

Here's a video of a pajeet finishing both parts in 2 minutes, Python:
youtube.com/watch?v=ZJuuatPU60g

Probably Python or C++.

>halfof the solution
kek

When will you finally accept chink supremacy

both parts are there friendo

I saw someone use itertools.combinations for part 2 which was pretty interesting

>import csv

HackerRank is meme, you can find all solutions on forums and complete the shits for each lang on 100% in a day.

Not bad pajeet, not bad at all.

I kinda stumbled on that one because I hated calling Math.max.apply(null, list) so I spend some time googling for a nicer way, and eventually did find Math.max(...list).

pythonic solution:
$ pip install adventofcode2017
$ ipython
> from adventofcode2017 import day2
> print day2.part1()
> print day2.part2()

It's linear time with respect to the number of integers, not their size.

More accurately, it's O(n*m), m being the largest integer in the list.

lets see your double for loop part 1 solution then buddy :^)

>how do I use filter with a binary conditional on the NEXT value of the array?
Both of the uses of filter in the post you replied to do that

kek

>see people using Shit++ and similar languages have 50 lines of code
>literally 3 lines in Matlab (can go down to 1 in Mathematica)

load input.txt
checksum = @(inp) sum(max(inp') - min(inp'));
checksum(input)

Is it all right if I join now but solve the problems later? I'm currently involved in a project and won't have time this and next week.

Making the factorization is linear time, user. Just because you're abstracting it in a function call, does not mean it goes away.

for n in range(100):
preform_linear_time_calculation(n)

This is n^2

impressive

ARE YOU MAD? DO IT NOW OR PERISH

[spoiler]It's cool dudem, it's just a silly competition.[/spoiler]

thanks senpai :3
I wish I had the time I used to for fun things

Can someone recommend a site where I can find more similar fun tasks?

>tfw I'm working till 1am tonight and wont be able to do #3 till the morning after it releases

You're conflating two different inputs.

The factorization is O(m), not O(n) - in other words the time increases linearly as a function of the number of integers, linearly as a function of the size of the integers, and exponentially as a function of both.

I have something to the effect of
total = 0
for(i = 0; i < charArray.lengh; /i++) {
// If statments and stuff
total += charArray[(int)i]
//...
}


Yet total just increments by 49 each time, rather than the value held in that position of the charArray read in.. wtf

i like coding challenges but the autists who obsess over number of lines should be put down.

runtime and readability are the only things that matter

Ignore the '/' before the i++

Stay up drinking all night in the nearby bar until I get kicked out around 3am or wake tup at 4:30 and try to solve it after having breakfast... tought decisions.