Skip to content

Instantly share code, notes, and snippets.

@shekhargulati
Created December 9, 2016 13:08
Show Gist options
  • Save shekhargulati/1d619fd34f7177638055958f49b5bb5b to your computer and use it in GitHub Desktop.
Save shekhargulati/1d619fd34f7177638055958f49b5bb5b to your computer and use it in GitHub Desktop.
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();
}
}
@hierynomus
Copy link

At line 41-46 you're first building the repeatedexpression and then doing the recursive expansion. Now any expansions in there are repeated repetitions times.
However if you write:

if (part2) {
    length += decompressedLength(expression, part2) * repetitions;
} else {
    length += repeatedExpression.length() * repetitions;
}

You do not need to do so many expansions.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment