TkReverse

TkReverse is a simple game inspired from a blog post by Paul Bissex [L1 ]. I was never a Tcl or Tk guru and have wanted to learn Tcl and Tk again, so I hacked together this version of Reverse that uses Tk as it's input/GUI method instead of the console as most of the versions listed in Paul's blog post uses.

I am posting the game here for two reasons...

  1. It's fun
  2. I would like people to comment on the implementation and make better versions so I can learn :-)

Game play is simple. You start off with a random list of 10 numbers, 1 thru 10. Your job is to order them. The trick is you can only reverse the first X numbers. X is a variable you choose. So, starting off you may have the very easy board:

 1 2 3 4 5 10 9 8 7 6

With that board, if you click the 6 button, the last, you will come up with:

 6 7 8 9 10 5 4 3 2 1

Now, click the 10 button and you will get a reversed copy again, but only of the numbers up to and including 10:

 10 9 8 7 6 5 4 3 2 1

Almost done, as you can see we now have the list in order, but reverse. I am sure you can figure out what to do now, but, for completness sake, press the 1 button. You now have an ordered list and a message dialog stating you have won the game in 3 moves. Not bad, however, you will never get that simple of a board. So, on with the code:


 #!/usr/bin/env wish8.4

 package require Tk
 
 ###########################################################################
 # Simple list helping functions
 #
 
 # Reverse a list
 proc lreverse {l} {
     for {set idx [llength $l]} {$idx >= 0} {incr idx -1} {
         lappend ret [lindex $l $idx]
     }
 
     return [lrange $ret 1 end]
 }
 
 # Reverse only upto $to
 proc lreverse-range {l to} {
     return [concat [lreverse [lrange $l 0 $to]] \
                 [lrange $l [expr $to + 1] end]]
 }
 
 # Randomize the list by reversing the list $times at random indexes
 proc lrandomize {l times} {
     for {set idx 0} {$idx < $times} {incr idx} {
         set l [lreverse [lreverse-range $l [expr int(10 * rand())]]]
     }
     return $l
 }
 
 ###########################################################################
 # Game play functions
 #
 
 # Reverse up to $to in the nums list, incrementing game state variables
 proc reverse-em {to} {
     global winner nums buts moves
     set nums [lreverse-range $nums $to]
     for {set idx 0} {$idx <= $to} {incr idx} {
         [lindex $buts $idx] configure -text [lindex $nums $idx]
     }
 
     incr moves
 
     if {$nums == $winner} {
         set answer [tk_messageBox -message \
                         "You've won in $moves moves! Play again?" -type yesno \
                         -icon question]
         switch -- $answer {
             no exit
             yes setup-board
         }
     }           
 }
 
 # Setup board and game state variables for a new game
 proc setup-board {} {
     global winner nums buts moves
     set nums [lrandomize $winner 100]
 
     # Goofy trick to update the button text with new list text
     reverse-em 9
     set moves 0
 }
 
 ###########################################################################
 # Tk GUI setup
 #
 
 wm title . "Reverse"
 
 set moves 0
 
 label .moves-text -text "Moves:"
 pack .moves-text -padx 10 -pady 10 -side left
 
 label .moves -textvariable moves
 pack .moves -padx 10 -pady 10 -side left
 
 for {set i 0} {$i <= 9} {incr i} {
     set this .btn$i
     button $this -command [list reverse-em $i]
     pack $this -padx 10 -pady 10 -side left
     lappend buts $this
 }
 unset this i
 
 button .exit -text Exit -command exit
 pack .exit -padx 10 -pady 10 -side right
 
 set winner [list 1 2 3 4 5 6 7 8 9 10]
 set nums $winner
 
 setup-board

Let me know if there are changes to make this code more efficient, easier to read, less lines, something done proper, etc... Thanks and enjoy a very simple fun game!


MG This is a really cool little game. :) Something I would've done differently myself is using a for loop to make the buttons at the start, to save typing it out several times (and to make it easy to adjust the number of buttons):

  for {set i 1} {$i <= 10} {incr i} {
   set this .btn$i
   button $this -command [list reverse-em $i]
   pack $this -padx 10 -pady 10 -side left
   lappend buts $this
  }
  unset this i ;# remove temp vars that aren't being used any more

Fiddling with this is probably going to keep me busy for hours. Thanks for sharing it :)

jnc Thanks for the code above. I was wanting to do something like that but was having problems generating the button variable. I was hoping someone would help me out with that. I've updated the code with your change, removing the old repetitive code of creating buttons one, two, three, etc...


2007-01-02 gg - Actually, there is a simple solution to this game in every case which wins the game with a maximum of 17 moves - without much thinking. Of course, 17 moves is not an amazing number, but still, maybe there should be some improvement (levels, "pars", etc.). I think you should be able to work the universal solution out yourself, but if you really want to know, contact me.

Anyway, a little "bug" I found (depends on whether you see it as a bug) is that when you click on the left-most number, no changes are made (obviously), but the number of turns is updated. Easily changed, but wanted to mention.


       Screenshot 

http://farm2.static.flickr.com/1270/4685330600_89e47e4a79_m.jpg

gold added pix


KPV This is known as Pancake Sorting . Bill Gates wrote the paper Bounds for Sorting by Prefix Reversal in 1979 proving an upper bounds on the number of flips at 5/3n. This has subsequently been improved to 18/11n. The problem of determining the minimal number of moves for a given stack has been shown to be NP-hard.