I’m angry about Day 24 because it was impossible to solve with code. You cannot brute force a 14 digit number, no matter how good your code is you’re not writing any. I did write the parser anyway, because I thought maybe Eric was going to be nice enough to restrict the range so it would be found quickly. He did not and so I wasted an hour on that.
I then thought maybe it was supposed to be a threading exercise, so I added parallel threads to my code. That didn’t improve things enough to have bothered. (It MIGHT have finished in a couple of days.)
I then wrote code to convert the input “program” into [Java] code, thinking maybe that would run fast enough if multi-threaded. It did run somewhat faster, but not fast enough to complete in reasonable time.
I then spent time simplifying the generated code, removing stuff that wasn’t really doing useful processing. As I was doing that, I started to see a trend in the input program. There are 14 input digits, and there was 14 sections in the program that were mostly identical, but with different constants.
Having then run out of ideas, I peeked at the Reddit thread and saw someone suggest the code was using the z register to implement a stack. Looking over the code, I started to see what they meant, and then manually transcoded the code into a set of 7 rules. I then used those rules to get the first 5 digits, and then let my now fast bruteforcer do the rest. That got me part one. Part two just meant revisiting the working out of the first 5 digits, and then some quick tweaks to my brute forcer and bingo part two done.
To be clear, I didn’t need to do any brute forcing, I just thought my code would be marginally faster at getting the results than my working it out by hand.
Although my parser is completely pointless, I will share it here. It also includes the code I used to translate the input program into Java code. I could also include my brute forcer, but it would include my working out of my supplied inputs, and wouldn’t really be useful without it, so I don’t think I should.
final class MonadProgram
{
private final String[] monadProgramInstructions;
private long w;
private long x;
private long y;
private long z;
private String[] programInput = new String[0];
private int inputPointer;
public MonadProgram(String[] monadProgramInstructions)
{
this.monadProgramInstructions = monadProgramInstructions;
}
public void translateProgramToJavaCode()
{
System.out.println("long w=0;");
System.out.println("long x=0;");
System.out.println("long y=0;");
System.out.println("long z=0;");
int programCounter = 0;
int inputNumber = 0;
while (programCounter < monadProgramInstructions.length)
{
final String instruction = monadProgramInstructions[programCounter++];
final String[] instructionParts = instruction.split(" ");
switch (instructionParts[0])
{
case "inp": System.out.println(instructionParts[1] + " = input[" + inputNumber++ + "];"); continue;
case "add": System.out.println(instructionParts[1] + " += " + instructionParts[2] + ";"); continue;
case "mul": System.out.println(instructionParts[1] + " *= " + instructionParts[2] + ";"); continue;
case "div": System.out.println(instructionParts[1] + " /= " + instructionParts[2] + ";"); continue;
case "mod": System.out.println(instructionParts[1] + " %= " + instructionParts[2] + ";"); continue;
case "eql": System.out.println(instructionParts[1] + " = (" + instructionParts[1] + "==" + instructionParts[2] + ")?1:0;"); continue;
default: throw new IllegalStateException("Unknown instruction: " + instructionParts[0]);
}
}
}
public void runWithInput(final String[] programInput)
{
w=0;
x=0;
y=0;
z=0;
inputPointer = 0;
this.programInput = programInput;
int programCounter = 0;
while (programCounter < monadProgramInstructions.length)
{
executeInstruction(monadProgramInstructions[programCounter++]);
}
}
private void executeInstruction(final String instruction)
{
final String[] instructionParts = instruction.split(" ");
switch (instructionParts[0])
{
case "inp": doInp(instructionParts[1]); return;
case "add": doAdd(instructionParts[1], instructionParts[2]); return;
case "mul": doMul(instructionParts[1], instructionParts[2]); return;
case "div": doDiv(instructionParts[1], instructionParts[2]); return;
case "mod": doMod(instructionParts[1], instructionParts[2]); return;
case "eql": doEql(instructionParts[1], instructionParts[2]); return;
default: throw new IllegalStateException("Unknown instruction: " + instructionParts[0]);
}
}
private void doInp(final String register)
{
if (inputPointer >= programInput.length) throw new IllegalStateException("Out of input");
final String input = programInput[inputPointer++];
final long val = Long.parseLong(input);
switch (register)
{
case "w": w = val; return;
case "x": x = val; return;
case "y": y = val; return;
case "z": z = val; return;
default: throw new IllegalStateException("Invalid register: " + register);
}
}
private void doAdd(final String register1, final String register2)
{
switch (register1)
{
case "w": w += switch(register2) {case "w" -> w; case "x" -> x; case "y" -> y; case "z" ->z; default -> Long.parseLong(register2);}; return;
case "x": x += switch(register2) {case "w" -> w; case "x" -> x; case "y" -> y; case "z" ->z; default -> Long.parseLong(register2);}; return;
case "y": y += switch(register2) {case "w" -> w; case "x" -> x; case "y" -> y; case "z" ->z; default -> Long.parseLong(register2);}; return;
case "z": z += switch(register2) {case "w" -> w; case "x" -> x; case "y" -> y; case "z" ->z; default -> Long.parseLong(register2);}; return;
default: throw new IllegalStateException("Invalid register: " + register1);
}
}
private void doMul(final String register1, final String register2)
{
switch (register1)
{
case "w": w *= switch(register2) {case "w" -> w; case "x" -> x; case "y" -> y; case "z" ->z; default -> Long.parseLong(register2);}; return;
case "x": x *= switch(register2) {case "w" -> w; case "x" -> x; case "y" -> y; case "z" ->z; default -> Long.parseLong(register2);}; return;
case "y": y *= switch(register2) {case "w" -> w; case "x" -> x; case "y" -> y; case "z" ->z; default -> Long.parseLong(register2);}; return;
case "z": z *= switch(register2) {case "w" -> w; case "x" -> x; case "y" -> y; case "z" ->z; default -> Long.parseLong(register2);}; return;
default: throw new IllegalStateException("Invalid register: " + register1);
}
}
private void doDiv(final String register1, final String register2)
{
switch (register1)
{
case "w": w /= switch(register2) {case "w" -> w; case "x" -> x; case "y" -> y; case "z" ->z; default -> Long.parseLong(register2);}; return;
case "x": x /= switch(register2) {case "w" -> w; case "x" -> x; case "y" -> y; case "z" ->z; default -> Long.parseLong(register2);}; return;
case "y": y /= switch(register2) {case "w" -> w; case "x" -> x; case "y" -> y; case "z" ->z; default -> Long.parseLong(register2);}; return;
case "z": z /= switch(register2) {case "w" -> w; case "x" -> x; case "y" -> y; case "z" ->z; default -> Long.parseLong(register2);}; return;
default: throw new IllegalStateException("Invalid register: " + register1);
}
}
private void doMod(final String register1, final String register2)
{
switch (register1)
{
case "w": w %= switch(register2) {case "w" -> w; case "x" -> x; case "y" -> y; case "z" ->z; default -> Long.parseLong(register2);}; return;
case "x": x %= switch(register2) {case "w" -> w; case "x" -> x; case "y" -> y; case "z" ->z; default -> Long.parseLong(register2);}; return;
case "y": y %= switch(register2) {case "w" -> w; case "x" -> x; case "y" -> y; case "z" ->z; default -> Long.parseLong(register2);}; return;
case "z": z %= switch(register2) {case "w" -> w; case "x" -> x; case "y" -> y; case "z" ->z; default -> Long.parseLong(register2);}; return;
default: throw new IllegalStateException("Invalid register: " + register1);
}
}
private void doEql(final String register1, final String register2)
{
final long compareTo = switch(register2) {case "w" -> w; case "x" -> x; case "y" -> y; case "z" ->z; default -> Long.parseLong(register2);};
switch (register1)
{
case "w": w = (w == compareTo)?1:0; return;
case "x": x = (x == compareTo)?1:0; return;
case "y": y = (y == compareTo)?1:0; return;
case "z": z = (z == compareTo)?1:0; return;
default: throw new IllegalStateException("Invalid register: " + register1);
}
}
long getW()
{
return w;
}
long getX()
{
return x;
}
long getY()
{
return y;
}
long getZ()
{
return z;
}
}
This is the threading runner I put in front of the above class to allow me to run parallel copies:
final class MonadProgramRunner implements Runnable
{
private final long start;
private final long end;
private long result = -1;
final MonadProgram mp;
MonadProgramRunner(final long start, final long end, final String[] inputProgram)
{
this.start = start;
this.end = end;
mp = new MonadProgram(inputProgram);
}
@Override
public void run()
{
result = -1;
for (long possibleSN = end; possibleSN>start; possibleSN--)
{
final String[] programInput = convertLongToProgramInput(possibleSN);
if (programInput.length == 0) continue;
if (possibleSN % 444_444 == 0) System.out.println(possibleSN); // provide some infrequent progress indication
mp.runWithInput(programInput);
if (mp.getZ() == 0)
{
result = possibleSN;
System.out.println("Found result: " + result);
break;
}
}
if (result == -1) System.out.println("Thread ends without result");
}
private static String[] convertLongToProgramInput(final long numberToConvert)
{
final String possibleSNStr = String.format("%d", numberToConvert);
final String[] result = new String[14];
for(int i=0; i<14; i++)
{
final char c = possibleSNStr.charAt(i);
if (c == '0') return new String[0];
result[i] = "" + c;
}
return result;
}
boolean isResult()
{
return result != -1;
}
long getResult()
{
return result;
}
}
This is the brute forcing code that scheduled the above class. There is commented code and other messiness because I never actually used this code the way I normally would. You can see the code commented out that I used to produce the Java code translation, for example. And you can see the code is currently in the state to brute force part two with some part one code commented out:
public static long getPart1Answer(final String[] day24InputLines)
{
//final MonadProgram mp = new MonadProgram(day24InputLines);
//mp.translateProgramToJavaCode();
return findLargestValidSN();
}
public static long getPart1AnswerSlowBruteForce(final String[] day24InputLines)
{
final ExecutorService executorService = Executors.newFixedThreadPool(30);
final List<Future<MonadProgramRunner>> futures = new ArrayList<>();
for (long possibleSN = 99999999999999L; possibleSN>11111111111111L; possibleSN-=10_000_000_000L)
{
final long start = possibleSN-10_000_000_000L;
final long end = possibleSN;
final MonadProgramRunner mpr = new MonadProgramRunner(start, end, day24InputLines);
final Future<MonadProgramRunner> future = executorService.submit(mpr);
futures.add(future);
}
long bestResult = -1;
for (final Future<MonadProgramRunner> future: futures)
{
final MonadProgramRunner mpr;
try
{
mpr = future.get();
}
catch (final InterruptedException | ExecutionException e)
{
throw new IllegalStateException("Couldn't get future: " + e);
}
if (mpr.isResult())
{
final long result = mpr.getResult();
if (result > bestResult)
{
System.out.println("Updating bestResult: " + result);
bestResult = result;
}
}
}
executorService.shutdown();
return bestResult;
}
private static String[] convertLongToProgramInput(final long numberToConvert)
{
final String possibleSNStr = String.format("%d", numberToConvert);
final String[] result = new String[14];
for(int i=0; i<14; i++)
{
final char c = possibleSNStr.charAt(i);
if (c == '0') return new String[0];
result[i] = "" + c;
}
return result;
}
static long findLargestValidSN()
{
long result = -1;
final int[] input = new int[14];
//for (int i=0; i<14; i++) input[i] =9;
for (int i=0; i<14; i++) input[i] =1;
input[0]=5; // This would actually be the first five digits of the answer, I changed them all to 5 here so as to not
input[1]=5; // give anything away about my input
input[2]=5;
input[3]=5;
input[4]=5;
while (result < 0)
{
if (isValidSN(input)) result = Long.parseLong(String.format("%d%d%d%d%d%d%d%d%d%d%d%d%d%d",
input[0], input[1], input[2], input[3], input[4], input[5], input[6], input[7],
input[8], input[9], input[10], input[11], input[12], input[13]));
/*
input[13]--;
if (input[13]==0)
{
input[12]--;
input[13]=9;
}
if (input[12]==0)
{
input[11]--;
input[12]=9;
}
if (input[11]==0)
{
input[10]--;
input[11]=9;
}
if (input[10]==0)
{
input[9]--;
input[10]=9;
}
if (input[9]==0)
{
input[8]--;
input[9]=9;
}
if (input[8]==0)
{
input[7]--;
input[8]=9;
}
if (input[7]==0)
{
input[6]--;
input[7]=9;
}
if (input[6]==0)
{
input[5]--;
input[6]=9;
}
if (input[5]==0)
{
input[4]--;
input[5]=9;
System.out.println("digit 4 wrap");
}
if (input[4]==0)
{
input[3]--;
input[4]=9;
System.out.println("digit 3 wrap");
}
if (input[3]==0)
{
input[2]--;
input[3]=9;
System.out.println("digit 2 wrap");
}
if (input[2]==0)
{
input[1]--;
input[2]=9;
System.out.println("digit 1 wrap");
}
if (input[1]==0)
{
input[0]--;
input[1]=9;
System.out.println("digit 0 wrap");
}
if (input[0]==0) throw new IllegalStateException("Ran out of digits");
*/
input[13]++;
if (input[13]==10)
{
input[12]++;
input[13]=1;
}
if (input[12]==10)
{
input[11]++;
input[12]=1;
}
if (input[11]==10)
{
input[10]++;
input[11]=1;
}
if (input[10]==10)
{
input[9]++;
input[10]=1;
}
if (input[9]==10)
{
input[8]++;
input[9]=1;
}
if (input[8]==10)
{
input[7]++;
input[8]=1;
}
if (input[7]==10)
{
input[6]++;
input[7]=1;
}
if (input[6]==10)
{
input[5]++;
input[6]=1;
}
if (input[5]==10)
{
input[4]++;
input[5]=1;
System.out.println("digit 4 wrap");
}
if (input[4]==10)
{
input[3]++;
input[4]=1;
System.out.println("digit 3 wrap");
}
if (input[3]==10)
{
input[2]++;
input[3]=1;
System.out.println("digit 2 wrap");
}
if (input[2]==10)
{
input[1]++;
input[2]=1;
System.out.println("digit 1 wrap");
}
if (input[1]==10)
{
input[0]++;
input[1]=1;
System.out.println("digit 0 wrap");
}
if (input[0]==10) throw new IllegalStateException("Ran out of digits");
}
return result;
}
This is the reduced generated Java code that I commented as I worked through it… This should give you a massive hint how it was done, so I will spoiler blur it:
static boolean isValidSN(final int[] input)
{
long w=0;
long x=0;
long y=0;
long z=0;
z += input[0]+7; // push input0+7
z *= 26;
z += input[1]+8; // push input1+8
z *= 26;
z += input[2]+10; // push input2+10
w = input[3];
x = z % 26 - 2; // does input3 == input2+8
z /= 26; // pop
x = (x==w)?1:0;
x = (x==0)?1:0;
y = 25 * x + 1;
z *= y;
y = (w+4)*x;
z += y;
w = input[4];
x = z % 26 - 10; // does input4 == input1-2
z /= 26; // pop
x = (x==w)?1:0;
x = (x==0)?1:0;
y = 25 * x + 1;
z *= y;
y = (w+4)*x;
z += y;
z *= 26;
z += input[5]+6; // push input5+6
\\ rest of the code resulting from my personal input is elided
I actually cracked 1000 with part one, coming in at 740 or so. I just straight out simulated the game, and it was so little code, I didn’t even code a new class, I just included it into the part one solution finder. For part two, I came up with the