8
\$\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.

[] [] -> []
[[]] [[]] -> [[]]
[[],[[]]] [[[]]] -> [[],[[]]]
[[[[]]]] [] -> []
[[],[[]],[]] [[],[[]]] -> [[],[],[],[[]],[],[]]
\$\endgroup\$
3
  • 5
    \$\begingroup\$ wow u sure do like ragged-lists this is like the 5th one in a row! \$\endgroup\$
    – DialFrost
    Jan 18 at 11:29
  • 1
    \$\begingroup\$ This is more of a puzzle for Haskell's type-checker than a programming problem! \$\endgroup\$
    – pxeger
    Jan 18 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 at 11:35

8 Answers 8

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.

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

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

Wolfram Language (Mathematica), 13 bytes

#0/@Tuples@#&

Try it online!

Takes input as a list of two ragged lists.

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

Charcoal, 34 bytes

⊞υAFυ«≔⊟ιηF⊟ιFEη⟦κλ⟧«⊞ιλ⊞υλ»»⭆¹§υ⁰

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

⊞υA

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

Fυ«

Loop over all the lists of ragged lists.

≔⊟ιη

Remove the second ragged list from the list.

F⊟ιFEη⟦κλ⟧«

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

\$\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)
\$\endgroup\$
0
0
\$\begingroup\$

Ruby, 28 bytes

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

Try it online!

Recursive by definition.

\$\endgroup\$
0
\$\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..

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

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