Wie stark sind nichtäre Zahlen?

10

Sie erhalten eine nicht negative Ganzzahl (Basis 9), die wie üblich aus den Ziffern 0 bis 8 besteht. Die Anzahl der Ziffern in dieser Zahl (ohne führende Nullen) ist jedoch ein Präfektenquadrat.

Aus diesem Grund kann die Nummer in einem quadratischen Raster angeordnet werden (wobei die Lesereihenfolge weiterhin erhalten bleibt).

Beispiel mit 1480 (1125 Base 10):

14
80

Lassen Sie nun jede Ziffer in einem solchen nichtären Gitter eine Bewegung in einen anderen Gitterraum anzeigen (mit periodischen Randbedingungen ):

432
501
678

Das sagt das

0 = stay still
1 = move right
2 = move right and up
3 = move up
...
8 = move right and down

Wenn Sie also im 1480-Raster bei der 4 beginnen, bewegen Sie sich nach oben (denken Sie an pbc) und nach links zur 8, was bedeutet, dass Sie sich nach rechts und unten zur 4 bewegen und einen Zyklus mit Periode 2 beginnen.

Im Allgemeinen wird dieser Vorgang fortgesetzt, bis Sie eine 0 erreichen oder ein Zyklus bemerkt wird. (Eine 0 wird als Zyklus mit Periode 1 betrachtet.)

Im Fall von 1480 beträgt die schließlich bei jeder der 4 Startziffern erreichte Periode 2 2 2 1jeweils.

Für ein größeres Gitter können diese Zahlen größer als 8 sein, aber wir können sie immer noch als "Ziffern" in einer neuen nicht-sekundären Zahl verwenden (einfach die Koeffizienten von 9 ^ n, als wären sie Ziffern):

2*9^3 + 2*9^2 + 2*9 + 1 = 1639 (base 10) = 2221 (base 9)

Wir werden dies die Stärke der ursprünglichen Nonary-Nummer nennen. Die Stärke von 1480 beträgt also 1639 (Basis 10) oder gleichwertig 2221 (Basis 9).

Herausforderung

Schreiben Sie das kürzeste Programm, das angibt, ob die Stärke einer Nicht-Zahl größer, kleiner oder gleich der Nicht-Zahl selbst ist. (Sie müssen die Stärke nicht unbedingt berechnen.)

Die Eingabe ist eine nicht negative nicht-sekundäre Zahl, die eine quadratische Anzahl von Ziffern enthält (und keine führenden Nullen außer dem Sonderfall 0 selbst). Es sollte von der Kommandozeile oder stdin kommen.

Die Ausgabe sollte wie folgt an stdout gehen:

G if the strength is larger than the original number (example: 1480 -> strength = 2221)
E if the strength is equal to the original number (example: 1 -> strength = 1)
L if the strength is less than the original number (example: 5 -> strength = 1)

Fun Bonus Challenge:
Was ist der höchste Input, den Sie finden können, der seiner Stärke entspricht? (Gibt es eine Grenze?)


quelle
Wird die Eingabe als Dezimalzahl angegeben, deren Ziffern mit der Nicht-Zahl oder mit der Dezimal- (oder Binär-) Darstellung der Nicht-Zahl identisch sind? dh: für 1480 (nicht) wird die Eingabe 1480 oder 1125 sein?
Overactor
@overactor Im nichtary Format.
2
Ich bin ziemlich zuversichtlich, dass niemand eine höhere Eingabe finden wird, die seiner Stärke entspricht als 10 ^ 71-1 (nicht), dh eine 64-stellige Zahl, die nur aus 8 besteht
Overactor
@overactor Es könnte mit Zyklen von mehr als 8 möglich sein, denke ich.
Martin Ender
@ MartinBüttner Ich werde sehr beeindruckt sein, wenn Sie eines davon finden.
Overactor

Antworten:

2

Python 2, 213 209 202

Bearbeiten: Kurzschluss entfernt, was manchmal falsch ist. Siehe unten.

(Weitgehend) Der gleiche Algorithmus wie @KSab, aber sehr stark golfen.

n=`input()`
s=int(len(n)**.5)
c=0
for i in range(s*s):
 a=[]
 while(i in a)<1:a+=[i];x='432501678'.find(n[i]);i=(i+x%3-1)%s+((i/s+x/3-1)%s)*s
 c=c*9+len(a)-a.index(i)
d=long(n,9)
print'EGL'[(c>d)-(c<d)]

Golf:

  • 213: Kurzschluss, fehlerhafte Lösung.

  • 209: Erste funktionierende Lösung.

  • 202: Kombiniert die beiden String-Lookups zu einem.

Bearbeiten: Ich habe gerade festgestellt, dass dieses Programm und damit auch das von KSab fehlerhaft sind, da sie mehrstellige Zykluslängen ignorieren. Beispielfehler:

3117
2755
3117
7455

Während die 3 eine Zykluslänge von 2 hat und somit der obige Algorithmus zu 'L' kurzschließt, sollte dies tatsächlich 'G' zurückgeben, da die Zykluslänge von 14 auf der zweiten Ziffer dies mehr als überwindet. Ich habe daher das Programm geändert. Es wurde auch kürzer, lustig genug. Verwenden Sie zum Testen Ihres Programms 3117275531177455. Es sollte zurückkehren G.

isaacg
quelle
Wow, ich dachte, ich hätte ein bisschen Golf gespielt, aber du hast dort ein paar ziemlich clevere Sachen gemacht.
KSab
@KSab Danke - Ihr Algorithmus war anfangs sehr clever - ich konnte keinen besseren Weg finden, dies zu tun.
isaacg
2

Python 296

Nicht wirklich zu ineffizient, sondern überprüft nur so viele Ziffern wie nötig.

n=raw_input();s=int(len(n)**.5);t=0
for i in range(s**2):
    l=[]
    while i not in l:l.append(i);c=n[i];i=(i%s+(-1 if c in'456'else 1 if c in'218'else 0))%s+((i/s+(-1 if c in'432'else 1 if c in'678'else 0))%s)*s
    t=t*9+len(l)-l.index(i)
print'EGL'[cmp(t,long(n,9))]

Was Zahlen betrifft, die ihrer Stärke entsprechen, denke ich, dass die einzigen Lösungen für jedes N x N-Quadrat bis zu N = 8 ein Quadrat sind, das N in jedem Raum enthält. Ich denke, da jede Zahl in einer Schleife dieselbe Zahl (die Länge der Schleife) sein muss, müsste jede Schleife alle in eine Richtung gehen. Dies bedeutet natürlich, dass die Größe der Schleife N sein muss (und jedes Element N sein muss). Ich bin mir ziemlich sicher, dass diese Logik auf Quadrate und Schleifen jeder Größe angewendet werden kann, was bedeutet, dass es keine Quadrate gibt, die ihrer Stärke entsprechen, außer den ersten 8.

KSab
quelle
Obwohl unwahrscheinlich, könnte es für Schleifen größer als 8 möglich sein.
Overactor
2
Ich denke, dies führt zu einem falschen Ergebnis 3117275531177455, da die Schleifengröße größer als 8 ist. Siehe meinen Beitrag.
isaacg
1
@isaacg Oh, das habe ich nicht gesehen, ich habe es geändert, damit es funktioniert, aber ich werde nicht versuchen, es weiter zu spielen, weil das so ziemlich nur das Kopieren Ihrer Antwort wäre. Oh und ich denke, Sie können Ihre letzten beiden Zeilen verbessern, indem Sie verwenden cmp.
KSab
1

CJam - 81

q:X,:L,{[L2*{_[_Lmqi:Smd@X=432501678s#3md]2/z{~+(S+S%}%Sb}*]L>_&,\X=~-}%9bg"EGL"=

Probieren Sie es unter http://cjam.aditsu.net/ aus.

Es kann wahrscheinlich noch mehr Golf gespielt werden.

Aditsu beenden, weil SE böse ist
quelle
0

Lua - Noch nicht Golf gespielt

Einfach hier zur Aufbewahrung einlegen. Ich werde es später spielen (und das "Für ein größeres Gitter sind diese Zahlen möglicherweise größer als 8, aber wir können sie trotzdem als" Ziffern "verwenden" implementieren). Funktioniert aber.

d={{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1}}
d[0]={0,0}ssd=''
n=arg[1]
q=math.sqrt(#n)t={}

    for y=1,q do
    table.insert(t,y,{})
    for x =1,q do
        v=(y-1)*q+x
        table.insert(t[y],x,n:sub(v,v)+0)
        io.write(t[y][x])
    end
end
for y=1,q do
    for x=1,q do
        cx=x cy=y pxy=''sd=0
        while pxy:match(cx..':%d*:'..cy..' ')==nil do
            pxy=pxy..cx..':'..sd..':'..cy.." "
            ccx=cx+d[t[cx][cy]][2]
            ccy=cy+d[t[cx][cy]][1]
            cx=ccx cy=ccy
            if cx<1 then cx=q elseif cx>q then cx=1 end
            if cy<1 then cy=q elseif cy>q then cy=1 end
            sd=sd+1
        end
        dds=(pxy:sub(pxy:find(cx..':%d+:'..cy)):match(':%d*'))
        ssd=ssd..(sd-dds:sub(2))
    end
end
print(ssd)
nn=tonumber(n,9) tn=tonumber(ssd,9)
if tn>nn then print("G") elseif tn==nn then print("E") else print("L") end
AndoDaan
quelle