#!/usr/bin/perl

use strict;

my %dic;

#load dictionary
open DIC,"< dictionary.txt" or die "$!";
while (<DIC>){
    chomp;
    my $w = uc($_);
    $w =~ s/"//g;
    if ($w =~ y/EJNQRWXDSYFTAMCIVBKULOPGHZ/01112223334455666777888999/){
        $w =~ s/[^0-9]//;
        push @{$dic{$w}},$_;
    }

}
close DIC;

# Partition the dictionary in 10 regular expressions.
# I do not know why the trie regex optimisation is not 
# supported for very large alternations (> 12000 entries).
# Changing ${^RE_TRIE_MAXBUFF} does not help

my @rex;
my @match;
for my $i (0..9){
    use re 'eval';
    my $re1  =  join ('|', grep { /^$i/ } keys %dic);
    $rex[$i] = qr{^($re1)(?{ push @match, [$-[0], $+[0]] })(*FAIL)};
}

my $num;

sub print_num {
    my $n = shift;
    $n =~ s/\ +/ /g;        # remove duplicate spaces
    $n =~ s/^\ //;          # remove leading space
    $n =~ s/\ $//;          # remove trailing space
    print "$num: $n\n";
}

sub process_num {
    my ($n,$rest,$last) = @_;
    if (length($rest)==0){
        print_num($n);
        return;
    }
    my $i = 0;
    @match=();
    for my $r (@rex){       # match all regexes
        $rest =~ /$r/;      # the result is stored in
    }                       # @match global variable
    my @matches = @match;   # and is copied locally
    for my $x (@matches){
        my $match = substr($rest,$x->[0],$x->[1]-$x->[0]);
        my $tail =  substr($rest,$x->[1]);
        for my $w (@{$dic{$match}}){   # we could have multiple words 
            my $m = $n;                # for one number
            $m =~ s/$match/ $w /;
            process_num($m,$tail,0);
        }
        $i++;
    }
    # permit only one digit if there is no match
    if (($i==0)&&($last==0)) {
        $rest=~s/.//;
        process_num($n,$rest,1);
    }
}

# Load input numbers
while (<>){
    chomp;
    my $n = $_;
    $n =~ s/[^0-9]//g;          # we are interested only in didits
    if (length($n)){            # if we have number here
        $num = $_;              # num is the original number
        process_num($n,$n,0);
    }
}