Sign in to follow this  

Adjacent number exchange Algorithm

This topic is 3490 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have come across a pretty specific problem that requires some kind of algorithmic approach. I'll try to explain the nature of the problem clearly and hopefully someone is familiar with a known algorithm for the problem. Otherwise, if anyone has any ideas on how to approach it, I would be grateful. Consider six containers lined up in a row. Each container has some amount of balls in it ranging from zero to five. Containers themselves do not change position. However, the balls do. Allowed operation: One ball may be passed from one container to an adjacent container. Restriction #1: Passing a ball may not result in the difference in the amount of balls in the starting container and the destination container to become greater than two. example: position: 1, 0, 2, 3, 4, 5 restriction: cannot pass from the 2nd container to the 3rd container because that would result in 1, -1, 3, 3, 4, 5 and the gap between -1 and 3 is more than 2 Restriction #2: A ball may not be passed from a container to another container if the two containers differ in the amount of balls they contain by more than two. example: position: 1, 0, 3, 2, 4, 5 restriction: a ball may not be passed from the 2nd container to the 3rd container (or vice versa) because they already differ by 3 and that is more than 2 My problem: From the starting position: 0 1 2 3 4 5 (that is, the containers contain (left to right) zero, one, two, three, four, and five balls) How do I get five balls in the leftmost container? I was able to find the steps to get five balls in the second container from the left: 0 1 2 3 4 5 0 1 2 3 5 4 0 1 2 5 3 4 0 1 2 4 4 4 0 1 3 3 4 4 0 2 2 3 4 4 0 2 3 2 4 4 0 2 3 4 2 4 0 2 3 4 3 3 0 2 4 3 3 3 0 4 2 3 3 3 0 4 3 2 3 3 0 4 3 2 4 2 0 4 3 4 2 2 0 4 3 4 3 1 0 4 4 3 3 1 0 4 4 4 2 1 0 4 5 3 2 1 0 5 4 3 2 1 But all my attempts to get five in the leftmost have failed. I don't doubt that my above solution for the second container could be optimized and I'm fairly certain if I could discover some general principle/algorithm here I could solve it for the leftmost. As of yet, a general principle/algorithm eludes me. [Edited by - sharpnova on May 24, 2008 9:45:25 PM]

Share this post


Link to post
Share on other sites
After a cursory look, it appears as though you currently ignore the left-most container entirely in your current algorithm. Surely you should add something to it before you end up with four balls in the container to its right?

PS: If I may ask, this isn't homework, is it?

Share this post


Link to post
Share on other sites
Quote:
Original post by Thaumaturge
After a cursory look, it appears as though you currently ignore the left-most container entirely in your current algorithm. Surely you should add something to it before you end up with four balls in the container to its right?

PS: If I may ask, this isn't homework, is it?


I ignore the leftmost container because the solution I posted was only meant to be a solution for getting five balls into container #2 so there was no need to pay any mind to the leftmost container.

And no this is not homework. It's actually just a curiosity that evolved in my mind over the course of a discussion with a friend. There were no "balls" or "containers" in the original problem. It was simply an array of #'s and passing 1 value from location to location to swap the values.. kind of towers of hanoi-esque. I used balls and containers to help describe the problem.

Share this post


Link to post
Share on other sites
012345
102345
111345
112245
112335
112344
202344
211344
212244
212334
212343
302343
311343
312243
312333
312342
321343
322243
322333
322342
331342
332242
332332
422332
431332
432232
432322
432331
423331
424231
424321
432321
433221
433311
433320
442320
443220
443310
533310
542310
543210

Simply scan left-to-right, moving one ball to the left iif it would keep all differences at or below 2. Repeat until done. You could scan right-to-left instead if you felt like it. The sequence you showed does this, but as Thaumaturge said, you stop short of the last bin.

Share this post


Link to post
Share on other sites
Thank you for your algorithm. I think I found a quicker way to do it though:

012345
102345
111345
112245
112335
112353
112443
113343
122343
212343
213243
222243
222423
224223
242223
422223
422232
422322
423222
432222
433122
442122
532122

I found this just by reasoning out some stuff about making a river of 2's and sailing the 4 across it then sailing a 3 across that same river.

Can you think of a way to modify your algorithm so that it gives the quickest solution?

I don't like how my method isn't very algorithmic. It was more intuitive.

Share this post


Link to post
Share on other sites
Quote:
Original post by sharpnova
Can you think of a way to modify your algorithm so that it gives the quickest solution?

Probably not; it's intended to be trivial and mechanical, not efficient. If you want efficient, try A*... should be fairly easy to come up with a good heuristic.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
Quote:
Original post by sharpnova
Can you think of a way to modify your algorithm so that it gives the quickest solution?

Probably not; it's intended to be trivial and mechanical, not efficient. If you want efficient, try A*... should be fairly easy to come up with a good heuristic.


Could you possibly give me a tip in this direction?

I'm fairly familiar with A* but I was always used to using it as a path-finding algorithm and I'm not sure how to apply that here since it's not just one simple starting position and one goal position and there are many moving things.

Share this post


Link to post
Share on other sites
Quote:
Original post by sharpnova
I'm fairly familiar with A* but I was always used to using it as a path-finding algorithm and I'm not sure how to apply that here since it's not just one simple starting position and one goal position and there are many moving things.

Don't think of A* as a physical pathfinding algorithm, and don't think of this problem as many moving things. A* is a graph search algorithm that finds an efficient way to get from one state in a graph to another state in the graph. In the physical use of A*, the "state" is "your current coordinates", and the transitions are "walk north, walk south, walk east, or walk west". In this case, the state is "how many balls are in each bin", and the transitions are "move a ball from bin 2 to bin 3", etc. Same deal. The only tricky part is figuring out a good heuristic.

Share this post


Link to post
Share on other sites
Would I be right in supposing that the general algorithm here is just mini-max and not necessarily A* in particular?

From what I read of A* it always seemed like it was nothing more than mini-max with some optimizations. (optimizations that I don't even think would apply here)

Granted, I've only read a couple tutorials on A* and I've never implemented it so I could be dead wrong of course and probably am.

Share this post


Link to post
Share on other sites
Quote:
Original post by sharpnova
Would I be right in supposing that the general algorithm here is just mini-max and not necessarily A* in particular?
No. Minimax is a decision algorithm which assumes two adversarial agents. It is utterly inapplicable here.
Quote:
From what I read of A* it always seemed like it was nothing more than mini-max with some optimizations. (optimizations that I don't even think would apply here)
A* is much like other graph search algorithms such as uniform-cost search, but uses a heuristic to optimize the search... and that sort of optimization most certainly applies here.

EDIT: were you thinking of alpha-beta pruning?

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
Quote:
Original post by sharpnova
Would I be right in supposing that the general algorithm here is just mini-max and not necessarily A* in particular?
No. Minimax is a decision algorithm which assumes two adversarial agents. It is utterly inapplicable here.
Quote:
From what I read of A* it always seemed like it was nothing more than mini-max with some optimizations. (optimizations that I don't even think would apply here)
A* is much like other graph search algorithms such as uniform-cost search, but uses a heuristic to optimize the search... and that sort of optimization most certainly applies here.

EDIT: were you thinking of alpha-beta pruning?


Yes I was thinking of alpha-beta pruning.

I was way off. I'm not sure why I said mini-max would apply.

I guess it's because I was thinking of just running a brute force search and for some reason that made my brain think "mini-max."

My thoughts on this are as follows (please tell me if any or all of them are simply wrong):

-a brute force search is probably feasible considering the fairly small search space

-most if not all optimizations on top of a brute force search would lend themselves to an intuitive optimal algorithm that could be done by hand easily (probably ANY optimization would lead to this) (i gave optimizations some thought and couldn't find one that didn't have an exception.. and i couldn't really tolerate a single exception since i'm not trying to find a good solution but the global best solution)

Share this post


Link to post
Share on other sites

This topic is 3490 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this