It’s time for Perl Weekly Challenge 235!
Task 1: Remove One
You are given an array of integers.
Write a script to find out if removing ONLY one integer makes it strictly increasing order.
Example 1
Input: @ints = (0, 2, 9, 4, 6)
Output: true
Removing ONLY 9 in the given array makes it strictly increasing order.
Example 2
Input: @ints = (5, 1, 3, 2)
Output: false
Example 3
Input: @ints = (2, 2, 3)
Output: true
Ok, let’s look at this challenge. We’re looking to return true or false depending on whether removing ONLY one integer from a list makes it strictly increasing order.
So what we need to do is go through the list and keep track of how many times a value is less than or equal to the value before it.
EDITED: As James Curtis-Smith on Facebook pointed out with a counter-example, this logic won’t work. I need to see if removing the value yields a strictly increasing list. So I added a function to test if the list was strictly increasing, and leveraged that:
#!/usr/bin/env perl
use v5.38;
sub isStrictlyIncreasing {
my @ints = @_;
# get the first integer from the list
my $last_int = shift @ints;
# test to make sure each subsequent int is greater
foreach my $this_int ( @ints ) {
return 0 if $this_int <= $last_int;
$last_int = $this_int;
}
return 1;
}
sub isStrictlyIncreasingExceptOne {
my @ints = @_;
# the list cannot be strictly increasing unless
# there are at least two items in it
return 0 if @ints <= 1;
# if it's strictly increasing without removing
# an item, it fails the test
return 0 if isStrictlyIncreasing(@ints);
# loop over the list by index
for (my $i = 1; $i <= $#ints; $i++) {
if ($ints[$i] <= $ints[$i - 1]) {
# remove the bigger item from the list
splice(@ints, $i-1, 1);
# after removing the element, is
# the list strictly increasing?
return isStrictlyIncreasing(@ints);
}
}
}
sub solution {
my @ints = @_;
say 'Input: @ints = (' . join(', ', @ints) . ')';
my $output = isStrictlyIncreasingExceptOne(@ints);
say 'Output: ' . ($output ? 'true' : 'false');
}
say "Example 1:";
solution(0, 2, 9, 4, 6);
say "\nExample 2:";
solution(5, 1, 3, 2);
say "\nExample 3:";
solution(2, 2, 3);
say "\nExample 4 from James Curtis-Smith:";
solution(1,2,3,4,1,2,3);
For those interested, Curtis-Smith does have a very tight, very Perlish solution posted on Facebook. Personally, I’d want to comment the heck out of it so it was clear what was happening, but it does demonstrate using array slices to solve the problem. I will admit that I borrowed the idea of doing it in two functions (one to check whether it’s in order, one to check if only one removal is needed), but I wanted my solution to be a bit easier to read.
EDITED A SECOND TIME! @SpaceLifeForm@infosec.exchange challenged me to do it without removal or recursion, and I managed to do it, but I do have to backtrack in the loop a bit:
sub isStrictlyIncreasingExceptOne {
my @ints = @_;
my $count = 0;
# the index of the first int we're comparing against
my $last_int = 0;
LOOP: for (my $this_int = 1;
$this_int <= $#ints;
$this_int++) {
unless ( $ints[$last_int] < $ints[$this_int] ) {
return 0 if ++$count > 1;
# if we're comparing something after the first integer,
# move the comparison back to the previous good integer
# and then retry the comparison
if ($last_int > 0) {
$last_int--;
redo LOOP;
}
# if we were comparing the first two integers, $last_int
# will become 1 and we'll compare that against $this_int
# as 2 the next time through the loop
}
$last_int = $this_int;
}
return $count == 1;
}
I’ve already submitted the first edit, so I’m not going to redo all of the other solutions to fit this second edit. I’m just posting it to show it can be done.
The Raku version is almost identical; really the only changes were to how the list of integers was passed to functions, and the syntax of the for loop and the infix ternary operator.
#!/usr/bin/env raku
use v6;
sub isStrictlyIncreasing(*@ints where ($_.all ~~ Int)) {
# get the first integer from the list
my $last_int = shift @ints;
for @ints -> $this_int {
return 0 if $this_int <= $last_int;
$last_int = $this_int;
}
return 1;
}
sub isStrictlyIncreasingExceptOne(*@ints where ($_.all ~~ Int)) {
# the list cannot be strictly increasing unless
# there are at least two items in it
return 0 if @ints <= 1;
# if it's strictly increasing without removing
# an item, it fails the test
return 0 if isStrictlyIncreasing(@ints);
# loop over the list by index
loop (my $i = 1; $i < @ints.elems; $i++) {
if (@ints[$i] <= @ints[$i - 1]) {
# remove the bigger item from the list
@ints.splice($i-1, 1);
# after removing the element, is
# the list strictly increasing?
return isStrictlyIncreasing(@ints);
}
}
}
sub solution(*@ints where ($_.all ~~ Int)) {
say 'Input: @ints = (' ~ @ints.join(', ') ~ ')';
my $output = isStrictlyIncreasingExceptOne(@ints);
say 'Output: ' ~ ($output ?? 'true' !! 'false');
}
say "Example 1:";
solution(0, 2, 9, 4, 6);
say "\nExample 2:";
solution(5, 1, 3, 2);
say "\nExample 3:";
solution(2, 2, 3);
say "\nExample 4 from James Curtis-Smith:";
solution(1,2,3,4,1,2,3);
The Python version varies a little because the list of integers is passed into my isStrictlyIncreasing function by reference, so I can’t modify the list while I’m testing it.
#!/usr/bin/env python
def isStrictlyIncreasing(ints):
intlist = ", ".join([ str(i) for i in ints ])
# get the first integer from the list
last_int = ints[0]
for this_int in ints[1:]:
if this_int <= last_int:
return False
last_int = this_int
return True
def isStrictlyIncreasingExceptOne(ints):
# the list cannot be strictly increasing unless
# there are at least two items in it
if len(ints) <= 1:
return False
# if it's strictly increasing without removing
# an item, it fails the test
if isStrictlyIncreasing(ints):
return False
length = len(ints)
for i in range(1, length-1):
if ints[i] <= ints[i - 1]:
print(f'removed {ints[i - 1]} at {i-1}')
ints.pop(i - 1)
return isStrictlyIncreasing(ints)
def solution(ints):
intlist = ", ".join([ str(i) for i in ints ])
print(f'Input: @ints = ({ intlist })')
output = isStrictlyIncreasingExceptOne(ints)
print(f'Output: {output}')
print("Example 1:")
solution([0, 2, 9, 4, 6])
print("\nExample 2:")
solution([5, 1, 3, 2])
print("\nExample 3:")
solution([2, 2, 3])
print("\nExample 4 from James Curtis-Smith:")
solution([1,2,3,4,1,2,3])
Now to the language I’m learning for this challenge, Java. It may seem odd that I’m teaching myself a non-Perl language for the Perl Weekly Challenge, but there’s a method to my madness: there’s a lot of Java code out there, and I want to be able to credibly work with it.
One of the things that’s different about Java is that it’s all statically typed. Not only do variables require a type, but if you’re declaring a native array of a particular type, you need to pre-define the size of the array. However, don’t worry: the language does provide for dynamically sized arrays—they’re just a special class, not a native data type.
Things I had to take note of:
- Joining arrays of non-string values takes a little bit of work. Fortunately, the Collectors class handles this beautifully, and the third example down in the documentation perfectly demonstrates converting elements into strings and then concatenating them separated by commas.
- Java allows you to concatenate a boolean to a string; the stringification is handled automatically.
import java.util.Arrays;
import java.util.stream.Collectors;
public class Ch1 {
public static String joined(int[] ints) {
// we're using it more than once, make it a method
return Arrays.stream(ints)
.mapToObj(String::valueOf)
.collect(Collectors.joining(", "));
}
public static boolean isStrictlyIncreasing(int[] ints) {
// get the first integer from the list
int last_int = ints[0];
// note that we start with element 1, because
// we've already put the value of the 0th
// element into last_int
for (int i = 1; i < ints.length; i++) {
if (ints[i] <= last_int) {
return false;
}
last_int = ints[i];
}
return true;
}
public static boolean isStrictlyIncreasingExceptOne(int[] ints) {
// the list cannot be strictly increasing unless
// there are at least two items in it
if (ints.length <= 1) {
return false;
}
// if it's strictly increasing without removing
// an item, it fails the test
if (isStrictlyIncreasing(ints)) {
return false;
}
for (int i = 1; i < ints.length; i++) {
if (ints[i] <= ints[i-1]) {
// make a new list to hold the list
// with one value removed
int[] newlist = new int[ints.length - 1];
// copy over all but the (i-1)th element
for (int j = 0; j < ints.length; j++) {
if (j == i - 1) {
continue;
}
if (j < i - 1) {
newlist[j] = ints[j];
}
else {
newlist[j-1] = ints[j];
}
}
// now test this new list to see
// if it's strictly increasing
return isStrictlyIncreasing(newlist);
}
}
return false;
}
public static void solution(int[] ints) {
System.out.println("Input: @ints = (" + joined(ints) + ")");
boolean output = isStrictlyIncreasingExceptOne(ints);
System.out.println("Output: " + output);
}
public static void main(String[] args) {
System.out.println("Example 1:");
solution(new int[] {0, 2, 9, 4, 6});
System.out.println("\nExample 2:");
solution(new int[] {5, 1, 3, 2});
System.out.println("\nExample 3:");
solution(new int[] {2, 2, 3});
System.out.println("\nExample 4 from James Curtis-Smith:");
solution(new int[] {1,2,3,4,1,2,3});
}
}
Task 2: Duplicate Zeros
You are given an array of integers.
Write a script to duplicate each occurrence of ZERO in the given array and shift the remaining to the right but make sure the size of array remain the same.
Example 1
Input: @ints = (1, 0, 2, 3, 0, 4, 5, 0)
Ouput: (1, 0, 0, 2, 3, 0, 0, 4)
Example 2
Input: @ints = (1, 2, 3)
Ouput: (1, 2, 3)
Example 3
Input: @ints = (0, 3, 0, 4, 5)
Ouput: (0, 0, 3, 0, 0)
This seems like a perfect solution to use Perl’s splice command. Whenever we want to duplicate a 0 at position $i, we execute splice(@ints, $i+1, 0, 0) followed by splice(@ints, -1) (which is essentially a pop(@ints)).
#!/usr/bin/env perl
use v5.38;
sub duplicateZeros {
my @ints = @_;
for (my $i = 0; $i < scalar(@ints); $i++) {
if ($ints[$i] == 0) {
splice(@ints, $i+1, 0, 0); # insert a 0 at $i+1
splice(@ints, -1); # pop the last element off @ints
$i++; # skip over the 0 we added!
}
}
return @ints;
}
sub solution {
my @ints = @_;
say 'Input: @ints = (' . join(', ', @ints) . ')';
@ints = duplicateZeros(@ints);
say 'Output: (' . join(', ', @ints) . ')';
}
say "Example 1:";
solution(1, 0, 2, 3, 0, 4, 5, 0);
say "\nExample 2:";
solution(1, 2, 3);
say "\nExample 3:";
solution(0, 3, 0, 4, 5);
In Raku, the C-style three statement loop is loop, not for. We need to use this form of loop if we want to modify the loop counter after we’ve inserted a 0 so we don’t processes it a second time.
#!/usr/bin/env raku
use v6;
sub duplicateZeros(*@ints where ($_.all ~~ Int)) {
loop (my $i = 0; $i < @ints.elems; $i++) {
if (@ints[$i] == 0) {
@ints.splice($i+1, 0, 0); # insert a 0 at $i+1
@ints.splice(*-1); # pop the last element off @ints
$i++; # skip over the 0 we added!
}
}
return @ints;
}
sub solution(*@ints where ($_.all ~~ Int)) {
say 'Input: @ints = (' ~ @ints.join(', ') ~ ')';
@ints = duplicateZeros(@ints);
say 'Output: (' ~ @ints.join(', ') ~ ')';
}
say "Example 1:";
solution(1, 0, 2, 3, 0, 4, 5, 0);
say "\nExample 2:";
solution(1, 2, 3);
say "\nExample 3:";
solution(0, 3, 0, 4, 5);
In Python, however, there isn’t a three statement loop. Also, from experience, I know if we explicitly use the array in the control of the loop, Python will complain when we modify the array. So let’s capture the length of the array first, and use a variable to track which iterations through the loop we’re skipping to pass over the 0 we added…
#!/usr/bin/env python
def duplicateZeros(ints):
length = len(ints)
skip_me = -1
for i in range(0, length):
if skip_me == i:
continue
if ints[i] == 0:
ints.insert(i+1, 0) # insert a 0 at i+1
ints.pop(-1) # pop the last element off ints
skip_me = i+1 # skip over the 0 we added!
return ints
def solution(ints):
intlist = ", ".join([ str(i) for i in ints ])
print(f'Input: @ints = ({ intlist })')
ints = duplicateZeros(ints)
intlist = ", ".join([ str(i) for i in ints ])
print(f'Output: ({ intlist })');
print("Example 1:")
solution([1, 0, 2, 3, 0, 4, 5, 0])
print("\nExample 2:")
solution([1, 2, 3])
print("\nExample 3:")
solution([0, 3, 0, 4, 5])
Which, finally, brings us to the Java implementation. We could have used variable-length array objects, but because the whole point of this task is that the array length stays the same, I should lean into that and just move the array elements manually and not rely on some splice method.
import java.util.Arrays;
import java.util.stream.Collectors;
public class Ch2 {
public static String joined(int[] ints) {
// we're using it more than once, make it a method
return Arrays.stream(ints)
.mapToObj(String::valueOf)
.collect(Collectors.joining(", "));
}
public static int[] duplicateZeros(int[] ints) {
for (int i = 0; i < ints.length; i++) {
if (ints[i] == 0) {
// shift all the values in the array to the right by one
for (int j = ints.length - 1; j > i; j--) {
ints[j] = ints[j - 1];
}
ints[i + 1] = 0; // insert a new 0
i++; // skip over the 0 we added!
}
}
return ints;
}
public static void solution(int[] ints) {
System.out.println("Input: @ints = (" + joined(ints) + ")");
ints = duplicateZeros(ints);
System.out.println("Output: (" + joined(ints) + ")");
}
public static void main(String[] args) {
System.out.println("Example 1:");
solution(new int[] {1, 0, 2, 3, 0, 4, 5, 0});
System.out.println("\nExample 2:");
solution(new int[] {1, 2, 3});
System.out.println("\nExample 3:");
solution(new int[] {0, 3, 0, 4, 5});
}
}
Here’s my solutions in GItHub: https://github.com/packy/perlweeklychallenge-club/tree/master/challenge-235/packy-anderson
I really like Bob Lied’s solutions: https://dev.to/boblied/pwc-235-steppin-in-a-slide-zone-la6
I also enjoyed his Moody Blues reference. 😁
Ooh! In
https://www.braincells.com/perl/2023/09/perl_weekly_challenge_week_235.html Jaldhar H. Vyas points out the very Raku-ish way to replace my isStrictlyIncreasing function: [<] @ints. It's using the Reduction Metaoperator ( https://docs.raku.org/language/operators#Reduction_metaoperators ) to compare all the items in the @ints array in a single statement.