/aocg/ - Advent of Code General #8

Redistribute the wealth 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:

youtube.com/watch?v=hhsJL9nO4tA
en.wikipedia.org/wiki/Cycle_detection#Floyd.27s_Tortoise_and_Hare
furaffinity.net/view/24260471/
twitter.com/SFWRedditGifs

tasks are so easy

the last 2 the part 2's have been really disappointing

I think he wants people to stick with it longer. Take a look at day 3, one harder task and half of the people comitted sudoku.

REEEE I JUST READ ON REDDIT THERE IS A NO NEED TO MODIFY CODE FOR PART 2 IT IS JUST [number of previous values] - [index of last value]

I really need to think more before I write
def reallocation():
with open("input.txt", 'r') as input:
banks = list(map(int, input.readline().split()))
size = len(banks)
seen = [[]]
steps = 0

while banks not in seen:
seen.append(banks[:])
steps += 1
max_index = banks.index(max(banks))
max_val = banks[max_index]
banks[max_index] = 0
for i in range(1, max_val + 1):
banks[(max_index + i) % size] += 1

return seen, banks


cycles, last = reallocation()
# Part 1
print(len(cycles))
# Part 2
print(len(cycles) - cycles.index(last))

Maybe I should get around to writing a vector type.

well i was using a map, so i could have simply kept track of the steps with the values.

It's a real shame it only takes about 12,000 steps to see a state recur. It should have taken like a million steps so the fags who did n comparisons for each new state would have been punished.

wooow so i'll take 20 seconds instead of 0.136s, big whoop

the only people being punished are the slowlangs

"the fags who"
>His standard library doesn't have a built in function to do this comparison at incredibly high speeds.
Matlab wins again.

>His standard library doesn't have a built in function to do this comparison at incredibly high speeds.
But my standard library has that, it's called a set.

Then are you also relying on your standard library to do the comparisons for you, or are you doing something else?
If yes why are you complaining about the fags?

If no, what else are you doing.
(I have no Idea about functional programming)

def distribute(membanks):
block = max(membanks)
i = membanks.index(block)
membanks[i]=0
while block != 0:
i+=1
if i == len(membanks):
i=0
membanks[i]+=1
block-=1
return membanks

with open("d6.txt") as f:
config = list(map(int, f.read().split()))
configs = []
while True:
config = distribute(config)
if config not in configs:
configs.append(config)
else:
break
print(len(configs))
Please help a brainlet out. I can't figure out for the life of me why I keep breaking early.

I'm talking about the people who stored the previous states in an array instead of using a set. Checking whether it is already in the array is O(n), while doing the same with a set is O(1).

Ah, thats what you mean.
But only pleb programming languages don't use matrices (starting at 1) for everything.

you mean a hashmap?

It looks like you aren't allowing the program to add 1 back into the chosen memory slot if there's leftovers. In the examples it shows when the highest is 4, it put 1 in the other three and then put 1 back into that slot. Change your while loop to "while block > 0" and this will allow it to throw that last 1 into that last slot instead of leaving it as a 0.

Hashsets and hashmaps have the same performance. I used a set for part 1, because I didn't need to have values associated with the keys (which was a bad move, because solving part 2 required a map anyway).

I'm not sure I get you. block != 0 and block > 0 function in the same way and produce the same output.
The issue isn't the distribute function(I really don't think so) but this part
while True:
config = distribute(config)
print(config)
if config not in configs:
configs.append(config)
else:
break
somehow breaking on the second loop.

Oh, shit. You're right. I could really use some sleep.

You seem to be dealing with a similar issue that I was dealing with.

configs.append(config[:])


configs.append([x for x in configs])


Either of these may help you as it did me. From what I have surmised from my limited background, despite the iteration, the configs list will have one and only one element: the memory allocation for config. If you change it to config[:], each iteration of the loop will have a unique memory allocation and it will allow configs to fill up with more than just the original config memory.

If any of this is wrong, please do correct me. I'm going to go to sleep.

Motherfucker.

configs.append([x for x in config])

Thanks a bunch, user. That worked like a charm.

I wonder if our favourite brainlet will skip day 6 too.

Oh wait I just noticed that he finally did day three.

Post link? Who is it?

youtube.com/watch?v=hhsJL9nO4tA
This guy, he got memed when he skipped day three.

how terrible is my part 2?
#!/usr/bin/python3
from sys import argv

cycles = 0
with open(argv[1], 'r') as data:
ar = [[int(i) for i in i.split()] for i in data][0]
ar_list = []
while True:
blockSize = int(max(ar) / (len(ar) - 1))
blocksLeft = max(ar)
if blockSize == 0:
blockSize = 1
pos = ar.index(max(ar))
ar[pos] = 0
nxt = pos + 1
while blocksLeft > 0:
if nxt >= len(ar):
nxt = 0
if blocksLeft < blockSize:
blockSize = blocksLeft
ar[nxt] += blockSize
blocksLeft -= blockSize
nxt += 1
if ar in ar_list:
print(cycles - ar_list.index(ar))
break
ar_list.append(ar.copy())
cycles += 1

he still didn't do part 2?

He did it in excel, but he was too lazy to repeat it for the sake of the video I guess (he probably just copied it from OEIS and lied desu).

Can anyone explain to me why does python modify list entries on the global range when they are only used in function as a local variables?
Lets say I have
instructions = [0, 3, 0, 1, -3]

print(instructions)
part_1_total = find_inst_sum(instructions)
print(instructions)
part_2_total = find_inst_sum(instructions)
and it prints
[0, 3, 0, 1, -3]
[0, 3, 0, 1, -3]

Yes, I know I can just make a [:] but why doesn't it treat them like locals in the first place?
Isn't it stupid?

>tfw i did the same thing with a spreadsheet while trying that problem
kek

Fuck, it prints
[0, 3, 0, 1, -3]
[2, 3, 2, 3, -1]
Wrong paste

Because mutable objects get passed by reference like in most languages.
Use tuples if you want it immutable.

Yeah, either lied or did the excel formula 200+ times like a brainlet. Love seeing idiots try defend their egos, though. How did Sup Forums find out about his vids?

Oh I get it, thanks

His videos come up for "advent of code 2017" on youtube, so I guess some user randomly found his videos and posted a screenshot.

but sets are inmutable in python, so you'd have to keep creating a set with every iteration. Or am I missing something?

Normal sets (set()) are mutable in Python.
frozenset is the immutable version.

>sets are inmutable in python
I used Erlang where everything is immutable, so it didn't really matter. Python sets are mutable tho, but even if they weren't, you could just use a dictionary with dummy values instead.

I must have looked up a solution

Phew, finally finished day 6. CS grads dropping out left and right

>money ebil!!!

data = '''11 11 13 7 0 15 5 5 4 4 1 1 7 1 15 11'''

def day_06_part_1(data_in):
data = list([int(j) for j in data_in.split('\t')])
configs = []
cycles = 0
while tuple(data) not in configs:
cycles += 1
configs.append(tuple(data))
index = data.index(max(data))
value = max(data)
data[index]=0
while value:
index = (index+1)%len(data)
value -=1
data[index]+=1
return cycles

def day_06_part_2(data_in):
data = list([int(j) for j in data_in.split('\t')])
configs = []
cycles = 0
while tuple(data) not in configs:
cycles += 1
configs.append(tuple(data))
index = data.index(max(data))
value = max(data)
data[index]=0
while value:
index = (index+1)%len(data)
value -=1
data[index]+=1
return (cycles - configs.index(tuple(data)))


print(day_06_part_1(data))
print(day_06_part_2(data))


So this advent thing is basically the second project or whatever I'm doing to learn python. How do I improve this code?

def day_06(data_in):
data = list([int(j) for j in data_in.split('\t')])
configs = []
cycles = 0
while tuple(data) not in configs:
cycles += 1
configs.append(tuple(data))
index = data.index(max(data))
value = max(data)
data[index]=0
while value:
index = (index+1)%len(data)
value -=1
data[index]+=1
return cycles, (cycles - configs.index(tuple(data)))


You dont need to write the same function twice

That's not what my autism told me

Tonight took me ages.. Went full pajeet tier but got both stars eventually. zzzz

>golang doesn't have sets and if you want an array and not a slice you have to define the length of the array in any function argument

aaaaaaaaaaaaaaAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA all that extra shit I needed to write

What was your answer?

4074
2793

4074?

And AoC website accepted it?
Because I'm getting 4074 with your input but with mine the website says wrong answer.

Can you check mine on your code:

int[] memory = new int[] { 4, 10, 4, 1, 8, 4, 9, 14, 5, 1, 14, 15, 0, 15, 3, 5 };

12841
8038

Hmm, so I fucked up somewhere

Post your code. I'm getting 12841 with your input also.

gonna try to debug and find issue

Weird that I'm getting correct answer for his array:

Just post it. I'm curious about the cause too.

Rubyfag here.
Day 6 = DONE!

Definitely my slowest solution, and doesn't feel massively elegant either - though I do love monkey-patching classes. Code here solves for parts 1 and 2.

class Array
def looping?
self.size - self.uniq.size > 0
end

def loop_size
self.index(self.last) - self.size-1
end
end

def redistribute(banks)
bank = banks.last.dup
i = bank.index(bank.max)
wealth = bank[i]
bank[i] = 0
while wealth > 0
i+=1
i = 0 if i == bank.size
bank[i] += 1
wealth -= 1
end
banks.push bank
end

def loop_size(banks)
banks.size-1 - banks.index(banks.last)
end

banks = [[5,1,10,0,1,7,13,14,3,12,8,10,7,12,0,6]]
#banks = [[0,2,7,0]]

until banks.looping?
redistribute banks
end

puts banks.size - 1
puts loop_size banks

> def looping?
self.size - self.uniq.size > 0
end
dude...

sup bruh? In ruby, 0 evaluates to true so you have to coerce it in to either nil or false sometimes.

No, no, bruh, I'm pointing out that it's an extremely inefficient way to determing if the newest addition has not been seen yet, builing a set from your array from scratch every iteration.

Ah shit you're right. It was a lazy pattern I used in an earlier challenge where execution time wasn't a factor as much. My bad

Made it more efficient and less brocode:

def looping?
self.select{|x| x == self.last}.size > 1
end

oh hurr I can provide arguments to Array#count, so it could just be self.count(self.last) > 1 - but execution time for the two are about the same and blocks are sexy

More boring problems.

So I was pretty busy these last few days and am only now catching up, just finished day4 (which was super easy compared to day3, imo...).

I really don't like my part two solution though (ew, nested for loops) - does anyone want to share a nicer looking one? Preferably in JS but I don't really care.

Dunno:

int[] memory = new int[] { 4, 10, 4, 1, 8, 4, 9, 14, 5, 1, 14, 15, 0, 15, 3, 5 };
int findLargest()
{
var pos = 0;
for (int i = 1; i < memory.Length; i++)
{
if (memory[pos] < memory[i]) { pos = i;}
}
return pos;
}
HashSet order = new HashSet();
order.Clear(); order.Add(string.Join("", memory));
var steps = order.Count;
while (order.Count == steps)
{
steps++;
var index = findLargest();
var max = memory[index]; memory[index] = 0;
for (; max > 0; max--)
{
if (++index > memory.Length - 1) { index = 0; }
memory[index]++;
}
order.Add(string.Join("", memory));
}
Console.WriteLine($"{steps}");
Console.ReadKey();


I suspect HashTable might have encountered some early has collision but then I've tried with other collections too - same result

>string.Join("", memory)
Come on now. You should be able to figure this one out.

Are you getting 9614?

what?
It converts array into string i.e. {1,2,3,4,5} into "12345" and then HashSet collection does checking automatically by hash. No duplicates can pass through

Yeah

I won't tell you the answer right now to make it a bit more exciting for you, so think a little bit more about why this is wrong.

>advent of CODE
>posts math problem instead
literally a scam

I'm retarded

Did you figure it out?

Yeah
No wonder I've hit dead end, revising the working code over and over again when the issue was how I track unique state

Who the FUCK is this autist?

That was easy. Has the calendar image been updated yet? If not I'll add OP's image to it.

Why would you want to use an array instead of a slice?

...

a pony

Golang arrays allow you to compare the contents with other arrays with comparison operators, but if you're using a slice you'll need to iterate over it with a range and compare the values in each slice individually

I've looked around and honestly I can't find an easier way, which is a shame.

Why not use a map to store the states of the memory banks?

Yeah I should have probably done it that way in the first place

>last days have been trivial to implement but incredibly slow when written idiomatically in functional languages

Every time I see ruby code it makes me want to learn it, looks so comfy

So how does the formula solution looks like?

en.wikipedia.org/wiki/Cycle_detection#Floyd.27s_Tortoise_and_Hare

I used sets in python, but it is still taking incredibly long time, is there a way to fuck up membership checking so that it becomes O(n) accidentally?

There isn't one because redistribution is a recurrence relation

you are running your purely functional shit on hardware that does mutable memory better than anything else, what were you expecting?

To clarify, there may be a closed form solution but finding it is going to be enormously difficult, especially considering how math-adverse this board is.

Today. Pretty easy. Might try golfing it or use a different lang for a challenge.

def main():
with open("input.txt") as f:
memory_banks = [int(i) for i in f.read().split()]
cycles, seen = 0, {}

while True:
cycles += 1
n, index = max(memory_banks), memory_banks.index(max(memory_banks))
memory_banks[index] = 0

for i in range(n):
index += 1
if index > len(memory_banks) - 1:
index = 0
memory_banks[index] += 1
current_state = tuple(memory_banks)

if current_state in seen:
# part1: print(cycles)
print(cycles - seen[current_state])
break
else:
seen[current_state] = cycles

The ST monad is idiomatic, dumbshit.

Thanks user

Didn't look like a pony to me, so I looked it up. Apparently it's some type of pokemon. furaffinity.net/view/24260471/

does it matter at this point

Why was day 3 so hard compared to 4-6?

filter

lets just say there's a lot of things you could be doing better

wrote a shitty version earlier because I was in a hurry, this one is quite a bit faster

You should do it. I'm trying to do my answers in a more idiomatic ruby way (hence the adding of a method to Array, rather than just calling someMethod(array). It's a very comfy language and super easy to learn imo.

with open("day6input.txt") as inputData:
row = [int(data) for data in inputData.read().split()]

perms = []
cycles = 0

while row not in perms:
perms.append(row[:])

maxVal = max(row)
startIndex = row.index(maxVal)

row[startIndex] = 0

for i in range(1, maxVal+1):
row[(startIndex+i)%len(row)] += 1

cycles += 1

print("Part 1 result:", cycles)
print("Part 2 result:", cycles - perms.index(row))