Hintergrund

In vielen esoterischen Programmiersprachen sind keine Zahlen in Literalen integriert, daher müssen Sie diese zur Laufzeit berechnen. und in vielen dieser Fälle kann die Zahlendarstellung sehr interessant sein. Wir hatten bereits eine Herausforderung , Zahlen für Unterlast darzustellen. Bei dieser Herausforderung geht es darum, Zahlen in Modular SNUSP darzustellen . (Beachten Sie, dass Sie SNUSP nicht lernen müssen, um diese Herausforderung abzuschließen. Alle Informationen, die Sie benötigen, sind in der Spezifikation enthalten. Möglicherweise finden Sie den Hintergrund jedoch interessant.)

Die Aufgabe

Für die Zwecke dieser Herausforderung ist eine modulare SNUSP-Nummer eine Zeichenfolge, die aus den Zeichen gebildet @wird +, und =mit der Ausnahme, dass das letzte Zeichen a #ist und das vorletzte Zeichen sein muss +oder =(es kann nicht sein @). Zum Beispiel gültige Zahlen sind @+#, ==#und @@+@=#; Beispiele für ungültige Nummern enthalten +=, @@#und +?+#.

Der Wert einer modularen SNUSP-Nummer wird rekursiv wie folgt berechnet:

• # hat einen Wert von 0 (dies ist der Basisfall).
• Wenn die Zahl =xfür eine Zeichenfolge die Form hat x, entspricht ihr Wert dem Wert von x.
• Wenn die Zahl +xfür eine Zeichenfolge die Form hat x, entspricht ihr Wert dem Wert xplus 1.
• Wenn die Zahl die Form @cxfür ein einzelnes Zeichen cund eine beliebige Zeichenfolge hat x, entspricht ihr Wert dem Wert von xplus dem Wert von cx.

Für diese Herausforderung müssen Sie ein Programm schreiben, das eine nichtnegative Ganzzahl als Eingabe verwendet und eine Zeichenfolge ausgibt, die die kürzestmögliche modulare SNUSP-Nummer ist und deren Wert der Eingabe entspricht.

Klarstellungen

• Es ist durchaus möglich, dass es mehr als eine Zeichenfolge mit demselben Wert gibt, und insbesondere für einige Ganzzahlen gibt es einen Gleichstand für die kürzeste modulare SNUSP-Nummer mit diesem Wert. In einem solchen Fall können Sie eine der beteiligten Zahlen mit dem Gleichstand ausgeben.
• Der Algorithmus, mit dem Sie die Nummer ermitteln, ist nicht eingeschränkt. Zum Beispiel ist es eine legale Taktik, Strings brutal zu erzwingen und zu bewerten, aber auch etwas Klügeres zu tun, um den Suchraum zu verkleinern.
• Wie bei PPCG üblich, kann Ihre Einreichung entweder ein vollständiges Programm oder eine Funktion sein (wählen Sie das aus, was in Ihrer Sprache prägnanter ist).
• Dies ist kein Problem bei der Verarbeitung von Eingabe- und Ausgabeformaten. Sie können also alle angemessenen Mittel verwenden, um eine nichtnegative Ganzzahl einzugeben und eine Zeichenfolge auszugeben. Es gibt eine vollständige Anleitung zu Meta , aber die am häufigsten verwendeten rechtlichen Methoden umfassen Funktionsargumente / -rückgaben, Befehlszeilenargumente und Standardeingabe / Standardausgabe.

Testfälle

Hier sind die kürzesten Darstellungen der ersten Zahlen:

• 0 :#
• 1 :+#
• 2 :++#
• 3 : +++#oder@++#
• 4 : ++++#oder +@++#oder@=++#
• 5 : @+++#oder@@++#
• 6 : +@+++#oder +@@++#oder @=+++#oder @=@++#oder@@=++#
• 7 : @++++#oder@+@++#
• 8 : @@+++#oder@@@++#
• 9 : +@@+++#oder +@@@++#oder @+++++#oder @++@++#oder @+@=++#oder @@=+++#oder@@=@++#
• 10 : @=@+++#oder @=@@++#oder @@@=++#( dies ist ein ziemlich wichtiger Testfall , da alle möglichen Antworten beinhalten =)
• 11 : @+@+++#oder @+@@++#oder @@++++#oder@@+@++#
• 12 : +@+@+++#oder +@+@@++#oder +@@++++#oder +@@+@++#oder @=+@+++#oder @=+@@++#oder @=@=+++#oder @=@=@++#oder @=@@=++#oder @@=++++#oder @@=+@++#oder@@=@=++#
• 13 : @@@+++#oder@@@@++#
• 14 : +@@@+++#oder +@@@@++#oder @=@++++#oder @=@+@++#oder @@+++++#oder @@++@++#oder@@+@=++#
• 15 : @+@++++#oder @+@+@++#oder @@=@+++#oder @@=@@++#oder @@@=+++#oder@@@=@++#

Als größerer Testfall ist der Ausgang vom Eingang 40 soll @@@=@@+++#, @@@=@@@++#, @@@@=@+++#, oder @@@@=@@++#.

Siegbedingung

Als Code-Golf- Herausforderung ist der Gewinner der kürzeste Eintrag, gemessen in Bytes.

Oracle SQL 11.2, 341 262 Bytes

WITH e AS(SELECT DECODE(LEVEL,1,'=',2,'@','+')e FROM DUAL CONNECT BY LEVEL<4),n(s,v,p,c,i)AS(SELECT'#',0,0,e,1 FROM e UNION ALL SELECT c||s,DECODE(c,'+',1,'@',p,0)+v,v,e,i+1 FROM n,e WHERE i<11)CYCLE s SET y TO 1 DEFAULT 0 SELECT s FROM n WHERE:1=v AND rownum=1;

Alte Version

WITH e AS(SELECT DECODE(LEVEL,1,'=',2,'@','+')e FROM DUAL CONNECT BY LEVEL<4),n(s,v,p,c) AS(SELECT'#',0,0,e FROM e UNION ALL SELECT s||c,CASE c WHEN'+'THEN 1 WHEN'='THEN 0 WHEN'@'THEN p ELSE 0 END+v,v,e FROM n,e WHERE LENGTH(s)<10)CYCLE s SET y TO 1 DEFAULT 0 SELECT MIN(REVERSE(s))KEEP(DENSE_RANK FIRST ORDER BY LENGTH(s))FROM n WHERE v=:1;

: 1 die Zahl, die in Modular SNUSP dargestellt werden soll

Nicht Golf:

WITH e AS (SELECT DECODE(LEVEL,1,'=',2,'@','+')e FROM DUAL CONNECT BY LEVEL<4),  
n(s,v,p,c,i) AS                   
(
  SELECT '#',0,0,e,1 FROM e
  UNION ALL
  SELECT s||c
       , DECODE(c,'+',1,'@',p,0)+v 
       , v
       , e
       , i+1
  FROM n,e
  WHERE i<11
) CYCLE s SET y TO 1 DEFAULT 0
SELECT s FROM n WHERE:1=v AND rownum=1;

Erstellen Sie zunächst eine Ansicht mit 3 Zeilen, eine für jedes Symbol, das zur Darstellung von Zahlen verwendet wird, minus #, das nur am Ende der Zeichenfolge verwendet wird:

SELECT DECODE(LEVEL,1,'=',2,'@','+')e FROM DUAL CONNECT BY LEVEL<4;    

Dann erzeugt die rekursive Ansicht n jede mögliche Zeichenfolge mit diesen 3 Symbolen, verkettet sie mit # und wertet sie aus.

Die Parameter sind:

s: die modulare SNUSP-Darstellung der zu bewertenden Zahl
v: der Dezimalwert von s, der durch die vorherige Iteration berechnet wurde
p: v, berechnet durch die i-2-Iteration
c: das nächste Symbol, das mit s
i verkettet wird : nur die Länge von s benötigt, um zwei LENGTH () für Golfzwecke loszuwerden

DECODE(c,'+',1,'@',p,0)+v 

Wenn das letzte Symbol + ist, addiere 1
Wenn es @ ist, addiere den Wert der i-2-Iteration.
Andernfalls ist das Symbol entweder # oder =. v wird im Init-Teil der rekursiven Ansicht mit 0 initialisiert, sodass das neue v in beiden Fällen gleich dem vorherigen v ist.

WHERE i<11

Jede mit den 3 Symbolen mögliche Zeichenfolge wird berechnet. Dieser Teil stellt sicher, dass die Anforderung erst nach dem großen Crunch ausgeführt wird.

CYCLE s SET y TO 1 DEFAULT 0

Da es keine Regel für die Konstruktion der Zeichenfolgen gibt, müssen Duplikate entstehen. In einer rekursiven Ansicht interpretiert Oracle diese Duplikate als Zyklen und gibt einen Fehler aus, wenn der Fall nicht explizit behandelt wird.

SELECT s FROM n WHERE:1=v AND rownum=1;

Gibt die erste modulare SNUSP-Darstellung zurück, die die als Parameter eingegebene Dezimalzahl ergibt: 1

In meinen Tests ist diese erste Zeile immer eine der kürzesten Darstellungen.

Falls Ihre Datenbank nicht auf die gleiche Weise funktioniert, sollte diese letzte Klausel durch ersetzt werden

SELECT MIN(s)KEEP(DENSE_RANK FIRST ORDER BY i)FROM n WHERE:1=v

JavaScript (ES6), 100 Byte

n=>eval("for(a=[['#',0,0]];[[s,t,p],...a]=a,t-n;)a.push(['='+s,t,t],['+'+s,t+1,t],['@'+s,t+p,t]);s")

Einfacher Brute-Force-Suchalgorithmus.

Pyth, 41 Bytes

L?b+ytb@[yttb001)Chb0+hfqQyTs^L"+@="UhQ\#

Testsuite

Wie es funktioniert:

Es gibt zwei Teile. Eine rekursive Funktion, die den Wert eines SNUSP-Ausdrucks ohne Trailing berechnet #, und eine Brute-Force-Routine.

Bewertung:

L?b+ytb@[yttb001)Chb0
L                        Define the function y(b) as follows
 ?b                      If b is nonempty
   +ytb                  The sum of y(tail(b)) and   # tail(b) = b[1:]
   @[       )            The element in the list at location
   Chb                   Character values of the first character.
                         Modular indexing means that 
                         + -> 3
                         @ -> 0
                         = -> 1
                         Index 2 is filler.
    [yttb001)            @ adds y(tail(tail(b)). Tail suppresses the error when
                         called on an empty list, so this treats @# as zero, but
                         this can't lead to problems because removing the @ will
                         always make the expression shorter.
                         + adds 1, = adds 0.
 0                       If b is the empty string, return 0

Rohe Gewalt:

+hfqQyTs^L"+@="UhQ\#
               UhQ      0 ... Q     # Q is the input
        ^L"+@="         Map that list to all strings formed from the characters
                        "+@=", with that many characters.
       s                Concatenate
  fqQyT                 Filter for strings which evaluate to the input
 h                      Take the first success, which is the shortest due to
                        the order the strings were generated.
+                 \#    Add a '#' and output

CJam, 58

ri:M;'#0_]]{_{M&}#_)!}{;{~[2,+1$f+"@=+"\]z\f+\af.+~}%}w=0=

Brute Force, mit ein wenig Inspiration von Neils Antwort. Probieren Sie es online aus

Effiziente Version, 107

ri0"#"a{_{:B\:A={'=A0j+}{A(B={'+B0j+}{AB>{BAB-j_N={'@\+}|}N?}?}?}{;_(0j'+\+a\,1>_W%.{j}Na-'@\f++{,}$0=}?}2j

Probieren Sie es online aus

Dies verwendet dynamische Programmierung.

Haskell , 89 86 Bytes

BEARBEITEN:

• -3 Bytes: Das Zippen war kürzer als das Indizieren.

Eine weitere Brute-Force-Lösung, die sich von Neils Antwort inspirieren ließ. (Obwohl es eher wie Isaacgs Pyth funktionierte, bevor das Golfen das einführte l.)

f n=[s|(a,_,s)<-l,a==n]!!0
l=(0,0,"#"):[(a+c,a,d:s)|(a,b,s)<-l,(c,d)<-zip[0,1,b]"=+@"]

Probieren Sie es online aus!

• f ist die Hauptfunktion, die eine Ganzzahl verwendet und eine Zeichenfolge zurückgibt.
• list eine unendliche Liste von Tupeln (a,b,s), kürzeste Darstellungen szuerst, zusammen mit ihrem Wert aund dem Wert bder Darstellung, wobei das erste Zeichen entfernt wird. (Wie andere ebenfalls bemerkt / bemerkt haben, ist es harmlos, letzteres als 0 für zu behandeln #.)
• Die Elemente von landeren als dem ersten werden rekursiv mit einem Listenverständnis erzeugt. dist das Zeichen, dem vorangestellt werden soll s, um eine neue Darstellung in der Liste zu generieren, und 'c' ist das entsprechende Inkrement zu a.