Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

This is a solution for the problem named Codes on the kattis platform:

Given a generator matrix of a linear code, calculate the minimum distance of the code.

I'm looking for reviews on optimization and best practices. Code readability should be preserved.

public static class LinearCode {
   private int[][] generator;
   private int n;
   private int k;

   public LinearCode(int[][] generator, int n, int k) {
      this.generator = generator;
      this.n = n;
      this.k = k;
   }

   public int getMinimumDistance() {
      int minDistance = n;
      int maxKString = 1 << k;

      // generate all k-strings
      for (int i = 1; i < maxKString; i++) {
          int kstring = i;
          int distance = 0;

          // matrix multiplication
          for (int j = 0; j < n; j++) {
              int p = 0;
              for (int z = 0; z < k; z++) {
                  int a = generator[j][k-z-1];
                  int b = (kstring >>> z) & 1;
                  p = (p + a * b) & 1;
              }
              // distance as number if 1 bits
              distance += p;
          }

          minDistance = Math.min(minDistance, distance);
      }

      return minDistance;
   }
}
share|improve this question

1 Answer 1

The n and k parameters seem pointless: you can derive them from the dimensions of the received generator matrix:

int n = generator.length;
int k = generator[0].length;

Instead of this:

for (int j = 0; j < n; j++) {

You could replace using for-each, which is just more natural:

for (int[] row : generator) {

I don't really see a reason to store the parameters as fields. The class doesn't need to hold data. You need just a pure function, so this can be a public static method.

Putting it together

Applying the above suggestions (+ a few minor things):

public static int getMinimumDistance(int[][] generator) {
    int n = generator.length;
    int k = generator[0].length;
    int minDistance = n;
    int maxKString = 1 << k;

    // generate all k-strings
    for (int i = 1; i < maxKString; i++) {
        int distance = 0;

        // matrix multiplication
        for (int[] row : generator) {
            int p = 0;
            for (int z = 0; z < k; z++) {
                int a = row[k - z - 1];
                int b = (i >>> z) & 1;
                p = (p + a * b) & 1;
            }
            // distance as number if 1 bits
            distance += p;
        }

        minDistance = Math.min(minDistance, distance);
    }

    return minDistance;
}

Unit testing

I recommend adding unit tests to verify your solution, for example:

@Test
public void testSampleExercise1() {
    assertEquals(3, LinearCode.getMinimumDistance(new int[][]{
            {1, 0, 0, 0},
            {0, 1, 0, 0},
            {0, 0, 1, 0},
            {0, 0, 0, 1},
            {0, 1, 1, 1},
            {1, 0, 1, 1},
            {1, 1, 0, 1},
    }));
}

@Test
public void testSampleExercise2() {
    assertEquals(0, LinearCode.getMinimumDistance(new int[][]{
            {1, 1},
            {0, 0},
            {1, 1},
    }));
}
share|improve this answer
1  
Thanks for your suggestions, your changes look reasonable. However, there is no bug actually: the first line of input in the example 3 2 are the n k parameters. –  Cristian Greco 13 hours ago
    
Ah, you're right, I overlooked that. Updated my answer. –  janos 13 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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