RabbitFarm

2021-05-30

The Weekly Challenge 114

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

Part 1

You are given a positive integer $N. Write a script to find out the next Palindrome Number higher than the given integer $N.

Solution


use strict;
use warnings;
sub next_palindrome{
    my($n) = @_;
    {
        $n++;
        return $n if $n eq join("", reverse(split(//, $n)));
        redo;
    }
}

MAIN:{
    my($N);
    $N = 1234;
    print next_palindrome($N) . "\n";
    $N = 999;
    print next_palindrome($N) . "\n";
}

Sample Run


$ perl perl/ch-1.pl
1331
1001

Notes

This is probably the most straight forward approach to this task. Here we iterate upwards from our starting point and check each number using reverse. Since we are guaranteed of eventually finding a palindrome the loop is done (via redo) without any exit criteria or bounds checking other than returning when one is found.

Part 2

You are given a positive integer $N. Write a script to find the next higher integer having the same number of 1 bits in binary representation as $N.

Solution


use strict;
use warnings;
sub count_bits{
    my($n) = @_;
    my $total_count_set_bit = 0;
    while($n){
        my $b = $n & 1;
        $total_count_set_bit++ if $b;
        $n = $n >> 1;
    }
    return $total_count_set_bit;
}

sub next_same_bits{
    my($n) = @_;
    my $number_bits = count_bits($n);
    {
        my $next = $n + 1;
        return $next if count_bits($next) == $number_bits;
        $n = $next;
        redo;
    }
}

MAIN:{
    my($N);
    $N = 3;
    print next_same_bits($N) . "\n";
    $N = 12;
    print next_same_bits($N) . "\n";
}

Sample Run


$ perl perl/ch-2.pl
5
17

Notes

The count_bits subroutine is based on code written for Challenge 079. Otherwise, the approach to this task is very similar to what was done in the first one this week.

References

Challenge 114

posted at: 16:01 by: Adam Russell | path: /perl | permanent link to this entry

The Weekly Challenge 114 (Prolog Solutions)

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

Part 1

You are given a positive integer $N. Write a script to find out the next Palindrome Number higher than the given integer $N.

Solution


:-initialization(main).

next_palindrome(N, NextPalindrome):-
    current_prolog_flag(max_integer, MAX_INTEGER),
    N0 is N + 1,
    between(N0, MAX_INTEGER, X),
    number_chars(X, C),
    reverse(C, R),
    number_chars(NR, R),
    NR == X,
    NextPalindrome = NR.

main:-
    next_palindrome(1234, NextPalindrome0),
    write(NextPalindrome0), nl,
    next_palindrome(999, NextPalindrome1),
    write(NextPalindrome1), nl,
    halt.

Sample Run


$ gprolog --consult-file prolog/ch-1.p
GNU Prolog 1.4.5 (32 bits)
Compiled Dec  3 2020, 00:37:14 with gcc
By Daniel Diaz
Copyright (C) 1999-2020 Daniel Diaz
compiling /home/adamcrussell/Projects/perlweeklychallenge-club/challenge-114/adam-russell/prolog/ch-1.p for byte code...
/home/adamcrussell/Projects/perlweeklychallenge-club/challenge-114/adam-russell/prolog/ch-1.p compiled, 18 lines read - 1808 bytes written, 38 ms
1331
1001

Notes

The solution to this task is probably the most intuitive: check numbers starting with N and for each one reverse and check.

Part 2

You are given a positive integer $N. Write a script to find the next higher integer having the same number of 1 bits in binary representation as $N.

Solution


:-initialization(main).

set_bits(N, X):-
    set_bits(N, 0, X).
set_bits(0, X, X).
set_bits(N, X_Acc, X):-
    B is N /\ 1,
    X0 is X_Acc + B,
    N0 is N >> 1,
    set_bits(N0, X0, X), !.

next_same_bits(N, NextSameBits):-
    current_prolog_flag(max_integer, MAX_INTEGER),
    set_bits(N, NumberBits),
    N0 is N + 1,
    between(N0, MAX_INTEGER, X),
    set_bits(X, B),
    B == NumberBits,
    NextSameBits = X.

main:-
    next_same_bits(3, NextSameBits0),
    write(NextSameBits0), nl,
    next_same_bits(12, NextSameBits1),
    write(NextSameBits1), nl,
    halt.

Sample Run


$ gprolog --consult-file prolog/ch-2.p
GNU Prolog 1.4.5 (32 bits)
Compiled Dec  3 2020, 00:37:14 with gcc
By Daniel Diaz
Copyright (C) 1999-2020 Daniel Diaz
compiling /home/adamcrussell/Projects/perlweeklychallenge-club/challenge-114/adam-russell/prolog/ch-2.p for byte code...
/home/adamcrussell/Projects/perlweeklychallenge-club/challenge-114/adam-russell/prolog/ch-2.p compiled, 26 lines read - 2763 bytes written, 42 ms
5
17

Notes

set_bits/2 is code re-used from Challenge 079. Otherwise, the code is very similar to the solution to the first task.

References

Challenge 114

posted at: 15:59 by: Adam Russell | path: /prolog | permanent link to this entry