Схожие формы

23

Похожие цифры

Два прямоугольника похожи, если отношения их сторон одинаковы.

Рассмотрим эти два прямоугольника; прямоугольник высотой 5 строк и шириной 11 символов:

===========
===========
===========
===========
===========

и прямоугольник высотой 10 строк и шириной 22 символа:

======================
======================
======================
======================
======================
======================
======================
======================
======================
======================

Эти формы похожи, потому что соотношения их сторон одинаковы. Чтобы выразить это формально ( h - самая короткая сторона, а w - самая длинная):

h1w1=h2w2

Вы также можете сделать:

h1h2=w1w2

Соревнование

Напишите программу или функцию, которая принимает «основной» прямоугольник и некоторые «другие» прямоугольники и печатает, какие из «других» похожи на «основные».

Вход

Форма и список форм. Каждая фигура состоит из 2 ненулевых натуральных чисел, которые обозначают ширину и высоту прямоугольника. Например, это:

(4,2), (3,9)

обозначает два прямоугольника, 4x2 и 3x9. Точный формат ввода может быть любым, по вашему желанию.

Выход

Индексы «других» фигур похожи на «основные». Вы можете выбрать, будут ли индексы основаны на 0 или 1, а также на точном формате и порядке вывода.

Пример программы

В Python:

main = eval(raw_input()) # The main rectangle.
rects = eval(raw_input()) # The list of rectangles.
similar = set()
for i, rect in enumerate(rects):
    if max(main)*min(rect) == min(main)*max(rect): # Cross-multiply
        # They are similar.
        similar.add(i)

print similar

Пример ввода и вывода

Входные данные:

(1, 2)
[(1, 2), (2, 4)]

Выход:

set([0, 1])

Входные данные:

(1, 2)
[(1, 9), (2, 5), (16, 8)]

Выход:

set([2])

выигрыш

Это код-гольф, поэтому выигрывает самое короткое представление.

Заметки

  • Это само собой разумеется, но стандартные лазейки запрещены .
  • Никакие встроенные функции для поиска похожих фигур не могут быть использованы. (Я даже не знаю, существует ли это, но я не удивлюсь!)
kirbyfan64sos
источник
Разрешено ли использование деления с плавающей запятой? Будет [1.0 2.0]ли приемлемый формат ввода?
Деннис
@Dennis При условии, что выбранный вами язык не имеет странно низкой точности с плавающей запятой и, следовательно, тесты не пройдены, все должно быть хорошо. ;)
kirbyfan64sos
Вместо индексов можем ли мы сами вывести фактические похожие фигуры?
orlp
@ или нет Нет! : D
kirbyfan64sos
3
Является ли выходной формат вывода индексов обязательным? Для теста, например [(1,2), (2,4), (1,9), (2,5), (16,8)], только [0,1,4]и [1,2,5]разрешено, или мы могли бы также вывести [1,1,0,0,1]или [(1,2), (2,4), (16,8)]?
Кевин Круйссен

Ответы:

11

Python, 61 байт

lambda a,b,l:[i for i,(x,y)in enumerate(l)if x/y in[a/b,b/a]]

Да, я трачу 9 символов, чтобы написать enumerate. Принимает участие как 1, 2, [(1, 9), (3,6), (2, 5), (16, 8)]. Для Python 2 входные значения должны быть записаны как числа с плавающей запятой.

На один символ длиннее (62) в Python 3:

def f(a,b,l,i=0):
 for x,y in l:b/a!=x/y!=a/b or print(i);i+=1
XNOR
источник
Вы не против объяснить это? Я хотел бы знать, что происходит.
The_Basset_Hound
@BassetHound для каждого элемента в списке ввода, понимание распаковывается iкак индекс и (x,y)как точка. Затем он проверяет, x/yравняется ли значение либо исходному двум числам 'quotient ( a/b), либо его обратному ( b/a). Если оно равно одному из этих значений, это значение iдобавляется в список, в противном случае оно отбрасывается.
FryAmTheEggman
9

CJam, 22 20 19 байтов

{:$::/_0=f=ee::*0-}

Выше приведена анонимная функция, которая извлекает один массив пар с плавающей запятой (первая пара - игла) из стека и возвращает массив индексов, основанных на 1, в ответ.

Попробуйте онлайн в интерпретаторе CJam .

Как это работает

:$                e# Sort each pair.
  ::/             e# [a b] -> a/b
     _0=          e# Push a copy of the array and extract the first float (needle).
        f=        e# Check which floats are equal to the needle.
          ee      e# Enumerate the resulting Booleans.
            ::*   e# Multiply each Boolean by its index.
                  e# This yields 0 for the needle (index 0) and for non-matching
                  e# haystack pairs (Boolean 0).
               0- e# Remove all zeroes from the array.
Деннис
источник
8

Haskell , 48 байтов

(a!b)l=[i|(i,(x,y))<-zip[0..]l,x/y+y/x==a/b+b/a]

Попробуйте онлайн!

Назовите это как (!) 1 2 [(1, 9), (3,6), (2, 5), (16, 8)].

Ближний порт моего ответа Python . Выражение zip[0..]lперечисляет список с его индексами.

Выражение x/y+y/x==a/b+b/aпроверяет, что отношение x/yравно a/bили b/a, так как функция f(z) = z + 1/zимеет f(z) = f(1/z)и не имеет других коллизий.

XNOR
источник
Может быть, заставить hоператора принимать три аргумента? Это спасло бы один байт, и я думаю, что это останется в рамках правил.
dfeuer
@dfeuer Конечно, это определенно разрешено современными стандартами, хотя в прошлом было более размыто, какие свободы можно было бы получить с помощью ввода / вывода.
xnor
7

Снеговик 1.0.2 , 61 символ

}vgvgaC"[0-9]+"sM:10sB;aM2aG:AsO:nD;aF;aM0AAgaA*|:#eQ;AsItSsP

Чистая тарабарщина (если только вы не знаете Снеговика), то есть в точности совпадающая с целью создания языка, которая заключается в том, чтобы как можно больше сбивать с толку.

Формат ввода такой же, как и в посте, формат вывода тоже минус set(и ).

Ungolfed (или unminified, действительно):

}vgvgaC     // read two lines of input, concatenate
"[0-9]+"sM  // use a regex to grab all numbers
:10sB;aM    // essentially map(parseInt)
2aG         // take groups of 2 (i.e. all the ordered pairs)

// now map over each ordered pair...
:
  AsO       // sort
  :nD;aF    // fold with division - with 2 array elements, this is just a[0]/a[1]
;aM

// we now have an array of short side to long side ratios
// take out the first one
0AAgaA      // active vars beg, b=array[0], g=the rest
*|          // store first ordered pair in permavar, bring the rest to top

// select indices where...
:
  #         // retrieve first ordered pair
  eQ        // equal?
;AsI

tSsP  // to-string and output

Я очень горжусь некоторыми уловками, которые я использовал в этом:

  • Я использовал тот же формат ввода, что и в посте. Но вместо того, чтобы попытаться как-то разобрать его, что может привести к путанице, я просто объединил две строки, а затем использовал регулярное выражение для извлечения всех чисел в один большой массив (что я и сделал 2aG, то есть получил каждую группу из 2).

  • :nD;aFэто довольно модно Он просто берет массив из двух элементов и делит первый на второй. Это кажется довольно простым, но сделать это интуитивно понятным способом ( a[0]/a[1]) было бы намного, намного дольше в Snowman: 0aa`NiN`aA|,nD(и это предполагает, что нам не нужно беспокоиться о путанице с другими существующими переменными). Вместо этого я использовал метод «сгиба» с предикатом «делить», который для массива из двух элементов достигает одного и того же.

  • 0AAgaAвыглядит достаточно безобидным, но на самом деле он сохраняет 0переменные, а затем берет все переменные с индексом, превышающим этот (то есть все переменные, кроме первой). Но хитрость заключается в том, что вместо AaG(который избавит от исходного массива и 0) я использовал AAg, который сохраняет оба. Теперь я использую aAat-index, используя тот же самый,0 чтобы получить первый элемент массива - более того, он находится в режиме потребления ( aAвместо aa), поэтому он также избавляется от 0и исходного массива, который теперь является мусором для нас.

    Увы, 0AAgaA*|делает по существу то же самое , что делает GolfScript в один символ: (. Тем не менее, я все еще думаю, что это довольно хорошо, по стандартам Snowman. :)

Дверная ручка
источник
3

Mathematica, 41 байт

Position[a=Sort@#;Sort@#/a&/@#2,{x_,x_}]&

Использование:

Position[a = Sort@#; Sort@#/a & /@ #2, {x_, x_}] &[{1, 2}, {{1, 2}, {2, 5}, {16, 8}}]
(* {{1}, {3}} *)
Мартин Эндер
источник
1
Я просто знал, что Mathematica собирается придумать как-нибудь!
kirbyfan64sos
3

Pyth - 14 байт

Фильтры путем сравнения факторов, затем карты indexOf.

xLQfqcFSTcFvzQ

Тестовый пакет .

Maltysen
источник
Это не сортирует основную фигуру, поэтому даст неправильный ответ, когда длина первой стороны основной фигуры будет больше. Смотрите этот тестовый пример
Исаак
@isaacg хорошая мысль, исправлю.
Maltysen
Это терпит неудачу на входах с повторяющимися элементами, например, 1,2и [(1, 2), (2, 4), (1, 2)]даст[0, 1, 0] а не правильно [0, 1, 2].
Орл
Я хочу принять это одно, так как он является самым коротким, но проблема @orlp упоминалось исправлена?
kirbyfan64sos
1
@ kirbyfan64sos Нет.
orlp
3

APL (Dyalog Unicode) , 16 13 байтов SBCS

(=.×∘⌽∨=.×)⍤1

Попробуйте онлайн!

-3 спасибо @ngn!

Объяснение:

(=.×∘⌽∨=.×)⍤1
(        )    "OR" together...
 =.    =.      ...fold by equality of:
   ×∘⌽         - the arguments multiplied by itself reversed
         x     - the argument multiplied by itself
           1  Applied at rank 1 (traverses)

Выходной формат - это двоичный вектор, подобный 1 1 0 0 1которому «другой» прямоугольник похож на другой.

APL (Dyalog Extended) , 11 байтов SBCS

=/-×⍥(⌈/)¨⌽

Попробуйте онлайн!

Объяснение:

=/-×⍥(⌈/)¨⌽  takes only a right argument: ⍵, shape: (main (other...))
            two transformations:
  -          - left (L) vectorized negation: -⍵
            - right (R): reverse. (main other) => (other main)
     (⌈/)¨   transformation: calculate the max (since L is negated, it calculates the min)
             (/ reduces over  max)
             this vectorizes, so the "main" side (with only one rect) will get repeated once for each "other" rect on both sides
   ×⍥        over multiplication: apply the transformation to both sides. F(LF(R)
=/           reduce the 2-element matrix (the "main" that's now the side of the "other") to check which are equal

Формат вывода совпадает с основным ответом Dyalog.

Спасибо Адаму за помощь в игре в гольф + Extended.

Вен
источник
(=.×∘⌽∨=.×)⍤1
СПП
Спасибо. Постараюсь проверить это первым
Ven
2

Юлия, 62 байта

f(m,o)=find([(t=sort(m).*sort(i,rev=true);t[1]==t[2])for i=o])

findФункция находит истинные элементы булева вектора. .*выполняет поэлементное умножение векторов.

Ungolfed:

function f(m::Array, o::Array)
    find([(t = sort(m) .* sort(i, rev=true); t[1] == t[2]) for i in o])
end

Использование:

f([1,2], {[1,9], [2,5], [16,8]})
Алекс А.
источник
2

К5, 19 байт

Я думаю, что это добьется цели:

&(*t)=1_t:{%/x@>x}'

Принимает список пар, где первая является «главной». Вычисляет соотношение путем деления отсортированных размеров каждой пары. Возвращает список позиций с 0 индексами совпадающих пар. (возможно, выбранный формат ввода делает это -1 индексируемым - если это считается недействительным1+ в начале и добавляет два символа к размеру моей программы.)

Пример использования:

  &(*t)=1_t:{%/x@>x}'(1 2;1 2;2 4;2 5;16 8)
0 1 3

Это работает хорошо - обратите внимание, что я неявно зависим от деления, всегда приводящего к результатам с плавающей запятой. Это будет работать в Kona, если вы добавите десятичную точку ко всем числам на входе и добавите пробел после _.

Johne
источник
2

Октава / Матлаб, 44 байта

Использование анонимной функции:

@(x,y)find((max(x))*min(y')==min(x)*max(y'))

Результат - индексирование на основе 1.

Чтобы использовать его, определите функцию

>> @(x,y)find((max(x))*min(y')==min(x)*max(y'));

и назовите его в следующем формате

>> ans([1 2], [1 9; 2 5; 16 8])
ans =
     3

Вы можете попробовать это онлайн .


Если результат может быть в логической индексации ( 0указывает на не похожее, 1указывает на сходное): 38 байт :

@(x,y)(max(x))*min(y')==min(x)*max(y')

Тот же пример, что и выше:

>> @(x,y)(max(x))*min(y')==min(x)*max(y')
ans = 
    @(x,y)(max(x))*min(y')==min(x)*max(y')

>> ans([1 2], [1 9; 2 5; 16 8])
ans =
 0     0     1
Луис Мендо
источник
2

Брахилог , 14 байт

z{iXhpᵐ/ᵛ∧Xt}ᵘ

Попробуйте онлайн!

Принимает входные данные в виде списка, содержащего список, содержащий основной прямоугольник и список других прямоугольников (так что тестовый пример 1 [[[1,2]],[[1,2],[2,4]]]), и выводит список индексов на основе 0 через выходную переменную.

z                 Zip the elements of the input, pairing every "other" rectangle with the main rectangle.
 {          }ᵘ    Find (and output) every unique possible output from the following:
  iX              X is an element of the zip paired with its index in the zip.
    h             That element
      ᵐ           with both of its elements
     p            permuted
        ᵛ         produces the same output for both elements
       /          when the first element of each is divided by the second.
         ∧Xt      Output the index.

Если такое нечетное и специфичное форматирование ввода обманывает, это немного дольше ...

Брахилог , 18 байт

{hpX&tiYh;X/ᵛ∧Yt}ᶠ

Попробуйте онлайн!

Принимает входные данные в виде списка, содержащего основной прямоугольник и список других прямоугольников (таким образом, тестовый пример 1 является более очевидным [[1,2],[[1,2],[2,4]]]), и выводит список основанных на 0 индексов через выходную переменную.

{               }ᵘ    Find (and output) every possible output from the following:
  p                   A permutation of
 h                    the first element of the input
   X                  is X,
    &                 and
      i               a pair [element, index] from
     t                the last element of the input
       Y              is Y,
        h             the first element of which
            ᵛ         produces the same output from
           /          division
         ;            as
          X           X.
             ∧Yt      Output the index.

Чтобы определить, представляют ли две пары ширина-высота одинаковые прямоугольники, требуется всего четыре байта pᵐ/ᵛ(которые выводят общее отношение или его обратную величину). Все остальное обрабатывает несколько прямоугольников для сравнения, а выходные данные являются индексами.

Несвязанная строка
источник
2

dzaima / APL , 7 байтов

=/⍤÷⍥>¨

Попробуйте онлайн!

8 байтов, выводящих список индексов вместо логического вектора

      ¨ for each (pairing the left input with each of the right)
    ⍥>    do the below over sorting the arguments
=/          equals reduce
           after
   ÷        vectorized division of the two
dzaima
источник
Хотя это хороший ответ, мы должны вывести индексы. Таким образом, ваш тестовый случай TIO должен привести либо к ( [0,1,4]или [1,2,5]не уверен, что ваш язык имеет индекс 0 или 1). Было бы лучше, если бы все три формата вывода были разрешены: индексы; фильтр для сохранения правдивых значений; список истинных / ложных значений (как у вас сейчас), а не только разрешенные индексы.
Кевин Круйссен
@KevinCruijssen "Вы можете выбрать [...] точный формат и порядок вывода." в APL очень распространенная практика хранить индексы как логический вектор, но вы правы, это, вероятно, следует уточнить.
Дзайма
Ну, я прочитал « Вы можете выбрать , будет ли индексы 0- или 1 на основе, а также точный формат и порядок вывода. » , Как это может быть [0,1,4], [1,2,5], 4\n0\n1, 5 2 1и т.д. и т.п., так как он по- прежнему указано индексы , Но я попросил ОП уточнить (если они ответят, так как это 4-летний вызов). В моем ответе 05AB1E это означало бы 14 байтов, если индексы являются обязательными, против 8 байтов, если разрешен любой из двух других вариантов. Несмотря на это, я проголосовал за ваш ответ. :)
Кевин Круйссен
1

PowerShell , 58 56 байт

-2 байта благодаря mazzy x2

param($x,$y,$b)$b|%{($i++)[$x/$y-($z=$_|sort)[0]/$z[1]]}

Попробуйте онлайн!

Это немного нарушает input may be however you desireпредложение, поскольку компоненты первой фигуры идут отдельно, чтобы сохранить 3 байта.

PowerShell , 61 59 байт

param($a,$b)$b|%{($i++)[$a[0]/$a[1]-($x=$_|sort)[0]/$x[1]]}

Попробуйте онлайн!

Использует условную индексацию для переключения между текущим индексом, начинающимся с нуля, и нулем в зависимости от того, выстроены ли соотношения. К счастью, в этом случае $iувеличивается, независимо от того, напечатан он или нет.

Veskah
источник
1
Вы можете сэкономить больше, если вы используете -вместо этого -ne.
Маззи
0

Javascript (ES6), 75

(a,b)=>b.filter(e=>e.l*a.h==a.l*e.h||e.l*a.l==a.h*e.h).map(e=>b.indexOf(e))

Альтернатива, также 75

(a,b)=>b.map((e,i)=>e.l*a.h==a.l*e.h||e.l*a.l==a.h*e.h?i:-1).filter(e=>e+1)

Ввод принимается как объект JSON, а массив объектов JSON

{
    l: length of rectangle,
    h: height of rectangle
}
DankMemes
источник
Я не думаю, что это работает со вторым тестовым примером.
kirbyfan64sos
@ kirbyfan64sos извините, не видел эту часть. Это исправлено (но я уверен, что я могу
играть в
Это не объекты JSON, это простые объекты javascript. JSON - это формат передачи данных.
edc65
0

05AB1E , 15 14 байтов

ʒ‚ε{ü/}Ë}J¹Jsk

Попробуйте онлайн или проверьте все контрольные примеры .

Объяснение:

ʒ               # Filter the (implicit) input-list by:
               #  Pair the current width/height with the (implicit) input width/height
  ε             #  Map both width/height pairs to:
   {            #   Sort from lowest to highest
    ü/          #   Pair-wise divide them from each other
              #  After the map: check if both values in the mapped list are equals
        }J      # After the filter: join all remaining pairs together to a string
          ¹J    # Also join all pairs of the first input together to a string
            s   # Swap to get the filtered result again
             k  # And get it's indices in the complete input-list
                # (which is output implicitly)

J OINS там , потому что 05AB1E не может определить индексы на многомерные списки AFAIK


Если вывести пары ширины / высоты, которые являются правдивыми, или вывести список значений истинности / фальши на основе input-list, это может быть 8 байт :

ʒ‚ε{ü/}Ë

Попробуйте онлайн или проверьте все контрольные примеры .

ε‚ε{ü/}Ë

Попробуйте онлайн или проверьте все контрольные примеры .

Кевин Круйссен
источник