Archive

Archive for March, 2015

Project euler problem 20

This problem is very simple one liner in python.

n! means n × (n − 1) × … × 3 × 2 × 1

For example, 10! = 10 × 9 × … × 3 × 2 × 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!

import math
print sum([int(x) for x in  str(math.factorial(100))])

real 0m0.164s
user 0m0.031s
sys 0m0.108s

Categories: Programming

Project euler problem 18 and 67

Project euler problem 67 and 16 both are almost same. The only difference is that for the first problem the input is very small and for the 67th problem it is large. This problem is one another classic example of Dynamic programming.

Problem:

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

Solution:

Just by looking at the problem we can quickly discern that it has optimal sub structure and overlapping sub problems. This gives an idea that we can use dynamic programming methodology.

Here is my code in Python.

apyr=[]
def pyr():
with open("pyramid.txt", "r")as out:
for i in out:
apyr.append(i.split())

for i in range(len(apyr) - 2, -1, -1):
for j in range(len(apyr[i])):
apyr[i][j] = str(int(apyr[i][j]) + max(int(apyr[i + 1][j]), int(apyr[i + 1][j + 1])))
print apyr

pyr()

Answer for problem 16: 1074

Answer for problem 67: 7273

real 0m0.195s
user 0m0.046s
sys 0m0.140s

Categories: Programming

Project Euler: Problem 16: Find the sum of all the digits in 2 power 1000

This problem is simple and straight forward. I’ve used a character buffer to store the powers of 2 for each iteration starting from 1 to 1000.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char *strrev(char *str)
{
char *p1, *p2;

if (! str || ! *str)
return str;
for (p1 = str, p2 = str + strlen(str) - 1; p2 > p1; ++p1, --p2)
{
*p1 ^= *p2;
*p2 ^= *p1;
*p1 ^= *p2;
}
return str;
}
int main(void)
{
char *digits = (char *)malloc(sizeof(char) * 2000);
memset(digits, 0, 2000);
digits = '1';
unsigned int carry = 0;
int i, j;
for (i = 0; i < 1000; i++) {
carry = 0;
for (j = 0; j < strlen(digits); j++) {
int m = (digits[j] - '0') * 2 + carry;
carry = (m / 10) % 10;
digits[j] = (m % 10) + '0';
}
if (carry)
digits[j] = carry + '0';
}
strrev(digits);
printf("2 power 1000 is: %s\n", digits);
carry = 0;
for (int i = 0; i < strlen(digits); i++)
carry += (digits[i] - '0');
}

2 power 1000 is:

10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

real 0m0.085s
user 0m0.015s
sys 0m0.062s

One interesting thing to notice here is that the above same code can be written in python with in a single line using comprehensions as follows. 🙂

sum([int(n) for n in str(2**1000)])

>>> sum([int(n) for n in str(2**1000)])
1366

Categories: Programming Tags: , ,

Project euler: Problem 15

You can find the project euler exact problem here. This problem is particularly interesting because it takes a very long time without any optimization. I started with a simple recursion but obviously not efficient, to my surprise the program did not even finish more than 10 minutes :P. The optimized version using dynamic programming hardly takes any time. Here is the code.

#include<stdio.h>

unsigned long long depth(int len)
{
unsigned long long dep[len + 1][len + 1];
dep = 0;
for (int i = 1; i <= len; i++) {
dep[i] = 1;
dep[i] = 1;
}
for (int i = 1; i <= len; i++) {
for(int j = 1; j <= len ; j++) {
dep[i][j] = dep[i - 1][j] + dep[i][j -1];
}
}
return dep[len][len];
}

int main(void)
{
int len = 20;
printf("%llu\n", depth(len));
}