/aocg/ - Advent of Code 2017 General #23

Update the friggin calendar 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:

ghostbin.com/paste/uu74s
pastebin.com/p1AKRPnZ
ghostbin.com/paste/ob2cj
pastebin.com/ihFynbwW
twitter.com/NSFWRedditGif

so check every particle against each other?

>this day
aaaaaaaaaaaaaa

I sure hope the 24th/25th are comfy quick ones so I can drink rather than think

Holy shit my brain hurts. I can't take it easy like this.
I think I'm going to start over.

...

$ rustc -C opt-level=3 21.rs -o 21-o3
$ time ./21-o3
p1 139
p2 1857134

real 0m3.826s
user 0m3.746s
sys 0m0.081s


Nice, 4.8x faster than the unoptimized mess I posted above. Any rustc flags I can throw in to make it faster?

also, would using a smaller data type for Square (as we're using u32 for a 1-bit cell) help with fitting more of this shit in the cache?
Or are the patterns small enough for that to not be worth the tradeoffs w.r.t. misaligned accesses, etc?

is seems flawed to think about it as 2d grid
3x3 grid spawns 4 2x2 grids which of each never affect any subtree of other 3 grids
each 2x2 grid spawns 3x3 grid etc
it's acyclic tree, also each pattern can just have a number, no need to actually work with arrays and match them

I did a string replace on u32->u8 and it shaved off 0.2 ms, so that doesn't seem to help tooo much..

I think I could save some time by flipping and rotating the input square of each rule and then storing them somewhere. Right now I flip and rotate the test square everytime and then compare it to the rules which is a bunch of extra work.

>I think I could save some time by flipping and rotating the input square of each rule and then storing them somewhere
oh yeah, I got a 2x speedup from that, IIRC. Just expand the lookup map from 1-to-1 to 8-to-1. With hash maps that shouldn't really increase the individual query times.

That's what I'm trying to do. However, anything deeper than 1 level gives me wrong result. And for the love of god I can't figure out why.

eval(2x2) = eval(3x3)
eval(3x3) = sum[1..4] eval(2x2)

>tree stuff
very interesting
>pattern 2 number
shit yer rite
we match rules for max 3x3 matrices. Flatten that and it's a 9-item list. Each item has 2 possibe values. I.e. we can map all possible in-patterns to 2**9 numbers, from 0 to 511. Constant time lookup. Just need conversion if we still keep the stuff as 2d/1d arrays.

But as you say, the mappings a sub-pattern thru rules might not affect the other parts of the overall pattern - but that's assuming in->out never has a smaller out-pattern.
Hmm

wait a sec, using the latest sbt & scala versions with the same shitty 30-liner code:
total: 6615 ms


Yeah, I think I'm more than OK with a 1.72x slowdown, considering all the benefits I get.

Strange, suddenly I don't feel too inclined to double or triple the code/complexity to gain 2.7 sec *smug*smug*

FINALLY
I FUKKEN DID IT GUYS
Also that part 2 was literally replacing 5 with 18, pretty happy about that to be honest.
Is 2s to run considered good or have people managed to get much faster?

cheers m8
2s is decent
rust dude got 1s on his machine (3.5 on mine)
so it depends on your box
and there's probably smarter ways to do it, e.g. in the direction of

did you guys actually implement threads for day 18 pt 2?

I did, but it isn't necessary

Yeah I was asking if anyone had managed to find a solution which runs by an order of magnitude faster so I assume my solution is good.

That's an interesting way to think about it. I'd test it if I weren't so burned out right now.

I used goroutines yeah

Congrats user, 2s is pretty rapid

So there is one key problem. There are 2x2 grids that are formed from multiple (up to 4) 3x3 grids.

there are none, 3x3 spawns 4 2x2, but each 2x2 spawns single 3x3

>There are 2x2 grids that are formed from multiple (up to 4) 3x3 grids.
yuup, need to do some combine/split shit
heck, it's even in the samples, methinks:
3x3 pat -> 4x4 pat split-> 2x2 2x2pats -> (1) 2x2 3x3 pats; merge-> 6x6 pat -> (2) 3x3 2x2 pats -> [...]
the 2x2 pats in (2) are built from parts of the 3x3 pats in (1)

counterexample: or did I mess it up?

No, I messed up. I haven't realized the there can be 2x2 split followed by another 2x2 split

lemme tidy that up
iter 1: 3x3 pat -rules> 4x4 pat
iter 2: 4x4 pat -split> 2x2 2x2pats -rules> (1) 2x2 3x3 pats -merge> 6x6 pat
iter 3: 6x6 pat -split> (2) 3x3 2x2 pats -rules> [...]

I had exactly the same idea - keep 2x2's, 3x3's and 6x6's.

Counterexample in picture

pretty pic, what'd ya make it in?
not sure I follow what's happening tho, gon' need some more context

How the fuck is this supposed to be done?

start w/ brainlet style, just manipulate some 2d arrays (flips, rotations, splits, merges) and throw in a map/dict, et voila

Direction 0 -> 1:
Take the entire 3x3 grid, find matching rule and create 4x4 grid.

Direction 1 -> 2:
Split 4x4 grid into four 2x2's. For each 2x2 find a matching rule and expand to 3x3.

Direction 2_bottom(GOOD) -> 3_up:
Splitting 6x6 into nine 2x2's . For each finding a matching rule, expanding to 3x3s.

Direction 2_up -> 3_bottom:
Continuing from the 3x3 from previous step, we expand it into 4x4 by matching rule.

In the two 9x9's created with two different methods you can clearly see discrepancy between activated almonds: [up=9, down=8] which means these are not isomorphic/permutation of each other and will continue to yield different results from this point on.

And here's what my result looks like after 19 iterations because it's much more interesting than 18.

Could just play white noise on TV and get the same result without waiting for 2197x2197 elements to calculate.

You can however very easily detect these cases:
Starting at t=0:

t mod 3 == 0 : expand 2x2's from previous t
t mod 3 == 1 : split 4x4 into 2x2's and use those
t mod 3 == 2 : merge 3x3's from previous t into 6x6, split the total grid into 2x2s

>In the two 9x9's created with two different methods you can clearly see discrepancy
oh yeah, I assume it'd have to be a very carefully crafted input to give identical results in both cases (first split-2 / first split-3), hence why I followed the problem statement exactly:
>If the size is evenly divisible by 2, [do split-2]
>Otherwise, the size is evenly divisible by 3, [do split-3]

...

wonder how much do we gain for going with 3x the code tho

Can't believe I fucked it up after double checking:

t mod 3 == 0 : use 3x3's (expanded 2x2's from previous t) to match rule
t mod 3 == 1 : split 4x4 (expanded 3x3 from previous t) into 2x2's and match rule
t mod 3 == 2 : merge 3x3's from previous t, split the total grid into 2x2's and match rule

Needs more fucks, there were at least a lot in the thread.

case in point :V

Seems like patterns "repeat" (they're not exactly the same but have similar properties) every 3 iterations.

I don't know, but I think any method which does not discern between these three cases will fail to correctly propagate the value.

oh, you're probably right about that. I was thinking about the pros/cons vs the brainlet way

PROS: less memory. For t iterations we'll need around t * 9 * |rules| as opposed to brainlet exponential memory bomb. Faster, probably, since we don't have to do matchings we've already done before.

interesting to see what space/time that'll translate to when/if implemented

But inbetween each triple step you still need to store the matrix, so it's still expspace, isn't it?

When? I don't see when I'd need to store the matrix. I'd have to create at most one 6x6 matrix at the same time if would be implemented in a straightforward way.

Wew that was not easy.

Almost had to throw in the towel there

>almost 17 hours and haven't finished yet
should I just drop programming all together?

what's a good hobby for brainlets?

>what's a good hobby for brainlets?
browse Sup Forums

>tfw seeing other people's code that execute for 30000 iterations in 0.300s

seconding this

just turn the pic on canvas into loss edit

Brainlet solution, working on ghostbin.com/paste/uu74s
Sadly Cloudflare, uMatrix and reCaptcha are a dangerous mix.

I opened the link and a stargate activated nearby.

out of all the FUCK problems, this one has been by far the most FUCK

```rust
rustc -C target-cpu=native
```
This will compile for your native cpu (instead of a generic x86-64 or whatever).

Gives a decent speedup sometimes, but usually you can speed it up using a better algorithm first.

Yeah. I easily spent more time on this one than any other.

>seems like patterns "repeat"

>what is a fractal?

brainlet tripfag btfo

>yesterday's problem kicked my ass due to rounding errors from solving quadratics
>still in a bad mood, go turbo pajeet today because I have other shit to do
>get reasonable answer for part 2
>"Your solution was incorrect" blah blah blah
>finally give in and look up other people's inputs
>try 3, get the right answer on each
>maybe it's a glitch-
fn flip_v(&self) -> [T; 9] {
[self[6], self[7], self[8], self[3], self[4], self[5], self[6], self[7], self[8]]
}

serves me right.

better late than never
some sloppy code reuse here, but it's relatively quick for pypy (2secs)

pastebin.com/p1AKRPnZ

You have 4 days left to shoehorn in a loss

FINALLY, it is complete. ∼150ms is its running time for pt2.

ghostbin.com/paste/ob2cj

Also apparently CSS is borked again now.

>CSS is borked again
Ctrl-F5

Jesus Christ, where can I learn these moonrunes? My solution takes 2400 ms and is five times as long.

pastebin.com/ihFynbwW

>and is five times as long.
maybe, but it took you 1/100th the time to write
priorities, yo

Fucking hell

Working on day1 i need to input a multi digit integer into a single digit array. I tried stack overload and the gave me code of pic related

When i run it it crashes on int.Parse(i.ToString())
Any idea Sup Forums?

Probably because the strings "C", ":"; "\"; etc are not valid integers

do you have node installed?

this what I've been using to load files

let fs = require('fs')

fs.readFile('./input.txt', 'utf8', function (err, data) {
if (err) {
return console.log(err)
}
main(data.split('\r\n'))
})


just put the input file in the same folder than your script and you are good to go.
Also some inputs are formatted differently than the standard line per entry, so you have to change the value of the split function accordingly.

right, i cant actually input the number there as its way to large, its 8 followed by 2,189 zeros

waitt a minute, this is no javascript, nvm

Is that C#? You'll want File.ReadAllBytes() from System.IO.

tis c#, i have no idea what the best way to input this number is

How would i use that to fill an array?

oh boy

i create an array, put the file path in and it throws me an error for every \

what about trying something like
@"C:\\Users\\You\\Desktop\\input.txt"

double backslash (\\) if is not clear enough..

ahh i just needed \\

protip: you can just use forward slashes instead

The @ in C# signifies an escaped string, that can't be it. Don't you want to read from the file? System.IO.File.ReadAllLines or something

So using this to fill my array, i get 50 returned as my first value instead of 8

Dude, come on. Work through some tutorials first so you at least know the basics. Also, 50 is the ascii code for the character '2'. I assume that's the second character of your input?

Right this is spitting out ascii code now

Neat.

nuMale

reTard

TIME TO SMOKE 10 CIGARETTES TO CALM MY NERVES

TWELVE MINUTES
SMOKE FASTER user

...

IT'S HERE

Just finished my memoization solution for day 21 and it computes instantly

from itertools import product

def memoize(f):
memo = {}
def helper(*args):
if args not in memo:
memo[args] = f(*args)
return memo[args]
return helper

def AOC21(file):
pattern_to_canon = dict()
canon_to_rule = dict()
def rotations(pattern):
for i in range(2):
pattern = tuple(row[::-1] for row in pattern)
for i in range(4):
pattern = tuple(''.join(row[::-1]) for row in zip(*pattern))
yield pattern
for line in file:
canon, rule = (tuple(x.split('/')) for x in line.split()[::2])
canon_to_rule[canon] = rule
for pattern in rotations(canon):
pattern_to_canon[pattern] = canon

@memoize
def transform(pattern, n):
while True:
if n == 0:
return ''.join(pattern).count('#')
if len(pattern) % 2 == 0:
L, a, b = len(pattern)//2, 2, 3
else:
L, a, b = len(pattern)//3, 3, 4
newpattern = ['' for _ in range(b*L)]
for i,j in product(range(0, a*L, a), repeat=2):
grid = tuple(pattern[j+x][i:i+a] for x in range(a))
new = canon_to_rule[pattern_to_canon[grid]]
for x, line in enumerate(new):
newpattern[j//a*b+x] += line
pattern = tuple(newpattern)
n -= 1

if n == 0 or len(pattern)%2 == 0: continue
total = 0
L = len(pattern)//3
for i,j in product(range(0, 3*L, 3), repeat=2):
grid = tuple(pattern[j+x][i:i+3] for x in range(3))
total += transform(grid, n)
return total

init = tuple('.#./..#/###'.split('/'))
for x in 5,18:
yield transform(init, x)

with open("test_cases/21.txt") as file:
print(list(AOC21(file)))

I cound't even finish day 21, I feel like such a fraud..

ARE YOU READY

Nope

FUCK

NOT AGAIN
F#.#
#U.#
.#C.
###K

LANGTON'S ANT

Where the fuck does the carrier start and what direction is it facing in my input?