#!/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 l
+etters /;
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 !/lengt
+h/, 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;
}
[download]