I’ve continued to enjoy this little puzzle and trying to find different ways of solving it. I’ve used the CONNECT BY clause to unpivot words into lists of letters but in this article I’ll show a more direct recursion on the word and then wrap up the series with the smallest and most efficient solution.
First, a recursive technique using CONNECT BY.
I’ll use TRANSLATE to map each letter to its corresponding hand and then recursively check if each letter alternates hands from the previous one. On the first repeat of a hand, the recursion stops and the search ends for that word. Finding words ending with the left hand is achieved with a simple LIKE condition (WHERE hand LIKE ‘%L’.)
SELECT word,
len,
LEVEL lvl,
hand
FROM (SELECT word,
LENGTH(word) len,
TRANSLATE(word, 'qwertasdfgzxcvb yuiophjklnm', 'LLLLLLLLLLLLLLL RRRRRRRRRRR') hand
FROM words)
WHERE hand LIKE '%L'
CONNECT BY word = PRIOR word
AND LEVEL <= len
AND (LEVEL = 1 OR SUBSTR(hand, LEVEL - 1, 2) IN ('RL', 'LR'))
AND PRIOR SYS_GUID() IS NOT NULL;
This parses words into a series like this:
WORD LEN LVL HAND --------- ---- ----- --------- aid 3 1 LRL aid 3 2 LRL aid 3 3 LRL baklava 7 1 LLRRLLL chair 5 1 LRLRL chair 5 2 LRLRL chair 5 3 LRLRL chair 5 4 LRLRL chair 5 5 LRLRL purchase 8 1 RRLLRLLL
Finding words that alternate from the first to the last letter is then just a matter of pulling rows where the level reaches the length of the word. In the example above that would be aid and chair, dropping baklava and purchase.
SELECT word
FROM ( SELECT word, len, LEVEL lvl
FROM (SELECT word,
LENGTH(word)
len,
TRANSLATE(
word,
'qwertasdfgzxcvb yuiophjklnm',
'LLLLLLLLLLLLLLL RRRRRRRRRRR'
)
hand
FROM words)
WHERE hand LIKE '%L'
CONNECT BY word = PRIOR word
AND LEVEL <= len
AND (LEVEL = 1 OR SUBSTR(hand, LEVEL - 1, 2) IN ('RL', 'LR'))
AND PRIOR SYS_GUID() IS NOT NULL)
WHERE lvl = len;
That works pretty well. While connect by can be somewhat cpu and memory intensive, I do like the searching has an early exit when a word repeats a hand unlike previously explored methods.
The next, perhaps obvious, method to try is a recursive sub-query factoring clause (WITH clause.) The syntax changes but the logic of the recursion is essentially the same. Translate the letters to hand, for each letter check if it alternates from the previous hand or not. If the hands alternate then continue, if they do not, then end early for that word. Keep only those rows where the counter reaches the length of the word.
WITH
translated(word, hand)
AS
(SELECT word,
TRANSLATE(word,
'qwertasdfgzxcvb yuiophjklnm',
'LLLLLLLLLLLLLLL RRRRRRRRRRR') hand
FROM words),
x(word, hand, n)
AS
(SELECT word, hand, 1
FROM translated
WHERE hand LIKE '%L'
UNION ALL
SELECT word, hand, n + 1
FROM x
WHERE SUBSTR(hand, n, 2) IN ('RL', 'LR'))
SELECT word
FROM x
WHERE n = LENGTH(word);
It’s slightly more cumbersome syntax but I think it’s an easier read for those new to the syntax compared to the CONNECT BY. It also doesn’t require any special tricks like the SYS_GUID() to properly connect children of each word.
And finally, while I have enjoyed playing around with syntax to find different methods to solve the same original question, all of them are unnecessarily complex. The two answers above provide a hint as to the direction I would go if I had to implement this in production instead of just for academic curiosity.
First, simply translate the letters to hands and then check if the resulting “word” was of the form LRLR…RL or RLRL…RL. That is, does it alternate with RL (so it ends with an L) and possibly start with an L?
So, a single call to translate and a regular expression filter provides the answer, both simply and efficiently.
SELECT word
FROM (SELECT word, TRANSLATE(word,
'qwertasdfgzxcvb yuiophjklnm',
'LLLLLLLLLLLLLLL RRRRRRRRRRR') hand
FROM words)
WHERE REGEXP_LIKE(hand, '^L?(RL)*
If you have an older version of the database that doesn’t support regular expressions, or if you wanted to port this puzzle and answer to non-Oracle systems. Then you can simply construct an alternating word using padding functions. Remember to check both right and left starting letters in the alternating.
This is slightly more complex than using REGEXP_LIKE; but this version should be supported back to at least version 7.3.
SELECT word
FROM (SELECT word,
TRANSLATE(word, 'qwertasdfgzxcvb yuiophjklnm', 'LLLLLLLLLLLLLLL RRRRRRRRRRR') hand
FROM wordlist)
WHERE hand LIKE '%L'
AND hand IN ('L' || RPAD('RL', LENGTH(word) - 1, 'RL'), RPAD('RL', LENGTH(word), 'RL'));
I hope you enjoyed this little exercise as much as I have. Thank you for reading!