Formas parecidas

23

Figuras semelhantes

Dois retângulos são semelhantes se as proporções dos lados forem iguais.

Considere estes dois retângulos; um retângulo com 5 linhas de altura e 11 caracteres de largura:

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

e um retângulo com 10 linhas de altura e 22 caracteres de largura:

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

Essas formas são semelhantes porque as proporções de seus lados são as mesmas. Para colocá-lo formalmente (com h sendo o lado mais curto W sendo o lado mais longo):

h1W1=h2W2

Você também pode fazer:

h1h2=W1W2

O desafio

Escreva um programa ou função que use um retângulo "principal" e alguns "outros" retângulos e imprima quais de "outros" são semelhantes a "principal".

A entrada

Uma forma e uma lista de formas. Cada forma consiste em 2 números inteiros positivos diferentes de zero, que indicam a largura e a altura do retângulo. Por exemplo, isto:

(4,2), (3,9)

denota dois retângulos, um 4x2 e um 3x9. O formato exato da entrada pode ser o que você desejar.

A saída

Os índices das "outras" formas que são semelhantes a "principal". Você pode escolher se os índices são baseados em 0 ou 1, bem como o formato e a ordem exatos da saída.

Programa de exemplo

Em 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

Entrada e saída de amostra

Entrada:

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

Saída:

set([0, 1])

Entrada:

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

Saída:

set([2])

Ganhando

Isso é código-golfe, então a submissão mais curta vence.

Notas

  • Isso deve ser óbvio, mas as brechas padrão são proibidas .
  • Nenhum componente interno para localizar figuras semelhantes pode ser usado. (Eu nem sei se isso existe, mas não ficaria surpreso!)
kirbyfan64sos
fonte
É permitida a divisão de ponto flutuante? Seria [1.0 2.0]um formato de entrada aceitável?
Dennis
@Dennis Desde que o seu idioma selecionado não tenha uma precisão de ponto flutuante estranhamente baixa e, portanto, os casos de teste falhem, tudo ficará bem. ;)
kirbyfan64sos
Em vez de índices, podemos também produzir as formas similares reais?
orlp 4/09/15
@orlp Nope !!! : D
kirbyfan64sos
3
O formato de saída dos índices é obrigatório? Para um caso de teste como [(1,2), (2,4), (1,9), (2,5), (16,8)], é apenas [0,1,4]e [1,2,5]permitido, ou poderíamos também produzir [1,1,0,0,1]ou [(1,2), (2,4), (16,8)]?
Kevin Cruijssen 15/03

Respostas:

5

Pitão, 15 bytes

fqcFS@QTcFSvzUQ
orlp
fonte
11

Python, 61 bytes

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

Sim, estou gastando 9 caracteres para escrever enumerate. Toma entrada como 1, 2, [(1, 9), (3,6), (2, 5), (16, 8)]. Para o Python 2, os valores de entrada precisam ser escritos como flutuadores.

Um caractere a mais (62) no 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
fonte
Você se importa de explicar isso? Eu gostaria de saber o que está acontecendo.
The_Basset_Hound
@BassetHound para cada elemento da lista de entrada, a compreensão é descompactada icomo índice e (x,y)como ponto. Em seguida, verifica se o valor x/yé igual ao quociente dos dois números iniciais ( a/b) ou recíproco ( b/a). Se for igual a um desses valores, esse valor iserá adicionado à lista, caso contrário, será descartado.
FryAmTheEggman # 4/15
9

CJam, 22 20 19 bytes

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

A descrição acima é uma função anônima que exibe uma única matriz de pares de ponto flutuante (o primeiro par é agulha) da pilha e empurra a matriz de índices baseados em 1 em troca.

Experimente online no intérprete CJam .

Como 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
fonte
8

Haskell , 48 bytes

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

Experimente online!

Chame isso como (!) 1 2 [(1, 9), (3,6), (2, 5), (16, 8)].

Uma porta próxima da minha resposta Python . A expressão zip[0..]lenumera a lista com seus índices.

A expressão x/y+y/x==a/b+b/averifica se a proporção x/yé a/bou b/a, uma vez que a função f(z) = z + 1/ztem f(z) = f(1/z)e não outras colisões.

xnor
fonte
Talvez faça hum operador usando três argumentos? Isso economizaria um byte e acho que permaneceria dentro das regras.
dfeuer 14/03
@dfeuer Certamente, é definitivamente permitido pelos padrões modernos, apesar de voltar a ser mais confuso quais liberdades poderiam ser tomadas com a E / S.
xnor 14/03
7

Boneco de neve 1.0.2 , 61 caracteres

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

Linguagem pura (a menos que você conheça o Snowman), ou seja, exatamente de acordo com o objetivo de design da linguagem de ser o mais confuso possível.

O formato de entrada é o mesmo da postagem, o formato de saída também é o mesmo menos set(e ).

Ungolfed (ou unminified, realmente):

}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

Estou muito orgulhoso de alguns dos truques que usei neste:

  • Usei o mesmo formato de entrada do post. Mas, em vez de tentar analisá-lo de alguma forma, o que seria realmente confuso, eu apenas concatenou as duas linhas e, em seguida, usei um regex para extrair todos os números em uma grande matriz (com a qual eu fiz 2aG, ou seja, obter todos os grupos de 2).

  • :nD;aFé bem chique. Ele simplesmente pega uma matriz de dois elementos e divide o primeiro pelo segundo. O que parece bastante simples, mas fazê-lo da maneira intuitiva ( a[0]/a[1]) seria muito, muito mais longo no Snowman: 0aa`NiN`aA|,nD(e isso pressupõe que não precisamos nos preocupar em mexer com outras variáveis ​​existentes). Em vez disso, usei o método "fold" com um predicado de "divide", que, para uma matriz de dois elementos, alcança a mesma coisa.

  • 0AAgaAparece bastante inócuo, mas o que realmente faz é armazenar 0a nas variáveis ​​e, em seguida, leva todas as variáveis ​​com um índice maior que isso (portanto, todas as variáveis, exceto a primeira). Mas o truque é que, em vez de AaG(que se livraria da matriz original e da 0), eu usei AAg, que mantém as duas. Agora eu uso aAat-index, usando o mesmo0 para obter o primeiro elemento da matriz - além disso, ele está no modo de consumo (em aAvez de aa), para que ela se livre da 0matriz original e também, que agora são lixo para nos.

    Infelizmente, 0AAgaA*|faz essencialmente a mesma coisa que GolfScript faz em um personagem: (. No entanto, eu ainda acho que é muito bom, para os padrões do Snowman. :)

Maçaneta da porta
fonte
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
fonte
1
Eu só sabia que o Mathematica iria aparecer de alguma forma!
Kirbyfan64sos #
3

Pitão - 14 bytes

Filtra comparando quocientes e depois mapeia indexOf.

xLQfqcFSTcFvzQ

Conjunto de Teste .

Maltysen
fonte
Isso não classifica a forma principal e, portanto, fornecerá a resposta errada quando o comprimento do primeiro lado da forma principal for maior. Veja este caso de teste
isaacg 5/15/15
@isaacg bom ponto, vai corrigir.
Maltysen 5/09/15
Isso falha nas entradas com elementos repetidos, por exemplo, 1,2e [(1, 2), (2, 4), (1, 2)]dará [0, 1, 0]mais do que o correto [0, 1, 2].
orlp 6/09/15
Quero aceitar esse, pois é o mais curto, mas o problema @orlp mencionado foi corrigido?
Kirbyfan64sos
1
@ kirbyfan64sos No.
orlp
3

APL (Dyalog Unicode) , 16 13 bytes SBCS

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

Experimente online!

-3 graças a @ngn!

Explicação:

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

O formato de saída é um vetor binário como o 1 1 0 0 1qual "outro" retângulo é semelhante.

APL (Dyalog Extended) , 11 bytes SBCS

=/-×⍥(⌈/)¨⌽

Experimente online!

Explicação:

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

O formato de saída é igual à resposta principal do Dyalog.

Agradecimentos a Adám pela ajuda no golfe + Extended.

Ven
fonte
(=.×∘⌽∨=.×)⍤1
ngn 12/04
Obrigado. Vai tentar inspecionar esse primeiro
Ven
2

Julia, 62 bytes

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

A findfunção localiza elementos verdadeiros em um vetor booleano. .*executa multiplicação elementar de vetores.

Ungolfed:

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.
fonte
2

K5, 19 bytes

Eu acho que isso vai fazer o truque:

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

Leva uma lista de pares onde o primeiro é o "principal". Calcula a proporção, dividindo as dimensões classificadas de cada par. Retorna uma lista das posições indexadas em 0 dos pares correspondentes. (indiscutivelmente, o formato de entrada que escolhi torna este -1 indexado - se isso for considerado uma aderência inválida 1+a no início e adicionar dois caracteres ao tamanho do meu programa.)

Exemplo de uso:

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

Isso funciona em OK - note que eu implicitamente dependo da divisão sempre produzindo resultados de ponto flutuante. Funcionaria em Kona se você adicionasse um ponto decimal a todos os números na entrada e adicionasse um espaço após o _.

JohnE
fonte
2

Oitava / Matlab, 44 bytes

Usando uma função anônima:

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

O resultado está na indexação baseada em 1.

Para usá-lo, defina a função

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

e chame-o com o seguinte formato

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

Você pode experimentá-lo online .


Se o resultado puder estar na indexação lógica ( 0indica não semelhante, 1indica similar): 38 bytes :

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

Mesmo exemplo que acima:

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

Braquilog , 14 bytes

z{iXhpᵐ/ᵛ∧Xt}ᵘ

Experimente online!

Recebe a entrada como uma lista que contém uma lista que contém o retângulo principal e a lista de outros retângulos (como é o caso de teste 1 [[[1,2]],[[1,2],[2,4]]]) e gera uma lista de índices baseados em 0 através da variável de saída.

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.

Se esse tipo de formatação de entrada ímpar e específica está trapaceando, é um pouco mais longo ...

Braquilog , 18 bytes

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

Experimente online!

Recebe a entrada como uma lista que contém o retângulo principal e a lista de outros retângulos (para que o caso de teste 1 seja o mais óbvio [[1,2],[[1,2],[2,4]]]) e gera uma lista de índices baseados em 0 através da variável de saída.

{               }ᵘ    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 se dois pares largura-altura representam retângulos semelhantes, são necessários apenas quatro bytes pᵐ/ᵛ(que gera a taxa compartilhada ou sua recíproca). Todo o resto está lidando com os vários retângulos a serem comparados e a saída sendo índices.

String não relacionada
fonte
2

dzaima / APL , 7 bytes

=/⍤÷⍥>¨

Experimente online!

8 bytes emitindo uma lista de índices em vez de um vetor 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
fonte
Embora seja uma boa resposta, temos que gerar os índices. Portanto, seu caso de teste de TIO deve resultar em um [0,1,4]ou [1,2,5](não tenho certeza se o seu idioma é indexado em 0 ou 1). Teria sido um desafio melhor se todos os três formatos de saída fossem permitidos: índices; filtro para manter os valores de verdade; lista de valores truthy / falsey (como você tem agora), em vez de apenas índices permitidos.
Kevin Cruijssen 15/03
@KevinCruijssen "Você pode escolher [...] o formato exato e a ordem da saída." no APL, é uma prática muito comum armazenar índices como um vetor booleano, mas você está certo, isso provavelmente deve ser esclarecido.
dzaima 15/03
Bem, eu li " Você pode escolher se os índices são 0- ou 1-baseado, assim como o formato exato e fim da saída. " Pois ele pode ser [0,1,4], [1,2,5], 4\n0\n1, 5 2 1, etc., etc., uma vez que ainda afirmou índices . Mas pedi ao OP para esclarecer (se eles responderem, já que é um desafio de 4 anos). Na minha resposta 05AB1E, significaria 14 bytes se os índices forem obrigatórios vs 8 bytes, se uma das outras duas opções for permitida. Independentemente disso, votei na sua resposta. :)
Kevin Cruijssen 15/03
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
fonte
56 bytes
dfeuer 14/03
54 bytes
dfeuer 14/03
1

PowerShell , 58 56 bytes

-2 bytes graças ao mazzy x2

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

Experimente online!

Isso abusa um pouco da input may be however you desire cláusula ao fazer com que os componentes da primeira forma sejam separados separadamente para salvar 3 bytes.

PowerShell , 61 59 bytes

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

Experimente online!

Usa a indexação condicional para alternar entre o índice atual baseado em zero e o nulo, com base na alinhação ou não das proporções. Felizmente, neste caso, é $iincrementado independentemente de sua impressão ou não.

Veskah
fonte
1
Você pode economizar mais se você usar -vez -ne.
mazzy 14/03
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, também 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)

A entrada é tomada como um objeto JSON e uma matriz de objetos JSON

{
    l: length of rectangle,
    h: height of rectangle
}
DankMemes
fonte
Eu não acho que isso funcione com o segundo caso de teste.
Kirbyfan64sos # 03/09/2015
@ kirbyfan64sos sorry não viu essa parte. É fixo (mas eu tenho certeza que posso jogar mais)
DankMemes 3/15
Esses não são objetos JSON, são objetos javascript simples. JSON é um formato de transferência de dados.
Edc65 7/09/15
0

05AB1E , 15 14 bytes

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

Experimente online ou verifique todos os casos de teste .

Explicação:

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

o J entradas estão lá porque 05AB1E não pode determinar os índices nas listas multidimensionais


Se estiver produzindo os pares largura / altura que são verdadeiros ou se estiver produzindo uma lista de valores de verdade / falsey com base na lista de entrada, pode haver 8 bytes :

ʒ‚ε{ü/}Ë

Experimente online ou verifique todos os casos de teste .

ε‚ε{ü/}Ë

Experimente online ou verifique todos os casos de teste .

Kevin Cruijssen
fonte