• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Ron McLeod
  • Jeanne Boyarsky
  • Paul Clapham
Sheriffs:
  • Tim Cooke
  • Liutauras Vilda
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • fred rosenberger
  • salvin francis
Bartenders:
  • Piet Souris
  • Frits Walraven
  • Carey Brown

Swap

 
Sheriff
Posts: 6450
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 ]
 
Ranch Hand
Posts: 1365
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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...)
 
Ranch Hand
Posts: 374
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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).
 
Ranch Hand
Posts: 4632
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 1365
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I've got a 17 move solution obtained with code that hasn't been tested too carefully.
 
Ranch Hand
Posts: 1012
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Greg Harris
Ranch Hand
Posts: 1012
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
here it is:
1-2-3-1-5-4-1-3-2-5-3-1-4-3-5-2-1
 
David Weitzman
Ranch Hand
Posts: 1365
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 6450
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It's a somewhat ugly solution, but at least it works.
Damn right it is! It's in C++!
 
Greg Harris
Ranch Hand
Posts: 1012
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
>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
Posts: 1365
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 1365
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 ]
 
If you believe you can tell me what to think, I believe I can tell you where to go. Go read this tiny ad!
Thread Boost feature
https://coderanch.com/t/674455/Thread-Boost-feature
    Bookmark Topic Watch Topic
  • New Topic