/aocg/ - Advent of Code 2018 General #32

This was a terrible mistake

Attached: file.png (857x50, 8K)

pastebin.com/mJiC8Xkk

What am I doing wrong?

rewrite it in rust

n!/r!(n-r)!
You'll need about 504 times the amount of memory than you had to solve part 1.
I doubt anyone has that amount of memory.

>python.exe
Come on user, I can't even get

Am I a brainlet?

Attached: Capture.png (526x541, 26K)

1 - > 7101012451, 2 (0.003 dict, 0.003 list)
12 -> 8916779251, 6 (0.003 dict, 0.003 list)
123 -> 1012616118, 780 (0.004 dict, 0.004 list)
1234 -> 1616971110, 10000 (0.018 dict, 0.016 list)
12345 -> 0915181111, 24997 (0.044 dict, 0.035 list)
123456 -> 1371276618, 450697 (0.831 dict, 0.600 list)
1234567 -> 1210161461, 2265190 (4.205 dict, 2.993 list)
12345678 ->5103410841, 57373003 (114.175 dict, 81.471 list)

the real way to approach it is "how do you make a 123456789 sequence?"
oh shut up

It's actually only about 1.3gb if you use 8bit integers.

Yes

>oh shut up
How well does yours perform?
# time pypy3 prob14.py 12345678
57373003

real 0m9.462s
user 0m0.000s
sys 0m0.016s

can someone explain to me what task 2 wants? i dont understand it

Cpython is slow.
# time python prob14.py 12345678
57373003

real 1m31.110s
user 1m27.515s
sys 0m3.250s

With bytearrays:
# time pypy3 prob14.py 12345678
57373003

real 0m4.407s
user 0m0.000s
sys 0m0.015s

But CPython had less speedup.

# time python prob14.py 12345678
57373003

real 1m19.981s
user 1m19.562s
sys 0m0.421s

Thanks for the idea, user. Maybe I can do 123456789 (probably not though).

>use circular linked list from day 9
>task almost solves itself

the index of the first instance of your input in the scoreboard

Sounds a bit heavyweight for a task where an array/array-like list and the modulo operator would do.

I'm up to chapter 8 of automate the boring stuff with python.
Should I even bother attempting this or am I going to embarrass myself?

>using a linked list when you're only appending

>appending values to a circular linked list

Attached: 035.png (457x472, 198K)

so if my input is 123
my recipe list looks like this:
7 3 0 1 8 9 2 1 2 3
i have to find 123 in the list and give back the index of the first digit?
index = 6?

Go for it. Just woke up and did both parts in ~20 minutes. Felt like a day 2 or 3 level problem

Meant to reply to

I get 1326928999 in about 36 seconds. Is this possibly correct?

This problem has had the worst wording yet so far. I was so fucking confused what the input was I had to come here to get it explained.
In part one I was putting my input as the starting array instead of always using 37.

yes but no
you're basically returning the length of the array to the left of the first instance of your input in the scoreboard, which is basically the index at which it starts
your scoreboard, however, is wrong, and your result should be 780, not 6
the first 20 items in the scoreboard are 3, 7, 1, 0, 1, 0, 1, 2, 4, 5, 1, 5, 8, 9, 1, 6, 7, 7, 9, 2 in that order

For anyone having issues with part 2, add this as a test: input = 15891, result = 10

That's correct.

>36 seconds
Nice. What language?

go with byte arrays

I did use bytearray in python and it still runs out of memory. Automatic cythonization still loses to pypy, perhaps unsurprisingly, and I couldn't find an easy way to cythonize more. .

A

WHOLE

FUCKING

HOUR

The only way I could understand the problem was to keep writing code until it matched the examples.
People who solved any part of today within 15 minutes are obviously cheating, because you can't untangle the word mess within that time span.

Learn to read nigga

youtube.com/watch?v=bFtcLJVN8yg

I'm curious what people in the top 20 of the private leaderboard are using. If you are top 20 post user number and language / editor.

Python / spyder / windows 7

#204638 / Go / Acme

Vorname Nachname / python / VS-Code / arch

Actually I misspoke, with the bytearray cythonization becomes possible. Still 4 times slower than pypy for 12345678, but a massive improvement.

is first place user still doing this

Can someone share his input and solution for task 1 and 2?

Yeah, I've tried that already. Terrible idea.

Wow, I'm retarded. I read that as advice to "go with bytearrays," rather than the language Go. Thanks for the answer user.

Your puzzle input was 440231.
Your puzzle answer was 1052903161.
Your puzzle answer was 20165504.

Some mathy thought about part2:
Once the scoreboard is long enough, the path starting from the first 9 scores will eventually converge. This means that the elves always jump over most of the scores on the scoreboard (about ~80% ?), this considerably lowers the memory requirement. Are there any solutions that makes use of this?

*first 10 scores, damn off by one.

Haskell is fun!
{-# LANGUAGE PartialTypeSignatures, ViewPatterns #-}
module Main where

import qualified Data.Sequence as S
import Data.Char (digitToInt)
import Data.Digits (digits)

type State = (Series, Int, Int)
type Series = S.Seq Int

main :: IO ()
main = do
let subseq = map digitToInt input; input = "030121"
let (_, nums) = (head.filter fst.map (match subseq 7)) sets
putStrLn $ "Silver: " ++ concatMap show (S.take 10 $ S.drop
(read input) nums); putStrLn $ "Gold: " ++ (show.length) nums

sets :: [State]
sets = iterate next (S.fromList [3,7], 1, 0)

next :: State -> State
next (xs, u, v) = (xs', f' u, f' v) where
xs' = foldl (S.|>) xs (if null ys then [0] else ys)
f' j = mod (j + 1 + ret j) $length xs'
ys = digits 10 (ret u + ret v)
ret = S.index xs

match :: [Int] -> Int -> State -> (Bool, Series)
match str i (S.viewr -> S.EmptyR, u, v) = (False, S.empty)
match str i (S.viewr -> xs S.:> x, u, v)
| last (-1:str) == x = match (init str) (i-1) (xs, u, v)
| i > 6 = match str (i-1) (xs, u, v)
| otherwise = (null str, xs S.|> x)

Attached: Crudely Drawn.png (500x667, 541K)

mine also runs in 41 seconds, dunno about mem tho
u, v, xs, code = 0, 1, [3,7], "030121"
fmt = lambda x: "".join(map(str,x))
while(code not in fmt(xs[-7:])):
xs += [*map(int, f"{xs[u] + xs[v]}")]
u,v = (u+xs[u]+1)%len(xs), (v+xs[v]+1)%len(xs)
offset = 6 if int(code[-1]) == xs[-1] else 7
print('Silver:', fmt(xs[int(code):][:10]))
print('Gold:', len(xs) - offset)

Attached: Drunk Chibi.jpg (1500x1500, 438K)

it worked for me at first try and it was fast enough

How's it been so far, /aocg/?

Attached: file.png (602x384, 46K)

this

I reached for a linked list the moment I saw a growing list and iterators on it. No time for reading the problem and understanding that you only append to the scoreboard.

thanks for making me feel better

Attached: adventofscore.png (617x413, 37K)

Eh, why the heck not.
I'm not really competing for the score at this point anyway.
I didn't have any problems with the tasks so far, but I'm really slow with everything. If anything AoC should pressure me into working on my speed.
How do I become faster?

Attached: Screenshot_2018-12-14_13-36-28.png (611x393, 60K)

Starting at midnight is really hampering my ability to win fake internet points.

Attached: 1521784770876.png (1166x812, 180K)

no discipline to get up at 6am..
still top 20

Attached: DeepinScreenshot_select-area_20181214134231.png (602x384, 36K)

It's been comfy.

Attached: Capture+_2018-12-14-07-43-08.png (1407x949, 201K)

How the fuck are you supposed to be in the top 100? Do you have to solve every problem sub 5 minutes?

I guess you have to be well-prepared. workflow wise and also practice,practice,practice.
like /ourguy/ said, any problem he comes across, he has already seen once or twice in almost the same form.
and I guess being highly integlligent also helps

You can look at the per-problem leaderboards to see how fast you would have needed to solve each problem to get points.

why would you want to? competitive programming is a meme only 3rd worlders are interested in that has no real world usefulness

Who is /ourguy/ and what did he say?

Also if using an array for part 2 you have to reallocate somehow, since you dont know in advance when you gonna find the sequence

anonymous user #193354
(first on Jow Forums leaderboard and third global)
and he said programming has been his only major hobby since he was ten and he has done lots of competitions.

What programming language does he use?

it's a hobby. you could say the same about "competitive ultimate frisbee" having no real world usefulness.

std::vector have an amortized O(1) push_back(). It reallocates every time it reaches 2^n+1 elements (in libstdc++). std::deque is also a good candidate, it doesn't need reallocation, but has other problems.

as far as I know mostly python. he mentioned C once.

TIL using the encapsulating classes for primitives in Java removes any memory efficiency you might have had.

Attached: bigboi.png (208x48, 3K)

I think I might be one of the few people doing this in Erlang.

>only 3rd worlders are interested in
well, what if I'm a 3rd world shit eater?

Same DESU senpai

Attached: 1500917096107.jpg (1280x720, 147K)

t. too stoopid to rank sub 1000 on any problem

Like the other user said, you can just use a data structure that reallocates your scoreboard. Do make sure you use an iterator or index that moves with the scoreboard.
Or allocate 1GB and be done with it, because if that's not enough you are doing it wrong.

i already know about that, but i guess its some kind of autism that makes me want to do every task with as little stdlib as possible, hence my list implementation came up as the idea for this one

it's a pity this thread slumbers during the day
where are my eurobros and american neets at?

Writing shitcode rather than shitposts

I'm here. I just don't really have anything to add.
Well, maybe if you want to see and review my shitcode, then feel free to do so:
pastebin.com/xmVzcW7w

>tfw not filtered yet

im gonna make it this year boyos

also all of this "node" bs is leftover from when I tried to implement it with a cyclic list for fun & giggles (boy, it didn't go well)
lesson learned: constant factor optimizations matter

-------Part 1-------- -------Part 2--------
Day Time Rank Score Time Rank Score
14 00:19:32 504 0 00:33:42 371 0
13 01:14:21 693 0 01:29:02 525 0
12 00:34:18 596 0 00:47:03 368 0
11 00:25:17 1092 0 00:31:26 463 0
10 00:49:35 953 0 00:52:02 963 0
9 00:44:51 829 0 01:14:23 623 0
8 00:11:30 278 0 00:15:38 186 0
7 00:43:46 1190 0 02:20:00 1518 0
6 02:04:56 2113 0 02:15:28 1904 0
5 00:38:01 2076 0 00:44:49 1538 0
4 00:47:44 990 0 00:49:12 790 0
3 00:18:06 823 0 00:20:56 553 0
2 00:03:58 145 0 00:09:25 155 0
1 03:43:11 4834 0 03:55:51 3735 0

>so much better than me and still 0 points

that's why we have a local leaderboard

Can someone explain to me with simple english what task 2 is looking for?

Basically run the recipe algorithm until the digits of the number you were given appear in it, then return the number of digits before that.

Keep adding more scores (numbers) to the scoreboard until you hit the pattern that's asked.
return how many scores have been given before (are to the left of) the pattern.
That's why "01245" results in "5": the scores 0,1,2,4,5 appear consecutively after 3,7,1,0,1 (the first 5 scores) on the scoreboard.

Thank you very much!

>because you can't untangle the word mess within that time span.
I've had that issue with a few of his past questions. Worst was counting the plant pots on day 12 I believe. It sounded like total cumulative plants found throughout all generations. No he wanted the sum of the "indexes" of the plant pots on the final generation.

The other one was that marble game where they tell you the marbles are "placed in a circle". I thought they were putting marbles in a circle drawn on the ground or something. He meant that if you get to the end of your marbles you loop around to the start again.

I didn't have too much of a problem today though.

% time ( ./a.out

Attached: DuW9X-4UYAAdqOC.jpg (554x942, 73K)

fn main() {
let input = "084601";

let offset: usize = input.parse().unwrap();
let search: Vec = input.chars().map(|c| c.to_digit(10).unwrap() as u8).collect();

let mut scoreboard: Vec = vec![3, 7];

let mut elf1 = 0;
let mut elf2 = 1;

loop {
let rcp1 = scoreboard[elf1];
let rcp2 = scoreboard[elf2];
let next = rcp1 + rcp2;

if next >= 10 {
scoreboard.push(next / 10);
if scoreboard.ends_with(&search) {
break;
}
}

scoreboard.push(next % 10);

if scoreboard.ends_with(&search) {
break;
}

elf1 = (elf1 + rcp1 as usize + 1) % scoreboard.len();
elf2 = (elf2 + rcp2 as usize + 1) % scoreboard.len();
}

let part1: String = scoreboard[offset..offset + 10]
.iter()
.map(|e| e.to_string())
.collect();

let part2 = scoreboard.len() - search.len();

println!("{} {}", part1, part2);
}

is there a better way to measure mem usage than GNU/Linux time??

$ /usr/bin/time -v ./target/release/day14
2688510125 20188250
Command being timed: "./target/release/day14"
User time (seconds): 0.51
System time (seconds): 0.01
Percent of CPU this job got: 99%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.52
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 21564
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 0
Minor (reclaiming a frame) page faults: 5056
[...]
Page size (bytes): 4096
Exit status: 0

21MB BOIS

My English ain't very good.
What is the second part asking?

>ain't
not a word

english is the only language I speak and I had to read it 10 times myself

if your input is 12345
output how many digits there are before "12345" appears