Suche nach der Sequenz der "Schneckennummer"

8

Sie erhalten Ganzzahlen Nund M, 1 <= N,M <= 10^6und Indizes iund j. Ihre Aufgabe ist es, die Ganzzahl an der Position zu finden [i][j]. Die Sequenz sieht folgendermaßen aus ( N=M=5, i=1, j=3das Ergebnis ist 23):

 1  2  3  4  5
16 17 18 19  6
15 24 25 20  7
14 23 22 21  8
13 12 11 10  9

Der kürzeste Code gewinnt. Viel Glück!

code-golf user32839
quelle
Sehr eng verwandt.
Martin Ender
So gut wie das.
Martin Ender
1
Vielleicht möchten Sie klären, ob M die Breite oder die Höhe ist.
Martin Ender
@ MartinBüttner: Ich denke N entspricht i und M entspricht j. Dann müssen Sie nur noch angeben, dass die Schnecke i=j=0in j=0Richtung beginnt und weitergeht .
M.Herzkamp
6
Muss unser Code in angemessener Zeit mit einer angemessenen Menge an Speicher für die angegebenen Grenzwerte abgeschlossen sein? Ich kann definitiv gültigen Code für diese Parameter schreiben , der nur die Spirale erzeugt und den Wert nachschlägt, aber ich habe nicht wirklich 4 TB Speicher herumliegen.
Martin Ender

Antworten:

6

Mathematica, 63 55 Bytes

f=If[#5<1,#+#4,f[#+#2,#3-1,#2,#5-1,#2-1-#4]]&;g=1~f~##&

Dies definiert eine Funktion, gdie wie aufgerufen werden kann

g[5, 5, 1, 3]

Ich benutze einen rekursiven Ansatz. Es werden bis zu 2 (N + M) Iterationen verwendet, je nachdem, wie weit unten in der Spirale das Ergebnis gefunden wird. Es verarbeitet alle Eingaben (bis zu g[10^6,10^6,5^5-1,5^5], was die meisten Iterationen erfordert) innerhalb weniger Sekunden, aber für größere Eingaben müssen Sie das Standard-Iterationslimit wie erhöhen

$IterationLimit = 10000000;

Wenn kdie Startnummer der Spirale ist, überprüfe ich im Grunde, ob der jIndex ist. 0In diesem Fall kann ich einfach zurückkehren k + i. Ansonsten werfe ich die oberste Reihe weg, drehe die Spirale um 90 Grad (gegen den Uhrzeigersinn), erhöhe sie kentsprechend und schaue stattdessen auf die verbleibende Spirale. Wir können mit der folgenden Zuordnung von Parametern zur nächsten Spirale übergehen:

  • k n + 1 = k n + m n
  • M n + 1 = N n - 1
  • N n + 1 = M n
  • i n + 1 = j n - 1
  • j n + 1 = n m - i n - 1

Dies setzt voraus, dass M die Breite und N die Höhe ist.

Martin Ender
quelle
51 Bytes:If[#5<1,#+#4,#0[#+#2,#3-1,#2,#5-1,#2-1-#4]]&[1,##]&
LegionMammal978
3

Pyth, 25 Bytes

D(GHYZ)R?+G(tHGtZt-GY)ZhY

Dies definiert eine Funktion (. Anwendungsbeispiel:

D(GHYZ)R?+G(tHGtZt-GY)ZhY(5 5 1 3

druckt 23.

Dies ist algorithmisch identisch mit der Mathematica-Antwort von Martin Büttner, obwohl sie unabhängig entwickelt wurde. Soweit ich das beurteilen kann, ist dies der einzig gute Weg, dies zu tun.

Beachten Sie, dass Pyth auf meinem Computer nicht den gesamten Eingabebereich verarbeiten kann. Es wird den Stapel überlaufen und bei großen Eingaben mit einem Segfault sterben.

isaacg
quelle
1

Haskell, 44

z j i m n|j==0=i+1|0<1=z(n-i-1)(j-1)n(m-1)+n

Dies verwendet den regulären rekursiven Ansatz

stolzer haskeller
quelle