#191096 - 2008-12-13 06:08 AM
KiXgolf - A Well-Formed Problem
|
Sealeopard
KiX Master
Registered: 2001-04-25
Posts: 11164
Loc: Boston, MA, USA
|
=============
The Challenge - A Well-Formed Problem
=============
XML, eXtensible Markup Language, is poised to become the lingua franca of structured data communication for the foreseeable future, due in part to its strict formatiing requirements. XML parsers must report anything that violates the rules of a well-formed XML document. An XML document is said to be well-formed if it meets all the well-formedness constraints as defined by the World Wide Web Consortium (W3C) XML specification.
XML documents are composed of units called elements, that contain either character data and/or other elements. Elements may also contain within their declaration, values called attributes. Consider the following XML document:
<?xml version="1.0"?>
<customer>
<name>
<first>John</first>
<last>Doe</last>
</name>
<address>
<street>
<number>15</number>
<direction>West</direction>
<name>34th</name>
</street>
<city>New York</city>
<state-code>NY</state-code>
<zip-code format="PLUS4">10001-0001</zip-code>
<country-code>USA</country-code>
</address>
<orders/>
</customer>
The identifiers contained within angle brackets are the elements of the document. The identifer "format" within the "zip-code" element is an attribute of that element. All elements, with the exception of "orders", have a start and an end declaration, also called tags. The "orders" element is an empty element, as indicated by the "/>" sequence that closes the element, and does not require a separate end-tag. The first line is a processing instruction for an XML parser and is not considered an element of the document.
The rules for a well-formed document are:
- There is exactly one element that is not contained within any other element. This element is identified as the "root" or "document" element. In the example above, "customer" is the document element.
- The structure of an XML document must nest properly. An element's start-tag must be paired with a closing end-tag if it is a non-empty element.
- The name in an element's end-tag must match the element type in the start-tag. For example, an element opened with <address> must be closed by </address>.
- No attribute may appear more than once in the same start-tag or empty-element tag.
- A parsed element must not contain a recursive reference to itself. For example, it is improper to include another address element within an address element.
- A named attributed must have an associated value.
- Values for attributes will always be properly enclosed in double quotes.
- The only processing instruction that will be present is the XML version processing instruction, and it will always appear only at the beginning of each document in the input.
- Element and attribute names are case-sensitive. For example, <Address> and <address> are considered to be different.
- Element and attribute names will use only alpha-numeric characters and the dash, "-", character.
A download is available at http://s91376351.onlinehome.us/kixtart/kixgolf_wfp.zip
=============
Inputs & Outputs
=============
The input will contain the filename of an XML document in the script folder. You will need to load and parse the file. The start of each document is identified by a line containing only the processing instruction "<?xml version="1.0"?>". As with all XML documents, white space between elements and attributes should be ignored. You may make the following assumptions with regards to the input.
- XML comments will not appear in the input.
For each input XML document, output a line containing the text "well-formed" if the document is well-formed, and "non well-formed" otherwise.
=======
Scoring
=======
The solution must pass all tests in order for it's KiXgolf Score to be considered.
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.
============
Test program
============
Test cases are provided to help screen entries and to provide the Golf Score.
Explanations of the test cases and the reasons they pass/fail
Test 1 = well-formed
Test 2 = well-formed
Test 3 = well-formed
Test 4 = <errand-list> is a second root element, rule 1
Test 5 = mismatch between opening element <direction> and immediately following closing element <directions>, rules 2 & 3
Test 6 = second identical attribute "format", rule 4
Test 7 = recursive element <city>, rule 5
Test 8 = attribute "format" with no associated value, rule 6
Test 9 = Beginning of document does not contain valid XML version processing instruction, rule 8
Test 10 = Beginning of document does not contain valid XML version processing instruction, rule 8
Test 11 = mismatch between opening element <zip-code> and immediately following closing element <ZIP-code> due to case-sensitivity, rule 9
Test 12 = Invalid character in element "<name@email>", rule 10
Test 13 = Attribute value for element <zip-code> attribute "format" not properly enclosed in quotes, rule 7
Test 14 = well-formed, an element can contain an attribute of the same name
Test 15 = closing element </name> without corresponding opening element <name>, rules 2 & 3
Test 16 = closing root element </name> without corresponding opening root element <name>, rules 2 & 3
Test 17 = well-formed
Test 18 = well-formed
Test 19 = <interm /> is a second root element, rule 1
Test 20 = well-formed
Test 21 = well-formed
Any script that passes the test cases can be submitted. If you are surprised that your solution passed the test cases, 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:
for $b=0 to ubound($a)
if $a[$b]>0
$c=$c+1
endif
next
for a score of 45.
Another solution is:
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 does not generate syntax or other errors when running the script in KiXtart.
4) The final solution MUST pass all test scripts that are part of the KiXtart golf challenge.
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
11) KiXtart Golf (a.k.a KiXgolf) codes must be written inside the KiXgolf UDF collection tags, ';!' and ';!;!'
12) Parameter names of the UDF's can be changed and additional optional parameters can be added.
13) Additional helper UDFs and code can be written as long as they reside inside the ';!' and ';!;!' tags.
14) The use of '$' as a variable is allowed.
15) The UDF layout is up to coder.
16) The UDF is expected to finish in a reasonable time, that is, on modern computers inside 1 hour timeframe.
17) You can submit scores as often as you want.
18) If you reach leading score, you are obligated to post your score immediately so others can try to compete with you.
19) The UDF may only use the KiXtart/KiXforms commands/functions/macros, no other code fragments are allowed.
20) Calls to COM components that are part of a standard default Windows installation are allowed.
21) The use of the KiXforms DLL is also permitted as the KiXforms DLL can now be considered an integral part of KiXtart scripting.
22) Calls to other executables, as long as they are part of a standard default Windows installation are allowed.
23) 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.
24) You may assume ASCII as character set.
25) You may use block comments as the KiXgolf Scoring Engine now supports block comments.
26) You are allowed to only use publicly available versions of KiXtart and KiXforms, private builds or alpha builds are NOT allowed.
27) Your submitted score must include the result print of the KiXgolf test-engine.
28) The SETOPTION() parameters in the KiXgolf script may not be modified and will govern the script behavior. SETOPTION() parameters may change depending on the particular needs of the KiXgolf challenge.
29) Tokenizing the UDF, script, or portions thereof is not allowed.
30) If something is not explicitly denied by the rules, it's allowed.
31) If Confusion arises, arranger of the KiXgolf round has the final say.
32) Additional test cases can be added during the private round by submitting a proposal for a new test case to the BBS. The proposed test case becomes official once it has been added to the existing test cases and the KiXgolf package has been reposted for download. If new test cases are added within 12 hours of private round end the private round will extend by an additional 24 hours. The public round will then start one day later and also end one day later. Not additional test cases will be added during the public round.
================================================================
KiXtart GOLF - The Duration of the Competition
================================================================
1) Private coding phase: 2008-12-13 to 2008-12-19
2) Public coding phase: 2008-12-20 to 2009-01-09
3) Final results: 2009-01-10
You will need the complete package from http://s91376351.onlinehome.us/kixtart/kixgolf_wfp.zip
Edited by Sealeopard (2008-12-17 05:03 AM)
_________________________
There are two types of vessels, submarines and targets.
|
|
Top
|
|
|
|
Moderator: Arend_, Allen, Jochen, Radimus, Glenn Barnas, ShaneEP, Ruud van Velsen, Mart
|
0 registered
and 700 anonymous users online.
|
|
|
