Finde heraus, ob eine Liste ein ABC-Tripel ist

16

Drei positive ganze Zahlen A, B, C sind ABC-Tripel, wenn sie Koprime sind, mit A <B und erfüllen die Beziehung: A + B = C

Beispiele:

  • 1, 8, 9 ist ein ABC-Tripel, da sie Koprime sind, 1 <8 und 1 + 8 = 9
  • 6, 8, 14 liegt nicht daran, dass sie nicht mitschuldig sind
  • 7, 5, 12 liegt nicht an 7> 5

In dieser Präsentation von Frits Beukers 2005 erfahren Sie mehr über ABC-Tripel.

Input-Output

Drei Ganzzahlen, dezimal geschrieben. Kann getrennte Werte oder Listen sein. Die Ausgabe musste ein wahrer / falscher Wert sein, ob die drei Ganzzahlen ein ABC-Tripel sind.

Hinweis: Es ist wichtig, die Reihenfolge ganzer Zahlen in der Liste zu 1, 8, 9beachten. Beispiel: Wird nicht als dieselbe Liste 9, 1, 8oder als eine andere Kombination angesehen. Also ist erstens ein ABC-Tripel und zweitens nicht.

Somit ist A das erste Element der Liste, B das zweite und C das dritte.

Testfälle

Jede der folgenden Listen sollte einen Wahrheitswert ausgeben

[1, 8, 9]
[2, 3, 5]
[2, 6436341, 6436343]
[4, 121, 125]
[121, 48234375, 48234496]

Jede der folgenden Listen sollte einen falschen Wert ausgeben

[1, 1, 2]
[1, 2, 5]
[1, 9, 8]
[4, 12872682, 12872686]
[6, 8, 14]
[7, 5, 12]
David
quelle
Muss die Ausgabe nur einer von zwei Werten sein, oder können wir für verschiedene Eingaben unterschiedliche Wahrheits- / Falschwerte ausgeben?
Luis Mendo
Ich denke, es sollte konsistent sein: Ihr Code muss unabhängig von der Eingabe eine Art wahrer / falscher Werte ausgeben. Aber das wahrheitsgemäße / falsche Paar kann das sein, was Sie wollen, soweit es die Aufgabe erfüllt: Unterscheiden von Listen.
David
Wenn wir die Eingabe als Liste mit drei Werten annehmen, muss die Eingabe in der Reihenfolge erfolgen [A,B,C], oder dürfen wir die Eingabe auch in der Reihenfolge vornehmen, [C,B,A]oder [C,A,B]?
Kevin Cruijssen
Sie müssen die Reihenfolge respektieren, da A <B ein Kriterium bei der Herausforderung ist.
David
1
Ich glaube nicht, dass die Anforderung einer bestimmten Listenreihenfolge kompatibel ist, um die Eingabe als separate Werte zuzulassen, da separate Werte von Natur aus ungeordnet sind und als Liste verwendet werden können .
Dennis

Antworten:

8

Gelee , 10 9 Bytes

Ṫ=S×</=g/

Probieren Sie es online!

Wie es funktioniert

Ṫ=S×</=g/  Main link. Argument: [a, b, c] (positive integers)

Ṫ          Tail; pop and yield c.
  S        Take the sum of [a, b], yielding (a + b).
 =         Yield t := (c == a + b).
    </     Reduce by less than, yielding (a < b).
   ×       Multiply, yielding t(a < b).
       g/  Reduce by GCD, yielding gcd(a, b).
      =    Check if t(a < b) == gcd(a, b).
Dennis
quelle
8

Haskell , 48 38 29 Bytes

-10 Bytes aufgrund TFeld ‚s gcdTrick!

-7 Byte dank HPWiz für die Verbesserung des Co-Primality-Tests und das Erkennen eines überflüssigen Speicherplatzes!

-2 Bytes danke an nimi für den Hinweis auf einen Infix-Operator!

(a!b)c=a<b&&a+b==c&&gcd a b<2

Probieren Sie es online!

Erläuterung

Die ersten zwei Bedingungen a < bund a + b == csind ziemlich offensichtlich, die dritten Verwendungen dass :gcd(a,b)=gcd(a,c)=gcd(b,c)

Das Schreiben von Verwendung von Bézouts Identität und das Ersetzen von ergibt:gcd(a,c)=Ua+Vcc=a+b

Ua+V(a+b)=(U+V)a+Vb

Da die zu dieser Identität die minimale positive Lösung ist , folgt daraus , dass . Der andere Fall ist symmetrisch.gcdgcd(a,b)=gcd(a,c)

ბიმო
quelle
1
Außerdem glaube ich, dass du das nur brauchst gcd a b==1. Da gcd a bteilt sich a+b=c. dhgcd(gcd a b)c=gcd a b
H.PWiz
@HPWiz: Ah ja, natürlich danke! Wird später bearbeitet, wenn nicht auf dem Handy ..
3.
7

Perl 6 , 33 32 Bytes

-1 byte dank nwellnhof

{(.sum/.[2]/2*[<] $_)==[gcd] $_}

Probieren Sie es online!

Anonymer Codeblock, der eine Liste mit drei Zahlen aufnimmt und Wahr oder Falsch zurückgibt.

Erläuterung

{                              }  # Anonymous code block
                       [gcd] $_   # Is the gcd of all the numbers
 (                  )==           # Equal to
  .sum        # Whether the sum of numbes
      /       # Is equal to
       .[2]/2 # The last element doubled
             *[<] $_   # And elements are in ascending order
Scherzen
quelle
2
32 Bytes
Nwellnhof
5

Excel, 33 Bytes

=AND(A1+B1=C1,GCD(A1:C1)=1,A1<B1)
Wernisch
quelle
4

Bash, 61 Bytes

factor $@|grep -vzP '( .+\b).*\n.*\1\b'&&(($1<$2&&$1+$2==$3))

Probieren Sie es online!

Eingabe als Kommandozeilenargumente, Ausgabe im Exit-Code (erzeugt auch Ausgabe auf stdout als Nebeneffekt, dies kann jedoch ignoriert werden).

Der zweite Teil (ab &&(() ist ziemlich normal, aber das Interessante ist der Coprime-Test:

factor $@      # produces output of the form "6: 2 3\n8: 2 2 2\n14: 2 7\n"
|grep -        # regex search on the result
v              # invert the match (return truthy for strings that don't match)
z              # zero-terminated, allowing us to match newlines
P              # perl (extended) regex
'( .+\b)'      # match one or more full factors
'.*\n.*'       # and somewhere on the next line...
'\1\b'         # find the same full factors
Türknauf
quelle
Letzter &&kann &wegen Vorrangigkeit
Nahuel Fouilleul
4

Java 10, 65 64 Bytes

(a,b,c)->{var r=a<b&a+b==c;for(;b>0;a=b,b=c)c=a%b;return r&a<2;}

-1 Byte danke an @Shaggy .

Probieren Sie es online aus.

Erläuterung:

(a,b,c)->{        // Method with three integer parameters and boolean return-type
  var r=          //  Result-boolean, starting at:
        a<b       //   Check if `a` is smaller than `b`
        &a+b==c;  //   And if `a+b` is equal to `c`
  for(;b>0        //  Then loop as long as `b` is not 0 yet
      ;           //    After every iteration:
       a=b,       //     Set `a` to the current `b`
       b=c)       //     And set `b` to the temp value `c`
    c=a%b;        //   Set the temp value `c` to `a` modulo-`b`
                  //   (we no longer need `c` at this point)
  return r        //  Return if the boolean-result is true
         &a<2;}   //  And `a` is now smaller than 2
Kevin Cruijssen
quelle
a==1-> a<2um ein Byte zu speichern.
Shaggy
@ Shaggy Danke!
Kevin Cruijssen
4

05AB1E , 12 11 10 Bytes

Dank Kevin Cruijssen 1 Byte gespeichert

ÂÆ_*`\‹*¿Θ

Probieren Sie es online! oder als Testsuite

Erläuterung

ÂÆ           # reduce a reversed copy of the input by subtraction
  _          # logically negate
   *         # multiply with input
    `        # push the values of the resulting list separately to stack
     \       # remove the top (last) value
      ‹      # is a < b ?
       *     # multiply by the input list
        ¿    # calculate the gcd of the result
         Θ   # is it true ?
Emigna
quelle
Hoppla .. habe meinen Kommentar gelöscht ..>.> Also nochmal: Sie können ein Byte speichern, indem Sie ein Vielfaches anstelle eines Austauschs mit Produkt: RÆ_*`\‹*¿Θ Test Suite verwenden .
Kevin Cruijssen
@ KevinCruijssen: Danke! Ja, normalerweise machst du etwas falsch, wenn du so viele Swaps hast: P
Emigna
3

Python 2 , 69 67 63 62 55 Bytes

lambda a,b,c:(c-b==a<b)/gcd(a,b)
from fractions import*

Probieren Sie es online!


Python 3 , 58 51 Bytes

lambda a,b,c:(c-b==a<b)==gcd(a,b)
from math import*

Probieren Sie es online!


-7 Bytes, danke an H.PWiz

TFeld
quelle
ist der gcdin gcdtrick gültig? Was ist, wenn anicht mit Coprime c?
Jo King
2
@ jo-king Wenn p a und c teilt, sollte es ca so b teilen.
david
2
@JoKing: Es ist in diesem Fall, aber nicht im Allgemeinen (Sie können es über die Identität von Bezout beweisen).
3.
Sie können es einen Schritt weiter gehen und verwenden gcd(a,b), da gcd(a,b)teilta+b
H.PWiz
@ H.PWiz Danke :)
TFeld
3

Japt , 16 14 13 11 Bytes

<V¥yU «NÔr-

Versuch es

                :Implicit input of integers U=A, V=B & W=C
<V              :Is U less than V?
  ¥             :Test that for equality with
   yU           :The GCD of V & U
      «         :Logical AND with the negation of
       N        :The array of inputs
        Ô       :Reversed
         r-     :Reduced by subtraction
Zottelig
quelle
Hier ist eine weitere 11-Byte-Lösung, die sich bei näherer Betrachtung in ihrer tatsächlichen Logik kaum von Ihrer unterscheidet.
Kamil Drakari
@KamilDrakari, hatte auch eine Variation darüber. Es können 10 Byte sein, wenn Variablen wie >folgt automatisch eingefügt werden ©.
Shaggy
3

JavaScript (ES6),  54 43 42  40 Byte

Vielen Dank an @Shaggy für den Hinweis, dass wir nicht berechnen müssen . Spart 11 Bytes, indem der Code entsprechend umgeschrieben wird.gcd(a,c)

Nimmt die Eingabe als 3 separate Ganzzahlen. Gibt für ein ABC-Tripel oder entweder oder andernfalls .true0false

f=(a,b,c)=>c&&a/b|a+b-c?0:b?f(b,a%b):a<2

Probieren Sie es online!

Arnauld
quelle
1
Ich glaube nicht, dass Sie testen müssen gcd(c,a).
Shaggy
@ Shaggy Danke! Ich habe den Code komplett umgeschrieben.
Arnauld
3

Wolfram Language 24 30 28 26 Bytes

Mit 2 Bytes von Doorknob rasiert. Weitere 2 Bytes, die @jaeyong gesungen hat

#<#2&&GCD@##==1&&#+#2==#3&
DavidC
quelle
Ich denke, Sie sollten auch in der Lage sein, CoprimeQ@##2 Bytes zu sparen.
Türknauf
@Doorknob, Wenn die erste und die zweite Zahl Coprime sind, müssen sie Coprime mit ihrer Summe sein?
DavidC
Sie sind es , aber die ursprüngliche Definition besagt tatsächlich, dass A, B und C Coprime sein sollten. Die meisten Antworten prüfen nur A und B, nur weil es normalerweise kürzer ist.
Türknauf
Ich denke, GCD@##==1würde 2 Bytes sparen
jaeyong
2

C # (Visual C # Interactive Compiler) , 90 Byte

n=>new int[(int)1e8].Where((_,b)=>n[0]%++b<1&n[1]%b<1).Count()<2&n[0]+n[1]==n[2]&n[0]<n[1]

Läuft für Nummern bis 1e8, dauert auf meinem Rechner ca. 35 Sekunden. Anstatt den gcd wie andere zu berechnen, instanziiert die Funktion einfach ein großes Array und filtert die Indizes, die keine Teiler von a oder b sind, und überprüft, wie viele Elemente übrig sind. Als nächstes wird geprüft, ob Element eins plus Element zwei gleich Element drei ist. Zuletzt wird geprüft, ob das erste Element kleiner als das zweite ist.

Probieren Sie es online!

Verkörperung der Ignoranz
quelle
2

ECMAScript Regex, 34 Bytes

Die Eingabe ist in der Domäne unär ^x*,x*,x*$(wiederholt xdurch ,).

^(?!(xx+)\1*,\1+,)(x*)(,\2x+)\3\2$

Probieren Sie es online! (.NET Regex Engine)
Probieren Sie es online! (SpiderMonkey Regex Engine)

# see /codegolf/178303/find-if-a-list-is-an-abc-triple
^
(?!                # Verify that A and B are coprime. We don't need to include C in the
                   # test, because the requirement that A+B=C implies that A,B,C are
                   # mutually comprime if and only if A and B are coprime.
    (xx+)\1*,\1+,  # If this matches, A and B have a common factor \1 and aren't coprime.
)
(x*)(,\2x+)\3\2$   # Verify that A<B and A+B=C. The first comma is captured in \3 and
                   # reused to match the second comma, saving one byte.

Die Frage lautet "Drei Ganzzahlen, dezimal geschrieben", sodass dies möglicherweise nicht qualifiziert ist (da Eingaben unärgerlich sind), aber es ergibt eine so elegante, reine Regex, dass ich hoffe, dass es zumindest geschätzt wird.

Beachten Sie jedoch, dass bei einer wörtlichen Interpretation der Phrasierung auch Lambda-Übermittlungen und Funktionsübermittlungen, die Ganzzahlargumente enthalten, zu disqualifizieren sind, da sie sich strikt an die Spezifikation der Frage halten und die Eingabe in Form einer Zeichenfolge vornehmen müssen.

Deadcode
quelle
1

Sauber , 43 Bytes

import StdEnv
$a b c=a<b&&a+b==c&&gcd a b<2

Probieren Sie es online!

Ähnlich wie im Grunde alles andere, da der direkte Test der gleiche ist.

Οurous
quelle
1

Befunge-98 (FBBI) , 83 Bytes

&:&:03p&:04pw>03g04g\:v_1w03g04g+w1.@
00:    [email protected][^j7      _^;>0.@;j7;>0.@;:%g00\p

Probieren Sie es online!

Die Eingabe, bei der es sich um ein Dreifach von Ganzzahlen [A,B,C]handelt, wird als durch Leerzeichen getrennte Ganzzahlen in Befunge eingespeist C B A.

Wisław
quelle
1

Mathematica 35 Bytes

CoprimeQ @@ # && #[[1]] + #[[2]] == #[[3]] & 

wenn die Reihenfolge wichtig ist:

CoprimeQ @@ # && Sort[#]==# && #[[1]] + #[[2]] == #[[3]] & 

oder...

And[CoprimeQ @@ #, Sort@# == #, #[[1]] + #[[2]] == #[[3]]] &
David G. Stork
quelle
1

Retina 0.8.2 , 42 41 Bytes

\d+
$*
A`^(11+)\1*,\1+,
^(1+)(,1+\1)\2\1$

Probieren Sie es online! Link enthält Testfälle. Bearbeiten: 1 Byte dank @Deadcode gespeichert. Erläuterung:

\d+
$*

In Unary konvertieren.

A`^(11+)\1*,\1+,

Stellen Sie sicher, dass A und B keinen gemeinsamen Faktor haben.

^(1+)(,1+\1)\2\1$

Überprüfen Sie, dass A <B und A + B = C.

Neil
quelle
1
Es scheint einen Fehler in Ihrem Programm zu geben. [121, 48234375, 48234496] gibt false zurück.
Deadcode
1
@Deadcode Behoben, danke, dass du mich informiert hast.
Neil
Wie bei meiner regex, können Sie 1 Byte fallen durch eine Änderung ^(1+),(1+\1),\1\2$an ^(1+)(,1+\1)\2\1$.
Deadcode
1
@Deadcode Danke! Es ist eine Schande, dass meine Verwendung der Retina- AOperation mir eigentlich keine Bytes erspart.
Neil
1
@Deadcode Ich benutze das Verhalten von Retina, um die letzte Regex in eine positive Behauptung umzuwandeln (tatsächlich eine (Anzahl der) Übereinstimmungsstufe), sodass das Verschieben des Antigrep 5 Byte kosten würde.
Neil