Judging Jenga Symmetries

Wherein we build our world layer-by-layer, piece-by-piece, then step back and look: does it appear the same from all angles, forward and back, up and down? What are its depths? What are its heights? What is at the peak of this edifice we’ve constructed?

THE WEEKLY CHALLENGE – PERL & RAKU #95

---

episode one:
“I Knew It Backwards and Forwards”

---

Task 1

Palindrome Number

Submitted by: Mohammad S Anwar

You are given a number $N.

Write a script to figure out if the given number is Palindrome. Print 1 if true otherwise 0.

Example 1:

Input: 1221
Output: 1

Example 2:

Input: -101
Output: 0, since -101 and 101- are not the same.

Example 3:

Input: 90
Output: 0

Method

Not too long ago (how time flies) we visited the idea of palindromic strings, and this challenge exists as sort of a nerfed version of that, only looking at numbers. They’re very similar ideas, written words and written numbers, but are also different in a few important ways.

Let’s just get right out in front of it right now and state that there’s no simple mathematical equation to produce palindromic numbers. The symmetries in a palindrome are wholly situated in the positional notation used to describe a given number and have little if anything to do with the value of the number in relationship to its compatriots. Just to check up on this rather bold assertion I had a look over to the Online Encyclopedia of Integer Sequences, to A002113 — Palindromes in base 10. There’s quite a lot of discussion as to properties of these well-studied numbers, but no, no formula per se was forthcoming. Also note I did qualify my statement to say there is no simple equation, as of course positional notation itself can be described mathematically, and so therefore the symmetrical nature of the digits can be in turn rigorously defined. We’ll even get to that later. But ultimately a more casual description like “the same number whether read backwards or forward” is infinitely more practical for what remains a textual distinction. It’s not so much about the value as to how you write it.

Because of this, it remains the most sensical path to treat our number as a string of characters, with one caveat: leading zeros. Leading zeros are a meaningless construct in positional numbering systems so are ignored and discounted — they are not considered part of the number, and numbers with leading zeros are not considered different numbers than the same digits without. So whereas the string 01210 is palindromic, the number 1210 is not. Conversely 0121 is the number 121, and hence palindromic, but the string is not.

Somewhat related to this line of reasoning is dealing with negative numbers. As example 2 points out, -101 and 101- are not the same number. In fact, 101- is not a number at all. Extrapolating from this, it stands to reason no negative number can be palindromic.

The last item to resolve is the range of the remaining numbers to consider, specifically to address the question of whether single digits are to be considered palindromic. Previously, when addressing strings, I had veered away from this position — I believe the word I used was “stupid”. But that was then, and this is now, and if we examine a formal positional definition of a palindrome it’s pretty clear the answer is yes.

When we looked at binary multiplication, we examined the positional number system by doing a distributive expansion of the number. For example:

123 = 1 × 10² + 2 × 10¹ + 3 × 10⁰

generalizing this we can say a number is palindromic if, for a number with k positions,

n₀ × 10^k + n₁ × 10^k-1 … n_k × 10⁰ = n_k × 10^k + n_k-1 × 10^k-1 … n₀ × 10⁰

Which is a drawn-out way of stating that if we reverse the positions of the digits, being the list n₀, n₁, … n_k, the number remains unchanged. Now with a single digit number, for example the number 3,

3 × 10⁰ = 3 × 10⁰

so we have a palindrome, QED. As this is also holds true for 0, zero joins the party as well. Negative 0, although seen in computer science, is not generally a meaningful construct, but should it wander in would be equivalent to 0, as -1 × 0 = 0, and hence palindromic. All this reasoning is borne out by another look at A002113.

PERL 5 SOLUTION

Previously I had approached this problem looking to find a regular expression to do the work of identifying palindromes for us, and because I really enjoy using regular expressions, that’s where we’ll start. It will require a bit of tuning, to allow a single digit to pass, and we’ll also need to force numification to give the correct answers should any any leading zeros be found.

The expression works by greedily matching as many characters as it can and capturing them, allowing the possibility of a central pivot digit, then reversing the capture and interpolating that reversed string back into the expression before evaluation. The (??{ ... }) construct is the magic here, a zero-width code block assertion that, in a manner analogous to the /ee eval switch, first evaluates the code block and then reevaluates the expression before continuing execution. I’m quite fond of this one.

use warnings;
use strict;
use feature ":5.26";

exit unless scalar @ARGV;

my $num = shift @ARGV;
$num += 0;

say 1 and exit if $num =~  m/^(.*).?(??{reverse($1)})$/;
say 0;

raku solution

In Raku, oddly enough, even though we require $num to be an Int, leading zeros from the input are not only accepted (which makes sense) but also still propagated (which doesn’t so much). This suggests the regex following is still looking at a string version of the value, but then again after forced numification using

$num += 0;

everything is behaving as expected again, which suggests otherwise. Not having read the Raku equivalent of perlguts it’s hard to say exactly what’s going on here.

unit sub MAIN (Int:D $num is copy) ;

$num += 0;

say
$num ~~ m:ex/^ (.*) {} .? "{$0.flip}" $/ ?? 1
                                         !! 0 ;

---

episode two:
“Stack the Deck With Hearts of Folly”

---

task 2

Demo Stack

Submitted by: Mohammad S Anwar

Write a script to demonstrate Stack operations like below:

• push($n) – add $n to the stack
• pop() – remove the top element
• top() – get the top element
• min() – return the minimum element

Example:

my $stack = Stack->new;
$stack->push(2);
$stack->push(-1);
$stack->push(0);
$stack->pop;       # removes 0
print $stack->top; # prints -1
$stack->push(0);
print $stack->min; # prints -1

Method

In the simplest construction of a stack, there are only two operations: push, to place an item on the stack, and pop to remove and return it. Like a physical stack of plates, items are accessed in a Last In, First Out manner. We’ve been requested to provide a couple of other operations on top of these two as well, to examine various aspects of the stack without altering it. These are top, to fetch the value of the last element in without removing it, and min, to provide the minimum value contained within the stack without indicating where it is located nor altering it in any way.

PERL 5 SOLUTION

Before we begin, I should note that given the built-in Perl data structures we could just use an array internally and tunnel through with the existing push and pop functions. Out in the real world should I need this functionality this is certainly the way I’d go about it, and forgo the whole object idea along with it. I mean, if you want a stack, make a list and then push and pop things on and off it. It’s already just sitting there. What, exactly, is the problem?

But we’re not going to do that. Of course not. No, the example suggests we’re being asked to create a Stack object, and so that we shall do. And I also think in the spirit of this home-brew construction we should avoid using any of the tools listed above, neither arrays nor the functions to manipulate them. It’ll be fine. We don’t need them.

Despite our intention of doing this the hard way, using the Moo object framework this whole project fell together in remarkably little time. To implement the stack all we need to do is create a linked list of objects, so we can traverse the stack to provide our min function. The Stack object will keep track of the last element added, and the individual Nodes will know their values and the location of the node immediately beneath them, to allow us to descend through the ranks.

The operations become subroutines, which we can add as we like. For the moment we’ll stick to the four that we’ve been asked to implement:

• push() creates a new Node object with the given value, setting its down attribute to the last attribute for the Stack, then updating the Stack->last attribute to the new node.
• pop returns the value of the node in Stack->last and sets the last attribute to the node’s down reference. Once unlinked the node, adrift, will be collected.
• top is easy, we only need return the value of the Stack->last node.
• min requires a tad more work, but not a lot. We start an accumulator at the top of the list with the minimum value collected so far, the value of the node at Stack->last. From there we follow the down links for the individual nodes, one to the next, assessing the value against that of our minimum and updating it accordingly. Once we reach the bottom of the stack we return the value.

There’s a small amount of bookkeeping to avoid warnings when we try to access nonexistent nodes, say when the stack is empty, but it’s not complicated. Rather than throwing an exception when we try and pop an empty stack, we simply return undef.

use warnings;
use strict;
use feature ":5.26";


package Node;
use Moo;

    has value => ( is => 'rw' );
    has down  => ( is => 'rw' );

package Stack;
use Moo;

    has last => ( is => 'rw' );

    sub push {
        my ($self, $value) = @_;
        my $node = Node->new( value => $value ,
                              down  => $self->last  );
        $self->last( $node );
    };

    sub pop {
        my $self = shift;
        my $node = $self->last;
        $self->last( $node->down );
        return $node->value;
    }

    sub top {
        my $self = shift;
       return $self->last->value;
    }

    sub min {
        my $self = shift;
        my $node = $self->last;
        my $min  = $node->value;
        while ( defined $node->down ) {
            $min = $node->down->value if $node->down->value < $min;
            $node = $node->down;
        }
        return $min;
    }

package main;

my $stack = Stack->new;
$stack->push( 2 );
$stack->push( -1 );
$stack->push( 0 );
$stack->pop;                # removes 0
say $stack->top;            # prints -1
$stack->push( 0 );
say $stack->min;            # prints -1

Raku Solution

As the Raku object system was the inspiration for Moose, which in turn was simplified into Moo, the objects in the two languages look and function quite similarly to each other. So to spice things up I decided to demonstrate the internal state of this stack — by showing the actions as they are being performed, the contents of the stack after the action, and the value returned if any. Just to be cocky I added a max function, mirroring min, that returns the maximum value contained within the stack. Because of the modular nature of the object, adding max only took a few minutes.

First the output:

================================================================================
Jan 15, 2021 at 2:02:28 PM
~/Code/PWC/95-2-jenga.raku
--------------------------------------------------------------------------------

method 'push 2'
stack now:            2

method 'push -1'
stack now:           -1  →   2

method 'push 0'
stack now:            0  →  -1  →   2

method 'pop'
stack now:           -1  →   2
returns: 0

method 'top'
stack now:           -1  →   2
returns: -1

method 'push 0'
stack now:            0  →  -1  →   2

method 'min'
stack now:            0  →  -1  →   2
returns: -1

method 'pop'
stack now:           -1  →   2
returns: 0

method 'pop'
stack now:            2
returns: -1

method 'min'
stack now:            2
returns: 2

method 'push 5'
stack now:            5  →   2

method 'max'
stack now:            5  →   2
returns: 5

… and the code. Note we also needed to add a pretty printing routine to view the list.

unit sub MAIN () ;

class Node {
    has Any  $.value is rw;
    has Node $.down  is rw;
}

class Stack {
    has Node $.last is rw;

    method push ( $value ) {
        my $node = Node.new( value => $value,
                              down => $.last  );
        $.last = $node;
        $.show_stack("method 'push $value'");
    }

    method pop () {
        return Nil if not defined $.last;
        my $value = $.last.value;
        $.last = $.last.down;
        $.show_stack("method 'pop'");
        return $value;
    }

    method top () {
        $.show_stack("method 'top'");
        return $.last.value;
    }

    method min () {
        return Nil if not defined $.last;
        my $node = $.last;
        my $min  = $node.value;
        while defined $node.down {
            $min  = min( $min, $node.down.value );
            $node = $node.down;
        }
        $.show_stack("method 'min'");
        return $min;
    }

    method max () {
        return Nil if not defined $.last;
        my $node = $.last;
        my $max  = $node.value;
        while defined $node.down {
            $max  = max( $max, $node.down.value );
            $node = $node.down;
        }
        $.show_stack("method 'max'");
        return $max;
    }


    method show_stack ($note?) {
        return Nil if not defined $.last;
        my $node = $.last;
        my @s = $node.value if defined $node;
        while defined  $node.down {
            @s.append: $node.down.value;
            $node = $node.down;
        }
        say '';
        say $note;
        say "stack now:          ", @s.fmt("%3d", ' → ');
    }
}

my $stack = Stack.new;

$stack.push(  2 );
$stack.push( -1 );
$stack.push(  0 );

say "returns: ", $stack.pop;            # removes  0
say "returns: ", $stack.top;            # returns -1

$stack.push(  0 );

say "returns: ", $stack.min;            # returns -1
say "returns: ", $stack.pop;            # removes  0
say "returns: ", $stack.pop;            # removes -1
say "returns: ", $stack.min;            # returns  2

$stack.push(  5 );

say "returns: ", $stack.max;            # returns  5