First of all, thanks to all who posted your solutions (publicly or
privately).
I got solutions from: Steve Kass, Adam Machanic, Rob Farley,
Maciej Pilecki and FoxTrot.
I got two types of solutions:
1. Brute Force method - generating all possible sentences, then filtering only
the ones that are palindromes. This logic allows for a very short and simple
solution query, but is extremely inefficient.
2. Constructing sentences from the edges, going inwards, and this way not
pursuing sentences that are known not to have potential to become
palindromes.
The winners would have to be Adam Machanic, Rob Farley and Steve
Kass;
all three used the second approach.
Here's an example for a solution based on the Brute Force method:
with c as
(
select cast(' ' + word + ' ' as varchar(max)) as sentence
from words
union all
select c.sentence + w.word + ' '
from c join words as w
on c.sentence not like '% ' + w.word + ' %'
)
select rtrim(ltrim(sentence)) as palindrome
from c
where replace(sentence, ' ', '') = reverse(replace(sentence, ' ', ''));
The nice thing about the brute force solution is of course that it's short
and simple. But it's extremely slow.
For n words, the brute force solution generates the following number of
sentences (before the outer query filters palindromes):
n + n*(n-1) + n*(n-1)*(n-2) + ... + n!
To illustrate how big those numbers can be, here's a recursive CTE that
calculates the number of sentences produced out of n unique words:
with c as
(
select
n as words, cast(n as bigint) as sentences,
cast(n as bigint) as v, n-1 as i
from nums -- auxiliary table of numbers
where n = 1
)
select words, sentences
from c where i = 0
order by words;
words sentences
----------- --------------------
1 1
2 4
3 15
4 64
5 325
6 1956
7 13699
8 109600
9 986409
10 9864100
11 108505111
12 1302061344
13 16926797485
14 236975164804
15 3554627472075
16 56874039553216
17 966858672404689
18 17403456103284420
19 330665665962403999
20 6613313319248080000
I think that the brute force solution is a good example to use for teaching
purposes to describe the logic of recursive queries.
As for the more efficient method (constructing sentences from the edges,
going inwards), following are the solutions that I got.
I used the following sample data to test the performance of the solutions:
create table words(word varchar(50) not null primary key);
insert into words values('even');
insert into words values('never');
insert into words values('odd');
insert into words values('or');
insert into words values('r');
insert into words values('e');
insert into words values('n');
insert into words values('er');
insert into words values('madam');
insert into words values('adam');
Solution by Steve Kass (165 ms):
create function ends(
@lft varchar(200),
@rgt varchar(200),
@used varchar(8000)
) returns table as return
with WW(w1word,w1wordX,w2word,w2wordX) as (
select w1.word,@lft+w1.word,w2.word,w2.word+@rgt
from words as w1, words as w2
where substring(@lft+w1.word,1,len(w2.word+@rgt))
= substring(reverse(w2.word+@rgt),1,len(@lft+w1.word))
and (w2.word w1.word)
and @used not like '%\[ *\]'+w1.word+'\[ *\]%'
and @used not like '%\[ *\]'+w2.word+'\[ *\]%'
), T(w,p,good,side,used) as (
select
w1wordX+w2wordX as w,
left(w1wordX,len(w2wordX)) + '.' +
right(w2wordX,len(w1wordX)) as p,
len(substring(w1wordX,1,len(w2wordX))) as good,
sign(len(w2wordX)-len(w1wordX)) as side,
replace(@used,'*',' '+w1word+'*'+w2word+' ') as used
from WW
union all
select
@lft+word+@rgt,
@lft+word+@rgt,
len(@lft+word+@rgt)/2,
0,
replace(@used,'*',' '+word+' ')
from words
where @lft+word+@rgt = reverse(@lft+word+@rgt)
and @used not like '%\[ *\]'+word+'\[ *\]%'
)
select *, substring(w,good+1,len(w)-2*good) as middle from T
go
with S(w,p,good,side,used,middle) as (
select * from ends('','','*')
union all
select E.*
from S
cross apply
ends(
parsename(S.p,2)+case when side=-1 then middle else '' end,
case when side=1 then middle else '' end + parsename(S.p,1),
S.used
) as E
)
select replace(rtrim(ltrim(used)),'*',' ')
from S
where middle = reverse(middle)
go
Steve's description of the solution:
"It first finds single words that are palindromes or pairs of
words that could be the leftmost and rightmost words in a
palindrome, such as "odder do" or "re bracer" For this to
be possible, left(first,minLen) = left(reverse(second),minLen)
where minLen is the minimum length of the two words.
To fill in "odder do" to a palindrome, we need to find words
that fit between odder and do that make a palindrome if
"der" (the unpaired middle) is appended to the left of those
words.
One way to start is by finding all possible single or double
words ending in red and having an appropriate variation of the
property above, so that they still can be extended inward to
a palindrome. For example, inserting "oblate bored" is ok,
because all the new mismatch occurs in oblate. On the other
hand, inserting "cat tarred" does not work, because the
sentence "odder cat tarred do" cannot be made a palindrome
by adding words in the middle. The c and the r will never
match.
The ends() function finds appropriate single or double words
that can take a potential palindrome and make it closer to one
(based on number of characters from each end that match).
I start with nothing, so there is no unmatched @lft or @rgt, nor
@used (which holds used words). That's the base case of the
recursive query. Then for every potential palindrome found,
@lft or @rgt is identified, and @used is, so when ends() is
invoked again, it finds fill-ins for the existing mismatch
in that potential palindrome. Because we need a table of
fill-ins for each potential palindrome, and to do this,
ends() needs information specific to that potential palindrome
(the @lft or @rgt along with the @used string of used words)
a CROSS APPLY is the appropriate way to go.
Once there are no more possible fill-ins, there will be both
incomplete and complete palindromes in the table. The complete
ones are those for which @lft+@rgt is itself a palindrome,
so that ' is a solution for the fill-in, meaning that the
potential palindrome is already a palindrome."
Solution by Adam Machanic (41 ms):
with n as
(
select
convert(varchar(1000), a.word) as parta,
convert(varchar(1000), b.word) as partb,
convert(varchar(1000), a.word) as repparta,
convert(varchar(1000), reverse(b.word)) as reppartb
from words a, words b
where a.word b.word
and ((len(a.word) > len(b.word)
and a.word like reverse(b.word) + '%')
or
(reverse(b.word) like a.word + '%'))
union all
select
convert(varchar(1000),
case
when len(repparta) > len(reppartb) then parta
when len(repparta) len(repparta) then partb
when len(repparta) > len(reppartb) then w.word + ' ' + partb
when p.n = 1 then partb
else w.word + ' ' + partb
end) as partb,
convert(varchar(1000),
replace(case
when len(repparta) > len(reppartb) then parta
when len(repparta) len(repparta) then partb
when len(repparta) > len(reppartb) then w.word + ' ' + partb
when p.n = 1 then partb
else w.word + ' ' + partb
end, ' ', '')))
from n
cross join words w
cross apply
(
select 1
union all
select 2 where len(repparta) = len(reppartb)
) p(n)
where
case when ' ' + parta + ' ' + partb + ' ' not like '% ' + word + ' %'
then
case
when len(repparta) > len(reppartb) then
case
when len(word) > len(repparta)-len(reppartb) then
case when right(word, len(repparta)-len(reppartb)) =
right(repparta, len(repparta)-len(reppartb))
then 1
else 0
end
else
case when word = substring(repparta, len(reppartb)+1,
len(word))
then 1
else 0
end
end
when len(reppartb) > len(repparta) then
case when len(word) > len(reppartb) - len(repparta) then
case when left(word, len(reppartb)-len(repparta)) =
substring(reppartb, len(repparta)+1,
len(reppartb)-len(repparta))
then 1
else 0
end
else
case when word = substring(reppartb, len(repparta)+1,
len(word))
then 1
else 0
end
end
else 1 --equal
end
else 0
end = 1
)
select final
from
(
select distinct
rtrim(ltrim(parta + ' ' + partb)) final
from n
) m
where replace(final, ' ', '') = reverse(replace(final, ' ', ''))
union all
select
word
from words
where word = reverse(word)
Adam's description of the solution:
"Much like the other solutions, the goal here is to build the palindrome
from
the outside in. The anchor part of the recursive CTE finds all pairs in the
words table, then finds the shorter word and uses it in a LIKE predicate
against the longer word. The solution I discovered is to always reverse the
rightmost word/group of words in the list: If the two words are "abcd" and
"cba", the predicate 'abcd' LIKE REVERSE('cba') + '%' is true. Likewise, if
the words are "abc" and "dcba", the predicate REVERSE('dcba') LIKE 'abc' +
'%' is true. Based on these, the anchor part finds potential palindromes.
The recursive part continues this logic in a slightly different way. It
uses a cross-join to the Words table to get all combinations of words with
the input set. The case expression does the following: First, it makes sure
that the given word has not already been used in the input set. Next, it
determines whether the right part or left part is longer. The same basic
logic is used in both cases, so we'll follow the right part being longer.
Assume that the two parts are: "abc" and "dcba". The difference is one
character, and that character is "d". The logic is to append any possible
words onto the left part, so the CASE expression finds all words in this
case that start with the letter "d". There is also a special case for the
differential being longer than the input. For instance, if the two parts
were "abc" and "gfedcba", and the word being compared were "de", that should
be a match. In that case, the expression looks at only as many characters
in the difference as the number of characters in the input word.
Finally, there is a special case for if the two input words are equal in
length. If so, a new row will be generated using the CROSS APPLY operator
(using the correlation name P). If the input set has the parts "abc" and
"cba", the idea is that any possible word could be a seed for a new
palindrome, appended to either the right or left part. So if the lengths are
equal and P.n = 1, the input word is appended to the left part. Otherwise,
it's appended to the right part.
After all of the recursion is done, the outer query does a final check to
determine whether or not each row is a palindrome. This final set is
unioned with any single words in the table that are, themselves, palindromes
(checked using REVERSE)."
Solution by Rob Farley (22 ms):
with pals as
(
--Base
select
cast('' as varchar(max)) as startchars,
cast('' as varchar(max)) as endchars,
cast(' ' as varchar(max)) as startwords,
cast(' ' as varchar(max)) as endwords
union all
--Sides even, so find a suitable word
select
startchars + w.word,
endchars,
startwords + w.word + ' ',
endwords
from pals p cross join words w
where len(p.startchars) = len(p.endchars)
and exists (select * from words w2 where w.word like reverse(w2.word) + '%'
or reverse(w2.word) like w.word + '%')
and startwords not like '% ' + w.word + ' %'
and endwords not like '% ' + w.word + ' %'
union all
--Right longer than left, so find a word for there
select
startchars + w.word,
endchars,
startwords + w.word + ' ',
endwords
from pals p cross join words w
where len(p.startchars) len(p.endchars)
and (w.word like '%' +
reverse(right(startchars,len(startchars)-len(endchars)))
or
reverse(right(startchars,len(startchars)-len(endchars))) like '%' +
w.word)
and startwords not like '% ' + w.word + ' %'
and endwords not like '% ' + w.word + ' %'
)
select rtrim(ltrim(startwords)) + ' ' + rtrim(ltrim(endwords))
from pals
where len(startchars) > 0
and startchars + endchars = reverse(startchars + endchars)
Rob's description of the solution:
"I figure that the best way of approaching this would be to build it up,
looking for words that would fit as candidates for being added to the start
or end of my palindromes. I wanted to have a space-separated word list as
well as a spaces-removed word list - one is good for both presentation at
the end and checking for unique words, the other is good for actually making
sure that the palindrome is being built correctly.
So taking the 'build it up' approach, a CTE seemed the way to go. I put a
starting scenario in which was to have an empty string at the start and end.
I was originally planning to remove this entry once the CTE was done, but
then later decisions changed my mind for me.
I figured I had three states that I could find myself in. One was when the
string holding the start of the palindrome was longer than the string
holding the end, another was when the string holding the end was longer than
the start, and the third state was when they were the same length. This
could then form a foundation for building the CTE (which I will come to in
the next paragraph). Once the CTE was built, I could filter out the working
lines - which were those ones where the result wasn't a palindrome, and the
base (empty) entry.
So when one string was longer than the other, I wanted to add a word to the
other side. This word had to be a candidate, so that if the difference
between the start-part and end-part was 'never' in the end-part, I could add
any word to the start-part that matched 'reven%', or was one of 'r', 're',
'rev', 'reve' (which translates into: 'reven' like word + '%'). Similar
logic would apply to the end. If the sides were even, I would have to find a
word for which there was candidate for the other side. So I wouldn't pick
'never' for the end-part if there wasn't a word that I would be able to
populate in the next step. I figured I could probably just throw in any word
here and the algorithm would still be valid (because it would get discarded
as a candidate later), but I included it anyway, thinking that it would be
good to get rid of bad candidates earlier.
Regardless of what state I was in, I also had to make sure I hadn't already
used the word, which is why lines like
startwords not like '% ' + w.word + ' %'
--keep appearing everywhere.
The fact that I wanted to cater for when I had the same length string on
both sides influenced me to leave the base case in there as an empty string.
Otherwise I would need to have a base which queried the words table for
candidate words, and that didn't really appeal to me all that much. And I
wasn't really looking for the fastest way of doing it, I was just looking
for a way of doing it.
And that's about it really... I just built the palindromes from the outside
in, populating a CTE, which I then queried to make sure that I only returned
completed palindromes."
And here's the solution that I came up with (267 ms):
with c as
(
select
cast(word as varchar(max)) as st,
cast('' as varchar(max)) as ed,
0 as consider
from words
where word = reverse(word)
union all
select
' ' + w1.word + ' ',
w2.word + ' ',
1
from words as w1
join words as w2
on w1.word w2.word
where w1.word like reverse(w2.word) + '%'
or reverse(w2.word) like w1.word + '%'
union all
select
st + word + ' ',
ed,
0
from c join words
on consider = 1
and st + ed not like '% ' + word + ' %'
where replace(st + word + ed, ' ', '') =
reverse(replace(st + word + ed, ' ', ''))
union all
select st + w1.word + ' ', w2.word + ' ' + ed, 1
from c
join words as w1
on consider = 1
and st + ed not like '% ' + w1.word + ' %'
join words as w2
on w1.word w2.word
and st + ed not like '% ' + w2.word + ' %'
where replace(st, ' ', '') + w1.word like
reverse(w2.word + replace(ed, ' ', '')) + '%'
or reverse(w2.word + replace(ed, ' ', '')) like
replace(st, ' ', '') +
w1.word + '%'
)
select ltrim(rtrim(st + ed)) as palindrome
from c
where replace(st + ed, ' ', '') = reverse(replace(st + ed, ' ', ''));
The logic in my solution is similar to the others who did not use the brute
force method.
The first CTE query (non recursive) simply isolates the single words that are
palindromes.
The second CTE query (also non recursive) generates two parts of sentences
(start part and end part) out of pairs of words that are either palindromes or
have potential to become palindromes. Start and end pairs have potential to
become a palindrome if start begins with the reverse of end, or the reverse of
end begins with the start.
The third CTE query (recursive) adds a word between start and end
only for words that do not yet appear in the sentence, and make the sentence
a palindrome.
The fourth CTE query (recursive) adds a pair of words; one after the start
and
one before the end, only in cases that become palindromes or have the
potential to become palindromes.
Cheers,
--
BG
