#148954 - 2005-10-01 12:45 AM
KiXgolf: Fragmentation
|
Sealeopard
KiX Master
Registered: 2001-04-25
Posts: 11164
Loc: Boston, MA, USA
|
=============
The Challenge
=============
Your friend, a biochemistry major, tripped while carrying a tray of computer files through the lab. All of the files fell to the ground and broke. Your friend picked up all the file fragments and called you to ask for help putting them back together again.
Fortunately, all of the files on the tray were identical, all of them broke into exactly two fragments, and all of the file fragments were found. Unfortunately, the files didn't all break in the same place, and the fragments were completely mixed up by their fall to the floor.
You've translated the original binary fragments into strings of ASCII 1's and 0's, and you're planning to write a program to determine the bit pattern the files contained. If there are 2N fragments in the input, it should be possible to concatenate these fragments together in pairs to make N copies of the output string.
There will be exactly one unique solution. The file can not be broken up at the same point multiple times, however even so you can have fragments that are the same. There will be no empty fragments.
Your friend is certain that there were no more than 8 files on the tray, and that the files were all no more than 9 bits in size.
A download is available at http://s91376351.onlinehome.us/kixtart/kixgolf_fragmentation.zip
=============
Specification
=============
The input are 2N broken file segments for N identical files. The output will be one unique bit-pattern represented by the 2N file fragments.
For example, consider three files on the tray that got fragmented into the following six pieces:
#1 = 011
#2 = 0111
#3 = 01110
#4 = 111
#5 = 0111
#6 = 10111
The file fragments are three, four, and five bits long each, thus the toal length of the file was eight bits. Fragments #1 and #6 belong together, as well as fragments #2 and #5. Thus, #3 and #4 are the last pair.
The file itself is therefore 01110111.
=============
Inputs & Outputs
=============
Input will consist of an array of "file fragments", one per array element. Each fragment consists of a string of ASCII 1's and 0's.
Output is a single string of ASCII 1's and 0's giving the bit pattern of the original files.
=======
Scoring
=======
All provided test cases representing our clumsy biochemist must be correctly solved in order to have the KiXgolf score count. However, if a script fails any valid public or non-public test case the KiXgolf score will not count.
=============
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 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 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.
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 Friday, September 30, 2005, 6:00pm EST
Private coding ends Wednesday, October 5, 2005, 6pm EST
Public coding start Wednesday, October 5, 2005, 6pm EST
Public coding ends Sunday, October 9, 2005, 6pm 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[/CODE]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)[/CODE]for a score of 53.
Better approach: Code sample 1
================================================================
KiXtart GOLF - The Rules
================================================================
- The goal of KiXtart Golf is to score the lowest strokes.
- 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.
- Code can be constructed any way you like, as long as it is syntactically correct with KiXtart.
- The final solution MUST pass all test scripts that accompagny the KiXtart golf challenge.
- The use of '$' as a variable is allowed.
- In case of questions about a particular way to count the KiXtart Golf Challenge organizer has the last call.
- During the private coding phase, no code is allowed to be posted. Violations result in disqualification of said player.
- During the public coding phase, code should be posted, reused, and borrowed from other players.
- The test script contains the official KiXgolf scoring engine
- While the provided test cases cover a whole range of situations they are by no means complete, and can be amended at any time with additional test cases.
_________________________
There are two types of vessels, submarines and targets.
|
|
Top
|
|
|
|
|
#148956 - 2005-10-01 01:04 AM
Re: KiXgolf: Fragmentation
|
NTDOC
Administrator
Registered: 2000-07-28
Posts: 11624
Loc: CA
|
Fire the dork for not wearing approved industrial shoes with a slip resistant sole 
Then call the Golf Masters to do the dirty work, I see how you are Jens.
Good luck you Golf Masters, not sure if I'll play or not, but would like to maybe give it a go.
|
|
Top
|
|
|
|
|
#148957 - 2005-10-01 04:42 AM
Re: KiXgolf: Fragmentation
|
maciep
Korg Regular
Registered: 2002-06-14
Posts: 947
Loc: Pittsburgh
|
very ugly but it seems to work
Quote:
KiXtart Engine
KiXtart Version = 4.50
KiXGolf Script = kixgolf_fragmentation.kix
Computer
OS = Windows XP Professional
CPU = Intel Pentium Celeron
Speed = 1096 MHz
Memory = 190 MB
KiXGolf Scoring Engine
Scoring Engine = 3.0.3
KiXGolf Score
Tournament = Fragmentation
Processing Start = 2005/09/30 22:20:20.500
Processing End = 2005/09/30 22:20:21.234
Duration = 0000/00/00 00:00:00.733
# Tests Run = 180
# Tests Passed = 180
# Tests Failed = 0
Result = passed
KiXGolf Score = 355
|
|
Top
|
|
|
|
|
#148958 - 2005-10-01 05:26 AM
Re: KiXgolf: Fragmentation
|
maciep
Korg Regular
Registered: 2002-06-14
Posts: 947
Loc: Pittsburgh
|
Quote:
KiXtart Engine
KiXtart Version = 4.50
KiXGolf Script = kixgolf_fragmentation.kix
Computer
OS = Windows XP Professional
CPU = Intel Pentium Celeron
Speed = 1096 MHz
Memory = 190 MB
KiXGolf Scoring Engine
Scoring Engine = 3.0.3
KiXGolf Score
Tournament = Fragmentation
Processing Start = 2005/09/30 23:05:06.875
Processing End = 2005/09/30 23:05:07.796
Duration = 0000/00/00 00:00:00.921
# Tests Run = 180
# Tests Passed = 180
# Tests Failed = 0
Result = passed
KiXGolf Score = 264
|
|
Top
|
|
|
|
|
#148959 - 2005-10-01 06:32 AM
Re: KiXgolf: Fragmentation
|
Allen
KiX Supporter
Registered: 2003-04-19
Posts: 4549
Loc: USA
|
Ack!
Works... but geesh...
Quote:
KiXtart Engine
KiXtart Version = 4.50
KiXGolf Script = kixgolf_fragmentation.KIX
Computer
OS = Windows XP Professional
CPU = AMD Athlon(tm) 64 Processor 3200+
Speed = 2003 MHz
Memory = 510 MB
KiXGolf Scoring Engine
Scoring Engine = 3.0.3
KiXGolf Score
Tournament = Fragmentation
Processing Start = 2005/10/01 00:00:08.625
Processing End = 2005/10/01 00:00:08.859
Duration = 0000/00/00 00:00:00.234
# Tests Run = 180
# Tests Passed = 180
# Tests Failed = 0
Result = passed
KiXGolf Score = 460
Thank you for participating in KiXtart Golf!
|
|
Top
|
|
|
|
|
#148962 - 2005-10-02 06:10 AM
Re: KiXgolf: Fragmentation
|
Allen
KiX Supporter
Registered: 2003-04-19
Posts: 4549
Loc: USA
|
What a pain this one is...
I think I've done all I can...
Quote:
KiXtart Engine
KiXtart Version = 4.50
KiXGolf Script = kixgolf_fragmentation.KIX
Computer
OS = Windows XP Professional
CPU = AMD Athlon(tm) 64 Processor 3200+
Speed = 2002 MHz
Memory = 510 MB
KiXGolf Scoring Engine
Scoring Engine = 3.0.3
KiXGolf Score
Tournament = Fragmentation
Processing Start = 2005/10/01 23:50:13.640
Processing End = 2005/10/01 23:50:13.843
Duration = 0000/00/00 00:00:00.202
# Tests Run = 180
# Tests Passed = 180
# Tests Failed = 0
Result = passed
KiXGolf Score = 350
|
|
Top
|
|
|
|
|
#148964 - 2005-10-02 07:15 AM
Re: KiXgolf: Fragmentation
|
Allen
KiX Supporter
Registered: 2003-04-19
Posts: 4549
Loc: USA
|
K... I lied... found a little more...
Quote:
KiXtart Engine
KiXtart Version = 4.50
KiXGolf Script = kixgolf_fragmentation.KIX
Computer
OS = Windows XP Professional
CPU = AMD Athlon(tm) 64 Processor 3200+
Speed = 2002 MHz
Memory = 510 MB
KiXGolf Scoring Engine
Scoring Engine = 3.0.3
KiXGolf Score
Tournament = Fragmentation
Processing Start = 2005/10/02 00:55:50.187
Processing End = 2005/10/02 00:55:50.390
Duration = 0000/00/00 00:00:00.202
# Tests Run = 180
# Tests Passed = 180
# Tests Failed = 0
Result = passed
KiXGolf Score = 344
Thank you for participating in KiXtart Golf!
|
|
Top
|
|
|
|
|
#148965 - 2005-10-02 07:22 AM
Re: KiXgolf: Fragmentation
|
Allen
KiX Supporter
Registered: 2003-04-19
Posts: 4549
Loc: USA
|
341
329
328
325
Dang! Still need to wipe out 60 strokes just to catch up... and who knows how many strokes maciep is holding back 
|
|
Top
|
|
|
|
|
#148967 - 2005-10-02 03:51 PM
Re: KiXgolf: Fragmentation
|
Allen
KiX Supporter
Registered: 2003-04-19
Posts: 4549
Loc: USA
|
Still trying...
Quote:
KiXtart Engine
KiXtart Version = 4.50
KiXGolf Script = kixgolf_fragmentation.KIX
Computer
OS = Windows XP Professional
CPU = AMD Athlon(tm) 64 Processor 3200+
Speed = 2002 MHz
Memory = 510 MB
KiXGolf Scoring Engine
Scoring Engine = 3.0.3
KiXGolf Score
Tournament = Fragmentation
Processing Start = 2005/10/02 09:32:37.203
Processing End = 2005/10/02 09:32:37.375
Duration = 0000/00/00 00:00:00.171
# Tests Run = 180
# Tests Passed = 180
# Tests Failed = 0
Result = passed
KiXGolf Score = 315
Thank you for participating in KiXtart Golf!
|
|
Top
|
|
|
|
|
#148972 - 2005-10-03 01:07 AM
Re: KiXgolf: Fragmentation
|
Allen
KiX Supporter
Registered: 2003-04-19
Posts: 4549
Loc: USA
|
yeah Jooel I'm having a similar problem with my alternate code. It is shorter than the version I am scoring with, but doesn't work on about 25% of the test cases.
Quote:
KiXtart Engine
KiXtart Version = 4.50
KiXGolf Script = kixgolf_fragmentation.KIX
Computer
OS = Windows XP Professional
CPU = AMD Athlon(tm) 64 Processor 3200+
Speed = 2002 MHz
Memory = 510 MB
KiXGolf Scoring Engine
Scoring Engine = 3.0.3
KiXGolf Score
Tournament = Fragmentation
Processing Start = 2005/10/02 18:40:01.343
Processing End = 2005/10/02 18:40:01.515
Duration = 0000/00/00 00:00:00.172
# Tests Run = 180
# Tests Passed = 180
# Tests Failed = 0
Result = passed
KiXGolf Score = 313
|
|
Top
|
|
|
|
Moderator: Arend_, Allen, Jochen, Radimus, Glenn Barnas, ShaneEP, Ruud van Velsen, Mart
|
0 registered
and 920 anonymous users online.
|
|
|
