Árboles de factor de decodificación

11

En caso de que se haya perdido los árboles de factores de codificación , aquí está la definición de un árbol de factores:

  • La cadena vacía es 1.
  • La concatenación representa la multiplicación.
  • Un número n entre paréntesis (o cualquier caracteres emparejados) representa el n º número primo, con 2 siendo el primer número primo.
    • Tenga en cuenta que esto se hace de forma recursiva: el n º es el primer árbol de factores n entre paréntesis.
  • Los factores de un número deben ordenarse de menor a mayor.

Por ejemplo, aquí están los árboles de factores para 2 a 10:

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

Este desafío usa un formato similar; Sin embargo, este desafío es decodificar estas estructuras.

Casos de prueba

Robado descaradamente reutilizado del último desafío.

Además de los 9 anteriores ...

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

Reglas

  • Los caracteres emparejados en la entrada son paréntesis, corchetes, llaves o corchetes de su elección. Puedo permitir otros formatos (por ejemplo, etiquetas XML) si me lo piden.
  • Debería poder manejar Factor Trees para cualquier número del 2 al 2 15 o 32768.
  • Como se trata de , gana la respuesta más corta en bytes.
Nissa
fuente

Respuestas:

9

Wolfram Language (Mathematica) , 52 45 bytes

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

Pruébalo en línea!

La entrada usa corchetes.

Transforma la entrada en una expresión de Mathematica que calcula el resultado. Hacemos esto simplemente reemplazando [con Prime[1. Esto funciona porque la concatenación es multiplicación en Mathematica.

Martin Ender
fuente
8

Prolog (SWI) , 134 128 127 124 bytes

Esta respuesta es parte de una colaboración entre mí y 0 '. Los dos trabajamos juntos en esto, la única razón por la que lo estoy publicando es porque gané Piedra, Papel, Tijeras.

\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}.

Pruébalo en línea!

Explicación

Esta respuesta es un ejemplo perfecto de lo que hace que jugar al golf en prolog sea divertido.


Esta respuesta utiliza el poderoso sistema Prologs para las gramáticas de cláusulas definidas. Aquí está nuestra gramática ungolfed un poco.

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),!.

La primera regla de construcción es:

head(1)-->[].

Esto le dice a Prolog que la cadena vacía corresponde a 1.

Nuestra segunda regla de construcción es un poco más compleja.

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

Esto nos dice que cualquier cadena no vacía contiene paréntesis alrededor de una cláusula con estas mismas reglas, a la derecha de una cláusula con estas mismas reglas.

También nos dice que el valor de esta cláusula ( Q) sigue la regla:

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

Desglosando esto, Qes el producto de 2 números Yy B. Bes solo el valor de la cláusula a la izquierda y Yes el Nprimer lugar donde Nestá el valor de la cláusula dentro de los paréntesis.

Esta regla cubre las dos reglas de formación del árbol de factores.

  • La concatenación se multiplica
  • El recinto toma la enésima prima

Ahora para las definiciones de predicados. En la versión sin golf hay dos predicados en juego (en mi código real he encadenado los predicados). Los dos predicados relevantes aquí son isprime/1, que coincide con un número primo y prime/2, que, dado Ny Y, coincide con iff Yes el Nnúmero primo. Primero tenemos

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

Esto funciona con una definición bastante estándar de primalidad, insistimos en que no hay un número entre 2 e I, incluido 2, pero no Ieso divide I.

El siguiente predicado también es bastante simple

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

Usamos findnsolspara encontrar los primeros Nnúmeros que son primos, luego devolvemos el último. El truco aquí es que, si bien findnsolsno se garantiza que encuentre los primos más pequeños N , debido a la forma en que SWI maneja between, siempre encontrará primos más pequeños antes. Sin embargo, esto significa que tenemos que cortar para evitar que encuentre más números primos.


Los campos de golf

Podemos reenviar la razón en nuestro código dos veces. Dado isprimeque solo se usa una vez, su definición se puede mover dentro de prime. El siguiente es movernos primedirectamente dentro del DCG, sin embargo, dado que usamos un corte primepara evitar findnsolsproducir demasiados números primos, tenemos un pequeño problema. El corte, corta todo el DCG en lugar de solo el bit que queremos. Después de investigar un poco la documentación, descubrimos que once/1podría usarse para cortar solo esta parte, pero no todo el DCG. Sin embargo, una mayor excavación de documentación reveló que el ->operador también podría usarse para realizar una tarea similar. El ->operador es más o menos equivalente a ,!,lo que movimos nuestro corte al otro lado append/3y lo reemplazamos con ->.

En SWI-Prolog, los predicados (y las reglas) se pueden dar a los operadores como nombres, lo que nos permite eliminar los paréntesis normalmente requeridos. De este modo podemos ahorrar 6 bytes llamando a la regla \.

Ad Hoc Garf Hunter
fuente
1

JavaScript (ES6), 98 bytes

Inspirado en la respuesta de Python de notjagan . Convierte la expresión de entrada en una cadena ejecutable enorme y fea.

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,`)

Fusionar las funciones Cy gen una sola puede ahorrar algunos bytes, pero requeriría aún más recursividad.

Casos de prueba

Arnauld
fuente