Example implementation of ADS Exercise

Serie3.java

package ads;

import java.text.MessageFormat;
import java.util.*;

/**
 * Created by sythelux on 25.04.17.
 */
public class Serie3 {
    private static Random random = new Random();

    public static void main(String[] args) {
        Aufgabe3_3();
        Aufgabe3_4();
    }

    private static void Aufgabe3_4() {
        System.out.println("Aufgabe 3.3");
        final int n = 10;
        int x = 80;

        int a[][] = new int[n][n];
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                a[i][j] = random.nextInt(Byte.MAX_VALUE);
            }
        }
        sortMatrix(a);
        System.out.println(Arrays.deepToString(a).replace("], ", "], \n\t").replace("[[", "[\n\t[").replace("]]", "]\n]"));


        //approach #1

        for (int i = 0; i < n; i++) {
            if (a[i / n][i % n] == x) {
                System.out.println("x:" + x + ", i:" + i + ", a[i / n][i % n]:" + a[i / n][i % n]);
            }
        }
        //nope

        //approach 2: centered and walk around to borders,
//        Pair pair3_4 = findPair3_4_Aron(n, x, a);
        Pair pair3_4 = findPair3_4_funktioniert(n, x, a);
        if (pair3_4 == null) {
            System.out.println("NEIN");
        } else {
            System.out.println(pair3_4);
        }
    }

    private static Pair findPair3_4_funktioniert(int n, int x, int[][] a) {
        int l = 0, r = n - 1;
        while (l < n && r > 0) {
            System.out.println(MessageFormat.format("x:{0}, l:{1}, r:{2}, a[l][r]:{3}", x, l, r, a[l][r]));
            if (a[l][r] == x) return new Pair(l, r);
            if (a[l][r] > x) r--;
            if (a[l][r] < x) l++;
        }
        return null;
    }

    private static Pair findPair3_4_Aron(int n, int x, int[][] a) { //funktioniert nicht
        int i = n / 2, j = n / 2;
        while (a[i][j] != x) {
            System.out.println(MessageFormat.format("x:{0}, i:{1}, j:{2}, a[i][j]:{3}", x, i, j, a[i][j]));
            if (a[i][j] > x) {
                if (a[i - 1][j] >= x && !(i - 2 < 0)) {
                    i--;
                } else if (a[i][j - 1] >= x && !(j - 2 < 0)) {
                    j--;
                } else {
                    System.out.println(MessageFormat.format("should be between i:{0}, j:{1} and i:{2}, j:{3}, but is not", i, j, i - 1, j - 1));
                    System.out.println(MessageFormat.format("x:{0}, i:{1}, j:{2}, a[i][j]:{3}", x, i - 1, j - 1, a[i - 1][j - 1]));
                    return null;
                }
            } else if (a[i][j] < x) {
                if (a[i + 1][j] <= x && !(i + 2 >= n)) {
                    i++;
                } else if (a[i][j + 1] <= x && !(j + 2 >= n)) {
                    j++;
                } else {
                    System.out.println(MessageFormat.format("should be between i:{0}, j:{1} and i:{2}, j:{3}, but is not", i, j, i + 1, j + 1));
                    System.out.println(MessageFormat.format("x:{0}, i:{1}, j:{2}, a[i][j]:{3}", x, i + 1, j + 1, a[i + 1][j + 1]));
                    return null;
                }
            }
        }
        System.out.println("x:" + x + ", i:" + i + ", j:" + j + ", a[i][j]:" + a[i][j]);
        return new Pair(i, j);
    }

    public static void sortMatrix(final int[][] matrix) {
        // Assuming the matrix is rectangular
        final int n = matrix.length;
        final int m = matrix[0].length;

        List<Integer> list = new AbstractList<Integer>() {
            @Override
            public Integer set(int index, Integer element) {
                return matrix[index / m][index % m] = element;
            }

            @Override
            public Integer get(int index) {
                return matrix[index / m][index % m];
            }

            @Override
            public int size() {
                return n * m;
            }
        };
        Collections.sort(list);
    }

    private static void Aufgabe3_3() {
        final int s = 10;
        final int t = 15;
        System.out.println("Aufgabe 3.3");

        //Byte.MAX_VALUE, weil sonst die wahrscheinlichkeit zu gering ist, dass er überhupt was findet
        int a[] = random.ints(s, 0, Byte.MAX_VALUE).toArray();
        int b[] = random.ints(t, 0, Byte.MAX_VALUE).toArray();

        Arrays.sort(a);
        Arrays.sort(b);

        System.out.println("a: " + Arrays.toString(a));
        System.out.println("b: " + Arrays.toString(b));

        Pair p = findPair3_3(a, b);
        if (p == null) {
            System.out.println("NEIN");
        } else {
            System.out.println(p);
        }
    }

    private static Pair findPair3_3(int[] a, int[] b) {
        int minA, minB, maxA, maxB;
        minA = a[0];
        maxA = a[a.length - 1];
        minB = b[0];
        maxB = b[b.length - 1];
        if (maxA < minB) {
            System.out.println("Alle Zahlen von a sind zu klein");
        } else if (maxB < minA) {
            System.out.println("Alle Zahlen von b sind zu klein");
        } else {
            int laufZahl = 0;
            int j = 0;
            for (int i = 0; i < a.length && j < b.length; ) {
                System.out.println(MessageFormat.format("i:{0}, i:{1}, a[i]:{2}, b[j]:{3}", i, j, a[i], b[j]));
                if (a[i] == b[j]) {
                    //es werden beide verglichen, wenn a[i] = b[i] dann pair gefunden
                    return new Pair(i, j);
                } else if (a[i] < b[j]) {
                    //wenn a[i]<b[j] dann i++
                    i++;
                } else if (a[i] > b[j]) {
                    //wenn a[i]>b[j] dann j++
                    j++;
                }
                laufZahl += 1; //2 wegen if und anweisung in if, vielleicht nur +=1?
            }
            System.out.println("laufZeit: " + (laufZahl + 1) + " von " + (a.length + b.length)); //im wurschtkäs hat er alles durchlaufen und nix gefunden.
        }
        return null;
    }

    private static class Pair {
        int i, j;

        public Pair(int i, int j) {
            this.i = i;
            this.j = j;
        }

        @Override
        public String toString() {
            return "Pair{" +
                    "i:" + i +
                    ", j:" + j +
                    '}';
        }
    }
}