#167180 - 2006-09-09 02:01 PM
KiXgolf: Shuttle Puzzle - Private Round
|
Sealeopard
KiX Master
Registered: 2001-04-25
Posts: 11164
Loc: Boston, MA, USA
|
============= The Challenge =============
The Shuttle Puzzle is a puzzle consisting of a strip of wood with nine holes. Placed on opposite ends of the strip were marbles of the same color, the center hole was left empty. The object of the puzzle was to reverse the marbles using one of two permissible moves. A marble could slide forward into an empty space, or a marble could jump another marble of the opposite color providing the new location was empty and the jump was in a forward direction. Invariably after making four or five moves one would arrive at a dead end, most often with a marble trapped on one end surrounded by a sea of marbles of the opposite color.
Therefore, we will put our computers to work and come up with a solution for such puzzles.
A download is available at http://s91376351.onlinehome.us/kixtart/kixgolf_shuttle.zip
============= Specification =============
The SHUTTLE PUZZLE of size 3 consists of 3 white marbles, 3 black marbles, and a strip of wood with 7 holes. The marbles of the same color are placed in the holes at the opposite ends of the strip, leaving the center hole empty. White marbles are always start out on the left side and black marbles always start out on the right side
INITIAL STATE: WWW BBB
GOAL STATE: BBB WWW
To solve the shuttle puzzle use only two types of moves. Move 1 marble 1 space (into the empty hole) or jump 1 marble over 1 marble of the opposite color (into the empty hole). You may not back up, and you may not jump over 2 marbles.
A Shuttle Puzzle of size N consists of N white marbles and N black marbles and 2N+1 holes.
Write an algorithm that will solve the SHUTTLE PUZZLE for any size 1<=N<=10. Your algorithm will be tested with the solution for N=(1,2,3,4)
Please note that if you come up with a solution that differs from the provided ones, please submit it to the KiXtart BBS so that it can be included in the test cases and it has been reviewed for validity. The validation script is written such that it can accomodate multiple solutions for the same n. however, as far as I know for 1<=n<=4 there are only unique solutions.
============= Inputs & Outputs =============
The input into the SHUTTLE PUZZLE UDF will be an integer with values between 1 and 10, inclusive.
The output should be an array of marble positions starting with the starting layout, all interim steps and ending with the final layout.
For n=1, the output array would therefore look like Code:
dim $sp[3]
$sp[0]='W B' $sp[1]='WB ' $sp[2]=' BW' $sp[3]='B W'
======= Scoring =======
All provided test cases must be correctly solved in order to have the KiXgolf score count. If a script fails any valid public or non-public test case the KiXgolf score will not count. Non-public test cases will be published after the end of the tournament.
============ Bonus Points ============ The first person to post the solution for n=10 created via a KiXtart script will be awared one bonus point, added to his final KiXgolf Score.
============= General rules =============
- The UDF must be written as one or more lines.
- The UDF is expected to finish in a reasonable time, e.g. if it gets started when the challenge opens, it's expected to be finished by the time the challenge closes even on a somewhat slow computer. The UDF has to be valid during the period that the challenge runs.
- You can submit scores as often as you want until the deadline, there's no reason to wait until the last minute for a score submission. In fact, other people want to see the score to beat. So don't be a spoilsport by hoarding your score. Submit early and often.
- The UDF may only use the KiXtart/KiXforms commands/functions/macros, no other code fragments are allowed. Calls to COM components that are part of a standard default Windows installation are allowed.
- Calls to other executables, as long as they are part of a standard default Windows installation are allowed.
- The use of the KiXforms DLL is also permitted as the KiXforms DLL can now be considered an integral part of KiXtart scripting.
- The UDF should be self-contained (except for any I/O mentioned in the challenge). In particular, you may not do things like fetching extra data from a remote site or file.
- You may assume ASCII as character set.
- You may not use block comments as the KiXgolf Scoring Engine does not support block comments
- You are not allowed to use additional code that is external to the KiXgolf UDF Collection. All code must be contained within the KiXgolf UDF Collection.
- You are allowed to only use publicly available versions of KiXtart and KiXforms, private builds or alpha builds are NOT allowed
- Your submitted score must include the KiXart/KiXforms version used.
- All variables must be properly declared as SETOPTION('Explicit','ON') has been coded into the main script
- Other script-wide restrictions, e.g. NoVarsInStrings=ON, are not in effect
- The KiXgolf UDF Collection as enclosed by the ';!' and ';!;!' tags can be modified to e.g. rename the parameter variables, add additional optional parameters or add additional sub-UDFs.
- Maximum runtime for the code solution is one hour
- Tokenizing the UDF, script, or portions thereof is not allowed
When posting KiXtart Golf Scores, please include the KIXGOLF_*.TXT file that is created in the script directory. It contains some basic information about the computer that the script is run on and the resulting scores.
======== Deadlines ========
Private coding starts Saturday, September 9, 2006 at 7am EST Private coding ends Saturday, September 16, 2006 at 7am EST Public coding start Saturday, September 16, 2006 at 7am EST Public coding ends Saturday, September 23, 2006 at 7am EST
============ Test program ============
A test program is provided to help screen entries and to provide the Golf Score. Any program that passes the test program can be submitted. If you are surprised that your solution passed the test program, please submit it anyway! That will help me identify bugs in the test program.
================================================================ KiXtart GOLF - How To Play ================================================================
Most importantly, anybody can play, no age restrictions, no penalties, no handicap!
The object in "real" golf is to hit the ball in the hole in the fewest strokes. The object in KiXtart Golf is to get from input (tee) to target (hole) in the fewest keystrokes.
Example: How many positive elements are in array $a?
Array $a could be of structure $a=[1, 2 ,-3, 4, -5, -7, 8, 9]
One approach: Code:
for $b=0 to ubound($a) if $a[$b]>0 $c=$c+1 endif next
for a score of 45.
Another solution is: Code:
DO $b=$b+1 if $a[$b]>0 $c=$c+1 endif UNTIL $b>(UBOUND($a)+1)
for a score of 53.
Better approach: Code sample 1
================================================================ KiXtart GOLF - The Rules ================================================================
1) The goal of KiXtart Golf is to score the lowest strokes. 2) Strokes are all characters in a piece of code except whitespace characters, unless the whitespace character is necessary for the line of code to work. Therefore, carriage returns and line feeds do not count or spaces in between the '=' sign when assigning variables, e.g. '$a = $b' scores 5. 3) Code can be constructed any way you like, as long as it is syntactically correct with KiXtart, i.e. the KiXgolf engine does not throw a syntax or other error. 4) The final solution MUST pass all test scripts that accompagny the KiXtart golf challenge. 5) The use of '$' as a variable is allowed. 6) In case of questions about a particular way to count the KiXtart Golf Challenge organizer has the last call. 7) During the private coding phase, no code is allowed to be posted. Violations result in disqualification of said player. 8) During the public coding phase, code should be posted, reused, and borrowed from other players. 9) The test script contains the official KiXgolf scoring engine 10) Only the person posting a particular score will be recognized for the score, unless the KiXtart Golf Challenge organizer or another delegate posts code on behalf of a player
You will need the complete package from http://s91376351.onlinehome.us/kixtart/kixgolf_shuttle.zip.
Edited by sealeopard (2006-09-09 02:12 PM)
_________________________
There are two types of vessels, submarines and targets.
|
Top
|
|
|
|
#167182 - 2006-09-09 02:43 PM
Re: KiXgolf: Shuttle Puzzle - Private Round
|
Lonkero
KiX Master Guru
Registered: 2001-06-05
Posts: 22346
Loc: OK
|
didn't compine the time rules
k, here goes first. for 1 there are 2 possible solutions:
1) 'W B','WB ',' BW','B W' 2) 'W B',' WB','BW ','B W'
|
Top
|
|
|
|
#167188 - 2006-09-09 03:33 PM
Re: KiXgolf: Shuttle Puzzle - Private Round
|
Lonkero
KiX Master Guru
Registered: 2001-06-05
Posts: 22346
Loc: OK
|
that sounded a bit obscene...
|
Top
|
|
|
|
#167194 - 2006-09-09 06:31 PM
Re: KiXgolf: Shuttle Puzzle - Private Round
|
Benny69
Moderator
Registered: 2003-10-29
Posts: 1036
Loc: Lincoln, Ne
|
Allen, I was just thinking the same thing, thank you.
|
Top
|
|
|
|
#167195 - 2006-09-09 06:33 PM
Re: KiXgolf: Shuttle Puzzle - Private Round
|
Lonkero
KiX Master Guru
Registered: 2001-06-05
Posts: 22346
Loc: OK
|
allen prove it. I did.
|
Top
|
|
|
|
#167196 - 2006-09-09 06:48 PM
Re: KiXgolf: Shuttle Puzzle - Private Round
|
Allen
KiX Supporter
Registered: 2003-04-19
Posts: 4549
Loc: USA
|
Proof eh? Well I'm not giving you any ammo to work with...
I've just started looking at this, and I'll be tied up all day, so it may be a while before I actually get to sit down and work on this one.
|
Top
|
|
|
|
#167199 - 2006-09-09 08:50 PM
Re: KiXgolf: Shuttle Puzzle - Private Round
|
Lonkero
KiX Master Guru
Registered: 2001-06-05
Posts: 22346
Loc: OK
|
k, I just HAD TO post my score. note this is not a working code, but the score is awesome :P
Code:
Shuttle Puzzle failed all 4 tests (0% correct)
KiXtart KiXtart Version = 4.53 Release Candidate 1 KiXforms Version = KiXGolf Script = kixgolf_shuttle.kix
Computer OS = Windows XP Professional CPU = Intel Pentium Model 13 Speed = 1866 MHz Memory = 760 MB
KiXGolf Scoring Engine Scoring Engine = 3.0.3
KiXtart Golf Score Tournament = KiXtart Golf: Shuttle Puzzle Processing Start = 2006/09/09 21:48:24.890 Processing End = 2006/09/09 21:48:28.421 Duration = 0000/00/00 00:00:03.531 KiXGolf Score = 1257
Thank you for participating in KiXtart Golf!
|
Top
|
|
|
|
Moderator: Arend_, Allen, Jochen, Radimus, Glenn Barnas, ShaneEP, Ruud van Velsen, Mart
|
0 registered
and 700 anonymous users online.
|
|
|