Rectangle into Squares

The drawing below gives an idea of how to cut a given "true" rectangle into squares ("true" rectangle meaning that the two dimensions are different).

 

Can you translate this drawing into an algorithm?

You will be given two dimensions

1. a positive integer length
2. a positive integer width

You will return a collection or a string (depending on the language; Shell bash, PowerShell, Pascal and Fortran return a string) with the size of each of the squares.

 

Examples in general form:

(depending on the language)

sqInRect(5, 3) should return [3, 2, 1, 1] sqInRect(3, 5) should return [3, 2, 1, 1] You can see examples for your language in **"SAMPLE TESTS".**

 

Notes:

• lng == wdth as a starting case would be an entirely different problem and the drawing is planned to be interpreted with lng != wdth. (See kata, Square into Squares. Protect trees! http://www.codewars.com/kata/54eb33e5bc1a25440d000891 for this problem).
• When the initial parameters are so that lng == wdth, the solution [lng] would be the most obvious but not in the spirit of this kata so, in that case, return None/nil/null/Nothing or return {} with C++, Array() with Scala, [] with Perl, Raku.
• In that case the returned structure of C will have its sz component equal to 0.
• Return the string "nil" with Bash, PowerShell, Pascal and Fortran.

 

Solution

#include <vector>

class SqInRect
{
  public:
  static std::vector<int> sqInRect(int lng, int wdth);
};

std::vector<int> SqInRect::sqInRect(int lng, int wdth) {
  std::vector<int> result;
  
  if(lng == wdth) return result;
  
  while(0 < lng && 0 < wdth) {
    result.push_back(lng < wdth ? lng : wdth);
    lng < wdth ? wdth -= lng : lng -= wdth;    
  }
  
  return result;
}

 

8fdafs2의 코드

using namespace std;

class SqInRect
{
  public:
  static vector<int> sqInRect(int lng, int wdth);
};

vector<int> SqInRect::sqInRect(int l, int w) {
    vector<int> ret;
    if (w == l) return ret;
    if (w > l) swap(l, w);
    while (w > 0) {
      ret.push_back(w);
      int t = w;
      w = l - w;
      l = t;
      if (w > l) swap(l, w);
    }
    return ret;
}

 

후기

막상 풀어보니 쉬웠다. 가로와 세로 길이 중 더 긴 것에서 짧은 것을 빼내고 다시 체크 다시 연산. 하지만 처음 이 문제를 보고서는 코드 카타를 접을 뻔했다. 왜냐하면, 이 문제는 반드시 피보나치수열로 이루어져 있고, 그렇게 풀면 될 것이라고 생각했기에 문제가 정말 안 풀렸기 때문이다. 사실 피보나치수열 개념으로 풀어도 되긴 한다. 단, 주어진 테스트 케이스에서만... 고정관념에서 벗어나는 사고방식을 가질 수 있도록 노력해봐야겠다.

남의 코드들을 봐도 그렇게 까다로운 문제가 아니었다. 그런데도 못했다는 건... 더욱 정진해야 한다는 뜻?

 

(url: https://www.codewars.com/kata/55466989aeecab5aac00003e)