5
\$\begingroup\$

I implemented Project Euler problem 40 in Java. It works correctly, producing the correct answer.

During the course of implementing this program, I wrote a method that directly calculates a digit of Champernowne's constant, as opposed to the obvious brute-force approach. While brute-force is fast, this method takes under 1ms. In terms of speed, this is good code.

However, the method has a lot of repetition that I would like to get rid of, but I am not sure how. This may be a case of different code structures having similar attributes (those inner if blocks) that are not able to be combined, or any such optimization would introduce so many other complexities that it makes the code less clear.

Notes:

  1. This method is long, too long. If there is no way to simplify this, I will split it into multiple methods on the top-level if statements. I have it all in one method in the meantime while looking for a way to refactor the code to be more concise.

  2. I could refactor it to have multiple return statements, and I know that everyone has their own preference on this. I implemented it this way (final return variable and exceptions) to fail fast. It cannot compile if I forget a code path, and the exceptions kill the program in case of a logic error.

  3. This is written in Java 8, so pretty much any language feature is fair game (e.g. lambdas).


The code:

  private static int getDigit(int d) {
    /* This algorithm does the following:
     * 
     * 1. Based on the requested digit, find which group of digits it belongs
     * to. A digit group is determined by how many digits each number has: for
     * example, all two-digit numbers are part of the two-digit group.
     * 
     * 2. Find the number that contains the requested digit. This can be easily
     * calculated because the size of each group is well-defined, and since all
     * numbers in the group have the same number of digits, we can easily
     * calculate which number contains the requested digit.
     * 
     * 3. Get the offset of the digit inside the number. This may actually be
     * in the next number. If the offset is zero, it is at the end of the
     * calculated number. If the offset (actually a remainder) is positive,
     * count that many digits into the next number.
     */
    final int result;
    if (d < 1) {
      throw new IllegalArgumentException("Argument [" + d + "] out of range [1-7,688,889]");
    }

    // Single digits are the first 9 values and take up 9 total digits (1 - 9).
    else if (d < 10) {
      result = d;
    }

    // Double digits are the next 90 values and take up 180 total digits (10 - 189).
    else if (d < 190) {
      int offset = d - 9;
      int number = offset / 2 + 9;
      int digit = offset % 2;
      if (digit == 0) {
        result = number % 10;
      }
      else if (digit == 1) {
        result = (number + 1) / 10;
      }
      else {
        throw new AssertionError(digit);
      }
    }

    // Triple digits are the next 900 values and take up 2,700 total digits (190 - 2,889).
    else if (d < 2_890) {
      int offset = d - 189;
      int number = offset / 3 + 99;
      int digit = offset % 3;
      if (digit == 0) {
        result = number % 10;
      }
      else if (digit == 1) {
        result = (number + 1) / 100;
      }
      else if (digit == 2) {
        result = ((number + 1) / 10) % 10;
      }
      else {
        throw new AssertionError(digit);
      }
    }

    // Quad digits are the next 9,000 values and take up 36,000 total digits (2,890 - 38,889).
    else if (d < 38_890) {
      int offset = d - 2_889;
      int number = offset / 4 + 999;
      int digit = offset % 4;
      if (digit == 0) {
        result = number % 10;
      }
      else if (digit == 1) {
        result = (number + 1) / 1_000;
      }
      else if (digit == 2) {
        result = ((number + 1) / 100) % 10;
      }
      else if (digit == 3) {
        result = ((number + 1) / 10) % 10;
      }
      else {
        throw new AssertionError(digit);
      }
    }

    // Five digits are the next 90,000 values and take up 450,000 total digits (38,890 - 488,889).
    else if (d < 488_890) {
      int offset = d - 38_889;
      int number = offset / 5 + 9_999;
      int digit = offset % 5;
      if (digit == 0) {
        result = number % 10;
      }
      else if (digit == 1) {
        result = ((number + 1) / 10_000) % 10;
      }
      else if (digit == 2) {
        result = ((number + 1) / 1_000) % 10;
      }
      else if (digit == 3) {
        result = ((number + 1) / 100) % 10;
      }
      else if (digit == 4) {
        result = ((number + 1) / 10) % 10;
      }
      else {
        throw new AssertionError(digit);
      }
    }

    // Six digits are the next 900,000 values and take up 7,200,000 total digits (488,890 - 7,688,889).
    else if (d < 7_688_890) {
      int offset = d - 488_889;
      int number = offset / 6 + 99_999;
      int digit = offset % 6;
      if (digit == 0) {
        result = number % 10;
      }
      else if (digit == 1) {
        result = ((number + 1) / 100_000) % 10;
      }
      else if (digit == 2) {
        result = ((number + 1) / 10_000) % 10;
      }
      else if (digit == 3) {
        result = ((number + 1) / 1_000) % 10;
      }
      else if (digit == 4) {
        result = ((number + 1) / 100) % 10;
      }
      else if (digit == 5) {
        result = ((number + 1) / 10) % 10;
      }
      else {
        throw new AssertionError(digit);
      }
    }

    else {
      throw new IllegalArgumentException("Argument [" + d + "] out of range [1-7,688,889]");
    }

    return result;
  }
\$\endgroup\$
4
\$\begingroup\$

The boundaries of where the number of digits increases can be generated and looped over:

int n=0, nDigits;
for(nDigits=1; n < d; nDigits++){
    n+= nDigits*(pow10(nDigits)-pow10(nDigits-1));
}

pow10(n) is a helper function to create the nth power of 10.

The big if-else can also be simplified and generalized a bit:

  if (digit == 0) {
    number--;
    digit = nDigits;
  }

  result = ((number + 1) / pow10(nDigits-digit)) % 10;
\$\endgroup\$
  • \$\begingroup\$ The idea is on the right track, but I am having difficulty getting this to work. I will check back later once I have more time to work with this idea some more. \$\endgroup\$ – user31517 Oct 11 '15 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy