• Post Reply Bookmark Topic Watch Topic
  • New Topic

Bowls and Marbles  RSS feed

 
N Goodie
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have a task which involves a circular arrangement of bowls which are filled with various amounts of marbles (as set by the user).

I have to create an "emptier" method which takes a bowl (at an index point chosen by the user), removes the marbles, and distributes them one-by-one clockwise to the other bowls in the circle, overlapping if necessary. If a bowl is left empty after a move, it is removed.

I also have to create a "solution" method, which performs 'emptier' operations successively until only one bowl is left. I'm supposed to try
every possible move from a given position and repeat this process for every resulting position until reaching a search limit.
It's supposed to involve a loop and recursion.

I'm also supposed to give a performance O estimate for my implementation of the empty operation, based on it's parameters (b - the number of bowls, n - the number of marbles in the bowl to be emptied.


I'm sort of at a point where I'm stuck because I have no idea where to begin with this, so can someone give me a rough idea of the sorting techniques I should use or the way that I should approach this task?

Thank you! ^_^
 
Campbell Ritchie
Marshal
Posts: 56578
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch

At this stage, silicon and its compounds are positively harmful. You need carbon. Graphite, more specifically, as lives in the middle of a pencil. Use the pencil and some paper and get a big eraser, which you will use a lot. Write down in words of one syllable how you would distribute the marbles like that. You may prefer to call them balls, so as to get them into one syllable.
When you have got the process on paper in words of one syllable, it will be much easier to see how you can code it.
 
N Goodie
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thankyou!

It seems like simple advice, but it really has worked quite well.

It seems stupid to ask, but the method header for the 'emptier' method has to have the format:

public Bowls emptier (int index)

...since the data type of the method is 'bowls', this means that Bowls has to be an abstract data type, yes?
 
Mike. J. Thompson
Bartender
Posts: 689
17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
N Goodie wrote:...since the data type of the method is 'bowls', this means that Bowls has to be an abstract data type, yes?


What do you mean by abstract data type? Bowls must be a type that the compiler can see when it compiles your emptier(...) method (so must either be in the same package as the class with the emptier(...) method or it must be imported by that class). Bowls could be an Interface, an abstract Class, a concrete Class (or even a generic Type).

It is generally good practice to program to Interfaces so it would be good if Bowls was an Interface, but that is not enforced by the language.
 
Piet Souris
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
N Goodie wrote:Thankyou!

It seems like simple advice, but it really has worked quite well.

Can you tell us what you have made so far? In what class have you defined the method 'emptier'?
Another question is: if the starting bowl gets empty and is removed, what will be the next bowl
to continue with?

It seems stupid to ask, but the method header for the 'emptier' method has to have the format:

public Bowls emptier (int index)

Have you any idea what class this 'Bowls' must be? Is it for instance a class that represents some collection of bowls
(perhaps containing only the remaining bolws and an indication which bowl to start next)?

And also: have you already figuered out what 'performance O' this game is?

Greetz,
Piet
 
N Goodie
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So far, the emptier method works fine.... now I'm stuck on the solution method.

It needs to use recursion, I'm just not sure where to place it in order to have it run emptier() on each index value of bowls and
then run emptier() on every index of each of the results from the first emptier "move", and so on and so forth until a limit or a solution is reached.




And this is the tester class:

 
Piet Souris
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi N.,

so, how's things going?

I see the problem is different from what I initially thought. I thought it was kind of a game, like the Bao game.
But I read that you must investigate all possible emptier sequences. For what purpose, I don't know.
I have some remarks.

1) it is indeed necessay to impose a limit, otherwise you're bound to end up in an infinite loop, sooner or later. Take
for instance the situation where you have two bowls, with contents (2, 2). Then, starting with bowl 1, you get
(1, 3). If your recursion then starts with bowl 2 (which you will by going through allp ossible sequences), then
you get (3,1). And in another recursion, starting again with bowl 1, you get (1, 3), and so on. By using a limit
you can impose a maximum on the recursion depth.

2) what are you supposed to return or report, when Bowls has a final size of 1 bowl? The sequence and the number
of recurions, couting from the starting bowl?

3) I have no idea why your emptier() method must return a Bowls. The only relevant issue here is the ArrayList, and that
is actually the only thing of importance here. So I would find it more logical if the emptier() method were to have an ArrayList
as parameter, and a level indicator or a limit, do the marble shuffling and then, seeing that there are still more than
one non empty bowl, call emptier again with the latest AL.

4) but there is a snag around. If you do something like:

and use newone for the creation of a new Bowls, then in fact you are only dealing with ONE AL, and all changes
that you make to AL newone, will also reflect in the original AL bowls (i.e. removing an empty bowl).
That will make it impossible to try out all possible sequences, since you've lost your original AL.

I have devised a small application, based on your code, that shows what I mean.
It starts with a Bowls b, with two bowls, and it prints out the whole recursion, both when a new Bowl is created
(see the emptier method), and when it is about to return. You see that in the return cycle, at the end,
that all AL's are equal!

So, what you have to do is to specifically create a copy of the AL of a Bowls, BEFORE creating a new Bowls and
going into the recursion (and use that copy for the new Bowls). A copy can easily be made by


Now, here's my code. You see that I did not go for every possible sequence, I always empty this very first
bowl, a strategy that is certain to end up with just one non empty bowl.
Your code does nicely start with an index in your emptier method, that enables you to search for all
possible sequences. So, I hope you see how to use recursion, and what to do to prevent the
destruction of your starting ArrayList.

Greetz,
Piet



Output
Entered emptier with level 0
[5, 4]
Entered emptier with level 1
[2, 7]
Entered emptier with level 2
[1, 8]
Entered emptier with level 3
[9]
returning from emptier, printing on level: 2
[9]
returning from emptier, printing on level: 1
[9]
returning from emptier, printing on level: 0
[9]
BUILD SUCCESSFUL (total time: 0 seconds)
 
N Goodie
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hey!

Thanks for the tips!

It needs to return a bowls object because I want the user to be able to do different things to manipulate the game.
(Note that I've already written the application class to do all of the following and I have no problem with it)

1. create a new instance of bowls
e.g. input: "bowls 3 1 1" would create instance of bowls

2. do an emptier() 'move' on whichever index is chosen by user and return the new bowls instance created.
e.g. input: "index 1" - would run emptier on bowl at index 1
(this is why it needs to return a bowl object, so that the original bowls can be overwritten with it in anticipation of the next move)

3. run solution() on the current bowls instance, with a limit set by user
e.g. input: "solvelimit 3" -would run solution() on current bowls instance, and print out all of the "solutions" that it comes to (i.e. any
paths that come to a one-bowl result before the limit of moves is used up).


At this point I really have no idea where the recursion needs to go in the solution method, and how to implement it without eliminating
the prior version of bowls when using a for-loop (which is causing my version of solution() posted above to only run through index0 of each
result of empty(0), and no other indexes).
Also, as far as I know, there shouldn't be any recursion in the emptier() method, only in the solution() method, because the emptier() method
needs to perform only one singular emptier move when it's called.

Sorry for not being clear enough about my specifications, I've sort of been working along as I go ^_^
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!