Drzewa Decode Factor


11

W przypadku pominięcia kodowania drzew czynników , oto definicja drzewa czynników:

  • Pusty ciąg to 1.
  • Łączenie oznacza mnożenie.
  • Liczba n ujęta w nawiasy (lub dowolne sparowane znaki) reprezentuje n- tą liczbę pierwszą, przy czym 2 oznacza pierwszą liczbę pierwszą.
    • Zauważ, że odbywa się to rekurencyjnie: n- ta liczba pierwsza jest drzewem czynników dla nw nawiasach.
  • Czynniki liczby należy uporządkować od najmniejszej do największej.

Na przykład, oto drzewa czynników dla 2 do 10:

()
(())
()()
((()))
()(())
(()())
()()()
(())(())
()((()))

To wyzwanie wykorzystuje podobny format; jednakże wyzwaniem jest odkodowanie tych struktur.

Przypadki testowe

Bezwstydnie skradzione zmieniło przeznaczenie z ostatniego wyzwania.

Oprócz 9 powyżej…

()()((()))((())) => 100
(()(()(()))) => 101
(()())(((())))(()(())) => 1001
(((((((()))))))) => 5381
(()())((((()))))(()()(())(())) => 32767
()()()()()()()()()()()()()()() => 32768

Zasady

  • Sparowane znaki na wejściu to twój wybór w nawiasach, nawiasach, nawiasach klamrowych lub nawiasach kątowych. Mogę zezwolić na inne formaty (np. Tagi XML), jeśli zostanie o to poproszony.
  • Powinieneś być w stanie obsłużyć Drzewa Faktorów dla dowolnej liczby od 2 do 2 15 lub 32768.
  • Ponieważ jest to , wygrywa najkrótsza odpowiedź w bajtach.

Odpowiedzi:


9

Wolfram Language (Mathematica) , 52 45 bajtów

ToExpression@*StringReplace[{"["->"Prime[1"}]

Wypróbuj online!

Wejście używa nawiasów.

Przekształca dane wejściowe w wyrażenie Mathematica, które oblicza wynik. Robimy to po prostu poprzez wymianę [z Prime[1. Działa to, ponieważ konkatenacja w Mathematica jest zwielokrotnieniem.


8

Prolog (SWI) , 134 128 127 124 bajtów

Ta odpowiedź jest częścią współpracy między mną a 0 '. Oboje nad tym pracowaliśmy razem, jedynym powodem, dla którego to publikuję, jest to, że wygrałem Rock, Paper, Scissors.

\Q-->{Q=1};"(",\N,")",\B,{findnsols(N,I,(between(2,inf,I),\+ (between(3,I,U),0=:=I mod(U-1))),L)->append(_,[Y],L),Q is Y*B}.

Wypróbuj online!

Wyjaśnienie

Ta odpowiedź jest doskonałym przykładem tego, co sprawia, że ​​gra w golfa w prologu jest przyjemnością.


Ta odpowiedź korzysta z potężnego systemu Prologs dla określonych gramatyk klauzulowych. Oto nasza gramatyka trochę niepolita.

head(1)-->[].
head(Q)-->"(",head(N),")",head(B),{prime(N,Y),Q is Y*B}.
isprime(I):- \+ (between(3,I,U),0 =:= I mod(U-1)).
prime(N,Y):-
  findnsols(N,I,(
    between(2,inf,I),
    isprime(I)
  ),L),
  append(_,[Y],L),!.

Pierwsza zasada budowy to:

head(1)-->[].

Mówi to Prologowi, że pusty ciąg odpowiada 1.

Nasza druga zasada budowy jest nieco bardziej złożona.

head(Q)-->"(",head(N),")",head(B),{prime(N,Y),Q is Y*B}.

To mówi nam, że każdy niepusty ciąg zawiera nawiasy wokół klauzuli z tymi samymi regułami, na prawo od klauzuli z tymi samymi regułami.

Mówi nam również, że wartość tej klauzuli ( Q) jest zgodna z regułą:

{prime(N,Y),Q is Y*B}

Podział tego Qjest iloczynem 2 liczb Yi B. Bjest tylko wartością klauzuli po lewej stronie i Yjest Nliczbą pierwszą, gdzie Njest wartość klauzuli w nawiasach.

Ta reguła obejmuje obie reguły tworzenia drzewa czynników

  • Łączenie się mnoży
  • Obudowa zajmuje n-tą liczbę pierwszą

Teraz definicje predykatów. W wersji bez golfa rozgrywane są dwa predykaty (w moim rzeczywistym kodzie przesłałem je do przodu). Dwa istotne tutaj predykaty isprime/1, które pasują do liczby pierwszej, i prime/2która, podana Ni Y, pasuje do iff, Yjest Nliczbą pierwszą. Najpierw mamy

isprime(I):- \+ (between(3,I,U),0 =:= I mod(U-1)).

To dzieło o dość standardowej definicji pierwotności, nalegamy, aby nie było liczby między 2 a I, w tym 2, ale nie Idzieli I.

Następny predykat jest również dość prosty

prime(N,Y):-
  findnsols(N,I,(
    between(2,inf,I),
    isprime(I)
  ),L),
  append(_,[Y],L),!.

Używamy, findnsolsaby znaleźć pierwsze Nliczby, które są pierwsze, a następnie zwracamy ostatnią. Sztuczka polega na tym, że chociaż findnsolsnie ma gwarancji znalezienia najmniejszych N liczb pierwszych, ze względu na sposób, w jaki obsługuje SWI between, zawsze znajdzie mniejsze liczby pierwsze. Oznacza to jednak, że musimy ciąć, aby zapobiec znalezieniu większej liczby pierwszych.


Golfa

Możemy dwukrotnie podać przyczynę w naszym kodzie. Ponieważ isprimejest używany tylko wtedy, gdy jego definicja może zostać przeniesiona do wewnątrz prime. Kolejnym krokiem jest przejście primebezpośrednio do DCG, ale ponieważ używamy wycięcia, primeaby zapobiec findnsolstworzeniu zbyt wielu liczb pierwszych, mamy trochę problemu. Cięcie tnie cały DCG zamiast tylko tego, czego chcemy. Po trochę kopania dokumentacji odkryliśmy, że once/1można go użyć do wycięcia tylko tej części, ale nie całego DCG. Jednak więcej kopania dokumentacji ujawniło, że ->operator może być również wykorzystany do wykonania podobnego zadania. ->Operator jest grubsza odpowiada ,!,więc przenieśliśmy naszą cięcie na drugiej stronie append/3i zastąpił go ->.

W SWI-Prolog predykaty (i reguły) można podawać operatorom jako nazwy, co pozwala nam upuścić normalnie wymagane nawiasy. W ten sposób możemy zaoszczędzić 6 bajtów, wywołując regułę \.



1

JavaScript (ES6), 98 bajtów

Zainspirowany pythonową odpowiedzią notjagana . Zmienia wyrażenie wejściowe w ogromny i brzydki łańcuch wykonywalny.

s=>eval(s.split`)(`.join`)*(`.split`(`.join`(g=(n,k)=>(C=d=>n%--d?C(d):k-=d<2)(++n)?g(n,k):n)(1,`)

Scalenie funkcji Ci gw jeden może zaoszczędzić niektóre bajty, ale wymagałoby to jeszcze większej rekurencji.

Przypadki testowe

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.