2

I'm tring to solve this https://app.codility.com/programmers/custom_challenge/technetium2019/

Here is the text of the exercise:

You are given a matrix A consisting of N rows and M columns, where each cell contains a digit. Your task is to find a continuous sequence of neighbouring cells, starting in the top-left corner and ending in the bottom-right corner (going only down and right), that creates the biggest possible integer by concatenation of digits on the path. By neighbouring cells we mean cells that have exactly one common side.

    Write a function:

    class Solution { public String solution(int[][] A); }

    that, given matrix A consisting of N rows and M columns, returns a string which represents the sequence of cells that we should pick to obtain the biggest possible integer.

    For example, given the following matrix A:

    [9 9 7] [9 7 2] [6 9 5] [9 1 2]

    the function should return "997952", because you can obtain such a sequence by choosing a path as shown below:

    [9 9 *] [* 7 *] [* 9 5] [* * 2]

    Write an efficient algorithm for the following assumptions:

            N and M are integers within the range [1..1,000];
            each element of matrix A is an integer within the range [1..9].

I cannot reach 100% because I fail the case where the values of the matrix are all the same.

I tried to read the matrix from left to right and down as requested in the exercise but I think I misunderstood the question.

Here is my code:

static String sol(int[][] A) {

    String st = "";

    int v = A.length - 1;
    int h = A[0].length - 1;
    if (h == 0) {
        for (int i = 0; i <= v; i++) {
            st = st.concat(String.valueOf(A[i][0]));
        }
    } else if (v == 0) {
        for (int i = 0; i <= h; i++) {
            st = st.concat(String.valueOf(A[0][i]));
        }

    } else {

        st = st.concat(String.valueOf(A[0][0]));

        int m = 0; //vertical
        int n = 0; // horizontal
        while(m<v && n<h) {
            if(A[m+1][n]>=A[m][n+1]){
                st = st.concat(String.valueOf(A[m+1][n]));
                m++;
            }else {
                st = st.concat(String.valueOf(A[m][n+1]));
                n++;
            }

        }

        st = st.concat(String.valueOf(A[v][h]));
    }


    return st;
}

I think I need to traverse the matrix calculating the weight of the path but I don't know how to proceed.

Here I found a solution, but it seems limited to a 3x3 matrix.

1
  • 1
    Giving us a link to Codality is problematic. It doesn't land on the actual text of the challenge but instead to the start of some sort of test. Also, you really need to format your error text. That's really unreadable. Commented Nov 11, 2019 at 16:36

5 Answers 5

2

This is my solution to the problem, but it fails last speed-tests (I get 77%). Not sure if I can optimize it even more than this...

public static String solution(int[][] A) {
    // write your code in Java SE 8

    int al = A.length;
    int all = A[0].length;

    BigInteger[][] res = new BigInteger[al+1][];
    for(int i=0; i<al+1; i++){
        res[i] = new BigInteger[all+1];
        for(int j=0; j<all+1; j++){
            res[i][j] = BigInteger.valueOf(0);
        }
    }

    for(int i=1; i<al+1; i++){
        for(int j=1; j<all+1; j++){
            res[i][j] = res[i-1][j]
                    .max(res[i][j-1])
                    .multiply(BigInteger.valueOf(10))
                    .add(BigInteger.valueOf(A[i-1][j-1]));
        }
    }

    return res[al][all].toString();

}
0

I tried to optimize the solution from @Bojan Vukasovic. I guess it fails to get 100% due to 2 main reasons:

  • 2-dimensional array of BigInteger allocates too much memory (I had a OOM for big input array of size 1000-by-1000). To avoid this 2-dimensional res array could be replaced by 2 1-dimensional arrays of size m (number of rows). And the solution will look like this:

     static String solution(int[][] A) {
    
      final int m = A.length;
      final int n = A[0].length;
    
      MutableInteger[] result = new MutableInteger[m];
      result[0] = new MutableInteger(A[0][0], m + n + 1);
    
      // initial raw from up to down
      for (int i = 1; i < m; i++) {
          result[i] = new MutableInteger(result[i - 1]).append(A[i][0]);
      }
    
      for (int j = 1; j < n; j++) {
          // top row we only can reach from left
          result[0].append(A[0][j]);
          // moving down
          for (int i = 1; i < m; i++) {
              MutableInteger previous = result[i - 1];
              MutableInteger current = result[i];
              // only replace if previous is bigger
              if (previous.compareTo(current) > 0) {
                  result[i].copy(previous);
              }
              result[i].append(A[i][j]);
          }
      }
    
      return result[m - 1].toString();
    }
    
  • Now Out Of Memory gone but 2 tests fail with a timeout. To fix it a new class MutableInteger with an optimized compareTo method has been introduced. And optimized multiply by 10 + value operation. Internally it has an array of digits like BigInteger but can compare long arrays for this problem more efficiently. Multiplication replaced by append method.

    private static class MutableInteger {
      int[] digits;
      int position;
      int sum;
      int capacity;
      int maxIndex;
    
      private MutableInteger(int digit, int capacity) {
          this.digits = new int[capacity];
          digits[0] = digit;
          sum = digit;
          this.capacity = capacity;
          position++;
      }
    
      private MutableInteger(MutableInteger value) {
          digits = value.digits.clone();
          position = value.position;
          capacity = value.capacity;
          sum = value.sum;
          maxIndex = value.maxIndex;
      }
    
      private MutableInteger append(int value) {
          digits[position] = value;
          position++;
          sum = Math.abs(sum * 10 + value); // here integer overflow to compare exact digits efficiently
          return this;
      }
    
      private void copy(MutableInteger value) {
          digits = value.digits.clone();
          position = value.position;
          capacity = value.capacity;
          sum = value.sum;
      }
    
      private int compareTo(MutableInteger other) {
          // optimization for long arrays comparison
          if (this.sum != other.sum) {
              int start = Math.min(this.maxIndex, other.maxIndex);
              for (int i = start; i < this.position; i++) {
                  int left = this.digits[i];
                  int right = other.digits[i];
                  if (left != right) {
                      other.maxIndex = i; // don't change this.maxIndex, it will be used in next iteration
                      return Integer.compare(left, right);
                  }
              }
          }
          return 0;
      }
    
      @Override
      public String toString() {
          StringBuilder out = new StringBuilder(position);
          for (int i = 0; i < position; i++) {
              out.append(digits[i]);
          }
          return out.toString();
      }
     }
    

the class is quite simple with 2 variables for optimization. sum (2 equals arrays have the same sum value even after integer overflow) and maxIndex (used to skip comparison from beginning the arrays of digits).

0

I tested this solutuion and it worked for me:

// you can also use imports, for example:
import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public String solution(int[][] A) {
        int i = 0;
        int j = 0;

        String result = String.valueOf(A[0][0]);
        String outout = compare(i, j, A);

        return result + outout;
    }

    public String compare(int i, int j, int[][] A) {
        int h = A.length - 1;
        int v = A[0].length - 1;

        if (i == h && j == v) {
            return "";
        }

        if (j == v) {
            return A[i + 1][j] + compare(i + 1, j, A);
        }

        if (i == h) {
            return A[i][j + 1] + compare(i, j + 1, A);
        }

        if (A[i][j + 1] > A[i + 1][j]) {
            return A[i][j + 1] + compare(i, j + 1, A);
        }
        else if (A[i][j + 1] < A[i + 1][j]) {
            return A[i + 1][j] + compare(i + 1, j, A);
        } else {
            String bottom = A[i + 1][j] + compare(i + 1, j, A);
            String right = A[i][j + 1] + compare(i, j + 1, A);

            if (Integer.parseInt(bottom) > Integer.parseInt(right)) {
                return bottom;
            } else {
                return right;
            }
        }
    }
}
0

My solution using recursion:

import java.math.BigInteger;

class Solution {
    static int[][] array;
    BigInteger selectedNumSeq = BigInteger.valueOf(0);
    int columnCount;
    int rowCount;
    int i = 0;
    public String solution(int[][] A) {
        int m = 0;
        int n = 0;
        array = A;
        columnCount = A.length; // 2
        rowCount = A[0].length; // 3
        StringBuilder startingChar = new StringBuilder(String.valueOf(array[m][n]));
        solveMe(m, n, startingChar);
        return String.valueOf(selectedNumSeq);
    }

    private void solveMe(int m, int n, StringBuilder answerItem) {
        StringBuilder currentSeq = new StringBuilder(answerItem);

        if (m +1 < columnCount) {
            int mm = m+1;
            String x = currentSeq.toString() + (array[mm][n]);
            solveMe(mm, n, new StringBuilder(x));
        }

        if (n +1 < rowCount) {
            int nn = n+1;
            String y = currentSeq.toString() + (array[m][nn]);
            solveMe(m, nn, new StringBuilder(y));
        }

        if ((n +1 == rowCount) && (m +1 == columnCount)) {
            BigInteger tempNumSeq = new BigInteger(answerItem.toString());
            if(selectedNumSeq.compareTo(tempNumSeq) < 0) {
                selectedNumSeq = tempNumSeq;
            }
        }
    }
}

Correctness: 100% (hence this will be correct for any input)

-1

Here is my solution to the problem, it will fail some cases though. I need to get more test cases to improve the algorithm.

console.log(solution([[ 9, 2, 9, 3, 5 ],
                      [ 5, 3, 9, 5, 1 ],
                      [ 5, 6, 4, 9, 1 ],
                      [ 4, 3, 8, 4, 5 ],
                      [ 1, 4, 3, 5, 3 ]]));
console.log(solution([[ 3, 6, 3, 8, 5, 3, 9, 8, 8, 6, 2, 4, 3, 8, 1 ],
                     [ 5, 6, 8, 3, 3, 7, 5, 4, 4, 3, 2, 6, 9, 7, 6 ],
                     [ 9, 2, 9, 3, 5, 9, 4, 5, 2, 9, 9, 2, 2, 5, 5 ],
                     [ 5, 3, 9, 5, 1, 7, 1, 2, 1, 6, 8, 6, 3, 8, 8 ],
                     [ 5, 6, 4, 9, 1, 9, 7, 8, 8, 2, 8, 6, 2, 8, 4 ],
                     [ 4, 3, 8, 4, 5, 5, 4, 6, 9, 1, 6, 3, 6, 6, 1 ],
                     [ 1, 4, 3, 5, 3, 8, 6, 7, 9, 5, 5, 2, 8, 1, 4 ],
                     [ 1, 7, 9, 4, 9, 4, 6, 9, 2, 1, 2, 1, 4, 2, 1 ],
                     [ 7, 9, 7, 9, 1, 6, 4, 3, 8, 3, 9, 4, 5, 7, 8 ],
                     [ 7, 1, 2, 6, 3, 9, 8, 8, 4, 8, 6, 8, 3, 5, 4 ]]));
console.log(solution([[ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 ],
            [ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 ],
            [ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 ],
            [ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 ],
            [ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 ],
            [ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 ],
            [ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 ],
            [ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 ],
            [ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 ],
            [ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 ]]))
function solution(A) {
var nextindex = 0;
var solution = A[0][0].toString();

for (i=0;i<A.length;i++){
        var row = A[i];
		 
         for(j=0;j<row.length;j++){
            
            var valueofright = row[nextindex+1];
            var valueofnextright = row[nextindex+2];
            
            if(i+1 < A.length){
               var valueofdown = A[i+1][nextindex];
             if(i+2 < A.length){
               var valueofnextdown = A[i+2][nextindex];
             }
            }else{
                 for (k=nextindex+1; k<row.length;k++){

                   solution = solution+row[k].toString();
                  }
                   break;
            }

            if((valueofdown == valueofright && valueofnextright > valueofnextdown)  || valueofright > valueofdown && nextindex+1 <= row.length){
               solution = solution+valueofright.toString();
               
     
               nextindex++;
               
              
            }else {
               solution = solution+valueofdown.toString();
            
               
               break;
            }

           
         }
     
    }
   return solution;
}

Explanation The algorithm tries to calculate the weight of the path by the factor of two steps.

We start from the leftmost corner and check if the right value is bigger than value below the current position, and to check the path weight I also look forward to one more hoop. If next hoops on right and down are equal than the decision to go down or right is made by the next consecutive numbers. You can improve the algorithm by adding recursive function to check if the next ones are equal until you find a different digit.

My algorithm works with all the normal scenarios and also solves the problem if all the elements in the matrix are same.

3
  • 1
    The question says "in java" and is tagged java. Posting a different incorrect attempt, in a different language, does not answer the question. You could at least explain how your attempt works, what it does differently to the code from the question, and how that addresses the bug in the code from the question (if it does).
    – kaya3
    Commented Dec 21, 2019 at 2:00
  • I downvoted because the algorithm is incorrect. As you said yourself, it fails some test cases. If there is some insight to be gained from your incorrect algorithm, it would be more useful to describe that insight with words.
    – kaya3
    Commented Dec 21, 2019 at 21:15
  • I didn't say it fails some test cases, I said it "will" because of the info in the question I could only come up with limited test cases and did you run the snippet? It addresses the concern from the question which was about the test case of the same numbers.
    – Yousaf
    Commented Dec 21, 2019 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.