Pascal's Bagatelle Beginner Coder Challenge

[rogster001]

Hi all,

Well i quite liked this one, i saw a maths demo on TV the other day, and thought it would be neat to write, then saw it actually makes for a good little programming problem for beginners methinks.

As I say, I am aiming it at beginners to have a go at. it is probably trivial for more advanced coders, but might provide some interest, I dont really consider myself advanced, but i know this has thrown up some wider project ideas for me at least.

Am keeping open for two weeks, winner is first correct working code sent to me by PM. That satisfies the requirements.
Output validation will be based on the expected distribution for the given parameters.

Sorry i can only accept win console.
Limit of 100 lines actual code, which should be plenty.
C or C++

It is worked around Pascal's triangle but as if it were set in a Bagatelle board where you ping a ball up like pinball and then it drops down into a field of pins and you win money depending where it lands.

This problem requires you to model the outcome of such a game in terms of the landing position of the ball.
As each new ball is dropped into the field then it will bounce off the pins and enventually end up in one of the columns at the bottom, see image:

http://img201.imageshack.us/img201/3...lbagatelle.jpg

In the image shown there are 4 columns for this size 'pin field', the arrow shows where a ball is dropped in, then it hits the first pin, and so on, until it finally lands in one of the four possible columns.

Your challenge is to write a program that can simulate this game and show the expected distribution of balls across the columns.

Your program must accept input for the base triangle size, (in the example this would be 3, ie three pins) and successfully show the outcome for the resulting number of columns required for the given base size.

That is to say your program must be able to scale its operation to any size field..

I am not asking for input validation as such, but it should be obvious that the minimum input has to be two.

set number of balls as twenty times your base input, this is just to keep the distribution values up.

Your output must be stored in an array, vector, or other container,number of elements equal to the columns required. - no bigger.

Display output will be:

A simple win console

request input triangle base size
display the value.
display the ball count

//start working part of program..
then:

The final display should just be a loop outputting each value in the container.with a pipe seperator

follwed by a sum of the column values which should be equal to the amount of balls used.

EG:

for(int i = 0; i < columns; i++)
{
    //print columns[i] and seperator
    //add columns[i] to check_total
    
}
//print check_total =

so it might look like:

input base: 5
ball count 100

..working..

output:
| 2 | 16 | 27 | 36 | 14 | 5 |

check total balls distributed: 100

[rogster001]

I have received a candidate winner but I think it may be beaten on a technicality.. so am keeping open for now to allow amendments or more entries to challenge.
Based on the feedback received and some of my thinking since re-reading my post i will clarify a couple of points:

one input for the base number of pins (ie triangle size) in the equilateral triangle that forms the obstacles field - everything else is determined programatically, the layout of the pins follows the pattern shown in the image.
Line limit i feel is generous and should encourage beginners to use concise code and suitable constructs - bear in mind it is actual code lines limit, not text layout length
Just in case anyone is digging out the physics engine library, It is simple probability for the paths, no physical effects per se need to be modelled. you just have to imagine a ball dropped in hitting the first pin, then it falls down to the next level hitting one of the two pins on the second level, depending on which direction it fell from the first pin, and so on down until it exits and falls into one of the containers

[rogster001]

Congratualtions to jdragyn! The winner of this challenge!
jdragyn submitted the most complete response to the question that i received, a nice bit of code with a neat method to calculate the ball position as it moves through the pin field, well within the line limit boundary and with the output distribution correct.

Congrats !

winning code nicely commented, posted here with permission:

/* jdragyn.c

implementation of Pascal's bagatelle for rogster001's contest at cboard

http://cboard.cprogramming.com/contests-board/148958-pascals-bagatelle-beginner-coder-challenge.html

*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int drop_ball(int count);

int main()
{
    int base_size = 0;
    int columns = 0;
    int *column = 0;
    int balls = 0;
    int i=0;

    srand ( time(NULL) );    
    
    /* get triangle size and figure everything else out */
    printf("\nbase size: ");
    scanf("%d", &base_size);
    
    /* If the triangle doesn't exist, just stop. */
    if(base_size < 1)
    {
        printf("\nReally?\n\n");
        exit(1);
    }
    
    balls = 20 * base_size;

    printf("ball count %d\n\n..working..",balls);

    columns = base_size +1;    
    column = malloc(columns * sizeof(int));
    if(!column)
    {
        printf("\n\nFailed malloc()...!");
        exit(1);
    }
    for(i=0; i< columns; ++i) 
        column[i]=0;

    /* drop the balls! */        
    for (i=0; i<balls; ++i)
    {
        int col = drop_ball(columns);
        ++column[col];
    }
    
    /* show the results */
    printf("\n\noutput:\n|");
    balls = 0;
    for (i=0; i<columns; ++i)
    {
        printf("%d|",column[i]);
        balls += column[i];
    }
    printf("\n\ncheck total balls distributed: %d\n", balls);

    free(column);
    return 0;
}

/* drop_ball()
 *
 * Given:
 *   the number of columns
 * 
 * Simulates dropping the ball on the center pin
 * at the top with a 50/50 chance of going left
 * or right on each pin.
 *
 * Returns the column that the ball will fall into
 */
int drop_ball(int count)
{
    int spots = count * 2;
    int cur_spot = count - 1;
    int i = 0;

    for (i = 0; i < count - 1; ++i)
        if ((rand() % 100) < 50)
            --cur_spot;
        else
            ++cur_spot;
    
    return cur_spot / 2;
}

A mention should go to whiteflags who was first through with a very good answer, that was acheived in a very compact program of around fifty actual lines, great work, I only failed it as it requested input for the number of balls in the game, which i had stated should be done programatically, a minor technicality i know..but a very worthy second place to whiteflags.

[jdragyn]

Hmmm, was trying to do the drop_ball() without a division and here's the first thing that comes to mind, though it is a cheap cop-out. heh

Still thinking about a truly division-less version. Also noticed that I have a spots variable that I don't actually use (or need).

int drop_ball(int count)
{
    float cur_spot = count * 0.5f; /* cheap cop-out to technically avoid division */
    int i = 0;

    for (i = 0; i < count - 1; ++i)
        if ((rand() % 100) < 50)
            cur_spot -= 0.5f;
        else
            cur_spot += 0.5f;
    
    count = cur_spot;
    return count;
}

Edit...
Ah hah! Here it is, no division and no cop-outs.

int drop_ball(int count)
{
    int cur_spot = 0;
    int i = 0;

    for (i = 0; i < count - 1; ++i)
        if ((rand() % 100) > 49)
            ++cur_spot;
    
    return cur_spot;
}

[whiteflags]

A mention should go to whiteflags who was first through with a very good answer, that was acheived in a very compact program of around fifty actual lines, great work, I only failed it as it requested input for the number of balls in the game, which i had stated should be done programatically, a minor technicality i know..but a very worthy second place to whiteflags.

Yeah well I don't want to be a noodle incident. For those curious, this was my code.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
double uniform_deviate (int seed)
{
	return seed * ( 1.0 / ( RAND_MAX + 1.0 ) );
}
void plinko (int buckets[], int nBuckets, int balls)
{
	int i, ball, rightBounce;
	srand((unsigned long)time(NULL));
	for(ball = 0; ball < balls; ball++) {
		rightBounce = 0;
		for(i = 0; i < (nBuckets - 1); i++) {
			if(uniform_deviate(rand()) > 0.5) {
				++rightBounce;
			}
		}
		++buckets[rightBounce];
	}
}
int main ()
{
	int nBuckets = 0;
	int balls = 0;
	int sum = 0;
	int *buckets = NULL;
	printf("enter the number of bottom pins: ");
	scanf("%i", &nBuckets);
	printf("enter the number of balls: ");
	scanf("%i", &balls);
	++nBuckets;
	if((buckets = calloc(nBuckets, sizeof buckets[0])) != NULL) {
		int i;
		plinko(buckets, nBuckets, balls);
		printf("\n\n|");
		for(i = 0; i < nBuckets; i++) {
			sum += buckets[i];
			printf("%d|", buckets[i]);
		}
		printf("\n\ncheck sum = %d\n", sum);
		free(buckets);
	} else {
		printf("Memory allocation failure\n");
	}
	return 0;
}