File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Programming Diversions and the fly likes Swap Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Swap" Watch "Swap" New topic
Author

Swap

Jason Menard
Sheriff

Joined: Nov 09, 2000
Posts: 6450
There are 5 balls in a 2 by 3 grid. You need to move 1 ball horizontally or vertically at a time to the empty slot to make ball 1 and ball 2 switch position. The final positions of balls 3, 4, and 5 aren't important. Determine a solution using as few moves as possible.
Starting Grid

Possible Ending Grid

[ July 03, 2003: Message edited by: Jason Menard ]
David Weitzman
Ranch Hand

Joined: Jul 27, 2001
Posts: 1365
Argh. Stop posting all these neat little problems -- I don't have time to be solving them! (Instead of a breadth-first search, I'd use depth-first with iterative deepening to save memory. Muhahahaha! Except I have work I'm supposed to be doing...)
David Hibbs
Ranch Hand

Joined: Dec 19, 2002
Posts: 374
First attempt was 21 moves in about 5 minutes. =)
(skipping a move each time...)
5x1 (original)
432
512
43x
512
x43
1x2
543
142
53x
1x4
532
134
x52
3x4
152
354
x12
and a final 5 shuffles to get them around to
542
3x1
which, neatly, has the numbers all in reverse order from where they started (CCW instaed of CW).


"Write beautiful code; then profile that beautiful code and make little bits of it uglier but faster." --The JavaPerformanceTuning.com team, Newsletter 039.
Michael Dunn
Ranch Hand

Joined: Jun 09, 2003
Posts: 4632
Not sure what response you're after, but here goes anyway - don't laugh if you didn't really want it in java
Also, don't know how the format of this will come out - something about UBB tags? (unfamiliar territory - I've clicked on "Instant UBB Code" -Code).

[Edited to fix the code tags. You created the tags correctly, but your code needs to go between them. --Jason]
[ June 13, 2003: Message edited by: Jason Menard ]
David Weitzman
Ranch Hand

Joined: Jul 27, 2001
Posts: 1365
I've got a 17 move solution obtained with code that hasn't been tested too carefully.
Greg Harris
Ranch Hand

Joined: Apr 12, 2001
Posts: 1012
i got a 17 move solution using michael's program (nice, by the way). however, i did not pay attention, so i cannot tell you what i did.


what?
Greg Harris
Ranch Hand

Joined: Apr 12, 2001
Posts: 1012
here it is:
1-2-3-1-5-4-1-3-2-5-3-1-4-3-5-2-1
David Weitzman
Ranch Hand

Joined: Jul 27, 2001
Posts: 1365
Yup -- that's the solution I got. Here's the code I used. It's not very polished. More significantly, it's not Java. It seemed like a convenient excuse to test a new C++ editor (Dev-C++ kept crashing my comp).
It's a somewhat ugly solution, but at least it works.
Jason Menard
Sheriff

Joined: Nov 09, 2000
Posts: 6450
It's a somewhat ugly solution, but at least it works.
Damn right it is! It's in C++!
Greg Harris
Ranch Hand

Joined: Apr 12, 2001
Posts: 1012
>Damn right it is! It's in C++!
well, i am taking a "linux systems programming" class using C this summer... so it could be worse!
David Weitzman
Ranch Hand

Joined: Jul 27, 2001
Posts: 1365
Actually I've used mostly C and not much in the way of ++. I wonder if I can do a bit of evil optimizing...
David Weitzman
Ranch Hand

Joined: Jul 27, 2001
Posts: 1365
This C version finds a solution in about 5 seconds even on my slow comp. It's basically the same idea as above, but faster :

[ June 13, 2003: Message edited by: David Weitzman ]
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Swap