RabbitFarm

2022-07-17

Suffering Succotash!

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 if the given number is an Esthetic Number.

Solution


use strict;
use warnings;
use boolean;

sub is_esthetic{
    my($n) = @_;
    my @digits = split(//, $n);
    my $d0 = pop @digits;
    while(@digits){
        my $d1 = pop @digits;
        return false if abs($d1 - $d0) != 1;
        $d0 = $d1;
    }
    return true;
}

MAIN:{
    my $n;
    $n = 5456;
    print "$n is ";
    print "esthetic\n" if is_esthetic($n);
    print "not esthetic\n" if !is_esthetic($n);
    $n = 120; 
    print "$n is ";
    print "esthetic\n" if is_esthetic($n);
    print "not esthetic\n" if !is_esthetic($n);
}

Sample Run


$ perl perl/ch-1.pl
5456 is esthetic
120 is not esthetic

Notes

I started to write this solution and then kept coming back to it, considering if there is a more elegant approach. If there is I could not come up with it on my own over this past week! This doesn't seem all that bad, just a bit "mechanical" perhaps?

  1. Break the number into an array of digits
  2. Do a pairwise comparison of successive digits by popping them off the array one at a time and retaining the most recently popped digit for the next iteration's comparison.
  3. If at any point the "different by 1" requirement is not met, return false.
  4. If we complete all comparisons without a failure, return true.

Part 2

Write a script to generate first 10 members of Sylvester's sequence.

Solution


use strict;
use warnings;
use bigint; 

sub sylvester_n{
    my($n) = @_;
    my @terms = (2, 3);
    my %product_table;
    $product_table{"2,3"} = 6;
    while(@terms < $n){
        my $term_key = join(",", @terms);
        my $term = $product_table{$term_key} + 1;
        push @terms, $term;
        $product_table{"$term_key,$term"} = $term * $product_table{$term_key}; 
    }
    return @terms;
}


MAIN:{
    print join(", ", sylvester_n(10)). "\n";
}

Sample Run


$ perl perl/ch-2.pl
2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443, 12864938683278671740537145998360961546653259485195807, 165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443

Notes

Much like the first part I considered what might be an optimal way to compute this. Here the standard recursion and memoization would be most appropriate, I believe. Just to mix things up a little I implemented my own memoization like lookup table and computed the terms iteratively. Otherwise though, the effect is largely the same in that for each new term we need not reproduce any previous multiplications.

These terms get large almost immediately! use bigint is clearly necessary here. An additional optimization would be the use of Tie::Hash and Tie::Array to save memory as we compute larger and larger terms. Since TWC 173.2 only specified 10 terms I left that unimplemented.

Finally, I should note that the title of this blog draws from Sylvester the Cat, not Sylvester the Mathematician! Sylvester the Cat's famous phrase is "Suffering Succotash!". See the link in the references for an example. Not everyone may not be familiar, so see the video link below! The comments on that video have some interesting facts about the phrase and the character.

References

Challenge 173

Thufferin' thuccotash!

posted at: 21:30 by: Adam Russell | path: /perl | permanent link to this entry