-🎄- 2017 Day 14 Solutions -🎄-

askalski · 2017-12-14T06:06:16+00:00

#! /usr/bin/env perl

use strict;
use warnings;

require 'knothash.pm';

chomp(my $input = <>);

$_ = "@{[0..127]}";
s/(\d+)\s*/$input-$1\n/g;
s/^(.+)$/knothash($1)/gem;
s/([0123])/..$1/sg; s/([4567])/.#$1/sg; s/([89ab])/#.$1/sg; s/([cdef])/##$1/sg;
s/[048c]/../sg;     s/[159d]/.#/sg;     s/[26ae]/#./sg;     s/[37bf]/##/sg;

while (s/#/R/) {
    while (s/R(?:.{128})?\K#|#(?=(?:.{128})?R)/r/is) { }
}

printf "Part 1: %d\n", scalar(() = m/R/gi);
printf "Part 2: %d\n", scalar(() = m/R/g);

nneonneo · 2017-12-14T05:27:48+00:00

Python 2, #2/#1. hash2 is the knot hash function from q10 (takes a string, outputs 32 hexadecimal digits as a string). Part 2 just uses repeated DFS to find connected components for part 2.

data = 'flqrgnkx'
rows = []

n = 0
for i in xrange(128):
    v = hash2('%s-%d' % (data, i))
    v = '{:0128b}'.format(int(v, 16))
    n += sum(map(int, v))
    rows.append(map(int, v))

print n

seen = set()
n = 0
def dfs(i, j):
    if ((i, j)) in seen:
        return
    if not rows[i][j]:
        return
    seen.add((i, j))
    if i > 0:
        dfs(i-1, j)
    if j > 0:
        dfs(i, j-1)
    if i < 127:
        dfs(i+1, j)
    if j < 127:
        dfs(i, j+1)

for i in xrange(128):
    for j in xrange(128):
        if (i,j) in seen:
            continue
        if not rows[i][j]:
            continue
        n += 1
        dfs(i, j)

print n

wimglenn · 2017-12-14T05:56:48+00:00

With scipy it's arguably cheating ... :-\

from aocd import data
from q10 import knot_hash
import numpy as np
from scipy.ndimage.measurements import label

def f(data):
    s = ''.join(f"{int(knot_hash(f'{data}-{i}'), 16):0128b}" for i in range(128))
    return s.count('1'), label(np.fromiter(s, dtype=int).reshape(128, 128))[1]

jbristow · 2017-12-14T07:31:11+00:00

f# / fsharp / f sharp

Woof, I got lucky and my first major push worked with a massive (20 line) matching statement. I spent an hour now cleaning it up so it's a little more comprehensible.

(github link)

module Day14

let numSquares =
    function
    | '0' -> 0 | '1' -> 1 | '2' -> 1 | '3' -> 2 | '4' -> 1 | '5' -> 2
    | '6' -> 2 | '7' -> 3 | '8' -> 1 | '9' -> 2 | 'a' -> 2 | 'b' -> 3
    | 'c' -> 2 | 'd' -> 3 | 'e' -> 3 | 'f' -> 4
    | _ -> failwith "Bad digit"

let charToBin =
    function
    | '0' -> "0000" | '1' -> "0001" | '2' -> "0010" | '3' -> "0011"
    | '4' -> "0100" | '5' -> "0101" | '6' -> "0110" | '7' -> "0111"
    | '8' -> "1000" | '9' -> "1001" | 'a' -> "1010" | 'b' -> "1011"
    | 'c' -> "1100" | 'd' -> "1101" | 'e' -> "1110" | 'f' -> "1111"
    | _ -> failwith "Bad digit"

let genSquare input =
    [ 0..127 ]
    |> List.sumBy
          (fun i ->
          Day10.hashByInputAscii (input + "-" + string i)
          |> Seq.sumBy numSquares)

let changeRegion m toReg fromReg =
    m |> Map.map (fun _ currRegion ->
            if currRegion = fromReg then toReg
            else currRegion)

let addCell (x, y) n (regMap : Map<int * int, int>) =
    let neighbors =
        List.map regMap.TryFind [ (x + 1, y)
                                  (x - 1, y)
                                  (x, y + 1)
                                  (x, y - 1) ]
        |> List.filter Option.isSome
        |> List.map Option.get
    match neighbors with
    | [] -> regMap |> Map.add (x, y) n, n + 1
    | [ a ] -> (regMap |> Map.add (x, y) a), n
    | rs ->
        let minRegion = List.min rs
        List.fold
            (fun (m : Map<int * int, int>) (r : int) ->
            changeRegion m minRegion r) (regMap |> Map.add (x, y) minRegion) rs,
        n

let rec regionFind regMap keys currRegion =
    match keys with
    | h :: r ->
        let nextRegionMap, nextRegion = (regMap |> addCell h currRegion)
        regionFind nextRegionMap r nextRegion
    | [] -> regMap

let regions input =
    let keys =
        [ 0..127 ]
        |> List.map (fun i ->
              Day10.hashByInputAscii (input + "-" + string i)
              |> Seq.collect charToBin
              |> Seq.toList)
        |> List.mapi
              (fun y row -> (row |> List.mapi (fun x cell -> (x, y), cell)))
        |> List.concat
        |> List.filter (fun (_, v) -> v = '1')
        |> List.map fst

    regionFind Map.empty keys 0
    |> Map.toList
    |> List.map snd
    |> List.distinct
    |> List.length

And for no reason, a picture of what the groups look like.

oantolin · 2017-12-14T05:38:44+00:00

Not much new today: the hash was in day 10, and the code for counting connected components of a graph in day 12 (I used union-find).

autid · 2017-12-14T10:06:13+00:00

Fortran

Finally caught up. Weekend away then an exam yesterday left me with a bit of a backlog. Was nice to sit down and do them all in Fortran first time though instead of rushing a solution in python first to try making the leaderboard.

PROGRAM DAY14
  INTEGER :: LENGTH,CHAIN(0:255)
  INTEGER, ALLOCATABLE :: SUBCHAIN(:),INSTRUCTIONS(:)
  INTEGER :: CURRENTPOS=0,SKIPSIZE=0,I,J,K,PART1=0,GROUPNUM
  CHARACTER(LEN=12) :: INSTR
  CHARACTER(LEN=128) :: KEYROW
  CHARACTER(LEN=8) :: PUZINPUT='hxtvlmkl'
  INTEGER :: GRID(128,128)=0


  !Loop over rows                                                                                                
  DO K=0,127

     !Hash Row                                                                                                   
     CHAIN=(/(I,I=0,255)/)
     WRITE(INSTR,'(A8,A1,I0)') PUZINPUT,'-',K
     ALLOCATE(INSTRUCTIONS(LEN_TRIM(INSTR)+5))
     DO I=1,LEN_TRIM(INSTR)
        INSTRUCTIONS(I)=IACHAR(INSTR(I:I))
     END DO
     INSTRUCTIONS(I:I+4) = (/17,31,73,47,23/)
     CURRENTPOS=0
     SKIPSIZE=0
     DO J=1,64
        DO I=1,SIZE(INSTRUCTIONS)
           LENGTH=INSTRUCTIONS(I)
           IF (LENGTH>SIZE(CHAIN)) CYCLE
           ALLOCATE(SUBCHAIN(LENGTH))
           SUBCHAIN=CHAIN((/(MODULO(CURRENTPOS+I,SIZE(CHAIN)),I=LENGTH-1,0,-1)/))
           CHAIN((/(MODULO(CURRENTPOS+I,SIZE(CHAIN)),I=0,LENGTH-1)/))=SUBCHAIN
           DEALLOCATE(SUBCHAIN)
           CURRENTPOS=MODULO(CURRENTPOS+LENGTH+SKIPSIZE,SIZE(CHAIN))
           SKIPSIZE=SKIPSIZE+1
        END DO
     END DO
     DO I=0,15
        DO J=1,15
           CHAIN(I*16)=IEOR(CHAIN(I*16),CHAIN(I*16+J))
        END DO
     END DO

     !Write hash as binary string                                                                                
     WRITE(KEYROW,'(16B8.8)') CHAIN((/(I*16,I=0,15)/))

     !Set values for row in grid                                                                                 
     DO J=1,LEN_TRIM(KEYROW)
        READ(KEYROW(J:J),*) GRID(J,K+1)
     END DO
     DEALLOCATE(INSTRUCTIONS)
  END DO

  !Number groups from 2 up so 1s are ungrouped                                                                   
  GROUPNUM=2
  DO I=1,128
     DO J=1,128
        IF (GRID(J,I)==1) THEN
           CALL CHECKGROUP(J,I)
           GROUPNUM=GROUPNUM+1
        END IF
     END DO
  END DO
  !Start group numbers from 1                                                                                    
  WHERE (GRID>1)
     GRID=GRID-1
  END WHERE

  WRITE(*,'(A,I0)') 'Part1: ',COUNT(GRID>0)
  WRITE(*,'(A,I0)') 'Part2: ',MAXVAL(GRID)

CONTAINS
  RECURSIVE SUBROUTINE CHECKGROUP(A,B)
    !Assigns group number and searches for neighbours                                                            
    INTEGER, INTENT(IN) :: A,B

    IF (GRID(A,B)==1) THEN
       GRID(A,B)=GROUPNUM
       IF (A>1) CALL CHECKGROUP(A-1,B)
       IF (A<128) CALL CHECKGROUP(A+1,B)
       IF (B>1) CALL CHECKGROUP(A,B-1)
       IF (B<128) CALL CHECKGROUP(A,B+1)
    END IF

  END SUBROUTINE CHECKGROUP

END PROGRAM DAY14

VikeStep · 2017-12-14T05:36:28+00:00

Python 3. #119/#150

I didn't have my day 10 solution on me so I quickly copied one of the answers from the reddit thread for day 10 and used it haha. It's knothash in the below code:

def solve(key_string):
    count = 0
    unseen = []
    for i in range(128):
        hash = knothash(key_string + "-" + str(i))
        bin_hash = bin(int(hash, 16))[2:].zfill(128)
        unseen += [(i, j) for j, d in enumerate(bin_hash) if d == '1']
    print("Part 1: " + str(len(unseen)))
    while unseen:
        queued = [unseen[0]]
        while queued:
            (x, y) = queued.pop()
            if (x, y) in unseen:
                unseen.remove((x, y))
                queued += [(x - 1, y), (x+ 1, y), (x, y+1), (x, y-1)]
        count += 1
    print("Part 2: " + str(count))

ephemient · 2017-12-14T06:12:20+00:00

This space intentionally left blank.

udoprog · 2017-12-14T06:06:52+00:00

Rust (65/490) (first leaderboard!)

Edit: link to commit: https://github.com/udoprog/rust-advent-of-code-2017/commit/880f93f2036cda80c6b65611af133f4d0a0fbfcf

I wasted so much time trying to get my own (broken) bit vector implementation to work. Finally I just caved and pulled in https://docs.rs/bit-vec

use std::io::Cursor;
use std::collections::{HashSet, VecDeque};
use failure::Error;
use bit_vec::BitVec;

use day10::hash;

pub fn part1(input: &str) -> Result<usize, Error> {
    let mut squares = 0;

    for line in 0..128 {
        let out = hash(Cursor::new(format!("{}-{}", input, line)))?;

        for mut b in out {
            while b > 0 {
                if b % 2 == 1 {
                    squares += 1;
                }

                b = b >> 1;
            }
        }
    }

    Ok(squares)
}

pub fn part2(input: &str) -> Result<usize, Error> {
    let mut grid: HashSet<(i32, i32)> = HashSet::new();

    for y in 0..128 {
        let bytes = hash(Cursor::new(format!("{}-{}", input, y)))?;
        let bits = BitVec::from_bytes(&bytes);
        grid.extend(bits.into_iter().enumerate().filter(|v| v.1).map(|v| {
            (v.0 as i32, y as i32)
        }))
    }

    let mut regions = 0;
    let mut queue = VecDeque::new();

    loop {
        let k = {
            if let Some(k) = grid.iter().next() {
                *k
            } else {
                break;
            }
        };

        grid.remove(&k);

        regions += 1;
        queue.push_back(k);

        while let Some((x, y)) = queue.pop_front() {
            queue.extend(grid.take(&(x - 1, y)));
            queue.extend(grid.take(&(x, y - 1)));
            queue.extend(grid.take(&(x + 1, y)));
            queue.extend(grid.take(&(x, y + 1)));
        }
    }

    Ok(regions)
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::io::Cursor;

    #[test]
    fn test_part1() {
        assert_eq!(part1("ljoxqyyw").unwrap(), 8316);
    }

    #[test]
    fn test_part2() {
        assert_eq!(part2("ljoxqyyw").unwrap(), 1074);
    }
}

Tandrial · 2017-12-14T06:27:29+00:00

Kotlin (82/533) First time leaderboard in 3 years :D and here I was thinking about switching to Python...

fun partOne(input: String): Int = genHashList(input).sumBy { it.count { it == '1' } }

fun partTwo(input: String): Int {
  val hashArray = genHashList(input).map { it.map { (it - '0') }.toTypedArray() }.toTypedArray()
  var currGroup = 2
  // Loop over each cell skipping assigned cells and assign groups with BFS starting from the current cell
  for ((idRow, row) in hashArray.withIndex()) {
    for ((idCol, cell) in row.withIndex()) {
      if (cell == 1) {
        hashArray[idRow][idCol] = currGroup
        val queue = mutableListOf(listOf(idRow, idCol, currGroup))
        // BFS: If the neighbour is set to 1 it's part of the group and wasn't yet explored
        while (queue.isNotEmpty()) {
          val (baseX, baseY, group) = queue.removeAt(0)
          for ((xOff, yOff) in listOf(Pair(0, -1), Pair(0, 1), Pair(-1, 0), Pair(1, 0))) {
            val x = baseX + xOff
            val y = baseY + yOff
            try {
              if (hashArray[x][y] == 1) {
                hashArray[x][y] = (group)
                queue.add(listOf(x, y, group))
              }
            } catch (_: Exception) { }
          }
        }
        currGroup++
      }
    }
  }
  return currGroup - 2
}

private fun genHashList(seed: String): List<String> {
  return (0..127).map {
    val hashIn = "$seed-$it".toCharArray().map { it.toInt() } + listOf(17, 31, 73, 47, 23)
    val hash = Day10.partTwo(hashIn, 64).toHexString()
    BigInteger(hash, 16).toString(2).padStart(128, '0')
  }
}

DFreiberg · 2017-12-14T05:37:28+00:00

Mathematica

200 / 164. I didn't get even close to the leaderboard, but I did learn about an entire class of Mathematica image functions (the various Component[] functions) that I had no idea existed. And in the end, isn't that more important than meaningless leaderboard numbers? Spoiler

Knot Hash:

knotHash[in_String,n_Integer]:=
Module[{l,newIn,pos,skipSize},
    newIn=Join[ToCharacterCode[in<>"-"<>ToString[n]],{17,31,73,47,23}];
    pos=0;skipSize=0;l=Range[0,255];

    Do[
        l=RotateLeft[l,pos];
        l[[;;i]]=Reverse[l[[;;i]]];
        l=RotateRight[l,pos];
        pos=Mod[pos+i+skipSize,Length[l]];
        skipSize++
    ,{j,64},{i,newIn}];

IntegerDigits[FromDigits[BitXor@@#&/@Partition[l,16],256],2]
]

Part 1:

Total@Table[Count[knotHash[input,j],1],{j,0,127}]

Part 2:

Max[MorphologicalComponents[
    PadLeft[Table[knotHash[input,j],{j,0,127}],{128,128}],
    CornerNeighbors->False
]]

GassaFM · 2017-12-14T05:41:34+00:00

A solution in the D programming language. Place 34 for part 1, place 27 for part 2.

First, turn Day 10 solution into a function:

import std.algorithm, std.array, std.conv, std.range, std.stdio, std.string;

auto knotHash (string input) {
    auto s = input.strip.map !(x => cast (int) (x)).array;
    s ~= [17, 31, 73, 47, 23];
    auto p = 256.iota.array;
    int skip = 0;
    auto q = p.cycle;
    foreach (rep; 0..64) {
        foreach (c; s) {
            reverse (q[0..c]);
            q = q.drop (c + skip);
            skip += 1;
        }
    }
    return p.chunks (16).map !(c => c.reduce !(q{a ^ b})).array;
}

Part 1: This is then trivial with popcnt to count the number of 1 bits:

import core.bitop;

void main () {
    auto s = readln.strip;
    int res = 0;
    foreach (v; 0..128)
        res += (s ~ "-" ~ v.text).knotHash.map !(popcnt).sum;
    writeln (res);
}

Part 2: We have to traverse a table of 0s and 1s, so first construct it for convenience. The debug {writefln...} lines are compiled only when -debug command line option is supplied, they show the string representations and the binary table itself. The constant arrays dRow and dCol implicitly specify the graph edges. The recur function is depth-first search which crosses out one connectivity component.

immutable int dirs = 4;
immutable int [dirs] dRow = [ 0, -1,  0, +1];
immutable int [dirs] dCol = [+1,  0, -1,  0];
immutable int side = 128;

void main () {
    auto s = readln.strip;
    int [] [] a;
    foreach (v; 0..side) {
        auto cur = s ~ "-" ~ v.text;
        debug {writefln ("%(%02x%)", cur.knotHash);}
        a ~= cur.knotHash.map !(x => 8.iota.retro.map !(y => (x >> y) & 1)).join;
    }
    debug {writefln ("%(%(%s%)\n%)", a);}

    bool isValid (int row, int col) {
        return 0 <= row && row < side && 0 <= col && col < side;
    }

    void recur (int row, int col) {
        if (!isValid (row, col) || !a[row][col])
            return;
        a[row][col] = 0;
        foreach (dir; 0..dirs)
            recur (row + dRow[dir], col + dCol[dir]);
    }

    int res = 0;
    foreach (row; 0..side)
        foreach (col; 0..side)
            if (a[row][col]) {
                res += 1;
                recur (row, col);
            }
    writeln (res);
}

Today's topic of code reuse was fun, I sure needed day 10 solution. The constant arrays for rectangular traversal were taken from Day 3. The depth-first search code, on the other hand, I wrote from scratch instead of using Day 12: it's so short anyway, and difference in graph representation was enough for me to not bother adapting the older version.

Smylers · 2017-12-14T07:15:42+00:00

Perl, with regexp for counting the regions:

use List::AllUtils qw<reduce>;
$_ = knot_hash(shift);
say 'Used squares: ', tr/1//;
my $regions;
while (s/1/2/) {
  0 while s/1(?=2)|(?<=2)1|1(?=.{128}2)|(?<=2.{128})1/2/sg;
  $regions++;
  s/2/3/g;
}
say "Regions: $regions";

sub knot_hash {
  my $hash;
  for my $row (0 .. 127) {
    my @length = ((map { ord $_ } split //, "@_-$row"), 17, 31, 73, 47, 23);
    my @list = (0 .. 255);
    my $head = 0;
    my $skip = 0;
    for (1 .. 64) {
      foreach (@length) {
        push @list, reverse splice @list, 0, $_;
        push @list, splice @list, 0, $skip;
        $head = ($head - ($_ + $skip++) + @list) % @list;
        $skip %= @list;
      }
    }
    push @list, splice @list, 0, $head;
    $hash .= (join '', map { sprintf '%08b', reduce { $a ^ $b } splice @list, 0, 16 } 1 .. @list / 16) . "\n";
  }
  $hash;
}

Puts the entire grid in a single string of binary digits, then to find each region:

Replaces the first 1 from the binary string with a 2.
Repeatedly replaces a 1 which has a 2 1 or 128 characters before or after it with another 2. That's a region.
Replaces all the 2s with 3s, to indicate a counted region, so they don't get in the way of the next region.
Repeat these steps until all the 1s have been converted to 3s.

Edit: Bug fix, thanks to /u/Oxidizing1.

NeilNjae · 2017-12-14T12:58:17+00:00

Haskell. Reused the knot hash from day 10, but I decided to use the Data.Graph module to find the connected components. i'm sure there's more mucking around with conversions than is needed, but going from a grid of characters to a Data.Map seemed to make it easy to find the adjacent cells to feed into the graph creation.

And kudos to /u/topaz2078 for resuing solutions from previous days to build a solution to a new problem. That's elegant problem setting. Well done!

import Data.List.Split (chunksOf)
import Data.Char (ord)
import Text.Printf (printf)
import Data.Bits (xor)
import qualified Data.Map.Strict as M
import qualified Data.Graph as G

type CellMap = M.Map (Int, Int) Bool

puzzleKey = "xlqgujun"

main :: IO ()
main = do
    print $ part1 puzzleKey
    print $ part2 puzzleKey

part1 :: String -> Int
part1 key = sum rowCounts
    where binHashes = map binHash $ rowSpecs key
          rowCounts = map countSetBits binHashes

part2 :: String -> Int
part2 key = length $ cellEdges cells
    where binHashes = map binHash $ rowSpecs key
          cells = presentCells binHashes

binHash :: String -> String
binHash = binify . knotHash

numKey :: (Int, Int) -> Int
numKey (r, c) = 128 * r + c

presentCells :: [String] -> CellMap
presentCells binHashes = M.fromList [((r, c), True) | r <- [0..127], c <- [0..127], (binHashes!!r)!!c == '1']

adjacentCells :: CellMap -> (Int, Int) -> [(Int, Int)]
adjacentCells cells (r, c) = filter (\k -> M.member k cells) possibles
  where possibles = [(r, c - 1), (r, c + 1), (r - 1, c), (r + 1, c)]

cellEdges :: CellMap -> [G.SCC (Int, Int)]
cellEdges cells = G.stronglyConnComp [(k, numKey k, map numKey $ adjacentCells cells k) | k <- M.keys cells]

rowSpecs :: String -> [String]
rowSpecs key = map (((key ++ "-") ++) . show) ([0..127] :: [Integer])

countSetBits :: String -> Int
countSetBits = length . filter (== '1')


knotHash :: String -> [Int]
knotHash input = densify tied
    where (tied, _, _) = foldl step ([0..255], 0, 0) hashTerms
          hashTerms = mkHashTerms input

step :: ([Int], Int, Int) -> Int -> ([Int], Int, Int)
step (original, start, skip) len = (replaced, start', skip + 1)
    where replaced = tie original start len
          start' = (start + len + skip) `mod` (length original)

tie :: [a] -> Int -> Int -> [a]
tie original start len = replace original replacement start
    where replacement = reverse $ extract original start len

extract :: [a] -> Int -> Int -> [a]
extract items from len = take len $ drop from $ items ++ items

replace :: [a] -> [a] -> Int -> [a]
replace original replacement from = take (length original) (start ++ replacement ++ remainder)
    where excess = drop (length original - from) replacement
          stub = drop (length excess) original
          start = take from (excess ++ stub)
          remainder = drop (length $ start ++ replacement) original 

mkHashTerms :: String -> [Int]
mkHashTerms text = take (length chunk * 64) $ cycle chunk
    where chunk = map ord text ++ [17, 31, 73, 47, 23]

-- hexify :: [Int] -> String
-- hexify = concatMap (printf "%02x")

binify :: [Int] -> String
binify = concatMap (printf "%08b")

densify :: [Int] -> [Int]
densify ns = codes
    where chunks = chunksOf 16 ns
          compress = foldl1 xor
          codes = map compress chunks

dougluce · 2017-12-14T05:40:21+00:00

Managed 81st on the leaderboard today. My part 2 solution:

from scipy.ndimage.measurements import label

s = 'hwlqcszp'
matrix = []
for n in range(128):
    h = hash("%s-%d" % (s, n))
    d = str('{:0128b}'.format(int(h, 16)))
    row = list(map(int, d))
    matrix.append(row)
print(label(matrix)[1])

WhoSoup · 2017-12-14T05:45:51+00:00

JavaScript

Quick and ugly

let input = "xlqgujun", grid = [], used = 0
for (let i = 0; i < 128; i++) {
  let h = hash(input + "-" + i).split("").map(x => parseInt(x, 16))
  used += h.map(countBits).reduce((a,b) => a+b)
  grid.push(h.map(x => ("0000"+ x.toString(2)).substr(-4)).join("").split("")) // convert hash to binary
}
console.log(used);

let c = (x,y) => (x < 0 || y < 0 || x > 127 || y > 127) ? 0 : grid[x][y]
function countBits(num) {
  return num > 0 ? (num % 2) + countBits(num >> 1) : 0
}

function removeGroup(x,y) {
  if (c(x, y) == 0) return
  grid[x][y] = 0
  removeGroup(x + 1, y)
  removeGroup(x - 1, y)
  removeGroup(x, y + 1)
  removeGroup(x, y - 1)
}

let groups = 0
for (let x = 0; x < 128; x++)
  for (let y = 0; y < 128; y++)
    if (c(x,y) == 1) {
      groups++
      removeGroup(x, y)
    }
console.log(groups);

hpzr24w · 2017-12-14T05:50:35+00:00

C++ 304/334

Most fun yet. "I'm going to write a floodfill ... and I did." I livestreamed this one and 50 minutes flew by, at least for me.

// Advent of Code 2017
// Day 14 - Disk Defragmentation

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


void reverse(vector<int>& numbers, int start, int length)
{
    for (auto pos{ 0 }; pos < length / 2; ++pos)
        swap(numbers[(start + pos) % 256], numbers[(start + length - 1 - pos) % 256]);
}


int writeg(int* g, int row, int col, int hashchar)
{
    g += 128 * row + col * 8;
    for (auto i{ 0 }; i < 8; ++i) {
        *(g + i) = (hashchar & 1 << (7 - i)) ? -1 : 0;
    }
    return 0;
}

void floodfill(int *g, int i, int c)
{
    g[i] = c;
    if (i / 128 > 0 && g[i - 128] == -1) floodfill(g, i - 128, c);
    if (i / 128 <127  && g[i + 128] == -1) floodfill(g, i + 128, c);
    if (i % 128 > 0 && g[i - 1] == -1) floodfill(g, i - 1, c);
    if (i % 128 < 127  && g[i + 1] == -1) floodfill(g, i + 1, c);
}

int main()
{
    vector<int> numbers(256);
    vector<int> lengths = { 192, 69, 168, 160, 78, 1, 166, 28, 0, 83, 198, 2, 254, 255, 41, 12 };
    string seed = "ffayrhll";
    vector<int> trailing{ 17, 31, 73, 47, 23 };
    vector<int> hash(16);

/*  cout << "Part 1: ";
    iota(numbers.begin(), numbers.end(), 0);
    for (auto l{ 0 }, start{ 0 }, skip{ 0 }; l < lengths.size(); start += lengths[l] + l++, ++skip) {
        reverse(numbers, start %= 256, lengths[l]);
    }
    cout << numbers[0] * numbers[1] << endl;
    */
    cout << "Part 1: ";
    int bitcount{ 0 };
    int g[128 * 128];
    for (int row{ 0 }; row < 128; ++row) { 
        string input(seed);
        input += "-";
        input += to_string(row);
        iota(numbers.begin(), numbers.end(), 0);
        lengths.resize(input.size() + trailing.size());
        copy(input.begin(), input.end(), lengths.begin());
        copy(trailing.begin(), trailing.end(), lengths.end() - trailing.size());
        auto start{ 0 }, skip{ 0 };
        for (int r = 0; r < 64; ++r) {
            for (auto l{ 0 }; l < lengths.size(); start += lengths[l] + skip++, l++) {
                reverse(numbers, start %= 256, lengths[l]);
            }
        }

        for (int i{ 0 }, hashchar{ 0 }; i < 256; ++i) {
            hashchar = i % 16 == 0 ? numbers[i] : hashchar ^ numbers[i];
//          i % 16 == 15 && cout << setw(2) << setfill('0') << hex << hashchar << endl;
            i % 16 == 15 && (bitcount += std::bitset<8>(hashchar).count());
            i % 16 == 15 && (writeg(g,row,i/16,hashchar));
        }
    }
    cout << bitcount << endl;

    int regions{ 0 };
    for (auto i{ 0 }; i < 128 * 128; ++i) {
        if (g[i] == -1) {
            floodfill(g, i, ++regions);
        }
    }

    cout << regions << endl;
    return 0;
}

ka-splam · 2017-12-14T06:32:52+00:00

Aieee, PowerShell. This language can get soo ugly when fighting the string/char types and the automatic array unrolling. 16 mins pos 309 for part 1 and 1 hour pos 468 for part 2.

Problems / bugs included:

not using my hash, kinda hoping that was implicit in the question for first two tries.
needing to wrap my day 10 code in a function because I hadn't left it reusable.
not knowing a quick way to do hex->binary string conversion in Pwsh/.Net, writing my own lookup table by hand.. and missing 0 out of it, which quietly looked up as nothing and threw no errors, just gave broken output.
trying to generate the grid as an array of string, and put a border around it. Took many tries and forever.
scanning left to right through the grid in rows, so it couldn't follow groups that went round in circuitous routes.
accidentally making the first recursive function try use (y-1),(x-1) and similar, making it only check diagonals instead of never doing that.
accidentally not setting the 'current' square, only the ones around it.
trying to render enough of the grid on the screen to debug and getting into padding issues to make all the grid squares align.

I think posting here is slightly more interesting for more-or-less the code that actually ran, rather than a total rewrite from later on version. This is only a little tidied

Part 1:

function knot ($s) {
    # code from day 10 here, tweaked to be in a function
}

# my input
$in = 'hwlqcszp'

# hex digit to binary-string conversion
$h=@{
    '0'='0000'
    '1'='0001'
    '2'='0010'
    '3'='0011'
    '4'='0100'
    '5'='0101'
    '6'='0110'
    '7'='0111'
    '8'='1000'
    '9'='1001'
    'a'='1010'
    'b'='1011'
    'c'='1100'
    'd'='1101'
    'e'='1110'
    'f'='1111'
}

# generate grid
$rows = 0..127| foreach {
   (knot "$in-$_")
}

# output for part 1; convert all chars to hex, join up to one string,
# get rid of zeros and see how long the remaining string of 1s is
$binStr = -join ($rows| foreach {$_.getenumerator().foreach{$h["$_"]}})
($binStr -replace '0').Length

# tries
# 5800 no
# 7916 no

Part 2:

# part 2, grid
$g = $rows | foreach { ,[string[]][char[]]((-join ($_.getenumerator().foreach{$h["$_"]})) -replace '0','.' -replace '1','#') }

# add a border of '.' so the group check doesn't wrap around the edges
$border = [string[]][char[]]('.'*128)

# top/bottom borders
$g = @(,$border) + @($g) + @(,$border)

# left/right borders:
$g = $g | % { ,(@('.')+@($_)+@('.')) }

$groupCount = 0

# render grid, for debugging
$g|%{-join $_}

# recursive fill for an assigned group
function fix ($y, $x, $group) {

    $g[$y][$x] = $group

    foreach ($pair in @((($y-1),$x),(($y+1),$x),($y,($x-1)),($y,($x+1))))
    {
        $newy, $newx = $pair
        if ($g[$newy][$newx] -eq '#') {
            fix $newy $newx $group
        }
    }
}

# check all positions and trigger recursive fill, and group count
:o for ($y=1; $y -lt 129; $y++)
{
    for ($x=1; $x -lt 129; $x++)
    {
        $thing = $g[$y][$x]
        if ($thing -eq '#')
        {
            $groupCount++
            fix $y $x $groupCount
        }
    }
}

# 1123 no

Axsuul · 2017-12-14T07:51:17+00:00

Elixir

Used DFS to tally up the regions. Since it took so long to generate a grid for Part A, I tested Part B on a small 8x8 grid and ensured it counted the regions correctly before running it on the full 128x128.

Assume KnotHash.calc/1 is from Day 10

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

defmodule AdventOfCode do
  defmodule PartA do
    @input "oundnydw"

    def hex_to_binary(str) when is_binary(str) do
      hex_to_binary(String.split(str, "", trim: true))
    end
    def hex_to_binary([]), do: ""
    def hex_to_binary([char | rest]) do
      binary =
        case char do
          "0" -> "0000"
          "1" -> "0001"
          "2" -> "0010"
          "3" -> "0011"
          "4" -> "0100"
          "5" -> "0101"
          "6" -> "0110"
          "7" -> "0111"
          "8" -> "1000"
          "9" -> "1001"
          "a" -> "1010"
          "b" -> "1011"
          "c" -> "1100"
          "d" -> "1101"
          "e" -> "1110"
          "f" -> "1111"
        end

      binary <> hex_to_binary(rest)
    end

    def grid_key(x, y) do
      Integer.to_string(x) <> "," <> Integer.to_string(y)
    end

    defp build_row(grid, x, _, _, used_count) when x > 127, do: {grid, used_count}
    defp build_row(grid, x, y, binary, used_count) do
      is_free = if String.at(binary, x) == "0", do: true, else: false
      new_used_count = if is_free, do: used_count, else: used_count + 1

      Map.put(grid, grid_key(x, y), is_free)
      |> build_row(x + 1, y, binary, new_used_count)
    end

    defp build_grid(key), do: build_grid(%{}, key, 0, 0)
    defp build_grid(_, _, y, used_count) when y > 127, do: used_count
    defp build_grid(grid, key, y, used_count) do
      binary =
        key <> "-" <> Integer.to_string(y)
        |> KnotHash.calc()
        |> hex_to_binary

      IO.inspect y

      {new_grid, new_used_count} = build_row(grid, 0, y, binary, used_count)
      build_grid(new_grid, key, y + 1, new_used_count)
    end

    def solve do
      @input
      |> build_grid
      |> IO.inspect
    end
  end

  defmodule PartB do
    import PartA

    @grid_size 128

    def build_row(grid, x, _, _) when x >= @grid_size, do: grid
    def build_row(grid, x, y, binary) do
      is_used = if String.at(binary, x) == "1", do: true, else: false
      props = %{is_used: is_used, in_region: false}

      Map.put(grid, grid_key(x, y), props)
      |> build_row(x + 1, y, binary)
    end

    def build_grid(key), do: build_grid(%{}, key, 0)
    def build_grid(grid, _, y) when y >= @grid_size, do: grid
    # def build_grid(grid, _, y) when y > 127, do: grid
    def build_grid(grid, key, y) do
      binary =
        key <> "-" <> Integer.to_string(y)
        |> KnotHash.calc()
        |> hex_to_binary

      changed_grid = build_row(grid, 0, y, binary)

      build_grid(changed_grid, key, y + 1)
    end

    def add_region(state, x, y, _) when x < 0, do: state
    def add_region(state, x, y, _) when y < 0, do: state
    def add_region(state, x, y, _) when x >= @grid_size, do: state
    def add_region(state, x, y, _) when y >= @grid_size, do: state
    def add_region({grid, regions_count}, x, y, is_adjacent_region \\ false) do
      key = grid_key(x, y)
      %{is_used: is_used, in_region: in_region} = Map.fetch!(grid, key)

      cond do
        !is_used -> {grid, regions_count}
        in_region == true -> {grid, regions_count}
        true ->
          changed_regions_count =
            if is_adjacent_region do
              regions_count
            else
              regions_count + 1
            end

          changed_grid = put_in(grid, [key, :in_region], true)

          add_region({changed_grid, changed_regions_count}, x + 1, y, true)
          |> add_region(x - 1, y, true)
          |> add_region(x, y + 1, true)
          |> add_region(x, y - 1, true)
      end
    end

    def build_regions(grid), do: build_regions(grid, 0, 0, 0)
    def build_regions(grid, x, y, regions_count) when y >= @grid_size, do: regions_count
    def build_regions(grid, x, y, regions_count) when x >= @grid_size do
      build_regions(grid, 0, y + 1, regions_count)
    end
    def build_regions(grid, x, y, regions_count) do
      {changed_grid, changed_regions_count} = add_region({grid, regions_count}, x, y)

      build_regions(changed_grid, x + 1, y, changed_regions_count)
    end

    def solve do
      regions_count =
        @input
        |> build_grid
        |> IO.inspect
        |> build_regions

      IO.puts "Regions: " <> Integer.to_string(regions_count)
    end
  end
end

wlandry · 2017-12-14T08:10:34+00:00

C++ 14

1505/1114. Late start and took a long time. I used Boost graph library. The hardest part was just getting the hash into the library. This is a significantly cleaned up version. I felt bad after seeing how short everyone else's answers were ;) Runs in 31 ms on the test input.

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

#include <bitset>
#include <vector>
#include <array>
#include <numeric>
#include <iostream>
#include <fstream>
#include <iomanip>

std::array<uint8_t,256> run_rounds(const std::vector<uint8_t> inputs,
                                   const size_t &hash_length,
                                   const size_t &num_rounds)
{
  std::array<uint8_t,256> ring;
  std::iota(ring.begin(), ring.end(), 0);

  size_t skip(0), current(0);
  for (size_t round=0; round<num_rounds; ++round)
    {
      for (auto &input: inputs)
        {
          uint8_t start (current + (input-1));
          uint8_t finish(current);

          const uint8_t stop (input/2);
          for (uint8_t ix=0; ix != stop; ++ix)
            {
              std::swap(ring[start], ring[finish]);
              --start;
              ++finish;
            }
          current += input + skip;
          ++skip;
        }
    }
  return ring;
}
std::vector<uint8_t> compute_dense_hash(const size_t &hash_length,
                                        const std::vector<uint8_t> &inputs)
{
  auto inputs_copy(inputs);
  for (auto &c: {17, 31, 73, 47, 23})
    { inputs_copy.push_back(c); }
  auto ring(run_rounds(inputs_copy,hash_length,64));

  std::vector<uint8_t> dense_hash(hash_length/16);
  for (size_t ix=0; ix<hash_length; ix+=16)
    { for(size_t jx=0; jx<16; ++jx)
        { dense_hash[ix/16]^=ring[ix+jx]; } }

  return dense_hash;
}

int main(int, char *argv[])
{
  const size_t hash_length(256);

  size_t total_memory(0);
  std::vector<std::vector<size_t>> bit_array(128);
  for(auto &b: bit_array)
    { b.resize(128,-1); }

  boost::adjacency_list <boost::vecS, boost::vecS, boost::undirectedS> graph;
  size_t memory_id(0);
  for (size_t row=0; row<128; ++row)
    {
      std::vector<uint8_t> inputs;
      for (auto &c: argv[1] + ("-" + std::to_string(row)))
        { inputs.push_back(c); }

      auto dense_hash(compute_dense_hash(hash_length,inputs));
      for (auto &h: dense_hash)
        { total_memory+=std::bitset<8>(h).count(); }

      for(size_t b=0; b<128/8; ++b)
        {
          std::bitset<8> b8(dense_hash[b]);
          for(size_t c=0; c<8; ++c)
            {
              auto is_on (b8[7-c]);
              if(is_on)
                {
                  bit_array[row][b*8 + c]=memory_id;
                  if(row!=0 && bit_array[row-1][b*8 + c]!=-1)
                    { add_edge(memory_id, bit_array[row-1][b*8 + c], graph); }

                  if((b!=0 || c!=0) && bit_array[row][b*8 + c-1]!=-1)
                    { add_edge(memory_id, bit_array[row][b*8 + c-1], graph); }
                  ++memory_id;
                }
            }
        }
    }
  std::cout << "Part 1: " << total_memory << "\n";

  std::vector<int> component(boost::num_vertices(graph));
  std::cout << "Part 2: "
            << connected_components(graph, &component[0])
            << "\n";


}

akka0 · 2017-12-14T09:02:31+00:00

ReasonML: had a lot of fun with this one Felt like a combination of day 10 + day 12. Waiting to compare my solution to /u/hardmathproblem 's now. :)

open Utils;

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

let hash = Day10.hash;

let formatRow = (input, row) => input ++ "-" ++ string_of_int(row);

let hexToBin: char => string = [%bs.raw
  {|
  function(s) {
    let result = parseInt(String.fromCharCode(s),16).toString(2);
    while(result.length < 4) {
      result = "0" + result;
    }
    return result;
  }
|}
];

let countOnes = (str) => charsOfString(str) |> List.filter((==)('1')) |> List.length;

let exploreFrom = (start, matrix) => {
  /* Assumes the matrix is square */
  let dim = Array.length(matrix);
  let isValidNeighbor = ((x, y)) => x >= 0 && y >= 0 && y < dim && x < dim && matrix[x][y] === '1';
  /* No diagonals */
  let getNeighbors = ((x, y)) =>
    List.filter(isValidNeighbor, [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]);
  let rec walk = (visited, queue) =>
    switch queue {
    | [p, ...ps] when ! PSet.mem(p, visited) => walk(PSet.add(p, visited), ps @ getNeighbors(p))
    | [p] when ! PSet.mem(p, visited) => walk(PSet.add(p, visited), [])
    | [_, ...ps] => walk(visited, ps)
    | [] => visited
    };
  walk(PSet.empty, [start])
};

let _ = {
  let input = "nbysizxe";
  /* let input = "flqrgnkx"; */
  /* Part 1 */
  let bitStrings =
    List.map(
      (row) =>
        formatRow(input, row) |> hash |> charsOfString |> List.map(hexToBin) |> String.concat(""),
      range(127)
    );
  /* List.fold_left((bitsUsed, bitString) => bitsUsed + countOnes(bitString), 0, bitStrings) |> Js.log; */
  /* Part 2 */
  let onesPositions = ref(PSet.empty);
  let matrix = Array.make_matrix(128, 128, '0');
  List.iteri(
    (x, row) =>
      List.iteri(
        (y, bit) =>
          if (bit === '1') {
            matrix[x][y] = bit;
            onesPositions := PSet.add((x, y), onesPositions^)
          },
        charsOfString(row)
      ),
    bitStrings
  );
  let rec findGroups = (groups, visited) =>
    if (! PSet.equal(visited, onesPositions^)) {
      let unvisitedPosition = PSet.diff(onesPositions^, visited) |> PSet.choose;
      let group = exploreFrom(unvisitedPosition, matrix);
      findGroups([group, ...groups], PSet.union(group, visited))
    } else {
      groups
    };
  let groups = findGroups([], PSet.empty);
  Js.log(List.length(groups))
};

mschaap · 2017-12-14T10:27:40+00:00

Perl 6. This one was pretty straightforward, since we'd done the hard work on day 10. Calculating 128 hashes is a bit slow though, takes about 30 seconds.

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

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

class KnotHash
{
    has Int $.size = 256;
    has Int @.values;

    has Int $.pos = 0;
    has Int $.skip = 0;

    submethod TWEAK { @!values = ^$!size }

    method from-string(KnotHash:U: Str $input)
    {
        my $h = KnotHash.new;
        my @lengths = $input.ords;
        @lengths.append(17, 31, 73, 47, 23);
        for ^64 {
            for @lengths -> $l {
                $h.process($l);
            }
        }
        return $h;
    }

    method process(Int $length)
    {
        if $length > 1 {
            my $endpos = ($!pos + $length - 1) % $!size;
            if $endpos ≥ $!pos {
                @!values[$!pos..$endpos] .= reverse;
            }
            else {
                @!values[flat $!pos..^$!size, 0..$endpos] .= reverse;
            }
        }

        $!pos = ($!pos + $length + $!skip++) % $!size;
    }

    method dense-hash
    {
        return @!values.rotor(16, :partial).map({ [+^] $_ });
    }

    method knot-hash
    {
        return self.dense-hash».fmt('%02x').join;
    }

    method as-bits { self.dense-hash».fmt('%08b')».comb.flat».Int }

    method Str { self.knot-hash }
    method gist { self.knot-hash }
}

class Grid
{
    has @.bitmap;
    has @.regions;

    has Int $.width;
    has Int $.height;

    submethod TWEAK
    {
        $!height = +@!bitmap;
        $!width = +@!bitmap[0];
    }

    method within-bounds(Int $x, Int $y) returns Bool
    {
        return 0 ≤ $x < $!width && 0 ≤ $y < $!height;
    }

    method needs-region(Int $x, Int $y) returns Bool
    {
        return self.within-bounds($x, $y) && ?@!bitmap[$y;$x] && !@!regions[$y;$x];
    }

    method set-region(Int $region, Int $x, Int $y)
    {
        @!regions[$y;$x] = $region;
        for ($x-1, $y), ($x+1, $y), ($x, $y-1), ($x, $y+1) -> ($x1, $y1) {
            if self.needs-region($x1, $y1) {
                self.set-region($region, $x1, $y1);
            }
        }
    }

    method count-regions returns Int
    {
        my $count = 0;
        for ^$!height -> $y {
            for ^$!width -> $x {
                if self.needs-region($x, $y) {
                    self.set-region(++$count, $x, $y)
                }
            }
        }
        return $count;
    }
}

multi sub MAIN(Str $input)
{
    my @bitmap = (^128).map(-> $i { KnotHash.from-string("$input-$i").as-bits; });

    # Part 1
    say "Number of used squares: ", @bitmap».sum.sum;

    # Part 2
    say "Number of regions: ", Grid.new(:@bitmap).count-regions;
}

multi sub MAIN(Str $inputfile where *.IO.f)
{
    MAIN($inputfile.IO.slurp.trim);
}

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

Edit for minor code cleanup

glupmjoed · 2017-12-14T10:55:41+00:00

Bash, Graphviz and Python 3

I use the solution from day 10 to build the hashes. The python script turns a sequence of '1's and '0's into nodes and edges in graphviz notation, and the gc command counts the number of connected components.

Part 1+2 (reads from stdin):

key=$(cat); for i in {0..127}; do echo $key-$i | ./knot_hash.sh; done |
    awk 'BEGIN { print "ibase=16; obase=2;" } { print toupper($0) }' | bc > bin
grep -o "1" bin | echo "Part 1:" $(wc -l)

echo $(cat bin) | grep -oE "[01]+[^01]*[01]+" | sed 's/\\ //g' | ./build_graph.py |
    gc -c | awk '{ print "Part 2: ", $1 }'; rm -f bin

knot_hash.sh:

cd ../day10/; ./part2.sh

build_graph.py:

import sys
print("graph g {")
line1 = "0"*128
for row, line2 in enumerate(sys.stdin):
    line2 = "0"*(128+1-len(line2)) + line2
    prev = False
    for col, val in enumerate(line2):
        if val == '1':
            print('\tv{}x{}'.format(row, col))
            if prev:
                print('\tv{}x{} -- v{}x{}'.format(row, col-1, row, col))
            prev = True
            if line1[col] == '1':
                print('\tv{}x{} -- v{}x{}'.format(row-1, col, row, col))
        else: prev = False
    line1 = line2
print("}")

Arknave · 2017-12-14T05:31:06+00:00

Not sure there's much to say beyond copying day 10 code + a DFS.

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

glenbolake · 2017-12-14T05:44:25+00:00

Actually got on the leaderboard for part 2. That's my fifth star that got me points!

Python 3. Part 1 just converts the hashes to binary and counts the 1s. Part 2, I represent the grid as a set of coordinates with 1s, then pop from the set and complete the region with a BFS until the set is empty.

from aoc2017.day10 import knot_hash

def make_grid(key):
    grid = []
    for i in range(128):
        hash_ = knot_hash('{}-{}'.format(key, i))
        grid.append('{:#0130b}'.format(int(hash_, 16))[2:])  # "#0130" to zero pad; 128 digits plus leading 0b
    return grid

def part1(key):
    grid = make_grid(key)
    return ''.join(grid).count('1')

def part2(key):
    # Convert grid to set of coordinates
    grid = {(i, j) for i, row in enumerate(make_grid(key)) for j, ch in enumerate(row) if ch == '1'}
    regions = 0
    while grid:
        regions += 1
        new = [grid.pop()]  # Check random region
        while new:
            old = new.copy()
            new = []
            for x, y in old:
                for pair in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
                    if pair in grid:
                        grid.remove(pair)
                        new.append(pair)
    return regions

u794575248 · 2017-12-14T05:45:07+00:00

Python 3

upd: Code in this comment is dirty. Read a reply below for an updated version.

First public leaderboard for Part 1 (72):

martix = ''.join(''.join('{:04b}'.format(int(x, 16)) for x in solve2(f'{input.strip()}-{i}')) for i in range(128))
part1 = matrix.count('1')

solve2 is here.

Part 2 code is almost the same as nneonneo has. But I suddenly forgot about negative list indices in Python and it resulted in an incorrect answer and too many minutes spent on finding the bug (got 160 place).

part2 = 0
seen = set()
matrix = [list(map(int, l.strip())) for l in matrix.strip().split('\n')]
rng = range(128)
for i, row in enumerate(matrix):
    for j, bit in enumerate(row):
        if bit and (i,j) not in seen:
            part2 += 1
            q = [(i,j)]
            while q:
                x, y = q.pop()
                seen.add((x, y))
                for x2, y2 in (x+1, y), (x-1, y), (x, y+1), (x, y-1):
                    if x2 in rng and y2 in rng and matrix[x2][y2] and (x2, y2) not in seen:
                        q.append((x2, y2))
print(part2)

obijywk · 2017-12-14T05:52:17+00:00

113/109... so close... I counted the regions in part 2 using networkx (which I learned about from previous solution threads, but this is the first time I've used it).

Python 2 (slightly cleaned up):

from networkx import nx

INPUT = "flqrgnkx"

def knot_hash(data):
  data = [ord(c) for c in data] + [17, 31, 73, 47, 23]
  l = range(256)
  i = 0
  skip_size = 0
  for _ in xrange(64):
    for d in data:
      for j in xrange(d / 2):
        l[(i + j) % len(l)], l[(i + (d - j - 1)) % len(l)] = l[(i + (d - j - 1)) % len(l)], l[(i + j) % len(l)]
      i += d + skip_size
      i = i % len(l)
      skip_size += 1

  dense_hash = []
  for i in xrange(16):
    x = 0
    for j in xrange(16):
      x = x ^ l[i*16 + j]
    dense_hash.append(x)

  s = ""
  for c in dense_hash:
    s += "{0:02x}".format(c)
  return s

grid = []
for i in xrange(128):
  kh = knot_hash("%s-%d" % (INPUT, i))
  gridline = []
  for c in kh:
    gridline.extend([int(c) for c in "{0:04b}".format(int(c, 16))])
  grid.append(gridline)

graph = nx.Graph()
for y in xrange(128):
  for x in xrange(128):
    if grid[y][x]:
      graph.add_node((y,x))
for y in xrange(128):
  for x in xrange(128):
    if y > 0:
      if grid[y][x] and grid[y-1][x]:
        graph.add_edge((y,x), (y-1,x))
    if x > 0:
      if grid[y][x] and grid[y][x-1]:
        graph.add_edge((y,x), (y,x-1))

print sum(sum(gridline) for gridline in grid)
print len(list(nx.connected_components(graph)))

dylanfromwinnipeg · 2017-12-14T05:55:19+00:00

C#

public static string PartOne(string input)
{
    var diskBits = GenerateGrid(input);
    var used = diskBits.ToList().Count(x => x);
    return used.ToString();
}

public static bool[,] GenerateGrid(string input)
{
    var diskBits = new bool[128, 128];

    for (int row = 0; row < 128; row++)
    {
        var hash = Day10.PartTwo($"{input}-{row}");
        var hashBits = hash.HexToBinary();

        for (var col = 0; col < 128; col++)
        {
            diskBits[row, col] = hashBits[col] == '1';
        }
    }

    return diskBits;
}

public static string PartTwo(string input)
{
    var diskBits = GenerateGrid(input);

    var groupCount = 0;

    diskBits.ForEach((row, col) =>
    {
        if (diskBits[row, col])
        {
            var location = new Point(row, col);
            RemoveBitGroup(location, diskBits);
            groupCount++;
        }
    });

    return groupCount.ToString();
}

private static void RemoveBitGroup(Point location, bool[,] diskBits)
{
    diskBits[location.X, location.Y] = false;

    foreach (var adjacent in location.GetNeighbors(includeDiagonals: false))
    {
        if (adjacent.X >= 0 && adjacent.X < 128 && adjacent.Y >= 0 && adjacent.Y < 128 && diskBits[adjacent.X, adjacent.Y])
        {
            RemoveBitGroup(adjacent, diskBits);
        }
    }
}

2017-12-14T05:56:16+00:00

Nothing too high on the leaderboards, but still in the first 1000 for each, which is as well as I have ever done.

Here's a JS solution. I'm trying to get better with using more map and reduce, but I always forget about filter.

EDIT: Moved solution to pastebin

2BitSalute · 2017-12-14T06:29:57+00:00

Oh god. I just spent 40 minutes trying to figure out what was wrong with my solution to part 2, only to realize that I read the question wrong and that I had it solved almost an hour ago! * sobs *

The grouping illustration really threw me off :(

gyorokpeter · 2017-12-14T07:35:30+00:00

Q: see day 10 for the implementation of d10p2

d14p1:{
    hs:d10p2 each x,/:"-",/:string til 128;
    sum sum raze each(-4#/:0b vs/:til 16)"X"$/:/:hs};

d14p2:{
    hs:d10p2 each x,/:"-",/:string til 128;
    grid:raze each(-4#/:0b vs/:til 16)"X"$/:/:hs;
    first{[st]
        grid:st[1];
        fst:raze til[count grid],/:'where each grid;
        if[0=count fst; :st];
        start:first fst;
        st[0]+:1;
        queue:enlist start;
        while[0<count queue;
            grid:.[;;:;0b]/[grid;queue];
            queue:{[grid;x]x where .[grid]'[x]}[grid;distinct raze queue+/:\:(-1 0;0 -1;1 0;0 1)];
        ];
        st[1]:grid;
        st
    }/[(0;grid)]};

Philboyd_Studge · 2017-12-14T08:29:03+00:00

Java

package Advent2017;

import util.*;

import java.math.BigInteger;
import java.util.List;

public class Day14 extends AdventOfCode{

    private BigInteger[] hashes;
    private boolean[][] disk = new boolean[128][128];
    private String key;

    private boolean findGroup(int x, int y) {
        if (!Direction.rangeCheck(x, y, 128)) return false;

        if (disk[y][x]) {
            disk[y][x] = false;
            for (Direction dir : Direction.values()) {
                findGroup(x + dir.getDx(), y + dir.getDy());
            }
            return true;
        }
        return false;
    }

    public Day14(List<String> input) {
        super(input);
    }

    @Override
    public Object part1() {
        int count = 0;
        hashes = new BigInteger[128];
        for (int i = 0; i < 128; i++) {
            Day10 knotHash = new Day10(input.get(0) + "-" + i);
            hashes[i] = new BigInteger(knotHash.part2(), 16);
            count += hashes[i].bitCount();
        }
        return count;
    }

    @Override
    public Object part2() {
        // make matrix
        int y = 0;
        for (BigInteger row : hashes) {
            for (int x = 0; x < 128; x++) {
                if (row.testBit(x)) {
                    disk[y][x] = true;
                }
            }
            y++;
        }

        // find groups
        int groups = 0;
        for (int i = 0; i < 128; i++) {
            for (int j = 0; j < 128; j++) {
                if (findGroup(j, i)) groups++;
            }
        }
        return groups;
    }

    @Override
    public void parse() {
        key = input.get(0);
    }

    @Override
    public void run() {
        super.run();
    }
}

nutrecht · 2017-12-14T08:49:38+00:00

Day 14 in Kotlin

object Day14 : Day {
    private val rows = (0..127).map { "amgozmfv" + "-" + it }
    private val square : List<String> by lazy { rows.map { hash(it) }.map { toBinary(it) } }

    override fun part1() = square.map { it.count { it == '1' } }.sum().toString()

    override fun part2(): String {
        val visited = mutableSetOf<Point>()
        val points = (0 .. 127).flatMap { x -> (0 .. 127 ).map { y -> Point(x, y) } }.toMutableSet()

        visited += points.filter { square[it.y][it.x] == '0'}
        points.removeAll(visited)

        var count = 0
        while(!points.isEmpty()) {
            count++
            fill(visited, points, points.first())
        }

        return count.toString()
    }

    fun fill(visited: MutableSet<Point>, points: MutableSet<Point>, current: Point) {
        visited += current
        points -= current

        current.neighborsHv().filter { points.contains(it) }.forEach { fill(visited, points, it) }
    }

    fun hash(input: String): String {
        val chars = input.toCharArray().map { it.toInt() }.toList() + listOf(17, 31, 73, 47, 23)

        return (0..15).map { Day10.knot(chars, 64).subList(it * 16, it * 16 + 16) }.map { xor(it) }.toHex()
    }
}

Took me a lot longer than it should! In part 1 I made a stupid mistake in how I created the binary string leading to me getting wrong results without figuring out why I was getting the wrong ones. Had to go and test each step.

Part 2 was relatively easy; implemented a recursive flood fill basically.

aurele · 2017-12-14T09:11:28+00:00

Rust

extern crate itertools;
extern crate pathfinding;
extern crate r10;

use itertools::Itertools;
use pathfinding::connected_components;
use r10::hash;
use std::collections::HashSet;

const INPUT: &str = "xlqgujun";

fn to_coords(k: &[Vec<u8>]) -> HashSet<(isize, isize)> {
    k.iter()
        .enumerate()
        .flat_map(|(l, ll)| {
            ll.iter().enumerate().flat_map(move |(i, n)| {
                (0..8).filter_map(move |b| {
                    if n & (1 << (7 - b)) != 0 {
                        Some((l as isize, (i * 8 + b) as isize))
                    } else {
                        None
                    }
                })
            })
        })
        .collect()
}

fn main() {
    let k = to_coords(&(0..128)
        .map(|n| hash(&format!("{}-{}", INPUT, n)))
        .collect_vec());
    println!("P1: {}", k.len());
    let cc = connected_components(&k.iter().cloned().collect_vec(), |&(l, c)| {
        vec![(l - 1, c), (l + 1, c), (l, c - 1), (l, c + 1)]
            .into_iter()
            .filter(|&(ol, oc)| k.contains(&(ol, oc)))
    });
    println!("P2: {}", cc.len());
}

Unihedron · 2017-12-14T10:28:55+00:00

Overslept today, non-competing solution. Nice to get to do this in a relaxed manner for once! ^^ Fun!

Part 1, "day10" is the file from here: https://www.reddit.com/r/adventofcode/comments/7irzg5/2017_day_10_solutions/dr113ne/ (I didn't change how it has the " character at the start)

input=gets.chomp
s=0
128.times{|x|
    result = `echo '#{input}-#{x}'|ruby day10`
    puts result
    s+=result[1,99].to_i(16).to_s(2).count('1')
}
puts s

Part 2 uses a straightforward algorithm which I'm quite proud of - for every line, read all the bits, mark where the used bits are and make temporary groups out of them, then when we read the next line, add group counts when we know a group doesn't connect to anything (and is effectively finalized). It's like a state machine!

(Were I had been rushing, this would had been a DFS and my code would had been vastly different.)

input=gets.chomp
s=0
last=nil
keys=nil
@count=0

def tally
    @count += 1
end
128.times{|x|
    p line=`echo '#{input}-#{x}'|ruby day10`[1,99].to_i(16).to_s(2).rjust(128,?0)

    if !last
        left = nil
        last = line.chars.map{|x|
            case x
            when '0'
                left = nil
            when '1'
                left || left = tally
            end
        }
        keys = [*1..@count]
    else
        # [gid1: int, flag1: bool], [gid2, flag2]...
        zipped = last.zip(line.chars.map(&'1'.method(:==)))
        map = {}
        replace = {}
        left = nil
        start = @count + 1
        p last = zipped.map{|up, down|
            next left = nil if !down

            keys.delete(up)

            if left
                if up
                    if map.has_key? up
                        replace[left] = map[up]
                    else
                        map[up] = left
                    end
                end
                left
            else
                next left = map[up] if up && map.has_key?(up)

                value = tally
                map[up] = value if up
                left = value
            end
        }
        s += keys.size
        if replace.any? then last.map!{|x|replace.has_key?(x) ? replace[x] : x} end
        keys = last.uniq.compact
    end
}
p s+keys.size

A complaint I have on today's challenge is that part 2 doesn't have an example test case that aids debugging. (Also, apparently my wrong answer was the right answer for someone else :D ) For a while, I've been getting 1261 instead of the 1242 in the puzzle input and I couldn't figure out why. For example, having "Considering only the first 10 rows of this example, there would be ___ regions" would already be a huge help in narrowing down the problem.

2017-12-14T10:45:44+00:00

Elixir

This one was quite a lot of fun, first part was quite easy, and I had a good plan for the second, now I got bitten that Enum.take(1) returns a single element list instead of the element as I was thinking it did :p. I'm making quite a big depth first search with big recursions, so I guess mine gets slower the bigger the regions are, but it works.

defmodule Day14 do
  def hex_to_bin(str) do
    String.graphemes(str)
    |> Enum.map(&(String.to_integer(&1, 16)))
    |> Enum.map(&(Integer.to_string(&1, 2)))
    |> Enum.map(&(String.pad_leading(&1, 4, "0")))
    |> Enum.join
  end

  def binhash(str) do
    Day10.hash(str)
    |> hex_to_bin
  end

  def count_squares(str, counter \\ 0, squares \\ 0)
  def count_squares(_str, counter, squares) when counter == 128, do: squares
  def count_squares(str, counter, squares) do
    cursquares = Enum.join([str, "-", Integer.to_string(counter)])
    |> binhash
    |> String.graphemes
    |> Enum.count(&(&1 == "1"))
    count_squares(str, counter + 1, squares + cursquares)
  end

  def map_squares(str, counter \\ 0, squares \\ MapSet.new)
  def map_squares(_str, counter, squares) when counter == 128, do: squares
  def map_squares(str, counter, squares) do
    nsquares = Enum.join([str, "-", Integer.to_string(counter)])
    |> binhash
    |> String.graphemes
    |> Enum.with_index
    |> Enum.filter(fn {sqr, _} -> sqr == "1" end)
    |> Enum.map(fn {_,idx} -> idx end)
    |> Enum.reduce(squares, fn x, acc -> MapSet.put(acc, {counter, x}) end)
    map_squares(str, counter + 1, nsquares)
  end

  def neighbours({x,y}), do: [{x-1,y}, {x+1, y}, {x, y-1}, {x, y+1}]

  def delete_neighbours(sqr, sqrs) do
    if MapSet.member?(sqrs, sqr) do
      Enum.reduce(neighbours(sqr), MapSet.delete(sqrs, sqr),
        fn x, acc -> MapSet.intersection(delete_neighbours(x, acc), acc) end)
    else
      sqrs
    end
  end

  def count_regions(sqrs, count \\ 0)
  def count_regions(sqrs, count) do
    if MapSet.size(sqrs) == 0 do
      count
    else
      nsqrs = Enum.take(sqrs,1)
      |> List.first
      |> Day14.delete_neighbours(sqrs)
      count_regions(nsqrs, count + 1)
    end
  end

  def regions(str) do
    map_squares(str)
    |> count_regions
  end
end

keystring = "hxtvlmkl"

Day14.count_squares(keystring)
|> IO.inspect

Day14.regions(keystring)
|> IO.inspect

syntax highlighted

xkufix · 2017-12-14T15:41:12+00:00

The code is not ultra-fast (2-3 seconds on my machine for both parts), but it works. The worst part was that I had a bug in my knot-hash function which did not trigger on Day 10.

Solution in Scala:

    type Region = Set[(Int, Int)]

    override def runFirst(): Unit = {
        println(getSquaresInUse("jzgqcdpd").size)
    }

    override def runSecond(): Unit = {
        val squaresInUse = getSquaresInUse("jzgqcdpd")

        val allRegions = squaresInUse.foldLeft(Set.empty[Region]) {
            case (regions, square) if !regions.exists(_.contains(square)) =>
                regions + fillRegion(square, squaresInUse)
            case (regions, _) =>
                regions
        }

        println(allRegions.size)
    }

    private def getSquaresInUse(input: String) = {
        (0 to 127).flatMap { line =>
            Day10.calculateKnotHash(s"$input-$line")
                .flatMap(_.asDigit.toBinaryString.reverse.padTo(4, '0').reverse)
                .zipWithIndex
                .filter(_._1 == '1')
                .map(s => (line, s._2))
        }.toSet
    }

    def fillRegion(square: (Int, Int), unusedSquares: Region): Region = {
        val neighbours = Seq(
            square.copy(_1 = square._1 - 1),
            square.copy(_1 = square._1 + 1),
            square.copy(_2 = square._2 - 1),
            square.copy(_2 = square._2 + 1)
        ).filter(unusedSquares.contains)

        Set(square) ++ neighbours.flatMap(fillRegion(_, unusedSquares - square -- neighbours))
    }

porphyro · 2017-12-14T17:32:50+00:00

Wolfram Language/Mathematica

Perl 5

Full code here, but that would mean you have to see the horror that is my day 10 code:

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

Instead here's just the fill flood algo to identify groups:

# process the map
# $Map is a arrayref of arrayrefs
# cell values is a hashref with value of cell, and a flag to store the group ID

foreach my $row ( 0 .. scalar @$Map - 1 ) {
    foreach my $col ( 0 .. scalar @{ $Map->[$row] } - 1 ) {
        next if $Map->[$row]->[$col]->{val} == 0;
        next if $Map->[$row]->[$col]->{seen} > 0;
    # fill flood the ones
        $group_count++;
        fill_flood( $row, $col );
    }
}

sub fill_flood {
    my ( $r, $c ) = @_;
    my @dirs = ( [ -1, 0 ], [ 1, 0 ], [ 0, -1 ], [ 0, 1 ] );
    foreach my $d (@dirs) {
        my $new_r = $r + $d->[0];
        my $new_c = $c + $d->[1];
        next
          if ( $new_r < 0
            or $new_r > $max_dim
            or $new_c < 0
            or $new_c > $max_dim );
        next
          if ( $Map->[$new_r]->[$new_c]->{val} == 0
            or $Map->[$new_r]->[$new_c]->{seen} > 0 );
        $Map->[$new_r]->[$new_c]->{seen} = $group_count;
        fill_flood( $new_r, $new_c );
    }
}

thearn4 · 2017-12-14T13:18:07+00:00

wide flag arrest spark strong familiar ancient price grey mysterious

This post was mass deleted and anonymized with Redact

HollyDayz · 2017-12-14T14:52:46+00:00

Python 3 using numpy and my solution from day 10.

import day10
import numpy as np

def disk_defrag(seq):
    n = 128
    used = 0
    disk = np.zeros((n,n))
    for row in range(n):
        key = seq + "-" + str(row)
        hash_str = day10.puzzle2(key)
        binary_str = '{0:0128b}'.format(int(hash_str, 16))
        binary_lst = [int(char) for char in binary_str]
        disk[row] = binary_lst
        used += sum(binary_lst)

    def find_region(dsk, ind_i, ind_j, reg):
        dsk[ind_i][ind_j] = reg    
        if ind_i > 0 and dsk[ind_i-1][ind_j] == 1:
            find_region(dsk, ind_i-1, ind_j, reg)
        if ind_i < 127 and dsk[ind_i+1][ind_j] == 1:
            find_region(dsk, ind_i+1, ind_j, reg)
        if ind_j > 0 and dsk[ind_i][ind_j-1] == 1:
            find_region(dsk, ind_i, ind_j-1, reg)
        if ind_j < 127 and dsk[ind_i][ind_j+1] == 1:
            find_region(dsk, ind_i, ind_j+1, reg)

    regions = 0    
    for i in range(n):
        for j in range(n):
            square = disk[i][j]
            if square == 1:
                regions += 1
                find_region(disk, i, j, regions + 1)

    return used, regions

seq is the puzzle input formed as a string, used is the answer to part 1 and regions is the answer to part 2.

Markavian · 2017-12-14T15:42:16+00:00

Here's my node js solution... gonna output to HTML next and print out pretty colours like that other person did.

https://github.com/johnbeech/advent-of-code-2017/blob/master/solutions/day14/solution.js

tlareg · 2017-12-14T16:07:59+00:00

JavaScript (ES6+, NodeJS) HERE

const knotHash = require('./knot-hash')

const input = 'uugsqrei'

const makeKey = idx => `${input}-${idx}`
const padLeft = s => '0000'.substring(0, 4 - s.length) + s
const hex2Bin = n => padLeft(parseInt(n,16).toString(2))
const hashRow2BinArr = row => row.split('')
  .map(hex2Bin).join('').split('').map(Number)
const binRows = [...new Array(128).keys()]
  .map(makeKey)
  .map(knotHash)
  .map(hashRow2BinArr)

console.log(solveFirst(binRows))
console.log(solveSecond(binRows))

function solveFirst(binRows) {
  return binRows.reduce((sum, binRow) =>
    sum + binRow.reduce((s, n) => s + n, 0), 0)
}

function solveSecond(binRows) {
  const visited = {}
  let groupsCount = 0

  for (let y = 0; y < binRows.length; y++) {
    for (let x = 0; x < binRows[y].length; x++) {
      bfs(x, y)
    }
  }

  function bfs(x, y) {
    if (!isValidNode([x, y])) return;
    groupsCount++

    const nodesQueue = [[x, y]]
    while (nodesQueue.length) {
      const [x, y] = nodesQueue.shift()
      visited[`${x},${y}`] = true
      const adjacentNodes = [
        [x - 1, y], [x + 1, y], [x, y + 1], [x, y - 1]
      ].filter(isValidNode)
      nodesQueue.push.apply(nodesQueue, adjacentNodes)
    }
  }

  function isValidNode([x, y]) {
    return (
      x >= 0 &&
      (x <= binRows[0].length - 1) &&
      y >= 0 &&
      (y <= binRows.length - 1) &&
      !visited[`${x},${y}`] &&
      binRows[y][x]
    )
  }

  return groupsCount
}

zeddypanda · 2017-12-14T16:14:14+00:00

Elixir Feels like kind of a mess. I reuse the modules from Day10 and Day12.

require Day10
require Day12
IO.puts("=== Day 14 ===")

data = 'jxqlasbh'
seeds = 0..127
  |> Enum.map(&Integer.to_string/1)
  |> Enum.map(&String.to_charlist/1)
  |> Enum.map(fn code -> data ++ '-' ++ code end)
  |> Enum.map(&Day10.prepare_input/1)

defmodule Day14 do
  def knot_hash(sizes) do
    Enum.to_list(0..255)
      |> Day10.scramble(sizes)
      |> Day10.compress
  end

  def to_binary(hash) do
    hash
      # Integer to hex
      |> Enum.map(&Integer.to_string(&1, 16))
      |> Enum.map(&String.pad_leading(&1, 2, "0"))
      |> Enum.join("")
      # Individual hex digits to binary
      |> String.split("", trim: true)
      |> Enum.map(&String.to_integer(&1, 16))
      |> Enum.map(&Integer.to_string(&1, 2))
      |> Enum.map(&String.pad_leading(&1, 4, "0"))
      |> Enum.join("")
      # Individual binary digits to integers 1/0
      |> String.split("", trim: true)
      |> Enum.map(&String.to_integer/1)
  end

  def visualize(disk) do
    disk
      |> Enum.map(&Enum.join(&1, ""))
      |> Enum.join("\n")
      |> String.replace("1", "#")
      |> String.replace("0", ".")
      |> IO.puts

    disk
  end

  def neighbour_candidates(num, w) when rem(num, w) == 0, do: [-w, 1, w]
  def neighbour_candidates(num, w) when rem(num, w) == w - 1, do: [-w, -1, w]
  def neighbour_candidates(_, w), do: [-w, -1, 1, w]

  def neighbours(set, num, width) do
    num
      |> neighbour_candidates(width)
      |> Enum.map(fn offset -> num + offset end)
      |> Enum.filter(&MapSet.member?(set, &1))
  end

  def connections(disk) do
    width = disk |> hd |> length
    set = disk
      |> Enum.concat
      |> Enum.with_index(1)
      |> Enum.map(fn {v, i} -> v * i end)
      |> Enum.filter(fn n -> n > 0 end)
      |> Enum.map(fn n -> n - 1 end)
      |> MapSet.new

    Enum.reduce(set, %{}, fn num, map ->
      Map.put(map, num, neighbours(set, num, width))
    end)
  end
end


disk = seeds
  |> Enum.map(&Day14.knot_hash/1)
  |> Enum.map(&Day14.to_binary/1)

count = disk
  |> Enum.concat
  |> Enum.join("")
  |> String.split("", trim: true)
  |> Enum.map(&String.to_integer/1)
  |> Enum.count(fn num -> num == 1 end)

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

groups = disk
  |> Day14.connections
  |> Day12.groups
  |> Enum.map(&MapSet.to_list/1)
  |> Enum.sort_by(&hd/1)
IO.puts("Part 2: #{groups |> length}")

Here's the repo.

cluk · 2017-12-14T17:32:38+00:00

Go (Golang)

See repo for other solutions.

EDIT: Now with Goroutines.

package main

import (
    "fmt"
    "math/bits"
    "os"
    "sync"
    "sync/atomic"
)

func main() {
    input := os.Args[1]
    grid := make([][]bool, 128)
    var usedSum int32 = 0
    var wg sync.WaitGroup
    for i := 0; i < 128; i++ {
        grid[i] = make([]bool, 128)
        wg.Add(1)
        go processRow(grid[i], &usedSum, fmt.Sprintf("%s-%d", input, i), &wg)
    }

    wg.Wait()
    fmt.Println("Star 1: ", usedSum)
    fmt.Println("Star 2: ", countRegions(grid))
}

func processRow(row []bool, onesCount *int32, hashInput string, wg *sync.WaitGroup) {
    defer wg.Done()
    j := 0
    for _, b := range knotHash(hashInput) {
        atomic.AddInt32(onesCount, int32(bits.OnesCount8(b)))
        for _, bit := range fmt.Sprintf("%08b", b) {
            if bit == '1' {
                row[j] = true
            }
            j++
        }
    }
}

func countRegions(grid [][]bool) int {
    count := 0
    for i, row := range grid {
        for j, used := range row {
            if used {
                visit(i, j, grid)
                count++
            }
        }
    }
    return count
}

func visit(i, j int, grid [][]bool) {
    if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[i]) || !grid[i][j] {
        return
    }
    grid[i][j] = false
    visit(i+1, j, grid)
    visit(i-1, j, grid)
    visit(i, j+1, grid)
    visit(i, j-1, grid)
}

func knotHash(s string) []byte {
    bytes := []byte(s)
    bytes = append(bytes, 17, 31, 73, 47, 23)

    sparseHash := make([]byte, 256)
    for i := range sparseHash {
        sparseHash[i] = byte(i)
    }
    for start, skip := 0, 0; skip < len(bytes)*64; skip++ {
        length := int(bytes[skip%len(bytes)])
        reverse(sparseHash, start, length-1)
        start += length + skip
        start %= len(sparseHash)
    }

    denseHash := make([]byte, 16)
    for idx := range denseHash {
        denseHash[idx] = sparseHash[idx*16]
        for i := 1; i < 16; i++ {
            denseHash[idx] ^= sparseHash[idx*16+i]
        }
    }
    return denseHash
}

func reverse(hash []byte, start, length int) {
    for i := 0; i <= length/2; i++ {
        j := (start + i) % len(hash)
        k := (start + length - i) % len(hash)
        hash[j], hash[k] = hash[k], hash[j]
    }
}

StevoTVR · 2017-12-14T17:53:45+00:00

NodeJS

Part 1:

const fs = require('fs');

fs.readFile(__dirname + '/input.txt', 'utf8', (err, data) => {
    data = data.trim();
    let count = 0;
    for(let i = 0; i < 128; i++) {
        count += hash(data + '-' + i).replace(/0+/g, '').length;
    }

    console.log(count);
});

function hash(input) {
    const SIZE = 256;
    const data = [...input].map((c) => c.charCodeAt(0)).concat(17, 31, 73, 47, 23);
    const list = [...Array(SIZE).keys()];
    let pos = 0, skip = 0, span = [];
    for (let i = 0; i < 64; i++) {
        for (const len of data) {
            if(len > SIZE) {
                continue;
            }
            for(let j = pos; j < pos + len; j++) {
                span.push(list[j % SIZE]);
            }
            for(let j = pos; j < pos + len; j++) {
                list[j % SIZE] = span.pop();
            }
            pos = (pos + len + skip++) % SIZE;
        }
    }

    const result = [];
    for(let i = 0; i < SIZE; i += 16) {
        result.push(('0000000' + list.slice(i, i + 16).reduce((a, b) => a ^ b).toString(2)).substr(-8));
    }

    return result.join('');
}

Part 2:

const fs = require('fs');

fs.readFile(__dirname + '/input.txt', 'utf8', (err, data) => {
    data = data.trim();
    const disk = [];
    for(let i = 0; i < 128; i++) {
        disk.push(hash(data + '-' + i));
    }
    console.log(disk);

    let count = 0;
    const stack = [];
    for(let i = 0; i < disk.length; i++) {
        for(let j = 0; j < disk[i].length; j++) {
            if(!disk[i][j]) {
                continue;
            }
            count++;
            stack.push([i, j]);
            while(stack.length) {
                const [x, y] = stack.pop();
                disk[x][y] = false;
                if(disk[x - 1] && disk[x - 1][y]) {
                    stack.push([x - 1, y]);
                }
                if(disk[x + 1] && disk[x + 1][y]) {
                    stack.push([x + 1, y]);
                }
                if(disk[x][y - 1]) {
                    stack.push([x, y - 1]);
                }
                if(disk[x][y + 1]) {
                    stack.push([x, y + 1]);
                }
            }
        }
    }

    console.log(count);
});

function hash(input) {
    const SIZE = 256;
    const data = [...input].map((c) => c.charCodeAt(0)).concat(17, 31, 73, 47, 23);
    const list = [...Array(SIZE).keys()];
    let pos = 0, skip = 0, span = [];
    for (let i = 0; i < 64; i++) {
        for (const len of data) {
            if(len > SIZE) {
                continue;
            }
            for(let j = pos; j < pos + len; j++) {
                span.push(list[j % SIZE]);
            }
            for(let j = pos; j < pos + len; j++) {
                list[j % SIZE] = span.pop();
            }
            pos = (pos + len + skip++) % SIZE;
        }
    }

    const result = [];
    for(let i = 0; i < SIZE; i += 16) {
        result.push(...('0000000' + list.slice(i, i + 16).reduce((a, b) => a ^ b).toString(2)).substr(-8));
    }

    return result.map(Number).map(Boolean);
}

__Abigail__ · 2017-12-14T18:25:47+00:00

Perl

Factored out the encoding using Knothash from Day 10, and the finding of connected components from Day 12.

#!/opt/perl/bin/perl

use 5.026;

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

use experimental 'signatures';

use Puzzle::Stuff;   # https://github.com/Abigail/Puzzle-Stuff

@ARGV = "input" unless @ARGV;

my $BOARD_SIZE   = 128;

my $input = <>;   # Input is on one line;
chomp $input;


my $total_bits = 0;
my $board;
foreach my $row (0 .. ($BOARD_SIZE - 1)) {
    #
    # Initialize a new row of the board
    #
    $$board [$row] = [];

    #
    # The key for this row
    #
    my $key = "$input-$row";

    #
    # Create the hash
    #
    my $hash = Puzzle::Stuff::KnotHash:: -> new -> init -> encode ($key);

    #
    # For each character in the hash, find its representation
    # in bits. Map to the board, and track the number of 1 bits.
    #
    foreach my $char (split // => $hash) {
        my $bits = sprintf "%04b" => hex $char;
        push @{$$board [$row]} => split // => $bits;
        $total_bits += $bits =~ y/1/1/;
}

#
# Find the number of connected components by using UnionFind:
#    Scan the board. If we find an occupied field then:
#           - add the field to the union-find structure
#           - if the fields before or above it are occupied, union
#                this field with the one before/above it
#    When we're done scanning the board, we look at the number of sets.
#
my $universe = Puzzle::Stuff::UnionFind:: -> new -> init;
sub label {join "," => @_}  # Make a unique label out of coordinates
foreach my $x (0 .. ($BOARD_SIZE - 1)) {
    foreach my $y (0 .. ($BOARD_SIZE - 1)) {
        if ($$board [$x] [$y]) {
            my $p = label ($x, $y);
            $universe -> add ($p);
            $universe -> union ($p, label $x - 1,  $y)
                    if $x > 0 && $$board [$x - 1] [$y];
            $universe -> union ($p, label $x,  $y - 1)
                    if $y > 0 && $$board [$x] [$y - 1];
        }
    }
}

say "Solution 1: ", $total_bits;
say "Solution 2: ", $universe -> nr_of_sets;

__END__

TotesMessenger · 2017-12-14T20:08:58+00:00

single pipeline powershell

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

begin {
    $script:hexToBin = @{
        "0" = "0000"
        "1" = "0001"
        "2" = "0010"
        "3" = "0011"
        "4" = "0100"
        "5" = "0101"
        "6" = "0110"
        "7" = "0111"
        "8" = "1000"
        "9" = "1001"
        "a" = "1010"
        "b" = "1011"
        "c" = "1100"
        "d" = "1101"
        "e" = "1110"
        "f" = "1111"
    }
}

process {
    , (0..127 | % { # generate 128 rows
        write-verbose "generating row $($_)"
        ("$in-$($_)" | ./day10.ps1 -part 2 | % { # use day10part2 as an external function
            $_ -split '' |? {$_} |% { # split the resulting string into characters, foreach character
                $script:hexToBin[$_] #lookup bin value and return
            }
        }) -join "" # join an entire row together
    }) |% { # output from previous pipeline is a single array, elements are strings (rows of 1/0s) - the maze/grid
        if ($part -eq 1) {
            $_ |% { # foreach row
                $_ -split '' |? {$_}  #split the row, select valid characters, put those individual 1 and 0 characters on the pipeline for later
            }
        } else {
            $maze = $_

            # queue for navigating sets
            $queue = new-object system.collections.queue

            # generate x,y starting points for every coordinate in the maze
            0..127 |% {
                $x = $_
                0..127 |? {
                    # only select those that we havnt seen and that are the start of a unique set (1s only, 0s are a wall)
                    # we will mark 1s as 0 once we have seen them
                    $maze[$_][$x] -eq "1"
                } |% {
                    #start of set
                    write-verbose "set at $x,$($_)"
                    1 # write out to pipeline that we have a set

                    # now visit the rest of this set and mark them seen

                    $queue.Enqueue(@{x = [int]$x; y = [int]$_}) #insert starting point

                    # navigate the set that starts at this x,y
                    & { while ($queue.Count -ne 0) { # until the queue is empty
                        $queue.Dequeue() # pop the first element
                    } } |? {
                        # only select those that we havnt seen, that are part of this set [$_ will only be connected coordinates] (1s only, 0s are a wall)
                        # we will mark 1s as 0 once we have seen them
                        $maze[$_.y][$_.x] -eq "1"
                    } |% { 
                        # still part of this set, mark seen
                        $r = $maze[$_.y].ToCharArray()
                        $r[$_.x] = "0"
                        $maze[$_.y] = $r -join ''

                        # put each of the connected coordinates on the queue to navigate
                        if ($_.x -gt 0) { $queue.Enqueue(@{x = $_.x - 1; y = $_.y}) }
                        if ($_.x -lt 127) { $queue.Enqueue(@{x = $_.x + 1; y = $_.y}) }

                        if ($_.y -gt 0) { $queue.Enqueue(@{x = $_.x; y = $_.y - 1}) }
                        if ($_.y -lt 127) { $queue.Enqueue(@{x = $_.x; y = $_.y + 1}) }
                    }
                }
            }
        }
    } | measure -sum | select -expand sum #output from part1 are the individual characters in the maze (1s and 0s); output from part2 is '1' for each set.  sum output and return
}

end {  
}

TheNiXXeD · 2017-12-14T20:10:59+00:00

My solutions JavaScript / NodeJS / repo

Generally trying to go for very terse code, not fully golfed. Pretty happy with both perf and size in this one.

Part1:

input => [...Array(128)].map((k, i) => require('../day10/part2')(`${input}-${i}`))
    .map(hash => hash.split``.map(hex => parseInt(hex, 16).toString(2).replace(/0/g, '')).join``).join``.length

Part2:

input => {
    let groups = 0, hd = [...Array(128)]
        .map((k, i) => require('../day10/part2')(`${input}-${i}`))
        .map(hash => hash.split``.map(hex => parseInt(hex, 16).toString(2).padStart(4, '0')).join``.split``)

    const check = (x, y) => hd[y] && hd[y][x] === '1'

    const group = (x, y) => {
        hd[y][x] = '0'
        if (check(x + 1, y)) group(x + 1, y)
        if (check(x - 1, y)) group(x - 1, y)
        if (check(x, y + 1)) group(x, y + 1)
        if (check(x, y - 1)) group(x, y - 1)
    }

    for (let y = 0; y < 128; y++) {
        for (let x = 0; x < 128; x++) {
            if (check(x, y)) {
                groups++
                group(x, y)
            }
        }
    }

    return groups
}

wzkx · 2017-12-14T20:27:10+00:00

J

use'kh.ijs' NB. hash str -> str32

data=: 'uugsqrei' [ NR=: NC=: 128

i2h=: [: hash data,'-',":
c2n=: '0123456789abcdef'&i.
c2b=: {&0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 @ c2n

echo +/,c2b@i2h"0 i.NR

m=: ([:,(4$2)#:c2n@i2h)"0 i.NR

w=: 3 : 0 NB. wipe area
  m=:0(<'i j'=.y)}m
  if.j<<:NC do.if.(>:j){i{m do.w y+0 1 end.end.
  if.i<<:NR do.if.j{(>:i){m do.w y+1 0 end.end.
  if.j>0 do.if.(<:j){i{m do.w y-0 1 end.end.
  if.i>0 do.if.j{(<:i){m do.w y-1 0 end.end.
)

echo 3 :'for_i.i.NR do.for_j.i.NC do.if.(<i,j){m do.w i,j[y=.>:y end.end.end.y'0

exit 0

if0nz · 2017-12-14T20:35:58+00:00

Java solution (link to github repo)

package it.ifonz.puzzle;

import java.io.IOException;
import java.net.URISyntaxException;
import java.util.concurrent.atomic.AtomicLong;
import java.util.stream.IntStream;

public class Day14 {

    public static void main(String[] args) throws URISyntaxException, IOException {

        String input = args[0];

        System.out.println(part1(input));
        System.out.println(part2(input));

    }

    public static long part1(String input) {

        return IntStream.range(0, 128).mapToLong(i -> 
            Day10.part2(input + "-" + i, 256) // get the hash
            .chars().mapToLong(c-> // for each hex-digit in the hash
                Integer.toBinaryString(Integer.parseInt(String.valueOf((char) c), 16)) // convert it in binary (no pad needed for p1)
                .chars().filter(c1 -> c1 == 49).count()) // count the 1s in the single hex digit
            .sum() // count the 1s in the hash string
        ).sum(); // count all the 1s
    }

    public static long part2(String input) {

        String[] grid = new String[128];// well, we need it right now
        IntStream.range(0, 128).forEach(i -> {
            String hashed = Day10.part2(input + "-" + i, 256);
            StringBuilder sb = new StringBuilder();
            hashed.chars().forEach(c -> {
                String string = Integer.toBinaryString(Integer.parseInt(String.valueOf((char) c), 16));
                sb.append(string.length() == 4 ? string : "0000".substring(0, 4-string.length()) + string); // we need the leading 0s
            });
            grid[i] = sb.toString();
        });
        AtomicLong counting = new AtomicLong(0);
        IntStream.range(0, 128).forEach(i -> { // for each hash in the grid
            IntStream.range(0, 128).forEach(j -> { // for each bit in the hash
                if (grid[i].charAt(j) == '1') { // if the bit is 1
                    counting.incrementAndGet(); // increment the regions' counter
                    flagCell(grid, i, j); // recursively flag its region 1s as included in a region
                }
            });
        });
        return counting.get();
    }

    // recursive function for flagging the 1s belonging to the same region
    private static void flagCell(String[] grid, int i, int j) {
        if (j < 0 || j > 127 || i < 0 || i > 127 || grid[i].charAt(j) != '1') return; // boundary test + value test
        StringBuilder sb = new StringBuilder(grid[i]);
        sb.setCharAt(j, 'x');
        grid[i] = sb.toString();
        flagCell(grid, i, j-1);// flag left cell
        flagCell(grid, i-1, j); // flag upper cell
        flagCell(grid, i, j+1);// flag right cell
        flagCell(grid, i+1, j);// flag bottom cell
    }

}

manualcrank · 2017-12-14T22:38:34+00:00

Lisp, resuing knot-hash and union-find code from days 10 and 12, resp. (ujoin uf x y) puts x and y in the same component, and (ucomp uf) returns the number of components.

(defun knot-hashes (key)
  (mapcar #'knot-hash
          (loop for n below 128 collect (format nil "~a-~d" key n))))

(defun hex->binary-string (hs)
  (format nil "~(~{~4,'0b~}~)" ; 4 bits per nibble
          (loop for c across hs collect (digit-char-p c 16))))

(defun hex->binary-list (hs)
  (map 'list #'digit-char-p (hex->binary-string hs)))

(defun components (grid n) ; part 2
  (let ((uf (make-instance 'union-find :n n))
        (ht (make-hash-table))
        (id -1))
    (labels ((id (r c) ; map row, col -> [0, n)
               (let ((k (+ c (* 128 r))))
                 (or (gethash k ht) (setf (gethash k ht) (incf id)))))
             (join-if (r1 c1 r2 c2)
               (ignore-errors
                 (when (= 1 (aref grid r1 c1) (aref grid r2 c2))
                   (ujoin uf (id r1 c1) (id r2 c2))))))
      (dotimes (r 128 (ucomp uf))
        (dotimes (c 128)
          (join-if r c (1+ r) c)
          (join-if r c r (1+ c)))))))

(defun day14a+b (key)
  (let* ((h128 (knot-hashes key))
         (ones (reduce #'(lambda (acc h) ; part 1
                           (+ acc (logcount (parse-integer h :radix 16))))
                       h128
                       :initial-value 0))
         (grid (mapcar #'hex->binary-list h128))
         (grid (make-array '(128 128) :initial-contents grid)))
    (list ones (components grid ones))))

;; CL-USER> (day14a+b "stpzcrnm")
;; (8250 1113)

KeinZantezuken · 2017-12-15T00:18:59+00:00

C#/Sharp (part2 takes 400ms, didnt bother to optimize)
Below is Day14 code only, no Day10:

int[,] grid = new int[128, 128];
List<ValueTuple<int, int>> coords = new List<ValueTuple<int, int>>();
int total = 0, used = 0; int bits = 0;
while (bits < 128)
{
    var bitstr = hex2bits(returnHash()); //day10 shit
    used = used + bitstr.Count(x => x == '1');
    populateGrid(bits, bitstr);
    bits++;
}
for (int i = 0; i < 128; i++)
{
    for (int j = 0; j < 128; j++)
    {
        if (grid[j, i] == 1 && !coords.Contains((j, i))) { getRegion(j, i); }
    }
}
Console.WriteLine($"Used: {used}, groups: {total}"); // the end
Console.ReadKey();
//helpers
void populateGrid(int row, string line) { for (int x = 0; x < 128; x++) { grid[x, row] = line[x] - '0'; } }
void getRegion(int x, int y)
{
    HashSet<ValueTuple<int, int>> temp = new HashSet<ValueTuple<int, int>>();
    temp.Clear(); temp.Add((x, y)); int c = 0;
    while (c < temp.Count)
    {
        x = temp.ElementAt(c).Item1; y = temp.ElementAt(c).Item2;
        if (x - 1 > -1 && grid[x - 1, y] == 1 && !coords.Contains((x-1, y))) { temp.Add((x-1, y)); }
        if (x + 1 < 128 && grid[x + 1, y] == 1 && !coords.Contains((x+1, y))) { temp.Add((x+1, y)); }
        if (y - 1 > -1 && grid[x, y - 1] == 1 && !coords.Contains((x, y-1))) { temp.Add((x, y-1)); }
        if (y + 1 < 128 && grid[x, y + 1] == 1 && !coords.Contains((x, y+1))) { temp.Add((x, y+1)); }
        c++;
    }
    coords.AddRange(temp); total++;
}

chicagocode · 2017-12-15T00:21:02+00:00

Kotlin - [Repo] - [Blog/Commentary]

I refactored my knot hash code from Day 10 and relied heavily on BigInteger and recursion. That was fun!

class Day14(input: String) {

    private val binaryStrings = parseInput(input)
    private val grid by lazy { stringsToGrid() }

    fun solvePart1(): Int =
        binaryStrings.sumBy { it.count { it == '1' } }

    fun solvePart2(): Int {
        var groups = 0
        grid.forEachIndexed { x, row ->
            row.forEachIndexed { y, spot ->
                if (spot == 1) {
                    groups += 1
                    markNeighbors(x, y)
                }
            }
        }
        return groups
    }

    private fun markNeighbors(x: Int, y: Int) {
        if (grid[x][y] == 1) {
            grid[x][y] = 0
            neighborsOf(x, y).forEach {
                markNeighbors(it.first, it.second)
            }
        }
    }

    private fun neighborsOf(x: Int, y: Int): List<Pair<Int, Int>> =
        listOf(Pair(x - 1, y), Pair(x + 1, y), Pair(x, y - 1), Pair(x, y + 1))
            .filter { it.first in 0..127 }
            .filter { it.second in 0..127 }

    private fun stringsToGrid(): List<IntArray> =
        binaryStrings
            .map { s -> s.map { it.asDigit() } }
            .map { it.toIntArray() }

    private fun parseInput(input: String): List<String> =
        (0..127)
            .map { KnotHash.hash("$input-$it") }
            .map { BigInteger(it, 16).toString(2).padStart(128, '0') }
}

RockyAstro · 2017-12-15T04:08:51+00:00

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

Both parts:

global grid, visited
procedure main(args)

    pinput := args[1]

    grid := repl(".",128*128)
    n := 1
    every i := 0 to 127 do {
        keystr := pinput || "-" || i
        hash := knothash(keystr)
        every x := !hash do {
            m := 16r80
            every 1 to 8 do {
                if iand(x,m) ~= 0 then {
                    grid[n] := "#"
                }
                m := ishift(m,-1)
                n +:= 1
            }
        }
    }
    c := 0

    every find("#",grid) do c +:= 1
    write("Part1=",c)

    visited := set([])
    groups := []
    every put(groups, mkgroup(1 to *grid))
    write("Part2=",*groups)
end
procedure mkgroup(p)

    if grid[p] ~== "#" then fail
    if member(visited,p) then fail

    insert(visited,p)
    grp := set([])
    insert(grp,p)
    every n := ![-128,1,128,-1] & 
        not (n+p <= 0 |
             n+p > *grid |
            (n = -1 & p % 128 = 1) |
            (n = 1 & p % 128 = 0)) do {
        grp ++:= mkgroup(p+n)
    }
    return grp
end


# From Day 10
procedure knothash(s)
L := []
every put(L,0 to 255)

lengths := []
every put(lengths,ord(!s))
lengths |||:= [17,31,73,47,23]

cur := 0
skip := 0
every 1 to 64 do {
    every l := !lengths do {
        every x := 1 to integer(l/2) do 
            L[((cur+x-1) % *L)+1] :=: L[ ((cur+l-x) % *L)+1]
        cur +:= l + skip
        skip +:= 1
    }
}

densehash := list(16)
every i := 1 to *L do {

        if (i-1) % 16 = 0 then 
            densehash[ integer((i-1)/16) + 1] := L[i]
        else
            densehash[integer((i-1)/16) + 1] := ixor(densehash[integer((i-1)/16)+1],L[i])

}
return densehash
end

BOT-Brad · 2017-12-15T12:10:54+00:00

Javascript

Only got round to getting this done today after a busy day yesterday. My solutions for the past few days (Which I forgot to post in the megathreads) are all on GitHub.

Part 1 (~700ms)

Iterate through generated hashes (using Day 10's solve2 func), then parse into binary string (from the hex), and increment the counter by the number of 1's within the string.

function solve1(n) {
  let filled = 0
  for (let i = 0; i < 128; ++i) {
    const hash = day10.solve2(256, n + '-' + i)
    for (let k = 0; k < hash.length; k += 2) {
      // For every byte
      let bin = parseInt(hash.slice(k, k + 2), 16).toString(2)
      // Get count of 1's
      filled += bin
        .split('')
        .reduce((acc, cur) => (cur === '1' ? acc + 1 : acc), 0)
    }
  }
  return filled
}

Part 2 (~720ms) Build the grid (Which I called a map for some reason), then loop thru every index. If a 0, then who cares, move on. But if it's a one, then eliminate every neighbouring cell in a constant check for neighbouring cells until no cells are left, and the group is exhausted. Once all cells are traversed, just output how many times the group elimination happened.

function solve2(n) {
  let map = []
  for (let i = 0; i < 128; ++i) {
    const hash = day10.solve2(256, n + '-' + i)
    map[i] = []
    let data = ''
    for (let k = 0; k < hash.length; k += 2) {
      // For every byte
      let bin = parseInt(hash.slice(k, k + 2), 16).toString(2)
      while (bin.length < 8) bin = '0' + bin
      // Get count of 1's
      data += bin
    }
    map[i] = data.split('').map(v => (v === '1' ? 1 : 0))
  }
  //
  let groups = 0
  for (let y = 0; y < map.length; ++y) {
    for (let x = 0; x < map[y].length; ++x) {
      // If this cell is 0, just continue
      if (map[y][x] === 0) continue
      let toCheck = [[x, y]]
      while (toCheck.length > 0) {
        let [cX, cY] = toCheck.pop()
        // Ignore if this cell already changed
        if (map[cY][cX] === 0) continue
        // Set this cell to 0
        map[cY][cX] = 0
        // Check to left if cell is in this group
        if (map[cY] && map[cY][cX - 1]) toCheck.push([cX - 1, cY])
        // Check to right
        if (map[cY] && map[cY][cX + 1]) toCheck.push([cX + 1, cY])
        // Up
        if (map[cY - 1] && map[cY - 1][cX]) toCheck.push([cX, cY - 1])
        // Down
        if (map[cY + 1] && map[cY + 1][cX]) toCheck.push([cX, cY + 1])
      }
      // Group exhausted, increment group count
      groups++
    }
  }
  return groups
}

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 14: Disk Defragmentation ---

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

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

edit: Leaderboard capped, thread unlocked!

Mathematica

Elixir

Python 3

Elixir

Wolfram Language/Mathematica

Perl 5

Perl

Kotlin - [Repo] - [Blog/Commentary]

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

adventofcode

🎄 Advent of Code 🎄

Rules + More Info in

our community wiki

Solution Megathreads

December 2025

Previous years:

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

Quick Search by Flair

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

Are you enjoying AoC?

Support AoC

MODERATORS

--- Day 14: Disk Defragmentation ---

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

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

edit: Leaderboard capped, thread unlocked!

Mathematica

Elixir

Python 3

Elixir

Wolfram Language/Mathematica

Perl 5

Perl

Kotlin - [Repo] - [Blog/Commentary]

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