11
\$\begingroup\$

In case you missed Encode Factor Trees, here is the definition of a Factor Tree:

  • The empty string is 1.
  • Concatenation represents multiplication.
  • A number n enclosed in parentheses (or any paired characters) represents the nth prime number, with 2 being the first prime number.
    • Note that this is done recursively: the nth prime is the factor tree for n in parentheses.
  • The factors of a number should be ordered from smallest to largest.

For example, here are the factor trees for 2 through 10:

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

This challenge uses a similar format; however, this challenge is to decode these structures.

Test Cases

Shamelessly stolen repurposed from the last challenge.

In addition to the 9 above…

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

Rules

  • The paired characters in the input are your choice of parentheses, brackets, braces, or angle brackets. I may allow other formats (e.g. XML tags) if asked.
  • You should be able to handle Factor Trees for any number from 2 to 215 or 32768.
  • Since this is , the shortest answer in bytes wins.
\$\endgroup\$
9
\$\begingroup\$

Wolfram Language (Mathematica), 52 45 bytes

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

Try it online!

Input uses brackets.

Transforms the input into a Mathematica expression that computes the result. We do this simply by replacing [ with Prime[1. This works because concatenation is multiplication in Mathematica.

\$\endgroup\$
8
\$\begingroup\$

Prolog (SWI), 134 128 127 124 bytes

This answer is part of a collaboration between myself and 0'. We both worked on this together, the only reason I'm posting it is because I won 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}.

Try it online!

Explanation

This answer is a perfect exemplar of what makes golfing in prolog fun.


This answer uses Prologs powerful system for definite clause grammars. Here is our grammar ungolfed a bit.

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

The first construction rule is:

head(1)-->[].

This tells Prolog that the empty string corresponds to 1.

Our second rule of construction is a tiny bit more complex.

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

This tells us that any non empty string contains parentheses around a clause with these same rules, to the right of a clause with these same rules.

It also tells us that the value of this clause (Q) follows the rule:

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

Breaking this down, Q is the product of 2 numbers Y and B. B is just the value of the clause to the left and Y is the Nth prime where N is the value of the clause inside the parentheses.

This rule covers both of the formation rules of the factor tree

  • Concatenation multiplies
  • Enclosure takes the nth prime

Now for the predicate definitions. In the ungolfed version there are two predicates at play (in my actual code I've forward chained the predicates away). The two relevant predicates here are isprime/1, which matches a prime number, and prime/2, which, given N and Y, matches iff Y is the Nth prime. First we have

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

This works of a pretty standard definition of primality, we insist that there is no number between 2 and I, including 2 but not I that divides I.

The next predicate is also pretty simple

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

We use findnsols to find the first N numbers that are prime, we then return the last one. The trick here is that while findnsols is not guaranteed to find the smallest N primes, because of the way SWI handles between it will always find smaller primes sooner. This however means we have to cut to prevent it from finding more primes.


The golfs

We can forward reason in our code twice. Since isprime is only used once its definition can be moved inside of prime. The next one is to move prime directly inside of the DCG, however since we use a cut in prime to prevent findnsols from producing too many primes we have a bit of an issue. The cut, cuts the entire DCG instead of just the bit we want. After a bit of documentation digging we found that once/1 could be used to cut just this portion but not the entire DCG. However more documentation digging revealed that the -> operator could also be used to perform a similar task. The -> operator is roughly equivalent to ,!, so we moved our cut to the other side of append/3 and replaced it with ->.

In SWI-Prolog predicates (and rules) can be give operators as names which allows us to drop the parentheses normally required. Thereby we can save 6 bytes by calling the rule \.

\$\endgroup\$
2
\$\begingroup\$

Python 3, 125 110 bytes

lambda s:eval(s.replace("]","1]*").replace("[","p[1*")+"1")
p=2,
k=P=1
while k<1e4:
 if P%k:p+=k,
 P*=k*k;k+=1

Try it online!

Uses xnor's implementation of the Wilson Theorem method to generate primes. Substitutes () with [].

\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 98 bytes

Inspired by notjagan's Python answer. Turns the input expression into a huge and ugly executable string.

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

Merging the C and g functions into a single one may save some bytes, but it would require even more recursion.

Test cases

let f =

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

;[
  "()",                             // 2
  "(())",                           // 3
  "()()",                           // 4
  "((()))",                         // 5
  "()(())",                         // 6
  "(()())",                         // 7
  "()()()",                         // 8
  "(())(())",                       // 9
  "()((()))",                       // 10
  "()()((()))((()))",               // 100
  "(()(()(())))",                   // 101
  "(()())(((())))(()(()))",         // 1001
  "(((((((())))))))",               // 5381
  "(()())((((()))))(()()(())(()))", // 32767
  "()()()()()()()()()()()()()()()"  // 32768
]
.forEach(s => console.log(s, '-->', f(s)))

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.