43
\$\begingroup\$

Consider this ASCII version of a mechanism similar to a bean machine or plinko/pachinko game:

    O

    ^
   \ ^
  ^ ^ \
 \ ^ / ^
U U U U U
1 2 3 4 5

The O is a ball that falls down.

  • When it hits a ^, there's a 50-50 chance it will go left or right.
  • When it hits a /, it always goes left.
  • When it hits a \, it always goes right.

The ball eventually falls into one of the numbered U troughs at the bottom. The question is, what is the probability it will end up in each trough?

For this particular case, the probabilities are 0.0, 0.1875, 0.5625, 0.125, and 0.125, for troughs 1 through 5 respectively.

Here's another example with 3 troughs instead of 5. The probabilities are 0.5, 0.5, and 0.0:

  O

  /
 ^ ^
U U U
1 2 3

In this challenge we will generalize this problem to a mechanism with any number of layers set up in any fashion.

Challenge

Write a program or function that takes in the ASCII representation of the pyramid structure of the mechanism. (Input via stdin/command line/function arg.)

You may either assume it comes in with spaces that put it in the proper shape, e.g.

   ^
  \ ^
 ^ ^ \
\ ^ / ^

Or you may assume it comes in with no spaces at all, e.g.

^
\^
^^\
\^/^

(If desired, you may assume there is a trailing newline and/or some consistent pattern of trailing spaces.)

The input pyramid structure may have any number of levels (aka lines), including zero. Each level has one more ^, /, or \ than the last, and there are levels + 1 troughs at the bottom (which aren't part of the input).

You program/function must print/return the list of the probabilities that the ball lands in each of the troughs (in the order leftmost trough to rightmost trough). These should be floating point values that, when printed, have at least 3 decimal places (superfluous zeros or decimal points are not required; 1 is fine for 1.000, .5 is fine for 0.500, etc.). If you wrote a function, you may print the values or return a list/array of the floats.

Any reasonable printed list format is fine. e.g. 0.5 0.5 0.0, [0.5 0.5 0.0], [0.5, 0.5, 0.0], {0.5, 0.5, 0.0}, or 0.5\n0.5\n0.0 would all be alright.

Examples

0 Levels: (boils down to one trivial U)

Input: [no input/empty string given]
Output: 1.0

1 Level:

Input: ^
Output: 0.5 0.5

Input: /
Output: 1.0 0.0

Input: \
Output: 0.0 1.0

2 Levels: (second example above)

Input:

 /
^ ^

Output: 0.5 0.5 0.0

3 Levels:

Input:

  ^
 ^ ^
^ ^ ^

Output: 0.125 0.375 0.375 0.125

Input:

  \
 / \
/ / \

Output: 0.0 0.0 0.0 1.0

4 Levels: (first example above)

Input:

   ^
  \ ^
 ^ ^ \
\ ^ / ^

Output: 0.0 0.1875 0.5625 0.125 0.125

7 Levels:

Input:

      ^
     / ^
    ^ ^ /
   / \ / \
  ^ ^ / ^ \
 ^ \ ^ \ / ^
\ ^ ^ ^ \ ^ /

Output: 0.0 0.09375 0.28125 0.4375 0.1875 0.0 0.0 0.0

Scoring

The shortest answer in bytes wins. Tiebreaker is earlier post.

\$\endgroup\$
8
  • 17
    \$\begingroup\$ Quincunx had better answer this. \$\endgroup\$ May 5, 2015 at 4:53
  • \$\begingroup\$ "some consistent pattern of trailing spaces" - may I assume that the trailing spaces on the Nth line encode the probability for the ball to land in the Nth bucket? \$\endgroup\$
    – Random832
    May 5, 2015 at 19:09
  • 5
    \$\begingroup\$ @Random832 No. (Do you really think that would fly?) \$\endgroup\$ May 5, 2015 at 19:15
  • \$\begingroup\$ There's a reason I posted it as a comment instead of an answer. I just thought it was interesting how permissive this puzzle was about input - most that I've seen dictate the format of the input and/or output more strictly. \$\endgroup\$
    – Random832
    May 5, 2015 at 19:16
  • \$\begingroup\$ @Random832: The input and output are very unambiguous. Standard loopholes (like encoding the answer in the input) don't need to be addressed in every challenge. \$\endgroup\$
    – Alex A.
    May 6, 2015 at 0:05

10 Answers 10

15
\$\begingroup\$

Ruby 140

->s{r=[1.0]
s.lines.map{|l|n=[i=0.0]*(r.size+1)
l.scan(/\S/).map{|e|a,b=e>?/?e>?]?[0.5]*2:[0,1]:[1,0]
z=r[i]
n[i]+=z*a
n[i+=1]+=z*b}
r=n}
r}

Function that takes as input the string (can be nicely formatted as a pyramid) and returns an array of floats.

Test it online: http://ideone.com/kmsZMe

Pretty straightforward implementation. Here it is ungolfed:

F = -> input {
  probabilities = [1.0]

  input.lines.each { |line|

    new_probabilities = [0.0] * (probabilities.size+1)
    elements = line.scan /\S/
    elements.map.with_index{|el, i|
      deltas = el > '/' ? (el > ']' ? [0.5,0.5] : [0,1]) : [1,0]

      d1, d2 = deltas

      new_probabilities[i] += probabilities[i] * d1
      new_probabilities[i + 1] += probabilities[i] * d2
    }
    probabilities = new_probabilities
  }
  return probabilities
}
\$\endgroup\$
13
\$\begingroup\$

Ruby, 140 158 bytes

Don't keep upvoting this when there's a better ruby version. Here are more tricks for you.

Unnamed function with one argument. Must not contain any spaces. May or may not contain a trailing newline.

->s{Z=(s.split'
')<<[]
K=[]
F=->i,j,f{k=Z[i][j]
K[i]||=0
k==?^?2.times{|m|F[i+1,j+m,f/2]}:!k ?K[j]+=f :F[i+1,j+(k==?/?0:1),f]}
F[0,0,1.0]
K}

Wastes 9 bytes on having to handle 0 levels (empty string). All test cases work out correctly, see here at ideone.

\$\endgroup\$
2
  • 4
    \$\begingroup\$ Just because there's a "better" Ruby answer doesn't mean yours (or any other Ruby answer for that matter) isn't worth votes. :) \$\endgroup\$
    – Alex A.
    May 5, 2015 at 14:36
  • \$\begingroup\$ I upvoted this myself because it contains some nice tricks. I like your multiline split, for example. \$\endgroup\$ May 6, 2015 at 6:29
12
\$\begingroup\$

Pyth, 43 42 41 bytes

umsdc+0sm@c[ZJhkJZKcJ2K)2x"\/"ekC,GH2.z]1

This expects the input to be without spaces. Try it online: Pyth Compiler/Executor

Pyth, 40 bytes (questionable)

umsdc+0sm,K@[ZJhkcJ2)x"\/"ek-JKC,GH2.z]1

Thanks to @isaacg, for saving one byte. Notice that this version didn't actually work in the version of Pyth, when the question was asked. There was a tiny bug in the compiler. Despite this code uses no new features of Pyth (only stuff that was in the Pyth docs for a long time and should have worked), this might not be a valid answer. Decide for yourself.

Try it online: Pyth Compiler/Executor

Explanation:

umsdc+0sm,K@[ZJhkcJ2)x"\/"ek-JKC,GH2.z]1   
u                                   .z]1  reduce G, starting with G = [1], for H in all_input():
                               C,GH         zip(G,H)
        m                                   map each pair k to:
            [ZJhkcJ2)                         create a list [0, k[0], k[0]/2]
                     x"\/"ek                  index of k[1] in "\/" (-1 for "^")
          K@                                  take the correspondent element of the list and store in K
         ,                  -JK               create a pair (K, k[0]-K)                                                      
     +0s                                    sum and insert 0 at the begin
    c                              2        chop into pairs
 msd                                        sum up each pair
                                            G gets updated with this new list

For instance if I currently have the input probabilities G = [0.5, 0.5, 0.0] and the row H = "^/^" the following happens:

  • zip ... [(0.5,"^"), (0.5,"/"), (0.0,"^")]
  • create output probabilities ... [[0.25,0.25], [0.5,0.0], [0.0, 0.0]]
  • 0+sum ... [0, 0.25, 0.25, 0.5, 0.0, 0.0, 0.0]
  • chop ... [0,0.25], [0.25,0.5], [0.0,0.0], [0.0]]
  • sum ... [0.25, 0.75, 0.0, 0.0]
\$\endgroup\$
5
  • 3
    \$\begingroup\$ I was trying to golf this, and it led me to a bug in the compiler. The golf works, now that I've fixed the bug. The golf is to replace the list of 2-value lists with one list, and then generate the other value by subtracting the first value from hk. ,K@[ZJhkcJ2)x"\/"ek-JK \$\endgroup\$
    – isaacg
    May 6, 2015 at 7:20
  • 1
    \$\begingroup\$ This is really a fine line when you fixing a bug is not being counted as a newer version of the language (and thus is still valid for questions asked before the fix) \$\endgroup\$
    – Optimizer
    May 6, 2015 at 9:03
  • 1
    \$\begingroup\$ @Optimizer Your right. Added some notes to the answer, that explains the circumstances. \$\endgroup\$
    – Jakube
    May 6, 2015 at 9:23
  • 2
    \$\begingroup\$ @Optimizer In this case, it seems like a good rule of thumb is whether it's really a newer version of the language or a newer version of the language implementation that fixes a bug, bringing the implementation closer into line with the spec. \$\endgroup\$
    – Desty
    May 6, 2015 at 13:29
  • \$\begingroup\$ @Desty That is why I mentioned that its a fine line ;) \$\endgroup\$
    – Optimizer
    May 6, 2015 at 14:24
10
\$\begingroup\$

CJam, 50 48 45 44 42 40 bytes

1]q{iD%"(+0 0+( (\Y/::+ (d2/_a+"S/=~+}/p

This expects the input to be without space and have a trailing newline. For example:

^
\^
^^\
\^/^

[0 0.1875 0.5625 0.125 0.125]

Algorithm

The basic idea is that you keep on parsing each character (there are only 4 different characters) and perform different operations on the probability distribution (initially an array containing 1 element of value 1). For each row of input characters (starting with the first character on first row), we maintain a probability array of that same size. Each character acts upon the first probability from the list and pushes the resultant pair to the end of the list. After each line, we sum up pairs from the list to get exact number of items as the items on the next line.

Here are the four characters and the required actions corresponding to each:

  • ^ : When this character occurs, you split the current probability to two parts. For example, if we have this on the first line, we have to convert the [1] to [0.5 0.5]
  • / : When this characters occurs, we have to put <current probability> 0 in place of the current probability in the array.
  • \ : When this characters occurs, we have to put 0 <current probability> in place of the current probability in the array.
  • \n : When this character occurs, we have a new line. Thus we group together all pairs from above 3 characters and sum them up to get probability of each item for the next line. For ex. [0 0.5 0.25 0.25] gets converted to [0 0.75 0.25]. Note that the first and last items have an implicit pair (valued 0) before and after them.

Now we only have to identify the right character and perform the right action. Lets use the usual maths here to do that. The ASCII codes for ^, \, / and \n are 94, 92, 47, and 10. After a few trials, we get this simple equation to convert these numbers into 0, 1, 2 and 3:

"^\/
":ied13f%ed4f%ed

gives:

Stack: [[94 92 47 10]]
Stack: [[3 1 8 10]]
Stack: [[3 1 0 2]]
3102

In an array of length 4, the last 4f% would be implicit. So we simply do %13 to the ASCII code of the character and choose the right action from an array of actions.

Code explanation:

1]                                 e# Initial probability array with 1 probability
  q{                          }/   e# Read the whole input and iterate char by char
    iD%                            e# mod the ASCII code of the character with 13
"(+0 0+( (\Y/::+ (d2/_a+"S/        e# This is our actions array in order of [\ / \n ^]
                           =~      e# We pick the correct action and eval it
                             +     e# Evaling each action will leave one number out of the
                                   e# pairs out of the array. So we put it back in
                                p  e# Print the final probability array

Try it online here

\$\endgroup\$
3
8
\$\begingroup\$

C#, 274 247 bytes

Nothing fancy, complete program that reads lines (with or without spaces, it just strips them) in from STDIN, and prints space separated results to STDOUT.

using Q=System.Console;class P{static void Main(){decimal[]k={1},t;string L;for(int l=0,i;(L=Q.ReadLine())!=null;k=t)for(L=L.Replace(" ",""),t=new decimal[++l+1],i=0;i<l;)t[i]+=k[i]-(t[i+1]=(8-L[i]%8)/2*k[i++]/2);Q.WriteLine(string.Join(" ",k));}}

Tidier code with comments:

using Q=System.Console;

class P
{
    // / 47
    // \ 92
    // ^ 94

    static void Main()
    {
        decimal[]k={1},t; // k is old array, t is new array

        string L; // L is the current line, R is the current result (1 if no rows)
        for(int l=0,i; // l is length of old array, i is index in old array
            (L=Q.ReadLine())!=null; // for each line of input
            k=t) // swap array over
            for(L=L.Replace(" ",""), // remove spaces
                t=new decimal[++l+1], // create a new array
                i=0;

                i<l;) // for each position

                t[i]+=k[i]-( // add to left position (for last time)
                        t[i+1]=(8-L[i]%8)/2*k[i++]/2 // assign right position (k is decimal)
                    );

        Q.WriteLine(string.Join(" ",k)); // print result
    }
}
\$\endgroup\$
7
\$\begingroup\$

Python 3, 113

P=[1]
for C in input().split():
 l,*Q=0,
 for p,c in zip(P,C):r=p*"\^/".find(c)/2;Q+=l+r,;l=p-r
 P=Q+[l]
print(P)

Repeatedly updates the probability vector P in response to each line. This new probability vector Q is created one entry at a time. Iterates through the new slots, and computes the contribution from the peg to its right as r, while also computing the remaining contribution to the upcoming slot as p-r.

Expects each line to end in at least one space to avoid an issue where lines end in a backslash.

\$\endgroup\$
3
  • \$\begingroup\$ The input will have multiple lines so I don't think a single input() can handle that. \$\endgroup\$
    – randomra
    May 6, 2015 at 19:13
  • \$\begingroup\$ a trailing newline is not required for each line of the input. \$\endgroup\$ May 7, 2015 at 1:52
  • \$\begingroup\$ @randomra I wrote this in Idle and it worked fine putting in multi-line inputs to the shell prompt. \$\endgroup\$
    – xnor
    May 7, 2015 at 6:28
6
\$\begingroup\$

Python 3, 138 bytes

def f(s):
 r=[1];p=t=0
 for e in s:
  if'!'<e:b=p==t*-~t/2;r+=[0]*b;t+=b;v=ord(e)%7+1;a=r[p]/2;r[-1]+=v//3*a;r+=v%3*a,;p+=1
 return r[~t:]

Works with any whitespaces as they are all filtered out (by if'!'<e).

Method:

  • We keep an ever expanding list r of the probabilities of reaching any obstacles and the implicit troughs below them. We start from the list [1].
  • If we are at the first obstacle in a row we need to add an extra 0 to the list for the leading trough. We decide if it is the first obstacle by comparing its index p to the next triangular number t*-~t/2.
  • For every obstacle we add its list-value partially to the last element and partially to a new trailing element. We divide the list-value based on the obstacle character (^:0.5 0.5; /:1 0; \:0 1). We use the following method:
    • Take v = ord(char) mod 7 + 1 yielding ^:4 /:6 \:2
    • v div 3 / 2 yields the first fraction (^:0.5 /:1 \:0)
    • v mod 3 / 2 yields the second fraction (^:0.5 /:0 \:1)
  • The result is the last t + 1 elements of the final list r.

2 bytes thanks to @Sp3000's chat advice.

\$\endgroup\$
4
\$\begingroup\$

Perl, 78

#!perl -p0a
@r=($/=1);$^=.5;@r=map$r-$l+($l=$$_*($r=shift@r)),/./g,$r=$l=0for@F;$_="@r"

Takes input without spaces.

Try me.

\$\endgroup\$
1
\$\begingroup\$

TI-BASIC, 73 76

Takes input one line at a time, and ends when a space is entered on its own, because neither line breaks in strings nor empty strings are legal in TI-BASIC.

{1→X
Input Str1
While Str1≠"  //one space
.5seq(inString("^/",sub(Str1,I,1)),I,1,dim(Ans
augment(Ans∟X,{0})+augment({0},∟X-∟XAns→X
Input Str1
End
∟X

I'm pretty sure I got the size right (TI-BASIC is tokenized, so each command takes either one or two bytes—seq() takes one, inString() takes two, dim() takes one, and so on. I counted the size manually.)

Although the backslash character is valid in a string, note that there is no way to input one from inside the program unless you have modified your calculator.

\$\endgroup\$
0
\$\begingroup\$

Javascript - 117

Tried using recursion, but that was too long...

Hat tip to xnor for the subtraction idea, which shaved off a dozen or more characters.

w=s=>{a=[1];s.split('\n').map(m=>{for(b=[i=0];z=a[i],f=m[i];b[i++]+=z-b[i])b[i+1]=f>']'?z/2:f<':'?0:z;a=b})
return a}

Ungolfed:

// s must not have spaces
w=s=>{
  // a is the current probability array
  a=[1];
  s.split('\n').map(
    // for each row of input...
    m=>{
      b=[0];  // b is the next row's probability array
      for(i=0; i<m.length;){
        z=a[i]; // z = probability
        f=m[i]; // f = letter
                                  // let's assume i == 0
        b[i+1] = (f>']') ? z/2 :  // if f == '^', b[1] = z/2
          (f<':' ? 0 :            // else if f == '/', b[1] = 0 
            z);                   // else b[1] = z
        b[i++]+=z-b[i];           // then add (z-b[1]) to b[0]
      }
      a=z-b    // increment current probability array
    }
  )
  return a;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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