org_roam/Notes/20241210001150-aoc_notes.org

AOC Notes

• Day 3
  • point 1
  • point 2
• Day 4
  • part 1
    • countWordOccurrences Method
    • Checking for the Word
    • Counting Matches
  • part 2
• Day 5
  • Part One: Identifying Correctly Ordered Updates
    • Splitting Input into Rules and Updates
    • Dependency Graph Representation
    • Checking Update Validity
    • Finding the Middle Page
  • Part Two: Reordering Incorrect Updates
    • Topological Sorting
    • Subgraph Creation
    • Cycle Detection
    • Finding Middle Page After Reordering
• Day 6
  • Part 1
    • Input Parsing
    • Guard Initialization
    • Movement Directions
    • Turning Logic
    • Visited Positions Tracking
    • Movement and Termination Logic
  • Part 2
    • Input Parsing
    • Guard Initialization
    • Movement Directions
    • Turning Logic
    • Valid Obstruction Positions
    • Loop Detection Helper Function
• Day 7
  • Part 1
    • Input Parsing
    • Validation Logic
    • Operator Combination Generator
    • Main Logic
  • Part 2
    • Input Parsing
    • Validation Logic
    • Operator Combination Generator
    • Main Logic
• Day 8
  • Part One
  • Part Two
  • Notes on Implementation
• Day 9
  • Part 1: Manipulating and Calculating Disk Placement
  • Part 2: Advanced Disk Rearrangement with Blocks
• Day 10
  • Part 1: Counting Trails in a 2D Grid
  • Part 2: Enhanced Trail Counting with Weighted Points
• Day 12
  • Core Logic and Functionality
    • Core Logic and Functionality
• Day 13
  • Part 1: Parsing Input and Solving Simultaneous Equations
  • Part 2: Transforming Input Data
• Day 14
  • Part 1: Simulating Robot Movement
  • Part 2: Identifying Patterns in Robot Positions

Here are the notes for the AOC (Advent Of Code) for the year 2024. Workspace:

import System.Process (callCommand)
main :: IO ()
main = do
    putStrLn "Launching IntelliJ in gnome-terminal with zsh..."
    _ <- callCommand "gnome-terminal -- zsh -c 'idea /home/zaine/Documents/projects/advent_of_code'"
    putStrLn "Terminal launched."

Day 3

point 1

A lot of basic string and numeric manipulation was tested. When you have a input string, and want to test weather there contains a substring, you can use

// input is the string
if (input.startsWith("mul(", i)) {
   int endIndex = input.indexOf(")", i);
   if (endIndex != -1) {
       String candidate = input.substring(i, endIndex + 1);
}
}

Here we can see that through the loop, an if check is being done to check if the string starts with "mul(", if so, it gets the endIndex of it too. Then it stores that "candidate" value into a String, using the substring method.

point 2

some regex below: this checks if the input is of the correct format.

    public static boolean isValidMul(String input) {
        // Regex to validate mul(X,Y) where X and Y are 1-3 digit numbers
        return input.matches("mul\\(\\d{1,3},\\d{1,3}\\)");
    }

Day 4

part 1

was extremely difficult. i had to load the input as a 2d array,

int cols = lines.get(0).length(); //where lines is var
int cols = grid[0].length; // where grid is a 2d array

this allows you to get the vertical length of the 2d array.

countWordOccurrences Method

Iterates through the grid to check for occurrences of the word "XMAS" in all possible directions (horizontal, vertical, and diagonal). Directions: Defined by the directions array, which contains 8 possible ways to traverse: {0, 1}: Right {0, -1}: Left {1, 0}: Down {-1, 0}: Up {1, 1}: Diagonal down-right {1, -1}: Diagonal down-left {-1, 1}: Diagonal up-right {-1, -1}: Diagonal up-left

For each starting position (row, col) in the grid:

The program checks each direction by calling isWordFound.

Checking for the Word

isWordFound Method Validates if the word exists starting from a specific position (row, col) in the grid, moving in the specified direction (dx, dy). For each character in the word:

• compute the new position (newRow, newCol) based on the direction.
• Check bounds to ensure the position is valid (not out of the grid).
• Compare the character at the position with the corresponding character in the word.
• If any check fails, return false.

If all characters match, the word is found, and the method returns true.

Counting Matches

For each occurrence of the word found by isWordFound, increment the count variable. After scanning all positions and directions in the grid, the total count is returned.

part 2

was alot easier, i looped through the whole grid, and wherever there is the letter 'A', i want to check around it, it can be in the form:

M.S
.A.
M.S

and this would count as one, as there is MAS twice (diagonally in the shape of an X)

Day 5

Part One: Identifying Correctly Ordered Updates

Splitting Input into Rules and Updates

Parsing the input file into two distinct sections (rules and updates) required identifying the empty line separator.

for (String line : lines) {
    if (line.trim().isEmpty()) {
        emptyLineFound = true;
        continue; // Skip the empty line itself
    }
    if (!emptyLineFound) {
        firstList.add(line);
    } else {
        secondList.add(line);
    }
}

Dependency Graph Representation

Representing the rules as a directed graph with each rule defining an edge (X|Y as X -> Y). This graph maps each page to a list of pages that must follow it.

Map<Integer, List<Integer>> graph = new HashMap<>();
graph.putIfAbsent(from, new ArrayList<>());
graph.get(from).add(to);

Checking Update Validity

Verifying if an update follows the rules using a map of page positions for quick lookup.

for (Map.Entry<Integer, List<Integer>> entry : graph.entrySet()) {
    int from = entry.getKey();
    for (int to : entry.getValue()) {
        if (positions.get(from) >= positions.get(to)) {
            return false; // Rule violated
        }
    }
}

Finding the Middle Page

Calculating the middle page for each correctly ordered update using list indexing.

int middlePage = pages.get(pages.size() / 2);

Part Two: Reordering Incorrect Updates

Topological Sorting

Reordering pages required implementing a topological sort, which ensures all dependencies (rules) are respected.

visiting.add(node);
for (int neighbor : graph.getOrDefault(node, Collections.emptyList())) {
    if (!dfs(neighbor, graph, visited, visiting, sorted)) {
        return false; // Cycle detected
    }
}
visiting.remove(node);
visited.add(node);
sorted.add(node);

Subgraph Creation

Only rules involving pages in the current update were considered. This required dynamically building a subgraph for each update.

for (int page : pages) {
    if (graph.containsKey(page)) {
        for (int dependent : graph.get(page)) {
            if (pages.contains(dependent)) {
                subGraph.get(page).add(dependent);
            }
        }
    }
}

Cycle Detection

Ensuring no cycles existed in the dependency graph was critical for valid sorting.

if (visiting.contains(node)) {
    return false; // Cycle detected
}

Finding Middle Page After Reordering

Same approach as in Part One but applied after sorting.

int correctedMiddlePage = reorderedPages.get(reorderedPages.size() / 2);

Day 6

Part 1

Input Parsing

List<String> input = Files.readAllLines(Paths.get("aoc_24/src/day_6/input"));
int rows = input.size();
int cols = input.get(0).length();
char[][] map = new char[rows][cols];

Guard Initialization

for (int r = 0; r < rows; r++) {
    for (int c = 0; c < cols; c++) {
        if ("^v<>".indexOf(map[r][c]) != -1) {
            guardRow = r;
            guardCol = c;
            guardFacing = map[r][c];
            map[r][c] = '.'; // Clear the guard's position
        }
    }
}

Movement Directions

Map<Character, int[]> directions = Map.of(
    '^', new int[] {-1, 0},
    'v', new int[] {1, 0},
    '<', new int[] {0, -1},
    '>', new int[] {0, 1}
);

Turning Logic

Map<Character, Character> turnRight = Map.of(
    '^', '>',
    '>', 'v',
    'v', '<',
    '<', '^'
);

Visited Positions Tracking

Set<String> visited = new HashSet<>();
visited.add(guardRow + "," + guardCol);

Movement and Termination Logic

while (true) {
    int[] move = directions.get(guardFacing);
    int nextRow = guardRow + move[0];
    int nextCol = guardCol + move[1];

    if (nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols) {
        break; // Guard leaves the map
    }

    if (map[nextRow][nextCol] == '#') {
        guardFacing = turnRight.get(guardFacing); // Turn right
    } else {
        guardRow = nextRow;
        guardCol = nextCol;
        visited.add(guardRow + "," + guardCol);
    }
}

Part 2

Input Parsing

List<String> input = Files.readAllLines(Paths.get("aoc_24/src/day_6/input"));
int rows = input.size();
int cols = input.get(0).length();
char[][] map = new char[rows][cols];

Guard Initialization

for (int r = 0; r < rows; r++) {
    for (int c = 0; c < cols; c++) {
        if ("^v<>".indexOf(map[r][c]) != -1) {
            guardRow = r;
            guardCol = c;
            guardFacing = map[r][c];
            map[r][c] = '.'; // Clear the guard's position
        }
    }
}

Movement Directions

Map<Character, int[]> directions = Map.of(
    '^', new int[] {-1, 0},
    'v', new int[] {1, 0},
    '<', new int[] {0, -1},
    '>', new int[] {0, 1}
);

Turning Logic

Map<Character, Character> turnRight = Map.of(
    '^', '>',
    '>', 'v',
    'v', '<',
    '<', '^'
);

Valid Obstruction Positions

Set<String> validObstructions = new HashSet<>();

for (int r = 0; r < rows; r++) {
    for (int c = 0; c < cols; c++) {
        if (map[r][c] == '.' && !(r == guardRow && c == guardCol)) {
            map[r][c] = '#'; // Temporarily place obstruction

            if (causesLoop(map, guardRow, guardCol, guardFacing, directions, turnRight)) {
                validObstructions.add(r + "," + c);
            }

            map[r][c] = '.'; // Remove obstruction
        }
    }
}
System.out.println("Number of valid obstruction positions: " + validObstructions.size());

Loop Detection Helper Function

private static boolean causesLoop(char[][] map, int guardRow, int guardCol, char guardFacing,
                                  Map<Character, int[]> directions, Map<Character, Character> turnRight) {
    Set<String> seenStates = new HashSet<>();
    int rows = map.length;
    int cols = map[0].length;

    while (true) {
        String state = guardRow + "," + guardCol + "," + guardFacing;
        if (seenStates.contains(state)) {
            return true; // Loop detected
        }
        seenStates.add(state);

        int[] move = directions.get(guardFacing);
        int nextRow = guardRow + move[0];
        int nextCol = guardCol + move[1];

        if (nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols) {
            return false; // Guard leaves the map
        }

        if (map[nextRow][nextCol] == '#') {
            guardFacing = turnRight.get(guardFacing); // Turn right
        } else {
            guardRow = nextRow;
            guardCol = nextCol;
        }
    }
}

Day 7

Part 1

Input Parsing

• Parse the input file, where each line is in the format `<testValue>: <number1> <number2> …`
• `testValue` is a target number, and we determine if it can be computed by combining the given numbers with `+` or `*`.

List<String> input = Files.readAllLines(Paths.get("aoc_24/src/day_7/input"));
long totalCalibrationResult = 0;

for (String line : input) {
    String[] parts = line.split(": ");
    long testValue = Long.parseLong(parts[0]);  // Target value
    String[] numbers = parts[1].split(" ");
}

Validation Logic

• The `isValidEquation` function checks if any combination of operators (`+` or `*`) between the numbers matches the `testValue`.
• Evaluation is performed left-to-right.

private static boolean isValidEquation(long testValue, String[] numbers) {
    List<String> operators = Arrays.asList("+", "*");
    List<String[]> operatorCombinations = generateOperatorCombinations(numbers.length - 1, operators);

    for (String[] operatorCombination : operatorCombinations) {
        long result = Long.parseLong(numbers[0]);
        for (int i = 1; i < numbers.length; i++) {
            String operator = operatorCombination[i - 1];
            long num = Long.parseLong(numbers[i]);

            if (operator.equals("+")) {
                result += num;
            } else if (operator.equals("*")) {
                result *= num;
            }
        }

        if (result == testValue) {
            return true; // Equation is valid
        }
    }
    return false; // No valid equation found
}

Operator Combination Generator

• Generate all possible combinations of `+` and `*` for `n-1` positions (where `n` is the number of numbers).

private static List<String[]> generateOperatorCombinations(int numOperators, List<String> operators) {
    List<String[]> combinations = new ArrayList<>();
    generateOperatorCombinationsRecursive(new String[numOperators], 0, operators, combinations);
    return combinations;
}

private static void generateOperatorCombinationsRecursive(String[] current, int index, List<String> operators, List<String[]> combinations) {
    if (index == current.length) {
        combinations.add(current.clone());
        return;
    }

    for (String operator : operators) {
        current[index] = operator;
        generateOperatorCombinationsRecursive(current, index + 1, operators, combinations);
    }
}

Main Logic

• Iterate over each line of input.
• Parse `testValue` and numbers.
• If a valid equation exists for the line, add the `testValue` to the total calibration result.

for (String line : input) {
    String[] parts = line.split(": ");
    long testValue = Long.parseLong(parts[0]);
    String[] numbers = parts[1].split(" ");

    if (isValidEquation(testValue, numbers)) {
        totalCalibrationResult += testValue;
    }
}
System.out.println("Total Calibration Result: " + totalCalibrationResult);

Part 2

Input Parsing

• Reads an input file where each line is formatted as `<testValue>: <number1> <number2> …`.
• Parses `testValue` and the numbers to evaluate equations that could result in `testValue`.

List<String> input = Files.readAllLines(Paths.get("aoc_24/src/day_7/input"));
long totalCalibrationResult = 0;

for (String line : input) {
    String[] parts = line.split(": ");
    long testValue = Long.parseLong(parts[0]);  // Target value
    String[] numbers = parts[1].split(" ");
}

Validation Logic

• The `isValidEquation` function checks if any combination of operators (`+`, `*`, or `||`) between numbers can match the `testValue`.

• Includes support for a new operator `||`:

  • Concatenates the current `result` and the next number as strings.
  • Converts the concatenated string back to `long` to update the result.
• Evaluation is performed left-to-right.

private static boolean isValidEquation(long testValue, String[] numbers) {
    List<String> operators = Arrays.asList("+", "*", "||");
    List<String[]> operatorCombinations = generateOperatorCombinations(numbers.length - 1, operators);

    for (String[] operatorCombination : operatorCombinations) {
        long result = Long.parseLong(numbers[0]);
        for (int i = 1; i < numbers.length; i++) {
            String operator = operatorCombination[i - 1];
            long num = Long.parseLong(numbers[i]);

            if (operator.equals("+")) {
                result += num;
            } else if (operator.equals("*")) {
                result *= num;
            } else if (operator.equals("||")) {
                result = Long.parseLong(Long.toString(result) + Long.toString(num));
            }
        }

        if (result == testValue) {
            return true;
        }
    }
    return false;
}

Operator Combination Generator

• Generates all possible combinations of `+`, `*`, and `||` operators for `n-1` positions (where `n` is the number of numbers).
• Recursively builds the combinations.

private static List<String[]> generateOperatorCombinations(int numOperators, List<String> operators) {
    List<String[]> combinations = new ArrayList<>();
    generateOperatorCombinationsRecursive(new String[numOperators], 0, operators, combinations);
    return combinations;
}

private static void generateOperatorCombinationsRecursive(String[] current, int index, List<String> operators, List<String[]> combinations) {
    if (index == current.length) {
        combinations.add(current.clone());
        return;
    }

    for (String operator : operators) {
        current[index] = operator;
        generateOperatorCombinationsRecursive(current, index + 1, operators, combinations);
    }
}

Main Logic

• Iterates over each line of input.
• Parses `testValue` and numbers.
• Adds `testValue` to the total if a valid equation exists for the line.

for (String line : input) {
    String[] parts = line.split(": ");
    long testValue = Long.parseLong(parts[0]);
    String[] numbers = parts[1].split(" ");

    if (isValidEquation(testValue, numbers)) {
        totalCalibrationResult += testValue;
    }
}
System.out.println("Total Calibration Result: " + totalCalibrationResult);

Day 8

Resonant Collinearity

Part One

• Objective: Identify unique antinode locations within a map, considering two antennas of the same frequency in a specific configuration.
• Key Condition: Antinode occurs if two antennas of the same frequency are aligned such that one is twice as far from the antinode as the other.

• Steps:

  1. Parse the input map to locate antennas grouped by their frequency.
  2. For each frequency group, iterate through all antenna pairs.
  3. Calculate potential antinode positions based on the defined condition.
  4. Use a Set to store unique antinode positions.
  5. Return the size of the Set as the total unique antinode count.
• Code Snippet:

for (int i = 0; i < locations.size(); i++) {
    for (int j = i + 1; j < locations.size(); j++) {
        int[] a = locations.get(i);
        int[] b = locations.get(j);

        // Calculate midpoints and validate conditions
        if ((b[0] - a[0]) % 2 == 0 && (b[1] - a[1]) % 2 == 0) {
            int midRow = (a[0] + b[0]) / 2;
            int midCol = (a[1] + b[1]) / 2;
            antinodes.add(midRow + "," + midCol);
        }
    }
}

Part Two

• Objective: Update the model to include all positions perfectly aligned with at least two antennas of the same frequency.

• Key Changes:

  • Antinodes occur at all positions along the straight line between antennas of the same frequency.
  • Antennas themselves are also antinodes unless they are the only instance of their frequency.

• Steps:

  1. Parse the input map and group antennas by frequency.

  2. For each pair of antennas of the same frequency:

     • Calculate direction vectors (reduced using GCD).
     • Traverse along the direction vector in both forward and backward directions, marking all valid positions as antinodes.
  3. Add each antenna location directly to the set of antinodes.
  4. Return the size of the unique antinode set.
• Code Snippet:

int dr = b[0] - a[0];
int dc = b[1] - a[1];
int gcd = gcd(Math.abs(dr), Math.abs(dc));
dr /= gcd;
dc /= gcd;

// Traverse along the line
int row = a[0], col = a[1];
while (isWithinBounds(row, col, rows, cols)) {
    antinodes.add(row + "," + col);
    row += dr;
    col += dc;
}

Notes on Implementation

• Data Structures:

  • Map<Character, List<int[]>>: Stores antenna positions by frequency.
  • Set<String>: Tracks unique antinode positions.

• Utility Functions:

  • isWithinBounds: Ensures coordinates are within map dimensions.
  • gcd: Simplifies direction vectors to avoid redundant calculations.

Day 9

Part 1: Manipulating and Calculating Disk Placement

Concept: Creating and manipulating a disk structure based on input. Input is split into alternating "id" and "space" values. Example of creating the disk:

for (String character : lines.getFirst().split("")) {
    int num = Integer.parseInt(character);
    if (space) {
        for (int i = 0; i < num; i++) disk.add(-1);
    } else {
        for (int i = 0; i < num; i++) disk.add(id);
        id++;
    }
    space = !space;
}

• Key Learning: Understanding alternating patterns in input and their translation to a data structure.

• Problem Solving: Adjusting misplaced items.

  • Utilize a while loop to locate and correct misplaced "-1" values in the disk.

  • Example:

    if (disk.get(i) == -1) {
        int val = -1;
        while (val == -1) {
            val = disk.removeLast();
        }
        disk.add(i, val);
    }

• Final Calculation: Using BigInteger for large numbers.

  • Formula: index * value for each position in the disk.

  • Example:

    BigInteger count = BigInteger.ZERO;
    for (int i = 0; i < disk.size(); i++) {
        count = count.add(BigInteger.valueOf(i).multiply(BigInteger.valueOf(disk.get(i))));
    }

Part 2: Advanced Disk Rearrangement with Blocks

• Concept: Representing disk as a list of Block objects.

  • Block stores size and id.

  • Example:

    public static class Block {
        private int size;
        private int id;
        public Block(int size, int id) {
            this.size = size;
            this.id = id;
        }
    }

• Key Learning: Encapsulating logic into objects improves clarity and scalability.

• Space Management: Finding and fitting blocks into available spaces.

  • Utilize a fit method to split or match blocks.

  • Example:

    public List<Block> fit(Block work) {
        if (work.size > this.size) return null;
        List<Block> newList = new ArrayList<>();
        newList.add(work);
        if (work.size < this.size) {
            newList.add(new Block(this.size - work.size, -1));
        }
        return newList;
    }

• Problem Solving: Iterating backward through the disk to find and rearrange blocks into spaces.

  • Restart loop when a fit is found to ensure proper placement.

  • Example:

    for (int i = 0; i < diskPlace; i++) {
        Block possibleSpace = disk.get(i);
        if (possibleSpace.getId() == -1) {
            List<Block> blocks = possibleSpace.fit(work);
            if (blocks != null) {
                disk.remove(diskPlace);
                disk.add(diskPlace, new Block(work.getSize(), -1));
                for (int j = blocks.size() - 1; j >= 0; j--) {
                    disk.add(i, blocks.get(j));
                }
                break;
            }
        }
    }

• Final Calculation: Summing placements using block properties.

  • Ensure large calculations are done efficiently with BigInteger.

  • Example:

    BigInteger count = BigInteger.ZERO;
    int placement = 0;
    for (Block block : disk) {
        if (block.getId() != -1) {
            for (int j = 0; j < block.getSize(); j++) {
                count = count.add(BigInteger.valueOf(placement).multiply(BigInteger.valueOf(block.getId())));
                placement++;
            }
        } else {
            placement += block.getSize();
        }
    }

Day 10

Part 1: Counting Trails in a 2D Grid

• Concept: Navigating and processing a 2D grid based on specific rules.

  • Input is parsed into a 2D map from a list of strings.

  • Conversion logic for parsing:

    int[] map = new int[width * height];
    int i = 0;
    for (String line : lines) {
        if (line.isBlank()) continue;
        for (String character : line.trim().split("")) {
            map[i] = Integer.parseInt(character);
            i++;
        }
    }

• Recursive Approach: Traversing paths with a helper function countTrails.

  • Recursion halts on boundaries, invalid values, or when a sequence completes.

  • Example:

    private static Set<Point> countTrails(int[] map, int x, int y, int width, int height, int val) {
        if (x >= width || y >= height || x < 0 || y < 0 || map[y * width + x] != val) return new HashSet<>();
        if (val == 9) return Set.of(new Point(9, x, y));
    
        Set<Point> result = new HashSet<>();
        result.addAll(countTrails(map, x + 1, y, width, height, val + 1));
        result.addAll(countTrails(map, x - 1, y, width, height, val + 1));
        result.addAll(countTrails(map, x, y + 1, width, height, val + 1));
        result.addAll(countTrails(map, x, y - 1, width, height, val + 1));
        return result;
    }

• Key Learning: Recursive exploration of a grid with stateful logic for trail validity.

• Result Calculation: Sum the size of all unique trail sets.

  • Example:

    long count = 0;
    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            Set<Point> set = countTrails(map, x, y, width, height, 0);
            count += set.size();
        }
    }

Part 2: Enhanced Trail Counting with Weighted Points

• Concept: Counting trails with weights using a Map<Point, Integer> for aggregation.

  • Modified helper function countTrails2 tracks weights for each point.

  • Example:

    private static Map<Point, Integer> countTrails2(int[] map, int x, int y, int width, int height, int val) {
        if (x >= width || y >= height || x < 0 || y < 0 || map[y * width + x] != val) return new HashMap<>();
        if (val == 9) return Map.of(new Point(1, x, y), 1);
    
        Map<Point, Integer> result = new HashMap<>();
        checkDirection(map, x + 1, y, width, height, val, result);
        checkDirection(map, x - 1, y, width, height, val, result);
        checkDirection(map, x, y + 1, width, height, val, result);
        checkDirection(map, x, y - 1, width, height, val, result);
        return result;
    }

• Helper Method: checkDirection facilitates merging results for trail continuity.

  • Example:

    private static void checkDirection(int[] map, int x, int y, int width, int height, int val, Map<Point, Integer> result) {
        Map<Point, Integer> res = countTrails2(map, x, y, width, height, val + 1);
        for (Point p : res.keySet()) {
            result.merge(p, res.get(p), Integer::sum);
        }
    }

• Key Learning: Using a Map to manage complex trail state and weights for precise calculations.

• Result Calculation: Sum weighted trail counts.

  • Example:

    long count = 0;
    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            Map<Point, Integer> res = countTrails2(map, x, y, width, height, 0);
            for (int value : res.values()) {
                count += value;
            }
        }
    }

• Encapsulation of grid points as objects (Point) simplifies hash-based operations and improves code clarity.
• Using collections like Set and Map effectively is crucial for aggregating results in a structured way.

Would you like to make any adjustments or add further examples?

Day 12

Core Logic and Functionality

1. Coordinates Mapping:

   • A map (coords) stores coordinates of each character from the input. For each character, all the coordinates where it appears are stored as Point objects.

     for (int i = 0; i < in.size(); i++) {
         for (int j = 0; j < in.get(i).length(); j++) {
             coords.putIfAbsent(in.get(i).charAt(j), new ArrayList<>());
             coords.get(in.get(i).charAt(j)).add(new Point(i, j));
         }
     }

2. Flood Fill Algorithm with Stack:

   • A flood-fill algorithm is used to explore areas connected by the same character. The algorithm uses a stack to explore adjacent points recursively.

     ArrayDeque<Point> stack = new ArrayDeque<>();
     stack.push(co);
     while (!stack.isEmpty()) {
         var cur = stack.pop();
         // explore neighbors
     }

3. Fence Counting:

   • For each region, the number of "fences" (edges where the character changes) is counted. The algorithm checks for boundaries or differing characters adjacent to each point.

     if (nd.x < 0 || nd.y < 0 || nd.x >= in.size() || nd.y >= in.get(0).length()) {
         fence++;
     } else if (in.get(nd.x).charAt(nd.y) != ch) {
         fence++;
     }

4. Side Fetching Logic:

   • The fetchSides() method computes the number of "sides" based on the placement of fences, counting how the fences are arranged along rows and columns.

     for (var xx : cols.keySet()) {
         var xl = cols.get(xx);
         Collections.sort(xl);
         // logic for sorting and counting sides
     }

5. Area and Fence Calculations:

   • For each character, the area (number of connected points) and the number of fences are calculated. The result is a product of area and fence count.

     ret += area * fence;
     p2 += area * fetchSides(fences);

Core Logic and Functionality

• Coordinates mapping using a Map<Character, List<Point>> to track character positions.
• Flood-fill algorithm using a stack to explore regions of connected characters.
• Fence counting logic to identify boundaries and different characters.
• Side fetching logic to count the number of fences arranged along rows and columns.
• Area and fence calculations for each region to compute the final result.

Day 13

Part 1: Parsing Input and Solving Simultaneous Equations

• Goal: Parse input, extract button coefficients and prize values, solve simultaneous equations to find valid token costs.

• Key Concepts:

  • Input parsing using BufferedReader.
  • Using determinants to solve simultaneous equations.
  • Validating solutions for constraints (non-negative integers, valid m/n).

• Code Snippets:

  • Parsing Input:

    if (line.startsWith("Button A:")) {
        String[] parts = line.split(":")[1].split(",");
        current = new ButtonPrize();
        current.buttonAX = Integer.parseInt(parts[0].trim().split("\\+")[1]);
        current.buttonAY = Integer.parseInt(parts[1].trim().split("\\+")[1]);
    }

  • Solving Simultaneous Equations:

    int determinant = buttonAX * buttonBY - buttonBX * buttonAY;
    if (determinant == 0) return 0;  // No solution
    
    long mNumerator = prizeX * buttonBY - prizeY * buttonBX;
    long nNumerator = prizeY * buttonAX - prizeX * buttonAY;
    
    if (mNumerator % determinant != 0 || nNumerator % determinant != 0) return 0;
    long m = mNumerator / determinant;
    long n = nNumerator / determinant;
    return (m < 0 || n < 0) ? 0 : m * 3 + n;  // Calculate token costs

• Challenges Faced:

  • Edge cases with determinant = 0 or invalid input format.
  • Ensuring no negative values for m/n.

Part 2: Transforming Input Data

• Goal: Modify prize values with a fixed offset before calculations.

• Key Concepts:

  • Transforming input data programmatically.
  • Reusing the existing calculation logic after transformation.

• Code Snippets:

  • Prepending Offset to Prize Values:

    private void prependZeroes(ButtonPrize bp) {
        bp.setPrizeX(bp.getPrizeX() + 10000000000000L);
        bp.setPrizeY(bp.getPrizeY() + 10000000000000L);
    }

  • Reusing Logic:

    for (ButtonPrize bp : data) {
        prependZeroes(bp);
        count_part2 += calculateSimultaneousEquations(bp.getButtonAX(), bp.getButtonAY(),
                                                      bp.getButtonBX(), bp.getButtonBY(),
                                                      bp.getPrizeX(), bp.getPrizeY());
    }

• Challenges Faced:

  • Avoiding modification of original input logic while adding transformations.
  • Maintaining readability and modularity.

Day 14

Part 1: Simulating Robot Movement

• Concept: Simulating the movement of robots on a grid, wrapping their positions around the edges.

  • The grid has dimensions 101x103, and the robot positions wrap around when they move out of bounds.

  • Wrapping is implemented using a helper method:

    public static int wrap(int value, int max) {
        return ((value % max) + max) % max;
    }

• Key Learning: Efficiently handling movement on a toroidal grid (wrap-around behavior).

• Quadrant Assignment:

  • Robots are excluded from the middle row and column (x=50, y=51).

  • Quadrant assignments are based on the x and y positions:

    if (x < 50 && y < 51) {
        quadrantCounts[0]++;  // Top-left
    } else if (x >= 50 && y < 51) {
        quadrantCounts[1]++;  // Top-right
    } else if (x < 50 && y >= 51) {
        quadrantCounts[2]++;  // Bottom-left
    } else if (x >= 50 && y >= 51) {
        quadrantCounts[3]++;  // Bottom-right
    }

• Safety Factor Calculation:

  • The safety factor is the product of the number of robots in each quadrant:

    int safetyFactor = 1;
    for (int count : quadrantCounts) {
        safetyFactor *= count;
    }

Part 2: Identifying Patterns in Robot Positions

• Concept: Simulating grid states to find a specific pattern of robot alignment.

  • Robots move based on their initial velocity, and their positions are updated iteratively.
  • A grid is used to track robot positions, and columns are checked for specific patterns.
• Key Learning: Efficiently detecting consecutive robot positions in a grid column.

• Grid Initialization:

  • A helper method initializes a 2D grid with given dimensions:

    private int[][] initializeGrid(int rows, int cols) {
        return new int[rows][cols];
    }

• Position Calculation:

  • New positions are computed using the robot's velocity and current step, with wrapping:

    private int[] calculateNewPosition(int[] position, int[] velocity, int step, int[] tileDimensions) {
        return new int[] {
            (position[0] + step * (tileDimensions[0] + velocity[0])) % tileDimensions[0],
            (position[1] + step * (tileDimensions[1] + velocity[1])) % tileDimensions[1]
        };
    }

• Pattern Detection:

  • A helper method checks for consecutive robots in a column:

    private boolean hasConsecutiveInRow(List<Integer> positions, int requiredConsecutive) {
        Collections.sort(positions);
        int consecutiveCount = 0;
    
        for (int i = 1; i < positions.size(); i++) {
            if (positions.get(i) - positions.get(i - 1) == 1) {
                consecutiveCount++;
                if (consecutiveCount >= requiredConsecutive) {
                    return true;
                }
            } else {
                consecutiveCount = 0;
            }
        }
        return false;
    }

• Stopping Condition:

  • Simulation stops when a column has at least requiredConsecutive robots aligned.

—

### Supporting Components

• Data Representation:

  • PointAndVelocity encapsulates robot data, including position (PX, PY) and velocity (VX, VY):

    public static class PointAndVelocity {
        private int PX;
        private int PY;
        private int VX;
        private int VY;
    
        // Getters and setters
        public int getVX() { return VX; }
        public void setVX(int vX) { VX = vX; }
        public int getVY() { return VY; }
        public void setVY(int vY) { VY = vY; }
        public int getPX() { return PX; }
        public void setPX(int pX) { PX = pX; }
        public int getPY() { return PY; }
        public void setPY(int pY) { PY = pY; }
    }

• Input Parsing:

  • Robot data is parsed from a file or input list. Each robot's position and velocity are extracted:

    private List<PointAndVelocity> getPointAndVelocities() {
        List<PointAndVelocity> pvs = new ArrayList<>();
        try (BufferedReader reader = new BufferedReader(new FileReader(fetchFilePath()))) {
            String line;
            while ((line = reader.readLine()) != null) {
                String[] parts = line.split(" ");
                PointAndVelocity pav = new PointAndVelocity();
                pav.setPX(Integer.parseInt(parts[0].split(",")[0].replace("p=", "")));
                pav.setPY(Integer.parseInt(parts[0].split(",")[1].replace("p=", "")));
                pav.setVX(Integer.parseInt(parts[1].split(",")[0].replace("v=", "")));
                pav.setVY(Integer.parseInt(parts[1].split(",")[1].replace("v=", "")));
                pvs.add(pav);
            }
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
        return pvs;
    }

• Simulation Control:

  • Part 1 iterates for 100 steps, while Part 2 continues until a pattern is found or the maximum steps are reached.