# Posts tagged ‘project euler’

I was sent a interesting logic problem by samsamsam which is as follows (or very similar):

Q:How can the prisoners tell, with certainty, that all 26 of them have visited the central living room with the light bulb.

Riddle:

26 prisoners are in solitary cells, unable to see, speak or communicate in any way from those solitary cells with each other. There’s a central living room with one light bulb; the bulb is initially off. No prisoner can see the light bulb from his own cell. Everyday, the warden picks a prisoner at random, and that prisoner goes to the central living room. While there, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting the claim that all 26 prisoners have been to the living room. If this assertion is false (that is, some prisoners still haven’t been to the living room), all 26 prisoners will be shot for their stupidity. However, if it is indeed true, all prisoners are set free. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.

**Solution**

I won’t explain the solution in words as that might ruin it if you were planning on figuring it out, instead I have posted some python code that calculates the probability of number of days it will take.

# -*- coding: utf-8 -*- from random import randint bin=[] binstep=50 # Loop for i in xrange(0,50000): nopris=26 light=0 count=0 days=0 # Create a set of prisoners with value 0 or 1 # for having visited the room when light is off p=[] for i in range(0,nopris): p.append(0) # Until all prisoners have switched light on and have # been counted while count<nopris-1: x=randint(0,nopris-1) # First person to be picked is the counter if days==0: counter=x p[x]=1 # Counter adds one if light is on and resets it elif x==counter and light==1: light=0 count+=1 # If light is off and prisoner hasn't turned light # on before he does so elif p[x]==0 and light==0: p[x]=1 light=1 else: pass days+=1 # Expand our bin if it isn't big enough while days>len(bin)*binstep: bin.append(0) bin[days/binstep]+=1 # Just chucking data into a histogram type layout # to speed up processing afterwards (I'm crap at # openoffice stuff) for i in range(0,len(bin)): print i*binstep+binstep/2,",",bin[i]

For 50k iterations I got the following output:

$ python prisoners.py

25 , 0

75 , 0

125 , 0

175 , 0

225 , 0

275 , 0

325 , 2

375 , 31

425 , 162

475 , 636

525 , 1659

575 , 3492

625 , 5448

675 , 7134

725 , 7755

775 , 7103

825 , 5758

875 , 4341

925 , 2884

975 , 1701

1025 , 909

1075 , 511

1125 , 255

1175 , 124

1225 , 63

1275 , 25

1325 , 4

1375 , 2

1425 , 1

Which shown as a histogram looks like:

Let me know how you’d improve this method or any other cool logic problems I can have a go at

Finding the highest common factor is useful in mathematics and cryptography.

It would be computationally expensive to calculate all the common factors of two numbers and then compare to find the highest factor in common. Instead (as usual) there is a mathematical theory that can be used to speed up this process, in this case it’s the Euclidean algorithm.

The Euclidean algorithm subtracts the smaller number from the larger number, then using this new number and the smaller number repeats this process until the numbers are equal and hence the subtraction goes to zero. This is the highest common factor.

**Example:**

Find the highest common factor of 252 and 105

252-105=147

147-105=42

105-42=63

63-42=21

42-21=21

21-21=0

Below is the python code to preform this

def hcf(no1,no2): while no1!=no2: if no1>no2: no1-=no2 elif no2>no1: no2-=no1 return no1

This method is quite quick even and scales well for larger numbers. If you know of a faster method or can see any improvements to make then please let me know.

## Python: Factors of a number

Project Euler often requires the factors of a number to be found, here is the function I have written for that purpose.

def factors(n): fact=[1,n] check=2 rootn=sqrt(n) while check<rootn: if n%check==0: fact.append(check) fact.append(n/check) check+=1 if rootn==check: fact.append(check) fact.sort() return fact

As always any help in speeding up my function would be appreciated. I think it could be improved using a sieve method or by checking if its divisible by 2 first then using check+=2 starting at 3 to improve the speed of the loop by a factor of 2.

Below is a the commented version to help explain what’s going on if it’s not clear.

def factors(n): # 1 and n are automatically factors of n fact=[1,n] # starting at 2 as we have already dealt with 1 check=2 # calculate the square root of n and use this as the # limit when checking if a number is divisible as # factors above sqrt(n) will already be calculated as # the inverse of a lower factor IE. finding factors of # 100 only need go up to 10 (sqrt(100)=10) as factors # such as 25 can be found when 5 is found to be a # factor 100/5=25 rootn=sqrt(n) while check<rootn: if n%check==0: fact.append(check) fact.append(n/check) check+=1 # this line checks the sqrt of the number to see if # it is a factor putting it here prevents it appearing # twice in the above while loop and putting it outside # the loop should save some time. if rootn==check: fact.append(check) # return an array of factors sorted into numerial order. fact.sort() return fact

## Python: palindrome checking function

I created a reasonable palindrome checking function in python.

**Method 1**

def ispalindrome(num): n=str(num) while len(n)>1: print n if n[0]!=n[-1]: return 0 n=n[1:-1] return 1

I thought that it would be faster avoiding a string conversion, and to somehow use the modulus (modulo) function. However when I came to write it, I found it quite difficult to code, and I’m sure there must be a better way.

**Method 2**

def ispalindrome2(num): l=1 while num/10**l>=1.0: l+=1 r=0 d=[] for i in range(1,l+1): p=num%10**i-r r+=p p=p/10**(i-1) d.append(p) for i in range(0,l/2): if d[i]!=d[-i-1]: return 0 return 1

Doing the speed tests show that Method 1 is over 5.2 times faster than Method 2.

Method 1 0.355437994003 Seconds elapsed Method 2 1.85815691948 Seconds elapsed

**Update: Mike of mikemeat sent me his method using slices (Method 3) and I adapted it slight (Method 4), then shortly after I realised it could be even more efficient by not needing to differentiate between even and odd strings (Method 5).**

**Method 3**

def ispalindrome3(x): z = str(x) if len(z)%2 == 0 and z[:len(z)/2]==z[-len(z)/2:][::-1]: return 1 if len(z)%2 != 0 and z[:(len(z)- 1)/2]==z[(-len(z) + 1)/2:][::-1]: return 1 else: return 0

**Method 4**

def ispalindrome4(x): z = str(x) if z[:len( z)/2]==z[len( z)/2+len( z)%2:][::-1]: return 1 return 0

**Method 5**

def ispalindrome5(x): z = str(x) l=len(z)/2 if z[:l]==z[-l:][::-1]: return 1 return 0

Method 1 0.357168912888 Seconds elapsed Method 2 1.83943104744 Seconds elapsed Method 3 0.179126977921 Seconds elapsed Method 4 0.179482936859 Seconds elapsed Method 5 0.149376153946 Seconds elapsed

## Python: sum of digits in a string

I have a function I wrote for a project euler that calculates the sum of the digits in a number. This is my first attempt which simply converts each letter to an integer and sums them.

**Method 1:**

def digitsum(x): total=0 for letter in str(x): total+=int(letter) return total

I thought that this could be improved using ord, which converts a letter into its decimal ascii number. Numbers ‘0’, ‘1’, ‘2’ … ‘9’ correspond to the ascii values of 48 – 57 and then took the moduli of this with 48 to give the integer value. I later realised that this was completely nonsensical and should have just subtracted 48, but I decided to include it for the purposes of the speed test.

**Method 2:**

def digitsum2(x): total=0 for letter in str(x): total+=ord(letter)%48 return total

**Method 3:**

def digitsum3(x): total=0 for letter in str(x): total+=ord(letter)-48 return total

**Speed Test:**

The test uses a long number and one million repetitions for each method.

from time import time # .. functions go here # Nice long number to sum x=981234153134415646571899783156122451653 tic = time() for i in range(0,1000000): digitsum(x) print time() - tic, 'Seconds elapsed' tic = time() for i in range(0,1000000): digitsum2(x) print time() - tic, 'Seconds elapsed' tic = time() for i in range(0,1000000): digitsum3(x) print time() - tic, 'Seconds elapsed'

**Results:**

#Method 1 29.3496568203 Seconds elapsed #Method 2 12.185685873 Seconds elapsed #Method 3 9.59367895126 Seconds elapsed

So we can see that the first method is much slower, avoiding the integer conversion by using ord speeds it up the function by ~60% and that using subtraction rather than modulus (a division based operation) saves a further ~20% on top of this.

I’ve been doing a lot of problem solving on Project Euler recently. If your not aware of Project Euler (PE) it is a website with lots of maths / programming based puzzles to solve. Many of the problems involve using or checking prime numbers, in many cases a sieve method would be applicable (see: Sieve of Eratosthenes for a clear explanation / animation).

However sometimes this is not necessary if you only require one prime number, or if memory limitations mean a sieve would be inconceivable. The following is the code I wrote to check if a number is prime or not in python. It tests upwards checking if the number is perfectly divisble, and as it does this it lowers the maximum number need to reach to stop as we know that if a number is not divisible by 2 then it will not be uniquely divisible (a repatition of a divislbe may exist) by anything greater than N/2

def isprime(number): if number<=1: return 0 check=2 maxneeded=number while check<maxneeded+1: maxneeded=number/check if number%check==0: return 0 check+=1 return 1

I hope that this made sense, and is useful to someone. If anyone has any more efficient methods I would be happy to hear from you.

Check out my profile to see which problems I’ve completed. If you’ve completed any I haven’t please get in contact and give me some tips.

**Update:**

Mike sent a suggestion that I could speed up the program by ignoring all factors of 2, it could also propbably be sped up by looking at 3,4,5 .. etc until certain point.

def isprime(number): if number<=1 or number%2==0: return 0 check=3 maxneeded=number while check<maxneeded+1: maxneeded=number/check if number%check==0: return 0 check+=2 return 1

So lets test the speed difference by doing 1,000 checks of the number 982,451,653 (known to be prime from this usefulsite)

Original Code: 9.99917411804 Seconds elapsed

Improved Code: 5.2977039814 Seconds elapsed

That’s approximately a factor of two speed increase, but this makes me think that a combination of the sieve method with this one may lead to an even further increase.