in reply to Another word puzzle with too many permutations

How about a recursive solution where you stop when you can no longer apply the remaining alphabet to the search space? That way you don't try all combinations, but only those that have a potential of succeeding. 

# pseudocode
sub find_some ( @choices, @alphabet ) {
    $results = [];
    for $choice ( @choices ) {
        if ( choice_is_in_alphabet ) {
            @new_choices  = @choices  - $choice;
            @new_alphabet = @alphabet - letters_in( $choice );
            push @$results, [ $choice, find_some( @new_choices, @new_a
+lphabet ) ];
        }
    }
    return $results;
}

[download]

You will be left with a spanning tree of all good solutions. With a stack you could also remove the recursion.

Update: Scope error

Update 2: I have noticed a couple of minor logic errors as well, but they appear to be easy enough to correct.

--MidLifeXis

Replies are listed 'Best First'.
Re^2: Another word puzzle with too many permutations
by MidLifeXis (Monsignor) on Oct 15, 2013 at 18:13 UTC

    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

[reply]
[d/l]
[select]
      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]

        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^2: Another word puzzle with too many permutations
by sarchasm (Acolyte) on Oct 15, 2013 at 17:25 UTC
    I agree that I need to figure out some way to use the pool of letters in the process to detect when the list is going down a path that doesn't fit the solution. I will think about your pseudocode and see if I can come up with anything. Thank you.
[reply]

In Section Seekers of Perl Wisdom