RabbitFarm
2022-05-15
The Weekly Challenge 164 (Prolog Solutions)
The examples used here are from the weekly challenge problem statement and demonstrate the working solution.
Part 1
Write a script to find all prime numbers less than 1000, which are also palindromes in base 10.
Solution
:-initialization(main).
palindrome(X):-
fd_labeling(X),
number_codes(X, C),
reverse(C, CR),
number_codes(X, CR).
palindrome_primes(N, PalindromePrimes, NumberPrimes):-
fd_labeling(NumberPrimes),
length(Primes, NumberPrimes),
fd_domain(Primes, 1, N),
fd_all_different(Primes),
maplist(palindrome, Primes),
maplist(fd_prime, Primes),
fd_labeling(Primes),
PalindromePrimes = Primes.
palindrome_primes(N, Primes):-
NP is N // 2,
fd_domain(NumberPrimes, 1, NP),
fd_maximize(palindrome_primes(N, Primes, NumberPrimes), NumberPrimes).
palindrome_prime(N, Prime):-
between(1, N, Prime),
palindrome(Prime),
fd_prime(Prime).
pp(_, _) --> [].
pp(N, Seen) --> [X], {palindrome_prime(N, X), \+ member(X, Seen)}, pp(N, [X|Seen]).
main:-
findall(Prime, palindrome_prime(1000, Prime), PalindromePrimes),
write(PalindromePrimes), nl.
Sample Run
$ gprolog --consult-file prolog/ch-1.p
[2,3,5,7,11,101,131,151,181,191,313,353,373,383,727,757,787,797,919,929]
| ?- phrase(pp(1000, []), PalindromePrimes).
PalindromePrimes = [] ? ;
PalindromePrimes = [2] ? ;
PalindromePrimes = [2,3] ? ;
PalindromePrimes = [2,3,5] ? ;
PalindromePrimes = [2,3,5,7] ? ;
PalindromePrimes = [2,3,5,7,11] ? ;
PalindromePrimes = [2,3,5,7,11,101] ? ;
PalindromePrimes = [2,3,5,7,11,101,131] ? ;
PalindromePrimes = [2,3,5,7,11,101,131,151] ? ;
PalindromePrimes = [2,3,5,7,11,101,131,151,181] ? ;
PalindromePrimes = [2,3,5,7,11,101,131,151,181,191] ? ;
PalindromePrimes = [2,3,5,7,11,101,131,151,181,191,313] ?
.
.
.
Notes
I experimented with a few different ways to generate Palindrome Primes. The quickest and
most efficient way is what is used in main/0
. Now, suppose we wanted to reason about
lists of such numbers versus just generating them there is also a DCG option as shown
which will generate or validate all possible lists of Palindrome Primes. Finally, there is
the extremely inefficient method using constraints to maximize the size of the list of
Palindrome Primes under 1000. This works! Now, does it work "well"? Absolutely not! This
is not a very good method for performing the task and is many orders of magnitude slower
than the other two. I will admit to an odd satisfaction to getting this unusual approach
work, however.
Part 2
Given a list of numbers, generate the skip summations.
Solution
:-initialization(main).
pdi(0, Total, Total).
pdi(N, Total_, Total):-
N_ is N // 10,
Total__ is Total_ + round(mod(N, 10) ** 2),
pdi(N_, Total__, Total).
pdi(N, Total):-
pdi(N, 0, Total).
happy(1, _).
happy(N, Seen):-
\+ member(N, Seen),
pdi(N, Total),!,
N_ is Total,
happy(N_, [N|Seen]).
happy(N):-
happy(N, []).
happy(_) --> [].
happy(Seen) --> [X], {between(1, 100, X), \+ member(X, Seen), happy(X)}, happy([X|Seen]).
main:-
length(Happy, 8),
phrase(happy([]), Happy),
write(Happy), nl.
Sample Run
$ gprolog --consult-file prolog/ch-2.p
[1,7,10,13,19,23,28,31]
Notes
As with the code in the first part I also implemented this as a DCG. Here a DCG is more practical since we are asked specifically to generate a list of the first 8 Happy Numbers. This is more of a "list reasoning" task than how the Palindrome Prime question was asked.
References
posted at: 23:58 by: Adam Russell | path: /prolog | permanent link to this entry
Happily Computing Prime Palindrome Numbers
The examples used here are from the weekly challenge problem statement and demonstrate the working solution.
Part 1
Write a script to find all prime numbers less than 1000, which are also palindromes in base 10.
Solution
use strict;
use warnings;
use Math::Primality qw/is_prime/;
sub palindrome_primes_under{
my($n) = shift;
my @palindrome_primes;
{
$n--;
unshift @palindrome_primes, $n if(is_prime($n) && join("", reverse(split(//, $n))) == $n);
redo if $n > 1;
}
return @palindrome_primes;
}
MAIN:{
print join(", ", palindrome_primes_under(1000));
}
Sample Run
$ perl perl/ch-1.pl
2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929
Notes
I have become incorrigible in my use of redo
! The novelty just hasn't worn off I
suppose. There is nothing really wrong with it, of course, it's just not particularly
modern convention what with it's vaguely goto
like behavior. Anyway, there's not a whole
lot to cover here. All the real work is done in the one line which tests both primality
and, uh, palindromedary.
Part 2
Write a script to find the first 8 Happy Numbers in base 10.
Solution
use strict;
use warnings;
use boolean;
use constant N => 8;
sub happy{
my $n = shift;
my @seen;
my $pdi = sub{
my $n = shift;
my $total = 0;
{
$total += ($n % 10)**2;
$n = int($n / 10);
redo if $n > 0;
}
return $total;
};
{
push @seen, $n;
$n = $pdi->($n);
redo if $n > 1 && (grep {$_ == $n} @seen) == 0;
}
return boolean($n == 1);
}
MAIN:{
my $i = 0;
my @happy;
{
$i++;
push @happy, $i if happy($i);
redo if @happy < N;
}
print join(", ", @happy) . "\n";
}
Sample Run
$ perl perl/ch-2.pl
1, 7, 10, 13, 19, 23, 28, 31
Notes
This solution has even more redo
, huzzah! Again, fairly straightforward bit of code
which follows the definitions. The happiness check is done using a perfect digit
invariant (PDI) function, here rendered as an anonymous inner subroutine. A good chance
here when looking at this code to remind ourselves that $n
inside that anonymous
subroutine is in a different scope and does not effect the outer $n
!
References
posted at: 23:58 by: Adam Russell | path: /perl | permanent link to this entry