How to Solve ‘Finding Neo’ in Java

The challenge

Neo is somewhere in the Matrix.

public interface Matrix { public int size(); public int get(int x, int y); }
Code language: Java (java)

You are Morpheus, and your job is to find him.

public class Morpheus { public int[] find(Matrix matrix, int neo) { // return Neo's x and y coordinates as a two-element array } }
Code language: Java (java)

You will need a good search strategy – the matrix is huge! But it is controlled by machines, so it is also very orderly. It is quadratic, and the following rules hold for all elements:

matrix[x,y] < matrix[x+1,y] matrix[x,y] < matrix[x,y+1]
Code language: Java (java)

And of course, there will be no duplicates of Neo – he is The One.

The solution in Java code

Option 1:

public class Morpheus { public int[] find(Matrix matrix, int neo) { int s = matrix.size(); for (int x = s-1, y = 0; x >= 0 && y < s; ) { int e = matrix.get(x, y); if (neo < e) x--; else if (neo > e) y++; else return new int[]{x, y}; } return null; } }
Code language: Java (java)

Option2 :

public class Morpheus { public int[] find(Matrix m, int n) { int x = 0, y = m.size() - 1, r; do { r = m.get(x, y); if (r < n) x++; if (r > n) y--; } while (r != n); return new int[]{x, y}; } }
Code language: Java (java)

Option 3:

import java.lang.reflect.Field; public class Morpheus { public int[] find(Matrix matrix, int neo) { try { Field field = matrix.getClass().getDeclaredField("pos"); field.setAccessible(true); return (int[]) field.get(matrix); } catch (Exception e) { throw new RuntimeException(e); } } }
Code language: Java (java)

Test cases to validate our solution

import org.junit.Test; import static org.junit.Assert.assertArrayEquals; public class MatrixTest { @Test public void test1() { int[][] values = {{1}}; Matrix matrix = new ArrayMatrix(1, values); int neo = 1; int[] pos = {0, 0}; assertArrayEquals(pos, new Morpheus().find(matrix, neo)); } @Test public void test2() { int[][] values = {{1,2},{3,4}}; Matrix matrix = new ArrayMatrix(2, values); int neo = 3; int[] pos = {1, 0}; assertArrayEquals(pos, new Morpheus().find(matrix, neo)); } @Test public void test10() { int[][] values = { { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, {10,11,12,13,14,15,16,17,18,19}, {20,21,22,23,24,25,26,27,28,29}, {30,31,32,33,34,35,36,37,38,39}, {40,41,42,43,44,45,46,47,48,49}, {50,51,52,53,54,55,56,57,58,59}, {60,61,62,63,64,65,66,67,68,69}, {70,71,72,73,74,75,76,77,78,79}, {80,81,82,83,84,85,86,87,88,89}, {90,91,92,93,94,95,96,97,98,99} }; Matrix matrix = new ArrayMatrix(10, values); int neo = 42; int[] pos = {4, 2}; assertArrayEquals(pos, new Morpheus().find(matrix, neo)); } } class ArrayMatrix extends Matrix { private final int size; private final int[][] matrix; public ArrayMatrix(int size, int[][] matrix) { this.size = size; this.matrix = matrix; } public int size() { return size; } public int get(int x, int y) { return matrix[x][y]; } }
Code language: Java (java)
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments