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 258

PWC 258 Last week (#257) I finished challenge 2 and my blog post for challenge 257 late last week, so had only submitted challenge 1. Here is my blog post for PWC 257 , including the full code for my challenge 2 solution. This week, I have done both challenges in perl 4.019 on DOSBOX. Both scripts also work fine on the latest Perl 5.38. I also did the challenges in Raku, where they are one-liners.  Challenge 1 (Count Even Digits Number) We are given a list of integers, and asked to count the number of elements whose base-10 representation has an even number of digits. In Raku , this is a one-liner. Here it is: raku -e 'say +@*ARGS.grep({$_.chars %% 2})' $@ It could be a one-liner in Perl 4 too, but since I run it on DOSBOX, my script would not be a bash shell script. Here is the short subroutine that does the job.  sub count_even_digits {  scalar( grep( ((length($_) % 2) == 0), @_) ); } The full code is here . Challenge 2 (Sum of values) We are given an integer k  an...
Read more

PWC 253

PWC 253 I do both challenges this week using old software on DOSBOX: perl 4.019, and for comparison, also python 1.4 beta. My solutions also work on the current versions of Perl 5 (5.38) and Python 2 (2.7.18) respectively. Challenge 1 (Split Strings) Links to code: perl4.019 python1.4b We are given a list of strings, and a single character say sep . We are asked to return the list, with the strings split into component substrings using sep as a separator. We should not include any empty strings in the output. In perl 4, I first stick a backslash in front of the separator character, so that it is escaped if entered in a regex. This is because the perl split function takes a regex as its first argument indicating the separator. If we have a character like '$' or ',', we want to escape it so that it is read literally when parsing the regex. Here is the key subroutine:   sub split_strings {  local ($separator, @words)=@_;  local (@retval)=(); #array to be returned  # ...
Read more

PWC 249

PWC 249 Challenge 1 (Equal pairs) We are given a list of integers with an even number of elements. We are asked to check if the list can be completely divided into sub-lists of size 2 with each sub-list containing the same integer repeated, like say (2,2). If so, we are asked to return the list of such sub-lists. This is straightforward in Perl 5. I use modern conveniences this time, though it could be done using only primitive Perl 4 syntax. Here is my subroutine. It returns a list of array references. local *equal_pairs = sub {     #-- return () if input is of odd length     ((scalar(@_) % 2) > 0) && (return ());          #-- count number of occurrences of each element using a hash     local %_ = ();     map {$_{$_}++} @_;          #-- if any element occurs an odd number of times, return ()     (grep {($_{$_} % 2) > 0} keys %_) &&...
Read more