Eine schlanke, gemeine Bohnenmaschine

26

Ein klassisches Beispiel für die Einführung in das Konzept einer diskreten Wahrscheinlichkeitsverteilung ist die Bohnenmaschine . Diese Maschine hat eine große Anzahl von Murmeln, die aus einem engen Durchgang oben herausfallen. Danach treffen sie auf Reihen von verflochtenen Stiften, wobei die Murmel an jedem Stift links oder rechts vom Stift hinabfallen können. Schließlich werden die Stifte in vertikalen Behältern am Boden der Maschine gesammelt. Ein einfaches Diagramm dieser Maschine sieht folgendermaßen aus:

|     O     |
|     ^     |
|    ^ ^    |
|   ^ ^ ^   |
|  ^ ^ ^ ^  |
| ^ ^ ^ ^ ^ |
|_|_|_|_|_|_|

In diesem Diagramm Obezeichnet das den Ort, von dem die Murmeln fallen. Jedes ^ist eine Stecknadel, bei der der Marmor eine 50% ige Chance hat, sich auf das Quadrat links oder rechts von der Stecknadel zu bewegen. Die Murmeln sammeln sich dann an den Behältern am Boden des Geräts, und bei einer ausreichenden Anzahl von Murmeln ähnelt die Höhe der Murmelstapel in den Behältern einer diskreten Binomialverteilung.

Herausforderung

Für diese Herausforderung berechnen Sie die resultierende Wahrscheinlichkeitsverteilung von Bean-Maschinen auf der Grundlage von Diagrammen wie dem obigen. Die Diagramme werden als zweidimensionales "Programm" interpretiert, durch das die Murmeln entweder zu Feldern an der Seite oder zu Feldern unterhalb des aktuellen Feldes laufen. Wenn die Murmeln den Boden der Maschine erreichen, werden sie für die Wahrscheinlichkeitsverteilung gezählt. Um es interessant zu halten, enthalten diese Diagramme ein paar Felder mehr als nur die einfache Quelle und die Pins. Ein Beispieldiagramm ist:

|     O     |
|     ^     |
|    ^ /    |
|   ^ | ^   |
|  <^- =  v |
| ^ ^ ^ ^ ^ |

Weiterhin haben die Murmeln nun jeweils eine Drehrichtung. Diese Richtung wird von einigen Feldern vorgegeben und bestimmt, zu welchem ​​nächsten Feld sich der Marmor in mehreren anderen Feldern bewegt.

Folgende Felder sind definiert:

  • O: Quelle. Spawns Murmeln direkt darunter. Die Richtung dieser Murmeln ist zu 50% links, zu 50% rechts. Jede Quelle produziert die gleiche Menge Murmeln.
  • U: Waschbecken. Jegliche Murmeln, die dieses Feld betreten, werden von der Bohnenmaschine entfernt.
  • : Freiraum. Wenn ein Marmor auf diesem Feld ankommt, bewegt er sich auf das Feld darunter.
  • -: Fußboden. Wenn ein Marmor auf diesem Feld ankommt, bewegt er sich je nach aktueller Richtung entweder zum linken oder zum rechten Feld.
  • ^: Splitter. Wenn ein Marmor auf diesem Feld ankommt, bewegt er sich zu 50% auf das Feld rechts oder das Feld links vom Splitter. Dies bestimmt auch die Richtung des Marmors.
  • v: Beitreten. Wenn ein Marmor auf diesem Feld ankommt, bewegt er sich auf das Feld darunter.
  • /: Schrägkissen. Wenn ein Marmor auf diesem Feld ankommt, bewegt er sich auf das Feld links vom Pad und legt die Richtung des Marmors fest.
  • \: Wie vorher, aber rechts.
  • |: Reflektor. Wenn ein Marmor auf diesem Feld ankommt, kehrt er die Richtung des Marmors um und verschiebt den Marmor auf der Grundlage dieser umgekehrten Richtung nach rechts oder links auf das Feld.
  • =: Kanone. Wenn ein Marmor in diesem Bereich kommt, wird es nach rechts oder in der Stromrichtung nach links zu verschieben, bis der Marmor ein Feld trifft , das nicht der Fall ist , -oder O.
  • <: Entspricht dem vorherigen, gibt jedoch immer die Richtung vor und bewegt sich nach links.
  • >: Wie vorher, aber rechts.

Die folgenden Garantien beziehen sich auf das Diagramm.

  • Jede Eingabezeile hat in Feldern genau die gleiche Länge.
  • Das Feld ganz links und ganz rechts jeder Zeile ist immer a |.
  • Das Diagramm enthält keine möglichen Pfade, auf denen Murmeln für eine unbestimmte Anzahl von Iterationen wie \/oder in der Maschine hängen bleiben können ^^.
  • Das Diagramm enthält nur die oben genannten Felder.
  • Es gibt eine oder mehrere Quellen

Ergebnis

Ihre Aufgabe wird es sein, ein 16-zeiliges ASCII-Balkendiagramm der Wahrscheinlichkeitsverteilung zu erstellen, in dem die Murmeln die untere Seite des Diagramms verlassen und so skaliert werden, dass die größte Wahrscheinlichkeit alle 16 Zeichen abdeckt. Also für folgendes Problem:

|     O     |
|     ^     |
|    ^ ^    |
|   ^ ^ ^   |
|  ^ ^ ^ ^  |
| ^ ^ ^ ^ ^ |

Ihr Programm sollte die folgende Lösung erzeugen (beachten Sie, dass es die gleiche Breite wie das Eingabeprogramm haben sollte, einschließlich der seitlichen Pipes:

     # #     
     # #     
     # #     
     # #     
     # #     
     # #     
     # #     
     # #     
   # # # #  
   # # # #  
   # # # #  
   # # # #  
   # # # #  
   # # # #  
 # # # # # #
 # # # # # # 

Beispiele

Das folgende Beispiel soll die Funktionalität aller verschiedenen Feldtypen testen:

|     O     O         |
|  O  ^ /  <^\\\      |
|    ^ >            ^ |
|   ^ ^ ^            =|
|  ^ ^ | ^    <^   O  |
| ^ > ^ | ^   O ^> v  |
||  ^U  ^  |  =    ^\ |
|  ^ ^ ^ ^U ^\ ---^   |
| = ^   ^     =    v  |

Es sollte die folgende Ausgabe ergeben:

                     # 
                     # 
                     # 
                     # 
                   # # 
                   # # 
                   # # 
       # #         # # 
       # #         # # 
       # #         # # 
       # #         # # 
      ## #         # # 
      ## # #       # # 
   # ### # #       # # 
 # # ### # #       # # 
 # # ### # #       # # 

Regeln

Sowohl Funktionen als auch vollständige Programme sind gültige Antworten auf diese Herausforderung. Sie erhalten das Diagramm als durch Zeilenumbrüche getrennte Zeichenfolge und sollten das Ausgabediagramm im angegebenen Format zurückgeben. Es gelten die Standard-Ein- / Ausgaberegeln . Während in der Ausgabe abschließende und führende Zeilenumbrüche zulässig sind, sollte jede Zeile genau die gleiche Breite wie die Eingabe haben.

Um kreativere Lösungen zu ermöglichen, muss Ihr Programm in mehr als 90% der Fälle das richtige Ergebnis für dasselbe Diagramm ausgeben. Es ist schließlich eine Wahrscheinlichkeitssimulation.

Wertung

Das ist , also gewinnt die niedrigste Punktzahl in Bytes.

CensoredUsername
quelle
Viel einfacher, aber verwandt .
Peter Taylor
Kommentare sind nicht für eine längere Diskussion gedacht. Diese Unterhaltung wurde in den Chat verschoben .
Dennis
also v= [space]?
14.
@ l4m2 vund [space]unterscheiden sich darin, wie Kanonen um sie herum interagieren.
CensoredUsername

Antworten:

8

Python 3 , 431 429 410 Bytes

def t(a):e=enumerate;p=a.split("\n");o=[0]*len(p[0]);{m(i,j,p,o,1):m(i,j,p,o,-1)for i,r in e(p)for j,c in e(r)if"O"==c};[print("".join(" #"[round(16*r/max(o)+i)>15]for r in o))for i in range(16)]
def m(r,k,p,o,l,x=1):
 while r<len(p):
  c=p[r][k]
  if"^"==c:x/=2;m(r,k-l,p,o,l,x)
  if"U"==c:return
  if c in" vO":r+=1;continue
  l=[1,l,-1,l,-l,1][ord(c)%6];k-=l
  while";"<c<"?"and p[r][k]in" O-":k-=l
 o[k]+=x

Probieren Sie es online!

Diese Antwort ist eine Zusammenarbeit zwischen Wheat Wizard und CensoredUsername. Als Referenz ist dies der Algorithmus ohne Golf.

-2 Bytes von Mr. Xcoder

-19 Bytes von CensoredUsername

Hat Wizard
quelle
-2 Bytes, wenn Sie zu Python 2 wechseln (print statement)?
Caird Coinheringaahing
1
Davon wurde gesagt: but I can confirm it's doable in 519 characters of python 3 code ;) I don't think I can golf mine much more- CensoredUsername
Stephen
Ich war hoffnungslos naiv, als ich das sagte. Trotzdem war der garantierte Golfwettbewerb ziemlich amüsant. Auch @cairdcoinheringaahing, die print-Anweisung von Python 2 ist eine Anweisung, kein Ausdruck und kann daher nicht für ein Listenverständnis verwendet werden. Dies würde bedeuten, dass der Oneliner oben in mehrere eingerückte Zeilen aufgeteilt werden muss, wodurch der 2-Byte-Gewinn durch das Entfernen ungültig wird.
CensoredUsername
4

Python 2 , 731 Bytes

i=raw_input
l=i()
c=[]
while l:c,l=c+[l],i()
p=[[0]*len(l)for l in c]+[[0]*max(map(len,c))]
S=lambda r,C,p:r>=0and C>=0and r<len(p)and C<len(p[r])
def U(r,C,P,D,N=0):
 if S(r,C,p):p[r][C]+=P
 if S(r,C,c):
	K=c[r][C]
	if K in' O':U(r+1-N,C+D*N,P,D,N)
	elif'v'==K:U(r+1,C,P,D)
	elif'-'==K:U(r,C+D,P,D,N)
	elif'^'==K:U(r,C-1,P/2,-1);U(r,C+1,P/2,1)
	elif'/'==K:U(r,C-1,P,-1)
	elif'\\'==K:U(r,C+1,P,1)
	elif'='==K:U(r,C+D,P,D,1)
	elif'>'==K:U(r,C+1,P,1,1)
	elif'<'==K:U(r,C-1,P,-1,1)
	elif'|'==K:U(r,C-D,P,-D)
for r in range(len(c)):
 for C in range(len(c[r])):
	if'O'==c[r][C]:U(r+1,C,1.,1);U(r+1,C,1.,-1)
p=p[-1][::-1]
s=16/max(p)
f=['#'*min(int(n*s),16)+' '*min(int(16-n*s),16)for n in p]
print('\n'.join(map(''.join,zip(*f)))[::-1])

Probieren Sie es online!

-17 bytes dank caird coinheringaahing

-12 Bytes dank Nathan Shiraini

-56 Bytes durch Umschalten auf gemischte Einrückung (Python 2)

-28 Dank an CensoredUsername, da die Wahrscheinlichkeiten am Ende normalisiert sind, sodass es nicht erforderlich ist, dass die Endwahrscheinlichkeiten immer 1 ergeben.

-7 Bytes dank Calculator Feline mit einer kürzeren Endung elif.

-218 Bytes durch Zusammenführen der beiden Funktionen

HyperNeutrino
quelle
1052 Bytes
Caird Coinheringaahing
@cairdcoinheringaahing Richtig, danke.
HyperNeutrino
2
Bei Anrufen nach Rund Lwie R(r+1-N,C+N,P,N=N)(erster Anruf nach R) brauchen Sie das N=am Ende nicht. es sollte R(r+1-N,C+N,P,N)stattdessen sein.
Nathan.Eilisha Shiraini
@ NathanShiraini Richtig, danke.
HyperNeutrino
... du hast einiges vergessen. Die letzten 2 Zeilen von beiden Lund R^^ Außerdem ist Ihre zweite Einrückungsstufe überall 4 Leerzeichen, ich denke, Sie könnten es zu 2 machen.
Nathan.Eilisha Shiraini
3

C 569 568 556 Bytes

Golf gespielt

#define A s[1]
#define c(i,j,k) break;case i:x=j;y=k;
w,S,i,j,d,x,y,z;main(int*a,char**s){w=strchr(&A[1],'|')+2-A;a=calloc(w,4);for(;i++<'~~';j=0){for(;A[j];){if(A[z=j++]==79){d=rand()%2;x=4;y=7;z+=w;for(;z<strlen(A);){z+=x%3-1+(y%3-1)*w;switch(A[z]){case 85:goto e;c(32,x/3*(3+1),y/3*(3+1))c(45,d*2+3,7)c(94,(d=rand()%2)*2+3,7)c(118,4,8)c(47,3,7)d=0;c(92,5,7)d=1;c(124,(d=!d)*2+3,7)c(60,x,y)case 62:d=A[z]/2%2;case 61:x=d*8;y=4;}}a[z%w]++;e:;}}}for(i=-1;++i<w;S=a[i]>S?a[i]:S);for(j=17;j-->1;puts(""))for(i=0;i<w-1;printf("%c",a[i++]*16./S+0.6<j?32:35));}

Ungolfed

//Variable Definitions
//direction - marbles current direction, 0 -> left, 1-> right
//arrwidth - width of array
//x - change in x of marble in base 3 - 0 -> Left, 1 -> stay, 2-> right
//y - change in y of marble in base 3 - 0 -> Up, 1 -> stay, 2-> Down
//z - position of marble
//i - iterator on runs of program
//j - iterator on string
//k - iterator on outputstring
//argc - array holding all buckets

#define c(i,j,k) break;case i:x=j;y=k;

arrwidth,scale,i,j,direction,x,y,z;

main(int *argc, char**argv){
  arrwidth=strchr(&A[1],'|')+2 - A; //get width
  argc=calloc(arrwidth,4);
  for(;i++<'~~';j=0){
    for(;A[j];){
      if(A[z=j++] == 79){ //if it finds an O, start sim
        direction=rand()%2;
        x=4;
        y=7;
        z+=arrwidth;
        for(;z<strlen(A);){
          z+=x%3-1 + (y%3-1)*arrwidth;
          switch (A[z]){
            case 85://marble dies dont record
              goto e;
            c(32,x/3*(3+1),y/3*(3+1)) //case ' '
            c(45,direction*2+3,7)    //case -
            c(94,(direction=rand()%2)*2+3,7)    //case ^
            c(118,4,8)    //case v
            c(47,3,7)    //case /
              direction=0;
            c(92,5,7)   //case '\'
              direction=1;
            c(124,(direction=!direction)*2+3,7)
            c(60,x,y)    //case <
            case 62:    //case >
              direction=A[z]/2%2;
            case 61:  //case =
              x=direction*8;
              y=4;
          }
        }
        argc[z%arrwidth]++;
        e:;
      }
    }
  }
  //get output answer in terms of '#'
  for(i=-1;++i<arrwidth;scale=argc[i]>scale?argc[i]:scale);
  for(j=17;j-->1;puts(""))
    for(i=0; i < arrwidth-1;printf("%c",argc[i++]*16./scale+0.6<j?32:35));
}

Bearbeitungen

12 Bytes durch Ändern meines Fallmakros gespart.

Anmerkungen

Mein Code verwendet ein System von Ganzzahlen zur Basis 3, um zu bestimmen, wohin der Marmor geleitet wird und wohin er geleitet wird (für Kanonen und andere Dinge).

Ich habe versucht, diese Python-Lösung zu schlagen, das habe ich wirklich getan.

dj0wns
quelle
1
Ich zähle 568 Bytes; Vielleicht haben Sie die nachgestellte Zeile gezählt? Und verdammt, ich fühle mich schlecht; in Python von C outgolfed? Meine Güte ...: P
HyperNeutrino
Sie haben Recht, ich habe einen nachgestellten Newling in der Datei hinterlassen. Vielen Dank!
dj0wns