Marbles in Three Baskets

Marbles in Three Baskets is an ACM-ICPC problem. My solution to it is up at my GitHub.

Here are my thoughts on the problem and my solution. I start by stating the problem in my own words.

Imagine that you are playing a game. You are given three baskets: Basket A, Basket B, and Basket C. In each basket, there are zero or more marbles. So, for example, Basket A may have 3 marbles, Basket B may have 0 marbles, and Basket C may have 11 marbles.

Your goal is to get the same number of marbles into each basket. So, for example, you want Basket A to have 3 marbles, Basket B to have 3 marbles, and Basket C to have 3 marbles.

The game proceeds in rounds until every basket has the same number of marbles. At each round, you may double the number of marbles in some basket by taking that number of marbles out of another basket and putting them into the basket. So, for example, if Basket C has 4 marbles in it and Basket B has 7 marbles in it, then you may take 4 marbles out of Basket B and put them into Basket C. Now Basket C has double the number of marbles that it had before, while Basket B has 4 fewer.

You win the game if and only if you reach your goal in the minimum number of moves. You have to get the same number of marbles in each basket in the fewest possible rounds.

I like this problem, because I think that it illustrates the idea that problem-solving is search.

In that model of problem-solving, a problem is defined by a few elements. Specifically, a problem is composed of:

(1) A given state. This is the state of the problem when you start. So, for example, the given state of this ACM-ICPC problem is the number of marbles in each basket at the outset.

(2) A set of performable actions. The world of a problem isn’t completely static. There’s a set of actions that you can perform to transform one state into another. In this case, you can double the number of marbles in a basket. After you perform that action, the state of the problem has changed. One basket has twice as many marbles in it, and another basket has that many fewer marbles in it.

(3) A goal state. Eventually, you have to stop. When you reach a state of the problem where your goal is met, you’ve completed your task. So, here, when each basket has the same number of marbles, we have reached our goal state.

The given state and the set of performable actions induce a graph. The given state is a node in the graph. The performable actions are edges. Edges lead to new states, and each of those states are nodes with edges branching off of them. So, when you perform actions, you effectively explore a graph, moving from state to state, until you reach your goal state.

When you solve a problem, you find a solution to it. A solution to a problem is a sequence of actions or states from the given state to the goal state. So, if you want to find the solution to a problem, you can search the space of problem states until you find a path from the given state to the goal state.

In this problem, we consider the number of marbles in the baskets at any given point as the state of the problem at that point. The given state is the initial number of marbles in the baskets. The only allowable action is doubling the number of marbles in a basket. The goal state is reached when each basket has the same number of marbles.

Because we want to get the same number of marbles into every basket in the minimum number of moves, we don’t want simply a sequence of actions from the given state to the goal state, but rather the shortest sequence of actions. So, we want to find a shortest path. Consequently, we want to use something like breadth-first search.

The core of the program is a shortest-path algorithm that is a hybrid of breadth-first search and Dijkstra’s algorithm. It has similarities and dissimilarities to both.

It’s dissimilar to both breadth-first search and Dijkstra’s algorithm, in that both of them operate on a given graph. Here, we are not given a graph. Instead, we are given an initial node, and we generate the graph on the fly, determining the children of each node as we go.

It’s similar to breadth-first search in that it explores nodes that it places onto a queue. Like breadth-first search, it loops through the queue until it either finds a goal node or runs out of nodes.

But breadth-first search tells you just whether a node is in a graph. Here, we want to determine a shortest path from the source node to the goal node. So, we take a cue from Dijkstra’s algorithm and keep track of each node’s predecessor node.

However, our graph is not weighted. So, unlike Dijkstra’s algorithm, we do not keep track of distances.

So, the algorithm is sort of a middle ground between both breadth-first search and Dijkstra’s algorithm. I used breadth-first search as a base and then incorporated Dijkstra’s algorithm.

Sources:

How to Solve Mathematical Problems, by Wayne A. Wicklegren

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s