Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

using perl to find words for scrabble

by Aldebaran (Chaplain)
on Sep 04, 2019 at 23:06 UTC ( #11105638=perlquestion: print w/replies, xml ) Need Help??

Aldebaran has asked for the wisdom of the Perl Monks concerning the following question:

Hello Monks,

I have been playing a variety of games like Scrabble and wanted to work up a perl utility to tilt the game in my favor. I've been mulling on how to capture the garden variety scrabble-like game. Clearly we need some sort of filesystem to house the lexicon of the language in question. I usually do things in other languages than english, but let's start there, as that is the current target environment. I think the gals I play with who are currently beating me would be amused at having been tagged to be within a "target environment." They've consented to let me use a perl script to help me on my phone during games, so I've downloaded Termux, and now I need to write the utility.

My basic question goes like this: Given an array of m @letters, which represents the single character tiles of the games, what english words can be formed for any subset n of m?

I think that if I tried to write my own, that I would be reinviting the wheel in significant ways, so let me throw it out there: are you aware of any existing solutions to this?

Left to my own devices, I would start enumerating cases in lexicographic order and then checking against a library whether the resulting "word" is legal. The list of words that count seems to crazy to me, with many short ones that don't get used in contemporary speech and then the absence of words I use all the time, like "perl." This is my humble start:

C:\Users\tblaz\Documents\evelyn>perl 1.letters.pl letters are a g r t u i v b o ["a", "g", "r", "t", "u", "i", "v", "b", "o"] C:\Users\tblaz\Documents\evelyn>type 1.letters.pl #!/usr/bin/perl -w use 5.016; use Data::Dump; my @letters = qw(a g r t u i v b o); say "letters are @letters"; dd \@letters; __END__ C:\Users\tblaz\Documents\evelyn>

Greetings from the volcanic buttes of the Cascades, and thank you for your comment....

Replies are listed 'Best First'.
Re: using perl to find words for scrabble
by tybalt89 (Parson) on Sep 05, 2019 at 00:13 UTC
    #!/usr/bin/perl # https://perlmonks.org/?node_id=11105638 use strict; use warnings; use Path::Tiny; my @words = grep /^[a-z]{4,}\z/ && /[aeiouy]/, # lc, size & vow +el path('/usr/share/dict/words')->lines({chomp => 1}); my @tiles = map +('a' .. 'z')[rand 26], 1 .. 9; print "tiles: @tiles\n"; my @matches; my $pattern = join '', map "$_?", sort @tiles; for my $word ( @words ) { if( join('', sort split //, $word) =~ /^$pattern$/ ) { push @matches, $word; } } print "\nmatches:\n\n@matches\n";

    Typical output:

    tiles: h l n l q g a l o matches: along gall gallon goal hall halo halon hang hogan llano loan loll long
      Typical output:

      ...indeed, as I can replicate. Thanks for your post. Yours has the advantage of getting up and running quickly and having some form of probability to try different combinations.

      C:\Users\tblaz\Documents\evelyn>perl 1.tyb.pl >1.tyb.txt C:\Users\tblaz\Documents\evelyn>type 1.tyb.txt tiles: o o y o q p i p g matches: goop goopy pipy pogy poop yogi C:\Users\tblaz\Documents\evelyn>

      I know, poop, ha-ha, but who knew pipy and pogy were english words?

      It seems to me that the method of letter generation should reflect the distribution of a given game and that a hash would be the appropriate data structure to do so. What is an elegant way to initialize the 26 key-value pairs? Frankly, there has to be a lot of initialization to pull off any game....

      distribution of letters in scrabble

      Thanks for your comments

        Simple way to do letter frequency:

        #!/usr/bin/perl # https://perlmonks.org/?node_id=11105638 use strict; use warnings; use Path::Tiny; my @letters = split //, 'aaaaaaaaabbccddddeeeeeeeeeeeeffgggghhiiiiiiii +ijkllllmmnnnnnnooooooooppqrrrrrrssssttttttuuuuvvwwxyyz'; my @tiles = @letters[map rand @letters, 1 .. 9]; print "tiles: @tiles\n"; my $pattern = join '', map "$_?", sort @tiles; my @matches = grep join('', sort split //) =~ /^$pattern$/, grep /^[@tiles]{2,}\z/ && /[aeiouy]/, # lc, size & vowel path('/usr/share/dict/words')->lines({chomp => 1}); print "\nmatches:\n\n@matches\n";
Re: using perl to find words for scrabble
by pryrt (Prior) on Sep 04, 2019 at 23:54 UTC
    I have been playing a variety of games like Scrabble and wanted to work up a perl utility to tilt the game in my favor.

    Always a fun challenge.

    are you aware of any existing solutions to this

    Games::Literati, originally by Chicheng Zhang (and now maintained by me), implements the rules for Scrabble (or Super Scrabble), Literati (the early-2000's yahoo-games clone), and Words With Friends. You can also implement custom boards, though my TODO on documenting that one has never been finished -- but if you study how the individual games are done, you should be able to figure out how to define your own gameboard function. For playing, you just have to supply a valid text dictionary file (one word per line), in whatever language you want. It originally started with Scrabble and Literati; when I took it over, I added Super Scrabble and Words With Friends (and fixed a couple scoring bugs). If you come up with a better algorithm for implementing the search than Chicheng Zhang did, and wanted to make a pull request, feel free (likely to be merged, as long as it passes all the coverage tests and doesn't change the user-interface, thus messing up my WWF-games-in-progress).

    update: link fixed. Thanks Discipulus and Corion

      I'd like to replicate what has gone before and ride that horse as far as I can. The module installs fine, and I got the dictionary downloaded. Who would have guessed that it takes 1.83 megs to capture the english language in this way? Let me post a link to the very useful page that the dictionary came from: google code archive. the entry you're looking for is enable1.txt .

      Then I try to follow the development on Games::Literati but don't seem to get anywhere on the invocation, and why would I, as right now, the command line has no connection to the dictionary?

      C:\Users\tblaz\Documents\evelyn>perl -MGames::Literati=scrabble -e'scr +abble()' < t.txt C:\Users\tblaz\Documents\evelyn>type t.txt ............... ............... ............... .......c....... ......ai....... .......s.header .......t....r.. ...jurors..soup .......o....p.h .upsilon.f..pea .......speering .........s..n.e .........t..g.. .........e..... ........broils. yes 7,8 10,14 7,14 eurmsss C:\Users\tblaz\Documents\evelyn>

      Meanwhile, I have an ordinary script as I know how to create them with the location of the dictionary as a script that does not receive reference:

      C:\Users\tblaz\Documents\evelyn>type 1.game.pl #!/usr/bin/perl -w use 5.016; use Data::Dump; my $WordFile = 'C:\Users\tblaz\Documents\html_template_data\dict\enabl +e1.txt'; C:\Users\tblaz\Documents\evelyn>

      How do I brook this gap?

      Thanks all for comments,

        My invocation is perl -e "use Games::Literati qw(wordswithfriends); $Games::Literati::WordFile = qq(/usr/dict/wordswithfriends.dict) ; wordswithfriends()" < t.txt

        Looking at your invocation: you're obviously on windows; the -e one-liner on Windows requires double-quotes, not linux single quotes; if I try with linux single quotes, I get nothing. If I convert your oneliner to double-quotes instead of single-quotes, it gives the error:

        Hashing words... Cannot open words file "./wordlist" No such file or directory at -e line 1.

        For your setup, I believe you should use perl -MGames::Literati=scrabble -e"$Games::Literati::WordFile = 'c:\users\tblaz\documents\html_template_data\dict\enable1.txt'; scrabble()" < t.txt. In your script version, $WordFile should not be a my variable; it's part of the Games::Literati module, so, as the documentation says, "These variables are exportable, so can be fully qualified as %Games::Literati::valid, or if included in the export list when you use the module, you can reference them directly", and then gives a multiline example. In your case you'll either need to use Games::Literati qw(scrabble $WordFile); $WordFile = '...';, or use the variable fully qualified variable name, as in use Games::Literati qw/scrabble/; $Games::Literati::WordFile = '...';

Re: using perl to find words for scrabble
by jcb (Hermit) on Sep 04, 2019 at 23:54 UTC

    I suggest a linear scan over a wordlist to select candidate words that contain only letters in your set. For a first pass, you could build a regex as my $pat = qr/^[$letters]+$/. You will also probably find it easier to enter a string than to directly fill in an array, and you can produce your @letters array with @letters = split //, $letters. This also means that your letters can be passed as the first command-line argument and picked up with my $letters = shift @ARGV; instead of editing the script for every turn.

    So we are at: (omitting boilerplate like use strict; and use warnings; because those should go without saying)

    my $letters = shift @ARGV; my @letters = split //, $letters; my $pat = qr/^[$letters]+$/;

    Now we have to open our wordlist file and filter out words that use letters we do not have:

    my $wordlist = 'words.en.list'; # assumed English wordlist my @words = (); { open my $words, '<', $wordlist or die "$wordlist: $! $^E"; while (<$words>) { push @words, $_ if m/$pat/ } close $words; }

    Now @words contains every legal word that we can form, and quite a few that we cannot. For example, if we have the letters "agrtuivbo", @words will contain "boot", which we cannot play, and "tuba", which we can. The other problem is the existing state of the board: what other letters can we play off of that we do not ourselves have? For simplification, I will assume that you are not actually playing Scrabble, and can only play words using letters in your current hand.

    For the next step, we must sieve by letter counts and here is an untested sub that will count letters in a word:

    sub count_letters ($) { my $word = shift; my %word = (); $word{$_}++ for split //, $word; return \%word; }

    I will leave resolving whether the letters in a word are playable given the letters that we have to the reader. (Hint: $letters is also a "word"!) Once you have a playable_word_p sub, you can filter @words with: grep {playable_word_p $letters, $_} @words.

    Enjoy!

Re: using perl to find words for scrabble -- further suggestions
by Discipulus (Abbot) on Sep 05, 2019 at 08:39 UTC
    hello Aldebaran,

    I'd go on my own because will be fun and a nice chance to improve your perl skills ;)

    My suggestions are:

    0) use strict; use warnings; (also dump from Data::Dump does not need a reference as Data::Dumper do)

    1) Sort the results by their score. This its easy and a hash with characters scores will be enough:

    use strict; use warnings; use Data::Dump; my %values; map{ $values{$_} = 1} qw(e a i o n r t l s u); map{ $values{$_} = 2} qw(d g); map{ $values{$_} = 3} qw(b c m p); map{ $values{$_} = 4} qw(f h v w y); map{ $values{$_} = 5} qw(k); map{ $values{$_} = 8} qw(j x); map{ $values{$_} = 10} qw(q z); # result words from tybalt89 example my @result_words = qw(along gall gallon goal hall halo halon hang hoga +n llano loan loll long); my %scores = words_values(@result_words); foreach my $word ( sort{ $scores{$b} <=> $scores{$a} } keys %scores ){ print "$word\tscore:\t$scores{$word}\n"; } sub words_values{ my @words = @_; my %scores = map { my $word = $_; my @chars = split '', $word; my $score; $score += $values{$_} for @chars; $word => $score; } @words; return %scores; } __DATA__ hogan score: 9 hang score: 8 halon score: 8 halo score: 7 gallon score: 7 hall score: 7 along score: 6 llano score: 5 goal score: 5 gall score: 5 long score: 5 loll score: 4 loan score: 4

    2) Scrabble is a board made of squares, so rows and columns, so it is an ArrayOfArrays. You can represent the empty board like:

    my @board = map{ [('.') x 15] } 0..14 ; print "Empty board:\n"; foreach my $row(@board){ foreach my $col( @$row ){ print $col; } print "\n"; } __DATA__ Empty board: ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ...............

    3) but the board has value modifiers for letters and for words too. You can build distinct AoA to hold these modifiers (initializing default to 1) like in my @board_letter_mod = map{ [('1') x 15]  } 0..14 ; adding by hand modifiers like in $board_letter_mod[0][3] = 3;

    Board letter modifiers( just one.. ): 111311111111111 111111111111111 111111111111111 111111111111111 111111111111111 111111111111111 111111111111111 111111111111111 111111111111111 111111111111111 111111111111111 111111111111111 111111111111111 111111111111111 111111111111111

    You can do the very same for @board_word_mod adding $board_word_mod[0][0] = 3; but..

    4) You are storing many informations for each tile in distinct structures! why do not stores them in just one structure? You can build an ArrayOfHashes intializing default values

    my @board; foreach my $row(0..14){ foreach my $col( 0..14 ){ $board[$row][$col] = { letter => '.', lett_mod => 1, word_mod +=> 1}; } } __DATA__ # will result in (first row) ( [ { lett_mod => 1, letter => ".", word_mod => 1 }, { lett_mod => 1, letter => ".", word_mod => 1 }, { lett_mod => 1, letter => ".", word_mod => 1 }, { lett_mod => 1, letter => ".", word_mod => 1 }, { lett_mod => 1, letter => ".", word_mod => 1 }, { lett_mod => 1, letter => ".", word_mod => 1 }, { lett_mod => 1, letter => ".", word_mod => 1 }, { lett_mod => 1, letter => ".", word_mod => 1 }, { lett_mod => 1, letter => ".", word_mod => 1 }, { lett_mod => 1, letter => ".", word_mod => 1 }, { lett_mod => 1, letter => ".", word_mod => 1 }, { lett_mod => 1, letter => ".", word_mod => 1 }, { lett_mod => 1, letter => ".", word_mod => 1 }, { lett_mod => 1, letter => ".", word_mod => 1 }, { lett_mod => 1, letter => ".", word_mod => 1 }, ], ...

    5) now the fun starts.. ;) You can simply modify the score based on the position on the board, computing both letter and word modifiers. But also words have to be put on the board using already present tiles. This will be difficult (but fun!): you have to consider many factors to achieve this correctly. I'd leave apart the possibility to form more than one word (valid in scrabble) because will be too complex (tybalt89 are you there? ;).

    One possible approach can be to scan the board's letters horizontally and vertically to count how many free spaces there are before and after that letter. You can now select all valid words using your own tiles and the letter already present, selecting only valid words and words that fit in empty tiles. Letters can be in reverse order too.. good luck!

    L*

    There are no rules, there are no thumbs..
    Reinvent the wheel, then learn The Wheel; may be one day you reinvent one of THE WHEELS.
Re: using perl to find words for scrabble
by atcroft (Abbot) on Sep 06, 2019 at 04:01 UTC

    I played with this a little too long, to be honest. (I also wanted to play with an inverted index, although I'm not sure if I coded that correctly or not.)

    The code below seems to do the following:

    • Run against a specified word list (default: /usr/share/dict/words).
    • Can filter on word length (min/max) and/or base word score (min/max).
    • Can have words included/excluded from the command line (but will NOT display a value that cannot be created with the tiles you specify).
    • Displays words in descending score order, then in alphabetical (case-INsensitive) order.
    • Coded to run under at least 5.10 and following (possibly even earlier).

    Enjoyed seeing what others posted on this one.

    Hope that helps.

Re: using perl to find words for scrabble
by QM (Parson) on Sep 12, 2019 at 10:52 UTC
    Years ago, here on PM, there was a TK version of a Scrabble with opponent, sort of a scrabble engine, for listing the highest scoring N plays with the current board and rack. For TM reasons, I think it was renamed Scribble or something. Unfortunately, I can't find it right now, even though I'm sure I posted in that thread, oh so many years ago.

    Can I buy a vowel?

    Update: After a little more coffee, I think this is what I meant: Scrabble Game.

    -QM
    --
    Quantum Mechanics: The dreams stuff is made of

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://11105638]
Approved by stevieb
Front-paged by haukex
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (9)
As of 2019-09-17 11:17 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    The room is dark, and your next move is ...












    Results (207 votes). Check out past polls.

    Notices?