/aocg/ - Advent of Code 2018 General #26:

graph of times of the top20 updated for day 9.

Attached: finishing_times.png (1920x1008, 371K)

For anyone interested posting my picture.
To user calling me brainlet for not being able to scale text well - I am not UI/graphical design faggot.

Attached: treeFinal2.2.png (1057x1002, 653K)

Someone really lost a disk with bigboy?

Can someone update the calendar?

Uh lads my code is still running, how long is this going to take? Am i reading the challenge right for part two?

Implement a linked list

or a circular list by using a double linked list

That's still a linked list.

Yes and no.

more or less... read I have not seen updated calendar for last 3 days. I did see someone post pictures for yesterday and day before that today I think.

>int remove = circle[circle[circle[circle[circle[circle[circle[current].prev].prev].prev].prev].prev].prev;

Attached: 1392042529961.jpg (500x600, 82K)

i ran out of memory user

Bigboy or regular input?

i got the pics for day6, 7 and 8 if you have the calendar

post them so they are easier to find for someone with calendar... since I do not have it :(

big boy part 2

i doubled my page file now

You should use another alg.

>forgot to make my DLL circular
>cant even get back 7 steps from 92

fuck this ugly faggot

Attached: uglyfaggot.jpg (400x400, 19K)

Attached: cal.png (10000x10000, 2.67M)

>my comment in day 6 and my picture in day9
I am doing pretty well in this aoc!

You're lucky. I want to be in that calendar.

love u bby

It's my mission to make it into as many as possible, so far I've made it into 5 of them.

god damn it. Good job user. Really impressive

Once the circle has more than 23 marbles (after two cycles), a single cycle has the form
>extract 23 marbles c_0,..,c_22 from the circle, leaving a link to the previous marble p and next marble n
>have new marbles m_0,..,m_22
>generate lists ps = c_0,m_0,..,m_18 and ns = m,_19,c_20,m_20,c_21,m_21,c_22
>append ps to p and prepend ns to n
>add the score c_19+m_22 to a player marble%23

This can be implemented with an unrolled linked list and should perform a lot faster than any step-based solution, while having little overhead compared to . To minimize list operations, don't store the 6 marbles in front but use them directly in the next iteration. To minimize malloc calls, reserve a large pool of {nextptr, grabbedUpTo, marble[38]} structs to quickly save those 38 marbles that are pushed to the back. Or, instead of having a pool, process 2^k cycles at once, though you'll waste a third of your memory. And no need to be precise in the number of turns at the end, because only every 23rd turn counts.
Moreover, at every point when you have m marbles, you can process up to m/23 parts in parallel because any marble c will either map to ps or ns (which are definitely mapped to the ps of the next cycle) or disappear, so you can multithread for what that's worth.

Then again, I can fill 64GB of zero-overhead marble pointers in a minute, so more speed is not that important.

* 1/23rd overhead because I never free the removed marbles

Part 2 run time 0.141 ms, ahahahah C++ strikes again, you can't do shit this fast in python that's for sure

Attached: ss.png (309x154, 3K)

Why does Rust think fundamental data structures are dangerous?

What is your input?

number of players 468
last marble 7101000

I do it in 50ms with my C code.

Oh, I'm sure there's an LLVM binding for Python out there. It's cute that you think there's anything unique about your programming language. Typical C++ fag completely ignorant about the modern world of programming. At leas C-fags KNOW what they'd be losing if they used a more abstract language. You C++ fags just think "muh speed" even though fucking plain old Javascript can run on your magnitude these days.

found the weblet

ok basically I suck massive dongs.
compiling to release makes Crystal with bigboy input a whole lot faster

Attached: aoc9bigboycrystalrelease.png (576x123, 26K)

only took 120m with my python code. basically the same.

120 minutes?

Wish I wasn't a britbong so I could get in on that 5am action

Inaccurate. Font-end's very specialized these days. It's more UX than what you would traditionally call traditional "programming" (i.e. algorithms and processing) these days. More framework-based and tool-based. For the most part, anyway. There are some websited that are basically just full-on web-based applications (some more successfully than others).

shut up and go write a medium article or something you weblet
enjoy your virtual machine

the c++ code I wrote compiles on gcc if I remove my iostream references and typedef my struct (or I could just refer to it as the long name). I'm sure if you ran my code on your computer it would also be 50ms.

Apart from the shittily worded part 2 (thought the last marble had a custom score, rather than that it was about 100x more marbles), today's is super easy with a doubly linked list.

Runtimes are also fairly decent without actually putting any effort in (and I'm doing it in slow ass java as well)

MarbleMania: [9/25] MarbleMania
MarbleMania: Part 1 -> [367634] (16 ms)
MarbleMania: Part 2 -> [3020072891] (173 ms)

173 minutes, java btfo

no 'ms' is centuries, for about a fifth of a millenium ; ezpz

>141ms
Look who's made out of time here

Attached: 1528155851888.png (874x140, 33K)

you got a different answer for the second part compared to

One small improvement later and getting sub-100ms (although is still faster but hey) on part 2.
poojet java can shit faster than the C++ fag can swallow his own cum it seems

Attached: cpp_fags_lul.png (908x66, 15K)

>attempt to use my function on examples
>(9, 25) -> 32
good so far
>(10, 1618) -> 8317
oh shit looks like i got it
>(13, 7999) -> 146071
wait what, oh no
>(17, 1104) -> 2764
wait but everything else is correct?
>(21, 6111) -> 54718
i dont understand what could have gone wrong
>(30, 5807) -> 37305
fuck it i'll just try it on the input and submit hoping for the best
>too high
guess today is my brainlet filter lads

You're right haha!
Forgot to change UInt32 to UInt64 in scores array

Attached: aoc9bigboycrystalrelease2.png (280x66, 9K)

20s for part 2 in python. Feels bad

there must be a O(1) solution

try pypy

use a linked list, store scores in an array not a list. also you get fucked by python arbitrary numbers probably

I used a doubly-linked list and stored my scores in a dict. I am a brainlet

Hopefully they do an interpreter puzzle soon so I can make mine a compiler for the hell of it

That's what I was thinking about last night but I'm a math brainlet

yep just go from dict to array and you'll already get a way faster run. then use pypy as per 's recommendation and down you go

pypy brings it down to 3s. Neato

I wonder how fast an unrolled linked list solution could be

someone please help
pastebin.com/4NDLs3Lr

Don't feel bad, you in the top

Attached: day09.png (700x227, 19K)

that's hot fucking garbage of a metric tho, top % of those that made it have code and solutions that work usually better than the rest of those that passed

ok so i'm not usually one to complain about imaged being cluttered with too much shit, but goddam this is on a whole other level

Brainlet here, stuck on day 2 challenge 1. I barely know regular expressions and thought that it's a good way to make myself learn them, but now I'm not sure if regex can do what I want.
I want to test a string to see if any letter from range [a-z] appears exactly 2 times {2} globally. Halp?

Attached: 1105553.jpg (640x480, 28K)

hint on how to save 1 pointer in the struct for node

Attached: xor-doubly-linked-list.png (1336x148, 37K)

this is a poor problem for a regex
don't use them

why bother, use an unrolled linked list with say 32 elements in a chunk, so you use only 1/32th of the memory on pointers versus a regular doubly linked list.

should be much faster due to better cache usage as well

that would require context-free parser
meaning PCRE could do it

Out of all the problems day 9 looks like stupid busywork.

> regular expressions parsing a context-free grammar

just because you can (by changing definitions) doesn't mean you should

but you can, that's what makes PCRE special (not in a good way)

Fuck it, I'll just sort the string alphabetically and loop over it to see if there are consecutive characters matching my needs. Brainlet solution is better than nothing.

Attached: 366482.jpg (640x480, 50K)

I bet a lot of regex implementations can do the same kind of thing, you could use backreferences I think?

but I wish they all called themselves regexes at least, instead of regular expressions (PCRE is perl-compatible regular expressions, no?)

that's a better solution in my opinion. getting in the habit of using stuff like backreferences is just a bad idea

backreferences make it context-free and not regular anymore

My 45ms code is in the last thread if you want to do a comparison on your machine.

I know.. that's what my whole point is. There's no efficient ( O(n) ) way to implement backreferences and it ignores the whole theory behind regular expressions in the first place, so I don't like them.

Can you post your code? Mine runs in 900 ms with 412 players and 71646 as the last marble:
void rotate_iterator(std::list& circle, std::list::iterator& it, int n)
{
if (n > 0) {
while (n-- > 0) {
if (it == circle.end())
it = circle.begin();
std::advance(it, 1);
}

if (it == circle.end())
it = circle.begin();

}
else if (n < 0) {
n = std::abs(n);
while (n-- > 0) {
if (it == circle.begin())
it = circle.end();
std::advance(it, -1);
}
}
}

uint32_t solve_part_two()
{
const uint32_t LAST_MARBLE2 = 100 * LAST_MARBLE;
std::vector player_scores((NPLAYERS));

std::list circle{ 0 };
auto curr_marble_it = circle.begin();
int curr_marble_pos = 0;
for (uint32_t i = 0; i < LAST_MARBLE2; ++i) {
if ((i + 1) % 23 == 0) {
rotate_iterator(circle, curr_marble_it, -7);
player_scores[i % NPLAYERS] += i + 1 + *curr_marble_it;
curr_marble_it = circle.erase(curr_marble_it);
if (curr_marble_it == circle.end())
curr_marble_it = circle.begin();
}
else {
rotate_iterator(circle, curr_marble_it, 2);
curr_marble_it = circle.insert(curr_marble_it, i + 1);
}
}

return *std::max_element(player_scores.begin(), player_scores.end());
}

I don't see any order of magnitude improvements I could use. Are you using a list?

I mean I understand it might be my processor being shit.

$ gcc -O3 -Wall -g -std=c11 c9.c && time ./a.out
Part1: 699538051
part2: 6900405220103
./a.out 2.50s user 0.64s system 99% cpu 3.141 total

size_t n_players;
size_t marbles;
std::string ignore;
std::unordered_map player_scores;

std::cin >> n_players
>> ignore >> ignore >> ignore >> ignore >> ignore
>> marbles
>> ignore;

What's a better way to parse the input in C++?

use scanf

use scanf

Hold the fuck up. If you're using scanf (or any other variant) then why not just use pure C? What's the point of using C++ if not for the safety it provides?

>not -Ofast -march=native

Ideally I want the input to come from a file, so would I have to open the file, get the line into a *char and then pass it to scanf? (If I don't want to use a file pointer)

std::string input;
std::cin >> input
sscanf(input.data, [...]);

safety!

fscanf()

read a string from an ifstream and parse it with sscanf

Scanf is slow. If you use scanf, you'll spend most of your run time in scanf for the big-boy input. This was discussed yesterday - the fastest solution wrote custom input parsing.
It's easiest to read from stdin. This way, you can read from both a file via shell redirection and from, well, standard input.

that may be true, but it hardly matters for this problem where you just need to read two numbers once at the beginning

thanks, didn't make it faster but I'll remember it

you could also use -Wpedantic to see possible errors