Flavour-Text

Die stapelbasierte esolang- Unterlast weist einige interessante Bindungen zur funktionalen Programmierung auf. Eine davon ist die Behandlung des numerischen Datentyps - wie beim Lambda-Kalkül stellen Sie die natürliche Zahl N durch eine Funktion dar, die eine Aktion N-mal ausführt.

Zur Vereinfachung betrachten wir nur die folgende Untermenge von Unterlastbefehlen:

• : - Dieser Befehl dupliziert das oberste Element auf dem Stapel.
• * - Dieser Befehl verknüpft die beiden obersten Elemente auf dem Stapel zu einem einzelnen Element.

Wir definieren eine Unterlastungszahl N als eine Zeichenfolge von :und *die, wenn sie ausgeführt wird, das oberste Element auf dem Stapel verbraucht und N Kopien dieses Elements erzeugt, die miteinander verkettet sind. Einige Beispiele:

• Es gibt keine Unterlastnummern 0, -1, 1/2, π.
• Die leere Zeichenfolge hat die Unterlastnummer 1, da der Stapel unberührt bleibt.
• :*ist die Unterlastzahl 2, da sie das oberste Element dupliziert und diese beiden Kopien dann zu einem einzigen Element zusammenfügt: (A):*= (A)(A)*= (AA).
• ::**ist die Unterlastzahl 3: (A)::**= (A)(A):**= (A)(AA)*= (AAA).
• :::*** ist die Unterlastzahl 4.
• :*:*ist auch die Unterlastzahl 4: (A):*:*= (AA):*= (AA)(AA)*= (AAAA).

Im Allgemeinen werden Sie feststellen, dass, wenn Mund Ndie Unterlastzahlen M und N sind, dann :N*die Zahl N + 1 ist und MNdie Zahl M × N ist.

Die Herausforderung

Ihre Aufgabe ist es, das kürzeste Programm (Eingabe über STDIN) oder die kürzeste Funktion (Eingabe über Argument) zu schreiben, die die kürzeste Darstellung der Unterlastzahl für ihre Eingabe als Zeichenfolge erzeugt. Das heißt, wenn die Eingabe eine positive natürliche Zahl N> 1 ist, müssen Sie eine Unterlastzahl N erzeugen, deren Länge in Zeichen kleiner oder gleich der jeder anderen Unterlastzahl N ist.

Beispiele für Ein- und Ausgänge: ("Input - OUTPUT.")

• 1 - .
• 2 - :*.
• 5 - ::*:**(2 × 2 + 1).
• 7 - ::*::***(2 × 3 + 1) oder :::**:**(3 × 2 + 1).
• 33 - ::*:*:*:*:**(2 × 2 × 2 × 2 × 2 + 1).
• 49 - ::*:*:*:*::***(16 × 3 + 1, Länge 14), aber nicht ::*::***::*::***(7 × 7, Länge 16).

Wenn es sich bei der Eingabe nicht um eine positive natürliche Zahl handelt, können Sie einen Fehler zurückgeben, undefiniertes Verhalten erzeugen oder die Eingabe sogar nicht beenden. Wir freuen uns über eine Erläuterung der Methode, mit der Sie die Antwort gefunden haben.

Es gelten die üblichen Lückenbeschränkungen: Keine zusätzlichen Eingaben, keine Webanfragen, Ausgabe- / Rückgabewerte müssen genau die Antwort sein und kein unendlicher Zufallsstrom von :und *usw.

GolfScript ( 61 60 55 54 53 Zeichen)

~:X'']({:A{.'.+'\*A{2$+}%~}%}*{,}${1\~X=}?{44/'*:'=}%

Dies ist weniger knifflig als meine frühere Version und verfolgt einen etwas anderen Ansatz, aber es ist immer noch rohe Gewalt. Wir wissen, dass dies ':'X*'*'X*+eine in Frage kommende Lösung ist. Wenn wir also alle bis zu dieser Länge gut ausbalancierten Zeichenfolgen erzeugen und die kürzeste auswählen, die zum richtigen Ergebnis führt, können wir sicher sein, eine zu finden.

# Evaluate input and store the target number in X
~:X
# Seed the generator with the empty string
'']
# X times...
({
    # Store the array of strings so far into A
    :A
    # Generate A' by mapping each element
    {
        # Dup: this leaves an untouched copy of the current string
        .
        # Wrap the duplicate in .+
        '.+'\*
        # For each element in A, generate that element suffixed with the current string
        A{2$+}%~
    }%
}*
# Order by length
{,}$
# Find the first element which evaluates to X
{1\~X=}?
# tr .+ :*
{44/'*:'=}%

Vielen Dank an Howard, von dessen Lösung ich ein paar 1-Zeichen-Tweaks gestohlen habe.

GolfScript ( 54 53 Zeichen)

Dies ist ein Ansatz, der im Geiste von Howard (Erstellen von Zeichenfolgen, die den richtigen Wert ergeben, und Auswählen der kürzesten statt der rohen Kraft durch Kandidatenzeichenfolgen, um diejenigen zu finden, die den richtigen Wert ergeben), der sich jedoch meiner Meinung nach ausreichend unterscheidet es gehört in eine separate antwort.

~.''':*':s@,{):x,2>{:^~$x^/~$+{s\*}x^%*}%{,}$0=}/]((=

Online-Demo nicht verfügbar, da eine fehlerhafte Version des Interpreters ausgeführt wird.

# Let <N> denote the string which evaluates to N
# We want to enter the main loop with three values on the stack: <0> <1> <2>
# However, we'll never use <0>, so we can actually replace that with any value at all.
# Getting the input from underneath 3 items would normally use two stack manipulations.
# Trick: let's use the input value for <0>! (This gives a further bonus later).
# NB We store the value of <2> in the variable s
~.''':*':s@
# for x=1 to input_value ...
,{):x
    # for ^=2 to x-1 ...
    ,2>{:^
        # Use negative stack offsets to index the stack from the start
        # I.e. -1$ gets the first item on the stack, which is <0>
        # -2$ gets the second item on the stack, which is <1>
        # In general, val~$ gets <val>
        ~$x^/~$+
        # We have the string <^><x / ^> on the stack.
        # Increment it (x % ^) times to get a candidate <x>.
        {s\*}x^%*
    }%
    # Select a shortest string.
    {,}$0=
}/
# Group the stack into one array and select the appropriate offset,
# reusing that hacky <0> substitute for the offset.
]((=

Python 2.7 - 87 84 92

u=lambda n:n>1and min([u(i)+u(n/i)for i in range(2,n)if n%i<1]+[':'+u(n-1)+'*'],key=len)or''

Erläuterung:
Dies ist eine ziemlich einfache Lösung. Es testet rekursiv alle möglichen Darstellungen von n als Produkt aus zwei Zahlen oder als :(n-1)*und findet dann die Lösung mit der minimalen Länge. range (2, n) ist notwendig, damit die Rekursion eine begrenzte Tiefe hat und n <2 den Basisfall ergibt.

Anmerkungen:
i und n / i sind die beiden Faktoren von n. Der ... und ... oder ... Ersatz für ... wenn ... sonst ... nicht funktioniert, weil '' als falsch ausgewertet wird. min von Saiten ergibt eine der kürzesten Saiten. Python 2.7 speichert 1 Zeichen mit / anstelle von //.

Bearbeiten: Der Basisfall wurde in den hinteren Bereich des Ausdrucks verschoben, sodass ich ... und ... oder ... verwenden und ein paar Leerzeichen rasieren kann.

Testfälle:

u(1)
''
u(5)
'::*:**'
u(49)
'::*:*:*:*::***'

GolfScript, 63 58 56 Zeichen

~n./\{:v~[':*'1$*v,,2>{v,\%!},{.v=v,@/v=+}/]{,}$0=]}*-2=

Der Code wird in STDIN eingegeben und gibt das Ergebnis aus.

Beispiele:

> 49
:::**:*:*:*:**

> 1234
::::*:*:*:**:*:*:**::**::***

Sie können Ihre eigenen Fälle online testen .

Brachylog 2 , 30 (möglicherweise 26) Bytes, Herausforderung nach den Sprachdaten

Hier ist eine Funktion, die mit der aktuellen Brachylog 2-Implementierung funktioniert (und eine Liste von Zeichencodes zurückgibt, da die aktuelle Implementierung einige Probleme mit der Zeichenfolgenbehandlung hat):

∧.l∧?{ḋp~c×ᵐ{-₁↰₁:[42,58]c↻}ᵐc}

Probieren Sie es online!

Die Sprache ist noch sehr neu. Hier ist eine 26-Byte- Version des Programms, die gemäß der Spezifikation funktionieren sollte, jedoch einige nicht implementierte Funktionen verwendet und daher noch nicht gültig ist, aber möglicherweise in Zukunft verfügbar sein wird (es ist auch noch weniger effizient):

{ḋp~c×ᵐ{-₁↰₁:"*:"c↻}ᵐc}ᶠlᵒh

Erläuterung

∧.l∧?{ḋp~c×ᵐ{-₁↰₁:[42,58]c↻}ᵐc}
∧.l∧?                            Evaluation hint: try shortest outputs first
     {                        }  Define an inner function
      ḋ                          Prime factor decomposition of the input
       p                         Find a permutation
        ~c                       Find an inverse concatenation (i.e. partition)
          ×ᵐ                     Take the product of each set inside the partition
      ḋp~c×ᵐ                     Find a decomposition into factors ≥ 2
            {              }ᵐ    For each of those factors:
             -₁                  Decrement it
               ↰₁                Call the inner function recursively
                 :[42,58]c       Append "*:" (as character codes)
                          ↻      Move the last element to the start
                             c   Append the results together

Die Grundidee ist ziemlich einfach: Wir wechseln zwischen der Zerlegung der Zahl in (1 oder mehr) Faktoren (nicht unbedingt Primfaktoren, aber Faktoren von 1 sind nicht zulässig) und dem Ausdrücken jeder dieser Faktoren als 1 + (eine Darstellung, die aus einem Rekursiv erhalten wird) Anruf). Dies ist garantiert, um alle möglichen Unterlastdarstellungen der Zahl zu durchsuchen (wir können eine Multiplikationsstufe "zweimal in Folge" anwenden, indem wir mehr als 2 Zahlen miteinander multiplizieren, und eine Inkrementierungsstufe zweimal in Folge, indem wir sie durch eine Multiplikationsstufe trennen, die multipliziert zusammen nur eine Nummer). Wir brauchen keinen expliziten Basisfall, da die Zerlegung von 1 in Primfaktoren eine leere Liste ergibt und wir sie daher mit einer Multiplikationsstufe konstruieren, die Nullzahlen miteinander multipliziert.

Das Programm ist ziemlich ineffizient, vor allem, weil der von mir gegebene Hinweis auf die Bewertungsreihenfolge (Generieren der kürzesten bis längsten Antworten in Bezug auf die Größe der endgültigen Ausgabe), während der "kürzeste" Teil der Frage gelöst wird, in Bezug auf nicht so großartig ist das Programm tatsächlich schnell fertig zu stellen (ein viel nützlicherer Hinweis wäre, "in jeder rekursiven Phase nur die kürzeste Antwort zu generieren", aber das braucht mehr Bytes ...). Darüber hinaus ḋp~c×ᵐkönnen mehrere multiplikative Partitionen generiert werden, wodurch das Programm eine Menge redundanter Arbeit leistet.

J - 81 Zeichen

Für die Nachwelt war dies das Beste, was ich in J tun konnte.

_2{::(0&(][,0{<@;"1@({~#(#~]-:"1<.)@(],.%)2}.i.@#)(/:#&>)@,':'<@,'*',~>@{:),~)&a:

Wir erstellen eine Liste der Ergebnisse, beginnend mit zwei leeren Zeichenfolgen (das ist das ,~und a:), die 0 (nie verwendet) und 1 darstellen, und iterieren dann ein Verb darüber (schleichende Verwendung von Hooks, Zügen und &), das an die kürzeste Darstellung der nächsten Zahl angehängt wird.

Das tatsächliche Verb, das wir iterieren, verwendet die Länge der Liste als Indikator für die Anzahl, mit der wir arbeiten. Zuerst zerlegen wir diese Zahl in Faktorenpaare ( #(#~]-:"1<.)@(],.%)2}.i.@#) und rufen jedes Paar durch Ziehen aus dem Array ( {~) ab. Wir wandeln jedes dieser Paare (es könnte 0 von ihnen geben, wenn die Zahl eine Primzahl ist) in einzelne Strings ( <@;"1) um.

Dann hängen wir an diese Liste den Eintrag für das vorherige Ergebnis in Klammern von :und *an und sortieren diese Liste nach Länge ( (/:#&>)). Schließlich nehmen wir das erste Ergebnis aus dieser Liste ( 0{) und hängen es an das Ende des Basisarrays ( [,) an. Wenn die Schleife iteriert ist, haben wir eine Liste mit einer Länge von 2 mehr als die Eingabe, beginnend mit 0. Wir müssen also den vorletzten String ( _2{::) zurückgeben.

   un =: _2{::(0&(][,0{<@;"1@({~#(#~]-:"1<.)@(],.%)2}.i.@#)(/:#&>)@,':'<@,'*',~>@{:),~)&a:
   un 49
::*:*:*:*::***
   un 1234
:*::*:*:*::*::***::*::*:****
   un 10010
:*::*:*::***::*:*:*:*:*:*:*::***
   2 * (1 + 3 * 2^2) * (1 + 3 * 2^7)
10010
   6!:2 'un 10010'   NB. time in seconds
19.5539

Jelly , 33 Bytes, Sprachnachstellung

ÆḌḊµ⁹÷Ñ;Ñð€
’ß”:;;”*W;ÇLÞḢµ“”>1$?

Probieren Sie es online!

Eine einfache Brute-Force-Lösung.

Erläuterung

Hauptprogramm

’ß”:;;”*W;ÇLÞḢµ“”>1$?
              µ  >1$?  If input is greater than 1, then:
’ß                       Run recursively on the input - 1
  ”:;                    Prepend a colon
     ;”*                 Append an asterisk
        W;               Cons to:
          Ç                the result of the helper, on {the original input}
           LÞ            Sort by length
             Ḣ           Take the first (i.e. shortest) result
               “”      Otherwise, return an empty string

Das Hauptprogramm verwendet die Hilfsfunktion, um alle möglichen Arten der Werterzeugung durch Multiplikation aufzulisten. Anschließend versucht es, den Wert durch Addition zu erzeugen, und gibt die kürzeste Möglichkeit zurück. Es behandelt auch den Basisfall (eine Eingabe von 1).

Hilfsfunktion

ÆḌḊµ⁹÷Ñ;Ñð€
ÆḌ µ     ð€            For all proper factors of the input
  Ḋ                    except the first (i.e. 1):
    ⁹÷                   Divide it into the input;
      Ñ                  Run the main program on it;
       ;                 Append the result of:
        Ñ                  the main program run on {the factor}

Die Hilfsfunktion versucht alle möglichen Methoden, um die Eingabe als Multiplikation von zwei Zahlen auszudrücken, und ruft das Hauptprogramm gegenseitig rekursiv auf, um die kürzesten Darstellungen zu erhalten.

GNU Prolog, 96 Bytes

v(N)-->{N#=1};{N#=A*B,A#<B,B#<N},v(A),v(B);{N#=M+1},":",v(M),"*".
s(N,S):-length(S,_),v(N,S,[]).

Die erste Zeile ist eine Grammatik, die die Unterlastauswertung implementiert und in umgekehrter Richtung funktioniert (tatsächlich funktioniert sie aufgrund der A#<BEinschränkung nicht ganz in Vorwärtsrichtung ; ändern Sie dies in A#<Nfür ein langsameres Programm, das in beide Richtungen funktioniert). Die zweite Zeile definiert das funktionsähnliche Prädikat s(das ist die Funktion, die als Lösung für dieses Programm implementiert wurde), das die kürzestmögliche Zeichenfolge findet, die als Eingabe ausgewertet wird (dies ist frustrierend wortreich für eine relativ einfache Aufgabe, aber das ist Prolog für dich…).

Das Programm sollte ziemlich selbsterklärend sein, da es sich mehr oder weniger um eine direkte Übersetzung der Spezifikation in eine Grammatik und dann in die Prolog-Syntax handelt. die Definition vsagt , dass N1 in eine leere Zeichenfolge ist, oder Nist , Ax B(mit Aweniger als Bweniger als N) , und die Schnur ist die Verkettung von v(A)und v(B)oder Nist , M+ 1 und die Saite wird :konkateniert mit v(M)konkateniert mit *. Die zweite Zeile ist etwas subtiler.length(S,_) bedeutet "S hat eine gewisse Länge", aber wenn Sie dies als erstes in der Zeile angeben, wird dies als Hinweis für die Prolog-Implementierung angesehen, dass zuerst die kürzesten Längen überprüft werden sollen (was bedeutet, dass wir die kürzestmögliche Länge für einen Rückgabewert erhalten). .