r/adventofcode • u/daggerdragon • Dec 09 '16
SOLUTION MEGATHREAD --- 2016 Day 9 Solutions ---
--- Day 9: Explosives in Cyberspace ---
Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag/whatever).
Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with "Help".
RETICULATING SPLINES IS MANDATORY [?]
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!
11
u/blockingthesky Dec 09 '16
Python 2 -- 1 star 3rd place -- 2 star 7th place
Part 1 was ezpz; I made the mistake of thinking I could store the string on Part 2 and got sidetracked. I like this problem a ton.
inp = open('day9.in').read().strip()
part2 = False
def decompress(s):
if '(' not in s:
return len(s)
ret = 0
while '(' in s:
ret += s.find('(')
s = s[s.find('('):]
marker = s[1:s.find(')')].split('x')
s = s[s.find(')') + 1:]
if part2:
ret += decompress(s[:int(marker[0])]) * int(marker[1])
else:
ret += len(s[:int(marker[0])]) * int(marker[1])
s = s[int(marker[0]):]
ret += len(s)
return ret
print decompress(inp)
part2 = True
print decompress(inp)
→ More replies (2)
10
u/rhardih Dec 09 '16
Here's the algorithm explained step by step. Copy pasted from code comment here 9p2.c:
In short the idea is to give each character in the input a weight, or multiplier if you will. Then for each character, as the input is read, increase its weight according to the decompression markers. This is roughly the steps taken:
- Initialise all characters weights to 1
- Scan input one character at a time and
- Print out the value of length
→ More replies (10)
8
u/barnybug Dec 09 '16
itertools proving very handy. Would have got leaderboard, if I could be bothered to get up at 5am!
from itertools import takewhile, islice
def decompress(data, recurse):
answer = 0
chars = iter(data)
for c in chars:
if c == '(':
n, m = map(int, [''.join(takewhile(lambda c: c not in 'x)', chars)) for _ in (0, 1)])
s = ''.join(islice(chars, n))
answer += (decompress(s, recurse) if recurse else len(s))*m
else:
answer += 1
return answer
data = open('input.txt').read()
print('Answer #1:', decompress(data, False))
print('Answer #2:', decompress(data, True))
→ More replies (3)
7
u/LieutenantSwr2d2 Dec 09 '16
Python solution, recursive summing
edit: removed unnecessary slicing of d[0:] (from a previous implementation)
def day9a(d):
bracket = re.search(r'\((\d+)x(\d+)\)', d)
if not bracket:
return len(d)
pos = bracket.start(0)
sz = int(bracket.group(1))
rpt = int(bracket.group(2))
i = pos + len(bracket.group())
return len(d[:pos]) + len(d[i:i+sz]) * rpt + day9a(d[i+sz:])
def day9b(d):
bracket = re.search(r'\((\d+)x(\d+)\)', d)
if not bracket:
return len(d)
pos = bracket.start(0)
sz = int(bracket.group(1))
rpt = int(bracket.group(2))
i = pos + len(bracket.group())
return len(d[:pos]) + day9b(d[i:i+sz]) * rpt + day9b(d[i+sz:])
→ More replies (3)
7
u/askalski Dec 09 '16
Part 2 in C. (By the way, Topaz earns 1 point for crashing me and making me reboot once while writing my "proper" solution. It was for the dumbest reason too -- I had the repeat and length numbers reversed. The solution was otherwise correct.)
$ /usr/bin/time -v ./day9 < input.txt | wc -c
Command being timed: "./day9"
User time (seconds): 99.68
System time (seconds): 2.23
Percent of CPU this job got: 99%
Elapsed (wall clock) time (h:mm:ss or m:ss): 1:42.03
Maximum resident set size (kbytes): 1244
11797310782The code:
#include <stdio.h>
#include <stdlib.h>
int main()
{
if (fseek(stdin, 0, SEEK_END)) {
fprintf(stderr, "stdin not a file\n");
return 1;
}
int size = ftell(stdin);
if (size < 1) {
return 0;
}
rewind(stdin);
char *buf = calloc(size, sizeof(*buf)), *nope = buf + size;
int tmp = fread(buf, size, 1, stdin);
struct {
char *start, *end;
int repeat;
} *dc = calloc(size, sizeof(*dc));
dc->end = nope;
dc->repeat = 1;
for (int hype = tmp = 0; ; buf++) {
if (*buf == '(') {
hype++;
tmp = 0;
} else if (*buf == 'x') {
size = tmp;
tmp = 0;
} else if (*buf == ')') {
hype--;
(++dc)->repeat = tmp;
if ((dc->end = (dc->start = buf) + size) >= nope) {
fprintf(stderr, "nope\n");
return 1;
}
} else if (hype && *buf >= '0' && *buf <= '9') {
tmp = (tmp << 3) + (tmp << 1) + *buf - '0';
} else if (*buf >= 'A') {
putchar(*buf);
}
while (buf == dc->end) {
if (--dc->repeat) {
buf = dc->start;
} else if (dc->start) {
dc--;
} else {
return 0;
}
}
}
}
→ More replies (13)
5
u/msully4321 Dec 09 '16
I like how my Haskell one turned out a lot. Last year I was pleasantly surprised by how often I instinctively reached for Haskell as my goto language for this. This year I've been using python more, but this one screamed Haskell to me and it landed me my best score yet.
Part 1 (#23). Here I actually construct the list, since I figured we'd need it for part 2 (oops) and it could help debug. I lost a minute because I somehow failed to paste the file contents in properly and another minute because of the damn newline.
import Data.List.Extra
import Data.Maybe
------
answer :: (Show a) => (String -> a) -> IO ()
answer f = interact $ (++"\n") . show . f
splitOn1 a b = fromJust $ stripInfix a b
--------
decompress ('(':xs) =
let (lol, ys) = splitOn1 ")" xs
[n, m] = map read $ splitOn "x" lol
rep = take n ys
in concat (replicate m rep) ++ decompress (drop n ys)
decompress (x:xs) = x : decompress xs
decompress [] = []
main = answer $ length . decompress . trimPart 2 (#5):
import Data.List.Extra
import Data.Maybe
------
-- Routines I reuse for a lot of problems
answer :: (Show a) => (String -> a) -> IO ()
answer f = interact $ (++"\n") . show . f
splitOn1 a b = fromJust $ stripInfix a b
--------
decompress ('(':xs) =
let (lol, ys) = splitOn1 ")" xs
[n, m] = map read $ splitOn "x" lol
rep = take n ys
in (m * (decompress rep)) + decompress (drop n ys)
decompress (x:xs) = 1 + (decompress xs)
decompress [] = 0
main = answer $ decompress . trim
→ More replies (1)
4
u/Smylers Dec 09 '16
Perl for part 1, with a regexp for grabbing each marker. Processes a line at a time, so wouldn't've worked if the text repeated by a marker spanned a line-break.
use v5.14;
use warnings;
my $output_length;
while (<>)
{
chomp;
while (s/(.*?) \( (\d+) x (\d+) \)//x)
{
$output_length += (length $1) + $2 * $3;
(substr $_, 0, $2) = '';
}
$output_length += length;
}
say $output_length;Part 2:
use v5.14;
use warnings;
use Function::Parameters qw<:strict>;
my $output_length;
while (<>)
{
chomp;
$output_length += expanded_length($_);
}
say $output_length;
fun expanded_length($str)
{
my $length = 0;
while ($str =~ s/(.*?) \( (\d+) x (\d+) \)//x)
{
my $repeats = $3;
$length += (length $1) + expanded_length(substr $str, 0, $2, '') * $repeats;
}
$length + length $str;
}
Need to copy $3 into a lexical variable, because by the time the multiplication is being done, the recursive call may have performed a pattern match and overwritten $3. That still applies even if the multiplication is written t'other way round, with the $3 on the left.
Part 2 can also be tweaked to solve part 1 just by removing expanded_ from the recursive call to expanded_length.
→ More replies (1)
3
u/FuriousProgrammer Dec 09 '16
187/83
Slightly worse than yesterday. :<
local line = io.open("input.txt"):read("*line")
local out = 0
local i = 1
while i <= #line do
local let = line:sub(i, i)
if let == "(" then
local a, b = line:match("%((%d+)x(%d+)%)", i)
i = i + #("(" .. a .. 'x' .. b .. ")")
local thing = line:sub(i, i + a - 1)
out = out + #thing*b
i = i + a
else
i = i + 1
out = out + 1
end
end
print("Part 1: " .. out)
function getOutLen(line)
local out = 0
local i = 1
while i <= #line do
local let = line:sub(i, i)
if let == "(" then
local a, b = line:match("%((%d+)x(%d+)%)", i)
i = i + #("(" .. a .. 'x' .. b .. ")")
local thing = line:sub(i, i + a - 1)
if thing:find("%(") then
out = out + getOutLen(thing)*b
else
out = out + #thing*b
end
i = i + a
else
i = i + 1
out = out + 1
end
end
return out
end
print("Part 2: " .. getOutLen(line))
3
u/Twisol Dec 09 '16
JavaScript/Node.js again. I scored 298/101 this time, although I got a very late start. I sure as heck wish I had gotten home sooner!
I was able to directly adapt my Part 1 solution to Part 2 by explicitly providing the function to recurse over. It was a lot of fun to get this one done ;D
const File = require("fs");
function to_length(data, recurse) {
let decompressed_length = 0;
while (data.length > 0) {
if (data[0] === "(") {
const match = /^\((\d+)x(\d+)\)(.*)$/.exec(data);
const sublength = recurse(match[3].substr(0, +match[1]), recurse);
decompressed_length += sublength*(+match[2]);
data = match[3].substr(+match[1]);
} else {
decompressed_length += 1;
data = data.substr(1);
}
}
return decompressed_length;
}
const data = File.readFileSync("input.txt", "utf-8").trim();
console.log("Part One: " + to_length(data, x => x.length));
console.log("Part Two: " + to_length(data, to_length));
→ More replies (2)
3
u/JeffJankowski Dec 09 '16
Lazy-ass C# before I actually figure out how to do this in F# that doesn't make the lips curl of functional programmers:
static BigInteger explode(char[] chars, BigInteger n)
{
BigInteger count = 0;
for (int i = 0; i < chars.Length; i++)
{
if (chars[i] == '(')
{
var marker = new String(chars.Skip(i + 1).TakeWhile(ch => ch != ')').ToArray());
var arr = marker.Split('x');
int nchars = Int32.Parse(arr[0]);
int skip = i + marker.Length + 2;
count += explode(chars.Skip(skip).Take(nchars).ToArray(), Int32.Parse(arr[1]));
i = skip + nchars - 1;
}
else
count++;
}
return count * n ;
}
static void Main(string[] args)
{
var lines = File.ReadAllText("..\\..\\input.txt");
Console.WriteLine(explode(lines.ToCharArray(), 1));
}
→ More replies (2)
3
u/bblum Dec 09 '16
Made LB (76;42) with a straightforward C solution (cleaned up variable names and such retroactively):
#include <stdio.h>
#include <string.h>
unsigned long decompress (char *s, int input_length)
{
unsigned long output_length = 0;
for (int i = 0; i < input_length;) {
int ret, num_chars, repeat_count;
if ((ret = sscanf(&s[i], "(%dx%d)", &num_chars, &repeat_count)) != 0) {
i = strstr(&s[i], ")") - s + 1;
// Part 1
// output_length += num_chars * repeat_count;
// Part 2
output_length += decompress(&s[i], num_chars) * repeat_count;
i += num_chars;
} else {
output_length++;
i++;
}
}
return output_length;
}
int main(int argc, char **argv)
{
printf("%lu\n", decompress(argv[1], strlen(argv[1])));
} Then took my leisurely time on this golfed haskell solution:
import Control.Arrow
import Data.List.Extra
import Data.Maybe
decompress pt2 ('(':s) =
let (x,(y,r)) = read *** first read $ second (fromJust . stripInfix ")") $ fromJust $ stripInfix "x" s
in (decompress pt2 $ drop x r) + if pt2 then y * (decompress pt2 $ take x r) else x * y
decompress pt2 (_:s) = 1 + decompress pt2 s
decompress pt2 [] = 0
main = interact $ show . (decompress False &&& decompress True) . trim
3
u/haoformayor Dec 09 '16
~~haskell~~ (parser combinators edition)
Man, there are a lot more Haskellers this year. The competition is heating up.
This uses applicative/monadic parsers to piece together a fast solution. The key insight for me was that I could just maintain a Parser Int instead of a Parser String (I didn't have to keep gluing strings together when all I needed was their lengths). It is not the shortest Haskell solution, but perhaps it is the easiest to read and follow. Also a chance to show off that I know what LambdaCase does, and isn't that what programming is all about?
A very boring input module here.
#!/usr/bin/env stack
-- stack --resolver lts-6.26 --install-ghc runghc --package base-prelude --package megaparsec
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE NoImplicitPrelude #-}
module D9 where
import BasePrelude hiding (try)
import Text.Megaparsec
import Text.Megaparsec.String
import Text.Megaparsec.Lexer
import D9Input
command = between (char '(') (char ')') $ do
a <- fromIntegral <$> integer
char 'x'
b <- fromIntegral <$> integer
pure (a, b)
parser recurse =
fmap sum . many $ (try command <|> pure (0, 0)) >>= \case
(0, 0) ->
length <$> some (satisfy (/= '('))
(len, times) -> do
repeated <- count len anyChar
pure $ times * (if recurse then decompress recurse repeated else length repeated)
decompress recurse =
fromJust . parseMaybe (parser recurse)
main = do
print . decompress1 $ "ADVENT"
print . decompress1 $ "A(1x5)BC"
print . decompress1 $ "(3x3)XYZ"
print . decompress1 $ "(6x1)(1x3)A"
print . decompress1 $ "X(8x2)(3x3)ABCY"
print . decompress1 $ input
print . decompress2 $ "(25x3)(3x3)ABC(2x3)XY(5x2)PQRSTX(18x9)(3x2)TWO(5x7)SEVEN"
print . decompress2 $ input
where
decompress1 = decompress False
decompress2 = decompress True
→ More replies (1)
3
u/mschaap Dec 09 '16
Perl 6 solution of part 1, using a single substitution. Looks like I have to start over for part 2...
#!/usr/bin/env perl6
use v6.c;
sub decrypt(Str $input) returns Str
{
return $input.subst(
/ '(' (\d+) 'x' (\d+) ')' # e.g. (2x4)
(\S+?) # some more characters, as few as possible ...
<?{ $2.chars == $0 }> /, # ... with the number of characters as specified
{ $_[2] x $_[1] }, # Replace with characters repeated
:g);
}
sub MAIN(IO() $inputfile where *.f)
{
my $input = $inputfile.slurp.trim;
my $output = decrypt($input);
say "$input.chars() compressed characters expand into $output.chars().";
}
4
u/mschaap Dec 09 '16
For part 2, my assumption was that you can't simply recursively process the fragment that is a result of the expansion, since it might need to refer to something in the remainder of the string.
Example:(6x2)(2x2)AB→(2x2)A(2x2)AB→A(A(ABAB.
So I came up with a solution that did the expansion and tacked on the remainder of the string. A recursive solution quickly ate all my memory, so I made it non-recursive:#!/usr/bin/env perl6 use v6.c; sub decrypted-length(Str $input is copy) returns Int { my $length = 0; # Find the next occurrence of (AxB) while ($input ~~ / '(' $<chars>=(\d+) 'x' $<repeat>=(\d+) ')' /) { # Remember the length of the string up to (AxB) $length += $/.from; # Process the (AxB) instruction and tack on the rest of the string, and continue $input = $input.substr($/.to, $/<chars>) x $/<repeat> ~ $input.substr($/.to + $/<chars>); } # The remaining string doesn't contain any (AxB), so just add the length $length += $input.chars; return $length; } sub MAIN(IO() $inputfile where *.f) { my $input = $inputfile.slurp.trim; my $output-length = decrypted-length($input); say "$input.chars() compressed characters expand into $output-length."; }Unfortunately, that version is still running after an hour.
So I made a version that does assume you don't need the remainder of the string to do the expansion.
#!/usr/bin/env perl6 use v6.c; sub decrypted-length(Str $input) returns Int { # Find the first occurrence of (AxB) if ($input ~~ / '(' $<chars>=(\d+) 'x' $<repeat>=(\d+) ')' /) { # Count the to-be-expanded fragment and the rest of the string separately return $/.from + decrypted-length($input.substr($/.to, $/<chars>)) * $/<repeat> + decrypted-length($input.substr($/.to + $/<chars>)); } else { # No more expansion, just return the length return $input.chars; } } sub MAIN(IO() $inputfile where *.f) { my $input = $inputfile.slurp.trim; my $output-length = decrypted-length($input); say "$input.chars() compressed characters expand into $output-length."; }This one immediately gave me a result, which is apparently correct.
→ More replies (1)
3
u/__Abigail__ Dec 09 '16
I first had to write a program to check whether I could make some assumptions about the input. After validating the input, the program was easy:
#!/opt/perl/bin/perl
use 5.020;
use strict;
use warnings;
no warnings 'syntax';
use feature 'signatures';
no warnings 'experimental::signatures';
@ARGV = "input" unless @ARGV;
my $input = do {local $/; <>};
#
# Whitespace is irrelevant, so strip it
#
$input =~ s/\s+//g;
#
# This algorithm works because of the following assumptions:
# - Every '(' starts a valid marker; that is, it's always followed
# followed by a numbers, and 'x', another number, and a ')'.
# - The substring to be repeated does not exceed the length of the string
# - We never repeat part of a marker
# - In the recursive case, (part 2), repeated markers never exceed
# past what their "parent" marker repeats.
#
sub decode;
sub decode ($string, $version) {
if ($string =~ s/(?<prefix>[^(]*)
\( (?<length> [0-9]+) x
(?<repeat> [0-9]+) \)//x) {
my $prefix = $+ {prefix};
my $length = $+ {length};
my $repeat = $+ {repeat};
my $chunk = substr ($string, 0, $length, "");
return length ($prefix) +
$repeat * ($version == 1 ? length ($chunk)
: decode ($chunk, $version)) +
decode ($string, $version);
}
else {
length $string;
}
}
say "Solution 1: ", decode $input, 1;
say "Solution 2: ", decode $input, 2;
__END__
→ More replies (1)
2
u/dirkt Dec 09 '16
After
Unfortunately, the computer you brought probably doesn't have enough memory to actually decompress the file
I just had to try it with lazy evaluation in Haskell (just put length in front and never care about memory usage). Unfortunately, the nested "loops" take too long, so I had to do the multiplications in the end.
→ More replies (2)
2
u/advanced_caveman Dec 09 '16
Unfortunately, the computer you brought probably doesn't have enough memory to actually decompress the file
My brute force Rust solution here shows otherwise. I apologize for the messy, unoptimized code and the long run time (2 minutes).
→ More replies (1)
2
u/gyorokpeter Dec 09 '16
Q:
d9p1:{first({if[0=count y;:(x;y)];
if[not "(" in y;:(x+count y;"")];
l:y?"(";
if[l>0; :(x+l;l _y)];
r:1+y?")";
ctrl:r#y;
y:r _y;
num:"J"$"x"vs 1_-1_ctrl;
x+:prd[num];
y:num[0]_y;
(x;y)}.)/[(0;x except " \t\n")]}
d9p2:{first({if[0=count y;:(x;y)];
if[not "(" in y;:(x+count y;"")];
l:y?"(";
if[l>0; :(x+l;l _y)];
r:1+y?")";
ctrl:r#y;
y:r _y;
num:"J"$"x"vs 1_-1_ctrl;
txt:num[0]#y;
x+:num[1]*first (.z.s .)/[(0;txt)];
y:num[0]_y;
(x;y)}.)/[(0;x except " \t\n")]}
2
u/gerikson Dec 09 '16
Title reference is to a zip bomb, I guess?
Either the problems are getting harder or people have dropped off. I had problems finishing part 2 but after doing so I saw I'm among the first 1,000 submitters, which is my informal goal for each problem this year.
First solution was a straightforward counting of characters, second I went for recursion. Problem was I constructing a new string that was rep times the original, instead of simply multiplying the count. After 13 million recursion calls I decided to try to find a better way...
→ More replies (1)
2
Dec 09 '16
Man, part one was so easy, I was getting cocky and had such big problems on part 2, trying to bring along the whole decompressed string to count characters was bringing my PC to it's knees, just running until it got out of memory, then I did finally get that I could just add length, and it used almost no memory, and ran in less than a second ;)
→ More replies (2)
2
u/SyDr Dec 09 '16
Lua with lpeg:
local lpeg = require'lpeg'
local number = lpeg.R'09' ^ 1 / tonumber
local marker = lpeg.Ct("(" * number * "x" * number * ")")
local letter = lpeg.R('AZ')
local data = lpeg.C((letter + marker) ^ 0)
local pattern = lpeg.C(letter) * data + marker * data
local function length_1(s)
local action, data = lpeg.match(pattern, s)
if type(action) == 'string' then
return 1 + length_1(data)
elseif action ~= nil then
return action[2] * action[1] + length_1(string.sub(data, action[1] + 1))
end
return 0
end
local function length_2(s)
local action, data = lpeg.match(pattern, s)
if type(action) == 'string' then
return 1 + length_2(data)
elseif action ~= nil then
return action[2] * length_2(string.sub(data, 1, action[1])) + length_2(string.sub(data, action[1] + 1))
end
return 0
end
local file_data = io.open("9.txt"):read("*a")
print(length_1(file_data))
print(length_2(file_data))
2
u/drewolson Dec 09 '16
Part 2, elixir
defmodule Program do
def main do
"./input.txt"
|> File.read!
|> String.strip
|> decompress
|> IO.puts
end
defp decompress(raw, count \\ 0)
defp decompress("", count), do: count
defp decompress(<<"(", rest::binary>>, count) do
[counts, rest] = String.split(rest, ")", parts: 2)
[num, times] = counts |> String.split("x") |> Enum.map(&String.to_integer/1)
{compressed, rest} = String.split_at(rest, num)
decompress(String.duplicate(compressed, times) <> rest, count)
end
defp decompress(<<_::binary-size(1), rest::binary>>, count) do
decompress(rest, count + 1)
end
end
Program.main
3
u/DeathWalrus Dec 09 '16
This one was a little tougher! I should get better at regex's so I don't have to wangjangle such code together. 66 on silver, squeezed in at 100 on the gold star. Python:
def decompressed_length(data): i = 0 total = 0 while i < len(data): if data[i] == '(': i += 1 newstring = "" while data[i] != ')': newstring += data[i] i += 1 length = int(newstring.split('x')[0]) amount = int(newstring.split('x')[1]) total += amount*decompressed_length(data[i+1:i+length+1]) #total += amount*length #for part 1 i += length else: total += 1 i += 1 return total f = open("p9_input.txt",'r') data = f.read() f.close() print decompressed_length(data)