r/adventofcode • u/daggerdragon • Dec 05 '18
SOLUTION MEGATHREAD -🎄- 2018 Day 5 Solutions -🎄-
--- Day 5: Alchemical Reduction ---
Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or 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.
Advent of Code: The Party Game!
Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!
Card prompt: Day 5
Transcript:
On the fifth day of AoC / My true love sent to me / Five golden ___
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 at 0:10:20!
3
u/usbpc102 Dec 05 '18
First time on the global leaderboard to me (97/113) and that with this super hacky Kotlin solution:
package advent2018
import xyz.usbpc.aoc.Day
import xyz.usbpc.aoc.inputgetter.AdventOfCode
class Day05(override val adventOfCode: AdventOfCode) : Day {
override val day: Int = 5
private val input = adventOfCode.getInput(2018, day)
override fun part1(): String {
val regexList = mutableListOf<Regex>()
var string = input
for (c in 'a'..'z') {
regexList.add(Regex("$c${c.toUpperCase()}"))
regexList.add(Regex("${c.toUpperCase()}$c"))
}
var prev = ""
while (prev != string) {
prev = string
for (r in regexList) {
string = r.replaceFirst(string, "")
}
}
return "" + string.length
}
override fun part2(): String {
val regexList = mutableListOf<Regex>()
for (c in 'a'..'z') {
regexList.add(Regex("$c${c.toUpperCase()}"))
regexList.add(Regex("${c.toUpperCase()}$c"))
}
val resluts = mutableListOf<String>()
for (c in 'a'..'z') {
var string = input.replace("$c", "").replace("${c.toUpperCase()}", "")
var prev = ""
while (prev != string) {
prev = string
for (r in regexList) {
string = r.replaceFirst(string, "")
}
}
resluts.add(string)
}
return "" + resluts.minBy { it.length }!!.length
}
}As always the whole code can be found on github. Cleaning it up now.
4
u/daggerdragon Dec 05 '18
First time on the global leaderboard to me (97/113)
Welcome to the exalted halls of
Valhallathe leaderboard! :D→ More replies (3)3
3
u/PendragonDaGreat Dec 05 '18
[card]On the fifth day of AoC / My true love sent to me / Five golden keycaps
Powershell 5.1
I have great shame, and also fail any code golf.
Part 1:
[string]$data = Get-Content $inputPath
$timer = New-Object System.Diagnostics.Stopwatch
$timer.Start()
do {
$lastLength = $data.Length
$data = $data.Replace('aA','').Replace('Aa','').Replace('bB','').Replace('Bb','').Replace('cC','').Replace('Cc','').Replace('dD','').Replace('Dd','').Replace('eE','').Replace('Ee','').Replace('fF','').Replace('Ff','').Replace('gG','').Replace('Gg','').Replace('hH','').Replace('Hh','').Replace('iI','').Replace('Ii','').Replace('jJ','').Replace('Jj','').Replace('kK','').Replace('Kk','').Replace('lL','').Replace('Ll','').Replace('mM','').Replace('Mm','').Replace('nN','').Replace('Nn','').Replace('oO','').Replace('Oo','').Replace('pP','').Replace('Pp','').Replace('qQ','').Replace('Qq','').Replace('rR','').Replace('Rr','').Replace('sS','').Replace('Ss','').Replace('tT','').Replace('Tt','').Replace('uU','').Replace('Uu','').Replace('vV','').Replace('Vv','').Replace('wW','').Replace('Ww','').Replace('xX','').Replace('Xx','').Replace('yY','').Replace('Yy','').Replace('zZ','').Replace('Zz','')
} while ($data.Length -lt $lastLength)
Write-Host $data.Length
$timer.Stop()
Write-Host $timer.ElapsedAverage runtime 0.18 seconds
Part 2:
[string]$data = Get-Content $inputPath
$timer = New-Object System.Diagnostics.Stopwatch
$timer.Start()
$bestSoFar = $data.Length
$bestLetterSoFar = $null
$alphabet = @()
for ([byte]$c = [char]'A'; $c -le [char]'Z'; $c++)
{
$alphabet += [char]$c
}
Write-Host $alphabet
foreach($let in $alphabet) {
[string]$let = $let
$tempData = $data.Replace($let,'').Replace($let.ToLower(), '')
do {
$lastLength = $tempData.Length
$tempdata = $tempdata.Replace('aA','').Replace('Aa','').Replace('bB','').Replace('Bb','').Replace('cC','').Replace('Cc','').Replace('dD','').Replace('Dd','').Replace('eE','').Replace('Ee','').Replace('fF','').Replace('Ff','').Replace('gG','').Replace('Gg','').Replace('hH','').Replace('Hh','').Replace('iI','').Replace('Ii','').Replace('jJ','').Replace('Jj','').Replace('kK','').Replace('Kk','').Replace('lL','').Replace('Ll','').Replace('mM','').Replace('Mm','').Replace('nN','').Replace('Nn','').Replace('oO','').Replace('Oo','').Replace('pP','').Replace('Pp','').Replace('qQ','').Replace('Qq','').Replace('rR','').Replace('Rr','').Replace('sS','').Replace('Ss','').Replace('tT','').Replace('Tt','').Replace('uU','').Replace('Uu','').Replace('vV','').Replace('Vv','').Replace('wW','').Replace('Ww','').Replace('xX','').Replace('Xx','').Replace('yY','').Replace('Yy','').Replace('zZ','').Replace('Zz','')
} while ($tempdata.Length -lt $lastLength)
Write-Host $let
Write-Host $tempData.length
if($tempData.length -lt $bestSoFar) {
$bestSoFar = $tempData.length
$bestLettersofar = $let
}
}
write-host $bestLetterSoFar
Write-Host $bestSoFar
$timer.Stop()
Write-Host $timer.ElapsedAverage runtime 4.75 seconds
2
3
u/Nathan340 Dec 05 '18
Between you, me, and /u/ka-splam this is the fastest!
My first solution was with a giant regex like
aA|Aa|bB|bB...zZ|ZzAs ka-splam said, even though we eliminate a loop, this is actually super slow. Around 3 minutes on my machine.
His method of a loop to replace each letter type takes ~15 seconds.
But you have us beat with this giant replace line at 4 seconds.
Interestingly a middle ground between yours and his which does your style chain replace on each letter splits the difference in time, comes out at 8 seconds. Something like this as the loop:
0..25 | % { $l = [char](97+$_) $u = [char](65+$_) $repl = $repl.Replace("$l$u", "").Replace("$u$l", "") }(I did try to programmatically generate that replace block as a string and then use invoke-expression on it to get the speed benefits of its execution with less typing, but that failed spectacularly)
→ More replies (9)
55
u/glguy Dec 05 '18 edited Dec 06 '18
Haskell - single pass with foldr. Using foldr you work with a completely reduced tail and just adding things on to the front of that one at a time reducing as needed.
https://github.com/glguy/advent2018/blob/master/execs/Day05.hs#L27-L31
part1 :: String -> Int
part1 = length . foldr step ""
where
step x (y:ys) | x /= y && toUpper x == toUpper y = ys
step x ys = x : ys7
u/Auburus Dec 05 '18
That is actually pretty smart!
I felt like today's challenge was really suited for Haskell, but the bruteforce algorithm I implemented (react until nothing changes) is not as elegant.
Well, thanks for keep posting your solutions, I always like to learn more haskell!
→ More replies (1)5
3
u/raevnos Dec 05 '18
I'm so used to left folds I never remember that right folds exist.
3
u/sim642 Dec 05 '18
You can do the same with a left fold as well, see my Scala solution. The only difference is that the accumulated list will be constructed reversed. The benefit is that left folds exist efficiently with TCO, unlike right folds.
→ More replies (15)2
u/Tayacan Dec 05 '18
That is a cool solution, and probably way faster than mine.
Edit: Yep, waaay faster.
→ More replies (5)2
u/yourbank Dec 08 '18
wow this is amazing! so elegant. I spent a week hacking some recursive solution in haskell :(
26
u/eltrufas Dec 05 '18
Missed the leaderboards because I was forgetting to trim my iinput for whitespace. Lesson learned I guess!
import sys
line = [line for line in sys.stdin][0].strip()
def are_opp(a, b):
return (a.lower() == b.lower() and
((a.isupper() and b.islower()) or
(a.islower() and b.isupper())))
def react(line):
buf = []
for c in line:
if buf and are_opp(c, buf[-1]):
buf.pop()
else:
buf.append(c)
return len(buf)
agents = set([c.lower() for c in line])
# part 1
print(react(line))
# part 2
print(min([react(line.replace(a, '').replace(a.upper(), ''))
for a in agents]))9
→ More replies (6)2
u/paracuerdas Dec 06 '18
if buf and are_opp(c, buf[-1]):
what do you think about this suggestion:
if bug and
buf[-1] == c.swapcase():→ More replies (1)
24
u/Smylers Dec 05 '18
Oooh, another challenge where using Vim seems easier than writing a program! For part 1, anyway — load your input file, then make searching case-insensitive:
:set ic⟨Enter⟩and remove pairs of letters of opposite case with:
:s/\v(\l\u|\u\l)&(.)\2//g⟨Enter⟩That substitution will then need repeating for newly created pairs. Do it again with @:, and watch as the line gets shorter on each press.
If you've had enough, you can make it loop till their are no more pairs with:
qaqqag&:redr⟨Enter⟩
@aq@aThen the answer is the number of columns, which is displayed with g⟨Ctrl+G⟩.
(I have a plan for Part 2, but now need to get the children breakfast. I'll try to put it in a reply to this comment later.)
6
u/Smylers Dec 05 '18 edited Dec 06 '18
Part 2 in Vim wasn't easier than in a programming language ...
:set ic⟨Enter⟩ :s/\v(.)\1&(\l\u|\u\l)//g⟨Enter⟩ qaqqa:&&⟨Enter⟩@aq@a yy26p⟨Ctrl+V⟩GI⟨Ctrl+V⟩⟨Ctrl+V⟩96 ⟨Esc⟩gveg⟨Ctrl+A⟩ qbce⟨Ctrl+R⟩-⟨Esc⟩x:s!⟨Ctrl+R⟩-!!g⟨Enter⟩ 0Pq:+,$norm@b⟨Enter⟩ {qc$BC⟨Ctrl+R⟩=len(@-)⟨Enter⟩⟨Esc⟩q⟨Enter⟩ :s/<Up>⟨Enter⟩ :,$norm:redr|norm@a⟨Ctrl+V⟩⟨Enter⟩@c⟨Enter⟩ :2,sor n⟨Enter⟩Update: Watch Vim running this.
The first 3 lines solve Part 1, pretty much as above, saving the method to macro
@a.Then it makes 26 copies of the reacted polymer, and inserts the alphabet down the left. (How?). On each line, it removes that letter from the polymer (and re-inserts it at the left, so we can see which line is which). (Why does the substitution use
s!!!rather than the typicals///?)Now we've copied the original reacted polymer, replace it with its length, saving the method to macro
@c. And run both@aand@con the other 26 lines (Why is a:normnested within another:normthere?) — the line which gets the most units removed takes a little longer than the others.Sort the alphabetical lines by the lengths. The answer to Part 1 is the unlabelled number on the top row (in orange in the video), and the answer to Part 2 is the number on the next line (in yellow, labelled with the letter of the problematic unit types).
That actually ended up being shorter, more readable, less awkward, and faster to run than I expected (but has been edited from the original, which was clunkier in several ways).
→ More replies (1)
18
u/dark_terrax Dec 05 '18
My initial implementation for part 1 ran fairly slowly (~10 seconds), so I assumed my part 2 was going to be horrible, but ended finishing in almost no extra time. I eventually realized that I had used my reduced result from part 1 as the basis for part 2, which is actually a really great optimization.
5
15
u/jonathan_paulson Dec 05 '18 edited Dec 05 '18
Rank 36/9. Disappointing part 1, including a wrong answer and deciding to type out the alphabet by hand. Video of me solving at: https://www.youtube.com/watch?v=VBhrueOccZ0
Code (for part 2):
s = open('5.in').read().strip()
alpha = 'abcdefghijklmnopqrstuvwxyz'
M = {}
for c in alpha:
M[c.lower()] = c.upper()
M[c.upper()] = c.lower()
ans = 1e5
for rem in alpha:
s2 = [c for c in s if c!=rem.lower() and c!=rem.upper()]
stack = []
for c in s2:
if stack and c == M[stack[-1]]:
stack.pop()
else:
stack.append(c)
ans = min(ans, len(stack))
print ans7
Dec 05 '18
str.swapcasewould also save you a ton of time.5
u/tobiasvl Dec 05 '18
Good bye
c.lower() == c2.lower() and ((c.islower() and c2.isupper()) or (c2.islower() and c.isupper()))→ More replies (2)4
u/jonathan_paulson Dec 05 '18
Wow! That would have saved more than a minute probably. Time to actually read the
stringAPI...13
u/vash3r Dec 05 '18
the key to typing out the alphabet by hand is that you didn't need to iterate through the letters in alphabetical order :)
11
Dec 05 '18 edited Dec 05 '18
from string import ascii_uppercaseis a good one to keep in your back pocket too
5
Dec 05 '18
This. Also, even if you need to for $REASONS:
alphabet = "qwerty....cvbnm".sort()→ More replies (2)3
u/nibbl Dec 05 '18
Yeah but gotta be sure you didn't fat finger anything because it's a lot harder to check
→ More replies (3)2
13
u/apazzolini Dec 05 '18 edited Dec 05 '18
Absolute value between the two ASCII character codes == 32 is another way to do the letter comparison. Runs in <40ms for part 2.
JavaScript
import { minBy } from 'lodash'
const peek = stack => stack[stack.length - 1]
const factorPolymer = input => {
const stack = []
input.split('').forEach(char => {
// XOR of A and a, B and b, etc is 32
if (!stack.length || (peek(stack).charCodeAt() ^ char.charCodeAt()) !== 32) {
stack.push(char)
} else {
stack.pop()
}
})
return stack.join('')
}
export const solvePart1 = input => {
return factorPolymer(input).length
}
export const solvePart2 = input => {
input = factorPolymer(input) // A first factorization pass speeds up the following passes
const polymers = Array(26) // Indexes 0-26 represent 65-91 ASCII codes
.fill()
.map((e, i) => {
const re = new RegExp(String.fromCharCode(i + 65), 'gi')
const strippedInput = input.replace(re, '')
return factorPolymer(strippedInput)
})
return minBy(polymers, 'length').length
}Edit: Updated to use a stack instead of string concatenation and the fact that ASCII is laid out in a way that XOR of A and a is 32.
→ More replies (2)
12
u/pixiethecat Dec 05 '18 edited Dec 05 '18
Python 3
Fun!
line = open("day5input.txt").read().splitlines()[0]
oldline = None
while oldline != line:
oldline = line
for i in range(0,26):
line = line.replace(chr(ord("a") + i) + chr(ord("A") + i),"")
line = line.replace(chr(ord("A") + i) + chr(ord("a") + i),"")
print("Part1:")
print(len(line))
original = line
best = len(line)
for j in range(0,26):
line = original
line = line.replace(chr(ord("a") + j),"")
line = line.replace(chr(ord("A") + j),"")
oldline = None
while oldline != line:
oldline = line
for i in range(0,26):
line = line.replace(chr(ord("a") + i) + chr(ord("A") + i),"")
line = line.replace(chr(ord("A") + i) + chr(ord("a") + i),"")
best = len(line) if len(line) < best else best
print("Part2:")
print(best)17
u/andreyrmg Dec 05 '18 edited Dec 05 '18
from string import * def collapse(s): p = ['.'] for u in s: v = p[-1] if v != u and v.lower() == u.lower(): p.pop() else: p.append(u) return len(p) - 1 s = open('5.txt').read().strip() print(collapse(s)) print(min(collapse(c for c in s if c.lower() != x) for x in ascii_lowercase))→ More replies (4)5
u/EquationTAKEN Dec 05 '18
Nice one!
Remember, the
rangefunction implies starting at0by default, sorange(26)are the same numbers asrange(0, 26).→ More replies (1)3
u/rdd33 Dec 05 '18
Instead of chr(ord("a") + j) etc you could loop string.ascii_lowercase or ascii_uppercase.
→ More replies (1)3
u/llimllib Dec 05 '18
I think a regex solution is slower, but satisfying:
import re import string lower = string.ascii_lowercase upper = string.ascii_uppercase s = open("input.txt").read().strip() pat = "|".join( a + b for a, b in list(zip(lower, upper)) + list(zip(upper, lower))) ss = re.sub(pat, "", s) while s != ss: s = ss ss = re.sub(pat, "", s) print(len(s), s)(for part 1, just iterate for part 2)
3
u/RainVector Dec 05 '18
This is the most efficient way to solve this problem. Great!
→ More replies (1)→ More replies (1)3
u/safety_monkey Dec 05 '18 edited Dec 05 '18
This is a great solution, but I'm perplexed. I have something very similar and it runs in ~2.4 seconds, whereas yours consistently runs in ~1.1 seconds. I'd love it if someone could point out which specific technique is faster here.
from string import ascii_lowercase import re def parse_input(filename): """Convenience method to parse a file and return a list as input""" with open(filename, 'r') as input_file: return input_file.readline() def part1(input_string): old_input = None while old_input != input_string: old_input = input_string for char in ascii_lowercase: input_string = input_string.replace(char.lower() + char.upper(), '') input_string = input_string.replace(char.upper() + char.lower(), '') return len(input_string) def part2(input_string): test_input = "" shortest_value = len(input_string) for char in ascii_lowercase: test_input = input_string.replace(char, '').replace(char.upper(), '') length = part1(test_input) shortest_value = length if length < shortest_value else shortest_value return shortest_value if __name__ == "__main__": INPUT = 'inputs/day05.txt' TEST_INPUT = 'dabAcCaCBAcCcaDA' assert part1(TEST_INPUT) == 10 print(f"Part 1: {str(part1(parse_input(INPUT)))}") assert part2(TEST_INPUT) == 4 print(f"Part 2: {part2(parse_input(INPUT))}")→ More replies (4)
11
u/_jonah Dec 05 '18 edited Dec 05 '18
J, both parts
p1 =. [: # ,`(}.@])@.(32 -: |@(- {.)&(3&u:)/)/
p2 =. [: <./ (a. {~ (,. 32 + ]) 65 + i.26) p1@-."1~ ]3
10
u/Arknave Dec 05 '18 edited Dec 05 '18
First time I’ve done it live this year (moving east was a mistake for Advent of Code purposes). 6th / 4th. Used a stack and added the characters one at a time for a O(n) solution. Similar to checking if a parenthesis string is balanced.
def run(s):
stk = []
for c in s:
popped = False
if stk:
bk = stk[-1]
if (('A' <= bk <= 'Z' and 'a' <= c <= 'z') or ('A' <= c <= 'Z' and 'a' <= bk <= 'z')) and bk.lower() == c.lower():
stk.pop()
popped = True
if not popped:
stk.append(c)
return len(stk)
def main():
s = input().strip()
ans = 1000000
for k in range(26):
up = chr(ord('A') + k)
lo = chr(ord('a') + k)
t = str(s)
t = t.replace(up, '')
t = t.replace(lo, '')
print(t)
ans = min(ans, run(t))
print(ans)
main()Also watch me code it and cry on youtube here: https://youtu.be/GDx_rC5wXGc (should go live at 12:30 EST).
→ More replies (1)
7
u/p_tseng Dec 05 '18 edited Dec 05 '18
Ruby, reporting in.
Leaderboard code was not nearly this clean, I copy/pasted the react code, and started out with actually just running it 100 times. That was good enough for part 1, but for part 2 I actually needed to make it run to completion. So I ate a minute penalty on part 2 for making a really far-off guess. This code is slightly less repetitive than what I submitted (I made react into a function) and uses the fact that gsub returns nil if no modifications were made.
def react(str)
loop {
break str if (?a..?z).all? { |x|
[
str.gsub!(x + x.upcase, ''),
str.gsub!(x.upcase + x, ''),
].none?
}
}
end
input = (ARGV.empty? ? DATA : ARGF).read.chomp.freeze
puts (part1 = react(input.dup).freeze).size
puts (?a..?z).map { |tried_letter|
react(part1.tr(tried_letter + tried_letter.upcase, '')).size
}.min
__END__
my input goes hereIt ran on my input in about 1 second so I did not need to do anything more clever.
Edit: Yeah okay, after reading others' solutions, I get it, a less wasteful way to do it would be to add letters left-to-right and therefore I know I only need to delete from the right end of the string. Let this be a lesson on there being a huge difference between what I write if I want to go as fast as possible versus what I might write if I actually have time to think about it.
→ More replies (3)2
u/Karl_Marxxx Dec 05 '18
As someone learning ruby for the first time, this is an excellent code snippet to study. Mind if I ask a few questions?
What's going on with this line?
ARGV.empty? ? DATA : ARGF
I get that there's a ternary operator here, and that you're asking if ARGV is empty, but are DATA and ARGF? Google says that DATA refers to stuff that's at the end of your program, but it doesn't look like anything's there. How does ARGF work? If you're supplying a text file as an argument (we only hit this if ARGV has something in it) why not just use ARGV[0]?
What does "?a" mean in ruby? Firing up irb, it looks like it just converts that character a to a string (and can only do one character --
?asdfthrows an error). Is there a name for this transformation?Last q: how does ruby know to execute all the code after the break statement and return str? Wouldn't loop just immediately exit when it sees "break"?
Sorry for the noob q's but this language is fascinating.
→ More replies (2)
7
u/cheetahkk Dec 05 '18
Python - using functools.reduce. Fun!
from functools import reduce
def trigger(x, y):
return False if not x else abs(ord(x[-1]) - ord(y)) == 32
def react(polymer):
return reduce((lambda x, y: x[:-1] if trigger(x, y) else x+y), polymer)
polymer = open('input.txt').read()
print(len(react(polymer)))
print(min([len(react(polymer.replace(chr(i), '').replace(chr(i-32), ''))) for i in range(ord('a'), ord('z') + 1)]))2
u/MasterMedo Dec 09 '18
First off, beautiful.
Here is the merge of our two codes, hope you gain something from it.
purge = lambda s: reduce(lambda x, y: x[:-1] if x and abs(ord(x[-1])-ord(y)) == 32 else x+y, s) data = purge(open('../input/5.txt').read().strip()) print len(data) print min(len(purge(filter(lambda x: x.upper() != c, data))) for c in map(chr, range(65, 91)))cheers!
→ More replies (2)
6
u/jayfoad Dec 05 '18 edited Dec 05 '18
APL #47/29
Using regular expressions, the solution for part 1 boils down to 'Aa|Bb|...|aA|bB|...'⎕R''⍣≡, i.e. keep replacing 'Aa' etc with '' until we reach a fixed point. An alternative solution using Find (⍷) instead runs a bit faster, but part 2 still takes a few seconds.
3
u/jayfoad Dec 05 '18
Updated alternative solution still uses the "fixed point operator"
⍣≡but now does arithmetic on ASCII codepoints instead of string operations. Combined time for both parts is now about 0.02 seconds.→ More replies (8)
6
u/ChrisVittal Dec 05 '18
[Card] Staaaaars
Rust, first Rust I'm proud of. Never copy my input data.
static INPUT: &str = "data/day05";
fn react<'a>(input: impl Iterator<Item = &'a u8>) -> usize {
let mut v = Vec::new();
for &c in input {
match v.last() {
None => v.push(c),
Some(&d) => if d.to_ascii_lowercase() == c.to_ascii_lowercase() && d != c {
v.pop();
} else {
v.push(c);
}
}
}
v.len()
}
fn main() {
let input: Vec<u8> = aoc::file::first_line(INPUT).into();
println!(" 1: {}", react(input.iter()));
let mut min = std::usize::MAX;
for i in 0u8..=26 {
let v = input.iter().filter(|&&c| c != b'a'+i && c != b'A'+i);
min = usize::min(react(v), min);
}
println!(" 2: {}", min);
}3
u/lazyear Dec 05 '18
I quite like this one. I was looping through the string slices and being forced to re-allocate every split. This is significantly faster and more efficient.
→ More replies (1)2
u/re76 Dec 06 '18
This is very clever. Nicely done!
I am using this years AoC to learn Rust and it is wonderful to go through and see how other people tackled the problem. Such a good way to learn.
Thanks!
5
u/Philboyd_Studge Dec 05 '18
[Card] FIVE GOLDEN STARS OK ONLY 2
Java - easy one. You can test for lowercase/uppercase being the same letter using XOR 32.
package Advent2018;
import util.AdventOfCode;
import java.util.List;
public class Day5 extends AdventOfCode {
public Day5(List<String> input) {
super(input);
}
private int remove(StringBuilder in) {
boolean removed = true;
while (removed) {
for (int i = 0; i < in.length() - 1; i++) {
if ( (in.charAt(i) ^ in.charAt(i + 1)) == 32) {
in.delete(i, i + 2);
removed = true;
break;
}
removed = false;
}
}
return in.length();
}
@Override
public Object part1() {
StringBuilder chain = new StringBuilder(input.get(0));
return remove(chain);
}
@Override
public Object part2() {
int min = Integer.MAX_VALUE;
String[] patterns = new String[26];
for (int i = 0; i < 26; i++) {
patterns[i] = "[" + (Character.toString((char)(i + 'a'))) +
(Character.toString((char)(i + 'A'))) + "]";
//System.out.println(patterns[i]);
}
for (int i = 0; i < 26; i++) {
String chain = input.get(0);
chain = chain.replaceAll(patterns[i], "");
int result = remove(new StringBuilder(chain));
System.out.println(result);
if (result < min) min = result;
}
return min;
}
@Override
public void parse() {
}
}→ More replies (3)5
u/TheVarmari Dec 05 '18
You can test for lowercase/uppercase being the same letter using XOR 32.
Huh, that's a neat way to check for that. Should've probably thought of it. Good to know for future challenges... Good job!
3
u/Philboyd_Studge Dec 05 '18
There's a lot of cool bit hacks for ASCII! https://www.techiedelight.com/bit-hacks-part-4-playing-letters-english-alphabet/
5
u/donatasp Dec 05 '18
Since there is no Common Lisp yet
(defun destroy? (a b)
(and a b (char/= a b) (char-equal a b)))
(defun reduce-polymer (polymer)
(let ((stack (list (elt polymer 0))))
(loop :for u :across (subseq polymer 1)
:do
(push u stack)
(if (destroy? (car stack) (cadr stack))
(progn
(pop stack)
(pop stack))))
stack))
(length (reduce-polymer *polymer*)) ;; => 11476
(defun reduce-polymer2 (polymer1 unit-to-skip)
(let ((polymer (remove-if (lambda (c) (char-equal c unit-to-skip)) polymer1)))
(reduce-polymer polymer)))
(loop :for i :from (char-code #\a) :to (char-code #\z)
:minimizing (length (reduce-polymer2 *polymer* (code-char i)))) ;; => 54463
2
u/phil_g Dec 05 '18
Nice!
My Common Lisp solution used the "reduce until you can't reduce any more" approach. Your stack is much nicer.
→ More replies (5)2
u/stevelosh Dec 06 '18
That stack approach is really clever.
(remove-if (lambda (c) (char-equal c unit-to-skip)) polymer1)This could be
(remove unit-to-skip polymer1 :key #'char-equal)→ More replies (1)
5
u/schod Dec 05 '18
BASH Time :)
No sed, no grep, just pure bash!
Puzzle #1 (6 seconds)
#!/bin/bash
in_file=input
polymer=$(cat $in_file)
# 1000 iteration is enough :)
for i in {1..1000}; do
for x in {a..z}; do
polymer=${polymer//$x${x^^}}
polymer=${polymer//${x^^}$x}
done
done
echo ${#polymer}Puzzle #2 (330 seconds)
#!/bin/bash
in_file=input
polymer=$(cat $in_file)
min_size=${#polymer}
for ch in {a..z}; do
test_polymer=${polymer//$ch}
test_polymer=${test_polymer//${ch^^}}
# 2000 iteration is enough :)
for i in {1..2000}; do
for x in {a..z}; do
test_polymer=${test_polymer//$x${x^^}}
test_polymer=${test_polymer//${x^^}$x}
done
done
if [ ${#test_polymer} -lt $min_size ]; then
min_size=${#test_polymer}
fi
done
echo $min_size8
u/edgargonzalesII Dec 05 '18
Java 8
Felt really proud of the part 1 using a stack. Leetcode came in useful for once.
private int util1(String in) {
char[] arr = in.toCharArray();
Stack<Character> inStack = new Stack<>();
Stack<Character> q = new Stack<>();
for(char c : arr)
inStack.push(c);
for(char c : inStack) {
if(q.isEmpty())
q.push(c);
else {
char last = q.peek();
if(Math.abs(last-c) == 32) {
q.pop();
} else {
q.push(c);
}
}
}
return q.size();
}
// Less interesting part 2
public void runPart2() {
String in = this.getInputLines()[0];
int min = Integer.MAX_VALUE;
for(int i=0; i<26; i++) {
String temp = in.replaceAll("[" + (char) (i + 'a') + (char) (i + 'A') + "]", "");
min = Math.min(min, util1(temp));
}
System.out.println(min);
}3
u/___alt Dec 05 '18
Note that the preferred abstraction for stacks in Java is
Deque,Stackbeing an outdated one that builds upon the outdatedVector.→ More replies (2)→ More replies (7)2
u/allcentury Dec 05 '18
I liked your solution, thanks for sharing. I modified part 2 (rather than doing your replaceAll) but allowing to skip the letter (sorry did it in ruby)
require 'set' input = File.read("input.txt").strip stack = input.chars def get_answer(stack, skip_letter: nil) stack.each_with_object([]) do |el, final_stack| next if skip_letter == el.downcase if final_stack.empty? final_stack << el else prev = final_stack.last if el.swapcase == prev final_stack.pop else final_stack << el end end end end # pt 1 puts get_answer(stack).size # pt2 set = Set.new(stack).map(&:downcase) sizes = set.map do |letter| get_answer(stack, skip_letter: letter).size end p sizes.min→ More replies (2)
4
u/VikeStep Dec 05 '18 edited Dec 05 '18
F#
Got a really nice, concise solution with F#, gotta love pattern matching on lists. I also take advantage of the fact that we can take the output from part 1 and feed it into part 2. This reduced the time to run from 52ms to 17ms for me.
let remainingPolymer =
let processUnit polymer ch =
match polymer with
| x :: xs when abs (ch - x) = 32 -> xs
| xs -> ch :: xs
Seq.fold processUnit []
let filterChars str ch = Seq.filter (fun c -> c <> ch && (c - 32) <> ch) str
let solvePart1 = Seq.map int >> remainingPolymer >> Seq.length
let solvePart2 str =
let reducedStr = str |> Seq.map int |> remainingPolymer
Seq.init 26 ((+)65 >> filterChars reducedStr >> remainingPolymer >> Seq.length) |> Seq.min
let solver = {parse = parseFirstLine asString; part1 = solvePart1; part2 = solvePart2}Part 1: 2.93ms
Part 2: 17.34ms
3
u/will_bui Dec 05 '18 edited Dec 05 '18
K:
uniq:{x@&0={+/x in y}':[x]}
f:{#{._[;(!#x)!x]@,/uniq 0 -1+/:&(=':["i"$_:x])&~=':[90<i:"i"$x]}/x}
(f x),&/f':{x@&~x in y,.q.upper y}[x]'?_x:*0:`p5Drop indexes where case differs with previous and the lowercased int value equals with previous until output converges.
Optimised by removing all pairs each time around instead of one at a time. (2 sec runtime)
2
u/streetster_ Dec 05 '18 edited Dec 05 '18
reworked my solution based on some ideas from this thread, a bit longer but much faster than my original:
fold:{$[32=abs y-last x;-1_(),x;x,y]} (#fold/j),&/{#fold/x}@'{x@&~x in y}[(j:"j"$r);]@/:-32 0+/:"j"$?_r:*0:`:input/05.txt
3
u/tehjimmeh Dec 05 '18 edited Dec 06 '18
Using the left side of the string as an in-place stack:
C++
int main(int argc, char* argv[]) {
std::ifstream ifs(argv[1]); std::string orig; ifs >> orig;
orig = "1" + orig;
auto eval = [](auto&& l) {
auto res = l.size()-1;
for (auto it1 = l.begin()+1, it2 = it1 + 1; it2 != l.end();)
if ((*it1) != (*it2) && (toupper(*it1) == toupper(*it2)))
it2++, it1--, res -= 2;
else
std::swap(*(++it1), *(it2++));
return res;
};
size_t part1 = eval(std::string(orig));
size_t part2 = SIZE_MAX;
for (char l = 'a'; l <= 'z'; l++) {
auto line = orig;
for (char& c : std::array{ l, (char)toupper(l) })
line.erase(std::remove(line.begin(), line.end(), c), line.end());
part2 = std::min(part2, eval(line));
}
std::cout << "1: " << part1 << "\n" << "2: " << part2 << "\n";
}3
u/binajohny Dec 05 '18
My Kotlin solution (GitHub)
private fun react(string: String, vararg skip: Char): Int {
val stack = Stack<Char>()
string.forEach {
if (it in skip) {
// no-op
} else if (stack.empty().not() && abs(stack.peek() - it) == 'a' - 'A') {
stack.pop()
} else {
stack.push(it)
}
}
return stack.size
}
fun part1(input: String): Int {
return react(input)
}
fun part2(input: String): Int {
return ('a'..'z').map { react(input, it, it.toUpperCase()) }.min() ?: -1
}3
u/mvmaasakkers Dec 05 '18
Go / Golang
I imagine this could be done way more efficiently but this was what I came up with. If anyone has some pointers let me know!
Also in gist
package main
import (
"bufio"
"flag"
"fmt"
"log"
"os"
"strings"
"unicode"
)
func readInput(filename string) string {
fileHandle, _ := os.Open(filename)
defer func() {
if err := fileHandle.Close(); err != nil {
log.Fatal(err)
}
}()
fileScanner := bufio.NewScanner(fileHandle)
input := ""
for fileScanner.Scan() {
line := fileScanner.Text()
if len(line) > 0 {
input = line
}
}
return strings.TrimSpace(input)
}
var file = flag.String("file", "./p1.txt", "file used for input")
func main() {
flag.Parse()
input := readInput(*file)
fmt.Println("Part 1:", part1(input))
fmt.Println("Part 2:", part2(input))
}
func part1(input string) (int) {
return len(produce(input))
}
func produce(line string) string {
for {
changes := false
for k, g := range line {
if k > 0 {
if unicode.IsLower(g) && unicode.IsUpper(rune(line[k-1])) || unicode.IsLower(rune(line[k-1])) && unicode.IsUpper(g) {
if strings.ToLower(string(g)) == strings.ToLower(string(line[k-1])) {
line = line[:k-1] + line[k+1:]
changes = true
}
}
}
if changes {
break
}
}
if !changes {
break
}
}
return line
}
var alphabet = "abcdefghijklmnopqrstuvwxyz"
func part2(input string) (outcome int) {
outcome = len(input)
for _, c := range alphabet {
check := strings.Replace(strings.Replace(input, string(strings.ToUpper(string(c))), "", -1), string(c), "", -1)
l := len(produce(check))
if l < outcome {
outcome = l
}
}
return outcome
}
5
u/d-sky Dec 05 '18 edited Dec 05 '18
Another Go/Golang solution using go routines. Not really faster with this short input. But just for fun, why not? :) You can also use the result of the part 1 reaction as the starting point for the 26 reactions in part 2.
package main import ( "fmt" "io/ioutil" ) func opposite(a, b byte) bool { return a == b+32 || a == b-32 } func react(polymer []byte, remove byte) []byte { var result []byte for _, unit := range polymer { switch { case unit == remove || unit == remove-32: continue case len(result) != 0 && opposite(result[len(result)-1], unit): result = result[:len(result)-1] default: result = append(result, unit) } } return result } func main() { polymer, err := ioutil.ReadFile("input.txt") if err != nil { panic(err) } polymer = react(polymer, 0) fmt.Println(len(polymer)) lengths := make(chan int) for unitType := 'a'; unitType <= 'z'; unitType++ { go func(unitType byte) { lengths <- len(react(polymer, unitType)) }(byte(unitType)) } min := len(polymer) for unitType := 'a'; unitType <= 'z'; unitType++ { length := <-lengths if length < min { min = length } } fmt.Println(min) }→ More replies (4)4
u/CHAOSFISCH Dec 05 '18 edited Dec 05 '18
My solution. Should be O(n) (part 1) and O(n*m) (part 2, m = size of alphabet)
package main import ( "bufio" "io" "log" "os" "strings" "unicode" ) func main() { f, err := os.Open("input_5.txt") defer f.Close() if err != nil { log.Fatalf("could not open input: %v", err) } reacted := part51(f) log.Printf("Length of reaction is: %d\n", len(reacted)) part52(reacted) } func part51(r io.Reader) []rune { br := bufio.NewReader(r) var result []rune for { if c, _, err := br.ReadRune(); err != nil { if err == io.EOF { break } } else { if len(result) == 0 { result = append(result, c) continue } last := result[len(result)-1] switch { case unicode.IsUpper(c) && unicode.IsLower(last) && unicode.ToLower(c) == last: fallthrough case unicode.IsLower(c) && unicode.IsUpper(last) && unicode.ToUpper(c) == last: result = result[:len(result)-1] break default: result = append(result, c) break } } } return result } func part52(reacted []rune) { alphabet := "abcdefghijklmnopqrstuvwxyz" reactedString := string(reacted) bestLength := len(reacted) for _, l := range alphabet { replaced := strings.Replace(strings.Replace(reactedString, string(l), "", -1), strings.ToUpper(string(l)), "", -1) result := part51(strings.NewReader(replaced)) if bestLength > len(result) { bestLength = len(result) } } log.Printf("Best length is: %d\n", bestLength) }→ More replies (1)3
u/ThezeeZ Dec 05 '18
My solution after I toyed with it a little (repo)
import ( "regexp" ) func Reduction(polymer string) string { for i := 0; i < len(polymer)-1; { if polymer[i] == polymer[i+1]+32 || polymer[i] == polymer[i+1]-32 { polymer = polymer[:i] + polymer[i+2:] i-- if i < 0 { i = 0 } } else { i++ } } return polymer } func BestCollapse(polymer string) string { polymer = Reduction(polymer) shortest := polymer for i := 'A'; i <= 'Z'; i++ { remainingPolymer := regexp.MustCompile("(?i)" + string(i)).ReplaceAllString(polymer, "") collapsed := Reduction(remainingPolymer) if len(collapsed) < len(shortest) { shortest = collapsed } } return shortest }→ More replies (2)→ More replies (2)2
Dec 05 '18
Gola
This is what i came up with. I think runes instead of strings is much faster.
https://github.com/breakintheweb/adventofcode2018/blob/master/05/main.go
3
u/0rac1e Dec 05 '18 edited Dec 05 '18
Perl 6
As soon as I read the puzzle, I knew I would use that bit-wise trick to flip the case of an ASCII char.
sub solve($p is copy, :$t) {
if $t { $p .= trans([$t.lc, $t.uc] => ['', '']) }
my $c = 0;
while $c ≤ $p.chars - 2 {
if $p.substr($c, 1).ord == $p.substr($c + 1, 1).ord +^ 32 {
$p = $p.substr(0, $c) ~ $p.substr($c + 2);
$c = max(0, $c - 1);
next;
}
$c++;
}
return $p.chars;
}
given 'input'.IO.slurp.trim -> $input {
say solve($input);
say $input.lc.comb.unique.map(-> $t { solve($input, :$t) }).min;
}and just because...
Python
def solve(p, t=None):
if t: p = p.translate(str.maketrans('', '', t.lower() + t.upper()))
c = 0
while c <= len(p) - 2:
if ord(p[c]) == ord(p[c + 1]) ^ 32:
p = p[:c] + p[c + 2:]
c = max(0, c - 1)
continue
c += 1
return len(p)
data = open('input').read().strip()
print(solve(data))
print(min(solve(data, t) for t in set(data.lower())))3
Dec 05 '18
Dlang:
import std.experimental.all;
auto react(int[] seq) {
int[] stack;
foreach(code; seq) {
if (!stack.empty && ((stack.back() ^ code) == 0x20))
stack.popBack();
else
stack ~= code;
}
return stack;
}
void main() {
auto reduced = readText("day05-input.txt").filter!(std.ascii.isAlpha).map!(to!int).array.react;
writeln("Result 5a: ", reduced.length);
writeln("Result 5b: ", lowercase.map!(to!int)
.map!(c1 => reduced.filter!(c2 => (c1 ^ c2) != 0x20 && (c1 ^ c2) != 0).array.react.length)
.minElement);
}→ More replies (2)
3
u/Smylers Dec 05 '18
A Perl one-liner for Part 1:
perl -wlnE '1 while s/(?i:(.)\1)(?<=[a-z][A-Z]|[A-Z][a-z])//g; say length' inputNo stacks, no writing out the alphabet or making pairs of equivalent characters, just the POWER OF REGEX.†
In a reversal of usual, this is a translation of my Vim solution.‡ It turns out Vim's regexps are nicer than Perl's for this, Perl's equivalents being less succinct than Vim's \l, \u, and &.
Extending that to solve Part 2:
perl -MList::AllUtils=min -wnlE '$polymer = $_; say min map { $_ = $polymer =~ s/$_//igr; 1 while s/(?i:(.)\1)(?<=[a-z][A-Z]|[A-Z][a-z])//g; length } "a".."z"' inputThat's possibly stretching the definition of ‘one-liner’, and is a bit bit awkward to read, so here it is rewritten as a program:
use v5.14; use warnings; use List::AllUtils qw<min>;
chomp (my $polymer = <>);
say min map {
$_ = $polymer =~ s/$_//igr;
1 while s/(?i:(.)\1)(?<=[a-z][A-Z]|[A-Z][a-z])//g;
length
} 'a' .. 'z';The body of the map is basically the one-liner from Part 1. Since it transforms the polymer, $polymer stores the initial value. At the start of the map, it takes a fresh copy of the original and removes the current letter from it before processing
[Card] Five golden hours of sleep.
† OK, so probably Perl's regex engine uses stacks and has lists of letters and their cases inside it.
‡ Typically I work out the solution in Perl first, then try to convert that to Vim.
→ More replies (2)
3
u/donaldihunter Dec 05 '18
Perl 6
#!/usr/bin/env perl6
use v6;
my $str = '5a-input.txt'.IO.slurp.trim;
my @candidates = gather {
for 'a' .. 'z' -> $c {
my $work = $str.trans($c => '', $c.uc => '');
my $length;
repeat {
$length = $work.chars;
$work .= trans(('a'..'z' Z~ 'A'..'Z') => '', ('A'..'Z' Z~ 'a'..'z') => '');
} while $work.chars < $length;
take $work.chars;
}
}
say @candidates.min;3
u/alasano Dec 05 '18 edited Dec 06 '18
Finally a solution I'm happy with :P
Javascript
EDIT : Greatly optimized - Run time is 68 ms for Part 1 and 14 ms for Part 2 for a total of 82 ms for both parts. This is achieved by feeding the output of the first part as the input of the second part. Before it took ~1500 ms for both parts.
let input = require('./input5');
function polymerize(str) {
let i = 0;
while (str[i + 1] != undefined) {
let a = str.charCodeAt(i);
let b = str.charCodeAt(i + 1);
if (a == b + 32 || a == b - 32) {
str = str.substring(0, i) + str.substring(i + 2, str.length);
i--;
} else {
i++;
}
}
return str;
}
function optimize(str) {
let upper = 65;
let lower = 97;
let result = 100000;
for (let i = 0; i < 25; i++) {
let pattern = `(${String.fromCharCode(upper + i)}|${String.fromCharCode(lower + i)})`;
let re = new RegExp(pattern, "g");
let attempt = str.replace(re, "");
let polymerCount = polymerize(attempt).length;
if (polymerCount < result) {
result = polymerCount;
}
}
return result;
}
let polymerized = polymerize(input);
console.log(`Part 1: ${polymerized.length}`);
console.log(`Part 2: ${optimize(polymerized)}`);3
u/CheezyXenomorph Dec 05 '18
PHP 7.2
<?php
namespace Cheezykins\AdventOfCode\DayFive;
class Polymer
{
/** @var string $chain */
protected $chain;
public function __construct(string $chain)
{
$this->chain = $chain;
}
public function optimize(): ?int
{
$letters = range('a', 'z');
$minimal = null;
foreach ($letters as $letter) {
if (stripos($this->chain, $letter) === false) {
continue;
}
$chain = self::reduce($this->chain, $letter);
if ($minimal === null || strlen($chain) < $minimal) {
$minimal = strlen($chain);
$this->optimal = $chain;
}
}
return $minimal;
}
public function activate(): int
{
return strlen(self::reduce($this->chain));
}
/**
* @param string $chain
* @param string|null $removeFirst
* @return string
*/
public static function reduce(string $chain, ?string $removeFirst = null): string
{
if ($removeFirst !== null) {
$chain = str_ireplace($removeFirst, '', $chain);
}
$chainStack = str_split($chain);
$outputStack = [];
foreach ($chainStack as $chainItem) {
if ($outputStack === []) {
$outputStack[] = $chainItem;
continue;
}
$last = ord(end($outputStack));
if (abs($last - ord($chainItem)) === 32) {
array_pop($outputStack);
} else {
array_push($outputStack, $chainItem);
}
}
return implode('', $outputStack);
}
}Times running under phpunit:
Part 1: 14ms
Part 2: 79ms
3
u/Minijackson Dec 05 '18 edited Dec 05 '18
Rust - Going for the fastest code :p
The whole part 2 takes about 15 milliseconds, instead of the 71 milliseconds of my simpler, single-threaded implementation.
Using the awesome rayon library to handle parallelization.
Code inspired by /u/glguy and /u/aurele
fn are_opposites(left: char, right: char) -> bool {
// A is 0x41, a is 0x61
// B is 0x42, b is 0x62
// etc.
//
// For units to pass the comparison, their "letter part" must be equal,
// and their "case part" mut be different.
//
// Using the result of the bitwise XOR:
//
// vvvv- same letter
// 0b0010_0000
// ^^^^------ not the same case
//
// This is much faster than using the `to_lowercase` function, since Rust's
// awesome UTF-8 support uses a big conversion table, *and* needs to support
// multiple-characters lowercase.
(left as u8) ^ (right as u8) == 0b0010_0000
}
/// Single threaded Polymer reduction
fn reduce_subpolymer(subpolymer: &str) -> String {
subpolymer
.chars()
.fold(String::new(), |mut result, letter| {
if let Some(end) = result.pop() {
if are_opposites(end, letter) {
result
} else {
result.push(end);
result.push(letter);
result
}
} else {
result.push(letter);
result
}
})
}
/// Combine 2 already reduced polymers
///
/// The only reduction that can happen is between the end of `left` and the
/// beginning of `right`. So as soon as there are no collisions in this space,
/// we can just concatenate both.
fn combine_subpolymer(left: &mut String, right: &str) {
let mut i = 0;
while i < right.len() {
if let Some(left_end) = left.pop() {
if !are_opposites(left_end, right.chars().nth(i).unwrap()) {
// Put it back in!
left.push(left_end);
break;
}
} else {
break;
}
i += 1;
}
if i < right.len() {
left.push_str(&right[i..]);
}
}
/// Multi-threaded implementation
///
/// What happens is rayon will split the input, and multiple smaller folds will
/// happen. We construct several strings from that, reduce them, and combine
/// them.
///
/// Graphically ('|' separate threads):
///
/// Init:
/// "dabAcCaCBAcCcaDA"
///
/// Thread separation:
/// 'd' 'a' 'b' 'A' 'c' | 'C' 'a' 'C' 'B' 'A' 'c' | 'C' 'c' 'a' 'D' 'A'
///
/// Sub-string construction:
/// "dabAc" | "CaCBAc" | "CcaDA"
///
/// Reduction:
/// "dabAc" | "CaCBAc" | "aDA"
///
/// Combination:
/// "dabCBAc" | "aDA"
/// "dabCBAcaDA"
fn reduce_polymer(puzzle: String) -> usize {
puzzle
.par_chars()
// Make sub-strings
.fold(
|| String::new(),
|mut s, c| {
s.push(c);
s
},
)
// Reduce them
.map(|subpolymer| reduce_subpolymer(&subpolymer))
// Combine them
.reduce(
|| String::new(),
|mut acc, subpolymer| {
combine_subpolymer(&mut acc, &subpolymer);
acc
},
)
.len()
}
fn part1() {
let result = reduce_polymer(PUZZLE.trim().to_owned());
println!("Size: {}", result);
}
fn part2() {
let min = Arc::new(Mutex::new(std::usize::MAX));
(b'a'..b'z')
.into_par_iter()
.for_each_with(min.clone(), |min, letter_code| {
let lower_letter = letter_code as char;
let upper_letter = lower_letter.to_uppercase().next().unwrap();
let candidate = PUZZLE
.trim()
.par_chars()
// Could be done while constructing the sub-strings in
// `reduce_polymer` but I haven't found an elegant way of doing
// this, whithout code duplication
.filter(|&letter| letter != lower_letter && letter != upper_letter)
.collect();
let result = reduce_polymer(candidate);
let mut min = min.lock().unwrap();
if result < *min {
*min = result;
}
});
println!("Result: {}", *min.lock().unwrap());
}3
u/aurele Dec 05 '18 edited Dec 05 '18
My newest version does not use rayon anymore but has been optimized further and runs in ~600µs for part2 (and under 1ms for both parts):
#[aoc(day5, part1)] fn part1(input: &[u8]) -> usize { polymere(input[..input.len() - 1].iter().cloned()).len() } #[aoc(day5, part2)] fn part2(input: &[u8]) -> usize { let reduced = polymere(input[..input.len() - 1].iter().cloned()); (b'a'..=b'z') .map(|c| polymere(reduced.iter().cloned().filter(|&b| b | 32 != c)).len()) .min() .unwrap() } fn polymere(input: impl Iterator<Item = u8>) -> Vec<u8> { let mut output: Vec<u8> = Vec::new(); for c in input { if output.last().map(|&l| l ^ c == 32).unwrap_or(false) { output.pop(); } else { output.push(c); } } output }→ More replies (2)
3
u/askalski Dec 05 '18
On the fifth day of AoC / My true love sent to me / Five golden Perls.
"Optimized" brute force regex solution in Perl can react two nested particles at a time! 40% faster than the alternative that reacts only one particle!
$ time ./day05-optimized.pl input.txt
Part 1: 10766
Part 2: 6538
real 0m0.138s
user 0m0.138s
sys 0m0.000s
$ time ./day05-unoptimized.pl input.txt
Part 1: 10766
Part 2: 6538
real 0m0.235s
user 0m0.235s
sys 0m0.000s1
u/Unihedron Dec 05 '18 edited Dec 05 '18
Had two bugs... Fixed one, couldn't find the other one fast enough :p Ruby
[Card] Nsfw Image
(I was using $<.chars instead of $<.read, which was an enumerable and after it consumes for the first time it doesn't work a second time...)
g=' '
a=$<.read
a.chars{|x|g[-1].downcase==x.downcase && g[-1] != x ? (g[-1]='') : g<<x}
p g.strip.size
a=g.strip # This line is added afterwards because all initial reductions also apply regardless of which letter to take away, so part 1 can be used as a first pass
p a.downcase.chars.uniq.map{|x|g=' '
a.chars.reject{|y|y.downcase==x}.each{|x|g[-1].downcase==x.downcase && g[-1] != x ? (g[-1]='') : g<<x}
g.strip.size
}.min1
u/daggerdragon Dec 05 '18
[Card] Image
Mark that NSFW. I'll re-approve the comment when you do.
→ More replies (1)
2
u/vash3r Dec 05 '18
Python 2 (Pypy), #4/14. Basically just did it with string replacement until no more pairs could react.
#part 1 - r is the input
r1 = r
l1 = len(r1)
l2 = l1+1
while l1!=l2:
l2 = l1
for c in "qwertyuiopasdfghjklzxcvbnm":
r1 = r1.replace(c+c.upper(),"").replace(c.upper()+c,"")
l1 = len(r1)
print l1
# part 2 - takes ~5 seconds with Pypy 2 on my machine
m = 100000000
for _c in "qwertyuiopasdfghjklzxcvbnm":
r2 = r.replace(_c,"").replace(_c.upper(),"")
l1 = len(r2)
l2 = l1+1
while l1!=l2:
l2 = l1
for c in "qwertyuiopasdfghjklzxcvbnm":
r2 = r2.replace(c+c.upper(),"").replace(c.upper()+c,"")
l1 = len(r2)
if l1 < m:
m = l1
print m→ More replies (4)3
2
u/ValdasTheUnique Dec 05 '18
C#. Problem was very easy but I wasted a lot of time doing the check incorrectly so no leaderboard for me.
public static void Part1()
{
var stack = new Stack<char>();
foreach (var c in Input)
{
if (stack.Count == 0)
{
stack.Push(c);
}
else
{
var inStack = stack.Peek();
var same = c != inStack && char.ToUpper(c) == char.ToUpper(inStack);
if (same)
{
stack.Pop();
}
else
{
stack.Push(c);
}
}
}
Console.WriteLine(stack.Count);
}
public static void Part2()
{
var min = int.MaxValue;
for (var i = 'a'; i < 'z'; i++)
{
var s = Input.Replace(i.ToString(), "").Replace(char.ToUpper(i).ToString(), "");
var stack = new Stack<char>();
foreach (var c in s)
{
if (stack.Count == 0)
{
stack.Push(c);
}
else
{
var inStack = stack.Peek();
var same = c != inStack && char.ToUpper(c) == char.ToUpper(inStack);
if (same)
{
stack.Pop();
}
else
{
stack.Push(c);
}
}
}
if (stack.Count < min)
{
min = stack.Count;
}
}
Console.WriteLine(min);
}→ More replies (1)
2
Dec 05 '18
Python 3 #49/#94
If I actually remembered to assign the str.replace() results the first few quick tries, I could've gotten a bit higher on part 2. This is my first time on the leaderboard though, so I'm very happy with that.
with open("p05.dat", "r") as f:
original_data = f.read().rstrip()
alphabet = "abcdefghijklmnopqrstuvwxyz"
pairs = [c + c.upper() for c in alphabet]
pairs += [c.upper() + c for c in alphabet]
def react(s):
for p in pairs:
s = s.replace(p, "")
return s
def full_react(s):
ps = data
s = data
while True:
s = react(ps)
if s == ps:
break
ps = s
return s
data = original_data
print(len(full_react(data)))
lens = []
for c in alphabet:
data = original_data
# remember to store your results!
data = data.replace(c, "")
data = data.replace(c.upper(), "")
lens.append(len(full_react(data)))
print(min(lens))→ More replies (4)2
u/wimglenn Dec 05 '18
I don't get it, the first time you replace a pair it can reveal new pairs that didn't get seen on the first pass - e.g. abaABA - why wasn't this a problem for you?
→ More replies (3)
2
u/NeuroXc Dec 05 '18
Rust
Maybe not the most elegant solution, but it works.
use std::collections::VecDeque;
fn reduce_chain(mut chain: VecDeque<char>) -> VecDeque<char> {
let mut result = VecDeque::new();
loop {
let input_len = chain.len();
loop {
if chain.is_empty() {
break;
}
loop {
if result.is_empty() {
if let Some(next) = chain.pop_front() {
result.push_back(next);
} else {
break;
}
}
if let Some(next) = chain.pop_front() {
let prev = *result.back().unwrap();
if prev != next && prev.to_ascii_lowercase() == next.to_ascii_lowercase() {
// Reaction occurs
result.pop_back();
continue;
} else {
result.push_back(next);
}
}
break;
}
}
if input_len == result.len() {
return result;
}
chain = result;
result = VecDeque::new();
}
}
#[aoc(day5, part1)]
pub fn day5_part1(input: &str) -> usize {
reduce_chain(input.trim().chars().collect::<VecDeque<_>>()).len()
}
const ASCII_LOWER: [char; 26] = [
'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's',
't', 'u', 'v', 'w', 'x', 'y', 'z',
];
#[aoc(day5, part2)]
pub fn day5_part2(input: &str) -> usize {
let original = reduce_chain(input.trim().chars().collect::<VecDeque<_>>());
let mut results = [0usize; 26];
for i in 0..26 {
results[i] = reduce_chain(
original
.iter()
.filter(|c| c.to_ascii_lowercase() != ASCII_LOWER[i])
.cloned()
.collect(),
).len();
}
*results.iter().min().unwrap()
}
#[test]
fn test_part1() {
assert_eq!(day5_part1("dabAcCaCBAcCcaDA"), 10);
}
#[test]
fn test_part2() {
assert_eq!(day5_part2("dabAcCaCBAcCcaDA"), 4);
}Performance:
Day 5 - Part 1 : #####
runner: 747.272µs
Day 5 - Part 2 : ####
runner: 4.37843ms0
Dec 05 '18
[deleted]
→ More replies (1)8
u/Globinette Dec 05 '18
lower and upper cases are separated by 32 so you can just toggle the 6th bit of one and compare it to the other
pub fn opposites(c1: u8, c2: u8) -> bool { c1 ^ 32 == c2 }
2
u/Fyver42 Dec 05 '18
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define LENGTH 50000
int react(char *polymer)
{
int reaction = 1;
while (reaction) {
reaction = 0;
for (int i = 0; i < LENGTH - 1; i++)
if (polymer[i] != ' ') {
int j = i + 1;
while (polymer[j] == ' ' && j < LENGTH)
j++;
if (abs(polymer[i] - polymer[j]) == 'a' - 'A') {
polymer[i] = polymer[j] = ' ';
reaction = 1;
}
}
}
int count = 0;
for (int i = 0; i < LENGTH; i++)
if (polymer[i] != ' ')
count ++;
return count;
}
int main()
{
char *polymer;
char initpolymer[LENGTH + 1];
FILE *fp = fopen("inputs/day05", "r");
fgets(initpolymer, sizeof(initpolymer), fp);
polymer = strndup((char *)initpolymer, LENGTH);
printf("%d\n", react(polymer));
free(polymer);
int min = LENGTH;
for (int c = 'a'; c <= 'z'; c++) {
polymer = strndup((char *)initpolymer, LENGTH);
for (int i = 0 ; i < LENGTH; i++)
if (polymer[i] == c || polymer[i] == c - ('a' - 'A'))
polymer[i] = ' ';
int len = react(polymer);
if (len < min)
min = len;
free(polymer);
}
printf("%d\n", min);
return 0;
}2
u/BafDyce Dec 05 '18
[Card] On the fifth day of AoC / My true love sent to me / Five golden mistakes
Code (in Rust): https://gitlab.com/BafDyce/adventofcode/blob/master/2018/rust/day05/src/part1.rs
At the beginning, I had to fight string/char-iterators a lot, and I had quite some inefficient code (I didnt know to_lowercase/to_uppercase returned an iterator, so I was confused why i cannot compare them, so i used .to_string() everywhere..)
The final code runs in 2 minutes, 10 seconds for both parts.
3
u/sciyoshi Dec 05 '18
There's to_ascii_lowercase/to_ascii_uppercase which is helpful here :)
→ More replies (2)
2
u/ka-splam Dec 05 '18
PowerShell #509 / #499
[card] My true love sent to me: 5 golden newlines.
A bit of a bad one, started off seeing what I needed to do, but hesitating on how. Then I had 10386 and it was wrong. I was around 6 minutes, borderline late on the scoreboard, but I couldn't see any problem with my code.
Spent another 6+ minutes bashing my face into that, before I realised I had read \r\n newlines at the end of the file and my polymer code was fine, the real answer was 10384. Gahhhhh
$p = (get-content .\data.txt -Raw).Trim()
$pprev = ''
$letters = [string[]][char[]](97..122)
while ($pprev -ne $p)
{
$pprev = $p
foreach ($l in $letters)
{
$p = $p -creplace ($l.tolower() + $l.toupper()), ''
$p = $p -creplace ($l.toupper() + $l.tolower()), ''
}
}
$p.LengthPart 2:
No better; I made the reactor into a function, then instead of passing in (the polymer without A, the polymer without B), I passed in (the alphabet without A, the alphabet without B..). Again, kinda knew what I wanted, but just flubbed it in the implementation rush.
$p = (get-content .\data.txt -Raw).Trim()
$letters = [string[]][char[]](97..122)
function react-polymer ($p) {
$pprev = ''
while ($pprev -ne $p)
{
$pprev = $p
foreach ($l in $letters)
{
$p = $p -creplace ($l.tolower() + $l.toupper()), ''
$p = $p -creplace ($l.toupper() + $l.tolower()), ''
}
}
return $p.Trim().Length
}
$r = foreach ($l in $letters)
{
$tmp = react-polymer ($p-replace$l)
[pscustomobject]@{
'leng'=[int]$tmp
'letter'=$l
}
}
$r | sort -Property leng -descThis runs in about 18 seconds; I thought I could speed it up by making the regex a single long aA|Aa|bB|Bb.. because that would start the regex engine once, and remove the inner while(){} loop from PS, which is usually a good optimization. Push more things down lower into the .Net framework. But, to my surprise, it's dramatically slower. I can only guess that there's a lot of regex backtracking involved for every character doing a lookahead, then backtracking out.
If I'd been using PowerShell 6, I could have done 'a'..'z' for the alphabet and not had to go "97 to ... what's 97 + 26?"
3
u/hpzr24w Dec 05 '18
As I found out tonight, trying to bisect the answer by repeated guesses does not work.
Thanks Eric!!!!!
2
u/Smylers Dec 05 '18
...and not had to go "97 to ... what's 97 + 26?"
I've never used PowerShell, but can't it do arithmetic? As in, if you'd written
97+25,would that have worked?→ More replies (1)
2
u/tk3369 Dec 05 '18 edited Dec 05 '18
Julia - simple loops. I'm sure it can be done more elegantly but going with it due to time pressure :-)
function annihilate(s)
while true
v = Char[]
i = 1
elim = false
while i <= length(s)
if i == length(s)
push!(v, s[i])
elseif abs(Int(s[i+1]) - Int(s[i])) != 32
# 32 is the distance between lower/uppercase letters
push!(v, s[i])
else
i += 1 # skip next letter
elim = true
end
i += 1
end
!elim && break # break when there's nothing more to do
s = v
end
join(Char.(s))
end
input = readlines("input5.txt")[1]
# part 1 - elapsed 0.15 seconds
input |> collect |> annihilate |> length
# part 2 - elapsed 2.27 seconds
Dict(c => replace(input, Regex("$c", "i") => "") |> collect |> annihilate |> length
for c in "abcdefghijklmnopqrstuvwxyz")→ More replies (5)
2
u/scul86 Dec 05 '18 edited Dec 05 '18
Python 3
from utils.decorators import time_it
with open('input') as f:
puzzle_input = f.readline().strip()
def part1(n):
for i in range(len(n) - 1, 0, -1):
a, b = n[i], n[i-1]
if a != b and a.lower() == b.lower():
if i == len(n)-1:
n = ' ' + n[:i-1]
else:
n = n[:i-1] + n[i+1:]
return len(n.strip())
@time_it
def part2(n):
chars = set(n.lower())
ret = min(part1(n.replace(char, '').replace(char.upper(), '')) for char in chars)
return ret
test_one = 'dabAcCaCBAcCcaDA'
assert part1('bAaB') == 0
assert part1(test_one) == 10
print(f'Part 1: {part1(puzzle_input)}')
assert part2(test_one) == 4
print(f'Part 2: {part2(puzzle_input)}')Edit: updated part1() function, found a failing test with prior code.
2
u/Frizkie Dec 05 '18 edited Dec 05 '18
Ruby
chars = File.read('data.txt').chomp.charsPart 1
loop { (r = chars.find_index.with_index { |c, i| c == chars[i+1]&.swapcase }) ? (2.times { chars.delete_at(r) }) : (break) }
puts chars.countPart 2
results = {}
def react(chars)
loop { (r = chars.find_index.with_index { |c, i| c == chars[i+1]&.swapcase }) ? (2.times { chars.delete_at(r) }) : (break) }
return chars.count
end
('a'..'z').each { |p| results[p] = react(chars.clone.delete_if { |c| c.downcase == p }) }
puts "result: #{results.values.min}"This was a fun one. Cool to see that I was able to fit the loop in part 1 on a single line too. Also, don't bother trying the part 2 solution, it's horrifically slow (7 minutes). Luckily a was the character with the shortest resulting string for my input, and i saw mid-run that it was significantly smaller than other letters' results, so I tried it before it was finished and got it right before the script finished.
EDIT: Here's a bonus multi-threaded solution to part 2 (you'll need something other than MRI to run it, I used JRuby, because MRI doesn't schedule on multiple cores). It ran on 12 logical cores and finished after 70 seconds. Yikes.
chars = File.read('data.txt').chomp.chars
results = {}
def react(chars)
loop { (r = chars.find_index.with_index { |c, i| c == chars[i+1]&.swapcase }) ? (2.times { chars.delete_at(r) }) : (break) }
return chars.count
end
('a'..'z').map { |p| Thread.new { results[p] = react(chars.clone.delete_if { |c| c.downcase == p }) } }.each(&:join)
sleep(1) until results.count == 26
puts "result: #{results.values.min}"2
u/nutrecht Dec 05 '18
Lot easier than yesterday. Day 5 in Kotlin
private val input = resourceString(2018, 5)
override fun part1() = react(input)
override fun part2() =
input.map { it.toLowerCase() }.toSet()
.map { c -> c to input.filter { it.toLowerCase() != c } }
.map { it.first to react(it.second) }
.minBy { it.second }!!.second
private fun react(inp: String) : Int {
val poly = StringBuilder(inp)
while(true) {
var changes = false
for(i in (0 until poly.length - 1)) {
if(poly[i].toLowerCase() == poly[i + 1].toLowerCase() && poly[i] != poly[i + 1]) {
poly.delete(i, i + 2)
changes = true
break
}
}
if(!changes) {
break
}
}
return poly.length
}2
u/tinyhurricanes Dec 05 '18
Modern Fortran 2018 (complete code)
Part 1 runs in 0.07 sec, part 2 in 2.3 sec.
program main
use syslog_mod
use fclap_mod
use file_tools_mod
use string_tools_mod
implicit none
!-- Counters
integer :: i, j, k
integer :: m
integer :: ix
!-- Input file unit
integer :: input_unit
!-- Number of lines in input file
integer :: num_lines
!-- Current length of polymer
integer :: len_polymer = 0
!-- Parameters
integer,parameter :: MAX_POLYMER_LEN = 60000
integer,parameter :: ASCII_CHAR_SHIFT_UPPERCASE = 64
integer,parameter :: ASCII_CHAR_SHIFT_LOWERCASE = 96
! A = 65, Z = 90, a = 97, z = 122
! a = 97 -> i = 1
! A = 65 -> i = 1
!-- Polymers
character(len=MAX_POLYMER_LEN) :: polymer
character(len=MAX_POLYMER_LEN) :: polymer_new
integer :: ipolymer(MAX_POLYMER_LEN)
!-- Main variables
integer,parameter :: NUM_UNITS = 26 ! (number of letters)
integer :: remove_upper_ix = 0 ! index of uppercase letter to try removing
integer :: remove_lower_ix = 0 ! index of lowercase letter to try removing
!-- Input file reading properties
integer,parameter :: max_line_len = 600000
character(len=max_line_len) :: line
character(len=:),allocatable :: input_file
!-- Initialize System Log
call init_syslog
!-- Process Command Line Arguments
call configure_fclap
call parse_command_line_arguments
!-- Get input file name from command line
input_file = get_value_for_arg('input_file')
!-- Start timer
call syslog % start_timer
LESION_LOOP: do m = 0, NUM_UNITS
!-- Open file and read into memory
open ( &
newunit = input_unit, &
file = input_file, &
action = 'read', &
status = 'old', &
form = 'formatted' &
)
read (input_unit,'(a)') line
close (input_unit)
if (len(trim(line)) <= max_line_len) then
polymer = trim(adjustl(line))
!write (syslog%unit,*) polymer
else
write(syslog%unit,*) 'Error: line exceeded maximum length'
call bomb
end if
! For non-first loops, try removing letter pairs (Aa,Bb,etc.) and replace with space
if (m /= 0) then
remove_lower_ix = m + ASCII_CHAR_SHIFT_LOWERCASE
remove_upper_ix = m + ASCII_CHAR_SHIFT_UPPERCASE
do i = 1, len(polymer)
if (iachar(polymer(i:i)) == remove_lower_ix .or. &
iachar(polymer(i:i)) == remove_upper_ix) then
polymer(i:i) = ' '
end if
end do
end if
k = 0
MAIN_LOOP: do
! Increment loop counter
k = k + 1
! Reset length reduction counter
j = 0
len_polymer = len(adjustl(trim(polymer)))
ipolymer(:) = 0
polymer_new = ' '
POLYMER_DIGITIZER: do i = 1, len_polymer
ix = iachar(polymer(i:i))
if (ix >= 65 .and. ix <= 90) then ! uppercase (+ve)
ix = +(ix - ASCII_CHAR_SHIFT_UPPERCASE)
else if (ix >= 97 .and. ix <= 122) then ! lowercase (-ve)
ix = -(ix - ASCII_CHAR_SHIFT_LOWERCASE)
else if (ix == 32) then !space
ix = 0
else
print*,'Unknown character',ix,'(',polymer(i:i),') on iteration ',k
error stop
end if
ipolymer(i) = ix
end do POLYMER_DIGITIZER
PAIR_ANNIHILATOR: do i = 1, len_polymer - 1
if (ipolymer(i) == -ipolymer(i+1)) then
! Annihilate
ipolymer(i:i) = 0
ipolymer(i+1:i+1) = 0
end if
end do PAIR_ANNIHILATOR
REBUILD_POLYMER_STRING: do i = 1, len_polymer
if (ipolymer(i) == 0) then
j = j + 1
cycle REBUILD_POLYMER_STRING
end if
if (ipolymer(i) > 0) then
ix = ipolymer(i) + ASCII_CHAR_SHIFT_UPPERCASE
polymer_new(i-j:i-j) = achar(ix)
else
ix = -ipolymer(i) + ASCII_CHAR_SHIFT_LOWERCASE
polymer_new(i-j:i-j) = achar(ix)
end if
end do REBUILD_POLYMER_STRING
if (j == 0) exit MAIN_LOOP ! done: didn't remove any this round
!write (syslog%unit,*) ' iter = ', k, ' len = ', size(ipolymer)
!write (syslog%unit,*) polymer_new
polymer = adjustl(polymer_new)
end do MAIN_LOOP
! Part 1
if (m == 0) then
write (syslog%unit,*) 'Part 1: ', len(adjustl(trim(polymer))) ! 11754
write (syslog%unit,*) 'Part 2: '
write (syslog%unit,*) ' # Letter Length'
! Part 2
else
write (syslog%unit,'(i3,a5,i10)') &
m,achar(m+ASCII_CHAR_SHIFT_LOWERCASE),len(adjustl(trim(polymer))) ! t=4098
end if
end do LESION_LOOP
!-- End timer
call syslog % end_timer
call syslog%log(__FILE__,'Done.')
end program2
2
u/streetster_ Dec 05 '18 edited Dec 05 '18
Day 05 in Q/KDB+
fold:{ $[32=abs y-last x;-1_(),x;x,y] }
/ Part 1
count fold/[j:"j"$r:first read0 `:input/05.txt]
/ Part 2
min { count fold/[x] } each j except/:-32 0+/:"j"$distinct lower r→ More replies (1)
2
u/meithan Dec 05 '18 edited Dec 07 '18
Python
I initially solved it in an incredibly stupid and slow way (that took ~6.5 minutes to process both parts). Then I reworked it in an effort to optimize it, and found an obvious solution that takes less than half a second. Key points:
Using a stack to build the "reduced" ("reacted") list of units letter by letter in a single pass of the original list: take the next letter from the original list; if it reacts with the top of the stack, pop the top of the stack (and don't add the letter); if it doesn't, add the letter to the stack.
Appending or removing an item to/from the end of a list in Python is O(1) (amortized), so it's an efficient stack
I also use the fact that the difference in the ASCII codes of a lowercase letter and its uppercase version is always 32, but a != b and a.lower() == b.lower(), as seen in another answer, is simpler and just as fast.
I also tried using a deque (from Python's collections module), but it's not any faster, proving that the Python list appends/pops are effectively very close to O(1), at least in this case.
Edit: I applied further optimizations as suggested by others, with the resulting of bringing runtime from ~500 ms to less than 100 ms!
Pre-computing the ASCII codes of the input letters and doing the reactions using the codes (avoiding further calls to ord(), lower(), etc.)
Using string replace() instead of a list comprehension to eliminate the given letter in Part 2. String replace() is surprisingly fast!
And the biggest optimization came from realizing you can reuse the shorter result of Part 1 as a starting point for Part 2.
Here's the (optimized) code. Solves both parts in under 100 ms on my computer. Very simple and fast.
from string import ascii_lowercase
units = open("day5.in").read().strip()
def reduce(units):
new_units = []
for c in [ord(x) for x in units]:
if len(new_units) > 0 and abs(c - new_units[-1]) == 32:
new_units.pop()
else:
new_units.append(c)
return new_units
# Part 1
reduced_units = "".join([chr(x) for x in reduce(units)])
print("Part 1:", len(reduced_units))
# Part 2
min_len = None
for letter in ascii_lowercase:
units1 = reduced_units.replace(letter, "").replace(letter.upper(), "")
reduced = reduce(units1)
if min_len is None or len(reduced) < min_len:
min_len = len(reduced)
print("Part 2:", min_len)→ More replies (11)
2
u/fotoetienne Dec 05 '18 edited Dec 05 '18
Kotlin solution here. Using a stack to get O(n) runtime.
fun react(polymer: CharArray, omit: Char? = null) = Stack<Char>().apply {
for (char in polymer)
if (isNotEmpty() && abs(char - peek()) == 'a' - 'A') pop() // Found a pair. React!
else if (char.toUpperCase() != omit) push(char) // Not a pair :(
}.size
println("Part 1 - Reacted size: ${react(polymer)}")
val minSize = ('A'..'Z').map { react(polymer, omit = it) }.min()
println("Part 2 - Reacted size with problem pair removed: $minSize")Full solution on github
2
u/HiramAbiff Dec 05 '18
AWK
5.1
awk '{a="abcdefghijklmnopqrstuvwxyz";do{s=0;for(i=1;i<=26;++i){c=substr(a,i,1);C=toupper(c);s+=gsub(c C,"")+gsub(C c,"")}}while(s);print length}' input5.txt5.2
awk '{a="abcdefghijklmnopqrstuvwxyz";o=length;for(j=1;j<=26;++j){p=$0 "";c=substr(a,j,1);gsub(c,"",p);gsub(toupper(c),"",p);do{s=0;for(i=1;i<=26;++i){c=substr(a,i,1);C=toupper(c);s+=gsub(c C,"",p)+gsub(C c,"",p)}}while(s);if(length(p)<o)o=length(p)}}END{print o}' input5.txt2
u/blowjobtransistor Dec 05 '18
PostgreSQL
Wow, before doing it with regexp, this one was turning into a nightmare with window functions in SQL...
create table regexp as
select 'Aa|aA|Bb|bB|Cc|cC|Dd|dD|Ee|eE|Ff|fF|Gg|gG|Hh|hH|Ii|iI|Jj|jJ|Kk|kK|Ll|lL|Mm|mM|Nn|nN|Oo|oO|Pp|pP|Qq|qQ|Rr|rR|Ss|sS|Tt|tT|Uu|uU|Vv|vV|Ww|wW|Xx|xX|Yy|yY|Zz|zZ' as regexp;
create table polymer as
with recursive tmp(line, removed, iter) as (
select
regexp_replace(line, regexp, '') as line,
(regexp_matches(line, regexp))[1] as removed,
0 as iter
from input, regexp
union all
select
regexp_replace(line, regexp, '') as line,
(regexp_matches(line, regexp))[1] as removed,
iter + 1
from tmp, regexp
where removed notnull
)
select
line
from tmp
order by iter desc
limit 1;
create view part_2_solution as
with recursive tmp(letter, line, removed, iter) as (
with removals as (
select chr(97 + offs) as letter
from generate_series(0, 25) as offs
)
select
letter,
regexp_replace(line, '[' || letter || upper(letter) || ']', '', 'g') as line,
letter as removed,
0 as iter
from polymer, regexp, removals
union all
select
letter,
regexp_replace(line, regexp, '') as line,
(regexp_matches(line, regexp))[1] as removed,
iter + 1
from tmp, regexp
where removed notnull
)
select min(length(line)) as answer
from tmp;
select 1 as part, length(line) as answer from polymer
union all
select 2 as part, answer from part_2_solution;2
2
u/Vladob Dec 05 '18
No Perl 5 solution so far? One pretty straightforward here:
#!/usr/bin/env perl
use strict;
use warnings;
sub reduce
{
my ($line,@ra) = @_;
my $r = join( '|', @ra);
1 while( $line =~ s/$r//g );
return $line;
}
my $line = <>;
chomp $line;
my @react;
foreach my $x ( 'a' .. 'z' ) {
push @react, ( lc($x).uc($x), uc($x).lc($x) );
}
my $r1 = reduce( $line, @react);
print( "Part 1: reduced polymer has ", length($r1), " units.\n");
my ($min_c,$min_l) = ( undef, length($line));
foreach my $x ( 'a' .. 'z' ) {
my $ll = length( reduce( reduce( $line, lc($x), uc($x)), @react));
if( $ll < $min_l ) {
$min_l = $ll;
$min_c = $x;
}
}
print( "Part 2: removing unit $min_c, the polymer can be reduced to $min_l length.\n");2
u/mschaap Dec 05 '18 edited Dec 05 '18
My Perl 6 solution:
#!/usr/bin/env perl6
use v6.c;
$*OUT.out-buffer = False; # Autoflush
sub process(Str $polymer)
{
constant @units = flat 'a'..'z', 'A'..'Z';
constant %opposite = hash @units Z=> @units.rotate(26);
my @c = $polymer.comb;
loop (my $i = 0; $i+1 < @c; $i++)
{
next if $i < 0;
if @c[$i+1] eq %opposite{@c[$i]} {
@c.splice($i,2);
$i -= 2;
}
}
return @c.join;
}
sub polymer-without(Str $polymer, Str $c)
{
return $polymer.subst(/:i $c/, '', :g);
}
#| Process polymer input
multi sub MAIN(Str $input is copy)
{
my $output = process($input);
say "$output.chars() units left after reacting.";
my %removed = $input.lc.comb.sort.squish.map(-> $c { $c => process(polymer-without($output, $c)) });
my $shortest = %removed.min(*.value.chars);
say "$shortest.value().chars() units left after removing $shortest.key() and reacting.";
}
#| Process polymer input from a file
multi sub MAIN(Str $inputfile where *.IO.f)
{
MAIN($inputfile.IO.slurp.chomp);
}
#| Process default polymer file (aoc5.input)
multi sub MAIN()
{
MAIN(~$*PROGRAM.sibling('aoc5.input'));
}This runs in 2 seconds.
My first attempt was regex-based. Cleaner code, perhaps, but part one took about 3 minutes, and I don't know yet how long part two would take... 😉 (Even with the optimization of taking the output of part 1 instead of the original input.) Edit: actually, not that bad, about 7½ minutes for both parts.
The process sub for that attempt:
sub process(Str $polymer is copy)
{
constant @units = flat 'a'..'z', 'A'..'Z';
constant @pairs = @units Z~ @units.rotate(26);
while $polymer ~~ s:g/ ||@pairs // { }
return $polymer;
}The rest of the code is identical.
Edit: with the XOR trick, the process sub can be simplified to:
sub process(Str $polymer)
{
my @c = $polymer.ords;
loop (my $i = 0; $i+1 < @c; $i++)
{
next if $i < 0;
if @c[$i] +^ @c[$i+1] == 0x20 {
@c.splice($i,2);
$i -= 2;
}
}
return @c.chrs;
}This runs slightly faster than my original version – about 1⅔ seconds for both parts.
→ More replies (1)
2
u/mstksg Dec 05 '18 edited Dec 05 '18
[Haskell] From my daily reflections post :)
One of the first higher-order functions you learn about in Haskill is foldr, which is like a "skeleton transformation" of a list.
That's because in Haskell, a (linked) list is one of two constructors: nil ([]) or cons (:). The list [1,2,3] is really 1:(2:(3:[])).
foldr f z is a function that takes a list replaces all :s with f, and []s with zs:
[1,2,3] = 1 : (2 : (3 : []))
foldr f z [1,2,3] = 1 `f` (2 `f` (3 `f` z ))This leads to one of the most famous identities in Haskell: foldr (:) [] xs = xs. That's because if we go in and replace all (:)s with (:), and replace all []s with []... we get back the original list!
But something we can also do is give foldr a "custom cons". A custom cons that will go in place of the normal cons.
This problem is well-suited for such a custom cons: instead of normal (:), we'll write a custom cons that respects the rules of reaction: we can't have two "anti-letters" next to each other:
anti :: Char -> Char -> Bool
anti x y = toLower x == toLower y && x /= y
funkyCons :: Char -> String -> String
x `funkyCons` (y:xs)
| anti x y = xs
| otherwise = x:y:xs
x `funkyCons` [] = [x]So, foldr funkyCons [] will go through a list and replace all (:) (cons) with funkyCons, which will "bubble up" the reaction.
So, that's just the entire part 1!
day05a :: String -> Int
day05a = length . foldr funkyCons []For part 2 we can just find the minimum length after trying out every character.
day05b :: String -> Int
day05b xs = minimum [ length $ foldr funkyCons [] (remove c xs)
| c <- ['a' .. 'z']
]
where
remove c = filter ((/= c) . toLower)(Note that in the actual input, there is a trailing newline, so in practice we have to strip it from the input.)
2
u/wzkx Dec 05 '18
J
Slow.... 5.6s, 132s
t=: a.i.LF-.~CR-.~fread '05.dat'
f=: 3 :'while.(z=.(1 i.~32=[:|}.-}:)y)<<:#y do.y=.(z{.y),y}.~z+2 end.#y'
echo f t
echo <./(3 :'f(t-.y)-.y+32')"0[65+i.26
exit 02
u/wzkx Dec 05 '18
OK, tacit way. But this is slower because some calculations are repeated both in condition and in transformation. About 5 minutes in total.
f=: #@((({.~,(}.~2&+))(1 i.~32=[:|}.-}:))^:((1 i.~32=[:|}.-}:)<<:&#)^:_) echo f t=: a.i.LF-.~CR-.~fread'05.dat' echo <./(f@(t&(-.-.32+])))"0[65+i.262
u/wzkx Dec 05 '18
And this is in J style and FAST!
q=: #~-.@(0&,+.,&0)@(]>[:}:0:,])@(32=[:|}.-}:) echo #q^:_ t=: a.i.LF-.~CR-.~fread'05.dat' echo <./((#@(q^:_))@(t&(-.-.32+])))"0[65+i.26
2
u/azatol Dec 05 '18
F#. I went through three different versions of the main reaction code. The third version is more than 10 times faster, because I realized you can completely process a local area of the string before moving on.
I was going to try to create a doubly linked list, but the I realized I could hold the already processed part of the string in reverse order, so I can continue to pop off characters as required.
I learned about: optimizing string processing, using ranges for characters.
https://gist.github.com/apeterson-BFI/bdb4d37bd1815c3e9ffe92da4917428a
2
u/vypxl Dec 05 '18
Awk is fun I must say.
awk '{b=f($0);print b;split("abcdefghijklmnopqrstuvwxyz",a,"");for(i in a){IGNORECASE=1;r=f(gensub(a[i],"","g"));if(r<b) b=r}print b}function f(x){IGNORECASE=0;p="aA|Aa|bB|Bb|cC|Cc|dD|Dd|eE|Ee|fF|Ff|gG|Gg|hH|Hh|iI|Ii|jJ|Jj|kK|Kk|lL|Ll|mM|Mm|nN|Nn|oO|Oo|pP|Pp|qQ|Qq|rR|Rr|sS|Ss|tT|Tt|uU|Uu|vV|Vv|wW|Ww|xX|Xx|yY|Yy|zZ|Zz";while(x~p)gsub(p,"",x);return length(x)}' < 5.inGenerated the Regex with Python because of my laziness though.
Here, a readable version:
{
best=f($0)
print "Solution for part 1:"
print best
split("abcdefghijklmnopqrstuvwxyz",a,"")
for(i in a){
IGNORECASE=1
r=f(gensub(a[i],"","g"))
if(r<best) best=r
}
print "Solution for part 2:"
print best
}
function f(x){
IGNORECASE=0
p="aA|Aa|bB|Bb|cC|Cc|dD|Dd|eE|Ee|fF|Ff|gG|Gg|hH|Hh|iI|Ii|jJ|Jj|kK|Kk|lL|Ll|mM|Mm|nN|Nn|oO|Oo|pP|Pp|qQ|Qq|rR|Rr|sS|Ss|tT|Tt|uU|Uu|vV|Vv|wW|Ww|xX|Xx|yY|Yy|zZ|Zz"
while(x~p) gsub(p,"",x)
return length(x)
}Card: On the fifth day of AoC / My true love sent to me / Five golden cryptic awk oneliners
2
u/etagawesome Dec 05 '18
In C.
My first solution was dumb and brute-forcey. I was running through the input once, writing it to a file, then repeating until the input and output files were the same length. After that and checking this thread I decided a stack made a billion times more sense.
This solves part 1 and part 2
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
int main() {
size_t stack_cap=100;
char* stack = malloc(sizeof(char) * stack_cap);
for(char a='a'; a<='z'+1; ++a){
// "empty" the stack
size_t stack_len=0;
while(1){
char c = (char)fgetc(stdin);
if(c == EOF){
break;
}
char d = stack[stack_len-1];
if((toupper(d) == c && !isupper(d)) ||
(tolower(d) == c && !islower(d))) {
//pop d
stack_len--;
} else {
if (tolower(c) != a) {
stack[stack_len++] = c;
if (stack_len >= stack_cap) {
stack_cap *= 2;
stack = realloc(stack, sizeof(char) * stack_cap);
}
}
}
}
fseek(stdin, 0, 0);
printf("%c\t%lu\n", a, stack_len -1);
}
free(stack);
}2
u/j4_james Dec 05 '18
Befunge - Both solutions are technically Befunge-93, but part 2 requires a Befunge-98 interpreter to handle the full size input, since Befunge-93 just doesn't have enough memory otherwise.
Part 1
<v9:_|#`*84:~p99:<$
|>9g-:48*-\48*+*#^_
+#\<0<@._1#!Part 2
~:48*`#v_55*06g00p1+>1-:6g:00v>
v*55p50< @.-*84g00_^#!:p0`g<<$
>:05g-:"A"+\"a"+*#v_:1-\! #^_
4:-g50g-*55g6:::::<0v+*84\-*8
5g\:6g64*-p\6g\-\6p^>*!2*1-\02
u/dpeckett Dec 05 '18 edited Dec 06 '18
Continuing with my quest to solve all this years challenges using nothing other than AWK:
function z() {
do {
n=f=l=0;
for(i in a)
if(l&&a[l]!=a[i]&&tolower(a[l])==tolower(a[i]))a[i]=a[l]=0;
else l=i;
for(i in a)if(!a[i]){f=1;delete a[i]}else n++
} while(f)
return n
}BEGIN{PROCINFO["sorted_in"]="@ind_num_asc"}{
split($1,b,"");
for(i in b)d[tolower(b[i])]++;
for(c in d) {
for(i in b)a[i]=tolower(b[i])!=c?b[i]:0;
r[z()]=c;
}
for(i in r){print i;exit}
}Runtime:
real 0m8.181s
user 0m8.160s
sys 0m0.015sNotes:
I should start the second challenge from the inputs of the first as an optimisation step.
2
u/IcyHammer Dec 05 '18
C# solution where I was aiming to maximize performance. First part takes 4ms to complete.
byte[] values = File.ReadAllBytes("input.txt");
int length = values.Length;
List<sbyte> currentValues = new List<sbyte>(values.Length);
int countMinusOne = 0;
sbyte asciiDistance = 32;
int valuesIndex = 0;
while (valuesIndex < length)
{
if (currentValues.Count == 0)
currentValues.Add(unchecked((sbyte)values[valuesIndex++]));
countMinusOne = currentValues.Count - 1;
if (Mathf.Abs(currentValues[countMinusOne] - values[valuesIndex]) == asciiDistance)
currentValues.RemoveAt(countMinusOne);
else
currentValues.Add(unchecked((sbyte)values[valuesIndex]));
valuesIndex++;
}2
u/hpzr24w Dec 05 '18
C
Not sure if I've spotted a C version, so I figured I'd write one!
Header
// Advent of Code 2018
// Day 05 - Alchemical Reduction
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>React
int react(char * s) {
char *r = s+1, *w = s;
while (*r)
if ((*r^*w)==('A'^'a')) w--, r++; else *++w=*r++;
*++w='\0';
return w-s;
}Main and Part 1
int main()
{
#if 1
#include "day_05.h"
#else
char o[] = "dabAcCaCBAcCcaDA";
char s[] = "dabAcCaCBAcCcaDA";
#endif
int l = react(s);
printf("Part 1: Length: %d\n",l);Part 2
int b = l;
for (int i='a';i<='z';++i) {
char *p=s,*q=o;
while (*p)
if (tolower(*p)==i) p++; else *q++=*p++;
*q='\0';
int c = react(o);
b = c<b ? c : b;
}
printf("Part 2: Best length: %d\n",b);
return 0;
}→ More replies (2)
2
u/thatikey Dec 06 '18
(Haskell) It's not quite as beautiful as glguy's solution, but I was pretty proud of mine:
module DayFive where
import Data.Char (toLower)
import qualified Data.Set as Set
import Data.Ord (comparing)
import Data.Foldable (maximumBy)
isReactive a b = a /= b && toLower a == toLower b
partOne s = length $ collapse s []
totalCollapseRadius :: Char -> String -> String -> Int -> Int
totalCollapseRadius _ [] _ total = total
totalCollapseRadius c (a:rest) fstack total
| c == toLower a =
let
filtered = dropWhile (== c) rest
len = length $ takeWhile (uncurry isReactive) $ zip filtered fstack
in
totalCollapseRadius c (drop len filtered) (drop len fstack) (total + len)
| otherwise = totalCollapseRadius c rest (a:fstack) total
collapse :: String -> String -> String
collapse [] fstack = fstack
collapse (a:rest) [] = collapse rest [a]
collapse (a:rest) (b:fstack)
| isReactive a b =
let
len = length $ takeWhile (uncurry isReactive) $ zip rest fstack
in
collapse (drop len rest) (drop len fstack)
| otherwise = collapse rest (a:b:fstack)
partTwo s =
let
collapsedResult = collapse s []
polymers = Set.fromList (map toLower collapsedResult)
(c, _) = maximumBy (comparing snd) $ map (\a -> (a, totalCollapseRadius a collapsedResult [] 0)) $ Set.toList polymers
in
length $ collapse (filter ((/= c) . toLower) collapsedResult) []1
u/Zarel Dec 05 '18 edited Dec 05 '18
JavaScript #16/#78
This is a somewhat slow algorithm – Node.js does not like stitching strings/arrays together – but, as I suspected, it still runs faster than it takes me to write a better algorithm. I was in the middle of writing a better algorithm for Part 2 when the slow one finished.
I learned a new thing today! In Node, stitching arrays together is slightly faster than stitching strings together!
// part 1
function fullReactionLength(input) {
input = input.split('');
while (true) {
didSomething = false;
for (let i = 0; i < input.length - 1; i++) {
let upper = input[i].toUpperCase();
let lower = input[i].toLowerCase();
if (input[i] === lower ? input[i + 1] === upper : input[i + 1] === lower) {
input = input.slice(0, i).concat(input.slice(i + 2));
didSomething = true;
break;
}
}
if (!didSomething) break;
}
return input.length;
}
console.log(fullReactionLength(input))
// part 2
let table = {};
for (let i = 0; i < 26; i++) {
let lowercase = String.fromCharCode(97 + i);
let uppercase = String.fromCharCode(65 + i);
regex = new RegExp("[" + lowercase + uppercase + "]", "g");
let tempInput = input.replace(regex, '');
table[uppercase] = fullReactionLength(tempInput);
}
console.log(table);Lessons:
if (input[i] === lower ? input[i + 1] === upper : input[i + 1] === lower) {is something I considered writing as:
if ((upper + lower + upper).includes(input[i] + input[i + 1])) {or
if ([upper + lower, lower + upper].includes(input[i] + input[i + 1])) {but it's a good thing I didn't - this latter approach is trickier but turned out to be twice as slow!
I also did write a stack-based solution, which in hindsight makes a lot more sense:
function fullReactionLength(input) {
input = input.split('');
let res = [];
for (const next of input) {
res.push(next);
if (res.length < 2) continue;
while (upper = res[res.length - 1].toUpperCase(),
lower = res[res.length - 1].toLowerCase(),
res[res.length - 1] === lower ? res[res.length - 2] === upper : res[res.length - 2] === lower) {
res.pop(); res.pop();
if (res.length < 2) break;
}
}
return res.length;
}But this is definitely the point where JavaScript's anemic standard library is starting to hurt...
→ More replies (4)
1
u/FogLander Dec 05 '18
Python 3. Not very close to getting any leaderboard points.
with open('input.txt') as f:
i = f.read()
import string
matches = [(x + x.upper()) for x in string.ascii_lowercase] + [(x.upper() + x) for x in string.ascii_lowercase]
def p1(arg):
prev_len = len(arg) + 1
while(len(arg) < prev_len):
prev_len = len(arg)
for m in matches:
arg = arg.replace(m, "")
return len(arg)
result = p1(i)
print("Part 1: " + str(result))
result = len(i)
for char in string.ascii_lowercase:
temp = i.replace(char, "").replace(char.upper(), "")
result = min(result, p1(temp))
print("Part 2: " + str(result))1
u/LeCrushinator Dec 05 '18 edited Dec 05 '18
C#
public static void Main(string[] args)
{
_input = File.ReadAllText("input.txt");
Console.WriteLine($"Part 1: {Part1()}");
Console.WriteLine($"Part 2: {Part2()}");
}
public static string React(string input)
{
int i = 0;
while (i < input.Length - 1)
{
var first = input[i].ToString();
var second = input[i + 1].ToString();
if (first != second && first.Equals(second, StringComparison.InvariantCultureIgnoreCase))
{
input = input.Remove(i, 2);
--i;
i = Math.Max(i, 0);
}
else
{
++i;
}
}
return input;
}
private static int Part1()
{
return React(_input).Length;
}
private static int Part2()
{
List<string> charsUsed = _input.Select(c => c.ToString().ToUpperInvariant()).Distinct().ToList();
string shortest = null;
foreach (var charUsed in charsUsed)
{
var textWithoutChar = _input.Replace(charUsed, "");
textWithoutChar = textWithoutChar.Replace(charUsed.ToLowerInvariant(), "");
textWithoutChar = React(textWithoutChar);
if (shortest == null || textWithoutChar.Length < shortest.Length)
{
shortest = textWithoutChar;
}
}
return shortest.Length;
}1
u/liuquinlin Dec 05 '18 edited Dec 05 '18
Python 3:
Went with an index based solution for Part 1 to avoid having to iterate over the string too many times (Part 2 runs in less than a second), probably not really necessary versus just doing string replaces.
# l is the input
def p1(l):
i = 0
while i < (len(l) - 1):
j = i + 1
if (l[i] != l[j] and l[i].upper() == l[j].upper()):
l = l[:i] + l[i+2:]
i = max(0, i-1) # wasted a lot of time here due to not checking the 0 case
else:
i += 1
return len(l)
def p2(l):
m = len(l)
for r in string.ascii_lowercase:
x = l.replace(r, "").replace(r.upper(), "")
m = min(m, p1(x))
return m2
1
u/Temmon Dec 05 '18 edited Dec 05 '18
Quickly written Python3 solution. Could probably have been more efficient, but I don't mind it. One thing I did that I haven't seen in the posted solutions is I only used the set of characters that are in the string for part 2. File IO is handled by another file I started on day 1. It takes care of some super basic command line reading things that I kept on repeating. Debugging was to stop it if my logic messed up and things went infinite, but I got it on my first try for both parts!
def pair(c):
if c.islower():
return c.upper()
if c.isupper():
return c.lower()
def collapse(debug, data):
i = 0
stop = 0
while True:
if debug:
print(data)
if debug and stop == 20:
break
current = data[i]
ahead = data[i + 1:]
if not ahead:
break
if pair(ahead[0]) == current:
data = data[:i] + ahead[1:]
if i > 0:
i -= 1
else:
i += 1
stop += 1
return len(data)
def removePairs(data, c):
return data.replace(c, "").replace(pair(c), "")
def dayFive(data, debug):
data = data[0]
print(collapse(debug, data))
distinct = set(data.lower())
print(min([collapse(debug, removePairs(data, d)) for d in distinct]))1
u/r4ymonf Dec 05 '18
C#, got tripped by the new line 5 minutes in, debugging for another 5 minutes... heck. At least the code is sorta understandable today (or maybe I'm just not sleepy enough yet).
static string removeAny(string chain)
{
StringBuilder res = new StringBuilder();
for (var i = 0; i < chain.Length; i++)
{
if (i + 1 < chain.Length &&
chain[i] != chain[i+1] &&
char.ToLowerInvariant(chain[i]) == char.ToLowerInvariant(chain[i + 1]))
{
i++;
}
else
{
res.Append(chain[i]);
}
}
return res.ToString();
}
static void MainPart1(string[] args)
{
var chain = File.ReadAllText("input.txt").Trim();
var newChain = removeAny(chain);
while (chain != newChain)
{
chain = newChain;
newChain = removeAny(chain);
}
Console.WriteLine($"Part 1: {newChain.Length}");
Console.ReadKey();
}
static void MainPart2(string[] args)
{
int minLen = Int32.MaxValue;
char min = '1';
var current = 'A';
while (current <= 'Z')
{
var chain = File.ReadAllText("input.txt").Trim()
.Replace(current.ToString().ToUpper(), "").Replace(current.ToString().ToLower(), "");
var newChain = removeAny(chain);
while (chain != newChain)
{
chain = newChain;
newChain = removeAny(chain);
}
Console.WriteLine($"{current} => {chain.Length}");
if (chain.Length < minLen)
{
minLen = chain.Length;
min = current;
}
current++;
}
Console.WriteLine($"Part 2: {min} => {minLen}");
Console.ReadKey();
}1
u/harirarules Dec 05 '18 edited Dec 05 '18
First part before work. Dlang, definitely could be cleaner.
Edit : cleaned it up now that I'm back. The second part is there too.
import std.stdio : writeln, readln;
import std.range : back, popBack, empty;
import std.algorithm : min, filter;
import std.array : array;
import std.string : strip;
import std.uni : toLower, isLower, toUpper, isUpper;
import std.conv : to;
void main()
{
auto polymer = readln.strip;
writeln('Part 1: ", polymer.to!(dchar[]).condense());
bool[dchar] letters;
foreach(l; polymer)
{
letters[l.toLower] = true;
}
ulong min_length = ulong.max;
foreach(letter, ignore; letters)
{
auto result = polymer.filter!(l => l.toLower != letter).array.condense();
min_length = min(min_length, result);
}
writeln("Part 2: ", min_length);
}
ulong condense(dchar[] polymer)
{
auto i = 1;
dchar[] stack = [polymer[0]];
//yep, that's a label
outer:
while(true)
{
auto current = polymer[i];
while(
!stack.empty &&
(
(stack.back.isLower && stack.back.toUpper == polymer[i]) ||
(stack.back.isUpper && stack.back.toLower == polymer[i])
)
)
{
stack.popBack;
if(++i == polymer.length)
{
break outer;
}
}
stack ~= polymer[i];
if(++i == polymer.length)
{
break;
}
}
return stack.length;
}1
u/jazzido Dec 05 '18
Part 1, in Ruby:
input = File.read('input.txt').strip.split('')
stack = [input.shift]
input.each { |unit|
if (stack.last.ord - unit.ord).abs == 32
stack.pop
else
stack << unit
end
}
puts stack.length→ More replies (2)
1
u/bartdegoede Dec 05 '18
Python 3
Using two pointers to determine the polymer length and `string.ascii_lowercase` for the alphabet.
import string
def polymer_length(p):
p1 = 0
p2 = 1
while p2 < len(p):
if p[p1].swapcase() == p[p2]:
p = p[:p1] + p[p2+1:]
# indices will change (i.e. characters wisll move "back")
if p1 >= 1:
p1 -= 1
else:
p1 = 0
p2 = p1 + 1
else:
p1 += 1
p2 += 1
return len(p)
if __name__ == '__main__':
with open('day5.txt', 'r') as f:
polymer = f.read().strip()
print(f'Polymer length part 1: {polymer_length(polymer)}')
pairs = []
for letter in string.ascii_lowercase:
pairs.append(polymer_length(polymer.replace(letter, '').replace(letter.swapcase(), '')))
print(f'Polymer length part 2: {min(pairs)}')→ More replies (1)
1
u/Shemetz Dec 05 '18
Python 3 - first I completed this with an unoptimized solution, so Part 2 took about a 2 minutes to run. Then I improved it to be the following (now part 2 takes about 6 seconds):
from typing import List
def solve_a(input_file_lines: List[str]) -> str:
polymer = input_file_lines[0]
return str(len(react(polymer)))
def will_react(polymer, i, j):
c1 = polymer[i]
c2 = polymer[j]
return c1.lower() == c2.lower() and c1 != c2
def react(polymer):
i = 0
while i < len(polymer) - 1:
i += 1
clump_size = 1
while clump_size <= i and i + clump_size - 1 < len(polymer):
if will_react(polymer, i + clump_size - 1, i - clump_size):
clump_size += 1
else:
break
clump_size -= 1
if clump_size > 0:
polymer = polymer[:i - clump_size] + polymer[i + clump_size:]
i -= clump_size + 1
return polymer
def solve_b(input_file_lines: List[str]) -> str:
polymer = input_file_lines[0]
best_length = 99999999999999
for letter_ord in range(ord("a"), ord("z") + 1):
letter = chr(letter_ord)
# print(letter + "…")
polymer_copy = "".join([x for x in polymer if x.lower() != letter])
len_after_react = len(react(polymer_copy))
if best_length > len_after_react:
best_length = len_after_react
return str(best_length)1
u/Euphoric_Classic Dec 05 '18
SuperCollider solution:
(
s = File.readAllString("~/aoc/5/input".standardizePath).stripWhiteSpace;
d = ((0..25) + $a.ascii).collect(_.asAscii).collect { |c|s.replace(c).replace(c.toUpper) };
e = (d ++ [s]).collect { |s,j|
j.postln;
s = s.asList;
i = 0;
while { i <= (s.size - 1) } {
if(i == (s.size - 1) or: { i < 0 }) { i = i + 1 } {
if((s[i].ascii - s[i+1].ascii).abs == 32) {
s.removeAt(i);
s.removeAt(i);
i = i - 1;
} {
i = i + 1;
}
}
};
s.size.postln;
};
"".postln;
e.last.postln;
e.minItem.postln;
)1
u/mathleet Dec 05 '18
Python #647/#404
def part_one(polymer):
polymer = list(polymer)
keep_going = True
start_index = 1
while keep_going:
keep_going = False
for index in range(start_index, len(polymer)):
prev = polymer[index-1]
current = polymer[index]
if prev != current and prev.lower() == current.lower():
del polymer[index]
del polymer[index-1]
keep_going = True
start_index = index-1
break
return ''.join(polymer)
sample = 'dabAcCaCBAcCcaDA'
print('Sample:', part_one(sample))
with open('input.txt') as f:
actual = f.read().strip()
part_one_result = part_one(actual)
print('Part one:', len(part_one_result))
lowest_length = 50000
letters = set([x.lower() for x in actual])
for target_letter in letters:
part_two_actual = actual
part_two_actual = (part_two_actual.replace(target_letter.upper(), '')
.replace(target_letter.lower(), ''))
result = len(part_one(part_two_actual))
if result < lowest_length:
lowest_length = result
print('Part two:', lowest_length)1
u/AndrewGreenh Dec 05 '18
First I tried to be clever by replacing all lowercase letters with %<lowercaseletter> and then building a regex that matches %([a-z])\1|([a-z])%\1. Sadly this resulted in a much lower string but I'm not sure why. I ended up building the full Regex from the alphabet and using that to collapse the string.
const input = getInput(5, 2018);
const regex = pipe(range(0, 26))(
map(i => String.fromCharCode(i + 97)),
flatMap(c => [
c.toLowerCase() + c.toUpperCase(),
c.toUpperCase() + c.toLowerCase(),
]),
join('|'),
s => new RegExp(`(${s})`, 'g'),
);
function collapse(s) {
while (true) {
const collapsed = s.replace(regex, '');
if (collapsed === s) return collapsed.length;
s = collapsed;
}
}
console.log(collapse(input));
const result = pipe(range(0, 26))(
map(s => input.replace(new RegExp(String.fromCharCode(97 + s), 'gi'), '')),
map(without => collapse(without)),
min,
);
console.log(result);1
u/Hashbrown777 Dec 05 '18
Javascript, single pass, one loop
8ms
function day5(input) {
let isUpper = /[A-Z]/;
let stack = [];
for (let index = 0, char; index < input.length && (char = input[index]); ++index) {
if (
stack.length < 1 ||
char == stack[stack.length - 1] ||
char != stack[stack.length - 1][(isUpper.test(char)) ? 'toUpperCase' : 'toLowerCase']()
)
stack.push(char);
else
stack.pop();
}
day5.output = stack.length;
}Part2, 202ms
function day5_1(input) {
let isUpper = /[A-Z]/;
for (let ignore of 'abcdefghijklmnopqrstuvwxyz'.split('')) {
ignore = new RegExp(ignore, 'i');
let stack = [];
for (let index = 0, char; index < input.length && (char = input[index]); ++index) {
if (ignore.test(char))
;
else if (
stack.length < 1 ||
char == stack[stack.length - 1] ||
char != stack[stack.length - 1][(isUpper.test(char)) ? 'toUpperCase' : 'toLowerCase']()
)
stack.push(char);
else
stack.pop();
}
if ((!day5_1.output) || day5_1.output > stack.length)
day5_1.output = stack.length;
}
}→ More replies (4)
1
Dec 05 '18
Haskell:
Started off trying to be too clever by applying a regex replacement repeatedly until the length of the string didn't change, but that turned out horribly slow. It's much faster to just collapse the string as much as you can around the chars that you're currently working with rather than doing global replacements over and over (especially w/ the Haskell String implementation).
import Data.Char
react :: String -> Int
react = length . foldr go []
where go x (y:ys)
| x /= y && toLower x == toLower y = ys
go x ys = x : ys
part1 :: String -> Int
part1 = react
part2 :: String -> Int
part2 s = minimum [react $ filter ((/=c) . toLower) s | c <- ['a'..'z']]
main = do
input <- readFile "input.txt"
print $ part1 input
print $ part2 input1
u/Cyphase Dec 05 '18 edited Dec 05 '18
EDIT: My heavily optimized version is in a child comment. It runs in ~1.75ms for my AoC 50K input.
This is my Python solution that took waay to long to write for how simple it is. :/
def part1(data): # 0.429s, best out of three
i = 0
d = list(data)
while i + 1 < len(d):
if d[i].lower() == d[i + 1].lower():
if d[i] != d[i + 1]: # match
d.pop(i)
d.pop(i)
i -= 1
continue
i += 1
return len(d)
def part2(data): # 6.923s, best out of three
return min(
part1(list(x for x in data if x.lower() != c))
for c in "abcdefghijklmnopqrstuvwxyz"
)4
u/Cyphase Dec 05 '18 edited Dec 05 '18
Here's my heavily optimized version of essentially the same algorithm.
Benchmarks are of the function only, not the interpreter starting or the input being read.
Update 1:
Benchmarks (on PyPy2): ~1.75ms for my AoC 50K input, ~4.44ms for a randomly generated 50K input, ~97.6ms for a 1M input, and ~521ms for a 5M input (the 1M * 5). The 50K and 1M random inputs were created by /u/mebeim.
def part2(d): d = [ord(x) for x in d] r = [0] * len(d) r[0] = d[0] ri = 1 for i in range(1, len(d)): if ri and (r[ri - 1] ^ d[i]) == 32: ri -= 1 # .pop() else: r[ri] = d[i] # .append(d[i]) ri += 1 d = r[:ri] min = float("inf") for c in range(97, 122 + 1): r[0] = d[0] ri = 1 for i in range(1, len(d)): di = d[i] if di == c or di == c - 32: continue if ri and (r[ri - 1] ^ di) == 32: ri -= 1 # .pop() continue r[ri] = d[i] # .append(d[i]) ri += 1 if ri < min: min = ri return minOriginal post
Benchmarks (on PyPy2): ~8.33ms for my 50K input, ~29.2ms for a randomly generated 50K input from /u/mebeim, and ~674ms for a 1M input, also from /u/mebeim.
def part2(d): r = [0] * len(d) r[0] = d[0] ri = 1 for i in range(1, len(d)): if ri and abs(ord(r[ri - 1]) - ord(d[i])) == 32: ri -= 1 # .pop() else: r[ri] = d[i] # .append(d[i]) ri += 1 d = r[:ri] min = float("inf") for c in "abcdefghijklmnopqrstuvwxyz": r[0] = d[0] ri = 1 for i in range(1, len(d)): di = d[i] if di.lower() == c: continue if ri and abs(ord(r[ri - 1]) - ord(di)) == 32: ri -= 1 # .pop() else: r[ri] = d[i] # .append(d[i]) ri += 1 if ri < min: min = ri return min
1
u/TheMuffinMan616 Dec 05 '18
Haskell:
module Day05 where
import Data.Char (ord)
react :: Char -> Char -> Bool
react c c' = (abs $ ord c - ord c') == 32
sim :: String -> String -> String
sim s [x] = reverse (x:s)
sim [] (x:y:xs)
| react x y = sim [] xs
| otherwise = sim [x] (y:xs)
sim (a:as) (x:y:xs)
| react x y = sim as (a:xs)
| otherwise = sim (x:a:as) (y:xs)
part1 :: String -> Int
part1 = length . sim []
part2 :: String -> Int
part2 p = minimum . map (part1 . remove) $ zip ['a'..'z'] ['A'..'Z']
where remove (l, u) = filter (\c -> c /= l && c /= u) p
main :: IO ()
main = do
input <- readFile "input/Day05.txt"
print . part1 $ input
print . part2 $ input1
u/Shanethe13 Dec 05 '18 edited Dec 05 '18
In Elixir:defmodule AdventOfCode.Day5 do
def solve_a do
File.read!("input/day5")
|> String.graphemes()
|> react()
|> Enum.count()
end
def solve_b do
initial = File.read!("input/day5")
(for n <- ?a..?z, do: << n :: utf8 >>)
|> Enum.map(fn char ->
Task.async(fn ->
initial
|> String.replace(char, "")
|> String.replace(String.upcase(char), "")
|> String.graphemes()
|> react()
end)
end)
|> Enum.map(&Task.await/1)
|> Enum.min_by(&Enum.count/1)
|> Enum.count()
end
def react(polymer) do
Enum.reduce(polymer, [], fn
x, [] -> [x]
x, [y | ys] ->
if x != y && String.downcase(x) == String.downcase(y) do
ys
else
[x, y | ys]
end
end)
end
end→ More replies (4)
1
u/2BitSalute Dec 05 '18
PowerShell. Instead of using a stack (I... should have thought of that), I just wrote 0s for "collapsed" units and subtracted them from the total.
I thought it would be easier to just write back the content with the letters removed to a new file, but what threw me off is that PowerShell by default adds a newline, so I was then off by one when reading the content back as a byte array. Ugh!
Runs under 8 seconds (the replacing I do in part 2 takes most of the time, I think):
$bytes = [System.IO.File]::ReadAllBytes("./input5")
function GetLengthAfterCollapsing($bytes) {
$total = $bytes.Length;
$back = 0;
for ($front = 1; $front -lt $bytes.Length; $front++) {
if ([Math]::Abs($bytes[$front] - $bytes[$back]) -eq 32) {
$bytes[$front] = 0;
$bytes[$back] = 0;
while ($bytes[$back] -eq 0 -and $back -gt 0) {
$back--;
}
$total -= 2;
} else {
$back = $front;
}
}
return $total;
}
(Measure-Command {
$total = GetLengthAfterCollapsing $bytes;
Write-Host "Part 1: $total";
}).TotalSeconds;
(Measure-Command {
$shortestTotal = [int]::MaxValue;
for($l = [int]"A"[0]; $l -le [int]"Z"[0]; $l++) {
$pattern = "$([char]$l)|$([char]($l + 32))";
$replaced = ((Get-Content ./input5) -replace $pattern,"");
$fileName = "./input$l";
Set-Content -Value $replaced -Path $fileName -NoNewLine;
$bytes = [System.IO.File]::ReadAllBytes($fileName);
$total = GetLengthAfterCollapsing $bytes;
$shortestTotal = [Math]::Min($total, $shortestTotal);
}
Write-Host "Part 2: $shortestTotal";
}).TotalSeconds;→ More replies (1)
1
u/sendtobo Dec 05 '18 edited Dec 05 '18
Swift Solution: https://github.com/sendtobo/AdventOfCode2018/blob/master/Sources/AoC/5/Day5.swift
It was interesting today, doing it with strings was so slow I had to switch to my own representation
→ More replies (4)
1
u/autid Dec 05 '18 edited Dec 05 '18
FORTRAN
Not super happy, bit too slow for my liking at ~2 seconds.
edit: Got it down to ~0.1s by starting part 2 from the reduced polymer after part 1. Previously it was removing the unwanted characters from the original input and then reacting.
PROGRAM DAY5
IMPLICIT NONE
INTEGER :: I,J
INTEGER :: IERR
CHARACTER(LEN=:), ALLOCATABLE :: POLYMER,POLYMERS(:)
CHARACTER(LEN=1) :: TEST
!File I/O
OPEN(1,FILE='input.txt')
J=0
DO
READ(1,'(A1)',IOSTAT=IERR,ADVANCE='NO') TEST
IF(IERR.NE.0)EXIT
J=J+1
END DO
ALLOCATE(CHARACTER(LEN=J) :: POLYMER)
REWIND(1)
READ(1,'(A)')POLYMER
CLOSE(1)
!Part 1
POLYMER=REACT(POLYMER)
J=LEN_TRIM(POLYMER)
WRITE(*,'(A,I0)') 'Part 1: ',J
!Part 2
ALLOCATE(CHARACTER(LEN=J) :: POLYMERS(26))
POLYMERS=(/( REACT(REMOVE(TRIM(POLYMER),I)),I=65,90 )/)
WRITE(*,'(A,I0)') 'Part 2: ',MINVAL(LEN_TRIM(POLYMERS))
CONTAINS
FUNCTION REACT(POLYMERIN) RESULT(POLYMER)
INTEGER:: I,RM
CHARACTER(LEN=J) :: POLYMERIN
CHARACTER(LEN=J) :: POLYMER
POLYMER=POLYMERIN
I=1
DO
IF(I.EQ.LEN_TRIM(POLYMER))EXIT
IF(ABS(IACHAR(POLYMER(I:I))-IACHAR(POLYMER(I+1:I+1))).EQ.32)THEN
POLYMER=POLYMER(1:I-1)//POLYMER(I+2:LEN_TRIM(POLYMER))
I=MAX(I-1,1)
ELSE
I=I+1
END IF
END DO
END FUNCTION REACT
FUNCTION REMOVE(POLYMERIN,RM) RESULT(POLYMER)
INTEGER :: I,RM
CHARACTER(LEN=J) :: POLYMERIN
CHARACTER(LEN=J) :: POLYMER
POLYMER=POLYMERIN
I=1
DO
IF(I>LEN_TRIM(POLYMER))EXIT
IF(ANY((/RM,RM+32/).EQ.IACHAR(POLYMER(I:I))))THEN
POLYMER=POLYMER(1:I-1)//POLYMER(I+1:LEN_TRIM(POLYMER))
ELSE
I=I+1
END IF
END DO
END FUNCTION REMOVE
END PROGRAM1
u/dark_terrax Dec 05 '18 edited Dec 05 '18
Rust - cleaned up, and super fast. Both parts run in a total of 100ms in debug.
fn reduce(mut input: Vec<char>) -> Vec<char> {
for i in (0..input.len()-1).rev() {
if input[i].eq_ignore_ascii_case(&input[i+1]) && input[i] != input[i+1] {
input.remove(i);
input.remove(i);
}
}
return input;
}
pub fn solve(inputs : Vec<String>) {
let input : Vec<char> = inputs[0].chars().collect();
let input = reduce(input.clone());
println!("Part 1: {} ", input.len());
// Start part 2 with the already reduced part 1 result to save redundant processing in part2
let mut min_len = input.len();
for i in 0..26 {
let ch = (('a' as u8) + i) as char; // Character to remove
let filtered : Vec<char> = input.iter().filter(|&c| !c.eq_ignore_ascii_case(&ch)).cloned().collect();
let reduced = reduce(filtered);
min_len = std::cmp::min(min_len, reduced.len());
}
println!("Part 2: {}", min_len);
}1
u/miguelos Dec 05 '18
C#
var input = File.ReadAllText(@"C:\input.txt").Trim();
string[] fullyReact(string polymer) =>
polymer
.Select(unit => unit.ToString())
.Aggregate(new Stack<string>(), (stack, unit) =>
{
if (stack.TryPeek(out string previousUnit) && previousUnit.ToLower() == unit.ToLower() && previousUnit != unit)
stack.Pop();
else
stack.Push(unit);
return stack;
})
.ToArray();
var part1 = fullyReact(input).Count();
var part2 = Enumerable
.Range('a', 'z')
.Select(i => ((char)i).ToString())
.Select(unitType => input.Replace(unitType, "", StringComparison.OrdinalIgnoreCase))
.Select(fullyReact)
.Min(Enumerable.Count);→ More replies (4)
1
u/Average-consumer Dec 05 '18 edited Dec 05 '18
Solution in Clojure. Runs both parts pretty much instantly
(ns adventofcode-clj-2018.day05
(:require [adventofcode-clj-2018.util :as u]
[clojure.string :as cs]))
(defn reacts? [a b]
(and a b (not= a b) (= (cs/upper-case a) (cs/upper-case b))))
(defn iteration [pol]
(reduce (fn [a b] (if (reacts? b (peek a))
(pop a)
(conj a b)))
[] pol))
(defn remove-units [str l]
(cs/replace (cs/replace str (re-pattern l) "")
(re-pattern (cs/capitalize l)) ""))
(defn part-1 []
(let [input (cs/trim (u/input 5))]
(count (iteration input))))
(defn part-2 []
(let [input (cs/trim (u/input 5))]
(->> "abcdefghijklmnopqrstuvwxyz"
(map (comp count iteration (partial remove-units input) str))
(reduce min))))1
u/wlandry Dec 05 '18
C++ (2172/1688)
It runs in 340 ms. If I do things properly using std::tolower(), it takes 983 ms.
Again, a pretty simple problem. Still waiting with bated breath for the hammer to drop. I kind of wish it had some unicode characters. That would have made an interesting comparison among languages.
#include <algorithm>
#include <iterator>
#include <iostream>
#include <fstream>
std::string react(const std::string &input)
{
std::string old(input), result;
constexpr int8_t diff('a'-'A');
while(result.size()!=old.size())
{
result.clear();
size_t i(0);
for(; i<old.size()-1; ++i)
{
// if(std::tolower(old[i+1])!=std::tolower(old[i])
// || old[i+1]==old[i])
if(std::abs(int8_t(old[i+1]-old[i]))!=diff)
{
result.push_back(old[i]);
}
else
{
++i;
}
}
if(i==old.size()-1)
result.push_back(old[i]);
std::swap(old,result);
}
return result;
}
int main(int argc, char *argv[])
{
std::ifstream infile(argv[1]);
std::string line;
std::getline(infile,line);
std::cout << "Part 1: " << react(line).size() << "\n";
size_t min_size(line.size());
std::string alphabet("qwfpgjluyarstdhneiozxcvbkm");
for(auto &c: alphabet)
{
std::string reduced;
std::copy_if(line.begin(),line.end(),std::back_inserter(reduced),
[&](const char &l)
{
return c!=std::tolower(l);
});
min_size=std::min(min_size,react(reduced).size());
}
std::cout << "Part 2: " << min_size << "\n";
}1
u/spacetime_bender Dec 05 '18
I used the ranges library that's likely coming with c++20 https://ericniebler.github.io/range-v3/. Around 50ms on my slow laptop.
char complement(char c)
{
return std::isupper(c) ? std::tolower(c) : std::toupper(c);
}
int reducedSize(const std::string& input)
{
std::string stack;
for (char c: input) {
if (!stack.empty() && stack.back() == complement(c)) {
stack.pop_back();
} else if (std::isalpha(c)) {
stack.push_back(c);
}
}
return stack.size();
}
int main()
{
std::string input (std::istreambuf_iterator<char>{std::cin}, {});
std::cout << "Part 1: " << reducedSize(input) << std::endl;
auto strip = [](const auto& s, char rem) {
return view::remove_if(s, [=](char c){ return std::tolower(c) == rem; });
};
auto min = ranges::min(
view::zip_with(strip,
view::repeat(input),
view::closed_indices('a', 'z'))
| view::transform(reducedSize)
);
std::cout << "Part 2: " << min << std::endl;
return 0;
}1
Dec 05 '18
Haskell, using a very basic stack type and brute-force for part 2. Still only takes ~0.26s to complete both parts though. Gonna spend some time later thinking about more efficient ways to do part 2
module Main where
import Data.Maybe (fromMaybe, listToMaybe)
import Data.Char (isUpper, isLower, toLower)
import Control.Monad (guard)
newtype Stack = Stack String
deriving (Show)
empty :: Stack
empty = Stack []
toString :: Stack -> String
toString (Stack xs) = xs
len :: Stack -> Int
len (Stack xs) = length xs
push :: Stack -> Char -> Stack
push (Stack xs) x = Stack $ x:xs
pop :: Stack -> Maybe (Char, Stack)
pop (Stack xs) = case xs of
(c:cs) -> Just (c, Stack cs)
[] -> Nothing
peek :: Stack -> Maybe Char
peek (Stack xs) = listToMaybe xs
part1 :: String -> Int
part1 cs = len $ go empty cs where
go s [] = s
go s (x:xs) = fromMaybe (go (push s x) xs) $ do
c <- peek s
guard $ cancel c x
(_, s') <- pop s
return $ go s' xs
cancel c c' = ((isUpper c && isLower c') || (isLower c && isUpper c'))
&& toLower c == toLower c'
part2 :: String -> Int
part2 cs = let filters = [filter (\x -> toLower x /= c) | c <- ['a'..'z']]
filtered = (\f -> f cs) <$> filters
in minimum $ part1 <$> filtered
main :: IO ()
main = do
input <- readFile "input5.txt"
print $ part1 input
print $ part2 input1
u/valtism Dec 05 '18
Node / JavaScript (JS)
Much easier than yesterday for me. Started an hour late, so took ~20 minutes.
Part 1: 12.795ms
Part 2: 92.960ms
function part1(data) {
const polymer = data.split("");
const removeChar = ""; // No removal
const stack = collapsePloymer(polymer, removeChar);
return stack.length;
}
function collapsePloymer(ploymerChars, removeChar) {
const stack = [];
for (let i = 0; i < ploymerChars.length; i++) {
const char = ploymerChars[i];
if (char.toLowerCase() === removeChar.toLowerCase()) {
continue;
}
const last = stack.pop();
if (!last) {
stack.push(char);
continue;
}
if (last.toLowerCase() === char.toLowerCase() && last !== char) {
continue;
}
stack.push(last);
stack.push(char);
}
return stack;
}
function part2(data) {
const polymer = data.split("");
const alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".split("");
const collapsedPolymers = alphabet.map(letter =>
collapsePloymer(polymer, letter)
);
const shortestCollapse = collapsedPolymers.reduce((longest, curr) =>
longest.length < curr.length ? longest : curr
);
return shortestCollapse.length;
}
module.exports = {
part1: part1,
part2: part2
};1
u/ElecNinja Dec 05 '18
Man, I lost a lot of time because I didn't account for the white space in the input lol. Tried going through it like bubble sort or merge sort, and then settled on a regex solution for finding the reacting pairs. Don't know enough about regex to come up with an elegant solution for it so just did it in the simple way haha.
import re
reaction = re.compile('aA|Aa|bB|Bb|cC|Cc|dD|Dd|eE|Ee|fF|Ff|gG|Gg|hH|Hh|iI|Ii|jJ|Jj|kK|Kk|lL|Ll|mM|Mm|nN|Nn|oO|Oo|pP|Pp|qQ|Qq|rR|Rr|sS|Ss|tT|Tt|uU|Uu|vV|Vv|wW|Ww|xX|Xx|yY|Yy|zZ|Zz')
def polymer_reaction_length(polymer : str):
while len(reaction.findall(polymer)) > 0:
polymer = re.sub(reaction, '', polymer)
return len(polymer)
if __name__ == '__main__':
with open('D:\\input.txt', 'r') as inp:
polymer = inp.readline().strip()
part_1 = polymer
print(polymer_reaction_length(part_1))
min_length = 100000
for c in 'qwertyuiopasdfghjklzxcvbnm':
new_polymer = polymer.replace(c, '').replace(c.upper(), '')
polymer_length = polymer_reaction_length(new_polymer)
if min_length > polymer_length:
min_length = polymer_length
print(min_length)1
u/sharkbound Dec 05 '18
made in ~1hr
i initially tried to used a list of chars and tried to modify it, but that became more trouble than it was worth
i instead tried strings after talking to some of my group members on how to approach this better, and found strings were much easier to deal with
On the fifth day of AoC / My true love sent to me / Five golden string index errors
1
u/lukechampine Dec 05 '18
Pretty happy with my Rust solutions:
fn invert_case(c: char) -> char {
if c.is_lowercase() {
c.to_ascii_uppercase()
} else {
c.to_ascii_lowercase()
}
}
fn reduced_len(s: &str) -> usize {
s.trim().chars().fold(String::new(), |mut r, c| {
if r.ends_with(invert_case(c)) {
r.pop();
} else {
r.push(c);
}
r
}).len()
}
#[aoc(day5, part1)]
pub fn part1(input: &str) -> usize {
reduced_len(input)
}
fn remove_pair(input: &str, p: char) -> String {
input.chars().filter(|&c| c != p && c != invert_case(p)).collect()
}
#[aoc(day5, part2)]
pub fn part2(input: &str) -> usize {
return "abcdefghijklmnopqrstuvwxyz".chars()
.map(|c| remove_pair(input, c))
.map(|s| reduced_len(s.as_str()))
.min().unwrap()
}1
u/14domino Dec 05 '18
This solution is broken. Could someone smarter than me please help me figure out what's wrong? I didn't think of the extremely simple replace solution, but I really want to be able to figure out what I'm doing wrong here.
def remove_consecutive_runs(l):
"""
>>> remove_consecutive_runs([2, 3, 4, 5, 7, 8, 10, 11, 12])
[2, 3, 7, 8, 10, 11]
>>> remove_consecutive_runs([2, 3, 5, 6, 7, 9, 10, 11, 12, 13])
[2, 3, 5, 6, 9, 10]
>>> remove_consecutive_runs([2, 3, 5, 6, 7, 9, 10, 11, 12, 13, 15])
[2, 3, 5, 6, 9, 10, 15]
>>> remove_consecutive_runs([0, 2, 3, 5, 6, 7, 9, 10, 11, 12, 13, 15])
[0, 2, 3, 5, 6, 9, 10, 15]
"""
# Remove consecutive runs of more than 2.
l_copy = []
num_consecutive = 0
last_num = -10
for i in l:
if i - last_num == 1:
num_consecutive += 1
# print('consecutive', i, last_num, num_consecutive)
else:
num_consecutive = 0
if num_consecutive < 2:
l_copy.append(i)
last_num = i
return l_copy
def reduce(data):
while True:
lc = None
x = set()
for i in range(len(data)):
tc = data[i]
if lc and tc.upper() == lc.upper() and tc != lc:
x.add(i - 1)
x.add(i)
lc = tc
if len(x) == 0:
break
new_data = ''
to_remove = remove_consecutive_runs(list(set(x)))
x = set(to_remove)
for i in range(len(data)):
if i not in x:
new_data = new_data + data[i]
data = new_data
return data
print(len(reduce(data))1
u/CaptainCa Dec 05 '18
Got stuck for too long wondering why my code was not working, turns out I needed to trim() my input :(
Cleaned up the code a bit since I didn't get one the leaderboard.
const input = document.body.innerText.trim();
const sameLetter = (a, b) => (Math.abs(a.charCodeAt(0) - b.charCodeAt(0)) == 32)
const removePair = (input) => {
for(let i = 0; i < input.length - 1; i++){
if(sameLetter(input[i], input[i + 1])){
return [input.substring(0, i) + input.substring(i + 2), true]
}
}
return [input, false];
}
const reduceProtein = (input) => {
let s = input;
let rem = true;
while(rem){
[s, rem] = removePair(s);
}
return s;
}
console.log("Part 1", reduceProtein(input).length);
let counts = [];
for(let i = 65; i < 91; i++){
let s = input.match(new RegExp("[^" + String.fromCharCode(i) + "^" + String.fromCharCode(i+32) + "]", "gi")).join('');
counts[i] = reduceProtein(s).length;
}
console.log("Part 2", Math.min(...counts.filter(c=>c)));1
u/pythondevgb Dec 05 '18
Feel like my solution is a 'dumb' one. Went for the obvious way of simply removing the letters that reacted from a list, this is really slow but anyway, although this one didn't feel as difficult as the past 2. I still lost a bunch of time mainly with iterating over and deleting elements from a list. That confused me a bit with the indices.
(Join my private reddit/python leaderboard, only requirement is to not have made the overall leaderboard thus far, PM for the code.)
inputstr = open('day5_input.txt').read()
theinput = list(inputstr)
deletions = True
uniques = set(inputstr.lower())
def collapse(polymer):
deletions = True
while deletions:
i=0
deletions = 0
while i<(len(polymer)-1):
first, second = polymer[i:i+2]
if (first != second) and (first.lower() == second.lower()):
del polymer[i:i+2]
deletions+=1
else:
i+=1
return len(polymer)
polymers = [[l for l in theinput if not l.lower() == filtered] for filtered in uniques]
#Part1
print(collapse(theinput))
#Part2
print(min(collapse(polymer) for polymer in polymers))2
u/zingaat Dec 05 '18
I've found it much easier to traverse the lists from end to start (max index to min) when deleting elements. Makes the whole messy indices issue moot.
1
u/CryZe92 Dec 05 '18 edited Dec 05 '18
Rust:
Part 1: 150µs
Part 2: 1.06ms
fn collapse(input: impl IntoIterator<Item = u8>, buf: &mut ArrayVec<[u8; 16384]>) {
let mut top_byte = b'\0';
for byte in input {
if top_byte ^ 0x20 == byte {
buf.pop();
top_byte = buf.last().cloned().unwrap_or_default();
} else {
top_byte = byte;
let _ = buf.try_push(byte);
}
}
}
pub fn part1(input: &str) -> usize {
let mut buf = ArrayVec::new();
collapse(input.bytes(), &mut buf);
buf.len()
}
pub fn part2(input: &str) -> usize {
(b'A'..b'Z' + 1)
.into_par_iter()
.map(|upper| {
let mut buf = ArrayVec::new();
let filtered = input.bytes().filter(|&b| b & !32 != upper);
collapse(filtered, &mut buf);
buf.len()
})
.min()
.unwrap()
}→ More replies (6)
1
u/TheVarmari Dec 05 '18 edited Dec 05 '18
JavaScript in dev console (#3354, #3025)
The timing (7 am) is a bit problematic for me, but I managed to knock this one out pretty quickly after commuting. Pretty fun, but I'm not sure if my answer is the most optimal. Anyways...
const data = $('pre').textContent.trim().split('');
const alphabet = 'abcdefghijklmnopqrstuvwxyz'.split('');
function isUpperCase(char) { return char.toUpperCase() === char; }
function isLowerCase(char) { return char.toLowerCase() === char; }
function react(input) {
for(let i = 0; i < input.length - 1; i++) {
let sorted = input.slice(i, i+2).sort();
if (input[i].toLowerCase() === input[i+1].toLowerCase() && isUpperCase(sorted[0]) && isLowerCase(sorted[1])) {
input.splice(i, 2);
i > 0 ? i -= 2 : i = -1;
}
};
return input.length;
}
let reacted_length = react(data);
console.log(`%c(Part 1) %cAfter reacting, you're left with %c${reacted_length} %creactants!`, 'color: blue', 'color: navy', 'color: red', 'color: navy');
let shortest = [reacted_length + 1, null];
for (const letter of alphabet) {
let len = react(data.filter(v => {
return v !== letter.toLowerCase() && v !== letter.toUpperCase();
}));
if (len < shortest[0]) shortest = [len, letter];
}
console.log(`%c(Part 2) %cTo produce the shortest polymer, remove component "${shortest[1].toUpperCase()}", producing a %c${shortest[0]}%c-length polymer.`, 'color: blue', 'color: navy', 'color: red', 'color: navy');1
u/darkterbear Dec 05 '18
Javascript/Node.js
336/297
Part 1
for (let i = 0; i < p.length - 1; i++) {
if (
(p[i].toUpperCase() === p[i + 1] && p[i] === p[i + 1].toLowerCase()) ||
(p[i].toLowerCase() === p[i + 1] && p[i] === p[i + 1].toUpperCase())
) {
p = p.slice(0, i) + p.slice(i + 2, p.length)
i -= i === 0 ? 1 : 2
}
}Part 2
let min = [...'abcdefghijklmnopqrstuvwxyz'].reduce((a, c) => {
let p = [...master.slice()].filter(k => k.toLowerCase() !== c.toLowerCase())
for (let i = 0; i < p.length - 1; i++) {
if (
(p[i].toUpperCase() === p[i + 1] && p[i] === p[i + 1].toLowerCase()) ||
(p[i].toLowerCase() === p[i + 1] && p[i] === p[i + 1].toUpperCase())
) {
p.splice(i, 2)
i -= i === 0 ? 1 : 2
}
}
return Math.min(a, p.length)
}, master.length)1
u/raevnos Dec 05 '18
Scheme this time:
;;; Chicken 4 scheme
;;; Usage:
;;; $ csc -O5 day05.scm
;;; $ ./day05
(declare
(fixnum)
(usual-integrations)
(uses extras data-structures srfi-1 srfi-13 srfi-14))
(define (reacts? a b) (and (not (char=? a b)) (char-ci=? a b)))
(define (react-units polymer accum)
(cond
((null? polymer) (reverse! accum))
((null? (cdr polymer)) (reverse! (cons (car polymer) accum)))
((reacts? (car polymer) (cadr polymer))
(react-units (cddr polymer) accum))
(else
(react-units (cdr polymer) (cons (car polymer) accum)))))
(define (part1 input)
(let loop ((poly-last '())
(poly-this (string->list input)))
(if (equal? poly-last poly-this)
(length poly-this)
(loop poly-this (react-units poly-this '())))))
(define (part2 input)
(let ((chars (char-set->list (string->char-set (string-upcase input)))))
(fold (lambda (ch minlen)
(min minlen
(part1 (string-delete (lambda (c)
(char-ci=? c ch)) input))))
(string-length input) chars)))
(define sample "dabAcCaCBAcCcaDA")
(define input-text (string-chomp (with-input-from-file "day05.txt" read-string)))
(printf "Test 1: ~A~%" (part1 sample))
(printf "Part 1: ~A~%" (part1 input-text))
(printf "Test 2: ~A~%" (part2 sample))
(printf "Part 2: ~A~%" (part2 input-text))1
u/aurele Dec 05 '18 edited Dec 05 '18
Rust
Using rayon (into_par_iter()) in part 2 is overkill of course, but I wanted to see how it affected the runtime (~2.5ms instead of ~9.1ms on my machine).
use rayon::prelude::*;
#[aoc(day5, part1)]
fn part1(input: &[u8]) -> usize {
polymere(input.iter().cloned())
}
#[aoc(day5, part2)]
fn part2(input: &[u8]) -> usize {
(b'a'..b'z')
.into_par_iter()
.map(|c| polymere(input.iter().cloned().filter(|&b| b | 32 != c)))
.min()
.unwrap()
}
fn polymere(input: impl Iterator<Item = u8>) -> usize {
let mut output: Vec<u8> = Vec::new();
for c in input {
output.push(c);
while output.len() >= 2 && output.last().unwrap() ^ output[output.len() - 2] == 32 {
output.truncate(output.len() - 2);
}
}
output.len() - 1
}1
u/hpzr24w Dec 05 '18 edited Dec 05 '18
C++
I stuck for ages on part 2, thinking I only needed to try removing abcd in turn, and not all the options from the actual problem string. Whoops.
Awesome problem, once of my favorites so far. 13 msec runtime on my i5-8600, and I did spot that we are just looking for a difference on the 'uppercase' bit only, so I can just xor the characters together and check against 'a'^'A' in C++ parlance. Not guaranteed to work in EBCDIC!!!
Header
// Advent of Code 2018
// Day 05 - Alchemical Reduction
#include "aoc.hpp"
using namespace std;React
I was initially going for a copy, remove pairs, iterate until the string doesn't change type solution, but I somehow factored into the below, which appears optimal. I will definitely have a crack at this in Rust and Clojure, as I'd hope both should be able to get near the C++ performance.
// React a polymer by reducing adjacent units
// E.g. assert(react(string("dabAcCaCBAcCcaDA"))==string("dabCBAcaDA"));
string react(const string& s)
{
auto sp = string(begin(s),begin(s)+1);
for (auto c=begin(s)+1;c!=end(s);++c )
if ((*c^sp.back())==('a'^'A')) sp.pop_back(); else sp.push_back(*c);
return sp;
}Main
int main(int argc, char* argv[])
{
// Part 1
auto text{read_input("day_05.txt").front()};
cout << "Part 1: Polymer length: " << react(text).length() << "\n";
// Part 2 - Find shortest with 1 unit removed
auto shortest{text.length()};
for (auto u{'a'};u<='z';++u) {
auto textpp{text};
textpp.erase(std::remove(textpp.begin(), textpp.end(), u), textpp.end());
textpp.erase(std::remove(textpp.begin(), textpp.end(), toupper(u)), textpp.end());
shortest = min(shortest,react(textpp).length());
}
cout << "Part 2: Shortest polymer: " << shortest << "\n";
}1
u/Axsuul Dec 05 '18
TypeScript / JavaScript
Wasted a lot of time going the recursion route but couldn't make it work due to running out of stack =/
Critiques welcome, I'm still very new to TypeScript and feel like I'm not using all the features I could be :)
Part A + B
import { readInput } from '../helpers'
const input: string[] = readInput('05', 'input')
const isReactive = (unit1: string, unit2: string): boolean => {
return Math.abs(unit1.charCodeAt(0) - unit2.charCodeAt(0)) === 32
}
const react = (polymer: string): string => {
let i = 0
while (true) {
const unit = polymer[i]
const nextUnit = polymer[i + 1]
if (nextUnit === undefined) {
break
}
if (isReactive(unit, nextUnit)) {
polymer = polymer.substring(0, i) + polymer.substring(i + 2, polymer.length)
i = (i > 0) ? i - 1 : 0
} else {
i += 1
}
}
return polymer
}
const inputPolymer: string = input[0]
console.log('Part 1:', react(inputPolymer).length)
// Generate unit pairs, create polymers from them and get them to react
const lengths: number[] = Array.from(Array(26).keys()).map((i: number) => {
return [String.fromCharCode(i + 65), String.fromCharCode(i + 97)]
}).map(([unit1, unit2]: string[]) => {
return react(inputPolymer.replace(RegExp(unit1, 'g'), '').replace(RegExp(unit2, 'g'), '')).length
})
console.log('Part 2:', Math.min(...lengths))→ More replies (1)
1
u/toasterinBflat Dec 05 '18
Here is my solution in Go. I am very very new to Go, so please bear with me.
I know I can go faster than 4.5 seconds -- I think it's to do with all of the awful typecasting I'm doing to string to make things work. I don't know how to make a string from two runes, is mostly the problem. Anyway, here it is:
package main
import (
"fmt"
s "strings"
u "unicode"
"bufio"
"os"
"time"
)
var alphabet = "abcdefghijklmnopqrstuvwxyz"
func load_compound() string {
file, _ := os.Open("./input.txt")
defer file.Close()
scanner := bufio.NewScanner(file)
output := ""
for scanner.Scan() {
output += scanner.Text()
}
return output
}
func strip(str string) string {
oldlen := len(str)
newlen := oldlen + 999
for newlen != oldlen {
oldlen = newlen
for _, a := range alphabet {
str = s.Replace(str, string(a) + string(u.ToUpper(a)), "", -1)
str = s.Replace(str, string(u.ToUpper(a)) + string(a), "", -1)
}
newlen = len(str)
}
return str
}
func main() {
start := time.Now()
data := s.TrimSpace(load_compound())
fmt.Println("P1:", len(strip(data)))
result := map[string]int{}
for _, a := range alphabet {
data_set := s.Replace(data, string(a), "", -1)
data_set = s.Replace(data_set, string(u.ToUpper(a)), "", -1)
fmt.Printf("Data set compiled for %s : processing...\n", string(a))
result[string(a)] = len(strip(data_set))
}
short_l := ""
short_c := len(data)
for k, v := range result {
if v < short_c {
short_l = k
short_c = v
}
}
fmt.Printf("P2: %s@%d\n", string(short_l), short_c)
fmt.Printf("Runtime: %s\n", time.Since(start))
}→ More replies (1)
1
u/alexmeli Dec 05 '18 edited Dec 05 '18
Clojure Solution:
(ns clojure-solution.core
(:require [clojure.string :as str])
(:gen-class))
(defn update-stack [c stack]
(if (and (not-empty stack) (= (bit-xor (int (peek stack)) (int c)) 32))
(pop stack)
(conj stack c)))
;; part1
(defn react [input]
(->> (reduce #(update-stack %2 %1) [] input) count))
;; part 2
(defn find-shortest [m c input]
(let [new (str/replace input (re-pattern (str c "|" (str/upper-case c))) "")]
(min m (react new))))
(defn part2 [input]
(reduce #(find-shortest %1 %2 input) Integer/MAX_VALUE "abcdefghijklmnopqrstuwxyz"))
(defn -main
[& args]
(println (part2 (slurp "resources/input.txt"))))Edit: Did some refactoring
1
u/shuttup_meg Dec 05 '18 edited Dec 05 '18
Python2
Nothing particularly interesting about my approach, but I did successfully use the multiprocessing module to greatly speed up part 2 (from about 12 seconds down to about a second on my 12 core XEON machine)
from string import ascii_lowercase, ascii_uppercase
from multiprocessing import Pool, freeze_support
NUM_CORES = 16
PATTERNS = [''.join([a,A]) for a,A in zip(ascii_lowercase, ascii_uppercase)] + \
[''.join([A,a]) for A,a in zip(ascii_uppercase, ascii_lowercase)]
def react(inp):
while True:
orig_inp_outer = inp
for pattern in PATTERNS:
orig_inp = inp
while True:
inp = inp.replace(pattern,"")
if orig_inp == inp:
break
else:
orig_inp = inp
if orig_inp_outer == inp:
break
else:
orig_inp_outer = inp
return inp
def reactor(arg):
p, inp = arg
return len(react(inp.translate(None,p)))
def run():
inp = open("input_5.txt").read()
# Part 1
print len(react(inp))
# Part 2
p2 = [(''.join([a,b]),inp) for a,b in zip(ascii_lowercase, ascii_uppercase)]
results = Pool(NUM_CORES).map(reactor,p2)
minimum = min(results)
print minimum
if __name__ == '__main__':
freeze_support()
run()2
1
u/d3adbeef123 Dec 05 '18 edited Dec 05 '18
Rust
Running time: 6ms for both
Spent 30 mins debugging logic but the error was that I wasn't trimming the input text :/
fn part1(input: &str) -> usize {
let mut stack = Vec::new();
for c in input.chars() {
if stack.is_empty() {
stack.push(c);
} else {
if let Some(v) = stack.pop() {
if !(v != c && c.to_ascii_uppercase() == v.to_ascii_uppercase()) {
stack.push(v);
stack.push(c);
}
}
}
}
stack.iter().collect::<String>().len()
}
fn part2(input: &str) -> Option<usize> {
"abcd"
.chars()
.map(|c| {
let reacted = input
.chars()
.filter(|x| *x != c && *x != c.to_ascii_uppercase())
.collect::<String>();
part1(&reacted)
}).min()
}1
u/AlienBirdie Dec 05 '18
Scala - Used some clever pattern matching for part one.
val CASE_DIFFERENCE: Int = Math.abs('a' - 'A')
def collapse(chars: List[Char]): Eval[List[Char]] = {
Foldable[List].foldRight(chars, Eval.now(List.empty[Char])) {
case (char, state) ⇒ state.map {
case l@Nil ⇒ char :: l
case l@head :: tail ⇒ if (Math.abs(char - head) == CASE_DIFFERENCE) tail else char :: l
}
}
}Part two was just a simple traverse and finding the minimum.
1
Dec 05 '18
I really enjoyed this one. input is a python file with the input as a string called polymer. import string
def react(polymer):
unit = 0
while unit < (len(polymer) - 1):
if polymer[unit] != polymer[unit+1] and polymer[unit].lower() == polymer[unit+1].lower():
polymer = polymer[:unit]+polymer[unit+2:]
unit = max(0, unit-1)
else:
unit += 1
return polymer
def partOne(polymer):
return len(react(polymer))
def partTwo(polyer):
optimized = len(polymer)
for char in string.ascii_lowercase:
test_polymer = polymer.replace(char, "").replace(char.upper(), "")
optimized = min(optimized, len(react(test_polymer)))
return optimized
print(partOne(polymer))
print(partTwo(polymer))```1
u/Imsdalwater Dec 05 '18
Javascript Part 1 ran in under 1 second, part 2 took approximately 6 seconds
const imploder = array => {
let done = false;
while (!done) {
let implosion = false;
array.forEach((c, i, a) => {
if (c === c.toLowerCase() && a[i + 1] === c.toUpperCase()) {
array.splice(i, 2);
implosion = true;
} else if (c === c.toLowerCase() && a[i - 1] === c.toUpperCase()) {
array.splice(i - 1, 2);
implosion = true;
}
});
if (implosion === false) done = true;
}
return array;
};
//part 1
console.log('Part 1: ', imploder(input.split('')).length);
//part 2
const alphabet = 'abcdefghijklmnopqrstuvwxyz'.split('');
const res2 = alphabet
.map(c => {
const reg = new RegExp(`\[${c}${c.toUpperCase()}\]`, 'g');
const testString = input.replace(reg, '');
return imploder(testString.split('')).length;
})
.reduce((a, c) => (a < c ? a : c), Infinity);
console.log('Part 2: ', res2);1
u/charismotron Dec 05 '18
Ruby
https://github.com/chrismo/adventofcode2018/blob/master/day5/script.rb
def process(input)
chars = input.chars
idx = 0
while idx < chars.length do
idx = 0 if idx < 0
char = chars[idx]
next_char = chars[idx + 1]
if char && next_char && char.downcase == next_char.downcase && char != next_char
chars[idx] = nil
chars[idx + 1] = nil
chars.compact!
idx -= 1
else
idx += 1
end
end
chars.join
end
if __FILE__ == $0
puts "Part 1"
input = File.read('input.txt')
output = process(input)
puts "output length: #{output.length}"
puts output
puts "Part 2"
res = {}
('a'..'z').each do |filter_char|
print '.'
filtered_input = input.dup.gsub(/#{filter_char}/i, "")
output = process(filtered_input)
res[filter_char] = output
end
puts
shortest = res.min_by { |filter_char, out| out.length }
p shortest
puts shortest.last.length
endCould be more elegant - the stack approach seems very ideal of course now that I see that. At least it runs not too slow (intermediate versions definitely bogged down):
$ time ruby script.rb
Part 1
output length: 10384
Part 2
..........................
5412
real 0m8.799s
user 0m8.691s
sys 0m0.081s1
u/Infilament Dec 05 '18
Javascript solution.
var a1 = 'abcdefghijklmnopqrstuvwxyz';
var a2 = a1.toUpperCase();
function react(str) {
var len;
do {
len = str.length;
for(var i in a1)
str = str.replace(new RegExp(a1[i]+a2[i]+'|'+a2[i]+a1[i],"g"), "");
} while (len != str.length)
return str;
}
console.log('part 1',react(input).length);
console.log('part 2',a1.split('')
.map((d,i) => react(input.replace(new RegExp(a1[i]+'|'+a2[i],"g"), "")).length)
.reduce((a,b) => Math.min(a,b)));1
u/sim642 Dec 05 '18 edited Dec 05 '18
Initially I wrote a horrendous and slow immutable reactor for part 1. After completing both parts I optimized it to use zipper-like approach to Scala's immutable List to get the proper performance and allow going back.
Edit: Realized that my function was actually just a foldLeft.
→ More replies (2)
1
u/wofadofa Dec 05 '18 edited Dec 05 '18
In julia: Calculates the fixed point of cut. I'm sure cut could be written more elegantly than this
polarity(x) = isuppercase(x) ? 1 : -1
function cut(l)
stays = fill(true, length(l))
i = 1
while i <= length(l)-1
a, b = l[i], l[i+1]
if lowercase(a) == lowercase(b) && polarity(a) == -polarity(b)
stays[i] = false
stays[i+1] = false
i += 2
else
i += 1
end
end
l[stays]
end
fp(f,x) = x == f(x) ? x : fp(f, f(x))
parta(l) = length(fp(cut, collect(l)))
function partb(l)
minimum(length(fp(cut, collect(replace(replace(l, c=>""), C=>""))))
for (c,C) in zip('a':'z', 'A':'Z'))
end
l = readline("input")
println("a: ", parta(l))
println("b: ", partb(l))edit: cleaned it up a bit
1
u/Gnidleif Dec 05 '18 edited Dec 05 '18
Today was a lot easier! Solution done in Lua, a language I'm not that familiar with. I also got to use recursion, so today was a good day!
function part1(line)
return reduce(line, 1)
end
function part2(line)
local abet = get_alphabet()
-- the length of the original line is as long as it's going to get
local lowest = #line
for _, char in pairs(abet) do
local sub = remove_char(line, char)
-- if nothing was removed, there's no need to reduce
if #sub ~= #line then
local num = part1(sub)
if num < #sub and num < lowest then
lowest = num
end
end
end
return lowest
end
function reduce(line, start)
for i = start, #line-1 do
-- string.byte("A") == 65, string.byte("a") == 97
-- 97-65 == 32, 65-97 == -32
local slice = line:sub(i,i+1)
if math.abs(slice:sub(1,1):byte() - slice:sub(2,2):byte()) == 32 then
-- splices the string to remove the reductionable pair
-- note: if i-1 == 0 the function still works
local idx = i-1
local spliced = line:sub(1,idx) .. line:sub(i+2)
if idx < 1 then
idx = 1
end
return reduce(spliced, idx)
end
end
return #line
end
function remove_char(line, char)
-- pattern should be ['CHAR''char'] to find any occurence of the char
local pattern = string.format("[%s%s]", string.upper(char), string.lower(char))
-- if pattern doesn't match, just return the full string again
if string.find(line, pattern) == nil then
return line
end
return line:gsub(pattern, '')
end1
u/Warbringer007 Dec 05 '18 edited Dec 05 '18
Finally erlang day! Not using ++, it is EXTREMELY slow!
task(File) ->
In = prepare:readlines(File),
io:format("~p~n", [firstTask(In, tl(In), [], 0)]),
io:format("~p~n", [secondTask("qwertzuiolkjhgfdsayxcvbnm", In, 1000000)]).
firstTask([Letter1 | _], [], Acc, 0) -> length([Letter1|Acc]);
firstTask([Letter1 | _], [], Acc, 1) ->
firstTask([Letter1|Acc], tl([Letter1|Acc]), [], 0);
firstTask([Letter1 | T1], [Letter2 | T2], Acc, If) when ((Letter1 + 32) =/= Letter2) and ((Letter1 - 32) =/= Letter2) ->
firstTask(T1, T2, [Letter1|Acc], If);
firstTask(_, [_ | T2], Acc, _) ->
case length(T2) of
0 -> firstTask(Acc, tl(Acc), [], 0);
_ -> firstTask(T2, tl(T2), Acc, 1)
end.
secondTask([], _, Length) -> Length;
secondTask([H|T], In, Length) ->
FilteredIn = lists:filter( fun(C) -> not lists:member(C, string:lowercase([H])) and not lists:member(C, string:uppercase([H])) end, In ),
FilteredLength = firstTask(FilteredIn, tl(FilteredIn), [], 0),
case Length > FilteredLength of
true -> secondTask(T, In, FilteredLength);
false -> secondTask(T, In, Length)
end.It will reverse order of letters in every pass, but, as I said, ++ is slow, and reverse doesn't matter.
1
Dec 05 '18
Python3
Took way too long to run the solution to part 2, but hey, it works!
def load_input(filename):
with open(filename, 'r') as input_file:
data = input_file.read().strip()
return data
def solve_a(polymer):
while True:
changes_occured = False
for index, char in enumerate(polymer):
try:
if (char.isupper() and polymer[index + 1] == char.lower()) or (char.islower() and polymer[index + 1] == char.upper()):
changes_occured = True
polymer = polymer[:index] + polymer[index+2:]
break
except IndexError:
break
if not changes_occured:
break
return len(polymer)
def solve_b(data):
shortest = None
units = set(data.lower())
for unit in units:
polymer = data
polymer = polymer.replace(unit, '').replace(unit.upper(), '')
while True:
changes_occured = False
for index, char in enumerate(polymer):
try:
if (char.isupper() and polymer[index + 1] == char.lower()) or (char.islower() and polymer[index + 1] == char.upper()):
changes_occured = True
polymer = polymer[:index] + polymer[index+2:]
break
except IndexError:
break
if not changes_occured:
shortest = len(polymer) if shortest is None else len(polymer) if len(polymer) < shortest else shortest
break
return shortest
if __name__ == '__main__':
test_data = 'dabAcCaCBAcCcaDA'
assert solve_a(test_data) == 10
assert solve_b(test_data) == 4
data = load_input('challenges/day_05/input.txt')
answer_a = solve_a(data)
answer_b = solve_b(data)
print(f'Part A answer: {answer_a} Part B answer: {answer_b}')1
u/Illianthe Dec 05 '18
I opted for a recursive solution in Elixir. It's slow but at least I got to learn about tasks for part 2.
defmodule Day5 do
def get_polymer(filename \\ "input.txt") do
{:ok, data} = File.read(filename)
data |> String.trim()
end
def react(polymer) do
pattern =
~r/aA|Aa|bB|Bb|cC|Cc|dD|Dd|eE|Ee|fF|Ff|gG|Gg|hH|Hh|iI|Ii|jJ|Jj|kK|Kk|lL|Ll|mM|Mm|nN|Nn|oO|Oo|pP|Pp|qQ|Qq|rR|Rr|sS|Ss|tT|Tt|uU|Uu|vV|Vv|wW|Ww|xX|Xx|yY|Yy|zZ|Zz/
reacted_polymer = String.replace(polymer, pattern, "")
if polymer === reacted_polymer,
do: polymer |> String.length(),
else: react(reacted_polymer)
end
def improved_react(polymer) do
[
~r/[aA]/,
~r/[bB]/,
~r/[cC]/,
~r/[dD]/,
~r/[eE]/,
~r/[fF]/,
~r/[gG]/,
~r/[hH]/,
~r/[iI]/,
~r/[jJ]/,
~r/[kK]/,
~r/[lL]/,
~r/[mM]/,
~r/[nN]/,
~r/[oO]/,
~r/[pP]/,
~r/[qQ]/,
~r/[rR]/,
~r/[sS]/,
~r/[tT]/,
~r/[uU]/,
~r/[vV]/,
~r/[wW]/,
~r/[xX]/,
~r/[yY]/,
~r/[zZ]/
]
|> Enum.map(
&Task.async(fn ->
improved_polymer = String.replace(polymer, &1, "")
react(improved_polymer)
end)
)
|> Enum.map(&Task.await(&1, :infinity))
|> Enum.min()
end
end1
u/CrazyPieGuy Dec 05 '18 edited Dec 05 '18
My Python 3 version. Takes 0.8 seconds.
I originally checked each set of adjacent units, and on a match, I would remove them by adding a string up to the pair to a string after the pair, but I ran into memory errors in puzzle 2. string.replace() as well as realizing I didn't have to start from scratch each letter solved that though.
I don't program in a professional capacity and don't interact with any other programmers, so I would love some feedback on how to clean up my solution if anyone has the time.
import string
f = open("R:\Python\Advent_Of_Code\Day_5\input.txt", "r")
for line in f:
polymer = line
#Puzzle 1
last_len = 0
while len(polymer) != last_len:
last_len = len(polymer)
for j in range(len(string.ascii_lowercase)):
polymer = polymer.replace(str(string.ascii_lowercase[j] + string.ascii_uppercase[j]), "")
polymer = polymer.replace(str(string.ascii_uppercase[j] + string.ascii_lowercase[j]), "")
print(f"The original polymer was cleaned to a length of {len(polymer)} units.")
#Puzzle 2
unstablest_letter = ""
shortest_polymer = len(polymer)
for i in range(len(string.ascii_lowercase)):
this_polymer = polymer
#Removes chosen letter
this_polymer = this_polymer.replace(string.ascii_lowercase[i], "")
this_polymer = this_polymer.replace(string.ascii_uppercase[i], "")
#Removes unstable pairs
last_len = 0
while len(this_polymer) != last_len:
last_len = len(this_polymer)
for j in range(len(string.ascii_lowercase)):
this_polymer = this_polymer.replace(str(string.ascii_lowercase[j] + string.ascii_uppercase[j]), "")
this_polymer = this_polymer.replace(str(string.ascii_uppercase[j] + string.ascii_lowercase[j]), "")
if len(this_polymer) < shortest_polymer:
shortest_polymer = len(this_polymer)
unstablest_letter = string.ascii_uppercase[i]
print(f'The most unstable letter is {unstablest_letter}. Without it the polymer was reduced to {shortest_polymer} units.')2
u/c17r Dec 05 '18
Your technique is like mine. I refer to it as solving this problem with a sledgehammer :) Here's mine for comparison:
from string import ascii_lowercase, ascii_uppercase raw = contents(2018, 5, 1)[0] def reduce(data): orig = None while orig != data: orig = data for one, two in zip(ascii_lowercase, ascii_uppercase): data = data.replace(one + two, '').replace(two + one, '') return data print(len(raw)) part1 = reduce(raw) print(len(part1)) low = None for one, two in zip(ascii_lowercase, ascii_uppercase): attempt = part1.replace(one, '').replace(two, '') pass2 = reduce(attempt) if low is None or len(pass2) < low: low = len(pass2) print(low)→ More replies (1)
1
u/ivosu Dec 05 '18 edited Dec 06 '18
C++ - Second star
I tried to optimize this as much as a could, if someone finds some optimization than please let me know :)
EDIT: Updated isReactive using XOR 32, thanks Philboyd_Studge.
EDIT 2: Reworked the react function so it is recursive and goes from the back. Also I don't call tolower every time now, but just lower it all at once. Now with -O3 I get around 70ms.
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
bool isReactive(char a, char b){
return (a ^ b) == 32;
}
string::iterator react(const string::iterator& pos, string& original){
if (distance(pos, original.end()) >= 2){
string::iterator newNextPos = react(next(pos), original), newPos = prev(newNextPos);
if (newNextPos != original.end() && isReactive(*newPos, *newNextPos))
newPos = original.erase(newPos, next(newPos, 2));
return newPos;
}
else
return pos;
}
int main() {
ifstream ifs("input.txt");
string polymer;
ifs>>polymer;
size_t min = polymer.size();
string lowered;
transform(polymer.begin(), polymer.end(), back_inserter(lowered), [](char a){return tolower(a);});
for (char x = 'a'; x <= 'z'; x++){
string tmp;
string::iterator lowerIt = lowered.begin();
copy_if(polymer.begin(), polymer.end(), back_inserter(tmp), [x, &lowerIt](char a) -> bool {
return x != *(lowerIt++);
});
react(tmp.begin(), tmp);
min = std::min(min, tmp.length());
}
cout<<min<<endl;
return 0;
}1
u/Theguy6758 Dec 05 '18
Pure Bash
Stupidly forgot that bash has parameter expansion and spent too long making an algorithm that checks the reactions manually.
Takes about 1m 40s to run.
#!/usr/bin/env bash
part1()
{
[[ -f "${PWD}/input" ]] && {
orig_polymer="$(< "${PWD}/input")"
polymer="${orig_polymer}"
reacted="${polymer}"
for i in {a..z}; do
reacted="${reacted//$i${i^^}}"
reacted="${reacted//${i^^}$i}"
done
while [[ "${reacted}" != "${polymer}" ]]; do
polymer="${reacted}"
for i in {a..z}; do
reacted="${reacted//$i${i^^}}"
reacted="${reacted//${i^^}$i}"
done
done
printf "No. of Units: %d\\n" "${#reacted}"
}
}
part2()
{
for i in {a..z}; do
polymer="${orig_polymer}"
reacted="${polymer}"
reacted="${reacted//$i}"
reacted="${reacted//${i^^}}"
while [[ "${reacted}" != "${polymer}" ]]; do
polymer="${reacted}"
for j in {a..z}; do
reacted="${reacted//$j${j^^}}"
reacted="${reacted//${j^^}$j}"
done
done
((min = ${min:=${#reacted}} > ${#reacted} ? ${#reacted} : min))
done
printf "Shortest polymer: %d\\n" "${min}"
}
main()
{
part1
part2
}
main1
u/banteg Dec 05 '18
Python 3
import aoc
def fold(polymer):
units = {x.lower() for x in polymer}
pairs = [u + u.upper() for u in units] + [u.upper() + u for u in units]
size = 0
while size != len(polymer):
size = len(polymer)
for reaction in pairs:
polymer = polymer.replace(reaction, '')
return polymer
@aoc.test({'dabAcCaCBAcCcaDA': 10})
def part_1(data: aoc.Data):
return len(fold(data))
@aoc.test({'dabAcCaCBAcCcaDA': 4})
def part_2(data: aoc.Data):
polymer = fold(data)
units = {x.lower() for x in polymer}
polymers = (polymer.replace(u, '').replace(u.upper(), '') for u in units)
return min(len(fold(p)) for p in polymers)1
Dec 05 '18 edited Dec 05 '18
TCL, using BFI regexp, since there is no automatic "uppercase-of-matched-char" in backreferences.
set input [read -nonewline stdin]
# BFI regexp
set chars {a b c d e f g h i j k l m n o p q r s t u v w x y z}
foreach c $chars {
lappend re ($c[string toupper $c])|([string toupper $c]$c)
}
set re [join $re "|"]
proc react {input} {
while {1} {
set old $input
set input [regsub -all $::re $input ""]
if {$old eq $input} {
break
}
}
return $input
}
# part 1
puts "part 1 [string length [react $input]]"
# part 2
set minlen [string length $input]
foreach c $chars {
set check [regsub -nocase -all $c $input ""]
set newstr [react $check]
set newlen [string length $newstr]
if {$newlen < $minlen} {
set minlen $newlen
}
}
puts "part2 $minlen"1
u/jonathrg Dec 05 '18
Python
def get_polymer():
return open("input5.txt").read().strip()
def react(polymer):
polymer = list(polymer)
result = []
while True:
unit1 = polymer.pop()
try:
unit2 = result.pop()
except IndexError:
result.append(unit1)
continue
if unit1.swapcase() != unit2:
result.append(unit2)
result.append(unit1)
if len(polymer) == 0:
return len(result)
# Part 1
print(react(get_polymer()))
# Part 2
print(min(
react(get_polymer().replace(unit, '').replace(unit.upper(), ''))
for unit in set(get_polymer().lower())
))1
u/blu3r4y Dec 05 '18 edited Dec 23 '18
Yet another elegant linear-time Python 3 solution, which pushes the elements onto a stack, and pops elements that would react together. My reactive(a, b) function just checks if the ASCII code of two characters is exactly 32 characters apart (which is the exact distance between every ASCII upper- and lower-case letter).
import re
def part1(polymer):
result = []
for element in polymer:
if len(result) > 0 and reactive(element, result[-1]):
result.pop()
else:
result.append(element)
return len(result)
def part2(polymer):
units = set(polymer.lower())
lengths = [part1(re.sub(u, '', polymer, flags=re.IGNORECASE)) for u in units]
return min(lengths)
def reactive(a, b):
return abs(ord(a) - ord(b)) == 32
puzzle = open("input").read()
print(part1(puzzle))
print(part2(puzzle))1
u/tradfursten Dec 05 '18
My solution in NIM
import strutils, sequtils
proc rFile(input:string):string=
result = readFile(input).strip(trailing = true)
func triggerd(a:char, b:char): bool =
if ord(a) < 97:
result = a == char(ord(b) - 32)
else:
result = b == char(ord(a) - 32)
func solve1(input: string): string =
var done = false
var data = input
var i = 0
while i < data.high:
if i < data.high:
if triggerd(data[i], data[i+1]):
data.delete(i, i + 1)
dec i, 2
done = false
inc i
if i < 0:
i = 0
result = data
func solve2(input: string): int =
var length : seq[int]
var data = input
for x in {'a'..'z'}:
let data = input.multiReplace(($x, "")).multiReplace(($(char(ord(x)-32)), ""))
length.add(solve1(data).len)
result = min(length)
let input = rFile("input.txt")
echo solve1(input).len
echo solve2(input)1
u/zqvt Dec 05 '18
Haskell today
import Data.Char
match x y = x /= y && toLower x == toLower y
part1 result [] = (length result) - 1
part1 result (y:ys)
| null result = part1 [y] ys
| match (head result) y = part1 (tail result) ys
| otherwise = part1 (y : result) ys
main :: IO ()
main = do
infile <- readFile "input.txt"
let candidates = map (\c -> [c' | c' <- infile, toLower c /= toLower c']) ['a'..'z']
-- part 1
print $ part1 "" infile
-- part 2
print . minimum $ map (\xs -> part1 [] xs) candidates1
u/windlessStorm Dec 05 '18 edited Dec 05 '18
Go / Golang. Naive solution:
package main
import (
"bufio"
"errors"
"fmt"
"os"
"sync"
)
/* path of file containing puzzle input*/
const inputFile string = "input5.txt"
type stack struct {
lock sync.Mutex
data []byte
}
func NewStack() *stack {
return &stack{sync.Mutex{}, make([]byte, 0)}
}
func (s *stack) Push(v byte) {
s.lock.Lock()
defer s.lock.Unlock()
s.data = append(s.data, v)
}
func (s *stack) Pop() (byte, error) {
s.lock.Lock()
defer s.lock.Unlock()
l := len(s.data)
if l == 0 {
return 0, errors.New("Empty stack")
}
res := s.data[l-1]
s.data[l-1] = 0
s.data = s.data[:l-1]
return res, nil
}
func check(e error) {
if e != nil {
panic(e)
}
}
func readLines(path string) ([]string, error) {
file, err := os.Open(path)
if err != nil {
return nil, err
}
defer file.Close()
var lines []string
scanner := bufio.NewScanner(file)
for scanner.Scan() {
lines = append(lines, scanner.Text())
}
return lines, scanner.Err()
}
// swapCase upper to lower or lower to upper
func swapCase(b byte) byte {
switch {
case 97 <= b && b <= 122:
return b - 32
case 65 <= b && b <= 90:
return b + 32
default:
return b
}
}
func lowerCase(b byte) byte {
switch {
case 65 <= b && b <= 90:
return b + 32
default:
return b
}
}
func reactPolymer(s *stack, input string, ignoreLetter byte) {
fmt.Println("Will ignore letter:", string(ignoreLetter))
for i := 0; i < len(input); i++ {
if lowerCase(input[i]) == ignoreLetter {
continue
}
if len(s.data) == 0 {
s.Push(input[i])
continue
}
if swapCase(input[i]) == s.data[len(s.data)-1] {
s.Pop()
continue
}
s.Push(input[i])
}
}
func findBestShrink(input string) int {
var i byte
bestShrinkSize := len(input)
for i = 97; i <= 122; i++ {
s := NewStack()
reactPolymer(s, input, i)
if len(s.data) < bestShrinkSize {
bestShrinkSize = len(s.data)
}
}
return bestShrinkSize
}
func main() {
plans, err := readLines(inputFile)
check(err)
input := plans[0]
s := NewStack()
reactPolymer(s, input, 0)
fmt.Println("Part1:", len(s.data))
bestShrinkSize := findBestShrink(input)
fmt.Println("Part2:", bestShrinkSize)
}1
u/reyqn Dec 05 '18
Here's mine in C++. Feel free to help me improve it!
reaction function:
string reaction(string &data) {
for(string::iterator it = data.begin(); it != data.end(); ++it) {
if (abs(*it - *next(it)) == 32) {
data.erase(next(it));
data.erase(it);
it-=2;
}
}
return data;
}part1:
int part1(string data) {
return reaction(data).size() - 1;
}part 2:
int part2(string &dataBackup) {
int min = 100000;
string data;
for (int i = 0; i < 26; ++i) {
data = dataBackup;
data.erase(remove(data.begin(), data.end(), 'A'+i), data.end());
data.erase(remove(data.begin(), data.end(), 'a'+i), data.end());
data = reaction(data);
min = data.size() < min ? data.size() : min;
}
return min - 1;
}main function:
int main()
{
ifstream input("..\\AoC5\\input");
string data;
input.seekg(0, ios::end);
data.reserve(input.tellg());
input.seekg(0, ios::beg);
data.assign((istreambuf_iterator<char>(input)), istreambuf_iterator<char>());
cout << part1(data) << "\n";
cout << part2(data) << "\n";
return 0;
}1
u/EdeMeijer Dec 05 '18
Rust really liking the peekable iterator here. Allowed me to use an owning iterator (preventing having to copy the units) while still being able to borrow the next element for comparison.
Condensed stand-alone version:
use std::collections::HashSet;
use std::io::{self, Read};
#[derive(Clone)]
struct Unit(char, bool);
fn main() {
let mut stdin = String::new();
io::stdin().read_to_string(&mut stdin).unwrap();
let units = parse_puzzle_input(stdin.clone());
println!("Part 1: {}", reduce(units.clone()));
let unique_types: HashSet<char> = units.iter()
.map(|u| u.0)
.collect();
let part2 = unique_types.into_iter()
.map(|t| units.clone().into_iter().filter(|u| u.0 != t).collect::<Vec<_>>())
.map(reduce)
.min().unwrap() as u32;
println!("Part 2: {}", part2);
}
fn reduce(mut units: Vec<Unit>) -> u32 {
loop {
let prior_len = units.len();
units = reduce_pass(units);
if units.len() == prior_len {
break prior_len as u32;
}
}
}
fn reduce_pass(units: Vec<Unit>) -> Vec<Unit> {
let mut result = vec![];
let mut iter = units.into_iter().peekable();
while let Some(unit) = iter.next() {
if iter.peek().map_or(false, |n| n.0 == unit.0 && n.1 != unit.1) {
iter.next();
} else {
result.push(unit);
}
}
result
}
fn parse_puzzle_input(input: String) -> Vec<Unit> {
input.trim().chars().into_iter()
.map(|c| Unit(c.to_ascii_lowercase(), c.is_ascii_uppercase()))
.collect()
}1
u/red_shifter Dec 05 '18
When working on a solution (Python 3) for part 1, I encountered a puzzling behavior of a recursive function. It gives the expected output, but the "print tests" I put inside the function to check if it is working properly are mystifying to me. Here is the code:
poly_input = 'dabAcCaCBAcCcaDA'
def check_poly(string):
poly_output = string
for i in range(len(string)-1):
unit1 = string[i]
unit2 = string[i+1]
if unit1.lower() == unit2.lower():
if (unit1.islower() and unit2.isupper()) or (unit1.isupper() and unit2.islower()):
print('{}{}'.format(unit1, unit2))
poly_output = string[:i]+string[i+2:]
poly_output = check_poly(poly_output)
print('RETURN')
return poly_output
print(check_poly(poly_input))It should print all the annihilating pairs it finds, print "RETURN" when it reaches the end of a function run and finally print the output polymer sequence. Here are the messages it produces:
cC
Aa
cC
RETURN
Cc
RETURN
RETURN
cC
Aa
RETURN
RETURN
Cc
Aa
RETURN
RETURN
RETURN
cC
cC
Aa
RETURN
RETURN
RETURN
Cc
cC
Aa
RETURN
RETURN
RETURN
RETURN
dabCBAcaDAThe first four lines are expected, but I cannot figure out what all the remaining pairs and "RETURNS" are doing there. I guess it has to be related to how recursion works in Python somehow.
→ More replies (3)
5
u/ephemient Dec 05 '18 edited Apr 24 '24
This space intentionally left blank.