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

Histogram for the 26 prisoners problem (50k iterations)

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.

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

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

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)

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

Method 3:

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

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.