Lookalike shapes

Question

Similar figures

Two rectangles are similar if the ratios of their sides are the same.

Consider these two rectangles; a rectangle 5 lines tall and 11 chars wide:

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

and a rectangle 10 lines tall and 22 chars wide:

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

These shapes are similar because the ratios of their sides are the same. To put it formally (with \$h\$ being the shortest side and \$w\$ being the longest side):

$$ \frac{h_1}{w_1} = \frac{h_2}{w_2} $$

You can also do:

$$ \frac{h_1}{h_2} = \frac{w_1}{w_2} $$

The challenge

Write a program or function that takes a "main" rectangle and some "other" rectangles and prints which of "others" are similar to "main".

The input

A shape and a list of shapes. Each shape consists of 2 non-zero positive integers, which denote the width and height of the rectangle. For instance, this:

(4,2), (3,9)

denotes two rectangles, a 4x2 and a 3x9. The exact format of the input may be however you desire.

The output

The indices of the "other" shapes that are similar to "main". You may choose whether the indices are 0- or 1-based, as well as the exact format and order of the output.

Sample program

In 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

Sample input and output

Input:

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

Output:

set([0, 1])

Input:

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

Output:

set([2])

Winning

This is code-golf, so the shortest submission wins.

Notes

• This should go without saying, but standard loopholes are banned.
• No builtins for locating similar figures may be used. (I don't even know if that exists, but I would't be surprised!)

Answer 1

Pyth, 15 bytes

fqcFS@QTcFSvzUQ

Answer 2

Python, 61 bytes

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

Yes, I'm using spending 9 chars to write enumerate. Takes input like 1, 2, [(1, 9), (3,6), (2, 5), (16, 8)]. For Python 2, input values need to be written as floats.

One char longer (62) in 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

Answer 3

CJam, 22 20 19 bytes

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

The above is an anonymous function that pops a single array of floating point pairs (first pair is needle) from the stack and pushes the array of 1-based indexes in return.

Try it online in the CJam interpreter.

How it works

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

Answer 4

Haskell, 48 bytes

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

Try it online!

Call this like (!) 1 2 [(1, 9), (3,6), (2, 5), (16, 8)].

A near-port of my Python answer. The expression zip[0..]l enumerates the list with its indices.

The expression x/y+y/x==a/b+b/a checks that the ratio x/y is either a/b or b/a, since the function f(z) = z + 1/z has f(z) = f(1/z) and no other collisions.

Answer 5

Snowman 1.0.2, 61 chars

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

Pure gibberish (unless you happen to know Snowman), a.k.a. exactly in line with the language's design goal of being as confusing as possible.

Input format is same as in the post, output format is also the same minus set( and ).

Ungolfed (or unminified, really):

}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

I'm pretty proud of some of the tricks I used in this one:

• I used the same input format as in the post. But instead of trying to parse it somehow, which would get really messy, I just concatenated the two lines and then used a regex to extract all the numbers into one big array (with which I then did 2aG, i.e. get every group of 2).

• :nD;aF is pretty fancy. It simply takes an array of two elements and divides the first one by the second one. Which seems pretty simple, but doing it the intuitive way (a[0]/a[1]) would be far, far longer in Snowman: 0aa`NiN`aA|,nD (and that's assuming we don't have to worry about messing with other existing variables). Instead, I used the "fold" method with a predicate of "divide," which, for an array of two elements, achieves the same thing.

• 0AAgaA looks innocuous enough, but what it actually does is store a 0 to the variables, then takes all variables with an index greater than that (so, all variables except for the first one). But the trick is, instead of AaG (which would get rid of the original array and the 0), I used AAg, which keeps both. Now I use aA, at-index, using the very same 0 to get the first element of the array—furthermore, this is in consume-mode (aA instead of aa), so it gets rid of the 0 and original array too, which are now garbage for us.

  Alas, 0AAgaA*| does essentially the same thing that GolfScript does in one character: (. However, I still think it's pretty nice, by Snowman standards. :)

Answer 6

APL (Dyalog Unicode), 16 13 bytes^SBCS

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

Try it online!

-3 thanks to @ngn!

Explanation:

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

Output format is a binary vector like 1 1 0 0 1 of which "other" rectangle is a look-a-like.

APL (Dyalog Extended), 11 bytes^SBCS

=/-×⍥(⌈/)¨⌽

Try it online!

Explanation:

=/-×⍥(⌈/)¨⌽ ⍝ 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

Output format is the same as the main Dyalog answer.

Thanks to Adám for the help golfing + Extended.

Answer 7

Mathematica, 41 bytes

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

Usage:

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

Answer 8

Pyth - 14 bytes

Filters by comparing quotients, then maps indexOf.

xLQfqcFSTcFvzQ

Test Suite.

Answer 9

Brachylog, 14 bytes

z{iXhpᵐ/ᵛ∧Xt}ᵘ

Try it online!

Takes input as a list containing a list containing the main rectangle and the list of other rectangles (so test case 1 is [[[1,2]],[[1,2],[2,4]]]), and outputs a list of 0-based indices through the output variable.

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.

If that sort of odd and specific input formatting is cheating, it's a bit longer...

Brachylog, 18 bytes

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

Try it online!

Takes input as a list containing the main rectangle and the list of other rectangles (so test case 1 is the more obvious [[1,2],[[1,2],[2,4]]]), and outputs a list of 0-based indices through the output variable.

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

To determine if two width-height pairs represent similar rectangles, it just takes the four bytes pᵐ/ᵛ (which outputs the shared ratio or its reciprocal). All the rest is handling the multiple rectangles to compare, and the output being indices.

Answer 10

dzaima/APL, 7 bytes

=/⍤÷⍥>¨

Try it online!

8 bytes outputting a list of indices instead of a boolean vector

      ¨ 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

Answer 11

Julia, 62 bytes

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

The find function locates true elements in a boolean vector. .* performs elementwise multiplication of vectors.

Ungolfed:

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

Usage:

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

Answer 12

K5, 19 bytes

I think this will do the trick:

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

Takes a list of pairs where the first is the "main". Computes the ratio by dividing the sorted dimensions of each pair. Returns a list of the 0-indexed positions of the matching pairs. (arguably the input format I chose makes this -1 indexed- if this is considered invalid tack on a 1+ to the beginning and add two characters to the size of my program.)

Usage example:

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

This runs in oK- note that I implicitly depend on division always producing floating point results. It would work in Kona if you added a decimal point to all the numbers in the input and added a space after the _.

Answer 13

Octave / Matlab, 44 bytes

Using an anonymous function:

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

The result is in 1-based indexing.

To use it, define the function

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

and call it with the following format

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

You can try it online.

---

If the result can be in logical indexing (0 indicates not similar, 1 indicates similar): 38 bytes:

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

Same example as above:

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

Answer 14

PowerShell, 58 56 bytes

^{-2 bytes thanks to mazzy x2}

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

Try it online!

This slightly abuses the input may be however you desire clause by having the first shape's components come separately to save 3 bytes.

PowerShell, 61 59 bytes

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

Try it online!

Uses conditional indexing to swap between the current zero-based index and null based on whether or not the ratios line up. Luckily in this case, $i increments regardless of it being printed or not.

Answer 15

PowerShell, 57 bytes

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

Try it online!

Indices are 1-based.

Answer 16

Haskell, 75 bytes

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

Answer 17

05AB1E, 15 14 bytes

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

Try it online or verify all test cases.

Explanation:

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

The Joins are there because 05AB1E can't determine the indices on multidimensional lists a.f.a.i.k.

---

If outputting the width/height pairs that are truthy, or outputting a list of truthy/falsey values based on the input-list, it could be 8 bytes instead:

ʒ‚ε{ü/}Ë

Try it online or verify all test cases.

ε‚ε{ü/}Ë

Try it online or verify all test cases.

Answer 18

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

Alternative, also 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)

Input is taken as a JSON object, and an array of JSON objects

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