PWC 193

PWC 193

Caveat that my scripts are all first pass solutions (I think it shows :-). Not optimized. 

Challenge 1 (Binary string)

We are given an integer n say, and asked to print out all the binary numbers of length n or less.

This is a one-liner in all three languages. In my scripts, n is read from the command line. Here it is for n=3.

In Perl 5:

perl -e 'for (eval ("0b".(0 x $ARGV[0]). ".." . "0b". (1 x $ARGV[0]))){printf("%b\n",$_)}' 3

In Raku:

raku -e 'use MONKEY-SEE-NO-EVAL; for (EVAL("0b" ~ (0 x @*ARGS[0]) ~ ".." ~ "0b" ~ (1 x @*ARGS[0]))) {printf("%b\n",Int($_))}' 3

In Julia:

julia -e 'for i in (parse( Int64, "0b" * repeat( "0", parse( Int64,ARGS[1] ))) : parse( Int64, "0b" * repeat( "1", parse(Int64, ARGS[1] )))); println( SubString( bitstring(i), 65-parse(Int64, ARGS[1]))); end;' 3

In all three languages, I iterate through the range 0b0 to 0b111.. (with n 1's), printing in binary format. Julia's version of printf does not have a "%b" format. But they do have a type called a bitstring, which is simply a binary number represented as a 64-character string. One just prints this string, chopping off  unwanted leading zeroes.

Challenge 2 (Odd string)

In this challenge, we are given a puzzle to solve. The puzzle consists of a list of strings, where all the input strings are the same length, and all the input strings are alphabetic, made up only of characters from the set [a-z].

All the strings but one satisfy the following property:

Suppose we compute the differences between the alphabet positions (e.g., 'a' is 1 and 'z' is 26) of adjacent characters in the string and store these in an array (e.g., for 'abc' we have 2 for b minus 1 for a giving 1, and then 3 for c minus 2 for b giving 1, so that the array is (1,1).)

Then these arrays will be the same for every string in the list, except one.

We are asked to find that one string.

For this challenge, the input needs to be just so.  I assume that the input requirements are met and do not consider input validation or exception handling.

Raku

I started with Raku.

Here is my Raku script.

I start by storing the 'a' .. 'z' => 1 .. 26 encodings in a global ("our") hash.

I next have two versions of a difference-array subroutine. One (inner) version computes the array of distances for a given string. Another (outer) version loops through the input array applying the inner version to each string therein. In the outer version, it is convenient to return not just the array of difference arrays, but also a hash linking each difference array to the string that engendered it.

To find the one non-conforming distance array, I first create a hash (the my-bag subroutine). This loops through the array of distance arrays, setting each element (an array) stringified as a hash key, and a counter as the corresponding value.

    for (@difference-array) -> @s {
        %retval{@s.raku}++;
  }

We can then find the odd string by finding the key of the hash outputted by &my-bag that has 1 as its corresponding value (We assume that our input matches the task specification and that there is exactly one and only one such key). This key is a difference array rather than the corresponding original input string, so we look up the hash we created earlier in the outer version of difference-array to get the string. Here is the main routine:

multi sub odd-string( @s ) {
    my @difference-array=&difference-array(@s);
    @difference-array[1]{(&odd-string(&my-bag(@difference-array[0])))};
}

Perl 5

In Perl 5, I decided to restrict myself to the minimal subset of the syntax inherited from Perl 4. 

Here is my Perl 5 script.

The core of the script is a subroutine odd_string, which contains several nested sub-subroutines that get called in sequence. &difference_array computes the difference array for a given string. &difference_array_loop loops through a list of strings storing the difference array for each one (stringified). &mybag uses a hash to count the occurrences of each difference array. Finally in the main section of odd_string, we identify the difference array with only one occurrence and return its corresponding original string.

local (@s)=@_;
    
local @difference_array_loop = &difference_array_loop;
local %mybag = &mybag(@difference_array_loop);
 
for (0 .. @difference_array_loop-1) {
    return $s[$_] if $mybag{$difference_array_loop[$_]}==1;
}

I was tempted to refactor by calling difference_array_loop just difference_array, and nesting the inner difference_array subroutine (operating on a string) inside it with the same name, somewhat similar to the multi subs in Raku. There's not much to be gained from that though, though I think the idea is cool.

Julia

My Julia script  follows a similar logic to the others. Compute a difference array for each string element, use a hash to count them, and then identify the lone exception from the hash. I use a nx2 (row-major) matrix to store the difference arrays, where n is the length of the input list. I then loop through rows of this matrix using Julia's eachrow() operator and my odd_string inner function finds the row number corresponding to the odd difference array. This is the same as the element number of the odd string in the input list, and so enables easy identification of the odd string.

Here is my Julia script.

Here is the core snippet:

function odd_string(a::Vector{String}) ::String
    myindx=odd_string(difference_array(a))
    return a[myindx]
end 

My Julia script is slow, taking consistently more than 1 second. The Raku script runs in around 0.29 seconds, and the Perl 5 script runs in around 0.006 seconds. 

I compared my Perl 5 run time with scripts from other contributors. My script was much faster than anyone else's, but this is  because of startup time.  For example, the script from Vamsi Meenavili ran in 0.13 seconds on my hardware. But when I commented out "use strict" and "use warnings" and replaced the test harness with simple print statements, it ran in 0.004 seconds. Flavio Poletti's code ran in 0.04 seconds, but that went to 0.005 seconds with "use warnings", "use experimental" commented out and "use v5.24" replaced with "use v5.36" (in which signatures are not experimental).

Of course, "use strict" is a very good idea indeed, as I'm sure we have all learned the hard way. :) The trivial startup overhead is, well, trivial.

Comments

Post a Comment

Popular posts from this blog

PWC 215

PWC 215 I have attempted the Perl Weekly Challenge after a hiatus of several weeks, as I was too busy at work. Still busy, so I have just attempted the current challenge in Perl 5. Like I like to do, I have restricted myself to perl 4 syntax as specified in the first edition of Programming perl. Update and disclaimer : These programs will not work on Perl 4 as I discovered later when I found and installed a Perl 4.019 executable. For one thing, the ability to assign a subroutine to a locally scoped typeglob was not available in Perl 4. Challenge 1 (Odd one out) In this challenge, we are given a list of alphabetic strings, and asked to return the list without the strings in which the characters are not sorted (I assume that this means sorted in lexical ascending order). We are also asked to print the number of strings that were removed (i.e., that were not sorted).  I use a subroutine &odd_one_out(@words) with a nested helper sub-sub-routine to check if a string is sorted. Here i
Read more

PWC 227

PWC 227 Challenge 1 (Friday 13th) This challenge requires us to count the number of times Friday 13th occurs in a particular year. I use Date::Manip. This module probably has easier ways to do this using a Date Range, but my approach is easy enough. My &friday_13th subroutine takes the year as input, throws an exception if it is outside the specified range (1753 to 9999), and then cycles through the 13th of each month, counting the Fridays. use Date::Manip; my $dateobj=Date::Manip::Date->new(); sub friday_13th {     my ($year)=@_;     my $retval=0;     ( ($year > 9999) || ($year < 1753) ) &&         die "Year should be between 1753 and 9999";     map {         ( ($dateobj->new_date("$year-$_-13")->printf('%w') ) == 5 ) &&             $retval++;     }     1 .. 12;          $retval; }   Challenge 2 (Roman Maths) This challenge requires us to implement a calculator that parses infix math operations using roman numerals.  There
Read more

PWC 234

PWC 234 I tried to restrict to Perl 4 syntax for both challenges this week, as documented in Rex Swain's Perl 4 reference or the 1st edition of Programming perl. I do use nested subroutines, which I am not sure would actually work in Perl 4, though they comply with the syntax. My programs are tested on Perl 5.38. (The -l in the shebang line works only in Perl 5. The Perl 4 equivalent was -L012 in Unix, which is no longer available.) As I have mentioned before, my aims in using the old syntax are just mild nostalgia plus to add a bit of additional challenge to the task. I know that this is not the most efficient or idiomatic way to do things today. But I should observe that it is really cool that I am able to write code using 30-year old syntax, and run it unmodified on the latest Perl 5.38. You cannot do this with Python 3 for example. This very deep backward compatibility is one of those unsung underappreciated beauties of Perl 5. In my opinion, it is a very cool thing in
Read more