8
\$\begingroup\$

This problem is quite easy to do by brute force. In fact, it'll be reasonably fast to brute force as well. But where's the fun in that?

The Problem

Produce a list of all unique 5 digit number pairs that sum to 121212. However, each decimal digit must appear exactly once in either number. So a valid pair would be (98167, 23045). But an invalid pair would be (23456, 97756) because 7, 5, 6 are repeated more than once, and 1, 8, 0 are not used at all. There are exactly 192 unique pairs.

Rules

  1. Efficiency: You can brute force this. But that's trivial to do. So instead, the real challenge here is to find a way to efficiently produce the list of numbers.

  2. Source Code Requirements: It cannot store the number list (or any part of it). The number sequence must be generated on the fly.

Have Fun!

\$\endgroup\$
  • 1
    \$\begingroup\$ Did I miss the part where you said "Assume base 10"? ;) \$\endgroup\$ – kojiro Mar 17 '11 at 17:30
  • 1
    \$\begingroup\$ @kojiro: How many fingers do YOU have? :-) \$\endgroup\$ – mellamokb Mar 17 '11 at 18:15
  • 1
    \$\begingroup\$ @kojiro: Nope. If you can find other bases where it works, by all means... I think that would be awesome! \$\endgroup\$ – ircmaxell Mar 17 '11 at 18:34
  • \$\begingroup\$ @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 \$\endgroup\$ – Cephalopod Jan 17 '14 at 15:18
  • \$\begingroup\$ @mellamokb 10 fingers, but I have 20 digits. \$\endgroup\$ – kojiro Jan 17 '14 at 15:55
6
\$\begingroup\$

JavaScript

function findpairs(arrin1,arrin2){
    functioncount++
    var arr1=[]
    var arr2=[]
    var strike=[]
    var overflow=0
    var b
    var len=arrin1.length
    for(var a=0;a<len;a++){
        arr1[a]=arrin1[a]
        arr2[a]=arrin2[a]
        strike[arr1[a]]=true
        strike[arr2[a]]=true
        overflow=+((arr1[a]+arr2[a])>9)
    }
    var desired=12-(len%2)-overflow
    for(a=9;a>0;a--){
        b=(desired-a)%10
        if(a>b && !strike[a] && !strike[b]){
            if(len==4){
                if((a+b)>9){
                    document.write(""+a+arr1[3]+arr1[2]+arr1[1]+arr1[0]+" "+b+arr2[3]+arr2[2]+arr2[1]+arr2[0]+"<br>")
                    document.write(""+a+arr1[3]+arr1[2]+arr1[1]+arr2[0]+" "+b+arr2[3]+arr2[2]+arr2[1]+arr1[0]+"<br>")
                    document.write(""+a+arr1[3]+arr1[2]+arr2[1]+arr1[0]+" "+b+arr2[3]+arr2[2]+arr1[1]+arr2[0]+"<br>")
                    document.write(""+a+arr1[3]+arr1[2]+arr2[1]+arr2[0]+" "+b+arr2[3]+arr2[2]+arr1[1]+arr1[0]+"<br>")
                    document.write(""+a+arr1[3]+arr2[2]+arr1[1]+arr1[0]+" "+b+arr2[3]+arr1[2]+arr2[1]+arr2[0]+"<br>")
                    document.write(""+a+arr1[3]+arr2[2]+arr1[1]+arr2[0]+" "+b+arr2[3]+arr1[2]+arr2[1]+arr1[0]+"<br>")
                    document.write(""+a+arr1[3]+arr2[2]+arr2[1]+arr1[0]+" "+b+arr2[3]+arr1[2]+arr1[1]+arr2[0]+"<br>")
                    document.write(""+a+arr1[3]+arr2[2]+arr2[1]+arr2[0]+" "+b+arr2[3]+arr1[2]+arr1[1]+arr1[0]+"<br>")
                    document.write(""+a+arr2[3]+arr1[2]+arr1[1]+arr1[0]+" "+b+arr1[3]+arr2[2]+arr2[1]+arr2[0]+"<br>")
                    document.write(""+a+arr2[3]+arr1[2]+arr1[1]+arr2[0]+" "+b+arr1[3]+arr2[2]+arr2[1]+arr1[0]+"<br>")
                    document.write(""+a+arr2[3]+arr1[2]+arr2[1]+arr1[0]+" "+b+arr1[3]+arr2[2]+arr1[1]+arr2[0]+"<br>")
                    document.write(""+a+arr2[3]+arr1[2]+arr2[1]+arr2[0]+" "+b+arr1[3]+arr2[2]+arr1[1]+arr1[0]+"<br>")
                    document.write(""+a+arr2[3]+arr2[2]+arr1[1]+arr1[0]+" "+b+arr1[3]+arr1[2]+arr2[1]+arr2[0]+"<br>")
                    document.write(""+a+arr2[3]+arr2[2]+arr1[1]+arr2[0]+" "+b+arr1[3]+arr1[2]+arr2[1]+arr1[0]+"<br>")
                    document.write(""+a+arr2[3]+arr2[2]+arr2[1]+arr1[0]+" "+b+arr1[3]+arr1[2]+arr1[1]+arr2[0]+"<br>")
                    document.write(""+a+arr2[3]+arr2[2]+arr2[1]+arr2[0]+" "+b+arr1[3]+arr1[2]+arr1[1]+arr1[0]+"<br>")
                    resultcount+=16
                }
            }
            else{
                arr1[len]=a
                arr2[len]=b
                findpairs(arr1,arr2)
            }
        }
    }
}
resultcount=0
functioncount=0
start=+new Date()
findpairs([],[])
end=+new Date()
document.write("<br>"+resultcount+" results<br>"+(end-start)+" ms<br>"+functioncount+" function calls")

Hosted at: http://ebusiness.hopto.org/findpairs.htm

Mathematical realization: If you have one pair 15 others can trivially be generated by swapping digits between the two numbers, therefore I only search for numbers where the digits of the first are all greater than the digits of the second, and then simply output all the permutations.

I start from the least significant digits and generate the sequence as a tree traversal, for each step asserting that the intermediate result is correct and that no digits are spent twice. With these methods the function need only be called 50 times in total. On my machine Chrome yield runtime results of typically 2 ms.

\$\endgroup\$
8
\$\begingroup\$

C++

#include<iostream>
using namespace std;
#include<algorithm>

int main()
{
    long long N,F,S;
    char str[11]="1023456789";
    while (1) {
        sscanf(str,"%lld",&N);
        F=N/100000;S=N%100000;
        if (F>60000)
           break;
        if (F+S==121212)
           printf("%lld %lld\n",F,S);
        next_permutation(str,str+10);
    }
}

http://www.ideone.com/Lr84g

\$\endgroup\$
  • 2
    \$\begingroup\$ Very interesting. So you're iterating over all possible permutations where the upper part is less than 60001 (about 1,768,168 iterations, or a little less than 10!/2) and then checking if it's summable to 121212. Not bad at all for a first run. But I'm still curious if we can get more efficient... \$\endgroup\$ – ircmaxell Mar 17 '11 at 14:17
  • \$\begingroup\$ Hmm I thought you weren't allowed to store the number list... Ambiguous phrasing ? \$\endgroup\$ – bltxd Mar 17 '11 at 15:20
  • \$\begingroup\$ @bltxd: I meant store it before hand. You can store it as you generate it. But you can't store that (51430, 69872) is a valid pair. You can pre-store the digit list (0123456789) and the sum (121212). \$\endgroup\$ – ircmaxell Mar 17 '11 at 15:34
  • \$\begingroup\$ I agree that it is not the most efficient way to do it, but I hope it is different. \$\endgroup\$ – fR0DDY Mar 17 '11 at 15:38
4
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

C

#include <stdio.h>

int mask(int n)
{
    int ret = 0;

    for (; n > 0; n /= 10)
        ret |= 1 << n % 10;

    return ret;
}

int main(void)
{
    int a, b;

    for (a = 21213, b = 99999; a < b; a++, b--)
        if ((mask(a) | mask(b)) == 0x3FF)
            printf("%d %d\n", a, b);

    return 0;
}

This traverses all pairs of 5-digit numbers that sum to 121212 (meaning 39393 iterations, or ~1/46th of the iterations used by fR0DDY's answer). For each pair, it forms a bit mask of the digits in each number, then sees if they OR to 0b1111111111.

\$\endgroup\$
  • \$\begingroup\$ If you add the 10 iterations for mask every time, it leaves the time complexity only ~1/5 times better then mine. :) \$\endgroup\$ – fR0DDY Mar 17 '11 at 16:05
2
\$\begingroup\$

Javascript (481)

function m(d,i){o=d-i;if(0<=o&&o<=9&&o!=i)return o;o+=10;if(0<=o&&o<=9&&o!=i)return o;return}function p(n,a){x=0;r=[];d=n%10;for(i=0;i<10;i++){if((!a||!a.contains(i))&&(o=m(d,i))&&(!a||!a.contains(o))&&i+o<=n)r[x++]=[i,o]}return r}function f(n,a){var x=0;var r=[];var d=p(n,a);for(var i=0;i<d.length;i++){var s=Math.floor((n-d[i][0]-d[i][1])/10);if(s>0){var t=f(s,d[i].concat(a));for(var j=0;j<t.length;j++)r[x++]=[t[j][0]*10+d[i][0],t[j][1]*10+d[i][1]]}else{r[x++]=d[i]}}return r}

http://jsfiddle.net/XAYr3/4/

Basic idea: generate combinations of valid digits that can be used in the right-most column. For instance, (0,2), (3,9), (4,8), (5,7). For each combination, recursively find pairs that work for the next-from-right digit, without duplicating digits in the first pair. Recurse until a pair of 5-digit numbers has been generated. Combine all those results into a single array, and the list is 192 elements. This I believe should require about the fewest iterations, but all of the array allocation/deallocation makes it overall somewhat practically inefficient.

My counting tests show that function f is called 310 times, the inner loop i is executed 501 times total (across all calls to f), and the inner-inner loop j is executed 768 times total (across everything).

\$\endgroup\$
1
\$\begingroup\$

Python, 171 characters

def R(x,y,d,c):
 if not d and x<y:print x,y
 for p in d:
  q=(12-c%2-p-(x+y)/10**c)%10
  if p-q and q in d:R(x+p*10**c,y+q*10**c,d-set([p,q]),c+1)
R(0,0,set(range(10)),0)

The code maintains the invariant that x,y have c digits and that all the unused digits are in the set d.

The routine R is called a total of 841 times, which is pretty efficient.

\$\endgroup\$
0
\$\begingroup\$

C++

#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>

int main()
{
        int i;
        char str1[11]="0123456789",str2[11];
        for (i=99999;i>60000;i--)
        {
                sprintf(str2,"%d%d",i,121212-i);
                sort(str2,str2+10);
                if(!strcmp(str1,str2))
                        printf("%d %d\n",i,121212-i);
        }
}

http://www.ideone.com/Lr84g

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.