В массиве, как узнать, могут ли выбранные индексы создавать прямоугольник или квадрат?

Question

У меня есть такой массив:

array = [
0, 1, 2, 3,
4, 5, 6, 7,
8, 9, 10, 11,
12, 13, 14, 15
];

И ввод, подобный следующему:

input = [5,6,9,10]

Когда мы сравниваем этот ввод с массивом, мы видим, что этот ввод фактически создает квадрат в массиве.

input = [6,9,10]

Этот, напротив, создает треугольник.

Я хочу написать функцию, которая проверяет, создает ли введенный ввод прямоугольник или квадрат . Если так, возвращает true, иначе возвращает false. Как мне написать эту функцию?

Answer 1

Вам необходимо sh заранее установить, является ли исходный массив квадратом или прямоугольником.

Внутреннее представление идентично, даже если массив не является квадратом с W = 4 и H = 4, но

[ 0, 1,  2,  3,  4,  5,  6,  7,
  8, 9, 10, 11, 12, 13, 14, 15 ];

, который представляет собой прямоугольник с W = 8, H = 2.

Вы можете видеть, что (5,6,9,10) образует квадрат, если W = 4, но ничего не делает, если W = 8.

Предположим, вам известна ширина массива W (и, следовательно, его высота H, которая является размером массива, деленным на W), тогда, если у вас есть для элемента N, такого как 5, его двумерные координаты в системе WH равны

{ 
  x: N % W, 
  y: floor(N / W)
}

Итак, вы видите, что N = 5 становится (1,1). Как только у вас есть двумерные координаты всех элементов, проверить форму не составит труда.

Квадрат и прямоугольник: у вас есть четыре элемента, (x1, y1), (x2, y2), (x3, y3), (х4, у4). Это квадрат или прямоугольник, ориентированный как массив, если x1 = x3, y1 = y2, x2 = x4 и y3 = y4. Если тогда x2-x1 равно y3-y1, это квадрат; в противном случае - прямоугольник.

Вы можете добавить более сложные условия, чтобы проверить другие варианты. Например, сторона 1-2 - это квадрат root из (x2-x1) (x2-x1) + (y2-y1) (y2-y1). То же самое можно сделать с диагоналями 1-3 и 2-4 и всеми остальными сторонами. Если диагонали одинаковой длины, это прямоугольник (или квадрат). Если дополнительно 1-2 и 2-3 стороны равны, то это квадрат. Это более сложное условие работает независимо от ориентации квадрата (то есть (2,6,8,10) будет распознано как квадрат).

Три точки всегда являются треугольником, если только сумма двух из три стороны в точности равны третьей (это вырожденный треугольник ). Если квадрат длины одной стороны равен сумме квадратов двух других, вы получите прямоугольный треугольник angular. Проверить наличие равнобедренности и равносторонности несложно.

Если вы не знаете W, вам нужно факторизовать размер S массива и попробовать все возможности. 16 равно 2 * 2 * 2 * 2, поэтому вам нужно проверить W = 2, W = 4, W = 8 и W = 16.

Answer 2

Предполагая, что прямоугольник должен быть выровнен по оси, а ввод упорядочен, тогда [a, b, c, d] образует прямоугольник, если (4096*a + 256*b + 16*d + c) % 17 = 0.

Это работает только для этого конкретного расположения значений от 0 до 15. Если у вас есть 25 значений (0-24), расположенных аналогичным образом, вы можете вместо этого использовать (15625*a + 625*b + 25*d + c) % 26 = 0. Шаблон можно обобщить.

Answer 3

Вы можете проверить, является ли данный вход прямоугольником или треугольником, определив два метода isRectangle и isTriangle и вызвав

return isTriangle(input) OR is Rectangle(input)

с

isRectangle(input):
   return length(input) == 4 AND input[0] < input [1] < input[2] < input [3]

и

isTriangle(input):
   return length(input) == 3 AND input[0] < input [1] < input[2]