aoc2021-17

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Solution17B {
  public static void main(String[] args) {
    String s = null;
    try {
      File myObj = new File(args[0]);
      Scanner myReader = new Scanner(myObj);
      s = myReader.nextLine();
      myReader.close();
    } catch (FileNotFoundException e) {
      System.out.println("An error occurred.");
      e.printStackTrace();
    }
    Pattern pattern = Pattern.compile("target area: x=(-?\\d+)..(-?\\d+), y=(-?\\d+)..(-?\\d+)");
    Matcher matcher = pattern.matcher(s);
    matcher.matches();
    int minX = Integer.valueOf(matcher.group(1));
    int maxX = Integer.valueOf(matcher.group(2));
    int minY = Integer.valueOf(matcher.group(3));
    int maxY = Integer.valueOf(matcher.group(4));
    // The slowest initial VX possible is the smallest one that gets the probe
    // past the minimum X boundary of the target area when the X velocity
    // reaches 0.
    int minVX = minX;
    // Find the largest that does not get the probe in the target area.
    // Binary search would theoretically be faster.
    while ((minVX*(minVX+1))/2 >= minX) {
      minVX--;
    }
    // The next one must get us past the minimum X boundary of the target area.
    minVX++;
    System.out.println("Min VX: " + minVX);
    if ((minVX*(minVX+1))/2 > maxX) {
      // I think this is possible but I cannot be certain...
      // Anyways, even if we overshoot when the probe will reach 0 X velocity,
      // we might be in the target area at the previous steps, so this is still
      // a good lower bound.
      System.out.println("WARN: Min VX overshoots.");
    }
    // Anything faster then the maximum X boundary will overshoot in the very
    // first step.
    int maxVX = maxX;
    System.out.println("Max VX: " + maxVX);
    // Anything faster then the minimum Y boundary will overshoot in the very
    // first step.
    int minVY = minY;
    System.out.println("Min VY: " + minVY);
    // Assume that the Y boundaries are alwasy negative (can we relax this?).
    // The fastest initial VY possible is one that makes the probe shoot upward,
    // reach 0, and then reach the minimum Y boundary at the very next step.
    int maxVY = -minY-1;
    System.out.println("Max VY: " + maxVY);
    if (2*maxVY+1 < maxVX) {
      // Ideally, we need the slowest X velocity to be slow enough so that the
      // probe can shoot upward and then come down by the time the probe reaches
      // 0 X velocity. Otherwise we are not guaranteed that there exists a
      // suitable VX that we can use with the fastest VY.
      System.out.println("WARN: Max VY min VX combination is not good.");
    }
    // Ignore potential warnings and assume that the fastest VY plus slowest VX
    // combination works... Otheriwise I could always use the search below to
    // keep track of the fastest initial VY or of the tallest Y point that lead
    // to a correct result.
    System.out.println("Max Y: " + (maxVY*(maxVY+1))/2);
    // Now brute force in the reduced search space.
    int count = 0;
    for (int vx = minVX; vx <= maxVX; vx++) {
      for (int vy = minVY; vy <= maxVY; vy++) {
        int x = 0, y = 0, vxc = vx, vyc = vy;
        // We could also check that (vxc > 0 || x >= minX) to try to weed out
        // bad results a little bit earlier.
        while (x <= maxX && y >= minY) {
          if (x >= minX && y <= maxY) {
            count++;
            break;
          }
          x += vxc;
          y += vyc;
          if (vxc > 0) vxc--;
          vyc--;
        }
      }
    }
    System.out.println("Count: " + count);
  }
}