The Weekly Challenge 267

Product Sign & Line Counts: Arithmetic Analysis and Text Layout Simulation in Perl & Python

Lubos Kolouch April 28, 2024 Challenge Details GitHub Solutions

Task 1: Product Sign

You are given an array of integers, @ints.

Write a script to return:

  • 1 if the product of all integers in the array is positive
  • -1 if the product is negative
  • 0 if the product is zero

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

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

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

Method Explanation

A naive approach would compute the cumulative multiplication of all integers in the list and inspect whether the result is positive, negative, or zero. However, computing the raw product of large arrays can lead to arithmetic overflow in fixed-precision languages and wastes processing time.

Instead, we observe that the sign depends only on two factors:

  • If any element in the array is 0, the product is immediately zero, allowing for early exit.
  • Positive numbers do not alter the overall sign.
  • Each negative number flips the sign. Thus, an even count of negative numbers yields a positive product (1), whereas an odd count yields a negative product (-1).

This runs in linear time $O(N)$ and requires $O(1)$ auxiliary memory.

Perl Solution

use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(ArrayRef Int);

signature_for product_sign => (
    method     => 0,
    positional => [ ArrayRef [Int] ],
);

sub product_sign ($ints_ref) {
    my $negative_count = 0;

    for my $value (@$ints_ref) {
        return 0 if $value == 0;
        $negative_count++ if $value < 0;
    }

    return $negative_count % 2 == 0 ? 1 : -1;
}

Python Solution

def product_sign(ints: list[int]) -> int:
    """Compute the sign of the product of a list of integers."""
    negative_count = 0
    for value in ints:
        if value == 0:
            return 0
        if value < 0:
            negative_count += 1

    return -1 if negative_count % 2 != 0 else 1

Task 2: Line Counts

You are given a string $str and an array of 26 integers @widths representing the display widths of characters from 'a' to 'z'.

Write a script to return the number of lines and the width of the last line needed to display the string, given a maximum line width limit of 100 units.

Characters are placed sequentially onto the current line. If adding a character causes the line width to exceed 100 units, that character starts a brand new line.

Example 1: Input: $str = "abcdefghijklmnopqrstuvwxyz", @widths = (10) x 26 → Output: (3, 60)

Example 2: Input: $str = "bbbcccdddaaa", @widths = (4, 10, (10) x 24) → Output: (2, 4)

Method Explanation

This task is a greedy string wrapping and layout simulation:

  • Initialize lines = 1 and current_width = 0.
  • Iterate character by character across the string.
  • Find the width of character $c$ by computing its zero-based index in the alphabet via its ASCII code: ord(c) - ord('a').
  • Check if current_width + char_width > 100:
    • If it exceeds 100, advance to the next line (lines++) and set current_width = char_width.
    • Otherwise, append the width to the current line: current_width += char_width.
  • Return the pair (lines, current_width).

The time complexity is $O(N)$ where $N$ is the length of the string, and space complexity is $O(1)$.

Perl Solution

use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(ArrayRef Int Str);

signature_for line_counts => (
    method     => 0,
    positional => [ Str, ArrayRef [Int] ],
);

sub line_counts ( $str, $widths_ref ) {
    my $max_width     = 100;
    my $current_width = 0;
    my $lines         = 1;

    for my $char ( split //, $str ) {
        my $char_width = $widths_ref->[ ord($char) - ord('a') ];
        if ( $current_width + $char_width > $max_width ) {
            $lines++;
            $current_width = $char_width;
        }
        else {
            $current_width += $char_width;
        }
    }

    return ( $lines, $current_width );
}

Python Solution

def line_counts(s: str, widths: list[int]) -> tuple[int, int]:
    """Calculate the number of lines and width of the last line for a string."""
    max_width = 100
    current_width = 0
    lines = 1

    for char in s:
        char_width = widths[ord(char) - ord("a")]
        if current_width + char_width > max_width:
            lines += 1
            current_width = char_width
        else:
            current_width += char_width

    return lines, current_width