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 ].

    <Reveal this spoiler or all spoilers in this node or all in this thread>
    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