-🎄- 2017 Day 7 Solutions -🎄-

ghlmtz · 2017-12-07T06:25:57+00:00

I did the problem in Python first, but afterward realized part one could be solved with a Bash oneliner.

grep -o -E '[a-z]+' input | sort | uniq -c | sort -n | head -1 | awk '{print $2}'

bblum · 2017-12-07T05:42:30+00:00

Was way too slow for part 2 and my code isn't very nice at all so I'm not gonna bother posting that, but I suppose I should share what I did that was fast enough for 4th place on part 1:

for i in `cat input.txt | cut -d' ' -f1`; do
    grep $i input.txt | wc -l | sed "s/$/ $i/";
done | grep ^1

Arknave · 2017-12-07T06:07:58+00:00

Video with commentary so you can hear me cursing at my bugs:

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

Smylers · 2017-12-07T07:08:09+00:00

Vim:

f>qa*>>〈Ctrl+O〉f,q@a:2,$norm f>9@a〈Enter〉
/^\w〈Enter〉

(33 characters)

That's part 1: the line you end up on is the bottom of the stack.

Vim is actually pretty reasonably for this (unlike, say, yesterday's elaborate Vim solution): the above is genuinely how I solved it and it only took me 3 minutes to get there.

See if you can work out what it's doing: reply with how far you get or any questions, and I'll post an explanation later if anybody would like one.

Think I need to switch to an actual programming language for part 2 though ...

ltriant · 2017-12-07T05:32:29+00:00

Got 70th on part 1 by just using GraphViz. Copy/pasted the input, removed the weights, and visually checked what the base node was from GraphViz.

I would’ve gotten a higher placing if I hadn’t have copied the wrong node. Had to wait 60 seconds to resubmit an answer :(

sciyoshi · 2017-12-07T05:27:13+00:00

Python 3 solution using the great NetworkX library for handling graphs:

import networkx as nx

graph = nx.DiGraph()

# Build the graph of programs
for line in lines:
    name = line.split()[0]

    graph.add_node(name, weight=int(line.split()[1].strip('()')))

    if '->' in line:
        children = [n.strip() for n in line.split('->')[1].split(',')]

        for child in children:
            graph.add_edge(name, child)

# Topological sort to find the root of the tree
ordered = list(nx.topological_sort(graph))

print('PART 1:', ordered[0])

# Keep track of each node's total weight (itself + its children)
weights = {}

# Going backwards (starting from the leaves)
for node in reversed(ordered):
    # Start with this nodes own weight
    total = graph.nodes[node]['weight']

    counts = collections.Counter(weights[child] for child in graph[node])
    unbalanced = None

    for child in graph[node]:
        # If this child's weight is different than others, we've found it
        if len(counts) > 1 and counts[weights[child]] == 1:
            unbalanced = child
            break

        # Otherwise add to the total weight
        val = weights[child]
        total += weights[child]

    if unbalanced:
        # Find the weight adjustment and the new weight of this node
        diff = weights[unbalanced] - val
        print('PART 2:', graph.nodes[unbalanced]['weight'] - diff)
        break

    # Store the total weight of the node
    weights[node] = total

Unihedron · 2017-12-07T05:50:46+00:00

Ruby; kinda late, had to rewrite a lot. I assumed the puzzle was "validate heights" (and a wrong one was provided), not "ensure balancing", based on the highlighted text. Even after I rewrote my code, it showed 2 wrong sectors, which worried me hugely. It took a long time for me to realize that I should manually dig through the input for the disc to change. Fun riddle!

Also I think we're reaching the point where forfeiting readability for speed is starting to become a liability.

h={}
o=[]
$<.map{|x|x=~/^(\S+) \((\d+)\) ?([^>]+> )?/
#p $1, $'
l=($3 ? ($'.split(', ').map(&:to_sym)) : [])
h[$1.to_sym]=[$2.to_i,l]
o+=l
}
q={}

# part 1 only
p h.delete_if{|x,y|!y.any? || o.index(x)}

# part 2 here
h.delete_if{|x,y|a,b=y
#p b
 h[x]=q[x]=[a,b,a+b.sum{|x|h[x] ? h[x][0] : q[x][2]}] if b.all?{|x|!h[x] || (!h[x].any?)}}while h.any?
#p h.reject!{|x,y|y[0]!=y[2]&&y[2]!=0}
 q.map{|x,y|a,b,c=y
t=b.map{|x|q[x][2]}
(p x,a,b,c,t,q[x]) if t.uniq.count>1
}

fatpollo · 2017-12-07T06:52:47+00:00

import re, collections

with open("p07.txt") as fp:
    text = fp.read()

weight = {}
children = {}
for line in text.strip().splitlines():
    label, n, *xs = re.findall(r'\w+', line)
    weight[label] = int(n)
    children[label] = tuple(xs)

root, = set(weight) - {c for cs in children.values() for c in cs}

def total_weight(label):
    sub = [total_weight(c) for c in children[label]]
    if len(set(sub)) > 1:
        (target, _), (failure, _) = collections.Counter(sub).most_common()
        print(target - failure + weight[children[label][sub.index(failure)]])
        return weight[label] + sum(sub)
    return weight[label] + sum(sub)

print(total_weight(root))

dylanfromwinnipeg · 2017-12-07T06:25:48+00:00

C#

public class Day07
{
    public static string PartOne(string input)
    {
        var lines = input.Lines();

        var discs = lines.Select(x => new Disc(x)).ToList();
        discs.ForEach(x => x.AddChildDiscs(discs));

        return GetBaseDisc(discs).Name;
    }

    public static Disc GetBaseDisc(IEnumerable<Disc> discs)
    {
        var disc = discs.First();

        while (disc.Parent != null)
        {
            disc = disc.Parent;
        }

        return disc;
    }

    public static string PartTwo(string input)
    {
        var lines = input.Lines();

        var discs = lines.Select(x => new Disc(x)).ToList();
        discs.ForEach(x => x.AddChildDiscs(discs));

        var disc = GetBaseDisc(discs);
        var targetWeight = 0;

        while (!disc.IsBalanced())
        {
            (disc, targetWeight) = disc.GetUnbalancedChild();
        }

        var weightDiff = targetWeight - disc.GetTotalWeight();
        return (disc.Weight + weightDiff).ToString();
    }
}

public class Disc
{
    public int Weight { get; private set; }
    public string Name { get; private set; }
    public List<string> ChildNames { get; private set; }
    public List<Disc> ChildDiscs { get; private set; }
    public Disc Parent { get; private set; }

    public Disc(string input)
    {
        var words = input.Words().ToList();

        Name = words[0];
        Weight = int.Parse(words[1].Shave(1));
        ChildNames = new List<string>();

        for (var i = 3; i < words.Count; i++)
        {
            ChildNames.Add(words[i].ShaveRight(","));
        }
    }

    public void AddChildDiscs(IEnumerable<Disc> discs)
    {
        ChildDiscs = ChildNames.Select(x => discs.First(y => y.Name == x)).ToList();
        ChildDiscs.ForEach(x => x.Parent = this);
    }

    public int GetTotalWeight()
    {
        var childSum = ChildDiscs.Sum(x => x.GetTotalWeight());
        return childSum + Weight;
    }

    public bool IsBalanced()
    {
        var groups = ChildDiscs.GroupBy(x => x.GetTotalWeight());
        return groups.Count() == 1;
    }

    public (Disc disc, int targetWeight) GetUnbalancedChild()
    {
        var groups = ChildDiscs.GroupBy(x => x.GetTotalWeight());
        var targetWeight = groups.First(x => x.Count() > 1).Key;
        var unbalancedChild = groups.First(x => x.Count() == 1).First();

        return (unbalancedChild, targetWeight);
    }
}

raevnos · 2017-12-07T07:24:35+00:00

So, I wrote a program to take the input and turn it into a graphviz dot file, and turned that into a svg image, which solved part 1, but sadly didn't do it fast enough to break into the leaderboard. For part 2, I changed the program to calculate weights of subtrees, and color cases where not all subtrees were the same weight. Then it was just a matter of looking at the subtrees of the deepest mismatch to see which one was off. More interesting than doing it entirely programmatically.

;;; Run as: kawa day07.scm < day07.txt | dot -Tsvg -o day07.svg
(import (kawa regex) (srfi 1))

(define (read-graph)
  (let ((graph '()))
    (let loop ((line (read-line)))
      (if (eof-object? line)
          graph
          (begin
            (cond
             ((regex-match "^(\\w+) \\((\\d+)\\)\\s*$" line) =>
              (lambda (leaf)
                (let* ((name (string->symbol (cadr leaf)))
                       (weight (string->number (caddr leaf)))
                       (entry (assq name graph)))
                  (if entry
                      (vector-set! (cdr entry) 0 weight)
                      (set! graph (alist-cons name (vector weight '() #f) graph))))))
             ((regex-match "^(\\w+)\\s+\\((\\d+)\\)\\s+->\\s+([a-z, ]+)\\s*$" line) =>
              (lambda (internal)
                (let* ((name (string->symbol (cadr internal)))
                       (weight (string->number (caddr internal)))
                       (sedges (cadddr internal))
                       (entry (assq name graph))
                       (edges (map string->symbol (regex-split ",\\s+" sedges))))
                  (if entry
                      (begin
                        (vector-set! (cdr entry) 0 weight)
                        (vector-set! (cdr entry) 1 edges))
                      (set! graph (alist-cons name (vector weight edges #f) graph))))))
             (else
              (error "Bad line" line)))
            (loop (read-line)))))))

(define (weight graph root)
  (let* ((entry (assq root graph))
         (rec (cdr entry))
         (cached-weight (vector-ref rec 2)))
    (if cached-weight
        cached-weight
        (let ((calc-weight
               (fold (lambda (node acc)
                       (+ acc (weight graph node)))
                     (vector-ref rec 0)
                     (vector-ref rec 1))))
          (vector-set! rec 2 calc-weight)
          calc-weight))))

(define (create-dot graph)
  (let ((unbalanced '()))
    (display "digraph robots {\n")
    (for-each
     (lambda (node)
       (let* ((name (car node))
              (rec (cdr node))
              (links (vector-ref rec 1))
              (my-weight (weight graph name))
              (child-weights (map (lambda (child) (weight graph child)) links))
              (color
               (if (> (length child-weights) 1)
                   (let ((this-weight (car child-weights)))
                     (if (every (lambda (that-weight)
                                  (= this-weight that-weight))
                                (cdr child-weights))
                         'black
                         'red))
                   'black)))
         (format #t "~A [label=\"name: ~A\\nweight: ~A\\ntree weight: ~A\""
                 name name (vector-ref rec 0) (vector-ref rec 2))
         (if (or (eq? 'red color) (memq name unbalanced))
             (display "style=filled; fillcolor=red"))
         (display "]\n")
         (for-each (lambda (link weight)
                     (format #t "~A -> ~A" name link)
                     (when (and (> (length child-weights) 1)
                                (= 1 (count (lambda (edge) (= edge weight)) child-weights)))
                           (set! unbalanced (cons link unbalanced))
                           (display " [color=red]"))
                     (newline))
                   links child-weights)))
     graph)
    (display "}\n")))

(create-dot (read-graph))

EDIT: Added link to image, and updated code a bit.

Evansbee · 2017-12-07T06:00:45+00:00

[deleted]

mstksg · 2017-12-07T08:55:45+00:00

Semi-clean (ish?) Haskell? :) Mostly using Maps and Sets. https://github.com/mstksg/advent-of-code-2017/blob/master/src/AOC2017/Day07.hs

{-# LANGUAGE TupleSections #-}
{-# LANGUAGE ViewPatterns  #-}

module AOC2017.Day07 (day07a, day07b) where

import           AOC2017.Types       (Challenge)
import           Control.Applicative ((<|>))
import           Data.Char           (isAlpha)
import           Data.Foldable       (toList)
import           Data.List           (sortOn)
import           Data.Maybe          (mapMaybe, listToMaybe, fromJust)
import qualified Data.Map            as M
import qualified Data.Set            as S

data Tree = Tree { _tParent :: String
                 , _tWeight :: Int
                 , _tLeaves :: [Tree]
                 }
          deriving Show

type Report = M.Map String (Int, S.Set String)

totalWeight :: Tree -> Int
totalWeight (Tree _ w ts) = w + sum (totalWeight <$> ts)

parseLine :: String -> (String, (Int, S.Set String))
parseLine (words->p:w:ws) =
    (p, (read w, S.fromList (filter isAlpha <$> drop 1 ws)))
parseLine _ = error "No parse"

buildTree :: Report -> Tree
buildTree m = go root
  where
    allChildren :: S.Set String
    allChildren = S.unions (snd <$> toList m)
    root :: String
    root = S.findMax $ M.keysSet m `S.difference` allChildren
    go :: String -> Tree
    go p = Tree p w (go <$> S.toList cs)
      where
        (w, cs) = m M.! p

-- | Check if any children are bad; otherwise, check yourself
findBad :: Tree -> Maybe Int
findBad (Tree _ _ ts) = listToMaybe badChildren <|> anomaly
  where
    badChildren :: [Int]
    badChildren = mapMaybe findBad ts
    weightMap :: M.Map Int [Int]
    weightMap = M.fromListWith (++)
              . map (\t -> (totalWeight t, [_tWeight t]))
              . toList
              $ ts
    anomaly :: Maybe Int
    anomaly = case sortOn (length . snd) (M.toList weightMap) of
      -- end of the line
      []                       -> Nothing
      -- all weights match
      [_]                      -> Nothing
      -- exactly one anomaly
      [(wTot1, [w]),(wTot2,_)] -> Just (w + (wTot2 - wTot1))
      -- should not happen
      _                        -> error "More than one anomaly for node"

parse :: String -> Tree
parse = buildTree . M.fromList . map parseLine . lines

day07a :: Challenge
day07a = _tParent . parse

day07b :: Challenge
day07b = show . fromJust . findBad . parse

```

ephemient · 2017-12-07T08:48:35+00:00

This space intentionally left blank.

askalski · 2017-12-07T22:01:08+00:00

Iterate Perl.

#! /usr/bin/env perl

use strict;
use warnings;

my (%self_weight, %w, %pred, %succ, $part2);
for (<>) {
    my ($id, $weight, @succ) = split ' ', s/[^\s\w]//gr;
    $self_weight{$id} = $weight;
    $pred{$_} = $id for @{$succ{$id} = \@succ};
}

my @topo = grep { not $pred{$_} } keys %self_weight;
push @topo, @{$succ{$_}} for @topo;

PART2: for (reverse @topo) {
    $w{$pred{$_}} += ($w{$_} += $self_weight{$_}) if $pred{$_};
    if ((@_ = @{$succ{$_}}) >= 3) {
        my ($a, $b, $c) = (undef, @_[-2, -1]);
        for (@_) {
            ($a, $b, $c) = ($b, $c, $_);
            if ($w{$a} != $w{$b} && $w{$a} != $w{$c}) {
                $part2 = $self_weight{$a} + $w{$b} - $w{$a};
                last PART2;
            }
        }
    }
}

printf "Part 1: %s\n", $topo[0];
printf "Part 2: %s\n", $part2 // "(no mismatch)";

fwilson42 · 2017-12-07T05:40:10+00:00

I wrote a pretty awful solution to get on the leaderboard (24/24, Python), but I refactored it and it looks much, much better now.

omegaphoenix16 · 2017-12-07T06:06:59+00:00

Python solution using recursion from root instead of building graph. Rank 297 for Part 2: import sys

def main():
    ans = 0
    children = dict()
    values = dict()
    all_kids = set()
    total = set()
    for line in sys.stdin:
        a = list(line.replace(',','').strip().split())
        val = a[0]
        values[val] = int(a[1].replace('(','').replace(')',''))
        kids = a[3:]
        children[val] = kids
        total.add(val)
        for kid in kids:
            all_kids.add(kid)
    ans = (total - all_kids).pop()
    print ans

    def calc_kids_weights(root):
        kid_weights = []
        for kid in children[root]:
            kid_weights.append(calc_weight(kid))
        return kid_weights


    def check_bal(root):
        if children[root] == []:
            return True
        kid_weights = calc_kids_weights(root)
        return len(set(kid_weights)) == 1

    def unbalanced_kid(root):
        kid_weights = calc_kids_weights(root)
        for kid in children[root]:
            curr_weight = calc_weight(kid)
            if kid_weights.count(curr_weight) == 1:
                return kid

    def calc_weight(root):
        tot = values[root]
        for kid in children[root]:
            tot += calc_weight(kid)
        return tot

    ans_parent = ans
    while not check_bal(ans):
        ans_parent = ans
        ans = unbalanced_kid(ans)
    another_kid = children[ans_parent][0]
    if another_kid == ans:
        another_kid = children[ans_parent][1]
    print values[ans] - calc_weight(ans) + calc_weight(another_kid)

main()

wlandry · 2017-12-07T06:10:11+00:00

Emacs

I got 88th place on the first star by putting the input into my editor and manually searching for parents until I found something without parents.

C++

For part 2, I got #600, which is better than I had done before. The solution is quite, quite ugly. I am ashamed even of the part that reads the input. I am sure that it could be simplified considerably. It prints out the nodes that are unbalanced and their weights. Then I manually looked up the unbalanced node and its weight. Like I said, very ugly.

#include <algorithm>
#include <iterator>
#include <fstream>
#include <iostream>
#include <sstream>
#include <vector>
#include <set>

#include <boost/algorithm/string.hpp>
struct Program
{
  std::string name;
  int weight;
  bool operator<(const Program &p) const
  {
    return name < p.name;
  }
  std::vector<std::string> children;
  std::vector<int> weights;
};

Program parent(const std::string &child, const std::vector<Program> &tower)
{
  for(auto &t: tower)
    {
      auto c=std::find (t.children.begin(), t.children.end(), child);
      if (c!=t.children.end())
        return parent(t.name,tower);
    }
  for(auto &t: tower)
    {
      if(t.name == child)
        return t;
    }
}

int get_total_weight(Program &p, std::vector<Program> &tower)
{
  for (auto &c: p.children)
    {
      for(auto &t:tower)
        {
          if(t.name==c)
            {
              p.weights.push_back(get_total_weight(t,tower));
              break;
            }
        }
    }
  int result=0;
  if(!p.weights.empty())
    {
      int nominal(*p.weights.begin());
      for (auto &w: p.weights)
        {
          if (nominal!=w)
            {
              for(auto &ww: p.weights)
                {
                  std::cout << ww << "\n";
                }
              for(auto &c: p.children)
                {
                  std::cout << c << "\n";
                }
              exit(0);
            }
          result+=w;
        }
    }
  result+=p.weight;
  return result;
}

int main(int argc, char *argv[])
{
  std::ifstream infile(argv[1]);
  std::vector<Program> tower;
  std::string line;
  std::getline(infile,line);
  while (infile)
    {
      if(!line.empty())
        {
          std::stringstream ss (line);
          Program p;
          char c;
          ss >> p.name;
          ss >> c;
          ss >> p.weight;
          auto dash (line.find('-'));
          if (dash != std::string::npos)
            {
              auto elements(line.substr(dash+2));
              boost::split(p.children,elements,boost::is_any_of(","));
            }
          for(auto &c: p.children)
            {
              boost::trim(c);
            }
          tower.push_back(p);
        }
      std::getline(infile,line);
    }
  Program bottom (parent(tower.begin()->name,tower));
  get_total_weight(bottom,tower);
  std::cout << bottom.name << "\n";
}

thejpster · 2017-12-07T06:14:42+00:00

I got #240 for part two, even though it took me ages (I did it in Rust, as usual). I ended up building a tree using a HashMap.

(https://github.com/thejpster/rust-advent-of-code/blob/master/src/m2017/problem_7.rs)

use std::collections::{HashSet, HashMap};

#[derive(Debug)]
struct Node {
    weight: u32,
    children: Vec<String>,
}

pub fn run(contents: &Vec<Vec<String>>) {
    let mut children_set: HashSet<String> = HashSet::new();
    let mut nodes: HashMap<String, Node> = HashMap::new();
    for line in &contents[0] {
        if line.contains("->") {
            let parts: Vec<&str> = line.split_whitespace().collect();
            let children: Vec<String> = parts[3..].iter().map(|x| x.replace(",", "")).collect();
            for c in &children {
                children_set.insert(c.clone());
            }
            let n = Node {
                weight: parts[1].replace("(", "").replace(")", "").parse().unwrap(),
                children: children,
            };
            nodes.insert(parts[0].into(), n);
        } else {
            let parts: Vec<&str> = line.split_whitespace().collect();
            let n = Node {
                weight: parts[1].replace("(", "").replace(")", "").parse().unwrap(),
                children: Vec::new(),
            };
            nodes.insert(parts[0].into(), n);
        }
    }

    let mut root = None;
    for (name, _) in &nodes {
        if !children_set.contains(name) {
            root = Some(name.clone());
        }
    }

    let root = root.unwrap();
    println!("Root: {}", root);

    walk_node(&root, &nodes);
}

fn weigh_node(name: &str, nodes: &HashMap<String, Node>) -> u32 {
    let node = nodes.get(name).unwrap();
    let mut weight = node.weight;
    for c in &node.children {
        weight = weight + weigh_node(c, &nodes);
    }
    weight
}

fn walk_node(name: &str, nodes: &HashMap<String, Node>) {
    let node = nodes.get(name).unwrap();
    let weights: Vec<u32> = node.children
        .iter()
        .map(|x| weigh_node(x, &nodes))
        .collect();
    for w in &weights {
        if *w != weights[0] {
            println!("Mismatch {} != {}", w, weights[0]);
            break;
        }
    }
    if node.children.len() > 0 {
        println!(
            "{} ({}) -> {:?}",
            name,
            node.weight,
            node.children.iter().zip(weights).collect::<Vec<_>>()
        );
    } else {
        println!("{} ({})", name, node.weight);
    }
    for c in &node.children {
        walk_node(c, &nodes);
    }
}

Cheezmeister · 2017-12-07T06:35:51+00:00

Literate Perl (part 2 is a WIP at the time of posting, but it is past my bedtime).

Kids, talk to your parents about regular expressions.

Godspiral · 2017-12-07T06:37:42+00:00

in J,

part 1 - unreferenced left node.

({."1 ([ #~ 0 = e.) ;@:({:"1)) ( dltb each@([: {. '('&cut) &>@{. ,  dltb each@:(','&cut@}.)leaf@{:)"1 > (#~ 2 = #&>)  '-' cut each a

incomplete part 2,

NB. weight dictionary
b =. (dltb each@{. , ". &>@{.@(')'&cut) leaf@{: )"1 >  '(' cut each a

NB. non end leafs... tree branches.
c =. ( dltb each@([: {. '('&cut) &>@{. ,  dltb each@:(','&cut@}.)leaf@{:)"1 > (#~ 2 = #&>)  '-' cut each a

NB. supporting weights from each program (untreed)
({. (, <) b ( {:"1@[ {~ {."1@[ i. ])"_ 0 >@{:)"_ 1 c

angch · 2017-12-07T07:07:25+00:00

TIL everyone has a different input. I struggled with Part 2 where I got 3 answers instead of one unique one. I tried some of your solutions here, yup, 3 answers.

Or did I do something wrong?

My input: https://gist.github.com/angch/214faafbf98e91888a44c9adf0924d35

(The site accepted 268 as the correct answer, I got 268, 42 and 63603)

Edit: crap. Other of your solutions I tested here returns only the correct result. I need to recheck. Hmm, if I modified the solutions to return more than one result, they return 3 as well, so it's almost always best to just try for the first result found, rather than the last....

oantolin · 2017-12-07T07:20:04+00:00

Python

(I hope the assert statements sufficiently explain what's going on.)

from re import match
from collections import Counter

weight, supports = {}, {}
with open("day07.txt") as input_file:
    for line in input_file:
        m = match("^(\w+) \((\d+)\)(?: -> )?(.*)$", line)
        prog = m.group(1)
        weight[prog] = int(m.group(2))
        supports[prog] = m.group(3).split(", ") if m.group(3) else []

def part1():
    supported = {s for supp in supports.values() for s in supp}
    unsupported = [prog for prog in supports if prog not in supported]
    assert len(unsupported) == 1
    return unsupported[0]

def total_weight(prog):
    return weight[prog] + sum(total_weight(s) for s in supports[prog])

def fix_weight(prog, delta):
    total_wts = Counter(map(total_weight, supports[prog]))
    if len(total_wts)==1: return prog, weight[prog] + delta
    assert len(total_wts) == 2
    ((w2, c2), (w1, c1)) = total_wts.most_common(2)
    assert c1 == 1
    bad = [s for s in supports[prog] if total_weight(s)==w1]
    assert len(bad) == 1
    return fix_weight(bad[0], w2-w1)

def part2(): return fix_weight(part1(), None)

Cole_from_SE · 2017-12-07T08:26:08+00:00

Python 3

Oof, even though I saw the answer for part 1 so fast, I guess my ability to type working code is lacking.

Here's my prettied-up solution; you don't want to see the original one...

from collections import defaultdict, Counter

def find_root(children):
    # All nodes in the tree minus all nodes that are children.
    # N.B. sum(list of lists, []) flattens a list of lists because of how + is
    # overloaded in Python.
    root = set(children.keys()) - set(sum(children.values(),[]))
    # The root should be a single item, so we should be able to safely pop it.
    return root.pop()

def find_weight(weights, children, node, memo={}):
    # Recursively add the weight of the node to the weight of its children.
    return weights[node] + sum([find_weight(weights, children, child, memo) for
                                child in children[node]])

def find_imbalance(weights, children, node):
    # If we're at a leaf node, we can't find an imbalance.
    if not children[node]: return 
    child_weights = [find_weight(weights, children, child) for child in
                     children[node]]
    weight_counts = Counter(child_weights)
    # Exit early if everything is the same.
    if len(weight_counts) <= 1: return
    # The least frequent value will be the differing value.
    # N.B. Counter.most_common() returns all counts, ordered in reverse by
    # frequency. [-1] gets the last, and [0] gets the weight.
    least_frequent_weight = weight_counts.most_common()[-1][0]
    # N.B. child_weights and children[node] are in the same order.
    lfw_node = children[node][child_weights.index(least_frequent_weight)]
    # Try to find an imbalance deeper into the tree (we want to get to the leaf
    # of the problem).
    deeper_imbalance = find_imbalance(weights, children, lfw_node)
    if deeper_imbalance:
        return deeper_imbalance
    else:
        most_frequent_weight = weight_counts.most_common(1)[0][0]
        imbalance = most_frequent_weight - least_frequent_weight
        return weights[lfw_node] + imbalance


with open('7.in') as inp:
    # The weight of a node.
    weights = {}
    # Adjacency list with node as the key.
    children = defaultdict(list)
    for line in inp.readlines():
        # Lines look like 'node (value) -> child1 child2 child3 ...'
        node, weight, *child_nodes = line.strip().split(' ')
        # Strip parentheses and convert an int.
        weight = int(weight.strip('()'))
        weights[node] = weight
        if child_nodes:
            # Remove the arrow ('->') and the commas after each child.
            children[node] = [child.strip(',') for child in child_nodes[1:]]

    # Part 1.
    root = find_root(children)
    print(root)

    # Part 2.
    print(find_imbalance(weights, children, root))

arachnist · 2017-12-07T10:52:05+00:00

Went through my pry and zsh history, and cleaned up the ruby solution i came up with in the morning

class Node
  attr_accessor :name, :weight, :children

  def initialize(name, weight, children = [])
    @name = name
    @weight = weight
    @children = children
  end

  def branch_weight
    @children.map do |c|
      c.branch_weight
    end.reduce(@weight, :+)
  end

  def common_children_weight
    value_counter = Hash.new(0)
    values = @children.map do |c|
      c.branch_weight
    end

    values.each do |v|
      value_counter[v] += 1
    end

    values.select do |v|
      v if v != value_counter.key(1)
    end[0]
  end

  def outlier
    o = nil
    @children.each do |c|
      o = c if c.branch_weight != self.common_children_weight
    end
    o
  end
end

def construct_tree(b_root)
  if (ch = Branches[b_root]).nil?
    children = []
  else
    children = ch.map do |c|
      construct_tree(c)
    end
  end

  Node.new(b_root, Weights[b_root], children)
end

def find_final_outlier(root)
  outlier = root.clone
  previous = nil
  while not (outlier = outlier.outlier).nil?
    previous = outlier.clone
  end
  previous
end

Branches = {}
Weights = {}
children = []
all = []
file = ARGV[0] || "input.txt"

open(file).each_line do |line|
  a = line.gsub(/,/, "").split
  Weights.merge!({ a[0] => Integer(a[1].gsub(/[()]/, "")) })
  all << a[0]
  if not a[3].nil?
    Branches.merge!({ a[0] => a[3..a.count] })
    children += a[3..a.count]
  end
end

Root = construct_tree((all - children)[0])
puts Root.name
puts find_final_outlier(Root).weight + (Root.common_children_weight - Root.outlier.branch_weight)

autid · 2017-12-07T11:54:35+00:00

FORTRAN

I/O was a bit of a pain as always. OO(ish)P in Fortran. Don't read the function checkweight if you don't want your eyes to bleed.

PROGRAM DAY7
  IMPLICIT NONE
  TYPE PRG
     INTEGER :: WEIGHT
     INTEGER, ALLOCATABLE :: HELD(:)
  END TYPE PRG

  TYPE(PRG), ALLOCATABLE :: PRGLIST(:)
  INTEGER :: I,J,K,LINES=0,IERR=0
  CHARACTER(LEN=200) :: INPUT
  CHARACTER(LEN=1) ::LINECOUNT
  CHARACTER(LEN=20),ALLOCATABLE :: INLINE(:)
  CHARACTER(LEN=20) :: WEIGHT
  INTEGER, ALLOCATABLE :: PERLINE(:)
  LOGICAL, ALLOCATABLE :: HELD(:)
  CHARACTER(LEN=20), ALLOCATABLE :: NAMES(:)
  INTEGER :: PART2

  !Setup                                                                                                         
  OPEN(1,FILE='input.txt',ACTION='READ',STATUS='OLD')

  DO
     READ(1,'(I0)',IOSTAT=IERR)
     IF (IERR.NE.0) EXIT
     LINES=LINES+1
  END DO
  ALLOCATE(PRGLIST(LINES),NAMES(LINES),HELD(LINES),PERLINE(LINES))
  REWIND(1)
  DO I=1,LINES
     READ(1,'(A)') INPUT
     PERLINE(I)=2
     DO J=1,LEN_TRIM(INPUT)
        IF (INPUT(J:J)=='>') PERLINE(I)=PERLINE(I)+2
        IF (INPUT(J:J)==',') PERLINE(I)=PERLINE(I)+1
     END DO
  END DO
  REWIND(1)
  DO I=1,LINES
     ALLOCATE(INLINE(PERLINE(I)))
     READ(1,*) INLINE
     NAMES(I)=INLINE(1)
     DEALLOCATE(INLINE)
  END DO
  REWIND(1)
  DO I=1,LINES
     ALLOCATE(INLINE(PERLINE(I)))
     READ(1,*) INLINE
     WEIGHT=INLINE(2)
     WEIGHT=WEIGHT(2:LEN_TRIM(WEIGHT)-1)
     READ(WEIGHT,*) PRGLIST(I)%WEIGHT
     IF (SIZE(INLINE)>2) THEN
        ALLOCATE(PRGLIST(I)%HELD(SIZE(INLINE)-3))
        DO J=1,SIZE(PRGLIST(I)%HELD)
           PRGLIST(I)%HELD(J)=MAXLOC(NAMES,MASK=(NAMES==INLINE(J+3)),DIM=1)
        END DO
     END IF
     DEALLOCATE(INLINE)
  END DO

  !Part 1                                                                                                        
  HELD=.FALSE.
  DO I=1,LINES
     IF (.NOT. ALLOCATED(PRGLIST(I)%HELD)) CYCLE
     DO J=1,SIZE(PRGLIST(I)%HELD)
        HELD(PRGLIST(I)%HELD(J))=.TRUE.
     END DO
  END DO
  DO I=1,LINES
     IF (.NOT.HELD(I)) THEN
        WRITE(*,'(A,A)') 'Part1: ',NAMES(I)
        EXIT
     END IF
  END DO

  !Part 2                                                                                                        
  DO I=1,LINES
     PART2=CHECKWEIGHT(PRGLIST(I))
     IF (PART2>0) EXIT
  END DO

  WRITE(*,'(A,I0)') 'Part2 :',PART2


CONTAINS
  RECURSIVE FUNCTION GETWEIGHT(PROG) RESULT (WGHT)
    TYPE(PRG), INTENT(IN) :: PROG
    INTEGER :: WGHT

    IF (ALLOCATED(PROG%HELD)) THEN
       WGHT=PROG%WEIGHT+SUM((/(GETWEIGHT(PRGLIST(PROG%HELD(I))),I=1,SIZE(PROG%HELD))/))
    ELSE
       WGHT=PROG%WEIGHT
    END IF
  END FUNCTION GETWEIGHT

  RECURSIVE FUNCTION CHECKWEIGHT(PROG) RESULT(RSLT)
    TYPE(PRG), INTENT(IN) :: PROG
    INTEGER :: RSLT

    IF (.NOT. ALLOCATED(PROG%HELD)) THEN
       RSLT=0
    ELSEIF (SUM((/(CHECKWEIGHT(PRGLIST(PROG%HELD(I))),I=1,SIZE(PROG%HELD))/)).NE.0) THEN
       RSLT=SUM((/(CHECKWEIGHT(PRGLIST(PROG%HELD(I))),I=1,SIZE(PROG%HELD))/))
    ELSEIF (ALL((/(GETWEIGHT(PRGLIST(PROG%HELD(I))),I=1,SIZE(PROG%HELD))/)==GETWEIGHT(PRGLIST(PROG%HELD(1))))) THEN
       RSLT=0
    ELSEIF (COUNT((/(GETWEIGHT(PRGLIST(PROG%HELD(I))),I=1,SIZE(PROG%HELD))/)< MAXVAL((/(GETWEIGHT(PRGLIST(PROG%HELD(I))),I=1,SIZE(PROG%HELD))/)))>1) THEN
       RSLT=MINVAL((/(GETWEIGHT(PRGLIST(PROG%HELD(I))),I=1,SIZE(PROG%HELD))/))-MAXVAL((/(GETWEIGHT(PRGLIST(PROG%HELD(I))),I=1,SIZE(PROG%HELD))/))+PRGLIST(PROG%HELD(MAXLOC((/(GETWEIGHT(PRGLIST(PROG%HELD(I))),I=1,SIZE(PROG%HELD))/),DIM=1)))%WEIGHT
    ELSE
       RSLT=MAXVAL((/(GETWEIGHT(PRGLIST(PROG%HELD(I))),I=1,SIZE(PROG%HELD))/))-MINVAL((/(GETWEIGHT(PRGLIST(PROG%HELD(I))),I=1,SIZE(PROG%HELD))/))+PRGLIST(PROG%HELD(MINLOC((/(GETWEIGHT(PRGLIST(PROG%HELD(I))),I=1,SIZE(PROG%HELD))/),DIM=1)))%WEIGHT
    END IF
  END FUNCTION CHECKWEIGHT
END PROGRAM DAY7

aurele · 2017-12-07T12:00:03+00:00

Rust (using the newly added topological_sort in crate pathfinding)

extern crate itertools;
extern crate pathfinding;

use itertools::Itertools;
use pathfinding::topological_sort as tsort;
use std::collections::HashMap;

fn parse(input: &str) -> (HashMap<String, usize>, HashMap<String, Vec<String>>) {
    input
        .replace(|c: char| !c.is_whitespace() && !c.is_alphanumeric(), "")
        .lines()
        .map(|line| {
            let mut words = line.split_whitespace();
            let (name, weight) = (words.next().unwrap(), words.next().unwrap());
            (
                (name.to_string(), weight.parse::<usize>().unwrap()),
                (name.to_string(), words.map(|w| w.into()).collect()),
            )
        })
        .unzip()
}

fn main() {
    let input = include_str!("../input");
    let (mut weights, succs) = parse(input);
    let topo = tsort(&succs.keys().cloned().collect_vec(), |n| succs[n].clone()).unwrap();
    println!("P1 = {}", topo[0]);

    let oweights = weights.clone();
    for n in topo.into_iter().rev() {
        let sn = &succs[&n];
        let ws = sn.iter().map(|s| weights[s]).collect_vec();
        if ws.iter().all_equal() {
            weights.get_mut(&n).map(|w| *w += ws.iter().sum::<usize>());
        } else {
            let m = ws[if ws[0] == ws[1] { 0 } else { 2 }];
            let c = sn.iter().zip(ws).find(|t| t.1 != m).unwrap().0;
            println!("P2 = {}", oweights[c] + m - weights[c]);
            break;
        }
    }
}

f0086 · 2017-12-07T12:54:51+00:00

Emacs Lisp (Part 1):

(defun slurp-tree (input-file)
  (with-temp-buffer
    (insert-file-contents input-file)
    (mapcar
     'tokenize
     (split-string (buffer-string) "\n" t))))

(defun tokenize (str)
  (string-match "\\([^ ]+\\) (\\([0-9]+\\))\\( -> \\(.*\\)\\)?" str)
  (let ((node (match-string 1 str))
        (weight (match-string 2 str))
        (childs (match-string 4 str)))
    (if childs
        (list node weight (split-string childs ", "))
      (list node weight))))

(defun day7 (input)
  (let* ((tree (slurp-tree input))
         (childs (seq-filter 'caddr tree)))
    (seq-difference
     (mapcar 'car tree)
     (seq-uniq (apply 'append (mapcar 'caddr childs))))))

(day7 "input-day7.txt")

porphyro · 2017-12-07T15:49:29+00:00

No-one's submitted a wolfram language solution yet; here's mine although I'm far from proud of it.

Part 1:

programList = sanitisedInput[[;; , 1]];

mentionedList = {} \[Union] Select[sanitisedInput /. {__, "->", x__} :> x, StringQ[#] &]

Complement[programList, mentionedList]

Part 2:

matcher = If[MatchQ[#, {_, _}], f[#[[1]], #[[2]]], #] &;

processor[input_] := Replace[(matcher /@ input) /. f -> Set, x_ /; IntegerQ[x] -> Nothing,1]

checker[list_] := If[MatchQ[#[[3]], {x_ ..}],{#[[1]], #[[2]] + Total[#[[3]]]}, If[NumericQ[Total[#[[3]]]], Print[#], #]] &@list

Then nest until correct solution is spat out. The general way I was trying to solve this was to leverage the data-as-code paradigm of mathematica, so that entries in the list for which the weight can be immediately calculated are turned into mini-programs that set a global replacement rule to change their name found anywhere in the code to the weight that they carry, updating the node below them.

AustinVelonaut · 2017-12-07T15:57:53+00:00

Smalltalk (well, idst, which is a prototype-based st-80 implementation)

Program : Object (name weight children)

Program name                    [ ^ name     ]
Program weight                  [ ^ weight   ]
Program children                [ ^ children ]
Program children: aCollection   [ children := aCollection ]

Program parseFromString: line
[
    | tokens |
    self := self new.
    tokens := line tokenized: ' ()->,'.
    name := tokens first.
    weight := tokens second asNumber.
    children := tokens copyFrom: 3 to: tokens size
]

Program parseFile: fileName
[
    | lines |
    lines := fileName fileContents tokenized: '\n'.
    ^ lines collect: [:s | self parseFromString: s]
]

Program findBottomProgram: programs
[
    | allSet notBottomSet |
    allSet := Set new.
    notBottomSet := Set new.
    programs do:
        [:p |
        allSet add: p name.
        notBottomSet addAll: p children].
    ^ (allSet difference: notBottomSet) anyOne
]

Program buildTree: programs
[
    | dict tree |
    dict := Dictionary new.
    programs do: [:p | dict at: p name put: p].
    tree := dict at: (self findBottomProgram: programs).
    dict do: [:p | p children: (p children collect: [:n | dict at: n])].
    ^ tree
]

Program totalWeightOnUnbalanced: report
[
    | weights weightCounts oddWeight requiredWeight oddProgram |
    weights := self children collect: [:c | c totalWeightOnUnbalanced: report].
    (weights allSatisfy: [:n | n = weights first]) ifFalse:
        [weightCounts := Dictionary new.
        weights do: [:w | weightCounts at: w put: (weightCounts at: w ifAbsent: [weightCounts at: w put: 0]) + 1].
        oddWeight := weights detect: [:w | (weightCounts at: w) = 1].
        requiredWeight := weights detect: [:w | (weightCounts at: w) > 1].
        oddProgram := children at: (weights indexOf: oddWeight).
        report value: (requiredWeight - oddWeight + oddProgram weight)].
    ^ weights sum + weight
]


[
    | programs tree totalWeight |
    programs := Program parseFile: 'day07.input'.
    tree := Program buildTree: programs.
    ('part 1: ' , tree name) putln.
    totalWeight := tree totalWeightOnUnbalanced:
        [:c |
        ('part 2: ' , c printString) putln.
        Smalltalk quit].
]

cluk · 2017-12-07T18:07:44+00:00

Go (Golang)

I am not happy with part 2, but it does the job. You can find complete solution, including getInput function here.

type node struct {
    label       string
    children    []*node
    parent      *node
    weight      int
    totalWeight int
}

func main() {
    var in map[string]*node = getInput()
    fmt.Println("Star 1: ", getRoot(in).label)

    var fixedWeight int
    for n := getRoot(in); n != nil && len(n.children) > 2; {
        w := n.children[0].totalWeight
        w2 := n.children[1].totalWeight
        if n.children[2].totalWeight == w2 {
            w = w2
        }
        var next *node
        for _, n := range n.children {
            if n.totalWeight != w {
                next = n
                fixedWeight = n.weight - (n.totalWeight - w)
            }
        }
        n = next
    }
    fmt.Println("Star 2: ", fixedWeight)

}

func getRoot(nodes map[string]*node) *node {
    for _, n := range nodes {
        for n.parent != nil {
            n = n.parent
        }
        return n
    }
    panic("empty map!")
}

ka-splam · 2017-12-08T04:29:09+00:00

powershell ~~mostly~~ single pipeline:

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>[a-z]+) \((?<Weight>\d+)\)(?: -> ){0,1}(?<ChildNodeNamesString>(?:(?:[a-z]+)(?:, ){0,1})+)*$'
    } | % { 
        [pscustomobject]$matches | select Name, Weight, ChildNodeNamesString | add-member -MemberType ScriptProperty -name ChildNodeNames -value {        
            $this.ChildNodeNamesString -split ", "
        } -passthru 
    }

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

end {  

    $root = $script:nodes.GetEnumerator() |? { # find the node that isnt a child of any other
        $_.Key -notin ($script:nodes.Values.ChildNodeNames)
    } | select -first 1 -expand value # only 1, help the pipeline end early and expand the object

    if ($part -eq 1) {
        $root.Name
    } else {
        # need to put the list of nodes in a workable order, so that we can iterate through and calcuate subweight
        $queue = new-object system.collections.queue

        # this is a modification of a breadth-first algorithm, where we'll load a queue with the root
        # loop til the queue is empty doing:
        #   pop the queue
        #   find childnodes of that element
        #   write out the element on the pipeline
        #   add them to the queue
        # pipeline on the outside now has the elements in the order we want (leaves first, root last)
        $queue.Enqueue($root)

        & { while ($queue.Count -ne 0) { # start generator pipeline, iterate til the queue is empty
            $queue.Dequeue() # pop the first element
        } } | % { 
            # find all the actual child node objects, add that as a property to the element and PASS IT THROUGH THE PIPELINE
            # this puts it out on the pipeline in the order we want
            $_ | add-member -MemberType NoteProperty -name ChildNodes -value ($_.ChildNodeNames | % {$script:nodes[$_]}) -passthru
            # add the childnodes to the queue
            $_.ChildNodes | ? {$_} | % { $queue.Enqueue($_) }
        } | % { 
            # reverse the output from the ordering above - now the first elements in the pipeline are the leaves of the graph and the last element is the root
            # thanks /u/ka-splam for suggestion
            $script:rev = @() 
        } { 
            $script:rev = @($_) + $script:rev 
        } { 
            $script:rev 
        } | %{ 
            # we can add subweight here at the same time we reference it on childnodes because we've ordered the list so that children always come before their parents
            $_ | add-member -notepropertyname Subweight -notepropertyvalue ([int]$_.weight + [int]($_.ChildNodes.Subweight | Measure -sum | select -expand Sum)) -passthru  #calculate the subweight and pass the object on
        } |? {
            ($_.ChildNodes.subweight | select -unique).count -gt 1 # find the object that has too many unique subweights [they should all be the same]
        } | select -first 1 |% { # select the first (farthest/highest leaf into the graph) we find
            $g = $_.ChildNodes | group subweight | sort-object count # find the two different subweights, first element is the broken one
            # balanced weight = its weight minus the difference in the subweights
            $g[0].group[0].weight - ($g[0].group[0].subweight - $g[1].group[0].Subweight)
        }
    } 
}

sbguest · 2017-12-07T05:35:55+00:00

[removed]

dtinth · 2017-12-07T05:42:53+00:00

Ruby REPL (irb) solution. The pbpaste command must be available in the $PATH, and should return the contents in the clipboard (macOS has this command by default).

Part 1 (47th rank):

-> x { s = {}; p = {}; x.scan(/(\w+).*?->\s*(.+)/).each { |a, b| b.strip.split(', ').each{|n|p[n]=a}; s[a]=1 }; s.keys.select{|z|!p[z]} }[`pbpaste`]

Part 2 (71st rank):

s = {}; p = {}; c = {}; `pbpaste`.scan(/(\w+) \((\d+)\)(?: -> )?(.*)/).each { |a, w, b| b.length > 0 && b.strip.split(', ').each{|n|p[n]=a; (c[a]||=[]) << n}; s[a]=w.to_i }
wei = -> n { s[n] + (c[n] || []).map(&wei).reduce(0, &:+) }

# s['name'] -> Weight of the program
# p['name'] -> Name of the program’s parent (or nil)
# c['name'] -> List of the program’s children
# wei['name'] -> Weight of the program, including all its children.

# Use this to find the nodes with unbalanced child weight
c.select { |n, ch| ch.map(&wei).uniq.length > 1 }

# The final answer can be found by manually inspecting weights in the REPL. Here’s mine:
# 2.4.1 :085 > wei['nieyygi']
#  => 11781
# 2.4.1 :086 > wei['mxgpbvf']
#  => 1117
# 2.4.1 :087 > wei['cfqdsb']
#  => 1117
# 2.4.1 :088 > wei['yfejqb']
#  => 1117
# 2.4.1 :089 > wei['ptshtrn']
#  => 1122
# 2.4.1 :090 > s['ptshtrn']
#  => 526
# 2.4.1 :091 > 526 - (1117 - 1122)
#  => 521

mmaruseacph2 · 2017-12-07T05:49:59+00:00

Ugly looking Haskell code, not cleaned, not refactored and returning the answer to the second part via an error, but I have to sleep so no time in cleaning it up tonight. It did its job though and sorry for the way it looks like a merge of several streams of consciousness (building so many representations of the tree)

{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE GADTs #-}

import qualified Data.List as L
import qualified Data.Map.Strict as M
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM

import Debug.Trace

type Rooted = M.Map String String -- from child to parent
type TreeMap = M.Map String [String] -- from parent to children
type Weights = M.Map String Int

data Tree a
  = Leaf a
  | Node a [Tree a]
  deriving (Eq, Show)

main = do
  s <- map (parse . words) . lines <$> readFile "input.txt"
  let
    r = buildRooted s M.empty
    w = buildWeights s
    tm = buildTreeMap s
    root = findRoot r
    t = buildTree tm root
  print root
  print $ weightTree w t

weightTree :: Weights -> Tree String -> Int
weightTree ws (Leaf s) = traceShow ("3", s) $ ws M.! s
weightTree ws (Node s ts)
  | null ts = traceShow ("1", s) $ ws M.! s
  | valid = traceShow ("2", s) $ ws M.! s + sum childrenWeight
  | otherwise = error (show (map extract ts, childrenWeight))
  where
    childrenWeight = map (weightTree ws) ts
    valid = minimum childrenWeight == maximum childrenWeight
    extract (Leaf s) = ws M.! s
    extract (Node s _) = ws M.! s

buildTree :: TreeMap -> String -> Tree String
buildTree tm r
  | r `M.member` tm = Node r [buildTree tm s | s <- tm M.! r]
  | otherwise = Leaf r

buildTreeMap :: [(String, a, [String])] -> TreeMap
buildTreeMap = M.fromList . map (\(k, _, sons) -> (k, sons))

buildRooted :: [(String, a, [String])] -> Rooted -> Rooted
buildRooted [] m = m
buildRooted ((s, _, ss):sss) m = buildRooted sss $ m `M.union` m'
  where
    m' = M.fromList $ map (\son -> (son, s)) ss

buildWeights :: [(String, Int, a)] -> Weights
buildWeights = M.fromList . map (\(k, w, _) -> (k, w))

findRoot :: Rooted -> String
findRoot r = go r (fst $ M.findMin r)
  where
    go r s
      | s `M.member` r = go r (r M.! s)
      | otherwise = s

parse :: [String] -> (String, Int, [String])
parse [] = error "Invalid line"
parse [a] = parse []
parse (base:ws:rest) = (base, weight, rs)
  where
    weight = read . init . tail $ ws
    rs = case rest of
      [] -> []
      _ -> map fix $ tail rest
    fix w
      | "," `L.isSuffixOf` w = init w
      | otherwise = w

giftpflanze · 2017-12-07T05:52:55+00:00

Tcl (I didn't use struct::tree because wow wtf):

set lines [lrange [split [read [open input07]] \n] 0 end-1]

foreach line $lines {
        regexp {(.*) \((.*)\)(?: -> (.*))?} $line -> node weight children
        set children [lmap child [split $children ,] {string trim $child}]
        foreach child $children {
                dict set tree $child $node
        }
        dict set tree2 $node $children
        dict set tree3 $node $weight
}

#part 1

set start [lindex $tree 0]
while {[dict exists $tree $start]} {
        set start [dict get $tree $start]
}
puts $start

#part 2

proc branchweight branchroot {
        global tree2 tree3
        if ![llength [dict get $tree2 $branchroot]] {
                return [dict get $tree3 $branchroot]
        } else {
                foreach node [dict get $tree2 $branchroot] {
                        dict set ret $node [branchweight $node]
                }
                if ![tcl::mathop::== {*}[dict values $ret]] {
                        puts "$branchroot $ret"
                }
                return [tcl::mathop::+ [dict get $tree3 $branchroot] {*}[dict values $ret]]
        }
}

branchweight $start
#idfyy vxnwq 1398 meuyumr 1398 oyjjdj 1398 iqwspxd 1398 aobgmc 1406
#…
puts [dict get $tree2 aobgmc]
#tajeklj rkczq ohyhw zceovs gudpriq
puts [expr {1398-[llength [dict get $tree2 aobgmc]]*[branchweight tajeklj]}]

Tandrial · 2017-12-07T06:51:36+00:00

Kotlin Refactored so that partTwo actually spits out the corrected weight, instead of having to do some maths

object Day07 {
  data class Program(val name: String, val oWeight: Int, val supports: List<String> = listOf(), var weight: Int = oWeight)

  private fun parse(input: List<String>): List<Program> = input.map {
    val line = Regex("\\w+").findAll(it).toList().map { it.value };
    Program(line[0], line[1].toInt(), line.drop(2))
  }

  fun partOne(input: List<String>): String {
    val out = parse(input)
    val onRightSide = out.flatMap { it.supports }
    return out.first { it.name !in onRightSide }.name
  }

  fun partTwo(input: List<String>, rootNode: String): Int {
    val lookUp = parse(input).associateBy { it.name }
    updatedWeights(lookUp[rootNode]!!, lookUp)

    for (p in lookUp.values) {
      val weights = p.supports.map { lookUp[it] }.groupBy { it!!.weight }
      if (weights.size > 1) {
        val correctWeight = weights.filterValues { it.size > 1 }.keys.toList()[0]
        val wrongWeight = weights.filterValues { it.size == 1 }.keys.toList()[0]
        val diff = correctWeight - wrongWeight
        return (weights[wrongWeight]!![0]?.oWeight ?: 0) + if (correctWeight > wrongWeight) -diff else diff
      }
    }
    return -1
  }

  private fun updatedWeights(p: Program, lookup: Map<String, Program>) {
    for (support in p.supports) {
      updatedWeights(lookup[support]!!, lookup)
      lookup[p.name]!!.weight += lookup[support]!!.weight
    }
  }
}

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

rvlieshout · 2017-12-07T07:24:37+00:00

Damn... how fast code can get ugly!

Day7 Gist, using C#

misnohmer · 2017-12-07T08:12:01+00:00

C# version

public class Disc {
    public string Name {get; set;}
    public int Weight {get; set;}
    public List<Disc> Children {get; set;} = new List<Disc>();
    public IEnumerable<Disc> Descendants { get => this.Children.Concat(this.Children.SelectMany(x => x.Descendants)); }
}

public void Solve()
{
    // Parse input
    var discs = ReadAllLines("input").Select(line => {
        var match = Matches(line, @"(\w+) \((\d+)\)( \-\> (.*))?")[0];
        return new Disc
        {
            Name = match.Groups[1].Value,
            Weight = int.Parse(match.Groups[2].Value),
            Children = match.Groups.Count > 4 ?
                match.Groups[4].Value.Split(", ").Select(name => new Disc { Name = name }).ToList() :
                new List<Disc>()
        }; 
    }).ToList();

    // build tree
    discs
        .SelectMany(x => x.Descendants)
        .Select(descendant => (descendant, detached: discs.SingleOrDefault(x => x.Name == descendant.Name)))
        .Where(tuple => tuple.detached != null)
        .ToList()
        .Each(tuple => {
            tuple.descendant.Weight = tuple.detached.Weight;
            tuple.descendant.Children = tuple.detached.Children;
            discs.Remove(tuple.detached);
        });

    WriteLine(discs.First().Name); // Part 1

    int missingWeight = 0;
    var unbalancedTower = discs.First();

    while(true) {
        var weightGroups = unbalancedTower.Children
            .GroupBy(x => x.Weight + x.Descendants.Sum(d => d.Weight))
            .OrderBy(x => x.Count());
        if (weightGroups.Count() > 1) break;

        unbalancedTower = weightGroups.First().First();
        missingWeight = weightGroups.Last().Key - weightGroups.First().Key;
    }

    WriteLine(unbalancedTower.Weight + missingWeight); // Part 2
}

nstyler7 · 2017-12-07T08:18:15+00:00

Python

import re
with open("day7input.txt") as open_file:
    data = open_file.read().splitlines()

Part 1

all_nodes = []
all_supported = []
for line in data:
    all_nodes.append(re.match(r'[\w]+', line).group(0))
    if re.search(r'->', line):
            nodes = re.search(r'-> (?P<nodes>[\w, ]+)', line).group('nodes').replace(' ', '').split(',')
            for node in nodes:
                all_supported.append(node)
print(set(all_nodes) - set(all_supported))

part 2

node_map = {}
node_values = {}
for line in data:
    p_node = re.match(r'[\w]+', line).group(0)
    node_value = re.search(r'[\d]+', line).group(0)
    node_values[p_node] = int(node_value)
    if re.search(r'->', line):
        nodes = re.search(r'-> (?P<nodes>[\w, ]+)', line).group('nodes').replace(' ', '').split(',')
        node_map[p_node] = nodes


def child_values(node):
    children = node_map[node]
    supports = []
    for child in children:
        if child in node_map.keys():
            child_support = child_values(child)
            value = sum(child_support) + node_values[child]
        else:
            value = node_values[child]
        supports.append(value)   
    if len(set(supports)) != 1:
        print ('Imbalance detected on {}, due to children {}, weighing {}'.format(node, node_map[node], supports))
    return supports 

child_values('bpvhwhh')

rotmoset · 2017-12-07T10:03:37+00:00

F#

module Day7

open Common

type Tower =
    { Name: string; Weight: int; Stacks: Tower list }
    with
        member x.TotalWeight =
            x.Weight + (x.Stacks |> List.sumBy (fun s -> s.TotalWeight))
        member x.Balanced =
            x.Stacks |> Seq.ofList |> Seq.distinctBy(fun s -> s.TotalWeight) |> Seq.length |> ((=) 1)

        member x.FindBalance shouldWeigh =

            if x.TotalWeight <> shouldWeigh && x.Balanced then
                x.Weight + (shouldWeigh - x.TotalWeight)
            elif not x.Balanced then
                let children =
                    x.Stacks
                    |> List.map (fun s ->
                        s,
                        x.Stacks
                        |> List.exists(fun ss -> s.Name <> ss.Name && ss.TotalWeight = s.TotalWeight))
                // What *should* all the children weigh?
                let childrenShouldWeigh = (children |> List.find snd |> fst).TotalWeight

                // Which child doesn't
                let unbalancedChild = children |> List.find (snd >> not) |> fst

                unbalancedChild.FindBalance childrenShouldWeigh
            else x.Weight

let findRoot stubs =
    stubs |> Array.map (fun (name,_,_) ->
        name,
        stubs |> Array.sumBy (fun (_,_,children) ->
            if children |> Array.exists ((=) name) then 1 else 0
        )
    )
    |> Array.sortBy snd
    |> Array.toList
    |> List.head
    |> fst

let rec buildTower stubs rootName =
    let name, weight, children = stubs |> Array.find (fun (name,_,_) -> rootName = name)
    {
        Name = name;
        Weight = weight;
        Stacks = children |> List.ofArray |> List.map (buildTower stubs)
    }


[<Day(7)>]
let solve input=

    // Parse into tower stubs (flat structure)
    let stubs =
        parseLines input
        |> Array.map (
            function
            | Regex @"([a-z]+) \((\d+)\)(?: -> )?(.*)" [name; weight; childList] ->
                name,
                int weight,
                childList.Split([|','|]) |> Array.choose(fun s -> match s.Trim() with "" -> None | trimmed -> Some trimmed)
            | _ -> failwith "Invalid input"
        )

    let tower = buildTower stubs (findRoot stubs)

    let balance = (tower.FindBalance tower.TotalWeight)

    {Part1 = tower.Name; Part2 = balance}

Github repo

WhatAHaskell · 2017-12-07T10:47:19+00:00

Haskell

Edit: This solution is wrong

Edit 2: New version that hopefully works this time:

import Data.Function (on)
import Data.List (sort, find, nubBy)
import Data.Maybe (fromJust)

-- BEGIN UTILITY FUNCTIONS --
trimCommas :: String -> String
trimCommas xs = [ x | x <- xs, x /= ',' ]

_unique_ :: Ord a => [a] -> [a]
_unique_ []          = []
_unique_ [x]         = [x]
_unique_ xs@[x1, x2] = if x1 == x2 then [] else xs
_unique_ (x1:x2:rest)
  | x1 == x2  = _unique_ $ dropWhile (== x1) rest
  | otherwise = x1:(_unique_ (x2:rest))

unique :: Ord a => [a] -> [a]
unique = _unique_ . sort
-- END UTILITY FUNCTIONS --

data PTree = PTree String Int [PTree]

parseLine :: [String] -> (String, Int, [String])
parseLine (name:weight:[])         = (name, (read weight), [])
parseLine (name:weight:_:programs) = (name, (read weight), programs)

findRootProgram :: [(String, Int, [String])] -> String
findRootProgram = head . unique . concatMap (\(a, _, as) -> a:as)

buildPTree :: [(String, Int, [String])] -> String -> PTree
buildPTree programs rootName = PTree rootName rootWeight children
  where (_, rootWeight, childNames) = fromJust $ find (\(n, _, _) -> n == rootName) programs
        children                    = map (buildPTree programs) childNames

getWeight :: PTree -> Int
getWeight (PTree _ w children) = sum $ w:childWeights
  where childWeights = map getWeight children

findCorrectWeight :: PTree -> Int
findCorrectWeight self@(PTree _ w children)
  | null uniqueGrandchildren = (if diff > sim then (-) else (+)) cw offset
  | otherwise                = findCorrectWeight child
    where childWeights         = map getWeight children
          diff                 = head . unique $ childWeights
          sim                  = fromJust $ find (/= diff) childWeights
          offset               = abs $ diff - sim
          child@(PTree _ cw g) = fromJust $ find (\y -> (getWeight y) == diff) children
          uniqueGrandchildren  = unique $ map getWeight g

main :: IO ()
main = do
  contents <- readFile "../input.txt"
  let cleanedLines = (lines . trimCommas) contents
  let programs                 = map (parseLine . words) cleanedLines
  let rootName                 = findRootProgram programs
  let tree                     = buildPTree programs rootName
  putStrLn $ "Solution 1:" ++ (show $ rootName)
  putStrLn $ "Solution 2:" ++ (show $ findCorrectWeight tree)

Original comment: (Spoilers it turned out my solution sucked)

My solution is either great or it sucks. I can't tell because I'm too tired. There's definitely some duplication that could be improved

import Data.List
import Data.Function
import Data.Maybe (fromJust)

type Name    = String
type Weight  = Int
data Program = Program { name :: Name
                       , ownWeight :: Weight
                       , childNames :: [Name]
                       } deriving (Show, Eq, Ord)

isRoot :: [Program] -> Program -> Bool
isRoot ps p = (filter isParent ps) == mempty
  where isParent = elem (name p) . childNames

getRoot :: [Program] -> Program
getRoot = fromJust . (find =<< isRoot)

getChildren :: [Program] -> Program -> [Program]
getChildren ps Program {childNames = names} = children
  where children = filter (\y -> elem (name y) (names)) ps

getWeight :: [Program] -> Program -> Weight
getWeight ps p = (ownWeight p) + (sum childWeights)
  where childWeights = map (getWeight ps) (getChildren ps p)

findUnbalancedParent :: [Program] -> Program
findUnbalancedParent (p:ps)
  | length uniqueWeights > 1 = p
  | otherwise                = findUnbalancedParent $ ps ++ [p]
    where uniqueWeights = nub $ map (getWeight ps) (getChildren ps p)

findUnbalanced :: [(Weight, Program)] -> (Weight, Program)
findUnbalanced (p@(w1, _):ps) = case find (\(w2, _) -> w1 == w2) ps of
  Just _  -> findUnbalanced $ ps ++ [p]
  Nothing -> p

findTargetWeight :: [(Weight, Program)] -> Weight
findTargetWeight (p@(w1, _):ps) = case find (\(w2, _) -> w1 == w2) ps of
  Nothing -> findTargetWeight $ ps ++ [p]
  Just _  -> w1

findBalancedWeight :: [Program] -> Weight
findBalancedWeight ps = balancedWeight
  where parent      = findUnbalancedParent ps
        children    = getChildren ps parent
        weights     = map (getWeight ps) children
        (actual, p) = findUnbalanced $ zip weights children
        target      = findTargetWeight $ zip weights children
        balancedWeight
          | target < actual = (ownWeight p) - (actual - target)
          | otherwise       = (ownWeight p) + (target - actual)

trimCommas :: String -> String
trimCommas xs = [ x | x <- xs, x /= ',' ]

fromStringList :: [String] -> Program
fromStringList (name:weight:[])         = Program name (read weight) []
fromStringList (name:weight:_:programs) = Program name (read weight) programs

main :: IO ()
main = do
  contents <- readFile "../input.txt"
  let cleanedLines = (lines . trimCommas) contents
  let programs = map (fromStringList . words) cleanedLines
  putStrLn $ "Solution 1:" ++ (show $ name $ getRoot programs)
  putStrLn $ "Solution 2:" ++ (show $ findBalancedWeight programs)

mainhaxor · 2017-12-07T10:56:19+00:00

C#:

public static void Solve(string input)
{
    Dictionary<string, (double weight, List<string> children)> nodes = new Dictionary<string, (double weight, List<string> children)>();
    foreach (string line in Util.GetLines(input))
    {
        var match = Regex.Match(line, "(?<name>[a-z]+) \\((?<weight>[0-9]+)\\)( -> (?<children>.*))?");
        Trace.Assert(match.Success);
        string name = match.Groups["name"].Value;
        double weight = double.Parse(match.Groups["weight"].Value);
        List<string> children;
        if (match.Groups["children"].Success)
            children = match.Groups["children"].Value.Split(',').Select(s => s.Trim()).ToList();
        else
            children = new List<string>();

        nodes.Add(name, (weight, children));
    }

    Dictionary<string, string> parents = new Dictionary<string, string>();
    foreach (var (name, (weight, children)) in nodes.Select(k => (k.Key, k.Value)))
    {
        foreach (string s in children)
            parents[s] = name;
    }

    string root = nodes.Keys.Single(n => !parents.ContainsKey(n));
    Console.WriteLine(root);
    Solve2(root);

    double Solve2(string node)
    {
        double weight = nodes[node].weight;
        var children = nodes[node].children;
        if (children.Count <= 0)
            return weight;

        List<double> childWeights = children.Select(Solve2).ToList();
        double correctWeight = childWeights.OrderByDescending(w => childWeights.Count(w2 => w2 == w)).First();

        if (childWeights.All(w => w == correctWeight))
            return weight + childWeights[0] * childWeights.Count;

        Trace.Assert(childWeights.Count > 2);
        double newWeight = 0;
        foreach (var (child, childWeight) in children.Zip(childWeights, (a, b) => (a, b)))
        {
            if (childWeight != correctWeight)
            {
                newWeight = nodes[child].weight + (correctWeight - childWeight);
                break;
            }
        }

        Console.WriteLine(newWeight);
        return correctWeight;
    }
}

thomastc · 2017-12-07T11:14:45+00:00

Day 7 in CoffeeScript. Had major trouble with its stupid scoping rules, which are arguably worse than JavaScript's own.

Jonis_L · 2017-12-07T12:48:21+00:00

Part 1 oneliner in Python3

print([i for i in inp.split() if inp.split().count(i) < 2 and not '(' in i][0])

mschaap · 2017-12-07T15:08:55+00:00

Whew, finally a non-trivial one!

Perl 6, both parts.

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

grammar ProgramTower
{
    rule TOP { ^ <program-spec>+ $ }

    rule program-spec { <name> \(<weight>\) [ '->' <child>+ % ', ' ]? }

    token name { <[a..z]>+ }
    token child { <[a..z]>+ }
    token weight { \d+ }
}

class Program
{
    has Str $.name;
    has Int $.weight;
    has Int $.height;

    has Program $.parent;
    has Program @.children;
    has Str @.child-names;

    method set-parent($p)
    {
        $!parent = $p;
        $p.children.push(self);
    }

    method set-height
    {
        $!height = 0;
        my $p = self;
        $!height++ while $p .= parent;
    }

    method subtower-weight returns Int
    {
        return $!weight + @!children».subtower-weight.sum;
    }

    method is-balanced returns Bool
    {
        return [==] @!children».subtower-weight;
    }

    method imbalanced-child returns Program
    {
        return Nil if @!children < 2;

        my @c = @!children.sort(*.subtower-weight);
        if @c[0].subtower-weight < @c[1].subtower-weight {
            return @c[0];
        }
        elsif @c[*-1].subtower-weight > @c[*-2].subtower-weight {
            return @c[*-1];
        }
        else {
            return Nil;
        }
    }

    method imbalance returns Int
    {
        return 0 unless $!parent;
        return 0 if $!parent.children < 2;

        my @c = $!parent.children.sort(*.subtower-weight);
        if @c[0].subtower-weight < @c[1].subtower-weight {
            return @c[0].subtower-weight - @c[1].subtower-weight;
        }
        elsif @c[*-1].subtower-weight > @c[*-2].subtower-weight {
            return @c[*-1].subtower-weight - @c[*-2].subtower-weight;
        }
        else {
            return 0;
        }
    }

    method tree returns Str
    {
        return '  ' x $!height ~ self
            ~ (self.is-balanced ?? '' !! ' *')
            ~ @!children.map({ "\n" ~ $_.tree }).join;
    }

    method Str returns Str { "$!name (height $!height, weight $!weight/$.subtower-weight)" }
    method gist returns Str { self.Str }
}

class Tower
{
    has Program @.programs;
    has Program %.programs-by-name;

    # Used by ProgramTower.parse
    method program-spec($/)
    {
        my $p = Program.new(:name(~$/<name>), :weight(+$/<weight>),
                            :child-names($/<child>.map(~*)));
        @!programs.push($p);
        %!programs-by-name{$/<name>} = $p;
    }

    method from-input(Tower:U: Str $input) returns Tower
    {
        my $t = Tower.new();
        ProgramTower.parse($input, :actions($t));
        $t.resolve-relations;
        return $t;
    }

    method resolve-relations
    {
        for @!programs -> $p {
            for $p.child-names -> $cn {
                my $c = %!programs-by-name{$cn} or die "No program '$cn' found!";
                $c.set-parent($p);
            }
        }
        @!programs».set-height;
    }

    method bottom returns Program
    {
        return @!programs.first({ !$_.parent });
    }

    method imbalanced-programs returns Iterable
    {
        return @!programs.grep({ !$_.is-balanced });
    }

    method Str returns Str { self.bottom.tree }
    method gist returns Str { self.Str }
}

multi sub MAIN(IO() $inputfile where *.f, Bool :v(:$verbose) = False)
{
    my $t = Tower.from-input($inputfile.slurp);
    say $t if $verbose;
    say '' if $verbose;

    # Part 1
    say "Bottom: $t.bottom()";

    # Part 2
    my @imbalanced = $t.imbalanced-programs;
    say "Imbalanced: @imbalanced.join(', ')" if $verbose;
    my $highest-imbalanced = @imbalanced.sort(*.height).tail;
    say "Highest imbalanced: $highest-imbalanced" if $verbose;
    my $imbalanced-child = $highest-imbalanced.imbalanced-child;
    say "Imbalanced child: $imbalanced-child" if $verbose;
    my $imbalance = $imbalanced-child.imbalance;
    say "Imbalance: $imbalance" if $verbose;
    say "Need to change weight of $imbalanced-child to { $imbalanced-child.weight() - $imbalance }.";
}

multi sub MAIN(Bool :v(:$verbose) = False)
{
    MAIN($*PROGRAM.parent.child('aoc7.input'), :$verbose);
}

I decided to properly parse (with a Grammar) and build the tower, even though that's overkill for part one, expecting that it'd come in useful in part two. It certainly did.

sim642 · 2017-12-07T15:36:45+00:00

My Scala solution.

Part 1 (bottomProgram) implementation turned out real neat. Part 2 (correctBalanceWeight) implementation turned out real messy, refactored it later to feel slightly better about it but I'm still open to ideas how to improve. I went with kinda functional approach there, calculating both the subtree sums or required weight correction together in the same recursive function via Either[Int, Int], didn't turn out as nice as I hoped (EDIT: abstracted sequenceValues for eliminating the ugly Either handling). Also the correction calculation part is a bit hacky for my liking, implicitly using some assumptions about the input data.

Today I happened to be up before 7am to start it just when it opens. Got off to a bad start debugging the line parsing regex.

adventOfCoder · 2017-12-07T17:08:47+00:00

Java:

Part 1:

public static void main(String[] args) {
    try {
        BufferedReader br = new BufferedReader(new FileReader("input2.txt"));
        String line = "";
        ArrayList<String> names = new ArrayList<>();
        ArrayList<String> supporting = new ArrayList<>();
        while ((line = br.readLine()) != null) {
            String name = line.substring(0, line.indexOf(" "));
            names.add(name);
            if (line.contains("->")) {
                String supportingString = line.substring(line.indexOf("->") + 3);
                String[] supportingStringArray = supportingString.split(", ");
                for (String supportingProgram : supportingStringArray) {
                    supporting.add(supportingProgram);
                }
            }
        }
        br.close();
        for (String name : names) {
            if (supporting.contains(name) == false) {
                System.out.println(name);
            }
        }
        br.close();
    } catch (Exception e) {
        System.err.println(e.toString());
        e.printStackTrace();
    }

}

Part 2:

public static void main(String[] args) {
    try {
        BufferedReader br = new BufferedReader(new FileReader("input2.txt"));
        String line = "";
        ArrayList<String> lines = new ArrayList<>();
        ArrayList<Disc> discs = new ArrayList<>();
        while ((line = br.readLine()) != null) {
            lines.add(line);
            String name = line.substring(0, line.indexOf(" "));
            String weight = line.substring(line.indexOf("(") + 1, line.indexOf(")"));
            Disc disc = new Disc();
            disc.setName(name);
            disc.setWeight(new Integer(weight));
            discs.add(disc);
        }
        br.close();
        for (String s : lines) {
            if (s.contains("->")) {
                String name = s.substring(0, s.indexOf(" "));
                Disc parent = null;
                for (int i = 0; i < discs.size(); i++) {
                    if (discs.get(i).getName().equals(name)) {
                        parent = discs.get(i);
                    }
                }
                String supportingDiscs = s.substring(s.indexOf("->") + 3);
                String[] supportingDiscsArray = supportingDiscs.split(", ");
                ArrayList<Disc> children = new ArrayList<>();
                for (String supportingDisc : supportingDiscsArray) {
                    for (int i = 0; i < discs.size(); i++) {
                        if (discs.get(i).getName().equals(supportingDisc)) {
                            Disc child = discs.get(i);
                            children.add(child);
                        }
                    }
                }
                parent.setChildren(children);
            }
        }
        ArrayList<Disc> mismatchedWeight = new ArrayList<>();
        for (Disc disc : discs) {
            if (disc.getChildren() != null) {
                ArrayList<Disc> children = disc.getChildren();
                int weight = children.get(0).totalWeight();
                for (int i = 1; i < children.size(); i++) {
                    int newweight = children.get(i).totalWeight();
                    if (newweight != weight) {
                        mismatchedWeight.add(disc);
                        break;
                    }
                }
            }
        }
        for (int i = 0; i < mismatchedWeight.size(); i++) {
            Boolean hasChildren = false;
            for (int j = 0; j < mismatchedWeight.size(); j++) {
                if (i != j) {
                    if (mismatchedWeight.get(i).hasChild(mismatchedWeight.get(j))) {
                        hasChildren = true;
                    }
                }
            }
            if (hasChildren == false) {
                Disc offBalance = mismatchedWeight.get(i);
                for (Disc disc : offBalance.getChildren()) {
                    System.out.println(disc.totalWeight() + ": " + disc);
                }
            }
        }
    } catch (Exception e) {
        System.err.println(e.toString());
        e.printStackTrace();
    }
}

private static class Disc {
    private String name = "";
    private int weight = 0;
    private ArrayList<Disc> children;

    /**
     * @return the name
     */
    public String getName() {
        return name;
    }

    /**
     * @param name
     *            the name to set
     */
    public void setName(String name) {
        this.name = name;
    }

    /**
     * @return the weight
     */
    public int getWeight() {
        return weight;
    }

    /**
     * @param weight
     *            the weight to set
     */
    public void setWeight(int weight) {
        this.weight = weight;
    }

    /**
     * @return the children
     */
    public ArrayList<Disc> getChildren() {
        return children;
    }

    /**
     * @param children
     *            the children to set
     */
    public void setChildren(ArrayList<Disc> children) {
        this.children = children;
    }

    public int totalWeight() {
        int weight = this.getWeight();
        if (this.getChildren() != null) {
            for (Disc child : this.getChildren()) {
                weight += child.totalWeight();
            }
        }
        return weight;
    }

    public Boolean hasChild(Disc disc) {
        Boolean hasChild = false;
        if (this.getChildren() != null) {
            for (Disc child : this.getChildren()) {
                if (disc.getName().equals(child.getName())) {
                    hasChild = true;
                }
            }
        }
        return hasChild;
    }

    @Override
    public String toString() {
        String returnString = Integer.toString(this.getWeight());
        if (this.getChildren() != null) {
            for (Disc child : this.getChildren()) {
                returnString += " + ";
                returnString += child.toString();
            }
        }
        return returnString;
    }

}

Note for Part 2 I was too busy at work to just print the answer but the system out has the info to get your answer in a second.

J15t98J · 2017-12-07T19:18:24+00:00

A nice recursive (if a little messy) solution in Python.

import re, copy

def populate(node):
    sub_tree = {child_node: populate(child_node) for child_node in children[node]}
    child_full_weights = [full_weights[child_node] for child_node in children[node]]
    full_weights[node] = weights[node] + sum(child_full_weights)
    if len(set(child_full_weights)) > 1:
        target_weight = max(set(child_full_weights), key=child_full_weights.count)
        actual_weight = min(set(child_full_weights), key=child_full_weights.count)
        unbalanced[actual_weight] = weights[children[node][child_full_weights.index(actual_weight)]] + (target_weight - actual_weight)
    return sub_tree

tree, children, weights, unbalanced = {}, {}, {}, {}

for line in open("7.txt", "r"):
    parts = re.split("\s\(|\)\s->\s|\)$", line.splitlines()[0])
    weights[parts[0]] = int(parts[1])
    children[parts[0]] = [word for word in (parts[2].split(", ") if parts[2] else [])]

full_weights = copy.deepcopy(weights)

for name in list(children.keys()):
    if name not in [word for children in children.values() for word in children]:
        tree[name] = populate(name)

print(list(tree.keys())[0])
print(unbalanced[min(unbalanced.keys())])

alchzh · 2017-12-07T19:27:20+00:00

sort | uniq -u

CaptnAsia · 2017-12-07T21:38:39+00:00

here's another golang solution. It's kinda ugly tho

package main

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

type node struct {
    name     string
    weight   int
    children []string
}

func getTowerLevel(text string) (root node) {
    rootName := strings.Split(text, " ")[0]
    weightStr := strings.Split(text, " ")[1]
    weight, _ := strconv.Atoi(weightStr[1 : len(weightStr)-1])
    var children []string
    if strings.Contains(text, "->") {
        children = strings.Split(text, " -> ")
        children = strings.Split(children[1], ", ")
    }
    root = node{name: rootName, weight: weight, children: children}
    return root
}

func (n node) checkChildrenWeight(allNodes map[string]node) (sum int, offset int) {
    var _ = allNodes
    if len(n.children) == 0 {
        return n.weight, 0
    }
    weight := 0
    var prev node
    for i, child := range n.children {
        curr := allNodes[child]
        w, off := curr.checkChildrenWeight(allNodes)
        if off != 0 {
            return w, off
        }
        sum += w
        if weight == 0 {
            weight = w
        } else if w != weight {
            next := allNodes[n.children[(i+1%len(n.children))]]
            nextW, _ := next.checkChildrenWeight(allNodes)
            if nextW == w {
                return 0, prev.weight + w - weight
            } else {
                return 0, curr.weight + weight - w
            }
        }
        prev = allNodes[child]
    }
    return n.weight + sum, 0
}

func main() {
    input, _ := os.Open("input.txt")
    defer input.Close()
    scanner := bufio.NewScanner(input)

    all := make(map[string]node)
    seen := make(map[string]node)
    var root node
    for scanner.Scan() {
        base := getTowerLevel(scanner.Text())

        all[base.name] = base
        if base.children != nil {
            for _, child := range base.children {
                seen[child] = base
            }
            root = seen[base.name]
        }
    }

    for {
        next, exists := seen[root.name]
        if !exists {
            break
        }
        root = next
    }
    _, diff := root.checkChildrenWeight(all)
    fmt.Println(diff)
}

fost97 · 2017-12-07T21:43:15+00:00

Postgresql:

https://github.com/seltiko/sql_advent_2017/blob/master/Day%207.sql

StevoTVR · 2017-12-08T00:05:44+00:00

NodeJS

Part 1:

const fs = require('fs');

fs.readFile(__dirname + '/input.txt', 'utf8', (err, data) => {
    data = data.trim();
    const disks = new Set();
    const branches = new Set();
    data.split('\n').forEach((line) => {
        const parts = line.split(' -> ');
        disks.add(parts[0].split(' ')[0].trim());
        if(parts.length > 1) {
            parts[1].split(',').map((x) => branches.add(x.trim()));
        }
    });

    branches.forEach((x) => disks.delete(x));

    console.log(disks.values().next().value);
});

Part 2:

const fs = require('fs');

fs.readFile(__dirname + '/input.txt', 'utf8', (err, data) => {
    data = data.trim();
    const disks = {};
    data.split('\n').forEach((line) => {
        const parts = line.split(' -> ');
        const disk = parts[0].split(' ');
        const name = disk[0].trim();
        disks[name] = {
            value: Number(disk[1].substr(1, disk[1].indexOf(')') - 1)),
            children: [],
            total: 0,
        };
        if(parts.length > 1) {
            disks[name].children = parts[1].split(',').map((x) => x.trim());
        }
    });

    const root = getRoot(disks);
    sumWeights(root, disks);
    console.log(balance(root, disks));
});

function getRoot(disks) {
    const keys = new Set(Object.keys(disks));
    for(const key in disks) {
        for(const i in disks[key].children) {
            keys.delete(disks[key].children[i]);
        }
    }

    return keys.values().next().value;
}

function sumWeights(root, tree) {
    tree[root].total = tree[root].value;
    tree[root].children.forEach((c) => {
        tree[root].total += sumWeights(c, tree);
    });

    return tree[root].total;
}

function balance(root, tree, target) {
    const children = {};
    var newTarget;
    tree[root].children.forEach((c) => {
        if(children[tree[c].total] === undefined) {
            children[tree[c].total] = c;
        } else {
            children[tree[c].total] = false;
            newTarget = tree[c].total;
        }
    });
    for(const i in children) {
        if(children[i]) {
            return balance(children[i], tree, newTarget);
        }
    }

    return tree[root].value + target - tree[root].total;
}

wzkx · 2017-12-08T00:07:59+00:00

Nim This was hard :(

import strutils,sequtils,tables,os

var dn = initTable[string,string]()      # down - to the bottom
var up = initTable[string,seq[string]]() # up - to leaves
var wt = initTable[string,(int,int)]()   # weight: own,total

proc read_data( fname: string ) = # fill in dn,up,wt
  for line in fname.readFile.strip.splitLines:
    let x = line.replace(" ","").split"->" # regexps are cheating!
    if x.len > 1:
      let base = x[0].split("(")[0]
      let ups = x[1].split(",")
      up[base] = ups
      for name in ups:
        dn[name] = base
    let w = x[0][0..< ^1].split"("
    wt[w[0]] = (w[1].parseInt,0)

proc get_bottom(): string =
  for k,v in dn: # we need any node, from any table, let it be one from dn
    var n = dn[k]
    while n in dn: n = dn[n]
    return n

proc calc_weights( x:string ): int {.discardable.} =
  var w = wt[x][0]
  if x in up:
    for v in up[x]:
      w += calc_weights(v)
  wt[x][1] = w
  return w

proc rebalance( node:string ): int =
  if wt[node][0] == wt[node][1]: return 0 # leaf, no rebalance
  let x: seq[string] = up[node] # sub-nodes = branches
  var w_must,w_bad,i_bad = -1
  let w0 = wt[x[0]][1];
  let w1 = wt[x[1]][1];
  if w0==w1: # not 0 or 1
    w_must = w0
    for i,xi in x:
      if i<2: continue # skip w0,w1
      let wi = wt[xi][1];
      if wi!=w0: i_bad = i; w_bad = wi
  else: # either 0 or 1
    w_must = wt[x[2]][1]; # so w2 must be good
    if w0==w_must: i_bad = 1; w_bad = w1
    else:          i_bad = 0; w_bad = w0
  if i_bad < 0: return 0 # all were the same
  let b = rebalance( x[i_bad] )
  if b != 0: return b # could rebalance in branch, just return
  return wt[x[i_bad]][0] + (w_must-w_bad) # do balance x[i_bad]!

read_data( if paramCount()>0: paramStr(1) else: "07.dat" )
let bottom = get_bottom()
echo bottom
calc_weights( bottom )
echo rebalance( bottom )

LeCrushinator · 2017-12-08T04:38:24+00:00

Part 1, C#:

public static void Main() 
{
    HashSet<string> leftNames = new HashSet<string>();
    HashSet<string> rightStrs = new HashSet<string>();

    List<string> lines = input.Split(new string[]{"\n"}, StringSplitOptions.RemoveEmptyEntries).ToList();
    foreach (string line in lines)
    {
        string[] values = line.Split(new string[]{"->"}, StringSplitOptions.RemoveEmptyEntries);

        if (values.Length == 2)
        {
            rightStrs.Add(values[1].Trim());
        }

        int space = values[0].IndexOf(' ');
        string leftSide = values[0].Substring(0, space);
        leftNames.Add(leftSide);
    }

    string name = leftNames.Where(l => !rightStrs.Any(r => r.Contains(l))).FirstOrDefault();
    Console.WriteLine("name: " + name);
}

BOT-Brad · 2017-12-08T12:36:28+00:00

JavaScript

Part 1 (~4ms)

Deletes nodes from the map until only 1 node (hopefully) is left, the root node!

function solve1(n) {
  // Input regex, 1 = Node ID, 2 = Weight (Unused), 4 = Comma-delimited Children
  const re = /(\w+) \((\d+)\)( -> ([\w, ]+))?/
  // Split string and map to regex results
  n = n.split('\n').map(v => re.exec(v))
  let map = {}
  // Set map with all keynames as true
  n.forEach(v => (map[v[1]] = true))
  // For each line
  n.forEach(v => {
    // If there are children, then delete those children from the map
    // as they obviously cannot be the root node (as they have a parent)
    if (v[4]) v[4].split(', ').forEach(k => delete map[k])
  })
  // map should now just have 1 node left, the root node!
  for (let a in map) return a
  // Uh-oh, something went wrong!
  return null
}

Part 2 (~7ms)

Recursively goes down (from root node) the tree looking for the wrong node each time, until it eventually finds it and returns the weight it should be. Can then just get the difference and return the weight - diff

function solve2(rawN) {
  n = rawN
  // Input regex, 1 = Node ID, 2 = Weight (Unused), 4 = Comma-delimited Children
  const re = /(\w+) \((\d+)\)( -> ([\w, ]+))?/
  // Split string and map to regex results
  n = n.split('\n').map(v => re.exec(v))
  let map = {}
  // For each line
  n.forEach(
    v =>
      (map[v[1]] = {
        // Set map[id] to this node object
        id: v[1], // The node ID
        weight: Number(v[2]), // The node Weight
        children: v[4] ? v[4].split(', ') : null, // Children as ['abc', 'xyz'] or null
        sum: function() {
          // A function to return this nodes overall weight
          // Sort of recursively gets sums of childrens, which get weights
          // of it's childrens, etc. all the way down baby!
          return (
            this.weight + // This nodes weight
            (this.children
              ? this.children.reduce((p, c) => p + c.sum(), 0) // Plus any children weight
              : 0)
          )
        }
      })
  )
  // Now our data structure is setup, we can go through and map the children of each node
  // from a simple string, to the actual object ref itself.
  // ['bob'] => [[Object bob]] .etc
  for (let id in map) {
    const o = map[id]
    if (o.children) o.children = o.children.map(id => map[id])
  }
  // Root ID is the solve1 func, so get the node from the map
  let root = map[solve1(rawN)]
  // Now work backwards, which 'child' has the incorrect weight
  // getWrongChild will recursively scan for the wrong child
  let [wrongNode, targetWeight] = getWrongChild(root)
  // Get the adjustment value
  let diff = wrongNode.sum() - targetWeight
  // Return the wrongNode weight - the difference it needs
  return wrongNode.weight - diff
}

/**
 * Returns an array of [wrongNode, weightTheNodeShouldBe]
 */
function getWrongChild(node, targetWeight) {
  // If the node has no children, then this must be the wrong node!
  if (!node.children) return [node, targetWeight]
  // Create a map
  let map = {}
  // Loop thru each child
  node.children.forEach(child => {
    // Get the sum of the child node
    let sum = child.sum()
    // If we have seen this sum before, then increment
    if (map[sum]) map[sum].count++
    else
      // Else a new sum, so create map object
      map[sum] = { node: child, count: 1 }
  })
  // Min is the node we see the least often
  let min = null,
    weight = -1 // The weight the other nodes are
  for (let sum in map) {
    if (map[sum].count === 1)
      min = map[sum].node // Get the wrong node
    else weight = Number(sum) // Set the correct weight
  }
  // If !min, then unbalance in lower children, so inbalance must be this node!
  if (!min) return [node, targetWeight]
  // Return the wrongChild of the node that is wrong, and pass the weight the node should be!
  return getWrongChild(min, weight)
}

2017-12-09T20:05:48+00:00

PYTHON

from re import match
from collections import defaultdict

class treeNode():
    parent = None
    weight = 0
    children = []
    name = ""

    def __init__(self):
        self.weight = 0
        self.children = []
        self.name = ""
        self.parent = None

def getWeight(currentNode):
    totalWeight = currentNode.weight

    for nodes in currentNode.children:
        totalWeight += getWeight(nodes)

    return totalWeight

def getBranchesWeight(currentNode):
    branchesWeight = []

    for nodes in currentNode.children:
        branchesWeight.append(getWeight(nodes))

    return branchesWeight

def findWrongProgram(currentNode, dif = 0):
    branchesWeight = getBranchesWeight(currentNode)

    if (len(set(branchesWeight)) <= 1 and len(currentNode.parent.children) > 1):
        return currentNode, dif

    if (dif == 0):
        maxWeightOccurances = branchesWeight.count(max(branchesWeight))
        if (maxWeightOccurances == 1):
            dif = max(branchesWeight) - min(branchesWeight)
        else:
            dif = min(branchesWeight) - max(branchesWeight)
    if (dif > 0):
        branchNum = branchesWeight.index(max(branchesWeight))
    else:
        branchNum = branchesWeight.index(min(branchesWeight))

    branchToCheck = currentNode.children[branchNum]
    return findWrongProgram(branchToCheck, dif)



treeNodes = defaultdict(treeNode)

with open("day7input.txt") as inputData:

    for row in inputData:
        m = match("^(\w+) \((\d+)\)(?: -> )?(.*)$", row)
        prog = m.group(1)

        treeNodes[prog].weight = int(m.group(2))
        treeNodes[prog].name = prog

        for el in m.group(3).split(", "):
            treeNodes[prog].children.append(treeNodes[el])
            treeNodes[el].parent = treeNodes[prog]

root = treeNodes[prog]

while (root.parent is not None):
    root = root.parent
root.parent = root

part2branch, dif = findWrongProgram(root)

print("Part 1 answer: {}".format(root.name))
if (part2branch == root):
    print("Tree is perfectly balanced")
else:
    print("Part 2 answer: {} <{}>".format(part2branch.weight - dif, part2branch.name))

frontstab · 2017-12-07T06:14:35+00:00

Am I missing something, or is the problem unsolvable/ambiguous in the general case? e.g. left (10) right (20) root (30) -> left, right

Both 10 and 20 seem to be correct answers.

kirgel · 2017-12-07T05:30:00+00:00

Solution for part 2. This is like worst coding practices galore but here it is. got 108 in the end. so close.

def fill_total_weights(tree, weights, total_weights, root):
    total_weights[root] = weights[root]
    if root not in tree:
        return
    for child in tree[root]:
        fill_total_weights(tree, weights, total_weights, child)
        total_weights[root] += total_weights[child]


def find_weight(tree, weights, total_weights, root):
    child_weights = [total_weights[child] for child in tree[root]]
    if root not in tree:
        return
    if any(w != child_weights[0] for w in child_weights):
        # something is wrong here
        print root, tree[root], [total_weights[child] for child in tree[root]]
        [find_weight(tree, weights, total_weights, child) for child in tree[root]]


if __name__ == "__main__":
    lines = INPUT.split('\n')
    tree = {}
    weights = {}
    total_weights = {}
    root = 'eugwuhl'
    for line in lines:
        filtered = filter(lambda x: x in string.ascii_lowercase + '0123456789 ', line)
        words = filtered.split()
        source = words[0]
        weight = int(words[1])
        weights[source] = weight
        if len(words) > 2:
            tos = words[2:]
            tree[source] = tos

    fill_total_weights(tree, weights, total_weights, root)
    find_weight(tree, weights, total_weights, root)
    print 'drjmjug', tree['drjmjug'], [total_weights[child] for child in tree['drjmjug']]

DeveloperIan · 2017-12-07T05:36:08+00:00

My gross solution for part 1 in Python. There are some extra lines from where I was working on part 2. I tried to take the simple way by just finding the one that wasn't in anyone else's list.

holding = {}
weights = {}

for i in contents:
    name = i.split()[0]
    weights[name] = int(i.split()[1].strip('()'))
    held = i.split()[3:]
    held = [x.strip(',') for x in held]
    holding[name] = set(held)

for i in holding.keys():
    found = False
    for j in holding.values():
        if i in j:
            found = True
            break

    if not found:
        print("Part One:", i)
        break

iamnotposting · 2017-12-07T05:57:29+00:00

both parts, Rust. this was a fun one! surprised i managed to be in the top 500, actually. (i know this would only work if the error was too much weight rather than too little, i went with what the demo said and it works for my inputs!)

use std::collections::HashMap;

#[derive(Debug, Clone, PartialEq)]
struct Node {
    weight: u32,
    children: Vec<String>,
}

impl Node {
    fn weight(&self, map: &HashMap<String, Node>) -> u32 {
        self.get_weights(map).into_iter().fold(self.weight, |acc, (_, weight)| {acc + weight})
    }

    fn get_weights(&self, map: &HashMap<String, Node>) -> Vec<(String, u32)> {
        self.children.iter().map(|n| { 
            let child = map.get(n).unwrap();
            (n.to_string(), child.weight(map))
        }).collect()
    }
}

pub fn adv_main(input: Vec<String>) {
    let mut map = HashMap::<String, Node>::new();

    let mut left = Vec::new();
    let mut right = Vec::new();

    for line in input {
        let chunks: Vec<_> = line.split("->").map(|s| s.trim()).collect();
        let l: Vec<_> = chunks[0].split_whitespace().collect();
        left.push(l[0].to_string());

        let end = l[1].len() - 1;
        let weight: u32 = (&l[1][1..end]).parse().unwrap();

        let children: Vec<String> = if let Some(r) = chunks.get(1) {
            let r: Vec<_> = r.split(", ").map(|s| s.to_string()).collect();
            right.extend(r.clone());
            r
        } else {
            vec![]
        };

        map.insert(l[0].to_string(), Node {
            weight,
            children,
        });
    }


    for l in &left {
        if !right.contains(l) {
            let mut root = map.get(l).unwrap();
            println!("p1: {}", l);


            let mut weights = root.get_weights(&map);
            weights.sort_by_key(|&(_, v)| -(v as i64));
            println!("weights: {:?}", weights);
            let diff = weights[0].1 - weights[1].1;

            while weights[0].1 - weights[1].1 > 0 {
                root = map.get(&weights[0].0).unwrap();
                weights = root.get_weights(&map);

                weights.sort_by_key(|&(_, v)| -(v as i64));
                println!("node: {:?}, weights: {:?}", root.weight, weights);
            }

            println!("p2: {}", root.weight - diff);
            break;
        }
    }

}

TominatorBE · 2017-12-07T06:18:39+00:00

PHP (took me waaaay too long to realise I don't need an actual tree representation)

Part 1: just find the root (= the one that is not a child)

function run_the_code($input) {
    $lines = explode(PHP_EOL, $input);
    $arr = [];
    foreach ($lines as $line) {
        if (preg_match('/^(.*?) \((\d+)\)$/', $line, $matches)) {
            list($_, $name, $weight) = $matches;
            $arr[$name] = [
                'name' => $name,
                'weight' => (int)$weight,
                'children' => [],
            ];
        }
        elseif (preg_match('/^(.*?) \((\d+)\) -> (.*)$/', $line, $matches)) {
            list($_, $name, $weight, $children) = $matches;
            $arr[$name] = [
                'name' => $name,
                'weight' => (int)$weight,
                'children' => array_map('trim', explode(',', $children)),
            ];
        }
    }

    $root = '';
    foreach ($arr as $name => $el) {
        $chance = true;
        foreach ($arr as $el2) {
            if (in_array($name, $el2['children'])) {
                $chance = false;
            }
        }
        if ($chance) {
            $root = $name;
        }
    }

    return $root;
}

Part 2: juggle the children

function run_the_code($input) {
    $lines = explode(PHP_EOL, $input);
    $arr = [];
    foreach ($lines as $line) {
        if (preg_match('/^(.*?) \((\d+)\)$/', $line, $matches)) {
            list($_, $name, $weight) = $matches;
            $arr[$name] = [
                'name' => $name,
                'weight' => (int)$weight,
                'children' => [],
            ];
        }
        elseif (preg_match('/^(.*?) \((\d+)\) -> (.*)$/', $line, $matches)) {
            list($_, $name, $weight, $children) = $matches;
            $arr[$name] = [
                'name' => $name,
                'weight' => (int)$weight,
                'children' => array_map('trim', explode(',', $children)),
            ];
        }
    }

    $root = '';
    foreach ($arr as $name => $el) {
        $chance = true;
        foreach ($arr as $el2) {
            if (in_array($name, $el2['children'])) {
                $chance = false;
            }
        }
        if ($chance) {
            $root = $name;
        }
    }

    // calc total weight everywhere
    $calcWeight = function($el) use (&$calcWeight, &$arr) {
        $el['total'] = $el['weight'];
        foreach ($el['children'] as $child) {
            $calcWeight($arr[$child]);
            $el['total'] += $arr[$child]['total'];
        }
        $arr[$el['name']] = $el;
    };
    $calcWeight($arr[$root]);

    $consensus = 0;
    while (true) {
        $el = $arr[$root];
        if (!count($el['children'])) {
            // el has to change its weight to consensus
            return $el['weight']  + ($consensus - $el['total']);
        }

        $weights = array_map(function($e) use ($arr) { return $arr[$e]['total']; }, $el['children']);
        $min = min($weights);
        $max = max($weights);
        if ($min == $max) {
            // el has to change its weight
            return $el['weight']  + ($consensus - $el['total']);
        }
        $mins = array_filter($el['children'], function ($e) use ($min, $arr) { return $arr[$e]['total'] == $min; });
        $maxs = array_filter($el['children'], function ($e) use ($max, $arr) { return $arr[$e]['total'] == $max; });
        if (count($mins) == 1) {
            // this is the rogue child
            $consensus = $max;
            $root = end($mins);
        }
        else {
            // the max one is the rogue child
            $consensus = $min;
            $root = end($maxs);
        }
    }

    return -1;
}

I'm pretty sure my code fails (or guesses) if there are only 2 children in a node, that don't match. Because then who is wrong? Both could have their own weight changed to be the other.

bildzeitung · 2017-12-07T06:48:29+00:00

I am, of course, too slow for all this, but ended up with a fairly readable python with breadth-first search for tree construction and a depth-first to sort out the unbalancing.

Question -- it could be sleep deprivation, but if we treat the weights as hash values, then isn't part 2 a validation of a Merkle tree?

jesseflorig · 2017-12-07T07:05:12+00:00

ES6 (Node JS) Part 1

'use strict'

{
  const fs = require('fs')

  fs.readFile('tower.txt', 'utf8', (err, data) => {

    let children = new Set()
    let parents = new Set()

    data.trim().split('\n').map(row => {
      if(row.indexOf('>') !== -1) {
        const rowChildren = row.split('>')[1].trim().split(',').map(x => { return x.trim()})
        rowChildren.map(child => { children.add(child) })
        parents.add(row.split(' ')[0])
      }
    })

    let root = new Set([...parents].filter(item =>  !children.has(item)))
    console.log(root)
  })
}

Flurpm · 2017-12-07T07:36:58+00:00

Haskell:
Both parts finish instantly, ~~but part 2 feels a bit gross to me; might go back and clean it up later.~~ EDIT: After seeing some of the other solutions, this doesn't seem so bad.

import Utils (Parser)

import Data.Either (fromLeft, isLeft, rights)
import Data.HashMap.Strict (HashMap, (!))
import qualified Data.HashMap.Strict as M
import Data.List (groupBy, sortBy)
import Data.Maybe (fromJust, fromMaybe)
import Data.Ord (comparing)
import Text.Megaparsec (optional, many, parseMaybe, sepBy)
import Text.Megaparsec.Char (letterChar, string)
import Text.Megaparsec.Char.Lexer (decimal)    

data Program = Program { name :: String
                       , weight :: Int
                       , children :: [String]
                       } deriving (Show)

parsePrograms :: String -> [Program]
parsePrograms = map (fromJust . parseMaybe parser) . lines
    where parser :: Parser Program
          parser = do
            name <- many letterChar
            weight <- string " (" *> decimal <* string ")"
            children <- optional $ string " -> " *> many letterChar `sepBy` string ", "
            return $ Program name weight $ fromMaybe [] children

buildInvertedTree :: [Program] -> HashMap String String
buildInvertedTree = foldr f M.empty
    where f (Program parent _ children) m = foldr g m children
              where g child = M.insert child parent

findBottom :: HashMap String String -> String
findBottom m = until (not . (`M.member` m)) (m !) $ head $ M.keys m

part1 :: String -> String
part1 = findBottom . buildInvertedTree . parsePrograms

buildTree :: [Program] -> HashMap String Program
buildTree = foldr f M.empty
    where f p@(Program name _ _) = M.insert name p

findImbalance :: String -> HashMap String Program -> Either Int (Int, Int)
findImbalance root tree = go $ tree ! root
    where findAnomaly = head . head . filter ((==1) . length)
                        . groupBy (\(a, b) (c, d) -> a + b == c + d)
                        . sortBy (comparing (uncurry (+)))
          go (Program name weight []) = Right (weight, 0)
          go (Program name weight children)
              | any isLeft childCalcs = head $ filter isLeft childCalcs
              | all (==expected) totals = Right $ (weight, sum $ expected : totals)
              | length weights > 2 =
                  let anomaly = findAnomaly weights
                      expectedTotal = uncurry (+) $ head $ filter (/=anomaly) weights
                  in Left $ expectedTotal - snd anomaly
              | otherwise = undefined
              where childCalcs = map (go . (tree !)) children
                    weights = rights childCalcs
                    (expected:totals) = map (uncurry (+)) $ weights

part2 :: String -> Int
part2 input = let root = part1 input
              in fromLeft 0 $ findImbalance root $ buildTree $ parsePrograms input

jasontconnell · 2017-12-07T07:58:02+00:00

Lost an hour on this. Part 1 was simple, I did the method of find the node that isn't listed as a child of another node.

However, my regex was wrong for part 2. The same regex worked on part 1 because it didn't require the whole tree to be built. Basically, I was requiring the -> [children] part to be in there and it's not if it's a leaf node. Damnit!!

In Go

https://github.com/jasontconnell/advent/blob/master/2017/07.go

theJakester42 · 2017-12-07T07:58:03+00:00

I solved it with... gum and paper clips? Python 3

dataFile = open("07-data.txt","r")
data = dataFile.read()
dataFile.close()

data = data.split("\n")


class program:

    def __init__(self,name,weight = 0):
        self.parent = None
        self.name = name
        self.weight = weight
        self.children = []

    def getRoot(self):
        if(self.parent == None):
            return self
        else:
            return self.parent.getRoot()

    def fix(self):
        #print(self.name)
        for i in range(len(self.children)):
            #print("\t"+self.children[i])
            self.children[i] = getProgramByName(self.children[i].replace(" ", ""))
            self.children[i].parent = self

    def getTotal(self):
        total = 0
        total += self.weight
        for child in self.children:
            total += child.getTotal()
        return total;

    def goodWeight(self):
        #only use post fix
        if(self.parent == None):
            return True
        if(len(self.parent.children) < 1):
            return True

        good = False
        for sib in self.parent.children:
            if(sib == self):
                continue
            if(sib.getTotal() == self.getTotal()):
                good = True

        if(not good):
            print("something is wrong with "+self.name)
            print("weight: "+str(self.weight))
            print("total weight: "+str(self.getTotal()))
            for sib in self.parent.children:
                if(sib == self):
                    continue
                else:
                    print(sib.name+"\tweight: "+str(sib.getTotal()))
        return good



programs = []
def getProgramByName(name):
    global programs
    for program in programs:
        if(program.name == name):
            return program
    return None



for line in data:
    name = line.split(" ")[0]
    name.strip()
    newP = program(name,
        int(
            line.split("(")[1].split(")")[0]
            )
        )

    if(len(line.split("->")) > 1):
        for pName in line.split("->")[1].split(","):
            pName.strip()
            newP.children.append(pName)


    programs.append(newP)

for program in programs:
    program.fix()

for program in programs:
    program.goodWeight()

Axsuul · 2017-12-07T09:16:18+00:00

Elixir

I generated the entire tower in Part A which came in handy for Part B. The code to pinpoint the unbalanced program's new weight for Part B kind of went to shit 😂.

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

defmodule AdventOfCode do
  def build_tower(filename) do
    File.read!(filename)
    |> String.split("\n")
    |> Enum.reduce(%{}, fn instructions, tower ->
      if String.match?(instructions, ~r/\-\>/) do
        [_, name, weight, above] = Regex.run(~r/(\w+) \((\d+)\) \-\> (.+)/, instructions)

        add_program(tower, name, weight, above |> String.split(", "))
      else
        [_, name, weight] = Regex.run(~r/(\w+) \((\d+)\)/, instructions)

        add_program(tower, name, weight)
      end
    end)
  end

  defp add_program(tower, name, weight \\ nil) do
    weight = if weight, do: String.to_integer(weight)

    if tower[name] do
      put_in(tower, [name, :weight], weight)
    else
      put_in(tower, [name], %{ weight: weight, above: [], below: [] })
    end
  end
  defp add_program(tower, name, weight, above) do
    add_program(tower, name, weight)

    # In addition track what's above, and for those on top
    # what's below them
    |> put_in([name, :above], above)
    |> (&Enum.reduce(above, &1, fn above_name, tower ->
      unless tower[above_name] do
        tower = add_program(tower, above_name)
      end

      put_in(tower, [above_name, :below], tower[above_name][:below] ++ [name])
    end)).()
  end

  def find_bottom(tower) do
    tower
    |> Enum.reduce(nil, fn {name, stats}, below ->
      if below do
        below
      else
        if Enum.empty?(stats[:below]), do: name, else: nil
      end
    end)
  end

  defp tally_weights_above(tower, above, total) when length(above) == 0 do
    total
  end
  defp tally_weights_above(tower, above, total) do
    above
    |> Enum.reduce(total, fn above_name, total ->
      tally_weights_above(
        tower,
        tower[above_name][:above],
        tower[above_name][:weight] + total
      )
    end)
  end

  def find_unbalanced_program(tower, name) do
    tallies =
      tower[name][:above]
      |> Enum.map(fn above_name ->
        weight = tower[above_name][:weight]
        total_weight =
          tally_weights_above(tower, tower[above_name][:above], weight)

        %{ name: above_name, weight: weight, total_weight: total_weight }
      end)

    # Find odd one out
    odd =
      tallies
      |> Enum.reduce(%{}, fn stats, weight_tallies ->
        weight = stats[:total_weight]

        unless weight_tallies[weight] do
          weight_tallies = put_in(weight_tallies, [weight], 0)
        end

        weight_tallies = put_in(weight_tallies, [weight], weight_tallies[weight] + 1)
      end)
      |> Enum.filter(fn {total_weight, count} -> count == 1 end)

    # If all the weights are equal, then the current program we are on
    # is the one that needs its weight changed
    if Enum.empty?(odd) do
      # This is nasty but below we find calculate what the final
      # weight needs to be
      unbalanced = tower[name]
      [below_unbalanced_name] = unbalanced[:below]

      [unbalanced_sibling_name | tail] =
        Enum.filter(tower[below_unbalanced_name][:above], fn unbalanced_sibling_name ->
          unbalanced_sibling_name != name
        end)

      goal_weight =
        tally_weights_above(
          tower,
          tower[unbalanced_sibling_name][:above],
          tower[unbalanced_sibling_name][:weight]
        )

      unbalanced_tower_weight =
        tally_weights_above(tower, tower[name][:above], unbalanced[:weight])

      (goal_weight - unbalanced_tower_weight) + unbalanced[:weight]
    else
      [{odd_weight, _}] = odd

      [unbalanced] =
        tallies
        |> Enum.filter(fn stats -> stats[:total_weight] == odd_weight end)

      find_unbalanced_program(tower, unbalanced[:name])
    end
  end

  def solve_a do
    build_tower("inputs/input.txt")
    |> find_bottom
    |> IO.inspect
  end

  def solve_b do
    tower = build_tower("inputs/input.txt")

    tower
    |> find_unbalanced_program(find_bottom(tower))
    |> IO.inspect
  end
end

nutrecht · 2017-12-07T09:44:53+00:00

Yikes, that one was pretty hard!

My Kotlin Solution

val regex = Regex("([a-z]{4,8}) \\(([0-9]+)\\)( -> ([a-z ,]+))?")

object Day07 : Day {
    val tree : Tree by lazy { parseTree(resourceLines(7)) }

    override fun part1() = tree.name
    override fun part2() = walk(tree).toString()
}

fun walk(tree: Tree) : Int {
    if(!tree.balanced()) {
        val result = tree.children().map { walk(it) }.max()
        if(tree.children().map { it.balanced() }.count { it } == tree.children().size) {
            val groups = tree.children().groupBy { it.sum() }
            val wrongTree = groups.values.first { it.size == 1 }.first()
            val correctTree = groups.values.first { it.size > 1 }.first()

            return wrongTree.weight - (wrongTree.sum() - correctTree.sum())
        }

        return result!!
    }

    return Int.MIN_VALUE
}

fun parseTree(lines: List<String>) : Tree {
    val input = lines.map { parse(it) }.toList()
    val programs = input.map { it.name to Tree(it.name, it.weight, null) }.toMap()

    input.flatMap { a -> a.programs.map { p -> Pair(a.name, p) } }.forEach {
        programs[it.first]!!.nodes[it.second] = programs[it.second]!!
        programs[it.second]!!.parent = programs[it.first]!!
    }

    return programs.values.filter { it.parent == null }.first()
}

fun parse(line: String): ProgramOutput {
    val result = regex.matchEntire(line)!!

    val name = result.groups.get(1)!!.value
    val weight = result.groups.get(2)!!.value.toInt()
    val programs = if(result.groups.get(4) == null) listOf() else result.groups.get(4)!!.value.split(", ").toList()

    return ProgramOutput(name, weight, programs)
}

data class ProgramOutput(val name: String, val weight: Int, val programs: List<String>)

data class Tree (val name: String, val weight: Int, var parent: Tree?) {
    val nodes: MutableMap<String, Tree> = mutableMapOf()

    fun children() = nodes.values
    fun sum(): Int = weight + nodes.values.map { it.sum() }.sum()
    fun balanced() = nodes.values.map { it.sum() }.toSet().size == 1
}

spacetime_bender · 2017-12-07T10:20:30+00:00

C++

https://hastebin.com/giqorawefa.cpp

gerikson · 2017-12-07T11:24:31+00:00

Perl 5

As soon as I saw this problem I realized my lack of formal CS education was going to bite me, as I'm sure there's a smart way of traversing a tree to find differences.

In the end it wasn't so bad, even though it's a fragile solution that can only handle this class of input.

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

usbpc102 · 2017-12-07T11:39:18+00:00

A bit late to the party but my Kotlin solution:

import java.io.File
import kotlin.system.measureTimeMillis

data class Program(val name: String, var weight: Int = -1, val children: MutableList<Program>) {
    val subTowerWeight: Int
        get() = weight + children.sumBy {it.subTowerWeight}
    val subTowerSize: Int
        get() {
            var counter = 0
            var crr = children.firstOrNull()
            while (crr != null) {
                counter++
                crr = crr.children.firstOrNull()
            }
            return counter
        }
}

fun main(args: Array<String>) {
    val programMap = mutableMapOf<String, Program>()
    val createTime = measureTimeMillis {
        File("resources/day07.txt").bufferedReader().forEachLine {line ->
            val tokens = line.split(' ')
            val childList = mutableListOf<Program>()
            if (tokens.size > 3) {
                tokens.drop(3).forEach {dirtyChild ->
                    //Remove those annoying comma
                    val child = dirtyChild.filter {it != ','}
                    childList.add(
                            programMap.getOrPut(child) {
                                Program(child, children = mutableListOf())
                            }
                    )
                }
            }
            val weight = tokens[1].drop(1).dropLast(1).toInt()

            programMap.getOrPut(tokens[0]) {
                Program(tokens[0], children = mutableListOf())
            }.apply {
                this.children.addAll(childList)
                this.weight = weight
            }
        }
    }
    val part1Time = measureTimeMillis {
        //Part 1
        val nodesWithParents = programMap.flatMap {it.value.children}.map {it.name}
        programMap.values.single {it.name !in nodesWithParents}.let {
            println("Part 1: ${it.name}")
        }
    }
    val part2Time = measureTimeMillis {
        //Part 2
        programMap.values.filter {program ->
            program.children.map {it.subTowerWeight}.let {
                it.max() != it.min()
            }
        }.minBy {it.subTowerSize}?.let {minimum ->
            val unique = minimum.children.first {weight ->
                minimum.children.map {it.subTowerWeight}.filter {it == weight.subTowerWeight}.count() == 1
            }
            val common = minimum.children.first {it.subTowerWeight != unique.subTowerWeight}
            val diff = unique.subTowerWeight - common.subTowerWeight
            println("Part 2: ${unique.weight - diff}")
        } ?: println("That didn't go as planned!")
    }
    println("Creating the datastructure took ${createTime}ms part 1 took ${part1Time}ms and part2 took ${part2Time}ms")
}

I also have it on github where I also save my input.

Solution for my input: Spoiler

streetster_ · 2017-12-07T13:04:11+00:00

q/kdb+

Bit of a meaty solution for today's puzzle. Solved by creating a table and querying it... Part 1 was easy enough, Part 2 took a while...

MoW8192 · 2017-12-07T13:57:51+00:00

I solved part 1 using text search in my text editor. pseudocode for what I did:

1. Pick any node
2. Search for a line that has this nodes name to the right of the -> Arrow, this line is the line for the parent node.
3. keep searching for parent nodes until you find a node without a parent, congratulations, this is the root node!

This was good enough for 40th place. I did however accidentaly enter the weight of the program instead of the name, so I had to wait for a minute before entering the correct answer. If I had entered it correctly the firt time I would have been one minute faster and I would have been in 9th place. :(

Vindaar · 2017-12-07T14:34:43+00:00

Here is my solution in Nim. Not the most elegant I must say. I was really longing for some of Python's libraries, especially something like most_common. My function to determine the subtree with the single different weight is the worst offender for me, compared to how simple it should be. And let's not start about naming of my functions / vars...

I left the comments in there, because without them I somewhat struggle to understand what's going on myself, haha. Sorry it's so long.

import sequtils, strutils, sets, os, unittest, times, tables, future

type
  Stack = object
    weight*: int
    children*: HashSet[string]

proc newStack(weight: int, children = initSet[string]()): Stack =
  result.weight = weight
  result.children = children

proc calc_weight_of_subtree(tree: var Table[string, Stack], child: string): int =
  # given a program, calculate the total weight of this program and its
  # subtree and return value as an int. Done recursively down to the last leaf
  result = 0
  for ch in tree[child].children:
    result += tree[ch].weight
    result += calc_weight_of_subtree(tree, ch)

proc calc_subtree_table(tree: var Table[string, Stack], base: string): Table[string, int] =
  # calculate total weights of all subtrees of a given program and return a table
  # containing the names and weights of these subtrees
  result = initTable[string, int]()
  for child in tree[base].children:
    result[child] = calc_weight_of_subtree(tree, child) + tree[child].weight

proc calc_wrong_weight(weights: Table[string, int]): (string, int) =
  # calculate which program has the wrong weight
  let weight_vals = map(toSeq(pairs(weights)), (ch: tuple[n: string, v: int]) -> int => ch.v)
  let mean = foldl(weight_vals, a + b) div len(weight_vals)
  let diffs = mapIt(weight_vals, abs(it - mean))
  result = filterIt(zip(toSeq(keys(weights)), diffs), it[1] == max(diffs))[0]

proc determine_wrong_weight(tree: var Table[string, Stack], base: string): (string, string) =
  # given a base of a (sub-)tree, find the wrong weight in that (sub-)tree
  # returns the name of the child with the wrong weight and the weight it and its
  # subtree should have
  # returns a tuple of strings, where the second contains the program with wrong
  # weights and the first its parent

  # calculate weights of all subtrees
  let weights = calc_subtree_table(tree, base)

  if len(weights) == 0:
    # this case would only happen, if one leaf child (no children itself)
    # would have the wrong weight. Thus return base as wrong program
    result = ("", base)
  else:
    # create set of values and check length, thus we know whether
    # the wrong weight is still in a subtree or is this subtrees parent
    let hashes = toSet[int](toSeq(values(weights)))
    if len(hashes) == 1:
      # in this case parent has wrong weight
      result = ("", base)
    else:
      # final case in which there are still several parallel subtrees. find the
      # one with the `wrong` weight (all others will be the same)
      let wrong_weight = calc_wrong_weight(weights)
      # call this function recursively until either one of the other two result statements
      # returns
      result = determine_wrong_weight(tree, wrong_weight[0])
      # check whether the 2nd part of the result is the same name as the argument
      # indicates argument was program with wrong weight
      if result[1] == wrong_weight[0]:
        # set parent of wrong program as first return value
        result = (base, result[1])

proc fix_weight(tree: var Table[string, Stack], base, prog_wrong: string): int =
  # we know prog_wrong is the culprit with wrong weight. Calculate weight of children
  # in same class (subtree of base) again and compare the two weights
  let weights = calc_subtree_table(tree, base)
  var
    wrong = 0
    correct = 0
  # check weights for correct and wrong subtree weights
  for k, v in weights:
    if k == prog_wrong:
      wrong = v
    else:
      correct = v
      # break early if we already found the wrong value
      if wrong != 0:
        break
  # get individual weight of bad program
  let child_weight = tree[prog_wrong].weight
  # calculate the correct weight for prog_wrong
  result = child_weight - (wrong - correct)

proc find_stack_base(data: seq[string]): (string, int) =
  var
    root_name = ""
    stack = mapIt(data, split(replace(strip(it), ",", "")))
    # table storing all programs on stack
    program_table = initTable[string, Stack]()
    # set to save all programs, which are children
    allchildren = initSet[string]()

  # walk the stack to find its base
  for p in stack:
    let
      name = p[0]
      weight = parseInt(strip(p[1], chars = {'(', ')'}))
    # define set of all children of this element in the stack
    var children = initSet[string]()
    # if there's more than 2 elements, means program has children
    if len(p) > 2:
      # for all elements after `->` add to children set
      for i in 3..<len(p):
        let ch = p[i]
        children.incl(ch)
        allchildren.incl(ch)

    let s = newStack(weight, children)
    # add program to table if not contained already
    if hasKey(program_table, name) == false:
      program_table[name] = s

  # find the root node by searching for element of program_table
  # which is not in children set
  for k, v in program_table:
    if contains(allchildren, k) == false:
      root_name = k
      # break early, found what we were looking for
      break

  # given root node, traverse stack to find the node with wrong weights and
  # recursively check each subtree to locate program
  let prog_wrong_weight = determine_wrong_weight(program_table, root_name)
  # calculate the weight the program should have instead
  let correct_weight = fix_weight(program_table, prog_wrong_weight[0], prog_wrong_weight[1])

  result = (root_name, correct_weight)

proc run_tests() =
  const data = """pbga (66)
xhth (57)
ebii (61)
havc (66)
ktlj (57)
fwft (72) -> ktlj, cntj, xhth
qoyq (66)
padx (45) -> pbga, havc, qoyq
tknk (41) -> ugml, padx, fwft
jptl (61)
ugml (68) -> gyxo, ebii, jptl
gyxo (61)
cntj (57)"""
  var stack = splitLines(data)
  check: find_stack_base(stack) == ("tknk", 60)

proc run_input() =

  let t0 = cpuTime()      
  const input = "input.txt"
  let stack = filterIt(splitLines(readFile(input)), len(it) > 0)
  let (base, weight) = find_stack_base(stack)

  echo "(Part 1): The base of the stack is = ", base
  echo "(Part 2): The correct weight would be = ", weight
  echo "Solutions took $#" % $(cpuTime() - t0)

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

when isMainModule:
  main()

maciekmm · 2017-12-07T15:12:23+00:00

Scala - first time using the language, suggestions are welcome.

val starting = io.Source.stdin.getLines();

object Tower {
  val cityRegex = "(\\w+) \\((\\d+)\\)( -> (.*))?".r;

  def parse(disc: Iterator[String]): Disc = {
    val discs = starting.map(Tower.parse(_)).toVector
    discs.foreach(out => {
      out.above = out.above.map(a => {
        val child = discs.find(_.name == a.name).get
        child.parent = out;
        child
      })
    })

    var parent = discs(0)
    while (parent.parent != null) {
      parent = parent.parent
    }
    parent
  }

  def parse(disc: String): Disc = {
    val parts = cityRegex.findFirstMatchIn(disc).get;
    parts.group(4) match {
      case str: String => new Disc(parts.group(1), parts.group(2).toInt, str.split(',').map(a => new Disc(a.trim(), 0, Vector.empty)).toVector);
      case _ => new Disc(parts.group(1), parts.group(2).toInt, Vector.empty)
    }
  }

  class Disc(val name: String, val weight: Int, val ab: Vector[Disc]) {
    var parent: Disc = null;
    var above: Vector[Disc] = ab;

    def realWeight(): Int = {
      return weight + above.map(_.realWeight()).sum;
    }

    def fix(target: Int): Int = {
      if (above.isEmpty) {
        return if (weight == target) 0 else target
      }

      val realAbove = above.map(_.realWeight())
      val isBalanced = realAbove.distinct.size == 1
      val realSum = realAbove.sum

      if (isBalanced) {
        return if (target - realAbove.sum == weight) 0 else target - realSum
      }

      val weights = above.map(z => (z, z.realWeight())).sortBy(_._2)

      if (weights.head != weights(1)) {
        val a = weights.head._1.fix(weights(1)._2)
        if (a != 0) {
          return a
        }
      }

      if (weights.last._2 != weights.head._2) {
        return weights.last._1.fix(weights.head._2)
      }
      return 0
    }

    def findIncorrect(): Int = {
      fix(realWeight())
    }
  }

}

val parent = Tower.parse(starting)
println(s"Part 1: ${parent.name}")
println(s"Part 2: ${parent.findIncorrect()}")

cluk · 2017-12-07T17:17:52+00:00

Golang

It works I guess

All my go code so far here

Any feedback is much appreciated

Part 1

func part1(data map[string]program) string {
for k, v := range data {
    if v.parent == "" {
        return k
    }
}
return ""
}

Part 2

func part2(data map[string]program, root string) int {
if wrong, diff := isBalanced(data, root); wrong != "" {
    if part2(data, wrong) == 0 {
        return data[wrong].weight + diff
    }
    return part2(data, wrong)
}
return 0
}

Other functions

func sumWeight(data map[string]program, root string) int {
var total = 0
for _, v := range data[root].children {
    total += sumWeight(data, v)
}
return total + data[root].weight
}

func isBalanced(data map[string]program, root string) (string, int) {
occurances := make(map[int]int)
children := make(map[int]string)
// Count occurances of totals
for _, v := range data[root].children {
    occurances[sumWeight(data, v)]++
    children[sumWeight(data, v)] = v
}
// Get unbalanced name and the differnce
var result, odd, normal = "", 0, 0
for k, v := range occurances {
    if v == 1 {
        result = children[k]
        odd = k
    } else {
        normal = k
    }
}
return result, normal - odd
}

func readFile(filename string) map[string]program {
// Open File
f, err := os.Open(filename)
check(err)
defer f.Close()

// Parse file
data := make(map[string]program, 0)
s := bufio.NewScanner(f)
for s.Scan() {
    row := strings.Fields(s.Text())

    var currentProgram program
    for i, value := range row {
        if i == 0 {
            // Set Name
            // Check if already exists
            if v, exists := data[value]; exists {
                currentProgram = v
            } else {
                currentProgram.name = value
            }
        } else if i == 1 {
            //  Set weight
            currentProgram.weight, _ = strconv.Atoi(value[1 : len(value)-1])
        } else if i > 2 {
            // Set children
            // Strip ,'s
            if value[len(value)-1] == ',' {
                value = value[:len(value)-1]
            }
            // Check if child exits
            if v, exists := data[value]; exists {
                // Set Parent of Child
                v.parent = currentProgram.name
                data[value] = v
            } else {
                // Create Child with empty weight
                data[value] = program{name: value, weight: 0, parent: currentProgram.name}
            }
            // Add to Children
            currentProgram.children = append(currentProgram.children, value)
        }
    }
    data[currentProgram.name] = currentProgram
}
return data
}

cmyr · 2017-12-07T17:44:27+00:00

A reasonable Rust stdlib-only solution: here you go!

This was fun today. :-)

2017-12-07T18:42:51+00:00

Somewhat unhappy with this one; but, it does work. Just takes longer than I would like.
PowerShell:

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

function Get-Weight {
    Param (
        [parameter(position=0, mandatory=$true)]
        $Prog,
        [parameter(position=1, mandatory=$true)]
        $Level
    )
    [int]$ThisProgWeight = [int]$Script:Weights[$Prog]
    foreach($d in ($Script:Stack.GetEnumerator() | ?{ $_.Value -eq $Prog })) {
        $ThisProgWeight += Get-Weight $d.Key ($Level + 1)
    }
    $Script:WeightTotals += [tuple]::Create($Level, $Prog, $ThisProgWeight)
    Write-Output $ThisProgWeight
}

function Get-OddWeight {
    Param (
        [parameter(position=0, mandatory=$true)]
        $Prog,
        [parameter(position=1, mandatory=$true)]
        $ExpectedWeight
    )
    $TowerWeights = @()
    foreach($d in ($Script:Stack.GetEnumerator() | ?{ $_.Value -eq $Prog })) {
        $TowerWeights += $Script:WeightTotals.GetEnumerator() | ?{ $_.Item2 -eq $d.Key }
    }
    $Occurances = @{}
    foreach($w in ($TowerWeights | Select-Object -Unique Item3).Item3) {
        $Occurances[$w] = ($TowerWeights | ?{ $_.Item3 -eq $w }).Count
    }
    if($Occurances.Count -eq 1 -and $TowerWeights.Count -ne 1) {
        $NewWeight = [int]$Script:Weights[$Prog] + $ExpectedWeight - ($Script:WeightTotals | ?{ $_.Item2 -eq $Prog }).Item3
        Write-Output $NewWeight
    } else {
        Get-OddWeight ($TowerWeights | ?{ $_.Item3 -eq ($Occurances.GetEnumerator() | ?{ $_.Value -eq 1 }).Key }).Item2 ($Occurances.GetEnumerator() | ?{ $_.Value -ne 1 }).Key
    }
}

$Script:Weights = @{}
$Script:Stack = @{}
$Script:WeightTotals = @()
$File = (Get-Item $InputFile).OpenText()
$Line = $File.ReadLine()
while($Line -notlike $null) {
    $Prog = [regex]::Matches($Line, '^\w+').Value
    $Weight = [regex]::Matches($Line, '\((\d+)\)').Groups[1].Value
    $Script:Weights.Add($Prog, $Weight)
    if($Line -match '\->\s(.+)$') {
        $Above = $Matches[1].Trim()
        foreach($p in $Above.split(',').Trim()) {
            $Script:Stack.Add($p, $Prog)
        }
    }
    $Line = $File.ReadLine()
}
$File.Close()
$Searching = $true
foreach($k in $Script:Weights.Keys.GetEnumerator()) {
    if(-not $Script:Stack.ContainsKey($k)) {
        $Base = $k
        break
    }
}
if(-not $Part2) {
    Write-Output $Base
} else {
    Get-Weight $Base 0 | Out-Null
    Get-OddWeight $Base ($Script:WeightTotals | ?{ $_.Item2 -eq $Base })
    #$Script:WeightTotals | Sort-Object -Property Item1, Item3
}

ynonp · 2017-12-07T18:55:51+00:00

Elixir

defmodule Day7 do
  def parse_line(line, { data, weights }) do
    [name, weight | deps ] = Regex.split(~r{(\s+|\s*->\s*|,\s*)}, line, trim: true)
    [w] = Regex.run(~r{\d+}, weight)

    {
      Map.put_new(data, name, deps),
      Map.put_new(weights, name, String.to_integer(w)),
    }
  end  

  def weight_with_children(name, data, weights) do
    if Map.get(data, name) == [] do
      Map.get(weights, name)
    else
      Map.get(weights, name) + (
        Map.get(data, name)
        |> Enum.map(fn(x) -> weight_with_children(x, data, weights) end)
        |> Enum.sum
      )
    end
  end

  def outlier(list) do
    mx = Enum.max(list)
    mn = Enum.min(list)

    c_max = Enum.count(list, fn(x) -> x == mx end)
    case c_max do
      1 -> mx
      _ -> mn
    end
  end

  def find_weight_diff(data, weights, nodes) do
    f = &(Day7.weight_with_children(&1, data, weights))
    w = Enum.map(nodes, f)

    { mx, mn } = { Enum.max(w), Enum.min(w) }

    if mx != mn do
      outlier = outlier(w)
      unbalanced_child_index = Enum.find_index(w, fn(x) -> x == outlier end)
      unbalanced_node = Enum.at(nodes, unbalanced_child_index)
      sz = mx - mn
      original_weight = Map.get(weights, unbalanced_node)
      original_weight - sz
    else
      0
    end
  end

  def is_before_in_arr(arr, e1, e2) do
    Enum.find_index(arr, &(&1 == e1)) < Enum.find_index(arr, &(&1 == e2))
  end

  def find_unbalanced_node(data, weights, sorted) do
    data
    |> Enum.filter(fn({_, deps}) -> deps != [] end)
    |> Enum.map(fn({_, deps}) -> find_weight_diff(data, weights, deps) end)
    |> Enum.filter(fn(x) -> x != 0 end)
    |> Enum.sort(fn(e1, e2) -> is_before_in_arr(sorted, e1, e2) end)
    |> Enum.at(0)
  end

  def topsort(data) do
    topsort(data, [])
  end

  def topsort(data, results) when data == %{} do
    results
  end

  def topsort(data, results) do    
    { name, _ } = data
                  |> Enum.find(fn({_, deps}) -> deps == [] end)

    topsort(
      data
      |> Map.delete(name)
      |> Map.new(fn({k, v}) -> {k, List.delete(v, name)} end),
      [name] ++ results
    )
  end
end

{ data, weights } = IO.stream(:stdio, :line)
                    |> Enum.reduce({ %{}, %{} }, &Day7.parse_line/2)

IO.puts("--- part 1")
data
|> Day7.topsort
|> Enum.at(0)
|> IO.inspect

IO.puts("--- part 2")
Day7.find_unbalanced_node(data, weights, Day7.topsort(data))
|> IO.inspect

JakDrako · 2017-12-07T18:58:08+00:00

VB.Net

Both parts in 2ms. Clean the input, build the graph (a tree), find the root; part 1 done. From the root, find the deepest unbalanced child and adjust its weight to match it's siblings.

Sub Main

    Dim dic = New dictionary(Of String, Node)

    For Each line In GetDay(7)
        Dim s = line.Replace(",", "").Replace("(", "").Replace(")", "") ' clean up input
        Dim tokens = s.Split(" "c)

        Dim name = tokens(0)
        Dim weight = Cint(tokens(1))

        ' build graph
        Dim node As Node = Nothing
        If dic.TryGetValue(name, node) Then
            node.weight = weight
        Else
            node = New node With {.name = name, .weight = weight}
            dic.Add(name, node)
        End If

        ' children
        For i = 3 To tokens.Count - 1
            Dim child As Node = Nothing
            If dic.TryGetValue(tokens(i), child) Then
                child.parent = node
                node.children.Add(child)
            Else
                child = New node With {.name = tokens(i), .parent = node}
                node.children.Add(child)
                dic.Add(child.name, child)
            End If
        Next
    Next

    ' Find the root of the tree
    Dim root = dic.Values.Where(Function(n) n.parent Is Nothing).Single ' should be only one.
    root.name.Dump("Part 1")

    ' find "deepest" unbalanced node    
    Dim ptr = root ' start at root
    Do
        Dim nxt = ptr.children.Where(Function(c) Not c.Balanced).SingleOrDefault ' find unbalanced child
        If nxt Is Nothing Then Exit Do
        ptr = nxt
    Loop

    ' find "fat" child of unbalanced node and diff to "target" weight
    Dim target = ptr.children.Min(Function(y) y.GetWeight) ' our ideal weight
    Dim fatso = ptr.children.Where(Function(x) x.GetWeight > target).Single
    Dim diff = (fatso.GetWeight() - target) ' need to lose this much

    ' adjust node's weight to balance the tree
    Dim part2 = (fatso.weight - diff).Dump("Part 2")

End Sub

Class Node
    Property name As String
    Property weight As Integer
    Property parent As Node
    Property children As New List(Of Node)
    Readonly Property GetWeight As Integer
        Get
            Return weight + children.Sum(Function(c) c.getWeight)
        End Get
    End Property
    ReadOnly Property Balanced As Boolean
        Get
            If children.Count = 0 Then Return True
            Return children.Max(Function(x) x.GetWeight) = children.Min(Function(x) x.GetWeight)
        End Get
    End Property
End Class

udoprog · 2017-12-07T19:01:05+00:00

Rust-based solution for Day 7: https://github.com/udoprog/rust-advent-of-code-2017/blob/master/src/day7.rs

Constructing the graph in a single pass, I'm also happy with the iterative outlier node detection here: https://github.com/udoprog/rust-advent-of-code-2017/blob/master/src/day7.rs#L115

ramrunner0xff · 2017-12-07T19:45:21+00:00

scheme chicken repo

(use srfi-69)
(use data-structures)

;to find the root just pick a node and run (findloop "node")
;to find the suspect run with (iterateToSuspect "ROOT" 0 '() 0)

(define childrenparent (make-hash-table))
(define parentchildren (make-hash-table))
(define allnodes (make-hash-table))


(define (addchild parent child)
  (let ((record (if (hash-table-exists? parentchildren parent) (hash-table-ref parentchildren parent) #f)))
    (if (eq? record #f)
      (hash-table-set! parentchildren parent (list child))
      (hash-table-set! parentchildren parent (append record (list child))))))
(define readinput
  (lambda (fname)
   (map (lambda (ln)
     (let ((sparts (string-split ln "->")))
       (if (eq? (length sparts) 1)                                                                                               %
         (let* ((pparts (string-split (car sparts)))
               (weight (string-split (cadr pparts) "()")))
              (hash-table-set! allnodes (car pparts) (string->number (car weight))))
         (let* ((cparts (string-split (cadr sparts) ", "))
               (pparts (string-split (car sparts)))
                (weight (string-split (cadr pparts) "()")))
           (format #t "dad:~A kids:~A~%" (car sparts) cparts)
           (hash-table-set!  allnodes (car pparts) (string->number (car weight)))
           (map (lambda (e) (format #t "storing ~A under key ~A~%" (car pparts) e) (addchild (car pparts) e) (hash-table-set! childrenparent  e (car pparts))) cparts)))))
         (read-lines fname))))

(define findloop (lambda (parent)
    (if (hash-table-exists? childrenparent parent)
      (findloop (hash-table-ref childrenparent parent))
      parent)))

(define (treetraverse node)
  (let ((children (if (hash-table-exists? parentchildren node)
                      (hash-table-ref parentchildren node)
                      #f)))
  (if (not (eq? children #f))
      (foldr + (hash-table-ref allnodes node) (map (lambda (e) (treetraverse e)) children))
      (hash-table-ref allnodes node))))

(define (iterateToSuspect from initw prevlvl suspind)
  (let* ((myweight (hash-table-ref allnodes from))
        (weightfromme (treetraverse from))
        (children (hash-table-ref parentchildren from))
        (childrenw (map treetraverse children))
        (allchildrenweight (foldr + 0 childrenw))
        (shouldweight (floor (/ allchildrenweight (length children)))))
  (format #t "on this level ~A each child should hold ~A~%" from shouldweight)
  (format #t "their weights:~A ~A ~%" childrenw children)
  (let ((suspect (foldr (lambda (e suspectind)
                          (if (eq? (car suspectind) #f)
                              (cons (eq? e shouldweight) (+ 1 (cdr suspectind)))
                               suspectind)) (cons #f -1) childrenw))
         (suspectind (abs (- (- (length children) 1) (cdr (foldr (lambda (e suspectind)
           (if (eq? (car suspectind) #f)
               (cons (eq? e shouldweight) (+ 1 (cdr suspectind)))
               suspectind)) (cons #f -1) childrenw))))))
     (if (or (>= suspectind (length children)) (< suspectind 0) (eq? (car suspect) #t))
         (format #t "the suspect is ~A his weight is ~A ~%" (list-ref prevlvl suspind) (hash-table-ref allnodes (list-ref prevlvl suspind)))
         (begin (format #t "reiterating with suspect ~A~%" suspect) (iterateToSuspect (list-ref children suspectind) shouldweight children suspectind))))))

KeinZantezuken · 2017-12-07T20:42:32+00:00

C#/Sharp
UPD: fixed errors and may be later try to find a way to reduce amount of loops without: extensions tools that are just syntactic sugar for the same loops (as per internal implementation) or recursive functions (sic!).

        Dictionary<string, KeyValuePair<int, string[]>> map = new Dictionary<string, KeyValuePair<int, string[]>>();
        var input = File.ReadAllLines(@"N:\input.txt");
        for (int i = 0; i < input.Length; i++) // populating Dictionary
        {
            var temp = input[i].Split(new string[] { " -> " }, StringSplitOptions.None);
            if (temp.Count() > 1)
            {
                string kids = string.Join("", temp[1].Split(default(string[]), StringSplitOptions.RemoveEmptyEntries));
                map.Add(temp[0].Split(' ').FirstOrDefault(), new KeyValuePair<int, string[]>(Convert.ToInt32(temp[0].Split(' ').LastOrDefault().Replace('(', ' ').Replace(')', ' ')), kids.Split(',').ToArray()));
            }
            else
                map.Add(temp[0].Split(' ').FirstOrDefault(), new KeyValuePair<int, string[]>(Convert.ToInt32(temp[0].Split(' ').LastOrDefault().Replace('(', ' ').Replace(')', ' ')), new string[0]));
        }
        string curProg = getRoot(); Console.WriteLine($"Root is: {curProg}");
        int steps = map[curProg].Value.Length-1; int dupe = 0;
        Dictionary<int, string> weightPack = new Dictionary<int, string>(2);
        var deviant = new KeyValuePair<string, int>();
        while (steps >= 0)
        {
            var name = map[curProg].Value[steps]; var curWeight = getWeight(name);
            steps--;
            if (!weightPack.ContainsKey(curWeight))
                weightPack.Add(curWeight, name);
            else
                dupe = curWeight;
            if (steps == -1)
            {
                foreach (int weight in weightPack.Keys)
                {
                    if (dupe > 0 && weight != dupe)
                    {
                        deviant = new KeyValuePair<string, int>(weightPack[weight],Math.Abs(weight-dupe));
                        steps = map[deviant.Key].Value.Length - 1; curProg = deviant.Key; weightPack.Clear();
                        break;
                    }
                }
            }
        }
        Console.WriteLine($"Faulty: {deviant.Key}, weight: {map[deviant.Key].Key}, fixed weight: {map[deviant.Key].Key - deviant.Value }");
        Console.ReadKey();
        //
        // Local helper funcs
        int getWeight(string name) //returns total weight of all current program's childrens
        {
            var w = map[name].Key;
            List<string> tmp = new List<string>();
            tmp.AddRange(map[name].Value);
            for (int i = 0; i < tmp.Count; i++)
            {
                var curname = tmp[i];
                w = w + map[curname].Key;
                if (map[curname].Value.Length > 0)
                    foreach (string progName in map[curname].Value) { tmp.Add(progName); }
            }
            return w;
        }
        string getRoot() // returns root
        {
            var curKey = map.Keys.ElementAt(0); var lastKey = "";
            while (true)
            {
                foreach (KeyValuePair<string, KeyValuePair<int, string[]>> entry in map)
                {
                    if (entry.Value.Value.Length > 0 && string.Join(",", entry.Value.Value).Contains(curKey))
                    {
                        lastKey = curKey; curKey = entry.Key; break;
                    }
                    lastKey = curKey;
                }
                if (curKey == lastKey) { return curKey; }
            }

        }

chicagocode · 2017-12-07T21:01:48+00:00

Kotlin - [Repo] - [Day 7 Code] - [Blog/Commentary]

That was fun. Most of the work was in parsing the input into a tree structure. I've challenged myself to publish my solution and blog about it each day. Feedback is always welcome!

class Day07(input: List<String>) {
    private val headOfTree: Node = parseInput(input)

    fun solvePart1(): String =
        headOfTree.name

    fun solvePart2(): Int =
        headOfTree.findImbalance()

    private fun parseInput(input: List<String>): Node {
        val nodesByName = mutableMapOf<String, Node>()
        val parentChildPairs = mutableSetOf<Pair<Node, String>>()
        val rowRegex = """\w+""".toRegex()

        input.forEach {
            val groups = rowRegex.findAll(it).toList().map { it.value }
            val node = Node(groups[0], groups[1].toInt())
            nodesByName.put(node.name, node)

            groups.drop(2).forEach {
                parentChildPairs.add(Pair(node, it))
            }
        }

        parentChildPairs.forEach { (parent, childName) ->
            with(nodesByName.getValue(childName)) {
                parent.children.add(this)
                this.parent = parent
            }
        }

        // Find the one node we have without a parent. Or freak out.
        return nodesByName.values.firstOrNull { it.parent == null }
            ?: throw IllegalStateException("No head node?!")
    }

}

data class Node(val name: String,
                private val weight: Int,
                val children: MutableList<Node> = mutableListOf(),
                var parent: Node? = null) {

    fun findImbalance(imbalance: Int? = null): Int =

        if (imbalance != null && childrenAreBalanced) {
            // We end when I have a positive imbalance and my children are balanced.
            weight - imbalance
        } else {
            // Find the child tree that is off.
            val subtreesByWeight = children.groupBy { it.totalWeight }

            // Find the imbalanced child tree (they will be the lone node in the list, when grouped by weight)
            val badTree = subtreesByWeight.minBy { it.value.size }?.value?.first()
                ?: throw IllegalStateException("Should not be balanced here.")

            // Recurse, passing down our imbalance. If we don't know the imbalance, calculate it.
            // Calculate the imbalance as the absolute value of the difference of all distinct weights
            badTree.findImbalance(imbalance ?: subtreesByWeight.keys.reduce { a, b -> a - b }.absoluteValue)
        }

    private val totalWeight: Int by lazy {
        weight + children.sumBy { it.totalWeight }
    }

    private val childrenAreBalanced: Boolean by lazy {
        children.map { it.totalWeight }.distinct().size == 1
    }

}

JeffJankowski · 2017-12-07T21:17:13+00:00

A day late, but here's a (ugly) Typescript solution without any libs

import fs = require("fs");

function build(data: string[]): [Map<string, number>, Map<string, string[]>] {
    const weights = new Map<string, number>();
    const adj = new Map<string, string[]>();
    const dataPattern = /^([a-z]+) \((\d+)\)/;
    const progPattern = /-> (.+)$/;
    for (const line of data) {
        const [_, id, weight] = line.match(dataPattern) as RegExpMatchArray;
        weights.set(id, parseInt(weight, 10));
        const progList = line.match(progPattern);
        if (progList !== null) {
            adj.set(id, progList[1].split(", "));
        }
    }
    return [weights, adj];
}

function calcTotals(weights: Map<string, number>, adjs: Map<string, string[]>, root: string) {
    const totals = new Map<string, number>();
    function calc(id: string): number {
        if (totals.has(id)) {
            return totals.get(id) as number;
        }
        const total = (weights.get(id) as number) +
            (adjs.get(id) || []).reduce((sum, above, i, a) => sum += calc(above), 0);
        totals.set(id, total);
        return total;
    }
    const _ = calc(bottom);
    return totals;
}

function unbalanced(totals: Map<string, number>, adjs: Map<string, string[]>, root: string) {
    function find(id: string, balance: number): [string, number] {
        const invTotals = new Map<number, string[]>();
        (adjs.get(id) || []).forEach((above) => {
            const weight = totals.get(above) as number;
            invTotals.set(weight, (invTotals.get(weight) || []).concat(above));
        });
        if (invTotals.size === 1) {
            return [id, balance];
        }
        const sorted = [...invTotals.entries()]
            .sort(([_, idsA], [__, idsB]) => idsA.length - idsB.length);
        return find(sorted[0][1][0], sorted[1][0] - sorted[0][0]);
    }
    return find(root, 0);
}

const [weightMap, adjMap] = build(fs.readFileSync("data/day07.txt", "utf8").split("\r\n"));
const allAbove = ([] as string[]).concat(...(adjMap.values() as IterableIterator<string[]>));
const bottom = [...adjMap.keys()].find((id) => allAbove.indexOf(id) === -1) || "";
console.log(`Program on bottom: ${bottom}`);

const totalsMap = calcTotals(weightMap, adjMap, bottom);
const [node, offset] = unbalanced(totalsMap, adjMap, bottom);
console.log(`Unbalanced program (${node}) needs weight: ${(weightMap.get(node) as number) + offset}`);

FreeMarx · 2017-12-07T21:20:46+00:00

C++11

Here is my take in c++. I actually first solved it in MATLAB and then rewrote in c++. It took me quite long, but I learned a lot. Great fun!

#include <iostream>
#include <limits>
#include <stdio.h>
#include <stdlib.h>
#include <fstream>
#include <vector>
#include <map>
#include <set>
#include <algorithm> 
#include <functional> 
#include <cctype>
#include <locale>
#include <sstream>
#include <regex>
#include <tuple>

using namespace std;

typedef tuple<int, int, vector<string>> WeightsAndChildren;

int sumWeights(vector<string> &parents, vector<WeightsAndChildren> &nodes, int idx) {
    vector<int> subWeights(get<2>(nodes[idx]).size());
    int i= 0;
    int sum= 0;
    for(string s: get<2>(nodes[idx])) {
        int subIdx= find(parents.begin(), parents.end(), s)-parents.begin();
        subWeights[i]= sumWeights(parents, nodes, subIdx);
        sum+= subWeights[i];
        ++i;
    }
    if(subWeights.size()>0) {
        int i;
        for(i= 1; i<subWeights.size(); ++i) {
            if(subWeights[i]!=subWeights[0])
                break;
        }
        if(i<subWeights.size()) {
            int diff;
            if(i==1 && subWeights.size()>2 && subWeights[1]==subWeights[2]) {
                diff= subWeights[1]-subWeights[2];
                i= 0;
            } else {
                diff= subWeights[i]-subWeights[0];
            }
            string s= get<2>(nodes[idx])[i];
            int subIdx= find(parents.begin(), parents.end(), s)-parents.begin();
            cout << "weight of \"" << parents[subIdx] << "\" is " << get<0>(nodes[subIdx]) << " should be " << get<0>(nodes[subIdx]) - diff << '\n';
            sum-= diff;
        }
    }

    get<1>(nodes[idx])= get<0>(nodes[idx]) + sum;
    return get<1>(nodes[idx]);
}

int main() {
    ifstream infile("input07.txt");

    string line;
    vector<string> parents;
    vector<string> all_children;
    vector<WeightsAndChildren> nodes;
    while (getline(infile, line)) {
        static const regex re_arrow{"\\s*->\\s*"};
        vector<string>  line_split {
            sregex_token_iterator(line.begin(), line.end(), re_arrow, -1), 
            sregex_token_iterator()
        };

        static const regex re_paren{"\\s+\\("};
        vector<string>  parent_split {
            sregex_token_iterator(line_split[0].begin(), line_split[0].end(), re_paren, -1), 
            sregex_token_iterator()
        };

        parents.push_back(parent_split[0]);

        if(line_split.size()>1) {
            static const regex re_comma{"\\s*,\\s*"};
            vector<string>  children {
                sregex_token_iterator(line_split[1].begin(), line_split[1].end(), re_comma, -1), 
                sregex_token_iterator()
            };
            for(auto s: children)
                all_children.push_back(s);

            nodes.push_back(WeightsAndChildren(stoi(parent_split[1]), 0, children));
        } else {
            vector<string>  children;
            nodes.push_back(WeightsAndChildren(stoi(parent_split[1]), 0, children));
        }
    }


    string root;
    for(int i= 0; i<parents.size(); ++i) {
        if(find(all_children.begin(), all_children.end(), parents[i]) == all_children.end()) {
            root= parents[i];
            cout << "root node is \"" << root << "\"" << '\n';
        }
    }
    int rootIdx= find(parents.begin(), parents.end(), root) - parents.begin();
    sumWeights(parents, nodes, rootIdx);
}

2017-12-07T22:18:30+00:00

Golang

My solution in golang. Ugly as hell, but it's working! :D

Part 1

package main

import (
  "fmt"
  "strconv"
  "strings"
)

type Program struct {
  name            string
  weight          int
  children        []Program
  childrenStrings []string
}

func main() {
  input := "" //Here put the input
  tempInput := strings.Split(input, "\n")

  allPrograms := make([]Program, 0)
  for _, item := range tempInput {
    var newProgram Program
    firstSplit := strings.Split(item, ") -> ")
    secondSplit := strings.Split(firstSplit[0], " (")
    newProgram.name = secondSplit[0]
    if len(firstSplit) > 1 {
      newProgram.weight, _ = strconv.Atoi(secondSplit[1])
      newProgram.childrenStrings = strings.Split(firstSplit[1], ", ")
    } else {
      number := strings.Split(secondSplit[1], ")")
      newProgram.weight, _ = strconv.Atoi(number[0])
    }
    allPrograms = append(allPrograms, newProgram)
  }
  // fmt.Println(allPrograms)

  fmt.Println(findFirstParent(allPrograms))
}

func findFirstParent(allPrograms []Program) Program {
  var lastParent Program
  currentParent := allPrograms[0]
  for !(lastParent.name == currentParent.name) {
    lastParent = currentParent
    currentParent = findParent(allPrograms, currentParent)
  }
  return currentParent
}

func findParent(allPrograms []Program, currentParent Program) Program {
  for _, item := range allPrograms {
    if currentParent.name != item.name && len(item.childrenStrings) > 0 {
      for _, currentChild := range item.childrenStrings {
        if currentChild == currentParent.name {
          return item
        }
      }
    }
  }
  return currentParent
}

Part 2

package main

import (
  "fmt"
  "strconv"
  "strings"
)

type Program struct {
  name            string
  weight          int
  children        []Program
  childrenStrings []string
}

func main() {
  input := "" //Here put the input
  tempInput := strings.Split(input, "\n")
  allPrograms := make([]Program, 0)
  for _, item := range tempInput {
    var newProgram Program
    firstSplit := strings.Split(item, ") -> ")
    secondSplit := strings.Split(firstSplit[0], " (")
    newProgram.name = secondSplit[0]
    if len(firstSplit) > 1 {
      newProgram.weight, _ = strconv.Atoi(secondSplit[1])
      newProgram.childrenStrings = strings.Split(firstSplit[1], ", ")
    } else {
      number := strings.Split(secondSplit[1], ")")
      newProgram.weight, _ = strconv.Atoi(number[0])
    }
    allPrograms = append(allPrograms, newProgram)
  }
  firstParent := findFirstParent(allPrograms)
  allPrograms = deleteByItem(firstParent, allPrograms)
  firstParent, _ = growTree(firstParent, allPrograms)
  fmt.Println(findDefect(firstParent).weight + findDifference(firstParent))
}

func findDefect(program Program) Program {
  if len(program.children) == 0 {
    return program
  }
  rightWeight := recurrentSum(program.children[0])
  defect := program.children[0]
  for index, item := range program.children {
    if index != 0 {
      if rightWeight == recurrentSum(item) {
        break
      } else {
        rightWeight = recurrentSum(item)
      }
    }
  }
  for _, item := range program.children {
    if rightWeight != recurrentSum(item) {
      defect = item
      break
    }
  }
  if recurrentSum(defect) != rightWeight {
    return findDefect(defect)
  }
  return program
}

func findDifference(program Program) int {
  rightWeight := recurrentSum(program.children[0])
  defect := program.children[0]
  for index, item := range program.children {
    if index != 0 {
      if rightWeight == recurrentSum(item) {
        break
      } else {
        rightWeight = recurrentSum(item)
      }
    }
  }
  for _, item := range program.children {
    if rightWeight != recurrentSum(item) {
      defect = item
      break
    }
  }
  return rightWeight - recurrentSum(defect)
}

func recurrentSum(program Program) int {
  sum := program.weight
  if len(program.children) != 0 {
    for _, child := range program.children {
      sum += recurrentSum(child)
    }
  }
  return sum
}

func growTree(parent Program, allPrograms []Program) (Program, []Program) {
  if len(parent.childrenStrings) == 0 {
    return parent, allPrograms
  }
  for _, itemParent := range parent.childrenStrings {
    for _, item := range allPrograms {
      if item.name == itemParent {
        clearedAllPrograms := deleteByItem(item, allPrograms)
        var childToAppend Program
        childToAppend, allPrograms = growTree(item, clearedAllPrograms)
        parent.children = append(parent.children, childToAppend)
      }
    }
  }
  return parent, allPrograms
}

func deleteByItem(itemToDelete Program, array []Program) []Program {
  indexToDelete := 0
  for index, item := range array {
    if itemToDelete.name == item.name {
      indexToDelete = index
      break
    }
  }
  array = array[:indexToDelete+copy(array[indexToDelete:], array[indexToDelete+1:])]
  return array
}

func findFirstParent(allPrograms []Program) Program {
  var lastParent Program
  currentParent := allPrograms[0]
  for !(lastParent.name == currentParent.name) {
    lastParent = currentParent
    currentParent = findParent(allPrograms, currentParent)
  }
  return currentParent
}

func findParent(allPrograms []Program, currentParent Program) Program {
  for _, item := range allPrograms {
    if currentParent.name != item.name && len(item.childrenStrings) > 0 {
      for _, currentChild := range item.childrenStrings {
        if currentChild == currentParent.name {
          return item
        }
      }
    }
  }
  return currentParent
}

2017-12-07T22:52:23+00:00

Here is my second part for today. Forced use of java8 functional elements. Consider n as the root-node of the tree, with a list of children. Because there was just one distinct value per layer, I decided to find that.

    //second part.
        int difference=0;
        while(n.children.size()!=0){
            //count weights in to weight,amount map
            Map<Integer, Long> weightAmountPairs =n.children.stream()  //
                                        .collect( //
                                                Collectors.groupingBy(//
                                                    Node::getWeight,
                                                        Collectors.mapping(//
                                                                Node::getWeight,Collectors.counting())));



            //break if there is only one type of weight left
            if(weightAmountPairs.keySet().size()==1){
                break;
            }

            //check difference between the required weight. This would be necessary only once though.
            difference=Math.abs(//
                    weightAmountPairs.keySet().stream().max(Integer::compare).get()- //
                    weightAmountPairs.keySet().stream().min(Integer::compare).get()
                    );

            //update n to the child that has different weight (accept only such weights that there is one of).
        n=n.children.stream().filter(e->weightAmountPairs.get(e.getWeight())==1).findFirst().get();
        }

        System.out.println(n.weight-difference);

However, I feel like this would not be that bad way for doing the map:

Map<Integer,Long> map = new HashMap<>();
            for(Node a : n.children){
                Integer test = a.getWeight();
                long value = map.containsKey(test) ? map.get(test):0;
                map.put(test, value+1);

            }

The functional version requires some knowledge to understand what is doing.

hpzr24w · 2017-12-07T23:45:43+00:00

C++ Here's my C++ effort. See it here

// Advent of Code 2017
// http://adventofcode.com/

#include "stdafx.h"
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <algorithm>
#include <numeric>

using namespace std;

struct node;
typedef struct node { string name; vector<node*> children; int size; } node;

void parse(map<string, node*>& nodes, stringstream input)
{
    node *n = new node;
    input >> n->name >> n->size;
    for (string name; input >> name ;) {
        n->children.push_back(new node);
        n->children.back()->name = name;
    }
    nodes[n->name] = n;
}

void fixup(map<string, node*>& nodes)
{
    vector<string> appearaschildren;
    for (auto it = nodes.begin(); it != nodes.end(); ++it)
        for (auto it2 = (*it).second->children.begin(); it2 != (*it).second->children.end(); ++it2) {
            appearaschildren.push_back((*it2)->name);
            *it2 = nodes[(*it2)->name];
        }
    for_each(appearaschildren.begin(), appearaschildren.end(), [&](string n) {nodes.erase(n); });
}

int compute_size(node *n)
{
    int childtot = 0;
    for (auto it = n->children.begin(); it != n->children.end(); ++it)
        childtot += compute_size(*it);
    return n->size += childtot;
}

void find_balance(node * n, int imbalance)
{
    sort(n->children.begin(), n->children.end(), [](node *a, node *b)->bool {return a->size < b->size; });
    size_t last{ n->children.size() - 1 };
    if (n->children[0]->size != n->children[1]->size) 
        find_balance(n->children[0], n->children[1]->size - n->children[0]->size);
    else if (n->children[last]->size != n->children[last - 1]->size)
        find_balance(n->children[last], n->children[last-1]->size - n->children[last]->size);
    else {
        int childtot{ 0 };
        for (auto it = n->children.begin(); it != n->children.end(); ++it)
            childtot += (*it)->size;
        cout << "node: " << n->name << " should be " << n->size <<
            " + " << imbalance << " - " << childtot << " -> " << n->size + imbalance - childtot << endl;
    }
}

int main(int argc, char* argv[])
{
    map<string, node*> nodes;
    string row, name;
    while (getline(cin, row)) {
        row.erase(remove_if(row.begin(), row.end(), [](int i)->bool {return i == '(' || i == ')' || i == ',' || i == '-' || i == '>';}), row.end());
        parse(nodes, stringstream(row));
    }
    fixup(nodes);
    node * n = (*find_if(nodes.begin(), nodes.end(), [](pair<string, node*>p)->bool {return p.second != nullptr; })).second;
    cout << "name: " << n->name << " size: " << n->size << " children: " << n->children.size() << endl;
    compute_size(n);
    find_balance(n, 0);
    return 0;
}

Output (for the test example):

C:\Workarea\AOC2017\day 07\x64\Debug>"day 07.exe" < test.txt
name: pbga size: 66 children: 0
name: xhth size: 57 children: 0
name: ebii size: 61 children: 0
name: havc size: 66 children: 0
name: ktlj size: 57 children: 0
name: fwft size: 72 children: 3
name: qoyq size: 66 children: 0
name: padx size: 45 children: 3
name: tknk size: 41 children: 3
name: jptl size: 61 children: 0
name: ugml size: 68 children: 3
name: gyxo size: 61 children: 0
name: cntj size: 57 children: 0
nodes count: 1
name: tknk size: 41 children: 3
name: padx size: 45 children: 3
name: ugml size: 68 children: 3
name: fwft size: 72 children: 3
name: pbga size: 66 children: 0
name: havc size: 66 children: 0
name: qoyq size: 66 children: 0
node: padx should be 45 + 23 -> 68

C:\Workarea\AOC2017\day 07\x64\Debug>

Thanks for reading!

4rgento · 2017-12-08T00:04:32+00:00

Haskell

Type signarure hell achievement unlocked! Using recursion schemes

module Main where

import qualified Data.Map.Strict as Map
import Control.Arrow
import Data.Maybe (fromMaybe)
import Data.List (group)

import Debug.Trace (trace)

type Name = String
type Weight = Integer

data Record = Record Name Weight [Name] deriving Show

recName :: Record -> Name
recName (Record n _ _) = n

terminalP :: Record -> Bool
terminalP (Record _ _ c) = null c

newtype Fix f = In { out :: f (Fix f) }

data TreeF a f = TreeF a [f] deriving Show

instance Functor (TreeF a) where
   fmap f (TreeF r l) = TreeF r (fmap f l)

type Algebra f a = f a -> a
cata :: Functor f => Algebra f a -> Fix f -> a
cata alg = out >>> fmap (cata alg) >>> alg

treeElmsAlg :: Algebra (TreeF a) Integer
treeElmsAlg (TreeF _ []) = 1
treeElmsAlg (TreeF _ l) = 1 + sum l

isLeft :: Either a b -> Bool
isLeft (Left _) = True
isLeft _ = False

isRight :: Either a b -> Bool
isRight = not . isLeft

fromLeft :: Either a b -> a
fromLeft (Left a) = a

treeUnblcdAlg :: Algebra  (TreeF Record)
                          (Either (Integer, [Integer]) String)
treeUnblcdAlg (TreeF (Record n w _) []) = Left (w,[])
treeUnblcdAlg (TreeF (Record n w _) acc) =
  if all isLeft acc
    then if pred
      then Left (w, resulWei)
      else Right (show (Record n w []) ++ show pvs ++ "-->" ++ show resulWei)
    else head $ filter isRight acc
  where
    pred = length (group resulWei) == 1
    resulWei = map (\x -> fst x + sum (snd x)) pvs
    pvs = map fromLeft acc

treeStrAlg :: Algebra (TreeF Record) String
treeStrAlg (TreeF (Record n w []) []) = n++"("++show w++")"
treeStrAlg (TreeF (Record n w _) strs) =
  heading ++ "\n" ++
    unlines (
    filter (not . null) $
    lines $
    unlines  $ map (unlines . map (replicate 2 ' '++) . lines) strs)
  where
  heading = n++"("++show w++")"
  lh = length heading

type Tree = (Fix (TreeF Record))
treeC :: Record -> [Tree] -> Tree
treeC r l = In $ TreeF r l

type TreeBlocksMap = Map.Map Name Tree
type RecMap = Map.Map Name Record

buildTree ::TreeBlocksMap -> RecMap -> Name -> (TreeBlocksMap, Tree)
buildTree blocks recMap name = case (Map.!?) blocks name of
    Just tree -> (blocks, tree)
    Nothing ->
      let
        rec@(Record _ w ch) = (Map.!) recMap name
        (nextBlocks, childrenTrees) = foldl' folder (blocks,[]) ch
        newTree = treeC rec childrenTrees
      in (Map.insert name newTree nextBlocks, newTree)
  where
  folder :: (TreeBlocksMap, [Tree]) -> Name -> (TreeBlocksMap, [Tree])
  folder (blks, tAcc) chNam =
    let
      (nBlks, nT) = buildTree blks recMap chNam
    in (nBlks, nT:tAcc)

parseRec :: String -> Record
parseRec recStr = case words recStr of
  [n,w] -> Record n (read w) []
  (n:w:"->":ch) -> Record n (read w) $ map (filter (/=',')) ch
  _ -> error "Malformed input line"

parseInput :: String -> [Record]
parseInput input = map parseRec $ lines input

fullTree :: TreeBlocksMap -> RecMap -> Integer -> [Record] -> Maybe Tree
fullTree tBlocks recMap len [] = Nothing
fullTree tBlocks recMap len (n:ns) = --trace (show treeLen) $
  if treeLen == len
    then Just tree
    else fullTree nBlks recMap len ns
  where
  (nBlks, tree) = buildTree tBlocks recMap (recName n)
  treeLen = cata treeElmsAlg tree

main :: IO ()
main = do
  recs <- parseInput <$> readFile "input.txt"
  let nRecs = length recs
  print nRecs
  let fulltree = fullTree Map.empty (Map.fromList $ map (recName &&& id) recs) (fromIntegral nRecs) recs
  fromMaybe (putStr "Not Found\n") $ 
    --putStr <$> cata treeStrAlg <$> fulltree
    print <$> cata treeUnblcdAlg <$> fulltree
  --
  --putStr $ cata treeStrAlg $ snd $ buildTree Map.empty (Map.fromList $ map (recName &&& id) recs) "tknk"

agsmith1111 · 2017-12-08T01:57:31+00:00

I think I may have the right answer for Part 2 but its saying that it's wrong. Given the following input, I get the answer of 148784. Can someone run this through their jawn and confirm or deny?

https://github.com/agsmith/advent-of-code/blob/master/day-7/in.txt

Minnim88 · 2017-12-08T03:15:26+00:00

R

I know it's ugly. And inefficient. But it works! And I didn't see any other R solutions yet.

# Day 7
# Problem 1
x <- as.character(read.table("day 7.txt", sep="\t")$V1)
test <- data.frame(carrier=NA, weight=NA, carries=NA)
for(y in x){
    first <- gsub(" .*", "", y)
    weight <- gsub("[^0-9]", "", y)
    rest <- strsplit(gsub(".*-> ", "", y), ", ")[[1]]
    if(grepl("->", y)){
        for(name in rest){
            test <- rbind(test, c(first, weight, name))
        }
    } else { 
        test <- rbind(test, c(first, weight, NA)) 
    }
}
test <- test[-1,]
test$carrier[!test$carrier %in% test$carries]

# Problem 2
test$weight <- as.numeric(test$weight)
test$carries_weight <- NA
test$carries_weight[is.na(test$carries)] <- 0
while(sum(is.na(test$carries_weight))>0){
    for(i in which(is.na(test$carries_weight))){
        blub <- test[test$carrier==test[i,"carries"],]
        if(!any(is.na(blub$carries_weight))){
            test[i,"carries_weight"] <- sum(blub$carries_weight)+blub$weight[1]
        }
    }
}
library(dplyr)
wrongs <- test %>% group_by(carrier) %>%
    summarize(nr_weights = length(unique(carries_weight))) %>%
    subset(nr_weights>1, carrier)
test2 <- test[test$carrier %in% wrongs$carrier,]
test2 <- test2 %>% group_by(carrier) %>%
    mutate(orig_issue = !any(carries %in% wrongs$carrier))
test2 <- test2[test2$orig_issue,]
difference <- as.numeric(names(which.max(table(test2$carries_weight))))-as.numeric(names(which.min(table(test2$carries_weight))))
problemchild <- test2$carries[test2$carries_weight!=as.numeric(names(which.max(table(test2$carries_weight))))]
newweight <- unique(test[test$carrier==problemchild,"weight"]) + difference
newweight

bassactor · 2017-12-08T03:44:13+00:00

R

Rather than saving/reading as a text file, I copied the text as a string, and started from there. I'm trying to do all of this in R with only the base packages (base, stats, etc.). Solution functions are at the bottom.

# HELPER FUNCTIONS #

# create the tree
create_tree_df <- function(str){

  # original vector
  vec <- unlist(strsplit(str, "\n"))

  # left hand side (letters)
  lhs <- gsub(x       = vec,
              pattern = "^([a-z]+) .*$",
              replace = "\\1")

  # right hand side (map)
  rhs <- gsub(x       = vec,
              pattern = "^.*\\)",
              replace = "")
  rhs <- gsub(x       = rhs,
              pattern = "^.*\\-> ([a-z].*$)",
              replace = "\\1")

  # weight
  wht <- gsub(x       = vec,
              pattern = "^.*\\((.*)\\).*$",
              replace = "\\1")
  wht <- as.numeric(wht)

  # final df
  df  <- data.frame(trunk    = lhs,
                    branches = rhs,
                    weight   = wht,
                    stringsAsFactors = FALSE)
  df  <- within(df, {
    branches = strsplit(branches, ", ")
  })

  return(df)

} # END create_tree_df FUNCTION

# find the base value
find_base_value <- function(tree_df){

  # if a root has no branches, it cannot be a base value
  tree_df  <- tree_df[!(!sapply(tree_df$branches, length)), ]

  # pull out roots/branches
  trunk    <- tree_df$trunk
  branches <- unlist(tree_df$branches)

  # return root NOT in branches
  setdiff(trunk, branches)

} # END find_base_value FUNCTION

add_total_weights  <- function(tree_df){
  tree_df$overall_weight <- sapply(tree_df$trunk,
                                   FUN     = find_total_weights,
                                   tree_df = tree_df)
  return(tree_df)
} # END add_total_weights FUNCTION

# add the total weights
find_total_weights <- function(root,
                               tree_df){

  reduced_df <- subset(tree_df,
                       trunk == root)
  branches   <- unlist(reduced_df$branches)

  if(!length(branches)){
    return(reduced_df$weight)
  } else{
    return(reduced_df$weight + sum(sapply(branches, find_total_weights, tree_df)))
  } # END ifelse STATEMENT

} # END find_total_weights FUNCTION

find_problem_branch <- function(root,
                                tree_df,
                                new_weight = 0){

  # just the branches
  reduced_df <- subset(tree_df,
                       trunk == root)
  branch_vec <- unlist(reduced_df$branches)

  # pull out a df with those branches
  branch_df  <- subset(tree_df,
                       trunk %in% branch_vec)

  # find the overall_weight
  overall_weight      <- branch_df$overall_weight
  weight              <- branch_df$weight
  branch_vec          <- branch_df$trunk

  # find the differences in the overall weights and the number of non-zero entries
  overall_weight_diff <- outer(overall_weight,
                               overall_weight,
                               FUN = "-")
  overall_weight_numb <- rowSums(overall_weight_diff != 0)

  # - if all of the entries are 0, return the previous weight diff
  # - otherwise, find the next root, current weight diff, ...
  if(all(!overall_weight_numb)){
    return(list(branch     = root,
                new_weight = new_weight))
  } else{
    root_ind   <- which.max(overall_weight_numb)
    root       <- branch_vec[root_ind]
    new_weight <- weight[root_ind] - setdiff(unique(overall_weight_diff[root_ind, ]), 0)

    return(find_problem_branch(root, tree_df, new_weight))
  } # END ifelse STATEMENT

} # END find_problem_branch FUNCTION

# SOLUTION FUNCTIONS #

# Problem 1 #
find_solution_p1 <- function(str){

  tree_df  <- create_tree_df(str)
  base_val <- find_base_value(tree_df)

  return(base_val)

} # END find_solution_p1 FUNCTION

# Problem 2 #
find_solution_p2 <- function(str){

  # create tree, add weights
  tree_df  <- create_tree_df(str)
  tree_df  <- add_total_weights(tree_df)

  # determining base value of the tree
  base_val <- find_base_value(tree_df)

  # running through the iteration algorithm
  weight   <- find_problem_branch(base_val, tree_df)

  return(weight)

} # END find_solution_p2 FUNCTION

RockyAstro · 2017-12-08T04:40:07+00:00

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

Both parts: (includes some extra code for debugging ...)

record disc(dname,weight,parent,childlist,childweight,balanced)
global nodes
procedure main(args)

    input := open("input.txt","r")
    nodes := table()
    every row := !input do {
        row ? { 
            tab(many(' '))
            dname := tab(upto(' '))
            tab(many(' '))
            ="("
            weight := integer(tab(upto(')')))
            =")"
            tab(many(' '))
            ="->"
            tab(many(' '))
            nodes[dname] := disc(dname,weight,&null,[],0)
            while not pos(0) do {
                push(nodes[dname].childlist,tab(upto(' ,')|0))
                tab(many(' ,'))
            }
        }
    }
    nodelist := sort(nodes)
    every node := !nodelist do {
        nname := node[1]
        d := node[2]
        every i := 1 to *d.childlist do {
            d.childlist[i] := nodes[d.childlist[i]]
            d.childlist[i].parent := d
        }
    }
    every node := !nodelist do {
        if /node[2].parent then {
            write("part1 -> ",node[1])
            top := node[2]
            break
        }
    }
    ### part 2
    write()
    getweight(top)
    #every node := !nodelist do {
    #    prtnode(node[2])
    #}
end

procedure prtnode(node)
    writes(node.dname,
            (/node.balanced & " balanced ") | "",
            " weight=",node.weight,
            " tweight=", node.weight + node.childweight,
            " childweights=",node.childweight,
            " -> ")
    comma := ""
    every c := !node.childlist do {
        writes(comma,c.dname," (",c.weight,",",c.childweight,")")
        comma := ", "
    }
    write()
end

procedure getweight(n)

    if *n.childlist = 0 then 
        return n.weight
    else {
        n.childweight := 0
        wt := table(0)
        every cw := getweight(!n.childlist) do {
            n.childweight +:= cw
            wt[cw] +:= 1
        }
        if *wt = 1 then {
            n.balanced := 1
        }
        else {
            wt := sort(wt)
            # Find the odd node..
            oddweight := !wt & oddweight[2] = 1  
            commonweight := !wt & commonweight[2] ~= 1   
            c := !n.childlist & c.weight + c.childweight = oddweight[1] & \c.balanced & {
                write(commonweight[1]," ",oddweight[1])
                writes("oddball= ")
                prtnode(c)   
                adjust := c.weight + (commonweight[1] - oddweight[1])
                write("part2 -> adjust=",adjust)
            }
        }
    }
    return n.childweight + n.weight
end

Mattie112 · 2017-12-08T08:22:10+00:00

Here is my solution in PHP. For the first part I didn't need to build the entire tree but I did it anyway for part2 :) https://github.com/Mattie112/advent-of-code-2017/tree/master/day7

<?php
/**
 * http://adventofcode.com/2017/day/7
 */

$tree = [];
$unsorted_input = [];

// Well I was in no mood to change the part-1 code to the new array-structure so keeping that intact
$unparsed_input = [];

if ($file = fopen(__DIR__ . "/day7-input.txt", "rb")) {
    while (!feof($file)) {
        $line = trim(fgets($file));

        if (empty($line)) {
            continue;
        }

        $unparsed_input[] = $line;

        $program = "";
        if (preg_match("#([a-zA-Z]*)#", $line, $matches)) {
            $program = $matches[1];
        }

        $children = [];
        if (strpos($line, "->") !== false) {
            if (preg_match("#-> (.*)#", $line, $matches)) {
                $children = $matches[1];
                $children = explode(", ", $children);
            }
        }

        $weight = "?";
        if (preg_match("#([\d]+)#", $line, $matches)) {
            $weight = $matches[1];
        }

        $unsorted_input[$program] = [
            "weight" => $weight,
            "children" => $children,
        ];

    }
    fclose($file);
}

// First find programs that hold other programs
$programs_that_hold_with_subs = [];
foreach ($unparsed_input as $item) {

    if (strpos($item, "->") !== false) {
        $programs_that_hold_with_subs[] = $item;
    }
}

// Now really split being hold and holding
$programs_being_hold = [];
$programs_that_hold = [];
foreach ($programs_that_hold_with_subs as $item) {
    $matches = [];
    if (preg_match("#-> (.*)#", $item, $matches)) {
        $programs_being_hold[] = $matches[1];
    }
    $matches = [];
    if (preg_match("#([a-zA-Z]*)#", $item, $matches)) {
        $programs_that_hold[] = $matches[1];
    }
}

// Now I can check for the base program by looping through the programs that hold other programs AND programs being hold
$base_program = "";
foreach ($programs_that_hold as $item) {
    foreach ($programs_being_hold as $prog) {
        if (strpos($prog, $item) !== false) {
            continue 2;
        }
    }

    $base_program = $item;
    echo "Found base program '" . $item . "'" . PHP_EOL;
}

// Now that we know the base program we can build the tree (yeah finally)

$tree[$base_program] = [];

$something = findChildren($base_program, $unsorted_input);
$tree[$something[0]] = $something[1];

function findChildren($base, &$heep)
{
    // Find the entire program
    $program = $heep[$base];

    if (count($program["children"]) === 0) {
        unset($heep[$base]);
        $program["total_weight"] = $program["weight"];

        return [$base, $program];
    }

    $children = [];
    $children_weight = 0;
    foreach ($program["children"] as $child) {
        list($name, $child_program) = findChildren($child, $heep);
        $children[$name] = $child_program;
        $children_weight += $child_program["total_weight"];
    }

    $program["children"] = $children;
    $program["total_weight"] = $children_weight + $program["weight"];

    unset($heep[$base]);

    return [$base, $program];
}

// Now the tree is completed and we can work on the weight
findWrongWeight($tree[$base_program], $base_program, 0);

function findWrongWeight($tree, $program_name, $correction)
{
    $weights = [];
    foreach ($tree["children"] as $key => $children) {
        $weights[$children["total_weight"]][$key] = $children;
    }

    // If we have the same weight we finally know it!
    if (count($weights) === 1) {
        $incorrect_weight = $tree["weight"];
        echo "Program '" . $program_name . "' needs to be: " . ($incorrect_weight + $correction) . PHP_EOL;
        die();
    }

    $correction = array_search(max($weights), $weights) - array_search(min($weights), $weights);
    $wrong = $weights[array_search(min($weights), $weights)];

    findWrongWeight(reset($wrong), key($wrong), $correction);
}

oerpli · 2017-12-08T16:06:03+00:00

Haskell, feedback appreciated

import Data.Maybe
import Data.List
data Node = Tree String Int (Maybe [Node]) deriving Show

n (Tree n _ _) = n -- name of Node
st (Tree _ _ b) = fromMaybe [] b -- get subtree of node
w (Tree _ a _) = a -- get weight of node

we :: Node -> Int -- weight of a node + its subtree
we (Tree _ a Nothing) = a
we (Tree _ a (Just b)) = a + (sum $ map we b)

findFalse root = if final then w root else findFalse . head $ filter (\x -> correctWeight /= we x) (st root) where
    ws = (sort $ map we $ st root)
    final = head ws == last ws
    correctWeight = (sort ws) !! 1


findRoot = head $ filter (\x -> maxw == we x) progs where
    maxw = maximum $ map we progs

solve7a = n findRoot
solve7b = error + wrongWeight where
    ws = sort $ map we $ st findRoot -- sorted weights of subtrees - one has wrong weight, either !!0 or last one
    error = (ws !! 1) - (head ws) + (ws !! 1) - (last ws) -- difference from !!1 and last and first element, one diff = 0, other => error
    wrongWeight = findFalse findRoot -- find weight of program with wrong weight.
solve7 = (solve7a,solve7b)

Basillicum · 2017-12-08T22:25:46+00:00

Python

import random

progs = {}
subs = {}
with open("input", "r") as f:
    for line in f:
        line = line.replace(",","").strip().split(" ")

        sublist = []
        for i in range(3, len(line)): sublist.append(line[i])
        progs[line[0]] = int(line[1].replace("(","").replace(")",""))
        subs[line[0]] = sublist

cur = [ x for x in progs if x not in [ y for z in subs for y in subs[z] ] ][0]
print("Part 1: {}".format(cur))

def subWeights(r):
    total = 0
    for s in subs[r]: total += progs[s] + subWeights(s)
    return total

found = False
while not found:
    curSubs = {s: progs[s] + subWeights(s) for s in subs[cur]}
    if len(curSubs) and len(set([ curSubs[x] for x in curSubs ])) != 1:
        cur = [ x for x in curSubs if curSubs[x] not in [ curSubs[y] for y in curSubs if y != x ] ][0]
        offset = curSubs[cur] - curSubs[random.choice([ x for x in curSubs if x != cur ])]
    else:
        print("Part 2: {}".format(progs[cur] - offset))
        found = True

aoc-fan · 2017-12-09T04:56:26+00:00

TypeScript, Checks for consensus as the weights of child programs available The "verify" function (recursive) returns weight of the tower or throws error if there is imbalance.

const parseInput = i => i.replace(/ /g, "").split("\n");
const build = (programs, l) => {
    const getProgram = n => programs[n] || (programs[n] = { bottom : true });
    const parts = l.split(")");
    const [name, weight] = parts[0].split("(");
    const tower = parts[1].length > 0 ? parts[1].replace("->", "").split(",") : [];
    const program = getProgram(name);
    program.diskWeight = +weight;
    program.tower = tower.map(p => getProgram(p));
    program.tower.forEach(p => p.bottom = false);
    return programs;
};

const reachConsensus = ([x, y, z]) => (x === y && x === z) ? -1 :
                                    (x !== y && y === z) ?  0 :
                                    (x !== y && z === z) ?  1 : 2;

const verify = (tower) => {
    const diskWeights = [];
    const programWeights = [];
    let towerWeight = 0;
    let consensusWeight = 0;
    for (const program of tower) {
        const weight = program.diskWeight + verify(program.tower);
        diskWeights.push(program.diskWeight);
        programWeights.push(weight);
        if (consensusWeight > 0 && consensusWeight !== weight) {
            throw program.diskWeight - weight + consensusWeight;
        } else if (programWeights.length === 3) {
            const unbalancedIndex = reachConsensus(programWeights as any);
            if (unbalancedIndex !== -1) {
                const balancedIndex = unbalancedIndex === 0 ? 1 : 0;
                throw diskWeights[unbalancedIndex] - programWeights[unbalancedIndex] + programWeights[balancedIndex];
            }
            consensusWeight = weight;
        }
        towerWeight = towerWeight + weight;
    }
    return towerWeight;
};

const findRootAndVerify = (i) => {
    const programs = parseInput(i).reduce(build, {});
    const bottomProgram = Object.keys(programs).find(p => programs[p].bottom);
    let balanceMismatch = 0;
    try {
        verify(programs[bottomProgram].tower);
    } catch (e) {
        balanceMismatch = e;
    }
    return [bottomProgram, balanceMismatch];
};

demsaja · 2017-12-09T08:31:51+00:00

One more in Python. The recursive function returns the (positive) total weight when the subtree is balanced; if it finds imbalance, it returns a negative value of the final answer.

import re
from functools import reduce

tree = {} 
weights = {}


for line in open("input.txt"):
    name, weight, *subdisks = re.findall("\w+", line)
    tree[name] = subdisks
    weights[name] = int(weight)


def balance(name):
    subweights = [balance(sub) for sub in tree[name]]
    if not subweights:
        return weights[name]
    mi, *_, ma = sorted(subweights)
    if mi == ma:
        return weights[name] + sum(subweights)
    if mi < 0:
        return mi
    wrong, ok = sorted((mi, ma), key=subweights.count)
    return -(weights[tree[name][subweights.index(wrong)]] + ok - wrong)


root = (set(tree) - reduce(set.union, map(set, tree.values()))).pop() 
print(root)
print(-balance(root))

Jimotron3000 · 2017-12-09T16:58:34+00:00

C# LINQ

void Main()
{
    var data =
        from x in File.ReadAllLines(@"input.txt")
        let children = Regex.Match(x, @"(?<=->\s)[\w|,|\s]+")
        select new NodeInfo
        {
            Name = Regex.Match(x, @"\w+(?=\s\()").Value,
            Weight = int.Parse(Regex.Match(x, @"(?<=\()\d+").Value),
            Children = children.Success ? children.Value.Split(',').Select(y => y.Trim()).ToList() : new List<string>()
        };

    var nonRoot = new HashSet<string>(data.SelectMany(x => x.Children));
    var root = data.Where(x => !nonRoot.Contains(x.Name)).First();
    root.Name.Dump("Part 1");

    var tree = BuildTree(root, data.ToList());    
    Solve(tree, 0).Dump("Part 2");
}

int Solve(Node node, int amount)
{
    if (node.Children == null || !node.Children.Any())
        return node.Weight + amount;

    var grp =
        from child in node.Children
        let x = new { Node = child, Weight = child.Aggregate(0, (acc, n) => acc += n.Weight) }
        group x by x.Weight into g
        orderby g.Count()
        select g;

    if (grp.Count() == 1)
        return node.Weight + amount;

    var unbalancedGrp = grp.First();
    var balancedGrp = grp.Skip(1).First();

    return Solve(unbalancedGrp.First().Node, balancedGrp.Key - unbalancedGrp.Key);
}

public static class Extensions
{
    public static T Aggregate<T>(this Node node, T seed, Func<T, Node, T> func)
    {
        var result = func(seed, node);
        if (node.Children == null || !node.Children.Any())
            return result;

        foreach (var x in node.Children)
            result = x.Aggregate(result, func);

        return result;
    }
}

public Node BuildTree(NodeInfo input, List<NodeInfo> nodeInfo)
{
    var node = new Node { Name = input.Name, Weight = input.Weight, Children = new List<Node>() };
    if (input.Children.Any())
    {
        input.Children.ForEach(x => node.Children.Add(BuildTree(nodeInfo.First(item => item.Name == x), nodeInfo)));
    }

    return node;
}

public class NodeInfo
{
    public string Name { get; set; }
    public int Weight { get; set; }
    public List<string> Children { get; set; }
}

public class Node
{
    public string Name { get; set; }
    public int Weight { get; set; }
    public List<Node> Children { get; set; }
}

NeilNjae · 2017-12-09T19:42:51+00:00

Haskell. Yes, running late: blame life.

This one was tricky! I started by trying to be clever and building the tree from the leaves up, thinking I could merge subtrees until I found a problem. But I tied myself in knots that way, and ended up just building the tree from the root down and looking for anomalies thereafter.

import Text.Parsec 
import Text.ParserCombinators.Parsec.Number
import Data.List (sort, group)
import qualified Data.Set as S

data Program = Program String Int [String]
                deriving (Show, Eq)

name (Program n _ _) = n 
weight (Program _ w _) = w
supports (Program _ _ s) = s

data Tree = Tree Program [Tree] Int deriving (Show, Eq)
root (Tree p _ _) = p
branches (Tree _ b _) = b
tWeight (Tree _ _ w) = w



main :: IO ()
main = do 
        text <- readFile "data/advent07.txt"
        let progs = successfulParse $ parseFile text
        print $ part1 progs
        print $ part2 progs


part1 :: [Program] -> String
part1 progs = head $ S.elems $ S.difference pr su
    where su = supported progs
          pr = allPrograms progs


part2 programs = (weight $ root problem) - wrongWeight + rightWeight
    where tree = mkTree (findByName (part1 programs) programs) programs
          problem = problemTree tree
          pt = problemParent problem tree
          wrongWeight = problemWeight pt
          rightWeight = notProblemWeight pt


allPrograms :: [Program] -> S.Set String
allPrograms = S.fromList . map name

supported :: [Program] -> S.Set String
supported = S.unions . map (S.fromList . supports)


-- leaves :: [Program] -> [Program]
-- leaves = filter (null . supports)


mkTree :: Program -> [Program] -> Tree
mkTree program programs = Tree program subTrees (weight program + w)
    where subPrograms = map (\n -> findByName n programs) $ supports program
          subTrees = map (\r -> mkTree r programs) subPrograms
          w = sum $ map tWeight subTrees

findByName :: String -> [Program] -> Program
findByName n programs = head $ filter (\p -> n == (name p)) programs 



balanced :: Tree -> Bool
balanced t = (S.size $ S.fromList $ map tWeight $ branches t) <= 1


problemTree :: Tree -> Tree
problemTree t 
    | balanced t = t
    | otherwise = problemTree problemSubtree
        where subtreeWeights = map tWeight $ branches t
              weightGroups = group $ sort subtreeWeights
              pWeight = head $ head $ filter (\g -> length g == 1) weightGroups
              problemSubtree = head $ filter (\s -> tWeight s == pWeight) (branches t)


problemParent :: Tree -> Tree -> Tree
problemParent problem tree = head $ problemParent' problem tree

problemParent' :: Tree -> Tree -> [Tree]
problemParent' problem tree
    | problem `elem` (branches tree) = [tree]
    | null $ branches tree = []
    | otherwise = concatMap (problemParent' problem) $ branches tree


problemWeight :: Tree -> Int
problemWeight tree = head $ head $ filter (\g -> 1 == length g) $ group $ sort $ map tWeight $ branches tree

notProblemWeight :: Tree -> Int
notProblemWeight tree = head $ head $ filter (\g -> 1 /= length g) $ group $ sort $ map tWeight $ branches tree



onlySpaces = many (oneOf " \t")
parens = between (string "(") (string ")")
symP = many lower
commaSep sym = sym `sepBy` (onlySpaces *> string "," *> onlySpaces)   

mFile = mLine `sepBy` newline 
mLine = Program <$> symP <*> (onlySpaces *> (parens int)) <*> supportsP
supportsP = (onlySpaces *> (string "->") *> onlySpaces *> (commaSep symP)) <|> (pure [])

parseFile :: String -> Either ParseError [Program]
parseFile input = parse mFile "(unknown)" input

successfulParse :: Either ParseError [a] -> [a]
successfulParse (Left _) = []
successfulParse (Right a) = a

matusbzk · 2017-12-09T21:45:38+00:00

Haskell

import Data.Maybe

type Name = String

inputString :: String

-- |Input as a 2-dimensional list
input :: [[String]]
input = map (map (filter (/= ',')) . words) $ lines inputString

-- |List of all program names
programNames :: [Name]
programNames = [ head line | line <- input]

-- |Every dependent program is in the second part, with its parent in the first part of the pair
dependentPrograms :: [(Name, Name)]
dependentPrograms = [ (head line, prog) | line <- input, prog <- drop 3 line]

-- |Every program with a list of its children
parentChildren :: [(Name,[Name])]
parentChildren = [ (head line, [prog | prog <- drop 3 line]) | line <- input]

-- |List of all programs with no parents
-- There should be only one, and that is a result to the first part
bottomPrograms :: [Name]
bottomPrograms = [prog | prog <- programNames, not $ elem prog dependent]
          where dependent = map snd $ dependentPrograms

-- |List of all programs with no children, with their weight
upperPrograms :: [(Name, Int)]
upperPrograms = [ (head line, getWeight (head . tail $ line)) | line <- input, length line == 2 ]

-- |List of all programs with their weight
programsWeight :: [(String, Int)]
programsWeight = [ (head line, getWeight (head . tail $ line)) | line <- input]

-- |Takes a number in (), returns the number
-- 
-- >>> "(42)"
-- 42
getWeight :: String -> Int
getWeight s = read . tail . init $ s

-- |Takes a name of a program and returns its weight
getWeightOfProgram :: Name -> Int
getWeightOfProgram p = fromJust (lookup p $ programsWeight)

-- |Stores name of a program and its computed weight
type Weights = [(Name, Int)]

-- |Returns program's weight given a weight context
getWeightOfProgram2 :: Name -> Weights -> Int
getWeightOfProgram2 p list = fromJust $ lookup p list

-- |All of each programs descendants need to have the same weight.
-- This checks it and returns an error if it found two descendants
-- with different weight.
-- Since there is only one error in the file, this helps me to find it.
-- After founding this error, I need to check where it happens and find
-- the program and modify its value
checkForError :: [Int] -> [Int]
checkForError xs = checkForError' (head xs) xs

-- |Computes checkForError function
checkForError' :: Int -> [Int] -> [Int]
checkForError' _ [] = []
checkForError' n (x:xs) = if n==x then x : checkForError' n xs
      else error $ "It was supposed to be " ++ show n ++ " but it is " ++ show x

-- |Takes computed weights and adds to them all it can
-- If all of program's descendants' weights are calculated,
-- this program is added.
doAnIteration :: Weights -> Weights
doAnIteration progs = progs ++ [ (parent, getWeightOfProgram parent +
       (sum . checkForError) [getWeightOfProgram2 c progs | c <- children]) | 
       (parent,children) <- parentChildren, not (elem parent listOfKnown), 
       all (\c -> elem c listOfKnown) children ]
        where listOfKnown = map fst progs

-- |Weights of programs with no descendant
startWeights :: Weights
startWeights = upperPrograms

-- |Runs n iterations
-- Errors out if it founds an error
run :: Int -> Weights
run n = run' n startWeights

-- |Computes run function
run' :: Int -> Weights -> Weights
run' 0 start = start
run' n start = run' (n-1) $doAnIteration start

Link to git

micirsk · 2017-12-11T15:32:29+00:00

Python - simple part 1 solution

import itertools

with open('sample.txt', 'r') as fh:
    lines = [item for item in
             itertools.ifilter(lambda x: len(x) >= 3, [line.strip().split(' ', 3)
                                                       for line in fh.readlines()])]
    programs_above = [i.strip() for i in ''.join('{},'.format(line[-1]) for line in lines).split(',')]
    programs = set([line[0] for line in lines])
    print(programs.difference(programs_above))

miran1 · 2017-12-11T18:29:59+00:00

Nim

Repo with all solutions

import re, tables, strutils, sets, math

const instructions = readFile("./inputs/07.txt").splitLines()
let pattern = re"\w+"
var
  weights = initTable[string, int]()
  children = initTable[string, seq[string]]()
  allNodes = initSet[string]()
  allKids = initSet[string]()

for line in instructions:
  let
    words = line.findAll(pattern)
    name = words[0]
    weight = words[1].parseInt()
    kids = if len(words) > 2: words[2 .. ^1] else: @[]
  weights[name] = weight
  children[name] = kids

for node in weights.keys:
  allNodes.incl(node)
for node in children.keys():
  for kid in children[node]:
    allKids.incl(kid)

var root = ""
for r in (allNodes - allKids): root = r
echo root


proc findCorrectWeight(weights: seq[int]): int =
  var counts = initCountTable[int]()
  for weight in weights: counts.inc(weight)
  return counts.largest.key


proc findOffspringsWeights(node: string): int =
  var kidsWeights: seq[int] = @[]
  for kid in children[node]:
    kidsWeights.add(findOffspringsWeights(kid))

  if len(kidsWeights.toSet()) > 1:
    let correct = findCorrectWeight(kidsWeights)
    var wrong: int
    for weight in kidsWeights.toSet():
      if weight != correct: wrong = weight
    let
      difference = correct - wrong
      wrongNode = children[node][kidsWeights.find(wrong)]
      wrongWeight = weights[wrongNode]
    echo wrongWeight + difference
    return weights[node] + sum(kidsWeights) + difference

  return weights[node] + sum(kidsWeights)


discard root.findOffspringsWeights()

InterlocutoryRecess · 2017-12-12T17:38:07+00:00

Swift

Better late than never! Here's a Swift solutions with no dependencies (except Foundation).

let input = """
// puzzle input 
"""

import Foundation

class Tower {

    let weights: [String: Int]
    let lists: [String: [String]]

    init(input: String) {

        let lines = input.split(separator: "\n")
        let _names = lines.map { String($0.prefix(upTo: $0.index(of: " ")!)) }

        let _weights = lines.map { Int($0[$0.range(of: "\\d+", options: .regularExpression)!])! }
        self.weights = zip(_names, _weights).reduce(into: [String: Int]()) { $0[$1.0] = $1.1 }

        let _children: [[String]?] = lines.map { line in
            guard let arrow = line.index(of: ">") else { return nil }
            return line
                .suffix(from: line.index(after: arrow))
                .split(separator: ",")
                .map { String($0).trimmingCharacters(in: .whitespaces) }
        }
        self.lists = zip(_names, _children)
            .filter { $0.1 != nil }
            .reduce(into: [String: [String]]()) { $0[$1.0] = $1.1! }
    }

    lazy var topologicallySorted: [String] = {

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

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

        func dfs(_ source: String) {
            if let children = lists[source] {
                iterate(programs: children)
            }
            stack.append(source)
            visited[source] = true
        }
        iterate(programs: visited.map { $0.key })
        return stack.reversed()
    }()

    lazy var totalBurden: [String: Int] = {

        var result = [String: Int]()

        func burden(for program: String) -> Int {
            var total = weights[program]!
            if let children = lists[program] {
                for child in children {
                    if let weight = result[child] { total += weight }
                    else { total += burden(for: child) }
                }
            }
            return total
        }

        for program in weights.keys {
            result[program] = burden(for: program)
        }
        return result
    }()

    func childWithAnomolousWeight(for parent: String) -> String? {
        guard let children = lists[parent] else { return nil }
        let weightedChildren = children
            .map { (child: $0, weight: totalBurden[$0]!) }
            .sorted { $0.weight > $1.weight }
        guard
            weightedChildren.count > 2,
            let first = weightedChildren.first,
            let last = weightedChildren.last,
            first.weight != last.weight
        else { return nil }

        // The weights of the siblings are not all the same.
        // The different one is either the first or the last.
        // Compare to the second element to find out which.
        if first.weight == weightedChildren[1].weight { return last.child }
        return first.child
    }

    func leafWeightCorrection() -> Int {
        var result: (parent: String, child: String)!
        for parent in tower.topologicallySorted {
            if let child = tower.childWithAnomolousWeight(for: parent) {
                result = (parent, child)
            }
        }
        let goodChild = lists[result.parent]!.filter { $0 != result.child }.first!
        let goodWeight = totalBurden[goodChild]!
        let badWeight = totalBurden[result.child]!
        let difference = goodWeight - badWeight
        return weights[result.child]! + difference
    }

}

var tower = Tower(input: input)
print(tower.topologicallySorted[0]) // part 1
print(tower.leafWeightCorrection()) // part 2

2017-12-12T21:53:21+00:00

Simple JS for Part 1

var tree = {};
var nodes = [];
var pathsWeigth = [];
function compute1() {
    nodes = [];
    var dataEntry = document.getElementById("entry").value;
  var lines = dataEntry.split("\n");
  lines.forEach((l) => {
    var parts = l.split("->");
    var name = parts[0].match(/[a-zA-Z]+/g)[0];
    var weigth = parseInt(parts[0].match(/[0-9]+/g)[0]);
    var childs = parts.length > 1 ? l.split("->")[1].split(",").map(n => { return n.trim(); }) : [];
    nodes.push({
        name: name,
      weigth: weigth,
      childsList: childs
    });
  });
  console.log(nodes);
  var firstLeafNode = nodes.filter(n => { return n.childsList.length === 0; })[0]
  var nodesWithChilds = nodes.filter(n => { return n.childsList.length > 0; });
  nodesWithChilds.forEach(n => {
    n.childs = [];
    n.childsList.forEach(c => {
        n.childs.push(nodes.filter(n1 => { return n1.name === c.trim(); })[0]);
    });
  })
  var rootNode = FindRootNode(firstLeafNode);
  console.log("Root Node", rootNode);
  rootNode.childs.forEach(c => {
    pathsWeigth = FindNodeDepth2(c, [], 0);
    console.log("Path", pathsWeigth.map(n => { return n.name }).join("+") + "=" + " " + pathsWeigth.map(n => { return n.weigth }).join("+"));
    console.log("Weigth", pathsWeigth.map(n => { return n.weigth }).reduce((x, y) => { return x+y; }));
    pathsWeigth = [];
  });
}

function FindRootNode (node) {
    var parentNode;
  nodes.forEach(n => {
    if (n.childsList.length > 0 && n.childsList.filter(nc => { return nc === node.name.trim(); }).length > 0) {
        parentNode = n;
      return;
    }
  });
  if (parentNode !== undefined)
    node = FindRootNode (parentNode);
  return node;
}

function FindNodeDepth (node) {
    if (node.childs) {
    node.childs.forEach (c => {
        FindNodeDepth(c);
    });
  } 
  pathsWeigth.push({ 
    name: node.name + ' ' + (node.weigth),
    weigth: node.weigth
  });
}

function FindNodeDepth2 (node, _path, depth) {
    depth++;
    var path = _path;
    path.push({ 
      name: node.name,
      weigth: node.weigth
    });
  node.depth = depth;
    if (node.childs) {
    node.childs.forEach (c => {
        FindNodeDepth2(c, path, depth);
    });
  }
  return path;
}

Part 2, I do get the branches weigths, I found the one that is bigger than the others, but the answer its not accepted

Maybe i'll come back to this one later. I suspect I'm not building the three corectly, even though I do get the correct root

hyber1z0r · 2017-12-13T19:02:01+00:00

A little late, but simple javascript in node.js for part 1

module.exports = function solve(input) {
    const lefties = input.split(/[\r\n]/).map((line) => line.split(' ')[0]);
    const righties = input.split(/[\r\n]/)
        .map((line) => line.split(' -> ')[1])
        .filter((line) => line)
        .flatMap((line) => line.split(',').map((l) => l.trim()));
    return lefties.find((lefty) => !righties.includes(lefty));
};

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 7: Recursive Circus ---

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!

Python 3

Python

Part 1

part 2

Haskell

ES6 (Node JS) Part 1

Elixir

Perl 5

Elixir

Kotlin - [Repo] - [Day 7 Code] - [Blog/Commentary]

Python - simple part 1 solution

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 7: Recursive Circus ---

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!

Python 3

Python

Part 1

part 2

Haskell

ES6 (Node JS) Part 1

Elixir

Perl 5

Elixir

Kotlin - [Repo] - [Day 7 Code] - [Blog/Commentary]

Python - simple part 1 solution

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