Task 1: Consecutive One

You are given a binary array containing only 0 or/and 1.

Write a script to find out the maximum consecutive 1 in the given array.

Example 1

Input: @binary = (0, 1, 1, 0, 1, 1, 1)
Output: 3

Example 2

Input: @binary = (0, 0, 0, 0)
Output: 0

Example 3

Input: @binary = (1, 0, 1, 0, 1, 1)
Output: 2

Approach

This is just a single loop through the list of bits, keeping track of two things: how many consecutive 1 bits we’ve seen, and what the largest value was for that sum of consecutive bits were. We start out with the consecutive counter at 0, and then start the loop. If the bit we’re currently examining is a 1, we increment the counter (which is why we start the counter at 0), and then compare that count to the largest count we’ve seen, updating the largest count if the current count is bigger. If the bit we’re currently examining is a 0, we reset the consecutive counter to 0 and move on.

One of the things I noted about all the examples, however, was that they all ended with the maximum consecutive 1 bits. I wanted to add some examples where there were runs of 1s after the largest one and make sure those didn’t mess up the count.

Raku

I thought about setting $max by calling max, but I thought “Why bother making a method call when it’s a simple condition?

sub consecutiveOne(@binary) {
  my $max = 0;
  my $consecutive = 0;
  for @binary -> $bit {
    if ($bit) {
      $consecutive++;
      $max = $consecutive if $consecutive > $max;
    }
    else {
      $consecutive = 0;
    }
  }
  return $max;
} 

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
Example 1:
Input: @binary = (0, 1, 1, 0, 1, 1, 1)
Output: 3

Example 2:
Input: @binary = (0, 0, 0, 0)
Output: 0

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

Example 4:
Input: @binary = (1, 1, 1, 0, 1, 1, 0)
Output: 3

Example 5:
Input: @binary = (1, 0, 1, 1, 0, 1, 0)
Output: 2

Perl

And because I didn’t need to import a max function from one of the List::Utils modules, the only thing I had to change going from Raku to Perl was the syntax of the for loop.

sub consecutiveOne(@binary) {
  my $max = 0;
  my $consecutive = 0;
  for my $bit (@binary) {
    if ($bit) {
      $consecutive++;
      $max = $consecutive if $consecutive > $max;
    }
    else {
      $consecutive = 0;
    }
  }
  return $max;
}

View the entire Perl script for this task on GitHub.

Python

Since Python has a built-in function max, and Python variables don’t have sigils to differentiate variables from functions, I just renamed $max to max_c.

def consecutiveOne(binary):
  max_c = 0
  consecutive = 0
  for bit in binary:
    if bit == 1:
      consecutive += 1
      if consecutive > max_c: max_c = consecutive
    else:
      consecutive = 0
  return max_c

View the entire Python script for this task on GitHub.

Elixir

As usual, when I need to loop over a list and just produce a side effect, recursion is the order of the day for Elixir. Line 19 calls our recursive loop with 0 values for consecutive and max_c (again, there’s a built in max function I need to steer clear of, though this time I’m actually using the function).

Line 6 is the recursive call: if the current bit is 1, it increments the number of consecutive bits and the max counter, and if it’s a 0, it resets the consecutive count and passes the max counter unmodified.

Line 4 is the termination clause once the list is empty, and it returns the max counter.

def consecutiveOne([], _, max_c), do: max_c

def consecutiveOne([current | remaining], consecutive, max_c) do
  cond do
    current == 1 ->
      consecutiveOne(
        remaining, consecutive + 1,
        max(max_c, consecutive + 1)
      )
    true ->
      consecutiveOne(remaining, 0, max_c)
  end
end

def consecutiveOne(binary) do
  consecutiveOne(binary, 0, 0)
end

View the entire Elixir script for this task on GitHub.

Task 2: Final Price

You are given an array of item prices.

Write a script to find out the final price of each items in the given array.

There is a special discount scheme going on. If there’s an item with a lower or equal price later in the list, you get a discount equal to that later price (the first one you find in order).

Example 1

Input: @prices = (8, 4, 6, 2, 3)
Output: (4, 2, 4, 2, 3)

Item 0:
The item price is 8.
The first time that has price <= current item price is 4.
Final price = 8 - 4 => 4

Item 1:
The item price is 4.
The first time that has price <= current item price is 2.
Final price = 4 - 2 => 2

Item 2:
The item price is 6.
The first time that has price <= current item price is 2.
Final price = 6 - 2 => 4

Item 3:
The item price is 2.
No item has price <= current item price, no discount.
Final price = 2

Item 4:
The item price is 3.
Since it is the last item, so no discount.
Final price = 3

Example 2

Input: @prices = (1, 2, 3, 4, 5)
Output: (1, 2, 3, 4, 5)

Example 3

Input: @prices = (7, 1, 1, 5)
Output: (6, 0, 1, 5)

Item 0:
The item price is 7.
The first time that has price <= current item price is 1.
Final price = 7 - 1 => 6

Item 1:
The item price is 1.
The first time that has price <= current item price is 1.
Final price = 1 - 1 => 0

Item 2:
The item price is 1.
No item has price <= current item price, so no discount.
Final price = 1

Item 3:
The item price is 5.
Since it is the last item, so no discount.
Final price = 5

Approach

Ok, this is another problem where I had to read through the examples to figure out what was happening, because calling things “current item price” and “discount” were confusing me. We have a list of numbers. We pull the first number, p1, off the list. We then examine the remaining list to find the first number, p2, where p2 <= p1. If such a number exists, we’re calculating (p1 - p2) and adding it to the output list. If no such number exists, we’re adding p1 to the output list.

Raku

I knew that Raku had to have a first method on the List class.

sub finalPrice(@prices) {
  my @discounts;
  while (my $current = @prices.shift) {
    if (my $lower = @prices.first: * <= $current) {
      $current -= $lower;
    }
    @discounts.push($current);
  }
  return @discounts;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: @prices = (8, 4, 6, 2, 3)
Output: (4, 2, 4, 2, 3)

Example 2:
Input: @prices = (1, 2, 3, 4, 5)
Output: (1, 2, 3, 4, 5)

Example 3:
Input: @prices = (7, 1, 1, 5)
Output: (6, 0, 1, 5)

Perl

Perl is practically the same, we just need to import first from List::AllUtils.

use List::AllUtils qw( first );

sub finalPrice(@prices) {
  my @discounts;
  while (my $current = shift @prices) {
    if (my $lower = first { $_ <= $current} @prices) {
      $current -= $lower;
    }
    push @discounts, $current;
  }
  return @discounts;
}

View the entire Perl script for this task on GitHub.

Python

In Python, it’s easy to simulate the first function by generating a list of value that meet our condition, and then use next to grab the next (first) value off that list. And there’s a bonus: if you pass a default value to the next function, it will return that if there’s no value in the list. Since we’re subtracting the value we get from next from the current value, having next default to 0 means if no value is found, we don’t subtract anything from the current value!

def finalPrice(prices):
  discounts = []
  while prices:
    current = prices.pop(0)
    lower = next((p for p in prices if p <= current), 0)
    current -= lower
    discounts.append(current)
  return discounts

View the entire Python script for this task on GitHub.

Elixir

Elixir, on the other hand, does have an equivalent to first, Enum.find/3:

find(enumerable, default \\ nil, fun)
Returns the first element for which fun returns a truthy value. If no such element is found, returns default.

And because we’re returning a default value of 0 (like we did in the Python solution), we can just subtract the returned value from the current price.

def finalPrice([], discounts), do: discounts

def finalPrice([current | prices], discounts) do
  lower = Enum.find(prices, 0, fn p -> p <= current end)
  finalPrice(prices, discounts ++ [current - lower])
end

def finalPrice(prices) do
  finalPrice(prices, [])
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-325/packy-anderson