PWC 189

PWC 189

Challenge 1 (Greater Character)

"You are given an array of characters (a..z) and a target character. Write a script to find out the smallest character in the given array lexicographically greater than the target character."

I sort the list. Then, in Perl 5 and Julia, I loop through the sorted elements until I hit one just bigger than the target. In Raku, I just use grep.

Here is the key snippet from my Raku script:

@arry.sort({$^a cmp $^b}).grep({$_ gt $target}).min;

Challenge 2 (Array Degree)

"You are given an array of 2 or more non-negative integers. Write a script to find out the smallest slice, i.e. contiguous subarray of the original array, having the degree of the given array."

The degree of the array is the maximum frequency with which any element occurs. Thus for the example given (1,3,3,2), the degree is 2 (the frequency of the most common or modal element 3).

The smallest slice with the same degree is the smallest slice containing every occurrence of the modal element. This would be the slice that starts with the first and ends with the last occurrence of the modal element: (3,3) in the above example.

There could be multiple modal elements, in which case there could be multiple slices returned.

For my Perl 5 script, I decided to restrict it to the core syntax inherited from Perl 4. I call a subroutine smallest_slice_with_same_degree that returns a list of strings, each of which is an expression of the form @arry[first_index .. last_index]. These have to be eval'd, so I also include a wrapper function print_smallest_slice, which evals and prints the output from smallest_slice_with_same_degree.

The Perl 5 script is fast, running the examples in around 0.007 seconds. This is not much slower than the executable from Ali Moradi's C program which ran in 0.002 seconds on my hardware.

My Raku and Julia scripts mimic the Perl 5 logic, but of course are more modern. The Raku script directly returns the list of slices (no pseudo-closure) as an array of arrays. The Julia script just prints the output directly from the subroutine rather than returning the value. Both scripts are slower than the Perl 5 script at around 0.46 seconds for Raku and around 0.86 seconds for Julia.

I enjoyed writing the Perl 5 script and found it easy and fast to write. Perl is designed to efficiently use flat lists and strings in solving puzzles. I often like looking for solutions that avoid more complicated data structures.

What works well for Perl does not work so well in Julia, though. Probably a different approach is called for in Julia, say using arrays instead of dictionaries.

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  and a list in
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 %_) && (return ());          #-- loop thru %_ keys, returning pairs of such keys     map {         my $k=$_;         my $num_pairs=( ($_{$k}
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