/aocg/ - Advent of Code 2017 General #14

Previous thread Not quite travelling salesman edition

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:

en.wikipedia.org/wiki/Disjoint-set_data_structure
en.wikipedia.org/wiki/Disjoint-set_data_structure#Applications
adventofcode.com/2015/day/19
twitter.com/NSFWRedditVideo

module Day12 where

import Control.Monad
import Data.Map as M
import Data.Set as Set

import Utils

testinput :: [[Int]]
testinput = [ [0,2], [1,1], [2, 0, 3, 4], [3, 2, 4]
, [4, 2, 3, 6], [5, 6], [4, 5]]

testset :: Set Int
testset = Set.fromList []

getGroup :: [[Int]] -> Set Int -> Int -> Set Int
getGroup reflist stored n =
let newstored = Set.union (Set.fromList $ reflist!!n) stored
in if (stored == newstored)
then stored
else
Prelude.foldl (\acc n -> getGroup reflist acc n)
newstored (Set.toList newstored)

getPartitions :: [[Int]] -> Set Int -> [Set Int]
getPartitions reflist stored =
Prelude.foldl
(\acc i -> h reflist acc i) [stored] [0..(length reflist - 1)]
where
h reflist stlist n =
let existing = or (Prelude.map
(\stored -> elem n (Set.toList stored) )
stlist )
in if existing then stlist
else (getGroup reflist (Set.fromList []) n):stlist

main = do
input >= (return . lines)
let intlist :: [[Int]]
intlist = Prelude.map deriveIntsFromString input --filter nums
part1 = getGroup intlist (Set.fromList []) 0
part2 = getPartitions intlist part1
forM_ ["Part1: ", (show . length) part1, "\n"] putStr
forM_ ["Part2: ", (show . length) part2, "\n"] putStr

Another overengineered shit

More like hope someone makes a better calendar image for today edition

>only wrote BFS and applied it repeatedly to find connected components
who /lazy/ here

Too late

I think that's what everybody would have ended up with. BFS or queues, it's the same thing.

func visit(n *Node) {
n.Visited = true
for _, p := range n.Peers {
if !p.Visited {
visit(p)
}
}
}

extern crate petgraph;
use petgraph::unionfind::UnionFind;

Damn it feels good to have a functioning package manager..
> near constant time set insertion and set merges

en.wikipedia.org/wiki/Disjoint-set_data_structure

...

Gonna solve day 7 by generating a set of all nodes and descendant nodes. Then set differencing them.

these examples are fucking joke, I don't care anymore. I've stolen code from reddit

routes = {}
for line in PUZZLE_INPUT.split("\n"):
route = line.split("")
program = int(route[0].strip())
pipes = [int(x.strip()) for x in route[1].split(",")]
routes[program] = pipes

def get_group(root):
search = set(routes[root])
searched = set()
while search:
for program in search:
search = search.union(routes[program])
searched.add(program)
search = search.difference(searched)
return searched

def count_groups():
count = 0
found = set()
for program in routes:
if program not in found:
found = found.union(get_group(program))
count += 1
return count

print(len(get_group(0))) # Part 1
print(count_groups()) # Part 2

I strive for conciseness with readability. Here's what I got.

holy shit you are brainlet. Did you try to think about it for at least 20 minutes?

>cheating in anonymous contest with no real prizes
ok, you are retarded

def search(start,ggg,seen):
seen.add(start)
[search(j,graph,seen) for j in graph[start] if j not in seen]
return

left = set(graph)
groups = set()
while left:
seen = set()
search(left.pop(),graph,seen)
[left.remove(j) for j in seen if j in left]
groups.add(tuple(sorted(seen)))
if 0 in seen:
print(len(seen))
print(len(groups))

>def search(start,ggg,seen):
def search(start,ggg,seen):

>tfw still no time to do these challenges
wagecucking was a mistake, don't do it bros

Friendly reminder that people like him work in programming positions all over the world. Some of them make six figures, too.

Wow. This one is pretty hard for me. First time dealing with graphs.

:^)

...

12, first part, in Perl.

my %conn=map{
/(\d+) (.*)/ or die;
$1 => [split /\s*,\s*/,$2]
} ;

sub investigate($;$){
my($id,$ref)=(@_,{});

for(@{$conn{$id}}){
next if $ref->{$_};
$ref->{$_}=1;

investigate($_,$ref)
}

$ref;
}

print scalar keys %{ investigate 0 };

at least these puzzles are finally creeping up in difficulty

And the second part.

Wow that was easy.

my %conn=map{
/(\d+) (.*)/ or die;
$1 => [split /\s*,\s*/,$2]
} ;

sub investigate($;$){
my($id,$ref)=(@_,{});

for(@{$conn{$id}}){
next if $ref->{$_};
$ref->{$_}=1;

investigate($_,$ref)
}

$ref;
}

my $ref={};
my $groupCount=0;
for(sort keys %conn){
next if $ref->{$_};

investigate $_,$ref;
$groupCount++;
}
print $groupCount;

import System.IO
import Data.Graph

bulidGraph :: [[Int]] -> Graph
bulidGraph s = a
where (a, b, c) = graphFromEdges $ map (\x -> (0, head x, tail x)) s

pipes :: String -> Int
pipes = length.
components.
bulidGraph.
map (map read).
map (map $ \x -> if last x == ',' then init x else x).
map (\(x:y:xs) -> x:xs).
map words.
lines

main = do
contents

Day 11 in perl, first part. Got by without grid.

use List::Util qw/sum/;

my %directions;
for(split /,/,){
chomp; $directions{$_}++;
}

my @reductions=(
[qw/n s/, ''],
[qw/sw ne/, ''],
[qw/se nw/, ''],
[qw/nw ne/, 'n'],
[qw/sw se/, 's'],
[qw/nw s/, 'sw'],
);

sub min ($$) { $_[$_[0] > $_[1]] }
sub dist() { sum values %directions }

while(1){
my $starting=dist;

for(@reductions){
my($ca,$cb,$cc)=@$_;
my $value=min($directions{$ca},$directions{$cb});

if($value>0){
$directions{$ca}-=$value;
$directions{$cb}-=$value;
$directions{$cc}+=$value if $cc;
}
}

last if $starting==dist;
}

print dist;

Simplified further (now with recursion!)
routes = {}
for line in PUZZLE_INPUT.split("\n"):
route = line.split("")
routes[int(route[0])] = {int(x) for x in route[1].split(",")}

def get_group(root, found=set([])):
new = routes[root].difference(found)
found = found.union(new)
for i in new:
found = found.union(get_group(i, found))
return found

def count_groups():
count = 0
remaining = set(routes)
while remaining:
remaining = remaining.difference(get_group(remaining.pop()))
count += 1
return count

print len(get_group(0)) # Part 1
print(count_groups()) # Part 2

This has been a great exercise to sharpen the set() tool in my toolbox.

Hate this kind of problems.

from util import to_string_rows, get_input_string_rows, test, run
from collections import defaultdict

def main():
input = get_input_string_rows(12)

def get_programs(prog_from, routes):
queue = [prog_from]
visited = set()

while queue:
prog_from = queue.pop()
for prog_to in routes.get(prog_from, set()):
if prog_to not in visited:
visited.add(prog_to)
queue.append(prog_to)

return visited

def get_groups(routes):
groups = 0
visited = set()

for prog_from in routes.keys():
if prog_from not in visited:
visited |= get_programs(prog_from, routes)
groups += 1

return groups

def solve(input, fun):
routes = defaultdict(set)

for row in input:
(prog_from, progs_to, ) = row.split(' ')
for dst in progs_to.split(', '):
routes[prog_from].add(dst)
routes[dst].add(prog_from)

return fun(routes)

run([
(solve, input, lambda routes: len(get_programs('0', routes)), ),
(solve, input, get_groups, ),
])

if __name__ == '__main__':
main()

Good practice for BFS and im/mutable collections.

ABSOLUTELY MUTABLE version, since I'm autisming on minimizing line length, at the cost of immutability and readability:
import collection.{mutable => mu}
val a = mu.Map[Int, Set[Int]]()
for(l

>my @reductions=(
> [qw/n s/, ''],
> [qw/sw ne/, ''],
> [qw/se nw/, ''],
> [qw/nw ne/, 'n'],
> [qw/sw se/, 's'],
> [qw/nw s/, 'sw'],
>);


Yep, definitely first part.

Usually I'd try and learn the theory behind graph searches and such. This time I decided to use the exercise to learn a bit more about graph theory, and specifically the ruby 'rgl' library. The result is a pretty small solution - the bulk of which is parsing the input file.

require 'rgl/adjacency'
require 'rgl/traversal'
require 'rgl/condensation'
nodes = RGL::DirectedAdjacencyGraph.new
File.open('input-12-1.txt').each do |l|
node, neighbours = l.match(/^(\d+) (.*)$/).captures
neighbours.split(', ').each do |n|
nodes.add_edge(node,n)
end
end

puts nodes.bfs_search_tree_from('0').vertices.size
puts nodes.condensation_graph.vertices.size

What's your excuse scrub?

Day 12 input seems to be 2k for nodes and 2k for unique edges:
val e = collection.mutable.Set[Set[Int]]()
for(l

s/var/val for all places but cnt

I get up 4-5 hours after the puzzles are released.

IUIC might behave incorrectly in some cases when the input is minimal instead of exhaustive (e.g. if we have 4 5 but no 5 4), given an unlucky traversal order, since we don't add the opposite edge in the adjacency list.
Worked on my input tho.
Adjusted input handler:
def add(s: Int, d: Int) = a(s) = a.getOrElse(s, Set.empty) + d
for(l

But why have you not done day 3 part 2?

Because clearly, as anyone with a non-negligible level of reading comprehension can tell, the post you replied to was directed at anonymous user #226179, and since you replied to it, you must be anonymous user #226179.

I thought you were asking what's (anyone's) excuse for not being in top 20, not why hasn't he done D3P2.

>D3P2

>3DPD
FTFY

lol so fahny ecks deee

small theory input for day 11:
efficient way to detect and track (dis)jointed sets in graph is ```Union-find'''.
Naive way is coloring (when each disjointed set gets its color and when you connect 2 sets with new edge, those sets change to same color). When joining big sets it can take a while to rewrite values on many nodes.
Assuming each node is identified by unique number - Union-find keeps supporting array. Number on index of the node's number represents it's parent in hypothetical subtree (includes same nodes as joined set). Starting with all nodes pointing on itself.
New edge to graph can either be nodes in same or different set. Take the ending nodes and find their root in subtree [O(log n) complexity]. If roots are the same, edge is inside the same set and you do nothing with supporting array. If roots are different, you only join the roots. This joins the sets with single integer change.
At the end you can count the disjointed sets by counting nodes that point to itself and tell if 2 nodes belong to same set by comparing their roots.
It doesn't make the set size efficient though.

s/day 11/day 12/

lolumad

Ey neat. Didn't know about that.
en.wikipedia.org/wiki/Disjoint-set_data_structure#Applications
Looks like Boost uses it for connected components.

I'm the lowest ranked guy with all stars, probably because I started when day 10 came out.

Oof, and I thought I was bad starting on day 6

not on the old leaderboard ;_; that belongs to me

>adventofcode.com/2015/day/19
>this prompt
>Red-Nosed Reindeer nuclear fusion/fission plant

2015's prompts were much more fun than 2017's are

To make things even better new tasks appear so early for me I lose 3 and a half hours before I get at them.

I'll repost my solutions for d12, since it's the old thread now:

(def in (.trim (slurp "puzzle-inputs/input12")))
(def parsed-in (parse-table in "[, ]+"))
(def pipes (into {} (map #(vector (first %) (into #{} (drop 2 %)))) parsed-in))

(defn get-connected [ret-set pipes-map pid]
(let [new-ret-set (conj ret-set pid)
new-additions (filter (complement new-ret-set) (pipes-map pid))]
(if (not-empty new-additions)
(reduce #(get-connected %1 pipes-map %2) new-ret-set new-additions)
new-ret-set)) )

(def day12p1 (count (get-connected #{} pipes "0")))

(def day12p2 (count (into #{} (map #(get-connected #{} pipes %)) (keys pipes))))

LONDON
O
N
D
O
N

This was good because it filters out people who don't know what a graph is

>storing edge(v1,v2) as set(v1,v2)
obviously misbehaves on edge(v1,v2)

The assignment literally tells you how to run BFS. You can do part 1 without even knowing the definition of a graph if you pick/define the right data structure.

london would have been +2 hours

>edge(v1,v1)
FTFM

Finally, got some time to solve day 12
from re import match
from collections import defaultdict

nodes = defaultdict(list)


with open("day12input.txt") as inputData:
for row in inputData:
m = match("^(\d+) () (.*)$", row)
n = int(m.group(1))
nodes[n] = [int(el) for el in m.group(3).split(", ")]


toVisit = []
visited = []
groupSize = defaultdict(int)
totalGroups = 0

while(len(visited) != len(nodes)):
totalGroups += 1

for i in range(len(nodes)):
if (i not in visited):
break
toVisit.append(i)

while(len(toVisit) > 0):
el = toVisit.pop()
if (el not in visited):
toVisit.extend(nodes[el])
groupSize[i] += 1
visited.append(el)

print("Part 1 result:", groupSize[0])
print("Part 2 result:", totalGroups)

I give up, where then?

Surprised how long I took there, considering how simple the actual solution ended up being.

- via DFS. Give it a big enough N and hello stack overflow! This ain't directly tail call optimizable
- also keeping only local mutability
def reachableFrom(root: Int) = {
var visited = mu.Set(root)

def walk(n: Int): Unit = {
visited add n
a(n) filterNot {visited(_)} foreach {walk(_)}
}
walk(root)

visited.toSet
}

Blame Twain (or whoever twat actually said it):
“I didn't have time to write a short [thingum], so I wrote a long one instead.”

captcha: turistics mexico

- via DFS. Give it a big enough N and hello stack overflow! This ain't directly tail call optimizable
- also keeping only local mutability
def reachableFrom(root: Int) = {
var visited = mu.Set(root)

def walk(n: Int): Unit = {
visited add n
a(n) filterNot(visited) foreach(walk)
}
walk(root)

visited.toSet
}

package main

import (
"bufio"
"fmt"
"os"
"strings"
"unicode"
)

var graph = make(map[string]string)

func subtreeRoot(n string) string {
for graph[n] != n {
n = graph[n]
}
return n
}

func subtreeSize(node string) int {
root := subtreeRoot(node)
c := 0
for n, _ := range graph {
if subtreeRoot(n) == root {
c++
}
}
return c
}

func countSubtrees() int {
c := 0
for n, p := range graph {
if n == p {
c++
}
}
return c
}

func main() {
scanner := bufio.NewScanner(os.Stdin)
for scanner.Scan() {
fld := strings.FieldsFunc(
scanner.Text(),
func(c rune) bool { return !unicode.IsNumber(c) },
)
for _, n := range fld {
if _, ok := graph[n]; !ok {
graph[n] = n
}
if subtreeRoot(fld[0]) != subtreeRoot(n) {
graph[subtreeRoot(n)] = subtreeRoot(fld[0])
}
}
}
fmt.Println(subtreeSize("0"))
fmt.Println(countSubtrees())
}

>no generics

I was afraid part two would involve finding some minimum distance.

You would just need a BFS if it did

Yes, but that would be ugly.

Day12 in Nim
import strutils, sequtils, tables, sets

var
input = readFile("input.txt").strip().splitLines()
pipes = initTable[int, seq[int]]()
maxid = 0
groups = 1

proc add(s: var HashSet[int], x: int) =
s.incl x
for y in pipes[x]:
if y notin s:
add s, y
pipes.del x

for line in input:
let items = map(split(replace(replace(line, ","), " ")), parseInt)
pipes[items[0]] = items[1..^1]
maxid = max(maxid, max(items))

var s = initSet[int]()
add s, 0
echo s.len
for i in 1..maxid:
if i in pipes:
groups += 1
var s = initSet[int]()
add s, i

echo groups

Not really, it is standard pathfinding in a graph

c#
Dictionary map = File.ReadAllLines(@"N:\input.txt").Select((kv) => new { kv }).ToDictionary(pair => int.Parse(pair.kv.Replace(" ", "|").Split('|').First()), pair => pair.kv.Replace(" ", "|").Split('|').Last().Split(',').Select(x => int.Parse(x)).ToArray()); ;
HashSet chain = new HashSet(); chain.Clear();
List groups = new List(); groups.Clear();
foreach (int id in map.Keys)
if (!groupExist(id))
groups.Add(groupByID(id));
Console.WriteLine(groups.Count);
// helpers
int[] groupByID(int groupID)
{
int c = 0; chain.Clear(); chain.Add(groupID);
while (c < chain.Count)
{
foreach (int z in map[chain.ElementAt(c)]) { chain.Add(z); }
c++;
}
return chain.ToArray();
}
bool groupExist(int ID)
{
for (int i = 0; i < groups.Count; i++) { if (groups[i].Contains(ID)) { return true; } }
return false;
}

Why is BFS better than DFS for day 12?

Is it?

the fuck is this supposed to mean

I mean ugly in the sense that it wouldn't be efficient.

There is no difference, you are not looking for a path, you are just crawling through all elements.

That's what I thought...

>linear solution is inefficient in immutable pure functional language
I see.............

>281 char long line
>sloppy copy-paste 12 char useless indentation
>uses hardcoded absolute file path
>uses file instead of stdin
>no mention of which day and parts this is for
>not even a single line comment to mention the approach taken (muh self-documenting code)
>generally shitty readability

I pity the sad fucks who'll have to work with your code if the world is unlucky enough to employ you as a code monkey somewhere

You could do A* if you had an idea for an heuristic, but I can't see any for this problem

Neat! I've been considering doing a few of these in Crystal, but I keep getting hung up on the thought that it would be more worthwhile to put that effort into a language with higher rising adoption.

But then I get hung up on all the drawbacks people bring up about such languages, like Go and Rust.

DFS is perfectly fine for a problem as small and non-demanding as d12 - e.g. just werks
No pragmatic difference in this case.
But in the general case:
- possible stack overflow depending on stack limits and input size
- some overhead due to the function calls, compared to a loop

Oh fuck, I though BFS stood for "brute force search", and not breadth-first search. Tbh I didn't really consider how I would actually find the smallest distance, so I just though the naive algorithm would be O(n^2) or even worse.

you can implement DFS with a loop and a stack

>I though BFS stood for "brute force search"
Lmao I'm going to do that to someone one day

>281 char long line
And? It is collection population, nobody cares what happens there.

>sloppy copy-paste 12 char useless indentation
The fuck is this supposed to mean?

>uses hardcoded absolute file path
And?
With the same success you could accuse me of not doing verification of the input data and exception handling. Or for not implementing user interface where he submits ID or data. Sure, I could write it and make it bloated 1000 lines in the end but why in the fuck would I do that if the task is pretty specific?
Are you genuinely autistic or just plain bored and want to fuck my brains out?

>uses file instead of stdin
AND?

>no mention of which day and parts this is for
WHY DOES IT MATTER MOTHERFROGGER

>not even a single line comment to mention the approach taken (muh self-documenting code)
WHO THE FUCK WOULD CARE ABOUT SOME RANDOM CODE ON Sup Forums THAT WILL DIE IN NEXT 1-2 HRS ALONG WITH THIS SHITTY THREAD

>generally shitty readability
YOU CAN SAY THAT ABOUT ANY CODE THAT WASNT WRITTEN BY YOU

>I pity the sad fucks who'll have to work with your code if the world is unlucky enough to employ you as a code monkey somewhere
IT'S A FUCKING HOBBY YOU MONGOLOID I'M A PROFESSIONAL 10 YEARS EXPERIENCED JANITOR AT NASA WHO CARES


REEEEEEEEEEEEEEEEEEEEEEEEEEEEEE


(chill m8)

memo = [-1 for x in input]
def f(x):
if memo[x] > 0:
return True if memo[x] == 1 else False
if x == 0:
return True
if input[x] == []:
memo[x] = 0
return False
for y in input[x]:
if f(y) is True:
memo[y] = 1
return True
memo[y] = 0
return False
total = 0
for i in range(len(input)):
if f(i) is True:
total+=1
print total


What's wrong with my memoization? Recursive pipes have been filtered, yet still I hit maximum recursion

never improve™

Wew lads look at this dropoff. I was just wondering when the next Malthusian drop would happen, but it doesn't look like there's much to weed out anymore.

AmIDoingItRight?

def AOC12(string):
d = dict()
for line in string.splitlines():
numbers = {int(n) for n in re.findall(r'\d+', line)}
for n in list(numbers):
if n in d: numbers.update(d[n])
for n in numbers:
d[n] = numbers
yield len(d[0])
yield len(set(id(x) for x in d.values()))

Man, 2015 day 21 was fucking tedious

>rages because he gets called out on being poojet
>tells the user to chill
???

holy shit user

>someone genuinely rages or being upset
>on Sup Forums
you really should go back

I really just deep searched all the stats combo that can win and counted items by hand with their value/price ratio.

thanks for using the mario hat user

damage control

didnt really see the reason it just some quickly put together code solution to a random programming taks on the interwebs across other thousands of similar tasks nobody really gives shit about. Unless you genuinely believe that on job talk if you mentioned that you have solved some AoC puzzles in X lines they will be in awe kek

I might pretty it up after dinner cooking is done tho

shit you've got me
how will I ever recover now

And my shitty code for it:
from itertools import *
from collections import *
from math import ceil
bhp = 103
bdm = 9
bar = 2
hp = 100
dm = 0
ar = 0
weapons = [[8,4,0],[10,5,0],[25,6,0],[40,7,0],[74,8,0]]
armors = [[13,0,1],[31,0,2],[53,0,3],[75,0,4],[102,0,5]]
rings = [[25,1,0],[50,2,0],[100,3,0],[20,0,1],[40,0,2],[80,0,3]]
goldw = dict()
goldl = dict()
cr = count()
for numweapons in [1]:
for numarmors in [0,1]:
for numrings in [0,1,2]:
for weapon_list in combinations(weapons,numweapons):
for armor_list in combinations(armors,numarmors):
for ring_list in combinations(rings,numrings):
indic = next(cr)
gd = 0
dm = 0
ar = 0
for weapon in weapon_list:
gd += weapon[0]
dm += weapon[1]
ar += weapon[2]
for armor in armor_list:
gd += armor[0]
dm += armor[1]
ar += armor[2]
for ring in ring_list:
gd += ring[0]
dm += ring[1]
ar += ring[2]

infl = dm-bar
infl = infl if infl > 0 else 0
taken = bdm-ar
taken = taken if taken > 0 else 0
turns_kill = ceil(bhp/infl) if infl else float('+inf')
turns_die = ceil(hp/taken) if taken else float('+inf')
if turns_kill turns_kill > turns_die:
goldl[indic] = gd
print(min(goldw.values()))
print(max(goldl.values()))

daily reminder that this is just a wholesome annual event, its okay to ask for help.

also shitting on somebody else's work in a passive aggressive fashion on a japanese anonymous crossdresser forum with no intention to offer any improvements outs you as the angsty loser that you are.

>just

It might be "just" that for you, but I don't know how to do what you described, or at least what the terminology "deep searched" actually refers to.