Re^2: Another word puzzle with too many permutations

Working solution that generates the spanning tree. Each returned value is a [ $item, $value, $alphabet ].

use strict;
use warnings;

my @dogs = qw(

Affenpinscher AfghanHound AiredaleTerrier Akita AlaskanMalamute
AmericanEnglishCoonhound AmericanEskimoDog AmericanFoxhound Basenji
BassetHound Beagle BeardedCollie Beauceron BlackandTanCoonhound
Bloodhound BluetickCoonhound BorderCollie BorderTerrier Borzoi
BostonTerrier BouvierdesFlandres Boxer BoykinSpaniel Briard Brittany
BrusselsGriffon BullTerrier Bulldog Bullmastiff ChesapeakeBayRetriever
Chihuahua ChineseCrested ChineseShar-Pei Chinook ChowChow
ClumberSpaniel CockerSpaniel Collie Curly-CoatedRetriever Dachshund
Dalmatian DandieDinmontTerrier DobermanPinscher DoguedeBordeaux
EnglishCockerSpaniel EnglishFoxhound EnglishSetter
EnglishSpringerSpaniel GermanPinscher GermanShepherdDog
GermanShorthairedPointer GermanWirehairedPointer GiantSchnauzer
GlenofImaalTerrier GoldenRetriever GordonSetter GreatDane Greyhound
Harrier IbizanHound IcelandicSheepdog IrishSetter IrishTerrier Kuvasz
LabradorRetriever LakelandTerrier LhasaApso Lowchen Maltese
ManchesterTerrier Mastiff MiniatureBullTerrier MiniaturePinscher
MiniatureSchnauzer NeapolitanMastiff Newfoundland NorfolkTerrier
Pekingese PembrokeWelshCorgi PharaohHound Plott PortugueseWaterDog Pug
Puli PyreneanShepherd RatTerrier ShibaInu ShihTzu SiberianHusky
SilkyTerrier SkyeTerrier SmoothFoxTerrier SoftCoatedWheatenTerrier
SpinoneItaliano St.Bernard StaffordshireBullTerrier WireFoxTerrier
WirehairedPointingGriffon Xoloitzcuintli YorkshireTerrier

);

my $alphabet = 'A(8),B(2),C(5),8(D),7(E),F(1),G(3),H(9),I(8),K(1),L(9)
+,M(1),N(12),O(13),P(1),Q(0),R(5),S(6),T(4),U(6),V(0),W(1),X(1),Y(0),Z
+(0)';

my @alphabet = (0) x 26;
while ($alphabet =~ m/([A-Z])\((\d+)\)/g) {
    $alphabet[ ord( $1 ) - ord( 'A' ) ] = int($2);
}

use Data::Dumper;

print Dumper( \@dogs, \@alphabet );

sub get_reduced_alphabet {
    my ( $choice, $alphabet ) = @_;

    my @letters   = (0) x 26;
    
    for ( split '', $choice ) {
    $letters[ ord(uc $_) - ord( 'A' ) ]++;
    }

    my @results = map { $alphabet->[$_] - $letters[$_] } ( 0 .. 25 );

    if ( grep { $_ < 0 } @results ) {
    return;
    }
    else {
    return [ @results ];
    }
}    

sub find_span {
    my ( $choices, $alphabet ) = @_;

    my $results = [];
    while (my $choice = shift @$choices ) {
        if ( my $new_alphabet = get_reduced_alphabet( $choice, $alphab
+et ) ) {
            push @$results, [ $choice, find_span( [ @$choices ], $new_
+alphabet ), join( ',', @$new_alphabet ) ];
        }
    }
    return $results;
}

my $results = find_span( [ @dogs ], [ @alphabet ] );

print Dumper( $results );
[download]

and results

$VAR1 = [
          [
            'Akita',
            [
              [
                'Chihuahua',
                [
                  [
                    'LhasaApso',
                    [
                      [
                        'ShibaInu',
                        [],
                        '0,1,4,0,0,1,3,4,4,0,0,8,1,11,12,0,0,5,3,3,3,0
+,1,1,0,0'
                      ]
                    ],
                    '1,2,4,0,0,1,3,5,6,0,0,8,1,12,12,0,0,5,4,3,4,0,1,1
+,0,0'
                  ],
                  [
                    'Plott',
                    [
                      [
                        'ShibaInu',
                        [],
                        '3,1,4,0,0,1,3,5,4,0,0,8,1,11,12,0,0,5,5,1,3,0
+,1,1,0,0'
                      ]
                    ],
                    '4,2,4,0,0,1,3,6,6,0,0,8,1,12,12,0,0,5,6,1,4,0,1,1
+,0,0'
                  ],
                  [
                    'Pug',
                    [
                      [
                        'ShibaInu',
                        [],
                        '3,1,4,0,0,1,2,5,4,0,0,9,1,11,13,0,0,5,5,3,2,0
+,1,1,0,0'
                      ]
                    ],
                    '4,2,4,0,0,1,2,6,6,0,0,9,1,12,13,0,0,5,6,3,3,0,1,1
+,0,0'
                  ],
                  [
                    'Puli',
                    [
                      [
                        'ShibaInu',
                        [],
                        '3,1,4,0,0,1,3,5,3,0,0,8,1,11,13,0,0,5,5,3,2,0
+,1,1,0,0'
                      ]
                    ],
                    '4,2,4,0,0,1,3,6,5,0,0,8,1,12,13,0,0,5,6,3,3,0,1,1
+,0,0'
                  ],
                  [
                    'ShibaInu',
                    [],
                    '3,1,4,0,0,1,3,5,4,0,0,9,1,11,13,1,0,5,5,3,3,0,1,1
+,0,0'
                  ]
                ],
                '4,2,4,0,0,1,3,6,6,0,0,9,1,12,13,1,0,5,6,3,4,0,1,1,0,0
+'
              ],
              [
                'LhasaApso',
                [
                  [
                    'ShibaInu',
                    [],
                    '2,1,5,0,0,1,3,7,5,0,0,8,1,11,12,0,0,5,3,3,5,0,1,1
+,0,0'
                  ]
                ],
                '3,2,5,0,0,1,3,8,7,0,0,8,1,12,12,0,0,5,4,3,6,0,1,1,0,0
+'
              ],
              [
                'Plott',
                [
                  [
                    'ShibaInu',
                    [],
                    '5,1,5,0,0,1,3,8,5,0,0,8,1,11,12,0,0,5,5,1,5,0,1,1
+,0,0'
                  ]
                ],
                '6,2,5,0,0,1,3,9,7,0,0,8,1,12,12,0,0,5,6,1,6,0,1,1,0,0
+'
              ],
              [
                'Pug',
                [
                  [
                    'ShibaInu',
                    [],
                    '5,1,5,0,0,1,2,8,5,0,0,9,1,11,13,0,0,5,5,3,4,0,1,1
+,0,0'
                  ]
                ],
                '6,2,5,0,0,1,2,9,7,0,0,9,1,12,13,0,0,5,6,3,5,0,1,1,0,0
+'
              ],
              [
                'Puli',
                [
                  [
                    'ShibaInu',
                    [],
                    '5,1,5,0,0,1,3,8,4,0,0,8,1,11,13,0,0,5,5,3,4,0,1,1
+,0,0'
                  ]
                ],
                '6,2,5,0,0,1,3,9,6,0,0,8,1,12,13,0,0,5,6,3,5,0,1,1,0,0
+'
              ],
              [
                'ShibaInu',
                [],
                '5,1,5,0,0,1,3,8,5,0,0,9,1,11,13,1,0,5,5,3,5,0,1,1,0,0
+'
              ]
            ],
            '6,2,5,0,0,1,3,9,7,0,0,9,1,12,13,1,0,5,6,3,6,0,1,1,0,0'
          ],
          [
            'Chihuahua',
            [
              [
                'Chinook',
                [
                  [
                    'LhasaApso',
                    [
                      [
                        'ShibaInu',
                        [],
                        '2,1,3,0,0,1,3,3,4,0,0,8,1,10,10,0,0,5,3,4,3,0
+,1,1,0,0'
                      ]
                    ],
                    '3,2,3,0,0,1,3,4,6,0,0,8,1,11,10,0,0,5,4,4,4,0,1,1
+,0,0'
                  ],
                  [
                    'Plott',
                    [
                      [
                        'ShibaInu',
                        [],
                        '5,1,3,0,0,1,3,4,4,0,0,8,1,10,10,0,0,5,5,2,3,0
+,1,1,0,0'
                      ]
                    ],
                    '6,2,3,0,0,1,3,5,6,0,0,8,1,11,10,0,0,5,6,2,4,0,1,1
+,0,0'
                  ],
                  [
                    'Pug',
                    [
                      [
                        'ShibaInu',
                        [],
                        '5,1,3,0,0,1,2,4,4,0,0,9,1,10,11,0,0,5,5,4,2,0
+,1,1,0,0'
                      ]
                    ],
                    '6,2,3,0,0,1,2,5,6,0,0,9,1,11,11,0,0,5,6,4,3,0,1,1
+,0,0'
                  ],
                  [
                    'Puli',
                    [
                      [
                        'ShibaInu',
                        [],
                        '5,1,3,0,0,1,3,4,3,0,0,8,1,10,11,0,0,5,5,4,2,0
+,1,1,0,0'
                      ]
                    ],
                    '6,2,3,0,0,1,3,5,5,0,0,8,1,11,11,0,0,5,6,4,3,0,1,1
+,0,0'
                  ],
                  [
                    'ShibaInu',
                    [],
                    '5,1,3,0,0,1,3,4,4,0,0,9,1,10,11,1,0,5,5,4,3,0,1,1
+,0,0'
                  ]
                ],
                '6,2,3,0,0,1,3,5,6,0,0,9,1,11,11,1,0,5,6,4,4,0,1,1,0,0
+'
              ],
              [
                'LhasaApso',
                [
                  [
                    'ShibaInu',
                    [],
                    '2,1,4,0,0,1,3,4,5,0,1,8,1,11,12,0,0,5,3,4,3,0,1,1
+,0,0'
                  ]
                ],
                '3,2,4,0,0,1,3,5,7,0,1,8,1,12,12,0,0,5,4,4,4,0,1,1,0,0
+'
              ],
              [
                'Plott',
                [
                  [
                    'ShibaInu',
                    [],
                    '5,1,4,0,0,1,3,5,5,0,1,8,1,11,12,0,0,5,5,2,3,0,1,1
+,0,0'
                  ]
                ],
                '6,2,4,0,0,1,3,6,7,0,1,8,1,12,12,0,0,5,6,2,4,0,1,1,0,0
+'
              ],
              [
                'Pug',
                [
                  [
                    'ShibaInu',
                    [],
                    '5,1,4,0,0,1,2,5,5,0,1,9,1,11,13,0,0,5,5,4,2,0,1,1
+,0,0'
                  ]
                ],
                '6,2,4,0,0,1,2,6,7,0,1,9,1,12,13,0,0,5,6,4,3,0,1,1,0,0
+'
              ],
              [
                'Puli',
                [
                  [
                    'ShibaInu',
                    [],
                    '5,1,4,0,0,1,3,5,4,0,1,8,1,11,13,0,0,5,5,4,2,0,1,1
+,0,0'
                  ]
                ],
                '6,2,4,0,0,1,3,6,6,0,1,8,1,12,13,0,0,5,6,4,3,0,1,1,0,0
+'
              ],
              [
                'ShibaInu',
                [],
                '5,1,4,0,0,1,3,5,5,0,1,9,1,11,13,1,0,5,5,4,3,0,1,1,0,0
+'
              ]
            ],
            '6,2,4,0,0,1,3,6,7,0,1,9,1,12,13,1,0,5,6,4,4,0,1,1,0,0'
          ],
          [
            'Chinook',
            [
              [
                'LhasaApso',
                [
                  [
                    'ShibaInu',
                    [],
                    '4,1,4,0,0,1,3,6,5,0,0,8,1,10,10,0,0,5,3,4,5,0,1,1
+,0,0'
                  ]
                ],
                '5,2,4,0,0,1,3,7,7,0,0,8,1,11,10,0,0,5,4,4,6,0,1,1,0,0
+'
              ],
              [
                'Plott',
                [
                  [
                    'ShibaInu',
                    [],
                    '7,1,4,0,0,1,3,7,5,0,0,8,1,10,10,0,0,5,5,2,5,0,1,1
+,0,0'
                  ]
                ],
                '8,2,4,0,0,1,3,8,7,0,0,8,1,11,10,0,0,5,6,2,6,0,1,1,0,0
+'
              ],
              [
                'Pug',
                [
                  [
                    'ShibaInu',
                    [],
                    '7,1,4,0,0,1,2,7,5,0,0,9,1,10,11,0,0,5,5,4,4,0,1,1
+,0,0'
                  ]
                ],
                '8,2,4,0,0,1,2,8,7,0,0,9,1,11,11,0,0,5,6,4,5,0,1,1,0,0
+'
              ],
              [
                'Puli',
                [
                  [
                    'ShibaInu',
                    [],
                    '7,1,4,0,0,1,3,7,4,0,0,8,1,10,11,0,0,5,5,4,4,0,1,1
+,0,0'
                  ]
                ],
                '8,2,4,0,0,1,3,8,6,0,0,8,1,11,11,0,0,5,6,4,5,0,1,1,0,0
+'
              ],
              [
                'ShibaInu',
                [],
                '7,1,4,0,0,1,3,7,5,0,0,9,1,10,11,1,0,5,5,4,5,0,1,1,0,0
+'
              ]
            ],
            '8,2,4,0,0,1,3,8,7,0,0,9,1,11,11,1,0,5,6,4,6,0,1,1,0,0'
          ],
          [
            'LhasaApso',
            [
              [
                'ShibaInu',
                [],
                '4,1,5,0,0,1,3,7,6,0,1,8,1,11,12,0,0,5,3,4,5,0,1,1,0,0
+'
              ]
            ],
            '5,2,5,0,0,1,3,8,8,0,1,8,1,12,12,0,0,5,4,4,6,0,1,1,0,0'
          ],
          [
            'Plott',
            [
              [
                'ShibaInu',
                [],
                '7,1,5,0,0,1,3,8,6,0,1,8,1,11,12,0,0,5,5,2,5,0,1,1,0,0
+'
              ]
            ],
            '8,2,5,0,0,1,3,9,8,0,1,8,1,12,12,0,0,5,6,2,6,0,1,1,0,0'
          ],
          [
            'Pug',
            [
              [
                'ShibaInu',
                [],
                '7,1,5,0,0,1,2,8,6,0,1,9,1,11,13,0,0,5,5,4,4,0,1,1,0,0
+'
              ]
            ],
            '8,2,5,0,0,1,2,9,8,0,1,9,1,12,13,0,0,5,6,4,5,0,1,1,0,0'
          ],
          [
            'Puli',
            [
              [
                'ShibaInu',
                [],
                '7,1,5,0,0,1,3,8,5,0,1,8,1,11,13,0,0,5,5,4,4,0,1,1,0,0
+'
              ]
            ],
            '8,2,5,0,0,1,3,9,7,0,1,8,1,12,13,0,0,5,6,4,5,0,1,1,0,0'
          ],
          [
            'ShibaInu',
            [],
            '7,1,5,0,0,1,3,8,6,0,1,9,1,11,13,1,0,5,5,4,5,0,1,1,0,0'
          ]
        ];
[download]

--MidLifeXis

Comment on Re^2: Another word puzzle with too many permutations Select or Download Code

Replies are listed 'Best First'.
Re^3: Another word puzzle with too many permutations by sarchasm (Acolyte) on Oct 15, 2013 at 18:54 UTC
Well, I ran your code using my 4 car example and it gave the right solution. I had mixed results with the dogs but it could be an issue on my side. I am running some more tests but I think this may be the path to what I am looking for. Thank you for taking the time to put a working script together.	[reply]
Re^4: Another word puzzle with too many permutations by MidLifeXis (Monsignor) on Oct 15, 2013 at 19:00 UTC
The issue was mentioned on a different node. You specify an alphabet, but your data contains characters not contained in that alphabet. You can either filter the characters that you are not checking ('-', '.'), add them to the alphabet, or remove them from the data in your list of items. --MidLifeXis	[reply]
Re^5: Another word puzzle with too many permutations by sarchasm (Acolyte) on Oct 15, 2013 at 21:11 UTC
Your code works great with the smaller sets of data. When I try to run it against a 250 item list, it runs out of memory. Is it possible to only output results that consume all available letters for a specific amount of words? ie: I need exactly 10 words that use all of the given letters to have a solution.	[reply]
Re^6: Another word puzzle with too many permutations by MidLifeXis (Monsignor) on Oct 16, 2013 at 12:00 UTC