tło

Wiele ezoterycznych języków programowania nie ma liczb wbudowanych w literały, więc musisz je obliczyć w czasie wykonywania; w wielu przypadkach reprezentacja liczb może być dość interesująca. Mieliśmy już wyzwanie dotyczące reprezentowania liczb w przypadku niedociążenia. Wyzwanie polega na reprezentowaniu liczb w Modular SNUSP . (Pamiętaj, że nie musisz uczyć się SNUSP, aby ukończyć to wyzwanie - wszystkie potrzebne informacje znajdują się w specyfikacji - ale tło może być dla ciebie interesujące).

Zadanie

Dla celów tego wyzwania, szereg Modular SNUSP to ciąg utworzony z bohaterów @, +oraz =z tym, że ostatni znak to #, że charakter i przedostatni musi być +albo =(nie może być @). Na przykład, ważne numery zawierać @+#, ==#oraz @@+@=#; Przykłady obejmują liczby nieważnych +=, @@#i +?+#.

Wartość modułowego numeru SNUSP oblicza się rekurencyjnie w następujący sposób:

• # ma wartość 0 (to jest przypadek podstawowy).
• Jeśli liczba ma postać =x, dla dowolnego łańcucha xjej wartość jest równa wartości x.
• Jeśli liczba ma postać +x, dla dowolnego łańcucha xjej wartość jest równa wartości xplus 1.
• Jeśli liczba ma postać @cx, dla dowolnego pojedynczego znaku ci dowolnego łańcucha x, jego wartość jest równa wartościx plus wartość cx.

Aby sprostać temu wyzwaniu, musisz napisać program, który przyjmuje nieujemną liczbę całkowitą jako dane wejściowe i generuje ciąg, który jest najkrótszym możliwym Modularnym numerem SNUSP o wartości równej wartości wejściowej.

Wyjaśnienia

• Jest całkiem możliwe, że będzie więcej niż jeden ciąg o tej samej wartości, a w szczególności dla niektórych liczb całkowitych będzie remis dla najkrótszego Modularnego numeru SNUSP o tej wartości. W takim przypadku możesz wypisać dowolną liczbę związaną z remisem.
• Nie ma ograniczeń w algorytmie używanym do znalezienia liczby; na przykład brutalne wymuszanie ciągów i ich ocenianie jest taktyką prawną, ale robi coś mądrzejszego, aby zmniejszyć przestrzeń wyszukiwania.
• Jak zwykle w PPCG, twoje zgłoszenie może być pełnym programem lub funkcją (wybierz ten, który jest bardziej zwięzły w twoim języku).
• Nie jest to problem z obsługą formatów wejściowych i wyjściowych, więc możesz użyć wszelkich rozsądnych środków, aby wprowadzić nieujemną liczbę całkowitą i wyprowadzić ciąg. Istnieje pełny przewodnik na temat meta , ale najczęściej stosowanymi metodami prawnymi są argumenty / powroty funkcji, argumenty wiersza poleceń oraz standardowe wejście / standardowe wyjście.

Przypadki testowe

Oto najkrótsze przedstawienia pierwszych kilku liczb:

• 0 :#
• 1 :+#
• 2) :++#
• 3 :+++# lub@++#
• 4 : ++++#lub +@++#lub@=++#
• 5 : @+++#lub@@++#
• 6 : +@+++#lub +@@++#lub @=+++#lub @=@++#lub@@=++#
• 7 : @++++#lub@+@++#
• 8 : @@+++#lub@@@++#
• 9 : +@@+++#lub +@@@++#lub @+++++#lub @++@++#lub @+@=++#lub @@=+++#lub@@=@++#
• 10 : @=@+++#lub @=@@++#lub @@@=++#( jest to dość ważny przypadek testowy do sprawdzenia , ponieważ wszystkie możliwe odpowiedzi obejmują =)
• 11 : @+@+++#lub @+@@++#lub @@++++#lub@@+@++#
• 12 : +@+@+++#lub +@+@@++#lub +@@++++#lub +@@+@++#lub @=+@+++#lub @=+@@++#lub @=@=+++#lub @=@=@++#lub @=@@=++#lub @@=++++#lub @@=+@++#lub@@=@=++#
• 13 : @@@+++#lub@@@@++#
• 14 : +@@@+++#lub +@@@@++#lub @=@++++#lub @=@+@++#lub @@+++++#lub @@++@++#lub@@+@=++#
• 15 : @+@++++#lub @+@+@++#lub @@=@+++#lub @@=@@++#lub @@@=+++#lub@@@=@++#

W większej testu na wyjściu z wejściem 40 powinny być @@@=@@+++#, @@@=@@@++#, @@@@=@+++#lub @@@@=@@++#.

Warunek zwycięstwa

Jako wyzwanie dla golfa , zwycięzca jest najkrótszym wejściem, mierzonym w bajtach.

Oracle SQL 11.2, 341 262 bajtów

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;

Stara wersja

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 liczba do reprezentowania w modułowym SNUSP

Bez golfa:

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;

Najpierw utwórz widok z 3 liniami, po jednym dla każdego symbolu używanego do przedstawienia liczb, minus #, który jest używany tylko na końcu ciągu:

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

Następnie widok rekurencyjny n generuje każdy możliwy ciąg z tymi 3 symbolami, łączy je do # i ocenia je.

Parametry to:

s: Modularna reprezentacja SNUSP ocenianej liczby
v: wartość dziesiętna s obliczona na podstawie poprzedniej iteracji
p: v obliczona na podstawie iteracji i-2
c: następny symbol do połączenia z s
i: tylko długość s, tylko potrzebne do pozbycia się dwóch LENGTH () do gry w golfa

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

Jeśli ostatnim symbolem jest +, to dodaj 1
Jeśli to @, dodaj wartość iteracji i-2 W
przeciwnym razie symbolem będzie # lub =. v jest inicjowane z 0 w części początkowej widoku rekurencyjnego, więc nowe v jest równe poprzedniemu v w obu przypadkach.

WHERE i<11

Każdy ciąg znaków z 3 symbolami jest obliczany, ta część zapewnia, że ​​żądanie nie zostanie uruchomione aż do wielkiego kryzysu.

CYCLE s SET y TO 1 DEFAULT 0

Ponieważ nie ma reguły dotyczącej konstrukcji ciągów, z pewnością powstaną duplikaty. Będąc w widoku rekurencyjnym Oracle interpretuje te duplikaty jako cykle i rzuca błąd, jeśli sprawa nie jest wyraźnie załatwiona.

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

Zwraca pierwszą reprezentację modułową SNUSP, która ocenia na liczbę dziesiętną wprowadzoną jako parametr: 1

W moich testach ta pierwsza linia jest zawsze jedną z najkrótszych reprezentacji.

W przypadku gdyby twoja baza danych nie działała w ten sam sposób, ostatnia klauzula powinna zostać zastąpiona przez

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

JavaScript (ES6), 100 bajtów

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")

Prosty algorytm wyszukiwania brute-force-first.

Pyth, 41 bajtów

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

Zestaw testowy

Jak to działa:

Istnieją dwie części. Funkcja rekurencyjna, która oblicza wartość wyrażenia SNUSP bez trailing #, oraz procedura brutalnej siły.

Ewaluacja:

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

Brutalna siła:

+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=

Brutalna siła, trochę inspirowana odpowiedzią Neila. Wypróbuj online

Wydajna wersja, 107

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

Wypróbuj online

Wykorzystuje to programowanie dynamiczne.

Haskell , 89 86 bajtów

EDYTOWAĆ:

• -3 bajty: zipowanie było krótsze niż indeksowanie.

Kolejne brutalne rozwiązanie, które zakończyło się dużą inspiracją z odpowiedzi Neila. (Chociaż działało to bardziej jak Pyth Isaacga przed wprowadzeniem gry w golfa 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]"=+@"]

Wypróbuj online!

• f jest główną funkcją, która przyjmuje liczbę całkowitą i zwraca ciąg znaków.
• ljest nieskończoną listą krotek (a,b,s), snajpierw najkrótszymi reprezentacjami , wraz z ich wartością ai wartością breprezentacji z usuniętym pierwszym znakiem. (jak zauważyli / zauważyli inni, nieszkodliwe jest traktowanie tego ostatniego jako 0 #).
• Elementy linne niż pierwszy są generowane rekurencyjnie ze zrozumieniem listy. dto znak, który należy poprzedzić, aby swygenerować nową reprezentację na liście, a „c” oznacza odpowiedni przyrost do a.