Peter
Peter Campbell Smith

Divisible pairs and
reduce to nothing

Weekly challenge 188 — 24 October 2022

Week 188 - 24 Oct 2022

Task 2

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:



example: 987



example: 654

Script


#!/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

The content of this website which has been created by
Peter Campbell Smith is hereby placed in the public domain