Formas parecidas

23

Figuras similares

Dos rectángulos son similares si las proporciones de sus lados son las mismas.

Considere estos dos rectángulos; un rectángulo de 5 líneas de alto y 11 caracteres de ancho:

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

y un rectángulo de 10 líneas de alto y 22 caracteres de ancho:

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

Estas formas son similares porque las proporciones de sus lados son las mismas. Para decirlo formalmente (siendo h el lado más corto w el lado más largo):

h1w1=h2w2

También puedes hacer:

h1h2=w1w2

El reto

Escriba un programa o función que tome un rectángulo "principal" y algunos "otros" rectángulos e imprima cuáles de "otros" son similares a "principal".

La entrada

Una forma y una lista de formas. Cada forma consta de 2 enteros positivos distintos de cero, que denotan el ancho y la altura del rectángulo. Por ejemplo, esto:

(4,2), (3,9)

denota dos rectángulos, un 4x2 y un 3x9. El formato exacto de la entrada puede ser el que desee.

La salida

Los índices de las "otras" formas que son similares a "principal". Puede elegir si los índices están basados ​​en 0 o 1, así como el formato exacto y el orden de la salida.

Programa de muestra

En 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

Muestra de entrada y salida

Entrada:

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

Salida:

set([0, 1])

Entrada:

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

Salida:

set([2])

Victorioso

Este es el código de golf, por lo que gana la presentación más corta.

Notas

  • Esto debería ser evidente, pero las lagunas estándar están prohibidas .
  • No se pueden usar constructores para localizar figuras similares. (¡Ni siquiera sé si eso existe, pero no me sorprendería!)
kirbyfan64sos
fuente
¿Se permite el uso de la división de punto flotante? ¿ [1.0 2.0]Sería un formato de entrada aceptable?
Dennis
@Dennis Siempre que el idioma seleccionado no tenga una precisión de punto flotante extrañamente baja y, por lo tanto, los casos de prueba fallan, debería estar bien. ;)
kirbyfan64sos
En lugar de índices, ¿podemos generar también las formas similares reales?
orlp
@orlp ¡No! : D
kirbyfan64sos
3
¿Es obligatorio el formato de salida de salida de los índices? Para un caso de prueba como [(1,2), (2,4), (1,9), (2,5), (16,8)], es solo [0,1,4]y [1,2,5]permitido, ¿o también podríamos generar [1,1,0,0,1]o [(1,2), (2,4), (16,8)]?
Kevin Cruijssen

Respuestas:

5

Pyth, 15 bytes

fqcFS@QTcFSvzUQ
orlp
fuente
11

Python, 61 bytes

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

Sí, estoy usando 9 caracteres para escribir enumerate. Toma entrada como 1, 2, [(1, 9), (3,6), (2, 5), (16, 8)]. Para Python 2, los valores de entrada deben escribirse como flotantes.

Un char más largo (62) en 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
fuente
¿Te importa explicar esto? Me gustaría saber qué está pasando.
The_Basset_Hound
@BassetHound para cada elemento en la lista de entrada, la comprensión se descomprime icomo índice y (x,y)como punto. Luego verifica si el valor x/yes igual al cociente inicial de dos números ( a/b) o su recíproco ( b/a). Si es igual a uno de esos valores, ese valor de ise agrega a la lista; de lo contrario, se descarta.
FryAmTheEggman
9

CJam, 22 20 19 bytes

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

Lo anterior es una función anónima que saca una matriz única de pares de coma flotante (el primer par es una aguja) de la pila y empuja la matriz de índices basados ​​en 1 a cambio.

Pruébelo en línea en intérprete de CJam .

Cómo funciona

:$                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
fuente
8

Haskell , 48 bytes

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

Pruébalo en línea!

Llama a esto como (!) 1 2 [(1, 9), (3,6), (2, 5), (16, 8)] .

Una respuesta cercana a mi puerto de Python . La expresión zip[0..]lenumera la lista con sus índices.

La expresión x/y+y/x==a/b+b/averifica que la relación x/ysea a/bo b/a, ya que la función f(z) = z + 1/ztiene f(z) = f(1/z)y ninguna otra colisión.

xnor
fuente
¿Quizás hacer que hun operador tome tres argumentos? Eso ahorraría un byte, y creo que se mantendría dentro de las reglas.
dfeuer
@dfeuer Claro, definitivamente está permitido por los estándares modernos, aunque atrás era más confuso qué libertades se podían tomar con E / S.
Xnor
7

Muñeco de nieve 1.0.2 , 61 caracteres

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

Puro galimatías (a menos que conozcas a Snowman), también conocido exactamente en línea con el objetivo de diseño del lenguaje de de ser lo más confuso posible.

El formato de entrada es el mismo que en la publicación, el formato de salida también es el mismo menos set(y) .

Sin golf (o sin minar, de verdad):

}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

Estoy bastante orgulloso de algunos de los trucos que utilicé en este:

  • Usé el mismo formato de entrada que en la publicación. Pero en lugar de intentar analizarlo de alguna manera, lo que se volvería realmente desordenado, simplemente concatenaba las dos líneas y luego usaba una expresión regular para extraer todos los números en una gran matriz (con lo que luego hice2aG , es decir, cada grupo de 2).

  • :nD;aFEs muy elegante. Simplemente toma una matriz de dos elementos y divide el primero por el segundo. Lo que parece bastante simple, pero hacerlo de forma intuitiva ( a[0]/a[1]) sería mucho, mucho más tiempo en Snowman: 0aa`NiN`aA|,nD(y eso es asumiendo que no tenemos que preocuparnos de jugar con otras variables existentes). En cambio, utilicé el método "fold" con un predicado de "divide", que, para una matriz de dos elementos, logra lo mismo.

  • 0AAgaAse ve lo suficientemente inocuo, pero lo que realmente hace es almacenar un 0a las variables, luego toma todas las variables con un índice mayor que eso (entonces, todas las variables excepto la primera). Pero el truco es que, en lugar de AaG(que eliminaría la matriz original y la 0), utilicé AAg, lo que mantiene ambos. Ahora uso aA, at-index, usando lo mismo0 para obtener el primer elemento de la matriz; además, esto está en modo consumo (en aAlugar de aa), por lo que también elimina la 0matriz original y, que ahora son basura para nosotros.

    Por desgracia, 0AAgaA*|lo hace esencialmente lo mismo que GolfScript hace en un personaje: (. Sin embargo, todavía creo que es bastante agradable, para los estándares de Snowman. :)

Pomo de la puerta
fuente
3

Mathematica, 41 bytes

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

Uso:

Position[a = Sort@#; Sort@#/a & /@ #2, {x_, x_}] &[{1, 2}, {{1, 2}, {2, 5}, {16, 8}}]
(* {{1}, {3}} *)
Martin Ender
fuente
1
¡ Sabía que Mathematica iba a aparecer de alguna manera!
kirbyfan64sos
3

Pyth - 14 bytes

Filtra comparando cocientes, luego mapas indexOf.

xLQfqcFSTcFvzQ

Test Suite .

Maltysen
fuente
Esto no ordena la forma principal, por lo que dará la respuesta incorrecta cuando la longitud del primer lado de la forma principal sea mayor. Vea este caso de prueba
isaacg el
@isaacg buen punto, lo arreglará.
Maltysen
Esto falla en entradas con elementos repetidos, por ejemplo, 1,2y [(1, 2), (2, 4), (1, 2)]dará en [0, 1, 0]lugar de lo correcto [0, 1, 2].
orlp
Quiero aceptar este, ya que es el más corto, pero ¿está solucionado el problema que mencionó @orlp?
kirbyfan64sos
1
@ kirbyfan64sos No.
orlp
3

APL (Dyalog Unicode) , 16 13 bytes SBCS

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

Pruébalo en línea!

-3 gracias a @ngn!

Explicación:

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

El formato de salida es un vector binario 1 1 0 0 1del cual "otro" rectángulo es similar.

APL (Dyalog Extended) , SBCS de 11 bytes

=/-×⍥(⌈/)¨⌽

Pruébalo en línea!

Explicación:

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

El formato de salida es el mismo que la respuesta principal de Dyalog.

Gracias a Adám por la ayuda de golf + extendido.

Ven
fuente
(=.×∘⌽∨=.×)⍤1
ngn
Gracias. Intentará inspeccionar eso primero
Ven
2

Julia, 62 bytes

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

La findfunción localiza elementos verdaderos en un vector booleano. .*realiza la multiplicación por elementos de vectores.

Sin golf:

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

Uso:

f([1,2], {[1,9], [2,5], [16,8]})
Alex A.
fuente
2

K5, 19 bytes

Creo que esto hará el truco:

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

Toma una lista de pares donde el primero es el "principal". Calcula la razón dividiendo las dimensiones ordenadas de cada par. Devuelve una lista de las posiciones indexadas en 0 de los pares coincidentes. (podría decirse que el formato de entrada que elegí hace que este -1 esté indexado, si esto se considera una tachuela no válida en un1+ al principio y agrega dos caracteres al tamaño de mi programa).

Ejemplo de uso:

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

Esto se ejecuta en OK ; tenga en cuenta que implícitamente dependo de que la división siempre produzca resultados de coma flotante. Funcionaría en Kona si agrega un punto decimal a todos los números en la entrada y agrega un espacio después de _.

JohnE
fuente
2

Octava / Matlab, 44 bytes

Usando una función anónima:

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

El resultado está en indexación basada en 1.

Para usarlo, defina la función

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

y llámalo con el siguiente formato

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

Puedes probarlo en línea .


Si el resultado puede estar en indexación lógica ( 0indica que no es similar, 1indica que es similar): 38 bytes :

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

Mismo ejemplo que el anterior:

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

Brachylog , 14 bytes

z{iXhpᵐ/ᵛ∧Xt}ᵘ

Pruébalo en línea!

Toma la entrada como una lista que contiene una lista que contiene el rectángulo principal y la lista de otros rectángulos (así es el caso de prueba 1 [[[1,2]],[[1,2],[2,4]]]), y genera una lista de índices basados ​​en 0 a través de la variable de salida.

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.

Si ese tipo de formato de entrada extraño y específico es trampa, es un poco más largo ...

Brachylog , 18 bytes

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

Pruébalo en línea!

Toma la entrada como una lista que contiene el rectángulo principal y la lista de otros rectángulos (por lo que el caso de prueba 1 es el más obvio [[1,2],[[1,2],[2,4]]]), y genera una lista de índices basados ​​en 0 a través de la variable de salida.

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

Para determinar si dos pares de ancho y alto representan rectángulos similares, solo toma los cuatro bytes pᵐ/ᵛ(que genera la relación compartida o su recíproco). Todo lo demás es manejar los múltiples rectángulos para comparar, y la salida son índices.

Cadena no relacionada
fuente
2

dzaima / APL , 7 bytes

=/⍤÷⍥>¨

Pruébalo en línea!

8 bytes que generan una lista de índices en lugar de un vector booleano

      ¨ 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
fuente
Aunque es una buena respuesta, tenemos que generar los índices. Por lo tanto, su caso de prueba de TIO debería resultar en uno [0,1,4]o [1,2,5](no estoy seguro si su idioma es 0 o 1 indexado). Hubiera sido un desafío mejor para mi si los tres formatos de salida están permitidos: índices; filtrar para mantener los valores de verdad; lista de valores de verdad / falsey (como ahora), en lugar de solo índices permitidos.
Kevin Cruijssen
@KevinCruijssen "Puede elegir [...] el formato y el orden exactos de la salida". en APL es una práctica muy común almacenar índices como un vector booleano, pero tienes razón, eso probablemente debería aclararse.
dzaima
Bueno, leí " Usted puede elegir si los índices son 0- o 1-basado, así como el formato exacto y el orden de la salida. " Ya que puede ser [0,1,4], [1,2,5], 4\n0\n1, 5 2 1, etc, etc, ya que todavía declaró índices . Pero le he pedido a OP que aclare (si responden, ya que es un desafío de 4 años). En mi respuesta 05AB1E significaría 14 bytes si los índices son obligatorios frente a 8 bytes si se permite alguna de las otras dos opciones. De todos modos, voté tu respuesta. :)
Kevin Cruijssen
1

Haskell, 75 bytes

import Data.List
a(x,y)=max x y/min x y
s r=elemIndices(True).map((==a r).a)
Leif Willerts
fuente
56 bytes
dfeuer
54 bytes
dfeuer
1

Potencia Shell , 58 56 bytes

-2 bytes gracias a mazzy x2

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

Pruébalo en línea!

Esto abusa ligeramente de input may be however you desire cláusula al hacer que los componentes de la primera forma vengan por separado para guardar 3 bytes.

PowerShell , 61 59 bytes

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

Pruébalo en línea!

Utiliza la indexación condicional para intercambiar entre el índice actual basado en cero y nulo en función de si las relaciones se alinean o no. Afortunadamente en este caso, $iaumenta independientemente de si se imprime o no.

Veskah
fuente
1
Puede ahorrar más si usa -en su lugar -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))

Alternativa, también 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)

La entrada se toma como un objeto JSON y una matriz de objetos JSON

{
    l: length of rectangle,
    h: height of rectangle
}
DankMemes
fuente
No creo que esto funcione con el segundo caso de prueba.
kirbyfan64sos
@ Kirbyfan64sos lo siento, no vi esa parte. Está solucionado (pero estoy seguro de que puedo jugar más)
DankMemes
Estos no son objetos JSON, son objetos javascript simples. JSON es un formato de transferencia de datos.
edc65
0

05AB1E , 15 14 bytes

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

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

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

Los Joins están ahí porque 05AB1E no puede determinar los índices en listas multidimensionales afaik


Si genera los pares de ancho / alto que son verdaderos, o genera una lista de valores de verdad / falsey basados ​​en la lista de entrada, podría ser 8 bytes en su lugar:

ʒ‚ε{ü/}Ë

Pruébelo en línea o verifique todos los casos de prueba .

ε‚ε{ü/}Ë

Pruébalo en línea o verifique todos los casos de prueba .

Kevin Cruijssen
fuente