id/email
password
forgot password | create account
about | help | code help+videos | done | prefs
CodingBat code practice

 

peter@norvig.com > regexp_list_matches
prev  |  next  |  chance

Jamie Zawinski, also known as JWZ, a legendary programmer who once worked with me, is noted for saying "Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems." What he meant, I think, is that regular expressions can be confusing. So let's give these people some help. The function regexp_list_matches(pattern, n) returns a list of all text strings of length n that match the pattern. That can help you understand how patterns work and whether you have built the right one for your problem. (To make it even easier, the list will be sorted alphabetically.) We will use a different language for patterns than in the previous exercise. This language is more powerful, and it is written in terms of nested lists, not just a single string. Here it is: a pattern can be any of the following: (1) a literal string, like 'hello', which matches exactly the string 'hello' and nothing else. (2) the list ['|', p1, p2], where p1 and p2 are patterns, means "p1 OR p2" and matches whatever p1 matches as well as whatever p2 matches. (3) ['*', p1] matches zero or more instances of p1. So, for example, ['*', 'x'] matches 'x', 'xx', 'xxx', and so on. (4) ['+', p1] matches one or more instances of p1. (5) ['?', p1] matches zero or one instances of p1. (6) ['[', chars], where chars is a string, matches any one of the characters in chars. (7) ['seq', p1, p2] matches anything p1 matches followed by anything p2 matches. For example, ['seq', 'x', ['|', '1', '2']] matches 'x1' and 'x2' (and nothing else).


regexp_list_matches(['seq', ['*', 'a'], ['seq', ['*', 'b'], ['*', 'c']]], 4) → ['aaaa', 'aaab', 'aaac', 'aabb', 'aabc', 'aacc', 'abbb', 'abbc', 'abcc', 'accc', 'bbbb', 'bbbc', 'bbcc', 'bccc', 'cccc']
regexp_list_matches(['seq', ['+', 'a'], ['seq', ['+', 'b'], ['+', 'c']]], 5) → ['aaabc', 'aabbc', 'aabcc', 'abbbc', 'abbcc', 'abccc']
regexp_list_matches(['*', ['|', 'a', 'b']], 4) → ['aaaa', 'aaab', 'aaba', 'aabb', 'abaa', 'abab', 'abba', 'abbb', 'baaa', 'baab', 'baba', 'babb', 'bbaa', 'bbab', 'bbba', 'bbbb']

...Save, Compile, Run (ctrl-enter)

def regexp_list_matches(pattern, n):

Editor font size %:
Shorter output


Forget It! -- delete my code for this problem

Progress graphs:
 Your progress graph for this problem
 Random user progress graph for this problem
 Random Epic Progress Graph

Python Help

Difficulty: 651 Post-solution available

Copyright Nick Parlante 2017 - privacy