Reconstruct a recursively prime-encoded integer

Question

Recursively prime-encoded integers

Consider \11681169775023850ドル = 2 \times 5 \times 5 \times 42239 \times 5530987843\$. This isn't a nice prime factorisation, as \42239ドル\$ and \5530987843ドル\$ make it difficult to store this factorisation in a small manner. Being primes, we can't then factorise them, but we can factorise \$p - 1\$, which is guaranteed to not be prime (ignoring \$p = 3\$). by doing this we get:

• \42239ドル \to 42238 = 2 \times 7 \times 7 \times 431\$
• \5530987843ドル \to 5530987842 = 2 \times 3 \times 17 \times 54225371\$

This helps, but \431ドル\$ and \54225371ドル\$ are still pesky, so we run the same procedure (prime factorising their decrement). Just to be safe, we'll also do it with \17ドル\$ so that we can only have single digit primes (\2,3,5,7ドル\$) in the final result. This eventually results in:

[2, 5, 5, [2, 7, 7, [2, 5, [2, 3, 7]]], [2, 3, [2, 2, 2, 2], [2, 5, [2, 2, 2, 5], [2, 2, 2, 2, 2, [2, 2, [2, 2, 2, 3, [2, 3, 7]]]]]]]

representing \11681169775023850ドル\$. This is a program that shows the steps of decomposition of the input, and this is a program which decomposes a given integer.

The representations for the integers from 2 to 25 are:

 2 [2]
 3 [3]
 4 [2, 2]
 5 [5]
 6 [2, 3]
 7 [7]
 8 [2, 2, 2]
 9 [3, 3]
10 [2, 5]
11 [[2, 5]]
12 [2, 2, 3]
13 [[2, 2, 3]]
14 [2, 7]
15 [3, 5]
16 [2, 2, 2, 2]
17 [[2, 2, 2, 2]]
18 [2, 3, 3]
19 [[2, 3, 3]]
20 [2, 2, 5]
21 [3, 7]
22 [2, [2, 5]]
23 [[2, [2, 5]]]
24 [2, 2, 2, 3]
25 [5, 5]

For example, for [2, [2, 5]], we first multiply the inner list and increment to get [2, 11]. From here, we just multiply, resulting in the final output of 22

---

You are to take the representation of a recursively prime-encoded integer and output the original integer.

The input will be a jagged list, where each element is either a single digit prime (\2,3,5,7ドル\$) or a list where the same rule applies. The input will never contain empty lists, and will never be empty.

This is code-golf, so the shortest code in bytes wins

Test cases

[2, 2, 2, 5] -> 40
[[2, 2, 3]] -> 13
[[2, 3, 5]] -> 31
[3] -> 3
[2, 3, 3, 5] -> 90
[2, [2, [2, 5]]] -> 46
[[2, 5]] -> 11
[[2, 2, 7, [2, 2, 2, 2, 3, 7]]] -> 9437
[2, 2, 2, 2, 2, 3, 5] -> 480
[2, 2, 2, 7, [2, 2, 2, 2]] -> 952
[2, [2, 2, 3, 7, [2, 3, 3]]] -> 3194
[2, 3, 3, [2, 2, 2, 2, 2, 2, 7]] -> 8082
[5, [2, 2, 7], [2, [2, [2, 5]]]] -> 6815
[5, [2, [2, 2, [2, 2, 2, 5], [2, [2, 5, 5, 5]]]]] -> 824935
[3, 3, [2, 2, 3, 3], [2, 7, [2, [2, 2, 2, 5]]]] -> 387279
[7, [2, 2, 5, 5], [2, 3, 5, [2, 3, 7]]] -> 912737
[[2, [2, [2, 5, [2, 2, 3]], [2, 2, 2, 2, 3, 3, 7]]]] -> 528719
[2, 2, 2, 2, 7, [2, 5], [2, 2, [2, 2, 2, 2, 2, 2, 3]]] -> 952336
[2, 3, 3, [2, 3, 5], [2, 5, 5, [2, 2, 7]]] -> 809658
[[2, 2, 2, 3, [2, 2, [2, 3, 7]]], [2, 2, 2, 2, 2, 2, 3, [2, 2, 3], [2, 2, 7, [2, 3, 3, 7]], [2, 5, [2, 2, 2, [2, 5]], [2, [2, 2, [2, 2, 3]]]]]] -> 3511306351619449
[5, 7, 7, [2, 3, [2, 5], [2, [2, 2, 2, 5]]], [2, 2, 2, 7, [2, [2, [2, 2, 2, [2, 5]]]], [2, 2, 2, 2, 2, 3, 3, [2, 5, [2, 3, [2, 2, 2, 2]]]]]] -> 8013135306533035
[2, 3, 3, [2, 2, 2, 3, 3], [2, 3, [2, [2, 5]]], [2, 3, [2, 2, 3, [2, 2, 2, 2, 2, 3], [2, [2, 5, 7, 7]], [2, 2, [2, 5], [2, 2, [2, 2, 3]]]]]] -> 2925382459116618

• Adamátor: This is very similar to jan Misali's proposed way of naming bases: youtube.com/watch?v=7OEF3JD-jYo

Answer 1

Python 2, 42 bytes

Thanks to @tsh for suggesting a 2-byte improvement

f=lambda x=1,*a:x<2or-(x*-1or~f(*x))*f(*a)

Try it online!

-(x*-1or~f(*x)) computes for a given element, its decoded value. If x is an integer, the or will short circuit, resulting in x as the value. If it is a list, x*-1 will return an empty list, and the result becomes a recursive call on x: -~f(*x).

This result is then multiplied by the rest of the elements through recursion: f(*a). Finally, the default x=1 argument assists in the terminating condition of x<2.

• tsh: Python 3, 43 bytes: f=lambda x=1,*a:x==1or-(x*-1or~f(*x))*f(*a)
• dan04: In case anybody is wondering about @tsh's modification: The original code relies on the < operator allowing comparisons between list and int. This is allowed in Python 2, but not in Python 3.

Answer 2

APL (Dyalog Extended), 13 bytes

 ̄1+(×ばつ/)⍥1⍣≡

Try it online!

Takes a nested APL array (which can be obtained from JSON-converting the test cases) and returns the original number.

How it works

This uses the Depth operator f⍥n, which hasn't made into mainstream yet. A depth-1 value in a mixed array can be a vector or a scalar (if one of its siblings is nested). ×ばつ/ is an expression that keeps scalar intact (product is itself and its depth ≡ is 0), and evaluates product + 1 for vectors. Now, we can simply repeat this at depth 1 until the entire value becomes a single number, and subtract 1 at the end (to negate the +1 applied at the very last layer).

• Jonah: I don't think this answer can be ported to J, but I'd appreciate any ideas you have on improving my answer. It felt like it should be much simpler, but given the way J's L: and L. verbs work, and the requirements for cases like [ x x ] and [[ x x ]], things got ugly.

Answer 3

yuno, 5 bytes

ᴘ’)υ‘

Try it online!

(ᴘ’)υ‘ Main Link
( )υ Deep Recurse; on each sub-list and recursively, call
 ᴘ - Product
 ’ - Increment
 ‘ Decrement

I've had the idea for υ from ever since I first started drafting yuno, but this adverb was implemented after this challenge.

Old version

yuno, 7 bytes

ɫ’)ᴅ?Ͼᴘ

Try it online!

Expect this to get shorter later once I implement more adverbs.

For now, this is the same approach as my Jelly solution.

(ɫ’)ᴅ?Ͼᴘ Main Link
 Ͼ For each item
 ? - If
 ᴅ - It has depth (it is a list and not just a single number)
(ɫ’) - Monadic function:
 ɫ - Call this link as a monad
 ’ - And increment
 ᴘ Take the product

• Adamátor: I'm looking forward to yuno becoming more usable!

Answer 4

JavaScript (ES6), 35 bytes

f=a=>a.map(n=>p*=+n||f(n)+1,p=1)&&p

Try it online!

• HK boy: You can save 1 byte by using | instead of &&.
• tsh: @HKboy but it failed on last 3 test cases.

Answer 5

Wolfram Language (Mathematica), (削除) 22 (削除ここまで) 17 bytes

1+1##&@@#&//@#-1&

Try it online!

1+1##&@@#&//@# expressions become the product of their arguments plus 1
 -1& subtract 1 (outermost list doesn't increment)

• Greg Martin: so beautiful! +1

Answer 6

Perl 5 (-p), 30 bytes

y/,]/*)/;s/\[/(1+/g;$_=-1+eval

replacing [ , ,, ] with (1+, *, ) resp., and evaluating.

Try it online!

Perl 5, 42 bytes

sub f{my$r=1;map$r*=@$_?1+f(@$_):$_,@_;$r}

with a recursive function

Try it online!

Answer 7

J, ⁴⁶ 45 bytes

[:(*>:)/[:;L:1^:_[:*/L:0;~&1^:((1=#)*1<L.)L:2

Try it online!

I thought this was going to be like 10 chars...

• Razetime: maybe Bubbler's solution would help with shortening this.
• Jonah: @Razetime I don't see a way, but I asked him for ideas.

Answer 8

Jelly, 9 bytes

ß‘μ1ŒḊ?€P

Try it online!

ß‘μPŒḊ?€P Main Link
 € For each element:
 ? - If
 ŒḊ - It has depth (isn't a number)
ß‘μ - Call this link on the sub-list, take the product, and increment it
 P - Otherwise, take the product (or first element, or sum, w/e)
 P Take the product

Answer 9

Stax, 13 bytes

â╥¡░Ω↕¬∟oqFμ+

Run and debug it

recursion's a bit clunky here, but thankfully it works.

Answer 10

Ruby, 41 bytes

f=->n{n.map{|x|x*0==0?x:f[x]+1}.reduce:*}

Try it online!

• dingledooper: 40 bytes

Answer 11

Retina, 34 bytes

~(`, 
$*
^.
.+¶$$.(
\[
$$.(_
]
$*)

Try it online! Link includes test cases. Explanation:

, 
$*

Change all separators into multiplication operators.

^.
.+¶$$.(

Change the opening [ into code to replace the input with the product of the values.

\[
$$.(_

Change the remaining [s into code to increment the product of the values.

]
$*)

Change the ]s into code to terminate the product expressions.

~(`

Evaluate the resulting program on the original input.

For example, the input [2, 2, 2, 7, [2, 2, 2, 2]] is transformed into the following Retina program:

.+
$.(2*2*2*7*$.(_2*2*2*2*))

The 2*2*2*2* evaluates to ________________, so the $.(_) results in 17, and the outer multiplication then produces the final result of 952.

Answer 12

Japt, 9 bytes

ËÉaßD)×ばつ

Try it or test 2-25 or run all test cases

Takes advantage of the fact that the sub-arrays are never singletons.

ËÉaßD)×ばつ :Implicit input of array
Ë :Map each D
 É : Subtract 1 (resulting in NaN if it's an array)
 a : Logical OR with
 ßD : A recursive call with argument D
 ) : Group that together
 Ä : Add 1 to the result
 Ã :End map
 ×ばつ :Reduce by multiplication

Answer 13

R, (削除) 65 (削除ここまで) 57 bytes

r=function(l,z=0)`if`(is.list(l),prod(sapply(l,r,1))+z,l)

Try it online!

Recursively adds 1 to the product of all list elements.

This would end-up one-too-many, so we skip adding 1 for the outermost loop.

Answer 14

MMIX, 56 bytes (14 instrs)

typedef union _rpe {
 struct {
 uint64_t flag : 1; // must be 1
 uint64_t val : 63;
 };
 union _rpe *list;
} rpe;
uint64_t __mmixware rpd(rpe encoded);

Lists terminate on a union _rpe that isn't a list (flag is on) whose val is 0. (MMIX pointers must be positive for user programs, or a trap occurs.)

00000000: 48000003 ec008000 f8010000 fe010004 H¡¡¤ġ¡0¡ẏ¢¡¡"¢¡\
00000010: e3020001 8f040000 e7000008 f303fff9 ẉ£¡¢Ɓ\¡¡ḃ¡¡®ṙ¤"ż
00000020: 42030003 1a020203 f1fffffb f6040001 B¤¡¤ȷ££¤ȯ""»ẇ\¡¢
00000030: 23000201 f8010000 #¡£¢ẏ¢¡¡

rpd BNN 0,0ドルF // if(encoded.flag)
 ANDNH 0,ドル#8000
 POP 1,0 // return encoded.val;
0H GET 1,ドルrJ
 SET 2,1ドル // uint64_t i = 1;
0H LDOU 4,ドル0ドル // loop: rpe n = *encoded.list;
 INCL 0,8ドル // encoded++;
 PUSHJ 3,ドルrpd // uint64_t j = rpd(n);
 BZ 3,0ドルF // if(!j) goto end;
 MULU 2,ドル2,ドル3ドル // i *= j;
 JMP 0B // goto loop;
0H PUT rJ,1ドル
 ADDU 0,ドル2,1ドル
 POP 1,0 // return i + 1;

Answer 15

Charcoal, 33 bytes

×ばつ⊟υΣι

Try it online! Link is to verbose version of code. Explanation:

FS≡ι

Loop over and switch on the input characters.

[⊞υ1

For [ push a 1 to the predefined empty list.

]¿⊖Lυ

For ] if the list has more than one element, then...

×ばつ⊕⊟υ⊟υ

... increment the top element and multiply the second element by it, otherwise...

Iυ

... print the result.

×ばつ⊟υΣι

Otherwise for digits multiply the top element by the value of the digits.

• Shaggy: "if the list has more than one element" - could you save anything there with the knowledge that sub-lists will always have more than one element? Or does that statement apply to the top-level list, too?
• Neil: @Shaggy I'm referring to the predefined empty list that I'm using as a stack to know how deep in [s I am, rather than the input "list" between the [ and ].
• Shaggy: Ah, I get it now :)

Answer 16

Gaia, (削除) 14 (削除ここまで) 12 bytes

Defines a function which takes a nested list and returns an integer.

⟨::C⟨←)⟩¿⟩¦Π

Try it online!

⟨ ⟩¦ # map over each element in the input
 :: # two copies of the TOS
 C # compare for two ints (0), count occurences for two lists (1)
 ⟨ ⟩¿ # if the TOS is truthy:
 ←) # recursively call the function and add 1
 Π # after the map: take the product

Answer 17

Pari/GP, 37 bytes

f(a)=vecprod([if(#b',f(b)+1,b)|b<-a])

Try it online!