Adding and removing integers

Weekly Challenge 235

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Remove One

Task

You are given an array of integers.

Write a script to find out if removing ONLY one integer makes it strictly increasing order.

My solution

When I first read the challenge (which I do on public transport on Monday evenings usually), the approach I was going to take was to remove one item at a time and check if the list is in increasing order.

Then I thought I would be cleaver and wrote code that counted the number of times a value was lower than the previous value. This would provide the correct results for the three examples. If that occurred more than once, then it is false.

However when I started writing this blog post, I realized a floor in my logic. Taking the sequence '8, 9, 1, 2, 3' would have returned true even though you couldn't remove a single value to make an incremental list.

My second attempt was to loop through the list once and see how many times the value is less than the current maximum. If this occurs more than once, it means there is no solution. However, this would fail for the list '8, 1, 2, 3' where it would return false when you could remove the 8 to pass the test.

So in the end, I went back to the original plan. Remove one number from the list, check if it is incrementing. Print true if it, print false if we exhaust all tests.

My final code looks like this

# Loop through each position of the list
for i in range(len(ints)):
    # Make a new list with the integer at that position remove
    new_list = ints.copy()
    del new_list[i]

    # Check if the list is incremental
    if all(new_list[j-1] <= new_list[j] for j in range(1, len(new_list))):
        # It is, tell the user about it
        print('true')
        return

# Oh dear. No solution is possible
print('false')

Had this being done in the real world, this is where I would talk with colleagues to figure out if this can be optimized more.

Examples

$ ./ch-1.py 0 2 9 4 6
true

$ ./ch-1.py 5 1 3 2
false

$ ./ch-1.py 2 2 3
true

Task 2: Duplicate Zeros

Task

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.

My solution

After the previous task, this should be easier. It also shows up short comings of my Python knowledge compared to Perl. So lets start with the Perl solution as it's straight forward. Generate a new list using the map function, and then use the splice function to truncate it.

my @solution = map { $_ ? $_ : ( 0, 0 ) } @ints;
splice( @solution, scalar(@ints) );

The Python solution does the same, but is a little more verbose. There is probably a way to do this more efficiently. After writing this blog post, I'll look at other peoples solutions.

for i in ints:
    # Add the original number
    solution.append(i)
    if i == 0:
        # Add it twice if it is zero
        solution.append(i)

solution = solution[:len(ints)]

Examples

$ ./ch-2.py 1 0 2 3 0 4 5 0
1, 0, 0, 2, 3, 0, 0, 4

$ ./ch-2.py 1 2 3
1, 2, 3

$ ./ch-2.py 0 3 0 4 5
0, 0, 3, 0, 0