4
\$\begingroup\$

This is a sequel to Ragged list pattern matching. In this challenge, the wildcard may match a sequence of items of any length instead of just a single item.

Given a pattern and a ragged list of integers, your task is to decide whether the pattern matches the ragged list.

The pattern is also represented by a ragged list. But in addition to positive integers, it may contain a wildcard value.

Here is the rule for matching:

  • A positive integer matches the same positive integer.
  • The wildcard value matches a sequence of items (integer or list) of any length, including the empty sequence.
  • A ragged list matches a ragged list if each item in the pattern matches the corresponding item in the list.

For example, if we write the wildcard as 0, then the pattern [0, [4, [5], 0]] matches the ragged list [[1, 2], [3], [4, [5]]]: here the first 0 matches the sequence [1, 2], [3], and the second 0 matches the empty sequence.

You may choose any fixed value as the wildcard, as long as it is consistent.

This is , so the shortest code in bytes wins.

This is . You may use your language's convention for truthy/falsy, or use two distinct, fixed values to represent true or false.

Testcases

Here I use 0 to represent the wildcard. The input here are given in the order pattern, ragged list.

Truthy

[], []
[0], []
[0], [1, 2]
[0], [[[]]]
[0, 0], [1, 2, 3]
[1, 0], [1, [[2, 3]]]
[1, 0, 2], [1, 2, 2, 2]
[1, 0, [2, 3]], [1, [2, 3]]
[1, [2, 0], 4], [1, [2, 3], 4]
[0, [4, [5], 0]], [[1, 2], [3], [4, [5]]]

Falsy

[1], []
[[]], []
[[0]], [3]
[[4]], [4]
[1, 0], [2, 1]
[[0]], [[1], [2]]
[1, 0, 2], [1, 2, 3]
[1, 0, 2, 0], [1, [3, 2, 3]]
[1, [0, 2], 4], [1, [2, 3], 4]
[[0], [4, [5], 0]], [[1, 2], [3], [4, [5]]]
\$\endgroup\$
1
  • 2
    \$\begingroup\$ suggest a test case who has two 0’s and expected output is false. When replace 0 by .* in its JSON representation, it matches. For example [1, 0, 2, 0] [1, [3, 2, 3]] \$\endgroup\$
    – tsh
    Mar 11, 2023 at 1:25

2 Answers 2

1
\$\begingroup\$

Retina, 71 bytes

>
,>
<,
<
~(L$`^.+
\n$&$
_,
(\d+,|<((?<_><)|(?<-_>>)|\d|,)+(?(_)^)>,)$*

Try it online! Takes two newline-separated <>-wrapped lists but link is to test suite that deletes spaces, splits on semicolons and converts other types of brackets for convenience. Uses _ to represent the wild card. Explanation: Based on my Retina answer to Ragged list pattern matching.

>
,>
<,
<

Ensure that non-empty lists end in a comma.

~(

Evaluate the result of the transformations below on the comma-safe input. Since they result in a single line, this makes Retina attempt to match the comma-safe input against the result.

L$`^.+
\n$&$

Take only the first line of the input and wrap it in \n and $ so that it will match against the second line of the input.

_,
(\d+,|<((?<_><)|(?<-_>>)|\d|,)+(?(_)^)>,)$*

Replace each _, with a match against any number ($* represents a literal * which would otherwise be the string repetition operator) of comma-safe non-negative integers or lists, using a .NET balancing group to ensure that the lists are properly balanced. A named capturing group ?<_> is used here because .NET allows capturing groups to be reused in this way and it's golfier than calculating the capturing group number.

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

Haskell, 89 bytes

Assumption: ragged lists are defined in the following way:

data RL a = L [RL a] | N a | W
  deriving Eq

Solution:

L(W:p)#L x|L p#L x=1>0
L(W:p)#L(_:x)=L(W:p)#L x
L(q:p)#L(y:x)=q#y&&L p#L x
a#b=a==W||a==b

Attempt This Online!

\$\endgroup\$

Your Answer

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

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