## Perl Weekly Challenge 114: Next Palindrome Number and Higher Integer Set Bits

These are some answers to the Week 114 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

*Spoiler Alert:* This weekly challenge deadline is due in a few days (May 30, 2021). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

## Task 1: Next Palindrome Number

*You are given a positive integer $N.*

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

*Example:*

```
Input: $N = 1234
Output: 1331
Input: $N = 999
Output: 1001
```

### Next Palindrome Number in Raku

In theory, we could build directly the next palindrome number from the current one. But there are different situations to cover, depending for example on whether the input number has an odd or even number of digits. Also, there are various edge cases. It is not so easy to be sure you’ve covered all possible cases. The alternative is to check each number in ascending order until you get a match. This brute force approach is much easier and in fact quite efficient for small and moderately large input numbers, as it is in most cases quite fast to find a palindrome larger than a given input number. We’ll use this second approach. We assume here that the input is a correct integer.

```
use v6;
my $input = @*ARGS[0] // 1234;
for $input .. Inf -> $candidate {
next unless $candidate eq $candidate.flip;
say $candidate;
last;
}
```

This program displays the following output:

```
$ raku ./palin.raku
1331
$ raku ./palin.raku 3445
3553
```

### Next Palindrome Number in Perl

We use the same algorithm, except that we use a `while`

loop instead of a `for`

because it is not possible to define an infinite range in Perl.

```
use strict;
use warnings;
use feature "say";
my $num = shift // 1234;
$num =~ s/^0+//; # remove leading 0s just in case
while (++ $num) {
say $num and last if $num eq reverse $num;
}
```

This program displays the following output:

```
$ perl palin.pl
1331
$ perl palin.pl 3554
3663
$ perl palin.pl 075
77
```

### Next Palindrome in Scala

Scala doesn’t have a `last`

or `break`

statement (there is a `break`

method, but it is not very practical). So we will use a `while`

loop with an explicit value incrementation.

```
object palindrome extends App {
var num = 1234
var found = 0
while (found == 0) {
if (num.toString == num.toString.reverse) {
println(num)
found = 1
}
num += 1
}
}
```

This program duly prints 1331.

### Next Palindrome in Python

```
import sys
num = int(sys.argv[1])
while (1):
if str(num) == str(num)[::-1]:
print(num)
break
num += 1
```

Output:

```
$ python3 palin.py 1234
1331
```

## Task 2: Higher Integer Set Bits

*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.*

*Example:*

```
Input: $N = 3
Output: 5
Binary representation of $N is 011. There are two 1 bits. So the next higher integer is 5 having the same the number of 1 bits i.e. 101.
Input: $N = 12
Output: 17
Binary representation of $N is 1100. There are two 1 bits.
So the next higher integer is 17 having the same number of 1 bits i.e. 10001.
```

It is easy to show that we can always find one such number with the same number of bits set to 1 for any strictly positive integer (you can just add a 1 at the front of the binary representation of the number and set any other 1 bit to 0, but that of course does not necessarily yields the next higher integer).

### Higher Integer Set Bits in Raku

To count the number of 1 bits, we just add all digits of the binary representation of the input number (in the `number_of_1`

subroutine). Then we just test all successive numbers larger than the input number until we find one that has the same number of bits set to 1.

```
use v6;
sub number_of_1 (Int $in) {
my $count = [+] $in.base(2).comb;
}
my $input = @*ARGS[0] // 3;
my $target = number_of_1 $input.Int;
for $input ^.. Inf -> $candidate {
next unless $candidate.Int.&number_of_1 == $target;
say $candidate;
last;
}
```

This program displays the following output for a few input values:

$ raku ./nextbin.raku 5

$ raku ./nextbin.raku 12 17

$ raku ./nextbin.raku 123 125

### Higher Integer Set Bits in Perl

This is essentially a port to Perl of the above Raku program with just a couple of changes: we use a loop to count the bits set to 1 and we use a `while`

loop instead of a `for`

loop

```
use strict;
use warnings;
use feature "say";
sub number_of_1 {
my $in = shift;
my $count = 0;
$count += $_ for split //, sprintf "%b", $in;
return $count;
}
my $num = shift // 3;
my $target = number_of_1 $num;
while (++ $num) {
say $num and last if $target == number_of_1 $num;
}
```

This program displays the following output for a few input values:

```
$ perl nextbin.pl
5
$ perl nextbin.pl 111
119
$ perl nextbin.pl 256
512
```

### Higher Integer Set Bits in Scala

```
object nextbin extends App {
def number_of_1(in: Int): Int = {
val binlist = in.toBinaryString.toList
var count = 0
for (char <- binlist) {
if (char == '1') count += 1
}
return count
}
var num = 111
val target = number_of_1(num)
var found = 0
while (found == 0) {
num += 1
if (number_of_1(num) == target) {
println(num)
found = 1
}
}
}
```

This program duly prints 119.

## Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on Sunday, June 6, 2021. And, please, also spread the word about the Perl Weekly Challenge if you can.

## Leave a comment