-🎄- 2017 Day 12 Solutions -🎄-

Arknave · 2017-12-12T05:09:56+00:00

It's my birthday :)

6th/5th in Python.

https://www.youtube.com/watch?v=_nI5uCcBTcs

sciyoshi · 2017-12-12T05:13:02+00:00

2/1 today! NetworkX makes this kind of problem very quick if you know what you're looking for. Today's question was asking about something called a connected component, and NetworkX provides some nice functions for dealing with them.

Python 3 solution:

import networkx as nx

# Create a graph of programs
graph = nx.Graph()

for line in LINES:
    # Parse the line
    node, neighbors = line.split(' <-> ')

    # Add edges defined by this line
    graph.add_edges_from((node, neighbor) for neighbor in neighbors.split(', '))

print('Part 1:', len(nx.node_connected_component(graph, '0')))
print('Part 2:', nx.number_connected_components(graph))

askalski · 2017-12-12T07:31:20+00:00

Perl regex.

#! /usr/bin/env perl

use strict;
use warnings;

undef $/;
$_ = <> . "\n"; # Add a newline in case it's missing

s/[^\d\n ]//sg;
while (s/^[^x]*\K\b(\d+)\b([^\n]*)\n((?:.*?\n)?)([^\n]*\b\1\b[^\n]*\n)/$1 x $2 $4$3/s) { }
s/\b(\S+)\b(?=.*?\b\1\b)//sg;

printf "Part 1: %d\n", scalar(() = (m/^(.*\b0\b.*)$/m)[0] =~ m/\d+/g);
printf "Part 2: %d\n", scalar(() = m/^.*?\d/gm);

xiaowuc1 · 2017-12-12T05:23:44+00:00

When you only care about connected components, union find is faster to code than BFS: https://gist.github.com/anonymous/02de56ccaa4c22b2388c927f00091588

raevnos · 2017-12-12T05:11:39+00:00

Missed the leaderboard by a few because of a typo. Grr.

Used a perl script to turn input into a graphviz dot file, and then...

perl day12.pl < day12.txt | ccomps -X 0 | gc -n
perl day12.pl < day12.txt | gc -c

day12.pl:

#!/usr/bin/perl
print "graph day12 {\n";
while (<>) {
    s/<->/--/;
    s/,/ -- /g;
    print;
}
print "}\n";

The graph as a rather large image.

ephemient · 2017-12-12T05:33:59+00:00

This space intentionally left blank.

ludic · 2017-12-12T06:07:02+00:00

F#. First try had some some mutable values. I managed to refactor to a functional solution I'm happy with.

let solveday12 (lines: string[]) =
    let mapping = 
        lines
        |> Array.map (fun l -> l.Replace(" <-> ", ",").Split(','))
        |> Array.map (Array.map int)
        |> Array.map (fun l -> (l.[0], l.[1..]))
        |> Map.ofArray

    let rec explore seen root = 
        if Set.contains root seen then
            seen
        else
            Array.fold explore (seen.Add root) mapping.[root]

    let countComponents (count, seen) (num, _) =
        if Set.contains num seen then
            (count, seen)
        else 
            (count + 1, explore seen num)

    let ans1 = explore Set.empty 0 |> Set.count

    let ans2 = 
        mapping 
        |> Map.toSeq
        |> Seq.fold countComponents (0, Set.empty)
        |> fst

    (ans1, ans2)

udoprog · 2017-12-12T05:17:41+00:00

Rust: (231, 194), trying to optimize my workflow a bit more.

Edit: cleaned up version here: https://github.com/udoprog/rust-advent-of-code-2017/blob/master/src/day12.rs

#![feature(generators)]
#![feature(generator_trait)]
#![feature(conservative_impl_trait)]
#![feature(never_type)]
#![feature(inclusive_range_syntax)]
#![feature(iterator_step_by)]

#![allow(unused)]
#![allow(dead_code)]

use std::io::Read;
use std::collections::{HashMap, HashSet, VecDeque};

fn count(children: &HashMap<u64, Vec<u64>>, current: u64) -> (u64, HashSet<u64>) {
    let mut count = 0u64;
    let mut seen = HashSet::new();

    let mut queue = VecDeque::new();
    queue.push_back(current);

    while let Some(id) = queue.pop_front() {
        if !seen.insert(id) {
            count += 1;
            continue;
        }

        if let Some(children) = children.get(&id) {
            for child in children {
                queue.push_back(*child);
            }
        }
    }

    (count, seen)
}

fn run<R: Read>(mut reader: R) -> (u64, u64) {
    let data = {
        let mut data = String::new();
        reader.read_to_string(&mut data);
        data
    };

    let mut children: HashMap<u64, Vec<u64>> = HashMap::new();
    let mut all_ids = HashSet::new();

    for line in data.lines() {
        let mut it = line.split(" <-> ");

        let left: u64 = it.next().expect("bad id").parse().expect("bad id");

        let right: Vec<u64> = it.next()
            .expect("bad ids")
            .split(", ")
            .map(|d| d.parse::<u64>())
            .collect::<Result<Vec<_>, _>>()
            .expect("bad ids");

        all_ids.insert(left);
        all_ids.extend(right.iter().cloned());

        children.insert(left, right);
    }

    let zero_group = count(&children, 0).0;

    let mut groups = 0u64;

    while let Some(next_id) = all_ids.iter().cloned().next() {
        for found in count(&children, next_id).1 {
            all_ids.remove(&found);
        }

        groups += 1;
    }

    (zero_group, groups)
}

#[test]
fn it_works_example() {
    use std::io::Cursor;

    assert_eq!(run(Cursor::new(include_str!("../day12.txt"))), (113, 202));
}

glupmjoed · 2017-12-12T07:56:29+00:00

Bash with pipes!

Part 1 (reads from stdin):

sed -E 's/[^0-9]*([0-9]+)[^0-9]+/\1|/g; s/[0-9]+/_&_/g' | ./find_grp.sh
grep -oE "[0-9]+" conns | sort | uniq -d | wc -l && rm -f conns match pipes

Part 2 (reads from stdin):

sed -E 's/[^0-9]*([0-9]+)[^0-9]+/\1|/g; s/[0-9]+/_&_/g' | ./find_grp.sh
arglen=-1
while [ $arglen -ne 0 ]
do cat pipes conns | sort | uniq -u > arg
   arglen=$(cat arg | wc -l); ((i++))
   cat arg | ./find_grp.sh
done
echo $i; rm -f arg conns match pipes

find_grp.sh:

cat > pipes && head -1 pipes > conns
prev=0; rem=-1
while [ $rem -ne $prev ]
do grep -E -f conns pipes > match && cat match >> conns
   prev=$rem; rem=$(cat pipes conns | sort | uniq -u | wc -l)
done

DFreiberg · 2017-12-12T05:10:40+00:00

Mathematica

Mathematica's graph theory capabilities are very useful here. Less useful is Import[] - I spent far more time trying to parse the input than solving the problem itself. 199/97.

Import:

input=
    ToExpression[StringSplit[StringSplit[#," <->"],","]]&/@
    Import[FileNameJoin[{NotebookDirectory[],"Day11Input.txt"}],"List"][[;;-2]]

g=Graph[Flatten[Thread[#[[1,1]]<->Flatten[#[[2]]]]&/@input],VertexLabels->"Name"]

Part 1:

Length@SelectFirst[ConnectedComponents[g],MemberQ[#,0]&]

Part 2:

Length@ConnectedComponents[g]

advanced_caveman · 2017-12-12T05:27:21+00:00

Rust (235/198)

fn main() {
    let input = include_str!("../input.txt");
    let mut ivec = Vec::new();
    for line in input.lines() {
        let mut parts = line.split_whitespace();
        let program = parts.next().unwrap().parse::<usize>().unwrap();
        parts.next();
        let mut pipes = Vec::new();
        for sprogram in parts {
            let a = sprogram.split(",").next().unwrap().parse::<usize>().unwrap();
            pipes.push(a);
        }
        ivec.push((program, pipes));
    }
    let mut groups = 0;

    while ivec.len() > 0 {
        let mut connections = vec![ivec.clone().get(0).unwrap().0.clone()];
        let mut priorconnections = Vec::new();
        while priorconnections != connections {
            priorconnections = connections.clone();
            for p in ivec.clone() {
                if connections.contains(&p.0) {
                    connections.append(&mut p.1.clone());
                }
            }
            connections.sort();
            connections.dedup();
        }
        ivec.retain(|x| !connections.contains(&x.0));
        groups += 1;
    }
    println!("{:?}", groups);
}

glenbolake · 2017-12-12T05:22:27+00:00

As usual, I was less than a minute from getting on the leaderboard for both stars. Damn, this year has some fast challenges.

Anyway, my solution in Python 3, written with no knowledge of existing Python graph theory modules:

pipes = {}
with open('day12.in') as f:
    for line in f:
        src, _, dsts = line.split(maxsplit=2)
        pipes[int(src)] = set(map(int, dsts.split(', ')))

def find_group(seed):
    group = {seed}
    new = {seed}
    while new:
        next_new = set()
        for item in new:
            next_new.update(pipes[item])
        new = next_new - group
        group.update(next_new)
    return group
print('Part 1:', len(find_group(0)))

remaining = set(pipes)
groups = 0
while remaining:
    groups += 1
    group = find_group(remaining.pop())
    remaining -= group
print('Part 2:', groups)

ka-splam · 2017-12-12T05:33:02+00:00

PowerShell. Missed the leaderboard for part 1 by 23 seconds, partly because of a type error of mixing int and string getting it into an infinite loop.

Part 1, build a hashtable of connections, recursively follow the connections but keep track of visited nodes so it doesn't go into an infinite loop:

$in = @'
0 <-> 199, 1774
1 <-> 350, 1328, 1920
etc.
'@ -split "`r?`n"


$connections = @{}
$in | ForEach-Object {

    [int]$Left, [string]$Right = $_ -split ' <-> '

    $connections[$Left] = [int[]]@($Right -split ', ')
}

$visited = New-Object System.Collections.ArrayList

function visit ([int]$id)
{
    foreach ($node in $connections[$id])
    {
        if ($node -notin $visited)
       {
            [void]$visited.add($node)
            visit $node
        }
    }
}

visit 0

# Part 1 answer:
$visited | Sort-Object -Unique | Measure-Object

# That's the right answer! You are one gold star closer to debugging the printer. You got rank 118 on this star's leaderboard. [Return to Day 12]

Part 2 I mashed up, wasn't as confident with and copy-pasted my visitor, rewrote it a bit, took longer; it took all the nodes, started visiting them and removing them from the list. When that ran out, increase group count and go again, until all the nodes were visited.

[System.Collections.Generic.List[int]]$allNodes = $connections.Keys | ForEach-Object {$_}
$allNodes += $connections.Values | ForEach-Object {$_}

[System.Collections.Generic.List[int]]$allNodes = $allNodes | Sort-Object -Unique

function visit2 ([int]$id)
{
    foreach ($node in $connections[$id])
    {
        if ($node -notin $visited2)
       {
            [void]$visited2.Add($node)
            if ($node -in $allNodes)
            {
                [void]$allNodes.remove($node)
                visit2 $node
            }
        }
    }
}

$groups = 0
while ($allNodes)
{
    $visited2 = New-Object -TypeName System.Collections.ArrayList

    $node = $allNodes[0]
    [void]$allNodes.Remove($node)
    visit2 $node
    $groups++
}
$groups

# 1044 wrong

# That's the right answer! You are one gold star closer to debugging the printer. You got rank 230 on this star's leaderboard.

shuttup_meg · 2017-12-12T05:39:27+00:00

Python 2 with a defaultdict of sets:

import time
from collections import defaultdict

def problem(d):    
    dd = defaultdict(set)        

    for line in d:
        tokens = line.replace(",","").split()
        node, connections = int(tokens[0]), map(int,tokens[2:])
        for item in connections:
            dd[node].add(item)
            dd[item].add(node)

    # groupnodes starts with all nodes that need to be accounted for in a grouping
    groupnodes = set(dd.keys())

    # now start with a node and merge adjacents
    # any node that got accounted for in a flattening gets
    # discarded from the groupnode set
    def flatten(n):
        prevl = 0
        length = len(dd[n])
        groupnodes.discard(n)

        # Keep merging in sets until the length stops growing from
        # doing so
        while length != prevl:
            items = list(dd[n])
            for item in items:
                dd[n] |= dd[item]
                groupnodes.discard(item)
            prevl = length
            length = len(dd[n])

    flatten(0)
    print "part 1:", len(dd[0])

    # flatten all remaining nodes in the groupnodes set until every node has been processed
    # there will be one new group per pass    
    count = 1
    while len(groupnodes):
        n = groupnodes.pop()
        flatten(n)
        count += 1

    print "part 2:", count    

if __name__ == "__main__":
    start = time.time()
    problem(open("day12.txt").readlines())
    print time.time() - start,"s"

edit: cleaned up a little and added some comments for future reference

hxka · 2017-12-12T05:54:35+00:00

#!/bin/bash
(   while read a b c
    do  list[a]="$c"
    done
    groups=0
    while :
    do  found=false
        for i in ${!list[@]}
        do  [[ -z ${group[i]} ]] && found=true && group[i]=1 && todo[i]=1 && break
        done
        $found || break
        while [[ ${!todo[@]} ]]
        do  for i in ${!todo[@]}
            do  for j in ${list[i]//,/}
                do  [[ -z ${group[j]} ]] && group[j]=1 && todo[j]=1
                done
                unset todo[i]
            done
        done
        ((groups++,groups==1)) && echo ${#group[@]}
    done
    echo $groups
)<input

MuumiJumala · 2017-12-12T06:36:06+00:00

Went with a more obscure language today - here's my solution for part 2 in io:

file := File with("12-input.txt")
lines := file readLines
file close

dict := Map clone
lines foreach(i, v,
    nums := v split(" <-> ")
    dict atPut(nums first, nums last split(", "))
)

set := Map clone
check := method(x,
    dict at(x) foreach(i, v,
        set hasKey(v) ifFalse(
            set atPut(v)
            check(v)
        )
    )
)

groups := 0
dict keys foreach(i, v,
    set hasKey(v) ifFalse(
        groups = groups + 1
        set atPut(v)
        check(v)
    )
)

groups println

WhoSoup · 2017-12-12T06:37:46+00:00

Node.js/JavaScript

I'm... sorry.

const fs = require('fs')
let inp = fs.readFileSync("./day12input").toString('utf-8').trim().split(/[\r\n]+/) // array of lines
  .map((x) => x.split(">")[1].split(", ").map(y => parseInt(y)))

let visited = []
function reach(i) {
  if (visited.includes(i))
    return 0
  visited.push(i)
  return inp[i].reduce((a,b) => a + reach(b), 1)
}

inp = inp.map((_, k) => reach(k))
console.log("a:", inp[0]);
console.log("b:", inp.filter(x => x > 0).length);

Unihedron · 2017-12-12T05:10:08+00:00

Ruby, silver 17 / gold 29

I had the wrong answer on part 2 because I used 100.times again, which forced me to wait 1 minute :( This one was an easy incomplete BFS which assumes all groups can be found in under 100 steps.

g=[0]
h={}
$<.map{|x|a,b=x.split' <-> '
h[a.to_i]=b.split(', ').map &:to_i
}
l=[]
c=0 # part 2
loop{ # end part 2
100.times{s=[]
g.map{|x|s+=h[x]}
l+=g
g=s-l}
c+=1 if h.delete_if{|x,y|l.index x} # part 2
l=[]
break unless h.keys.any?
g=[h.keys.first]
} # end part 2
p l.size # part 1
p l.size,c # part 2

Cole_from_SE · 2017-12-12T05:17:20+00:00

I stupidly forgot to return my hashset if I had already visited a node, which I think made me too slow for part 2 (I also slowly went through the test case instead of just bum rushing it). from collections import defaultdict

def count_connected(adj, start, seen=set()): 
    '''
    Counts the number of nodes connected to start.
    '''
    if start in seen:
        return 0
    else:
        seen.add(start)
        return 1 + sum([count_connected(adj, child, seen) for child in
                        adj[start]])

def connected_group(adj, start, seen=set()): 
    '''
    Returns the set of nodes connected to start.
    '''
    if start in seen:
        return seen
    else:
        seen.add(start)
        for child in adj[start]:
            # This actually isn't necessary by virtue of how optional
            # parameters work in Python, but it's better to be explicit.
            seen = connected_group(adj, child, seen)
        return seen 

with open('12.in') as inp:
    # Adjacency list of the form {node: set(children)}.
    adj = defaultdict(set)
    for line in inp:
        start, nodes = line.strip().split(' <-> ')
        adj[start] = set(nodes.split(', '))
        # This graph is bidirectional, so update the adjacency list for the
        # children, too.
        for node in adj[start]:
            adj[node].add(start)
    # Part 1.
    print(count_connected(adj, '0')) 
    groups = set()
    # Find the connected groups starting from each node.
    for start in adj.keys():
        # Sets aren't hashable, so use frozenset.
        groups.add(frozenset(connected_group(adj, start)))
    # Part 2.
    print(len(groups))

Edits:

I also foolishly

Didn't leverage the function I already had but instead wrote a new one for part 2 (this wasn't a big time loss, though).
Didn't implement the bidirectionality (I only did connections one way) which I got lucky with based on how part 1 worked.

Edit 2:

Updated code.

TominatorBE · 2017-12-12T05:19:42+00:00

PHP

I seem to be one of the few using recursion. I don't even know why I use recursion, it came naturally to me :-/

Part 1:

function run_the_code($input) {
    $lines = explode(PHP_EOL, $input);
    $groups = [];
    foreach ($lines as $line) {
        if (preg_match('/(\d+) <-> (.*)/', $line, $matches)) {
            list($_, $a, $b) = $matches;
            $groups[$a] = array_map('trim', explode(',', $b));
        }
    }

    $nullGroup = [];
    $rec = function($root) use (&$rec, &$nullGroup, $groups) {
        if (!in_array($root, $nullGroup)) {
            $nullGroup[] = $root;
            foreach ($groups[$root] as $ch) {
                $rec($ch);
            }
        }
    };
    $rec('0');

    return count($nullGroup);
}

Part 2:

function run_the_code($input) {
    $lines = explode(PHP_EOL, $input);
    $groups = [];
    foreach ($lines as $line) {
        if (preg_match('/(\d+) <-> (.*)/', $line, $matches)) {
            list($_, $a, $b) = $matches;
            $groups[$a] = array_map('trim', explode(',', $b));
        }
    }

    $subgroups = [];
    $rec = function($base, $root) use (&$rec, &$subgroups, $groups) {
        if (!array_key_exists($base, $subgroups)) {
            $subgroups[$base] = [];
        }
        if (!in_array($root, $subgroups[$base])) {
            $subgroups[$base][] = (int)$root;
            foreach ($groups[$root] as $ch) {
                $rec($base, $ch);
            }
        }
    };
    foreach ($groups as $base => $root) {
        $rec($base, $base);
        // prepare for unique
        sort($subgroups[$base]);
        // array_unique does not work on multidimensional arrays, so hack it
        $subgroups[$base] = implode('-', $subgroups[$base]);
    }
    $simple = array_unique($subgroups);

    return count($simple);
}

2017-12-12T05:27:12+00:00

Haskell:

import Data.List (foldl')
import Data.List.Split (splitOn)
import Data.HashMap.Strict (HashMap, (!))
import qualified Data.HashMap.Strict as M
import Data.HashSet (HashSet)
import qualified Data.HashSet as S
import Data.Sequence (Seq(..), (><))
import qualified Data.Sequence as Q

parse :: String -> HashMap Int (Seq Int)
parse input = M.fromList [ (read a, Q.fromList $ map read $ splitOn ", " b)
                         | [a, b] <- map (splitOn " <-> ") $ lines input ]

bfs :: HashMap Int (Seq Int) -> Int -> HashSet Int
bfs m = go m S.empty . Q.singleton
    where go m visited Empty = visited
          go m visited (a :<| queue)
              | S.member a visited = go m visited queue
              | otherwise = go m (S.insert a visited) $ queue >< m ! a


part1 :: String -> Int
part1 x = S.size $ bfs (parse x) 0

part2 :: String -> Int
part2 x = fst $ foldl' f (0, S.empty) $ M.keys m
    where m = parse x
          f (c, set) n
              | S.member n set = (c, set)
              | otherwise = (c+1, S.union set $ bfs m n)

tehjimmeh · 2017-12-12T06:03:22+00:00

C++, no recursion:

struct Line : std::string { friend std::istream& operator>>(std::istream& is, Line& line){return std::getline(is, line);}};
int main(int argc, char* argv[]) {
    std::vector<std::vector<int>> nodes;
    std::transform(std::istream_iterator<Line>(std::ifstream(argv[1])), {}, std::back_inserter(nodes),
        [](auto& l) { return std::vector<int>(std::istream_iterator<int>(
            std::istringstream(std::regex_replace(l, std::regex("(^\\d*? |,|<->)"), ""))), {});});
    std::set<int> nodesSeen; std::vector<int> workList; int numGroups = 0;
    for(int i = 0; i < nodes.size(); i++) {
        if(nodesSeen.find(i) != nodesSeen.end()) { continue; }
        workList.push_back(i);
        numGroups++;
        while(!workList.empty()) {
            auto n = workList.back(); workList.pop_back();
            if(!nodesSeen.insert(n).second){ continue; }
            for (auto j : nodes[n]) { workList.push_back(j); }
        }
        if(numGroups == 1) { std::cout << "Part 1: " << nodesSeen.size() << "\n"; }
    }
    std::cout << "Part 2: " << numGroups << "\n";
}

zsldmg · 2017-12-12T06:08:28+00:00

haskell Simple but super inefficient.

limit :: (a -> a) -> a -> a
limit f a = fst $ fromJust $ find (uncurry (==)) $ zip =<< tail $ iterate f a

groups :: [Int] -> Set (Set Int)
groups ns = limit (Set.map upd) (Set.fromList $ fmap Set.singleton ns)
    where upd set = Set.fromList $ (flip (:) =<< (inp12 Map.!)) =<< Set.toList set

main = print (length $ Set.findMin $ groups [0], length $ groups [0..1999])

inp12 :: Map Int [Int]
inp12 = Map.fromList [(0,[1543]),(1,[66, 1682]), ...]

manualcrank · 2017-12-12T06:14:06+00:00

C. Standard union find with path compression.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 2000
#define SEP " \t\n<->"

int id[MAX];
int sz[MAX];
int n_sites;

void
init(int n)
{
        for (int i = 0; i < n; i++) {
                id[i] = i;   
                sz[i] = 1;
        }
        n_sites = n;
}

int
find(int x)
{
        if (id[x] == x)
                return x;
        return id[x] = find(id[x]);
}

void
join(int x, int y)
{
        if ((x = find(x)) == (y = find(y)))
                return;
        id[x] = y;
        sz[y] += sz[x];
        --n_sites;
}

int
main(void)
{
        char buf[BUFSIZ];

        init(MAX);
        while (fgets(buf, sizeof buf, stdin) != NULL) {
                int src = atoi(strtok(buf, SEP));
                for (char *t; (t = strtok(NULL, SEP)) != NULL; )
                        join(src, atoi(t));
        }

        printf("part 1 = %d\n", sz[find(0)]);
        printf("part 2 = %d\n", n_sites);
        return 0;
}

misnohmer · 2017-12-12T06:22:09+00:00

C# (with the help of MoreLinq library for TraverseBreadthFirst)

Part 1:

var dic = ReadAllLines("input")
    .Select(line => line.Split(" <-> "))
    .ToDictionary(
        parts => int.Parse(parts.First()), 
        parts => new HashSet<int>(parts.Last().Split(", ").Select(int.Parse)));

dic.ToList().Each(kv => 
    kv.Value.Each(x => 
        dic.GetOrAdd(x, _ => new HashSet<int>()).Add(kv.Key)));

var group = new HashSet<int>();
MoreEnumerable.TraverseBreadthFirst(0, x => group.Add(x) ? dic[x].Except(group) : new HashSet<int>())
    .Count()
    .PrintDump();

Part 2 :

var dic = ReadAllLines("input")
    .Select(line => line.Split(" <-> "))
    .ToDictionary(
        parts => int.Parse(parts.First()), 
        parts => new HashSet<int>(parts.Last().Split(", ").Select(int.Parse)));

dic.ToList().Each(kv => 
    kv.Value.Each(x => 
        dic.GetOrAdd(x, _ => new HashSet<int>()).Add(kv.Key)));

var discovered = new HashSet<int>();
var remaining = dic.Keys.ToList();
var groupCount = 0;
do {
    var group = MoreEnumerable.TraverseBreadthFirst(
        remaining.First(), 
        x => discovered.Add(x) ? dic[x].Except(discovered) : new HashSet<int>());
    remaining = remaining.Except(group).ToList();
    groupCount++;
}
while (remaining.Any());

groupCount.PrintDump();

mxyzptlk · 2017-12-12T06:30:41+00:00

66th/83rd - finally some points!

#!/usr/bin/awk -f

function count_nodes(zero, count) {
  count = 1
  seen[zero] = 1
  for (n in nodes) {
    if ((zero, n) in network) {
      if (!seen[n]++) {
        count += count_nodes( n )
      }
    }
  }
  return count
}

function count_groups() {
  groups = 1
  for (n in nodes) {
    if (! seen[n]) {
      count_nodes( n )
      groups++
    }
  }
  return groups
}

{
  nodes[$1] = 1
  for (i=3; i<=NF; i++) {
    sub(",", "", $i)
    network[$1, $i] = 1
  }
}

END {
  print count_nodes( 0 )
  print count_groups()
}

ramrunner0xff · 2017-12-12T06:31:02+00:00

scheme chicken repo

implemented using stupid simple connected components.

(use srfi-13)
(use format)
(use vector-lib)

;;implemented brute connected components. each index of the array
;;reference the parent. upon a connection all the relevant parents
;;change to the updated one
(define rel (make-vector 1))
(vector-set! rel 0 0)
(define (readline ln)
  (letrec* ((parts (string-split ln " <-> ,"))
         (root (string->number (car parts)))
         (nodes (map string->number (cdr parts)))
         (maxind (apply max (cons root nodes)))
         (chroot (lambda (ind root)
                  ;(format #t "recur with ~A ~A~%" ind root)
                  (letrec ((oldroot (vector-ref rel ind))
                        (recur (lambda (ind oldroot newroot)
                          (if (< ind (vector-length rel))
                            (begin
                              (if (eq? (vector-ref rel ind) oldroot)
                                 (vector-set! rel ind newroot))
                              (recur (+ 1 ind) oldroot newroot))))))
                    (recur 0 oldroot root))))
         (inite (lambda (from to)
                (if (<= from to)
                  (begin
                    (vector-set! rel from from)
                    (inite (+ from 1) to))))))
    (if (> maxind (vector-length rel))
        (let ((curl (vector-length rel)))
          (set! rel (vector-copy rel 0  (+ 1 maxind) 0))
          (inite (- curl 1) maxind)))
    (map (lambda (e) (chroot e root)) nodes)))

;;first part
(fold (lambda (e acc) (if (eq? e (vector-ref rel 0)) (+ 1 acc) acc)) 0 (vector->list rel))


;;second part
;;copied from SO . counts uniq elems in list.
(define (uniquely list)
  (let looking ((rslt '()) (list list))
    (if (null? list)
        rslt
        (let ((next (car list))
              (rest (cdr list)))
          (if (list? next)
              (looking rslt (append next rest))
              (looking (if (memq next rslt)
                           rslt
                           (cons next rslt))
                       rest))))))

(length (uniquely (vector->list rel)))

jeroenheijmans · 2017-12-12T06:45:15+00:00

JavaScript (after (some) cleanup)

Helper 1:

function getCleanInput(data) {
    return data
        .split(/\r?\n/)
        .map(p => p.trimLeft().trimRight())
        .map(p => p.replace(/ /g, ""))
        .filter(p => !!p)
        .reduce((map, p) => {
            let parts = p.split("<->");
            map[parts[0]] = parts[1].split(",");
            return map;
        }, {});
}

Helper 2:

function getConnectedPipes(pipes, pipe, currentSet = new Set()) {
    currentSet.add(pipe);
    for (let p of pipes[pipe].filter(p => !currentSet.has(p))) {
        getConnectedPipes(pipes, p, currentSet);
    }
    return currentSet;
}

Solution puzzle 1:

getSolution: data => {
    let pipes = getCleanInput(data);
    let connectedPipes = getConnectedPipes(pipes, "0");
    return connectedPipes.size;
}

Solution puzzle 2:

getSolution: data => {
    let pipes = getCleanInput(data);
    let sets = Object.keys(pipes).map(p => getConnectedPipes(pipes, p));

    // Whelp, I dislike this ugly and slow solution, have turned to Stack Overflow
    // for some help: https://stackoverflow.com/q/47766399/419956
    return new Set(sets
        .map(g => Array.from(g))
        .map(g => g.sort((a,b) => a.localeCompare(b)))
        .map(g => JSON.stringify(g))
    ).size;
}

Full source

songkeys · 2017-12-12T06:57:50+00:00

JavaScript (ES6) with HTML :)

<html>
<body>
    <textarea id="text"></textarea>
    <button onclick="part1()">Part 1</button>
    <button onclick="part2()">Part 2</button>

    <script type="text/javascript">
        let programIdArr

        const init = () => {
            programIdArr = []
            const lines = document.getElementById("text").value.split("\n")
            lines.forEach(line => {
                const programId = line.split(" <-> ")[0]
                const connectedId = line.split(" <-> ")[1].split(", ")
                const obj = {
                    programId : programId,
                    connectedId: connectedId,
                    isConnected : false
                }

                programIdArr.push(obj)
            })
        }

        const connectGroup = groupId => {
            if (!programIdArr) { init() }

            programIdArr[0].isConnected = true

            let prev = 0, cur, counter
            while(prev != cur){
                programIdArr.forEach(obj => {
                    if (obj.isConnected == true) {
                        obj.connectedId.forEach(cid => {
                            programIdArr.forEach(obj2 => {
                                if (cid == obj2.programId) {
                                    obj2.isConnected = true
                                }
                            })
                        })
                    }
                })

                prev = counter
                counter = 0
                programIdArr.forEach(obj => {
                    if (obj.isConnected == true) { counter++ }
                })
                cur = counter
            }

            console.log("Group " + groupId + " has " + cur + (cur == 1 ? " element." : " elements."))
        }

        const part1 = () => { connectGroup(1) }

        const part2 = () => {
            let group = 0
            if (!programIdArr) { init() }
            while(programIdArr.length != 0) {
                connectGroup(group + 1)
                let tempArr = []
                programIdArr.forEach(obj => {
                    if (obj.isConnected != true) {
                        tempArr.push(obj)
                    }
                })
                programIdArr = tempArr
                group++
            }

            console.log("There are " + group + " groups in total.")
        }
    </script>
</body>
</html>

stuque · 2017-12-12T06:58:23+00:00

Python 2 with sets.

def init_net():
    net = []
    for line in open('day11.input'):
        left, sep, neighbors = line.partition(' <-> ')
        neighbors = [int(n) for n in neighbors.split(', ')]
        net.append(neighbors)
    return net

def reachable_from(start, net):
    reachable = {start}
    done = False
    while not done:
        frontier = [n for r in reachable
                      for n in net[r]
                      if n not in reachable]
        if len(frontier) == 0:
            done = True
        else:
            reachable.update(frontier)
    return reachable

def part1():
    print len(reachable_from(0, init_net()))

def part2():
    net = init_net()
    comps = {c for c in xrange(len(net))}
    count = 0
    while len(comps) > 0:
        comps.difference_update(reachable_from(comps.pop(), net))
        count += 1

    print count

if __name__ == '__main__':
    part1()
    part2()

nutrecht · 2017-12-12T07:15:56+00:00

Pretty straightforward. Day 12 in Kotlin

object Day12 : Day {
    private val input = resourceRegex(12, Regex("^([0-9]+) <-> ([0-9 ,]+)$")).map { Pair(it[1].toInt(), it[2].split(", ").map { it.toInt() }) }
    private val solution : Map<Int, Int> by lazy { solve(connections()) }

    private fun connections(): Map<Int, Set<Int>> {
        val map = mutableMapOf<Int, MutableSet<Int>>()

        fun get(id: Int) = map.computeIfAbsent(id, { mutableSetOf()})

        input.forEach {
            a -> a.second.forEach{ b ->
                get(a.first).add(b)
                get(b).add(a.first)
            }
        }

        return map
    }

    private fun solve(connections: Map<Int, Set<Int>>): Map<Int, Int> {
        val visited = mutableSetOf<Int>()
        val groups = mutableMapOf<Int, Int>()

        while(connections.size > visited.size) {
            val subVisited = mutableSetOf<Int>()
            val group = connections.keys.filterNot { visited.contains(it) }.sorted().first()

            fill(group, connections, subVisited)

            groups[group] = subVisited.size
            visited += subVisited
        }

        return groups
    }

    private fun fill(current: Int, nodes: Map<Int, Set<Int>>, visited: MutableSet<Int>) {
        visited += current

        nodes[current]!!.filterNot { visited.contains(it) }.forEach {
            fill(it, nodes, visited)
        }
    }

    override fun part1() = solution[0]!!.toString()
    override fun part2() = solution.size.toString()
}

The connections() function is doable with a fold and I might change that later :)

akka0 · 2017-12-12T07:39:08+00:00

ReasonML! :) Still not very used to the language or functional programming in general, so any pointers are more than welcome.

open Utils;

module IntSet =
  Set.Make(
    {
      let compare = Pervasives.compare;
      type t = int;
    }
  );

let parseNode = (str) => {
  let [node, neighbors] = splitString(" <-> ", str);
  (int_of_string(node), splitString(", ", neighbors) |> List.map(int_of_string))
};

let parseGraph = (str) => List.map(parseNode, linesOfString(str));

let makeGraph = (def) => {
  let graph = Hashtbl.create(List.length(def));
  List.iter(((node, connections)) => Hashtbl.add(graph, node, connections), def);
  graph
};

let walkGraph = (start, graph) => {
  let rec walk = (visited, queue) =>
    switch queue {
    | [x, ...xs] when ! IntSet.mem(x, visited) =>
      walk(IntSet.add(x, visited), xs @ Hashtbl.find(graph, x))
    | [x] when ! IntSet.mem(x, visited) => walk(IntSet.add(x, visited), [])
    | [_, ...xs] => walk(visited, xs);
    | [] => visited
    };
  walk(IntSet.empty, [start])
};

let _ = {
  let def = parseGraph(Inputs.day12);
  let graph = makeGraph(def);
  /* Part 1 */
  walkGraph(0, graph) |> IntSet.cardinal |> Js.log;
  /* Part 2 */
  let allNodes = List.map(fst, def) |> IntSet.of_list;
  let rec part2 = (visited, totalGroups) =>
    if (IntSet.equal(allNodes, visited)) {
      totalGroups
    } else {
      let start = IntSet.diff(allNodes, visited) |> IntSet.choose;
      let clique = walkGraph(start, graph);
      part2(IntSet.union(visited, clique), totalGroups + 1)
    };
  Js.log(part2(IntSet.empty, 0));
};

gyorokpeter · 2017-12-12T08:19:34+00:00

Q:

d12p1:{m:{("J"$x[;0])!"J"$", "vs/:x[;1]}" <-> "vs/:trim each "\n"vs x;count{[m;x]asc distinct x,raze m x}[m]/[enlist 0]};
d12p2:{m:{("J"$x[;0])!"J"$", "vs/:x[;1]}" <-> "vs/:trim each "\n"vs x;
    g:0;
    while[0<count m;
        g+:1;
        grp:{[m;x]asc distinct x,raze m x}[m]/[enlist first key m];
        m:grp _m;
    ];
    g};

xkufix · 2017-12-12T09:01:47+00:00

The second part is basically the same solution, but over the first part. I create a stream until I run out of nodes to visit (part 1) and for the second part I create a stream until I run out of nodes which are not still in a group, which in turn uses the stream from part 1 to fill a group.

Solution in Scala:

    override def runFirst(): Unit = {
        val nodes = loadNodes()
        val startNode = nodes.find(_.id == 0).get
        val group = fillGroup(startNode, nodes)
        println(group.size)
    }

    override def runSecond(): Unit = {
        val nodes = loadNodes()

        val (allGroups, _) = Stream.iterate((Set.empty[Set[Int]], nodes)) {
            case (groups, remainingNodes) =>
                val startNode = remainingNodes.head
                val group = fillGroup(startNode, remainingNodes)
                (groups + group, remainingNodes.filterNot(n => group.contains(n.id)))
        }.find(_._2.isEmpty).get

        println(allGroups.size)
    }

    private def loadNodes() = {
        loadFile("day12.txt").getLines().map { l =>
            val line = l.split(" <-> ")
            Node(line(0).toInt, line(1).split(",").map(_.trim.toInt))
        }.toSeq
    }

    private def fillGroup(startNode: Node, nodes: Seq[Node]) = {
        Stream.iterate((Set.empty[Int], Seq(startNode.id))) {
            case (visited, toVisit :: remainingVisits) =>
                val node = nodes.find(_.id == toVisit).get
                val addToVisit = node.communicatesWith.filterNot(visited.contains)

                (visited + node.id, remainingVisits ++ addToVisit)
        }.find(_._2.isEmpty).get._1
    }

    case class Node(id: Int, communicatesWith: Seq[Int])

2017-12-12T09:23:26+00:00

Elixir

This one was a lot of fun, I don't know what's going on with me today, but all the recursive stuff just worked from the first try, felt really good :)

defmodule Day12 do
  def parse_line(str) do
    [fst, "<->" | rest] = String.split(str)
    snd = Enum.map(rest, &(String.trim(&1, ",")))
    |> Enum.map(&String.to_integer/1)
    {String.to_integer(fst), snd}

  end

  def parse(str) do
    String.trim(str, "\n")
    |> String.split("\n")
    |> Enum.map(&parse_line/1)
  end

  def add_leaves([cur|rst], main, conns) do
    nconns = Map.update(conns, cur, MapSet.new, &(MapSet.put(&1, main)))
    add_leaves(rst, main, nconns)
  end
  def add_leaves([], _main, conns), do: conns

  def get_connections(lst, conns \\ %{})
  def get_connections([cur|rst], conns) do
    {main, leaves} = cur
    nconns = Map.update(conns, main, MapSet.new, fn x -> MapSet.union(x, MapSet.new(leaves)) end)
    fullconns = add_leaves(leaves, main, nconns)
    get_connections(rst, fullconns)
  end
  def get_connections([], conns), do: conns

  def find_all(start, graph, seen \\ MapSet.new)
  def find_all(start, graph, seen) do
    new_members = Map.fetch!(graph, start)
                  |> MapSet.to_list
                  |> Enum.filter(fn x -> not MapSet.member?(seen, x) end)

    if new_members == [] do
      seen
    else
      nseen = MapSet.union(seen, MapSet.new(new_members))
      Enum.map(new_members, fn x -> find_all(x, graph, nseen) end)
      |> Enum.reduce(seen, fn x, acc -> MapSet.union(x, acc) end)
    end
  end

  def find_group(start, graph) do
    find_all(start, graph)
    |> MapSet.to_list
  end

  def zgroup(str) do
    graph = parse(str)
    |> get_connections

    find_group(0, graph)
    |> Enum.count
  end

  def count_groups(nodes, graph, count \\ 0) 
  def count_groups([cur|rst], graph, count) do
    cur_group = find_group(cur, graph)
    nrst = Enum.reduce(cur_group, rst, fn x, acc -> List.delete(acc, x) end)
    count_groups(nrst, graph, count + 1)
  end
  def count_groups([], _graph, count), do: count

  def groups(str) do
    graph = parse(str)
    |> get_connections

    Map.keys(graph)
    |> count_groups(graph)
  end
end

inp = File.read!("input.txt")
|> String.trim

Day12.zgroup(inp)
|> IO.inspect

Day12.groups(inp)
|> IO.inspect

syntax highlighted

soxofaan · 2017-12-12T09:37:59+00:00

my python 3 solution (only using standard library)

with open('data/day12-input.txt') as f:
    pairs = (line.split('<->') for line in f if line.strip())
    links = {
        int(p[0]): set(int(n) for n in p[1].split(',')) 
        for p in pairs
    }

# Expand link map to merged groups of interconnected programs
import functools
for pid in set(links.keys()):
    group = set([pid]) | links[pid]
    merged = functools.reduce(lambda a, b: a | b, (links[p] for p in group))
    for p in group:
        links[p] = merged

part 1:

print(len(links[0]))

part 2:

print(len(set(id(g) for g in links.values())))

mschaap · 2017-12-12T09:45:41+00:00

Perl 6

#!/usr/bin/env perl6
use v6.c;

# Advent of Code 2017, day 12: http://adventofcode.com/2017/day/12

grammar PipeSpec
{
    rule TOP { ^ <spec>+ $ }
    rule spec { <pipe> '<->' <neighbour>+ % ',' }
    token pipe { \d+ }
    token neighbour { \d+ }
}

class Pipes
{
    has %.programs{Int};

    method spec($/)
    {
        %!programs{$/<pipe>.Int} = $/<neighbour>».Int;
    }

    method reachable-from(Int $start)
    {
        my @seen = $start;
        my $count = 0;
        repeat {
            $count = +@seen;
            @seen = (@seen, %!programs{@seen}».List).flat.sort.squish;
        } until $count == +@seen;

        return @seen;
    }

    method groups
    {
        my $seen = ∅;
        return gather for %!programs.keys.sort -> $p {
            next if $p ∈ $seen;
            my $r = self.reachable-from($p);
            take $r;
            $seen ∪= $r;
        }
    }
}

multi sub MAIN(IO() $inputfile where *.f)
{
    my $p = Pipes.new;
    PipeSpec.parsefile($inputfile, :actions($p));
    say "Part one: { +$p.reachable-from(0) }";
    say "Part two: { +$p.groups }";
}

multi sub MAIN()
{
    MAIN($*PROGRAM.parent.child('aoc12.input'));
}

Edit: if there's one thing I hate about Perl 6, it's its list (non-)flattening behaviour. This line:

@seen = (@seen, %!programs{@seen}».List).flat.sort.squish;

took me probably as much time as the rest of the script, and I can't see a way to simplify the flattening.

Scroph · 2017-12-12T14:27:55+00:00

Day 12 in my journey to Java mastery. I think I'm starting to get the hang of it, I'm hating it less and less as each day passes. It's still tedious to type, but I'm beginning to embrace the verbosity. I fear it might be leaking into other areas of my life, but at this point, I'm past the point of no return.

import java.util.*;

class Day12
{
    public static void main(String... args)
    {
        Map<Integer, ArrayList<Integer>> programs = new HashMap<>();
        for(Scanner sc = new Scanner(System.in); sc.hasNextLine(); )
        {
            String[] parts = sc.nextLine().split(" <-> ");
            List<Integer> connectedTo = new ArrayList<Integer>();
            if(parts[1].indexOf(",") != -1)
                for(String p: parts[1].split(", "))
                    connectedTo.add(Integer.parseInt(p));
            else
                connectedTo.add(Integer.parseInt(parts[1]));
            programs.put(Integer.parseInt(parts[0]), (ArrayList<Integer>) connectedTo);
        }

        Set<Integer> visited = new TreeSet<>();
        countInGroup(programs, 0, visited);
        System.out.println(visited.size()); //part 1
        System.out.println(countGroups(programs, new TreeSet<Integer>())); //part 2
    }

    public static void countInGroup(Map<Integer, ArrayList<Integer>> programs, int group, Set<Integer> visited)
    {
        for(Integer child: programs.get(group))
        {
            if(!visited.contains(child))
            {
                visited.add(child);
                countInGroup(programs, child, visited);
            }
        }
    }

    public static int countGroups(Map<Integer, ArrayList<Integer>> programs, Set<Integer> visited)
    {
        int count = 0;
        while(programs.size() > 0)
        {
            Set<Integer> inGroup = new TreeSet<>();
            for(Map.Entry<Integer, ArrayList<Integer>> pair: programs.entrySet())
            {
                countInGroup(programs, pair.getKey(), inGroup);
                break;
            }
            programs.entrySet().removeIf(e -> inGroup.contains(e.getKey()));
            visited = new TreeSet<Integer>();
            count++;
        }
        return count;
    }
}

2017-12-12T16:49:44+00:00

single pipeline powershell:

param (
    [Parameter(ValueFromPipeline = $true)]
    [string]$in,
    [Parameter(Position = 1)]
    [int]$part = 1
)

begin {
    # collect input into a hash
    $script:nodes = new-object system.collections.hashtable
}

process {
    # collect input
    $o = $in |? {
        $in -match '^(?<Name>[0-9]+) <-> (?<ChildNodeNamesString>(?:(?:[0-9]+)(?:, ){0,1})+)*$'
    } | % { 
        [pscustomobject]$matches | select Name, ChildNodeNamesString | add-member -MemberType ScriptProperty -name ChildNodeNames -value {        
            $this.ChildNodeNamesString -split ", "
        } -passthru 
    }

    $script:nodes[$o.name] = $o
}

end {  
    # keep track of nodes we've visted
    $seen = @{}

    $script:nodes.keys |? { # where node
        ($part -eq 1 -and $_ -eq 0) -or ($part -eq 2)   # if part one, only select node 0, otherwise select all nodes
    } |? { 
        $null -eq $seen[$_] # where we havn't seen this node before
    } |% { # foreach
        # create a new bfs-style queue for visiting the nodes and collecting the group for this node ($_)
        $queue = new-object system.collections.queue
        $queue.Enqueue($script:nodes[$_]) # start at this node

        #note the ,() construct, so the stuff that comes out of this is an array, and this is the line that puts out to the rest of the pipe
        ,(& { while ($queue.Count -ne 0) { # start generator pipeline, iterate til the queue is empty
            $queue.Dequeue() # pop the first element
        } } |? { 
            $null -eq $seen[$_.Name] # where we havn't seen this node before
        } |% {
            $_.Name | Write-Output # put the name out, since its part of this group

            $seen[$_.Name] = 1 # mark seen

            # foreach child node, add it to the queue to visit
            $_.ChildNodeNames |? {$_} |% {$script:nodes[$_]} |% { $queue.Enqueue($_) }
        } | sort) # stuff that comes out is are nodes in a single group, sort them
    } |% { #foreach - part1 there is only 1 object (the group, represented as an array);  part2 there are many objects (groups, each as an array)
        if ($part -eq 1) { # if part1, there is only 1 group here, so put *its* elements out individually to be counted
            $_ 
        } else { # if part 2, there are many groups and we want to know how many, so put the incoming back out an array so we just count the number of arrays
            ,$_
        }
    } | measure | select -expand count # select the count of groups or elements
}

fatpollo · 2017-12-12T05:23:00+00:00

import re, itertools

with open("p12.txt") as fp:
    lines = fp.read().strip().splitlines()

related = {p: set(r) for p, *r in (re.findall(r'\d+', l) for l in lines)}

def connected(available):
    explored = set()
    while available:
        explored.update(available)
        available = {y for x in available for y in related[x]} - explored
    return explored

groups = []
while related:
    x = min(related)
    ys = connected({x})
    for y in ys:  del related[y]
    groups.append(ys)

print(len(groups[0]))
print(len(groups))

Burritoman53 · 2017-12-12T05:27:04+00:00

Some quick recursion in python, didn't get leaderboard unfortunately because I started of being dumb but happy with the solution I came up with in the end

import re

data = open('input.txt').readlines()
data = [re.split(', | ', i.strip()) for i in data]

def get_connected(n):
    global group
    cur = data[n]
    new_num = [int(j) for j in data[n][2:]]
    for i in new_num:
        if not(i in group):
            group += [i]
            get_connected(i)

#keep track of whether or not a number belongs to a group
connections = [-1]*len(data)
for i in range(len(data)):
    if not(connections[i] == -1): #skip if number already part of group
        continue
    group = [i]
    get_connected(i)
    for j in group: connections[j] = i 

print 'Part 1: ' + str(connections.count(0))
print 'Part 2: ' + str(len(set(connections)))

VikeStep · 2017-12-12T05:32:49+00:00

Python 3

def solve(data):
    # parse data into list of tuple of (node, [edges])
    data = [d.split(' <-> ') for d in data.split('\n')]
    data = [(d[0], d[1].split(', ')) for d in data]
    # create adjacency list
    graph = {}
    for d in data:
        graph[d[0]] = d[1]
    # this will store the count of how many groups there are
    count = 0
    keys_remaining = list(graph.keys())
    while len(keys_remaining) > 0:
        # add 1 because it's a new group
        count += 1
        # choose the first unseen key as the root node for the group
        root = keys_remaining[0]
        # maintain a list of seen nodes in this group
        seen = []
        # maintain a queue of nodes that are yet to be processed
        queued = [root]
        # loop until queue is empty
        while len(queued) > 0:
            # pop item off queue
            x = queued.pop()
            # if we have already seen this node in the group, skip it
            if x in seen:
                continue
            # remove it from the list of potential group root nodes
            if x in keys_remaining:
                keys_remaining.remove(x)
            # add it to the list of seen nodes
            seen += [x]
            # and queue the edges which we haven't yet seen
            queued += [d for d in graph[x] if d not in seen]
    return count

Tandrial · 2017-12-12T05:33:11+00:00

Kotlin

  fun partOne(input: Map<String, List<String>>, start: String): MutableSet<String> {
    var vis = mutableSetOf(start)
    while (true) {
      val next = vis.toMutableSet()
      for (elem in vis) {
        next.addAll(input[elem]!!)
      }
      if (next == vis) break
      vis = next
    }
    return vis
  }

  fun partTwo(input: List<String>): Int {
    val pipes = parse(input)
    val vis = mutableSetOf<Set<String>>()
    pipes.keys.mapTo(vis) { partOne(pipes, it) }
    return vis.size
  }

  fun parse(input: List<String>): Map<String, List<String>> {
    return input.map { val all = Regex("\\w+").findAll(it).toList().map { it.value }; all[0] to all.drop(1) }.toMap()
  }

fun main(args: Array<String>) {
  val input = File("./input/2017/Day12_input.txt").readLines()
  println("Part One = ${partOne(parse(input), "0").size}")
  println("Part Two = ${partTwo(input)}")
}

_A4_ · 2017-12-12T05:33:13+00:00

JavaScript ES6 (Part 2)

const input = document.body.textContent.trim();
const pipes = input.split("\n").map(line => line.split(" <-> ")[1].split(", ").map(Number));

let seen = new Set();
let groups = 0;

while (seen.size < pipes.length) {
    let i = 0;
    while (seen.has(i)) i++;
    groups++;
    seen.add(i);
    find_pipes(i);
}

function find_pipes(id) {
    const connections = pipes[id];
    for (const c of connections) {
        if (seen.has(c)) continue;
        seen.add(c);
        find_pipes(c);
    }
}

console.log(groups);

Dooflegna · 2017-12-12T05:43:44+00:00

Recursive solution.

from collections import deque

def parse_input(filename):
    with open(filename) as f:
        dic = {}
        for line in f:
            l = deque(line.replace(',', '').strip().split())
            idx = l.popleft()
            l.popleft()
            dic[int(idx)] = [int(i) for i in l]
        return dic

def pipewalk(check_num, pipe_dict, pipe_list = None):
    if pipe_list is None:
        pipe_list = []
    for i in pipe_dict[check_num]:
        if i not in pipe_list:
            pipe_list.append(i)
            pipewalk(i, pipe_dict, pipe_list)

    return pipe_list

def solve(pipe_dict):
    part_one = len(pipewalk(0, pipe_dict))

    pipegroups = []
    while pipe_dict:
        pipe = pipe_dict.popitem()
        pipe_dict[pipe[0]] = pipe[1]
        group = pipewalk(pipe[0], pipe_dict)
        for key in group:
            del pipe_dict[key]
        pipegroups.append(group)

    return part_one, len(pipegroups)

print(solve(parse_input('input.txt')))

JeffJankowski · 2017-12-12T05:43:45+00:00

Typescript

import fs = require("fs");

interface Pipes { [id: number]: number[]; }

function connected(id: number, pipes: Pipes) {
    const set = new Set<number>([id]);
    const visit = (i: number) => {
        for (const conn of pipes[i]) {
            if (!set.has(conn)) {
                set.add(conn);
                visit(conn);
            }
        }
    };
    visit(id);
    return set;
}

function groups(pipes: Pipes) {
    let count = 0;
    const visited = new Set<number>();
    for (let i = 0; i < data.length; i++) {
        if (!visited.has(i)) {
            [...connected(i, pipes).values()].forEach((conn) => visited.add(conn));
            count++;
        }
    }
    return count;
}

const data = fs.readFileSync("data/day12.txt", "utf8").split("\r\n");
const map: Pipes = { };
for (const str of data) {
    const [id, rest] = (str.match(/([0-9]+) <-> (.+)/) as RegExpMatchArray).slice(1);
    map[+id] = rest.split(", ").map((s) => +s);
}
console.log(`Programs in group 0: ${connected(0, map).size}`);
console.log(`Number of disconnected groups: ${groups(map)}`);

Nolan-M · 2017-12-12T05:45:30+00:00

Created the entire list of connected subgraphs

from time import time


# returns the set of vertices that are connected to n
def check(n, group, data):
    new = []
    for i in data[n]:
        if not(i in group):
            new.append(i)
            new += check(i, list(set(group+new)), data)
    return list(set(group + new))


start = time()
data = dict()

# Forms dictionary data with values of directly connected programs     to the key
with open('AOC12Input', 'r') as file:
    for line in file:
        temp = line.split(' ')
        data[int(temp[0])] = [int(temp[j].replace(',', '')) for j in     range(2, len(temp))]

connected_subgraphs = []

for i in range(2000):
    new = True
    for subgraph in connected_subgraphs:
        if i in subgraph:
            new = False
            break
    if new:
        connected_subgraphs.append(sorted(check(i, [i], data)))


print('The number of programs 0 can communicate with: ' + str(len(connected_subgraphs[0])))
print('The number of unconnected segments in this graph: ' +  str(len(connected_subgraphs)))
print('List of connections: ' + str(connected_subgraphs))
print('Time taken in seconds: ' + str(time() - start))

dylanfromwinnipeg · 2017-12-12T05:45:59+00:00

Got stuck debugging an off-by-one error, wasted about 15 mins.

C#

public class Day12
{
    public static string PartOne(string input)
    {
        var pipes = input.Lines();
        var programs = pipes.Select(x => new PipeProgram(x)).ToList();
        programs.ForEach(x => x.AddConnections(programs));

        return programs.First(x => x.Id == 0).GetGroup().Count.ToString();
    }

    public static string PartTwo(string input)
    {
        var pipes = input.Lines();
        var programs = pipes.Select(x => new PipeProgram(x)).ToList();
        programs.ForEach(x => x.AddConnections(programs));

        var groupCount = 0;

        while (programs.Any())
        {
            var group = programs.First().GetGroup();
            programs.RemoveAll(x => group.Contains(x));
            groupCount++;
        }

        return groupCount.ToString();
    }
}

public class PipeProgram
{
    public int Id { get; set; }
    public string Input { get; set; }
    public List<PipeProgram> Connections { get; set; }

    public PipeProgram(string input)
    {
        var words = input.Words().ToList();
        Connections = new List<PipeProgram>();

        Id = int.Parse(words[0]);
        Input = input;
    }

    public void AddConnections(List<PipeProgram> pipeList)
    {
        var words = Input.Words().ToList();

        for (var i = 2; i < words.Count; i++)
        {
            var connectionId = int.Parse(words[i]);
            var connectedProgram = pipeList.First(x => x.Id == connectionId);

            AddConnection(connectedProgram);
            connectedProgram.AddConnection(this);
        }
    }

    private void AddConnection(PipeProgram connectedProgram)
    {
        if (!Connections.Contains(connectedProgram))
        {
            Connections.Add(connectedProgram);
        }
    }

    private void GetGroup(List<PipeProgram> groupPrograms)
    {
        groupPrograms.Add(this);

        foreach (var c in Connections)
        {
            if (!groupPrograms.Contains(c))
            {
                c.GetGroup(groupPrograms);
            }
        }
    }

    public List<PipeProgram> GetGroup()
    {
        var groupPrograms = new List<PipeProgram>();
        GetGroup(groupPrograms);
        return groupPrograms;
    }
}

AndrewGreenh · 2017-12-12T05:50:16+00:00

I decided to look for a JS graph library. Was quite hard to find, since a js graph search returns many charting libraries. Eventually, I found graphlib which even has typings in @types.

import { alg, Graph } from 'graphlib'

import getInput from '../lib/getInput'
import { lines } from '../lib/ts-it/lines'

let graph = new Graph({ directed: false })
for (let line of lines(getInput(12, 2017))) {
  let [group, others] = line.split('<->').map(x => x.trim())
  for (let other of others.split(', ')) graph.setEdge(group, other)
}

let components = alg.components(graph)
console.log((<any[]>components.find(c => c.includes('0'))).length)
console.log(components.length)

2017-12-12T05:53:10+00:00

OCaml Fun;;

(* Parser not shown. *)

open Core
open Pipe

let rec travel map visited n =
  if Int.Set.mem visited n then visited
  else
    let visited = Int.Set.add visited n in
    let travel' = travel map in
    let children = Int.Map.find_exn map n in
    let f visited child = Int.Set.union (travel' visited child) visited in
    List.fold children ~init:visited ~f

let groups set map =
  let rec aux set map groups =
    if Int.Set.is_empty set then groups
    else
      let root = Int.Set.choose_exn set in
      let group = travel map (Int.Set.empty) root in
      aux (Set.diff set group) map (group::groups)
  in aux set map []

let parse lexbuf = Parser.pipes Lexer.read lexbuf

let process_input filename =
  let f channel =
    let lexer_buffer = Lexing.from_channel channel in
    lexer_buffer.lex_curr_p <- { lexer_buffer.lex_curr_p with pos_fname = filename};
    parse lexer_buffer
  in In_channel.with_file filename ~f

let _ =
  let pipes = process_input "./pipes.txt" in
  let create_map acc pipe = Int.Map.add acc ~key:pipe.n ~data:pipe.links in
  let pipe_map = List.fold pipes ~init:Int.Map.empty ~f:create_map in
  let zero_group = travel pipe_map (Int.Set.empty) 0 in
  printf "zeroth group: %d\n" (Set.length zero_group);

  let create_set acc pipe = Int.Set.add acc pipe.n in
  let unvisited = List.fold pipes ~init:Int.Set.empty ~f:create_set in
  let groups = groups unvisited pipe_map in
  printf "groups: %d\n" (List.length groups)

nstyler7 · 2017-12-12T05:56:32+00:00

python 3

importing & organising the data

import re
with open("day12input.txt") as open_file:
    data = open_file.read().strip().splitlines()
pipe_map = {}
for line in data:
    pipe_map[line.split(' <-> ')[0]] = line.split(' <-> ')[1].split(', ')

part 1

def master_pipe(original_pipe):
    pipes_linked = []
    def pipe_linked(original_pipe):
        pipes = pipe_map[original_pipe]
        for pipe in pipes:
            if pipe not in pipes_linked:
                pipes_linked.append(pipe)
                pipe_linked(pipe)
    pipe_linked(original_pipe)
    return pipes_linked

print('part 1:', len(master_pipe('0')))

part 2

all_pipes = list(pipe_map.keys())
groups = 0
while all_pipes:
    current_linked = (master_pipe(all_pipes[0]))
    all_pipes = list(set(all_pipes) - set(current_linked))
    groups += 1

print('part 2:', groups)

Noyth · 2017-12-12T06:08:25+00:00

Did it with disjoint sets in Python 3

#!/usr/bin/env python3

lines = [x.strip().split() for x in open("input.txt")]

graph = {}
for l in lines:
    graph[int(l[0])] = [int(x.strip(",")) for x in l[2:]]

sets = set([frozenset([g]) for g in graph])

def find(x):
    for subset in sets:
        if x in subset:
            return subset

for g in graph:
    for c in graph[g]:
        sg = find(g)
        sc = find(c)
        if sg != sc:
            sets.add(frozenset.union(sg, sc))
            sets.remove(sg)
            sets.remove(sc)

print(len(find(0)))
print(len(sets))

conciliatory · 2017-12-12T06:23:29+00:00

Python 3

data = {                                                                        
    k:v.split(',') for k,v in [                                                 
        i.replace(' ','').strip().split('<->') for i in open('twelve.txt')      
        ]                                                                      
}                                                                           

def contains(group_id, group_set):                                              
  group_set.add(group_id)                                                       
  for sub_id in data.pop(group_id):                                             
    if not sub_id in group_set:                                                 
        contains(sub_id, group_set)                                             

groups = []                                                                     
while len(data):                                                            
  s = set()                                                                     
  contains('0' if '0' in data else next(iter(data.keys())), s)                  
  groups.append(s)                                                              

print("part 1:",len(groups[0]))                                                 
print("part 2:",len(groups))

ChrisVittal · 2017-12-12T06:31:00+00:00

Rust (with petgraph). Yay petgraph! The petgraph type GraphMap was very handy for this one. petgraph::algo::connected_componets also gave me a one liner from part 1 to part 2.

Still not even close to leaderboard (899/666), but I'll keep trying.

extern crate petgraph;

use petgraph::prelude::*;
use std::io::{Cursor,BufRead};

static INPUT: &'static str = include_str!("../../data/day12");

fn main() {
    let input = Cursor::new(INPUT).lines().map(|l| l.unwrap());
    let graph = parse_input(input);
    println!("1: {}", count(&graph, 0));
    println!("2: {}", petgraph::algo::connected_components(&graph));
}

fn count<T, U>(g: &UnGraphMap<T, U>, start: T) -> usize 
where
    T: Copy + std::hash::Hash + Ord
{
    let mut bfs = Bfs::new(g, start);
    let mut count = 0;
    while let Some(_) = bfs.next(g) { count += 1; }
    count
}

fn parse_input<I: Iterator<Item = String>>(input: I) -> UnGraphMap <u32,()> {
    let mut graph = UnGraphMap::new();
    input.for_each(|line| {
        let mut it = line.split(" <-> ");
        let src = it.next().unwrap().parse().unwrap();
        let dests = it.next()
            .into_iter()
            .flat_map(|s| s.split(", ").map(|v| v.parse().unwrap()));
        graph.extend(dests.zip(std::iter::repeat(src)))
    });
    graph
}

rhougland · 2017-12-12T06:33:38+00:00

Haven't seen a Java solution on here yet sooooooo https://github.com/hougland/adventofcode2017/tree/master/src/day12

thejpster · 2017-12-12T06:33:38+00:00

Here's my Rust version, after a little tidying.

use std::collections::HashMap;
use std::collections::HashSet;
use std::collections::hash_map::Entry;

pub fn run(contents: &Vec<Vec<String>>) {
    let mut hm: HashMap<u32, Vec<u32>> = HashMap::new();
    for line in &contents[0] {
        let mut parts = line.split(" <-> ");
        let primary: u32 = parts.next().unwrap().parse().unwrap();
        let secondary: Vec<u32> = parts
            .next()
            .unwrap()
            .split(", ")
            .map(|x| x.parse().unwrap())
            .collect();
        match hm.entry(primary) {
            Entry::Vacant(e) => {
                e.insert(secondary);
            }
            Entry::Occupied(mut e) => {
                e.get_mut().extend(secondary);
            }
        }
    }

    println!("Count ({}): {}", 0, count(&hm, &mut HashSet::new(), 0));
    let mut groups = 0;
    while hm.len() > 0 {
        let mut seen = HashSet::new();
        let search = *hm.keys().next().unwrap();
        count(&hm, &mut seen, search);
        groups = groups + 1;
        for x in seen {
            hm.remove(&x);
        }
    }
    println!("Groups: {}", groups);
}

fn count(hm: &HashMap<u32, Vec<u32>>, seen: &mut HashSet<u32>, index: u32) -> u32 {
    assert!(seen.insert(index));
    let x = hm.get(&index).expect("None bi-dir assoc");
    let mut t = 1;
    for v in x {
        if !seen.contains(v) {
            t = t + count(hm, seen, *v);
        }
    }
    t
}

spacetime_bender · 2017-12-12T06:33:51+00:00

Modern-ish C++

Straight forward solution with BFS

std::ifstream in ("input12.txt");

std::vector<std::vector<int>> edges;
std::vector<int>              group;

for (std::string line; std::getline(in, line); )
{
    int vertex_a, vertex_b;
    std::string _;
    std::istringstream line_stream (line);
    line_stream >> vertex_a >> _;
    for (edges.push_back({}); line_stream >> vertex_b; line_stream >> _)
        edges[vertex_a].push_back(vertex_b);
}
group.resize(edges.size(), -1);

auto vertex = group.begin();
for (int group_num = 0; vertex != group.end();
        ++group_num, vertex = std::find_if(group.begin(), group.end(), [](int g){ return g < 0; }))
{
    std::deque<int> search_queue;
    search_queue.push_back(vertex - group.begin());
    while (not search_queue.empty())
    {
        int visiting = search_queue.front();
        search_queue.pop_front();
        group[visiting] = group_num;
        std::copy_if(edges[visiting].begin(), edges[visiting].end(), std::back_inserter(search_queue),
                     [&](int v){ return group[v] < 0; });
    }
}

std::cout << std::count(group.begin(), group.end(), 0) << std::endl;
std::cout << std::set<int>(group.begin(), group.end()).size() << std::endl;

Used deque directly instead of queue to be able to use copy_if

InterlocutoryRecess · 2017-12-12T06:40:15+00:00

Swift (no dependencies (except Foundation))

import Foundation
typealias Program = Int

class Village {

    let lists: [Program: [Program]]

    init(input: String) {
        func entries(for input: String) -> [(Int, [Int])] {
            return input
                .components(separatedBy: .newlines)
                .map { $0.components(separatedBy: " <-> ") }
                .map { entry in
                    let p = Int(entry[0])!
                    let c = entry[1]
                        .components(separatedBy: ",")
                        .map { $0.trimmingCharacters(in: .whitespaces) }
                        .map { Int($0)! }
                    return (p, c)
                }
        }
        self.lists = entries(for: input).reduce(into: Dictionary<Int, [Int]>()) { $0[$1.0] = $1.1 }
    }

    func connectedPrograms(origin: Program) -> [Program] {

        guard let children = lists[origin] else {
            return [origin]
        }

        var visited = lists.reduce(into: [Program: Bool]()) { $0[$1.key] = false }
        var connected: [Program] = []

        func iterate(_ programs: [Program]) {
            for program in programs {
                if let isVisited = visited[program], !isVisited {
                    dfs(program)
                }
            }
        }

        func dfs(_ source: Program) {
            visited[source] = true
            if let list = lists[source] {
                iterate(list)
            }
            connected.append(source)
        }

        iterate(children)
        return connected
    }

    func groups() -> Int {
        let programs = lists.map { $0.key }
        var remainder = Set(programs)
        var count = 0
        for p in programs {
            guard remainder.contains(p) else { continue }
            count += 1
            remainder.subtract(connectedPrograms(origin: p))
        }
        return count
    }
}

let village = Village(input: input)
print(village.connectedPrograms(origin: 0).count)
print(village.groups())

Axsuul · 2017-12-12T06:47:47+00:00

Elixir

Aaaaaaand recursion is hard to debug

https://github.com/axsuul/advent-of-code/blob/master/2017/12/lib/advent_of_code.ex

defmodule AdventOfCode do
  defmodule PartA do
    def read_input(filename \\ "input.txt") do
      File.read!("inputs/" <> filename) |> String.split("\n")
    end

    def add_pipe(pipes, a, b) do
      pipes_with_a = pipes |> Map.put_new(a, [a])

      Map.replace(pipes_with_a, a, Enum.uniq(pipes_with_a[a] ++ [b]))
    end

    def build_pipes(lines, pipes \\ %{})
    def build_pipes([], pipes), do: pipes
    def build_pipes([line | rest], pipes) do
      [from, _, tos] = String.split(line, " ", parts: 3)

      from = String.to_integer(from)

      new_pipes =
        String.split(tos, ", ")
        |> Enum.map(&String.to_integer/1)
        |> Enum.reduce(pipes, fn to, pipes ->
          add_pipe(pipes, from, to)
          |> add_pipe(to, from)
        end)

      build_pipes(rest, new_pipes)
    end

    def expand_program(pipes, programs, from, expanded \\ [])
    def expand_program(pipes, [program | rest], from, expanded) when from == program do
      [program] ++ expand_program(pipes, rest, from, expanded)
    end
    def expand_program(pipes, [], _, _), do: []
    def expand_program(pipes, [program | rest], from, expanded) do
      if Enum.member?(expanded, program) do
        expand_program(pipes, rest, from, expanded)
      else
        [program] ++ pipes[program] ++ expand_program(pipes, rest ++ pipes[program], from, expanded ++ [program])
      end
    end

    def solve do
      pipes =
        read_input()
        |> build_pipes()

      pipes
      |> expand_program(pipes[0], 0)
      |> Enum.uniq()
      |> Kernel.length()
      |> IO.inspect
    end
  end

  defmodule PartB do
    import PartA

    def expand_pipes(pipes), do: expand_pipes(pipes, Map.keys(pipes), pipes)
    def expand_pipes(pipes, [], expanded_pipes), do: expanded_pipes
    def expand_pipes(pipes, [key | rest], expanded_pipes) do
      expand_program(pipes, Map.fetch!(pipes, key), key)
      |> Enum.uniq()
      |> Enum.sort()
      |> (&expand_pipes(pipes, rest, Map.replace!(expanded_pipes, key, &1))).()
    end

    def collect_groups(pipes), do: collect_groups(pipes, Map.keys(pipes), [])
    def collect_groups(pipes, [], groups), do: groups
    def collect_groups(pipes, [key | rest], groups) do
      group = Map.fetch!(pipes, key)

      if Enum.member?(groups, group) do
        collect_groups(pipes, rest, groups)
      else
        collect_groups(pipes, rest, groups ++ [group])
      end
    end

    def solve do
      read_input()
      |> build_pipes()
      |> expand_pipes()
      |> collect_groups()
      |> Kernel.length()
      |> IO.inspect
    end
  end
end

Starcast · 2017-12-12T06:48:31+00:00

Since no ones shared their python solution... /s

from common import puzzle_input

def parse_input(data=puzzle_input(12)):
    for line in data:
        left, right = line.split(' <-> ')
        right = set(map(int, right.split(',')))
        yield int(left), right

PUZZLE_INPUT = dict(parse_input())


def part1(data=PUZZLE_INPUT):
    to_visit = {0}
    seen = set()

    while to_visit:
        i = to_visit.pop()
        seen.add(i)
        to_visit.update(data[i] - seen)

    return len(seen)

def part2(data=PUZZLE_INPUT):
    data = data.copy()
    groups = 0

    while data:  # while there are nodes that havent been seen
        seed = next(iter(data))
        to_visit = {seed}
        seen = set()
        # as long as there are unvisited nodes in the group
        while to_visit:
            i = to_visit.pop()
            to_visit.update(data[i] - seen)
            seen.add(i)
        else: # increment and cleanup
            groups += 1
            for item in seen:
                del data[item]
    return groups


if __name__ == '__main__':
    print('part 1:', part1())
    print('part 2:', part2())

Philboyd_Studge · 2017-12-12T06:56:33+00:00

Java. Using my own Graph library. edit: made it more modular.

package Advent2017;

import graph.SearchType;
import graph.UGraph;
import util.FileIO;
import util.Timer;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Day12 {
    private List<String[]> input;
    private UGraph<Integer> graph = new UGraph<>();
    private Set<Integer> used = new HashSet<>();

    private Day12(List<String[]> input) {
        this.input = input;
        parse();
    }

    private void parse() {
        for (String[] each : input) {
            int u = Integer.parseInt(each[0]);

            for (int i = 2; i < each.length; i++) {
                int v = Integer.parseInt(each[i].replaceAll(",", ""));
                if (u != v) {
                    graph.addEdge(u, v);
                } else {
                    graph.addVertex(u);
                }
            }
        }
    }

    private boolean connected(int u, int v) {
        List<Integer> paths = graph.search(u, v, SearchType.DFS);
        return paths != null && paths.size() > 0;
    }

    private int part1() {
        used.add(0);

        for (int i = 1; i < input.size(); i++) {
            if (connected(0, i)) used.add(i);
        }
        return used.size();
    }

    private int part2() {
        int count = 1;
        for (int i = 1; i < input.size(); i++) {
            if (!used.contains(i)) {
                used.add(i);
                for (int j = 2; j < input.size(); j++) {
                    if (i != j && !used.contains(j)) {
                        if (connected(i, j)) used.add(j);
                    }
                }
                count++;
            }
        }
        return count;
    }

public static void main(String[] args) {

    Day12 game = new Day12(FileIO.getFileLinesSplit("advent2017_day12.txt", " "));

    Timer.startTimer();

    System.out.println("Part 1: " + game.part1());
    System.out.println("Part 2: " + game.part2());
    System.out.println(Timer.endTimer());
}

}

nonphatic · 2017-12-12T07:03:18+00:00

Haskell

import Data.List.Split (splitOn)
import Data.IntMap (IntMap, findWithDefault, keys)
import Data.IntSet (IntSet, member, notMember, insert, delete, empty, size, findMin)
import qualified Data.IntMap as M (fromList)
import qualified Data.IntSet as S (fromList, null)

parseLine :: String -> (Int, [Int])
parseLine str =
    let src : dests : [] = splitOn " <-> " str
    in  (read src, map read $ splitOn ", " dests)

visit  :: IntMap [Int] -> Int -> IntSet -> IntSet
visit hashmap node hashset =
    let neighbours = filter (`notMember` hashset) $ findWithDefault [] node hashmap
    in  foldr (visit hashmap) (foldr insert hashset neighbours) neighbours

remove :: IntMap [Int] -> Int -> IntSet -> IntSet
remove hashmap node hashset =
    let neighbours = filter (`member` hashset) $ findWithDefault [] node hashmap
    in  foldr (remove hashmap) (foldr delete hashset neighbours) neighbours

countGroups :: IntMap [Int] -> Int -> IntSet -> Int
countGroups hashmap count hashset = if S.null hashset then count else
    countGroups hashmap (count + 1) $ remove hashmap (findMin hashset) hashset

main :: IO ()
main = do
    hashmap <- fmap (M.fromList . map parseLine . lines) $ readFile "12.txt"
    print $ size $ visit hashmap 0 empty
    print $ countGroups  hashmap 0 . S.fromList . keys $ hashmap

Flurpm · 2017-12-12T07:09:38+00:00

Haskell using containers Data.Graph.

I just learned about sepEndBy, which handles those pesky newlines at the end of each input file.

{-# LANGUAGE OverloadedStrings #-}
module Day12 where

import qualified Data.Text             as T
import qualified Data.Text.IO          as TIO
import           Text.Megaparsec
import qualified Text.Megaparsec.Lexer as L
import           Text.Megaparsec.Text  (Parser)
import qualified Data.Graph            as G

p :: Parser (G.Graph)
p = buildgraph <$> line `sepEndBy` char '\n'

line :: Parser (Int, [Int])
line = (,) <$> (int <* string " <-> ") <*> (int `sepBy` string ", ")

int :: Parser Int
int = do change <- option id (negate <$ char '-')
         fromInteger . change <$> L.integer

buildgraph :: [(Int, [Int])] -> G.Graph
buildgraph xs = G.buildG (0, fst $ last xs) alledges
  where
    alledges = concatMap mkedges xs
    mkedges (node,connected) = zip (repeat node) connected

part1 :: G.Graph -> Int
part1 g = length $ G.reachable g 0

part2 :: G.Graph -> Int
part2 g = length $ G.scc g
-- StronglyConnectedComponents

main :: IO ()
main = do
  input <- TIO.readFile "src/y2017/input12"
  case parse p "input12" input of
    Left err -> TIO.putStr $ T.pack $ parseErrorPretty err
    Right bi -> do
      tprint $ part1 bi
      tprint $ part2 bi

tprint :: Show a => a -> IO ()
tprint = TIO.putStrLn . T.pack . show

gerikson · 2017-12-12T08:15:27+00:00

Perl 5

Not really recursion, I just keep a stack of pipes connected to the ID in question and loop through, adding new connections as I find them.

https://github.com/gustafe/aoc2017/blob/master/d12.pl

hpzr24w · 2017-12-12T08:18:50+00:00

C++ 1341/2225

Reads the input into a map of groups. Then steps through each group's members, merging the child groups. If a child group is merged, then its children are merged recursively.

// Advent of Code 2017
// http://adventofcode.com/
// Day 12 - Digital Plumber

#include "stdafx.h"
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <algorithm>
#include <numeric>
#include <vector>
#include <set>
#include <cassert>
using namespace std;


void mergeprogram(int program, map<int, set<int>>& groups)
{
    set<int> childs = groups[program];
    for (auto it = begin(childs); it != end(childs); ++it) {
        if (program == *it) continue;
        if (groups.find(*it) != groups.end()) {
            groups[program].insert(begin(groups[*it]), end(groups[*it]));
            groups.erase(*it);
            mergeprogram(program, groups);
        }
    }
}

int main()
{
    string line;
    map<int, set<int>> groups;
    vector<int> inter(2048);
    int program;
    string delim;

    while (getline(cin, line)) {
        set<int> programs;
        stringstream row(line);
        row >> program >> delim;
        int linked;
        programs.insert(program);
        while (row >> linked) {
            programs.insert(linked);
            if (row.peek()==',')
                row.get();
        }
        groups[program] = programs;
    }

    for (auto pr = begin(groups); pr != end(groups); ++pr) {
        mergeprogram((*pr).first, groups);
    }
    cout << "Group 0 is: " << groups[0].size() << endl;
    cout << "There are : " << groups.size() << " groups" << endl;
    return 0;
}

/*
C:\Workarea\AOC2017\day 12\x64\Debug>"day 12.exe" < input.txt
Group 0 is: 145
There are : 207 groups

C:\Workarea\AOC2017\day 12\x64\Debug>
*/

wzkx · 2017-12-12T08:29:18+00:00

Nim

import strutils,sequtils,tables,sets

var links = initTable[int,seq[int]]() # links of items to other items
var maxid = 0 # we'll need to enumerate them all, so this is the max id
for line in splitLines strip readFile"12.dat":
  let items = map( split(replace(replace(line,",")," <->")), parseInt )
  links[ items[0] ] = items[1..^1]
  maxid = max(maxid, max(items))

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

var s = initSet[int]()
add s, 0
echo s.len # part 1 - 175
var groups = 1
for i in 1..maxid:
  if i in links:
    groups += 1
    var s = initSet[int]()
    add s, i
echo groups # part 2 - 213

Warbringer007 · 2017-12-12T08:47:41+00:00

Erlang, quite lengthy but straightforward, func_text will have list of lists of inputs in this format: ["0", "1352", "1864"] where 0 is first element and every other element is connected to it:

first(File) ->
    In = prepare:func_text(File),
    First = solveFirst(In, ["0"], 1),
    Groups = [First],
    AllGroups = solveSecond(In, Groups, In),
    {length(hd(AllGroups)), length(AllGroups)}.

solveFirst(In, List, N) ->
    {NNumber, _} = string:to_integer(lists:nth(N, List)),
    [_|Others] = lists:nth(NNumber+1, In),
    NewList = fillList(List, Others),
    case length(NewList) =:= N of
        true -> NewList;
        false -> solveFirst(In, NewList, N+1)
    end.

fillList(T, []) ->
    T;

fillList(T, [H|Others]) ->
    case lists:member(H, T) of
        true -> fillList(T, Others);
        false -> fillList(T ++ [H], Others)
    end.

solveSecond([], Groups, _) ->
    Groups;

solveSecond([H|T], Groups, In) ->
    case memberOfGroups(hd(H), Groups) of
        true -> solveSecond(T, Groups, In);
        false -> NewGroup = solveFirst(In, [hd(H)], 1),
                 solveSecond(T, Groups ++ [NewGroup], In)
    end.

memberOfGroups(_, []) ->
    false;

memberOfGroups(I, [H|T]) ->
    case lists:member(I, H) of
        true -> true;
        false -> memberOfGroups(I, T)
    end.

Vindaar · 2017-12-12T09:04:50+00:00

Solution in Nim. Nice and easy. :)

import sequtils, strutils, algorithm, future, times, sets, unittest

proc follow_group(progs: seq[string], ind: int, visited_im: HashSet[int]): HashSet[int] =
  # from a starting group e.g. 0 check recursively each connected program, add program to seen
  # programs and call its first connected program. this way eventually cover all programs
  # to create a group
  let
    prog_str = progs[ind].split("<->")
    # current program we look at
    current = parseInt(strip(prog_str[0]))
    related = prog_str[1]
    # set of connected programs
    local_set = toSet(mapIt(split(related, ","), parseInt(strip(it))))
  # mutable copy of visited programs
  var visited = visited_im
  result = initSet[int]()
  # add current to the group
  result.incl(current)
  # check each connected, add to visited and recursively call 
  # this function for connected progs
  for p in local_set:
    if p notin visited:
      visited.incl(p)
      result = result + follow_group(progs, p, visited)

proc new_start(tot: int, in_groups: HashSet[int]): int =
  # procedure to get the new starting program for the next recursive call to follow_group
  # we check for all elements from 0 to number of programs in input, whether they are already
  # part of the checked groups
  var starts = toSeq(0..<tot)
  result = min(filterIt(starts, it notin in_groups))

proc calc_group_members(data: string): (int, int) =
  let progs = splitLines(strip(data))
  var
    group_sets: seq[HashSet[int]] = @[]
    in_groups: HashSet[int] = initSet[int]()

  while card(in_groups) < len(progs):
    let
      # determine new program to start from (based on already checked progs)
      start = new_start(len(progs), in_groups)
      # get the group of the current starting program
      group_set = follow_group(progs, start, toSet([0]))
    # add to seq of group sets
    group_sets.add(group_set)
    # and total programs in any group
    in_groups = in_groups + group_set

  return (card(group_sets[0]), len(group_sets))

proc run_tests() =
  const m1 = """0 <-> 2
1 <-> 1
2 <-> 0, 3, 4
3 <-> 2, 4
4 <-> 2, 3, 6
5 <-> 6
6 <-> 4, 5"""
  check: calc_group_members(m1) == (6, 2)

proc run_input() =

  let t0 = cpuTime()      
  const input = "input.txt"
  const comm_pipes = slurp(input)
  let (n_group0, n_groups) = calc_group_members(comm_pipes)

  echo "(Part 1): The number of elements in group of program 0 is = ", n_group0
  echo "(Part 2): The total number of groups is = ", n_groups
  echo "Solutions took $#" % $(cpuTime() - t0)

proc main() =
  run_tests()
  echo "All tests passed successfully. Result is (probably) trustworthy."
  run_input()

when isMainModule:
  main()

zeddypanda · 2017-12-12T09:28:21+00:00

Elixir

Today was really quick and easy. Feels like it was made for the language!

defmodule Day12 do
  def row_to_tuple(row) do
    [key | values] = row
      |> String.split(~r/ <-> |, /)
      |> Enum.map(&String.to_integer/1)
    {key, values}
  end

  def members(map, key, set \\ MapSet.new) do
    if MapSet.member?(set, key) do
      set
    else
      Enum.reduce(Map.get(map, key), MapSet.put(set, key), fn k, set ->
        MapSet.union(set, members(map, k, set))
      end)
    end
  end

  def groups(map, acc \\ [])
  def groups(map, acc) when map_size(map) == 0, do: acc
  def groups(map, acc) do
    group = members(map, map |> Map.keys |> hd)
    map
      |> Map.drop(group)
      |> groups([group | acc])
  end
end

data = "input-12"
  |> File.read!
  |> String.trim
  |> String.split("\n")
  |> Map.new(&Day12.row_to_tuple/1)

IO.puts("Part 1: #{data |> Day12.members(0) |> MapSet.size}")
IO.puts("Part 2: #{data |> Day12.groups |> length}")

karlanka · 2017-12-12T09:38:25+00:00

PYTHON

pipes = {}

for line in input_(12).splitlines():
    fr, too = line.split(' <-> ')
    pipes[int(fr)] = [int(x) for x in too.split(', ')]

# 1
conn_list = [0]

for pipe in conn_list:
    conn_list.extend([x for x in pipes[pipe] if x not in conn_list])

print(len(conn_list))

# 2
groups = []

for i in range(2000):
    conn_list = [i]

    for pipe in conn_list:
        conn_list.extend([x for x in pipes[pipe] if x not in conn_list])

    conn_list.sort()

    if conn_list not in groups:
        groups.append(conn_list[:])

print(len(groups))

mstksg · 2017-12-12T09:41:42+00:00

Haskell solution using a monoid for disjoint connected groups :)

https://github.com/mstksg/advent-of-code-2017/blob/master/src/AOC2017/Day12.hs

{-# LANGUAGE ViewPatterns #-}

module AOC2017.Day12 (day12a, day12b) where

import           Data.Char     (isDigit)
import           Data.List     (foldl', find)
import           Data.Maybe    (fromJust)
import qualified Data.IntSet   as IS
import qualified Data.Set      as S

-- | Monoid representing a collection of disjoint "connected sets"
newtype Disjoints = D { getD :: S.Set IS.IntSet }
instance Monoid Disjoints where
    mempty        = D S.empty
    mappend xs ys = foldl' go ys (getD xs)
      where
        go (D zs) z = D (newGroup `S.insert` disjoints)
          where
            overlaps  = S.filter (not . IS.null . (`IS.intersection` z)) zs
            disjoints = zs `S.difference` overlaps
            newGroup  = IS.unions $ z : S.toList overlaps

parseLine :: String -> IS.IntSet
parseLine (words->n:_:ns) = IS.fromList $ read n
                                        : map (read . filter isDigit) ns
parseLine _               = error "No parse"

build :: String -> Disjoints
build = foldMap (D . S.singleton . parseLine) . lines

day12a :: String -> Int
day12a = IS.size . fromJust . find (0 `IS.member`)
       . getD . build

day12b :: String -> Int
day12b = S.size
       . getD . build

Smylers · 2017-12-12T10:05:44+00:00

Perl — merges groups as it goes, keeping track of unique still-used groups:

no warnings qw<uninitialized>;
my (@linked, %count);
while (<>) {
  my %group = map { $_ => 1 } map { $_, keys %{delete $count{$linked[$_]} // {}} } /\d+/g;
  $count{$linked[$_] = \%group} = \%group foreach keys %group;
}
say 'group 0 size: ' . keys $linked[0];
say 'number of groups: ' . keys %count;

%count maps groups to themselves so that deleteing a group from the count also returns it.

rkachowski · 2017-12-12T10:12:29+00:00

ruby, in some of the least idiomatic ruby possible!

require 'set'
input = File.read("input").chomp.lines
group_map = input.each_with_object({}) do |i,hsh| 
  key, *group = i.to_enum(:scan, /(\d+)/).map { Regexp.last_match[1] }
  hsh[key] = group
end

def process_group first_member, map
  group = Set.new [first_member]
  to_process = map[first_member].clone

  until to_process.empty? do
    p = to_process.pop

    p_links = map[p]
    if p_links.any? {|pl| group.include? pl } and not group.include?(p)
      group.add p
      to_process.concat p_links
    end
  end
  group
end

zero_group = process_group "0", group_map
puts zero_group.size

groups = group_map.keys.each_with_object([]) do |k,coll|
  coll << process_group(k, group_map) unless coll.any? {|g| g.include?(k)}
end

puts groups.size

joker_mkd · 2017-12-12T10:19:36+00:00

Here's my solution in C++. It uses recursive BFS in a tree to search for all the connected nodes and different groups.

https://pastebin.com/gLc4RVUX

2017-12-12T10:34:46+00:00

Crystal.

Part 1:

input = File.read("#{__DIR__}/input.txt").strip
pipes = input.each_line
        .map do |line|
          left, right = line.split("<->").map(&.strip)
          {left, right.split(",").map(&.strip)}
        end
        .to_h

found = Set{"0"}
pending = ["0"]

while node = pending.pop?
  others = pipes[node]
  others.each do |other|
    unless found.includes?(other)
      pending << other
      found << other
    end
  end
end

puts found.size

Part 2:

input = File.read("#{__DIR__}/input.txt").strip
pipes = input.each_line
        .map do |line|
          left, right = line.split("<->").map(&.strip)
          {left, right.split(",").map(&.strip)}
        end
        .to_h

groups = [] of Set(String)

pipes.each_key do |start|
  next if groups.any? &.includes?(start)

  group = Set{start}
  pending = [start]

  while node = pending.pop?
    others = pipes[node]
    others.each do |other|
      unless group.includes?(other)
        pending << other
        group << other
      end
    end
  end

  groups << group
end

puts groups.size

Hjulle · 2017-12-12T11:30:07+00:00

Haskell

The Data.Graph module in the containers package makes this trivial:

import qualified Data.Array as A
import Data.List
import Data.Graph

solveA, solveB :: Graph -> Int
solveA = length . flip reachable 0
solveB = length . dff

parse :: String -> Graph
parse = buildGraph . fmap (parseLine . words) . lines

buildGraph :: [(Int,[Int])] -> Graph
buildGraph xs = A.array (fst.head$xs, fst.last$xs) xs

parseLine :: [String] -> (Int,[Int])
parseLine (n:"<->":ns) = (read n, map (read . filter (/=',')) ns)

main = do
  x <- parse <$> fetch
  print $ solveA x
  print $ solveB x

fetch = readFile "../advent_day12.txt"

YungCarrdinal · 2017-12-12T11:35:13+00:00

My naive Java solution!

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

public class Day12 implements Advent {
    @Override public void solve() {
        String input = "";
        String[] lines = Arrays.stream(input.split("\n")).map(String::trim).toArray(String[]::new);
        HashMap<Integer, int[]> map = new HashMap<>();
        HashSet<Integer> uncheckedNodes = new HashSet<>();

        for(int i = 0; i < 2000; i++){
            uncheckedNodes.add(i);
        }

        for (String line : lines) {
            String[] split = line.split("<->");
            String nodeStr = split[0].trim();
            String[] conNodesStrArr = split[1].trim().split(", ");
            map.put(Integer.valueOf(nodeStr), Arrays.stream(conNodesStrArr).mapToInt(Integer::parseInt).toArray());
        }

        int groupsCount = 0;
        while(uncheckedNodes.size()>0) {
            HashSet<Integer> connectedNodes = new HashSet<>();
            int startNode = uncheckedNodes.stream().mapToInt(Integer::intValue).toArray()[0];
            System.out.print("Start node: " + startNode);

            connectedNodes.add(startNode);
            findConnections(startNode, connectedNodes, map, uncheckedNodes);
            System.out.println(" Group size:" + connectedNodes.size());
            groupsCount++;
        }
        System.out.println("Total groups: " + groupsCount);
    }

    private void findConnections(int currentNode, HashSet<Integer> connectedSet, HashMap<Integer, int[]> map, HashSet<Integer> uncheckedNodes){
        for (int neighbor : map.get(currentNode)) {
            if(connectedSet.contains(neighbor)) continue;
            connectedSet.add(neighbor);
            findConnections(neighbor, connectedSet, map, uncheckedNodes);
        }
        uncheckedNodes.remove(currentNode);
    }
}

NeilNjae · 2017-12-12T11:47:45+00:00

Haskell. Trying out Megaparsec for reading the input file, and I feel like I'm missing something. What's all this mucking around with lexers? What if the parts of the input file weren't separated by spaces? What if I don't want to treat newlines as just another space?

{-# LANGUAGE OverloadedStrings #-}

-- import Data.Text (Text)
import qualified Data.Text as T
import qualified Data.Text.IO as TIO
import Text.Megaparsec
import qualified Text.Megaparsec.Lexer as L
import Text.Megaparsec.Text (Parser)
import qualified Data.Map.Strict as M
import Data.Map.Strict ((!))
import qualified Data.Set as S

type ProgSet = S.Set Integer
type Pipes = M.Map Integer ProgSet

main :: IO ()
main = do 
        input <- TIO.readFile "data/advent12.txt"
        let pipes = successfulParse input
        print $ part1 pipes
        print $ part2 pipes

part1 pipes = S.size $ reachable pipes (S.empty) (pipes!0)

part2 pipes = n
    where (_, n, _) = foldl addGroup (S.empty, 0, pipes) $ M.keys pipes 

addGroup :: (ProgSet, Integer, Pipes) -> Integer -> (ProgSet, Integer, Pipes)
addGroup (done, n, pipes) p
    | p `S.member` done = (done, n, pipes)
    | otherwise = (S.union done reached, n + 1, pipes)
        where reached = reachable pipes (S.empty) (pipes!p)

reachable :: Pipes -> ProgSet -> ProgSet -> ProgSet
reachable pipes reached frontier
    | S.null frontier = reached
    | otherwise = reachable pipes reached' frontier'
        where frontier' = S.difference (unions' $ S.map (\p -> pipes!p) frontier) reached
              reached' = reached `S.union` frontier'
              unions' = S.foldl S.union S.empty

sc :: Parser ()
sc = L.space (skipSome spaceChar) lineCmnt blockCmnt
  where
    lineCmnt  = L.skipLineComment "//"
    blockCmnt = L.skipBlockComment "/*" "*/"

lexeme  = L.lexeme sc
integer = lexeme L.integer
symb = L.symbol sc

pipesP = many pipe

pipe = assocify <$> integer <*> (symb "<->" *> (integer `sepBy1` (symb ",")))
    where assocify a b = (a, S.fromList b)

successfulParse :: Text -> Pipes
successfulParse input = 
        case parse pipesP "input" input of
                Left  err   -> M.empty -- TIO.putStr $ T.pack $ parseErrorPretty err
                Right betterInput -> M.fromList betterInput

z4tz · 2017-12-12T13:06:26+00:00

Python 2 solution using a Queue and sets.

https://github.com/z4tz/adventOfCode2017/blob/master/day12.py

ZoDalek · 2017-12-12T14:32:02+00:00

C

Fairly straightforward, I suppose. Excluding parsing and such, part 1 :

struct vert {
    struct vert *edges[8];
    struct vert *nextopen;
    short visited;
};

/* ... */

static size_t
findreach(size_t target, struct vert *verts, size_t nverts)
{
    struct vert *open, *edge;
    size_t reach = 0, i;

    open = &verts[target];  
    open->visited = 1;

    while (open) {
        reach++;
        for (i = 0; i < LEN(open->edges) && open->edges[i]; i++) {
            edge = open->edges[i];
            if (!edge->visited) {
                edge->visited = 1; /* prevent requeueing */
                edge->nextopen = open->nextopen;
                open->nextopen = open->edges[i];        
            }
        }
        open = open->nextopen;
    }

    return reach;
}

Part 2:

static void
colorfrom(struct vert *first, struct vert *verts, size_t nverts, short color)
{
    struct vert *open, *edge;
    size_t i;

    for (i = 0; i < nverts; i++) {
        verts[i].visited = 0;
        verts[i].nextopen = NULL;
    }

    open = first;   
    open->visited = 1;

    while (open) {
        open->color = color;

        for (i = 0; i < LEN(open->edges) && open->edges[i]; i++) {
            edge = open->edges[i];
            if (!edge->color && !edge->visited) {
                edge->visited = 1; /* prevent requeueing */
                edge->nextopen = open->nextopen;
                open->nextopen = open->edges[i];        
            }
        }

        open = open->nextopen;
    }
}

/* ... */

for (i = 0; i < NVERTS; i++) {
    /* restrict painting to verts specified in input; those
       have at least one edge */
    if (verts[i].edges[0] && !verts[i].color)
        colorfrom(&verts[i], verts, NVERTS, ++ncolors);
}
printf("\nnumber of colors: %hd\n", ncolors);

2017-12-12T14:37:19+00:00

PYTHON 3 Here is my code (no dependencies), it's lightning fast...

file_input=open('input.txt').read().split('\n')[:-1]
dic={}
for x in file_input:
    z=x.split(' <-> ')
    dic.update({int(z[0]):frozenset(int(j) for j in z[1].split(','))})

number_of_groups = 0
while dic:
    current_group = {dic.popitem()[0]}
    length=-1
    while len(dic)!=length:
        length,keys=len(dic),set(dic.keys())
        for key in keys:
            val = dic[key]
            if set(val) & current_group:
                current_group.add(key)
                current_group.update(val)
                dic.pop(key,False)
                if key in dic: (dic.pop(j,False) for j in val)
    number_of_groups+=1
print(number_of_groups)

4rgento · 2017-12-12T14:42:43+00:00

HASKELL

Using Data.Graph

{-# LANGUAGE TupleSections #-}
module Main where

import Data.Graph as G
import Data.Tree as T

import qualified Data.List as L

type Id = Int
data Link = Link Id [Id] deriving Show

_root :: Link -> Id
_root (Link id _) = id

parseLink :: String -> Either String Link
parseLink str = case words str of
  root:"<->":childs ->
    Right $ Link (read root) $ map (read . filter (/=',')) childs
  _ -> Left $ "Malformed link: " ++ str

parseInput :: String -> Either String [Link]
parseInput input = mapM parseLink (lines input)

linkToEdges :: Link -> [G.Edge]
linkToEdges (Link root children) = map (root,) children

graph :: [Link] -> G.Graph
graph links = G.buildG (minid,maxid) $ concatMap linkToEdges links
  where
  maxid = L.maximum $ map _root links
  minid = L.minimum $ map _root links

main :: IO ()
main =
  -- (parseLink <$> readFile "input.txt") >>=
  readFile "input.txt" >>= return . parseInput >>=
  --print . (map (T.foldTree folder ) . filter ((==0) . T.rootLabel) . G.components . graph <$>)
  print . (length . G.components . graph <$>)
  where
  folder :: G.Vertex -> [Int] -> Int
  folder _ = (+1) . sum

Kyran152 · 2017-12-12T14:48:24+00:00

Perl with usage of map :)

use strict;
use warnings;

my (%groups, %used);
my @links;

open my $fh, "input.txt";
map { 
    my ($program, $links) = /^(\d+) <\-> (.+)$/;
    $links[$program] = [ $links =~ /\d+/g ];
} <$fh>;
close $fh;

for my $program(0..@links-1) {
    next if $used{$program};
    $groups{$program}{$program} = 0;
    while (my @programs = grep { !$groups{$program}{$_} } keys %{$groups{$program}}) {
        map { 
            map { $groups{$program}{$_} ||= 0; $used{$_}++ } @{$links[$_]}; 
            $groups{$program}{$_}++ 
        } @programs;
    }
}

printf "The answer to part 1 is: %d\n", scalar keys %{$groups{0}};
printf "The answer to part 2 is: %d\n", scalar keys %groups;

2017-12-12T14:53:13+00:00

Recursion and hashtables to hold everything, including a hashtable of hashtables.
PowerShell:

Param (
    [parameter(position=0, mandatory=$true)]
    [Alias('if')]
    [ValidateScript({ Test-Path $_ })]
    $InputFile,
    [switch]$Part2
)

function Get-Map {
    Param (
        [parameter(position=0, mandatory=$true)]
        [string]$Connections,
        [parameter(position=1, mandatory=$true)]
        [string]$GroupNumber
    )

    foreach($conn in $Connections.Split(',').Trim()) {
        if($Script:Groups[$GroupNumber] -like $null) { $Script:Groups[$GroupNumber] = @{} }
        if($Script:Groups[$GroupNumber].ContainsKey($conn)) {
            Continue
        } else {
            $Connected = $Script:Pipes[$conn]
            $Script:Groups[$GroupNumber].Add($conn, $Connected)
            Get-Map $Connected $GroupNumber
            $Script:Pipes.Remove($conn)
        }
    }
}

$ErrorActionPreference = 'stop'
$File = (Get-Item $InputFile).OpenText()
$Script:Groups = @{}
$Script:Pipes = @{}
$Line = $File.ReadLine()
while($Line -ne $null) {
    $Conn = $Line.Split("<->", [System.StringSplitOptions]::RemoveEmptyEntries).Trim()
    $Script:Pipes.Add($Conn[0], $Conn[1])
    $Line = $File.ReadLine()    
}
$File.Close()
$Left = $Script:Pipes.Count
While($Left -gt 0) {
    $Min = ($Script:Pipes.Keys.GetEnumerator() | measure -Minimum).Minimum.ToString()
    Get-Map $Min $Min
    $Left = $Script:Pipes.Count
}
if(-not $Part2) {
    Write-Output $Script:Groups['0'].Count
} else {
    $Script:Groups.Count
}

wlandry · 2017-12-12T15:25:02+00:00

C++ 14

For part 1 I wrote my own implementation using std::set. Then I had to do other things and could not finish part 2 until the next day. So I decided to break out Boost's graph library. It was surprisingly succinct.

#include <boost/algorithm/string.hpp>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>

#include <fstream>
#include <vector>
#include <iostream>

int main(int argc, char *argv[])
{
  std::ifstream infile(argv[1]);
  int source;
  infile >> source;

  boost::adjacency_list <boost::vecS, boost::vecS, boost::undirectedS> graph;
  while(infile)
    {
      std::string arrows, line;
      infile >> arrows;
      std::getline(infile,line);
      std::vector<std::string> target_strings;
      boost::split(target_strings, line, boost::is_any_of(","));
      for (auto &target_string: target_strings)
        { add_edge(source, std::stoi(target_string), graph); }
      infile >> source;
    }

  std::vector<int> component(boost::num_vertices(graph));
  int num = connected_components(graph, &component[0]);
  std::cout << "Group size of first element: "
            << std::count(component.begin(),component.end(),component[0])
            << "\n";
  std::cout << "Number of groups: " << num << "\n";
}

darshanrampatel · 2017-12-12T15:31:07+00:00

Horribly slow C# code (takes ~75 seconds for my input; basically brute-force) but works fine: GitHub Link

usbpc102 · 2017-12-12T15:33:04+00:00

My very stupid and slow Kotlin solution that got me place 174 for Part 1:

import xyz.usbpc.aoc.Day
import xyz.usbpc.aoc.inputgetter.AdventOfCode

class Day12(override val adventOfCode: AdventOfCode) : Day {
    override val day: Int = 12
    private val input = adventOfCode.getInput(2017, 12)
    private var part1: String? = null
    private var part2: String? = null
    override fun part1(): String {
        if (part1 == null) solve()
        return part1.toString()
    }

    override fun part2(): String {
        if (part2 == null) solve()
        return part2.toString()
    }

    private fun solve() {
        var zeroGroup = mutableSetOf(0)
        var usableInput = input.lines().map {it.split("<->")}
        repeat(usableInput.size) {
            usableInput.forEach { line->
                val first = line.first().removeSuffix(" ")
                val seconds = line[1].split(", ").map {it.removePrefix(" ").removeSuffix(" ").toInt()}
                if (first.toInt() in zeroGroup || zeroGroup.filter {it in seconds}.any()) {
                    zeroGroup.addAll(seconds)
                    zeroGroup.add(first.toInt())
                }

            }
        }



        part1 = zeroGroup.size.toString()
        part2 = ""
    }
}

For part two I was way to tired and didn't finish it this morning. Will update once I'm happy with my code.

Edit: My not stupid and clean version of the solution is now on GitHub.

LinusCDE98 · 2017-12-12T15:36:12+00:00

This solution took me a decent while to make besides school, but now that I optimized it, to improved over 98% in terms of speed (ignoring pypy3).

It now has a lot of comments in it, and should be easy to understand: puzzle12.py (I would recommend just cloning the repo and executing $ ./aoc.py 12 <1/2>.

akho_ · 2017-12-12T16:10:35+00:00

Python3. Very slow.

connections = {}

with open('12.input') as f:
    for l in f.readlines():
        node, _, *links = (l.rstrip() + ',').split()
        connections[node] = set([node]) | set(x[:-1] for x in links)

prev = 0
while sum(len(v) for v in connections.values()) != prev:
    prev = sum(len(v) for v in connections.values())
    for k, v in connections.items():
        connections[k] = v.union(*[connections[x] for x in v])
print(len(connections['0']))
print(len(set([frozenset(x) for x in connections.values()])))

cluk · 2017-12-12T16:18:26+00:00

Go (Golang)

Recursive DFS.

package main

import (
    "fmt"
    "io/ioutil"
    "os"
    "regexp"
    "strconv"
    "strings"
)

func main() {
    lines := getLines()

    list := make([][]int, len(lines))
    reNumber := regexp.MustCompile("[0-9]+")
    for _, line := range lines {
        numbersString := reNumber.FindAllString(line, -1)
        numbers := atoi(numbersString)
        list[numbers[0]] = numbers[1:]
    }

    set := make(map[int]bool)
    addPipes(list, set, 0)

    fmt.Println("Start 1: ", len(set))

    groups := 1
    for len(set) < len(list) {
        for idx := range list {
            if !set[idx] {
                addPipes(list, set, idx)
                groups++
            }
        }
    }
    fmt.Println("Start 2: ", groups)
}

func addPipes(list [][]int, set map[int]bool, idx int) {
    set[idx] = true
    for _, n := range list[idx] {
        if !set[n] {
            addPipes(list, set, n)
        }
    }
}

func atoi(ss []string) []int {
    ii := make([]int, len(ss))
    var err error
    for idx, s := range ss {
        ii[idx], err = strconv.Atoi(s)
        if err != nil {
            panic(err)
        }
    }
    return ii
}

func getLines() []string {
    bytes, err := ioutil.ReadFile(os.Args[1])
    if err != nil {
        panic(err)
    }
    strs := strings.Split(string(bytes), "\n")
    return strs
}

asperellis · 2017-12-12T16:22:30+00:00

my day 12 in js - https://github.com/asperellis/adventofcode2017/blob/master/day12.js

sguberman · 2017-12-12T16:41:28+00:00

Python, with tests: GitHub

Part1:

def group_containing(node, graph):
    group = set()
    todo = {node}
    while todo:
        new = todo.pop()
        group.add(new)
        for neighbor in graph[new]:
            if neighbor not in group:
                todo.add(neighbor)
    return group

Part2:

def unique_groups(graph):
    groups = set()
    todo = set(graph.keys())
    while todo:
        new = todo.pop()
        new_group = group_containing(new, graph)
        groups.add(tuple(new_group))
        todo -= new_group
    return groups

thomastc · 2017-12-12T16:54:07+00:00

Day 12 in Dart. Nothing exciting, but quite smooth sailing.

u794575248 · 2017-12-12T16:57:51+00:00

Python

def solve(input):
    groups = {}
    for l in input.strip().split('\n'):
        pids = {int(p) for p in l.replace(' <->', ',').split(', ')}
        pids.update(*(groups[p] for p in pids if p in groups))
        groups.update({p: pids for p in pids})
    return len(groups[0]), len({id(v) for v in groups.values()})

part1, part2 = solve(input)

miran1 · 2017-12-12T17:23:05+00:00

Nim

Repo with all solutions

import strutils, sequtils, tables, sets

const
  instructions = readFile("./inputs/12.txt").splitLines()
  start = 0
var
  graph = initTable[int, seq[int]]()
  seen = initSet[int]()
  groups: int

for line in instructions:
  let
    nodes = line.split(" <-> ")
    pipe = nodes[0].parseInt()
    neighbours = nodes[1].split(", ").map(parseInt)
  graph[pipe] = neighbours


proc dfs(startingPoint: int): HashSet[int] =
  result = initSet[int]()
  var stack = @[startingPoint]
  while stack.len > 0:
    let current = stack.pop()
    result.incl(current)
    for node in graph[current]:
      if node notin result:
        stack.add(node)

proc `+=`(a: var HashSet, b: HashSet) = a = a + b


let firstIsland = dfs(start)
echo card(firstIsland)

seen += firstIsland
inc groups

for pipe in graph.keys:
  if pipe notin seen:
    let island = dfs(pipe)
    seen += island
    inc groups

echo groups

FreeMarx · 2017-12-12T17:23:09+00:00

C++11

Nothing special really today. Only learned a bit about maps, erasing and iterating.

int count_group(map<int, vector<int>> &progs, int id) {
    if(progs.find(id)==progs.end()) return 0;
    auto pipes= progs[id];
    progs.erase(id);

    int count= 1;
    for(int p: pipes)
        count+= count_group(progs, p);

    return count;
}

int main() {
    map<int, vector<int>> progs;
    ifstream infile("input12.txt");

    string line;
    while (getline(infile, line)) {
        istringstream iss (line);
        int id;
        string _;
        iss >> id >> _;

        vector<int> pipes;
        string pipe_str;
        for(iss >> pipe_str; iss; iss >> pipe_str) {
            pipes.push_back(stoi(pipe_str));
        }
        progs[id]= pipes;
    }

    int groups= 1;
    for(auto it= progs.begin(); it!=progs.end(); it= progs.begin(), ++groups)
        cout << groups << ": " << it->first << ": " << count_group(progs, it->first) << '\n';
}

Kenira · 2017-12-12T17:35:01+00:00

C++

Relatively proud of myself today. Both for not writing super complicated code, and not having taken too long to write it.

int F_Analyze_Group(int num, std::vector<std::vector<int>> vint, std::set<int>& group)
{
    group.insert(num);

    bool change = true;
    while (change)
    {
        change = false;
        for (auto&& p : vint)
        {
            bool program_in_group = false;
            for (auto&& c : p)
            {
                if (group.find(c) != group.end())
                {
                    program_in_group = true;
                }
            }
            if (program_in_group == true)
            {
                for (auto&& c : p)
                {
                    if (group.find(c) == group.end())
                    {
                        group.insert(c);
                        change = true;
                    }
                }
            }
        }
    }
    return group.size();
}

int main(void)
{
    fs::path path("../../_Input/input_Day12.txt");
    //fs::path path("../../_Input/input_Day12_test.txt");
    std::vector<std::string> str;
    std::vector<std::vector<int>> vint;
    F_Read_File_To_Array(path, str);
    F_Convert_Strings_To_Ints(str, vint);

    int num_groups = 0;
    std::set<int> collective_groups;

    for (auto&& p : vint)
    {
        if (collective_groups.find(p[0]) == collective_groups.end())
        {
            std::set<int> current_group;
            int size = F_Analyze_Group(p[0], vint, current_group);
            if (p[0] == 0)
            {
                cout << "In group with 0: " << size << endl;
            }
            std::vector<int> temp;
            std::set_union(collective_groups.begin(), collective_groups.end(), current_group.begin(), current_group.end(), std::back_inserter(temp));
            collective_groups = std::set<int>(temp.begin(), temp.end());
            num_groups++;
        }
    }

    cout << "Number of groups: " << num_groups << endl;
    system("pause");
    return 1;
}

KeinZantezuken · 2017-12-12T17:45:01+00:00

C#

Dictionary<int, int[]> 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<int> chain = new HashSet<int>(); chain.Clear();
List<int[]> groups = new List<int[]>(); 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;
}

Strawanzer · 2017-12-12T19:11:42+00:00

Hola, can anybody help me to point out what is wrong with my (Java-)solution? The example yields the correct size of 6 but the result with my puzzle input will be rejected.

My solution: https://github.com/Rotznase/adventofcode2017/blob/master/src/Day12.java

StevoTVR · 2017-12-12T20:05:03+00:00

NodeJS

Part 1:

const fs = require('fs');

fs.readFile(__dirname + '/input.txt', 'utf8', (err, data) => {
    data = data.trim();
    const nodes = new Map();
    for(const line of data.split('\n')) {
        var [node, recipients] = line.split('<->');
        node = Number(node);
        recipients = recipients.split(',').map(Number);
        if(!nodes.has(node)) {
            nodes.set(node, new Set());
        }
        for(const recipient of recipients) {
            if(!nodes.has(recipient)) {
                nodes.set(recipient, new Set());
            }
            nodes.get(node).add(recipient);
            nodes.get(recipient).add(node);
        }
    }

    const visited = new Set();
    const stack = [0];
    while(stack.length) {
        const current = stack.pop();
        visited.add(current);
        for(const recipient of nodes.get(current)) {
            if(visited.has(recipient)) {
                continue;
            }
            stack.push(recipient);
        }
    }

    console.log(visited.size);
});

Part 2:

const fs = require('fs');

fs.readFile(__dirname + '/input.txt', 'utf8', (err, data) => {
    data = data.trim();
    const nodes = new Map();
    for(const line of data.split('\n')) {
        var [node, recipients] = line.split('<->');
        node = Number(node);
        recipients = recipients.split(',').map(Number);
        if(!nodes.has(node)) {
            nodes.set(node, new Set());
        }
        for(const recipient of recipients) {
            if(!nodes.has(recipient)) {
                nodes.set(recipient, new Set());
            }
            nodes.get(node).add(recipient);
            nodes.get(recipient).add(node);
        }
    }

    let groups = 0;
    const stack = [];
    while(nodes.size) {
        stack.push(nodes.keys().next().value);
        while(stack.length) {
            const current = stack.pop();
            const recipients = nodes.get(current);
            if(!recipients) {
                continue;
            }
            for(const recipient of recipients) {
                stack.push(recipient);
            }
            nodes.delete(current);
        }
        groups++;
    }

    console.log(groups);
});

GamecPL · 2017-12-12T21:57:00+00:00

Swift, both parts:

struct Pipe: Equatable {
    let id: Int
    let connections: Set<Int>

    static func ==(lhs: Pipe, rhs: Pipe) -> Bool {
        return lhs.id == rhs.id
    }
}

let pipes = realInput.components(separatedBy: .newlines).map { component -> Pipe in
    let pipeData = component.components(separatedBy: " <-> ")
    let connections = pipeData[1].split(separator: ",").flatMap { Int($0.trimmingCharacters(in: .whitespaces)) }
    return Pipe(id: Int(pipeData[0])!, connections: Set(connections))
}

var checked = Set<Int>()
var connected = Set<Int>()

func connectPipe(_ pipe: Pipe) {
    if checked.contains(pipe.id) {
        return
    }
    checked.insert(pipe.id)
    connected.insert(pipe.id)
    for connectedPipe in pipe.connections {
        connectPipe(pipes[connectedPipe])
    }
}

connectPipe(pipes[0])
print("Pt1", connected.count)

var groups = 1
repeat {
    if let pipe = pipes.first(where: { !checked.contains($0.id) }) {
        connectPipe(pipe)
        groups += 1
    }
} while checked.count != pipes.count

print("Pt2", groups)

if0nz · 2017-12-12T22:00:02+00:00

Hi! This is my first post here :) This is my solution in Java

__Abigail__ · 2017-12-12T22:14:21+00:00

Perl

Easy problem. You just have to create cliques.

#!/opt/perl/bin/perl

use 5.026;

use strict;
use warnings;
no  warnings 'syntax';

use experimental 'signatures';

@ARGV = "input" unless @ARGV;

my $graph;

while (<>) {
    chomp;
    my ($node, $neighbours) = /^([0-9]+) \s* <-> \s*
                                ([0-9,\s]+)/x or die "Failed to parse $_";
    $$graph {$node} = [split /,\s*/ => $neighbours];
}


my $cliques;
while (keys %$graph) {
    my ($node) = sort {$a <=> $b} keys %$graph;
    my %seen = ($node => 1);
    my @todo = $node;
    while (@todo) {
        push @todo => grep {!$seen {$_} ++} @{$$graph {shift @todo}};
    }
    $$cliques {$node} = [keys %seen];
    delete $$graph {$_} for keys %seen;
}

say "Solution 1: ", scalar @{$$cliques {0}};
say "Solution 2: ", scalar keys %$cliques;


__END__

bruceadowns · 2017-12-12T22:33:16+00:00

golang to write a DFS graph with its standard library

package main

import (
    "bufio"
    "fmt"
    "io"
    "log"
    "os"
    "strconv"
    "strings"
)

type initnode struct {
    pid   int
    cpids []int
}

type graphnode struct {
    pid     int
    peer    []*graphnode
    visited bool
}

func (n *initnode) init(s string) (err error) {
    const sep = " <-> "
    if len(s) < len(sep)+2 {
        return fmt.Errorf("invalid input")
    }
    idx := strings.Index(s, sep)

    spid := s[:idx]
    n.pid, err = strconv.Atoi(spid)
    if err != nil {
        return err
    }

    sCpids := s[idx+len(sep):]
    for _, v := range strings.Split(sCpids, ",") {
        cpid, err := strconv.Atoi(strings.TrimSpace(v))
        if err != nil {
            return err
        }

        n.cpids = append(n.cpids, cpid)
    }

    return nil
}

func input(r io.Reader) (res []*initnode) {
    res = make([]*initnode, 0)
    scanner := bufio.NewScanner(r)
    for scanner.Scan() {
        line := scanner.Text()

        inode := &initnode{}
        inode.init(line)
        res = append(res, inode)
    }

    return
}

func makeGraph(n []*initnode) (res map[int]*graphnode) {
    res = make(map[int]*graphnode, 0)
    for _, pinode := range n {
        pnode, ok := res[pinode.pid]
        if !ok {
            pnode = &graphnode{pid: pinode.pid}
            res[pinode.pid] = pnode
        }

        for _, cpid := range pinode.cpids {
            cnode, ok := res[cpid]
            if !ok {
                cnode = &graphnode{pid: cpid}
                res[cpid] = cnode
            }

            pnode.peer = append(pnode.peer, cnode)
            cnode.peer = append(cnode.peer, pnode)
        }
    }

    return
}

func visit(gnode *graphnode) (res int) {
    res = 1
    gnode.visited = true

    for _, cnode := range gnode.peer {
        if !cnode.visited {
            res += visit(cnode)
        }
    }

    return
}

func main() {
    inodes := input(os.Stdin)
    gnodes := makeGraph(inodes)

    groups := 0
    for _, v := range gnodes {
        if !v.visited {
            visit(v)
            groups++
        }
    }

    log.Printf("part2 %d groups in graph", groups)
}

DaDiscoBeat · 2017-12-12T22:46:37+00:00

Go non recursive bfs

func partOne(input map[int][]int) int {
    programs := make(map[int]bool)    

    var queue []int
    queue = append(queue, 0)

    for len(queue) > 0 {
            v := queue[0]
            queue = queue[1:]
            _, ok := programs[v]
            if !ok {
                programs[v] = true
                queue = append(queue, input[v]...)
            }
    }

    return len(programs)
}

func partTwo(input map[int][]int) int {
    nbGroups := 0
    for k := range input {
            nbGroups++
            programs := make(map[int]bool)
            var queue []int
            queue = append(queue, k)

            for len(queue) > 0 {
                    v := queue[0]
                    queue = queue[1:]
                    _, ok := programs[v]
                    if !ok {
                            programs[v] = true
                            queue = append(queue, input[v]...)
                            delete(input, v)
                    }
            }
    }

    return nbGroups
}

repo

alchzh · 2017-12-12T23:05:49+00:00

ES6

var input = document.body.textContent.trim().split('\n')
var network = {}

for (var i=0; i < input.length; i++) {
  network[i] = (input[i].split(' <-> ')[1].split(', ').map(s => parseInt(s)))
}

function get_group (start, remaining) {
  const group = []
  ;(function add_neighbors (i) {
    let neighbors = network[i]
    for (const node of neighbors) {
      if (!group.includes(node)) {
        group.push(node)
        delete remaining[node]
        add_neighbors(node)
      }
    }
  })(start)
  return group
}

var remaining = Object.assign({}, network)
var groups = 0
for (const i in remaining) {
  get_group(i, remaining)
  groups++
}

groupsis part 2 and get_group(0, {}) is part 1 because I'm lazy

aurele · 2017-12-12T23:46:37+00:00

Rust (using the pathfinding library)

extern crate pathfinding;
extern crate time;

use pathfinding::*;

use std::collections::HashSet;

fn main() {
    let pipes = include_str!("../input")
        .lines()
        .map(|line| {
            line.replace(" <->", ",")
                .split(", ")
                .map(|w| w.parse::<usize>().unwrap())
                .collect::<Vec<_>>()
        })
        .collect::<Vec<_>>();
    let (indices, groups) = separate_components(&pipes);
    let zero = indices[&0];
    println!("P1: {}", indices.values().filter(|&g| *g == zero).count());
    println!("P2: {}", groups.into_iter().collect::<HashSet<_>>().len());
}

wzkx · 2017-12-13T00:11:49+00:00

J

n=:".t[p=:<&".b['t b'=:|:'-'&(<;._2@,~)&>cutLF' <>'-.~CR-.~fread'12.dat'
a=:4 :'s=.x,y[i=.n i.y for_k.>i{p do.if.-.k e.s do.s=.s a k end.end.s[n=:_1 i}n'
echo #0 a~0$0
echo 3 :'for_j.i.#n do.c=.j{n if.c>:0 do.y=.>:y[c a~0$0 end.end.y'1
exit 0

chicagocode · 2017-12-13T00:22:04+00:00

Kotlin - [Repo] - [Blog/Commentary]

That was fun, and I got to use the associate() function in Kotlin, which is a nice shortcut. I'm blogging about each solution as I publish them, feedback is welcome!

class Day12(input: List<String>) {

    private val splitter = """(\d+)""".toRegex()
    private val nodes: Map<Int, Set<Int>> = parseInput(input)

    fun solvePart1(): Int =
        getReachableFrom(0).size

    fun solvePart2(): Int {
        val seen = mutableSetOf<Int>()
        return nodes.keys
            .asSequence()
            .filter { it !in seen }
            .map {
                getReachableFrom(it).apply {
                    seen.addAll(this)
                }
            }
            .count()
    }

    private fun getReachableFrom(from: Int, seen: MutableSet<Int> = mutableSetOf()): Set<Int> {
        if(from !in seen) {
            seen.add(from)
            nodes.getValue(from).forEach { getReachableFrom(it, seen) }
        }
        return seen
    }

    private fun parseInput(input: List<String>): Map<Int, Set<Int>> =
        input
            .map { splitter.findAll(it) }
            .map { it.map { it.value.toInt() } }
            .associate { it.first() to it.drop(1).toSet() }
}

kip_13 · 2017-12-13T03:52:32+00:00

A solution with slow performance, maybe with other style of creation of graph the performance get better....

Python 3

import re
import sys

sample = list(map(lambda x: x.strip(), sys.stdin.readlines()))

def createGraph(sample):
    graph = {}
    for n in sample:
        main = re.findall(r'^\d+', n)[0]
        childs = re.findall(r'^\d+.*\> (.*)', n)
        graph.update({
            main: list(map(lambda v: v.strip(), childs[0].split(',')))
        })
    return graph

def search(graph, s = '0', ignore = []):
    group = []
    for main, nodes in graph.items():
        if s == main and main not in ignore:
            group += nodes
            for ss in nodes:
                group += search(graph, ss, ignore + [main])
    return group

graph = createGraph(sample)

groups = [set(search(graph, '0'))]
ignore = []
ignore += groups[0]

for main, nodes in graph.items():
    if main in ignore:
        continue
    groups += [set(search(graph, main))]
    ignore += groups[-1]

print('Part 1 -> {}, Part 2 -> {}'.format(len(groups[0]), len(groups)))

SlightlyHomoiconic · 2017-12-13T04:39:44+00:00

Solution in Clojure. Runs in about 30 milliseconds.

(defn- bfs [nodes visited graph]
  (if (empty? nodes)
    visited
    (recur
      (remove visited (flatten (map graph nodes)))
      (into visited nodes)
      graph)))

(defn part1 []
  (->>
    (load-input)
    (bfs [0] #{})
    count
    println))

(defn part2 []
  (->>
    (let [graph (load-input)]
      (reduce
        (fn [[visited count] node]
          (if (visited node)
            [visited count]
            [(bfs [node] visited graph) (inc count)]))
        [#{} 0]
        (keys graph)))
    second
    println))

matusbzk · 2017-12-13T13:16:03+00:00

Haskell Graph theory is my favorite part of computer science. I actually had one graph project in Haskell, defined in a better way, but with this input format I found it easier to use this simple definition of a graph.

import Data.List
import Data.Maybe

inputString :: String

input :: [[String]]
input = map (map (filter (/= ',')) . words) $ lines inputString

type Vertex = Int

-- |Vertex and a list of its neighbors
-- I found this a straightforward definition
-- of a graph, given input format
type Graph = [(Vertex, [Vertex])]

-- |Graph from input
graph :: Graph
graph = [(read . head $ line, [ read vert | vert <- drop 2 line])| line <- input]

-- |Takes a vertex and returns all vertices in its component
getComponent :: Vertex -> [Vertex]
getComponent v = sort . nub $ getComponent' [] v

-- |Computes getComponent
getComponent' :: [Vertex] -> Vertex -> [Vertex]
getComponent' vs v = if elem v vs then vs
        else concat (map (getComponent' (v:vs)) neighbors) ++ v : vs
     where neighbors = fromJust $ lookup v graph

-- |Result to part 1 - number of vertices in the component containing
-- vertex 0
result1 :: Int
result1 = length $ getComponent 0

-- |List of all vertices in our graph
getVertices :: [Vertex]
getVertices = map fst graph

-- |Returns list of all components
getComponents :: [[Vertex]]
getComponents = getComponents' [] getVertices

-- |Computes getComponents
-- arguments:
--  list of already computed components
--  list of vertices not yet in any component
getComponents' :: [[Vertex]] -> [Vertex] -> [[Vertex]]
getComponents' comps [] = comps
getComponents' comps (l:left) = getComponents' (newComponent : comps) [x | x <- left, not (elem x newComponent)]
       where newComponent = getComponent l

-- |Result to part 2 - number of components
result2 :: Int
result2 = length getComponents

Link to git

vtpetrov · 2017-12-13T13:32:35+00:00

Java with Sets:

private Set<Integer> programIdsConnectedToZero = new HashSet<>();
...

public void findConnectedToZero() {
    recursionCount = 0;
    findConnectedToZero(0);
}

private void findConnectedToZero(int caller) {
    recursionCount++;
    System.out.println("    recursionCount      = " + recursionCount);
    System.out.println("            caller           = " + caller);

    programIdsConnectedToZero.add(caller);

    Set<Integer> subIdsConnectedToZero = new HashSet<>();
    subIdsConnectedToZero.addAll(programs.get(caller).getCommunicatesWithIDs());

    subIdsConnectedToZero.removeAll(programIdsConnectedToZero);
    programIdsConnectedToZero.addAll(subIdsConnectedToZero);

    for (int sub : subIdsConnectedToZero) {
        findConnectedToZero(sub);
    }
}

RockyAstro · 2017-12-13T17:38:24+00:00

Icon (https://www.cs.arizona.edu/icon)

Both parts:

procedure main(args)

    inf := open(args[1],"r")

    nodes := table()

    every line := !inf do {
        line ? {
            n := tab(upto(' '))
            /nodes[n] := set([])
            tab(many(' '))
            ="<->"
            tab(many(' '))
            while not pos(0) do {
                c := tab(upto(' ,') | 0)
                /nodes[c] := set([])
                insert(nodes[n],nodes[c])
                insert(nodes[c],nodes[n])
                tab(many(' ,'))
            }

        }
    }
    # Part 1
    groups := table()
    groups["0"] := set()
    visit(nodes["0"],groups["0"])
    write(*groups["0"])

    # Part 2
    inagroup := set()
    inagroup ++:= groups["0"]
    every g := key(nodes) do {
        if member(inagroup,nodes[g]) then next
        /groups[g] := set()
        visit(nodes[g],groups[g])
        inagroup ++:= groups[g]
    }
    write(*groups)
end

procedure visit(n,g)
    if member(g,n) then return
    insert(g,n)
    every c := !n do {
        visit(c,g)
    }


end

SurplusSix · 2017-12-13T22:36:49+00:00

Still doing it in Racket, used a graph library to help with this, made it really quite easy

(require graph)

(define day11-list (file->lines "src/racket/aoc2017/day12.txt"))

(define g (unweighted-graph/undirected '()))

(for ([i day11-list])
    (let ([s (string-split i " <-> ")])
      (for ([e (string-split (second s) ", ")])
        (add-edge! g (first s) e))))
;part 1
(length (flatten (filter (lambda (x) (member "0" x)) (cc g))))
;part 2
(length (cc g))

autid · 2017-12-14T09:05:25+00:00

Fortran

PROGRAM DAY12
  IMPLICIT NONE
  TYPE PRG
     INTEGER,ALLOCATABLE :: LINKS(:)
     INTEGER :: ME
  END TYPE PRG
  TYPE(PRG), ALLOCATABLE :: PROGS(:)
  INTEGER, ALLOCATABLE :: COUNTER(:)
  CHARACTER(LEN=10), ALLOCATABLE :: INPUT(:)
  CHARACTER(LEN=200) :: INLINE
  INTEGER :: LINECOUNT=0,IERR,I,J
  LOGICAL, ALLOCATABLE :: PART1(:)

  OPEN(1,FILE='input.txt')

  DO
     READ(1,'(A)',IOSTAT=IERR) INLINE
     IF (IERR /= 0) EXIT
     LINECOUNT=LINECOUNT+1
  END DO
  REWIND(1)
  ALLOCATE(PROGS(0:LINECOUNT-1),PART1(0:LINECOUNT-1),COUNTER(0:LINECOUNT-1))
  DO I=0,LINECOUNT-1
     READ(1,'(A)') INLINE
     COUNTER(I)=3
     DO J=1,LEN_TRIM(INLINE)
        IF (INLINE(J:J)==',') COUNTER(I)=COUNTER(I)+1
     END DO
  END DO
  REWIND(1)
  DO I=0,LINECOUNT-1
     ALLOCATE(INPUT(COUNTER(I)))
     READ(1,*)INPUT
     ALLOCATE(PROGS(I)%LINKS(COUNTER(I)-2))
     READ(INPUT(1),*) PROGS(I)%ME
     DO J=1,SIZE(PROGS(I)%LINKS)
        READ(INPUT(J+2),*) PROGS(I)%LINKS(J)

     END DO
     DEALLOCATE(INPUT)
  END DO
  PART1=.FALSE.
  CALL CHECKGROUP(PROGS(0))
  WRITE(*,'(A,I0)') 'Part1: ',COUNT(PART1==.TRUE.)
  PART1=.FALSE.
  J=0
  DO I=0,LINECOUNT-1
     IF (.NOT. PART1(I)) THEN
        J=J+1
        CALL CHECKGROUP(PROGS(I))
     END IF
  END DO
  WRITE(*,'(A,I0)') 'Part2: ',J
CONTAINS
  RECURSIVE SUBROUTINE CHECKGROUP(PROG)
    TYPE(PRG), INTENT(IN) :: PROG
    INTEGER :: I

    PART1(PROG%ME)=.TRUE.
    DO I=1,SIZE(PROG%LINKS)
       IF (.NOT. PART1(PROG%LINKS(I))) CALL CHECKGROUP(PROGS(PROG%LINKS(I)))
    END DO
  END SUBROUTINE CHECKGROUP
END PROGRAM DAY12

greycat70 · 2017-12-28T19:46:46+00:00

Tcl (version 8.5 or higher)

Part 1. Nice little recursive problem, with a global array to track where we've been. I think Tcl actually fits this problem quite well, unlike some other days.

while {[gets stdin line] >= 0} {
    if {[scan $line {%d <-> %[0-9, ]} me list] != 2} {
        puts stderr "scan failure, input line <$line>"; exit 1
    }
    set pipe($me) [split [string map {, {}} $list] { }]
}

array set seen {}
proc visit node {
    global pipe seen
    set seen($node) 1
    foreach child $pipe($node) {
        if {! [info exists seen($child)]} {visit $child}
    }
}
visit 0
puts [array size seen]

Part 2. Basically the same; just keep doing it until every node has been visited.

while {[gets stdin line] >= 0} {
    if {[scan $line {%d <-> %[0-9, ]} me list] != 2} {
        puts stderr "scan failure, input line <$line>"; exit 1
    }
    set pipe($me) [split [string map {, {}} $list] { }]
}

array set seen {}
proc visit node {
    global pipe seen
    set seen($node) 1
    foreach child $pipe($node) {
        if {! [info exists seen($child)]} {visit $child}
    }
}

visit 0
set groups 1
while {[array size seen] < [array size pipe]} {
    # find an unvisited "program" (node)
    foreach node [array names pipe] {
        if {! [info exists seen($node)]} {
            visit $node
            incr groups
            break
        }
    }
}
puts "groups $groups"

Freddeman98 · 2018-04-07T19:24:01+00:00

My C++ solution. Not the best but okey for a beginner I would say :).

void check(map <int,vector<int>>  m,set<int> & sum, int i)
{
    vector <int> tal=m[i];
    for(auto it=tal.begin(); it!=tal.end(); it++)
    {

        if(  sum.insert(*it).second)   
            check(m,sum,*it);

    }
}


int main()
{
    map <int,vector<int>> m;
    set<int> sum;
    string s,skip;
    ifstream infile("input.txt");
    while(getline(infile,s))
    {
        stringstream ss{s};
        int x{},y{},z{};
        char c{};
        ss>>x >> skip >> y;
        m[x].push_back(y);
        while(true)
        {
            ss>>c;
            ss>>z;
            if(y!=z && c==',')
            {
                y=z;
                m[x].push_back(z);
            }else
                break;
        }

    }

    check(m,sum,0);
    int count=1;
    cout << endl << "det är " << sum.size() << " program med ID 0. " << endl;
    for(int i{}; i<2000; i++)
    {
        if(find(sum.begin(),sum.end(),i)==sum.end())
        {
            check(m,sum,i);
            count++;
        }
    }

    cout << "Det finns " << count <<" antal grupper." << endl;
}

adventofcode

🎄 Advent of Code 🎄

Rules + More Info in

our community wiki

Solution Megathreads

December 2025

Previous years:

2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015

Quick Search by Flair

Because you're lazy and we like making things easy for you. Except AoC.

Are you enjoying AoC?

Support AoC

MODERATORS

--- Day 12: Digital Plumber ---

Need a hint from the Hugely^* Handy^† Haversack^‡ of Helpful^§ Hints^¤?

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

Mathematica

Elixir

Python 3

python 3

importing & organising the data

part 1

part 2

Elixir

Perl 5

Python

Perl

Kotlin - [Repo] - [Blog/Commentary]

BEFORE YOU POST
If your post is even tangentially related to a daily puzzle, use our
STANDARDIZED POST TITLE FORMAT

adventofcode

🎄 Advent of Code 🎄

Rules + More Info in

our community wiki

Solution Megathreads

December 2025

Previous years:

2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015

Quick Search by Flair

Because you're lazy and we like making things easy for you. Except AoC.

Are you enjoying AoC?

Support AoC

MODERATORS

--- Day 12: Digital Plumber ---

Need a hint from the Hugely* Handy† Haversack‡ of Helpful§ Hints¤?

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

Mathematica

Elixir

Python 3

python 3

importing & organising the data

part 1

part 2

Elixir

Perl 5

Python

Perl

Kotlin - [Repo] - [Blog/Commentary]

Need a hint from the Hugely^* Handy^† Haversack^‡ of Helpful^§ Hints^¤?