This puzzle series (first published here) is based on extracting information from statements about well-known classic rock bands. For each band, some or all of the most recognised band members are listed. Of these bands, 5 of them are British: The Beatles, The Rolling Stones, The Who, Electric Light Orchestra (ELO), and Queen. This article contains spoilers! In fact, the whole article is a spoiler as it contains solutions to the puzzles. If you are trying to solve the puzzles yourself and just want some pointers to get you started, stop reading when you have enough, and return if you get stuck again, or just want to compare your solution to mine! Note that, throughout this article, I have shown regular expressions that have been used with regex101, but it could be used equally well with the rex command in SPL. Part One The first part is to simply match the statements about The Beatles, The Rolling Stones, The Who, Electric Light Orchestra, and Queen. For example, your input includes: In the late '70's/early '80's, Blondie (Debbie Harry, Chris Stein, Jimmy Destri, Gary Valentine, Frank Infante, Nigel Harrison and Clem Burke) enjoyed much commercial success with their studio albums, before disbanding in late '82.
When he was with The Beatles, (John Lennon, Paul McCartney, Ringo Starr and George Harrison), Ringo Starr had two sole writing credits: Don't Pass Me By and Octopus's Garden.
Wings, a British rock band from 1971 to 1981, originally consisting of Paul McCartney, Linda McCartney, Denny Laine and Denny Seiwell, went through frequent personnel changes; however, the core trio of the McCartneys and Denny Laine, remained intact throughout the group's existence.
The crest used by Queen (John Deacon, Brian May, Freddie Mercury and Roger Taylor) was designed by Freddie Mercury, using the astrological signs of the four members. The full list (your puzzle input) can be found here. You will know you have (probably) got it right if you find 10 matches. Finding the bands Perhaps the simplest way to do this is to just list the bands as options in an Alternation construct with pipe symbols separating the bands. (?<match>.*(The Beatles|The Rolling Stones|The Who|Electric Light Orchestra|Queen).*) (Do not forget that we need to capture the complete statement about the band.) In regex101.com, (with the PCRE2 syntax) this takes about 15.5k steps, with the puzzle input. There are a number of ways to reduce this step count. Firstly, notice that three of the bands begin with "The", so, remove this repetition by having an alternation within the alternation. (?<match>.*(The (Beatles|Rolling Stones|Who)|Electric Light Orchestra|Queen).*) This gives about 10.4k steps, a 33% reduction. But, can we do better? Probably the biggest contributor to the number of steps is the "greedy any" match at the beginning. This means that the regex engine has to try matching to a lot of different characters before deciding whether there is a match or not. By making this a "lazy" or "reluctant" match (by placing a "?" after the "*"), we can reduce the number of steps. (?<match>.*?(The (Beatles|Rolling Stones|Who)|Electric Light Orchestra|Queen).*) This brings it down to 3.7k steps, about a 64% reduction. What else could we do to reduce the number of steps? Notice that all the alternates start on a word boundary, so, would taking that into account help? (?<match>.*?\b(The (Beatles|Rolling Stones|Who)|Electric Light Orchestra|Queen).*) Down to 2.3k steps, saving another 38%. This is a 85% reduction from our original 15.5k steps! It is possible to reduce this slightly like this: (?<match>.*?\b(The (B|R|W)|El|Q).*) This comes down to 2.2k steps, but, while it works with the original input, it is far less robust, for example, statements about "The Weeknd" would also be matched! Let's try another line of attack. The "any" match (the dot ".") at the beginning can be made more specific, allowing the regex engine to match or fail faster. We already know the initial letters of the bands, so anything that does not start with these letters can be skipped over. (?<match>[^TEQ]*?\b(The (Beatles|Who|Rolling Stones)|Queen|Electric Light Orchestra).*) That was a huge step in the wrong direction; over 120k steps. But, looking at which statements are actually matched, we can see that the beginning of the input has been included in the initial match, and that the statement beginning with "T" (which is not the start of a band name) has missed capturing the initial "T". To fix these issues, we can try this: (?<match>^.?[^TEQ\n]*?\b(The (Beatles|Who|Rolling Stones)|Queen|Electric Light Orchestra).*) Back down to a more respectable 4.6k steps. But still not as good as we had before. It turns out that some of the optimisations we put in before are getting in the way. For example, we do not need to check for word boundaries any more: (?<match>^.?[^TEQ\n]*?(The (Beatles|Who|Rolling Stones)|Queen|Electric Light Orchestra).*) Down to a very impressive 330 steps (without compromising on robustness of band names!) - just over 2% of our original step count! Part Two - Update For the second part, your input has changed - more data has become available and your previous match might not find all the expected statements (like that never happens!). You are still looking to match statements about The Beatles, The Rolling Stones, The Who, Electric Light Orchestra, and Queen. The full list (your puzzle input) can be found here. This time, you will know you have (probably) got it right if you find 11 matches. Finding the differences Perhaps the first thing to check is whether the previous expression finds all the correct matches. Unfortunately, this only finds 9 matches, not even the 10 we had earlier! By comparing the two sets of input, we can see that "Electric Light Orchestra" has been abbreviated to "ELO", "The Beatles" were also known as "The Fab Four", and there are a couple of additional statements about bands. Adapting the previous expression to take these differences into account gives this: (?<match>^.?[^TEQ\n]*?(The (Beatles|Fab Four|Who|Rolling Stones)|Queen|E(lectric )?L(ight )?O(rchestra)?).*) Interestingly, this does appear to work; although you may have noticed that one of the new statements does mention "Electric Light Orchestra" but the expression does not pick that statement up. I will leave it for you to figure out why this is. Alternative method The puzzle description lists the bands we are interested in, but it does not define who the members of the bands are. Either from your own research or by examining the data, we can determine the following well-known band line-ups for the British bands we are looking for: The Beatles - John Lennon, Paul McCartney, Ringo Starr and George Harrison The Rolling Stones - Charlie Watts, Bill Wyman, Brian Jones, Mick Jagger and Keith Richards The Who - Roger Daltrey, Pete Townshend, John Entwistle and Keith Moon Electric Light Orchestra (ELO) - Jeff Lynne, Roy Wood and Bev Bevan Queen - Brian May, Freddie Mercury, Roger Taylor and John Deacon Using these names, we can find all the statements containing these names. (?<match>.*(John Lennon|Paul McCartney|Ringo Starr|George Harrison|Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards|Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon|Jeff Lynne|Roy Wood|Bev Bevan|Brian May|Freddie Mercury|Roger Taylor|John Deacon).*) This finds all the statements we are interested in, but it also includes a couple of other statements which mention some of these band members when they were part of other bands. How do we ensure that the list in the statement contains just members from the desired bands? Finding lists The band members are in comma-separated lists, and, as all the bands have at least three members, can we use this to find statements which "list" at least three band members? (?<match>.*(John Lennon|Paul McCartney|Ringo Starr|George Harrison|Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards|Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon|Jeff Lynne|Roy Wood|Bev Bevan|Brian May|Freddie Mercury|Roger Taylor|John Deacon), (John Lennon|Paul McCartney|Ringo Starr|George Harrison|Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards|Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon|Jeff Lynne|Roy Wood|Bev Bevan|Brian May|Freddie Mercury|Roger Taylor|John Deacon), (John Lennon|Paul McCartney|Ringo Starr|George Harrison|Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards|Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon|Jeff Lynne|Roy Wood|Bev Bevan|Brian May|Freddie Mercury|Roger Taylor|John Deacon).*) Looking at the results, you might notice that a few of the statements, which we might have expected to be there, are not being matched. One reason for this is because, where only three band members are listed, the last two are separated by an "and" instead of a comma, so we can modify the expression to take this into account. (?<match>.*(John Lennon|Paul McCartney|Ringo Starr|George Harrison|Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards|Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon|Jeff Lynne|Roy Wood|Bev Bevan|Brian May|Freddie Mercury|Roger Taylor|John Deacon), (John Lennon|Paul McCartney|Ringo Starr|George Harrison|Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards|Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon|Jeff Lynne|Roy Wood|Bev Bevan|Brian May|Freddie Mercury|Roger Taylor|John Deacon) and (John Lennon|Paul McCartney|Ringo Starr|George Harrison|Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards|Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon|Jeff Lynne|Roy Wood|Bev Bevan|Brian May|Freddie Mercury|Roger Taylor|John Deacon).*) Part Three - Another Update For the third part, your input has changed again - more data has become available and your previous match might not find all the expected statements (like that never happens!). You are still looking to match statements about The Beatles, The Rolling Stones, The Who, Electric Light Orchestra, and Queen. The full list (your puzzle input) can be found here. Again, you will know you have (probably) got it right if you find 11 matches. Checking lists Using the list expression from earlier no longer works for all the desired statements. This is because some lists do not include "and", whereas other lists include a comma before the "and" (the so-called "Oxford" or "serial" comma). To fix this, we can make them optional with the '?' quantifier. (?<match>.*(John Lennon|Paul McCartney|Ringo Starr|George Harrison|Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards|Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon|Jeff Lynne|Roy Wood|Bev Bevan|Brian May|Freddie Mercury|Roger Taylor|John Deacon), (John Lennon|Paul McCartney|Ringo Starr|George Harrison|Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards|Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon|Jeff Lynne|Roy Wood|Bev Bevan|Brian May|Freddie Mercury|Roger Taylor|John Deacon),?( and)? (John Lennon|Paul McCartney|Ringo Starr|George Harrison|Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards|Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon|Jeff Lynne|Roy Wood|Bev Bevan|Brian May|Freddie Mercury|Roger Taylor|John Deacon).*) By the way, the previous method of just checking the band name still appears to work. Part Four - Requirements Change For the fourth part, not only has your input has changed (again), your requirements have changed too (sound familiar?) - your expression needs to ensure that the list of band members contains at least two members of the relevant band. You are still looking to match statements about The Beatles, The Rolling Stones, The Who, Electric Light Orchestra, and Queen, with at least two of the band members listed. The full list (your puzzle input) can be found here. This time, you will know you have (probably) got it right if you find 14 matches. Checking lists Using the previous list-based expression (from earlier) finds most of the desired statements. However, one of the statements is missed, because it only includes two of the band members, so reduce the number of band members being matched appropriately. (?<match>.*(John Lennon|Paul McCartney|Ringo Starr|George Harrison|Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards|Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon|Jeff Lynne|Roy Wood|Bev Bevan|Brian May|Freddie Mercury|Roger Taylor|John Deacon),?( and)? (John Lennon|Paul McCartney|Ringo Starr|George Harrison|Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards|Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon|Jeff Lynne|Roy Wood|Bev Bevan|Brian May|Freddie Mercury|Roger Taylor|John Deacon).*) That fixes one problem, but creates another; we have matched an additional statement which list two of the band members but they are from different classic British rock bands and this statement is not about one of the five bands we are trying to match with anyway. How do we ensure that each list only contains members from the same British rock band? Finding the lists of band members Rather than listing all the members of the 5 British rock bands in a single list of names, we can group them based on which classic British rock band they are members of. Since we have to assume that the band members might be listed in any order, so, we match with all of the relevant band members each time. (Note the use of nested option groups, i.e. an option for each band and within that options for each band member.) (?<match>.*((John Lennon|Paul McCartney|Ringo Starr|George Harrison),?( and)? (John Lennon|Paul McCartney|Ringo Starr|George Harrison)|(Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards),?( and)? (Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards)|(Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon),?( and)? (Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon)|(Jeff Lynne|Roy Wood|Bev Bevan),?( and)? (Jeff Lynne|Roy Wood|Bev Bevan)|(Brian May|Freddie Mercury|Roger Taylor|John Deacon),?( and)? (Brian May|Freddie Mercury|Roger Taylor|John Deacon)).*) Part Five - Additional Requirement You have done such a good job, you are now required to extract the full list of band members to a new field (group) - at least your input hasn't changed! You will know you have (probably) got it right if you (still) find 14 matches and more than 85% of the words in the lists of band members have four or more letters. (This check is probably easier to do in SPL!) Additional Capture Group We now have matched all the statements which list members of the 5 classic British rock bands, but this is only the "match" part of the puzzle. Now we need to find the "group", i.e. the band members that are listed in the statement. We could try making the outer alternate group a named capture group. (?<match>.*(?<group>(John Lennon|Paul McCartney|Ringo Starr|George Harrison),?( and)? (John Lennon|Paul McCartney|Ringo Starr|George Harrison)|(Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards),?( and)? (Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards)|(Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon),?( and)? (Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon)|(Jeff Lynne|Roy Wood|Bev Bevan),?( and)? (Jeff Lynne|Roy Wood|Bev Bevan)|(Brian May|Freddie Mercury|Roger Taylor|John Deacon),?( and)? (Brian May|Freddie Mercury|Roger Taylor|John Deacon)).*) But this only captures the last two band members list in the group. What happens if we try to capture all members of the group, 4 for The Beatles, The Who and Queen, 5 for The Rolling Stones and 3 for ELO? (?<match>.*(?<group>(John Lennon|Paul McCartney|Ringo Starr|George Harrison), (John Lennon|Paul McCartney|Ringo Starr|George Harrison), (John Lennon|Paul McCartney|Ringo Starr|George Harrison),?( and)? (John Lennon|Paul McCartney|Ringo Starr|George Harrison)|(Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards), (Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards), (Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards), (Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards),?( and)? (Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards)|(Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon), (Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon), (Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon), (Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon),?( and)? (Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon)|(Jeff Lynne|Roy Wood|Bev Bevan), (Jeff Lynne|Roy Wood|Bev Bevan),?( and)? (Jeff Lynne|Roy Wood|Bev Bevan)|(Brian May|Freddie Mercury|Roger Taylor|John Deacon), (Brian May|Freddie Mercury|Roger Taylor|John Deacon), (Brian May|Freddie Mercury|Roger Taylor|John Deacon),?( and)? (Brian May|Freddie Mercury|Roger Taylor|John Deacon)).*) This works fine if all the band members are listed, but this is not the case for some of the statements. What if we make the first few repeats optional (again, with the '?' quantifier)? (?<match>.*(?<group>((John Lennon|Paul McCartney|Ringo Starr|George Harrison), )?((John Lennon|Paul McCartney|Ringo Starr|George Harrison), )?(John Lennon|Paul McCartney|Ringo Starr|George Harrison),?( and)? (John Lennon|Paul McCartney|Ringo Starr|George Harrison)|((Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards), )?((Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards), )?((Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards), )?(Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards),?( and)? (Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards)|((Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon), )?((Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon), )?(Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon),?( and)? (Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon)|((Jeff Lynne|Roy Wood|Bev Bevan), )?(Jeff Lynne|Roy Wood|Bev Bevan),?( and)? (Jeff Lynne|Roy Wood|Bev Bevan)|((Brian May|Freddie Mercury|Roger Taylor|John Deacon), )?((Brian May|Freddie Mercury|Roger Taylor|John Deacon), )?(Brian May|Freddie Mercury|Roger Taylor|John Deacon),?( and)? (Brian May|Freddie Mercury|Roger Taylor|John Deacon)).*) Now, we are back to just capturing two members of the group! Looking more closely at our regular expression, hopefully, you may have noticed the "greedy" match at the beginning. By modifying this to a "lazy" match, we can capture all the listed members of the group! (?<match>.*?(?<group>((John Lennon|Paul McCartney|Ringo Starr|George Harrison), )?((John Lennon|Paul McCartney|Ringo Starr|George Harrison), )?(John Lennon|Paul McCartney|Ringo Starr|George Harrison),?( and)? (John Lennon|Paul McCartney|Ringo Starr|George Harrison)|((Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards), )?((Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards), )?((Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards), )?(Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards),?( and)? (Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards)|((Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon), )?((Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon), )?(Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon),?( and)? (Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon)|((Jeff Lynne|Roy Wood|Bev Bevan), )?(Jeff Lynne|Roy Wood|Bev Bevan),?( and)? (Jeff Lynne|Roy Wood|Bev Bevan)|((Brian May|Freddie Mercury|Roger Taylor|John Deacon), )?((Brian May|Freddie Mercury|Roger Taylor|John Deacon), )?(Brian May|Freddie Mercury|Roger Taylor|John Deacon),?( and)? (Brian May|Freddie Mercury|Roger Taylor|John Deacon)).*) Now we have the members of the "group" but we can tidy this expression up by compacting the first couple of list item matches into a single "greedy" match i.e. zero or more occurrences. (?<match>.*?(?<group>((John Lennon|Paul McCartney|Ringo Starr|George Harrison), )*(John Lennon|Paul McCartney|Ringo Starr|George Harrison),?( and)? (John Lennon|Paul McCartney|Ringo Starr|George Harrison)|((Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards), )*(Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards),?( and)? (Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards)|((Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon), )*(Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon),?( and)? (Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon)|((Jeff Lynne|Roy Wood|Bev Bevan), )*(Jeff Lynne|Roy Wood|Bev Bevan),?( and)? (Jeff Lynne|Roy Wood|Bev Bevan)|((Brian May|Freddie Mercury|Roger Taylor|John Deacon), )*(Brian May|Freddie Mercury|Roger Taylor|John Deacon),?( and)? (Brian May|Freddie Mercury|Roger Taylor|John Deacon)).*) Part Six - Scope-creep As well as the full list of band members, you are now required to extract the penultimate band member listed to a new field (member) - at least your input hasn't changed! You will know you have (probably) got it right if you find 14 matches and only two repeated band member names. Penultimate member listed We could try capturing the penultimate group member because, by definition, it is the one before the optional "and". (?<match>.*?(?<group>((John Lennon|Paul McCartney|Ringo Starr|George Harrison), )*(?<member>John Lennon|Paul McCartney|Ringo Starr|George Harrison),?( and)? (John Lennon|Paul McCartney|Ringo Starr|George Harrison)|((Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards), )*(?<member>Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards),?( and)? (Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards)|((Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon), )*(?<member>Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon),?( and)? (Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon)|((Jeff Lynne|Roy Wood|Bev Bevan), )*(?<member>Jeff Lynne|Roy Wood|Bev Bevan),?( and)? (Jeff Lynne|Roy Wood|Bev Bevan)|((Brian May|Freddie Mercury|Roger Taylor|John Deacon), )*(?<member>Brian May|Freddie Mercury|Roger Taylor|John Deacon),?( and)? (Brian May|Freddie Mercury|Roger Taylor|John Deacon)).*) However, this (usually) generates an error since we are not (normally) allowed to use duplicate capture group names. So, change the names so that they are unique. (Note that there are option settings in some versions of regular expressions that allow duplicate capture group names, but we are not going to try to use them in this instance.) (?<match>.*?(?<group>((John Lennon|Paul McCartney|Ringo Starr|George Harrison), )*(?<beatle>John Lennon|Paul McCartney|Ringo Starr|George Harrison),?( and)? (John Lennon|Paul McCartney|Ringo Starr|George Harrison)|((Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards), )*(?<stone>Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards),?( and)? (Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards)|((Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon), )*(?<who>Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon),?( and)? (Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon)|((Jeff Lynne|Roy Wood|Bev Bevan), )*(?<elo>Jeff Lynne|Roy Wood|Bev Bevan),?( and)? (Jeff Lynne|Roy Wood|Bev Bevan)|((Brian May|Freddie Mercury|Roger Taylor|John Deacon), )*(?<queen>Brian May|Freddie Mercury|Roger Taylor|John Deacon),?( and)? (Brian May|Freddie Mercury|Roger Taylor|John Deacon)).*) You can use SPL to check you have found the repeated names. | eval member=coalesce(beatle, elo, queen, stone, who)
| eventstats count by member
| eval repeats=if(count > 1, member, null())
| eventstats values(repeats) as repeats Part Seven - Stretch goal You finally(?) manage to find out what is actually required: you are now required to extract just three named groups / fields: the statements (match); the listed band members (group); and the penultimate band member listed (member), but only for statements where the band member appears later on in the statement - at least your input hasn't changed! You will know you have (probably) got it right if you find 10 matches and no repeated band member names, and only three named groups. Subsequent mention The simplest way to find out if the penultimate band member is mentioned further on in the statement is by adding another capture group. (?<match>.*?(?<group>((John Lennon|Paul McCartney|Ringo Starr|George Harrison), )*(?<beatle>John Lennon|Paul McCartney|Ringo Starr|George Harrison),?( and)? (John Lennon|Paul McCartney|Ringo Starr|George Harrison)|((Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards), )*(?<stone>Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards),?( and)? (Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards)|((Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon), )*(?<who>Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon),?( and)? (Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon)|((Jeff Lynne|Roy Wood|Bev Bevan), )*(?<elo>Jeff Lynne|Roy Wood|Bev Bevan),?( and)? (Jeff Lynne|Roy Wood|Bev Bevan)|((Brian May|Freddie Mercury|Roger Taylor|John Deacon), )*(?<queen>Brian May|Freddie Mercury|Roger Taylor|John Deacon),?( and)? (Brian May|Freddie Mercury|Roger Taylor|John Deacon)).*(?<member>(?P=beatle)|(?P=who)|(?P=queen)|(?P=stone)|(?P=elo)).*) This capture group "member" matches to the penultimate band member extracted earlier depending on which classic band has been listed. Unfortunately, this doesn't quite work for all cases. By placing the match to the band member, sometimes the penultimate band member is not matched correctly. This is because of the way we have assumed the lists have been constructed. To explain this, look at the following simplified lists: A, B, C, and D A, B, C and D A, B, C, D A, B and C A and B All these list types are present in the input. For the penultimate item in the list, we have assumed that it appears before the "and" (if it exists). However, another way to look at it is that, the penultimate item in the list is the last item (followed by a comma and a space or just a space) that is not followed by any more non-terminating list items (i.e. those followed by a comma or an "and") and not followed by an "and". For example: A, (followed by "B, "), B, (followed by "C, "), C, (penultimate, because it is followed by "and") A, (followed by "B, "), B, (followed by "C "), C (penultimate, because it is followed by "and") A, (followed by "B, "), B, (followed by "C, "), C, (penultimate, because it is followed by a terminating list item i.e. an item not followed by a comma or an "and") A, (followed by "B "), B (penultimate, because it is followed by "and") A (penultimate, because it is followed by "and") The "cheat" here is that all the early items in the list are followed by commas; if they were followed by just spaces, the match would still work but could the "list" be considered as a list? (?<match>.*?(?<group>((?<beatle>John Lennon|Paul McCartney|Ringo Starr|George Harrison),? )+((John Lennon|Paul McCartney|Ringo Starr|George Harrison)(?!(,| and))|and (John Lennon|Paul McCartney|Ringo Starr|George Harrison))|((?<stone>Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards),? )+((Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards)(?!(,| and))|and (Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards))|((?<who>Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon),? )+((Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon)(?!(,| and))|and (Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon))|((?<elo>Jeff Lynne|Roy Wood|Bev Bevan),? )+((Jeff Lynne|Roy Wood|Bev Bevan)(?!(,| and))|and (Jeff Lynne|Roy Wood|Bev Bevan))|((?<queen>Brian May|Freddie Mercury|Roger Taylor|John Deacon),? )+((Brian May|Freddie Mercury|Roger Taylor|John Deacon)(?!(,| and))|and (Brian May|Freddie Mercury|Roger Taylor|John Deacon))).*(?<member>(?P=beatle)|(?P=who)|(?P=queen)|(?P=stone)|(?P=elo)).*) Note that this expression makes use of an interesting feature of capture groups when there are multiple matches, and that is that only the last captured value is kept; so when the back-reference to the capture group is made, for example, (?P=beatle), this takes on the last value in this capture group (not the whole set of values captured). This is why the "groups" are made up of a selection of names multiple times, followed by the same selection of names once more, ensuring that the multiple selection captures the penultimate value. Optimisations Before we start to try and complete this part (by removing the unwanted named capture groups / fields), let's look at ways to optimise the expression. One way to optimise is to shorten the expression; the first way to do this is to use shorter names for the capture group names (except where they are important to completing the puzzle). Just for fun, following the top line of letters on a standard UK keyboard, I have used "q" (for Queen), "w" (for The Who), "e" (for ELO), "r" (for The Rolling Stones), and "t" (for The Beatles). (?<match>.*?(?<group>((?<t>John Lennon|Paul McCartney|Ringo Starr|George Harrison),? )+((John Lennon|Paul McCartney|Ringo Starr|George Harrison)(?!(,| and))|and (John Lennon|Paul McCartney|Ringo Starr|George Harrison))|((?<r>Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards),? )+((Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards)(?!(,| and))|and (Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards))|((?<w>Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon),? )+((Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon)(?!(,| and))|and (Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon))|((?<e>Jeff Lynne|Roy Wood|Bev Bevan),? )+((Jeff Lynne|Roy Wood|Bev Bevan)(?!(,| and))|and (Jeff Lynne|Roy Wood|Bev Bevan))|((?<q>Brian May|Freddie Mercury|Roger Taylor|John Deacon),? )+((Brian May|Freddie Mercury|Roger Taylor|John Deacon)(?!(,| and))|and (Brian May|Freddie Mercury|Roger Taylor|John Deacon))).*(?<member>(?P=q)|(?P=w)|(?P=e)|(?P=r)|(?P=t)).*) Next, there is a lot of repetition of text in this expression; can some of this text be removed to shorten the expression? This optimisation uses subroutines; subroutines are re-usable regular expressions. Rather than repeating the list of possible band members three times in the expression, create a subroutine listing the possible band members, and reuse it twice more. (Note the syntax for defining a subroutine and making calls to the subroutine.) (?<match>.*?(?<group>((?'t'John Lennon|Paul McCartney|Ringo Starr|George Harrison),? )+((?&t)(?!(,| and))|and (?&t))|((?'r'Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards),? )+((?&r)(?!(,| and))|and (?&r))|((?'w'Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon),? )+((?&w)(?!(,| and))|and (?&w))|((?'e'Jeff Lynne|Roy Wood|Bev Bevan),? )+((?&e)(?!(,| and))|and (?&e))|((?'q'Brian May|Freddie Mercury|Roger Taylor|John Deacon),? )+((?&q)(?!(,| and))|and (?&q))).*(?<member>(?P=t)|(?P=w)|(?P=q)|(?P=r)|(?P=e)).*) As you can see, this is much shorter than the previous version. The next set of optimisations are to do with the number of steps taken to complete the matches (for example, as measured by regex101). The current expression takes just over 88.3k steps against the full set of data. By anchoring the match to the start of the line we can reduce this to just over 88k steps. (?<match>^.*?(?<group>((?'t'John Lennon|Paul McCartney|Ringo Starr|George Harrison),? )+((?&t)(?!(,| and))|and (?&t))|((?'r'Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards),? )+((?&r)(?!(,| and))|and (?&r))|((?'w'Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon),? )+((?&w)(?!(,| and))|and (?&w))|((?'e'Jeff Lynne|Roy Wood|Bev Bevan),? )+((?&e)(?!(,| and))|and (?&e))|((?'q'Brian May|Freddie Mercury|Roger Taylor|John Deacon),? )+((?&q)(?!(,| and))|and (?&q))).*(?<member>(?P=t)|(?P=w)|(?P=q)|(?P=r)|(?P=e)).*) (We could try anchoring the match to the end of the line, but this actually takes more steps!) By shuffling the order of the bands in the group and member options can shave a few more steps off (but nothing significant) - generally, putting the longer options first seems to helps, although this is not always the case. (?<match>^.*?(?<group>((?'r'Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards),? )+((?&r)(?!(,| and))|and (?&r))|((?'q'Brian May|Freddie Mercury|Roger Taylor|John Deacon),? )+((?&q)(?!(,| and))|and (?&q))|((?'w'Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon),? )+((?&w)(?!(,| and))|and (?&w))|((?'t'John Lennon|Paul McCartney|Ringo Starr|George Harrison),? )+((?&t)(?!(,| and))|and (?&t))|((?'e'Jeff Lynne|Roy Wood|Bev Bevan),? )+((?&e)(?!(,| and))|and (?&e))).*(?<member>(?P=r)|(?P=q)|(?P=w)|(?P=t)|(?P=e)).*) As shown earlier, another area to explore is the quantifiers. By converting the greedy "any" (*) match (between the group and the later mention) to a lazy "at least once" (+) match improves the number of steps down to just over 84k. (?<match>^.*?(?<group>((?'r'Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards),? )+((?&r)(?!(,| and))|and (?&r))|((?'q'Brian May|Freddie Mercury|Roger Taylor|John Deacon),? )+((?&q)(?!(,| and))|and (?&q))|((?'w'Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon),? )+((?&w)(?!(,| and))|and (?&w))|((?'t'John Lennon|Paul McCartney|Ringo Starr|George Harrison),? )+((?&t)(?!(,| and))|and (?&t))|((?'e'Jeff Lynne|Roy Wood|Bev Bevan),? )+((?&e)(?!(,| and))|and (?&e))).+?(?<member>(?P=r)|(?P=q)|(?P=w)|(?P=t)|(?P=e)).*) The other thing we tried earlier was to replace the "any" (dot) with a more specific negative character class. (?<match>^.?[^BCFGJKMPR\n]*?(?<group>((?'r'Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards),? )+((?&r)(?!(,| and))|and (?&r))|((?'q'Brian May|Freddie Mercury|Roger Taylor|John Deacon),? )+((?&q)(?!(,| and))|and (?&q))|((?'w'Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon),? )+((?&w)(?!(,| and))|and (?&w))|((?'t'John Lennon|Paul McCartney|Ringo Starr|George Harrison),? )+((?&t)(?!(,| and))|and (?&t))|((?'e'Jeff Lynne|Roy Wood|Bev Bevan),? )+((?&e)(?!(,| and))|and (?&e))).+?(?<member>(?P=r)|(?P=q)|(?P=w)|(?P=t)|(?P=e)).*) This brings the step count down, but, unfortunately, it does not match with all the required statements. The issue appears to be if there is a word the starts with one of the initials of the band members, which is not the name of the band member. So, another way to look at the prefix to the band member's name, is that it contains their initials or not their initials, zero or more times ("lazy" match so we do not go too far), up to the point where it matches their name (as defined in the capture group). (?<match>^([BCFGJKMPR]|[^BCFGJKMPR\n]++)*?(?<group>((?'r'Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards),? )+((?&r)(?!(,| and))|and (?&r))|((?'q'Brian May|Freddie Mercury|Roger Taylor|John Deacon),? )+((?&q)(?!(,| and))|and (?&q))|((?'w'Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon),? )+((?&w)(?!(,| and))|and (?&w))|((?'t'John Lennon|Paul McCartney|Ringo Starr|George Harrison),? )+((?&t)(?!(,| and))|and (?&t))|((?'e'Jeff Lynne|Roy Wood|Bev Bevan),? )+((?&e)(?!(,| and))|and (?&e))).+?(?<member>(?P=r)|(?P=q)|(?P=w)|(?P=t)|(?P=e)).*) Now we are back down to a reasonable 19k steps. Just one more thing Re-reading the puzzle description, the requirement is to extract "just three fields", but the named groups in regex101 (and the fields created in SPL with the rex command) include "r", "q", "w", "t" and "e". How do we remove these? Obviously, in SPL we could add a fields command to remove them, but this is primarily a regex puzzle, so we need to remove them from the regular expression. The first thing we can do is remove the back-references to the named capture groups by using their number instead. (Determining the number is reasonably easy by counting the opening and closing parentheses or by looking at the explanation of the regular expression provided by regex101.) (?<match>^(?:[BCFGJKMPR]|[^BCFGJKMPR\n]++)*?(?<group>((?'r'Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards),? )+((?&r)(?!(,| and))|and (?&r))|((?'q'Brian May|Freddie Mercury|Roger Taylor|John Deacon),? )+((?&q)(?!(,| and))|and (?&q))|((?'w'Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon),? )+((?&w)(?!(,| and))|and (?&w))|((?'t'John Lennon|Paul McCartney|Ringo Starr|George Harrison),? )+((?&t)(?!(,| and))|and (?&t))|((?'e'Jeff Lynne|Roy Wood|Bev Bevan),? )+((?&e)(?!(,| and))|and (?&e))).+?(?<member>\4|\8|\12|\16|\20).*) In addition, we can, in fact, make a call to the expression used in a capture group by number as if it had been defined as a named subroutine, that is, we do not need the names at all - we can make un-named subroutine calls! (Note the change in syntax for calling un-named subroutines.) (?<match>^(?:[BCFGJKMPR]|[^BCFGJKMPR\n]++)*?(?<group>((Charlie Watts|Bill Wyman|Brian Jones|Mick Jagger|Keith Richards),? )+((?4)(?!(,| and))|and (?4))|((Brian May|Freddie Mercury|Roger Taylor|John Deacon),? )+((?8)(?!(,| and))|and (?8))|((Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon),? )+((?12)(?!(,| and))|and (?12))|((John Lennon|Paul McCartney|Ringo Starr|George Harrison),? )+((?16)(?!(,| and))|and (?16))|((Jeff Lynne|Roy Wood|Bev Bevan),? )+((?20)(?!(,| and))|and (?20))).+?(?<member>\4|\8|\12|\16|\20).*) There may be further optimisations but I will leave that for you to discover. The puzzle description also defined some statistics about the result that you could use to validate your result and hinted that this could be done in SPL. I will leave that part to you as well. Part Eight - Validation Your challenge has not changed, in terms of capturing just three named groups / field for the statements, listed band members and penultimate band member subsequently mentioned, but, in addition, your regular expression should validate that the listed band members are part of the usual, recognised line-up for the classic British rock band in question. Your input has changed, so your expression should be as robust as possible while aiming to reduce the number of bytes used in your expression, and minimising the number of steps required to match against the input. You should aim for fewer than 1,500 bytes and fewer than 20,000 steps. The full list (your puzzle input) can be found here. Forward planning Since the challenge has not changed, we should be able to reuse the same expression, at least for the extraction. The extra element (apart from new data), is that we want to ensure that the extraction only occurs for statements where the list of band members matches the name of the band, For this, the name of the band may come before or after the list of names. This is where positive lookahead comes to the fore. By checking that the band name is followed by a list of the relevant band members, or the band name follows the list of band members, we can restrict the extraction to the correct statements. (?=^(([TEQ]|[^TEQ\n]++)*?((The Rolling Stones)([BCFGJKMPR]|[^BCFGJKMPR\n]++)*?((Charlie Watts|B(?:ill Wyman|rian Jones)|Mick Jagger|Keith Richards),? )+(?:(?7)(?!(,| and))|and (?7))|(Queen)(?5)*?((Brian May|Freddie Mercury|Roger Taylor|John Deacon),? )+(?:(?11)(?!((?8)))|and (?11))|(The Who)(?5)*?((Roger Daltrey|Pete Townshend|John Entwistle|Keith Moon),? )+(?:(?15)(?!((?8)))|and (?15))|(The (Beatles|Fab Four))(?5)*?((John Lennon|Paul McCartney|Ringo Starr|George Harrison),? )+(?:(?20)(?!((?8)))|and (?20))|(E(lectric Light Orchestra|LO))(?5)*?((Jeff Lynne|Roy Wood|Bev Bevan),? )+(?:(?25)(?!((?8)))|and (?25)))|(?5)*?(((?7),? )+(?:(?7)(?!((?8)))|and (?7))((?2))*?(?4)|((?11),? )+(?:(?11)(?!((?8)))|and (?11))((?2))*?(?9)|((?15),? )+(?:(?15)(?!((?8)))|and (?15))((?2))*(?13)|((?20),? )+(?:(?20)(?!((?8)))|and (?20))((?2))*?(?17)|((?25),? )+(?:(?25)(?!((?8)))|and (?25))((?2))*?(?22))))(?<match>^(?5)*?(?<group>(?:((?7)),? )+(?:(?45)(?!(,| and))|and (?45))|(?:((?11)),? )+(?:(?47)(?!(,| and))|and (?47))|(?:((?15)),? )+(?:(?49)(?!(,| and))|and (?49))|(?:((?20)),? )+(?:(?51)(?!(,| and))|and (?51))|(?:((?25)),? )+(?:(?53)(?!(,| and))|and (?53)))(?5)+?(?<member>\45|\47|\49|\51|\53).*) I realise that this looks very complicated, but all the elements of the expression have been covered by earlier parts, e.g. un-named subroutines, back-referencing by number, etc.. To check that the expression performs correctly, you could try altering the input to change one of the band names, for example, if a correctly matched statement is about "The Beatles", change it to "The Who" and make sure it no longer matches, etc. Summary In summary, the key to solving these puzzles is, firstly to break it down into manageable steps and build up from there. From a regular expression point of view, understanding how capture groups work, particularly the fact that only the last capture value can be back-referenced, and how to make ("un-named") subroutine calls is important. The optimisations, in terms of expression length, come from using subroutine calls, and, in terms of steps taken, come from appropriate anchors and quantifiers. Also, the approach outlined here shows that sometimes we need to re-frame the problem to bring a solution into reach. Have questions or thoughts? Comment on this article or in Slack #puzzles channel. Whichever you prefer.
... View more