[QUIZ] Crossword Solver (#132)

ruby-talk
1

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

···

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Eugene Kalenkovich

Write a Ruby crossword solver. Randomly fill a crossword template with words
from a dictionary. Use any dictionary you want (/usr/share/dict/words, text of
pickaxe, etc.).

Template is provided in a file formatted very similarly to one in quiz #10
(http://www.rubyquiz.com/quiz10.html), with "X" substituted with "#". Simple
template example:

   _ _ _ _ _
   
   _ # _ # _
   
   _ _ _ _ _
   
   _ # _ # _
   
   _ _ _ _ _

Format output any way you want, just make it readable. Each run of the program
with big enough dictionary should give a different solution. Example results for
a simple template:

   F U G U E
   
   U U R
   
   D E I G N
   
   G D S
   
   E J E C T
   
   R E S T S
   
   I K T
   
   N I E C E
   
   D W E
   
   S U S A N

Bonus 1 (simple). Allow partially pre-filled templates:

   # # _ # # # # M
   
   _ _ _ _ _ _ # A
   
   # # _ # # _ # T
   
   R U B Y Q U I Z
   
   U # _ # # _ # #
   
   B # _ _ _ _ _ _
   
   Y # # # # _ # #

One of result variants:

       U M
   
   P A S C A L A
   
       A O T
   
   R U B Y Q U I Z
   
   U L N
   
   B Y E A G E R
   
   Y E

Bonus 2: Avoid combinatorial explosion. Fill a big template within reasonable
time:

   _ _ _ _ # _ _ _ _ _ _ _ _ _ # _ _ _ _
   
   _ # _ # _ # _ # _ # _ # _ # _ # _ # _
   
   _ _ _ _ _ _ _ _ _ # _ _ _ _ _ _ _ _ _
   
   _ # _ # _ # _ # _ _ _ # _ # _ # _ # _
   
   # _ _ _ _ # _ # _ # _ # _ # _ _ _ _ #
   
   _ # _ # # # _ _ _ _ _ _ _ # # # _ # _
   
   _ _ _ _ _ _ # # _ # _ # # _ _ _ _ _ _
   
   _ # _ # # _ # _ _ _ _ _ # _ # # _ # _
   
   _ _ _ _ _ _ _ _ # _ # _ _ _ _ _ _ _ _
   
   _ # # _ # _ # _ _ _ _ _ # _ # _ # # _
   
   _ _ _ _ _ _ _ _ # _ # _ _ _ _ _ _ _ _
   
   _ # _ # # _ # _ _ _ _ _ # _ # # _ # _
   
   _ _ _ _ _ _ # # _ # _ # # _ _ _ _ _ _
   
   _ # _ # # # _ _ _ _ _ _ _ # # # _ # _
   
   # _ _ _ _ # _ # _ # _ # _ # _ _ _ _ #
   
   _ # _ # _ # _ # _ _ _ # _ # _ # _ # _
   
   _ _ _ _ _ _ _ _ _ # _ _ _ _ _ _ _ _ _
   
   _ # _ # _ # _ # _ # _ # _ # _ # _ # _
   
   _ _ _ _ # _ _ _ _ _ _ _ _ _ # _ _ _ _
   
   C H A O L E N I E N T L Y C O I L
   
   Y V L M D O E O K A
   
   S H A R E A B L E O E D I P A L L Y
   
   T I A R N U N G E A S
   
     F L I P Y T T E C O H N
   
   I A O L I V I E R O I
   
   R E B U F F F M A S H M A N
   
   R L A B Y T E S D A T
   
   I N E R T I A L Y I S S U A N C E
   
   T U R A S P E N O D N
   
   A L T E R E R S E U P R O O T E D
   
   T O S E A S E S B O I
   
   E X T A N T B N S U N T A N
   
   S T U T R E C H T A G
   
     W E E P N A L R D E L L
   
   P R U T M A O U A L M
   
   R E I N S E R T S S O M E W H E R E
   
   O N H U O E A N R A
   
   S A G S B E R N A D I N E U S E D

2

Where can I get a file with the dictionary list? I would rather not
have to make my own.

···

--
Posted via http://www.ruby-forum.com/.

3

Hi,

Here's my solution: http://pastie.caboo.se/83230

I've been inspired by Eric I.'s solution to the Verbal Arithmetic Ruby Quiz
(http://rubyquiz.com/quiz128.html): divide the problem into steps, solve
each step in turn, backtrack if you're stuck. Things are a lot simpler
though for this case than for the Verbal Arithmetic case, since there are
less different types of step to consider for the Crossword case.

Some examples using /usr/share/dict/words as dictionary (1.cw, 2.cw
and 3.cwcontain the 3 given crossword definitions):

$ ./rq132_crosswordsolver_rafc.rb 1.cw
INNER
N#O#E
CRUMB
A#N#E
SISAL
(Solution found in 0.042307 seconds.)

$ ./rq132_crosswordsolver_rafc.rb 2.cw
##D####M
CLOSES#A
##U##T#T
RUBYQUIZ
U#L##C##
B#ERECTS
Y####O##
(Solution found in 0.029773 seconds.)

$ ./rq132_crosswordsolver_rafc.rb 3.cw
CLUE#OLIGOCENE#ODER
A#N#S#I#L#H#A#O#I#E
PARAMECIA#ENVISAGED
E#U#U#K#DIN#I#L#E#S
#SLOG#E#I#I#E#OHSA#
W#I###DOODLES###T#C
HYENAS##L#L##RETINA
O#S##E#SINEW#E##O#T
OUTREACH#A#INSIGNIA
S##E#L#ATOLL#O#I##L
HEADBAND#M#MALAGASY
I#M##N#ERICA#V##N#Z
NOUGAT##O#A##EXCITE
G#S###ESTELLA###M#S
#WINE#N#T#L#G#WAIF#
I#N#L#K#ELI#A#I#S#V
DIGESTION#POSTNATAL
E#L#A#D#E#E#S#E#I#A
SAYS#GUARDRAIL#SCAD
(Solution found in 0.575114 seconds.)

For this last case, the runtime is usually under a second, but I must admit
that it can wildly fluctuate and sometimes takes minutes to find a solution.

Regards,
Raf

4

Ruby Quiz wrote:

Write a Ruby crossword solver. Randomly fill a crossword template with words
from a dictionary. Use any dictionary you want (/usr/share/dict/words, text of
pickaxe, etc.).

This solution requires Gecode/R ( http://gecoder.rubyforge.org/ ).

== Overview

The problem is modelled as a matrix of cells where each cell can be
assigned a number representing the letters a..z and #. The letters are
converted to integers in order to use integer variables to represent
them. Similarly each word is converted to a base 26 number with the
converted letters as digits. Hence allowing the words to be represented
as integers as well.

The constraint that sequences of cells longer than one letter must form
words is then added by constraining that the linear combination of the
involved cells forming the corresponding base 26 number, with each
variable as one digit, must be equal to one of the words converted to a
number.

== Weaknesses

It has two major problems
* The words converted to numbers have to fit in the range of an integer
variable, which only allows words of up to 6 characters in my case. This
can probably be helped by using multiple numbers to represent each word.
* There's no randomness in the exploration. Gecode itself does support
custom branching (which would allow such randomness), but Gecode/R does not.

In some cases the exploration will take a long time. I'm unsure whether
it's because of flaws in the model or because of the problem's difficulty.

== Code

require 'enumerator'
require 'rubygems'
require 'gecoder'

# The base we use when converting words to and from numbers.
BASE = ('a'..'z').to_a.size
# The offset of characters compared to digits in word-numbers.
OFFSET = 'a'[0]
# The range of integers that we allow converted words to be in. We are
# only using the unsigned half, we could use both halves, but it would
complicate
# things without giving a larger allowed word length.
ALLOWED_INT_RANGE = 0..Gecode::Raw::Limits::Int::INT_MAX
# The maximum length of a word allowed.
MAX_WORD_LENGTH = (Math.log(ALLOWED_INT_RANGE.last) /
  Math.log(BASE)).floor

# Describes an immutable dictionary which represents all contained words
# as numbers of base BASE where each digit is the corresponding letter
# itself converted to a number of base BASE.
class Dictionary
  # Creates a dictionary from the contents of the specified dictionary
  # file which is assumed to contain one word per line and be sorted.
  def initialize(dictionary_location)
    @word_arrays =
    File.open(dictionary_location) do |dict|
      previous_word = nil
      dict.each_line do |line|
        word = line.chomp.downcase
        # Only allow words that only contain the characters a-z and are
        # short enough.
        next if previous_word == word or word.size > MAX_WORD_LENGTH or
          word =~ /[^a-z]/
        (@word_arrays[word.length] ||= ) << self.class.s_to_i(word)
        previous_word = word
      end
    end
  end

  # Gets an enumeration containing all numbers representing word of the
  # specified length.
  def words_of_size(n)
    @word_arrays[n] ||
  end

  # Converts a string to a number of base BASE (inverse of #i_to_s ).
  def self.s_to_i(string)
    string.downcase.unpack('C*').map{ |x| x - OFFSET }.to_number(BASE)
  end

  # Converts a number of base BASE back to the corresponding string
  # (inverse of #s_to_i ).
  def self.i_to_s(int)
    res =
    loop do
      digit = int % BASE
      res << digit
      int /= BASE
      break if int.zero?
    end
    res.reverse.map{ |x| x + OFFSET }.pack('C*')
  end
end

class Array
  # Computes a number of the specified base using the array's elements
  # as digits.
  def to_number(base = 10)
    inject{ |result, variable| variable + result * base }
  end
end

# Models the solution to a partially completed crossword.
class Crossword < Gecode::Model
  # The template should take the format described in RubyQuiz #132 . The
  # words used are selected from the specified dictionary.
  def initialize(template, dictionary)
    @dictionary = dictionary

    # Break down the template and create a corresponding square matrix.
    # We let each square be represented by integer variable with domain
    # -1...BASE where -1 signifies # and the rest signify letters.
    squares = template.split(/\n\s*\n/).map!{ |line| line.split(' ') }
    @letters = int_var_matrix(squares.size, squares.first.size,
      -1...BASE)

    # Do an initial pass, filling in the prefilled squares.
    squares.each_with_index do |row, i|
      row.each_with_index do |letter, j|
        unless letter == '_'
          # Prefilled letter.
          @letters[i,j].must == self.class.s_to_i(letter)
        end
      end
    end

    # Add the constraint that sequences longer than one letter must form
    # words. @words will accumelate all word variables created.
    @words =
    # Left to right pass.
    left_to_right_pass(squares, @letters)
    # Top to bottom pass.
    left_to_right_pass(squares.transpose, @letters.transpose)

    branch_on wrap_enum(@words), :variable => :largest_degree,
      :value => :min
  end

  # Displays the solved crossword in the same format as shown in the
  # quiz examples.
  def to_s
    output =
    @letters.values.each_slice(@letters.column_size) do |row|
      output << row.map{ |x| self.class.i_to_s(x) }.join(' ')
    end
    output.join("\n\n").upcase.gsub('#', ' ')
  end

  private

  # Parses the template from left to right, line for line, constraining
  # sequences of two or more subsequent squares to form a word in the
  # dictionary.
  def left_to_right_pass(template, variables)
    template.each_with_index do |row, i|
      letters =
      row.each_with_index do |letter, j|
        if letter == '#'
          must_form_word(letters) if letters.size > 1
          letters =
        else
          letters << variables[i,j]
        end
      end
      must_form_word(letters) if letters.size > 1
    end
  end

  # Converts a word from integer form to string form, including the #.
  def self.i_to_s(int)
    if int == -1
      return '#'
    else
      Dictionary.i_to_s(int)
    end
  end

  # Converts a word from string form to integer form, including the #.
  def self.s_to_i(string)
    if string == '#'
      return -1
    else
      Dictionary.s_to_i(string)
    end
  end

  # Constrains the specified variables to form a word contained in the
  # dictionary.
  def must_form_word(letter_vars)
    raise 'The word is too long.' if letter_vars.size > MAX_WORD_LENGTH
    # Create a variable for the word with the dictionary's words as
    # domain and add the constraint.
    word = int_var @dictionary.words_of_size(letter_vars.size)
    letter_vars.to_number(BASE).must == word
    @words << word
  end
end

puts 'Reading the dictionary...'
dictionary = Dictionary.new(ARGV.shift || '/usr/share/dict/words')
puts 'Please enter the template (end with ^D)'
template = ''
loop do
  line = $stdin.gets
  break if line.nil?
  template << line
end
puts 'Building the model...'
model = Crossword.new(template, dictionary)
puts 'Searching for a solution...'
puts((model.solve! || 'Failed').to_s)

__END__

···

--
Andreas Launila

5

"Ruby Quiz" <james@grayproductions.net> wrote in message

Write a Ruby crossword solver. Randomly fill a crossword template with
words
from a dictionary. Use any dictionary you want (/usr/share/dict/words,
text of
pickaxe, etc.).

My solution, slightly optimized for performance version of the code that was
used originally to generate examples for this quiz:

class CrossTempl
  def initialize(templ)
    @tmpl=templ.collect { |line| line.split(//) }
    @words=
    @tmpl.each_index do |i|
      @tmpl[i].each_with_index do |char, j|
        if char!='#'
          if (j==0||@tmpl[i][j-1]=='#') && !@tmpl[i][j+1].nil? &&
@tmpl[i][j+1]!='#'
            @words << [i,j,0] if self.template(i,j,0).include?('_')
          end
          if (i==0||@tmpl[i-1][j]=='#') && !@tmpl[i+1].nil? &&
@tmpl[i+1][j]!='#'
            @words << [i,j,1] if self.template(i,j,1).include?('_')
          end
        end
      end
    end
    @words.sort! {|a,b| a[0]+a[1]<=>b[0]+b[1]}
  end

  def template(i,j,dir)
    str=''
    chr=@tmpl[i][j]
    while !chr.nil? && chr!='#'
      str<<chr
      i+=dir
      j+=1-dir
      break if @tmpl[i].nil?
      chr=@tmpl[i][j]
    end
    str
  end

  def (idx)
    ar=@words[idx]
    return nil if ar.nil?
    template(ar[0],ar[1],ar[2])
  end

  def =(idx,word)
    ar=@words[idx]
    i=ar[0]; j=ar[1];
    word.split(//).each do |chr|
      @tmpl[i][j]=chr
      i+=ar[2]
      j+=1-ar[2]
    end
  end

  def to_s
    @tmpl.each do |line|
      lstr=line.to_s
      puts lstr.gsub(/#/,' ').gsub(/(.)/) {"#{$&} "}
    end
  end

end

$words=
File.open("/usr/share/dict/words") {|f| f.readlines}.each do |word|
  w=word.upcase.delete("^A-Z")
  l=w.length
  $words[l]||=
  $words[l]<<w
end
$words.each {|ar| ar.uniq! if ar }

tfile=ARGV[0]
if tfile.nil?
  STDERR.puts "please provide a template file"
  exit 1
end

tmpl=File.read(tfile).split(/\n/).collect{|line| line.gsub(/\s/,'').upcase}
$ct=CrossTempl.new(tmpl)

def findWord(i)
  pattern=$ct[i]
  return true if pattern.nil?
  choices=$words[pattern.length].grep(/\A#{pattern.tr("_", ".")}\Z/).sort_by
{ rand }
  until choices.empty?
    guess=choices.pop
    $ct[i]=guess
    puts $ct
    return true if findWord(i+1)
    break if i>0 && rand(2)==1 # fighting incorrect word sorting
                               # by un-ballancing search
  end
  $ct[i]=pattern
  return false
end

if findWord(0)
  puts $ct
else
  puts "O-ops"
end

6

Ruby Quiz <james@grayproductions.net> writes:

by Eugene Kalenkovich

Write a Ruby crossword solver. Randomly fill a crossword template with words
from a dictionary. Use any dictionary you want (/usr/share/dict/words, text of
pickaxe, etc.).

# A simple, stupid and not very efficient recursive depth-first
# solver, written using regular expressions.

···

#
# 28jul2007 +chris+

# Transpose a string
def flip(str)
  str.split("\n").map { |s| s.split(//) }.transpose.map { |s| s.join }.join("\n")
end

def wordlist(crossword)
  sizes = ( crossword .scan(/[A-Z]*_[A-Z_]+/) +
           flip(crossword).scan(/[A-Z]*_[A-Z_]+/)).
    map { |w| w.size }.uniq - [1]

  print "Gathering words... "
  all_words = File.read("/usr/share/dict/words").
    split("\n"). # save a chomp
    reject! { |w| not sizes.include?(w.size) }.
    map! { |w| w.upcase }
  puts "found #{all_words.size}"

  all_words
end

def solve(crossword, words=wordlist(crossword), flipped=false)
  # Is there a word to be filled?
  if crossword =~ /([A-Z]*_[A-Z_]+)/
    words.grep(Regexp.new("\\A#{$1.tr('_', '.')}\\z")).
      sort_by { rand }. # faster results
      each { |fit|
        solve flip(crossword.sub(/[A-Z]*_[A-Z_]+/, fit)), words, !flipped
    }
  elsif flip(crossword) =~ /([A-Z]*_[A-Z_]+)/
    solve(flip(crossword), words, !flipped)
  elsif crossword !~ /_/ # fully filled?
    crossword = flip(crossword) if flipped
    puts crossword
    puts
  end
end

def clean(crossword)
  crossword.delete(" \t").gsub(/\n{2,3}/, "\n")
end

# Test data

cw = <<EOF
   _ _ _ _ _
   
   _ # _ # _
   
   _ _ _ _ _
   
   _ # _ # _
   
   _ _ _ _ _
EOF

cw2 = <<EOF
   # # _ # # # # M
   
   _ _ _ _ _ _ # A
   
   # # _ # # _ # T
   
   R U B Y Q U I Z
   
   U # _ # # _ # #
   
   B # _ _ _ _ _ _
   
   Y # # # # _ # #
EOF

# Good luck with this one...
cw3 = <<EOF
   _ _ _ _ # _ _ _ _ _ _ _ _ _ # _ _ _ _
   
   _ # _ # _ # _ # _ # _ # _ # _ # _ # _
   
   _ _ _ _ _ _ _ _ _ # _ _ _ _ _ _ _ _ _
   
   _ # _ # _ # _ # _ _ _ # _ # _ # _ # _
   
   # _ _ _ _ # _ # _ # _ # _ # _ _ _ _ #
   
   _ # _ # # # _ _ _ _ _ _ _ # # # _ # _
   
   _ _ _ _ _ _ # # _ # _ # # _ _ _ _ _ _
   
   _ # _ # # _ # _ _ _ _ _ # _ # # _ # _
   
   _ _ _ _ _ _ _ _ # _ # _ _ _ _ _ _ _ _
   
   _ # # _ # _ # _ _ _ _ _ # _ # _ # # _
   
   _ _ _ _ _ _ _ _ # _ # _ _ _ _ _ _ _ _
   
   _ # _ # # _ # _ _ _ _ _ # _ # # _ # _
   
   _ _ _ _ _ _ # # _ # _ # # _ _ _ _ _ _
   
   _ # _ # # # _ _ _ _ _ _ _ # # # _ # _
   
   # _ _ _ _ # _ # _ # _ # _ # _ _ _ _ #
   
   _ # _ # _ # _ # _ _ _ # _ # _ # _ # _
   
   _ _ _ _ _ _ _ _ _ # _ _ _ _ _ _ _ _ _
   
   _ # _ # _ # _ # _ # _ # _ # _ # _ # _
   
   _ _ _ _ # _ _ _ _ _ _ _ _ _ # _ _ _ _
EOF

solve(clean(cw2))

--
Christian Neukirchen <chneukirchen@gmail.com> http://chneukirchen.org

7

Here is my solution: http://pastie.caboo.se/83905

This took a bit longer to finish than expected (apparently I need more
practice with these types of problems), but it was fun to put together and I
was pleased to write a fairly elegant solve method, once a framework was in
place. Anyway, this solution does work for partial puzzles (bonus 1), but is
fairly slow (no bonus 2).

Some example output:

crossword_solver.rb linux.words.txt test_board.txt

C E L I A

H # U # C

A S C O T

N # K # E

T O Y E D

Here is a link to all of the files, if anyone is interested:

Thanks,

Justin

···

On 7/27/07, Ruby Quiz <james@grayproductions.net> wrote:

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz
until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby Talk follow the discussion. Please reply to the original quiz
message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Eugene Kalenkovich

Write a Ruby crossword solver. Randomly fill a crossword template with
words
from a dictionary. Use any dictionary you want (/usr/share/dict/words,
text of
pickaxe, etc.).

Template is provided in a file formatted very similarly to one in quiz #10
(http://www.rubyquiz.com/quiz10.html\), with "X" substituted with "#".
Simple
template example:

         _ _ _ _ _

         _ # _ # _

         _ _ _ _ _

         _ # _ # _

         _ _ _ _ _

Format output any way you want, just make it readable. Each run of the
program
with big enough dictionary should give a different solution. Example
results for
a simple template:

         F U G U E

         U U R

         D E I G N

         G D S

         E J E C T

         R E S T S

         I K T

         N I E C E

         D W E

         S U S A N

Bonus 1 (simple). Allow partially pre-filled templates:

         # # _ # # # # M

         _ _ _ _ _ _ # A

         # # _ # # _ # T

         R U B Y Q U I Z

         U # _ # # _ # #

         B # _ _ _ _ _ _

         Y # # # # _ # #

One of result variants:

             U M

         P A S C A L A

             A O T

         R U B Y Q U I Z

         U L N

         B Y E A G E R

         Y E

Bonus 2: Avoid combinatorial explosion. Fill a big template within
reasonable
time:

         _ _ _ _ # _ _ _ _ _ _ _ _ _ # _ _ _ _

         _ # _ # _ # _ # _ # _ # _ # _ # _ # _

         _ _ _ _ _ _ _ _ _ # _ _ _ _ _ _ _ _ _

         _ # _ # _ # _ # _ _ _ # _ # _ # _ # _

         # _ _ _ _ # _ # _ # _ # _ # _ _ _ _ #

         _ # _ # # # _ _ _ _ _ _ _ # # # _ # _

         _ _ _ _ _ _ # # _ # _ # # _ _ _ _ _ _

         _ # _ # # _ # _ _ _ _ _ # _ # # _ # _

         _ _ _ _ _ _ _ _ # _ # _ _ _ _ _ _ _ _

         _ # # _ # _ # _ _ _ _ _ # _ # _ # # _

         _ _ _ _ _ _ _ _ # _ # _ _ _ _ _ _ _ _

         _ # _ # # _ # _ _ _ _ _ # _ # # _ # _

         _ _ _ _ _ _ # # _ # _ # # _ _ _ _ _ _

         _ # _ # # # _ _ _ _ _ _ _ # # # _ # _

         # _ _ _ _ # _ # _ # _ # _ # _ _ _ _ #

         _ # _ # _ # _ # _ _ _ # _ # _ # _ # _

         _ _ _ _ _ _ _ _ _ # _ _ _ _ _ _ _ _ _

         _ # _ # _ # _ # _ # _ # _ # _ # _ # _

         _ _ _ _ # _ _ _ _ _ _ _ _ _ # _ _ _ _

         C H A O L E N I E N T L Y C O I L

         Y V L M D O E O K A

         S H A R E A B L E O E D I P A L L Y

         T I A R N U N G E A S

           F L I P Y T T E C O H N

         I A O L I V I E R O I

         R E B U F F F M A S H M A N

         R L A B Y T E S D A T

         I N E R T I A L Y I S S U A N C E

         T U R A S P E N O D N

         A L T E R E R S E U P R O O T E D

         T O S E A S E S B O I

         E X T A N T B N S U N T A N

         S T U T R E C H T A G

           W E E P N A L R D E L L

         P R U T M A O U A L M

         R E I N S E R T S S O M E W H E R E

         O N H U O E A N R A

         S A G S B E R N A D I N E U S E D

8

Here is my solution. :smiley:

http://pastie.caboo.se/83968

I think there is still a little bug in which search cycles, but it's
highly improbable (got it once in ~50 runs) Will try to fix it.

···

On Jul 27, 8:10 am, Ruby Quiz <ja...@grayproductions.net> wrote:

The three rules of Ruby Quiz:

9

Not sure where this is on linux, and no idea if something like this even
exists on windows.
Chris

···

On 7/27/07, Lloyd Linklater <lloyd@2live4.com> wrote:

Where can I get a file with the dictionary list? I would rather not
have to make my own.
--
Posted via http://www.ruby-forum.com/\.

If you're on a mac, cat /usr/share/dict/words

10

Where can I get a file with the dictionary list? I would
rather not have to make my own.

http://wordlist.sourceforge.net/ is a good resource, especially if
you're on Windows and don't have /usr/share/dict/words

- donald

11

Lloyd Linklater wrote:

Where can I get a file with the dictionary list? I would rather not have to make my own.

/usr/share/dict/words on most any *NIX.

12

Andreas Launila wrote:

Ruby Quiz wrote:

Write a Ruby crossword solver. Randomly fill a crossword template with words
from a dictionary. Use any dictionary you want (/usr/share/dict/words, text of
pickaxe, etc.).

This solution requires Gecode/R ( http://gecoder.rubyforge.org/ ).

I thought I would update this solution to use the recently introduced
tuple constraints. The updated version no longer has a limitation on
word-lengths and seems to scale well with both the template size and
dictionary size.

The model is almost the same as before. Each square is represented by an
integer variable that can be assigned a number representing one of the
letters a..z and #. The difference is that a different type of
constraint is used to force sequences of cells, longer than one letter,
to form words. The model now uses tuple constraints, which each
constrain an enumeration of integer variables (e.g. letters that should
form words) to take the value of one of many tuples (e.g. all tuples
representing words of the correct length).

The code requires Gecode/R 0.8.1 to run, which can be installed, along
with the Gecode 2.1.1 dependency, using

  gem install gecoder-with-gecode

== Code

require 'enumerator'
require 'rubygems'
require 'gecoder'

# The alphabet used.
ALPHABET = ('a'..'z').to_a

# Describes an immutable dictionary which represents all contained words
# as an array of integers where each integer represents a letter. Each
# integer used is between 0 and ALPHABET.size - 1.
class Dictionary
  # Creates a dictionary from the contents of the specified dictionary
  # file which is assumed to contain one word per line and be sorted.
  def initialize(dictionary_location)
    @word_arrays =
    File.open(dictionary_location) do |dict|
      previous_word = nil
      # A regexp that matches strings not in our alphabet.
      not_in_alphabet = /[^#{ALPHABET.join}]/
      dict.each_line do |line|
        word = line.chomp.downcase
        # Only allow words that are in our alphabet.
        next if previous_word == word or not_in_alphabet.match(word)
        (@word_arrays[word.length] ||= ) <<
          self.class.s_to_i_array(word)
        previous_word = word
      end
    end
  end

  # Gets an enumeration containing all arrays of integers representing
  # word of the specified length.
  def words_of_size(n)
    @word_arrays[n] ||
  end

  # Converts a string to an array of integers (inverse
  # of #i_array_to_s ).
  def self.s_to_i_array(string)
    if @c_to_i_map.nil?
      @c_to_i_map =
        Hash[*ALPHABET.zip((0...ALPHABET.size).to_a).flatten]
    end
    @c_to_i_map.values_at *string.scan(/./)
  end

  # Converts an array of integers back to the corresponding string
  # (inverse of #s_to_i_array ).
  def self.i_array_to_s(int_array)
    if @i_to_c_map.nil?
      @i_to_c_map = ALPHABET
    end
    @i_to_c_map.values_at *int_array
  end
end

# Models the solution to a partially completed crossword.
class Crossword < Gecode::Model
  # The template should take the format described in RubyQuiz #132 . The
  # words used are selected from the specified dictionary.
  def initialize(template, dictionary)
    @dictionary = dictionary

    # Break down the template and create a corresponding square matrix.
    # We let each square be represented by an integer variable with
    # domain -1...BASE where -1 signify # and the rest signify letters.
    squares = template.split(/\n\s*\n/).map!{ |line| line.split(' ') }
    @letters =
      int_var_matrix(squares.size, squares.first.size,
        -1...ALPHABET.size)

    # Do an initial pass, filling in the prefilled squares.
    squares.each_with_index do |row, i|
      row.each_with_index do |letter, j|
        unless letter == '_'
          # Prefilled letter.
          @letters[i,j].must == self.class.s_to_i_array(letter).first
        end
      end
    end

    # Add the constraint that sequences longer than one letter must form
    # words.
    # Left to right pass.
    left_to_right_pass(squares, @letters)
    # Top to bottom pass.
    left_to_right_pass(squares.transpose, @letters.transpose)

    # Branch on intersections first.
    branch_on @letters, :variable => :largest_degree, :value => :min
  end

  # Displays the solved crossword in the same format as shown in the
  # quiz examples.
  def to_s
    output =
    @letters.values.each_slice(@letters.column_size) do |row|
      output << row.map{ |x| self.class.i_array_to_s() }.join(' ')
    end
    output.join("\n\n").upcase.gsub('#', ' ')
  end

  private

  # Parses the template from left to right, line for line, constraining
  # sequences of two or more subsequent squares to form a word in the
  # dictionary.
  def left_to_right_pass(template, variables)
    template.each_with_index do |row, i|
      letters =
      row.each_with_index do |letter, j|
        if letter == '#'
          must_form_word(letters) if letters.size > 1
          letters =
        else
          letters << variables[i,j]
        end
      end
      must_form_word(letters) if letters.size > 1
    end
  end

  # Converts a word from integer form to string form, including the #.
  def self.i_array_to_s(int_array)
    if int_array == [-1]
      return '#'
    else
      Dictionary.i_array_to_s(int_array)
    end
  end

  # Converts a word from string form to integer form, including the #.
  def self.s_to_i_array(string)
    if string == '#'
      return [-1]
    else
      Dictionary.s_to_i_array(string)
    end
  end

  # Constrains the specified variables to form a word contained in the
  # dictionary.
  def must_form_word(letters)
    words_of_right_size = @dictionary.words_of_size(letters.size)
    if words_of_right_size.empty?
      raise RuntimeError, "There are no words of size #{letters.size}."
    end
    # Add the tuple constraint. Use propagation kind :memory if you run
    # out of memory.
    wrap_enum(letters).must_be.in words_of_right_size, :kind => :speed
  end
end

puts 'Reading the dictionary'
dictionary = Dictionary.new(ARGV.shift || '/usr/share/dict/words')
puts 'Enter the template (end with ^D)'
template = ''
loop do
  line = $stdin.gets
  break if line.nil?
  template << line
end
puts 'Building the model'
model = Crossword.new(template, dictionary)
puts 'Searching for a solution'
puts((model.solve! || 'Failed').to_s)

__END__

···

--
Andreas Launila

13

Ball, Donald A Jr (Library) wrote:

http://wordlist.sourceforge.net/ is a good resource, especially if
you're on Windows and don't have /usr/share/dict/words

Perfect! I got this, then chose the 6 files that were straight
wordlists. I wrote a program to read each file, change it to uppercase,
get rid of non alpha characters (which are no good for the puzzle), get
rid of all duplicates and write the new (sorted) list to a new file. It
has something like 108k words. nice!

Thanks all!

···

--
Posted via http://www.ruby-forum.com/\.