Mein Dreieck braucht mehr Knoten

20

Betrachten Sie das gleichseitige Standarddreieck mit Knoten, die mit Schwerpunktkoordinaten beschriftet sind :

Wir können dieses Dreieck mit 3 Knoten in ein Dreieck mit 6 Knoten umwandeln, indem wir eine neue Linie mit 3 Knoten hinzufügen (eine mehr als auf einer Seite des ursprünglichen Dreiecks mit 3 Knoten vorhanden war), interne Kanten entfernen (aber keine internen Knoten) und normalisiere die Koordinaten:

Bildbeschreibung hier eingeben

Wiederholen Sie den Vorgang, um von einem 6-Knoten-Dreieck zu einem 10-Knoten-Dreieck zu wechseln, fügen Sie eine Linie aus 4 Eckpunkten hinzu (wieder eine mehr, als auf einer Seite des ursprünglichen 6-Knoten-Dreiecks vorhanden war), und entfernen Sie alle internen Kanten (jedoch keine internen Knoten) ) und normalisiere die Koordinaten:

Bildbeschreibung hier eingeben

Dieser Vorgang kann auf unbestimmte Zeit wiederholt werden. Das Ziel dieser Abfrage ist eine Ganzzahl, Ndie angibt , wie oft dieser Prozess ausgeführt wurde. Geben Sie alle Knoten für das zugehörige Dreieck in baryzentrischen Koordinaten aus.

Eingang

Ihr Programm / Ihre Funktion sollte als Eingabe eine einzelne nicht negative Ganzzahl verwenden, Ndie angibt , wie oft dieser Prozess angewendet wurde. Beachten Sie, dass Sie für N=0das ursprüngliche Dreieck 3 Knoten ausgeben sollten.

Der Eingang kann von einer beliebigen Quelle stammen (Funktionsparameter, Stdio usw.).

Ausgabe

Ihr Programm / Ihre Funktion sollte alle Knoten in normalisierten Schwerpunktkoordinaten ausgeben. Die Reihenfolge der Knoten spielt keine Rolle. Eine Zahl kann als Bruchzahl (keine Bruchkürzung erforderlich) oder als Gleitkommazahl angegeben werden. Sie können auch "skalierte" Vektoren ausgeben, um einen Knoten anzugeben. Beispielsweise sind alle 3 der folgenden Ausgaben gleichwertig und zulässig:

0.5,0.5,0

1/2,2/4,0

[1,1,0]/2

Wenn Sie eine Gleitkommaausgabe verwenden, sollte Ihre Ausgabe auf 1% genau sein. Die Ausgabe kann auf eine beliebige Senke erfolgen (stdio, Rückgabewert, Rückgabeparameter usw.). Beachten Sie, dass Sie alle 3 Zahlen pro Knoten ausgeben sollten, obwohl die Schwerpunktkoordinaten eindeutig durch nur 2 Zahlen pro Knoten bestimmt werden.

Beispiele

Beispielfälle sind wie folgt formatiert:

N
x0,y0,z0
x1,y1,z1
x2,y2,z2
...

Dabei ist die erste Zeile die Eingabe N, und alle folgenden Zeilen bilden einen Knoten x,y,z, der genau einmal in der Ausgabe enthalten sein soll. Alle Zahlen sind als ungefähre Gleitkommazahlen angegeben.

0
1,0,0
0,1,0
0,0,1

1
1,0,0
0,1,0
0,0,1
0.5,0,0.5
0.5,0.5,0
0,0.5,0.5

2
1,0,0
0,1,0
0,0,1
0.667,0,0.333
0.667,0.333,0
0.333,0,0.667
0.333,0.333,0.333
0.333,0.667,0
0,0.333,0.667
0,0.667,0.333

3
1,0,0
0.75,0,0.25
0.75,0.25,0
0.5,0,0.5
0.5,0.25,0.25
0.5,0.5,0
0.25,0,0.75
0.25,0.25,0.5
0.25,0.5,0.25
0.25,0.75,0
0,0,1
0,0.25,0.75
0,0.5,0.5
0,0.75,0.25
0,1,0

Wertung

Das ist Code Golf; kürzester Code in Bytes gewinnt. Es gelten Standardlücken. Sie können beliebige integrierte Funktionen verwenden.

helloworld922
quelle
Sie sagen " Wenn Sie die Gleitkommaausgabe verwenden ". Welche Alternativen gibt es? Brüche? Wenn ja, müssen sie reduziert werden? Wie wäre es mit skalierten Vektoren wie [1,2,3]/6?
Peter Taylor
Ja, all diese Alternativen sind zulässig. Ich werde die Problembeschreibung aktualisieren.
helloworld922

Antworten:

7

CJam (22 Bytes)

{):X),3m*{:+X=},Xdff/}

Dies ist ein anonymer Block (eine Funktion), der Nden Stapel annimmt und ein Array von Doppelarrays auf dem Stapel hinterlässt. Online-Demo

Präparation

{         e# Define a block
  ):X     e# Let X=N+1 be the number of segments per edge
  ),3m*   e# Generate all triplets of integers in [0, X] (inclusive)
  {:+X=}, e# Filter to those triplets which sum to X
  Xdff/   e# Normalise
}
Peter Taylor
quelle
6

Haskell, 53 Bytes

f n|m<-n+1=[map(/m)[x,y,m-x-y]|x<-[0..m],y<-[0..m-x]]
Damien
quelle
5

Python 3, 87 Bytes

Dies soll eigentlich ein Kommentar zur Lösung von TheBikingViking sein, aber ich habe nicht genug Ruf für Kommentare.

Man kann ein paar Bytes einsparen, indem man nur die Variablen durchläuft i,jund die Tatsache ausnutzt , dass sie sich mit der dritten addieren n+1.

def f(n):d=n+1;r=range(n+2);print([[i/d,j/d,(d-i-j)/d]for i in r for j in r if d>=i+j])
Elvorfirilmathredia
quelle
4

Mathematica,  44  43 Bytes

Select[Range[0,x=#+1]~Tuples~3/x,Tr@#==1&]&

Dies ist eine unbenannte Funktion, die ein einzelnes ganzzahliges Argument verwendet. Die Ausgabe ist eine Liste von Listen mit exakten (reduzierten) Brüchen.

Generiert alle 3-Tupel von Vielfachen 1/(N+1)zwischen 0 und 1 einschließlich und wählt dann diejenigen aus, deren Summe 1 ist (wie von den Schwerpunktkoordinaten gefordert).

Martin Ender
quelle
4

05AB1E , 10 Bytes

ÌL<¤/3ãDOÏ

Erläuterung

ÌL<          # range(1,n+2)-1
   ¤/        # divide all by last element (n+1)
     3ã      # cartesian product repeat (generate all possible triples)
       DO    # make a copy and sum the triples
         Ï   # keep triples with sum 1

Probieren Sie es online aus

Emigna
quelle
¤Warum wird /das Array dadurch geteilt, da es das Array verbraucht ? Erinnert es sich an den zuletzt aufgetauchten Wert und verwendet ihn bei Bedarf?
Luis Mendo
@ LuisMendo: ¤ist einer der wenigen Befehle, die nicht vom Stapel genommen und verbraucht werden. Es verschiebt das letzte Element der Liste, während die Liste auf dem Stapel bleibt.
Emigna
Ja natürlich! Vielen Dank für die Erklärungen
Luis Mendo
3

MATL , 17 Bytes

2+:qGQ/3Z^t!s1=Y)

Probieren Sie es online!

Erläuterung

Der Ansatz ist der gleiche wie in anderen Antworten:

  1. Generiere das Array [0, 1/(n+1), 2/(n+1), ..., 1], wo nist die Eingabe;
  2. Generiere alle 3-Tupel mit diesen Werten;
  3. Behalte nur die, deren Summe ist 1.

Genauer:

2+     % Take input and add 2: produces n+2
:q     % Range [0 1 ... n+1]
GQ/    % Divide by n+1 element-wise: gives [0, 1/(n+1), 2/(n+1)..., 1]
3Z^    % Cartesian power with exponent 3. Gives (n+1)^3 × 3 array. Each row is a 3-tuple
t      % Duplicate
!s     % Sum of each row
1=     % Logical index of entries that equal 1
Y)     % Use that index to select rows of the 2D array of 3-tuples
Luis Mendo
quelle
1

Qualle , 37 33 Bytes

Vielen Dank an Zgarb für das Speichern von 4 Bytes.

p
*%
# S
`
=E   S
`/
1+r#>>i
   3

Probieren Sie es online!

Wie meine Mathematica- und Peters-CJam-Antworten generiert dies eine Reihe von Kandidatentupeln und wählt dann nur diejenigen aus, die die Summe 1 ergeben. Ich bin mit dem Layout noch nicht ganz zufrieden und frage mich, ob ich einige Bytes mit Hooks oder Gabeln speichern kann. aber ich muss das später untersuchen.

Martin Ender
quelle
1

Perl 6: 50 40 Bytes

{grep *.sum==1,[X] (0,1/($_+1)...1)xx 3}

Gibt eine Folge von Listen mit 3 Elementen von (exakten) rationalen Zahlen zurück.

Erläuterung:

  • $_
    Implizit deklarierter Parameter des Lambda.
  • 0, 1/($_ + 1) ... 1
    Verwendet den Sequenzoperator ..., um die arithmetische Sequenz zu erstellen, die den möglichen Koordinatenwerten entspricht.
  • [X] EXPR xx 3
    Nimmt das kartesische Produkt von drei Kopien von EXPR, erzeugt also alle möglichen 3-Tupel.
  • grep *.sum == 1, EXPR
    Filtertupel mit einer Summe von 1.
smls
quelle
1

Rubin, 62

Es würde mich wundern, wenn dies nicht verbessert werden kann:

->x{0.step(1,i=1.0/(x+1)){|a|0.step(1-a,i){|b|p [a,b,1-a-b]}}}

Unter Berücksichtigung des im Puzzle latenten Hinweises berechnet dies die Optionen des zweiten Knotens basierend auf dem ersten und des dritten Knotens durch Subtrahieren der ersten beiden.

Nicht dieser Charles
quelle
0

Python 3, 106 Bytes

def f(n):r=range(n+2);print([x for x in[[i/-~n,j/-~n,k/-~n]for i in r for j in r for k in r]if sum(x)==1])

Eine Funktion, die sie über ein Argument eingibt und eine Liste von Float-Listen an STDOUT ausgibt.

Python ist nicht gut in kartesischen Produkten ...

Wie es funktioniert

def f(n):                         Function with input iteration number n
r=range(n+2)                      Define r as the range [0, n+1]
for i in r for j in r for k in r  Length 3 Cartesian product of r
[i/-~n,j/-~n,k/-~n]               Divide each element of each list in the product
                                  by n+1
[x for x in ... if sum(x)==1]     Filter by summation to 1
print(...)                           Print to STDOUT

Probieren Sie es auf Ideone

TheBikingViking
quelle
0

Eigentlich 15 Bytes

Dies verwendet einen Algorithmus ähnlich dem in TheBikingVikings Python-Antwort . Golfvorschläge sind willkommen. Probieren Sie es online!

u;ur♀/3@∙`Σ1=`░

Ungolfed:

u;                Increment implicit input and duplicate.
  ur              Range [0..n+1]
    ♀/            Divide everything in range by (input+1).
      3@∙         Take the Cartesian product of 3 copies of [range divided by input+1]
         `Σ1=`    Create function that takes a list checks if sum(list) == 1.
              ░   Push values of the Cartesian product where f returns a truthy value.
Sherlock9
quelle
0

Rubin, 77 74 Bytes

Eine weitere Antwort mit dem Algorithmus in TheBikingVikings Python-Antwort . Golfvorschläge sind willkommen.

->n{a=[*0.step(1,i=1.0/(n+1))];a.product(a,a).reject{|j|j.reduce(&:+)!=1}}

Ein weiterer 74-Byte-Algorithmus basiert auf der Antwort Not that Charles's Ruby .

->x{y=x+1;z=1.0/y;[*0..y].map{|a|[*0..y-a].map{|b|p [a*z,b*z,(y-a-b)*z]}}}
Sherlock9
quelle
0

JavaScript (Firefox 30-57), 88 81 Bytes

n=>[for(x of a=[...Array(++n+1).keys()])for(y of a)if(x+y<=n)[x/n,y/n,(n-x-y)/n]]

Gibt ein Array von Arrays von Gleitkommazahlen zurück. Bearbeiten: Speichert 7 Bytes, indem die dritte Koordinate direkt berechnet wird. Ich habe versucht, das zu beseitigen, ifindem ich den Bereich von ydirekt berechnet habe, aber es kostet ein zusätzliches Byte:

n=>[for(x of a=[...Array(++n+1).keys()])for(y of a.slice(x))[x/n,(y-x)/n,(n-y)/n]]
Neil
quelle
Hast du am Ende [x/n,y/n/z/n]ein Komma vergessen?
Kamoroso94
@ kamoroso94 Du hast recht, ich habe das letzte Komma getippt, danke, dass du mich informiert hast.
Neil