46 lines
1.5 KiB
Plaintext
46 lines
1.5 KiB
Plaintext
CREATE OR REPLACE FUNCTION matches(block, letter) as (
|
|
block[1] = letter or block[2] = letter
|
|
);
|
|
|
|
# permute(lst, n, word) generates sub-permutations, perm (of length n), of the list lst,
|
|
# that satisfy matches(perm[i], word[i]), for i in range(1, n+1).
|
|
# Normally n = length(word).
|
|
# The caller is responsible for ensuring appropriate adjustment of typographical case.
|
|
CREATE OR REPLACE FUNCTION permute(lst, n, word) as table (
|
|
WITH RECURSIVE permute(perm, remaining) as (
|
|
-- base case
|
|
SELECT
|
|
[]::VARCHAR[] as perm,
|
|
lst::VARCHAR[] as remaining
|
|
UNION ALL
|
|
-- recursive case: add one element from remaining to perm and remove it from remaining
|
|
SELECT
|
|
(perm || [element]) AS perm,
|
|
(remaining[1:i-1] || remaining[i+1:]) AS remaining
|
|
FROM (select *, unnest(remaining) AS element, generate_subscripts(remaining,1) as i
|
|
FROM permute)
|
|
WHERE length(perm) < n
|
|
and matches(element, word[1 + length(perm)])
|
|
)
|
|
SELECT perm
|
|
FROM permute
|
|
WHERE length(perm) = n
|
|
);
|
|
|
|
# All solutions
|
|
CREATE OR REPLACE FUNCTION solve(word) as table (
|
|
from permute(
|
|
['BO', 'XK', 'DQ', 'CP', 'NA', 'GT', 'RE', 'TG', 'QD', 'FS',
|
|
'JW', 'HU', 'VI', 'AN', 'OB', 'ER', 'FS', 'LY', 'PC', 'ZM'],
|
|
length(word), upper(word) )
|
|
);
|
|
|
|
CREATE OR REPLACE FUNCTION one_solution(word) as (
|
|
from solve(word)
|
|
limit 1
|
|
);
|
|
|
|
# Examples
|
|
select word, one_solution(word)
|
|
from (select unnest(['','A','BarK','BOOK','TREAT','COMMON','SQUAD','Confuse','abba']) as word);
|