$ wc -l /usr/share/dict/words 234937 /usr/share/dict/words $ ./1056884.pl 548: a e i l n r s t $ wc -l /tmp/2of12inf.txt 81536 /tmp/2of12inf.txt $ ./1056884.pl /tmp/2of12inf.txt 337: a e i n p r s t #### #!/usr/bin/perl -w # Author: Dean Serenevy 2013 # This software is hereby placed into the public domain. use strict; use warnings; use 5.010; use Getopt::Long qw/:config bundling/; use Hash::Util qw/ lock_keys /; our $VERSION = '0.0.0'; our %OPT = ( greedy => 8, letters => 8 ); our @OPT_SPEC = qw/ help|h version noact|no-act|dry-run DEBUG greedy letters /; sub USAGE { <<"__USAGE__" }; usage: $_[0] [options] __USAGE__ $| = 1; my @ALPHABET = 'a'..'z'; use List::Util qw/ sum /; get_options( \%OPT, @OPT_SPEC ); MAIN(@ARGV); sub MAIN { my $wordlist = build_wordlist(@_); my %alphabet = (e => 1);# obvious first choice my $chosen = sum(0, values %alphabet); while ($chosen < $OPT{greedy}) { my ($opt, $count) = greedy_expand(\%alphabet, $wordlist); die "Not implemented" if @$opt > 1; $chosen += 1; add(\%alphabet, $$opt[0]); say "$count: ", str(\%alphabet); } } sub add { $_[0]{$_[1]}++ } sub del { $_[0]{$_[1]}--; delete $_[0]{$_[1]} if $_[0]{$_[1]} <= 0 } sub str { $a = shift; join " ", map +($_)x($$a{$_}), sort grep !/length/, keys %$a } sub greedy_expand { my ($alph, $words) = @_; my $best = []; my $best_count = 0; for my $l (@ALPHABET) { my $count = 0; add($alph, $l); $count += spells_part($alph, $_) for @$words; if ($count > $best_count) { @$best = ($l); $best_count = $count; } elsif ($count == $best_count) { push @$best, $l; } del($alph, $l); } return ($best, $best_count); } sub bag { my %bag = ( length => length($_[0]) ); $bag{$_}++ for split //, $_[0]; return \%bag; } sub build_wordlist { my $list = shift || "/usr/share/dict/words"; open my $F, "<", $list or die "Error reading $list: $!"; my @words; my %seen; while (defined(my $word = <$F>)) { chomp($word); $word = lc($word); next if length($word) > $OPT{letters} or $seen{$word}++; push @words, bag($word); } return \@words; } sub spells { my ($alph, $word) = @_; for my $l (%$word) { next if $l eq 'length'; return 0 if !exists($$alph{$l}) or $$alph{$l} < $$word{$l}; } return 1; } sub spells_part { my ($alph, $word) = @_; my $spare = 8 - $$word{length}; for my $l (keys %$alph) { if (!exists($$word{$l})) { $spare -= $$alph{$l}; } elsif ($$alph{$l} > $$word{$l}) { $spare -= $$alph{$l}-$$word{$l}; } return 0 if $spare < 0; } return 1; } sub get_options { my $OPT = shift; GetOptions $OPT, @_ or usage(1); usage() if $$OPT{help} || $$OPT{version}; lock_keys(%$OPT, keys %$OPT, map /^(\w+)/, @_); } sub usage { my $status = (@_ && $_[0] =~ /^\d+$/) ? shift(@_) : 0+@_; print @_, "\n" if @_; require File::Spec; my $exe = (File::Spec->splitpath($0))[2]; $OPT{$_} = $OPT{$_} ? "enabled" : "disabled" for map /^(\w+).*!/, @OPT_SPEC; print $OPT{version} ? "$exe version $VERSION\n" : USAGE($exe); exit $status; }