There is 2D array long[50][50] which is filled with random numbers from 0 to 100. I need to find the longest way from the biggest (or first highest) to the smallest. You can move up, down, left and right.
I found how to find single way: find the biggest nearest number (but no bigger, that it is) and move there.
public static int measure = 50;
public long[][] map = new long[measure][measure];
My move methods:
private long moveUp(int x, int y) {
if (x >= measure || x == 0 || y == 0 || y >= measure) {
return -1;
}
return map[x - 1][y];
}
private long moveRight(int x, int y) {
if (x >= measure || x == 0 || y == 0 || y >= measure) {
return -1;
}
return map[x][y + 1];
}
private long moveDown(int x, int y) {
if (x >= measure || x == 0 || y == 0 || y >= measure) {
return -1;
}
return map[x + 1][y];
}
private long moveLeft(int x, int y) {
if (x >= measure || x == 0 || y == 0 || y >= measure) {
return -1;
}
return map[x][y - 1];
}
Find nearest biggest:
private long rightWay(int x, int y) {
List<Long> pickList = new ArrayList<>();
long up = moveUp(x, y);
long right = moveRight(x, y);
long down = moveDown(x, y);
long left = moveLeft(x, y);
if (up != -1 && up < map[x][y]) {
pickList.add(moveUp(x, y));
}
if (right != -1 && right < map[x][y]) {
pickList.add(moveRight(x, y));
}
if (down != -1 && down < map[x][y]) {
pickList.add(moveDown(x, y));
}
if (left != -1 && left < map[x][y]) {
pickList.add(moveLeft(x, y));
}
if (pickList.size() == 0) {
return -1;
} else {
Collections.sort(pickList);
for (int i = 0; i < pickList.size(); i++) {
System.out.println("right way " + i + " -> " + pickList.get(i));
}
return pickList.get(pickList.size() - 1);
}
}
Then find the longest way using only nearest biggest values:
private void findRoute(long[][] route, long current, int width, int height) {
System.out.println("width = " + width + " height = " + height);
long nextSpetHeight = rightWay(width, height);
System.out.println("max = " + nextSpetHeight);
if (nextSpetHeight == -1) {
return;
} else {
if (nextSpetHeight == moveUp(width, height)) {
findRoute(route, nextSpetHeight, width - 1, height);
way.add(nextSpetHeight);
}
if (nextSpetHeight == moveRight(width, height)) {
findRoute(route, nextSpetHeight, width, height + 1);
way.add(nextSpetHeight);
}
if (nextSpetHeight == moveDown(width, height)) {
findRoute(route, nextSpetHeight, width + 1, height);
way.add(nextSpetHeight);
}
if (nextSpetHeight == moveLeft(width, height)) {
findRoute(route, nextSpetHeight, width, height - 1);
way.add(nextSpetHeight);
}
}
}
And the size of way would be the length of such route.
But now I don't know how to find all possible routes from some coordinates to find the longest of them. I mean I don't know what it is a best way to come back on "fork" and continue with another route.
I hope the explanation is clear. Thanks in advance.
If you see this problem like a directed graph problem, you can apply the known graphs algorithm.
This is an implementation of Johnson's algorithm
At the first time, It search the local-max values on points matrix. They'll be the first candidates, then the algorithm iterates over candidates, It follows the Johnson's algorithm. And It computes all lengths to any point.
public class Solver {
private static class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
private static class State {
static State best;
State parent;
List<State> children = new ArrayList<>();
int length;
Point p;
public State(State parent, Point p) {
this.parent = parent;
this.p = p;
this.length = parent.length + 1;
this.parent.children.add(this);
if (best.length < length) {
best = this;
}
}
public State(Point p) {
this.parent = null;
this.p = p;
this.length = 1;
if (best == null) {
best = this;
}
}
public void checkParent(State st) {
if (st.length + 1 > length) {
parent.children.remove(this);
this.parent = st;
updateLength();
}
}
private void updateLength() {
this.length = parent.length + 1;
if (best.length < length) {
best = this;
}
for (State state : children) {
state.updateLength();
}
}
}
public static boolean checkRange(int min, int max, int x) {
return min <= x && x < max;
}
public static boolean maxLocal(int x, int y, int[][] points) {
int value = points[x][y];
if (x > 0 && points[x - 1][y] > value) {
return false;
}
if (y > 0 && points[x][y - 1] > value) {
return false;
}
if (x < points.length - 1 && points[x + 1][y] > value) {
return false;
}
return !(y < points[0].length - 1 && points[x][y + 1] > value);
}
private static List<Point> getNeigbours(int x, int y, int[][] points) {
int value = points[x][y];
List<Point> result = new ArrayList<>(4);
if (x > 0 && points[x - 1][y] < value) {
result.add(new Point(x - 1, y));
}
if (y > 0 && points[x][y - 1] < value) {
result.add(new Point(x, y - 1));
}
if (x < points.length - 1 && points[x + 1][y] < value) {
result.add(new Point(x + 1, y));
}
if (y < points[0].length - 1 && points[x][y + 1] < value) {
result.add(new Point(x, y + 1));
}
return result;
}
private static int[][] generateRandomPoint(int width, int height, int max) {
int[][] result = new int[width][height];
Random rand = new Random(0L);
for (int i = 0; i < result.length; i++) {
for (int j = 0; j < result[i].length; j++) {
result[i][j] = rand.nextInt(max);
}
}
return result;
}
public static void main(String[] args) {
int[][] points = generateRandomPoint(50, 50, 100);
State[][] states = new State[points.length][points[0].length];
List<State> candidates = new ArrayList<>(points.length*points[0].length);
for (int x = 0; x < points.length; x++) {
for (int y = 0; y < points[0].length; y++) {
if (maxLocal(x, y, points)) {
states[x][y] = new State(new Point(x, y));
candidates.add(states[x][y]);
}
}
}
while (!candidates.isEmpty()) {
State candidate = candidates.remove(candidates.size() - 1);
for (Point p : getNeigbours(candidate.p.x, candidate.p.y, points)) {
if (states[p.x][p.y] == null) {
states[p.x][p.y] = new State(candidate, p);
candidates.add(states[p.x][p.y]);
} else {
states[p.x][p.y].checkParent(candidate);
}
}
}
State temp = State.best;
List<Point> pointList = new ArrayList<>(temp.length);
while (temp != null) {
pointList.add(temp.p);
temp = temp.parent;
}
for (int x = 0; x < points.length; x++) {
for (int y = 0; y < points[0].length; y++) {
if (points[x][y] < 10) {
System.out.print(" ");
} else if (points[x][y] < 100) {
System.out.print(" ");
}
System.out.print(points[x][y] + " ");
}
System.out.println();
}
System.out.println("-------");
for (Point point : pointList) {
System.out.println(point.x + ", " + point.y + " -> " + points[point.x][point.y]);
}
System.out.println();
System.out.println("lengths:");
for (int x = 0; x < points.length; x++) {
for (int y = 0; y < points[0].length; y++) {
if (states[x][y].length < 10) {
System.out.print(" ");
}
System.out.print(states[x][y].length + " ");
}
System.out.println();
}
}
}
It prints (with 10 x 10 matrix)
First block: The 2D-matrix (10x10)
Second block: The coordinates of the longest solution from min to max values.
Last block: The Coordinate's length.
output:
60 48 29 47 15 53 91 61 19 54
77 77 73 62 95 44 84 75 41 20
43 88 24 47 52 60 3 82 92 23
45 45 37 87 2 62 25 53 38 35
60 75 55 30 98 91 74 36 12 62
19 77 16 46 7 16 8 37 43 47
87 88 5 58 8 17 51 18 58 18
38 72 57 51 26 80 97 62 35 20
67 73 17 69 5 52 89 43 1 41
23 80 68 14 16 23 57 22 5 71
-------
5, 4 -> 7
6, 4 -> 8
7, 4 -> 26
7, 3 -> 51
7, 2 -> 57
7, 1 -> 72
8, 1 -> 73
9, 1 -> 80
lengths:
2 3 6 5 6 2 1 4 5 1
1 2 3 4 1 5 2 3 4 5
6 1 7 6 5 4 5 2 1 4
5 4 5 1 6 3 4 3 4 3
4 3 4 5 1 2 3 5 5 1
5 2 5 2 8 4 5 4 3 2
2 1 5 1 7 3 2 4 1 5
4 3 4 5 6 2 1 2 3 4
3 2 5 1 7 3 2 3 4 2
4 1 2 6 5 4 3 4 5 1