Formes similaires

23

Chiffres similaires

Deux rectangles sont similaires si les rapports de leurs côtés sont identiques.

Considérez ces deux rectangles; un rectangle de 5 lignes de haut et 11 caractères de large:

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

et un rectangle de 10 lignes de haut et 22 caractères de large:

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

Ces formes sont similaires car les rapports de leurs côtés sont les mêmes. Pour le dire formellement ( étant le côté le plus court et étant le côté le plus long):hw

h1w1=h2w2

Vous pouvez également faire:

h1h2=w1w2

Le défi

Écrivez un programme ou une fonction qui prend un rectangle "principal" et quelques "autres" rectangles et imprime ceux des "autres" qui sont similaires à "principaux".

L'entrée

Une forme et une liste de formes. Chaque forme se compose de 2 entiers positifs non nuls, qui indiquent la largeur et la hauteur du rectangle. Par exemple, ceci:

(4,2), (3,9)

désigne deux rectangles, un 4x2 et un 3x9. Le format exact de l'entrée peut être celui que vous désirez.

Le résultat

Les indices des «autres» formes qui sont similaires à «principales». Vous pouvez choisir si les indices sont basés sur 0 ou 1, ainsi que le format et l'ordre exacts de la sortie.

Exemple de programme

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

Exemple d'entrée et de sortie

Contribution:

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

Sortie:

set([0, 1])

Contribution:

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

Sortie:

set([2])

Gagnant

Il s'agit de code-golf, donc la soumission la plus courte l'emporte.

Remarques

  • Cela va sans dire, mais les failles standard sont interdites .
  • Aucun élément intégré pour localiser des figures similaires ne peut être utilisé. (Je ne sais même pas si cela existe, mais je ne serais pas surpris!)
kirbyfan64sos
la source
L'utilisation de la division en virgule flottante est-elle autorisée? Serait [1.0 2.0]un format d'entrée acceptable?
Dennis
@Dennis À condition que votre langue sélectionnée n'ait pas une précision en virgule flottante étrangement faible et que, par conséquent, les cas de test échouent, cela devrait aller. ;)
kirbyfan64sos
Au lieu d'indices, pouvons-nous également produire les formes similaires réelles elles-mêmes?
orlp
@orlp Nope !!! : D
kirbyfan64sos
3
Le format de sortie de la sortie des indices est-il obligatoire? Pour un cas de test comme [(1,2), (2,4), (1,9), (2,5), (16,8)], est seulement [0,1,4]et [1,2,5]autorisé, ou pourrions-nous également produire [1,1,0,0,1]ou [(1,2), (2,4), (16,8)]?
Kevin Cruijssen

Réponses:

5

Pyth, 15 octets

fqcFS@QTcFSvzUQ
orlp
la source
11

Python, 61 octets

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

Oui, j'utilise 9 caractères pour écrire enumerate. Prend l'entrée comme 1, 2, [(1, 9), (3,6), (2, 5), (16, 8)]. Pour Python 2, les valeurs d'entrée doivent être écrites sous forme de flottants.

Un caractère plus long (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
la source
Ça vous dérange d'expliquer cela? J'aimerais savoir ce qui se passe.
The_Basset_Hound
@BassetHound pour chaque élément de la liste d'entrée, la compréhension décompresse icomme index et (x,y)comme point. Il vérifie ensuite si la valeur x/yest égale au quotient ( a/b) des deux nombres initiaux ou à sa réciproque ( b/a). S'il est égal à l'une de ces valeurs, cette valeur de iest ajoutée à la liste, sinon elle est supprimée.
FryAmTheEggman
9

CJam, 22 20 19 octets

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

Ce qui précède est une fonction anonyme qui extrait un seul tableau de paires à virgule flottante (la première paire est aiguille) de la pile et pousse le tableau d'index basés sur 1 en retour.

Essayez-le en ligne dans l' interpréteur CJam .

Comment ça marche

:$                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
la source
8

Haskell , 48 octets

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

Essayez-le en ligne!

Appelez ça comme (!) 1 2 [(1, 9), (3,6), (2, 5), (16, 8)].

Un port proche de ma réponse Python . L'expression zip[0..]lénumère la liste avec ses indices.

L'expression x/y+y/x==a/b+b/avérifie que le rapport x/yest soit a/bou b/a, puisque la fonction f(z) = z + 1/za f(z) = f(1/z)et aucune autre collision.

xnor
la source
Peut-être faire hun opérateur prenant trois arguments? Cela économiserait un octet, et je pense que cela resterait dans les règles.
dfeuer
@dfeuer Bien sûr, c'est définitivement autorisé par les normes modernes, mais en arrière, il était plus flou quelles libertés pouvaient être prises avec les E / S.
xnor
7

Snowman 1.0.2 , 61 caractères

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

Du charabia pur (à moins que vous ne connaissiez Snowman), c'est-à-dire exactement conforme à l'objectif de conception du langage d'être aussi déroutant que possible.

Le format d'entrée est le même que dans la publication, le format de sortie est également le même moins set(et ).

Non golfé (ou non minimisé, vraiment):

}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

Je suis assez fier de certaines des astuces que j'ai utilisées dans celui-ci:

  • J'ai utilisé le même format d'entrée que dans le post. Mais au lieu d'essayer de l'analyser d'une manière ou d'une autre, ce qui deviendrait vraiment compliqué, j'ai simplement enchaîné les deux lignes et ensuite utilisé une expression régulière pour extraire tous les nombres dans un grand tableau (avec lequel j'ai ensuite fait 2aG, c'est-à-dire obtenir chaque groupe de 2).

  • :nD;aFest assez chic. Il prend simplement un tableau de deux éléments et divise le premier par le second. Ce qui semble assez simple, mais le faire de manière intuitive ( a[0]/a[1]) serait beaucoup, beaucoup plus long dans Snowman: 0aa`NiN`aA|,nD(et c'est en supposant que nous n'avons pas à nous soucier de jouer avec d'autres variables existantes). Au lieu de cela, j'ai utilisé la méthode "fold" avec un prédicat de "divide" qui, pour un tableau de deux éléments, réalise la même chose.

  • 0AAgaAsemble assez inoffensif, mais ce qu'il fait réellement est de stocker un 0dans les variables, puis prend toutes les variables avec un indice supérieur à celui (donc, toutes les variables sauf la première). Mais l'astuce est, au lieu de AaG(ce qui éliminerait le tableau d'origine et le 0), j'ai utilisé AAg, ce qui garde les deux. Maintenant aA, j'utilise , at-index, en utilisant la même chose0 pour obtenir le premier élément du tableau - en outre, c'est en mode consommation ( aAau lieu de aa), donc il se débarrasse du 0tableau d'origine et aussi, qui sont maintenant des ordures pour nous.

    Hélas, 0AAgaA*|fait essentiellement la même chose que GolfScript fait dans un seul caractère: (. Cependant, je pense toujours que c'est plutôt sympa, selon les normes de Snowman. :)

Poignée de porte
la source
3

Mathematica, 41 octets

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}} *)
Martin Ender
la source
1
Je savais juste que Mathematica allait arriver d'une manière ou d'une autre!
kirbyfan64sos
3

Pyth - 14 octets

Filtre en comparant les quotients, puis mappe indexOf.

xLQfqcFSTcFvzQ

Suite de tests .

Maltysen
la source
Cela ne trie pas la forme principale, donc cela donnera la mauvaise réponse lorsque la longueur du premier côté de la forme principale est plus grande. Voir ce
scénario de
@isaacg bon point, corrigera.
Maltysen
Cela échoue sur les entrées avec des éléments répétés, par exemple 1,2et [(1, 2), (2, 4), (1, 2)]donnera [0, 1, 0]plutôt que le correct [0, 1, 2].
orlp
Je veux accepter celui-ci, car il est le plus court, mais le problème mentionné @orlp est-il résolu?
kirbyfan64sos
1
@ kirbyfan64sos No.
orlp
3

APL (Dyalog Unicode) , 16 13 octets SBCS

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

Essayez-le en ligne!

-3 grâce à @ngn!

Explication:

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

Le format de sortie est un vecteur binaire comme celui 1 1 0 0 1dont "l'autre" rectangle est une ressemblance.

APL (Dyalog Extended) , 11 octets SBCS

=/-×⍥(⌈/)¨⌽

Essayez-le en ligne!

Explication:

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

Le format de sortie est le même que la réponse Dyalog principale.

Merci à Adám pour l'aide golf + Extended.

Ven
la source
(=.×∘⌽∨=.×)⍤1
ngn
Merci. J'essaierai d'inspecter cela en premier
Ven
2

Julia, 62 octets

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

La findfonction localise les vrais éléments dans un vecteur booléen. .*effectue la multiplication par élément des vecteurs.

Non golfé:

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]})
Alex A.
la source
2

K5, 19 octets

Je pense que cela fera l'affaire:

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

Prend une liste de paires où le premier est le "principal". Calcule le rapport en divisant les dimensions triées de chaque paire. Renvoie une liste des positions indexées 0 des paires correspondantes. (sans doute le format d'entrée que j'ai choisi rend ce -1 indexé- si cela est considéré comme un point non valide sur un 1+au début et ajoutez deux caractères à la taille de mon programme.)

Exemple d'utilisation:

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

Cela fonctionne en oK - notez que je dépend implicitement de la division produisant toujours des résultats en virgule flottante. Cela fonctionnerait dans Kona si vous ajoutiez un point décimal à tous les nombres dans l'entrée et ajoutiez un espace après le _.

JohnE
la source
2

Octave / Matlab, 44 octets

Utilisation d'une fonction anonyme:

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

Le résultat est une indexation basée sur 1.

Pour l'utiliser, définissez la fonction

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

et appelez-le au format suivant

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

Vous pouvez l' essayer en ligne .


Si le résultat peut être dans l'indexation logique ( 0indique pas similaire, 1indique similaire): 38 octets :

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

Même exemple que ci-dessus:

>> @(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
la source
2

Brachylog , 14 octets

z{iXhpᵐ/ᵛ∧Xt}ᵘ

Essayez-le en ligne!

Prend l'entrée comme une liste contenant une liste contenant le rectangle principal et la liste des autres rectangles (donc le cas de test 1 l'est [[[1,2]],[[1,2],[2,4]]]), et génère une liste d'index basés sur 0 via la variable de sortie.

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 ce type de formatage étrange et spécifique triche, c'est un peu plus long ...

Brachylog , 18 octets

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

Essayez-le en ligne!

Prend l'entrée comme une liste contenant le rectangle principal et la liste des autres rectangles (donc le cas de test 1 est le plus évident [[1,2],[[1,2],[2,4]]]), et génère une liste d'index basés sur 0 via la variable de sortie.

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

Pour déterminer si deux paires largeur-hauteur représentent des rectangles similaires, il suffit de prendre les quatre octets pᵐ/ᵛ(qui produisent le rapport partagé ou sa réciproque). Tout le reste gère les multiples rectangles à comparer, et la sortie étant des indices.

Chaîne indépendante
la source
2

dzaima / APL , 7 octets

=/⍤÷⍥>¨

Essayez-le en ligne!

8 octets produisant une liste d'index au lieu d'un vecteur booléen

      ¨ 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
la source
Bien que ce soit une bonne réponse, nous devons produire les indices. Ainsi, votre cas de test TIO devrait aboutir à [0,1,4]ou [1,2,5](vous ne savez pas si votre langue est indexée 0 ou 1). Cela aurait été un meilleur défi à mon humble avis si les trois formats de sortie étaient autorisés: les indices; filtre pour garder les valeurs véridiques; liste des valeurs truey / falsey (comme vous l'avez maintenant), au lieu des seuls indices autorisés.
Kevin Cruijssen
@KevinCruijssen "Vous pouvez choisir [...] le format et l'ordre exacts de la sortie." dans APL, il est très courant de stocker des indices en tant que vecteur booléen, mais vous avez raison, cela devrait probablement être clarifié.
dzaima
Eh bien, je lis " Vous pouvez choisir si les indices sont basés sur 0 ou 1, ainsi que le format et l'ordre exacts de la sortie. " Comme cela peut être [0,1,4],[1,2,5] , 4\n0\n1, 5 2 1, etc. , etc., car il encore déclaré indices . Mais j'ai demandé à OP de clarifier (s'ils répondent, car c'est un défi de 4 ans). Dans ma réponse 05AB1E, cela signifierait 14 octets si les indices sont obligatoires contre 8 octets si l'une des deux autres options est autorisée. Quoi qu'il en soit, j'ai voté pour votre réponse. :)
Kevin Cruijssen
1

Haskell, 75 octets

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

PowerShell , 58 56 octets

-2 octets grâce à mazzy x2

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

Essayez-le en ligne!

Cela abuse légèrement de la input may be however you desire clause en faisant venir séparément les composants de la première forme pour économiser 3 octets.

PowerShell , 61 59 octets

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

Essayez-le en ligne!

Utilise l'indexation conditionnelle pour permuter entre l'index de base zéro actuel et null selon que les ratios sont alignés ou non. Heureusement dans ce cas, $iincrémente indépendamment du fait qu'il soit imprimé ou non.

Veskah
la source
1
Vous pouvez économiser plus si vous utilisez à la -place -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))

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

L'entrée est considérée comme un objet JSON et un tableau d'objets JSON

{
    l: length of rectangle,
    h: height of rectangle
}
DankMemes
la source
Je ne pense pas que cela fonctionne avec le deuxième cas de test.
kirbyfan64sos
@ kirbyfan64sos désolé n'a pas vu cette partie. Il est fixe (mais je suis sûr que je peux
jouer au
Ce ne sont pas des objets JSON, ce sont des objets javascript simples. JSON est un format de transfert de données.
edc65
0

05AB1E , 15 14 octets

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

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

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

Les Joins sont là parce que 05AB1E ne peut pas déterminer les indices sur les listes multidimensionnelles afaik


Si la sortie des paires largeur / hauteur qui sont véridiques, ou la sortie d'une liste de valeurs véridiques / falsey basée sur la liste d'entrée, cela pourrait être de 8 octets à la place:

ʒ‚ε{ü/}Ë

Essayez-le en ligne ou vérifiez tous les cas de test .

ε‚ε{ü/}Ë

Essayez-le en ligne ou vérifiez tous les cas de test .

Kevin Cruijssen
la source