DEV Community

Bob Lied
Bob Lied

Posted on

PWC 333 Algebra review and much ado about nothing

#perl #pwc #perlweeklychallenge

Task 1: Straight Line 

You are given a list of co-ordinates.
Write a script to find out if the
given points make a straight line.
Enter fullscreen mode Exit fullscreen mode
  • Example 1:
    • Input: @list = ([2, 1], [2, 3], [2, 5])
    • Output: true
  • Example 2:
    • Input: @list = ([1, 4], [3, 4], [10, 4])
    • Output: true
    • Example 3:
    • Input: @list = ([0, 0], [1, 1], [2, 3])
    • Output: false
  • Example 4:
    • Input: @list = ([1, 1], [1, 1], [1, 1])
    • Output: true
  • Example 5:
    • Input: @list = ([1000000, 1000000], [2000000, 2000000], [3000000, 3000000])
    • Output: true

This is not so much a programming problem as it as an algebra review problem. There's a straight-forward calculation that answers the question. I knew that, but didn't remember the details, so I looked it up. Once again, the 8th grade cynics who said we would never need this in real life are proven wrong, 53 years later.

sub isLine(@point)
{
    my @x = map { $_->[0] } @point;
    my @y = map { $_->[1] } @point;

    return ($y[1] - $y[0]) * ( $x[2] - $x[0] )  == ( $y[2] - $y[0] ) * ( $x[1] - $x[0] )
}
Enter fullscreen mode Exit fullscreen mode

The more interesting programming problem to me was not the geometric algebra, but the data representation of the points and how to reference them in some readable way. In the function, I chose to pass an array of references to pairs, as the examples show. Then I extract the x and y coordinates from each pair as lists to create the readable implementation of the formula.

To pass data into the script from the command line, I chose to pass comma-separated pairs. For example: perl ch-1.pl 1,1 2,2 3,3

Each of the pairs needs to be turned into a reference to a pair of numbers, which can be done by putting the results of a split inside a pair of square brackets, and applying that to every argument with map.

my @point = map {  [split ',', $_] } @ARGV;
die "Need three points" unless @point == 3;

say isLine(@point) ? "true" : "false";
Enter fullscreen mode Exit fullscreen mode

Task 2: Duplicate Zeroes 

You are given an array of integers.
Write a script to duplicate each occurrence
of zero, shifting the remaining elements to
the right. The elements beyond the length of
the original array are not written.
Enter fullscreen mode Exit fullscreen mode
  • Example 1:
    • Input: @ints = (1, 0, 2, 3, 0, 4, 5, 0)
    • Output: (1, 0, 0, 2, 3, 0, 0, 4)
    • Each zero is duplicated. Elements beyond the original length (like 5 and last 0) are discarded.
  • Example 2:
    • Input: @ints = (1, 2, 3)
    • Output: (1, 2, 3)
    • No zeros exist, so the array remains unchanged.
  • Example 3:
    • Input: @ints = (1, 2, 3, 0)
    • Output: (1, 2, 3, 0)
  • Example 4:
    • Input: @ints = (0, 0, 1, 2)
    • Output: (0, 0, 0, 0)
  • Example 5:
    • Input: @ints = (1, 2, 0, 3, 4)
    • Output: (1, 2, 0, 0, 3)

This is a little tour of how easy it is to manipulate arrays in Perl. I have three possible solutions in mind:

  1. Copy to a new array, adding an extra zero when needed.
  2. Map each zero to a pair of zeroes, then cut to size. This also effectively makes a copy of the list.
  3. Splice an extra zero into the original list Let's develop them and run a benchmark.

Copy with insertion

In this solution, we'll push each element of the original list to a new list, and add an extra 0 every time we see a 0.

sub duplicateZero(@int)
{
    my @out;
    my $length = @int;
    while ( defined(my $n = shift @int) && @out < $length)
    {
        push @out, $n;
        push @out, 0 if $n == 0 && @out < $length;
    }
    return \@out;
}
Enter fullscreen mode Exit fullscreen mode

Pretty straight-forward. I'm annoyed by having to check the length twice, but I can live with it.

Mapping to pairs and truncating

In this solution, we'll transform every 0 to a pair, and then reduce to the correct size.

sub dupCut(@int)
{
    my @out = map { $_ == 0 ? (0,0) : ($_) } @int;
    splice(@out, scalar(@int) ); 
    return \@out;
}
Enter fullscreen mode Exit fullscreen mode

The cuteness here is that a single element can be mapped to a list, and then the list is flattened. Perl is doing its famous "do what I mean" trick here.

Truncating the list could be done either with an array slice, or by using splice. Using a slice would create a copy, so I prefer to modify in place. On my first attempt, I tried to return the result of splice, but that's wrong, because splice returns the part that was removed, not the remainder. I could have spliced the complement (splice(@out, 0, @int-1)) to make it a single line, but this way seems more readable.

My one reservation about this solution is that it might do a lot of unnecessary work. Imagine a very long list (a million, maybe) where there are a lot of zeroes. After getting about halfway through the list, we might have already exceeded the length, but we'll continue to convert the other half-million elements, only to throw them away.

Splice in place

The third solution tries to avoid the overhead of creating a second list, and instead inserts zeroes into the original list.

sub dupSplice(@int)
{
    my $length = @int;
    for ( reverse 0 .. $#int )
    {
        splice(@int, $_, 1,  0,0) if $int[$_] == 0;
    }
    splice(@int, $length);
    return \@int;
}
Enter fullscreen mode Exit fullscreen mode

Some notes here:

  • reverse 0 .. $#int -- I'm working backwards because I need to use indexes into the list, and when I insert new elements the indexes will change.
  • splice doesn't only removes elements from a list. Given extra arguments, it can also replace. Once again I'm replacing a single element with a short list.
  • This is not very different from the map-and-truncate solution, except that the loop is explicit and there's no second array.
  • Like the previous solution, this might do unnecessary work, especially since we're starting from the back and must work through the entire list.

Benchmark

Let's see if there's any performance advantage among the solutions. My intuition tells me that modification in place without creating a second array not only wins in memory, but should be faster.

sub runBenchmark($repeat)
{
    use Benchmark qw/cmpthese/;

    my @int = map { int(rand(20)) + 1 } 1 .. 100;
    $int[$_] = 0 for map { int(rand(100)) } 1..10;

    cmpthese($repeat, {
            copy   => sub { duplicateZero(@int) },
            cut    => sub { dupCut(@int) },
            splice => sub { dupSplice(@int) },
        });
}
Enter fullscreen mode Exit fullscreen mode

I set up a longer array with random non-zero numbers. They don't need to be random, but it makes me feel better to emulate the examples. Then I randomly set some percentage of them to 0. Here's a result:

$ perl ch-2.pl -b 80000
           Rate   copy splice    cut
copy    76923/s     --   -54%   -54%
splice 166667/s   117%     --     0%
cut    166667/s   117%     0%     --
Enter fullscreen mode Exit fullscreen mode

The map-and-truncate solution is just as fast as splicing in place. As predicted, both are better than building a copy of the list.

I played a bit with making the list contain no zeroes, or all zeroes, or other proportions of zeroes, but the result is the same.

Top comments (0)