Archive

Posts Tagged ‘algorithm’

Project euler 31: Coin sums


https://projecteuler.net/problem=31

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?

Solution:
This a very nice Dynamic programming question:

def noOfCoins(coins, n):
    noOfWays= [x * 0 for x in range(n + 1)]
    noOfWays[0] = 1
    for i in range(len(coins)):
        for j in range(coins[i], n + 1):
            noOfWays[j] = noOfWays[j] + noOfWays[j - coins[i]]
    return noOfWays[n]
            
if __name__ == '__main__':
    coins = [1,2,5,10,20,50,100,200]
    n = 200
    print(noOfCoins(coins, n))

Answer: 73682
Time Complexity: O(number of available coins * n) ~ o(N)
Space Complexity: O(N)

Advertisements
Categories: Programming Tags: ,

Project euler 30: Digit fifth powers


https://projecteuler.net/problem=30

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 1^4 + 6^4 + 3^4 + 4^4
8208 = 8^4 + 2^4 + 0^4 + 8^4
9474 = 9^4 + 4^4 + 7^4 + 4^4

As 1 = 1^4 is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

Solution:

It is straight forward answer.

def powrs(n, pw):
    prod = 1
    for i in range(0, pw):
        prod *= n
    return int(prod)

def sumdigitpows(n, pw):
    sum = 0
    orig = n
    while (n > 0):
        sum +=powrs(int(n % 10), pw)
        n /= 10
        if sum > orig:
            return 0
    return int(sum)

def fifthpowers():
    pw = 5
    sum = 0
    for i in range(1000, 10000000):
        if i == sumdigitpows(i, pw):
            sum += i
            print (i)
    print ("Answr: %s" % str(sum))

if __name__ == '__main__':
    fifthpowers()

Answr: 443839

Categories: Programming Tags: ,

Project euler problem 22: Names scores


Problem 22

Using names.txt (right click and ‘Save Link/Target As…’), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714.

What is the total of all the name scores in the file?

Solution:

Solution is for this problem is straight forward. I have used python for the ease of string operations.

apyr=[]
def pyr():
    with open("names.txt", "r")as out:
        for i in out:
            i=i.replace('\"','')
            apyr = i.split(',')
    apyr = sorted(apyr)
    gsum = 0
    for i in range(1, len(apyr) + 1):
        lsum = 0
        for j in range(0, len(apyr[i - 1])):
            lsum += (ord(apyr[i - 1][j]) - 64)
        gsum += lsum * i
    print gsum


pyr()

Answer: 871198282

Time taken for the solution is:

real 0m0.160s
user 0m0.030s
sys 0m0.140s

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[0][0]

pyr()

Answer for problem 16: 1074

Answer for problem 67: 7273

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

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[0] = '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');
    printf("Answer: %d\n", carry);
}

2 power 1000 is:

10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

Answer: 1366

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: , ,

Program to convert one endian ness to another


Here is the program to convert from given endian ness to other endian ness. If the given endian ness is little it converts to big endian and vice versa.
This code has been written keeping in mind sizeof(int) = 4 Bytes.

#include <stdio.h>
 
int main(void)
{
    int i = 0x12345678;
    printf("Before 0x%x\n", i);
    int p = 0;
    p |= ((0xff & i) << 24);
    p |= ((((0xff << 8) & i) >> 8) << 16);
    p |= ((((0xff << 16) & i) >> 16) << 8);
    p |= ((((0xff << 24) & i) >> 24));
    printf("After 0x%x\n", p);
    return 0;
}

Thanks for the comments. As per the suggestions adding some more explanation.

Here the following code tells you whether you have LSB representation or MSB representation

#include <stdio.h>
 
int main(void)
{
    int i = 0x12345678;
    char *r;
    r = &i;
    printf("Internal storage representation: %x%x%x%x\n", r[0], r[1], r[2],  r[3]);
    return 0;
}

After you run the above code if you get the prints as 78563412 then you have LSB based representation. Else this code prints 12345678 then you have MSB based representation.

So, if you quickly see the above two representations for i = 0x12345678; For any byte sequence p1 p2 p3 p4 the other endian representation is p4 p3 p2 p1.
Hence for conversion for a 4 byte integers we need to take the last byte and place it in the appropriate 31 to 24 bit position.

ie., p |= ((0xff & i) << 24);

Now we need to take the bits from 9 to 16 (ie., second byte) and place them in 23 to 16 positions.

ie., p |= ((((0xff <> 8) << 16);

same applies for the next two bytes as well.

Thanks for reading the article.

Codechef: Find the largest AND operation result between any two elements of a given array


At first the problem looks very simple and can be solved easily in O(N^2).

#include <iostream>
using namespace std;
 
int main() {
 
	int n;
	cin>>n;
	long data[n] ;
	for(int i = 0; i < n; i++) {
		cin>>data[i];
		
	}
	long max = 0;
	for(int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++)
		if (max < (data[i] & data[j]) )
			max = (data[i] & data[j]);
	}
	cout<<max;
	return 0;
} 

But when it comes to huge data sets the solution for finding the maximum between every pair of elements is too much time consuming. A different approach is needed to find it quickly. Here we are reducing the complexity of the algorithm from O(N^2) to merely O(sizeof(long) * 8 * N). This is a good improvement for this algorithm.


#include <iostream>
using namespace std;
 
int main() {
	int n;
	cin>>n;
	long data[n] ;
	for(int i = 0; i < n; i++) {
		cin>>data[i];
	}
	long res = 0;
	int count = 0;
	for(int i = sizeof(long) * 8; i >= 0; i--) {
		count = 0;
		for (int j = 0; j < n; j++) {
			if ((data[j] & (res | (1 << i))) == (res | (1 << i))) {
				count++;
			}
			if (count >= 2) {
				res |= (1 << i);	
				break;
			}
		}
	}
	cout<<res;
	return 0;
}

The above same code can be found here. http://ideone.com/W1LlV0