/aocg/ - Advent of Code 2018 General #16

>tfw when was trying to insert the whole resulting string in the answer input instead of it's length.

Attached: 1523130302651.png (500x595, 278K)

Takes like 250ms, not the fastest but fast enough

Is Python worth learning? What can I do with it aside from this?

I did this twice

BIG BOY TIME
This kills the brainlet.
I just pasted my input into itself a couple of times.

anonfile.com/K0n2Lbm3bf/biginput

Attached: Screenshot_20181205_091255.png (798x424, 59K)

Made a quick recursive function too, but if I cared about speed I'd probably check for new local matches instantly after each collapse, which should vastly reduce the overall amount of compares and copies.

whats the efficient algo for solving day 5?
this is my Nim solution
part 1: 280ms
part 2: 3352ms
import sequtils, strutils, tables, threadpool

proc part_one(input: string): int =
var stack = newSeq[char]()
var offset = 0

for i in input: stack.add(i)

while offset < stack.len - 1:
if chr(ord(stack[offset]) - 32) == stack[offset + 1]:
stack.delete(offset, offset + 1)
if offset > 0: offset -= 1
elif chr(ord(stack[offset]) + 32) == stack[offset + 1]:
stack.delete(offset, offset + 1)
if offset > 0: offset -= 1
else:
inc(offset)
return stack.len

proc async_helper(input: string, ch: char): int =
var stack = newSeq[char]()
var offset = 0
for i in input:
if ch != i and chr(ord(ch) - 32) != i:
stack.add(i)
while offset < stack.len - 1:
if chr(ord(stack[offset]) - 32) == stack[offset + 1]:
stack.delete(offset, offset + 1)
if offset > 0: offset -= 1
elif chr(ord(stack[offset]) + 32) == stack[offset + 1]:
stack.delete(offset, offset + 1)
if offset > 0: offset -= 1
else:
inc(offset)
return stack.len

proc part_two(input: string): int =
var count_t: array[26, FlowVar[int]]
for i in 'a'..'z':
count_t[ord(i) - 97] = spawn async_helper(input, i)
sync()
return ^count_t.min
let input = readFile("input.txt").strip
echo part_one(input)
echo part_two(input)

This is the second time for me too. The first time was with the puzzle from the day three. I was counting the rectangles instead of the area.

>353ms, code unchanged from before
feels real nice

>big boy
>only about twice as large as the standard input data
Try again.

that's probably it, 90% of the time my sanitise calls are just deleting two at a time

I fucked up

part 1: 6ms
part 2: 804ms
using this code not sure why this runs faster than my original input

Python is worth learning yes because it's very useful but for programming contests like this, C++ is better

For this particular contest, Python is better since it's easier to code faster in.

>again only top 5000 because I wake up 2 hours late
This isn't fair ;_;

I blame it on the time pressure

Actual big boy input
About 20 times the original.
anonfile.com/edr0L0mab2/biginput

Attached: newbig.png (640x363, 49K)

8.026s for my decently fast haskell

fun main(args: Array) {
val input = File("day5.txt").bufferedReader().readLines()[0]
println("part 1: " + part1(input))
println("part 2: " + part2(input))
}

private fun part1(input: String): Int {
val stack = Stack()
for (c in input) {
with(stack){
if (empty()) push(c)
val tmp = pop()
if (tmp == c+32 || tmp == c-32){}
else {
push(tmp)
push(c)
}
}
}
return stack.size-1
}

private fun part2(input: String): Int {
var result = input.length
for (c in 'A'..'Z'){
val s = input.replace(Regex("(?i)$c"), "")
if (s.length < result){
result = s.length
continue
}
var k = part1(s)
if (k < result) {
result = k
}
}
return result
}

Total: 104ms
Part1: 15ms
Part2: 78ms

1.2s /w

post code

About 13.8s for my less fast haskell

>File("day5.txt").bufferedReader().readLines()[0]
Why not just File(...).readText() ?

-- boilerplate imports and reading input

let prereacted = react polymer

print $ length prereacted
print . minimum $ map (reactedLength prereacted) ['a'..'z']

reactedLength polymer c =
length . react $ filter ((/=c) . toLower) polymer

react [] = []
react (x:rest)
| 32 == xor (ord x) (ord (head reacted)) = tail reacted
| reacted == [] = x : []
| otherwise = x : reacted
where reacted = react rest

No reason, I've just been copy/pasting my file reading code all week, and they're usually by line. Just changed it, cut about 5-10ms off the paring time

import Data.Function
import Data.Char
import Data.Tuple

match a b = same a b && (a/=b)

same = (==) `on` toLower

simplereduce l@(x:y:xs)
| match x y = simplereduce xs
| otherwise = l
simplereduce l = l

cascade l1@(x:y:xs) l2@(a:b:as)
| match a x = cascade (y:xs) (b:as)
| match x y = cascade xs l2
| match a b = cascade l1 as
| otherwise = (l1,l2)

cascade l@(x:y:xs) [a]
| match x y = cascade xs [a]
| match x a = (y:xs, [])
| otherwise = (l,[a])

cascade [x] l@(a:b:as) = swap $ cascade l [x]

cascade [x] [a]
| match x a = ([],[])
| otherwise = ([x],[a])

cascade l [] = (simplereduce l, [])
cascade [] l = ([], simplereduce l)

reduc :: String -> String -> String
reduc (x:y:xs) r
| match x y = uncurry reduc $ cascade xs r
| otherwise = reduc (y:xs) (x:r)
reduc [x] r = r

reduce l = reduc l []

part2 l = minimum $ (map $ length . reduce . remove l) ['a'..'z']

remove l c = filter (not . same c) l

part1 = length . reduce
main = do
l

How come difficulty is so jumpy?
yesterdays task was like hour and half of coding for me. Today it was 15 min for both parts.

Also is it possible to see stats of other people?

Inspired by Haskell foldr solutions
in =: a. i. }: fread 'input'
react =: [: # }.@]`,@.(32 ~: [ XOR {.@])/
p1 =: react in
p2 =:

Ridiculous.
let are_opp c1 c2 =
Char.uppercase_ascii c1 = Char.uppercase_ascii c2 && c1 c2
;;

let rec react left c = function
| [] -> List.rev (c :: left)
| r :: right ->
if are_opp c r then
match left with
| [] ->
begin
match right with
| [] -> []
| c :: right -> react [] c right
end
| l :: left ->
react left l right
else
react (c :: left) r right
;;

maurits.vdschee.nl/scatterplot/

btw. since so little people noticed it was a stack problem, are there any resources that can help you train using basic data structures by posing simple fizz-buzz problems involving stacks, queues, heaps, priority queues, etc?
Something on a level that a middle school kid who just learned programming could handle?
I know a book like that but it's not in English unfortunately

I was asking as in "click on username on leaderboard and see times"

>yesterdays task was like hour and half of coding for me. Today it was 15 min for both parts.
Yesterday I solved it literally dead drunk in 20-something minutes while I did today in 30 minutes
I can't even fucking remember what day 4 was about. My vision was spinning af and I threw up an hour later.

This is just how it always goes, on average the difficulty seems to go up but there are also local peaks & valleys maybe to give people a day off so to speak

Well fuck that... After yesterday I was " no need to raise early, difficulty went up so I will not manage to do it before I need to go to work" and today proves me wrong... Now I will have to raise early every day just to check if task is easy or not.
fuck this all.

Well... everyones brain works differently I guess.

since today was the easy one it'll likely go up for a few days again

You know what they say - never skip the stack day.

Attached: stack-metal-weights-gym-equipment-as-bodybuilding-concept-75735434.jpg (984x1300, 108K)

We need more. I'm currently uploading a true big boy input, 10000x the size of the original.

Fuck it. Not taking any chances of missing something as easy again.

I'm ready.

Easy.

>half a gig
I guess it's easy to generate the input for this, just needs to be random.
Might be neat to propose implementing a specified LFSR for people to generate the same big boy input locally, as an extension to the puzzle.
Perhaps a 31 bit one with the highest and lowest bits XORed for the next bit, mod 52 mapped to A...Za...z, symmetrical to ensure endianness has no impact on the random stream. Seed it with 1, and generate half a gig (by base 2 standards).
No idea if anyone wants to give it a go, might be some fun.

Attached: 1532741697307.png (720x720, 694K)

The puzzle input is not random it's biased towards generating pairs, you wouldn't get a 90% size reduction with pure random inputs.

I guess that would be a problem. Defining a constant weighting mechanism is probably out of the scope for this, but it was worth suggesting.
Maybe it's not so bad of an idea for a different puzzle.

Latecomer here, are you saving solutions anywhere or do I go back to previous threads to see them?

I keep all of my solutions locally, but haven't put them in one place online.

NPC reporting in. Joined this "adventure" this morning. What did I miss?

Attached: Screenshot from 2018-12-05 20-37-19.png (3840x2160, 444K)

Takes about 6 seconds for my Haskell.

react2' :: Char -> (String,String) -> String
react2' c (a, []) = a --reverse a
react2' c ([], (a:as)) = react2' c ([a], as)
react2' c ((a:as), (b:bs))
| a == c || toLower a == c = react2' c (as, b:bs)
| isLower a && isUpper b && a == toLower b = react2' c (as, bs)
| isUpper a && isLower b && a == toUpper b = react2' c (as, bs)
| otherwise = react2' c (b:a:as, bs)

react2 c i = react2' c ([], i)

I'm annoyed that in my stack implementation if you cancel the attempts in part 2 after the resulting stack becomes too big, the extra check negates any time you save by doing it.

So is 10 seconds a good runtime for a BASH solution?

(use-modules (srfi srfi-1))
(use-modules (srfi srfi-26))
(use-modules (aoc utils))

(define w (string->list (car (file->list "input.txt"))))
(define (alphabet) (map integer->char (iota 26 97 1)))

(define (same? a b) (eqv? (char-downcase a) (char-downcase b)))
(define (match? a b) (and (same? a b) (not (eqv? a b))))

(define (simple x)
(cond ((null? x) x)
((null? (cdr x)) x)
((match? (car x) (cadr x)) (simple (cddr x)))
(else x)))

(define (reduce-r l r)
(if (null? l) r (reduce-r (cdr l) (simple (cons (car l) r)))))

(define (reduce l) (reduce-r l '()))

(define (with-removed l c) (length (reduce (filter (compose not (cute same? c )) l))))
(define (part2 l) (apply min (map (cute with-removed l ) (alphabet))))

(define reduced (reduce w))
(report (cl length reduced) (cl part2 reduced))

Part 1: 1971155
Part 2: 763439
Time: 262ms

Rust truly is the fastest of all languages

Attached: day5.png (680x513, 241K)

Unfortunately there's a big downside which is you have to use rust

>he is butthurt because his pajeet tier solutions got BTFO by my Rust solution

btw, std::deque lets you push and pop from both ends of the queue and gives you constant time access by index.

does this work? I can't program in rust but this looks like you are just removing the lower case version of the character from the input.

Of course this works. Or'ing an ascii letter with 0x20 makes it lowercase.

tfw two brainlet to use a stack

tux@oniichan /m/D/t/s/0/2/05> hyperfine ./a.out
Benchmark #1: ./a.out
Time (mean ± σ): 728.9 ms ± 28.2 ms [User: 723.4 ms, System: 3.9 ms]
Range (min … max): 689.2 ms … 763.9 ms

#include
#include
#include
#include
using namespace std;

int clobber(const char *line, char ignore = 32) {
char *copy = strdup(line);
char *c0 = copy;
char *c1 = copy+1;
int proteins = 1;
while (*c1) {
while (tolower(*c0) == ignore) c0++;
while (tolower(*c1) == ignore) c1++;
if (*c0 != *c1 && tolower(*c0) == tolower(*c1)) {
*c0 = ignore;
*c1 = ignore;
while (*c0 == ignore) c0--;
while (*c1 == ignore) c1++;
proteins--;
} else {
c0++;
c1++;
proteins++;
}
}
free(copy);
return proteins;
}

int main()
{
ifstream f("biginput");
if (!f)
return 1;
std::string line;// = "dabAcCaCBAcCcaDA";
std::getline(f, line);
const char *read = line.c_str();
std::cout

Everyone using Rust, Haskell etc. is childish. Here's a list of languages that real companies use:

>JavaScript
>C#
>Visual Basic
>C++
>Go (if you're at Google)

Learning a new language takes months, and becoming fluent takes years. Studying gimmick languages is a waste of time and brainpower, especially if they won't get you hired.

Attached: amy_smug3.png (287x302, 107K)

>C#
>Real company

Attached: 1534935983694.jpg (1291x3600, 610K)

firecracker-microvm.github.io/
>written in Rust

65ms with OCaml, a language with a non zero cost abstraction. Are you even trying?

>Learning a new language takes months
Also some hot opinions from this faggot:

>You can teach yourself computer science.
>Java is a meme language
>Web devs are paid better than software engineers
>RUST is a real language
how many did I get right?

I wrote a horrible O(n^2) solution but at least I'm still in the Jow Forums top 20

Are you sure you use the big boy input? If so post source code.

why the fuck is everyone's goal to get some shitty job working for in ?
you get one fucking life then you die and you're gone forever
motherfucker, don't piss that shit away on writing data-shuffling code for people who don't care about you
i'd rather do ANYTHING else
there are way better ways to have fun, and way better ways to improve the world. the corporate option provides nothing of value
fuck you

I just want the money, man

Imagine being so out of touch with reality

Oh, you're talking of the big boy, sorry. I'm gonna try with sepples.

This. Believe me, I'd love to be working on the big world-changing type stuff. But it's hard to get there when you grow up poor and everything is a climb. I'm not complaining, but there's a long way to go before I feel comfortable starting to go after the life I really want to have lived all along.
That's kind of sad but that's just the way it is. I also hate corporate bullshit, so I'm gonna get in and get out with the resources I need to actually do something valuable with the rest of my time. It's like investing in my own future.

Nice bait

I'm learning some things from you fellow rust user.. I spent a while trying to figure out how to run code inside an arm of a match statement. That "if let Some(&)" is pretty nice.

I also hooked into rayon to mutlithread part two out for free.

Attached: day5.png (1430x1534, 115K)

True BIG BOY INPUT:
mega.nz/#!Cz5h1QDT!YKzqfnY2fRN--s4ZbaFzj3_HO3uHhmbo02Rw-TbUe20

500MB

you should be able to do this in under 2 minutes.

Attached: 8246808524_0409980f1a_z.jpg (612x612, 96K)

How do you remove chars from large string quickly in C without regex brehs? Calling memmove() everytime I come across said char takes forever.

This has been much harder than the problem itself.

Attached: ffffffffffmpeg.png (376x258, 11K)

The fuck are you trying to encode?

Use two indexes src and dst, src is the current character you are examining, dst is the last character that you added (starting at -1)
>if dst < 0 then buf[++dst] = buf[src]
>if tolower(buf[src]) == tolower(buf[dst]) then dst--
> otherwise buf[++dst] = buf[src]
Something like this, haven't tested it.

Oh fuck that's neat, I actually applied the same technique some time ago but forgot about it. Guess yesterday turned me into a pajeet.

Using my Rust solution from here: Part 1: 43563512
Part 2: 41818510
Time: 8.23s

note that the quadratic solution is completely fine with the puzzle input if you are coding in C

You're off by 1

BLAZING speed
my haskell solution took 4m3s

and apparently it wasn't off by one either
43563511
41818509

I'm optimizing my solution but I don't know why I'm getting the wrong output. can anyone help
import sequtils, strutils, threadpool

proc part_one(input: string): int =
var stack = newSeq[char]()

for ch in input:
if stack.len == 0: stack.add(ch)
elif stack[stack.high] == ch:
stack.del(stack.high)
else: stack.add(ch)

return stack.len

proc async_helper(input: string, ch: char): int =
var stack = newSeq[char]()

for i in input:
if i == ch: continue
elif stack.len == 0: stack.add(i)
elif stack[stack.high] == i:
stack.del(stack.high)
else: stack.add(i)
return stack.len

proc part_two(input: string): int =
var count_t: array[26, FlowVar[int]]
var smallest: int

for i in 'a'..'z':
count_t[ord(i) - ord('a')] = spawn async_helper(input, i)
sync()
smallest = ^count_t[0]
for i in count_t[1..25]:
if ^i < smallest: smallest = ^i
return smallest

let input = readFile("biginput.txt").strip.toLowerAscii
echo part_one(input)
echo part_two(input)

>0.5GB
Fuck off.

SEETHING brainlet alert

not my fault when you retarded nigglet have a \n at the end. the input must only be ascii letters.

What's the problem? The rustard did it in 8 seconds.