23
\$\begingroup\$

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!)
\$\endgroup\$
11
  • \$\begingroup\$ Is using floating point division allowed? Would [1.0 2.0] be an acceptable input format? \$\endgroup\$
    – Dennis
    Sep 4, 2015 at 0:08
  • \$\begingroup\$ @Dennis Provided your selected language doesn't have oddly low floating point precision and therefore the test cases fail, it should be fine. ;) \$\endgroup\$ Sep 4, 2015 at 0:20
  • \$\begingroup\$ Instead of indices may we also output the actual similar shapes themselves? \$\endgroup\$
    – orlp
    Sep 4, 2015 at 1:36
  • \$\begingroup\$ @orlp Nope!!! :D \$\endgroup\$ Sep 4, 2015 at 2:06
  • 3
    \$\begingroup\$ Is the output format of outputting the indices mandatory? For a test case like [(1,2), (2,4), (1,9), (2,5), (16,8)], is only [0,1,4] and [1,2,5] allowed, or could we also output [1,1,0,0,1] or [(1,2), (2,4), (16,8)]? \$\endgroup\$ Mar 15, 2019 at 14:38

19 Answers 19

11
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ Do you mind explaining this? I'd like to know what's going on. \$\endgroup\$ Sep 4, 2015 at 20:12
  • \$\begingroup\$ @BassetHound for each element in the input list, the comprehension unpacksi as the index, and (x,y) as the point. It then checks if the value x/y is either equal to the initial two numbers' quotient (a/b) or its reciprocal (b/a). If it is equal to one of those values, that value of i is added to the list, otherwise it is discarded. \$\endgroup\$ Sep 4, 2015 at 21:18
9
\$\begingroup\$

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.
\$\endgroup\$
8
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Maybe make h an operator taking three arguments? That'd save one byte, and I think it would stay within the rules. \$\endgroup\$
    – dfeuer
    Mar 14, 2019 at 22:12
  • \$\begingroup\$ @dfeuer Sure, it's definitely allowed by modern standards though back it was fuzzier what liberties could be taken with I/O. \$\endgroup\$
    – xnor
    Mar 14, 2019 at 23:50
7
\$\begingroup\$

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

\$\endgroup\$
5
\$\begingroup\$

Pyth, 15 bytes

fqcFS@QTcFSvzUQ
\$\endgroup\$
3
\$\begingroup\$

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}} *)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I just knew Mathematica was going to come up somehow! \$\endgroup\$ Sep 3, 2015 at 23:32
3
\$\begingroup\$

Pyth - 14 bytes

Filters by comparing quotients, then maps indexOf.

xLQfqcFSTcFvzQ

Test Suite.

\$\endgroup\$
5
  • \$\begingroup\$ This doesn't sort the main shape, so it will give the wrong answer when the main shape's first side length is larger. See this test case \$\endgroup\$
    – isaacg
    Sep 5, 2015 at 19:39
  • \$\begingroup\$ @isaacg good point, will fix. \$\endgroup\$
    – Maltysen
    Sep 5, 2015 at 19:40
  • \$\begingroup\$ This fails on inputs with repeated elements, for example 1,2 and [(1, 2), (2, 4), (1, 2)] will give [0, 1, 0] rather than the correct [0, 1, 2]. \$\endgroup\$
    – orlp
    Sep 6, 2015 at 6:26
  • \$\begingroup\$ I want to accept this one, since it is the shortest, but is the problem @orlp mentioned fixed? \$\endgroup\$ Sep 14, 2015 at 16:40
  • 1
    \$\begingroup\$ @kirbyfan64sos No. \$\endgroup\$
    – orlp
    Sep 14, 2015 at 16:43
3
+200
\$\begingroup\$

APL (Dyalog Unicode), 16 13 bytesSBCS

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

=/-×⍥(⌈/)¨⌽

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.

\$\endgroup\$
2
  • \$\begingroup\$ (=.×∘⌽∨=.×)⍤1 \$\endgroup\$
    – ngn
    Apr 12, 2019 at 18:28
  • \$\begingroup\$ Thanks. Will try to inspect that first \$\endgroup\$
    – Ven
    Apr 15, 2019 at 18:23
2
\$\begingroup\$

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]})
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
0
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ Although it's a nice answer, we have to output the indices. So your TIO test case should result in either [0,1,4] or [1,2,5] (not sure if your language is 0- or 1-indexed). It would have been a better challenge imho if all three output-formats are allowed: indices; filter to keep the truthy values; list of truthy/falsey values (like you have now), instead of only allowed indices. \$\endgroup\$ Mar 15, 2019 at 14:36
  • \$\begingroup\$ @KevinCruijssen "You may choose [...] the exact format and order of the output." in APL it's very common practice to store indices as a boolean vector, but you're right, that probably should be clarified. \$\endgroup\$
    – dzaima
    Mar 15, 2019 at 14:40
  • \$\begingroup\$ Well, I read "You may choose whether the indices are 0- or 1-based, as well as the exact format and order of the output." as it can be [0,1,4], [1,2,5], 4\n0\n1, 5 2 1, etc. etc., since it still stated indices. But I've asked OP to clarify (if they response, since it's a 4 year old challenge). In my 05AB1E answer it would mean 14 bytes if the indices are mandatory vs 8 bytes if either of the other two options are allowed. Regardless, I upvoted your answer. :) \$\endgroup\$ Mar 15, 2019 at 14:49
1
\$\begingroup\$

Haskell, 75 bytes

import Data.List
a(x,y)=max x y/min x y
s r=elemIndices(True).map((==a r).a)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 56 bytes \$\endgroup\$
    – dfeuer
    Mar 14, 2019 at 22:05
  • 1
    \$\begingroup\$ 54 bytes \$\endgroup\$
    – dfeuer
    Mar 14, 2019 at 22:30
1
\$\begingroup\$

PowerShell, 57 bytes

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

Try it online!

Indices are 1-based.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You can save more if you use - instead -ne. \$\endgroup\$
    – mazzy
    Mar 14, 2019 at 17:54
0
\$\begingroup\$

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
}
\$\endgroup\$
3
  • \$\begingroup\$ I don't think this works with the second test case. \$\endgroup\$ Sep 3, 2015 at 23:47
  • \$\begingroup\$ @kirbyfan64sos sorry didn't see that part. It's fixed (but I'm sure I can golf it more) \$\endgroup\$
    – DankMemes
    Sep 3, 2015 at 23:53
  • \$\begingroup\$ These are not JSON objects, these are plain javascript objects. JSON is a data transfer format. \$\endgroup\$
    – edc65
    Sep 7, 2015 at 18:46
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Uiua, 10 bytes

⊚↥∩/=⊃×÷⊙⍉

Try it online!

-2 if I can take the second input transposed.

⊚↥∩/=⊃×÷⊙⍉    input: a shape S, a list of shapes M (2d matrix with two columns)
          ⊙⍉    transpose the 2nd input
      ⊃×÷        fork(mul, div): take S and M and give S*M and S/M
                  the operations are done between each item of S and each row of M
   ∩/=            both(reduce by equal): for each of the two matrices,
                  compare the two rows elementwise and give 1 when equal
                  for similar shapes, * gives 1 if in reverse order, / otherwise
  ↥               boolean OR of the two vectors
⊚                vector of indices of ones
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.