/aocg/ - Advent of Code 2018 General #11

Fabricedition

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.

Private leaderboard join code:

368748-e33dcae3


People who are inactive for 5 days will be kicked, but other leaderboards can be made if desired.

Alternative leaderboard for those waiting for inactives to be kicked from the first:

208834-4a1a9383

Attached: AoC.png (1428x880, 937K)

Other urls found in this thread:

my.mixtape.moe/ehsecw.txt
gist.github.com/ParrotParrot/67f62b4c8f8e07d52f52626e88a6bf9d
docs.python.org/3.7/library/functions.html
pastebin.com/iMmkT57p
pastebin.com/7RB6Ue21
twitter.com/NSFWRedditVideo

How do you get each line from a file and put them in an array ??
I spent the whole day on the first star and I still can't do it.

I'm coding in C

I have a 2 dimensional array, and convert that to text using a nested loop.

getline?

char **getInput()
{
int i = 0;
static char *string[1399];
char line[25];

FILE *file;
file = fopen("input", "r");

while (fgets(line, sizeof line, file) != NULL) {
string[i] = line;
i++;
}

fclose(file);
return string;
}

This returns an array filled with only the last line, why is that ?

Part 1
#include
#include
#include
#include
#include
#include
#include
#include

struct Claim {
Claim(int id, int left, int top, int width, int height)
: id(id), left(left), top(top), width(width), height(height) {}
int id;
int left;
int top;
int width;
int height;
};

std::vector get_claims() {
std::fstream input("day3p1_input");

if (!input.is_open())
return {};

std::vector claims;

std::string buff;
while (std::getline(input, buff)) {
const std::regex format(R"(#(\d+)\s@\s(\d+),(\d+):\s(\d+)x(\d+))");
std::smatch results;

if (std::regex_match(buff, results, format)) {
const int id = std::stoi(results[1]);
const int left = std::stoi(results[2]);
const int top = std::stoi(results[3]);
const int width = std::stoi(results[4]);
const int height = std::stoi(results[5]);

claims.emplace_back(id, left, top, width, height);
}
}

return claims;
}

namespace std {
template struct hash {
std::size_t operator()(const std::pair& p) const {
const std::hash hasher;
return hasher(p.first) & hasher(p.second);
}
};
}

int main() {
const auto claims = get_claims();
std::unordered_map map;

for (const auto& claim : claims) {
for (int col = claim.top; col < claim.top + claim.height; ++col) {
for (int row = claim.left; row < claim.left + claim.width; ++row) {
map[std::make_pair(row, col)].push_back(claim.id);
}
}
}

int overlaps = 0;

for (const auto& cord : map) {
if (cord.second.size() > 1)
++overlaps;
}

std::cout

Day 2. Slow for the same reason. My code is too long to post but only main() is different
int main() {
const auto claims = get_claims();
std::unordered_map map;

for (const auto& claim : claims) {
for (int col = claim.top; col < claim.top + claim.height; ++col) {
for (int row = claim.left; row < claim.left + claim.width; ++row) {
map[std::make_pair(row, col)].push_back(claim.id);
}
}
}

for (const auto& claim : claims) {
bool overlap = false;

for (int col = claim.top; col < claim.top + claim.height; ++col) {
for (int row = claim.left; row < claim.left + claim.width; ++row) {
if (map[std::make_pair(row, col)].size() > 1) {
overlap = true;
break;
}
}
}

if (!overlap) {
std::cout

> he can't solve advent of code problems in one line

+/ > ". each (< ;. _2) (readfile fn)

string[i] = line only copies the pointer, not the string. I think you use strcpy in C.

It segfaults now

post code again

char **getInput()
{
int i = 0;
static char *string[1399];
char line[25];

FILE *file;
file = fopen("input", "r");

while (fgets(line, sizeof line, file) != NULL) {
//string[i] = line;
strcpy(string[i], line);
i++;
}

fclose(file);
return string;
}

I'm ashamed of my solution. Solved both parts with different data structures and 2nd part is very suboptimal (the more optimal would be removing cuts that already overlapped). But hey it werks
import re
import sys

board = [[0 for _ in range(1000)] for _ in range(1000)]

r_line = re.compile(r'^#([0-9]+) @ ([0-9]+),([0-9]+): ([0-9]+)x([0-9]+)')


class Rectangle:
def __init__(self, x, y, w, h):
self.x = x
self.y = y
self.w = w
self.h = h

def overlap(self, r):
return self.x < r.x + r.w and self.x + self.w > r.x and self.y < r.y + r.h and self.y + self.h > r.y

cuts = []
for line in sys.stdin:
n, x, y, w, h = list(map(int, r_line.findall(line)[0]))
cuts.append(Rectangle(x, y, w, h))
for row in range(h):
for col in range(w):
board[y+row][x+col] += 1

# part 1
count = 0
for r in board:
for c in r:
if c > 1:
count += 1
print(count)

# part 2
for i in range(len(cuts)):
for j in range(len(cuts)):
if i == j:
continue
if cuts[i].overlap(cuts[j]):
break
else:
print(i + 1)

Maybe learn what a pointer is first. string[i] is a value, not a pointer.

Had to quit at day 2 part 2. Already too hard cause I'm too stupid to write real code.

string[i] is a char *

Solution to day 3 part 2 in MATLAB where grid is a 1000x1000 grid and data is all the data from the input.

for i = 1:length(data)
n = data(i,1);
x = data(i,2) + 1;
y = data(i,3) + 1;
w = data(i,4);
h = data(i,5);

if grid(y:(y+h-1), x:(x+w-1)) == ones(h,w)
only_fabric_not_overlapping = n
break;
end
end

Also my part 1 solution

for i = 1:length(data)
x = data(i,2) + 1;
y = data(i,3) + 1;
w = data(i,4);
h = data(i,5);
grid(y:(y+h-1), x:(x+w-1)) = grid(y:(y+h-1), x:(x+w-1)) + ones(h, w);
end

Did people just quit already?

which day/part?

>quit
Quit what? Don't forget, it's a work day.

no, it's char
&string[i] or string+i is char*

getline or (f/s)scanf

got the same
$ time ./a.out
p1: 2476165700
p2: 10642
p2: 14038
p2: 16150
p2: 42813
p2: 56253
p2: 59351
p2: 73875
p2: 89877
./a.out 27.35s user 0.66s system 100% cpu 28.001 total

Rust lifetimes make me want to fucking die.

Oh, my bad, sorry. So obviously you can't strcpy into an uninitialized pointer. The reason doesn't work is because the memory at the pointer to line is overwritten with the next call to fgets. You're storing the same pointer into string and the pointer contains what fgets last wrote.

I don't use C very often but here
#include
#include

char** getInput() {
FILE *file;
file = fopen("input", "r");

char** strings = malloc(1407 * sizeof(char*));
size_t n = 0;

for (int i = 0; i < 1407; ++i) {
strings[i] = NULL;
n = 0;
getline(&strings[i], &n, file);
}

fclose(file);
return strings;
}

int main() {
char** strs = getInput();

for (int i = 0; i < 1407; ++i) {
printf("%s", strs[i]);
}

for (int i = 0; i < 1407; ++i) {
free(strs[i]);
}

free(strs);
}

Oh right, I am in UTC+1 and I just forgot most people here aren't in my timezone.

because every language deserves to be used
//

foreach($input as $a) {
foreach($a as $b) {
$coordinates = explode(',', $b[2]);
$coordinates[1] = rtrim($coordinates[1], ':');
$area = explode('x', $b[3]);
for($j = 1; $j

>work
Hopefully completing these challenges will finally land me a job.

Attached: 1454210657107.png (732x743, 370K)

27s? whew, what language/processor?

the vector was not necessary. I used it as a counter lol
int main() {
const auto claims = get_claims();
std::unordered_map map;

for (const auto& claim : claims) {
for (int col = claim.top; col < claim.top + claim.height; ++col) {
for (int row = claim.left; row < claim.left + claim.width; ++row) {
++map[std::make_pair(row, col)];
}
}
}

int overlaps = 0;

for (const auto& cord : map) {
if (cord.second > 1)
++overlaps;
}

std::cout

C on Intel Core i5-4210M CPU @ 2.6GHz

Thanks

your algo must be miles better than mine then cus that's around what i have hah

what's the typical flags for ghc optimization, I've been doing -O2 -optc-O3, is that good enough?

Wrong. The weak should fear the strong.

Attached: hask.jpg (1080x1350, 460K)

Thank god you reminded me about enabling optimizations. My 1m solution just went down to 10s

Just a big square array where I write all the claims and keep track of whether a space is occupied by 0, 1 or many claims

I'm paid to generate safe C code using OCaml. So for me AoC is just relaxation.

living the dream, fren

Do you work at Jane Street dude

>living the dream
I know.
>Do you work at Jane Street dude
No.

hurr durr everyone who uses ocaml works at the one place i know that uses ocaml

Estimation? How many of our private leaderboard will collect the 50 stars? I didn't participate last years so I don't know.

Attached: 4.jpg (852x480, 33K)

i think we can do better and have O(nlogn) with double stacks.

I'll make the logo

I started to learn golang yesterday.
package main

import (
"bufio"
"fmt"
"os"
"regexp"
"strconv"
)

func main() {
re := regexp.MustCompile(`#(\d+) @ (\d+),(\d+): (\d+)x(\d+)`)
board := make(map[[2]int]int)
scanner := bufio.NewScanner(os.Stdin)
var lines []string
for scanner.Scan() {
lines = append(lines, scanner.Text())
}
for _, line := range lines {
text := re.FindStringSubmatch(line)
x, _ := strconv.Atoi(text[2])
y, _ := strconv.Atoi(text[3])
w, _ := strconv.Atoi(text[4])
h, _ := strconv.Atoi(text[5])
for i := x; i < x+w; i++ {
for j := y; j < y+h; j++ {
if count, ok := board[[2]int{i, j}]; ok {
board[[2]int{i, j}] = count + 1
} else {
board[[2]int{i, j}] = 1
}
}
}
}

sum := 0
for _, v := range board {
if v > 1 {
sum += 1
}
}
fmt.Println(sum)

var res int
LINES:
for _, line := range lines {
text := re.FindStringSubmatch(line)
n, _ := strconv.Atoi(text[1])
x, _ := strconv.Atoi(text[2])
y, _ := strconv.Atoi(text[3])
w, _ := strconv.Atoi(text[4])
h, _ := strconv.Atoi(text[5])
for i := x; i < x+w; i++ {
for j := y; j < y+h; j++ {
if count, _ := board[[2]int{i, j}]; count != 1 {
continue LINES
}
}
}
res = n
break
}
fmt.Println(res)
}

Attached: serveimage2.jpg (750x1000, 74K)

no u

What a hideous language, and I say this as someone who uses Haskal

use python

but haskal is beautiful and very readable.

The timing sucks for yuros. The challenges unlock while I'm at work.

>The challenges unlock while I'm at work.
What do you think I did this morning at work? That's not an excuse user.

>Get to work at 0650
>AoC unlocks at 0700
>Get comfy solving the puzzles at work before anybody else has even arrived

static int SolvePartOneParallel(List boxes)
{
int maxX = boxes.Max(b => b.LastX) + 1;
int maxY = boxes.Max(b => b.LastY) + 1;

var matrix = new int[maxY,maxX];

Parallel.ForEach(boxes, (box, state, i) => {
foreach (var p in box.GetAllPoints())
{
Interlocked.Increment(ref matrix[p.Y, p.X]);
}
});

int count = 0;

Parallel.For(0, maxY * maxX, (i, state) => {
int y = i / maxX;
int x = i % maxX;

if (matrix[y,x] >= 2)
Interlocked.Increment(ref count);
});

return count;
}

Attached: 1532162580573.jpg (750x761, 57K)

I used a literal goto (break out of named loop) in my Go solution

There is nothing wrong with goto, though.

My shitty unoptimized python took less than a sec.

Attached: 20181203_211210.jpg (2036x870, 682K)

use regex to replace newlines with ", " then just make it an array

3m40 on the big boy input, how does this compare?

For the big boy input?

>remember that this thing exists
>it's already day 4
I guess I'll wait for next year.

on the big boy file? that's the 100,000 claims one.

Paid to C++. Still do these in python.
>tfw constantly forgetting that True and False are capitalized in python.

he works for facebook

Wouldn't take very long to catch up desu, you could even just copy other people 's code

Where can I find those? New to these threads.

anyone know how to make this transformation
[(2,-5),(2,-3),(1,-7),(4,-6),(2,-4)]

into
[1,2,2,2,-3,4,-4,-5,-6,-7]

essentially flattening and then sorting by abs(x) in python?

...

I posted it in the last thread
my.mixtape.moe/ehsecw.txt
the expected results are
the code I used to produce that is here gist.github.com/ParrotParrot/67f62b4c8f8e07d52f52626e88a6bf9d
honestly, feel free to generate more reliable or bigger ones on your own, that one already defeats most O(n^2) memory algorithms and I couldn't verify it myself

yea

yes

nvm i'm a stupid shitfuck. kept trying to pass it into the sort param without reading the docs.

Big boy set here
Get on my level plebs

Attached: 1534065629294.png (242x175, 6K)

docs.python.org/3.7/library/functions.html
RTFM

Trying to get better at rust, rate my solution plz.

use regex::Regex;
use std::collections::HashSet;

struct Claim {
id: u32,
x: u32,
y: u32,
h: u32,
w: u32,
}

#[derive(Clone, PartialEq)]
enum Point {
Free,
Claimed(u32),
Overlap,
}

use self::Point::*;

fn main() {
let input = include_str!("../input");
let regex = Regex::new(r"(?m)^#(\d+) @ (\d+),(\d+): (\d+)x(\d+)$").unwrap();

let claims: Vec = regex
.captures_iter(input)
.map(|c| Claim {
id: c[1].parse().unwrap(),
x: c[2].parse().unwrap(),
y: c[3].parse().unwrap(),
w: c[4].parse().unwrap(),
h: c[5].parse().unwrap(),
})
.collect();

let mut fabric = vec![vec![Point::Free; 1000]; 1000];
let mut overlap_ids = HashSet::new();

for claim in &claims {
for x in claim.x..(claim.x + claim.w) {
for y in claim.y..(claim.y + claim.h) {

let square = &mut fabric[y as usize][x as usize];

*square = match square {
Free => Claimed(claim.id),
Claimed(id) => {
overlap_ids.insert(*id);
overlap_ids.insert(claim.id);
Overlap
}
Overlap => {
overlap_ids.insert(claim.id);
Overlap
},
};
}
}
}

let overlaps = fabric
.iter()
.flatten()
.filter(|point| **point == Overlap)
.count();

let claim = claims
.iter()
.find(|claim| !overlap_ids.contains(&claim.id))
.unwrap();

println!("{}\n{}", overlaps, claim.id);
}


I tried a HashMap at first, but it's about twice as slow as the nested Vecs.

>inb4 4 4 4

>>> list_of_lists = [(2,-5),(2,-3),(1,-7),(4,-6),(2,-4)]
>>> [y for x in list_of_lists for y in x]
[2, -5, 2, -3, 1, -7, 4, -6, 2, -4]

Why does this work?

Just got back from class.
This function isn't working. Is it an error in understanding or implementation?

Attached: 2018-12-03-153726_887x428_scrot.png (887x428, 41K)

tuples are iterable in python. this reads as "each element of each element of list of lists"

can you share your code to check it on my processor?

>Cnile
gonna have to go with both

It's the only language I know well enough to do this in.

Because for variable in iterator is a self contained block that declares the value that the iterator is referenced with
y is your iterator for x
x if your iterator for list_of_lists
you go through each y in x, which is each tuple in list_of_lists
consider that (value, value) isn't a list, [value, value] is

moot seems to have something against my code
pastebin.com/iMmkT57p

>Rust code compiles
>puzzle input is wrong
I GOT LIED TO

looks like mine but more verbose and also not rushed pastebin.com/7RB6Ue21
this 22ms on input, 1m11s on bigboye

my rust also compiles but didn't solve the problem. ANGERY
fn main() {
println!("Hello World!");
}

Honestly doesn't look like as much of a filter as people were worried initially. I think there was just some initial shock before everybody realized it wasn't that bad.

Attached: notwall.png (691x622, 14K)

eh i did the second part, i looped through the fabric twice once to build up a 2d array of overlaps then again to find which one didn't have a fabric overlap >1

Attached: figure_1.png (2400x1305, 60K)

>He actually weighted the problems so he can draw a christmas tree
devilish

>try to optimize solution
>end up breaking it instead
JUST

You've already solved it, so just sout the answer. Why are you wasting time processing things more than once.

I already did the released parts in python, trying to learn some J by redoing them

that was day 1 part 1

this is day 1 part 2

lines =: < ;. _2 (readfile fn)
nums =: > ". each (< ;. _2) (readfile fn)
repeated =: 1000 ((* #) $]) nums
prefixSums =: +/\ repeated
indexOfDup =: (~: prefixSums) i. 0

indexOfDup { prefixSums

Yay mine still wins

Attached: 1512729069379.png (838x468, 18K)

Around 30 did all stars last year, though not sure whether that takes into account those who solved them after the event

time ./a.out
107043
346

real 0m0,009s
user 0m0,009s
sys 0m0,000s


I'd imagine I could do this in less than 5ms with some optimizations

you didn't post that result you little bitch. stop trying to take credit