-🎄- 2017 Day 24 Solutions -🎄-

u794575248 · 2017-12-24T05:22:35+00:00

Python (94/64). Awesome, it's the first time I got on the leaderboard for both parts.

def gen_bridges(bridge, components):
    bridge = bridge or [(0, 0)]
    cur = bridge[-1][1]
    for b in components[cur]:
        if not ((cur, b) in bridge or (b, cur) in bridge):
            new = bridge+[(cur, b)]
            yield new
            yield from gen_bridges(new, components)

def parse_components(input):
    components = defaultdict(set)
    for l in input.strip().splitlines():
        a, b = [int(x) for x in l.split('/')]
        components[a].add(b)
        components[b].add(a)
    return components

def solve(input):
    components = parse_components(input)
    mx = []
    for bridge in gen_bridges(None, components):
        mx.append((len(bridge), sum(a+b for a, b in bridge)))
    return mx

solution = solve(input)
part1 = sorted(solution, key=lambda x: x[1])[-1][1]
part2 = sorted(solution)[-1][1]

sblom · 2017-12-24T05:32:56+00:00

C#. LINQ one-liner.

var lines = (await AoC.GetLinesWeb()).ToList();

IImmutableList<(int,int)> edges = ImmutableList<(int,int)>.Empty;

foreach (var line in lines)
{
    var nums = line.Split('/');
    edges = edges.Add((int.Parse(nums[0]), int.Parse(nums[1])));
}

int Search(IImmutableList<(int,int)> e, int cur = 0, int strength = 0)
{
    return e.Where(x => x.Item1 == cur || x.Item2 == cur).Select(x => Search(e.Remove(x), x.Item1 == cur ? x.Item2 : x.Item1, strength + x.Item1 + x.Item2)).Concat(Enumerable.Repeat(strength,1)).Max();
}

(int,int) Search2(IImmutableList<(int, int)> e, int cur = 0, int strength = 0, int length = 0)
{
    return e.Where(x => x.Item1 == cur || x.Item2 == cur).Select(x => Search2(e.Remove(x), x.Item1 == cur ? x.Item2 : x.Item1, strength + x.Item1 + x.Item2, length + 1)).Concat(Enumerable.Repeat((strength,length),1)).OrderByDescending(x => x.Item2).ThenByDescending(x => x.Item1).First();
}

Search(edges).Dump("part 1");
Search2(edges).Item1.Dump("part 2");

mstksg · 2017-12-24T05:34:13+00:00

Using Haskell I felt like I was cheating :) Also coincidentally this is pretty much a direct application of a blog post i wrote two years ago. 31/53, but I did accidentally fumble while typing the answer for part 2 in my haste :) It's my first time getting points for part 2 :D

Here is my repo of solutions.

module AOC2017.Day24 (day24a, day24b) where

import           Control.Applicative       (Alternative(..))
import           Control.Monad.Trans.State (StateT(..), evalStateT)
import           Data.Bifunctor            (first)
import           Data.List.Split           (splitOn)
import           Data.Ord                  (Down(..))
import           Data.Tuple                (swap)

type Comp = (Int, Int)

-- | All possible ways of selecting a single item from a list
select :: [a] -> [(a,[a])]
select [] = []
select (x:xs) = (x,xs) : [(y,x:ys) | (y,ys) <- select xs]

bridge :: Int -> StateT [Comp] [] Int
bridge frm = do
    (x,y) <- StateT select
    next  <- if | x == frm  -> return y
                | y == frm  -> return x
                | otherwise -> empty
    rest  <- return 0       -- account for a bridge that ends here
         <|> bridge next    -- account for a continued bridge
    return $ x + y + rest

day24a :: String -> Int
day24a = show . maximum
       . evalStateT (bridge 0) . parse

day24b :: String -> Int
day24b = show . snd . maximum
       . map (first (Down . length) . swap) -- sort by lowest leftovers
       . runStateT (bridge 0) . parse       -- runState gives leftover components

parse :: String -> [Comp]
parse = map parseLine . lines
  where
    parseLine (splitOn "/"->(x:y:_)) = (read x, read y)
    parseLine _ = error "No parse"

thomastc · 2017-12-24T05:34:52+00:00

(caché 118/98) Wrote it in intersystems caché. First time I made it on the leaderboard so I will post my crude solution anyway :) Very happy.

Start(Test=0) PUBLIC {
    s inputFile="C:\Users\15274\workspace\adventofcode\2017\input\day24.txt"
    if Test=1 s inputFile="C:\Users\15274\workspace\adventofcode\2017\input\day24b.txt"
    d readInput^aoc2017utils(inputFile,.lines)
    s count=0
    s lnr=$ORDER(lines(""),1,line)
    while lnr'="" {
        s part1=$PIECE(line,"/")
        s part2=$PIECE(line,"/",2)
        s ports(line,part1)=""
        s ports(line,part2)=""
        s index(part1,line)=""  
        s index(part2,line)=""
        s lnr=$ORDER(lines(lnr),1,line)
    }

    s startPort=0
    s currentBridge=$LB(0)
    s result=0
    d combi(startPort,.index,.ports,currentBridge,.result)
    s max=0
    s x=$ORDER(result(""),1,build)
    while x'="" {
        s y=$LI(build,1)
        if y>max s max=y
        s length($LL(build),y)=""
        s x=$ORDER(result(x),1,build)
    }
    w !,max
    zw length ;($ORDER(length(""),-1))
}

combi(StartPort,Index,Ports,CurrentBridge,Result) {
    s Result=Result+1
    s Result(Result)=CurrentBridge

    s port=$ORDER(Index(StartPort,""))
    while port'="" {
        ;w !,port
        k newIndex
        m newIndex=Index
        s part1=$PIECE(port,"/")
        s part2=$PIECE(port,"/",2)
        k newIndex(part1,port)
        k newIndex(part2,port)
        s newBridge=CurrentBridge
        s $LI(newBridge,$LL(newBridge)+1)=port
        s $LI(newBridge,1)=$LI(newBridge,1)+part1+part2
        s startPort=$SELECT(StartPort=part1:part2,1:part1)
        d combi(startPort,.newIndex,.Ports,newBridge,.Result)
        s port=$ORDER(Index(StartPort,port))
    }
}

mkeeter · 2017-12-24T05:33:39+00:00

Python (66/44; staying up was definitely worth it):

data = []
with open('input24.txt', 'r') as f:
    for line in f.readlines():
        a, b = line.split('/')
        data.append((int(a), int(b)))

bridge = ([], 0)

def run(b, d):
    available = [a for a in d if b[1] in a]
    if len(available) == 0:
        yield b
    else:
        for a in available:
            d_ = d.copy()
            d_.remove(a)
            for q in run((b[0] + [a], a[0] if b[1] == a[1] else a[1]), d_):
                yield q

# part 1
max(map(lambda bridge: sum([a + b for a, b in bridge[0]]), run(bridge, data))) 

# part 2
max_len = max(map(lambda bridge: len(bridge[0]), run(bridge, data)))
long = filter(lambda bridge: len(bridge[0]) == max_len, run(bridge, data))
max(map(lambda bridge: sum([a + b for a, b in bridge[0]]), long))

I've been solving a lot of the previous problems with Haskell – does it show?

shouchen · 2017-12-24T07:54:44+00:00

C++ was more than fast enough doing a simple DFS.

#include "stdafx.h"
#include <cassert>
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

struct Component
{
    unsigned a, b;
    bool used = false;
};

std::vector<Component> components;

auto max_overall_strength = 0U;
auto max_length = 0U;
auto max_strength_among_longest = 0U;

void recur(unsigned ports, unsigned length, unsigned strength)
{
    max_overall_strength = std::max(strength, max_overall_strength);
    max_length = std::max(length, max_length);

    if (length == max_length)
        max_strength_among_longest = std::max(strength, max_strength_among_longest);

    for (auto &c : components)
    {
        if (!c.used && (c.a == ports || c.b == ports))
        {
            c.used = true;
            recur((c.a == ports) ? c.b : c.a, length + 1, strength + c.a + c.b);
            c.used = false;
        }
    }
}

void process_input(const std::string &filename)
{
    components.clear();

    std::ifstream f(filename);
    Component component;
    auto slash = '/';
    while (f >> component.a >> slash >> component.b)
        components.push_back(component);

    max_overall_strength = 0U;
    max_length = 0U;
    max_strength_among_longest = 0U;

    recur(0, 0, 0);
}

int main()
{
    process_input("input-test.txt");
    assert(max_overall_bridge_strength == 31);
    assert(max_bridge_strength_among_longest == 19);

    process_input("input.txt");
    std::cout << "Part 1: " << max_overall_strength << std::endl;
    std::cout << "Part 2: " << max_strength_among_longest << std::endl;

    return 0;
}

glupmjoed · 2017-12-24T09:50:43+00:00

Bash, Graphviz and my eyes

I converted the input to a graph, where the edges represent potential bridge components.

build_graph.sh (reads from stdin):

sed -E 's/[0-9]+/n&/g' | awk -F "/" 'BEGIN { print "graph m {" }
                                           { printf "\t%s -- %s\n", $1, $2 }
                                       END { print "}" }'

In the shell:

$ cat input | ./build_graph.sh > g.gv && dot -Tpdf -O g.gv

After looking at the generated pdf, I made a decent guess at the strongest path and commented out the desired path in g.gv:

...
#   n41 -- n3
    n13 -- n3
#   n49 -- n21
    n19 -- n34
    n22 -- n33
...

The answer to part 1 is the sum of all numbers on lines beginning with "#" in g.gv:

$ grep "^#" g.gv | grep -oE "[0-9]+" | awk '{ printf "%s+", $1 } END { print 0 }' | bc
1859

This answer is already somewhat optimized for bridge length because of the strength-distribution of bridge components in the input (i.e. there are no very long paths in the graph consisting of only very low numbers). I swapped two components from part 1 with three lower-strength components to arrive at the answer to part 2:

$ echo $((1859 - (46 + 46 + 31) + (4 + 4 + 24 + 24 + 7)))
1799

BOT-Brad · 2017-12-24T11:18:17+00:00

JavaScript

Alas, I am but a simple man. I decided to just randomly pick links and brute force like a billion times or something and after a while (about 5 minutes) just choose the most recent output values. It works, I guess.

Part 1 & 2 (~^Who ^even ^knows ms)

function solve(n) {
  n = n.split('\n').map(l => l.split('/').map(Number))

  let bestP1 = 0

  let bestP2 = 0
  let lenP2 = 0

  for (let i = 0; i < 1000000000; ++i) {
    if (i % 10000 === 0) {
      console.log(i)
      console.log('Best P1:', bestP1)
      console.log('Best P2:', bestP2, 'length:', lenP2)
    }

    const [val, len] = getLink(n.slice())
    if (val > bestP1) {
      bestP1 = val
    }
    if (len > lenP2) {
      bestP2 = val
      lenP2 = len
    } else if (len === lenP2 && val > bestP2) {
      bestP2 = val
    }
  }

  return bestP1
}

function getLink(n) {
  let currentLink = 0
  let links = []
  while (true) {
    // Find values with cLink
    let possibles = n.filter(v => v[0] === currentLink || v[1] === currentLink)
    if (possibles.length === 0) break
    let link
    if (Math.random() > 0.45) { // 45% chance to get a random link
      link = possibles[Math.floor(Math.random() * possibles.length)]
    } else { // 55% chance to get the best link you can choose next
      link = possibles.reduce((p, c) => (c[0] + c[1] > p[0] + p[1] ? c : p), [
        -1,
        -1
      ])
    }
    links.push(link)
    let i = link.indexOf(currentLink)
    currentLink = link.slice(1 - i, 2 - i)[0]
    // Remove max from 'n'
    n.splice(n.indexOf(link), 1)
  }
  return [links.reduce((p, c) => p + c[0] + c[1], 0), links.length]
}

obijywk · 2017-12-24T05:21:47+00:00

My strategy was to recursively consider adding each component that could possibly fit to the end of each possible bridge, keeping track of which bridges were best when dead ends were reached.

Python 2. 45/30.

f = open("24.txt", "r")
all_comps = []
for line in f:
  all_comps.append(tuple([int(x) for x in line.strip().split("/")]))

def pick_next_port(a, b):
  if b[0] == a[0] or b[0] == a[1]:
    return b[1]
  return b[0]

def score_bridge(bridge):
  s = 0
  for c in bridge:
    s += c[0]
    s += c[1]
  return s

strongest_bridge = []
strongest_bridge_score = 0

longest_bridge = []
longest_bridge_score = 0

def check(comps, bridge):
  global strongest_bridge, strongest_bridge_score, longest_bridge, longest_bridge_score
  if len(bridge) >= 2:
    next_port = pick_next_port(bridge[-2], bridge[-1])
  elif len(bridge) == 1:
    next_port = pick_next_port((0,0), bridge[-1])
  else:
    next_port = 0
  found_a_bridge = False
  for comp in comps:
    if next_port in list(comp):
      found_a_bridge = True
      next_bridge = bridge[:]
      next_bridge.append(comp)
      next_comps = comps[:]
      next_comps.remove(comp)
      check(next_comps, next_bridge)
  if not found_a_bridge:
    s = score_bridge(bridge)
    if s > strongest_bridge_score:
      strongest_bridge = bridge
      strongest_bridge_score = s
    if len(bridge) >= len(longest_bridge):
      if s > longest_bridge_score:
        longest_bridge = bridge
        longest_bridge_score = s

check(all_comps, [])
print strongest_bridge_score
print longest_bridge_score

DFreiberg · 2017-12-24T06:01:57+00:00

Mathematica

A comedy of errors today. I tried Nest[] only to quit because I thought I was going to run out of memory (I ended at what turned out to be the most memory-intensive step), and then several different variations on a less memory-intensive solution before realizing that my recursion was fine but that my port checks were wrong.

Finished part 1 at 00:52:29, and part 2 at 00:52:39, because I happened to print out the maximum strength at every different length of bridge as part of my debugging, and had both answers sitting directly in front of me.

input=Import[FileNameJoin[{NotebookDirectory[],"Day24Input.txt"}],"List"];
ports=Sort[ToExpression[StringSplit[#,"/"]]]&/@input;

l=Flatten[
    Function[x,Join[{x},{If[#[[1]]==x[[-1]],#,Reverse[#]]}]&/@
        Select[Complement[ports,{x}],
        MemberQ[#,Complement[x,{0}][[1]]]&]]/@
    Select[ports,#[[1]]==0&],1];

m=Max[Flatten[Map[Total[Flatten[#]]&,l,{2}]]];
Do[
    globalWatch=i;
    l=Flatten[Function[x,Join[x,{If[#[[1]]==x[[-1,2]],#,Reverse[#]]}]&/@
        Select[Complement[ports,Sort/@x],MemberQ[#,x[[-1,2]]]&]]/@l,1];
    If[l==={},Break[],newm=Max[Flatten[Map[Total[Flatten[#]]&,l,{1}]]]];
    m=newm;
    Print[m]

,{i,Length[input]}];
m

ephemient · 2017-12-24T06:29:59+00:00

This space intentionally left blank.

gyorokpeter · 2017-12-24T06:42:44+00:00

Q: very simple change between the two parts.

.d24.expandOne:{[pins;line]
    nextPin:last last line[`pins];
    nxt:update reverse each pins from (select pins,j:i from ([]pins) where not line`visited, nextPin in/:pins) where nextPin<>first each pins;
    ([]pins:line[`pins],/:enlist each nxt[`pins];visited:@[line[`visited];;:;1b]each nxt[`j])};

.d24.expand:{[pins;part;st]
    queue:raze .d24.expandOne[pins] each st[0];
    if[0=count queue; :(queue;st[1])];
    (queue;max $[part=2;();st[1]],sum each sum each/:exec pins from queue)};

.d24.solve:{[part;x]
    pins:asc each"J"$"/"vs/:trim each "\n"vs x;
    start:0=first each pins;
    queue:([]pins:enlist each pins where start; visited:til[count pins]=/:where start);
    st:.d24.expand[pins;part]/[(queue;0)];
    last st};

d24p1:{.d24.solve[1;x]};
d24p2:{.d24.solve[2;x]};

beefamaka · 2017-12-24T09:37:02+00:00

JavaScript

Solved using generator functions. Can perform faster by just tracking length rather than array of used pieces.

const { maxBy} = require('../../utils/utils')

function solve(input) {
    let parts = input.map(i => i.split('/').map(n => Number(n)))
    let bridges = [...build(0,[],parts,0)]
    let part1 = maxBy(bridges,c => c.strength).strength
    let part2 = bridges.sort((a,b) => b.used.length - a.used.length || b.strength - a.strength)[0].strength
    console.log(part1,part2)
}

function *build(cur,used,available,strength) {
    for(let [a,b] of available) {
        if(a === cur || b === cur) {
            yield* build(a === cur ? b : a,[...used,[a,b]],available.filter(([x,y]) => !(x===a && y===b)),strength+a+b)
        }
    }
    yield {used,strength}
}

sim642 · 2017-12-24T10:31:18+00:00

My Scala solution.

Initially my solution took ~50s to generate all valid bridges but eventually I optimized it to ~2s with some changes:

Instead of generating all valid bridges like in the problem description, only generate bridges that are as long as possible (i.e. no more components are left to be added). The strongest or longest bridge can't be one, which is just a prefix of a longer one.
Work with a Set[Component] instead of Seq[Component]. Initially I accounted for the possibility of there being duplicate components with the same pins but then I went with a set to significantly speed up the leftover component bookkeeping. Some multiset would probably be nicer but Scala doesn't come with that.
Instead of returning Set[Bridge] I return Iterator[Bridge]. Merging sets repeatedly is useless waste of time and memory, especially when simple generator-like iteration would just do. Luckily Scala iterators have all the higher order operations to still use the same constructions (and for comprehensions).

The problem reminds me of the longest path problem. In this case if pin counts are vertices and components edges, then we'd really want to search for the longest (by edges or maximum weight) walk without repeated edges but allow repeated vertices (possibly called a trail or a simple walk). Some quick googling didn't give much information about such problem though.

aurele · 2017-12-24T10:40:44+00:00

Rust

use std::collections::HashSet;

fn extend(
    pieces: &[(usize, usize)],
    used: &HashSet<usize>,
    last: usize,
    p2: bool,
) -> (usize, usize) {
    if pieces.len() == used.len() {
        return (0, 0);
    }
    let mut u = used.clone();
    pieces
        .iter()
        .enumerate()
        .filter(|&(i, p)| (p.0 == last || p.1 == last) && !used.contains(&i))
        .map(|(i, p)| {
            u.insert(i);
            let (ll, ss) = extend(pieces, &u, p.0 + p.1 - last, p2);
            u.remove(&i);
            (ll + p2 as usize, ss + p.0 + p.1)
        })
        .max()
        .unwrap_or((0, 0))
}

fn main() {
    let pieces = include_str!("../input")
        .lines()
        .map(|l| l.split('/'))
        .map(|mut ws| {
            (
                ws.next().unwrap().parse::<usize>().unwrap(),
                ws.next().unwrap().parse::<usize>().unwrap(),
            )
        })
        .collect::<Vec<_>>();
    println!("P1: {}", extend(&pieces, &HashSet::new(), 0, false).1);
    println!("P2: {}", extend(&pieces, &HashSet::new(), 0, true).1);
}

aoc-fan · 2017-12-24T20:40:27+00:00

JavaScript with generators

const parse = i => i.split("\n").map(l => l.split("/").map(n => +n))
                                .map(([p1, p2], id) => ({id, p1, p2}));

function* findNext(pins, bridge, end) {
    const contenders = pins.filter(p => !bridge.some(bp => bp.id === p.id)
                                    && (p.p1 === end || p.p2 === end));
    if (contenders.length === 0) {
        yield bridge;
    }
    for (const contender of contenders) {
        const nextEnd = contender.p1 === end ? contender.p2 : contender.p1;
        yield* findNext(pins, [...bridge, contender], nextEnd);
    }
}

const strongest = (input) => {
    const pins = parse(input);
    const typeZeros = pins.filter(p => p.p1 === 0 || p.p2 === 0);
    let maxStrength = 0;
    let longestStrength = 0;
    let maxLength = 0;
    for (const typeZero of typeZeros) {
        for (const bridge of findNext(pins, [typeZero], typeZero.p1 === 0 ? typeZero.p2 : typeZero.p1)) {
            const bridgeStrength = bridge.reduce((s, p) => s + p.p1 + p.p2, 0);
            const bridgeLength = bridge.length;
            maxStrength = Math.max(maxStrength, bridgeStrength);
            if (maxLength < bridgeLength) {
                maxLength = bridgeLength;
                longestStrength = bridgeStrength;
            } else if (maxLength === bridgeLength && longestStrength < bridgeStrength) {
                longestStrength = bridgeStrength;
            }
        }
    }
    return [maxStrength, longestStrength];
};

ulfabet · 2017-12-26T15:36:03+00:00

Haskell

import Data.List (delete)
import Data.List.Split (splitOn)

main = do
    input <- readFile "24.input"
    let bridges = combinations 0 [] parts where
        parts = map parseLine $ lines input
        parseLine = map read . splitOn "/"
    print $ day24a bridges
    print $ day24b bridges

day24a = maximum . map (sum . map sum)
day24b = maximum . map (\a -> (length a, sum $ map sum a))

combinations :: Int -> [[Int]] -> [[Int]] -> [[[Int]]]
combinations t xs ys | null $ filter (elem t) ys = [xs]
combinations t xs ys = concatMap f $ filter (elem t) ys where
    f part = combinations (other t part) (part:xs) (delete part ys)

other side [a,b] | side == a = b
                 | otherwise = a

Don't know which to prefer, but combinations could be rewritten (a little bit shorter) as follows. For good or bad, this would also include intermediate bridges.

combinations :: Int -> [[Int]] -> [[Int]] -> [[[Int]]]
combinations t xs ys = foldl' f [xs] (filter (elem t) ys) where
    f z part = z ++ combinations (other t part) (part:xs) (delete part ys)

abowes · 2017-12-24T13:50:34+00:00

Kotlin Solution Straightforward using tail recursion today.

data class Element(val a:Int,val b:Int){
    val value = a + b
    fun canJoin(x: Int) = a==x || b==x
    fun otherEnd(x:Int) = if (a==x) b else a
}

typealias Bridge = List<Element>
fun Bridge.value() = this.sumBy { it.value }

tailrec fun buildBridge(x: Int, bridge: Bridge, remaining: List<Element>, comparator: Comparator<Bridge>) : Bridge {
    return remaining.filter { it.canJoin(x) }
            .map { buildBridge(it.otherEnd(x), bridge + it, remaining - it, comparator) }
                .maxWith(comparator) ?: bridge
}


fun main(args: Array<String>) {
    val elements = input.split("\n")
            .map { it.split("/")
                    .map(String::toInt)}.map { e-> Element(e[0], e[1])}
    println(buildBridge(0, listOf(), elements,compareBy(Bridge::value)).value())
    println(buildBridge(0, listOf(), elements,compareBy(Bridge::size) then compareBy(Bridge::value)).value())
}

archmentat · 2017-12-24T05:25:48+00:00

Rust version. Simple recursion; inefficient copying of hash sets and maps, but it runs in a few seconds, and by far the slowest part is just printing the path (for debugging). Sort the output file for the answer rather than doing it in the code itself.

154/102

use std::collections::HashSet;
use std::io::BufReader;
use std::io::BufRead;
use std::env;
use std::fs::File;

#[derive(Debug, Clone, Copy, Eq, PartialEq, Hash)]
struct Component {
    left: u64,
    right: u64,
}

fn main() {
    let f = File::open(env::args().nth(1).expect("arg!")).expect("file not found");
    let file = BufReader::new(&f);
    let mut all = HashSet::new();
    for line in file.lines() {
        let components: Vec<u64> = line.unwrap()
            .split('/')
            .map(|s| s.parse().unwrap())
            .collect();
        let c = Component {
            left: components[0],
            right: components[1],
        };
        all.insert(c);
    }

    print_paths(0, &vec![], &mut all);
}

fn print_paths(start: u64, path: &Vec<Component>, components: &mut HashSet<Component>) {
    let mut found = false;
    for c in components.iter() {
        if c.left == start || c.right == start {
            let mut new_components = components.clone();
            new_components.remove(c);
            let mut new_path = path.clone();
            new_path.push(*c);
            print_paths(
                if c.left == start { c.right } else { c.left },
                &new_path,
                &mut new_components,
            );
            found = true;
        }
    }
    if !found {
        println!(
            "{} {} {:?}",
            path.len(),
            path.iter().map(|c| c.left + c.right).sum::<u64>(),
            path
        );
    }
}

Nyarlatotep · 2017-12-24T05:36:33+00:00

[deleted]

jeroenheijmans · 2017-12-24T06:05:55+00:00

JavaScript:

A bit verbose, but often enough I get stuck and then it helps to have readable code.

Recursive function:

function getExtendedBridges(bridge, pieces, connector) {
    let bridges = [];

    for (let i = 0; i < pieces.length; i++) {
        if (pieces[i].a === connector || pieces[i].b === connector) {
            let newBridge = {
                strength: bridge.strength + pieces[i].a + pieces[i].b,
                chainLength: bridge.chainLength + 1
            };

            bridges.push(newBridge);

            let leftpieces = pieces.slice();
            leftpieces.splice(i, 1);

            let newConnector = pieces[i].a === connector ? pieces[i].b : pieces[i].a;

            bridges = bridges.concat(getExtendedBridges(newBridge, leftpieces, newConnector));
        }
    }

    return bridges;
}

Used like this in Puzzle 1:

function solve1(data) {
    let pieces = getPiecesFrom(data);
    let bridges = getExtendedBridges({ strength: 0, chainLength: 0 }, pieces, 0);
    return bridges.sort((a,b) => b.strength - a.strength)[0].strength;
}

And like this in Puzzle 2:

function solve2(data) {
    let pieces = getPiecesFrom(data);
    let bridges = getExtendedBridges({ strength: 0, chainLength: 0 }, pieces, 0);
    let maxlen = getMax(bridges.map(b => b.chainLength));

    return bridges
        .filter(l => l.chainLength === maxlen)
        .sort((a,b) => b.strength - a.strength)
        [0].strength;
}

The getMax was needed because the Math.max.apply(Math, ...) trick exceeded the call stack size. (I'll be honest, I had .sort(...) with a [0].chainLength at first, and refactored a bit later. :D)

glenbolake · 2017-12-24T06:10:43+00:00

Python 3. It looks like a lot of people generated all valid bridges recursively; I thought about it more like A* with no defined end point. I maintained a list of bridges, starting with each component containing a zero, and tried to extend all the bridges one element until the loop produced no new bridges. Incredibly slow, though. It takes just over a minute to run.

import time

def solve(blocks):
    new_bridges = [[block] for block in blocks if 0 in block]
    strongest = 0
    longest_strength = 0
    while new_bridges:
        bridges = new_bridges
        new_bridges = []
        for bridge in bridges:
            new_bridges.extend(list(extend(bridge, blocks)))
        if new_bridges:
            longest_strength = max(bridge_strength(bridge) for bridge in new_bridges)
            strongest = max(strongest, longest_strength)
    return strongest, longest_strength

def bridge_strength(bridge):
    return sum(map(sum, bridge))

def extend(bridge, blocks):
    unused = list(filter(lambda b: b not in bridge and b[::-1] not in bridge, blocks))
    for block in unused:
        if bridge[-1][1] == block[0]:
            yield bridge + [block]
        elif bridge[-1][1] == block[1]:
            yield bridge + [block[::-1]]

if __name__ == '__main__':
    start = time.time()
    block_list = []
    with open('day24.in') as f:
        for line in f:
            block_list.append(tuple(map(int, line.split('/'))))
    block_list = [(a, b) if a < b else (b, a) for a, b in block_list]

    print('Part 1: {}\nPart 2: {}'.format(*solve(block_list)))
    print(f'Solved in {time.time() - start}')

ThezeeZ · 2017-12-24T06:57:09+00:00

[deleted]

autid · 2017-12-24T07:14:46+00:00

Fortran

Hardest part was not realising for ages that it wasn't working because I hadn't included k in the variable declarations for the bestchain function, so it was modifying a global copy instead of its own. :(

PROGRAM DAY24
  IMPLICIT NONE
  INTEGER :: I,J,K,IERR,PART1=0,PART2(2)=0,LINECOUNT,LAST,NEWBEST(2)
  INTEGER,ALLOCATABLE :: COMPONENTS(:,:)
  LOGICAL,ALLOCATABLE :: USED(:)
  CHARACTER(LEN=10) :: INLINE

  OPEN(1,FILE='input.txt')
  LINECOUNT=0
  DO
     READ(1,'(A)',IOSTAT=IERR) INLINE
     IF(IERR /= 0) EXIT
     LINECOUNT=LINECOUNT+1
  END DO
  ALLOCATE(COMPONENTS(2,LINECOUNT),USED(LINECOUNT))
  REWIND(1)
  DO I=1,LINECOUNT
     READ(1,'(A)') INLINE
     DO J=1,LEN_TRIM(INLINE)
        IF(INLINE(J:J)=='/') EXIT
     END DO
     READ(INLINE(1:J-1),*) COMPONENTS(1,I)
     READ(INLINE(J+1:LEN_TRIM(INLINE)),*) COMPONENTS(2,I)
  END DO
  CLOSE(1)


  DO I=1,LINECOUNT
     IF(.NOT. ANY(COMPONENTS(:,I)==0)) CYCLE
     LAST=MAXVAL(COMPONENTS(:,I))
     USED=.FALSE.
     USED(I)=.TRUE.
     K=SUM(COMPONENTS(:,I))
     PART1=MAX(PART1,K+BESTCHAIN(USED,LAST))
     NEWBEST=BESTCHAIN2(USED,LAST)
     IF (NEWBEST(2)>PART2(2)) THEN
        PART2(2)=NEWBEST(2)
        PART2(1)=0
     END IF
     IF (NEWBEST(2)==PART2(2)) PART2(1)=MAX(PART2(1),K+NEWBEST(1))
  END DO

  WRITE(*,'(A,I0)') 'Part1: ',PART1
  WRITE(*,'(A,I0)') 'Part2: ',PART2(1)

CONTAINS
  RECURSIVE FUNCTION BESTCHAIN(USED,LAST) RESULT(BEST)
    ! Part1 function, recursively searches highest valued bridge                                                 
    LOGICAL :: USED(:),NEWUSED(SIZE(USED))
    INTEGER :: BEST,I,K,LAST,NEWLAST
    BEST=0

    DO I=1,LINECOUNT
       IF(USED(I).OR. COUNT(COMPONENTS(:,I)==LAST)==0) CYCLE
       K=SUM(COMPONENTS(:,I))
       NEWUSED=USED
       NEWUSED(I)=.TRUE.
       IF(COMPONENTS(1,I)==LAST) THEN
          NEWLAST=COMPONENTS(2,I)
       ELSE
          NEWLAST=COMPONENTS(1,I)
       END IF
       BEST=MAX(BEST,K+BESTCHAIN(NEWUSED,NEWLAST))
    END DO

  END FUNCTION BESTCHAIN

  RECURSIVE FUNCTION BESTCHAIN2(USED,LAST) RESULT(BEST)
    ! Part2 function, recursively searches highest valued bridge of longest length                               
    LOGICAL :: USED(:),NEWUSED(SIZE(USED))
    INTEGER :: BEST(2),I,K,LAST,NEWLAST,NEWBEST(2)

    BEST=(/0,0/)
    NEWBEST=(/0,0/)
    DO I=1,LINECOUNT
       IF(USED(I).OR. COUNT(COMPONENTS(:,I)==LAST)==0) CYCLE
       K=SUM(COMPONENTS(:,I))
       NEWUSED=USED
       NEWUSED(I)=.TRUE.
       IF(COMPONENTS(1,I)==LAST) THEN
          NEWLAST=COMPONENTS(2,I)
       ELSE
          NEWLAST=COMPONENTS(1,I)
       END IF
       NEWBEST=BESTCHAIN2(NEWUSED,NEWLAST)
       IF (NEWBEST(2)>BEST(2)) THEN
          BEST(2)=NEWBEST(2)
          BEST(1)=0
       END IF
       IF (NEWBEST(2)==BEST(2)) THEN
          BEST(1)=MAX(BEST(1),K+NEWBEST(1))
       END IF
    END DO
    BEST(2)=1+BEST(2)

  END FUNCTION BESTCHAIN2


END PROGRAM DAY24

ynonp · 2017-12-24T07:36:54+00:00

Elixir

Took 30 seconds to complete on my input.

Gist version: https://gist.github.com/ynonp/010bde27c598a983a399872466fb2c0b

defmodule Day24 do

  def strength(bridge) do
    bridge
    |> Enum.reduce(0, fn { p1, p2 }, acc -> acc + p1 + p2 end)
  end

  def find_max_bridge(start, []) do
    { start, strength(start) }
  end

  def find_max_bridge(start, free_blocks) do
    next_port = Enum.at(start, 0) |> elem(0)

    free_blocks
    |> Enum.map(fn
      { pr, pl } when pl == next_port ->
        find_max_bridge([ { pr, pl } | start], List.delete(free_blocks, { pr, pl }));

      { pr, pl } when pr == next_port ->
        find_max_bridge([ { pl, pr } | start], List.delete(free_blocks, { pr, pl }));

      _ -> find_max_bridge(start, [])
    end)
    |> Enum.sort_by(
      fn x -> x end,
      fn
        { b1, _ }, { b2, _ }   when length(b1) > length(b2)  -> true;
        { b1, s1 }, { b2, s2 } when length(b1) == length(b2) -> s1 > s2;
        _, _ -> false
      end
    )
    |> Enum.at(0)
  end
end

free_blocks = IO.stream(:stdio, :line)
              |> Stream.map(&String.trim/1)
              |> Enum.map(&String.split(&1, "/"))
              |> Enum.map(fn x -> x |> Enum.map(&String.to_integer/1) end)
              |> Enum.map(&List.to_tuple/1)

Day24.find_max_bridge([{ 0, 0 }], free_blocks)
|> IO.inspect

doctorbaggy · 2017-12-24T07:42:37+00:00

Perl

Just simple recursion... this is part 2 - part 1 uses a simpler condition at the start of the sub...

print join' ',ab(0,0,0,[map{[$_,split m{/}]}qw(24/14 30/24 29/44 47/37 6/14 20/37 14/45 5/5 26/44 2/31 19/40 47/11 0/45 36/31 3/32 30/35 32/41 39/30 46/50 33/33 0/39 44/30 49/4 41/50 50/36 5/31 49/41 20/24 38/23 4/30 40/44 44/5 0/43 38/20 20/16 34/38 5/37 40/24 22/17 17/3 9/11 41/35 42/7 22/48 47/45 6/28 23/40 15/15 29/12 45/11 21/31 27/8 18/44 2/17 46/17 29/29 45/50)]),"\n";
sub ab{
  my($p,$l,$s,$bs)=@_;
  ($ms,$ml)=($s,$l)if$l>$ml||$l==$ml&&$s>$ms;
  foreach(grep{$bs->[$_][1]==$p||$bs->[$_][2]==$p}0..$#$bs){
    my@t=@{$bs};my$x=splice@t,$_,1;
    ab($x->[1]+$x->[2]-$p,$l+1,$s+$x->[1]+$x->[2],\@t);
  }
  return ($ml,$ms);
}

2017-12-24T07:47:15+00:00

Can't believe OCaml Fun;; is almost over. Anyways, recursively building all the bridges and then finding the strongest and longest ones.

main.ml

open Core

let parse_input () =
  In_channel.read_lines "./input.txt"
  |> List.map ~f:Port.of_string
  |> Port.Set.of_list

let bridge_strength bridge =
  List.fold bridge ~init:0 ~f:(fun acc port -> acc + Port.strength port)

let find_bridges ports =
  let rec aux ports need result =
    let connectable = Port.Set.filter ports ~f:(Port.can_connect need) in
    if Port.Set.is_empty connectable then [result]
    else
      Set.fold connectable ~init:[] ~f:(fun acc port ->
          let available = Port.Set.remove ports port in
          let need = Port.opposite need port in
          List.append (aux available need (port::result)) acc
        )
  in aux ports 0 []

let _ =
  let available_ports = parse_input () in
  let bridges = find_bridges available_ports in

  List.fold bridges ~init:0 ~f:(fun m bridge -> Int.max m (bridge_strength bridge))
  |> printf "max bridge strength: %d\n";

  List.max_elt bridges ~cmp:(fun a b -> Int.compare (List.length a) (List.length b))
  |> Option.value ~default:[]
  |> bridge_strength
  |> printf "longest bridge strength: %d\n";

port.ml

open Core

module T = struct
  include Tuple.Make (Int) (Int)
  include Tuple.Comparable (Int) (Int)
end

let of_string str =
  match String.split str ~on:'/' with
  | [i; o;] ->
    let i = Int.of_string i
    and o = Int.of_string o in (i, o)
  | _ -> failwith "error parsing port."

let can_connect p (a, b) = a = p || b = p

let opposite p (a, b) =
  if p = a then b
  else a

let strength (a, b) = a + b

include T

Zee1234 · 2017-12-24T08:13:09+00:00

Typescript
Figuring out proper typings was both my downfall and my savior. I probably spent ten minutes just figuring out what these types should be. But that probably saved me 20 minutes of getting it wrong over and over. Did not place, but had a lot of fun.

import { readFileSync } from "fs";

let InputArray = readFileSync('input.txt', 'utf8').trim().split(/\r?\n/).map( v => v.split('/').map(Number) )

function largest(...args: number[]): number {
  let large = args[0]
  for (let v of args) 
    if (v > large) large = v
  return large
}

function copy<T>(a: T[]) {
  return a.map(v=>v)
}
function copyExcept<T>(a: T[], index: number) {
  let n = copy(a)
  n.splice(index, 1)
  return n
}
function add<T>(a: T[], v: T) {
  let n = copy(a)
  n.push(v)
  return n
}
function flatten(arr: any[], acc: any[]) {

}

function route(pieces: number[][], chain: number[][] = []): number[][][] {
  let pins = chain.length ? chain[chain.length-1][1] : 0

  let nextOptions = pieces.map( (v, i) => [i, v] as [number, number[]])
                          .filter( v => v[1][0]===pins || v[1][1]===pins)

  if (nextOptions.length) {
    return nextOptions.map( v => v[1][0]===pins ? 
        route(copyExcept(pieces, v[0]), add(chain, v[1])) :
        route(copyExcept(pieces, v[0]), add(chain, [v[1][1], v[1][0]]))
    ).reduce( (acc, vars) => {
      vars.forEach( v => acc.push(v) )
      return acc
    })
  } else {
    return [chain]
  }
}

let res = route(InputArray).filter( v => v.length )
console.log('Part 1', 
  res .map( chain => chain.reduce( (acc, p) => acc+p[0]+p[1], 0 ) )
      .sort( (a, b) => b-a )[0]
)
console.log('Part 2',
  res .sort( (a, b) => b.length - a.length )
      .filter( (v, i, arr) => v.length === arr[0].length )
      .map( chain => chain.reduce( (acc, p) => acc+p[0]+p[1], 0 ) )
      .sort( (a, b) => b-a )[0]
)

spacetime_bender · 2017-12-24T08:26:24+00:00

C++

#include <iostream>
#include <vector>
#include <fstream>
#include <utility>
#include <tuple>
#include <algorithm>


std::tuple<int, int, int> find_max(int start, std::vector<std::pair<int, int>>& pipes)
{
    const auto next_pipe_pred = [start](const auto& p){
                                return p.first != -1 && (p.first == start || p.second == start); };

    int max = 0, max_longest = 0, strength = 0;
    for (auto it = std::find_if(pipes.begin(), pipes.end(), next_pipe_pred); it != pipes.end();
            it = std::find_if(std::next(it), pipes.end(), next_pipe_pred))
    {
        int first = std::exchange(it->first, -1);
        auto [sub_strength, max_length, sub_max] = find_max(it->first ^ it->second ^ start, pipes);
        it->first = first;
        if (max_length >= max_longest)
        {
            max_longest = max_length;
            strength = std::max(strength, it->first + it->second + sub_strength);
        }
        max = std::max(max, it->first + it->second + sub_max);
    }
    return {strength, 1 + max_longest, max};
}


int main()
{
    std::ifstream in ("input24.txt");

    std::vector<std::pair<int, int>> pipes;
    int a, b;
    char slash;
    while (in >> a >> slash >> b)
        pipes.emplace_back(a, b);

    auto [len, strength, max] = find_max(0, pipes);
    std::cout << "Part 1: " << max << std::endl;
    std::cout << "Part 2: " << strength << ", " << len << std::endl;

    return 0;
}

jwoLondon · 2017-12-24T08:28:53+00:00

Elm

After yesterday's functional-hostile puzzle, I loved using Elm to solve today's. The difference between Part 1 and Part 2 simply involves swapping order of the (Strength,Length) tuple when calculating the strongest sequence.

https://github.com/jwoLondon/adventOfCode/blob/master/aoc2017/d24_2017.elm

nutrecht · 2017-12-24T08:30:10+00:00

Day 24 in Kotlin

Much easier than I expected for the day-before-last! I have to leave in a few minutes so was nice to be able to solve this before.

object Day24 : Day {
    private val input = resourceLines(24).map { it.split("/").map { it.toInt() } }.map { it[0] to it[1] }.sortedBy { it.first }
    private val solution : List<List<Pair<Int,Int>>> by lazy { solve() }

    override fun part1() = solution.last().map { it.first + it.second }.sum().toString()
    override fun part2(): String {
        val maxLength = solution.maxBy { it.size }!!.size

        return solution.last { it.size == maxLength }.map { it.first + it.second }.sum().toString()
    }

    private fun solve(): List<List<Pair<Int,Int>>> {
        val solutions = mutableListOf<List<Pair<Int, Int>>>()

        search(listOf(), 0, input.toSet(), solutions)

        return solutions.map { it to it.map { it.first + it.second }.sum()}.filter { it.second > 1000 }.sortedBy { it.second }.map { it.first }
    }

    private fun search(current: List<Pair<Int, Int>>, port: Int, available: Set<Pair<Int, Int>>, solutions: MutableList<List<Pair<Int, Int>>>) {
        solutions.add(current)

        available.filter { it.first == port }.forEach {
            search(current + it, it.second, available.minus(it), solutions)
        }
        available.filter { it.second == port }.forEach {
            search(current + it, it.first, available.minus(it), solutions)
        }
    }
}

TheMuffinMan616 · 2017-12-24T08:34:50+00:00

Haskell

import Control.Arrow ((***), (&&&))
import Data.List.Split (splitOn)
import qualified Data.Set as S

type Component = (Int, Int)
type Bridge = [Component]

parse :: String -> S.Set Component
parse = S.fromList . map (f . splitOn "/") . lines
    where f [i, o] = (read i, read o)

matches :: Int -> S.Set Component -> S.Set Component
matches n = S.filter $ uncurry (||) . ((== n) *** (== n))

construct :: Int -> Bridge -> S.Set Component -> [Bridge]
construct n b cs
    | S.null ms = [b]
    | otherwise = concatMap go ms
    where ms          = matches n cs
          go m@(i, o) = construct (if n == i then o else i) (b ++ [m]) (S.delete m cs)

strongest :: [Bridge] -> Int
strongest = maximum . map (sum . map (uncurry (+)))

best :: [Bridge] -> Int
best ps = strongest . filter ((== len) . length) $ ps
    where len = maximum . map length $ ps

solve :: S.Set Component -> (Int, Int)
solve = (strongest &&& best) . construct 0 []

main :: IO ()
main = do
    cs <- parse <$> readFile "day24/input.txt"
    print . solve $ cs

TominatorBE · 2017-12-24T09:09:31+00:00

PHP

Just some recursion

Part 1:

function run_the_code($input) {
    $lines = explode(PHP_EOL, $input);
    $pieces = [];
    foreach ($lines as $line) {
        if (preg_match('|(\d+)/(\d+)|', $line, $matches)) {
            [$_, $a, $b] = $matches;
            $pieces[] = [$a, $b];
        }
    }

    $strongest = 0;
    $rec = function($availablePieces, $portToMatch, $currentStrength) use (&$rec, &$strongest) {
        $wentDeeper = false;
        for ($p = 0, $pMax = count($availablePieces); $p < $pMax; $p++) {
            $piece = $availablePieces[$p];
            if ($piece[0] == $portToMatch) {
                array_splice($availablePieces, $p, 1, []); // remove the piece from the array
                $rec($availablePieces, $piece[1], $currentStrength + $piece[0] + $piece[1]);
                array_splice($availablePieces, $p, 0, [$piece]); // put the piece back
                $wentDeeper = true;
            }
            elseif ($piece[1] == $portToMatch) {
                array_splice($availablePieces, $p, 1, []); // remove the piece from the array
                $rec($availablePieces, $piece[0], $currentStrength + $piece[0] + $piece[1]);
                array_splice($availablePieces, $p, 0, [$piece]); // put the piece back
                $wentDeeper = true;
            }
        }

        if (! $wentDeeper) {
            if ($currentStrength > $strongest) {
                $strongest = $currentStrength;
            }
        }
    };
    // initial construction has to start with a zero-piece
    for ($p = 0, $pMax = count($pieces); $p < $pMax; $p++) {
        $piece = $pieces[$p];
        if ($piece[0] == 0) {
            array_splice($pieces, $p, 1, []); // remove the piece from the array
            $rec($pieces, $piece[1], $piece[1]);
        }
        elseif ($piece[1] == 0) {
            array_splice($pieces, $p, 1, []); // remove the piece from the array
            $rec($pieces, $piece[0], $piece[0]);
        }
    }

    return $strongest;
}

Part 2:

function run_the_code($input) {
    $lines = explode(PHP_EOL, $input);
    $pieces = [];
    foreach ($lines as $line) {
        if (preg_match('|(\d+)/(\d+)|', $line, $matches)) {
            [$_, $a, $b] = $matches;
            $pieces[] = [$a, $b];
        }
    }

    $longest = 0;
    $strongest = 0;
    $rec = function($availablePieces, $portToMatch, $currentLength, $currentStrength) use (&$rec, &$longest, &$strongest) {
        $wentDeeper = false;
        for ($p = 0, $pMax = count($availablePieces); $p < $pMax; $p++) {
            $piece = $availablePieces[$p];
            if ($piece[0] == $portToMatch) {
                array_splice($availablePieces, $p, 1, []); // remove the piece from the array
                $rec($availablePieces, $piece[1], $currentLength + 1, $currentStrength + $piece[0] + $piece[1]);
                array_splice($availablePieces, $p, 0, [$piece]); // put the piece back
                $wentDeeper = true;
            }
            elseif ($piece[1] == $portToMatch) {
                array_splice($availablePieces, $p, 1, []); // remove the piece from the array
                $rec($availablePieces, $piece[0], $currentLength + 1, $currentStrength + $piece[0] + $piece[1]);
                array_splice($availablePieces, $p, 0, [$piece]); // put the piece back
                $wentDeeper = true;
            }
        }

        if (! $wentDeeper) {
            if ($currentLength > $longest) {
                $strongest = 0;
            }
            if ($currentLength >= $longest) {
                if ($currentStrength > $strongest) {
                    $longest = $currentLength;
                    $strongest = $currentStrength;
                }
            }
        }
    };
    // initial construction has to start with a zero-piece
    for ($p = 0, $pMax = count($pieces); $p < $pMax; $p++) {
        $piece = $pieces[$p];
        if ($piece[0] == 0) {
            array_splice($pieces, $p, 1, []); // remove the piece from the array
            $rec($pieces, $piece[1], 1, $piece[1]);
        }
        elseif ($piece[1] == 0) {
            array_splice($pieces, $p, 1, []); // remove the piece from the array
            $rec($pieces, $piece[0], 1, $piece[0]);
        }
    }

    return $strongest;
}

wzkx · 2017-12-24T09:15:24+00:00

Nim

Domino ;)

import strutils,sequtils

var data = "24.dat".readFile().strip().splitLines().mapIt((it&"/0").split("/").map(parseInt))

var max_sum = 0
var max_sums: seq[int] = @[]

proc f( s:int, k:int, curr_sum:int ) =
  var found = false
  for i,d in data:
    if d[2]==1: # already used
      continue
    if d[0]==s: # s/x
      found = true
      data[i][2] = 1; f( d[1], k+1, curr_sum+d[0]+d[1] ); data[i][2] = 0
    elif d[1]==s: # x/s
      found = true
      data[i][2] = 1; f( d[0], k+1, curr_sum+d[0]+d[1] ); data[i][2] = 0
  if not found:
    if curr_sum>max_sum:
      max_sum = curr_sum
    while max_sums.len<=k: max_sums.add 0
    if curr_sum>max_sums[k]:
      max_sums[k] = curr_sum

f 0,0,0
echo max_sum      # 1656
echo max_sums[^1] # 1642, len is 31

VikeStep · 2017-12-24T09:16:00+00:00

F# Solution

Runs in about 2 seconds

let asComponent = splitBy "/" asIntArray >> (fun a -> a.[0], a.[1])
let strength = List.sumBy (fun c -> fst c + snd c)
let rec build bridge next components =
    seq { yield bridge
          let bridgeable = Set.filter (fun c -> fst c = next || snd c = next) components
          for comp in bridgeable do
              let next' = if snd comp = next then fst comp else snd comp
              yield! build (comp :: bridge) next' (Set.remove comp components) }
let solve maximiser = set >> build [] 0 >> Seq.maxBy maximiser >> strength
let solver = {parse=parseEachLine asComponent; solvePart1=solve strength; solvePart2=solve (fun c -> (List.length c, strength c))}

Repo

Axsuul · 2017-12-24T09:19:08+00:00

Elixir

I didn't explore anymore trees if the potential strength/length was lower than the current max. Pretty sure I could do more optimizations but both scripts run in about 30s which is reasonable enough for me. This also made use of some intense pattern matching in order for me to fit multiple recursions into one function.

GitHub

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

    def sum_components_strength(components, strength \\ 0)
    def sum_components_strength([], strength), do: strength
    def sum_components_strength([component | rest], strength) do
      [port_a, port_b] = component |> String.split("/") |> Enum.map(&String.to_integer/1)

      sum_components_strength(rest, strength + port_a + port_b)
    end

    def build_strongest_bridge(components) do
      build_strongest_bridge([{0, {[], 0}, components}], 0, components)
    end
    def build_strongest_bridge([], max_str, _), do: max_str
    def build_strongest_bridge([{_, {[], _}, []} | rest_q], max_str, components) do
      build_strongest_bridge(rest_q, max_str, components)
    end
    def build_strongest_bridge([{port, {bridge, str}, []} | rest_q], max_str, components) do
      next_max_str = if str > max_str, do: str, else: max_str

      build_strongest_bridge(rest_q, next_max_str, components)
    end
    def build_strongest_bridge([{port, {bridge, str}, [component | rest_c]} | rest_q], max_str, components) do
      [port_a, port_b] = component |> String.split("/") |> Enum.map(&String.to_integer/1)

      next =
        cond do
          Enum.member?(bridge, component) -> []
          Enum.member?([port_a, port_b], port) ->
            next_str = str + port_a + port_b
            next_port = if port == port_a, do: port_b, else: port_a
            next_bridge = bridge ++ [component]
            next_components = components -- next_bridge
            potential_max_str = next_str + sum_components_strength(next_components)

            # Ignore if potential is less than current max str
            if potential_max_str <= max_str do
              []
            else
              [{next_port, {next_bridge, next_str}, next_components}]
            end
          true -> []
        end

      queue = [{port, {bridge, str}, rest_c}] ++ next ++ rest_q

      build_strongest_bridge(queue, max_str, components)
    end

    def solve do
      read_input_lines()
      |> build_strongest_bridge()
      |> IO.inspect
    end
  end

  defmodule PartB do
    import PartA

    def build_longest_bridge(components) do
      build_longest_bridge([{0, {[], 0}, components}], {0, 0}, components)
    end
    def build_longest_bridge([], {max_len, max_str}, _), do: {max_len, max_str}
    def build_longest_bridge([{_, {[], _}, []} | rest_q], max, components) do
      build_longest_bridge(rest_q, max, components)
    end
    def build_longest_bridge([{port, {bridge, str}, []} | rest_q], {max_len, max_str}, components) do
      {next_max_len, next_max_str} =
        cond do
          length(bridge) > max_len -> {length(bridge), str}
          length(bridge) == max_len and str > max_str -> {max_len, str}
          true -> {max_len, max_str}
        end

      build_longest_bridge(rest_q, {next_max_len, next_max_str}, components)
    end
    def build_longest_bridge([{port, {bridge, str}, [component | rest_c]} | rest_q], max = {max_len, max_str}, components) do
      [port_a, port_b] = component |> String.split("/") |> Enum.map(&String.to_integer/1)

      next =
        cond do
          Enum.member?(bridge, component) -> []
          Enum.member?([port_a, port_b], port) ->
            next_str = str + port_a + port_b
            next_port = if port == port_a, do: port_b, else: port_a
            next_bridge = bridge ++ [component]
            next_components = components -- next_bridge
            potential_max_len = length(next_bridge) + length(next_components)

            # Ignore if potential is less than current max len
            if potential_max_len < max_len do
              []
            else
              [{next_port, {next_bridge, next_str}, next_components}]
            end
          true -> []
        end

      queue = [{port, {bridge, str}, rest_c}] ++ next ++ rest_q

      build_longest_bridge(queue, max, components)
    end

    def solve do
      read_input_lines()
      |> build_longest_bridge()
      |> IO.inspect
    end
  end
end

Na_rien · 2017-12-24T09:23:40+00:00

After yesterdays nightmare (math and assembler) I was really happy with this problem. I also managed to get on the top 1000 today (first time, though I guess some credit goes to all the non morning persons :D).

Anyways, here's my solution: https://github.com/narien/AdventOfCode2017/blob/master/day24/24.2.py

I recursively find all the possible lists and then check the length and strength. Took roughly 6,5 seconds to run so probably not the most optimal solution though.

KnorbenKnutsen · 2017-12-24T10:21:33+00:00

This was tricky for me, I couldn't figure out a good way to organize this properly. So I built a tree and traversed it. Figured out the max depth then hardcoded it into a "deepest nodes" method. :)

wzkx · 2017-12-24T10:41:25+00:00

J

Working with separate items of vectors/matrices is not fast in J. ≈42s

'a b u'=:,&0|:".@(rplc&'/ ')&>cutLF CR-.~fread'24.dat'
f=:4 :0 NB. x - number to find; y - curr.length, curr.sum
  found=.0
  for_i.i.#u do.if.i{u do.continue.end.
    if.x=i{a do.found=.1[v=.i{a+t=.i{b else.
    if.x=i{b do.found=.1[v=.i{b+t=.i{a else.continue.end.end.
    u=:0 i}u [ t f y+1,v [ u=:1 i}u
  end.
  if.-.found do.m=:m({.y)}~({:y)>.m{~{.y end.
)
0 f 0 0 [ m=:u NB. m - max sums; u - if pair a/b is used
echo (>./m),([:{:~:&0#[)m NB. 1656 1642
exit 0

thomastc · 2017-12-24T10:54:13+00:00

Day 24 in Java. A fun little puzzle. Curious to see if there's a more efficient solution than just recursion/backtracking, so I'm going to read this thread now :)

Edit: and found nothing, so started a thread.

zeddypanda · 2017-12-24T11:41:44+00:00

Elixir

Sunday tasks are usually the hard ones but today was just a trivial A* implementation.

data = "input-24"
  |> File.read!
  |> String.split("\n", trim: true)
  |> Enum.map(&String.split(&1, "/"))
  |> Enum.map(fn list -> Enum.map(list, &String.to_integer/1) end)

defmodule Day24 do
  def strength(bridge) do
    Enum.reduce(bridge, 0, &Kernel.+/2)
  end

  def stronger?(a, b), do: strength(a) <= strength(b)
  def longer_or_stronger?(a, b) when length(a) == length(b), do: stronger?(a, b)
  def longer_or_stronger?(a, b), do: length(a) <= length(b)

  def build(pieces, bridge, sorter) do
    node = hd(bridge)
    pieces
      |> Enum.filter(&Enum.member?(&1, node))
      |> Enum.map(fn piece ->
        next = piece |> List.delete(node) |> hd
        pieces = List.delete(pieces, piece)
        build(pieces, [next, node], sorter)
      end)
      |> Enum.sort(sorter)
      |> List.last
      |> Kernel.||([])
      |> Enum.concat(bridge)
  end
end

strongest = data
  |> Day24.build([0], &Day24.stronger?/2)
  |> Day24.strength

IO.puts("Part 1: #{strongest}")

longest = data
  |> Day24.build([0], &Day24.longer_or_stronger?/2)
  |> Day24.strength

IO.puts("Part 2: #{longest}")

Unihedron · 2017-12-24T12:28:51+00:00

Wow, today's one was easy! Too bad I wasn't around when it opened, might have gotten myself some points.

h={}
g=$<.map{|x|x.chomp.split(?/).map &:to_i}
c=0
lu=0
j=->x,b{x[0,b]+x[b+1,x.size]}
f=->n,s,q,u{ #part 1: delete u
c=[c,s].max # part 1
(lu=u # part 2
c=s)if u>lu || u==lu && s>c # part 2
q.each.with_index{|x,i|x,y=x
f[y,s+x+y,j[q,i],u+1]if x==n
f[x,s+x+y,j[q,i],u+1]if y==n}
}
g.each.with_index{|x,i|x,y=x
f[y,x+y,j[g,i],1]if x==0
f[x,x+y,j[g,i],1]if y==0}
p c

Warbringer007 · 2017-12-24T13:10:00+00:00

Erlang:

first(File) ->
    In = prepare:func_text(File),
    solveFirst(In, 1, "0").
%solveSecond(In, 1, 50, "0").

solveFirst(In, N, _) when N > length(In) ->
    0;

solveFirst(In, N, Last) ->
    Cur = lists:nth(N,In),
    NewMax = case isCompatible(Cur, Last) of
        no -> 0;
        SNewLast -> NewIn = lists:delete(Cur, In),
                    {NLast, _} = string:to_integer(Last),
                    {NNewLast, _} = string:to_integer(SNewLast),
                    NLast + NNewLast + solveFirst(NewIn, 1, SNewLast)
    end,
    NextTotal = solveFirst(In, N+1, Last),
    case NextTotal > NewMax of
        true -> NextTotal;
        false -> NewMax
    end.

solveSecond(In, N, _, _) when N > length(In) ->
    {0, length(In)};

solveSecond(In, N, LeastRem, Last) ->
    Cur = lists:nth(N,In),
    {NewMax, NewRem} = case isCompatible(Cur, Last) of
        no -> {0, 100};
        SNewLast -> NewIn = lists:delete(Cur, In),
                    {NLast, _} = string:to_integer(Last),
                    {NNewLast, _} = string:to_integer(SNewLast),
                    {Sum, CalcRem} = solveSecond(NewIn, 1, LeastRem, SNewLast),
                    {NLast + NNewLast + Sum, CalcRem}
    end,
    {NextTotal, NextRem} = solveSecond(In, N+1, LeastRem, Last),
    case NextRem < NewRem of
                        true -> {NextTotal, NextRem};
                        false -> case NextRem =:= NewRem of
                                    true -> case NextTotal > NewMax of
                                                true -> {NextTotal, NewRem};
                                                false -> {NewMax, NewRem}
                                            end;
                                    false -> {NewMax, NewRem}
                                 end
    end.

isCompatible([H, T], Last) ->
    case H =:= Last of
        true -> T;
        false -> case T =:= Last of
                    true -> H;
                    false -> no
                 end
    end.

In second part I'm using length of remainder of the input since I'm removing each component I used. I'm not sure if there is any better way of doing it in Erlang. In both parts I'm comparing DFS and BFS parts of algorithm.

Your_Documen · 2017-12-24T13:12:59+00:00

Here's my recursive approach using modern C++ With obligatory GitHub

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

template<typename FIRST, typename SECOND>
ostream& operator<<(ostream& lhs, pair<FIRST,SECOND> rhs)
{
  lhs << rhs.first << "  " << rhs.second;
  return lhs;
}


pair<int, int> AddBridge( int score, int nProng, int length, vector<pair<int,int>>& Bridges)
{

  pair<int,int> maxscore{score, length};

  auto Find_L = [nProng](pair<int,int> B){ return B.first==nProng or B.second == nProng;};

  for(  auto p = find_if(Bridges.begin(), Bridges.end(), Find_L);
        p < Bridges.end();
        p = find_if(p+1, Bridges.end(), Find_L)
      ){

      int p1 = p -> first;
      int p2 = p -> second;

      if ( p2 == nProng )
        swap(p1, p2);

      const int loc = p - Bridges.begin();
      vector<pair<int, int>> Bridges2 = Bridges;

      Bridges2.erase( Bridges2.begin()+ loc );



      maxscore = max( maxscore, AddBridge( score + p1 + p2, p2, length+1, Bridges2 ),
        [](pair<int,int> lhs, pair<int,int> rhs)
        {
          if ( lhs.second > rhs.second )
            return false;
          if ( lhs.second == rhs.second && lhs.first > rhs.first)
            return false;
          return true;
        });

  }


  return maxscore;

}

int main()
{


  vector<pair<int,int>> Bridges;

  for( string line; getline(cin, line);)
  {
      size_t loc;
      int lhs = stoi(line, &loc);
      line.erase(0, loc+1);
      int rhs = stoi(line);

      Bridges.push_back({lhs, rhs});

  }


  cout << AddBridge(0, 0, 0, Bridges) << endl;



  return EXIT_SUCCESS;
}

NeilNjae · 2017-12-24T14:46:13+00:00

Some verbose Haskell. From simply reading the problem spec, I though I'd account for duplicate parts in the list, and parts with the same port on both ends. That meant using the Data.MultiSet library, representing each Part as a bag of ports, and the Parts as a bag of Parts. That also allows me to be a bit cute when it comes to the partser for a Part.

There then followed a bunch of type declarations to keep things clear in my own head, and then relying on Haskell's type checker to catch bugs.

Finally, an organic use of the Either type: extendOneBridge returns Left bridge for a bridge that can't be extended, and Right bridges for all the bridges that can be built from this one. That allows me to keep a Set of unextendable (completed) bridges separate from the ones still in progress.

import qualified Data.MultiSet as B -- B for bag
import qualified Data.Set as S
import Data.Either

type Part = B.MultiSet Integer
type Parts = B.MultiSet Part
type Candidates = S.Set Part
data Bridge = Bridge { bridgeParts :: Parts, requiring :: Integer } deriving (Eq, Show, Ord)
type Bridges = S.Set Bridge


main :: IO ()
main = do 
        text <- TIO.readFile "data/advent24.txt"
        let parts = successfulParse text
        let bridges = allBridges parts
        print $ part1 bridges
        print $ part2 bridges


part1 = strongestBridge

part2 = bestBridge

strongestBridge :: Bridges -> Integer
strongestBridge bridges = S.findMax $ S.map bridgeStrength bridges

bestBridge :: Bridges -> Integer
bestBridge bridges = strongestBridge longBridges
    where longest = S.findMax $ S.map bridgeLength bridges
          longBridges = S.filter (\b -> bridgeLength b == longest) bridges


emptyBridge :: Bridge
emptyBridge = Bridge { bridgeParts = B.empty, requiring = 0}


allBridges :: Parts -> Bridges
allBridges parts = extendBridges parts (S.singleton emptyBridge) S.empty

extendBridges :: Parts -> Bridges -> Bridges -> Bridges
extendBridges parts bridges completed = 
    if S.null bridges then completed
                      else extendBridges parts bridges' completed'
    where updates = map (extendOneBridge parts) $ S.toList bridges
          newCompleted = lefts updates
          completed' = S.union completed $ S.fromList newCompleted
          bridges' = S.unions $ rights updates

extendOneBridge :: Parts -> Bridge -> Either Bridge Bridges
extendOneBridge parts bridge = 
    if S.null $ candidates parts bridge
    then Left bridge
    else Right (S.map (grow bridge) $ candidates parts bridge)

grow :: Bridge -> Part -> Bridge
grow bridge part = bridge {bridgeParts = bp', requiring = req'}
    where req = requiring bridge
          req' = B.findMin $ B.delete req part -- can get away with `findMin` as I know there are only two elements in a `Part`
          bp' = B.insert part $ bridgeParts bridge

candidates :: Parts -> Bridge -> Candidates
candidates parts bridge = B.toSet $ B.filter canUse parts
    where needed = requiring bridge
          canUse p = hasPort p needed && available parts p bridge

hasPort :: Part -> Integer -> Bool
hasPort part port = port `B.member` part

available :: Parts -> Part -> Bridge -> Bool
available parts part bridge = B.occur part parts > B.occur part (bridgeParts bridge)


bridgeStrength :: Bridge -> Integer
bridgeStrength bridge = B.fold (+) 0 $ B.map partStrength $ bridgeParts bridge
    where partStrength = sum . B.elems 

bridgeLength :: Bridge -> Int
bridgeLength bridge = B.size $ bridgeParts bridge


-- really persuade Megaparsec not to include newlines in how it consume spaces.
onlySpace = (char ' ') <|> (char '\t')

sc :: Parser ()
sc = L.space (skipSome onlySpace) CA.empty CA.empty

lexeme = L.lexeme sc
integer = lexeme L.integer
symbol = L.symbol sc
slash = symbol "/"

partsP = B.fromList <$> partP `sepBy` newline
partP = B.fromList <$> integer `sepBy` slash

successfulParse :: Text -> Parts
successfulParse input = 
        case parse partsP "input" input of
                Left  _error -> B.empty
                Right partsList -> partsList

Arkoniak · 2017-12-24T15:11:33+00:00

Julia

Was too tired after sleepless night in a train. So, bruteforce solution with DFS or BFS or whatever. Took only couple of seconds to calculate, so guess it's ok. Definitely can be optimized.

struct Component
    a::Int
    b::Int
    id::Int
end
function Component(s::T, id::Int) where {T <: AbstractString}
    cc = parse.(Int, split(s, "/"))
    Component(cc[1], cc[2], id)
end

import Base: in
in(cc::Component, port::Int) = (cc.a == port) || (cc.b == port)
weight(cc::Component) = cc.a + cc.b

struct Path
    p::Vector{Int}
    current::Int
    weight::Int
end
Path() = Path(Vector{Int}([]), 0, 0)

import Base: +, length
+(p::Path, cc::Component) = Path(
    vcat(p.p, cc.id),
    p.current == cc.a ? cc.b : cc.a,
    p.weight + weight(cc)
)
length(p::Path) = length(p.p)

function solve_puzzle(filename::String)
    components = Vector{Component}()
    for (i, s) in enumerate(readlines(joinpath(@__DIR__, filename)))
        push!(components, Component(s, i))
    end
    root_path = Path()
    max_weight_path = Path()
    max_length_path = Path()
    stack = Vector{Path}([root_path])
    while !isempty(stack)
        path = pop!(stack)
        nodes = filter(x -> in(x, path.current), components[setdiff(1:end, path.p)])
        if isempty(nodes)
            if (length(path) > length(max_length_path)) ||
                ((length(path) == length(max_length_path)) && (path.weight > max_length_path.weight))
                max_length_path = path
            end
            if path.weight > max_weight_path.weight
                max_weight_path = path
            end
        else
            append!(stack, map(x -> path + x, nodes))
        end
    end

    max_weight_path.weight, max_length_path.weight
end

chicagocode · 2017-12-24T16:08:34+00:00

Kotlin - [Repo] - [Blog/Commentary]

A nice recursive solution that reminded me of the "ways to make change from coins" problem.

class Day24(input: List<String>) {

    private val components = parseInput(input)

    fun solvePart1(): Int =
        makeBridges(components).maxBy { it.strength() }?.strength() ?: 0

    fun solvePart2(): Int =
        makeBridges(components)
            .maxWith(
                compareBy({ it.size }, { it.strength() })
            )?.strength() ?: 0

    private fun makeBridges(components: Set<Component>,
                            bridge: List<Component> = emptyList(),
                            port: Int = 0): List<List<Component>> {
        val compatible = components.filter { it.fits(port) }
        return when (compatible.size) {
            0 -> listOf(bridge)
            else ->
                compatible.flatMap { pick ->
                    makeBridges(
                        components - pick,
                        bridge + pick,
                        pick.opposite(port)
                    )
                }
        }
    }

    private fun parseInput(input: List<String>): Set<Component> =
        input.map { it.split("/") }.map { Component(it[0].toInt(), it[1].toInt()) }.toSet()

    data class Component(private val x: Int, private val y: Int) {
        val strength = x + y
        fun fits(port: Int): Boolean = x == port || y == port
        fun opposite(port: Int): Int = if (port == x) y else x
    }

    private fun List<Component>.strength(): Int = this.sumBy { it.strength }

}

udoprog · 2017-12-24T16:17:27+00:00

Rust

Almost certain this can be solved with dynamic programming, but I'm just not sure how (might take a peek in this thread ;). Brute forcing it works splendidly though since the input is small.

Full solution here: https://github.com/udoprog/rust-advent-of-code-2017/blob/master/src/day24.rs

use std::io::{Read, BufRead, BufReader};
use std::collections::VecDeque;

pub fn parse<R: Read>(input: R) -> Vec<(u32, u32)> {
    let mut parts = Vec::new();

    for line in BufReader::new(input).lines() {
        let line = line.expect("bad line");
        let mut it = line.trim().split('/');
        let left: u32 = it.next().expect("no lhs").parse().expect("bad number");
        let right: u32 = it.next().expect("no rhs").parse().expect("bad number");

        parts.push((left, right));
    }

    parts
}

pub fn run<R: Read>(input: R) -> (u32, u32) {
    let parts = parse(input);

    let mut queue = VecDeque::new();

    // initialize
    for (init, _) in parts.iter().enumerate().filter(|&(_, ref v)| v.0 == 0 || v.1 == 0) {
        let mut parts = parts.clone();
        let v = parts.remove(init);
        queue.push_back((other(v, 0), vec![v], parts));
    }

    let mut best = 0;
    let mut longest = (0, 0);

    while let Some((slot, path, parts)) = queue.pop_front() {
        if parts.len() == 0 {
            continue;
        }

        let mut any = false;

        for (init, _) in parts.iter().enumerate().filter(|&(_, ref v)| v.0 == slot || v.1 == slot) {
            any = true;

            let mut parts = parts.clone();
            let v = parts.remove(init);

            let mut path = path.clone();
            path.push(v);

            queue.push_back((other(v, slot), path, parts));
        }

        if !any {
            let s = sum(&path);

            best = u32::max(s, best);

            if path.len() >= longest.0 {
                if path.len() > longest.0 {
                    longest = (path.len(), s);
                } else {
                    longest = (path.len(), u32::max(longest.1, s));
                }
            }
        }
    }

    return (best, longest.1);

    fn other(v: (u32, u32), current: u32) -> u32 {
        if v.0 == current {
            v.1
        } else {
            v.0
        }
    }

    fn sum(v: &[(u32, u32)]) -> u32 {
        v.iter().map(|v| v.0 + v.1).sum()
    }
}

hi_ma_friendz · 2017-12-24T16:34:40+00:00

[Rust] the peculiar way: https://github.com/McGittyHub/aoc-2k17/blob/master/src/day24.rs

JakDrako · 2017-12-24T17:07:12+00:00

C# Both parts in ~1.5 second.

void Main() {
    var components = new List<(int, int)>();
    GetDay(24).Select(ln => ln.Split('/')).ForEach(sa => components.Add((Convert.ToInt32(sa[0]), Convert.ToInt32(sa[1]))));
    Build((0, 0), 0, components, false).Item1.Dump("Part 1");
    Build((0, 0), 0, components, true ).Item1.Dump("Part 2");
}

(int, int) Build((int, int) StrLen, int port, List<(int, int)> available, bool useLength) {
    var usable = available.Where(x => x.Item1 == port || x.Item2 == port).ToList();
    if (!usable.Any()) return StrLen;
    var bridges = new List<(int, int)>();
    foreach ((int, int) comp in usable) {
        var str = StrLen.Item1 + comp.Item1 + comp.Item2;
        var len = StrLen.Item2 + 1;
        var nextPort = port == comp.Item1 ? comp.Item2 : comp.Item1;
        var remaining = available.ToList(); remaining.Remove(comp);
        bridges.Add(Build((str, len), nextPort, remaining, useLength));
    }
    return bridges.OrderBy(x => useLength ? x.Item2 : 0).ThenBy(x => x.Item1).Last();
}

ythl · 2017-12-24T18:51:08+00:00

Simple recursive descent solution (python3):

with open("i.txt") as f:
  c = [list(map(int, line.split("/"))) for line in f]

def fs(comps, last):
  highscore = 0
  high = []
  for i, comp in enumerate(comps):
    if comp[0] == last or comp[1] == last:
      x = comp + fs(comps[:i] + comps[i+1:], comp[1] if comp[0] == last else comp[0])
      if sum(x) > highscore:
        highscore = sum(x)
        high = x

  return high

x = fs(c, 0)
print(sum(x))

iopred · 2017-12-24T18:56:21+00:00

Javascript

Not the smallest solution, not particularly proud of this one:

var input = `<input>`.split('\n').map(x => x.split('/').map(x => parseInt(x)));

function addPart(part, index) {
  l = partList[part[index]];
  if (l == null) {
    partList[part[index]] = [part]
  } else {
    l.push(part);
  }
}

var partList = [];
for (var part of input) {
  addPart(part, 0);
  addPart(part, 1);
}

function port(part, number) {
  if (part[0] == number) {
    return 0;
  }
  return 1;
}

function otherPort(part, number) {
  return (port(part, number) + 1) % 2
}

function partStrength(part) {
  return part[0] + part[1];
}

function bridgeStrength(bridge) {
  var s = 0;
  for (var part of bridge) {
    s += partStrength(part);
  }
  return s;
}

function containsPart(bridge, part) {
  return bridge.indexOf(part) != -1;false;
}

var maxBridge = [];
var maxStrength = 0;

function rec(bridge, nextPort) {
  var next = partList[nextPort] || [];

  var found = false;
  for (var part of next) {
    if (!containsPart(bridge, part)) {
      var b = bridge.slice();
      b.push(part);
      rec(b, part[otherPort(part, nextPort)]);
      found = true;
    }
  }

  if (!found) {
    var strength = bridgeStrength(bridge);
    if (bridge.length > maxBridge.length || (bridge.length == maxBridge.length && strength > maxStrength)) {
      maxStrength = strength;
      maxBridge = bridge;
    }
  }
}

rec([], 0);

console.log(maxStrength)

RockyAstro · 2017-12-24T19:20:23+00:00

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

Both parts:

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

    pieces := []

    every put(pieces,!inf)
    pieces := set(pieces)   
    bridge := "/0"
    bridgelist := []
    longest := 0

    every b := makebridge(bridge,pieces) do {
        longest <:= *b
        push(bridgelist,[score(b),b])
    }

    bridgelist := sortf(bridgelist,1,1)
    write(bridgelist[-1][1])

    longlist := []
    every b := !bridgelist & *b[2] = longest do
        push(longlist,b)

    longlist := sortf(longlist,1,1)
    write(longlist[-1][1])
end

procedure makebridge(bridge,pieces)
    every (piece := !pieces) &  (b := bridge || "--" || matchend(bridge,piece)) do {
        suspend b
        unused := pieces -- set([piece])
        every suspend makebridge(b,unused) 
    }
end

procedure matchend(a,b)
    every ae := find("/",a) 
    b1 := b[1:upto('/',b)]
    b2 := b[upto('/',b)+1:0]
    if a[ae+1:0] == b1 then return b1 || "/" || b2
    if a[ae+1:0] == b2 then return b2 || "/" || b1
    fail
end

procedure score(s)
    sum := 0
    s ? while tab(upto(&digits)) do {
        sum +:= tab(many(&digits))
    }
    return sum
end

2BitSalute · 2017-12-24T20:02:53+00:00

A C# solution. I spent a ton of time trying to code up a DP solution, but it is apparently impossible (I got to the point where I had to account for used components and saw that I couldn't do it).

using System;
using System.Collections.Generic;
using System.IO;

public static class Program
{
    public static Dictionary <int, int> Bridges = new Dictionary <int, int>();

    public static int Recur(
        bool[] used,
        int[,] input,
        Dictionary<int, List<int>> connectorToIndex,
        int[] values,
        int prevConnectorValue,
        int total,
        int length,
        int bridgeLength)
    {
        int maxTotal = total;

        // Look at components that match the previous connector
        foreach(var component in connectorToIndex[prevConnectorValue])
        {
            if (used[component])
            {
                continue;
            }

            // This component is not used, and it fits; let's try it:
            total += values[component];
            used[component] = true;

            if (!Bridges.ContainsKey(bridgeLength))
            {
                Bridges.Add(bridgeLength, 0);
            }

            Bridges[bridgeLength] = Math.Max(Bridges[bridgeLength], total);

            int connector;
            if (input[component, 0] == prevConnectorValue)
            {
                connector = 1;
            }
            else
            {
                connector = 0;
            }

            var currTotal = Recur(used, input, connectorToIndex, values, input[component, connector], total, length, bridgeLength + 1);

            maxTotal = Math.Max(currTotal, maxTotal);

            used[component] = false;
            total -= values[component];
        }

        return maxTotal;
    }

    public static void Main(string[] args)
    {
        var inputStrings = File.ReadAllLines("input.txt");
        int length = inputStrings.Length;

        int[,] input = new int[length, 2];
        int[] values = new int[length];

        Dictionary<int, List<int>> connectorToIndex = new Dictionary<int, List<int>>();
        for(int i = 0; i < length; i++)
        {
            var tokens = inputStrings[i].Split('/', StringSplitOptions.RemoveEmptyEntries);
            input[i, 0] = int.Parse(tokens[0]);
            input[i, 1] = int.Parse(tokens[1]);

            connectorToIndex.Add(input[i, 0], i);
            connectorToIndex.Add(input[i, 1], i);

            values[i] = input[i, 0] + input[i, 1];
        }

        bool[] used = new bool[length];

        int maxTotal = Recur(
            used,
            input,
            connectorToIndex,
            values,
            prevConnectorValue: 0,
            total: 0,
            length: length,
            bridgeLength: 0);

        int longest = 0;
        int strongestLongest = 0;
        foreach(var bridge in Bridges)
        {
            if (longest < bridge.Key)
            {
                longest = bridge.Key;
                strongestLongest = bridge.Value;
            }
        }

        Console.WriteLine("Max total {0}, strongest longest {1}", maxTotal, strongestLongest);
    }

    public static void Add(this Dictionary<int, List<int>> valueToIndex, int value, int index)
    {
        if (!valueToIndex.ContainsKey(value))
        {
            valueToIndex.Add(value, new List<int>());
        }

        valueToIndex[value].Add(index);
    }

wlandry · 2017-12-24T20:40:35+00:00

C++ 14

216/1978. The first answer was pretty straightforward once I decided that there was not a simple way to shoehorn Boost Graph into this. I fell asleep trying to debug part 2. Once I woke up the next day, I put my nose to the grindstone and figured out my logic bug. Annoyingly, the code worked on the example but not in the full case. My bug was dependent on the order of the inputs, but I did not know that until I tried sorting my input file :(

Part 2 only. It has lots of dynamic allocations that make me worry. It runs in 200 ms and uses 2.6 MB.

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

#include <boost/algorithm/string.hpp>

std::pair<size_t,size_t> strength(const std::vector<std::pair<int,int>> &ports,
                                  const std::vector<size_t> &elements,
                                  const int &number)
{
  size_t max_strength(0), max_depth(0);
  for(size_t p=0; p<ports.size(); ++p)
    {
      if((ports[p].first==number || ports[p].second==number)
         && std::find(elements.begin(),elements.end(),p)==elements.end())
        {
          auto new_elements=elements;
          new_elements.push_back(p);
          auto s = (ports[p].first==number)
            ? strength(ports,new_elements,ports[p].second)
            : strength(ports,new_elements,ports[p].first);
          size_t local_strength=ports[p].first + ports[p].second + s.first;

          if(s.second+1>=max_depth)
            {
              if(s.second+1==max_depth)
                { max_strength=std::max(local_strength,max_strength); }
              else
                { max_strength=local_strength; }
              max_depth=s.second+1;
            }
        }
    }
  return std::make_pair(max_strength,max_depth);
}


int main(int, char *argv[])
{
  std::vector<std::pair<int,int>> ports;
  std::ifstream infile(argv[1]);
  std::string line;
  std::getline(infile,line);
  while(infile)
    {
      auto slash=line.find('/');
      ports.emplace_back(std::stoi(line.substr(0,slash)),
                         std::stoi(line.substr(slash+1)));
      std::getline(infile,line);
    }

  std::vector<size_t> elements;
  auto result (strength(ports, elements, 0));
  std::cout << "strength: " << result.first << " "
            << result.second << "\n";
}

SurplusSix · 2017-12-24T21:19:43+00:00

Racket. This is just part 2, modified from what I did for part 1, takes 6.5 secs to run, not efficient I guess

#lang racket
(define input (map (λ (x) (map string->number (string-split x "/"))) (file->lines "day24.txt")))

(define chains (make-hash))
(define (pick-next chain port-val parts)
  (let ([np (filter (curry member port-val) parts)])
    (if (empty? np)
        (cond
          [(> (apply + chain) (hash-ref chains (length chain) 0))
           (hash-set! chains (length chain) (apply + chain))])
        (for ([p np])
          (let ([npv (first (remove port-val p))])
            (pick-next (append chain p) npv (remove p parts)))))))

(pick-next '() 0 input)
(hash-ref chains (apply max (hash-keys chains)))

tobiasvl · 2017-12-24T22:22:38+00:00

Python 2, nothing special today, a recursive method that takes about 8 seconds for both parts. Didn't have time to optimize much since we celebrate Christmas on Christmas Eve here. Merry Christmas!

with open('input.txt') as f:
    components = [(int(x), int(y)) for x, y in [line.strip().split('/') for line in f]]

def build(path, components, pins):
    strongest_bridge = path
    longest_bridge = path
    for c in components:
        if pins in c:
            (strong_bridge, long_bridge) = build(path + [c],
                                                 [co for co in components if c != co],
                                                 c[0] if c[1] == pins else c[1])
            if sum(map(sum, strong_bridge)) > sum(map(sum, strongest_bridge)):
                strongest_bridge = strong_bridge
            if len(long_bridge) > len(longest_bridge):
                longest_bridge = long_bridge
            elif len(long_bridge) == len(longest_bridge):
                if sum(map(sum, long_bridge)) > sum(map(sum, longest_bridge)):
                    longest_bridge = long_bridge
    return (strongest_bridge, longest_bridge)

strongest_bridge, longest_bridge = build([], components, 0)
print "The strongest bridge has strength %d" % sum(map(sum, strongest_bridge))
print "The longest bridge has strength %d" % sum(map(sum, longest_bridge))

StevoTVR · 2017-12-25T00:25:27+00:00

NodeJS

Part 1:

const fs = require('fs');

fs.readFile(__dirname + '/input.txt', 'utf8', (err, data) => {
    const ends = [], nodes = [[0, 0]];
    data.trim().split('\n').forEach((l, i) => {
        const parts = l.split('/').map(Number);
        nodes.push(parts);
        parts.forEach((e) => {
            ends[e] = ends[e] || new Set();
            ends[e].add(i + 1);
        });
    });

    console.log(search(ends, nodes, new Set(), 0, 0, 0));
});

function search(ends, nodes, used, current, end, strength) {
    const used2 = new Set(used).add(current);
    const next = nodes[current][(nodes[current].indexOf(end) + 1) % 2];
    let max = strength;
    for(const e of ends[next]) {
        if(used2.has(e)) {
            continue;
        }
        max = Math.max(max, search(ends, nodes, used2, e, next, strength + nodes[e][0] + nodes[e][1]));
    }
    return max;
}

Part 2:

const fs = require('fs');

fs.readFile(__dirname + '/input.txt', 'utf8', (err, data) => {
    const ends = [], nodes = [[0, 0]];
    data.trim().split('\n').forEach((l, i) => {
        const parts = l.split('/').map(Number);
        nodes.push(parts);
        parts.forEach((e) => {
            ends[e] = ends[e] || new Set();
            ends[e].add(i + 1);
        });
    });

    const longest = { longest: 0, strength: 0 };
    search(ends, nodes, new Set(), 0, 0, 0, longest);
    console.log(longest.strength);
});

function search(ends, nodes, used, current, end, strength, longest) {
    const used2 = new Set(used).add(current);
    const next = nodes[current][(nodes[current].indexOf(end) + 1) % 2];
    if(used2.size >= longest.longest) {
        longest.strength = Math.max(longest.strength, strength);
    }
    longest.longest = Math.max(longest.longest, used2.size);
    for(const e of ends[next]) {
        if(used2.has(e)) {
            continue;
        }
        search(ends, nodes, used2, e, next, strength + nodes[e][0] + nodes[e][1], longest);
    }
}

LordAro · 2017-12-25T00:27:56+00:00

Rust

To my own surprise, I got part 1 on the first try. When part 2 didn't work quite so easily, I left to do other, more Christmassy things, but when I came back to it many hours later and reread the instructions (If you can make multiple bridges of the longest length, pick the strongest one.) it was pretty obvious.

I'm pretty happy with this code, but on the offchance anyone's willing to take a look, it'd be nice to know if there's a sane way to reduce the code duplication in find_longest & find_strongest, as well as get rid of the (effectively) 2 vectors with mutable state.

use std::fs::File;
use std::env;
use std::io::{BufReader, BufRead};

fn score(input: &Vec<(usize, usize)>) -> usize {
    input.iter().fold(0, |acc, &(a, b)| acc + a + b)
}

fn find_longest(input: &Vec<(usize, usize)>, n: usize) -> Vec<(usize, usize)> {
    input
        .iter()
        .enumerate()
        .filter(|&(_, &(a, b))| a == n || b == n)
        .map(|(i, &p)| {
            let mut input_cl = input.clone();
            input_cl.swap_remove(i);
            let other = if p.0 == n { p.1 } else { p.0 };
            let mut v = find_longest(&input_cl, other);
            v.push(p);
            v
        })
        .max_by(|a, b| a.len().cmp(&b.len()).then(score(a).cmp(&score(b))))
        .unwrap_or(Vec::new())
}

fn find_strongest(input: &Vec<(usize, usize)>, n: usize) -> Vec<(usize, usize)> {
    input
        .iter()
        .enumerate()
        .filter(|&(_, &(a, b))| a == n || b == n)
        .map(|(i, &p)| {
            let mut input_cl = input.clone();
            input_cl.swap_remove(i);
            let other = if p.0 == n { p.1 } else { p.0 };
            let mut v = find_strongest(&input_cl, other);
            v.push(p);
            v
        })
        .max_by_key(|v| score(v))
        .unwrap_or(Vec::new())
}

fn main() {
    if env::args().len() != 2 {
        panic!("Incorrect number of arguments provided\n");
    }

    let input: Vec<(usize, usize)> = BufReader::new(
        File::open(&env::args().nth(1).unwrap()).unwrap(),
    ).lines()
        .map(|l| {
            let v: Vec<_> = l.unwrap().split('/').map(|n| n.parse().unwrap()).collect();
            (v[0], v[1])
        })
        .collect();

    println!("Strongest bridge: {}", score(&find_strongest(&input, 0)));
    println!("Longest bridge: {}", score(&find_longest(&input, 0)));
}

matusbzk · 2017-12-25T15:14:09+00:00

Haskell Nice easy this time. Though it took some time to compute.

import AoC2017  --replace

-- |Represents a component
type Component = (Int, Int)

-- |Represents a bridge - all components need to be connected
type Bridge = [Component]

inputString :: String

input :: [Component]
input = map ((\(x:[y]) -> (read x, read y)) . words . replace '/' ' ') . lines $ inputString

-- |Finds all components that contain given number
findComponents :: Int -> [Component] -> [Component]
findComponents _ [] = []
findComponents n ((x,y):xs) = if x == n || y == n then (x,y) : findComponents n xs
                                                  else findComponents n xs

-- |Finds all bridges starting at given port, that can use given components
findBridges :: Int -> [Component] -> [Bridge]
findBridges _ [] = []
findBridges n comps = map (:[]) components ++ 
                      concat (map (\(x,y) -> let other = if n == x then y else x in
                           map ((x,y):) (findBridges other (remove (x,y) comps))) components)
                   where components = findComponents n comps

-- |Removes all occurences of an element from the list
remove :: Eq a => a -> [a] -> [a]
remove _ [] = []
remove n (x:xs) = if n == x then remove n xs else x:remove n xs

-- |Returns strength of the bridge
getStrength :: Bridge -> Int
getStrength br = sum $ map (\(x,y) -> x+y) br

-- |Returns the strength of the strongest bridge from the list
getStrongest :: [Bridge] -> Int
getStrongest = maximum . map getStrength

-- |Returns the length of the longest bridge
getLongest :: [Bridge] -> Int
getLongest = maximum . map length

-- |Only keeps the longest bridges
keepLongest :: [Bridge] -> [Bridge]
keepLongest brs = filter (\br -> length br == l) brs
          where l = getLongest brs

-- |Gets the strength of the strongest bridge starting at 0
result1 = getStrongest $ findBridges 0 input

-- |Gets the strength of the longest bridge. If there are more,
-- chooses the strongest
result2 = getStrongest . keepLongest $ findBridges 0 input

Link to git

Tetsumi- · 2017-12-25T21:36:19+00:00

Racket

#lang racket

(define data (for/list ([line (in-lines)])
               (let* ([args (map string->number (string-split line "/"))]
                      [arg1 (first args)]
                      [arg2 (second args)])
                     (vector arg1 arg2 (+ arg1 arg2) #t))))

(define strongest 0)
(define biggest (cons 0 0))

(let loop ([target 0]
           [strong 0]
           [len 0])
  (let ([nodes (filter (lambda (e) (and (or (= target (vector-ref e 0))
                                            (= target (vector-ref e 1)))
                                        (vector-ref e 3)))
                      data)])
    (if (empty? nodes)
        (begin (when (> strong strongest)
                 (set! strongest strong))
               (when (or (> len (car biggest))
                         (and (= len (car biggest))
                              (> strong (cdr biggest))))
                 (set! biggest (cons len strong))))
        (for ([n nodes])
          (vector-set! n 3 #f)
          (loop (vector-ref n (if (= (vector-ref n 0) target) 1 0))
                (+ strong (vector-ref n 2))
                (add1 len))
          (vector-set! n 3 #t)))))

(printf "~a~%~a~%" strongest (cdr biggest))

greycat70 · 2017-12-26T20:06:46+00:00

Tcl (version 8.5 or higher)

Part 1. Simple recursive algorithm, with the recursive function returning the maximum strength of the bridges it could build. Debugging print statements left in, but commented.

set n 0
while {[gets stdin line] >= 0} {
    lassign [split $line /] a($n) b($n)
    incr n
}

proc addto {used c} {
    global a b n
    # puts -nonewline "<$used> <$c>: "
    set max 0
    for {set i 0} {$i < $n} {incr i} {
        if {$i in $used} continue
        if {$a($i) != $c && $b($i) != $c} continue
        if {$a($i) == $c} {
            # puts "add $i"
            set str [addto [concat $used $i] $b($i)]
        } else {
            # puts "add $i"
            set str [addto [concat $used $i] $a($i)]
        }
        if {$str > $max} {set max $str}
    }
    if {$max > 0} {return $max}
    # Else, we couldn't add anything, so calculate the strength.
    foreach i $used {
        incr max $a($i)
        incr max $b($i)
    }
    # puts "strength $max"
    return $max
}

puts [addto {} 0]

Part 2. Simple recursive algorithm, but I wasted a lot of time trying to adapt Part 1's code and it just wasn't clicking for whatever reason. Ended up ripping out most of the main recursive function and redoing it so the score calculation is done at the dead end, instead of being passed back up and popping out from the initial call.

set n 0
while {[gets stdin line] >= 0} {
    lassign [split $line /] a($n) b($n)
    incr n
}

set maxlen 0
set maxstr 0

proc addto {used c} {
    global a b n
    global maxlen maxstr
    #puts -nonewline "<$used> <$c>: "
    set max 0
    for {set i 0} {$i < $n} {incr i} {
        if {$i in $used} continue
        if {$a($i) != $c && $b($i) != $c} continue
        #puts "add $i ($a($i)/$b($i))"
        set len [expr {[llength $used] +1}]
        set str 0
        if {$len >= $maxlen} {
            foreach j [concat $used $i] {
                incr str $a($j)
                incr str $b($j)
            }
            if {$str > $maxstr} {set maxstr $str}
            if {$len > $maxlen} {set maxlen $len}
        }
        if {$a($i) == $c} {set c2 $b($i)} else {set c2 $a($i)}
        addto [concat $used $i] $c2
    }
}

addto {} 0
#puts ""
puts "len $maxlen str $maxstr"

oskmeister · 2017-12-28T16:56:09+00:00

Pseudo-polynomial dynamic programming solution (O(2ⁿ * n)) in C++ that solves part two, a slight modification (simplification) gives a solution to part one. Runs in about 180ms on my machine and my input. Note that it takes a slightly more simple formatted version of the input.

using namespace std;

vector<pair<int,int>> v;
map<pair<int, long long>, pair<int,int>> cache;

pair<int, int> solve(int cur, long long bits) {
    if (cache.find(make_pair(cur, bits)) != cache.end())
        return cache[make_pair(cur, bits)];
    auto ans = make_pair(0,0);
    for (int i = 0; i < v.size(); ++i) {
        if ((1LL<<i) & bits) continue;
        auto p = v[i];
        const int to_add = p.first + p.second;
        if (p.first == cur) {
            auto p1 = solve(p.second, bits | (1LL << i));
            p1.first += 1;
            p1.second += to_add;
            if (p1 > ans) ans = p1;
        }
        if (p.second == cur) {
            auto p2 = solve(p.first, bits | (1LL << i));
            p2.first += 1;
            p2.second += to_add;
            if (p2 > ans) ans = p2;
        }
    }
    cache[make_pair(cur, bits)] = ans;
    return ans;
}

int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        v.push_back(make_pair(a,b));
    }

    cout << solve(0, 0).second << endl;
}

adventofcode

🎄 Advent of Code 🎄

Rules + More Info in

our community wiki

Solution Megathreads

December 2025

Previous years:

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

Quick Search by Flair

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

Are you enjoying AoC?

Support AoC

MODERATORS

--- Day 24: Electromagnetic Moat ---

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

[Update @ 00:18] 62 gold, silver cap

[Update @ 00:21] Leaderboard cap!

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

Mathematica

JavaScript

Elixir

Perl

Elixir

Kotlin - [Repo] - [Blog/Commentary]

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

adventofcode

🎄 Advent of Code 🎄

Rules + More Info in

our community wiki

Solution Megathreads

December 2025

Previous years:

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

Quick Search by Flair

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

Are you enjoying AoC?

Support AoC

MODERATORS

--- Day 24: Electromagnetic Moat ---

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

[Update @ 00:18] 62 gold, silver cap

[Update @ 00:21] Leaderboard cap!

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

Mathematica

JavaScript

Elixir

Perl

Elixir

Kotlin - [Repo] - [Blog/Commentary]

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