patternjavaMinor
Project Euler 40: directly calculate digits of Champernowne's constant
Viewed 0 times
constantdigitsprojectchampernownecalculatedirectlyeuler
Problem
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
Notes:
-
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
-
I could refactor it to have multiple
-
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.
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:
-
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.-
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.-
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.
Solution
The boundaries of where the number of digits increases can be generated and looped over:
The big if-else can also be simplified and generalized a bit:
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;Code Snippets
int n=0, nDigits;
for(nDigits=1; n < d; nDigits++){
n+= nDigits*(pow10(nDigits)-pow10(nDigits-1));
}if (digit == 0) {
number--;
digit = nDigits;
}
result = ((number + 1) / pow10(nDigits-digit)) % 10;Context
StackExchange Code Review Q#107104, answer score: 4
Revisions (0)
No revisions yet.