Python 2.
It's pretty efficient because it constructs the numbers (the inner-most loop is executed 4570 times total) and pretty short because I golfed a little (201 characters), but I'm not really sure I want to explain this :)
p=lambda t,a,d:((x,y)for x in range(10)for y in[(t-x-a)%10]if(x not in d)&(y not in d)and x-y)
w=lambda s:[s]if len(s)==10and s[:5]<s[5:]else(m for n in p(2-len(s)/2%2,sum(s[-2:])/10,s)for m in w(s+n))
The returned values are pretty peculiar, though: call w
with an empty tuple, and you get an iterator of 10-tuples. These 10 tuples are the digits of the two numbers, alas backwards and alternating, i.e. the tuple
(2, 0, 8, 3, 7, 4, 9, 1, 6, 5)
represents the numbers 51430 and 69782.
Test:
result = list(w(()))
assert len(set(result)) == 192 # found all values
assert len(result) == 192 # and no dupes
for digits in result:
assert all(0 <= d <= 9 for d in digits) # real digits -- zero through nine
assert len(set(digits)) == 10 # all digits distinct
n1 = int("".join(map(str, digits[9::-2])))
n2 = int("".join(map(str, digits[8::-2])))
assert n1 + n2 == 121212 # sum is correct
Here is the ungolfed version:
ppcalls = 0 # number of calls to possiblePairs
ppyields = 0 # number of pairs yielded by possiblePairs
ppconstructed = 0 # number of construced pairs; this is the number
# of times we enter the innermost loop
def possiblePairs(theirSumMod10, addition, disallowed):
global ppcalls, ppyields, ppconstructed
ppcalls += 1
for a in range(10):
b = (theirSumMod10 - a - addition) % 10
ppconstructed += 1
if a not in disallowed and b not in disallowed and a != b:
ppyields += 1
yield (a, b)
def go(sofar):
if len(sofar) == 10:
if sofar[:5] < sofar[5:]: # dedupe
yield sofar
digitsum = 2 - (len(sofar) / 2) % 2 # 1 or 2, alternating
for newpair in possiblePairs(digitsum, sum(sofar[-2:]) / 10, sofar):
for more in go(sofar + newpair):
yield more
list(go(())) # iterate
print ppcalls # 457
print ppyields # 840
print ppconstructed # 4570
1Did I miss the part where you said "Assume base 10"? ;) – kojiro – 2011-03-17T17:30:32.253
1@kojiro: How many fingers do YOU have? :-) – mellamokb – 2011-03-17T18:15:44.537
1@kojiro: Nope. If you can find other bases where it works, by all means... I think that would be awesome! – ircmaxell – 2011-03-17T18:34:22.377
@kojiro kind of: "*each decimal digit must appear ...*" although it seems you could find two 5-digit hex numbers as long as they don't contain A-F – Cephalopod – 2014-01-17T15:18:00.307
@mellamokb 10 fingers, but I have 20 digits. – kojiro – 2014-01-17T15:55:26.813