#!/usr/bin/perl
use strict;
use warnings;
use constant  WORD => 0;
use constant   LEN => 1;
use constant NFORM => 2;
use Inline C =>;

my $file = $ARGV[0] || 'dictionary.txt';
open(my $fh, '<', $file) or die "Unable to open '$file' for reading: $!";

my @word;
while (<$fh>) {
    $_ = lc;
    tr/a-z//cd;
    my %uniq = map {$_ => undef} split //;
    my $len = keys %uniq;
    push @word, [$_, $len, join '', sort keys %uniq];
}

@word = sort {$b->[LEN] <=> $a->[LEN] } @word;

for my $i (0 .. $#word - 1) {
    next if ! defined $word[$i];
    for my $j ($i + 1 .. $#word) {
        next if ! defined $word[$j];
        $word[$j] = undef if ! distinct($word[$i][NFORM], $word[$j][NFORM]);
    }
}
for (grep defined, @word) {
    print join "\t", $_->[NFORM], $_->[WORD];
    print "\n";
}
__END__
__C__

int distinct(unsigned char *str1, unsigned char *str2) {
    /* Actual code has 256 0s - truncated for post */
    char exists[256] = {};

    /* Turn array into a hash */
    while (*str1) {
        exists[*str1++] = 1;
    }

    /* Determine if str2 contains any chars str1 does not */
    while (*str2) {
        if (! exists[*str2++]) return 1;
    }
    return 0;
}

##</code><code>##

#!/usr/bin/perl
use strict;
use warnings;
use constant NEW_LET => 1;
use constant     LEN => 2;

use Inline C =>;

my $file = $ARGV[0] || 'phase1.data';
open(my $fh, '<', $file) or die "Unable to open '$file' for reading: $!";

my @word;
while (<$fh>) {
    chomp;
    push @word, [split /\t/];
}

my %seen_nform;
for my $i (0 .. $#word - 1) {
    my ($nform1, $str1) = @{$word[$i]};
    my (@new_word, %seen);
    for my $j ($i + 1 .. $#word) {
        my ($nform2, $str2) = @{$word[$j]};
        my $new_let = diff($nform2, $nform1);
        next if ! $new_let || $seen{$new_let}++;
        push @new_word, [$str2, $new_let, length($new_let)]; 
    }
    @new_word = sort { $b->[LEN] <=> $a->[LEN] } @new_word;
    for my $i2 (0 .. $#new_word - 1) {
        next if ! defined $new_word[$i2];
        for my $j2 ($i2 + 1 .. $#new_word) {
            next if ! defined $new_word[$j2];
            $new_word[$j2] = undef if ! distinct($new_word[$i2][NEW_LET], $new_word[$j2][NEW_LET]);
        }
    }
    for (grep defined, @new_word) {
        my $str2 = $_->[0];
        my %uniq = map {$_ => undef} split //, $nform1 . $str2;
        my $new_nform = join '', sort keys %uniq;
        next if $seen_nform{$new_nform}++;
        print join "\t", $new_nform, $str1, $str2;
        print "\n";
    }
}
__END__
__C__

SV* diff ( char *str1, char *str2 ) {
    SV *sv= newSVpvn( "", 0 );
    int result_index= 0;
    char *result= SvGROW( sv, 257);

    /* identify all chars present in str2 */
    while ( *str1 && *str2 ) {
        if ( *str1 < *str2) 
            result[ result_index++ ]= *str1++;
        while ( *str1 && *str1 == *str2) {
            str1++; str2++;
        }
        if ( *str1 > *str2 )
            str2++;
    }
    while (*str1) 
        result[ result_index++ ]= *str1++;

    result[ result_index ]= 0;
    SvCUR_set( sv, result_index );
    
    return sv;
}

int distinct(unsigned char *str1, unsigned char *str2) {
    /* Actual code has 256 0s - truncated for post */
    char exists[256] = {};
    /* Turn array into a hash */
    while (*str1) {
        exists[*str1++] = 1;
    }

    /* Determine if str2 contains any chars str1 does not */
    while (*str2) {
        if (! exists[*str2++]) return 1;
    }
    return 0;
}

##</code><code>##

import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Scanner;
 
public class Phase3 {
    public static final String regex = "[a-z]+";

    public static char alphabet[] = {
        'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
        'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
    };

    public static BitSet[] seen_nform = {
        new BitSet(),        new BitSet(26),       new BitSet(325),     new BitSet(2600),
        new BitSet(14950),   new BitSet(65780),    new BitSet(230230),  new BitSet(657800),
        new BitSet(1562275), new BitSet(3124550),  new BitSet(5311735), new BitSet(7726160),
        new BitSet(9657700), new BitSet(10400600), new BitSet(9657700), new BitSet(7726160),
        new BitSet(5311735), new BitSet(3124550),  new BitSet(1562275), new BitSet(657800),
        new BitSet(230230),  new BitSet(65780),    new BitSet(14950),   new BitSet(2600),
        new BitSet(325),     new BitSet(26),       new BitSet(1)
    };    

    public static HashMap<Character, Integer> lookup = new HashMap<Character, Integer>(26);


    public static void main(String[] args) {
        initlookup();
        Scanner scr1, scr2;
        String  line;
        LinkedHashMap<String, String> word = new LinkedHashMap<String, String>(3477);

        // Load phase1.data into word
        try {
            scr1 = new Scanner(new File(args[0]));
            while (scr1.hasNextLine()) {
                line  = scr1.nextLine();
                scr2  = new Scanner(line);
                word.put(scr2.next(regex), scr2.next(regex));
            }
        }
        catch (IOException ioe) {
            ioe.printStackTrace();
        }

        // Process phase2.data
        String nform, str1, str2;
        try {
            scr1 = new Scanner(new File(args[1]));
            while (scr1.hasNextLine()) {
                line  = scr1.nextLine();
                scr2  = new Scanner(line);
                nform = scr2.next(regex);
                str1  = scr2.next(regex);
                str2  = scr2.next(regex);
                HashSet<String> seen = new HashSet<String>();
                ArrayList<String[]> new_word = new ArrayList<String[]>();

                for (Map.Entry<String, String> entry : word.entrySet()) {
                    String new_nform = uniq(nform, entry.getValue());
                    int len = new_nform.length();
                    int bit = getBit(len, new_nform);
                    if (seen_nform[len].get(bit)) { continue; }
                    String new_let = diff(entry.getKey(), nform);
                    if (new_let.length() == 0 || seen.contains(new_let)) { continue; }
                    seen.add(new_let);
                    String[] e = {entry.getValue(), new_let, new_nform, Integer.toString(bit)};
                    new_word.add(e);
                }
                String[] new1, new2;
                int idx;
                int end = new_word.size();
                for (int i = 0; i < end - 1; ++i) {
                    new1 = new_word.get(i);
                    if (new1 == null) { continue; }
                    for (int j = i + 1; j < end; ++j) {
                        new2 = new_word.get(j);
                        if (new2 == null) { continue; }
                        idx = j;
                        if (new2[1].length() > new1[1].length()) {
                            String[] temp = new1;
                            new1 = new2;
                            new2 = temp;
                            idx  = i;
                        }
                        int res = distinct(new1[1], new2[1]);
                        if (res == 0) {
                            new_word.set(idx, null);
                        }
                    }
                }
                for (String[] e : new_word) {
                    if (e == null) { continue; }
                    String str3 = e[0];
                    String new_nform = e[2];
                    int len = new_nform.length();
                    int bit = Integer.decode(e[3]);
                    /* Probably not needed */
                    if (seen_nform[len].get(bit)) { continue; }
                    seen_nform[len].set(bit);
                    System.out.println(new_nform + "\t" + str1 + "\t" + str2 + "\t" + str3);
                }
            }
        }
        catch (IOException ioe) {
            ioe.printStackTrace();
        }
    }

    private static void initlookup () {
        // Actual code goes a-z, reduced for post
        lookup.put('a', new Integer("1"));
        lookup.put('b', new Integer("2"));
    }

    // Determine Chars in str1 not present in str2
    private static String diff(String str1, String str2) {
        int len = str2.length();
        HashSet<Character> have = new HashSet<Character>(len);
        for (Character c : str2.toCharArray()) {
            have.add(c);
        }
        StringBuilder new_let = new StringBuilder(len);
        for (Character c : str1.toCharArray()) {
            if (have.contains(c)) {
                continue;
            }
            new_let.append(c);
        }
        return new_let.toString();
    }

    // Determine if str2 (shorter) contains any chars not in str1 (longer)
    private static int distinct(String str1, String str2) {
        HashSet<Character> have = new HashSet<Character>(str1.length());
        for (Character c : str1.toCharArray()) {
            have.add(c);
        }
        for (Character c : str2.toCharArray()) {
            if (have.contains(c)) {
                continue;
            }
            return 1;
        }
        return 0;
    }
 
    // List of unique chars in alphabetic order in str1 & str2
    private static String uniq(String str1, String str2) {
        HashSet<Character> have = new HashSet<Character>();
        for (Character c : str1.toCharArray()) {
            have.add(c);
        }
        for (Character c : str2.toCharArray()) {
            have.add(c);
        }
        StringBuilder unique = new StringBuilder(26);
        for (char let : alphabet) {
            if (have.contains(let)) {
                unique.append(let);
            }
        }
        return unique.toString();
    }

    private static int binomial(int n, int k) {
        int c = 1;
        for (int i = 0; i < k; ++i) {
            c *= n - i;
            c /= i + 1;
        }
        return c;
    }

    private static int getBit(int len, String str) {
        int    sum = 0;
        for (int i = 0; i < len; ++i) {
            sum += binomial(lookup.get(str.charAt(i)) - 1, i + 1);
        }
        return sum;
    }
}

##</code><code>##

#!/usr/bin/perl
use strict;
use warnings;
use Inline C =>;

my $file = $ARGV[0] || 'phase1.data';
open(my $fh, '<', $file) or die "Unable to open '$file' for reading: $!";

my @word;
while (<$fh>) {
    chomp;
    my ($nform, $word) = split /\t/;
    push @word, $word;
}

$file = $ARGV[1] || 'phase3.data';
open($fh, '<', $file) or die "Unable to open '$file' for reading: $!";
while (<$fh>) {
    my ($nform, $str1, $str2, $str3) = split /\t/;
    for (@word) {
        if (! diff('abcdefghijklmnopqrstuvwxyz', $_ . $nform)) {
            print "abcdefghijklmnopqrstuvwxyz\t$_\t$str1\t$str2\t$str3";
            exit;
        }
    }
}
print "No Cigar\n";

__END__
__C__

SV *diff(char *str1, char *str2) {
    /* Actual code has 256 0s - truncated for post */
    char exists[256] = {};
    SV *ret_sv = newSVpvn("",0);
    
    /* identify all chars present in str2 */
    while (*str2) {
        exists[(U8)*str2++] = 1;
    }

    /* Determine chars in str1 not in str2 */
    for ( ; *str1 ; str1++ ) 
        if (! exists[(U8)*str1]) 
            sv_catpvn(ret_sv,str1,1);
    
    return ret_sv;
}

##</code><code>##

import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashMap;
import java.util.Scanner;
 
public class Phase5 {
    public static final String regex = "[a-z]+";

    public static BitSet[] seen = {
        new BitSet(),        new BitSet(26),       new BitSet(325),     new BitSet(2600),
        new BitSet(14950),   new BitSet(65780),    new BitSet(230230),  new BitSet(657800),
        new BitSet(1562275), new BitSet(3124550),  new BitSet(5311735), new BitSet(7726160),
        new BitSet(9657700), new BitSet(10400600), new BitSet(9657700), new BitSet(7726160),
        new BitSet(5311735), new BitSet(3124550),  new BitSet(1562275), new BitSet(657800),
        new BitSet(230230),  new BitSet(65780),    new BitSet(14950),   new BitSet(2600),
        new BitSet(325),     new BitSet(26),       new BitSet(1)
    };    

    public static HashMap<Character, Integer> lookup = new HashMap<Character, Integer>(26);

    public static void main(String[] args) {
        initlookup();
        String  line = null;
        Scanner s2   = null;
        for (String filename : args) {
            try {
                Scanner scr = new Scanner(new File(filename));
                while (scr.hasNextLine()) {
                    line = scr.nextLine();
                    s2 = new Scanner(line);
                    if (! s2.hasNext(regex)) {
                        continue;
                    }
                    getSets(s2.next(regex), line);
                }
            }
            catch (IOException ioe) {
                ioe.printStackTrace();
            }
        }
    }

    private static void initlookup () {
        // Actual code goes a-z, reduced for post
        lookup.put('a', new Integer("1"));
        lookup.put('b', new Integer("2"));
    }

    private static void getSets(String str, String line) {
        int len = str.length();
        int bit = getBit(len, str);
        if (! seen[len].get(bit)) {
            seen[len].set(bit);
            System.out.println(str + "\t" + line);
            for (StringBuilder set : subsets(str)) {
                getSets(set.toString(), line);
            }
        }
    }

    private static ArrayList<StringBuilder> subsets(String str) {
        ArrayList<StringBuilder> subs = new ArrayList<StringBuilder>();
        if (str.length() == 1) {
            return subs;
        }
        for (int i = 0; i < str.length(); ++i) {
            StringBuilder set = new StringBuilder(str);
            set.deleteCharAt(i);
            subs.add(set);
        }
        return subs;
    }

    private static int binomial(int n, int k) {
        int c = 1;
        for (int i = 0; i < k; ++i) {
            c *= n - i;
            c /= i + 1;
        }
        return c;
    }

    private static int getBit(int len, String str) {
        int    sum = 0;
        String key;
        for (int i = 0; i < len; ++i) {
            sum += binomial(lookup.get(str.charAt(i)) - 1, i + 1);
        }
        return sum;
    }
}

##</code><code>##

#!/usr/bin/perl
use strict;
use warnings;
use Storable;

my %fwd;
my $file = $ARGV[0] || 'phase1.data';
open(my $fh, '<', $file) or die "Unable to open '$file' for reading: $!";

my $n;
while ( <$fh> ) {
    chomp;
    my ($nform, $word) = split /\t/;
    $fwd{$word} = ++$n;
}

my %sol_fh;
for (1 .. 26) {
    my $file_name = sprintf("%.2d", $_) . ".data";
    open($sol_fh{$_}, '>', $file_name) or die $!;
}

$file = $ARGV[1] || 'phase5.data';
open($fh, '<', $file) or die "Unable to open '$file' for reading: $!";

while ( <$fh> ) {
    chomp;
    my ($nform, undef, @words) = split /\t/;
    $_ = $fwd{$_} for @words;
    print { $sol_fh{length($nform)} } $nform, "\t", (join "-", @words), "\n";
}

my %rev = reverse %fwd;
store \%rev, 'sol.rev';

##</code><code>##

#!/usr/bin/perl
use strict;
use warnings;
use DBD::SQLite;

my $dbh = DBI->connect("dbi:SQLite:dbname=solution.db","","") or die $DBI::errstr;

for my $size (1 .. 26) {
    my $sql = "CREATE TABLE solution$size (nform TEXT, solution TEXT)";
    $dbh->do($sql) or die $dbh->errstr;
}
$dbh->disconnect or die $dbh->errstr;

##</code><code>##

#!/usr/bin/perl -T
use strict;
use warnings;
use CGI::Simple;
use DBD::SQLite;
use HTML::Template;
use Storable;

$CGI::Simple::POST_MAX        = 1024;
$CGI::Simple::DISABLE_UPLOADS = 1;
#$CGI::Simple::DEBUG = 1;

my $q = CGI::Simple->new();

# TODO: if unable to get exclusive lock on $0 display_error()
# TODO: Add error handling - duh!

$q->param('answer') ? display_answer() : display_question();

sub display_question {
    my $template = HTML::Template->new(filename => 'question.tmpl');
    print $q->header;
    print $template->output();
    exit(0);
}

sub display_answer {
    my $template = HTML::Template->new(filename => 'answer.tmpl');
    my $input = get_input();
    my $len   = length($input);
    my $rev   = retrieve('sol.rev');
    my $dbh   = DBI->connect("dbi:SQLite:dbname=solution.db","","")
        or die $DBI::errstr;
    my $sth   = $dbh->prepare("SELECT solution FROM solution$len WHERE nform=?")
        or die $dbh->errstr;
    $sth->execute($input)                                                  or die $dbh->errstr;
    my @word;
    while (my @row = $sth->fetchrow_array() ) {
        push @word, map { {WORD => $rev->{$_}} } split /-/, $row[0];
    }
    $template->param(USER_INPUT => $input);
    $template->param(WORD_LIST  => \@word);
    print $q->header;
    print $template->output();
    #$sth->finish();
    #$dbh->disconnect;
    exit(0);
}

sub get_input {
    my $input = $q->param('question') || '';
    $input = lc($input);
    $input =~ tr/a-z//cd;
    $input ||= 'abcdefghijklmnopqrstuvwxyz';
    my %uniq = map {$_ => undef} split //, $input;
    return join '', sort keys %uniq;
}

##</code><code>##

<html>
<head><title>How many words does it take.....</title></head>
<body>
<center>
<h2>How many words does it take....</h2>
<p>
Please enter a unique list of lower case letters (a-z) below.
<br />
Be warned that some of the "words" may not be safe for work (NSFW).
</p>
<p>
<form name="display_question" action="demo.cgi">
<input type=text name="question">
<input type=hidden name="answer" value="1">
<br />
<input type="submit" value="Submit">
</form>
</p>
</center>
</body>
</html>

##</code><code>##

<html>
<head><title>It takes.....</title></head>
<body>
<center>
<h2>For <TMPL_VAR NAME=USER_INPUT> it takes....</h2>
<p>
<TMPL_LOOP NAME=WORD_LIST>
    Word: <TMPL_VAR NAME=WORD>
    <br />
</TMPL_LOOP>
</p>
</center>
</body>
</html>