Created
December 9, 2016 13:08
-
-
Save shekhargulati/1d619fd34f7177638055958f49b5bb5b to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.nio.file.Files; | |
import java.nio.file.Paths; | |
import static adventofcode.Utils.toInt; | |
import static strman.Strman.repeat; | |
public class Problem09 { | |
public static void main(String[] args) throws Exception { | |
String input = Files.readAllLines(Paths.get("src", "test", "resources", "problem09.txt")).get(0); | |
long startTime1 = System.currentTimeMillis(); | |
System.out.println(String.format("part 1 %d", decompressedLength(input, false))); // Answer is 98135 | |
long endTime1 = System.currentTimeMillis(); | |
System.out.println("Total time taken: " + (endTime1 - startTime1) / 1000 + " seconds"); | |
long startTime2 = System.currentTimeMillis(); | |
System.out.println(String.format("part 2 %d", decompressedLength(input, true))); // Answer is 10964557606 | |
long endTime2 = System.currentTimeMillis(); | |
System.out.println("Total time taken: " + (endTime2 - startTime2) / 1000 + " seconds"); | |
} | |
private static long decompressedLength(String input, boolean part2) { | |
long length = 0; | |
char[] chars = input.toCharArray(); | |
for (int index = 0; index < chars.length; index++) { | |
char ch = chars[index]; | |
if (!Character.isWhitespace(ch)) { | |
if (ch == '(') { | |
StringBuilder marker = new StringBuilder(); | |
while (ch != ')') { | |
ch = chars[++index]; | |
if (ch != ')') { | |
marker.append(ch); | |
} | |
} | |
String[] parts = marker.toString().trim().split("x"); | |
int take = toInt(parts[0]); | |
int repetitions = toInt(parts[1]); | |
String expression = takeN(chars, index + 1, index + 1 + take); | |
String repeatedExpression = repeat(expression, repetitions); | |
if (part2) { | |
length += decompressedLength(repeatedExpression, part2); | |
} else { | |
length += repeatedExpression.length(); | |
} | |
index += take; | |
} else { | |
length++; | |
} | |
} | |
} | |
return length; | |
} | |
private static String takeN(char[] chars, int start, int end) { | |
StringBuilder builder = new StringBuilder(); | |
for (int j = start; j < end; j++) { | |
builder.append(chars[j]); | |
} | |
return builder.toString(); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
At line 41-46 you're first building the
repeatedexpression
and then doing the recursive expansion. Now any expansions in there are repeatedrepetitions
times.However if you write:
You do not need to do so many expansions.