Total Zero

You are given two positive integers $x and $y.

Write a script to find out the number of operations needed to make both ZERO. Each operation is made up either of the following:

• $x = $x - $y if $x >= $y
• or $y = $y - $x if $y >= $x (using the original value of $x)

Examples

Example 1
Input: $x = 5, $y = 4
Output: 5

Example 2
Input: $x = 4, $y = 6
Output: 3

Example 3
Input: $x = 2, $y = 5
Output: 4

Example 4
Input: $x = 3, $y = 1
Output: 3

Example 5
Input: $x = 7, $y = 4
Output: 5

Analysis

It seems that this task as stated is impossible. Applying the supplied rules to any pair of starting x and y will never result in both x and y reaching zero, because:

• Each operation reduces either x and y and leaves the other unchanged
• So the values before the last operation would have to be (0, n) or (n, 0) where n > 0
• But that isn't possible because subtracting 0 from n cannot result in 0.

Inspection of the examples suggests that what was intended is that the process finishes when either of x and y reaches zero, and indeed if the rules are applied in the order specified, it will be x that does so.

But is it the case that all starting values of x and y will result in x == 0? The answer is yes, because:

• After each operation, x + y always reduces, but cannot become negative
• There cannot therefore be more than x + y - 1 steps, even if each step only reduces x + y by 1
• Unless x or y is zero, it is always possible to make another step

The maximum number of steps (x + y - 1) will be required if the starting value of x or y is 1 and the minimum number (1) if the starting values of x and y are equal.

Nice discussion of every aspect of the task, Great job.

This review may cover either or both challenges for this week.

I am sorry that the 'Try it' feature is currently working very slowly or not at all owing to some issue with my web hosting provider.

Try it 

Try running the script with any input:

Your $x =

example: 987

Your $y =

example: 654

⤡

#!/usr/bin/perl

# Peter Campbell Smith - 2022-10-26
# PWC 188 task 2

use v5.28;
use utf8;
use warnings;
binmode(STDOUT, ':utf8');

my (@tests, $x, $y, $ops);

# test input (pairs of x, y)
@tests = (5, 4,  4, 6,  2, 5,  3, 1,  7, 4, 987, 654);

# loop over tests
TEST: while ($tests[0]) {
    
    # initialise
    $x = shift @tests;
    $y = shift @tests;
    $ops = 0;
    say qq[\nInput:  \$x = $x, \$y = $y];
    
    # apply rules
    while ($x > 0 and $y > 0) {
        if ($x >= $y) {
            $x -= $y;
        } else {
            $y -= $x;
        }
        $ops ++;
    say qq[x $x y $y];
    }
    # and the answer
    say qq[Output: $ops];
}

19 lines of code

Output from script

Input:  $x = 5, $y = 4
x 1 y 4
x 1 y 3
x 1 y 2
x 1 y 1
x 0 y 1
Output: 5

Input:  $x = 4, $y = 6
x 4 y 2
x 2 y 2
x 0 y 2
Output: 3

Input:  $x = 2, $y = 5
x 2 y 3
x 2 y 1
x 1 y 1
x 0 y 1
Output: 4

Input:  $x = 3, $y = 1
x 2 y 1
x 1 y 1
x 0 y 1
Output: 3

Input:  $x = 7, $y = 4
x 3 y 4
x 3 y 1
x 2 y 1
x 1 y 1
x 0 y 1
Output: 5

Input:  $x = 987, $y = 654
x 333 y 654
x 333 y 321
x 12 y 321
x 12 y 309
x 12 y 297
x 12 y 285
x 12 y 273
x 12 y 261
x 12 y 249
x 12 y 237
x 12 y 225
x 12 y 213
x 12 y 201
x 12 y 189
x 12 y 177
x 12 y 165
x 12 y 153
x 12 y 141
x 12 y 129
x 12 y 117
x 12 y 105
x 12 y 93
x 12 y 81
x 12 y 69
x 12 y 57
x 12 y 45
x 12 y 33
x 12 y 21
x 12 y 9
x 3 y 9
x 3 y 6
x 3 y 3
x 0 y 3
Output: 33