Diese Herausforderung stellte einen Algorithmus zum Codieren einer Ganzzahl nals eine andere Ganzzahl dar r. Was folgt, ist eine kurze Erklärung dieses Algorithmus am n=60Beispiel.

Der ursprüngliche Algorithmus

Zuerst codieren wir die Zahl als eine Klammer.
- Wenn n = 1, geben Sie eine leere Zeichenfolge zurück.
- Andernfalls nehmen wir die naufsteigende Primzerlegung sortiert und ersetzen jedes Element durch seinen Primindex (1-indiziert) in Klammern.60 = 2*2*3*5 => [1][1][2][3]
- Tun Sie dies rekursiv, bis wir nur noch Klammern haben. [1][1][2][3] => [][][[1]][[2]] => [][][[]][[[1]]] => [][][[]][[[]]]
Sobald wir unsere Klammer haben, konvertieren wir diese mit dem folgenden Prozess in eine Ganzzahl.
- Konvertieren Sie jede öffnende Klammer in a 1und jede schließende Klammer in a 0.[][][[]][[[]]] => 10101100111000
- Entfernen Sie alle nachfolgenden 0s und das Finale 1.10101100111000 => 1010110011
- Konvertieren Sie die letzte Zeichenfolge von 0s und 1s von binär in eine Ganzzahl.1010110011 => 691

Dekodierung dieser Kodierung

Eine interessante Eigenschaft dieses Algorithmus ist, dass er nicht surjektiv ist. Nicht jede Ganzzahl kann das Ergebnis dieser Codierung sein.

Erstens muss die binäre Darstellung des Ergebnisses darin bestehen r, balance-abledass die Anzahl von 0s niemals die Anzahl von 1s überschreiten darf . Ein kurzer Falsey-Testfall ist 4, der 100binär ist.
Zweitens müssen die Klammern in der Binärdarstellung stehen, sorted ascendingwenn das letzte 1und das nachfolgende 0s erneut angehängt werden. Ein kurzer Falsey-Testfall ist 12 <= 1100 <= 110010 <= (())().

Nur zu bestimmen, ob eine Zahl auf diese Weise decodierbar ist, würde eine kurze Herausforderung darstellen. Stattdessen besteht die Herausforderung darin , eine bestimmte Eingabe wiederholt zu decodieren , bis entweder eine nicht decodierbare Zahl oder ein Zyklus erreicht ist, und die resultierende Folge von Zahlen zurückzugeben.

Die Herausforderung

Geben Sie bei einer gegebenen Zahl 1 <= r <= 2**20 = 1048576die Folge von Zahlen zurück , in die r nacheinander dekodiert wird, beginnend mit sich rselbst und endend mit einer nicht dekodierbaren Zahl oder einem Zyklus.
Wenn eine nicht decodierbare Nummer als Eingabe angegeben wird, z. B. 4oder 12, wird eine Liste zurückgegeben, die nur die Eingabe enthält.
Eine Sequenz, die in einem Zyklus endet, sollte auf irgendeine Weise angezeigt werden, entweder durch Anhängen oder Voranstellen eines Markers (wählen Sie eine nicht positive Ganzzahl, Zeichenfolge, Liste usw. als Marker aus, aber halten Sie sie konsistent) oder durch Wiederholen des Zyklus in auf irgendeine Weise (Wiederholung des ersten Elements, Wiederholung des gesamten Zyklus, unendliche Wiederholung usw.).
Betrachten Sie es als undefiniertes Verhalten, wenn eine der Sequenzen nicht unendlich ist (z. B. indem Sie für immer zunehmen).
Das ist Code Golf. Die kleinste Anzahl von Bytes gewinnt.

Ein funktionierendes Beispiel für die Dekodierung

   1 -> 1 -> 1100 -> [[]] -> [2] -> 3
-> 3 -> 11 -> 111000 -> [[[]]] -> [[2]] -> [3] -> 5
-> 5 -> 101 -> 101100 -> [][[]] -> 2*[2] -> 2*3 -> 6
-> 6 -> 110 -> 110100 -> [[][]] -> [2*2] -> [4] -> 7
-> 7 -> 111 -> 11110000 -> [[[[]]]] -> [[[2]]] -> [[3]] -> [5] -> 11
-> 11 -> 1011 -> 10111000 -> [][[[]]] -> 2*[[2]] -> 2*[3] -> 2*5 -> 10
-> 10 -> 1010 -> 101010 -> [][][] -> 2*2*2 -> 8
-> 8 -> 1000  ERROR: Unbalanced string

Testfälle

4 -> [4]
12 -> [12]
1 -> [1, 3, 5, 6, 7, 11, 10, 8]
2 -> [2, 4]
13 -> [13, 13]    # cycle is repeated once
23 -> [23, 22, 14, 17]
51 -> [51, 15, 31, 127, 5381]
691 -> [691, 60]
126 -> [126, 1787, 90907]
1019 -> [1019, 506683, 359087867, 560390368728]

Vorschläge und Feedback zu dieser Herausforderung sind herzlich willkommen. Viel Glück und gutes Golfen!

code-golf primes balanced-string Sherlock9
quelle

Sandkasten .

user202729

Wie gibt 1es 3?

Undichte Nonne

@LeakyNun 1- (Anhängen einer 1und nachfolgende Nullen) -> 1100-> [[]]-> [[1]]-> [2]->3

Colera Su

6-> 110-> 110100was ist nicht gültig, oder? Also sollte Input 1geben [1,3,5,6]?

Dylnan

Und für 7: 7-> 111-> 11110000-> [[[[]]]]-> 4. Primzahl = 7? Vielleicht verstehe ich den Algorithmus nicht

Dylnan

Python 3 , 379 358 339 337 327 310 304 Bytes

Vermutung: Ist 13die einzige Zahl, die zu einem Zyklus führt? (Es gibt keine Ausnahmen kleiner als 10 ^6. )

Fehler und -7 Bytes dank Sherlock9 behoben .
-3 Byte dank Jonathan Frech .
-16 Bytes dank Ovs .
-6 Bytes dank Mr. Xcoder .

Wenn es einen Zyklus gibt, wird der gesamte Zyklus wiederholt.

def p(a,x=0,n=1):
 while a:x+=1;a-=n%x;n*=x*x
 return x
def g(a):
 c=i=0
 for v in a:
  c+=int(v)*2-1
  if c<0:return 0,0
  if c<1:break
  i+=1
 if a:x=p(g(a[1:i])[0]);b,c=g(a[i+1:]);return(x>c>0)*(0,0)or(x*b,x)
 return 1,0
def f(a):
 x=a,
 while(x.count(a)<3)*a:a,t=g(bin(a-~a)[2:]);x+=a,
 return x[:-1]

Probieren Sie es online aus!

Erläuterung:

def p(a,x=0,n=1):     # return the a-th prime
 while a:             # magical way to enumerate primes
  x+=1
  a-=n%x
  n*=x*x
 return x

def g(a):             # decode a 0/1 string
 c=i=0
 for v in a:
  c+=int(v)*2-1       # +1 if 1, -1 if 0
  if c<0: return(0,0) # c<0: unbalanced parentheses
  if c<1: break       # first outermost parentheses
  i+=1
 if a:
   x=p(g(a[1:i])[0])  # recursive solve those inside the parentheses ...
   b,c=g(a[i+1:])     # and the remaining
   if x>c and c:      # if not ascending
    return (0,0)
   return (x*b,x)     # return (result, value of first closed parentheses)
 return (1,0)         # empty string

def f(a):
 x=a,
 while a and x.count(a)<3: # detect non-decodable or cycle
  a,t=g(bin(a-~a)[2:])     # a-~a is a*2+1
  x+=a,
 return x[:-1]

Colera Su
quelle

Dekodiere diese Nummer weiter!

Antworten:

Python 3 , 379 358 339 337 327 310 304 Bytes

Pyth, 62 Bytes