10
\$\begingroup\$

You are probably familiar with the Cartesian product. It takes two lists and creates a list of all pairs that can be made from an element of the first and an element from the second:

\$ \left[1,2\right] \times \left[3,4\right] = \left[(1,3),(1,4),(2,3),(2,4)\right] \$

Here the order of the result is such that the pairs whose first element is earlier in the first list come earlier in the result, and if the first elements come from the same element the pair whose second element comes first is earlier.

Now we can also have a generalized Cartesian product which takes 3 arguments, two lists and a function to combine pairs.

So for example if we wanted to find all ways to add an element of the first list to an element of the second list:

\$ \mathrm{Cart} : \left((A,B) \rightarrow C, [A], [B]\right)\rightarrow[C]\\ \mathrm{Cart}\left(+,[1,2],[3,4]\right) = [4,5,5,6] \$

This is the same as taking the regular Cartesian product and then adding up each pair.

Now with this generalized Cartesian product we are going to define the "product all the way down"

\$ a\otimes b = \mathrm{Cart}\left(\otimes, a,b\right) \$

This recursive definition is a little bit mind bending. \$\otimes\$ takes a ragged list containing nothing but lists all the way down and combines each pair of elements using itself.

Lets work through some examples. The simplest example is \$[\space]\otimes[\space]\$. Since the generalized Cartesian product of an empty list with anything is the empty list it doesn't matter that this is recursive the answer is just \$[\space]\otimes[\space] = [\space]\$. There are two elements to combine so there are no ways to combine two elements.

The next example is \$[[\space]]\otimes[[\space]]\$, here we have some elements. The regular Cartesian product of these is \$[([\space],[\space])]\$, we already know how to combine \$[\space]\$ with \$[\space]\$ so we can do that. Our result is \$[[\space]]\$.

Ok Let's do \$[[\space],[[\space]]]\otimes[[[\space]]]\$. First we take the Cartesian product,

\$ [([\space],[[\space]]),([[\space]],[[\space]])] \$

Then we combine each with \$\otimes\$:

\$ \begin{array}{ll} [[\space]\otimes[[\space]],&[[\space]]\otimes[[\space]]] \\ [[\space],&[[\space]]\otimes[[\space]]] \\ [[\space],&[[\space]\otimes[\space]]] \\ [[\space],&[[\space]]] \\ \end{array} \$

Task

Your task is to take two finite-depth ragged lists and return their "product all the way down".

Answers will be scored in bytes with the goal being to minimize the size of the source code.

Test cases

If you are having difficulty understanding please ask rather than try to infer the rules from test cases.

[] [] -> []
[[]] [[]] -> [[]]
[[],[[]]] [[[]]] -> [[],[[]]]
[[[[]]]] [] -> []
[[],[[]],[]] [[],[[]]] -> [[],[],[],[[]],[],[]]
Improve this question
\$\endgroup\$
3
  • 6
    \$\begingroup\$ wow u sure do like ragged-lists this is like the 5th one in a row! \$\endgroup\$
    – DialFrost
    Jan 18, 2022 at 11:29
  • 1
    \$\begingroup\$ This is more of a puzzle for Haskell's type-checker than a programming problem! \$\endgroup\$
    – pxeger
    Jan 18, 2022 at 11:33
  • 1
    \$\begingroup\$ @pxeger To do it in Haskell you can use the fixed point combinator. There's a nice elegant way to do this, which in fact inspired this challenge in the first place. \$\endgroup\$
    – Wheat Wizard ♦
    Jan 18, 2022 at 11:35

11 Answers 11

Reset to default
4
\$\begingroup\$

APL (Dyalog Unicode), 17 bytes

Anonymous infix lambda.

{0∊≢¨⍺⍵:⍬⋄,⍵∘.∇⍺}

Try it online!

{…} "dfn"; left argument is ⍺ and right argument is ⍵:

 0∊ Is zero a member of…
 ≢¨ the length of each of…
 ⍺⍵ the arguments?
 :⍬ If so, return the empty list.

 ⋄ Otherwise,…
 , ravel (flatten)…
 ⍵∘.∇⍺ the Cartesian self-product of the reversed arguments.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 13 bytes

#0/@Tuples@#&

Try it online!

Takes input as a list of two ragged lists.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Python, 42 bytes

f=lambda X,Y:[f(x,y)for x in X for y in Y]

Attempt This Online!

The obvious.

Improve this answer
\$\endgroup\$
0
2
\$\begingroup\$

Vyxal, 4 bytes

λΠvx

Try it Online!

Port of Jonathan Allan's Jelly answer.

Explanation

λ    # Start a lambda function
 Π   # Cartesian product
  v  # For each inner list:
   x #  Do a recursive call
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 19 11 bytes

"`â®δ.V"©.V

Input as a pair of ragged lists.

Try it online or verify all test cases.

Explanation:

"..."    # Recursive string as defined below
     ©   # Store this string in variable `®`
      .V # Execute it as 05AB1E code, using the (implicit) input as argument
         # (after which the result is output implicitly)

`        # Push both lists in the pair separated to the stack
 â       # Take the cartesian product of these two lists
   δ     # Map over each inner pair of lists:
  ® .V   # Execute `®` as 05AB1E code, doing a recursive call

If only 05AB1E had a recursive function builtin..

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 34 bytes

⊞υＡＦυ«≔⊟ιηＦ⊟ιＦＥη⟦κλ⟧«⊞ιλ⊞υλ»»⭆¹§υ⁰

Try it online! Link is to verbose version of code. Takes input as a list of two ragged lists. Explanation:

⊞υＡ

Push the list of two ragged lists to the predefined empty list.

Ｆυ«

Loop over all the lists of ragged lists.

≔⊟ιη

Remove the second ragged list from the list.

Ｆ⊟ιＦＥη⟦κλ⟧«

Remove the first ragged list from the list and loop over the Cartesian product of the lists.

⊞ιλ⊞υλ

Push each new list of two ragged lists to the ragged list being processed and also to the predefined empty list so that it will be "recursively" processed.

»»⭆¹§υ⁰

Pretty-print the resulting ragged list. (The default output for a ragged list is blank, so I don't have much choice here.)

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Jelly, 4 bytes

Œp߀

A monadic link accepting a list of the two ragged lists that yields their product-all-the-way-down.

Try it online!
Or see the test-suite (The footer parses and reformats like the question for ease of comparison)

How?

Œp߀ - Link, "f": list of lists (initially the two inputs), A:
Œp   - Cartesian product of A's items
   € - for each resulting list, a:
  ß  -   call this Link - i.e. f(a)
Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

Thunno, \$ 15 \log_{256}(96) \approx \$ 12.35 bytes

Y"yzSeYxAv"AxAv

Attempt This Online!

Port of Kevin Cruijssen's 05AB1E answer.

Explanation

Y"yzSeYxAv"AxAv  # Implicit input
Y                # Store it in y for later
 "yzSeYxAv"Ax    # Store the recursive string in x:
  yzS            #  Get the cartesian product of the elements of y
     e           #  Map:
      Y          #   Store the list in y
       xAv       #   And execute x as Thunno code
             Av  # Execute x as Thunno code
                 # Implicit output
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Ruby, 28 bytes

f=->a,b{a.product(b).map &f}

Try it online!

Recursive by definition.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

JavaScript, 33 bytes

f=A=>B=>A.flatMap(a=>B.map(f(a)))

Try it online!

Use as f(A)(B), as permitted here.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

jq, 24 bytes

def f:[combinations|f];f

Try it online!

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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