Ainodyne Coding: February 2015

Saturday, February 28, 2015

Problem 011 : Largest Product in a Grid

Largest product in a grid

Problem 11

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08

49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00

49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65

70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91

31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80

47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50

98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70

26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21

55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72

36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95

17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92

39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57

56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58

80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40

52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66

36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69

42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36

69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16

73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54

70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.
What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

(https://projecteuler.net/problem=11)

Problem 11 can be done manually without complicated algorithms.

There will be four components in our calculation: horizontal —, vertical |, descending diagonal \ and ascending diagonal /.

First step is to store the numbers into 20 x 20 2-D arrays.

This can be done manually, or using file reader.

public static int[][] read()
{
 int[][] text = new int[20][20];
 File file = new File(text011);
 try (BufferedReader br = new BufferedReader(new FileReader(file)))
 {
  String line;
  for (int i=0; (line = br.readLine()) != null; i++)
  {
   String[] temp = line.split(" ");
   for (int j=0; j < 20; j++)
    text[i][j] = Integer.parseInt(temp[j]);
  }
 }
 catch (IOException e)
 {
  System.err.println(e);
 }
 return text;
}

After this, we will set the limit to 20 - 3, or 17.

The reason is that once we get to the column (or row) 17, we reached the maximum starting point since 17, 18, 19, 20 will form the last four-adjacent groups.

The remaining steps are to calculate the greatest sum using nested for-loops.

Horizontal will be increasing column by 0, 1, 2, 3:

h = grid[i][j] * grid[i][j+1] * grid[i][j+2] * grid[i][j+3];

Vertical will be increasing row by 0, 1, 2, 3:

v = grid[j][i] * grid[j+1][i] * grid[j+2][i] * grid[j+3][i];

Descending Diagonal will be increasing both row and column by 0, 1, 2, 3:

d1 = grid[i][j] * grid[i+1][j+1] * grid[i+2][j+2] * grid[i+3][j+3];

Ascending Diagonal will be decreasing column and increasing row at the same time by 1:

d2 = grid[i][j+3] * grid[i+1][j+2] * grid[i+2][j+1] * grid[i+3][j];

thus maintaining the sum of row and column as i + j + 3.

It was relatively easy problem, and there isn't any faster or fancier algorithm to solve it.

Answer is 70600674
Execution time is 3.771644 ms, or 0.003 seconds
Source Code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem011.java

Friday, February 20, 2015

Problem 010 : Summation of Primes

Summation of primes

Problem 10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.

https://projecteuler.net/problem=10

Problem 10 is about primality of integers.

There are two main ways to do this, but let's start with the one we already know.

First method is to use boolean isPrime(int n) to check each integer until we reach two million.

public static boolean isPrime(int n)
{
     if (n <= 3) return n > 1;
     else if (n % 2 == 0 || n % 3 == 0) return false;
     else
     {
      for (int i = 5, end = (int)Math.sqrt(n); i <= end; i += 6)
      {
       if (n % i == 0 || n % (i + 2) == 0) return false;
      }
     }
     return true;
}

Loop through each integer using for-loop and check their primality.

We get the answer in 603 ms. Pretty decent, but we are not really satisfied.

So here comes our new approach to this problem.

But before that, let's briefly talk about different ways to store integers in an array.

We will consider storing 1, 3, 5, 8 into an array.

First way is to directly store integers in an array.

index	0	1	2	3
value	1	3	5	8

Second way is to have a boolean array and stored number has true value in its index.

index	0	1	2	3	4	5	6	7	8
value	false	true	false	true	false	true	false	false	true

This array contains exactly same information as the first array.

Only index 1, 3, 5, 8 have true value, which means the "if array has that value" will be true.

The only difference is that the array size is usually larger than the number of integers we want to store.

However, it is phenomenally faster for finding certain integers in the array and adding/ removing certain integer.

Adding would be just changing that index to true, removing would be false.

Using this basic idea, we will now use the Sieve of Eratosthenes.

Sieve of Eratosthenes uses exactly same concept as the second example.

We will make a boolean array called isPrime, and isPrime[n] will return whether n is a prime or not.

The basic concept of the sieve is that "any multiple of prime number is not a prime."

Let's start with a table of numbers from 1 to 20.

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20

Now, by definition, 1 is not a prime. (as well as any integer less than or equal to 0)

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20

We are on 2 right now. We started with 0, and until we came to 2, no number could cross out 2.

Therefore 2 is a prime number.

Because 2 is a prime number, any multiple of it (which will be rest of even integers) won't be prime.

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20

Now, we are on 3. Until we came to 3, no number could cross out 3.

Therefore 3 is a prime number.

Because 3 is a prime number, any multiple of it (6, 9, 12, 15, ...) won't be prime.

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20

Now we are on 4. Uh-oh, it's already crossed out. Until we came to 4, some number crossed out 4.

So 4 is not a prime, and we just go on to the next number.

We are on 5. Until we came to 5, no number could cross out 5.

Therefore 5 is a prime number.

Because 5 is a prime number, any multiple of it (5, 10, 15, ...) won't be prime.

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20

And we notice that no additional composite numbers were crossed out this time.

So we know our limit for checking the prime is up to the square root of the original limit.

For example, square root of 20 is 4.47, and 5 is above that limit, so we didn't need to check 5.

In other sieves, we will repeat the above process until we get to the square root of original limit.

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20

Notice that the uncrossed numbers are all prime numbers.

So if we convert this table into an array of boolean values,

the crossed-out index will have false value, while survived index will have true value.

And this information will be stored in isPrime array and we can just call array every time we need.

For example, if we want to check whether 9 is a prime number, then:

public static void main(String[] args)
{
    if (isPrime[9])
    {
        System.out.println("9 is a prime number.");
    }
    else System.out.println("9 is not a prime number."); // this will print
}

And here is the implementation for the sieve.

public static boolean[] primeList(int n)
{
        //sieve of Eratosthenes
        boolean[] prime = new boolean[n+1];
        Arrays.fill(prime, 2, prime.length, true);
        for (int i=4; i < prime.length; i+=2) prime[i] = false;
        for (int i=3, end = (int)Math.sqrt(n); i <= end; i+=2)
        {
         if (prime[i])
          for (int j=i*i; j <= n; j+=2*i)
           prime[j] = false;
        }
        return prime;
}

Answer is 142913828922
Execution time is 15 ms, or 0.015 seconds
Source code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem010.java

Wednesday, February 11, 2015

Problem 009 : Special Pythagorean Triplet

Special Pythagorean triplet

Problem 9

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

https://projecteuler.net/problem=9

Problem 9 is about Pythagorean triplet.

The basic formula is :

A² + B² = C²

Using this formula will easily solve the problem.

One quick trick is to set the limit to int A and B so that we can reduce the time.

Assuming that B is always greater than or equal to A, B will always start with A.

Also, A will be less than one third of the perimeter since A is the smallest side of a triangle.

B will be less than one half of the perimeter since B should be smaller than the hypotenuse, C.

for (int a=1, end = 1000/3; a < end; a++)
{
 for (int b=a, end2 = 1000/2; b < end2; b++)
 {
  int c = 1000-a-b;
  if (c>0 && a*a + b*b == c*c)
  {
   System.out.println(a*b*c);
   return;
  }
 }
}

Answer is 31875000

Execution time is 1.7 ms, or 0.0017 seconds

Source code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem009.java

Monday, February 2, 2015

Problem 008 : Largest Product in a Series

Largest product in a series

Problem 8

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934

96983520312774506326239578318016984801869478851843

85861560789112949495459501737958331952853208805511

12540698747158523863050715693290963295227443043557

66896648950445244523161731856403098711121722383113

62229893423380308135336276614282806444486645238749

30358907296290491560440772390713810515859307960866

70172427121883998797908792274921901699720888093776

65727333001053367881220235421809751254540594752243

52584907711670556013604839586446706324415722155397

53697817977846174064955149290862569321978468622482

83972241375657056057490261407972968652414535100474

82166370484403199890008895243450658541227588666881

16427171479924442928230863465674813919123162824586

17866458359124566529476545682848912883142607690042

24219022671055626321111109370544217506941658960408

07198403850962455444362981230987879927244284909188

84580156166097919133875499200524063689912560717606

05886116467109405077541002256983155200055935729725

71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

https://projecteuler.net/problem=8

Problem 8 is a simple problem if we know how to deal with string and char.

First, we store the series into a string.

private static final String NUM = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";

Then we will store each item into char array so that we attain an easy access to each value.

int[] digit = new int[NUM.length()];
for (int i=0; i < NUM.length(); i++)
 digit[i] = Character.digit(NUM.charAt(i), 10);

Now, we just need to use nested for-loop to find the greatest 13-adjacent product in the series.

long max = 0;
for (int i=0; i <= NUM.length()-LEN; i++)
{
 long temp = 1;
 for (int j=i; j < i+LEN; j++)
 {
  if (digit[j] == 0) break;
  temp *= digit[j];
 }
 if (temp > max) max = temp;
}
System.out.println(max);

Answer is 23514624000
Execution time is 1 ms, or 0.001 seconds
Source code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem008.java

Ainodyne Coding