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

clockwise = right = forward = next
counter-clockwise = left = back = previous

What you should have learned so far:
>day1: sets or hashmaps
>day4: reading the instructions
>day5: stacks, push and pop
>day6: L1 norm
>day7: topological sorting
>day8: tree recursion
>day9: linked lists

Attached: 1540637261137.png (515x487, 420K)

based, thank you

wasn't there also something with graphs that they couldn't do yesterday? imagine using a meme language unironically lmao

>day4: reading the instructions
I used a grid. What kinds of CS concept is that?

>day8: tree recursion
>day9: linked lists
I learnt shit since I implement all of above using arrays

Fuck me. Rust iterators CANNOT MOVE BACKWARDS.

There is no prev() for an IterMut on the Linked List.

Even though you can O(1) insert with insert_next(), you can't move backwards on the 23.

Took me ages in Haskell, hand rolled a zipper to model the ring of marbles, shifts focus in amortized O(1), insert and remove are both O(1).

Attached: zipper.png (834x950, 53K)

>day 1: sets
>day 5: stacks
>tfw didn't do either

Attached: sundowner.jpg (500x540, 58K)

they can't in C++ either
you need a reverse iterator for that

Python solution using blist. The index math is messy, but it executes in 4 seconds.

def solve(playerCount, endScore):
from blist import blist
score = [0]*int(playerCount)
state, stateLen = blist([0,2,1]), 3
player = 2
old = 1
for i in range(3, endScore + 1):
if i % 23 == 0:
new = (old - 7) % stateLen
score[player] += i + state[new]
del state[new]
stateLen -= 1
old = new
else:
if (old == stateLen - 1):
new = (old + 3) % (stateLen + 1)
else:
new = (old + 2) % (stateLen + 1)
state.insert(new, i)
stateLen += 1
old = new
player = (player + 1) % len(score)
print(max(score))

Attached: jontron_it_works.jpg (807x677, 109K)

(cont.)
Chucked everything in state monad to model all the imperative stuff (score, numPlayers, marblesRemaining, etc.). Part 2 wouldn't finish in ghci, compiled it with -O3 and it finished in a minute or so.

Attached: state.png (839x1646, 92K)

What I learned:
> day 1 - 3: read instructions
> day 4: guards are lazy
> day 5: don't skip a day because ea task might appear
> day 6: muricans in manhatan are retarded.
> day 7: Read instructions CAREFULLY
> day 8: I hate recursion
> day 9: ArrayList vs custom class with pointers to next/previous - 0:1

import re
import string
import collections

with open('input.txt') as f:
lines = f.readlines()
lines = [line.strip() for line in lines]

stmt = re.sub('['+string.ascii_lowercase+';'+']', "", lines[0]).split()
stmt = [int(stmt[0]), int(stmt[1])]
print(stmt)

circle = collections.deque()
circle.append(0)
players = [0] * stmt[0]

def place_marble(player_i, value):
if value % 23 == 0:
players[player_i] += value
circle.rotate(7)
players[player_i] += circle.pop()
circle.rotate(-1)
else:
circle.rotate(-1)
circle.append(value)

i = 1
go = True
while go:
for player in range(len(players)):
place_marble(player, i)
i += 1
if i == stmt[1] * 100:
go = False
break
print(max(players))

Updated code to use deque for part 2. Would have probably been faster to let the list-based approach run than figure out how I should be using the deque. But now the big input runs about as fast as the normal input did previously.

Attached: 9part2.png (158x141, 3K)

Okay, insert_next is unstable, that's why I didn't know about it. But yeah, iterators consume elements. What we really want is a cursor, which is still stuck in RFC land.

I used arrays for both...

--iterator;

I think there's a crate for linked lists that has cursors, AND they're circular. Unfortunately, it's not a part of the stdlib. That said, my n^2 solution has been running for over an hour, so I might as well try.

>The best surprises don't even appear in the source until you unlock them for real.
what did the html comment mean by this?

>day3
Learned about defaultdict.
>day4
Learned I should read the instructions, not to overcomplicate with datetime.
>day5
That I should think about what type of data structure is good for the job.
>day7
READ THE INSTRUCTIONS CAREFULLY.
>day9
Should think about the efficiency of data structures using based on operations I will be using most often.

ty

Fuck it, I'm gonna drop down to C for this. I can't Rust a circularly linked list, and I'm not going to be trying to get my code to work with a 3 year old crate.

last year shitty """"easter eggs"""" appeared on all riddles once you finished everything.

Attached: 1542533417614.png (257x353, 101K)

I tried using this crate (github.com/4e554c4c/list_cursors), which is the reference implementation for a list cursor RFC. However, I couldn't make it work. The cursor went to None whenever I went off either end of the list. In the end I peeked at another Rust solution and it was easier to [spoiler]use a VecDeque, keep the current element at the front, and use pop_front/push_back or pop_back/push_front to rotate the list.[/spoiler]

Day 6 got nullified for private leaderboards.

Guess that explains why I fell down the order even though I did decent today.

Attached: niggers.png (799x67, 15K)

In this very special episode of Advent of Code rustards learn their language is a meme.

Show us your beautiful code, o mighty warlock, so that we may learn from it.

Could you rustlets use a hash table with each element keeping references to cw/ccw?

>nice, my C scripts solves part 1 in 7 ms
>let's try part 2
>Segmentation fault (core dumped)
REEEEEEEEEEEEEEEEEEE

Attached: twingo colérique.jpg (800x581, 91K)

java solution:

class Pos {
Pos(int val) {
this.value = val;
}
int value;
Pos next;
Pos prev;
}

@Test
public void day9_cust() {
int players = 10;
int lastMarble = 1618;
Pos node0 = new Pos(0);
Pos node1 = new Pos(1);
Pos node2 = new Pos(2);
node0.next = node2;
node0.prev = node1;
node1.next = node0;
node1.prev = node2;
node2.next = node1;
node2.prev = node0;
Pos mainNode = node2;
long[] scores = new long[players];
for (int i = 3; i < lastMarble; i++) {
if (i % 23 == 0) {
mainNode = mainNode.prev.prev.prev.prev.prev.prev.prev;
scores[i % players] = scores[i % players] + i + mainNode.value;
mainNode = mainNode.next;
mainNode.prev = mainNode.prev.prev;
mainNode.prev.next = mainNode;
} else {
mainNode = mainNode.next;
Pos newNode = new Pos(i);
Pos next = mainNode.next;
newNode.next = next;
newNode.prev = mainNode;
next.prev = newNode;
mainNode.next = newNode;
mainNode = newNode;
}
}
int mind = -1;
long max = -1;
for (int i = 0; i < scores.length; i++) {
if (scores[i] > max) {
max = scores[i];
mind = i;
}
}
System.out.println("max> " + max);
System.out.println("i> " + mind);
}

Yeah, I guess you can implement your own doubly-linked list with a HashMap. You'd probably have to store keys instead of references though. A hash map that stores references to itself sounds like lifetime hell.

try long int

>tfw quit visual studio code for the night and CPU jumped to 400% for ~15 seconds lagging my entire computer before something called Code Helper crashed

>day 1: I should read the instructions
>day 2: you gotta be awake to place
>day 3: I'm not going to implement a quadtree in 10 minutes and 2d arrays are fast enough
>day 4: lots of y'all should read the instructions better
>day 5: string slicing is fast enough for now
>day 6: when your boss fucks up, you still pay the price
>day 7: topological sorting
>days 8-9: I fuck up when I try to go fast

Attached: goingplaces.png (126x216, 2K)

Simulation is for brainlets.

OFFICIAL BIG BOY INPUT

1488 players; last marble is worth 6000000 points

Part 2 rules apply (x100 marbles). Be warned: If it takes you more than 5 minutes, you're an honorary pajeet.

Attached: lets_go.png (493x487, 183K)

#include
#include

#define PLAYERS 419
#define MAX_MARBLE 7105200

struct List {
struct List *next;
struct List *prev;
size_t value;
};

typedef struct List Marbles;

Marbles* seek_list(Marbles *list, int amount)
{
if (amount < 0) { return seek_list(list->prev, amount+1); }
else if (amount > 0) { return seek_list(list->next, amount-1); }
else { return list; }
}

Marbles* insert_list(Marbles *list, size_t value)
{
Marbles *newnode = malloc(sizeof(Marbles));

newnode->value = value;
newnode->prev = list;
newnode->next = list->next;
list->next->prev = newnode;
list->next = newnode;

return newnode;
}

Marbles* remove_list(Marbles *list)
{
Marbles *next = list->next;
next->prev = list->prev;
list->prev->next = next;
free(list);
return next;
}

int main(void)
{
size_t scores[PLAYERS] = { 0 };
Marbles *current = malloc(sizeof(Marbles));

current->value = 0;
current->prev = current;
current->next = current;

for (int i = 1; i value;
current = remove_list(current);
}
else {
current = seek_list(current, 1);
current = insert_list(current, (size_t)i);
}
}

size_t best = 0;
for (int i = 0; i < PLAYERS; i++) {
if (scores[i] > best) { best = scores[i]; }
}

printf("high score: %zu\n", best);
}

Solved in a few milliseconds more time than it took for my Rust solution to do the original problem. My C solution solves the original problem in like 3 milliseconds though.

>1488 players; last marble is worth 6000000 points
nice one. Too easy tho
result: 699538051
time taken - 343ms (measured by junit test)

>tfw 1x input already takes 20 seconds
It's python. What can you do?

>Too easy tho
It's hard enough to filter all Python users.

>Part 2 rules apply (x100 marbles)
I don't have enough RAM for this.

made my own linked list with just a dictionary that used marble number as key and list of next key/prev key as the value.

even my sloppy brainlet code takes only 9.6 seconds to run for part 2 in python

goddam it feels good to have this working after seeing that my part1 code would have needed possibly hours to do this shit. see you fags tomorrow, this is a lot of fun

Attached: feelsgoodman.png (354x363, 133K)

Haskell ft. too many imports

Attached: Code_F17Go5ZL0G.png (729x688, 84K)

Using my new C solution, 1488 players and 6,000,000 last marble, I get the following results:
time ./alt.elf
high score: 699538051

real 0m0.188s
user 0m0.116s
sys 0m0.072s

Attempting to multiply the value of the last marble by 100, I get this, however:
time ./alt.elf
Killed

real 0m14.641s
user 0m7.624s
sys 0m4.900s

It seems my 16 GiB of system memory is insufficient for such an input, particularly when it needs to be shared with processes such as Firefox.

>Part 2 rules apply (x100 marbles).

did not notice this... please wait for result....

part 1 - 7.9 seconds
part 2 - MemoryError

RIP

If you are using a 64 bit operating system, and each node in your linked list uses 2 pointers and an integer, it should take 24 bytes per node, not including allocator overhead. For 22 out of every 23 marbles, you will need a single node.

(600,000,000) * (22/23) * 24 = about 13.77 GB or 12.83 GiB.

Do you have this much memory available?

>it's an user makes a big boy input that's larger than most people's ram episode
7502964 7080576 python3 ./python.py

If you think I'm gonna write a swapfile system just to solve it, you're gonna be disappointed.

BASED PYTHON

bigboy part2

normal input part2 has about 6sec runtime for me

Attached: Capture.png (954x119, 17K)

Okay, I struggled a bit with using iterators and it took some experimentation to find out exactly what they were doing, but went:
>took 20+ minutes
>was integer overflowed on completion...
>spent the time figuring out the iterator
>fast completion, still integer overflow
>ezpz to change ints to longs
>right answer for part 2 on first input
>2.7s runtime

>C++ using iterators into a std::list
>wtf why is my shit so slow on part 2
>turns out my progress printf within my loop was slowing it down
>remove it
>now i can solve all the sample data, part 1, and part 2, in 0.503s

% cat Input.txt
10 players; last marble is worth 1618 points
13 players; last marble is worth 7999 points
17 players; last marble is worth 1104 points
21 players; last marble is worth 6111 points
30 players; last marble is worth 5807 points
424 players; last marble is worth 71144 points
424 players; last marble is worth 7114400 points
% time (./a.out < Input.txt)
10 players; last marble is worth 1618 points: high score is 8317
13 players; last marble is worth 7999 points: high score is 146373
17 players; last marble is worth 1104 points: high score is 2764
21 players; last marble is worth 6111 points: high score is 54718
30 players; last marble is worth 5807 points: high score is 37305
424 players; last marble is worth 71144 points: high score is 405143
424 players; last marble is worth 7114400 points: high score is 3411514667
( ./a.out < Input.txt; ) 0.46s user 0.05s system 99% cpu 0.508 total

Sorry for calling you a mistake std::list

>Do you have this much memory available?
32gb of godly ddr4 ram + 32gb swap
Ram use seems to have stabilized on 12.3gb (htop result, so intellij+firefox+etc+ this runing)
What concerns me more is cpu usage - all 12 cores ~100% (threads.. only 6 cores technically)

Use a VecDeque

>OFFICIAL BIG BOY INPUT
>1488 players; last marble is worth 6000000 points
[Part 2] Players: 1488 Marbles: 600000000 Elf's Score = 6900405220103

>people complaining about deque being slow

Isn't the whole point of using a deque is to rotate it so you can do all your item manipulation exclusively on the ends? Does the implementation of deque you're using not have rotate? If so, just do q.push_front(q.pop_back) or q.push_back(q.pop_front) instead

1488 players; last marble is worth 6000000 points: high score is 699538051
( ./a.out < BigBoy.txt; ) 0.42s user 0.08s system 99% cpu 0.493 total

some "big boy"

C++ wins again

Attached: kitty_2018-12-09_03-19-01.png (820x803, 627K)

Using my Python code in :

6900405220103
Time: 1693.49 seconds

You're running part 1.

>6000000
x 100 sweaty

Takes 2-3 minutes in pypy.

Big boy part 2 sure is concerning me more than I thought it would with how long it's taking to run.
I might try this in C and see how fast I can really get it to go now that the logic is settled.

I just added two 00s to the input rather than manually do x100 in my code.

Here's part 2 running on my 64gb ddr4 workstation

time (cat BigBoy.txt| ./a.out)
1488 players; last marble is worth 600000000 points: high score is 6900405220103
( cat BigBoy.txt | ./a.out; ) 21.74s user 4.45s system 99% cpu 26.237 total

oeis.org/search?q=9,17,11,15,50,58,66&sort=&language=english&go=Search
>Sorry, but the terms do not match anything in the table.

Boooo! I want a formula for the popped marble, not simulate the whole circle.

Scratch that, it took around 1.5 seconds for each 1/100 tick, but it ran out of memory first. Let me try it in 64 bit python

man you guys are losers. i've been coding literally 3 months and all of these took me

>21 seconds
How will interpreted languages ever recover?

Attached: rosen_nice.gif (320x260, 962K)

Try replacing 23 with a smaller value and seeing if those patterns exist.

probably a situation like "man, you bridge-builders are losers. I threw some toilet paper across the river and it only took me a few minutes."

highest score 6900405220103

real 0m9,822s
user 0m6,103s
sys 0m4,079s

although it doesn't work every time, sometimes it can't allocate enough memory. I wonder why it's not deterministic.

It took me a similar amount of time to write up my C solution. Some of us are trying to challenge ourselves. In my case, trying to learn Rust. Unfortunately, circularly linked lists in Rust are a fucking no no. At least not without abusing the hell out of unsafe.

Smaller prime, in particular
Important that it's prime

beat you on 6mil (316ms, max 168MB max RSS), but lost out on 600mil (35s, 7.3G max RSS).
I guess I should actually free these deleted nodes...

There are no real-world challenges that require more than a passing knowledge of programming. That's why serious CS courses focus more on project management and social networking.

Why?

>tfw if i had used doubly-linkedlist from the start would have been much easier because no more BS with list index and modulus

It is over 21 min... java is still computing

My original was on an i3-6100 which took 0.5
The big boy part 2 was on my workstation which has an i9-7900x with 64gb of ram so my part 1 will be different on the workstation.
Good job though Im totally at the mercy of standard structure implementations and some circular iterator logic

Every number divides into a prime uniquely. Which is why they picked a prime number rather than some number like 32 where it would make it an almost entirely analytical problem without the need of a linked list

I just bruteforced it and let my script run while I was eating breakfast

what the fuck is that font

Proggy fonts on a 4k screen deal with it

6900405220103
41612ms

but my processor is 10 years old, so...

nice pajeet CPU

man, it was a good deal
got it for free from microcenter with a coupon that had no purchase necessary
literally too good to pass up

Python3.7 on Windows:
699538051
1.56 seconds
6900405220103
436.34 seconds

pypy:
699538051
0.78 seconds
RPython traceback:
File "rpython_jit_metainterp.c", line 7949, in handle_jitexception_4
File "pypy_module_pypyjit.c", line 112, in portal_4
File "pypy_interpreter_1.c", line 18686, in handle_bytecode__AccessDirect_None
File "pypy_module_pypyjit.c", line 982, in jump_absolute__AccessDirect_None
File "rpython_jit_metainterp_1.c", line 10106, in crash_in_jit_53
out of memory: couldn't allocate the next arena

#include
#include

#define PLAYERS 462
#define MARBLES 7193800

struct node {
struct node *next;
struct node *prev;
int value;
};

typedef struct node marble;

int main() {
long scores[PLAYERS] = {0};
size_t i_player = 0;
marble *current = malloc(sizeof(marble));
current->value = 0;
current->next = current;
current->prev = current;

for (int k = 1; k < MARBLES; k++) {
i_player = (i_player + 1)%PLAYERS;
if (k%23 == 0) {
scores[i_player] += k;
for (int i = 0; i < 7; i++) current = current->prev;
scores[i_player] += current->value;
current->prev->next = current->next;
current->next->prev = current->prev;
current = current->next;
}
else {
current = current->next;
marble *new = malloc(sizeof(marble));
new->value = k;
new->next = current->next;
new->prev = current;
current->next->prev = new;
current->next = new;
current = new;
}
}

long best = 0;
for (int p = 0; p < PLAYERS; p++) {
if (scores[p] > best) best = scores[p];
}

printf("%ld \n", best);

return 0;

Learned a lot about memory today. Thanks for the user that posted a C solution, I copied you a bit.

$ time ./day9
3212830280

real 0m0.312s
user 0m0.252s
sys 0m0.060s

Not sure if my program can run big boy part 2. It keeps getting bogged down at ~70-80 million and I'm not sure exactly why. It doesn't crash, just stops progressing. like 70-80m doesn't take long at all, and then it just won't go any higher. I can't tell if it starts paging, or what...

>Learned a lot about memory today.
>>does not free any of the allocated memory
a-user...

Attached: 1543746305637.jpg (545x526, 49K)

open up taskmgr performance tab
memory at 100%?

I think I just killed my computer with the big boy part 2
Posting from my phone right now