Skip to content

Instantly share code, notes, and snippets.

@woyczek

woyczek/LICENSE

Forked from kentor/boggle.rb
Last active October 25, 2016 09:39
Show Gist options
  • Save woyczek/93752e74b476818d8df4717f0da50fda to your computer and use it in GitHub Desktop.
Save woyczek/93752e74b476818d8df4717f0da50fda to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. woyczek revised this gist Oct 25, 2016. 1 changed file with 3 additions and 3 deletions.
    6 changes: 3 additions & 3 deletions boggle.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -133,7 +133,7 @@ def initialize(str, score = '' , dict = "", lang="en" )
    "f" => 4, "g" => 2, "h" => 5, "i" => 1, "j" => 8,
    "k" => 6, "l" => 2, "m" => 2, "n" => 2, "o" => 2,
    "p" => 4, "q" => 8, "r" => 2, "s" => 2, "t" => 2,
    "u" => 1, "v" => 4, "w" => 5, "x" => 5, "y" => 5,
    "u" => 2, "v" => 4, "w" => 5, "x" => 5, "y" => 5,
    "z" => 5
    }
    @scores=@fra if lang == "fr"
    @@ -370,11 +370,11 @@ def find(word, position, score=0, idx = 1, visited = @visited.clear, w_multi_loc
    word=ARGV.shift.to_s
    elsif (arg == "-l") || (arg == "--lang")
    lang=ARGV.shift.to_s
    elsif arg =~ /^[a-z]+$/i ################# BOARD
    elsif arg =~ /^[a-z.-\/@+_()=]+$/i ################# BOARD
    puts arg
    board = arg.downcase.tr('.-/@+_()=','')
    scores = scores.ljust(board.size,'1')
    elsif arg =~ /^[0-9dt]+$/i ################# SCORES
    elsif arg =~ /^[0-9dt.-\/@+_()=]+$/i ################# SCORES
    scores = arg.tr('.-/@+_()=','').ljust(board.size,'1')
    else
    raise "Invalid parameter #{arg}"
  2. woyczek revised this gist Oct 25, 2016. 1 changed file with 62 additions and 44 deletions.
    106 changes: 62 additions & 44 deletions boggle.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -9,26 +9,30 @@
    #DICO = '/usr/share/dict/words'
    DICO=FRA

    def help
    #
    # SPECS
    #
    # script_name.rb <grid> <bonus> [-g|--grid] [-w|--word WORD] [-l|--lang LANG]
    #
    # grid is a square grid transformed in string of letters. It may include any char from [.-_()+@/]
    # --> It will be verified nxn sized.
    # aeio | ae.io | (ae)(io) | ae_io
    #
    #
    # bonus is a square grid transformed in string. It may include any char from [.-_()+@/]
    # --> It will be verified nxn sized but by "grid" method
    # 1113 | 11.13 | 1.13.1
    # Bonus may be n, T, D, B for "n x letter value", "triple word", "double word", "bonus word"
    #
    # -g|--grid displays the grid, but dont solve it
    #
    # -w|--word word displays the word on the grid
    #
    # -l|--lang changes the dictionnary and the scoring matrix curently (fr|en)
    print '
    script_name.rb <grid> <bonus> [-g|--grid] [-w|--word WORD] [-l|--lang LANG]
    grid is a square grid transformed in string of letters. It may include any char from [.-_()+@/]
    --> It will be verified nxn sized.
    aeio | ae.io | (ae)(io) | ae_io
    bonus is a square grid transformed in string. It may include any char from [.-_()+@/]
    --> It will be verified nxn sized but by "grid" method
    1113 | 11.13 | 1.13.1
    Bonus may be n, T, D, B for "n x letter value", "triple word", "double word", "bonus word"
    -g|--grid displays the grid, but dont solve it
    -w|--word word displays the word on the grid
    -l|--lang changes the dictionnary and the scoring matrix curently (fr|en)
    '
    end


    class Point < Complex
    @@ -347,40 +351,54 @@ def find(word, position, score=0, idx = 1, visited = @visited.clear, w_multi_loc

    end

    board = ARGV.shift.downcase.tr('.-/@+_()=','')
    scores = ARGV.shift.tr('.-/@+_()=','')
    board = ""
    scores = ""

    puts "Boggle solver -- v2016.2"

    word=""
    lang=DEFLANG

    begin
    # Options parser
    while ARGV.size > 0 do
    arg=ARGV.shift
    if (arg == "-g") || (arg == "--grid")
    action="grid"
    end
    if (arg == "-w") || (arg == "--word")
    action="word"
    word=ARGV.shift.to_s
    end
    if (arg == "-l") || (arg == "--lang")
    lang=ARGV.shift.to_s
    while ARGV.size > 0 do
    arg=ARGV.shift
    if (arg == "-g") || (arg == "--grid")
    action="grid"
    elsif (arg == "-w") || (arg == "--word")
    action="word"
    word=ARGV.shift.to_s
    elsif (arg == "-l") || (arg == "--lang")
    lang=ARGV.shift.to_s
    elsif arg =~ /^[a-z]+$/i ################# BOARD
    puts arg
    board = arg.downcase.tr('.-/@+_()=','')
    scores = scores.ljust(board.size,'1')
    elsif arg =~ /^[0-9dt]+$/i ################# SCORES
    scores = arg.tr('.-/@+_()=','').ljust(board.size,'1')
    else
    raise "Invalid parameter #{arg}"
    end
    end
    end

    grille = Boggle.new(board,scores,"",lang)

    if action == "grid" then
    grille.show_grid
    elsif word != ""
    grille.solve(true,word)
    grille.show_grid(word)
    else
    grille.solve(false)
    arr=grille.show_best(10)
    arr.push(*grille.show_longuest(10))
    Boggle.display_words(arr.sort { |a,b| a[1] <=> b[1] })
    raise "Invalid empty board" if board == ''

    grille = Boggle.new(board,scores,"",lang)

    if action == "grid" then
    puts "GRILLE"
    grille.show_grid
    elsif word != ""
    grille.solve(true,word)
    grille.show_grid(word)
    else
    grille.solve(false)
    arr=grille.show_best(10)
    arr.push(*grille.show_longuest(10))
    Boggle.display_words(arr.sort { |a,b| a[1] <=> b[1] })
    end
    puts ""
    rescue Exception => e
    help
    raise e
    end
    puts ""
  3. woyczek revised this gist Oct 15, 2016. 1 changed file with 1 addition and 0 deletions.
    1 change: 1 addition & 0 deletions france2.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -45755,6 +45755,7 @@ castillanes
    castillans
    castine
    castines
    casting
    castor
    castoreum
    castoreums
  4. woyczek revised this gist Oct 12, 2016. 1 changed file with 6 additions and 3 deletions.
    9 changes: 6 additions & 3 deletions boggle.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -118,7 +118,7 @@ def initialize(str, score = '' , dict = "", lang="en" )
    end
    @fra = {
    "a" => 1, "b" => 4, "c" => 4, "d" => 5, "e" => 1,
    "f" => 4, "g" => 3, "h" => 4, "i" => 1, "j" => 8,
    "f" => 5, "g" => 3, "h" => 4, "i" => 1, "j" => 8,
    "k" => 10, "l" => 2, "m" => 3, "n" => 2, "o" => 1,
    "p" => 4, "q" => 8, "r" => 2, "s" => 1, "t" => 1,
    "u" => 1, "v" => 5, "w" => 10, "x" => 10, "y" => 10,
    @@ -350,6 +350,8 @@ def find(word, position, score=0, idx = 1, visited = @visited.clear, w_multi_loc
    board = ARGV.shift.downcase.tr('.-/@+_()=','')
    scores = ARGV.shift.tr('.-/@+_()=','')

    puts "Boggle solver -- v2016.2"

    word=""
    lang=DEFLANG

    @@ -361,10 +363,10 @@ def find(word, position, score=0, idx = 1, visited = @visited.clear, w_multi_loc
    end
    if (arg == "-w") || (arg == "--word")
    action="word"
    word=ARGV.shift.dup
    word=ARGV.shift.to_s
    end
    if (arg == "-l") || (arg == "--lang")
    lang=ARGV.shift
    lang=ARGV.shift.to_s
    end
    end

    @@ -381,3 +383,4 @@ def find(word, position, score=0, idx = 1, visited = @visited.clear, w_multi_loc
    arr.push(*grille.show_longuest(10))
    Boggle.display_words(arr.sort { |a,b| a[1] <=> b[1] })
    end
    puts ""
  5. woyczek revised this gist Oct 12, 2016. 1 changed file with 0 additions and 1 deletion.
    1 change: 0 additions & 1 deletion france2.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -255561,7 +255561,6 @@ rainetassiez
    rainetassions
    rainetat
    rainetates
    rainete
    rainetee
    rainetees
    raineter
  6. woyczek revised this gist Oct 12, 2016. 2 changed files with 87 additions and 54 deletions.
    3 changes: 2 additions & 1 deletion LICENSE
    View file
    Original file line number Diff line number Diff line change
    @@ -1,7 +1,8 @@
    Copyright (c) 2012 Caleb Spare
    Copyleft (l) 2016 Gaetan Ryckeboer

    Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

    The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
    138 changes: 85 additions & 53 deletions boggle.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -40,6 +40,15 @@ class << self
    class Case
    #class Case < Complex

    attr_accessor :visited
    attr_accessor :valeur
    attr_accessor :multi
    attr_accessor :numorder

    def visited
    @visited=true
    end

    def point
    @c
    end
    @@ -48,14 +57,6 @@ def pointH
    @point
    end

    def valeur
    @valeur
    end

    def multi
    @multi
    end

    def abs
    @c.abs
    end
    @@ -69,33 +70,36 @@ def -(arg)
    @c-arg
    end

    def initialize(c,valeur,multi)
    def initialize(c,valeur,multi,numorder=0)
    @multi=1
    @valeur=1
    @numorder=numorder
    @c=c
    @point=c
    @valeur=valeur
    @multi=multi
    @valeur=valeur unless (valeur==nil || valeur=='')
    @multi=multi unless (multi==nil || multi=='')
    # puts c.to_s + " - " + valeur.to_s + " - " + multi.to_s
    self
    end

    def self.c_create(c,valeur,multi)
    def self.c_create(c,valeur,multi,numorder)
    self.new(c,valeur,multi)
    end

    def self.new(*args,valeur,multi)
    def self.new(*args,valeur,multi,numorder)
    if args.count > 1 then
    super(Complex.rect(args[0].to_i,args[1].to_i),valeur,multi)
    super(Complex.rect(args[0].to_i,args[1].to_i),valeur,multi,numorder)
    else
    super(c,valeur,multi)
    super(c,valeur,multi,numorder)
    end
    end

    def self.r_create(x,y,valeur,multi)
    self.c_create(Complex.rect(x,y),valeur,multi)
    def self.r_create(x,y,valeur,multi,numorder)
    self.c_create(Complex.rect(x,y),valeur,multi,numorder)
    end

    def pretty_print(inst)
    puts @point.to_s + " : " + @valeur.to_s + " x " + @multi.to_s
    puts @numorder.to_s + " " + @point.to_s + " : " + @valeur.to_s + " x " + @multi.to_s + ( @visited ? " V" : " -")
    return @point.to_s + " : " + @valeur.to_s + " x " + @multi.to_s
    end

    @@ -145,13 +149,14 @@ def initialize(str, score = '' , dict = "", lang="en" )
    @positions = Hash.new { |h,k| h[k] = [] }
    @positionsC = Hash.new { |h,k| h[k] = [] }
    @str.each_char.with_index do |c, i|
    @positionsC[c] << Case.new(i / @side, i % @side, @scores[c], score.chars[i])
    @positionsC[c] << Case.new(i / @side, i % @side, @scores[c], score.chars[i], i)
    @positions[c] << Point.new(i / @side, i % @side )
    end

    @possible = Regexp.new("^[#{@positionsC.keys.join}]{3,#{@str.length}}$")

    @visited ||= Set.new
    @v_cells ||= Array.new
    self
    end

    @@ -160,59 +165,76 @@ def solve(display=false,word="")
    @words = []
    #puts @dict
    if word != "" then
    search_for_word(word)
    #puts word
    search_for_word(word,display)
    else
    File.new(@dict, 'r').each_line do |word|
    search_for_word(word)
    search_for_word(word,display)
    end
    end
    end

    self
    end

    def show_grid
    # Displays grid
    def show_grid(word='')
    # require 'pp'
    # Displays grid, with the first found word if any
    @rows = Array.new
    rownum = 0
    row = ""
    r = 0
    @str.each_char.with_index do |c, i|
    # divide total positions by side
    s = "["
    if @score_str[i].to_i > 0 then
    if @score_str[i].to_i > 1 then
    s = s + "33m"
    # @positionsC.each do |pos|
    # c=pos[0]
    # pos[1].each do |p|
    # pp p
    # i=p.numorder
    # divide total positions by side
    s = " [2;"
    b='44;' if @v_cells[i]
    b='40;' unless @v_cells[i]
    if @score_str[i].to_i > 0 then
    if @score_str[i].to_i > 1 then
    f="33;"
    s = s + b + "5;" + f + "m"
    else
    f="37;"
    s = s + b + "5;" + f + "m"
    end
    s = s +(@score_str[i].to_i * @scores[c].to_i ).to_s.rjust(2)
    else
    s = s + "37m"
    if @score_str[i].downcase == "d" then
    f="31;"
    s = s + "0;" + b + f + "m"
    elsif @score_str[i].downcase == "t" then
    f="32;"
    s = s + "0;" + b + f + "m"
    elsif @score_str[i].downcase == "b" then
    f="35;"
    s = s + "0;" + b + f + "m"
    end
    s = s + @scores[c].to_s.rjust(2)
    end
    s = s + " "+(@score_str[i].to_i * @scores[c] ).to_s.rjust(2)
    else
    if @score_str[i].downcase == "d" then
    s = s + "31m"
    elsif @score_str[i].downcase == "t" then
    s = s + "32m"
    elsif @score_str[i].downcase == "b" then
    s = s + "35m"
    row = row + s + "[0;" + b + f + "1m" + c.upcase + ""
    # If next position is on next row,
    r = (i+1) / @side
    if r != rownum then
    @rows[ r ] = row
    row = ""
    rownum = r
    end
    s = s + " " + @scores[c].to_s.rjust(2)
    end
    row = row + s + "" + c.upcase + ""
    # If next position is on next row,
    r = (i+1) / @side
    if r != rownum then
    @rows[ r ] = row
    row = ""
    rownum = r
    end
    # end
    end
    #puts DICO
    @rows.each do | s |
    puts s
    end
    show_best(1) if defined?(@words)
    end

    def Boggle.display_words(arr)
    # Display an array of word/size/score
    arr.each do | w |
    puts w[1].to_s + " : " + w[0] + " " + w[0].length.to_s
    end
    @@ -244,7 +266,11 @@ def has_word?(word)
    # Switch cell bonus into word/letter multiplier
    l_multi=1
    w_multi=1
    if position.multi == "D" then
    if position.multi == "" then
    l_multi=1
    elsif position.multi == nil then
    l_multi=1
    elsif position.multi == "D" then
    l_multi=w_multi*2
    elsif position.multi == "T" then
    l_multi=w_multi*3
    @@ -253,6 +279,7 @@ def has_word?(word)
    else
    l_multi=position.multi.to_i
    end
    #l_multi=1 if l_multi<1

    # if a word is found, return the word score
    if (local_score=find(word, position, position.valeur.to_i * l_multi, 1 , @visited.clear, w_multi)) != 0
    @@ -266,8 +293,9 @@ def has_word?(word)

    def search_for_word(word,display=false)
    # Search for a word in the tree, and display if needed
    #puts word
    if @words then
    word.chomp!.downcase
    word=word.chomp.downcase
    local_score = has_word?(word)
    if local_score != 0
    @words << [ word, local_score ]
    @@ -281,6 +309,10 @@ def find(word, position, score=0, idx = 1, visited = @visited.clear, w_multi_loc

    if idx == word.length
    # Word is found. The score is multiplied by word multiplier.
    visited.each do |v|
    @v_cells[v.numorder]=true
    end
    @v_cells[position.numorder]=true
    return score * w_multi_local
    end

    @@ -329,20 +361,20 @@ def find(word, position, score=0, idx = 1, visited = @visited.clear, w_multi_loc
    end
    if (arg == "-w") || (arg == "--word")
    action="word"
    word=ARGV.shift
    word=ARGV.shift.dup
    end
    if (arg == "-l") || (arg == "--lang")
    lang=ARGV.shift
    end
    end

    grille = Boggle.new(board,scores)
    grille = Boggle.new(board,scores,"",lang)

    if action == "grid" then
    grille.show_grid
    elsif word != ""
    grille.solve(false,word)
    arr=grille.show_best(10)
    grille.solve(true,word)
    grille.show_grid(word)
    else
    grille.solve(false)
    arr=grille.show_best(10)
  7. woyczek revised this gist Oct 12, 2016. 1 changed file with 27 additions and 23 deletions.
    50 changes: 27 additions & 23 deletions README.md
    View file
    Original file line number Diff line number Diff line change
    @@ -1,27 +1,31 @@
    Dictionnaries from :
    English :
    # What is it ?
    A ruby boggle solver, for multiple languages, with variable grid size, and bonus managment.

    ----

    # Dictionnaries from :
    ## English :
    twl06.txt
    Francais :
    http://www.pallier.org/ressources/dicofr/liste.de.mots.francais.frgut.txt
    ## Francais :
    [link](http://www.pallier.org/ressources/dicofr/liste.de.mots.francais.frgut.txt)

    #
    # SPECS
    #
    # script_name.rb <grid> <bonus> [-g|--grid] [-w|--word WORD] [-l|--lang LANG]
    #
    # grid is a square grid transformed in string of letters. It may include any char from [.-_()+@/]
    # --> It will be verified nxn sized.
    # aeio | ae.io | (ae)(io) | ae_io
    #
    #
    # bonus is a square grid transformed in string. It may include any char from [.-_()+@/]
    # --> It will be verified nxn sized but by "grid" method
    # 1113 | 11.13 | 1.13.1
    # Bonus may be n, T, D, B for "n x letter value", "triple word", "double word", "bonus word"
    #
    # -g|--grid displays the grid, but dont solve it
    #
    # -w|--word word displays the word on the grid
    #
    # -l|--lang changes the dictionnary and the scoring matrix curently (fr|en)

    script_name.rb <grid> <bonus> [-g|--grid] [-w|--word WORD] [-l|--lang LANG]

    grid is a square grid transformed in string of letters. It may include any char from [.-_()+@/]
    --> It will be verified nxn sized.
    aeio | ae.io | (ae)(io) | ae_io


    bonus is a square grid transformed in string. It may include any char from [.-_()+@/]
    --> It will be verified nxn sized but by "grid" method
    1113 | 11.13 | 1.13.1
    Bonus may be n, T, D, B for "n x letter value", "triple word", "double word", "bonus word"

    -g|--grid displays the grid, but dont solve it

    -w|--word word displays the word on the grid

    -l|--lang changes the dictionnary and the scoring matrix curently (fr|en)

  8. woyczek revised this gist Oct 12, 2016. 2 changed files with 33 additions and 21 deletions.
    7 changes: 7 additions & 0 deletions LICENSE
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,7 @@
    Copyright (c) 2012 Caleb Spare

    Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

    The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
    47 changes: 26 additions & 21 deletions README.md
    View file
    Original file line number Diff line number Diff line change
    @@ -1,22 +1,27 @@
    A simple boggle solver written in Ruby for fun. It generates a random board and then prints out solutions.
    Dictionnaries from :
    English :
    twl06.txt
    Francais :
    http://www.pallier.org/ressources/dicofr/liste.de.mots.francais.frgut.txt

    #
    # SPECS
    #
    # script_name.rb <grid> <bonus> [-g|--grid] [-w|--word WORD] [-l|--lang LANG]
    #
    # grid is a square grid transformed in string of letters. It may include any char from [.-_()+@/]
    # --> It will be verified nxn sized.
    # aeio | ae.io | (ae)(io) | ae_io
    #
    #
    # bonus is a square grid transformed in string. It may include any char from [.-_()+@/]
    # --> It will be verified nxn sized but by "grid" method
    # 1113 | 11.13 | 1.13.1
    # Bonus may be n, T, D, B for "n x letter value", "triple word", "double word", "bonus word"
    #
    # -g|--grid displays the grid, but dont solve it
    #
    # -w|--word word displays the word on the grid
    #
    # -l|--lang changes the dictionnary and the scoring matrix curently (fr|en)

    ## Usage

    First you need to install the `fast_trie` gem:

    $ gem install fast_trie

    Then run the solver:

    $ ruby solver.rb --random

    This generates a random board and solves it. You can also input the board from stdin or a file:

    $ ruby solver.rb
    T L T P
    N E N G
    T N O A
    B I S A
    <C-d>

    $ ruby solver.rb your_board.txt
  9. woyczek revised this gist Oct 12, 2016. 1 changed file with 22 additions and 0 deletions.
    22 changes: 22 additions & 0 deletions README.md
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,22 @@
    A simple boggle solver written in Ruby for fun. It generates a random board and then prints out solutions.

    ## Usage

    First you need to install the `fast_trie` gem:

    $ gem install fast_trie

    Then run the solver:

    $ ruby solver.rb --random

    This generates a random board and solves it. You can also input the board from stdin or a file:

    $ ruby solver.rb
    T L T P
    N E N G
    T N O A
    B I S A
    <C-d>

    $ ruby solver.rb your_board.txt
  10. woyczek revised this gist Oct 12, 2016. 1 changed file with 205 additions and 86 deletions.
    291 changes: 205 additions & 86 deletions boggle.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -1,8 +1,35 @@
    #!/usr/bin/env ruby

    @lang="fr"
    DEFLANG="fr"

    MIN_SIZE = 2
    DICO = 'france2.txt'
    ENG = 'anglais.txt'
    FRA = 'france2.txt'
    #DICO = '/usr/share/dict/words'
    DICO=FRA

    #
    # SPECS
    #
    # script_name.rb <grid> <bonus> [-g|--grid] [-w|--word WORD] [-l|--lang LANG]
    #
    # grid is a square grid transformed in string of letters. It may include any char from [.-_()+@/]
    # --> It will be verified nxn sized.
    # aeio | ae.io | (ae)(io) | ae_io
    #
    #
    # bonus is a square grid transformed in string. It may include any char from [.-_()+@/]
    # --> It will be verified nxn sized but by "grid" method
    # 1113 | 11.13 | 1.13.1
    # Bonus may be n, T, D, B for "n x letter value", "triple word", "double word", "bonus word"
    #
    # -g|--grid displays the grid, but dont solve it
    #
    # -w|--word word displays the word on the grid
    #
    # -l|--lang changes the dictionnary and the scoring matrix curently (fr|en)


    class Point < Complex
    class << self
    @@ -47,7 +74,7 @@ def initialize(c,valeur,multi)
    @point=c
    @valeur=valeur
    @multi=multi
    puts c.to_s + " - " + valeur.to_s + " - " + multi.to_s
    # puts c.to_s + " - " + valeur.to_s + " - " + multi.to_s
    self
    end

    @@ -80,41 +107,37 @@ class Boggle
    attr_reader :words

    #def initialize(str, dict = '/usr/share/dict/words')
    def initialize(str, score = '' , dict = DICO )
    @scores = {
    "a" => 1,
    "b" => 3,
    "c" => 3,
    "d" => 2,
    "e" => 1,
    "f" => 4,
    "g" => 2,
    "h" => 4,
    "i" => 1,
    "j" => 8,
    "k" => 10,
    "l" => 2,
    "m" => 2,
    "n" => 2,
    "o" => 1,
    "p" => 4,
    "q" => 8,
    "r" => 2,
    "s" => 1,
    "t" => 1,
    "u" => 1,
    "v" => 4,
    "w" => 10,
    "x" => 10,
    "y" => 10,
    def initialize(str, score = '' , dict = "", lang="en" )
    if dict == "" then
    dict = FRA if lang == "fr"
    dict = ENG if lang == "en"
    end
    @fra = {
    "a" => 1, "b" => 4, "c" => 4, "d" => 5, "e" => 1,
    "f" => 4, "g" => 3, "h" => 4, "i" => 1, "j" => 8,
    "k" => 10, "l" => 2, "m" => 3, "n" => 2, "o" => 1,
    "p" => 4, "q" => 8, "r" => 2, "s" => 1, "t" => 1,
    "u" => 1, "v" => 5, "w" => 10, "x" => 10, "y" => 10,
    "z" => 10
    }
    @eng = {
    "a" => 1, "b" => 3, "c" => 4, "d" => 2, "e" => 1,
    "f" => 4, "g" => 2, "h" => 5, "i" => 1, "j" => 8,
    "k" => 6, "l" => 2, "m" => 2, "n" => 2, "o" => 2,
    "p" => 4, "q" => 8, "r" => 2, "s" => 2, "t" => 2,
    "u" => 1, "v" => 4, "w" => 5, "x" => 5, "y" => 5,
    "z" => 5
    }
    @scores=@fra if lang == "fr"
    @scores=@eng if lang == "en"

    #def initialize(str, dict = DICO )
    # Ouverture du dictionnaire
    @str = str.dup
    @dict = dict.dup

    @score_str=score.dup

    @side = Math.sqrt(@str.length).round

    raise 'Invalid Board' unless @side ** 2 == @str.length
    @@ -129,104 +152,200 @@ def initialize(str, score = '' , dict = DICO )
    @possible = Regexp.new("^[#{@positionsC.keys.join}]{3,#{@str.length}}$")

    @visited ||= Set.new
    self
    end

    def solve
    def solve(display=false,word="")
    if !@words
    @words = []
    puts @dict
    File.new(@dict, 'r').each_line do |word|
    word.chomp!.downcase
    local_score = has_word?(word)
    if local_score != 0
    @words << word
    puts "-- " + word + " : " + local_score.to_s
    #puts @dict
    if word != "" then
    search_for_word(word)
    else
    File.new(@dict, 'r').each_line do |word|
    search_for_word(word)
    end
    end
    end

    self
    end

    def show_grid
    # Displays grid
    @rows = Array.new
    rownum = 0
    row = ""
    r = 0
    @str.each_char.with_index do |c, i|
    # divide total positions by side
    s = "["
    if @score_str[i].to_i > 0 then
    if @score_str[i].to_i > 1 then
    s = s + "33m"
    else
    s = s + "37m"
    end
    s = s + " "+(@score_str[i].to_i * @scores[c] ).to_s.rjust(2)
    else
    if @score_str[i].downcase == "d" then
    s = s + "31m"
    elsif @score_str[i].downcase == "t" then
    s = s + "32m"
    elsif @score_str[i].downcase == "b" then
    s = s + "35m"
    end
    s = s + " " + @scores[c].to_s.rjust(2)
    end
    row = row + s + "" + c.upcase + ""
    # If next position is on next row,
    r = (i+1) / @side
    if r != rownum then
    @rows[ r ] = row
    row = ""
    rownum = r
    end
    end
    #puts DICO
    @rows.each do | s |
    puts s
    end
    end

    def Boggle.display_words(arr)
    arr.each do | w |
    puts w[1].to_s + " : " + w[0] + " " + w[0].length.to_s
    end
    end

    def show_best(number)
    arr=@words.sort { |a,b| a[1] <=> b[1] }.last(number)
    #Boggle.display_words(arr)
    arr
    end

    def show_longuest(number)
    arr=@words.sort { |a,b| a[0].length <=> b[0].length }.last(number)
    #Boggle.display_words(arr)
    arr
    end

    private

    def has_word?(word)
    # OK if the cell is the starting of a dictionnary word
    unless word =~ @possible
    return 0
    end

    # pp @positions[word][0]
    @positionsC[word[0]].each do |position|
    # pp position

    multi=1
    local_multi=1
    if position.multi == "D" then
    multi=multi*2
    elsif position.multi == "T" then
    multi=multi*3
    else
    local_multi=position.multi
    end
    # List cells for every char from the word

    # Switch cell bonus into word/letter multiplier
    l_multi=1
    w_multi=1
    if position.multi == "D" then
    l_multi=w_multi*2
    elsif position.multi == "T" then
    l_multi=w_multi*3
    elsif position.multi == "B" then
    l_multi=w_multi*1
    else
    l_multi=position.multi.to_i
    end

    if (local_score=find(word, position, position.valeur.to_i * local_multi.to_i, multi )) != 0
    return local_score
    # if a word is found, return the word score
    if (local_score=find(word, position, position.valeur.to_i * l_multi, 1 , @visited.clear, w_multi)) != 0
    # The score is only multipiled by word multiplier at the time the end of the dictionnary word is reached
    return local_score
    end
    end

    0
    end

    def find(word, position, score=0, idx = 1, visited = @visited.clear, multi=1)
    # pp position
    def search_for_word(word,display=false)
    # Search for a word in the tree, and display if needed
    if @words then
    word.chomp!.downcase
    local_score = has_word?(word)
    if local_score != 0
    @words << [ word, local_score ]
    puts "-- " + word + " : " + local_score.to_s if display
    end
    end
    end

    def find(word, position, score=0, idx = 1, visited = @visited.clear, w_multi_local=1)
    # Recursive search method to find a word in the tree previously built

    if idx == word.length
    return score
    # Word is found. The score is multiplied by word multiplier.
    return score * w_multi_local
    end

    # Add cell to visited positions
    visited << position
    #:score = score + @scores[word]

    @positionsC[word[idx]].each do |position2|
    local_multi=1
    if position2.multi == "D" then
    multi=multi*2
    elsif position2.multi == "T" then
    multi=multi*3
    else
    local_multi=position2.multi.to_i
    end
    w_multi=w_multi_local
    l_multi=1
    if position2.multi == "D" then
    w_multi=w_multi*2
    elsif position2.multi == "T" then
    w_multi=w_multi*3
    else
    l_multi=position2.multi.to_i
    end
    if (position.point - position2.point).abs < 2 && !visited.include?(position2)
    if (local_score=find(word, position2, score+position2.valeur.to_i*local_multi.to_i, idx + 1, visited,multi)) != 0
    puts multi.to_s + " - " + local_multi.to_s
    return local_score
    if (local_score=find(word, position2, score+position2.valeur.to_i * l_multi, idx + 1,
    visited, w_multi)) != 0
    # puts local_score.to_s + " - " + w_multi.to_s
    return local_score # * w_multi
    end
    end
    end

    #:score = score - @scores[@positions[word][idx]]
    # Remove cell to visited positions if the word is still uncomplete
    # If not, the function has been breaked by "return" so this line is not executed
    visited.delete(position)

    0
    end

    end

    require 'pp'
    #pp Boggle.new('fxieamloewbxastu').solve.words.group_by(&:length)
    #
    board = ARGV.shift.downcase
    scores = ARGV.shift
    puts board
    #pp Point.new(1,2)
    #
    t=Case.new(1,2,4,5)
    pp t
    puts t.abs
    puts "toto"

    #pp Boggle.new(board).solve.words.group_by(&:length)
    Boggle.new(board,scores).solve.words.group_by(&:length)
    #pp Boggle.new(board,scores).solve.words.group_by(&:length)
    #pp Boggle.new('cretepoeniaialsurteesaint').solve.words.group_by(&:length)
    ##pp Boggle.new('crEtepoenIaIaLsurtEesAint').solve.words.group_by(&:length)
    #puts 'Fin finale'
    board = ARGV.shift.downcase.tr('.-/@+_()=','')
    scores = ARGV.shift.tr('.-/@+_()=','')

    word=""
    lang=DEFLANG

    # Options parser
    while ARGV.size > 0 do
    arg=ARGV.shift
    if (arg == "-g") || (arg == "--grid")
    action="grid"
    end
    if (arg == "-w") || (arg == "--word")
    action="word"
    word=ARGV.shift
    end
    if (arg == "-l") || (arg == "--lang")
    lang=ARGV.shift
    end
    end

    grille = Boggle.new(board,scores)

    if action == "grid" then
    grille.show_grid
    elsif word != ""
    grille.solve(false,word)
    arr=grille.show_best(10)
    else
    grille.solve(false)
    arr=grille.show_best(10)
    arr.push(*grille.show_longuest(10))
    Boggle.display_words(arr.sort { |a,b| a[1] <=> b[1] })
    end
  11. woyczek revised this gist Oct 11, 2016. 1 changed file with 155 additions and 110 deletions.
    265 changes: 155 additions & 110 deletions boggle.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -1,175 +1,214 @@
    #!/usr/bin/env ruby

    MIN_SIZE = 2
    DICO = 'france2.txt'
    #DICO = '/usr/share/dict/words'

    class Point < Complex
    # Derivee de matrice (2D) aka complexe
    # def initialize(x,y,score)
    # @score = score
    # @point = super(x,y)
    # end
    class << self
    alias :new :rectangular
    end
    end

    #def self.new (x,y,score)
    # @score = score
    # @point = self.rectangular(x,y)
    # self
    #end
    class Case
    #class Case < Complex

    # alias oldNew new
    def score
    @score
    def point
    @c
    end

    class << self
    def score
    @score
    end
    def pointH
    @point
    end

    def create (complexe,sc=1)
    @score = sc
    @c_point=complexe
    self
    end
    def valeur
    @valeur
    end

    def new (reel,imag,sc=1)
    @score = sc
    @c_point=rectangular(reel,imag)
    self
    end
    def multi
    @multi
    end

    def to_s(*args)
    super(*args) + " : " + @score.to_s
    end
    def abs
    @c.abs
    end

    def to_x(*args)
    @c_point
    end
    def pretty_print(inst)
    puts "PP"
    return inst.point.to_s + " : " + inst.valeur.to_s + " x "
    end

    def -(other)
    puts @c_point.to_s
    puts other.to_s
    result=@c_point-other.to_x
    Point.create(result,@score)
    end
    def -(arg)
    @c-arg
    end

    def abs
    @c_point.abs
    end
    def initialize(c,valeur,multi)
    @c=c
    @point=c
    @valeur=valeur
    @multi=multi
    puts c.to_s + " - " + valeur.to_s + " - " + multi.to_s
    self
    end

    def pretty_print(inst)
    return inst.to_s + " : " + @score.to_s
    end
    def self.c_create(c,valeur,multi)
    self.new(c,valeur,multi)
    end

    def self.new(*args,valeur,multi)
    if args.count > 1 then
    super(Complex.rect(args[0].to_i,args[1].to_i),valeur,multi)
    else
    super(c,valeur,multi)
    end
    end
    alias :inspect :to_s

    end
    def self.r_create(x,y,valeur,multi)
    self.c_create(Complex.rect(x,y),valeur,multi)
    end

    MIN_SIZE = 2
    DICO = 'france2.txt'
    #DICO = '/usr/share/dict/words'
    def pretty_print(inst)
    puts @point.to_s + " : " + @valeur.to_s + " x " + @multi.to_s
    return @point.to_s + " : " + @valeur.to_s + " x " + @multi.to_s
    end

    @scores = {
    "a" => 1,
    "b" => 3,
    "c" => 3,
    "d" => 2,
    "e" => 1,
    "f" => 4,
    "g" => 2,
    "h" => 4,
    "i" => 1,
    "j" => 8,
    "k" => 10,
    "l" => 2,
    "m" => 2,
    "n" => 2,
    "o" => 1,
    "p" => 4,
    "q" => 8,
    "r" => 2,
    "s" => 1,
    "t" => 1,
    "u" => 1,
    "v" => 4,
    "w" => 10,
    "x" => 10,
    "y" => 10,
    "z" => 10
    }
    end

    class Boggle
    require 'set'

    attr_reader :words

    #def initialize(str, dict = '/usr/share/dict/words')
    # Parametres : AEIOTESTB, 123456789, DICO.txt
    def initialize(str, score = '' , dict = DICO )
    @scores = {
    "a" => 1,
    "b" => 3,
    "c" => 3,
    "d" => 2,
    "e" => 1,
    "f" => 4,
    "g" => 2,
    "h" => 4,
    "i" => 1,
    "j" => 8,
    "k" => 10,
    "l" => 2,
    "m" => 2,
    "n" => 2,
    "o" => 1,
    "p" => 4,
    "q" => 8,
    "r" => 2,
    "s" => 1,
    "t" => 1,
    "u" => 1,
    "v" => 4,
    "w" => 10,
    "x" => 10,
    "y" => 10,
    "z" => 10
    }

    #def initialize(str, dict = DICO )
    # Ouverture du dictionnaire
    @str = str.dup
    @dict = dict
    @score = score
    @dict = dict.dup

    @side = Math.sqrt(@str.length).round

    raise 'Invalid Board' unless @side ** 2 == @str.length

    # Matrice carree
    @positions = Hash.new { |h,k| h[k] = [] }
    @positionsC = Hash.new { |h,k| h[k] = [] }
    @str.each_char.with_index do |c, i|
    # Creation du point de la matrice de jeu
    @positions[c] << Point.new(i / @side, i % @side, score)
    puts @positions
    @positionsC[c] << Case.new(i / @side, i % @side, @scores[c], score.chars[i])
    @positions[c] << Point.new(i / @side, i % @side )
    end

    # Tableau des mots possibles : toutes les lettres, entre N et length fois.
    @possible = Regexp.new("^[#{@positions.keys.join}]{#{MIN_SIZE},#{@str.length}}$")
    @possible = Regexp.new("^[#{@positionsC.keys.join}]{3,#{@str.length}}$")

    @visited ||= Set.new
    end

    def solve
    if !@words
    @words = []
    puts @dict
    File.new(@dict, 'r').each_line do |word|
    word.chomp!.downcase
    @words << word if has_word?(word)
    local_score = has_word?(word)
    if local_score != 0
    @words << word
    puts "-- " + word + " : " + local_score.to_s
    end
    end
    end

    puts 'Fin solve'
    self
    end

    private

    def has_word?(word)
    return false unless word =~ @possible
    unless word =~ @possible
    return 0
    end

    # pp @positions[word][0]
    @positionsC[word[0]].each do |position|
    # pp position

    multi=1
    local_multi=1
    if position.multi == "D" then
    multi=multi*2
    elsif position.multi == "T" then
    multi=multi*3
    else
    local_multi=position.multi
    end

    @positions[word[0]].each do |position|
    return true if find(word, position)
    if (local_score=find(word, position, position.valeur.to_i * local_multi.to_i, multi )) != 0
    return local_score
    end
    end

    false
    0
    end

    def find(word, position, idx = 1, visited = @visited.clear)
    return true if idx == word.length
    def find(word, position, score=0, idx = 1, visited = @visited.clear, multi=1)
    # pp position

    visited << position
    if idx == word.length
    return score
    end

    @positions[word[idx]].each do |position2|
    # puts "P:" + position.to_s
    # puts "P2:" + position2.to_s
    # puts position.score
    if (position - position2).abs < 2 && !visited.include?(position2)
    return true if find(word, position2, idx + 1, visited)
    visited << position
    #:score = score + @scores[word]

    @positionsC[word[idx]].each do |position2|
    local_multi=1
    if position2.multi == "D" then
    multi=multi*2
    elsif position2.multi == "T" then
    multi=multi*3
    else
    local_multi=position2.multi.to_i
    end
    if (position.point - position2.point).abs < 2 && !visited.include?(position2)
    if (local_score=find(word, position2, score+position2.valeur.to_i*local_multi.to_i, idx + 1, visited,multi)) != 0
    puts multi.to_s + " - " + local_multi.to_s
    return local_score
    end
    end
    end

    #:score = score - @scores[@positions[word][idx]]
    visited.delete(position)

    false
    0
    end
    puts 'Fin init class'
    end

    require 'pp'
    @@ -178,10 +217,16 @@ def find(word, position, idx = 1, visited = @visited.clear)
    board = ARGV.shift.downcase
    scores = ARGV.shift
    puts board
    pp Point.new(1,2,4)
    puts "--- toto"

    pp Boggle.new(board,scores).solve.words.group_by(&:length)
    #pp Point.new(1,2)
    #
    t=Case.new(1,2,4,5)
    pp t
    puts t.abs
    puts "toto"

    #pp Boggle.new(board).solve.words.group_by(&:length)
    Boggle.new(board,scores).solve.words.group_by(&:length)
    #pp Boggle.new(board,scores).solve.words.group_by(&:length)
    #pp Boggle.new('cretepoeniaialsurteesaint').solve.words.group_by(&:length)
    #pp Boggle.new('crEtepoenIaIaLsurtEesAint').solve.words.group_by(&:length)
    puts 'Fin finale'
    ##pp Boggle.new('crEtepoenIaIaLsurtEesAint').solve.words.group_by(&:length)
    #puts 'Fin finale'
  12. woyczek revised this gist Oct 10, 2016. 1 changed file with 85 additions and 9 deletions.
    94 changes: 85 additions & 9 deletions boggle.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -1,10 +1,71 @@
    #!/usr/bin/env ruby
    class Point < Complex
    # Derivee de matrice (2D) aka complexe
    # def initialize(x,y,score)
    # @score = score
    # @point = super(x,y)
    # end

    #def self.new (x,y,score)
    # @score = score
    # @point = self.rectangular(x,y)
    # self
    #end

    # alias oldNew new
    def score
    @score
    end

    class << self
    alias :new :rectangular
    def score
    @score
    end

    def create (complexe,sc=1)
    @score = sc
    @c_point=complexe
    self
    end

    def new (reel,imag,sc=1)
    @score = sc
    @c_point=rectangular(reel,imag)
    self
    end

    def to_s(*args)
    super(*args) + " : " + @score.to_s
    end

    def to_x(*args)
    @c_point
    end

    def -(other)
    puts @c_point.to_s
    puts other.to_s
    result=@c_point-other.to_x
    Point.create(result,@score)
    end

    def abs
    @c_point.abs
    end

    def pretty_print(inst)
    return inst.to_s + " : " + @score.to_s
    end

    end
    alias :inspect :to_s

    end

    MIN_SIZE = 2
    DICO = 'france2.txt'
    #DICO = '/usr/share/dict/words'

    @scores = {
    "a" => 1,
    "b" => 3,
    @@ -40,21 +101,27 @@ class Boggle
    attr_reader :words

    #def initialize(str, dict = '/usr/share/dict/words')
    def initialize(str, dict = './france2.txt')
    # Parametres : AEIOTESTB, 123456789, DICO.txt
    def initialize(str, score = '' , dict = DICO )
    # Ouverture du dictionnaire
    @str = str.dup
    @dict = dict
    @score = score

    @side = Math.sqrt(@str.length).round

    raise 'Invalid Board' unless @side ** 2 == @str.length

    # Matrice carree
    @positions = Hash.new { |h,k| h[k] = [] }
    @str.each_char.with_index do |c, i|
    @positions[c] << Point.new(i / @side, i % @side)
    # Creation du point de la matrice de jeu
    @positions[c] << Point.new(i / @side, i % @side, score)
    puts @positions
    end

    @possible = Regexp.new("^[#{@positions.keys.join}]{3,#{@str.length}}$")
    # Tableau des mots possibles : toutes les lettres, entre N et length fois.
    @possible = Regexp.new("^[#{@positions.keys.join}]{#{MIN_SIZE},#{@str.length}}$")

    @visited ||= Set.new
    end
    @@ -63,11 +130,12 @@ def solve
    if !@words
    @words = []
    File.new(@dict, 'r').each_line do |word|
    word.downcase.chomp!
    word.chomp!.downcase
    @words << word if has_word?(word)
    end
    end

    puts 'Fin solve'
    self
    end

    @@ -89,6 +157,9 @@ def find(word, position, idx = 1, visited = @visited.clear)
    visited << position

    @positions[word[idx]].each do |position2|
    # puts "P:" + position.to_s
    # puts "P2:" + position2.to_s
    # puts position.score
    if (position - position2).abs < 2 && !visited.include?(position2)
    return true if find(word, position2, idx + 1, visited)
    end
    @@ -98,14 +169,19 @@ def find(word, position, idx = 1, visited = @visited.clear)

    false
    end
    puts 'Fin init class'
    end

    require 'pp'
    #pp Boggle.new('fxieamloewbxastu').solve.words.group_by(&:length)
    #
    board = ARGF.read.dowcase
    board = ARGV.shift.downcase
    scores = ARGV.shift
    puts board
    pp Point.new(1,2,4)
    puts "--- toto"

    pp Boggle.new(board).solve.words.group_by(&:length)
    pp Boggle.new('cretepoeniaialsurteesaint').solve.words.group_by(&:length)
    pp Boggle.new('crEtepoenIaIaLsurtEesAint').solve.words.group_by(&:length)
    pp Boggle.new(board,scores).solve.words.group_by(&:length)
    #pp Boggle.new('cretepoeniaialsurteesaint').solve.words.group_by(&:length)
    #pp Boggle.new('crEtepoenIaIaLsurtEesAint').solve.words.group_by(&:length)
    puts 'Fin finale'
  13. woyczek revised this gist Oct 10, 2016. 1 changed file with 8 additions and 2 deletions.
    10 changes: 8 additions & 2 deletions boggle.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -5,7 +5,7 @@ class << self
    end
    end

    @scores = hash.new {
    @scores = {
    "a" => 1,
    "b" => 3,
    "c" => 3,
    @@ -63,7 +63,7 @@ def solve
    if !@words
    @words = []
    File.new(@dict, 'r').each_line do |word|
    word.chomp!
    word.downcase.chomp!
    @words << word if has_word?(word)
    end
    end
    @@ -102,4 +102,10 @@ def find(word, position, idx = 1, visited = @visited.clear)

    require 'pp'
    #pp Boggle.new('fxieamloewbxastu').solve.words.group_by(&:length)
    #
    board = ARGF.read.dowcase
    puts board

    pp Boggle.new(board).solve.words.group_by(&:length)
    pp Boggle.new('cretepoeniaialsurteesaint').solve.words.group_by(&:length)
    pp Boggle.new('crEtepoenIaIaLsurtEesAint').solve.words.group_by(&:length)
  14. woyczek revised this gist Oct 10, 2016. 3 changed files with 515257 additions and 3 deletions.
    178,691 changes: 178,691 additions & 0 deletions anglais.txt
    View file
    178,691 additions, 0 deletions not shown because the diff is too large. Please use a local Git client to view these changes.
    38 changes: 35 additions & 3 deletions boggle.rb
    100644 → 100755
    View file
    Original file line number Diff line number Diff line change
    @@ -1,15 +1,47 @@
    #!/usr/bin/env ruby
    class Point < Complex
    class << self
    alias :new :rectangular
    end
    end

    @scores = hash.new {
    "a" => 1,
    "b" => 3,
    "c" => 3,
    "d" => 2,
    "e" => 1,
    "f" => 4,
    "g" => 2,
    "h" => 4,
    "i" => 1,
    "j" => 8,
    "k" => 10,
    "l" => 2,
    "m" => 2,
    "n" => 2,
    "o" => 1,
    "p" => 4,
    "q" => 8,
    "r" => 2,
    "s" => 1,
    "t" => 1,
    "u" => 1,
    "v" => 4,
    "w" => 10,
    "x" => 10,
    "y" => 10,
    "z" => 10
    }

    class Boggle
    require 'set'

    attr_reader :words

    def initialize(str, dict = '/usr/share/dict/words')
    #def initialize(str, dict = '/usr/share/dict/words')
    def initialize(str, dict = './france2.txt')
    # Ouverture du dictionnaire
    @str = str.dup
    @dict = dict

    @@ -69,5 +101,5 @@ def find(word, position, idx = 1, visited = @visited.clear)
    end

    require 'pp'

    pp Boggle.new('fxieamloewbxastu').solve.words.group_by(&:length)
    #pp Boggle.new('fxieamloewbxastu').solve.words.group_by(&:length)
    pp Boggle.new('cretepoeniaialsurteesaint').solve.words.group_by(&:length)
    336,531 changes: 336,531 additions & 0 deletions france2.txt
    View file
    336,531 additions, 0 deletions not shown because the diff is too large. Please use a local Git client to view these changes.
  15. @kentor kentor revised this gist Nov 1, 2013. 1 changed file with 25 additions and 23 deletions.
    48 changes: 25 additions & 23 deletions boggle.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -1,40 +1,41 @@
    require 'pp'
    class Point < Complex
    class << self
    alias :new :rectangular
    end
    end

    class Boggle
    require 'set'

    attr_reader :words

    def self.solve(str)
    new(str).solve
    end

    def initialize(str)
    def initialize(str, dict = '/usr/share/dict/words')
    @str = str.dup
    @dict = dict

    @side = Math.sqrt(@str.length).round

    raise 'Invalid Board' unless @side ** 2 == @str.length

    @positions = {}
    @positions = Hash.new { |h,k| h[k] = [] }
    @str.each_char.with_index do |c, i|
    @positions[c] ||= []
    @positions[c] << [i / @side, i % @side]
    @positions[c] << Point.new(i / @side, i % @side)
    end

    @possible = Regexp.new("^[#{@positions.keys.join}]{3,#{@str.length}}$")

    @seen ||= Set.new
    @visited ||= Set.new
    end

    def solve
    if !@words
    @words = []
    File.new('/usr/share/dict/words', 'r').each_line do |word|
    File.new(@dict, 'r').each_line do |word|
    word.chomp!
    @words << word if has_word?(word)
    end
    end

    self
    end

    @@ -43,29 +44,30 @@ def solve
    def has_word?(word)
    return false unless word =~ @possible

    @positions[word[0]].each do |x, y|
    return true if find(word, x, y)
    @positions[word[0]].each do |position|
    return true if find(word, position)
    end

    false
    end

    def find(word, x, y, idx = 1, seen = @seen.clear)
    def find(word, position, idx = 1, visited = @visited.clear)
    return true if idx == word.length

    seen << coord = x * @side + y
    visited << position

    @positions[word[idx]].each do |i, j|
    if (x-i).abs <= 1 && (y-j).abs <= 1 && !seen.include?(i * @side + j)
    return true if find(word, i, j, idx + 1, seen)
    @positions[word[idx]].each do |position2|
    if (position - position2).abs < 2 && !visited.include?(position2)
    return true if find(word, position2, idx + 1, visited)
    end
    end

    seen.delete(coord)
    visited.delete(position)

    false
    end
    end

    b = Boggle.solve('fxieamloewbxastu')
    pp b.words.group_by(&:length)
    require 'pp'

    pp Boggle.new('fxieamloewbxastu').solve.words.group_by(&:length)
  16. @kentor kentor revised this gist May 2, 2012. 1 changed file with 6 additions and 6 deletions.
    12 changes: 6 additions & 6 deletions boggle.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -3,7 +3,7 @@
    class Boggle
    require 'set'

    attr_reader :results
    attr_reader :words

    def self.solve(str)
    new(str).solve
    @@ -27,11 +27,11 @@ def initialize(str)
    end

    def solve
    if !@results
    @results = []
    File.new('words', 'r').each_line do |word|
    if !@words
    @words = []
    File.new('/usr/share/dict/words', 'r').each_line do |word|
    word.chomp!
    @results << word if has_word?(word)
    @words << word if has_word?(word)
    end
    end

    @@ -68,4 +68,4 @@ def find(word, x, y, idx = 1, seen = @seen.clear)
    end

    b = Boggle.solve('fxieamloewbxastu')
    pp b.results.group_by(&:length)
    pp b.words.group_by(&:length)
  17. @kentor kentor revised this gist May 2, 2012. 1 changed file with 19 additions and 12 deletions.
    31 changes: 19 additions & 12 deletions boggle.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -3,6 +3,12 @@
    class Boggle
    require 'set'

    attr_reader :results

    def self.solve(str)
    new(str).solve
    end

    def initialize(str)
    @str = str.dup
    @side = Math.sqrt(@str.length).round
    @@ -15,18 +21,21 @@ def initialize(str)
    @positions[c] << [i / @side, i % @side]
    end

    @possible = Regexp.new("^[#{@str.split('').uniq!.join}]{3,#{@str.length}}$")
    @possible = Regexp.new("^[#{@positions.keys.join}]{3,#{@str.length}}$")

    @seen ||= Set.new
    end

    def solve
    results = []
    File.new('words', 'r').each_line do |word|
    word.chomp!
    results << word if has_word?(word)
    if !@results
    @results = []
    File.new('words', 'r').each_line do |word|
    word.chomp!
    @results << word if has_word?(word)
    end
    end
    results.group_by(&:length)

    self
    end

    private
    @@ -44,10 +53,10 @@ def has_word?(word)
    def find(word, x, y, idx = 1, seen = @seen.clear)
    return true if idx == word.length

    seen << coord = :"#{x}#{y}"
    seen << coord = x * @side + y

    @positions[word[idx]].each do |i, j|
    if (x-i).abs <= 1 && (y-j).abs <= 1 && !seen.include?(:"#{i}#{j}")
    if (x-i).abs <= 1 && (y-j).abs <= 1 && !seen.include?(i * @side + j)
    return true if find(word, i, j, idx + 1, seen)
    end
    end
    @@ -58,7 +67,5 @@ def find(word, x, y, idx = 1, seen = @seen.clear)
    end
    end

    b = Boggle.new('dsrodgtemensrasitodgntrpreiaestsclpd')
    # b = Boggle.new('gautprmrdolaesic')
    pp b
    pp b.solve
    b = Boggle.solve('fxieamloewbxastu')
    pp b.results.group_by(&:length)
  18. @kentor kentor revised this gist May 2, 2012. 1 changed file with 17 additions and 15 deletions.
    32 changes: 17 additions & 15 deletions boggle.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -4,23 +4,25 @@ class Boggle
    require 'set'

    def initialize(str)
    @raw = str.dup
    @side = Math.sqrt(@raw.length).round
    @str = str.dup
    @side = Math.sqrt(@str.length).round

    raise "Invalid Board" unless @side ** 2 == @raw.length
    raise 'Invalid Board' unless @side ** 2 == @str.length

    @positions = {}
    @raw.each_char.with_index do |c, i|
    @str.each_char.with_index do |c, i|
    @positions[c] ||= []
    @positions[c] << [i / @side, i % @side]
    end

    @possible = Regexp.new("^[#{@raw.split('').uniq!.join}]{3,#{@raw.length}}$")
    @possible = Regexp.new("^[#{@str.split('').uniq!.join}]{3,#{@str.length}}$")

    @seen ||= Set.new
    end

    def solve
    results = []
    File.new("words", "r").each_line do |word|
    File.new('words', 'r').each_line do |word|
    word.chomp!
    results << word if has_word?(word)
    end
    @@ -33,21 +35,20 @@ def has_word?(word)
    return false unless word =~ @possible

    @positions[word[0]].each do |x, y|
    return true if dfs(word, x, y)
    return true if find(word, x, y)
    end

    false
    end

    def dfs(word, x, y, idx = 1, seen = Set.new)
    coord = :"#{x}#{y}"
    seen << coord

    def find(word, x, y, idx = 1, seen = @seen.clear)
    return true if idx == word.length

    @positions[word[idx]].each do |i,j|
    seen << coord = :"#{x}#{y}"

    @positions[word[idx]].each do |i, j|
    if (x-i).abs <= 1 && (y-j).abs <= 1 && !seen.include?(:"#{i}#{j}")
    return true if dfs(word, i, j, idx + 1, seen)
    return true if find(word, i, j, idx + 1, seen)
    end
    end

    @@ -57,6 +58,7 @@ def dfs(word, x, y, idx = 1, seen = Set.new)
    end
    end

    # b = Boggle.new('dsrodgtemensrasitodgntrpreiaestsclpd')
    b = Boggle.new('gautprmrdolaesic')
    b = Boggle.new('dsrodgtemensrasitodgntrpreiaestsclpd')
    # b = Boggle.new('gautprmrdolaesic')
    pp b
    pp b.solve
  19. @kentor kentor revised this gist May 2, 2012. 1 changed file with 3 additions and 7 deletions.
    10 changes: 3 additions & 7 deletions boggle.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -9,14 +9,10 @@ def initialize(str)

    raise "Invalid Board" unless @side ** 2 == @raw.length

    @board = @raw.chars.each_slice(@side).to_a

    @positions = {}
    @board.each_with_index do |row, i|
    row.each_with_index do |c, j|
    @positions[c] ||= []
    @positions[c] << [i, j]
    end
    @raw.each_char.with_index do |c, i|
    @positions[c] ||= []
    @positions[c] << [i / @side, i % @side]
    end

    @possible = Regexp.new("^[#{@raw.split('').uniq!.join}]{3,#{@raw.length}}$")
  20. @kentor kentor revised this gist May 2, 2012. 1 changed file with 10 additions and 16 deletions.
    26 changes: 10 additions & 16 deletions boggle.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -11,11 +11,11 @@ def initialize(str)

    @board = @raw.chars.each_slice(@side).to_a

    @starts = {}
    @positions = {}
    @board.each_with_index do |row, i|
    row.each_with_index do |c, j|
    @starts[c] ||= []
    @starts[c] << [i, j]
    @positions[c] ||= []
    @positions[c] << [i, j]
    end
    end

    @@ -24,8 +24,8 @@ def initialize(str)

    def solve
    results = []
    File.new("/usr/share/dict/words", "r").each_line do |w|
    word = w.chomp
    File.new("words", "r").each_line do |word|
    word.chomp!
    results << word if has_word?(word)
    end
    results.group_by(&:length)
    @@ -36,7 +36,7 @@ def solve
    def has_word?(word)
    return false unless word =~ @possible

    @starts[word[0]].each do |x, y|
    @positions[word[0]].each do |x, y|
    return true if dfs(word, x, y)
    end

    @@ -49,16 +49,9 @@ def dfs(word, x, y, idx = 1, seen = Set.new)

    return true if idx == word.length

    x_min = [x-1, 0].max
    x_max = [x+1, @side-1].min
    y_min = [y-1, 0].max
    y_max = [y+1, @side-1].min

    x_min.upto(x_max) do |i|
    y_min.upto(y_max) do |j|
    if @board[i][j] == word[idx] && !seen.include?(:"#{i}#{j}")
    return true if dfs(word, i, j, idx + 1, seen)
    end
    @positions[word[idx]].each do |i,j|
    if (x-i).abs <= 1 && (y-j).abs <= 1 && !seen.include?(:"#{i}#{j}")
    return true if dfs(word, i, j, idx + 1, seen)
    end
    end

    @@ -68,5 +61,6 @@ def dfs(word, x, y, idx = 1, seen = Set.new)
    end
    end

    # b = Boggle.new('dsrodgtemensrasitodgntrpreiaestsclpd')
    b = Boggle.new('gautprmrdolaesic')
    pp b.solve
  21. @kentor kentor revised this gist Apr 28, 2012. 1 changed file with 2 additions and 3 deletions.
    5 changes: 2 additions & 3 deletions boggle.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -28,7 +28,7 @@ def solve
    word = w.chomp
    results << word if has_word?(word)
    end
    results
    results.group_by(&:length)
    end

    private
    @@ -69,5 +69,4 @@ def dfs(word, x, y, idx = 1, seen = Set.new)
    end

    b = Boggle.new('gautprmrdolaesic')
    pp b
    p b.solve
    pp b.solve
  22. @kentor kentor revised this gist Apr 28, 2012. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions boggle.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -14,7 +14,7 @@ def initialize(str)
    @starts = {}
    @board.each_with_index do |row, i|
    row.each_with_index do |c, j|
    @starts[c] ||= Set.new
    @starts[c] ||= []
    @starts[c] << [i, j]
    end
    end
    @@ -45,7 +45,7 @@ def has_word?(word)

    def dfs(word, x, y, idx = 1, seen = Set.new)
    coord = :"#{x}#{y}"
    seen.add(coord)
    seen << coord

    return true if idx == word.length

  23. @kentor kentor revised this gist Apr 28, 2012. 1 changed file with 11 additions and 9 deletions.
    20 changes: 11 additions & 9 deletions boggle.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -22,6 +22,17 @@ def initialize(str)
    @possible = Regexp.new("^[#{@raw.split('').uniq!.join}]{3,#{@raw.length}}$")
    end

    def solve
    results = []
    File.new("/usr/share/dict/words", "r").each_line do |w|
    word = w.chomp
    results << word if has_word?(word)
    end
    results
    end

    private

    def has_word?(word)
    return false unless word =~ @possible

    @@ -55,15 +66,6 @@ def dfs(word, x, y, idx = 1, seen = Set.new)

    false
    end

    def solve
    results = []
    File.new("/usr/share/dict/words", "r").each_line do |w|
    word = w.chomp
    results << word if has_word?(word)
    end
    results
    end
    end

    b = Boggle.new('gautprmrdolaesic')
  24. @kentor kentor created this gist Apr 28, 2012.
    71 changes: 71 additions & 0 deletions boggle.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,71 @@
    require 'pp'

    class Boggle
    require 'set'

    def initialize(str)
    @raw = str.dup
    @side = Math.sqrt(@raw.length).round

    raise "Invalid Board" unless @side ** 2 == @raw.length

    @board = @raw.chars.each_slice(@side).to_a

    @starts = {}
    @board.each_with_index do |row, i|
    row.each_with_index do |c, j|
    @starts[c] ||= Set.new
    @starts[c] << [i, j]
    end
    end

    @possible = Regexp.new("^[#{@raw.split('').uniq!.join}]{3,#{@raw.length}}$")
    end

    def has_word?(word)
    return false unless word =~ @possible

    @starts[word[0]].each do |x, y|
    return true if dfs(word, x, y)
    end

    false
    end

    def dfs(word, x, y, idx = 1, seen = Set.new)
    coord = :"#{x}#{y}"
    seen.add(coord)

    return true if idx == word.length

    x_min = [x-1, 0].max
    x_max = [x+1, @side-1].min
    y_min = [y-1, 0].max
    y_max = [y+1, @side-1].min

    x_min.upto(x_max) do |i|
    y_min.upto(y_max) do |j|
    if @board[i][j] == word[idx] && !seen.include?(:"#{i}#{j}")
    return true if dfs(word, i, j, idx + 1, seen)
    end
    end
    end

    seen.delete(coord)

    false
    end

    def solve
    results = []
    File.new("/usr/share/dict/words", "r").each_line do |w|
    word = w.chomp
    results << word if has_word?(word)
    end
    results
    end
    end

    b = Boggle.new('gautprmrdolaesic')
    pp b
    p b.solve