# Challenge

Origami (folding paper) is a creative form of art. As far as I know, master of Origami prefers square paper. Let's start from beginning - convert a rectangular paper to a square one.

So the paper is divided into squares. We remove the biggest square which shares one shorter edge with the current shape, step by step (see the picture below). And if the remaining part after one step is less or equal than 0.001 * (area of the original paper), the paper cannot be divided any further. It is possible that nothing remains at last.

Your task is to calculate how many squares are made during the process. The square in the last step that makes the paper unable to be divided is counted into the output.

Example (a paper of 1.350 width/height), output is 10: # Input and Output

Input: width / height ratio for the rectangular paper, one decimal (or an integer without the dot) from 1.002 to 1.999 with a minimal step of 0.001. You may also use any other reasonable format describing the ratio. Just mention it in your answer.

Output: square count, one integer.

# Example I/O

A mapping format is used to keep the page tidy, while your code doesn't need to support a list input nor to be a mapping function.

1.002 => 251
1.003 => 223
1.004 => 189
1.005 => 161
1.006 => 140
1.007 => 124
1.008 => 111
1.009 => 100


Thanks to @LuisMendo, here is the graph of answers. # Remarks

• This is a code-golf so shortest code wins
• Pay attention to standard loopholes
• It's your freedom to decide how to deal with input and output but they should follow standard restrictions.

By the way...

• Comment if you have anything unclear about the challenge
• Personally I would suggest your answer contains a explanation if you are using a golfing language
• Thanks to @GregMartin, read his answer for a good mathematical explanation for the challenge.

# Example Code

Here is a ungolfed version of C++ code:

#include <iostream>
#include <utility>

int f (double m)
{
double n = 1, k = 0.001;
int cnt = 0;
k *= m;                       // the target minimum size
while(m*n >= k)
{
m -= n;                   // extract a square
if(n > m)
std::swap(n, m);      // keep m > n
++ cnt;
}
return cnt;
}

int main()
{
double p;
std::cin >> p;
std::cout << f(p);
return 0;
}


All calculations related in the example code need an accuracy of 6 decimal digits, which is covered in float.

• Can two numbers forming the ratio be used as inputs? – Luis Mendo Jan 9 '17 at 15:15
• @LuisMendo yes, as your wish. – Keyu Gan Jan 9 '17 at 15:15
• Neat challenge! – flawr Jan 9 '17 at 15:36
• The list of answers produces a nice graph – Luis Mendo Jan 9 '17 at 15:46
• @KeyuGan Of course, go ahead! Let me know if you need a version with some other format – Luis Mendo Jan 9 '17 at 15:52

# MATL, 19 bytes

SZ}y-htG/p1e-3>}x@


The input is an array with the two numbers defining the original ratio, such as [1, 1.009]. (It is not necessary that the numbers be sorted or that one of them be 1.)

Try it online!

### Explanation

        % Do...while loop
S      %   Sort array. Takes 1×2 array as input (implicit) the first time
Z}     %   Split array into its 2 elements: first the minimum m, then the maximum M
y      %   Duplicate m onto the top of the stack. The stack now contains m, M, m
-      %   Subtract. The stack now contains m, M-m
h      %   Concatenate into [m, M-m]. This is the remaining piece of paper
t      %   Duplicate
G/     %   Divide by input, element-wise
p      %   Product of array. Gives ratio of current piece's area to initial area
1e-3>  %   True if this ratio exceeds 1e-3. In that case the loop continues
}        % Finally (execute after last iteration, but still within the loop)
x      %   Delete last piece of paper
@      %   Push current loop counter. This is the result
% End (implicit)
% Display (implicit)


# Haskell, 71 70 65 63 62 61 58 56 bytes

Thanks to @xnor for a some ingenious improvements!

(n#m)e|e>n*m*1e3=0|n<m=m#n$e|d<-n-m=(d#m)e+1 n!m=n#m$n*m


Try it online!

• It think the m==n at the end can be 1>0 because it's the only possibility remaining. Or, maybe the cases could be rearranged to allow a bind here. – xnor Jan 9 '17 at 15:57
• Actually, is the equality case needed? If n>m is expanded to n>=m and the first check is written e>m*n*1000, that should give 1 for equality. – xnor Jan 9 '17 at 16:01
• @xnor Good idea, thank you! – flawr Jan 9 '17 at 16:04
• Moving around guards for 56: (n#m)e|e>n*m*1e3=0|n<m=m#n$e|d<-n-m=(d#m)e+1;n!m=n#m$n*m – xnor Jan 10 '17 at 7:01
• Wow, using the d<-n-m as otherwise is really neat!!! – flawr Jan 10 '17 at 11:19

## JavaScript (ES6), 59 58 bytes

f=(m,n=!(k=m/1e3,c=0))=>m*n<k?c:(c++,m-=n)<n?f(n,m):f(m,n)


### Test

f=(m,n=!(k=m/1e3,c=0))=>m*n<k?c:(c++,m-=n)<n?f(n,m):f(m,n)

console.log(f(1.002))
console.log(f(1.003))
console.log(f(1.004))
console.log(f(1.005))
console.log(f(1.006))
console.log(f(1.007))
console.log(f(1.008))
console.log(f(1.009))

# Mathematica, non-non-competing (21 bytes)

This answer is non-competing because it doesn't answer the actual question asked! But it does answer a variant of the question, and provides an excuse to highlight some interesting math.

Tr@*ContinuedFraction


Symbolic function taking a positive rational number as input (whose numerator and denominator represent the dimensions of the original paper) and returning a positive integer. For example, Tr@*ContinuedFraction[1350/1000] returns 10. (ContinuedFraction acts differently on floating-point numbers due to precision issues, which is why a rational number is needed as input in this context.)

An interesting interpretation of the geometric procedure described in the problem (cutting squares off a rectangle repeatedly) is that it's an implementation of the Euclidean algorithm for finding greatest common divisors! Consider the example in the question itself, with ratio 1.35, which could be modeled by having a piece of paper with dimensions (1350,1000). Every time a square is cut off, the smaller number is subtracted from the larger number; so the resulting rectangles in this example have dimensions (350,1000), then (350,650), then (350,300), then (50,300), then (50,250) and (50,200) and (50,150) and (50,100) and (50,50), and also (50,0) once we take away the last square from itself. This is exactly how the Euclidean algorithm operates (modulo the difference between division and repeated subtraction), and indeed we see that 50 is indeed the GCD of 1350 and 1000.

Typically in the Euclidean algorithm, one keeps track of these intermediate dimensions and discards the number of subtractions; however, one can alternately record how many times we subtracted one number from the other before the difference becomes too small and we have to switch what we're subtracting. That method of recording is precisely the continued fraction of a rational number. (Continued fractions of irrational numbers, which never terminate, are also super cool, but not relevant here.) For example, in the example 1350/1000, we subtracted 1000 1 time, then 350 2 times, then 300 1 time, then 50 6 times; therefore the continued fraction of 1350/1000 is {1,2,1,6}. Mathematically, we've rewritten 1350/1000 as 1+1/(2+1/(1+1/6)), which you can verify.

So for this problem, if you don't stop when the squares get smaller than a certain threshhold, but simply count all the finitely many squares before it stops, then the total number of squares equals the total number of subtractions, which is to say the sum of all the integers in the continued fraction—and that is precisely what the composition of functions Tr@*ContinuedFraction computes! (For the given example 1.35, it gets the answer the OP desires, because the final square is large enough that all squares were counted. But Tr@*ContinuedFraction[1001/1000], for example, yields 1001, since it counts the one huge square and all 1000 of the small 1x1000 squares.)

• While this is indeed interesting, the non-competing label is reserved for languages which are newer than the challenge. Independently of that, all answers do need to solve the challenge. Hence, this answer should really be deleted. Would you be able to reconstruct from the continued fraction list where to cut it off so this could be turned into an equally interesting but valid solution? – Martin Ender Jan 10 '17 at 12:03
• I had a mental itch to scratch when writing this answer, but I agree that this is a delete-worthy answer according to community standards. (Thank you for your gentle yet accurate feedback!) If TPTB feel like delaying its deletion for 24 hours, I might be able to complify the approach to yield the right answer ... if not, delete away and no hard feelings. – Greg Martin Jan 10 '17 at 18:19

## Mathematica, 64 53 bytes

({t=1,#}//.{a_,b_}/;1000a*b>#:>Sort@{++t;a,b-a};t-1)&


An imperative (C-style) solution is exactly the same length:

(For[t=a=1;b=#,1000a*b>#,If[a>b,a-=b,b-=a];++t];t-1)&


# C (GCC/Clang), 61 59 bytes

c,k;f(m,n){for(k=m*n;m*n/k;m>n?(m-=n):(n-=m))++c;return c;}


Input is two integers (width & height) without dot, such as f(1999,1000).

I hope someone could save one byte pushing C into the 58-byte club. ;)

• Suggest removing the parentheses around m-=n – ceilingcat Jul 31 '19 at 6:41

# C, 59 bytes

s,a,n=1e3;C(m){for(a=m;m*n>a;s++)m>n?m-=n:(n-=m);return s;}


Try It online

The input is an integer which is the width / height ratio in thousandths (eg. 1002 for 1.002:1).

### Ungolfed version

int C(int m)
{
int n = 1000;
int a = m;
int s = 0;

while (m * n > a)
{
if (m > n)
m -= n;
else
n -= m;

s++;
}

return s;
}