Real Software Forums

The forum for Real Studio and other Real Software products.
[ REAL Software Website | Board Index ]
It is currently Wed Nov 22, 2017 4:03 am
xojo

All times are UTC - 5 hours




Post new topic Reply to topic  [ 13 posts ] 
Author Message
 Post subject: Tower of Hanoi and Solutions: Anyone for Sharing Code?
PostPosted: Thu Jan 17, 2013 6:47 pm 
Offline

Joined: Fri Sep 30, 2005 1:53 pm
Posts: 914
Location: Philadelphia, PA
Last night I wrote an RB program to calculate the moves needed for the Tower of Hanoi, the object of which is to transfer all of the disks of different sizes on one peg or pole to another. (There are three pegs, two of which start out empty.)

There are essentially only two rules: (1) you can move only one disk at at time. (2) No disk may be placed on top of a smaller disk.

Important: I did not write the game program itself. (I'm hoping to find someone here who may be interested enough to work with me on that.) What I wrote was a program which shows the minimum moves, step-by-step, required to solve the puzzle.

Here's where you can find the source code for my program:

http://traver.org/RB2013/Hanoi.rbp

Here's the Web page that inspired me:

http://britton.disted.camosun.bc.ca/jbhanoi.htm

And here's a sample of what my program does:
_____

SOLUTION FOR 10 DISKS
(1023 moves minimum required)

1 (Move 1): Move disk 1 onto empty peg.
10 (Move 2): Move disk 2 onto empty peg.
11 (Move 3): Move disk 1 onto disk 2.
100 (Move 4): Move disk 3 onto empty peg.
101 (Move 5): Move disk 1 but NOT onto disk 3.
....
_____

My program was written in Windows, which uses Chr (13) as an end-of-line marker for text inside a TextArea. That will have to be changed for the program to work properly on the Mac or on Linux.

What I'm looking for from people on the Forum is suggestions for improvement of my program. (If someone wants to write, say, something that will allow people to play the game on their own computer, that would be great!) If you prefer to send me a private email rather than posting a note, that would be okay, but posting on the Forum would enable others here to benefit from the discussion. My objective here is to encourage sharing of code.

Barry Traver

P.S. I'm actually hoping that I may find here at least a few hobbyist programmers who have an interest in working together on logic-type games, such as those discussed by Martin Gardner in his "Mathematical Games" column in Scientific American in years past.


Top
 Profile  
Reply with quote  
 Post subject: Re: Tower of Hanoi and Solutions: Anyone for Sharing Code?
PostPosted: Thu Jan 24, 2013 9:26 am 
Offline
User avatar

Joined: Thu Sep 10, 2009 2:50 am
Posts: 418
Location: Santa Cruz, CA, USA
I've been fiddling with this over the last couple days. It's pretty garish, just about the minimum to represent the game. Might add more but I've been thinking about Tempest...

http://home.comcast.net/~trochoid/hanoi_0a.rbp.zip

Also check out Project Euler, not so much games as puzzles to solve with code and math. I've done the first 11:)

http://projecteuler.net/problems


Top
 Profile  
Reply with quote  
 Post subject: Re: Tower of Hanoi and Solutions: Anyone for Sharing Code?
PostPosted: Thu Jan 24, 2013 2:38 pm 
Offline

Joined: Fri Sep 30, 2005 1:53 pm
Posts: 914
Location: Philadelphia, PA
doofus,

Wow! Great job! I only wish I had written it myself!

The Tower(s) of Hanoi is your program, so you have the right to decide what other people are allowed to do with it and what not. Therefore I have a question for you:

Do you mind if I play around the code, make modifications, and make the results available to others, provided that I indicate that you were the author of the program (and thus deserve the credit for the "good stuff") and that I am merely the author of the modifications?

I have two possible modifications in mind:

(1) If someone puts a larger disk on a smaller disk, your program (with this minor modification) would indicate that this is an illegal move and would return the disk to its earlier position.

(2) Another modification would be to create a program which would combine your program and my program, the combination having the capability of showing, move-by-move, the solution(s) for the puzzle.

I believe the person who writes a program has the right to decide what other people can do with it, so I'm not putting pressure on you to answer one way or the other. Naturally, I would love it if you say "Yes," but it is your decision, and we'll still be friends whatever your decision. (After all, you've graciously let people see your code and learn from it!)

If you do say "Yes," then you have to decide what you want me to put as to the author of your program. Obviously, the program was not written by a "doofus" (your real name might be preferable for that reason), but that also is your decision.

Barry Traver

P..S. The link to Project Euler was also much appreciated. Two questions: (1) What is "Tempest"? (2) Do you have your own Web site open to the public?


Top
 Profile  
Reply with quote  
 Post subject: Re: Tower of Hanoi and Solutions: Anyone for Sharing Code?
PostPosted: Mon Jan 28, 2013 5:58 am 
Offline
User avatar

Joined: Thu Sep 10, 2009 2:50 am
Posts: 418
Location: Santa Cruz, CA, USA
barrytraver wrote:
Do you mind if I play around the code, make modifications, and make the results available to others
Please do. Credit me or not, I stake no claim.

barrytraver wrote:
Another modification would be to create a program which would combine your program and my program
That's where I was going too, just hadn't figured it out yet. I had to understand your code and how to translate the move directions into stack indices to move amongst, which I've done now. I also added a quick drop animation and keyboard movement. It got pretty sloppy adding these, going for easiest to hack in vs good design. It's stable but I didn't think through and account for every situation (ie, if you key and mouse the highlight can be screwed with).

http://home.comcast.net/~trochoid/hanoi_0c.rbp.zip

3 ways to use
A) Click and drag pieces, as before.
B) press left, down, right to select stacks 0, 1, 2, respectively. The first selection highlights a stack piece, second selection moves it to that stack. Pressing up or the same stack removes the highlight.
C) Turn on the the 'play solution' checkbox and press one of the buttons to run the answer at 10 moves per second. To stop running hold down the shift key. There's no resuming or stepping. Video of 10 piece run http://vimeo.com/58298517

I've had fun seeing how fast I can solve 6 or 7 pieces with the keyboard, it gets to be like tapping out morse code. 10 piece takes too long but it's fun to be in the middle of it and maintain where you are in the recursion. I'd like to make it a game with stats on speed, moves and errors.

This still allows illegal moves (I like the physics of it) but there's code in MouseDown, MouseUp and processKey to be uncommented for restricting that.

...Tempest is a 80's video game http://www.youtube.com/watch?v=K8Na1UdjGaA


Top
 Profile  
Reply with quote  
 Post subject: Re: Tower of Hanoi and Solutions: Anyone for Sharing Code?
PostPosted: Mon Jan 28, 2013 11:46 am 
Offline

Joined: Fri Sep 30, 2005 1:53 pm
Posts: 914
Location: Philadelphia, PA
"doofus,"

I love what you've done with the Tower of Hanoi! There's a lot I can learn from what you've done. One thing I'm anxious to understand is how you moved pieces not only by "drag and drop" (I've got that at least partly figured out), but also from the code itself (as when the computer displays the solutions to the Tower of Hanoi).

There is one problem for which there may or may not be a REALbasic solution: the problem of flicker. It is worse at some times than at other times,and thus far I haven't figured out why. Indeed, the same code can have varying amounts of flicker at different times for no apparent reason. Any thoughts on that (or on how to reduce flicker)?

Your coding makes me realize how much I don't know about programming. I was pleased that it took only one night for me to write a program displaying the solutions for the Tower of Hanoi, but your programs make me realize how much I really don't know.

That can be seen in my CheckersDrawDrag program (downloadable from "http://traver.org/rb/"). It's not even a real program: it's just a demo of some techniques that I'm still learning.

In it, I start with pixel values, move to row and column values for the 64 squares, and finish up with the standard values for the 32 squares actually used in a checkers game. Why checkers? Why not chess? Well, as Edgar Allan Poe expressed it, "Some people prefer chess to checkers because they mistake complexity for profundity" (or something like that).

Warm regards,

Barry Traver


Top
 Profile  
Reply with quote  
 Post subject: Re: Tower of Hanoi and Solutions: Anyone for Sharing Code?
PostPosted: Tue Jan 29, 2013 8:11 am 
Offline
User avatar

Joined: Thu Sep 10, 2009 2:50 am
Posts: 418
Location: Santa Cruz, CA, USA
barrytraver wrote:
There is one problem for which there may or may not be a REALbasic solution: the problem of flicker.
I'm on a mac which doesn't have flicker issues so I'm geussing you're on windows. I don't know what causes flicker but I think if you turn on DoubleBuffer of the Canvas it'll stop. Or maybe calling Invalidate(False) will do it and be lighter weight.

barrytraver wrote:
One thing I'm anxious to understand is how you moved pieces not only by "drag and drop" (I've got that at least partly figured out), but also from the code itself (as when the computer displays the solutions to the Tower of Hanoi).
some setup: There's a Block class used to maintain the geometrics of the scene. The method layoutStand() will position all the blocks in the scene. The property 'pieces() As Piece' stores the Piece objects, but those same instances are also stored in the property 'stacks(2) As Variant'. stacks is where the actual game state is stored, pieces is just for easier looping in mousedown and paint.

To move a piece in code you move an element in stacks then call positionPieceInStack. You'll see this in animSoln and processKey.

dim s1() As Piece = stacks(stackIndexToMoveFrom) //get array to remove from top
dim s2() As Piece = stacks(stackIndexToMoveTo) //get array to append to top

dim p As Piece = s1(s1.Ubound) //grab piece on top of s1

s1.Remove s1.Ubound //remove it from s1
s2.Append p //append it to s2 < now it's been moved in game state

positionPieceOnStack(p, stackIndexToMoveTo, s2.Ubound, p.size) //move geometry

Invalidate 'redraw when geometry changes


The trick here is the use of Variant() to create a jagged array. If in the game the first stack has 3 pieces, the next 2 pieces and the last has 5 pieces then stacks looks like this...
stacks(0) = 3 element array of Piece
stacks(1) = 2 element array of Piece
stacks(2) = 5 element array of Piece
You can't cast to those inner arrays, it's a 2 step process of assigning to a Piece array variable then manipulate that..

Mouse dragging creates sort of a fuzzy state. In MouseDown the dragged piece is removed from stacks and held in the property dragPiece. It stays removed until MouseUp where it's put back in. Even though the piece is now in stacks it's geometric position is unchanged and a timer then animates a drop.


Top
 Profile  
Reply with quote  
 Post subject: Re: Tower of Hanoi and Solutions: Anyone for Sharing Code?
PostPosted: Tue Jan 29, 2013 5:12 pm 
Offline

Joined: Fri Sep 30, 2005 1:53 pm
Posts: 914
Location: Philadelphia, PA
I've been experimenting with the flicker in Windows on half a dozen or so different programs (including the original CanvasDrawDrag from Real Software, my Checkers program, your first Tower of Hanoi program, and one or two others).

Warning: Since I don't really know what I'm doing, what follows in this note may be more speculation than an accurate description of the facts.

I think I may have discovered a way to reduce flicker, but -- even if I have -- I don't know if I can even give a good description of what I did. (I don't even have the technical terminology for that.) But here's my attempt to describe what I think may have happened....

There are sort of two places where things can be drawn. Let's call them "foreground" and "background" (since I don't know whether there is a technical term for them). There are two types of things being drawn: (1) the pegs, the checkerboard, and the picture in the Real Software demo (no need to draw these more than once), and (2) the disks, checkers, and the ovals with letters in them (all of which are continually being redrawn).

Things in the first category don't change. That is, they don't move. They do not need to be redrawn . Things in the second category are different: they are continually changing, moving, being redrawn. Things in the second category belong in the "foreground," while things in the first category belong in the "background."

I don't remember exactly what I did, but I had a flickering program and a flicker-free program. Taking the flickering program, I modeled it to be similar to the flicker-free program, moving non-moving stuff away from the code involving moving stuff. The result was that the flickering program lost its flicker.

I'm not describing it very well (and the description may not even be accurate), but it certainly seemed as though the program went from flickering to non-flickering. (Or I could be imagining it....)

Barry Traver


Top
 Profile  
Reply with quote  
 Post subject: Re: Tower of Hanoi and Solutions: Anyone for Sharing Code?
PostPosted: Tue Jan 29, 2013 5:40 pm 
Offline

Joined: Fri Jan 06, 2006 3:21 pm
Posts: 12388
Location: Portland, OR USA
You describe it well enough. You could even go one step further if performance were an issue. Of all the disks and checker pieces, only one is moving at a time. All the rest can be considered "background". Or perhaps, "fixed foreground". At any given time in the Paint event of the canvas you only need to draw 2 things: the static portion (background and fixed foreground) that you have in a Picture object, and the piece that is selected/moving. If you composite them into a temporary image and draw that to the canvas, you eliminate (or at least greatly reduce) flicker.


Top
 Profile  
Reply with quote  
 Post subject: Re: Tower of Hanoi and Solutions: Anyone for Sharing Code?
PostPosted: Tue Jan 29, 2013 6:11 pm 
Offline
User avatar

Joined: Mon Apr 02, 2007 2:08 am
Posts: 1225
Location: San Francisco, CA, USA
doofus wrote:
barrytraver wrote:
There is one problem for which there may or may not be a REALbasic solution: the problem of flicker.
I'm on a mac which doesn't have flicker issues so I'm geussing you're on windows. I don't know what causes flicker but I think if you turn on DoubleBuffer of the Canvas it'll stop. Or maybe calling Invalidate(False) will do it and be lighter weight.


Set EraseBackground = False and DoubleBuffer = True to eliminate most or all flickering on Windows (caused by e.g. the MouseDrag event firing rapidly and each time calling Invalidate or Refresh.)

_________________
Boredom Software


Top
 Profile  
Reply with quote  
 Post subject: Re: Tower of Hanoi and Solutions: Anyone for Sharing Code?
PostPosted: Tue Jan 29, 2013 7:21 pm 
Offline

Joined: Fri Sep 30, 2005 1:53 pm
Posts: 914
Location: Philadelphia, PA
charonn0 wrote:
Set EraseBackground = False and DoubleBuffer = True to eliminate most or all flickering on Windows (caused by e.g. the MouseDrag event firing rapidly and each time calling Invalidate or Refresh.)

Thanks to you and others on flickering in Windows.

In the expanded Hanoi program by "doofus" most of the flicker occurred while the disks were being moved. I tried commenting out "Invalidate" for the MouseDrag code, but that (as you would expect) did more harm than good (the Hanoi disk disappeared during any move of a disk!).

It didn't seem to matter much whether or not EraseBackground was set to False, BUT setting DoubleBuffer to True made a tremendous difference (essentially eliminating flicker entirely!)

Barry Traver


Top
 Profile  
Reply with quote  
 Post subject: Re: Tower of Hanoi and Solutions: Anyone for Sharing Code?
PostPosted: Wed Jan 30, 2013 2:44 am 
Offline

Joined: Fri Sep 30, 2005 1:53 pm
Posts: 914
Location: Philadelphia, PA
"doofus,"

Here's the URL for the latest version of Hanoi you posted:

http://home.comcast.net/~trochoid/hanoi_0c.rbp.zip

That version is nearly perfect. I say nearly perfect because there are two changes that I think you'll agree would be good to make, one cosmetic and the other more substantial.

The cosmetic one: At the very start of the program "3" is the pushbutton highlighted at the bottom, but there are 6 disks on the peg. (As I said, it's merely a cosmetic matter.)

The substantial one: The program allows the breaking of one of the main rules for the Tower of Hanoi: It permits the placing of a larger disk on top of a smaller disk. (What I'd like to see is the user being informed "Illegal Move" and the disk returned to where it was.)

I've been given enough information (full source code PLUS lots of comments PLUS all the notes in this threat) that I should be able to figure out by myself what changes in the source code need to be made to make your nearly perfect program really perfect <grin>.

I intend to do that. Just don't tell us how until I've had some time and opportunity to work on it. (I'm hoping not to disappoint you or others here.)

Barry Traver


Top
 Profile  
Reply with quote  
 Post subject: Re: Tower of Hanoi and Solutions: Anyone for Sharing Code?
PostPosted: Wed Jan 30, 2013 7:34 am 
Offline

Joined: Fri Sep 30, 2005 1:53 pm
Posts: 914
Location: Philadelphia, PA
The code for the MainWindow.Controls.display.Open event should be this to change the number of disks to 3:

me.stackUpNPieces(3)

So now the number of disks and the bottom highlighted pushbutton will be the same (i.e., both will be 3).

I'm still working, however, on how to change which bottom pushbutton is highlighted. (One reason for my not having solved that yet is that I don't think I've seen pushbuttons used as radiobuttons before this. Interesting.)

Barry Traver


Top
 Profile  
Reply with quote  
 Post subject: Re: Tower of Hanoi and Solutions: Anyone for Sharing Code?
PostPosted: Thu Jan 31, 2013 7:01 am 
Offline
User avatar

Joined: Thu Sep 10, 2009 2:50 am
Posts: 418
Location: Santa Cruz, CA, USA
barrytraver wrote:
The cosmetic one: At the very start of the program "3" is the pushbutton highlighted at the bottom, but there are 6 disks on the peg.
Pushbuttons don't get focus on mac so I didn't see that.

barrytraver wrote:
me.stackUpNPieces(3)
So now the number of disks and the bottom highlighted pushbutton will be the same (i.e., both will be 3).
Another way is to remove that code and in MainWindow.Open put "buttonN(3).Push". This will programmatically push the button and maybe also set the focus. If that doesn't focus then also add "me.SetFocus" to buttonN.Action.

Also, in MainWindow.KeyDown it's returning true. I think this blocks tabbing between controls, it shouldn't be there.

There's other cosmetic (and worse) issues. Namely if you use the keyboard to highlight a piece then start dragging... the highlight stays even though it's lost meaning, and the key tracking variable keyStack1 isn't updated which can lead to a crash. (I've since fixed this in MouseDown by resetting the key cycle). There's also duplicated code and hard coded constants.

barrytraver wrote:
The substantial one: The program allows the breaking of one of the main rules for the Tower of Hanoi: It permits the placing of a larger disk on top of a smaller disk. (What I'd like to see is the user being informed "Illegal Move" and the disk returned to where it was.)
Code is already in there to do this :) it's just commented out. They're marked with "//<<<***" so you can search for that. The user isn't alerted to illegal moves, it's just prevented (in mousing the piece returns to it's original position, in keying the piece loses it's highlight).

I like to play rapid fire with the keys and found I get a twitchy hand. Blocking illegal moves helps not mess up the board and keep up the pace, doing a 6 piece tower in about 30 seconds. Larger towers are mostly more of the same but at times I'll lose track where the tower is going. It needs to get deep to lose track (the pattern is somewhat instinctive now) but it takes so long to get into it. I want to start in the middle and just get it into one of the simple states.

Another fun way to play is shuffling the initial stack. Still block illegal moves, but because it's jumbled the solving pattern loses it's regularity.

http://home.comcast.net/~trochoid/hanoi_1b.rbp.zip
This version has those changes with shuffling and blocking moves as options; shows win time and pressing space bar resets to last stack type. I also setup the canvas like charonn0 suggested and use Invalidate(False) everywhere. Hopefully that'll help with flicker but I don't understand why it's always "mostly reduce flicker". Seems there should be a way to absolutely not flicker.


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 13 posts ] 

All times are UTC - 5 hours


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group