Perl Weekly Challenge: Zero is Not the End of the Line

This week’s challenge is about straight lines and duplicate zeros, so let’s jump to the end of the line and listen to some musicians who were decidedly not zeroes.

So let’s live the life we please with Perl Weekly Challenge 333.

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.

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

Approach

I thought about this, and if we’re given three points, a, b, and c are collinear if the line between the first two points has the same slope as the line between the last two points (and we know they’re not disconnected because they have the middle point in common). Since the formula for the slope of ab is

m = a y b y a x b x

and the slope for bc is

m = b y c y b x c x

the slopes are equal if

a y b y a x b x = b y c y b x c x


But, because we don’t want the possibility of dividing by 0, we can simplify this to

( a y b y ) ( b x c x ) = ( b y c y ) ( a x b x )

Raku

One of the first problems I ran into in my Raku solution was I was getting errors when I first tried running it:

Use of uninitialized value @b[1] of type Any in numeric context
  in sub straightLine at raku/ch-1.raku line 8

Initially, I had

sub straightLine(@list) {
  my @a = @list[0];
  my @b = @list[1];
  my @c = @list[2];

But when I added debugging print statements, I found out I was still getting a list of lists.

Input: @list = ([2, 1], [2, 3], [2, 5])
a: [[2, 1],]
b: [[2, 3],]
c: [[2, 5],]

Reading through the Raku documentation on lists, sequences, and arrays pointed me to a solution:

sub straightLine(@list) {
  my @a = @list[0].Array;
  my @b = @list[1].Array;
  my @c = @list[2].Array;
Input: @list = ([2, 1], [2, 3], [2, 5])
a: [2, 1]
b: [2, 3]
c: [2, 5]

So with that snag out of the way, I was able to complete the task:

sub straightLine(@list) {
  my @a = @list[0].Array;
  my @b = @list[1].Array;
  my @c = @list[2].Array;
  return (
    (@a[0] - @b[0]) * (@b[1] - @c[1])
    ==
    (@b[0] - @c[0]) * (@a[1] - @b[1])
  );
}
 

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
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

Perl

The Perl solution was actually easier, because the lists within the list were scalar pointers to lists, so I could just treat them as scalars when I popped them off the list.

sub straightLine(@list) {
  my $a = shift @list;
  my $b = shift @list;
  my $c = shift @list;
  return (
    ($a->[0] - $b->[0]) * ($b->[1] - $c->[1])
    ==
    ($b->[0] - $c->[0]) * ($a->[1] - $b->[1])
  ) ? 'true' : 'false';
}

View the entire Perl script for this task on GitHub.

Python

Python was just as easy, as long as I remembered that the way to shift an element off the front of a list was list.pop(0)

def straightLine(point_list):
  a = point_list.pop(0)
  b = point_list.pop(0)
  c = point_list.pop(0)
  return (
    (a[0] - b[0]) * (b[1] - c[1])
    ==
    (b[0] - c[0]) * (a[1] - b[1])
  )

View the entire Python script for this task on GitHub.

Elixir

In the Elixir solution, I used List.pop_at/3 and Enum.at/3 to grab the elements from the list I needed to do the calculations.

  def straightLine(point_list) do
    {a, point_list} = List.pop_at(point_list, 0)
    {b, point_list} = List.pop_at(point_list, 0)
    {c, _}          = List.pop_at(point_list, 0)
    (
      (Enum.at(a,0) - Enum.at(b,0)) *
      (Enum.at(b,1) - Enum.at(c,1))
      ==
      (Enum.at(b,0) - Enum.at(c,0)) *
      (Enum.at(a,1) - Enum.at(b,1))
    )
  end

View the entire Elixir script for this task on GitHub.


Task 2: Duplicate Zeros

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.

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)

Approach

Yes, we could modify the array in place and worry about shifting the remaining elements to the right, or we could just copy elements to a new array and stop when the new array has just as many elements as the source array.

Raku

I’m returning a splice from the resulting array because in example 3, we wind up pushing too many elements onto the destination array. Entering the last iteration of the loop, @dest is (1, 2, 3). But then we encounter the last element of @ints, 0, and we push two 0s onto @dest: (1, 2, 3, 0, 0). Since the problem description says to discard elements beyond the original length of the input array, chopping the result array down accomplishes that.

sub duplicateZeros(@ints is copy) {
  my $size = @ints.elems;
  my @dest;
  while (@dest.elems < $size) {
    my $i = @ints.shift;
    @dest.push($i);
    @dest.push($i) if $i == 0;
  }
  return @dest.splice(0, $size);
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: @ints = (1, 0, 2, 3, 0, 4, 5, 0)
Output: (1, 0, 0, 2, 3, 0, 0, 4)

Example 2:
Input: @ints = (1, 2, 3)
Output: (1, 2, 3)

Example 3:
Input: @ints = (1, 2, 3, 0)
Output: (1, 2, 3, 0)

Example 43:
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)

Perl

In Perl, I got to take advantage of the feature that when you evaluate an array in a scalar context, you get the size of the array. Hence, line 5 where I store the original size of the array, and line 7, where I check that the destination array hasn’t gotten too big.

sub duplicateZeros(@ints) {
  my $size = @ints;
  my @dest;
  while (@dest < $size) {
    my $i = shift @ints;
    push @dest, $i;
    push @dest, $i if $i == 0;
  }
  return splice(@dest, 0, $size);
}

View the entire Perl script for this task on GitHub.

Python

The Python solution shows off how array slicing is built into the language.

def duplicate_zeros(ints):
  size = len(ints)
  dest = []
  while len(dest) < size:
    i = ints.pop(0)
    dest.append(i)
    if i == 0: dest.append(i)
  return dest[0:size]

View the entire Python script for this task on GitHub.

Elixir

For the Elixir solution, however, I didn’t bother trying to exit the loop once the destination list got longer than the original list; I could probably have done it with a recursive function where I passed the desired length, but this was such a simple thing to code using Enum.map_reduce/3, and I was going to have to truncate the output anyway (example 3!), so I just ran through the whole list.

  def duplicate_zeros(ints) do
    size = length(ints)
    {_, dest} = Enum.map_reduce(ints, [],
      fn i, dest ->
        case i do
          0 -> {i, dest ++ [0, 0]}
          _ -> {i, dest ++ [i]}
        end
      end
    )
    drop = size - length(dest)
    Enum.drop(dest, drop)
  end

View the entire Elixir script for this task on GitHub.


Here’s all my solutions in GItHub: https://github.com/packy/perlweeklychallenge-club/tree/master/challenge-333/packy-anderson