Integer Division Loops

8

Herausforderung

Bei jeder positiven Ganzzahl, die von Ihrer Sprache unterstützt wird:

  1. Nehmen Sie die Eingabe und teilen Sie sie in zwei Hälften. Wenn die Eingabe für alle Abteilungen in diesem Programm ungerade ist, runden Sie eine Hälfte nach oben und eine Hälfte nach unten (z. B. 7 -> 3,4nicht 7 -> 3.5,3.5).
  2. Teilen Sie eine der beiden Zahlen in zwei Hälften, nehmen Sie dann die größere dieser beiden neuen Hälften und addieren Sie sie zu der Zahl, die nicht geteilt wurde. Bsp.: 3,4 -> (1,2),4 -> 1,6Oder 3,4 -> 3,(2,2) -> 5,2.
  3. Wiederholen Sie Schritt 2, bis Sie einen Satz erreicht haben, den Sie zuvor gesehen haben. Bsp. : 5 -> 3,2 -> (1,2),2 -> 1,4 -> 1,(2,2) -> 3,2. Wie wir schon gesehen 3,2haben, hören wir möglicherweise auf, uns zu wiederholen. Sie können dabei einen Stapel vollständig erschöpfen. Bsp. : 5 -> 3,2 -> (1,2),2 -> 1,4 -> (0,1),4 -> 0,5.
  4. Geben Sie jedes Paar in der Schleife aus (dh die obigen Schritte ohne Zwischenschritte vom ersten Auftreten eines Paares bis zum zweiten, jedoch ohne das zweite). Bsp. : 3,2 -> 1,4. Wenn die Eingabe enthalten ist, geben Sie keine 0mit - 5 -> 3,2 -> 1,4- nicht 0,5 -> 3,2 -> 1,4.
  5. Wiederholen Sie die Schritte 1 bis 4, indem Sie die Paare unterschiedlich aufteilen.

I / O.

Die Eingabe ist eine positive Ganzzahl, die größer 1und kleiner als die von Ihrer Sprache unterstützte maximale Ganzzahl oder die maximale Ganzzahl ist, die den Computer nicht zum Absturz bringt, je nachdem, welcher Wert kleiner ist.

Die Ausgabe erfolgt über die Schleifen von oben in einem beliebigen Format (Zeichenfolge, Liste, Array usw.). Nachgestellte Leerzeichen sind zulässig.

Geben Sie nicht zweimal dieselbe Schleife oder verschiedene Versionen derselben Schleife aus. Beispiel: 2 -> 1,1und 1,1 -> 2sind beide gültige Schleifen, aber sie beschreiben dieselbe Schleife, beginnend an verschiedenen Punkten der Schleife. Ebenso sollten zwei Schleifen, die identisch sind, aber in umgekehrter Reihenfolge ablaufen, nicht ausgegeben werden. Bsp.: 3 -> 1,2 -> 2,1Und 3 -> 2,1 -> 1,2sind die gleiche Schleife, aber sie gehen in die entgegengesetzte Richtung voneinander.

Sie können ein beliebiges Trennzeichen verwenden, um zwischen den Paaren, zwischen jeder Zahl in den Paaren und zwischen jeder Schleife zu unterscheiden, vorausgesetzt, es handelt sich um drei verschiedene Zeichen oder Zeichenfolgen. Oben habe ich die Zahlen mit Kommas geteilt, die Paare mit ->'s und die Schleifen mit langweiligen Anweisungen. In den folgenden Beispielen verwende ich Klammern um jedes Paar, Kommas zwischen jeder Zahl innerhalb eines Paares und neue Zeilen zwischen jeder Schleife.

Beispiele

Dank an den Code von @ WheatWizard für die Korrektur meiner Beispielliste. Wie ich in einem früheren Entwurf sagte, war ich mir sicher, dass ich einige vermisste, da ich es von Hand tat, aber Junge, ich vermisste einige.

Eingabe: 2
Ausgabe:(2)(1,1)

Eingabe: 3
Ausgabe:

(3)(1,2)
(1,2)(2,1)
(3)(1,2)(2,1)

Eingabe: 4
Ausgabe:

(4)(2,2)(1,3)
(1,3)(3,1)
(4)(2,2)(1,3)(3,1)
(4)(2,2)(3,1)(1,3)
(3,1)(1,3)
(4)(2,2)(3,1)

Eingang: 5

Ausgabe:

(5)(2,3)(1,4)
(1,4)(3,2)
(2,3)(1,4)(3,2)(4,1)
(5)(2,3)(1,4)(3,2)(4,1)
(2,3)(4,1)
(5)(2,3)(4,1)

Eingang: 6

Ausgabe:

(6)(3,3)(1,5)
(1,5)(4,2)(2,4)
(4,2)(2,4)
(1,5)(4,2)(5,1)(2,4)
(4,2)(5,1)(2,4)
(6)(3,3)(1,5)(4,2)(5,1)
(6)(3,3)(5,1)(2,4)(1,5)
(2,4)(1,5)(4,2)
(5,1)(2,4)(1,5)(4,2)
(2,4)(4,2)
(5,1)(2,4)(4,2)
(6)(3,3)(5,1)

Eingang: 7

Ausgabe:

(7)(3,4)(1,6)
(1,6)(4,3)(2,5)
(2,5)(5,2)
(3,4)(1,6)(4,3)(2,5)(5,2)(6,1)
(7)(3,4)(1,6)(4,3)(2,5)(5,2)(6,1)
(3,4)(1,6)(4,3)(6,1)
(7)(3,4)(1,6)(4,3)(6,1)
(7)(3,4)(5,2)(2,5)(1,6)
(2,5)(1,6)(4,3)
(3,4)(5,2)(2,5)(1,6)(4,3)(6,1)
(7)(3,4)(5,2)(2,5)(1,6)(4,3)(6,1)
(5,2)(2,5)
(3,4)(5,2)(6,1)
(7)(3,4)(5,2)(6,1)

Wertung

Dies ist , also gewinnt die niedrigste Byteanzahl.


Dies ist meine erste Herausforderung hier, daher wäre jedes Feedback sehr dankbar. Link zur Sandbox hier .

Eine lustige Tatsache: Ich war eines Tages gelangweilt und spielte auf diese Weise mit zufälligen kleinen Bleistiftbleistücken und bemerkte schließlich, dass ich in solchen Schleifen weitermachen konnte. Aus irgendeinem Grund war meine erste Reaktion: "Hey, das wäre eine große Herausforderung für Code-Golf."

DonielF
quelle
4
Willkommen bei PPCG, schöne erste Herausforderung!
FlipTack
Dürfen wir (a,0)anstelle von drucken (a)? Dies ist in stark typisierten Sprachen eher sinnvoll.
Ad-hoc-Garf-Jäger
@ WheatWizard Nein. Wenn Sie die Eingabe drucken, drucken Sie einfach die Eingabe ohne Null. Ich habe hier keine Herausforderung gesehen, bei der es nur um ein oder zwei Bytes geht.
DonielF
Ok, das ist fair genug. Aber für die Aufzeichnung würde ich es sicherlich nicht ein oder zwei Bytes nennen. Für mich sieht es so aus, als ob ungefähr 30% meiner Byteanzahl aus dem Entfernen der Null stammen.
Ad-hoc-Garf-Jäger
Können wir die Schleifen in umgekehrter Reihenfolge ausgeben, da dieselbe Schleife in umgekehrter Richtung dieselbe ist?
ousurous

Antworten:

2

Sauber , 267 ... 167 Bytes

import StdEnv
f s l|any((==)s)l=[dropWhile((<>)s)l]#[h,t:_]=s
|1>h*t=f[max h t]l=f[h/2,(h+1)/2+t](l++[s])++(f[(t+1)/2+h,t/2](l++[s]))
@n=removeDup(f[n/2,(n+1)/2][[n]])

Probieren Sie es online aus!

Ungolfed:

loops num
    = removeDup (half (divide num) [[num]])
where
    divide num
        = [num/2, (num+1)/2]
    half [_, 0] list
        = list
    half [0, _] list
        = list
    half [a, b] list
        | isMember [a, b] list
            = [dropWhile ((<>) [a, b]) list]
        # [u, v: _]
            = divide a
        # [x, y: _]
            = divide b
        = (half [u, v+b] (list ++ [a, b])) ++ (half [a+y, x] (list ++ [a, b]))
Οurous
quelle
2

Haskell , 227 203 Bytes

17 Bytes gespart dank Οurous

(%)=div
u x|odd x=x%2+1|1>0=x%2
[0,b]!l=[b]!l
[b,0]!l=[b]!l
t!l|elem t l=[dropWhile(/=t)l]
t@[a,b]!l|q<-l++[t]=[a%2,u a+b]!q++[u b+a,b%2]!q
f x|q<-[x%2,u x]![[x]]=[a|(a,b)<-zip q[0..],notElem a$take b q]

Probieren Sie es online aus!

Ad-hoc-Garf-Jäger
quelle
Wäre die Verwendung von Listen nicht kürzer als Tupel, da Sie sowohl die 1- als auch die 2-Element-Fälle mit denselben behandeln könnten show?
ousurous
@ Οurous Eigentlich hast du recht, es ist kürzer, es braucht nur etwas Arbeit.
Ad-hoc-Garf-Jäger