OraQA

The following is an interesting puzzle posted by Itasofware on the web.

In the game of Ghost , two players take turns building up an English word from left to right.

Each player adds one letter per turn. The goal is to not complete the spelling of a word: if you add a letter that completes a word (of 4+ letters), or if you add a letter that produces a string that cannot be extended into a word, you lose.

Write a program that allows a user to play Ghost against the computer. The computer should play optimally given the following dictionary: WORD.LST.

Allow the human to play first. If the computer thinks it will win, it should play randomly among all its winning moves; if the computer thinks it will lose, it should play so as to extend the game as long as possible (choosing randomly among choices that force the maximal game length).

—————————————————————————————————————————————————-
Here is the strategy for solving this problem: Try to add a letter to the current input string, so that there is only “one word” left in the whole dictionary for your opponent. Once your opponent adds the next letter to the input string, that will complete the spelling of the word.

Solution:
Copy the word.lst from the web to a word.txt file on the database server ( \tmp directory).

create or replace directory tmp as 'C:\oracle\tmp';

CREATE  TABLE words (str VARCHAR2(38))
     ORGANIZATION EXTERNAL
     (
       TYPE ORACLE_LOADER
       DEFAULT DIRECTORY tmp
       ACCESS PARAMETERS
       (
         records delimited by newline
         fields terminated by whitespace
         missing field values are null
         ( str
         )
       )
       LOCATION ('word.txt')
     )
     REJECT LIMIT UNLIMITED;

COLUMN input FORMAT A18
COLUMN destination FORMAT A28
COLUMN next_char   FORMAT A12

variable input varchar2(38)
SQL> exec :input :='tar'

PL/SQL procedure successfully completed.

------------------------------SQL Solution----------------- 

WITH data AS
(SELECT str, length(str) as len, :input as input, length(:input) as in_len,
        case when str like :input||'_'
             then  str
             end as flag_str
 FROM words
 WHERE str LIKE :input||'%' and length(str) >=4
),
flag_data as
(
SELECT flag_str FROM data WHERE flag_str is not null
),
Filter_data as
(
SELECT distinct a.str FROM data a , flag_data b
WHERE substr(a.str, 1, length(b.flag_str)) = b.flag_str
),
Base_data as
(SELECT str, len , in_len, input FROM data
 WHERE str not in ( SELECT str FROM Filter_data)
)
SELECT input, destination, next_char
FROM
(SELECT input, str as destination, substr(str, in_len+1, 1) as next_char
  FROM
 (SELECT a.str, a.len, input, a.in_len,
         case when mod(a.len, 2) = 0 then 1
              else case when  REGEXP_LIKE (a.str, '^'||input||'[[:alpha:]]{2}$')
                        then case when
                                 (SELECT count(*) FROM data
                                  WHERE REGEXP_LIKE (str, '^'||substr(a.str,0,length(a.input)+1)||'[[:alpha:]]{2,}$')
                                  and  not REGEXP_LIKE (str, '^'||a.str||'[[:alpha:]]+$')
                                  ) = 0
                                  then 4
                                  else 3
                             end
                        else  2
                    end
         end as flag
  FROM Base_data a
 ) ORDER BY flag desc , case when flag = 1 then len else 0 end desc
)
WHERE ROWNUM = 1;

INPUT              DESTINATION                  NEXT_CHAR
------------------ ---------------------------- ------------
tar                targe                        g

SQL> exec :input := 'bot'

SQL> /

INPUT              DESTINATION                  NEXT_CHAR
------------------ ---------------------------- ------------
bot                botch                        c

SQL> exec :input := 'aba'

SQL> /

INPUT              DESTINATION                  NEXT_CHAR
------------------ ---------------------------- ------------
aba                abamp                        m

Filed under General, SQL. Follow any responses to this entry through this RSS 2.0 feed.