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
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
posted at: 12:55 by: Adam Russell | path: /prolog | permanent link to this entry