Task — 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.

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];
}

Output

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