Updated 2016-11-22 22:13:29 by kpv

TkReverse is a simple game inspired from a blog post by Paul Bissex [1]. 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

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.