Lookalike Formen

23

Ähnliche Figuren

Zwei Rechtecke sind ähnlich, wenn die Seitenverhältnisse gleich sind.

Betrachten Sie diese beiden Rechtecke. Ein Rechteck mit 5 Zeilen Höhe und 11 Zeichen Breite:

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

und ein 10 Zeilen großes und 22 Zeichen breites Rechteck:

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

Diese Formen sind ähnlich, weil die Seitenverhältnisse gleich sind. Formal ausgedrückt (wobei die kürzeste und die längste Seite ist):hw

h1w1=h2w2

Sie können auch tun:

h1h2=w1w2

Die Herausforderung

Schreiben Sie ein Programm oder eine Funktion, die ein "Haupt" -Rechteck und einige "andere" Rechtecke verwendet und druckt, welche der "anderen" ähnlich wie "Haupt" sind.

Die Eingabe

Eine Form und eine Liste von Formen. Jede Form besteht aus 2 positiven Ganzzahlen ungleich Null, die die Breite und Höhe des Rechtecks ​​angeben. Zum Beispiel das:

(4,2), (3,9)

bezeichnet zwei Rechtecke, ein 4x2 und ein 3x9. Das genaue Format der Eingabe kann beliebig sein.

Die Ausgabe

Die Indizes der "anderen" Formen, die "main" ähnlich sind. Sie können wählen, ob die Indizes 0- oder 1-basiert sind, sowie das genaue Format und die Reihenfolge der Ausgabe.

Beispielprogramm

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 Ein- und Ausgabe

Eingang:

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

Ausgabe:

set([0, 1])

Eingang:

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

Ausgabe:

set([2])

Gewinnen

Dies ist Code-Golf, also gewinnt die kürzeste Einsendung.

Anmerkungen

  • Dies sollte selbstverständlich sein, aber Standardlücken sind verboten .
  • Es dürfen keine Builtins zum Auffinden ähnlicher Figuren verwendet werden. (Ich weiß nicht einmal, ob das existiert, aber ich wäre nicht überrascht!)
kirbyfan64sos
quelle
Ist die Verwendung einer Gleitkommadivision zulässig? Wäre [1.0 2.0]ein akzeptables Eingabeformat?
Dennis
@Dennis Vorausgesetzt, Ihre ausgewählte Sprache weist keine merkwürdig niedrige Gleitkommagenauigkeit auf, und daher schlagen die Testfälle fehl, sollte dies in Ordnung sein. ;)
kirbyfan64sos
Können wir anstelle von Indizes auch die tatsächlich ähnlichen Formen selbst ausgeben?
Orlp
@orlp Nein !!! : D
kirbyfan64sos
3
Ist das Ausgabeformat für die Ausgabe der Indizes obligatorisch? Für einen Testfall wie [(1,2), (2,4), (1,9), (2,5), (16,8)], ist nur [0,1,4]und [1,2,5]erlaubt, oder könnten wir auch ausgeben [1,1,0,0,1]oder [(1,2), (2,4), (16,8)]?
Kevin Cruijssen

Antworten:

5

Pyth, 15 Bytes

fqcFS@QTcFSvzUQ
orlp
quelle
11

Python, 61 Bytes

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

Ja, ich verwende 9 Zeichen zum Schreiben enumerate. Nimmt Eingaben wie 1, 2, [(1, 9), (3,6), (2, 5), (16, 8)]. Für Python 2 müssen Eingabewerte als Float geschrieben werden.

Ein Zeichen länger (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
xnor
quelle
Macht es Ihnen etwas aus, das zu erklären? Ich würde gerne wissen, was los ist.
The_Basset_Hound
@BassetHound Für jedes Element in der Eingabeliste wird das Verständnis ials Index und (x,y)als Punkt entpackt . Anschließend wird geprüft, ob der Wert x/yentweder dem Quotienten ( a/b) der ersten beiden Zahlen oder dem Kehrwert ( b/a) entspricht. Wenn er einem dieser Werte entspricht, wird der Wert von izur Liste hinzugefügt, andernfalls wird er verworfen.
FryAmTheEggman
9

CJam, 22 20 19 Bytes

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

Bei der obigen Funktion handelt es sich um eine anonyme Funktion, die ein einzelnes Array von Gleitkomma-Paaren (erstes Paar ist needle) aus dem Stapel entfernt und das Array von 1-basierten Indizes zurückgibt.

Versuchen Sie es online in dem CJam Dolmetscher .

Wie es funktioniert

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

Haskell , 48 Bytes

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

Probieren Sie es online!

Nennen Sie das wie (!) 1 2 [(1, 9), (3,6), (2, 5), (16, 8)].

Ein Near-Port meiner Python-Antwort . Der Ausdruck zip[0..]lzählt die Liste mit ihren Indizes auf.

Der Ausdruck x/y+y/x==a/b+b/aüberprüft, ob das Verhältnis x/yentweder a/boder b/a, da die Funktion f(z) = z + 1/zhat f(z) = f(1/z)und keine weiteren Kollisionen.

xnor
quelle
Lassen Sie heinen Operator vielleicht drei Argumente annehmen? Das würde ein Byte sparen und ich denke, es würde innerhalb der Regeln bleiben.
Dienstag,
@dfeuer Sicher, es ist definitiv nach modernen Maßstäben erlaubt, obwohl es damals unklarer war, welche Freiheiten mit I / O genommen werden konnten.
14.
7

Schneemann 1.0.2 , 61 Zeichen

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

Pures Kauderwelsch (es sei denn, Sie kennen Snowman), auch bekannt als genau das gestalterische Ziel der Sprache, so verwirrend wie möglich zu sein.

Das Eingabeformat ist das gleiche wie im Beitrag, das Ausgabeformat ist auch das gleiche Minus set(und ).

Ungolfed (oder wirklich nicht abgeschlossen):

}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

Ich bin ziemlich stolz auf einige der Tricks, die ich in diesem verwendet habe:

  • Ich habe das gleiche Eingabeformat wie im Beitrag verwendet. Aber anstatt zu versuchen, es irgendwie zu analysieren, was wirklich chaotisch werden würde, habe ich einfach die beiden Zeilen verkettet und dann mit einem regulären Ausdruck alle Zahlen in ein großes Array extrahiert (mit dem ich dann 2aGjede Gruppe von 2 erhalten habe).

  • :nD;aFist ziemlich schick. Es nimmt einfach ein Array von zwei Elementen und teilt das erste durch das zweite. Das scheint ziemlich einfach zu sein, aber auf intuitive Weise ( a[0]/a[1]) wäre in Snowman weitaus länger 0aa`NiN`aA|,nD(und das unter der Annahme, dass wir uns nicht um das Durcheinander mit anderen vorhandenen Variablen kümmern müssen). Stattdessen habe ich die Methode "fold" mit dem Prädikat "divide" verwendet, mit der für ein Array von zwei Elementen dasselbe erreicht wird.

  • 0AAgaAEs sieht harmlos aus, aber tatsächlich speichert es a 0in den Variablen und nimmt dann alle Variablen mit einem größeren Index (also alle Variablen mit Ausnahme der ersten). Aber der Trick ist, AaGdass ich anstatt (was das ursprüngliche Array und das Array loswerden würde 0) AAgbeides verwendet habe. Jetzt benutze ich aA, at-Index, mit dem gleichen0 das erste Element des Arrays-weiterhin zu erhalten, ist dies in konsumieren-Modus ( aAstatt aa), so dass es dem loswerden wird 0zu und Original - Array, das sind jetzt Müll für uns.

    Ach, 0AAgaA*|tut im Wesentlichen die gleiche Sache , dass GolfScript in einem Zeichen tut: (. Trotzdem finde ich es für Schneemann-Verhältnisse ziemlich nett. :)

Türknauf
quelle
3

Mathematica, 41 Bytes

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

Verwendung:

Position[a = Sort@#; Sort@#/a & /@ #2, {x_, x_}] &[{1, 2}, {{1, 2}, {2, 5}, {16, 8}}]
(* {{1}, {3}} *)
Martin Ender
quelle
1
Ich wusste nur, dass Mathematica irgendwie auftauchen würde!
kirbyfan64sos
3

Pyth - 14 Bytes

Filtert nach Quotienten und ordnet sie zu indexOf.

xLQfqcFSTcFvzQ

Test Suite .

Maltysen
quelle
Dadurch wird die Hauptform nicht sortiert, sodass die falsche Antwort angezeigt wird, wenn die erste Seitenlänge der Hauptform größer ist. Siehe diesen Testfall
isaacg
@isaacg guter Punkt, wird behoben.
Maltysen
Dies schlägt beispielsweise bei Eingaben mit wiederholten Elementen fehl 1,2und [(1, 2), (2, 4), (1, 2)]gibt [0, 1, 0]eher als das richtige aus [0, 1, 2].
Orlp
Ich möchte dieses akzeptieren, da es ist die kürzeste, aber das Problem ist @orlp fixiert erwähnt?
kirbyfan64sos
1
@ kirbyfan64sos Nr.
Orlp
3

APL (Dyalog Unicode) , 16 bis 13 Byte SBCS

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

Probieren Sie es online!

-3 danke an @ngn!

Erläuterung:

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

Das Ausgabeformat ist ein binärer Vektor, 1 1 0 0 1von dem "anderes" Rechteck ein Aussehen hat.

APL (Dyalog Extended) , 11 Byte SBCS

=/-×⍥(⌈/)¨⌽

Probieren Sie es online!

Erläuterung:

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

Das Ausgabeformat ist dasselbe wie die Hauptantwort von Dyalog.

Vielen Dank an Adám für die Hilfe Golf + Extended.

Ven
quelle
(=.×∘⌽∨=.×)⍤1
12.
Vielen Dank. Werden versuchen , die zuerst zu prüfen
Ven
2

Julia, 62 Bytes

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

Die findFunktion findet wahre Elemente in einem Booleschen Vektor. .*Führt eine elementweise Multiplikation von Vektoren durch.

Ungolfed:

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

Verwendung:

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

K5, 19 Bytes

Ich denke, das wird den Trick machen:

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

Nimmt eine Liste von Paaren auf, wobei das erste das "Haupt" ist. Berechnet das Verhältnis durch Teilen der sortierten Dimensionen jedes Paares. Gibt eine Liste der 0-indizierten Positionen der übereinstimmenden Paare zurück. (Möglicherweise bewirkt 1+das von mir gewählte Eingabeformat, dass diese Angabe -1 indiziert wird, wenn dies als ungültiger Ansatz an einem Anfang betrachtet wird, und fügt der Größe meines Programms zwei Zeichen hinzu.)

Anwendungsbeispiel:

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

Dies läuft in OK - beachten Sie, dass ich implizit von der Division abhängig bin, die immer Gleitkommaergebnisse liefert. In Kona würde es funktionieren, wenn Sie allen Zahlen in der Eingabe ein Dezimalzeichen und nach dem ein Leerzeichen hinzufügen _.

JohnE
quelle
2

Oktave / Matlab, 44 Bytes

Verwenden einer anonymen Funktion:

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

Das Ergebnis ist eine 1-basierte Indizierung.

Um es zu benutzen, definieren Sie die Funktion

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

und rufen Sie es mit dem folgenden Format auf

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

Sie können es online ausprobieren .


Wenn das Ergebnis eine logische Indizierung sein kann ( 0zeigt nicht ähnlich an, 1zeigt ähnlich an): 38 Bytes :

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

Gleiches Beispiel wie oben:

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

Brachylog , 14 Bytes

z{iXhpᵐ/ᵛ∧Xt}ᵘ

Probieren Sie es online!

Nimmt die Eingabe als Liste mit einer Liste, die das Hauptrechteck und die Liste der anderen Rechtecke enthält (Testfall 1 ist also [[[1,2]],[[1,2],[2,4]]]), und gibt eine Liste von 0-basierten Indizes über die Ausgabevariable aus.

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.

Wenn diese Art von seltsamer und spezifischer Eingabe-Formatierung schummelt, ist es etwas länger ...

Brachylog , 18 Bytes

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

Probieren Sie es online!

Übernimmt die Eingabe als Liste mit dem Hauptrechteck und der Liste der anderen Rechtecke (Testfall 1 ist also offensichtlicher [[1,2],[[1,2],[2,4]]]) und gibt eine Liste von 0-basierten Indizes über die Ausgabevariable aus.

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

Um festzustellen, ob zwei Breite-Höhe-Paare ähnliche Rechtecke darstellen, werden nur die vier Bytes pᵐ/ᵛ(die das gemeinsame Verhältnis oder dessen Kehrwert ausgeben) benötigt. Der Rest besteht darin, die mehreren zu vergleichenden Rechtecke und die Ausgabe als Indizes zu behandeln.

Nicht verwandte Zeichenfolge
quelle
2

dzaima / APL , 7 Bytes

=/⍤÷⍥>¨

Probieren Sie es online!

8 Bytes, die eine Liste von Indizes anstelle eines Booleschen Vektors ausgeben

      ¨ 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
quelle
Obwohl es eine schöne Antwort ist, müssen wir die Indizes ausgeben. Ihr TIO-Testfall sollte also entweder [0,1,4]oder ergeben [1,2,5](nicht sicher, ob Ihre Sprache 0- oder 1-indiziert ist). Es wäre imho eine bessere Herausforderung gewesen, wenn alle drei Ausgabeformate erlaubt wären: Indizes; filtern, um die wahren Werte zu erhalten; Liste der wahrheitsgemäßen / falschen Werte (wie Sie es jetzt getan haben), anstatt nur zulässige Indizes.
Kevin Cruijssen
@KevinCruijssen "Sie können das genaue [...] Format und die Reihenfolge der Ausgabe auswählen." in APL ist es sehr üblich , zum Speichern von Indizes als boolean Vektor, aber du hast recht, das ist wahrscheinlich geklärt werden soll.
Dzaima
Nun, ich habe gelesen " Sie können wählen, ob die Indizes 0- oder 1-basiert sind, sowie das genaue Format und die Reihenfolge der Ausgabe. “ , Wie es sein kann [0,1,4], [1,2,5], 4\n0\n1, 5 2 1, etc. etc., da es nach wie vor angegeben Indizes . Aber ich habe OP gebeten zu klären (ob sie antworten, da es eine 4 Jahre alte Herausforderung ist). In meiner 05AB1E-Antwort würde dies 14 Bytes bedeuten, wenn die Indizes obligatorisch sind, im Gegensatz zu 8 Bytes, wenn eine der beiden anderen Optionen zulässig ist. Unabhängig davon habe ich Ihre Antwort positiv bewertet. :)
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
quelle
56 bytes
dfeuer
54 Bytes
14.
1

Power Shell , 58 56 Byte

-2 Bytes dank mazzy x2

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

Probieren Sie es online!

Dies missbraucht leicht die input may be however you desire Klausel , da die Komponenten der ersten Form separat geliefert werden, um 3 Byte zu sparen.

Power , 61 59 Bytes

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

Probieren Sie es online!

Verwendet die bedingte Indizierung, um zwischen dem aktuellen nullbasierten Index und null zu wechseln, je nachdem, ob die Verhältnisse aufeinander abgestimmt sind oder nicht. Zum Glück wird in diesem Fall $iunabhängig davon, ob gedruckt wird oder nicht , inkrementiert.

Veskah
quelle
1
Sie können mehr sparen, wenn Sie -stattdessen verwenden -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))

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

Die Eingabe wird als JSON-Objekt und als Array von JSON-Objekten verwendet

{
    l: length of rectangle,
    h: height of rectangle
}
DankMemes
quelle
Ich denke nicht, dass dies mit dem zweiten Testfall funktioniert.
kirbyfan64sos
@ kirbyfan64sos leider nicht diesen Teil gesehen. Es ist behoben (aber ich bin sicher, ich kann es mehr Golf)
DankMemes
Dies sind keine JSON-Objekte, sondern reine Javascript-Objekte. JSON ist ein Datenübertragungsformat.
EDC65
0

05AB1E , 15 14 Bytes

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

Probieren Sie es online aus oder überprüfen Sie alle Testfälle .

Erläuterung:

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

Die JOins sind da, weil 05AB1E die Indizes für mehrdimensionale Listen afaik nicht bestimmen kann


Wenn Sie die wahrheitsgemäßen Breiten- / Höhenpaare ausgeben oder eine Liste von wahrheitsgemäßen / falschen Werten basierend auf der Eingabeliste ausgeben, könnten es stattdessen 8 Bytes sein :

ʒ‚ε{ü/}Ë

Probieren Sie es online aus oder überprüfen Sie alle Testfälle .

ε‚ε{ü/}Ë

Probieren Sie es online aus oder überprüfen Sie alle Testfälle .

Kevin Cruijssen
quelle