/aocg/ - Advent of Code 2017 General #17

Judge Dredd for the SNES 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.

The new leaderboard with empty space is
join-code: 43046-941b8011

The old (full) leaderboard is
join-code: 194764-c554ff91

Other urls found in this thread:

maurits.vdschee.nl/scatterplot/
godbolt.org/g/h4EJ8s
adventofcode.com/2016/day/5
twitter.com/AnonBabble

public static long generateNumber(char generator, long prev, int part) {
long factor = (generator == 'A') ? 16807 : 48271;
long modulo = (generator == 'A') ? 4 : 8;
prev = (prev * factor) % 2147483647;
if(part == 2)
while((prev % modulo) != 0)
prev = (prev * factor) % 2147483647;
return prev;
}

public static int solve(int part, long A, long B, long mask) {
int matched = 0;
int loopRange = (part == 1) ? 40000000 : 5000000;

for(int i=0; i

so what are some actually good ways to achieve the same result without string slicing?

See: Bit ops are a thing.

I corrected my functions a bit and this is what I have
Note how the stable squares in the middle keep their colors

I'll be off to work now, have a good day anons

that was underwhelming.

4256ms for both parts combined. sepples with an i5 2500k.
anyone have a fast solution?

make that 685ms with -O3 flag

>6x9=42

>mod 0x10000 instead of & 0xffff
Why's that?

Hitchhiker's Guide to the Galaxy.

The more you get bantsed for sloppy code, the more likely you'll come up with the better answer first next time around
(at least in theory)

In base 13 it's true

Well, I feel like a fucking idiot. I forgot that it was 6*9 specifically.

I don't think negative reinforcement is as productive at achieving those goals as you think it is.

mine
is similar, 5s on debug and ~550ms with --release on an i5.

cuz that's the first thing I thought of and the compiler is smart enough to optimize it. and-ing 0xffff would have made more sense tho

It sounds like a fine idea to me

Well you could always try the reddit circle jerk if this place is too much for you

And you wouldn't be wrong. Negative reinforcement CAN work. However, in the most ironic fashion, according to a number of experiments, positive reinforcement is more effective at conditioning than its negative counterpart. Moreover, negative reinforcement tends to create a wealth of other issues down the line.

In a way, it's logical to care about feelings.

The more you know.

Why? You don't want to bant about bants?

>repeating yourself instead of using do-while
this is the power of Rust

A-at least I finally got to use generators in Python:
def dueling_generators(modulo=False):
a = generate_value(512, 16807, 4, modulo)
b = generate_value(191, 48271, 8, modulo)
count = 0
times = 5000000 if modulo else 40000000

for _ in range(times):
x, y = next(a), next(b)
count += 1 if bin(x)[-16:] == bin(y)[-16:] else 0

return count


def generate_value(default_value, factor, modulo, use_modulo):
n = default_value
while True:
n = (n * factor) % 2147483647
if use_modulo and n % modulo != 0:
continue
yield n


# Part 1
print(dueling_generators())
# Part 2
print(dueling_generators(modulo=True))

lol same

function* numbers(start = 0, multiplier = 0, checker = 2) {
let nd = checker - 1;
let prev = start;
while (true) {
prev = (prev * multiplier) % 2147483647;
if ((prev & nd) === 0) yield prev;
}
}

const genA = numbers(699, 16807, 4);
const genB = numbers(124, 48271, 8);

let score = 0;
for (let i = 0; i < 5e6; i++) {
const scr1 = genA.next().value;
const scr2 = genB.next().value;
if ((scr1 & 65535) === (scr2 & 65535)) score++;
}

console.log(score);

Please change image for Day 12. It is highly offensive.

Just noticed, but /ourguy/ is number one on the overall leaderboard

oy vey its annuda 40 million
think of poor python fags whos cpus where ovened

Good joke, friend. I am sure you have added that image by mistake. You don't want to be an antisemite, right?

Congrats, user. You're an hero to all of us.

Mehmet / Pajeet hopscotch: A-okay
Travelling merchant: OY to the VEY

Behold, the fastest solution in this thread:

#include
#include
#include
#include

long long * aL;
long long * bL;

void Loop(long long start, long long * x, int y, int z)
{
int i = 0;
long long a = start;
while (1) {
a = a * y % 2147483647;
if (a % z == 0) {
x[i++] = a;
if (i == 5000000) { break; }
}
}
}

void ALoop(long long aS) { Loop(aS, aL, 16807, 4); }
void BLoop(long long bS) { Loop(bS, bL, 48271, 8); }

int PartTwo(long long aS, long long bS)
{
int count = 0, i;
aL = malloc(5000000 * sizeof(long long));
bL = malloc(5000000 * sizeof(long long));

pthread_t tidA, tidB;
pthread_create(&tidA, NULL, ALoop, aS);
pthread_create(&tidB, NULL, BLoop, bS);
pthread_join(tidA, NULL);
pthread_join(tidB, NULL);

for (i = 0; i < 5000000; i++) {
if ((aL[i] & 65535) == (bL[i] & 65535)) {
count++;
}
}

free(aL);
free(bL);
return count;
}

int main()
{
clock_t begin = clock();
int output = PartTwo(65, 8921);
clock_t end = clock();
double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
printf("%d (%.0f ms)\n", output, time_spent * 1000);
}

240 ms when compiled with -Ofast. The big bottleneck here is (a * y % 2147483647); if there was a way to do it with bitwise operations, it could probably break sub-100 ms.

>BLoop

jej

what other flags?

Nice compiler warnings, fuckface.

Finished day 14 but my ranking is ass because I was busy with finals til day 10.

God I'm retarded, meant to say day 15.

man, part 2 took me forever because I stopped after generating 5 million candidates instead of actually sending 5 million to the judge and I just couldn't see my mistake.

Could anyone point me to some resources about understanding strictness and thunks and shit in Haskell? My first solution overflowed and all the help I could find was variations of

> just make it strict bro! Don't let those thunks get too deep bro!

15, scala, quick n sloppy due to being in transit
p1
var matches = 0
var a = L
var b = L
for(i

Yeah. you didn't use enough iterator adapters.
fn main() {
let gen = |a: u64, b| {
(0..).scan((a, b), |s, _| {
s.0 = s.0 * s.1 % 2147483647;
Some(s.0)
})
};
println!(
"{}",
gen(65, 16807)
.zip(gen(8921, 48271))
.take(40000000)
.filter(|&(a, b)| (a ^ b) & 0xFFFF == 0)
.count()
);
println!(
"{}",
gen(65, 16807)
.filter(|&a| a % 4 == 0)
.zip(gen(8921, 48271).filter(|&b| b % 8 == 0))
.take(5000000)
.filter(|&(a, b)| (a ^ b) & 0xFFFF == 0)
.count()
);
}

package main

import "fmt"

func generator(factor, start, div int) func() int {
return func() int {
for {
start = (start * factor) % 2147483647
if start % div == 0 {
break
}
}
return start
}
}

func main() {
a := generator(16807, 883, 4)
b := generator(48271, 879, 8)
count := 0
for i := 0; i < 5000000; i++ {
av, bv := a(), b()
if (av & 65535) == (bv & 65535) {
count++
}
}
fmt.Println(count)
}

OY VEY SHUT IT DOWN

>tfw whole fucking day without electricity.

r8 my solution pls no bully

it's basically the same as everyone else's/10

Yeah this day was fucking easy wtf.

no spaces between operators / 10

seriously WHY do people do this?

Elegant but twice as slow as
package main

import (
"fmt"
"time"
)

func main() {
o := time.Now()
a := 289
b := 629
pairs := 0
iterations := 5000000
arr := make([][2]int, 5000000)
i := 0
for i < iterations {
a = genA(a)
if a%4 == 0 {
arr[i][0] = a
i++
}
}
i = 0
for i < iterations {
b = genB(b)
if b%8 == 0 {
arr[i][1] = b
i++
}
}
for _, row := range arr {
if row[0]&0xffff == row[1]&0xffff {
pairs++
}
}
fmt.Println(pairs)

fmt.Println(time.Since(o))
}

func genA(i int) int {
return (i * 16807) % 2147483647
}

func genB(i int) int {
return (i * 48271) % 2147483647
}

Honestly the only somewhat hard day so far was 7.

I've had more trouble with day 11. 7 was on the easier side in my opinion.

how is your box so colorful?

and 7 wasn't even hard, it was just annoying. You could describe the algorithm in a few sentences.

I did a hexagonal coordinate problem for my uni's programming competition a few months back. So problem 11 was easy for me.

you have to actually complete the challenges to get a cool visualization :^)

0 stars brainlet detected

>mfw only 8 stars

Show your boxes. boxlets need to apply.

Rate my code for Day 11
ins = input().split(",")
dir = {"nw":[0,-1,1],"n":[-1,0,1],"ne":[-1,1,0],"se":[0,1,-1],"s":[1,0,-1],"sw":[1,-1,0]}
loc = [0,0,0]

for i in ins:
loc[0] += dir[i][0]
loc[1] += dir[i][1]
loc[2] += dir[i][2]

print(max(loc))

patrician box here

...

...

neat. I used it as an excuse to fuck around with channels.

package main

import (
"fmt"
)

func main() {
count := 0
cha := make(chan int, 5)
chb := make(chan int, 5)

go generate(116, 16807, 4, cha)
go generate(299, 48271, 8, chb)

for i := 0; i < 5000000; i++ {
i, _ :=

When you write shit code that takes 70 seconds to run but then you run through pypy and 70 seconds goes down to 2.5 seconds without any changes to the code.

from util import test, run

def main():
gen_a_start = 289
gen_b_start = 629

factor_a = 16807
factor_b = 48271

remainder = 2147483647

def advance(gen, factor):
return (gen * factor) % remainder

def advance_both(gen_a, gen_b):
return (advance(gen_a, factor_a, ), advance(gen_b, factor_b, ))

def advance_muls(gen_a, gen_b):
(gen_a, gen_b, ) = advance_both(gen_a, gen_b)

while gen_a % 4 != 0:
gen_a = advance(gen_a, factor_a)

while gen_b % 8 != 0:
gen_b = advance(gen_b, factor_b)

return (gen_a, gen_b, )

def solve(input, fun):
count = 0
(gen_a, gen_b, iterations, ) = input

for _ in range(iterations):
(gen_a, gen_b, ) = fun(gen_a, gen_b, )

if (gen_a & 0xFFFF) ^ (gen_b & 0xFFFF) == 0:
count += 1

return count

run([
(solve, (gen_a_start, gen_b_start, 40000000, ), advance_both, ),
(solve, (gen_a_start, gen_b_start, 5000000, ), advance_muls, ),
])

if __name__ == '__main__':
main()

pypy is fucking magic

No. CPython if fucking trash.

It's just better at some tasks than CPython but keep in mind it's not always faster, I always take my code for a spin through pypy when I'm done with a solution and some days it's actually much slower than CPython.

initially I though the array alignment could have something to do with it, but it's faster only due to hardcoded factor and divisor.

>but it's faster only due to hardcoded factor and divisor.
LOL. Is his the true power of Go?

>faster only due to hardcoded factor and divisor

Yeah, that's plain stupid. Seriously did not expected that. Checked the same in C and it is both the same speed there.

well at least it compiled fast

>has a compiler
>it is still sometimes slower than the interpreter
So this is the true power of python?

user...

Ok it happens to C as well with -O0, so Go compiler is missing some optimization. Anyone has an idea what could that be?

generics?

>please register with fagbook, jewgle or your big brother of choice to continue
Thanks but no thanks.

You wouldn't be able to deal with day 1 anyway.

...

while you're being a little bitch who won't register a dummy github, we're all enjoying saving Christmas

>(((sjwhub)))
>just do it

it's ok, you can keep spamming your latest fizzbuzz on /dpt/ instead

Incorrect
maurits.vdschee.nl/scatterplot/

Your experience may not reflect the experience of others.

I didn't expect AoC to make us test the MINSTD Lehmer generators.

About two weeks late with that bait.

programming is gay.

Neat

Pointer magic did seem like a nice alternative to "& 0xFFFF", but it turned out it's not really faster

>but it turned out it's not really faster
Are you retarded? Why would it be faster??

If you're on x86, compilers should generate a 16-bit compare anyway.

What is this code doing?

godbolt.org/g/h4EJ8s
get rekt retard

Anyone did this adventofcode.com/2016/day/5 ?
I finished part 1 easily using openssl MD5 function in C++ but it takes 4.5 seconds to find the password.
I feel like there is a better way than hashing everything like a retard.

There is no better way

Am I understanding this correctly?

>&A
Address of A
>(uint16_t*)
Cast the address of A to a 16-bit unsigned integer (treat A as a 16-bit unsigned integer)
>*
dereference that pointer

hashing on more cores
hashing on GPU
hashing on distributed cluster

Anything for today's calendar image?

>part 2 is even more brute forcing
JUST

yeah I'll try using multiple cores latter but I think openssl MD5 function is not parallelizable (is that a real word?)

No, D5P2 in 2015 was literally "what if you needed to spend a billion more computing power to solve this?"

Did some profiling and modulo was an issue. Seems like compiler knows some tricks for modulo with constants and does some generic algo for variables. Unlike GCC it doesn't pay attention that arguments are constants only that keeps it generic.

Judge Dredd judging binary numbers

Part 2 takes 17 fucking seconds
>mfw I imagine the python fags trying to compute the password

Unless they implement MD5 in Python it shouldn't be a big problem