PWC 188

PWC 188

Challenge 1 (Divisible pairs)

We are given a list of integers, @list say, as well as a scalar integer $k.

We are asked to count the number of pairs of elements of @list whose sum is divisible by $k.

Thus, if $a and $b are elements of @list, we count ($a,$b) as an eligible pair if ($a+$b) is divisible by $k.

This is a potential one-liner in Raku. But I settled for a one-line subroutine. Here is the key snippet:

(0 .. @test-1).combinations(2).grep({@test[$_].sum %% $k}).elems

The task specification asks us to find pairs of indices of @list rather than pairs of elements of @list directly. I have followed this specification literally with Raku. 

Of course it makes no difference if we get the pairs from the list directly. I did this with my Perl 5 and Julia versions, both of which are derived from the Raku one.

Julia key snippet: 

for i in collect(combinations(list,2))
     if (sum(i) % k == 0)
            ctr = ctr+1
    end
end
Perl 5 key snippet:
 
for my $i (combinations(\@list,2)) {
    ((sum @$i) % $k == 0) && ($ctr++)
}
In Julia, I use the Combinatorics library to get the equivalent of Raku's combination operator. In Perl 5, I use Algorithm::Combinatorics.
 
 

Challenge 2 (Total zero)

We are given two positive integers x and y say. Without loss of generality, let x >= y. We are asked to reduce the integers to zero via a series of operations as follows:

  • If both integers are equal, replace them both with zero. Stop.
  •  Otherwise, replace x with x-y, i.e., x=x-y. 
    • If x is still greater than y, repeat.
    • If x is now less than y, swap x and y, (i.e., (x,y)=(y,x) in Perl) and repeat.
We are asked to count the number of steps it takes until both integers are zero.
 
(This is not quite how the problem is stated by our host, but can be inferred from the examples.)

One can do a bit better than brute force here.

First, notice that we would keep replacing x with x-y until y > x. The number of steps to reach y > x would be the integer part of x / y say n. We can start by adding n to our count, then repeat the same calculation with the pair (y, x - n*y), and so on.

One can notice a few edge cases.

  • If x is divisible by y, then n is the answer, as x-n*y reaches 0. We do not need to go further.
  • From the above, if y=1, then the answer is x. 
  • As noted above, if x=y, then the answer is 1 (we finish in 1 step).

In Raku, I use multi subroutines to set up a recursive solution. I set up versions of the total-zero subroutine for each of the edge cases above. Then I use a recursive call in the default version of the subroutine.

my $times=Int($bigger/$smaller);
return $times + total-zero($smaller, $bigger-$times*$smaller);

In Perl 5 and Julia, I use the same recursive approach as in Raku without the multiple dispatch.

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