/aocg/ - Advent of Code General #4

Previous thread: The puzzles are getting harder! I hope you like spiral arrays!!
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.

Every puzzle gives you an input file, you provide the correct output, so there's no need to submit code.
Sup Forums has it's own private leaderboard join code: 194764-c554ff91
You need to register with an account but you can appear as anonymous.
Also, (anonymous user #194764), please delete the the users with no stars off your leaderboard so new people can join.

Other urls found in this thread:

ghostbin.com/paste/kyjwz
twitter.com/SFWRedditVideos

It's okay to give up. Not everyone has what it takes to be a programmer.

TFW software engineer for past 4 years.
TFW giving up part 2 day 1...

I don't want to live any more.

>tfw cheated on d3p2 by writing out the spiral

You may not like it but this is what peak performance looks like.

Not to rub salt in your wounds, but it's basically a harder FizzBuzz. What made you give up?

I won't do it, but every square number is n-1 steps from the original position. e.g. 5^2 is 4 steps off 1, 6^2 is 5 steps off, etc.

top of your code is cut off, m80

where do you work, i'd like a job there

So I decided to do them in powershell because, why not... 1_1 was easy... 1_2 I just can't seem to get it to work, i know the solution, its easy, but with powershell i can't seem to make it work.

Output;
Test Array; 121244
Comparing - 2 to 1
Comparing - 4 to 2
Comparing - 4 to 1
Comparing - to 2
Comparing - to 4
Comparing - to 4
Sum: 0

There's got to be a better way.

Hard to say what the problem is without seeing the code. You are taking the index modulo 6, right?

I was thinking that the entire time I was doing that problem

if ($inputCharArray[$i] -eq $inputCharArray[(($inputCharArray.length / 2) + $i)]) {
$mySum += [Convert]::ToInt32(($inputCharArray[$i]), 10)
}

>not just using OEIS on part 2

Alas, there is a better way. This is truly the peak of performance.
#include
#include

int main() {
unsigned int data;
unsigned int result = 0;
printf ("Enter value: ");
scanf ("%u", &data);
if (data > 1) {
int counter = 1;
int corner = counter * counter;
while (corner < data) {
counter += 2;
corner = counter * counter;
}

int dist_from_centre = abs((((corner - data) % (counter - 1)) - ((counter - 1) / 2)));
result = dist_from_centre + ((counter - 1) / 2);
} else if (data < 1) {
printf ("Invalid input data!\n");
return -1;
}
printf ("Steps: %i\n", result);
return result;
}

That's for 3.1, isn't it? That guy's solution looks like something for 3.2.

am i a cuck for using exception handling on part 2? is this considered taking the easy way out?

Sorry but fuck day 3.

There's a "trick" described all over Reddit that makes it easy. Except it's BS to claim you solved it if you only did it by following a trick someone else found.

Or do it the long way, and your solution sucks.

Try this on line 1.

if ($inputCharArray[$i] -eq $inputCharArray[(($inputCharArray.length / 2) + $i) % $inputCharArray.length]) {

Absolutely gross, but got there in the end..

If your solution is perfect, there's nothing for you to learn.

Throwing/catching exceptions has a massive performance impact. You should not use it as flow control.

>Throwing/catching exceptions has a massive performance impact
Not in C++ it doesn't

I take that back. Didn't read all the way. They are much slower if you're using them as flow control, yes.

How about this

from itertools import product
for i,j in product(*[[-1,0,1]]*2):
if (x+i,y+j) in space:
sum += space([x+i,y+j])

I did the same thing you did on the left. There's got to be a better way.

Well it ain't nice, but im trying to create a linked spiral data structure for day 2 part 2. It's a lot of fun although I'm sure there basically a formula you can use.
After all, a formula is what I used for part 1.

>linked spiral
What the fuck are you talking about?

Like a linked list but each node has a source node and possibly neighbors depending on its position in the spiral.

Thanks friendly user, I didn't know about that.

>That private leaderboard is full.
well that's annoying.

quality oc, thanks lad

so i guess all the work in pt1 means shit all in pt2.
might as well fuck it all and crank it out by hand

Aaah fuck, I was trying to find a reasonable solution and didn't even think of this.

I was trying to set up an if which manipulated the index back when it hit the array length but it was just getting messy and confusing me further. Time for bed i think...

There is a better way

ara ara

it's just a game brev, take it easy.
no one is forcing you to even participate, let alone go and crowdsource an answer.

I haven't even tested if the bounds checking works, but I rewrote my day 3 to be slightly less shit.

What exactly are you supposed to program in Day3 P1?
You just need a calculator, right?
(I also got a bit lucky since my number was in the right arm of the spiral, which saved me a bit of work)

yea I just used a calculator but if you program it you'll lay the groundwork for part 2

Yeah, you are probably right.
If I had wanted to be fast doing Part 1 the "proper" would have been faster.

you can do part 2 on paper

Part 1 in python
def day3a(arg):
root = 1
while root**2 < arg:
root += 2
side = root - 1
if root**2 - arg

The answer is on spiral 4 for me, so it actually wouldn't take long at all to just brute force it.

God damn this got hard.

Here's the general pseudocode as to how I did it:
-Write out the spiral and figure out an arithmetic relationship for each corner that we turn at (see below)
TOP LEFT
(2n)^2 +1
TOP RIGHT
(2n)^2 - (2n-1)
BOTTOM LEFT
(2n+1)^2 - 2n
BOTTOM RIGHT
(2n+1)^2

BR -> TR -> TL -> BL -> BR ...

-Store each location where we turn in an array (rotation_vec)

-When we're actually creating the array, start at the center, and go until the number of elements you've written matches a number in the rotation_vec
-If the number matches, then change the "state"
-The state determines in which direction we go in (up, down, left, or right)

I can't fucking believe it took me 200 fucking lines.
I'm a fucking failure

>/* Fucking kill me*/

For me it was on Spiral 300, which makes it a lot harder to do on paper.
Especially Part 2.

Really?
Is there some kind of explicit formula again?

>For me it was on Spiral 300
what the fuck
what was the input number?

>what was the input number?
361527

That's like spiral 5

I meant on part 1.
Sorry didn't read it correctly...

Anyway, any idea for an explicit formula?

Taking requests to put in December 1, 2

For part 1 I found 4 different formulas, see python code above
I'm doing part 2 at the moment, I can't think of something else than computing every element

>I can't think of something else than computing every element
Don't see any reason not to. It's a very small number of elements

class Node():
EDGE = 1
CORNER = 0

def __init__(self, value, t, source=None):
self.value = value
self.source = source
self.type = t

class Spiral():
def __init__(self):
self.nodes = []
self.side_gen = self.next_side()
self.side_length = next(self.side_gen)
def next_side(self):
# Spiral side length follows the pattern 1, 1, 2, 2, 3, 3...
i = 1.0
while True:
yield int(i)
i += 0.5
def append(self, value):
if not self.nodes:
self.nodes.append(Node(value, Node.EDGE))
else:
if self.side_length == 1:
self.side_length = next(self.side_gen)
self.nodes.append(Node(value, Node.CORNER, self.nodes[-1]))
else:
self.nodes.append(Node(value, Node.EDGE, self.nodes[-1]))
self.side_length -= 1
def index(self, value):
for i, node in enumerate(self.nodes):
if node.value == value:
return i
raise ValueError
def distance_to_center(self, value):
current_node = self.nodes[self.index(value)]
distance = [0, 0]
vec = (0, 1)
while(True):
if current_node.source is not None:
current_node = current_node.source
distance[vec[0]] += 1*vec[1]
if current_node.type == Node.CORNER:
if vec == (0, 1):
vec = (1, 1)
elif vec == (1, 1):
vec = (0, -1)
elif vec == (0, -1):
vec = (1, -1)
elif vec == (1, -1):
vec = (0, 1)
else:
return abs(distance[0]) + abs(distance[1])

def insert(self, value):
# Ha ha ha ha fuck that
pass

Obviously not an efficient method, but was fun to reason about.
Each node stores its value and whether it's a corner or edge. The spiral class knows how to build a spiral and traverse it. For part 1, create a spiral, add n values and then use the distance to center method for n.
s = Spiral()
for i in range(1, 101):
s.append(i)
print(s.distance_to_center(100)

I think I did something similar, just on paper.
Somebody said you could do part 2 on paper, which wouldn't be a problem since the Spiral stays small, but I though there could be an easier way that would be different from simply doing what the program would do.

Why are you all trying to avoid creating a 2D array and procedurally generating the spiral for real?

What made you think using exponentiation wasn't going to fuck you over in pt. 2?

>Why are you all trying to avoid creating a 2D array and procedurally generating the spiral for real?
It is more fun not to brute force it.

Put the CS guy on day 1.

Am I retarded or is Day 3 a whole fucking lot harder than one and two?

I can't think of a solution without googling for formulas, which feels like cheating.

maybe programming isn't for you

You could brute force it or try to think of the formulas yourself.
Part 1 can be done purely on paper.

It is harder, but you should be able to think of a solution. Making one that isn't ugly is the hard part.

Just find what n such that (n*2+1)^2 < x < ((n+1)*2+1)^2. That's the radius. Then the fan offset is how far (x - (n*2+1)^2) % (n*2+1) is from n+1.

That's barely even programming; it's just math.

How does xiaowuc1 manage to finish these things in under 4 minutes?

I looked him up and he shows up on a bunch of other "coding challenge" sites, he tops the leaderboards on those sites too.

hes probably done a shitload of similar problems and has snippets of code ready to copy and paste

Fuck me.

checkAround can be done in a nested loop

D3P1 was pretty tedious to solve, but D3P2 was easy as fuck.

>writing a solution that isn't O(1)
pukinganimegirl.jpg

reee fuck part 2

>Hands always prepared to grab nearby snippets of code

> finished the spiral thingy using Haskell
> sees the second part

Ugh this puzzle, man. Haskell seems so poor with grids and matrices, I think an imperative lang will be a natural tool for this second part.

just do it the brute force way
don't fall for the math trap

The "math trap" was what actually made it easy for me. Once I had an O(1) function for getting the coordinates of a given number, part 2 was only a matter of inserting coordinate => stored value pairs into a map.

Ok, finished D3P2, it's total shite, spent way too long looking for a pattern. Never found one.

This is my D3P1

This is my matlab solution. (not a very clean one)
I am starting to think that this language isn't actually complete garbage which should never be used.

But math is fun!

>tfw you're a meme

lost in a for loop forest, send a search party please

Ok I managed to do part 2 in python the ugly way
If the grid isn't big enough to store everything needed, it just crashes
def day3b(arg):
def nextij(i,j):
if i < j or (i == j and i > 0):
if i

Don't really understand what big O notation is yet, but here is my code, optimized yet again

#include
#include
#include

int main() {
unsigned int data, result = 0;
printf ("Enter value: ");
scanf ("%u", &data);
if (data > 1) {
int counter = (int) ceil(sqrt((double) data));
counter += (counter + 1) % 2;
int corner = counter * counter;

int dist_from_centre = abs((((corner - data) % (counter - 1)) - ((counter - 1) / 2)));
result = dist_from_centre + ((counter - 1) / 2);
} else if (data < 1) {
printf ("Invalid input data!\n");
return -1;
}
printf ("Steps: %i\n", result);
return result;
}

Day 2 Part 1
Had to do some interesting.. Interestingly, the matched object ($numbers) - when checking the length gave me back another object which was the length of the matches.

So I had to get the length of the length the length of the matches object in order to get the length of the object for the for loop. Unexpected.

# DAY 2 Part 1
function day2_1 ($_inp) {
foreach ($line in $_inp) {
[int]$curMin = ([int16]::MaxValue); $curMax = ([int16]::MinValue);
$numbers = ([regex]'([0-9])*').Matches($line)

for ($i = 0; $i -lt ($numbers.length).length; $i++) {
if ($numbers[$i].Value -ne "") {
if ([int]($numbers[$i].Value) -lt $curMin) { $curMin = [int]($numbers[$i].Value) }
if ([int]($numbers[$i].Value) -gt $curMax) { $curMax = [int]($numbers[$i].Value) }
}
}
$sum += ($curMax - $curMin)
}
return $sum
}

>To play, please identify yourself via one of these services:
nice try NSA

autism

Here's the program for part 1

That IDE looks nice, but how do you compile your code?

I also did part 1 on paper, I did practically the same.

Using your brain. (Although it is not free software, which makes Stallman sad)

Like this

>Don't really understand what big O notation is yet
Please, try to get a basic grasp of it, it seems theoretical and impractical, but it's really the easiest way to predict how efficient your code will be time/memory wise.
It's also not that complicated as you might think, it'll be natural for you soon.

Watching a youtube video on it now. Doesn't seem too complicated when your not trying to figure it out from wikipedia formulas.

Seeing as my code has no loops, and would run basically the same speed no matter what number you put in, wouldn't it qualify as O(1)?

wrote mine on a whiteboard before figuring it out and just wrote some quick code to get the steps of any number.
stumped on 2 for a couple hours now, got my brain all jumbled up. will just bruteforce it tomorrow if i can't figure it out after i wake up.

yes

Has anybody figured out a O(1) way of solving D3P2? Can't figure out any other way than brute forcing

Part 2

# DAY 2 Part 2
function day2_2 ($_inp) {
foreach ($line in $_inp) {
$numbers = ([regex]'([0-9])*').Matches($line)
$lineLength = ($numbers.length).length

for ($i = 0; $i -lt $lineLength; $i++) {
if ($numbers[$i].Value -ne "") {
for ($x = 0; $x -lt $lineLength; $x++) {
if (([int]$numbers[$x].Value) -ne 0 -and $i -ne $x -and ([int]$numbers[$i].Value) % ([int]$numbers[$x].Value) -eq 0) {
$sum += (([int]$numbers[$i].Value) / ([int]$numbers[$x].Value))
}
}
}
}
}
return $sum
}


Powershell, language of champions.

>Has anybody figured out a O(1) way of solving D3P2?
No, I tried for a bit but really couldn't find anything.
Please let me (us) know if you manage to come up with something.

Yes, O(1) means your code's execution time does not depend on the input size. If you don't try to understand the mathsy part, it's really easier. The thing that helped me most is writing different sorting algorithms, time them, and try to understand how execution time relates to input size. It's very empirical and hands-on, so it will stick.

Finally something more interesting... is this a good solution, or am I Pajeet? Takes around 750 ms combined for both parts. I struggled with storing negative coordinates at first, but then I realized I can store it as 4 separate quadrants.

ghostbin.com/paste/kyjwz

>If you don't try to understand the mathsy part, it's really easier
what is so difficult to understand in "it represents the number of steps your algorithm needs to terminate"?

I mean the typical wall of formulas you find around, it's obvious you need some math to understand it.

>am I Pajeet?
If you don't want to be a Pajeet you can do part 1 without writing a program.
My matlab solution takes 20ms (without any JIT compiler help from running the program again) for Part 2.

>what is so difficult to understand in "it represents the number of steps your algorithm needs to terminate"?
That has nothing to do with the math behind it.
It is about the convergence properties of certain functions compared to other functions.

fugg I forgot it's a pain in the ass to get started on a new project in C. You need to rewrite so much shit like vector struct and shit.