Non-working Day 21 revision for posterity - gonna rewrite

robabrazado · robabrazado · commit 0a305be9f56c · 2024-12-30T10:01:53.000-05:00
diff --git a/README.md b/README.md
@@ -225,6 +225,10 @@ Once I implemented my third attempt at part 2, the only stumbling block was that
 
 [On day 30] As tends to go, I had inspiration last night after I had shut everything down about how to fix this. I don't have time to work on it at the time of this writing, but I am committing the work I've done so far, even though I'm going to largely rewrite everything. One, it's bordering on unhinged, and I want to save it. :) Two...who knows, it might even come in handy later! I have seen part 2 yet, so maybe I'll get to make use of something unhinged after all. It's not a terrible commit. At least it's better than the version I was bughunting before where it turned out my numeric keypad didn't have a "1 2 3" row. :D
 
+[A little later] It occurs to me that maybe I *can* salvage what I already wrote and just make it do less with a flag or something. Maybe I don't need a whole rewrite.
+
+[A little later] GOD DAMN IT the algorithm wasn't the problem! I mean...it was, and still is, but it's not that the puzzle took up too much RAM, it's that I **added an extra keypad to the chain**. So...with the correct number of robots (and therefore keypads), my solution actually executes and looks like it's producing a result in the right neighborhood, but it's still wrong. It looks like whatever I was cooking up in there isn't passing test data. So *once again*, I am going to commit for posterity and then basically start over. I could halfway justify trying to salvage the unhinged implementation if it meant I could just shortcut the performance problems and get the right answer. But...I shortcut the performance problems and got the _wrong_ answer. Between that and the knowledge that the thing is already wildly overengineered for the puzzle ask, I might as well start from scratch. Sadly, I can't do it as I'm writing this, but I hope to give it another shot in the afternoon.
+
 ## Day 22: Monkey Market
 
 I wasn't even going to start a new puzzle today, but the description for part 1 seemed so straightforward that I assumed either part 2 would be way complicated, or else I was fooling myself and part 1 would take forever with a naive implementation. I rolled the dice, though, and got part 1 relatively quickly. Then, of course, part 2 is *way* more complicated, so I'm not going to try that tonight. Until next time, monkeys!
diff --git a/src/com/robabrazado/aoc2024/day21/Day21Solver.java b/src/com/robabrazado/aoc2024/day21/Day21Solver.java
@@ -19,10 +19,16 @@ public Day21Solver() {
 	@Override
 	public String solve(Stream<String> puzzleInput, boolean partOne, boolean isTest) {
 		BigInteger result = BigInteger.ZERO;
-		KeypadRobot myRobot = new KeypadRobot(KeypadRobot.KeypadType.DIRECTIONAL).setWorker(		// I control crowded robot, who controls...
-				new KeypadRobot(KeypadRobot.KeypadType.DIRECTIONAL).setWorker(						// ...cold robot, who controls...
-						new KeypadRobot(KeypadRobot.KeypadType.DIRECTIONAL).setWorker(				// ...radiation robot, who controls...
-								new KeypadRobot(KeypadRobot.KeypadType.NUMERIC))));					// ...vacuum robot, who controls the door.
+		
+		KeypadRobot robotAtDepressurizedControllerAtRadiation = new KeypadRobot(KeypadRobot.KeypadType.NUMERIC);
+		
+		KeypadRobot robotAtRadiationControllerAtFreezing = new KeypadRobot(KeypadRobot.KeypadType.DIRECTIONAL);
+		robotAtRadiationControllerAtFreezing.setWorker(robotAtDepressurizedControllerAtRadiation);
+		
+		KeypadRobot robotAtFreezingControllerAtCrowded = new KeypadRobot(KeypadRobot.KeypadType.DIRECTIONAL);
+		robotAtFreezingControllerAtCrowded.setWorker(robotAtRadiationControllerAtFreezing);
+		
+		KeypadRobot myRobot = robotAtFreezingControllerAtCrowded;
 		
 		Iterator<String> it = puzzleInput.iterator();
 		Pattern inputP = Pattern.compile("^(\\d+)A$");
@@ -37,40 +43,16 @@ public String solve(Stream<String> puzzleInput, boolean partOne, boolean isTest)
 			}
 			System.out.println("Checking base input " + baseInput);
 			
-//			String command = myRobot.getShortestCommandForBaseInput(baseInput);
-			String command = "SOME FOO";
+			String command = myRobot.getShortCommandForBaseInput(baseInput);
 			System.out.println("Found command string " + command);
 			
+			System.out.println("Previous command string " + robotAtRadiationControllerAtFreezing.getShortCommandForBaseInput(baseInput));
+			
 			int complexity = numericPortion * command.length();
 			System.out.println("Complexity " + complexity);
 			result = result.add(BigInteger.valueOf(complexity));
 		}
 		
-		// TESTING SHIT
-		
-		System.out.println("---");
-		
-		String testBaseInput = "029A";
-		
-		KeypadRobot testNumericRobot = new KeypadRobot(KeypadRobot.KeypadType.NUMERIC);
-		System.out.println(testNumericRobot.getShortestCommandForBaseInput(testBaseInput));
-		
-		KeypadRobot testDirectionalRobot = new KeypadRobot(KeypadRobot.KeypadType.DIRECTIONAL);
-		testDirectionalRobot.setWorker(testNumericRobot);
-		System.out.println(testDirectionalRobot.getShortestCommandForBaseInput(testBaseInput));
-		
-		KeypadRobot testDirectionalRobot2 = new KeypadRobot(KeypadRobot.KeypadType.DIRECTIONAL);
-		testDirectionalRobot2.setWorker(testDirectionalRobot);
-		System.out.println(testDirectionalRobot2.getShortestCommandForBaseInput(testBaseInput));
-		
-		KeypadRobot testDirectionalRobot3 = new KeypadRobot(KeypadRobot.KeypadType.DIRECTIONAL);
-		testDirectionalRobot3.setWorker(testDirectionalRobot2);
-		System.out.println(testDirectionalRobot3.getShortestCommandForBaseInput(testBaseInput));
-		
-		System.out.println("---");
-		
-		// END TESTING
-		
 		return result.toString();
 		
 	}
diff --git a/src/com/robabrazado/aoc2024/day21/KeypadRobot.java b/src/com/robabrazado/aoc2024/day21/KeypadRobot.java
@@ -39,6 +39,15 @@
  * returning the shortest commands, on the assumption that one of the
  * shortest commands for me will be shortest for my controller, as well.
  * If that needs to change, the method signatures are already set up.
+ * 
+ * [Much later, during part 1]
+ * 
+ * It having been demonstrated that I WILDLY overengineered this, I had
+ * considered starting over again, but I realized I could just basically
+ * put a governor on this thing so the puzzle wouldn't make it keep
+ * running out of RAM. So the structure on this is, I'm sure, all messed
+ * up. Perhaps I'll come back to optimize...perhaps not. It will probably
+ * depend on what part 2 of the puzzle looks like.
  */
 public class KeypadRobot {
 	private final KeypadType keypadType;
@@ -88,51 +97,46 @@ public KeypadRobot setWorker(KeypadRobot worker) {
 		return this;
 	}
 	
-	// Assumes starting at 'A' position; terminates each button press with ACT command
-	public String getShortestCommandForBaseInput(String input) {
-		List<String> commands = this.getCommandsForBaseInput(input);
-		if (commands.isEmpty()) {
-			throw new RuntimeException("Robot has no commands for base input " + input);
-		}
-		return commands.get(0);
+	// Assumes starting at 'A' position
+	public String getShortCommandForBaseInput(String input) {
+		return this.getShortCommandsForBaseInput(input, true).get(0);
 	}
 	
-	// Assumes starting at 'A' position; terminates each button press with ACT command
-	public List<String> getCommandsForBaseInput(String input) {
+	public List<String> getShortCommandsForBaseInput(String input, boolean exactlyOneResult) {
 		List<String> result;
 		if (this.worker != null) {
-			List<String> workerCommands = worker.getCommandsForBaseInput(input);
+			List<String> workerCommands = worker.getShortCommandsForBaseInput(input, exactlyOneResult);
 			if (workerCommands.isEmpty()) {
 				throw new RuntimeException("Robot's worker reports no command options for base input " + input);
 			}
 			result = new ArrayList<String>();
+			/*
+			 * I think this is the part that screws me on RAM. For now, only call this
+			 * with exactlyOneResult = true. 
+			 */
 			result = workerCommands.stream()
 					.map(workerCommand -> this.getShortestCommandForMyInput(workerCommand))
 					.collect(Collectors.toList());
 		} else {
 			// I AM BASE
-			result = this.getCommandsForMyInput(input);
+			result = this.getShortCommandsForMyInput(input, exactlyOneResult);
+			Collections.sort(result, Comparator.comparingInt(String::length));
 		}
-		Collections.sort(result, Comparator.comparingInt(String::length));
 		return result;
 	}
 	
 	// Assumes starting at 'A' position; terminates each button press with ACT command
 	public String getShortestCommandForMyInput(String input) {
-		List<String> commands = this.getCommandsForMyInput(input);
-		if (commands.size() < 1) {
-			throw new RuntimeException("Robot has no commands for this input");
-		}
-		return commands.get(0);
+		return this.getShortCommandsForMyInput(input, true).get(0);
 	}
 	
 	// Assumes starting at 'A' position; terminates each button press with ACT command
-	public List<String> getCommandsForMyInput(String input) {
+	public List<String> getShortCommandsForMyInput(String input, boolean exactlyOneResult) {
 		List<String> commands = new ArrayList<String>(Collections.singletonList(""));
 		char[] chars = input.toCharArray();
 		char from = 'A';
 		for (char to : chars) {
-			List<String> newCommands = this.getCommandsForMyInput(from, to, true);
+			List<String> newCommands = this.getShortCommandsForMyInput(from, to, exactlyOneResult);
 			if (newCommands.isEmpty()) {
 				throw new RuntimeException("Robot found no command string from " + from + " to " + to);
 			}
@@ -149,9 +153,14 @@ public List<String> getCommandsForMyInput(String input) {
 		return commands;
 	}
 	
-	public List<String> getCommandsForMyInput(char from, char to, boolean terminateWithAct) {
+	public String getShortCommandForMyInput(char from, char to) {
+		return this.getShortCommandsForMyInput(from, to, true).get(0);
+	}
+	
+	// Due to my bad decisions, calling with "exactly one result" flag always skips caching; maybe fix later
+	public List<String> getShortCommandsForMyInput(char from, char to, boolean exactlyOneResult) {
 		CharPair pair = new CharPair(from, to);
-		if (!this.myCommandCache.containsKey(pair)) {
+		if (!this.myCommandCache.containsKey(pair) || exactlyOneResult) {
 			List<String> commands = new ArrayList<String>();
 			
 			this.checkKey(from);
@@ -211,10 +220,21 @@ public List<String> getCommandsForMyInput(char from, char to, boolean terminateW
 								colCount <= maxColOffset && rowCount <= maxRowOffset;
 					}
 					if (canUse) {
-						if (terminateWithAct) {
-							strb.append(Command.ACT.c);
+						// All my command strings terminate with ACT
+						commands.add(strb.append(Command.ACT.c).toString());
+						if (exactlyOneResult) {
+							break;
 						}
-						commands.add(strb.toString());
+					}
+				}
+				
+				// HEADS UP: early exit
+				if (exactlyOneResult) {
+					if (commands.size() == 1) {
+						return commands;
+					} else {
+						throw new RuntimeException(String.format("Robot was asked for 1 result but produced %d; from '%c' to '%c'",
+								commands.size(), from, to));
 					}
 				}
 			} else {
