Perl Weekly Challenge 118: Binary Palindrome

We can split this task into two:

• Find the binary representation of the given number.
• Determine whether this is a palindrome.

For most languages, the latter is done by reversing the binary representation, and see if the result is the same string.

For our Perl solution, we use sprintf to get the binary representation of the number (using the %b format).

We could have use reverse to reverse the string, but then we would have to store the result of the sprintf in a variable. And then we would need to use two lines. Instead, we use a regular expression to test if the result of sprintf is a palindrome, so we have a one-liner as a solution:

say sprintf ("%b" => $_) =~ /^([01]?|([01])(?1)\g{2})$/ || 0 while <>;

To understand the pattern, note that we can define a palindrome in a recursive way:

Commented, the pattern looks like:

/^          # Start of string
 (          # Start of main group (which matches a palindrome)
   [01]?    # Either an empty string, or a single 0 or 1.
   |        # Or
   ([01])   # Capture a single character using second group  (0 or 1)
   (?1)     # Recurse into the main group (hence, match a palindrome)
   \g{2}    # Match what was matched by the second group
 )          # End of main group
 $/x        # End of string

Find the full program on GitHub.

First, a function to get the binary representation:

function dec2bin (dec, bin) {
    while (dec) {
        bin = dec % 2 bin
        dec = int (dec / 2)
    }
    return (bin)
}

AWK doesn't have a build in way to reverse a string, so we're just going to compare individual characters:

{
    bin = dec2bin($1)
    l   = length (bin)
    #
    # Check if it's a palindrome
    #
    for (i = 1; i < l / 2; i ++) {
        if (substr (bin, i, 1) != substr (bin, l - i + 1, 1)) {
            print (0)
            next
        }
    }
    print (1)
}

Find the full program on GitHub.

Our Bash solution looks a lot like the AWK solution. First, a function to get the binary representation:

function dec2bin () {
    dec=$1
    bin=""
    while ((dec > 0))
    do    bin=$((dec % 2))$bin
          ((dec /= 2))
    done
}

It puts the result in the global variable bin.

No build in method to reverse a string, so we compare characters again:

while read dec
do    dec2bin $dec
      for ((i = 0; i < ${#bin} / 2; i ++))
      do  if   [ "${bin:$i:1}" = "${bin:$((${#bin} - i - 1)):1}" ]
          then continue
          fi
          echo 0
          continue 2
      done
      echo 1
done

Find the full program on GitHub.

In C, we will not get a binary representation. Instead, we compare bits directly. First, we read the input, and find the highest power of two equal or less than the given number. This corresponds to the the first 1 in its binary representation:

long long dec;
while (scanf ("%lld", &dec) == 1) {
    long long i = 1;
    int k = 0;
    for (k = 0; i <= dec; k ++, i = i << 1);
    /*
     * We overshot by 1
     */
    k -= 1;

So, now we have: \(2^k \leq \text{dec} < 2^{k+1}\).

We now know that the number has \(k + 1\) bits. We now check for each pair \(0 \leq i < j \leq k, i + j = k\) if bits \(i\) and \(j\) are either both set, or both unset in the given number. If this is true for all such pairs, the binary representation is a number:

int is_palin = 1;
for (int j = 0; j < k; k --, j ++) {
    if (((dec & (1 << j)) >> j) != ((dec & (1 << k)) >> k)) {
        is_palin = 0;
        break;
    }
}
printf ("%d\n", is_palin);

Find the full program on GitHub.

For Go, we start off with a helper function which returns the reverse of a string:

func reverse (str string) string {
    rev := [] rune (str)
    for i, j := 0, len (rev) - 1; i < j; i, j = i + 1, j - 1 {
        rev [i], rev [j] = rev [j], rev [i]
    }
    return string (rev)
}

To get the binary representation of an integer, we make use of the FormatInt method in the strconv package. Which leads to the following main program:

func main () {
    var dec int64
    for {
        var n, err = fmt . Scanf ("%d", &dec)
        if (n != 1 || err != nil) {
            break
        }
        var bin = strconv . FormatInt (dec, 2)
        if (bin == reverse (bin)) {
            fmt . Println (1)
        } else {
            fmt . Println (0)
        }
    }
}

Find the full program on GitHub.

Java has the toBinaryString method in the Integer class, which we use to get the binary representation of the number. The StringBuilder class has a reverse method.

So we get:

public class ch1 {
    public static void main (String [] args) {
        Scanner scanner = new Scanner (System . in);
        try {
            while (true) {
                int    dec = scanner . nextInt ();
                String bin = Integer . toBinaryString (dec);

                if (bin . equals (new StringBuilder (bin) .
                                  reverse () . toString ())) {
                    System . out . println (1);
                }
                else {
                    System . out . println (0);
                }
            }
        }
        catch (Exception e) {
            //   
            // EOF
            //
        }
    }
}

Find the full program on GitHub.

To get the binary representation of a number:

function dec2bin (dec)
    local bin = {}
    while dec > 0 do 
        bin [#bin + 1] = dec % 2
        dec = math . floor (dec / 2)
    end
    return table . concat (bin)
end

It collects the bits into a table, which at the end it concats into a single string.

To check for a palindrome, we reverse the string and compare:

for line in io . lines () do
    bin = dec2bin (tonumber (line))
    if bin == string . reverse (bin) then
        print (1)
    else
        print (0)
    end
end

Find the full program on GitHub.

In Node.js, it's easy to get the binary representation of a number: toString (2). Node.js does not have a reverse acting on a string, but it does have a reverse acting on an array. So, to reverse a string, we split it into an array of characters, reverse the array, then join it back together.

This leads to the following lines (at this point, the read in number is in the string variable line):

let bin = (+line) . toString (2)
console . log (bin == bin . split ("") . reverse () . join ("") ? 1 : 0)

Find the full program on GitHub.

To get a binary representation, we use format, using {:b} as the format string (line is our input):

bin = '{:b}' . format (int (line))

Reversing a string is done by taking a slice of the string, getting all the characters but stepping one-by-one from the end:

if bin == bin [::-1]:
    print (1)
else:
    print (0)

Find the full program on GitHub.

bin = "%b" % dec

puts (bin == bin . reverse ? 1 : 0)