RabbitFarm

2021-10-17

A Couple of Brute Force Computations

The examples used here are from The Weekly Challenge problem statement and demonstrate the working solution.

Part 1

Write a script to generate first 5 Pandigital Numbers in base 10.

Solution


use strict;
use warnings;
##
# Write a script to generate first 5 Pandigital Numbers in base 10.
##
use boolean;

sub first_n_pandigitals {
    my ($n)         = @_;
    my $found       = false;
    my $pandigitals = [];
    my $x           = 1_000_000_000;
    do {
        my $test = $x;
        push @{$pandigitals}, $x
          if ( $test =~ tr/0//d ) > 0
          && ( $test =~ tr/1//d ) > 0
          && ( $test =~ tr/2//d ) > 0
          && ( $test =~ tr/3//d ) > 0
          && ( $test =~ tr/4//d ) > 0
          && ( $test =~ tr/5//d ) > 0
          && ( $test =~ tr/6//d ) > 0
          && ( $test =~ tr/7//d ) > 0
          && ( $test =~ tr/8//d ) > 0
          && ( $test =~ tr/9//d ) > 0;
        $found = ( @{$pandigitals} == $n );
        $x++;
    } while ( !$found );
    return $pandigitals;
}

sub first_5_pandigitals {
    return first_n_pandigitals(5);
}
MAIN: {
    my $pandigitals = first_5_pandigitals;
    for my $x ( @{$pandigitals} ) {
        print "$x\n";
    }
}

Sample Run


$ perl perl/ch-1.pl
1023456789
1023456798
1023456879
1023456897
1023456978

Notes

From the definition we know that we will need at least 10 digits and, intuitively, the first five pandigital numbers will start with 1. So then, we start with 1_000_000_000 and iterate upwards testing each candidate until we find the first five. The test used here is to determine if tr finds all the required digits.

Part 2

You are given 2 positive numbers, $m and $n. Write a script to generate multiplication table and display count of distinct terms.

Solution


use strict;
use warnings;
##
# You are given 2 positive numbers, $m and $n.
# Write a script to generate multiplcation table and display count of distinct terms.
##
sub compute_print {
    my ( $m, $n ) = @_;
    my $distinct = {};
    print " x | " . join( " ", ( 1 .. $n ) ) . "\n";
    print "---+-" . "-" x ( $n * 2 - 1 ) . "\n";
    for my $i ( 1 .. $m ) {
        print " $i | " . join( " ", map { $i * $_ } ( 1 .. $n ) ) . "\n";
        for my $j ( 1 .. $n ) {
            $distinct->{ $i * $j } = undef;
        }
    }
    return $distinct;
}
MAIN: {
    my $distinct = compute_print( 3, 3 );
    print "Distinct Terms: "
      . join( ", ", sort { $a <=> $b } keys %{$distinct} ) . "\n";
    print "Count: " . keys( %{$distinct} ) . "\n";
    print "\n\n";
    $distinct = compute_print( 3, 5 );
    print "Distinct Terms: "
      . join( ", ", sort { $a <=> $b } keys %{$distinct} ) . "\n";
    print "Count: " . keys( %{$distinct} ) . "\n";
}

Sample Run


$ perl perl/ch-2.pl
 x | 1 2 3
---+------
 1 | 1 2 3
 2 | 2 4 6
 3 | 3 6 9
Distinct Terms: 1, 2, 3, 4, 6, 9
Count: 6


 x | 1 2 3 4 5
---+----------
 1 | 1 2 3 4 5
 2 | 2 4 6 8 10
 3 | 3 6 9 12 15
Distinct Terms: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15
Count: 11

Notes

This is a perfectly Perl shaped problem. The computations can be handled in a straightforward way, especially with map. Getting rid of duplicates is done using the idiomatic method with hash keys. Finally, formatting the output cleanly is done without much undo stress. Compare what we do here to format the table with what was necessary to represent the same table in Prolog.

References

Challenge 134

Pandigital Numbers

posted at: 13:03 by: Adam Russell | path: /perl | permanent link to this entry

The Weekly Challenge 134 (Prolog Solutions)

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

Part 1

Write a script to generate first 5 Pandigital Numbers in base 10.

Solution


:-initialization(first_5_pandigitals).

pandigital(Pandigitals):-
    Digits = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
    Pandigitals = [A, B, C, D, E, F, G, H, I, J],
    fd_domain([A, B, C, D, E, F, G, H, I, J], Digits),
    A #= 1,
    B #= 0,
    fd_labeling(Pandigitals).

first_5_pandigitals:-
    setof(P, pandigital(P), Pandigitals),
    sort(Pandigitals, [A, B, C, D, E | _ ]),
    print_pandigitals([A, B, C, D, E]).

print_pandigitals([]).
print_pandigitals([H|T]):-
    maplist(number_codes, H, Codes), 
    flatten(Codes, DigitCodes), 
    number_codes(Number, DigitCodes),
    write(Number), nl,
    print_pandigitals(T). 

Sample Run


$ gplc prolog/ch-1.p 
$ prolog/ch-1   
1023456789
1023456798
1023456879
1023456897
1023456978

Notes

Rather than recursively iterate over numbers like in the Perl solution I instead use a bit of constraint programming to generate and test a large number of candidates. I then take only the first five as required. A bit of intuition, based on the definition, reduces the number of candidates generated: the first digit will clearly be a 1, the second a 0.

This runs pretty quickly, yet another testimonial to the design and implementation of GNU Prolog's FD solver. On my 2018 Mac Mini it ran to completion in about second. This is much faster than the brute force Perl solution which takes about 20s on the same machine.

Part 2

You are given 2 positive numbers, $m and $n. Write a script to generate multiplication table and display count of distinct terms.

Solution


:-initialization(main).

table(M, N, K):-
    between(1, M, I),
    between(1, N, J),
    K is I * J.

print_table(M, N, Distinct):-
    findall(K, table(M, N, K), Ks),
    setof(K, table(M, N, K), Distinct),
    print_header(M, N),
    print_seperator(M, N),
    print_rows(M, N, Ks),
    maplist(number_chars, Distinct, DistinctRow), 
    maplist(add_space, DistinctRow, DistinctSpaced),
    flatten(DistinctSpaced, DistinctSpacedFlattened),
    format("~nDistinct Terms: ~S~n", [DistinctSpacedFlattened]),
    length(Distinct, Count),
    format("Count: ~d ~n", [Count]).

print_rows(0, _, _).
print_rows(M, N, Products):-
    length(Row, N),
    append(Rest, Row, Products),
    M0 is M - 1,
    print_rows(M0, N, Rest),
    maplist(number_chars, Row, RowChars), 
    maplist(add_space, RowChars, CharsSpaced),
    flatten(CharsSpaced, CharsSpacedFlattened),
    format(" ~n  ~d | ~S ", [M, CharsSpacedFlattened]).

print_header(_, N):-
    format("  x | ", _),
    print_header(N).    
print_header(0).
print_header(N):-
    N0 is N - 1,
    print_header(N0),
    format("~d ", [N]). 

print_seperator(_, N):-
    format("~n  --+-", _),
    print_seperator(N).
print_seperator(0).
print_seperator(N):-
    N0 is N - 1,
    print_seperator(N0),
    format("~a", ['--']).

add_space(C, CS):-
    flatten(C, F),
    append(F, [' '], FS),
    atom_chars(A, FS),
    atom_chars(A, CS).       

main:-
    print_table(3, 3, _), nl, nl,
    print_table(3, 5, _),
    halt.

Sample Run


$ gplc prolog/ch-2.p
$ prolog/ch-2
  x | 1 2 3 
  --+------- 
  1 | 1 2 3   
  2 | 2 4 6   
  3 | 3 6 9  
Distinct Terms: 1 2 3 4 6 9 
Count: 6 


  x | 1 2 3 4 5 
  --+----------- 
  1 | 1 2 3 4 5   
  2 | 2 4 6 8 10   
  3 | 3 6 9 12 15  
Distinct Terms: 1 2 3 4 5 6 8 9 10 12 15 
Count: 11 

Notes

This was an interesting exercise in formatting output in Prolog! As can be seen, the vast majority of the code here is to format the table in the required way. I haven't ever done all that much with format/2, but it is quite versatile. As far as formatting output goes it provides a solid set of primitives in the spirit of C's printf that allow for us to do whatever we want, albeit with a bit of work.

The actual computation of the value takes no more than the first half dozen or so lines of code in table/3 and print_table/3.

References

Challenge 134

Pandigital Numbers

GNU Prolog format/2

posted at: 12:55 by: Adam Russell | path: /prolog | permanent link to this entry