# aoc2021-17

unknown
java
2 years ago
3.8 kB
4
Indexable
Never
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]);
} 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);
}
}