Learning Perl Challenge: Be better than Quorum

Sinan Ünür wrote about some click bait that claimed Perl programmers were worse than programmers in a fictional language named Quorum. His post goes through all the experimental and analytic errors, as many of his posts do.

One of the tasks in this pseudoscientific research was described as:

This code will count the number of values that are and are not divisible by c and lie between a and b. It then compares the number of values that are and are not divisible by c and makes the greater of them available to the user.

The solutions the participants submitted in the seven minutes they were allotted were fine. I’m not too concerned about that. People who don’t know a language muddle their way through, and we have a way to deal with that. We create an interface and hide the details behind a subroutine.

David Farrell (publisher of PerlTricks and organizer of Mini-Conf) and I were talking about this challenge. How would be do it? When I gave it a whack, I came up with a not-so-great solution my self on my first go, but it worked. If it was important, I could go back and redo it. Too often we show the result which is much less illuminating than the path to the result.

I’ll show my tries after next week, but I’m going to give my readers a chance to come up with their own solutions first. But, I’m going to do it with these honor-system rules:

Complete the task in five minutes. Your first idea is more important than the best idea. Save that program.
Stop working, but think about it for a day. Come back the next day and start over with what you thought about. Do it in five minutes this time too.
Post both solutions. You can do that here, or in some other blog. Explain what you were thinking on the first go, what you thought about away from the keyboard, and why you went with the new code. I’m interested in how you think more than the best solution more than the solution.

For my solutions, I’ll apply my normal constraints. I’ll only use what I’ve presented in Learning Perl.

Here’s a stub test file to help you. Even though we don’t cover testing until Intermediate Perl, that’s not a necessary part of this challenge. You only have to fill in the body for the count subroutine. In this stub I use a couple of v5.20 features: subroutine signatures and postfix dereferencing.

use v5.20;
use feature qw(postderef signatures);
no warnings qw(experimental::postderef experimental::signatures);

use Test::More;

my @tests = (
	# start end divisor answer
	[  0,  10,  3,  7 ],
	[  0,  20,  3, 14 ],
	[  5, 100, 37, 94 ],
	[ -9,   9,  4, 14 ],
	);

foreach my $row ( @tests ) {
	is( count( $row->@[0..2] ), $row->[-1] );
	} 

done_testing();

sub count ( $start, $end, $divisor ) {
	... # fill in here
	}

If you don’t like the new features, you can use this stub instead:

use Test::More;

my @tests = (
	# start end divisor answer
	[  0,  10,  3,  7 ],
	[  0,  20,  3, 14 ],
	[  5, 100, 37, 94 ],
	[ -9,   9,  4, 14 ],
	);

foreach my $row ( @tests ) {
	is( count( @{$row}[0..2] ), $row->[-1] );
	} 

done_testing();

sub count {
	... # fill in here
	}

9 thoughts on “Learning Perl Challenge: Be better than Quorum”

Adam Millerchip says:

June 5, 2015 at 04:22
Here’s mine.

First attempt took more than 5 minutes because I half-implemented it three times while realising I’d not understood the question. Initially I thought the question wanted to return the maximum value that was (or was not) divisible. Anyway, I came up with this:
```
sub count ( $start, $end, $divisor ) {
    my ($divisible, $not) = (0,0);
    for ($start .. $end) {
        $_ % $divisor ? $not++ : $divisible++;
    }
    return $divisible > $not ? $divisible : $not;
}
```
I just followed the instuction in the question: first count the whether the items are divisable (by testing the result of the % operator). Then return the maxumim of the aggregated results.

After a day of thinking I was trying to think of ways to improve this, but I’m actually quite happy with it. I’d never used List::Util before so I thought maybe I could make use of the reduce and max functions. But when I implemented it, it turned out reduce was no good because I needed two pieces of information (the number of divisible and non-divisible), rather than just one, however I then realised that was overkill anyway and if I prepared an array of boolean results, I could just grep the array:
```
sub count ( $start, $end, $divisor ) {

    use List::Util qw(max);

    my @is_divisible = map { $_ % $divisor ? 0 : 1 } ($start..$end);
    my $divisible = grep { $_ } @is_divisible;
    my $not = @is_divisible - $divisible;
    max $divisible, $not;
}
```
I also left List::Util in just to demonstrate another way of finding the maximum.

But I don’t think this an improvement. It’s trying to be clever and in the process is using intermediate lists and is harder to understand. I’m wondering if there is a way to avoid the @is_divisible array, but I don’t know how to determine the size of the input list in that case. I’d probably just stick with the first version. 🙂
1. Adam Millerchip says:
  
  June 5, 2015 at 07:28
  I simplified the 2nd example. This is probably the kind of effect that was supposed to happen between the first and second examples. 🙂 I still prefer the first one for ease of understanding.
  
  I started to think if we can make it more efficient by skipping multiples of numbers we’ve already checked. But too difficult for a 5-minute implementation!
```
sub count ( $start, $end, $divisor ) {

    use List::Util qw(max);

    my $indivisible = grep { $_ % $divisor } ($start..$end);
    my $divisible = $end - $start + 1 - $indivisible;
    max $divisible, $indivisible;
}
```
Steven Wilson says:

June 6, 2015 at 15:41

Here are my attempts.
Ken Williams says:

June 8, 2015 at 13:13

You should be able to do this without any looping (or grepping or mapping). Since multiples of $divisor are evenly distributed in the interval, you can count how many there are without actually testing each number.
Joe Zbiciak says:

June 8, 2015 at 14:34

When I first read the puzzle question, my mind immediately went in the direction Adam’s did in the comments before mine. (For loop; grep in a scalar context.)

I didn’t bother trying to write that code.

I came back a few minutes later, and realized that using a looping construct here was like counting on your fingers, except in software.

I won’t show my answer here, but I will leave that as a hint. There’s a way to do this without an explicit (or implicit) loop.
Gustavo Chaves says:

June 8, 2015 at 16:41
This is my first attempt, which took me about 4min30s, mostly because I too misunderstood the question at first.
```
 sub count ( $start, $end, $divisor ) {
    use integer;
    my $is = 0;
    my $isnt = 0;
    for (my $i = $start; $i <= $end; ++$i) {
        if (($i % $divisor) == 0) {
            ++$is
        } else {
            ++$isnt;
        }
    }
    return $is > $isnt ? $is : $isnt;
}
```
Soon after finishing it I begun to think of a solution with constant complexity instead of linear as is the case of the first one which loops over all integers from $start to $end.
```
sub count ( $start, $end, $divisor ) {
    use integer;
    my $sm   = ($start % $divisor) ? $start - ($start % $divisor) + $divisor : $start;
    my $em   = $end   - $end   % $divisor + $divisor - 1;
    my $is   = ($em - $sm + 1) / $divisor;
    my $isnt = ($end - $start + 1) - $is;
    return $is > $isnt ? $is : $isnt;
}
```
I had tried the solution on paper first and was surprised when the last test failed. It took me more than 10min to realize that the culprit was the “use integer;” line. Removing it made the test succeed.

Take a look at this:
```
$ perl -e 'print "$^V\n"'
v5.20.1

$ perl -e 'printf "%d\n", -9 % 4;'        
3

$ perl -Minteger -e 'printf "%d\n", -9 % 4;'                 
-1
```
I could understand it only after reading perldoc integer with care. After what I saw that I didn’t have to use integer after all. Good learning side effect of this exercise!

I guess my second attempt has room for improvement but I’m satisfied with it as it is.
1. Gustavo Chaves says:
  
  June 8, 2015 at 16:53
  
  (Ish… the syntax of my scripts above is botched. I used the ‘code’ tag but it didn’t seem to work. I’ll try the ‘pre’ tag now hoping it will work… Let’s see.)
  
  This is my first attempt, which took me about 4min30s, mostly because I too misunderstood the question at first.
  
  sub count ( $start, $end, $divisor ) {
  use integer;
  my $is = 0;
  my $isnt = 0;
  for (my $i = $start; $i $isnt ? $is : $isnt;
  }
  
  Soon after finishing it I begun to think of a solution with constant complexity instead of linear as is the case of the first one which loops over all integers from $start to $end.
  
  sub count ( $start, $end, $divisor ) {
  use integer;
  my $sm = ($start % $divisor) ? $start – ($start % $divisor) + $divisor : $start;
  my $em = $end – $end % $divisor + $divisor – 1;
  my $is = ($em – $sm + 1) / $divisor;
  my $isnt = ($end – $start + 1) – $is;
  return $is > $isnt ? $is : $isnt;
  }
  
  I had tried the solution on paper first and was surprised when the last test failed. It took me more than 10min to realize that the culprit was the “use integer;” line. Removing it made the test succeed.
  
  Take a look at this:
  
  $ perl -e ‘print “$^V\n”‘
  v5.20.1
  
  $ perl -e ‘printf “%d\n”, -9 % 4;’
  3
  
  $ perl -Minteger -e ‘printf “%d\n”, -9 % 4;’
  -1
  
  I could understand it only after reading “perldoc integer” with care. After what I saw that I didn’t have to use integer after all. Good learning side effect of this exercise!
  
  I guess my second attempt has room for improvement but I’m satisfied with it as it is.
E. Choroba says:

June 8, 2015 at 22:04
```
sub count {
    my ($start, $end, $div) = @_;
    my ($divisible, $nondivisible);
    ($_ % $div ? $divisible : $nondivisible)++ for $start .. $end;
    return $divisible > $nondivisible ? $divisible : $nondivisible
}
```
Initially, I thought the subroutine should return the longer list, so the code used @divisible and @nondivisible, with push instead of ++. Interestingly, it still passed the tests, as arrays in scalar context return their size, but when I noticed the word “count”, I still had 30 seconds left. I’ll post my second try tomorrow.
Steven Wilson says:

June 9, 2015 at 12:54
Starting with a 5 minute inital version. I’m only concerned with getting a correct count for each variable and passing the tests.
```
sub count {
    my ($start, $end, $divisor) = @_;
    my $is = 0;
    my $not = 0;

    for ($start .. $end){
        if ($_ % $divisor == 0){
            $is++;
        }
        else {
            $not++
        }
    }
    if ($not > $is){
        return $not;
    }
    else {
        return $is;
    }
}
```
After finishing it I’m already having thoughts about reducing the number of assignments by only incrementing when we find a value then working out the number of times it isn’t divisible using the length of the sequence minus the number of values found.

I’d also like to reduce the number of comparisons. This led to thoughts of skipping ahead in the range by the value of the divisor when the first value is found. If the subsequent value is still in the range then increment the count and skip ahead again or else return the count.

Here is the second version, the pseudocode took a couple of minutes but my perl is not strong so it took a bit longer to get the syntax correct.
```
sub count {
    my ($start, $end, $divisor) = @_;
    my @range = ($start .. $end);
    my $is = 0;

    for (@range){
        my $num = $_;
        if ($num % $divisor == 0){
            while ( $num ~~ @range) {
                $num += $divisor;
                $is++;
            }
            last;
        }
    }
    my $not = scalar @range - $is;
    if ( $not > $is ) { $not } else { $is };
}
```

Comments are closed.