Tekst aromatyzujący

Stos oparte esolang niedoci¿eniem ma jakieś ciekawe powiązania programowania funkcjonalnego. Jednym z nich jest traktowanie liczbowego typu danych - podobnie jak rachunek lambda, reprezentujesz liczbę naturalną N za pomocą funkcji, która wykonuje akcję N razy.

Aby uprościć sprawę, rozważymy tylko następujący podzbiór poleceń niedociążenia:

• : - To polecenie powiela najwyższy element na stosie.
• * - To polecenie łączy dwa górne elementy stosu w jeden element.

Określamy niedociążenia liczbowy N jako łańcuch :i *która, gdy jest wykonywany, zajmują pozycję górną na stosie, i wytwarzania N kopii tego elementu sklejone. Kilka przykładów:

• Nie ma cyfr niedociążenia 0, -1, 1/2, π.
• Pusty ciąg jest liczbą niedociążoną 1, ponieważ pozostawia stos nietknięty.
• :*jest liczbą niedociążoną 2, ponieważ kopiuje najwyższy element, a następnie łączy te dwie kopie razem w jeden element: (A):*= (A)(A)*= (AA).
• ::**jest liczbą niedociążenia 3: (A)::**= (A)(A):**= (A)(AA)*= (AAA).
• :::*** jest liczbą niedociążenia 4.
• :*:*jest również liczbą niedociążenia 4: (A):*:*= (AA):*= (AA)(AA)*= (AAAA).

Ogólnie rzecz biorąc, przekonasz się, że jeśli Mi Nsą liczbami niedociążenia M i N, to :N*jest liczbą N + 1 i MNjest liczbą M × N.

Wyzwanie

Twoim zadaniem jest napisanie najkrótszego programu (przyjmującego dane wejściowe na STDIN) lub funkcji (przyjmującego dane wejściowe za pomocą argumentu), który tworzy najkrótszą reprezentację liczby niedociążenia dla jej danych wejściowych w postaci łańcucha. To znaczy, jeśli wejściowa liczba jest dodatnią liczbą naturalną N> 1, musisz utworzyć liczbę niedociążenia N, której długość w znakach jest mniejsza lub równa długości każdej innej liczby niedociążenia N.

Przykładowe wejścia i wyjścia: („Input - OUTPUT.”)

• 1 - .
• 2 - :*.
• 5 - ::*:**(2 × 2 + 1).
• 7 - ::*::***(2 × 3 + 1) lub :::**:**(3 × 2 + 1).
• 33 - ::*:*:*:*:**(2 × 2 × 2 × 2 × 2 + 1).
• 49 - ::*:*:*:*::***(16 × 3 + 1, długość 14), ale nie ::*::***::*::***(7 × 7, długość 16).

Jeśli dane wejściowe nie są dodatnią liczbą naturalną, możesz zwrócić błąd, wywołać niezdefiniowane zachowanie, a nawet nie zakończyć działania. Docenione zostanie wyjaśnienie metody przesłania odpowiedzi.

Standardowe ograniczenia loophole zastosowania: brak dodatkowego nakładu, żadnych żądań internetowych, wartość wyjściowa / powrót musi być dokładnie taka odpowiedź i nie nieskończony strumień losowych :i *itp

GolfScript ( 61 60 55 54 53 znaków)

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

Jest to mniej skomplikowane niż moja wcześniejsza wersja i ma nieco inne podejście, ale wciąż jest brutalne. Wiemy, że ':'X*'*'X*+jest to rozwiązanie kandydujące, więc jeśli wygenerujemy wszystkie dobrze zbalansowane łańcuchy do tej długości i weźmiemy najkrótszy, który ocenia właściwą rzecz, możemy być pewni, że go znajdziemy.

# 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/'*:'=}%

Dzięki Howardowi, z którego rozwiązania ukradłem kilka drobnych usprawnień.

GolfScript ( 54 53 znaki)

Jest to podejście zgodne z duchem Howarda (budowanie łańcuchów, które oceniają na prawidłową wartość i wybieranie najkrótszej, a nie brutalnej siły poprzez łańcuchy kandydatów, aby znaleźć te, które oceniają na prawidłową wartość), ale jest wystarczająco inne, niż myślę należy do osobnej odpowiedzi.

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

Demo online nie jest dostępne, ponieważ działa błędna wersja interpretera.

# 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''

Objaśnienie:
Jest to dość proste rozwiązanie. Rekurencyjnie testuje wszystkie możliwe reprezentacje n jako iloczyn dwóch liczb lub jako :(n-1)*, a następnie znajduje rozwiązanie minimalnej długości. zakres (2, n) jest konieczny, aby rekursja ograniczała głębokość, a n <2 daje przypadek podstawowy.

Uwagi:
i oraz n / i to dwa czynniki n. ... i ... lub ... zamiennik ... jeśli ... inaczej ... nie działa, ponieważ '' zwraca wartość false. min ciągów daje jeden z najkrótszych ciągów. Python 2.7 zapisuje 1 znak przy użyciu / zamiast //.

Edycja: przeniesiono podstawową skrzynkę na tył wyrażenia, pozwalając mi użyć ... i ... lub ... i ogolić kilka miejsc.

Przypadki testowe:

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

GolfScript, 63 58 56 znaków

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

Kod pobiera dane wejściowe STDIN i drukuje wynik.

Przykłady:

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

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

Możesz przetestować własne przypadki online .

Brachylog 2 , 30 (może w końcu 26) bajtów, wyzwanie dla postdate języka

Oto funkcja, która działa z bieżącą implementacją Brachylog 2 (i zwraca listę kodów znaków, ponieważ obecna implementacja ma pewne problemy z obsługą łańcuchów):

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

Wypróbuj online!

Język jest wciąż bardzo nowy. Oto 26-bajtowa wersja programu, która powinna działać zgodnie ze specyfikacją, ale wykorzystuje pewne niezaimplementowane funkcje, a zatem nie jest jeszcze ważna, ale może będzie w przyszłości (jest nawet jeszcze mniej wydajna):

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

Wyjaśnienie

∧.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

Podstawowa idea jest dość prosta: na przemian rozkładamy liczbę na (1 lub więcej) czynników (niekoniecznie czynniki pierwsze, ale czynniki 1 nie są dozwolone) i wyrażamy każdy z nich jako 1 + (reprezentacja uzyskana z rekurencyjnego połączenie). Gwarantuje to przeszukanie wszystkich możliwych reprezentacji niedociążenia liczby (możemy zastosować etap mnożenia „dwa razy z rzędu” przez pomnożenie razem więcej niż 2 liczb oraz etap przyrostu dwa razy z rzędu poprzez oddzielenie ich od etapu mnożenia, który zwielokrotnia razem tylko jedna liczba). Nie potrzebujemy wyraźnego przypadku podstawowego, ponieważ rozkład 1 na czynniki pierwsze daje nam pustą listę, a zatem tworzymy ją z etapem mnożenia, który zwielokrotnia liczby zerowe razem.

Program jest dość nieefektywny, szczególnie dlatego, że podałem wskazówkę dotyczącą kolejności oceny (generuję odpowiedzi od najkrótszych do najdłuższych pod względem wielkości ostatecznego wyniku), a jednocześnie rozwiązując „najkrótszą” część pytania, nie jest tak świetne pod względem faktycznie sprawiając, że program szybko się skompletuje (o wiele bardziej użyteczną wskazówką byłoby „generowanie tylko najkrótszej odpowiedzi na każdym etapie rekurencyjnym”, ale to zajmuje więcej bajtów…). Dodatkowo ḋp~c×ᵐmoże generować multiplikatywne partycje kilka razy, co powoduje, że program wykonuje wiele zbędnych czynności.

J - 81 znaków

Dla potomności było to najlepsze, co mogłem zrobić w J.

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

Tworzymy listę wyników, zaczynając od dwóch pustych ciągów (to jest ,~i a:) reprezentujących 0 (nigdy nie używanych) i 1, a następnie iterujemy nad nimi czasownik (podstępne użycie haków, pociągów i &), który dołącza najkrótszą reprezentację następnego numeru.

Rzeczywisty czasownik, który iterujemy, wykorzystuje długość listy jako wskaźnik tego, na jakiej liczbie operujemy. Najpierw dzielimy tę liczbę na pary czynników ( #(#~]-:"1<.)@(],.%)2}.i.@#) i pobieramy każdą parę, wyciągając z tablicy ( {~). Zamieniamy każdą z tych par (może być 0, jeśli liczba jest liczbą pierwszą) na pojedyncze ciągi ( <@;"1).

Następnie dołączyć do tej listy wpis dla poprzedniego wyniku nawiasie :i *oraz sortowania tej listy długości ( (/:#&>)). Na koniec bierzemy pierwszy wynik z tej listy ( 0{) i dołączamy go na końcu tablicy podstawowej ( [,). Po zakończeniu iteracji pętli mamy listę o długości 2 większą niż dane wejściowe, zaczynając od 0. Więc to, co musimy zwrócić, to ciąg znaków „od końca do ostatniego” ( _2{::).

   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

Galaretka , 33 bajty, wyzwanie dla postdate języka

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

Wypróbuj online!

Proste rozwiązanie brutalnej siły.

Wyjaśnienie

Główny program

’ß”:;;”*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

Program główny używa funkcji pomocnika do wyliczenia wszystkich możliwych sposobów generowania wartości przez mnożenie, a następnie próbuje wygenerować wartość przez dodanie i zwraca najkrótszą możliwość. Obsługuje również skrzynkę podstawową (wejście 1).

Funkcja pomocnika

ÆḌḊµ⁹÷Ñ;Ñð€
ÆḌ µ     ð€            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}

Funkcja pomocnika próbuje wszystkich możliwych metod wyrażania danych wejściowych jako mnożenia dwóch liczb i wzajemnie rekurencyjnie wywołuje program główny w celu uzyskania ich najkrótszych reprezentacji.

GNU Prolog, 96 bajtów

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,[]).

Pierwszy wiersz to gramatyka, która implementuje ocenę niedociążenia i działa w odwrotnym kierunku (w rzeczywistości nie działa całkiem do przodu z powodu A#<Bograniczenia; zmień to A#<Nna wolniejszy program, który działa w obie strony). Drugi wiersz definiuje predykat podobny do funkcji s(która jest funkcją zaimplementowaną jako rozwiązanie tego programu), która znajduje najkrótszy możliwy ciąg, który ocenia na liczbę podaną jako dane wejściowe (jest to frustrująco szczegółowe dla tego, co jest stosunkowo prostym zadaniem, ale to dla ciebie Prolog…).

Program powinien być dość zrozumiały, biorąc pod uwagę, że jest to mniej więcej bezpośrednie tłumaczenie specyfikacji na gramatykę, a następnie na składnię Prologu; definicja vmówi, że Njest to 1 w pustym łańcuchu lub Njest A× B(z Amniej niż Bmniej niż N), a łańcuch jest konkatenacją v(A)i v(B), lub Njest M+ 1, a łańcuch jest :konkatenowany z v(M)konkatenacją z *. Druga linia jest nieco subtelniejsza;length(S,_) oznacza „S ma pewną długość”, ale określenie tego jako pierwszej rzeczy w wierszu działa jako wskazówka dla implementacji Prologa, że ​​powinien najpierw sprawdzić najmniejsze długości (co oznacza, że ​​otrzymamy możliwie najkrótszą długość dla wartości zwracanej) .