[Tutor] Testing if a number occurs more than once

[Michael Williams]

Well, the general consensus is that there isn't much general consensus 
and that the best solution depends on the form of the problem.

The problem is a trivial little thing from the British magazine ``New 
Scientist''. Each week, in a section called ``Enigma'' they set a 
number puzzle. I could see no way of solving this week's analytically, 
so threw Python at it. Here's the problem:

New Scientist wrote:
> Brits who venture to Euroland quickly discover that you get 
> one-and-a-bit Euros for every pound. I can reveal that the "bit" 
> varies between 4/3 and 11/8 because:
>    EURO * 4/3 == POUND
>    EURO * 11/8 == POUND
> These two sums are entirely distinct: any letter may or may not have 
> the same value in one sum as in the other. But within each sum digits 
> have been consistently represented by capital letters, different 
> letters being used for different digits. No number starts with a zero. 
> What were the five-digit numbers represented by pound in (a) and (b)?

So it's the same problem with two different coefficients. Let's 
consider (b). Firstly, we know the minimum possible value of POUND is 
10000 since neither number starts with a zero. Therefore, the minimum 
EURO is 10000/(11/8) == 7272. This saves some time during the program.

So here is the first solution I came up with:
========================================

coeff = 1 + 3.0/8

min_euro = 10000/coeff
solved = 0

for euro in range(min_euro, 10000, 1):
   # go through the possible EUROs.
   e = int(str(euro)[0])
   u = int(str(euro)[1])
   r = int(str(euro)[2])
   o = int(str(euro)[3])
   # go through the possible POUNDs (O and U already decided)
   for p in range(1,10,1):
     for n in range(0,10,1):
       for d in range(0,10,1):
         pound_s = str(p) + str(o) + str(u) + str(n) + str(d)
         pound = int(pound_s)
         numbers = [int(str(euro)[0]), int(str(euro)[1]),
                int(str(euro)[2]), int(str(euro)[3]),
                int(str(pound)[0]), int(str(pound)[3]),
                int(str(pound)[4])]
         if not morethanone(numbers):
           if test(euro, pound, coeff):
             solved = 1
             break
       if solved == 1: break
     if solved == 1: break
   if solved == 1: break

================================

test() is just a function that tests whether euro * coeff == pound. 
morethanone() is the function that determines whether or not an number 
occurs more than once in the list numbers. So morethanone() acts on a 
list only seven elements long, which is going to affect the way we 
write morethanone().

Having thought about it some more I realised that where I call 
morethanone() will drastically affect how much effort I put into 
optimising it. In the above form morethanone is called for *every* 
combination of the seven digits in the range. That's a lot of times.

By calling it only after establishing that euro + coeff == pound, we 
reduce the number of calls it gets to half-a-dozen times. This is 
probably the best way to do it: call test() many times, call 
morethanone() few, since test() is simple, morethanone() is not.

So, with a bit of thought on my part, I realised that the optimisation 
of morethanone is a red-herring in this case and profiling the various 
morethanone()s (summarised below) in this case would not throw up any 
significiant differences.

Here are the morethanone()s suggested:

Yann Le Du:
-----------
for n in l:
   if l.count(n) > 1:
     return 1
   return 0

Jeff Shannon (and a similar one from Danny Yoo):
------------------------------------------------
mycopy = l[:]		# as Jeff suggested this is unnecessary in this case
mycopy.sort()
for n in range(1, len(mycopy))
   if mycopy[n] == mycopy[n-1]:
     return 1
return 0

Jeff Shannon (and a similar one--I think!--from Alan Gauld)
-----------------------------------------------------------
res = {}
for item in l:
   if res.get(item, 0):
     res[item] = 1
   else:
     return 1
return 0

p.s. If anyone does the problem themselves, I make the answers:
in (a) POUND is 12056
in (b) it is 10945

-- 
Michael