Dieses Problem ist mit roher Gewalt recht einfach zu lösen. Tatsächlich wird es auch ziemlich schnell sein, Gewalt anzuwenden. Aber wo ist der Spaß dabei?

Das Problem

Erstellen Sie eine Liste aller eindeutigen 5-stelligen Zahlenpaare, die sich summieren 121212. Jede Dezimalstelle muss jedoch in jeder Zahl genau einmal vorkommen. Ein gültiges Paar wäre also (98167, 23045). Ein ungültiges Paar wäre jedoch, (23456, 97756)weil 7, 5, 6es mehr als einmal wiederholt wird und 1, 8, 0überhaupt nicht verwendet wird. Es gibt genau 192 einzigartige Paare.

Regeln

1. Effizienz: Sie können dies brutal erzwingen. Aber das ist trivial. Stattdessen besteht die eigentliche Herausforderung darin, einen Weg zu finden, um die Liste der Zahlen effizient zu erstellen.

2. Quellcode-Anforderungen: Die Nummernliste (oder ein Teil davon) kann nicht gespeichert werden. Die Nummernfolge muss im laufenden Betrieb generiert werden.

Habe Spaß!

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")

Gehostet unter: http://ebusiness.hopto.org/findpairs.htm

Mathematische Realisierung: Wenn Sie ein Paar haben, können 15 andere trivial durch Vertauschen von Ziffern zwischen den beiden Zahlen erzeugt werden. Daher suche ich nur nach Zahlen, bei denen die Ziffern der ersten alle größer als die Ziffern der zweiten sind, und gebe dann einfach alle aus Permutationen.

Ich gehe von den niedrigstwertigen Ziffern aus und generiere die Sequenz als Baumdurchquerung für jeden Schritt, in dem bestätigt wird, dass das Zwischenergebnis korrekt ist und keine Ziffern zweimal ausgegeben werden. Mit diesen Methoden muss die Funktion insgesamt nur 50 Mal aufgerufen werden. Auf meinem Computer liefert Chrome Laufzeitergebnisse von normalerweise 2 ms.

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

Python 2.

Es ist ziemlich effizient, weil es die Zahlen konstruiert (die innerste Schleife wird insgesamt 4570 Mal ausgeführt) und ziemlich kurz, weil ich ein wenig Golf gespielt habe (201 Zeichen), aber ich bin mir nicht sicher, ob ich das erklären möchte :)

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))

Die zurückgegebenen Werte sind jedoch ziemlich eigenartig: Rufen Sie wmit einem leeren Tupel auf, und Sie erhalten einen Iterator mit 10 Tupeln. Diese 10 Tupel sind leider die Ziffern der beiden Zahlen rückwärts und abwechselnd , dh das Tupel

(2, 0, 8, 3, 7, 4, 9, 1, 6, 5)

repräsentiert die Nummern 51430 und 69782.

Prüfung:

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

Hier ist die 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

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;
}

Dies durchläuft alle Paare von 5-stelligen Zahlen, die sich zu 121212 summieren (dh 39393 Iterationen oder ~ 1/46 der Iterationen, die von der Antwort von fR0DDY verwendet werden ). Für jedes Paar bildet es eine Bitmaske der Ziffern in jeder Zahl und prüft dann, ob sie ODER bis 0b1111111111 sind.

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/

Grundidee: Generieren Sie Kombinationen gültiger Ziffern, die in der Spalte ganz rechts verwendet werden können. Zum Beispiel (0,2), (3,9), (4,8), (5,7). Suchen Sie für jede Kombination rekursiv Paare, die für die von rechts nächste Ziffer funktionieren, ohne die Ziffern im ersten Paar zu duplizieren. Wiederholen, bis ein Paar 5-stelliger Zahlen generiert wurde. Kombinieren Sie alle diese Ergebnisse zu einem einzigen Array, und die Liste enthält 192 Elemente. Dies sollte meiner Meinung nach ungefähr die wenigsten Iterationen erfordern, aber die gesamte Array-Zuweisung / Freigabe macht es insgesamt etwas ineffizient.

Meine Zähltests zeigen, dass die Funktion f310-mal aufgerufen wird, die innere Schleife iinsgesamt 501-mal ausgeführt wird (über alle Aufrufe von f) und die innere-innere Schleife j768-mal ausgeführt wird (über alles).

Python, 171 Zeichen

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)

Der Code behält die Invariante bei x, ydie cZiffern hat und dass alle nicht verwendeten Ziffern im Satz enthalten sindd .

Die Routine Rwird insgesamt 841 Mal aufgerufen, was ziemlich effizient ist.

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