26
\$\begingroup\$

A classic example to introduce people to the concept of a discrete probability distribution is the bean machine. This machine has a large amount of marbles fall from a narrow passageway at the top, after which they hit rows of interlaced pins, where at each pin the marble hits it might fall to the left or the right of the pin. Finally, the pins are collected in vertical bins at the bottom of the machine. A simple diagram of this machine looks like this:

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

In this diagram, the O signifies the location from which the marbles fall. Each ^ is a pin at which the marble has a 50% chance to move to the square either to the left or the right of the pin. The marbles then gather at the bins on the bottom of the device, and for a large enough number of marbles, the height of the marble stacks in the bins will resemble a discrete binomial distribution.

Challenge

For this challenge, you will be calculating the resulting probability distribution of bean machines based on diagrams like the above one. The diagrams are interpreted as a two-dimensional 'program' that the marbles pass through, either towards fields at the side or fields below the current field. When the marbles reach the bottom of the machine they are counted for the probability distribution. To keep it interesting, these diagrams will contain a few more fields than just the simple source and pins. An example diagram is:

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

Furthermore, the marbles now each have a rotation direction. This direction is set by some fields and determines to which next field the marble moves in several other fields.

The following fields are defined:

  • O: Source. Spawns marbles directly below it. The direction of these marbles is 50% left, 50% right. Each source produces the same amount of marbles.
  • U: Sink. Any marbles which enter this field are removed from the bean machine.
  • : Empty space. If a marble arrives at this field, it will move to the field below.
  • -: Floor. If a marble arrives at this field, it will move to either the field to the left or the field on the right, depending on its current direction.
  • ^: Splitter. If a marble arrives at this field, it has a 50% of moving to the field to the right or the field to the left of the splitter. This also determines the direction of the marble.
  • v: Join. If a marble arrives at this field, it will move to the field below.
  • /: Slanted pad. If a marble arrives at this field, it will move to the field on the left of the pad, setting the direction of the marble.
  • \: Same as the previous, but to the right.
  • |: Reflector. If a marble arrives at this field, it will reverse the direction of the marble, and move the marble to the field to the right or the left, based on this reversed direction.
  • =: Cannon. If a marble arrives at this field, it will move it to the right or the left in the current direction, until the marble encounters a field that is not , - or O.
  • <: Same as the previous, but will always set the direction and move towards the left.
  • >: Same as the previous, but to the right.

The following guarantees are given regarding the diagram.

  • Each input row will have exactly the same length in fields.
  • The leftmost and rightmost field of each row will always be a |.
  • The diagram will not contain any possible paths through which marbles can get stuck in the machine for an indeterminate amount of iterations, like \/ or ^^.
  • The diagram will only contain the above mentioned fields.
  • There are one or more sources

Result

Your task will be to generate an 16-line tall ASCII bar graph of the probability distribution in which the marbles exit the bottom side of the graph, scaled so the largest probability covers all 16 characters. So for the following problem:

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

Your program should produce the following solution (note that it should have the same width as the input program, including the pipes to the side:

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

Examples

The following is an example that should test the functionality of all different field types:

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

It should result in the following output:

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

Rules

Both functions and full programs constitute valid answers for this challenge. You will receive the diagram as a newline-separated string, and you should return the output graph in the given format. Default input/output rules apply. While trailing and leading newlines are allowed in the output, each row should have exactly the same width as the input.

As to allow more creative solutions, it is only required that your program outputs the correct result more than 90% of the time for the same diagram. It is a probability simulation after all.

Scoring

This is , so the lowest score in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Much simpler but related. \$\endgroup\$ – Peter Taylor Jun 28 '17 at 16:25
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Dennis Jun 30 '17 at 18:58
  • \$\begingroup\$ so v = [space]? \$\endgroup\$ – l4m2 May 16 '18 at 0:48
  • \$\begingroup\$ @l4m2 v and [space] differ in how cannons interact around them. \$\endgroup\$ – CensoredUsername May 16 '18 at 14:46
8
\$\begingroup\$

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

Try it online!

This answer is a collaborative effort between Wheat Wizard and CensoredUsername. For reference, this is the ungolfed algorithm.

-2 bytes from Mr. Xcoder

-19 bytes from CensoredUsername

\$\endgroup\$
  • \$\begingroup\$ -2 bytes if you switch to Python 2 (print statement)? \$\endgroup\$ – caird coinheringaahing Jun 29 '17 at 18:19
  • 1
    \$\begingroup\$ Of this was said: 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 \$\endgroup\$ – Stephen Jun 29 '17 at 18:20
  • \$\begingroup\$ I was hopelessly naive when I said that. That said, the ensuring golfing competition was quite amusing. Also @cairdcoinheringaahing, python 2's print statement is a statement, not an expression and it can therefore not be used in a list comprehension. This would mean that the oneliner at the top has to be split up into several indented lines which would make the 2 byte gain from removing it void. \$\endgroup\$ – CensoredUsername Jun 29 '17 at 20:27
4
\$\begingroup\$

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])

Try it online!

-17 bytes thanks to caird coinheringaahing

-12 bytes thanks to Nathan Shiraini

-56 bytes by switching to mixed indentation (Python 2)

-28 thanks to CensoredUsername because the probabilities are normalized in the end, so it's not necessary that the end probabilities always add up to 1.

-7 bytes thanks to Calculator Feline by using a shorter ending elif statement.

-218 bytes by merging the two functions

\$\endgroup\$
  • \$\begingroup\$ 1052 bytes \$\endgroup\$ – caird coinheringaahing Jun 29 '17 at 6:26
  • \$\begingroup\$ @cairdcoinheringaahing Right, thanks. \$\endgroup\$ – HyperNeutrino Jun 29 '17 at 6:56
  • 2
    \$\begingroup\$ In calls to R and L like R(r+1-N,C+N,P,N=N) (first call to R), you don't need the N= at the end; it should be R(r+1-N,C+N,P,N) instead. \$\endgroup\$ – Nathan.Eilisha Shiraini Jun 29 '17 at 11:07
  • \$\begingroup\$ @NathanShiraini Right, thanks. \$\endgroup\$ – HyperNeutrino Jun 29 '17 at 14:02
  • \$\begingroup\$ ... you forgot some. The last 2 line of both L and R ^^ Also, your second level of indentation is 4 spaces everywhere, I think you could make it 2. \$\endgroup\$ – Nathan.Eilisha Shiraini Jun 29 '17 at 14:19
3
\$\begingroup\$

C, 569 568 556 Bytes

Golfed

#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));
}

Edits

Saved 12 bytes by changing my case macro.

Notes

My code uses a system of base 3 integers to determine where the marble is headed and will be headed after (for cannons and stuff).

I tried so had to beat that python solution, I really did.

\$\endgroup\$
  • 1
    \$\begingroup\$ I count 568 bytes; maybe you counted the trailing newline? And darn I feel bad; outgolfed in Python by C? Jeez... :P \$\endgroup\$ – HyperNeutrino Jun 30 '17 at 16:08
  • \$\begingroup\$ You are correct, I left a trailing newling in the file. thanks! \$\endgroup\$ – dj0wns Jun 30 '17 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.