Podobne liczby

Dwa prostokąty są podobne, jeśli proporcje ich boków są takie same.

Rozważ te dwa prostokąty; prostokąt o wysokości 5 linii i szerokości 11 znaków:

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

i prostokąt o wysokości 10 linii i szerokości 22 znaków:

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

Te kształty są podobne, ponieważ proporcje ich boków są takie same. Ujmując to formalnie (gdzie jest najkrótszym bokiem, a najdłuższym bokiem):$h$$w$

Możesz także:

Wyzwanie

Napisz program lub funkcję, która pobiera „główny” prostokąt oraz niektóre „inne” prostokąty i drukuje, które z „innych” są podobne do „głównych”.

Dane wejściowe

Kształt i lista kształtów. Każdy kształt składa się z 2 niezerowych dodatnich liczb całkowitych, które oznaczają szerokość i wysokość prostokąta. Na przykład:

(4,2), (3,9)

oznacza dwa prostokąty, 4x2 i 3x9. Dokładny format danych wejściowych może być dowolny.

Wyjście

Wskaźniki „innych” kształtów podobnych do „głównych”. Możesz wybrać, czy indeksy będą oparte na 0 czy 1, a także dokładny format i kolejność danych wyjściowych.

Przykładowy program

W Pythonie:

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

Przykładowe wejście i wyjście

Wkład:

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

Wydajność:

set([0, 1])

Wkład:

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

Wydajność:

set([2])

Zwycięski

To jest golf golfowy, więc wygrywa najkrótsza przesyłka.

Notatki

• Powinno to być oczywiste, ale standardowe luki są zabronione .
• Nie można używać wbudowanych do lokalizowania podobnych liczb. (Nawet nie wiem, czy to istnieje, ale nie byłbym zaskoczony!)

Pyth, 15 bajtów

fqcFS@QTcFSvzUQ

Python, 61 bajtów

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

Tak, używam do wydania 9 znaków enumerate. Przyjmuje dane wejściowe jak 1, 2, [(1, 9), (3,6), (2, 5), (16, 8)]. W Pythonie 2 wartości wejściowe należy zapisać jako zmiennoprzecinkowe.

O jeden znak dłużej (62) w Pythonie 3:

def f(a,b,l,i=0):
 for x,y in l:b/a!=x/y!=a/b or print(i);i+=1

CJam, 22 20 19 bajtów

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

Powyżej jest anonimowa funkcja, która wyrzuca pojedynczą tablicę par zmiennoprzecinkowych (pierwsza para to igła) ze stosu i wypycha w zamian tablicę indeksów 1.

Wypróbuj online w interpretatorze CJam .

Jak to działa

:$                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.

Haskell , 48 bajtów

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

Wypróbuj online!

Nazwij to tak (!) 1 2 [(1, 9), (3,6), (2, 5), (16, 8)].

Bliski port mojej odpowiedzi w języku Python . Wyrażenie zip[0..]lwylicza listę wraz z jej indeksami.

Wyrażenie x/y+y/x==a/b+b/asprawdza, czy stosunek x/yjest albo, a/balbo b/a, ponieważ funkcja f(z) = z + 1/zma f(z) = f(1/z)i nie ma innych kolizji.

Snowman 1.0.2 , 61 znaków

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

Czysty bełkot (chyba że znasz Bałwana), aka dokładnie zgodny z celem projektu, jakim jest bycie tak zagmatwanym, jak to możliwe.

Format wejściowy jest taki sam jak w poście, format wyjściowy jest również taki sam minus set(i ).

Niegolfowany (lub nieupoważniony, naprawdę):

}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

Jestem bardzo dumny z niektórych sztuczek, których użyłem w tym:

• Użyłem tego samego formatu wejściowego co w poście. Ale zamiast próbować go jakoś parsować, co stałoby się naprawdę nieuporządkowane, po prostu połączyłem dwie linie, a następnie użyłem wyrażenia regularnego, aby wyodrębnić wszystkie liczby w jedną dużą tablicę (przy pomocy której to zrobiłem 2aG, tj. Otrzymałem każdą grupę 2).

• :nD;aFjest dość fantazyjne. Po prostu bierze tablicę dwóch elementów i dzieli pierwszy przez drugi. Co wydaje się dość proste, ale robienie tego intuicyjnie ( a[0]/a[1]) byłoby znacznie dłużej w Snowman: 0aa`NiN`aA|,nD(i zakładając, że nie musimy się martwić o bałagan z innymi istniejącymi zmiennymi). Zamiast tego zastosowałem metodę „fold” z predykatem „divide”, która dla tablicy dwóch elementów osiąga to samo.

• 0AAgaAwygląda wystarczająco nieszkodliwie, ale tak naprawdę zapisuje a 0do zmiennych, a następnie bierze wszystkie zmienne o indeksie większym niż ten (a więc wszystkie zmienne oprócz pierwszej). Ale sztuczka polega na tym, że zamiast AaG(który pozbyłby się oryginalnej tablicy i 0) użyłem AAg, która zachowuje oba. Teraz używam aA, at-index, używając tego samego,0 aby uzyskać pierwszy element tablicy - co więcej, jest to w trybie konsumpcji ( aAzamiast aa), więc pozbywa się również 0oryginalnej tablicy, która jest teraz śmieciem dla nas.

  Niestety, 0AAgaA*|nie w zasadzie to samo, co GolfScript robi w jednej postaci: (. Jednak nadal uważam, że jest całkiem niezły, jak na standardy Snowmana. :)

Mathematica, 41 bajtów

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

Stosowanie:

Position[a = Sort@#; Sort@#/a & /@ #2, {x_, x_}] &[{1, 2}, {{1, 2}, {2, 5}, {16, 8}}]
(* {{1}, {3}} *)

Pyth - 14 bajtów

Filtruje przez porównanie ilorazów, a następnie map indexOf.

xLQfqcFSTcFvzQ

Pakiet testowy .

APL (Dyalog Unicode) , 16 13 bajtów ^SBCS

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

Wypróbuj online!

-3 dzięki @ngn!

Wyjaśnienie:

(=.×∘⌽∨=.×)⍤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)

Format wyjściowy jest wektorem binarnym, 1 1 0 0 1którego „inny” prostokąt przypomina wyglądem.

APL (Dyalog Extended) , 11 bajtów ^SBCS

=/-×⍥(⌈/)¨⌽

Wypróbuj online!

Wyjaśnienie:

=/-×⍥(⌈/)¨⌽ ⍝ 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(L)×F(R)
=/          ⍝ reduce the 2-element matrix (the "main" that's now the side of the "other") to check which are equal

Format wyjściowy jest taki sam jak główna odpowiedź Dyalog.

Dzięki Adám za pomoc w grze w golfa + Extended.

Julia, 62 bajty

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

findFunkcja lokalizuje prawdziwe elementy w logiczną wektorze. .*wykonuje elementowe mnożenie wektorów.

Nie golfowany:

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

Stosowanie:

f([1,2], {[1,9], [2,5], [16,8]})

K5, 19 bajtów

Myślę, że to załatwi sprawę:

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

Pobiera listę par, w których pierwsza jest „główna”. Oblicza współczynnik, dzieląc posortowane wymiary każdej pary. Zwraca listę indeksowanych pozycji 0 pasujących par. (prawdopodobnie wybrany przeze mnie format wejściowy powoduje indeksowanie -1 - jeśli jest to uważane za nieprawidłowe tals 1+na początku i dodaje dwa znaki do rozmiaru mojego programu).

Przykład użycia:

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

Działa to w porządku - zauważ, że domyślnie polegam na podziale, który zawsze daje wyniki zmiennoprzecinkowe. To działałoby w Kona, jeśli dodałeś przecinek dziesiętny do wszystkich liczb na wejściu i dodałeś spację po _.

Octave / Matlab, 44 bajty

Korzystanie z anonimowej funkcji:

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

Wynikiem jest indeksowanie 1.

Aby z niego skorzystać, zdefiniuj funkcję

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

i nazwij to w następującym formacie

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

Możesz spróbować online .

Jeśli wynik może być w logicznym indeksowaniu ( 0wskazuje nie podobny, 1oznacza podobny): 38 bajtów :

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

Taki sam przykład jak powyżej:

>> @(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

Brachylog , 14 bajtów

z{iXhpᵐ/ᵛ∧Xt}ᵘ

Wypróbuj online!

Pobiera dane wejściowe jako listę zawierającą listę zawierającą główny prostokąt i listę innych prostokątów (tak jak w przypadku testowym 1 [[[1,2]],[[1,2],[2,4]]]) i wysyła listę indeksów opartych na 0 poprzez zmienną wyjściową.

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.

Jeśli tego rodzaju dziwne i specyficzne formatowanie danych wejściowych oszukuje, jest to trochę dłużej ...

Brachylog , 18 bajtów

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

Wypróbuj online!

Pobiera dane wejściowe jako listę zawierającą główny prostokąt i listę innych prostokątów (więc przypadek testowy 1 jest bardziej oczywisty [[1,2],[[1,2],[2,4]]]) i wysyła listę wskaźników opartych na 0 poprzez zmienną wyjściową.

{               }ᵘ    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.

Aby ustalić, czy dwie pary szerokość-wysokość reprezentują podobne prostokąty, wystarczy wziąć cztery bajty pᵐ/ᵛ(co daje wynik wspólnego współczynnika lub jego wzajemności). Cała reszta obsługuje wiele prostokątów do porównania, a dane wyjściowe są indeksami.

dzaima / APL , 7 bajtów

=/⍤÷⍥>¨

Wypróbuj online!

8 bajtów wyprowadzających listę indeksów zamiast wektora boolowskiego

      ¨ 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

Haskell, 75 bajtów

import Data.List
a(x,y)=max x y/min x y
s r=elemIndices(True).map((==a r).a)

PowerShell , 57 bajtów

$args|%{$x,$y=$_|sort
($i++)[$r-$y/$x]
if(!$r){$r=$y/$x}}

Wypróbuj online!

Indeksy są oparte na 1.

PowerShell , 58 56 bajtów

^{-2 bajty dzięki mazzy x2}

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

Wypróbuj online!

To nieznacznie narusza input may be however you desireklauzulę, ponieważ komponenty pierwszego kształtu są dostarczane osobno, aby zaoszczędzić 3 bajty.

PowerShell , 61 59 bajtów

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

Wypróbuj online!

Używa indeksowania warunkowego do przełączania między bieżącym indeksem zerowym a zerowym w zależności od tego, czy stosunki się zgadzają. Na szczęście w tym przypadku $iprzyrosty są wykonywane niezależnie od tego, czy zostaną wydrukowane, czy nie.

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))

Alternatywnie, również 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)

Dane wejściowe są traktowane jako obiekt JSON i tablica obiektów JSON

{
    l: length of rectangle,
    h: height of rectangle
}

05AB1E , 15 14 bajtów

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

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

ʒ               # 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)

Na JMonety są tam dlatego 05AB1E nie można określić indeksy na wielowymiarowe listy AFAIK

Jeśli wyprowadzasz pary szerokości / wysokości, które są prawdziwe, lub wypisujesz listę wartości prawdy / falseya na podstawie listy danych wejściowych, może to być 8zamiast bajtów :

ʒ‚ε{ü/}Ë

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

ε‚ε{ü/}Ë

Wypróbuj online lub sprawdź wszystkie przypadki testowe .