/aocg/ - Advent of Code 2017 General #20/aocg/ - Advent of Code 2017 General #22

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

reposting for discussion

so, it seems like python is a top tier language for these kinds of challenges
>extremely little boiler plate
>easy type conversions
>easy string manipulation
>list comprehensions, map/reduce, etc functional things to do work on all the data
only downside is questions like day 20 where the solution you come up with might involve looping x thousand times since it's slow as dicks

if not python, what is the best™ language for these competitions?

I am so fucking bad at making the OP holy shit, edition

Updated calendar up to yesterday

r8 my 20ms solution for d20 part 2
pls no bully

How are you guys doing part 2

Do I need some advanced knowledge to do this? I mean, I know Python and I'm able to solve some problems but this seems hard.

If you know how to use a modulus and a dictionary you're good to go

not for day 20, for some other days you may require a little bit of outside knowledge

auto? REEEEE

same way I did all the other ones
don't try to be clever, just do the actual simulation

>brainlets like pic related are above me because time zones

> implying I'm going to type std::multimap::iterator&
>not using nice feature from a language because muh autismo
I bet you think goto is evil

B-but, user, you just typed it.

I copy/pasted it :^)

as an obviously biased cunt, I can recommend giving Scala (or Kotlin, Swift, etc) a shot
>extremely little boiler plate
decent stdlibs def help with that
>easy type conversions
scala's got some pros and cons here
>easy string manipulation
yup, jelly of python's slice syntax tho
>list comprehensions, map/reduce, etc functional things to do work on all the data
preaching to the choir
>only downside is questions like day 20 where the solution you come up with might involve looping x thousand times since it's slow as dicks
JVM startup and warmup are shite, but for longer-running shit (soon as you go over a second or a few) its a whole nother ballpark - got a mere 2x slowdown compared to c++ (idiomatic code on both sides) the one time I could be arsed to compare on the same shitty netbook-level box
captcha: chadderton

>not waking up at improbable hours to try to enter the leader board
>not interrupting work to try to enter the leader board
It's like you don't even try

FUCK physics honestly

My hacky packy solution to D20P2

def get_distance(x_str, y_str):
a,b,c = [int(x) for x in x_str.split('#')]
d,e,f = [int(y) for y in y_str.split('#')]
return abs(a-d)+abs(b-e)+abs(c-e)

vectors = np.array(vectors[:])
for i in range(1,100):
print("There are {} particles after {} runs".format(len(vectors), i))
positions = [get_position_direct(vector, i) for vector in vectors]
mask = [positions.count(x) == 1 for x in positions]
vectors = vectors[mask]
print("There are {} particles.".format(len(vectors)))

>implying this is anywhere near advanced physics simulation difficulty
laughingwhore.jpg

1) Physics is awesome
2) Constant acceleration movement is easy
3) You don't even need to know physics to do this anyway

would be neat if it were though
>the particles are in space
>here are a bunch of randomly placed spherical cosmic bodies with mass [n...m]
>the particles are attracted to them by gravity

>only downside is questions like day 20 where the solution you come up with might involve looping x thousand times since it's slow as dicks
Python is just fine for day 20 (particles). Mine does 1000 iterations in 2.5 seconds, and you only need maybe 5k to solve it.

>and you have to handle what happens when they collide
>protip : it's not an elastic choc

My solution only does 139 iterations. Post your input

>P.first
>P.second.first
>P.second.second
readability/10
>long long px py pz vx vy vz ax ay az
I mean, it's trivial to understand, nice-fast-n-unboxed, but structs exist for a reason, and are lightweight enough
unless .count doesn't do deep equality checks, in which case, jeez
>//hacky hack to get all collisions
I'd add something mentioning that we'll break out of the loop after 100 iters of no collisions somewhere - for readability's sake
Or just
- rename `i` to noCollisionStreakLen or something less Java-verbose
- get rid of the redundant-ish new_ptcls.size != ptcls.size in the for expression

>doesn't paste entire code
it's like you're baiting us to bully you

Can someone give me the ffmpeg arguments to turn a video into a postable webm? I have a working 3D view.

I mean 5000 is the worst case for the brainlet solution where you just simulate and print the result every so often to see when it stops changing

It's not constant acceleration; it's based off triangular numbers. P + tV + T(t)A, where T(n) is the nth triangular number

Oops
def get_position_direct(vector, t):
x, v, a = vector
res = np.array(x + t*v + t*(t+1)*a//2)
return "{}#{}#{}".format(res[0], res[1], res[2])


def get_distance(x_str, y_str):
a,b,c = [int(x) for x in x_str.split('#')]
d,e,f = [int(y) for y in y_str.split('#')]
return abs(a-d)+abs(b-e)+abs(c-e)

vectors = np.array(vectors[:])
for i in range(1,100):
print("There are {} particles after {} runs".format(len(vectors), i))
positions = [get_position_direct(vector, i) for vector in vectors]
mask = [positions.count(x) == 1 for x in positions]
vectors = vectors[mask]
print("There are {} particles.".format(len(vectors)))

>It's not constant acceleration

>acceleration doesn't change at all
>not constant
uhhhhhh

I have virtually no idea
Maybe you /gif/ or /wsg/ knows

ffmpeg -i input.mkv -c:v libvpx -b:v 1M -an -sn output.webm
1M is the video bitrate, adjust as needed for quality/filesize

He means it's not continuous acceleration

Are you implying that x = c is not a continuous function?

Actually in this case acceleration is a dirac comb, so it's neither continuous nor constant

Get em user
If they want to bitch on the words they deserve it

Not if x(t) = c where t is discrete.

I've been ill lately, and couldn't focus on AoC. I haven't done problems 17-19 yet.

then it's the composition of functions x(t()) that's discrete. the function x() is still continuous

pls remove those ugly ass scroll bar from your terminal

Can't do that, I actually use the scrollbar when I need really fast scrolling.

>all cpp98+ features are abhorrent
>writes std replacements in "pure" c++ for "speed"
>overrides new/delete with malloc/free
>creates own sub-classes for formatting with sprintf that cast and copy char*s multiple times and ends up using them in stringstreams anyway
Yep, it checks out, makes 25k a month too

Thanks.

The input appears to be made of a dense sphere surrounded by a more sparse one. All the collisions happen very close to the origin.
For a scale reference, the lines at the origin are equivalent to 250 units long.

hahaha, holy shit

Are you on linux?

No, windows (7 specifically).

No I'm on GNU/Linux

one of you is a faggot

No I'm on GNU/Linux/SystemD

Who specifically?

Windows 7.

You. Specifically.

So the collisions are the particles that start at one end and try to go to the other while all the rest float out to space.

>Try to use these challenges as a nice way to polish my Rust
>Struggle with the first one between the UTF8 and picking up a \n that I didn't notice
Back to Python it is

>polish
>rust
Think about it

Back to Google instead. Scratch your head a bit man.

I finished it but it took me like 3 hours. By doing the right thing the language makes the simple processing of ascii more difficult.
int(string[index]) is way more simple than (string.toBytes()[x].copy().as char).to_digit(10).unwrap()

I did it boys

We're all gonna save Christmas, lads

>This spinlock isn't just consuming computing power, but memory, too

>spinlock
>consuming memory

u wot m8

What are the symbols supposed to be in the main page drawing?
Wires are wires,
o hole
^^^ resistor
|( diode or polarized capacitor
rectangle some chip

But dunno about the others, there's probably a capacitor, inductance, a battery maybe, but they don't quite match the usuals. There's
[-]
oTo
┤|├
┤[]├
=

oTo could be press switch
┤[]├ - looks like quartz crystal
┤|├ - looks like a batter
= - could be ground
[-] - a connector of some kind?

Does everyone have a particle with a=?

I feel like I could've been top 10 on today's problem. I thought of searching for zero acceleration really quickly, but I started 18 hours too late.

>not searching for the smallest acceleration
I didn't have a btw, only a .

No, you got lucky. Surprised that's even a generated input.

And by smallest I mean the one where the sum of absolute values is the smallest, because muh Manhattan distance.

That's easy to find as well. The trick would've been to literally search for the line number, rather than writing a program.

like day 7 part 1
open it up in notepad and do a couple ctrl+f's to get the answer
easier on day 7 though since you don't need to evaluate anything, just search a couple times to the bottom

This is all I could gather.
calendar-ornament0 ∧∧∧ resistor
calendar-ornament1 |( capacitor
calendar-ornament2 [─] dip switch?
calendar-ornament3 ┤|├ battery
calendar-ornament4 oTo press switch
calendar-ornament5 ┤[]├ crystal
calendar-star * star
o via
= ground
V vcc


Also here's some bad, bad code for day 20.

⎕io ← 0
data ← ((,∘3 3≢)⍴⊢)⊃⊃(⍎¨(∼∊∘',

Nice.

this day was pain in go
package main

import "fmt"

const ITER = 10000

type vec3 [3]int

type velacc struct { vel, acc vec3 }

func dist(pos vec3) int {
return abs(pos[0]) + abs(pos[1]) + abs(pos[2])
}

func next(p vec3, v velacc) (vec3, velacc) {
for i := 0; i < 3; i++ {
v.vel[i] += v.acc[i]
p[i] += v.vel[i]
}
return p, v
}

func abs(n int) int {
if n < 0 {
return -n
}
return n
}

func parseLine() (vec3, velacc, bool) {
var pos vec3
var v velacc
r, err := fmt.Scanf("p=, v=, a=\n",
&pos[0], &pos[1], &pos[2],
&v.vel[0], &v.vel[1], &v.vel[2],
&v.acc[0], &v.acc[1], &v.acc[2],
)
return pos, v, (r == 9 && err == nil)
}

func main() {
parts := make(map[vec3]velacc)
for {
pos, v, ok := parseLine()
if !ok {
break
}
parts[pos] = v
}
for i := 0; i < ITER; i++ {
nextP := make(map[vec3]velacc)
toDel := make(map[vec3]struct{})
for p, v := range parts {
np, nv := next(p, v)
if _, ok := nextP[np]; ok {
toDel[np] = struct{}{}
continue
}
nextP[np] = nv
}
for p, _ := range toDel {
delete(nextP, p)
}
parts = nextP
}
fmt.Println(len(parts))
}

if you have any idea how to simplify this, gimme

>⍋
A little Christmas tree, how cute!

>type velacc struct { vel, acc vec3 }
You could call that a particle. Also why not store the position in that struct?

>func dist(pos vec3) int
Why not func (p *particle) dist() int { ? Same for your next(), using a receiver is much cleaner.

>nextP := make(map[vec3]velacc)
toDel := make(map[vec3]struct{})
Personally I made a slice of *particle and each particle has an alive bool field. I don't bother removing them from the slice when they die. I don't know if it's faster to use a linked list and remove stuff or using a slice and just discarding dead particles.

precisely the level I'm able to reason about his code

I hope day 25 will be really difficult. Nothing has required complex logic or proper optimization yet, just simple tricks that trivialize everything.

>Also why not store the position in that struct?
Because I wanted position as key in dictionary.
>why not dist() and next() methods of full particle struct
implication of ^, would do otherwise
>life bool field
you could do map[particle]bool. how do you actually detect collision? n^2 complexity nested for loops?

Sup Forums won't let me post my part 2. Pretends there's a "connection error".

That means cloudflare bot detection is trying to show you a captcha. But it can't show a captcha through an AJAX request. If you use the top form to post the reply, it'll work (once you do cloudflare's captcha).

Indeed, writing quick throwaway challenge code is one of the places where I'd prefer Python over, say, Haskell

>how do you actually detect collision? n^2 complexity nested for loops?
different user here but that approach works just fine because there are so few elements

>how do you actually detect collision? n^2 complexity nested for loops?
Build a mapping from position to list of points at that position. If len(lst) > 1 then delete everything in the list. O(n)

Reminder that if you have to stop your part 2 loop after an arbitrary number of ticks then you are a pajeet.

>Implying you didn't do this

c noob here working on day 1 (just found out about this). When I do int token = fgetc(infile) and print it out (printf("%d", token)) it prints the ASCII value instead of the decimal value. Why?

because fgetc gets a character, and you're just implicitly casting that character to an int, which gets you that character's ascii value.

Because %d is for digits, use %c.

ok but how would I convert that char (which is a number) into an int? Just subtract 48?

>Just subtract 48?
Yeah that'd work. Protip, because chars are an integral type, you can do token - '0' instead of - 48 (same thing, but it's more obvious what you're doing)

Yes, subtracting the character '0' is more readable and understood using 48.

int x = c - '0'

ok thanks guys

>polish
>turd

I didn't, mine determines safe particles and removes them one at a time until there are no particles left, then terminates.

and I told you in previous thread there could be cases when with more diverse input it will fail to process them properly

You are wrong my dude, particles will always sort themselves by acceleration (or velocity if acceleration is 0) in the 6 possible directions

SIXTEEN MINUTES

EIGHT MINUTES AND THIRTY SECONDS

Get ready boys.
Don't forget to stretch before every puzzle.

ONE MINUTE

YOU AIN'T FOOLIN ME

why am I so nervous?
WHY AM I SO NERVOUS?????