Page 1 of 5 12345>
Topic Options
#148954 - 2005-10-01 12:45 AM KiXgolf: Fragmentation
Sealeopard Offline
KiX Master
*****

Registered: 2001-04-25
Posts: 11162
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
#148955 - 2005-10-01 12:52 AM Re: KiXgolf: Fragmentation
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22344
Loc: OK
nice.
need to think this over but I really liked the story.
_________________________
!

download KiXnet

Top
#148956 - 2005-10-01 01:04 AM Re: KiXgolf: Fragmentation
NTDOC Administrator Offline
Administrator
*****

Registered: 2000-07-28
Posts: 11611
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 Offline
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 Offline
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 Administrator Offline
KiX Supporter
*****

Registered: 2003-04-19
Posts: 4518
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
#148960 - 2005-10-01 01:28 PM Re: KiXgolf: Fragmentation
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22344
Loc: OK
just woke up.
nice to see that Allen is already racing.
_________________________
!

download KiXnet

Top
#148961 - 2005-10-02 02:30 AM Re: KiXgolf: Fragmentation
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22344
Loc: OK
and getting to bed.
the code is still not working. (well, partly passes the tests but...)
_________________________
!

download KiXnet

Top
#148962 - 2005-10-02 06:10 AM Re: KiXgolf: Fragmentation
Allen Administrator Offline
KiX Supporter
*****

Registered: 2003-04-19
Posts: 4518
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
#148963 - 2005-10-02 06:13 AM Re: KiXgolf: Fragmentation
Allen Administrator Offline
KiX Supporter
*****

Registered: 2003-04-19
Posts: 4518
Loc: USA
So where are all the other golfers? Not playing, or having trouble getting it working?
Top
#148964 - 2005-10-02 07:15 AM Re: KiXgolf: Fragmentation
Allen Administrator Offline
KiX Supporter
*****

Registered: 2003-04-19
Posts: 4518
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 Administrator Offline
KiX Supporter
*****

Registered: 2003-04-19
Posts: 4518
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
#148966 - 2005-10-02 10:01 AM Re: KiXgolf: Fragmentation
NTDOC Administrator Offline
Administrator
*****

Registered: 2000-07-28
Posts: 11611
Loc: CA
Well I really did want to play this one, but alas, the whole weekend so far except few bits of time here and there is called for by the family and mini projects. Been building Ikea junk most of the day for the kids. Wow, guess Sweden is expensive - notice that they now have stuff built by other places for them.
Top
#148967 - 2005-10-02 03:51 PM Re: KiXgolf: Fragmentation
Allen Administrator Offline
KiX Supporter
*****

Registered: 2003-04-19
Posts: 4518
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
#148968 - 2005-10-02 10:21 PM Re: KiXgolf: Fragmentation
MightyR1 Offline
MM club member
*****

Registered: 1999-09-09
Posts: 1264
Loc: The Netherlands
Quote:

So where are all the other golfers? Not playing, or having trouble getting it working?




Like I said, busy weekend.
Will start tomorrow @work. There I've got about 8 hours of free time
_________________________
Greetz,
Patrick Rutten

- We'll either find a way or make one...
- Knowledge is power; knowing how to find it is more powerful...
- Problems don't exist; they are challenges...

Top
#148969 - 2005-10-02 10:34 PM Re: KiXgolf: Fragmentation
iffy Offline
Starting to like KiXtart

Registered: 2005-05-29
Posts: 149
Loc: The Netherlands
Hey, I want one of those jobs, where can I send my application?
Top
#148970 - 2005-10-02 11:59 PM Re: KiXgolf: Fragmentation
NTDOC Administrator Offline
Administrator
*****

Registered: 2000-07-28
Posts: 11611
Loc: CA
Unable to download the file. Perhaps someone else could host it.
Top
#148971 - 2005-10-03 12:37 AM Re: KiXgolf: Fragmentation
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22344
Loc: OK
I am stuck with the test 14.
can't understand really why but my code just blows up with it.
_________________________
!

download KiXnet

Top
#148972 - 2005-10-03 01:07 AM Re: KiXgolf: Fragmentation
Allen Administrator Offline
KiX Supporter
*****

Registered: 2003-04-19
Posts: 4518
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
#148973 - 2005-10-03 01:55 AM Re: KiXgolf: Fragmentation
maciep Offline
Korg Regular
*****

Registered: 2002-06-14
Posts: 947
Loc: Pittsburgh
my 264 code works but it's flawed. If i change the order of some of the inputs, it doesn't work.

I have working working code with a score 317

Top
Page 1 of 5 12345>


Moderator:  Arend_, Allen, Jochen, Radimus, Glenn Barnas, ShaneEP, Ruud van Velsen, Mart 
Hop to:
Shout Box

Who's Online
0 registered and 315 anonymous users online.
Newest Members
Praveer, Ollero, rayyo, Foxlicht, DonChild
17742 Registered Users

Generated in 0.044 seconds in which 0.014 seconds were spent on a total of 13 queries. Zlib compression enabled.

Search the board with:
superb Board Search
or try with google:
Google
Web kixtart.org