Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
BrowserUk,
The following code should produce the correct output. I have tested it individually on a handful of the "expected output" numbers. I am going to let it run overnight to see how long it takes. Using perl -MO=Deparse solution.pl | wc -l it is 44 lines of code.
#!/usr/bin/perl use strict; use warnings; use Algorithm::Loops qw/NextPermute NestedLoops/; use Integer::Partition::Unrestricted; # see http://perlmonks.org/?node +_id=533164 my %lookup = ( E => 0, e => 0, J => 1, j => 1, N => 1, n => 1, Q => 1, q => 1, R +=> 2, r => 2, W => 2, w => 2, X => 2, x => 2, D => 3, d => 3, S => 3, s => 3, Y +=> 3, y => 3, F => 4, f => 4, T => 4, t => 4, A => 5, a => 5, M => 5, m => 5, C +=> 6, c => 6, I => 6, i => 6, V => 6, v => 6, B => 7, b => 7, K => 7, k => 7, U +=> 7, u => 7, L => 8, l => 8, O => 8, o => 8, P => 8, p => 8, G => 9, g => 9, H +=> 9, h => 9, Z => 9, z => 9 ); my ($fh, $part, %data) = (undef, Integer::Partition::Unrestricted->new +(), ()); open($fh, '<', 'dictionary.txt') or die "Unable to open 'dictionary.tx +t' for reading: $!"; while (<$fh>) { chomp; my $num = join '', map {defined $lookup{$_} ? $lookup{$_} : ()} sp +lit //, $_; push @{$data{$num}}, $_; } $data{$_} = [$_] for 0 .. 9; open($fh, '<', 'input.txt') or die "Unable to open 'input.txt' for rea +ding: $!"; while (<$fh>) { chomp; my $num = $_; $num =~ s/\D//g; my $next = $part->gen_iter(length($num)); while (my @part = sort {$a <=> $b} $next->()) { my $ones = "@part" =~ tr/1//; next if $ones > ((@part - 1) / 2 + 1); my $ok = 1; while ($ok) { next if "@part" =~ /\b1 1\b/; my $template = join '', map {'A' . $_} @part; my @dig = unpack($template, $num); next if grep {! defined $data{$_}} @dig; my @solution = map {[@{$data{$_}}]} @dig; my $iter = NestedLoops( \@solution ); while (my @list = $iter->()) { print "$_: @list\n"; } } continue { $ok = NextPermute(@part); } } }

In a nutshell, it generates the unrestricted integer partitions of the number. It skips over any partitioning that has so many 1s it could not satisfy the problem constraints. It then generates all permutations of each possible partition - skipping over partitioning with two adjacent 1s. It then checks if it produces a valid solution. I am sure it could be optimized a lot, but that would add code complexity and lines of code.

Update: Shortly after posting, I realized by re-arranging some logic it would be more efficient. The node has been updated to reflect that.

Cheers - L~R


In reply to Re: One for the weekend: challenge by Limbic~Region
in thread One for the weekend: challenge by BrowserUk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others chanting in the Monastery: (6)
    As of 2014-08-29 00:26 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      The best computer themed movie is:











      Results (275 votes), past polls