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]]]
Improve this question
\$\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\$ Commented Mar 11, 2023 at 1:25

2 Answers 2

Reset to default
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.

Improve this answer
\$\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!

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.