15
\$\begingroup\$

In Haskell (and probably some other languages or something) zip is a function which takes two lists, and produces a list of tuples by pairing elements at the same index:

zip [1,2,3] [6,5,4] = [(1,6),(2,5),(3,4)]

If there are extra elements on one of the input lists those are trimmed off and don't appear in the result:

zip [1,2,3] [6,5,4,3,2,1] = [(1,6),(2,5),(3,4)]

A ragged list is like a list, but instead of just containing one type of thing it can contain two types of things, one being itself. For example:

[1,[2,3,[2]]]

This is a ragged list of integers. It contains integers and ragged lists of integers.

You can easily imagine zipping ragged lists which have a similar enough structure. For example:

zip [1,[2,3,9],3] [2,[3,4,5,6]] = [(1,2),[(2,3),(3,4),(9,5)]]

But things get a little tricky when you have to combine an element (e.g. an integer) with a structure (e.g. a ragged list of integers). To do this we are going to distribute the element across the structure. Some examples:

zip [1] [[2,3,[5,4]]] = [[(1,2),(1,3),[(1,5),(1,4)]]] zip [1,2] [3,[4,5]] = [(1,3),[(2,4),(2,5)]] zip [[2,3],4] [1,[6,7]] = [[(2,1),(3,1)],[(4,6),(4,7)]]

This whole behavior can be captured by this Haskell program:

data Ragged a = Ragged (Either a [Ragged a]) zip' :: Ragged a -> Ragged b -> Ragged (a, b) zip' (Ragged x) (Ragged y) = Ragged $ go x y where go :: Either a [Ragged a] -> Either b [Ragged b] -> Either (a,b) [Ragged (a,b)] go (Left x) (Left y) = Left (x, y) go (Left x) (Right ys) = Right $ (zip' $ Ragged $ Left x) <$> ys go (Right xs) (Left y) = Right $ (flip zip' $ Ragged $ Left y) <$> xs go (Right xs) (Right ys) = Right $ zipWith zip' xs ys

Attempt This Online!

Task

Take as input two ragged lists of positive integers and output their zip as defined above. The output should be a ragged list of integer tuples. You may represent ragged lists and tuples in any reasonable way. The definition of ragged lists given here implies there is always a list at the top level, (e.g. 1 is not a ragged list of integers) so you may assume that this is the case for your inputs, but you may also support integers at the top level if its more convenient.

This is so the goal is to minimize the size of your source code as measured in bytes.

Improve this question
\$\endgroup\$
11
  • \$\begingroup\$ What is the correct output for zip 3 4? (3,4) or [(3, 4)] or both of them? \$\endgroup\$ Commented Feb 22, 2023 at 15:31
  • \$\begingroup\$ @EzioMercer There's no requirement to support zip 3 4 since 3 and 4 aren't considered ragged lists by the challenge. But the most sensible answer is (3,4) IMO, and that's the one given by the Haskell sample implementation. \$\endgroup\$ Commented Feb 22, 2023 at 15:39
  • 1
    \$\begingroup\$ @EzioMercer That's not really a test case it's part of the explanation of zip. I will modify these to make them more test-case like. \$\endgroup\$ Commented Feb 22, 2023 at 15:43
  • 1
    \$\begingroup\$ What's the result of inputs [1] and [2, 3]? \$\endgroup\$ Commented Feb 23, 2023 at 1:02
  • 1
    \$\begingroup\$ @Neil That's just a regular zip. [(1,2)] \$\endgroup\$ Commented Feb 23, 2023 at 3:50

9 Answers 9

Reset to default
6
\$\begingroup\$

Whython, 53 bytes

z=lambda a,b:map(z,[+a]*len(b)?a,[+b]*len(a)?b)?(a,b)

Takes two lists; returns map iterators instead of lists. Attempt This Online!

Explanation

Partly inspired by 97.100.97.109's Python answer.

z=lambda a,b:

Define z as a function of two arguments a and b.

map(z,...,...)

Map z over corresponding items from the following two iterables:

[+a]*len(b)?a

If a is an integer and b is a list, convert a to a list by putting it into a single-element list and then repeating it a number of times equal to the length of b. Otherwise, the first expression errors, either because +a is an error when a is a list, or because len(b) is an error when b is an int. In this case, catch the error with ? and use just a instead.

[+b]*len(a)?b

The second iterable is the same thing but for b instead of a.

If either or both of a and b are lists, the map will get two lists as arguments and will succeed. However, if they are both ints, the map will get two ints as arguments and will error. Thus:

?(a,b)

If the map errors, return a tuple containing a and b instead.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ The ? operator is the only feature of Whython used here? \$\endgroup\$ Commented Feb 23, 2023 at 3:57
  • 1
    \$\begingroup\$ @innisfree - Could it be that the ? operator is the only feature of Whython... \$\endgroup\$ Commented Feb 23, 2023 at 11:22
  • \$\begingroup\$ @innisfree Dominic van Essen is basically right. Whython does also have function composition via a[b] syntax, but that wasn't useful for this challenge (and, in fact, is rarely useful in golf). \$\endgroup\$ Commented Feb 23, 2023 at 16:58
4
\$\begingroup\$

Haskell, 100 92 bytes

data R a=I a|L[R a] I a%I b=I(a,b) L x%L y=L$zipWith(%)x y a%L y=L$map(a%)y L x%b=L$map(%b)x

Try it online!

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

K (ngn/k), 58 bytes

{$[&/i:`i=@:'(x;y);x,'y;|/i;x o'y;o'/#/:/|1(&/#:')\(x;y)]}

Try it online!

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

JavaScript, 76 bytes

z=(a,b,f=c=>c.shift?.()??c)=>a<z|b<z?[]:a+b>z?[z(f(a),f(b)),...z(a,b)]:[a,b] 

z=(a,b,f=c=>c.shift?.()??c)=>a<z|b<z?[]:a+b>z?[z(f(a),f(b)),...z(a,b)]:[a,b] console.log(JSON.stringify(z([1,2,3], [6,5,4]))); // [(1,6),(2,5),(3,4)] console.log(JSON.stringify(z([1,2,3], [6,5,4,3,2,1]))); // [(1,6),(2,5),(3,4)] console.log(JSON.stringify(z([1,[2,3,9],3], [2,[3,4,5,6]]))); // [(1,2),[(2,3),(3,4),(9,5)]] console.log(JSON.stringify(z([1], [[2,3,[5,4]]]))); // [[(1,2),(1,3),[(1,5),(1,4)]]] console.log(JSON.stringify(z([1,2], [3,[4,5]]))); // [(1,3),[(2,4),(2,5)]] console.log(JSON.stringify(z([[2,3],4], [1,[6,7]]))); // [[(2,1),(3,1)],[(4,6),(4,7)]]

Code with comment:

zip = (a, b) => { if (isEmptyArray(a) || isEmptyArray(b)) return []; if (isNonEmptyArray(a) || isNonEmptyArray(b)) { return [zip(pop(a), pop(b)), ...zip(a, b)]; } return [a, b]; }; isEmptyArray = a => a < zip; isNonEmptyArray = a => a > zip; pop = a => Array.isArray(a) ? a.shift() : a;
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ can't you remove z= from the byte count? The lambda function is supposed to be enough \$\endgroup\$ Commented Feb 24, 2023 at 10:02
  • 1
    \$\begingroup\$ @Kaddath no, z is used in the function. Without z= it would be confuse what it supposed to be. \$\endgroup\$ Commented Feb 24, 2023 at 10:48
1
\$\begingroup\$

Python, 101 91 bytes

-10 bytes thanks to @DLosc

g=lambda a,b:(a,b)*(a*0==0==b*0)or map(g,a*0!=0and a or[a]*len(b),b*0!=0and b or[b]*len(a))

Attempt This Online!

Takes in input as a tuple.

Python, 97 87 bytes

g=lambda a,b:(a,b)*(a*0==0==b*0)or map(g,a*(a*0!=0)or[a]*len(b),b*(b*0!=0)or[b]*len(a))

Attempt This Online!

Same as above, except it also assumes that the integers are never zero.

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

Rust, 294 284 271 bytes

#[derive(Clone)] enum A{b(i32),c(Vec<A>)}fn f(x:(A,A))->A{A::c(match x{(A::c(i),A::c(j))=>i.into_iter().zip(j).map(f).collect(),(y,A::c(j))=>j.into_iter().map(|k|f((y.clone(),k))).collect(),(A::c(i),z)=>i.into_iter().map(|k|f((k,z.clone()))).collect(),w=>vec![w.0,w.1]})}

Playground Link

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Oops I accidentally subtracted 100 from my score \$\endgroup\$ Commented Feb 23, 2023 at 7:58
1
\$\begingroup\$

JavaScript, 90 bytes

Expects input like z(list1, list2). Supports integer inputs

z=(a,b)=>a>z?a.flatMap((x,i)=>b[i]?[z(x,b[i])]:b>z?[]:[z(x,b)]):b>z?b.map(x=>z(a,x)):[a,b]

Ungolfed version:

z=(a,b)=>{ if (a>z) return a.flatMap((x,i)=>b[i]?[z(x,b[i])]:b>z?[]:[z(x,b)]) if (b>z) return b.map(x=>z(a,x)) return [a,b] }

Try it:

z=(a,b)=>a>z?a.flatMap((x,i)=>b[i]?[z(x,b[i])]:b>z?[]:[z(x,b)]):b>z?b.map(x=>z(a,x)):[a,b] ;[ [ [1, 2], '[1,2]' ], [ [1, [2,3]], '[[1,2],[1,3]]' ], [ [1, [2,[3]]], '[[1,2],[[1,3]]]' ], [ [[2,3], 1], '[[2,1],[3,1]]' ], [ [[1,2,3], [4,5,6]], '[[1,4],[2,5],[3,6]]' ], [ [[1,2], [4,5,6]], '[[1,4],[2,5]]' ], [ [[1,2,3], [4,5]], '[[1,4],[2,5]]' ], [ [[1], [[2,3,[4,5]]]], '[[[1,2],[1,3],[[1,4],[1,5]]]]' ], [ [[1,2], [3,[4,5]]], '[[1,3],[[2,4],[2,5]]]' ], [ [[[1,2],3], [4,[5,6]]], '[[[1,4],[2,4]],[[3,5],[3,6]]]' ], ].forEach(([[a,b],c])=>console.log(JSON.stringify(z(a,b)), JSON.stringify(z(a,b)) === c))

UPD 126 -> 98

Thanks to tsh for the tip to reduce bytes count

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You should include z= in front of your program. And you can replace a.length? by a>z?, replace i<b[l] by b[i], use flatMap instead of map. z=(a,b)=>a>z?b>z?a.flatMap((x,i)=>b[i]?[z(x,b[i])]:[]):a.map(x=>z(x,b)):b>z?b.map(x=>z(a,x)):[a,b] \$\endgroup\$ Commented Feb 23, 2023 at 5:29
  • \$\begingroup\$ @tsh I finally understand everything that you advised :) Thank you very much! It was very informative \$\endgroup\$ Commented Feb 23, 2023 at 14:04
1
\$\begingroup\$

Elm, 159 155 bytes

4 bytes saved thanks to Wheat Wizard!

type R a=I a|L(List(R a)) z v u=case(v,u)of (I x,I y)->I(x,y) (L x,L y)->L(List.map2 z x y) (_,L y)->L(List.map(z v)y) (L x,_)->L(List.map(\n->z n u)x)

Elm's pattern matching is not very golfy, and given the nature of the language, it is hard to squeeze out bytes in the case branches themselves. We define a recursive type R to encapsulate the ragged structures used in the challenge, since Elm does not natively support ragged lists. The function itself z is called on two such structures (of Ints), and returns a structure (of pairs of ints (Int, Int)). We must also fully qualify such structures to pass it to the program, as is the nature of Elm:

z (L[I 1, L[I 2, I 3, I 9], I 3]) (L[I 2, L[I 3, I 4, I 5, I 6]])

corresponds to zipRagged [1,[2,3,9],3] [2,[3,4,5,6]]. In the testing harness below, I've defined a parseCase function which allows the function to be called as z (parseCase "[1,[2,3,9],3]") (parseCase "[2,[3,4,5,6]]").

Testing

You can try it here with the following test program:

import Html exposing (..) -- begin code golf type R a=I a|L(List(R a)) z v u=case(v,u)of (I x,I y)->I(x,y) (L x,L y)->L(List.map2 z x y) (_,L y)->L(List.map(z v)y) (L x,_)->L(List.map(\n->z n u)x) -- end code golf -- z : R Int -> R Int -> R (Int, Int) -- display showResult : R (Int, Int) -> String showResult res = case res of I (x, y) -> "(" ++ (String.fromInt x) ++ "," ++ (String.fromInt y) ++ ")" L list -> "[" ++ (List.map showResult list |> String.join ", ") ++ "]" -- zip [1,[2,3,9],3] [2,[3,4,5,6]] = [(1,2),[(2,3),(3,4),(9,5)]] parseCase : String -> R Int parseCase str = str |> String.split "" |> parseCaseHelper type alias ParseState = { depth : Int , build : R Int , number : String , stack : List (R Int) } pushNumber : ParseState -> ParseState pushNumber state = if state.number == "" then state else let parsedNumber = state.number |> String.toInt |> Maybe.withDefault -1 pushed = case state.build of I x -> I parsedNumber L v -> L (v ++ [I parsedNumber]) in { state | number = "" , build = pushed } parseCaseHelper : List (String) -> R Int parseCaseHelper = List.foldl (\el state -> if el == "[" then { state | stack = state.build :: state.stack , build = L [] } else if el == "," then pushNumber state else if el == "]" then let nextState = pushNumber state in case nextState.stack of head :: rest -> { nextState | stack = rest , build = case (nextState.build, head) of (L b, L h) -> L (h ++ [nextState.build]) _ -> L [I -2] -- never occurs. "error" } _ -> state -- unbalanced. "error" else if "0" <= el && el <= "9" then { state | number = state.number ++ el } else state ) { depth = 0, build = L [], number = "", stack = [] } >> .build >> (\x -> case x of L ((L inner) :: rest) -> L inner _ -> x ) cases = [ ( "[1,[2,3,9],3]" , "[2,[3,4,5,6]]" ) , ( "[1]" , "[[2,3,[5,4]]]" ) , ( "[1,2]" , "[3,[4,5]]" ) , ( "[[2,3],4]" , "[1,[6,7]]" ) ] overTuple : (a -> b -> c) -> (a, b) -> c overTuple fn (left, right) = fn left right main = cases |> List.map (Tuple.mapBoth parseCase parseCase >> overTuple z >> showResult) |> List.map (\str -> Html.p [] [ text str ] ) |> Html.div []
Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

Charcoal, 63 60 bytes

⊞υθＦυＦ⊙ι⁼κ⁺κ⟦⟧«≔⮌Ｅ²⊟ιηＵＭη⎇⁼λ⁺λ⟦⟧λＥ§η¬μλＦＥ⌊ηＥη§νμ«⊞ιλ⊞υλ»»⭆¹θ

Try it online! Link is to verbose version of code. Takes input as a pair list of ragged lists, and outputs using pair lists as tuples. Explanation:

⊞υθＦυ

Start a breadth-first search with the pair of input lists.

Ｆ⊙ι⁼κ⁺κ⟦⟧«

If at least one corresponding entry from the pair is a list, then:

≔⮌Ｅ²⊟ιη

Extract the pair into a new list so that they can be replaced by their zipped entries.

ＵＭη⎇⁼λ⁺λ⟦⟧λＥ§η¬μλ

If one of the entries is an integer then repeat it for the length of the other list.

ＦＥ⌊ηＥη§νμ«

Loop over the transpose of the entries.

⊞ιλ⊞υλ

Push the new pairs back to the list that held the pair being processed but also to the list of lists to be processed so that they will themselves be zipped.

»»⭆¹θ

Pretty-print the final list because the default output format doesn't work well for ragged lists.

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.