Podobne kształty

23

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

h1w1=h2)w2)

Możesz także:

h1h2)=w1w2)

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!)
kirbyfan64sos
źródło
Czy stosowanie podziału zmiennoprzecinkowego jest dozwolone? Byłby [1.0 2.0]akceptowalny format wejściowy?
Dennis,
@Dennis Pod warunkiem, że wybrany język nie ma dziwnie niskiej precyzji zmiennoprzecinkowej, a zatem przypadki testowe zawodzą, powinno być dobrze. ;)
kirbyfan64sos
Czy zamiast indeksów możemy również wyprowadzać same podobne kształty?
orlp
@orlp Nope !!! : D
kirbyfan64sos
3
Czy format wyjściowy generowania wskaźników jest obowiązkowy? W przypadku testowym typu „ [(1,2), (2,4), (1,9), (2,5), (16,8)]jest tylko [0,1,4]i [1,2,5]dozwolone”, czy możemy również generować dane wyjściowe [1,1,0,0,1]lub [(1,2), (2,4), (16,8)]?
Kevin Cruijssen

Odpowiedzi:

5

Pyth, 15 bajtów

fqcFS@QTcFSvzUQ
orlp
źródło
11

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
xnor
źródło
Masz coś przeciwko wytłumaczeniu tego? Chciałbym wiedzieć, co się dzieje.
The_Basset_Hound
@BassetHound dla każdego elementu na liście wejściowej, zrozumienie rozpakowuje się ijako indeks i (x,y)jako punkt. Następnie sprawdza, czy wartość x/yjest albo równa ilorazowi pierwszych dwóch liczb ( a/b), czy jego odwrotności ( b/a). Jeśli jest równa jednej z tych wartości, wartość ta ijest dodawana do listy, w przeciwnym razie jest odrzucana.
FryAmTheEggman
9

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.
Dennis
źródło
8

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.

xnor
źródło
Może zmusi hoperatora do wzięcia trzech argumentów? Pozwoliłoby to zaoszczędzić jeden bajt i myślę, że byłby zgodny z zasadami.
dfeuer
@dfeuer Pewnie, jest to na pewno dozwolone przez współczesne standardy, choć z drugiej strony było bardziej niepewne, jakie swobody można uzyskać dzięki I / O.
xnor
7

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

Klamka
źródło
3

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}} *)
Martin Ender
źródło
1
Po prostu wiedziałem, że Mathematica jakoś wymyśli!
kirbyfan64sos
3

Pyth - 14 bajtów

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

xLQfqcFSTcFvzQ

Pakiet testowy .

Maltysen
źródło
Nie sortuje to głównego kształtu, więc da złą odpowiedź, gdy długość pierwszego boku głównego kształtu będzie większa. Zobacz ten przypadek testowy
isaacg,
@isaacg dobry punkt, naprawi.
Maltysen
Nie działa to na przykład na wejściach z powtarzającymi się elementami 1,2i [(1, 2), (2, 4), (1, 2)]da [0, 1, 0]raczej niż poprawne [0, 1, 2].
orlp
Chcę zaakceptować ten, ponieważ jest on najkrótszy, ale czy problem @orlp wymieniony został rozwiązany?
kirbyfan64sos
1
@ kirbyfan64sos No.
orlp
3

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(LF(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.

Ven
źródło
(=.×∘⌽∨=.×)⍤1
ngn
Dzięki. Spróbuję to sprawdzić najpierw
Ven
2

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]})
Alex A.
źródło
2

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 _.

JohnE
źródło
2

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
Luis Mendo
źródło
2

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.

Niepowiązany ciąg
źródło
2

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
dzaima
źródło
Chociaż jest to dobra odpowiedź, musimy wyprowadzać wskaźniki. Więc sprawa TIO badanie powinno skutkować albo [0,1,4]albo [1,2,5](nie wiem, czy Twój język jest 0- lub 1-indeksowane). Lepszym wyzwaniem byłoby imho, gdyby dozwolone były wszystkie trzy formaty wyjściowe: indeksy; filtruj, aby zachować prawdziwe wartości; lista wartości truey / falsey (jak teraz), zamiast tylko dozwolonych indeksów.
Kevin Cruijssen
@KevinCruijssen „Możesz wybrać [...] dokładny format i kolejność danych wyjściowych.” w APL bardzo powszechną praktyką jest przechowywanie indeksów jako wektora boolowskiego, ale masz rację, to prawdopodobnie powinno zostać wyjaśnione.
dzaima
Dobrze, czytałem „ może wybrać, czy indeksy są 0- lub 1-na podstawie, a także dokładny format i kolejność wyjścia. ” Jak to może być [0,1,4], [1,2,5], 4\n0\n1, 5 2 1, itd. Itd., Ponieważ ciągle stwierdził indeksów . Ale poprosiłem OP o wyjaśnienie (jeśli odpowiedzą, ponieważ jest to 4-letnie wyzwanie). W mojej odpowiedzi 05AB1E oznaczałoby to 14 bajtów, jeśli indeksy są obowiązkowe w porównaniu z 8 bajtami, jeśli jedna z dwóch pozostałych opcji jest dozwolona. Niezależnie od tego, głosowałem za odpowiedzią. :)
Kevin Cruijssen
1

Haskell, 75 bajtów

import Data.List
a(x,y)=max x y/min x y
s r=elemIndices(True).map((==a r).a)
Leif Willerts
źródło
56 bajtów
dfeuer
54 bajty
dfeuer
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.

Veskah
źródło
1
Możesz -zamiast tego zaoszczędzić więcej -ne.
mazzy
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))

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
}
DankMemes
źródło
Nie sądzę, że to działa z drugim przypadkiem testowym.
kirbyfan64sos
@ kirbyfan64sos przepraszam, nie widziałem tej części. Jest naprawiony (ale jestem pewien, że mogę bardziej
zagrać w
To nie są obiekty JSON, to zwykłe obiekty javascript. JSON to format przesyłania danych.
edc65
0

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 .

Kevin Cruijssen
źródło