[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: all-XSLT implementation of Minesweeper

Subject: Re: all-XSLT implementation of Minesweeper
From: Sean Whalen <seanwhalen@xxxxxxxxxxx>
Date: Fri, 18 Mar 2005 06:28:29 -0500
yet another implementation of minesweeper
David:
I'd considered using a key, but the code that is there uses a variable that changes with each recursive iteration. I was concerned that the task of limiting the key values in the same way would wipe out any performance benefit. I'll give it a try though. I wasn't really satisfied with how the algorithm ended up.


below is chunk of the code. The $zeros variable contains the area near the user's click that the algorithm has processed. the $field variable contains the the non-bombs that have not been revealed yet. With every iteration, the set contained in $zeros will get larger and what remains in the $field will get smaller. I didn't see a way, built into the Key feature, to get that ability. The practical benefit of reducing the $field each time is that there's no risk of putting a square into the $alreadyRevealed set again. But, yes, I probably could use a key, and add soemthing like "AND NOT IN ($alreadyRevealed)" (that's psuedo-sql, because its 6am here). Also note that all the exisiting code is working with sets of non-bombs, which is likely to be a big ratio of the whole set. So, I was also concerned that a key that was almost as large as the full data set wouldn't be much faster. But I'll give it a try.

<xsl:variable name = "zeros" select = " $alreadyRevealed[@nbc = 0 and @isRevealed = 0]"/>

<xsl:variable name = "field" select = "SweeperMap/square[(@isBomb != -1 and @isRevealed = 0 and not (@sqID = $alreadyRevealed/@sqID )) ]"/>

<xsl:variable name = "revealing" select = "$field[ (...
or (concat(@h -1 ,'/', @v -1) = $zeros/@sqID)
or (concat(@h -1 ,'/', @v +1) = $zeros/@sqID)
...
)



And, while I'm writing, is this really impossible and/or inaccurate:


<xsl:variable name = "revealing" select = "$field[ (...
or (@h -1 = $zeros/@h AND @v + 1 = $zeros/@v)
...
)


I'd played with that kind of syntax for a long time before giving up. The code was returning $zeros/@h AND $zeros/@v values from different elements, which caused chaos. Not that this is related to performance, but is there way a to test 2 attributes like that?
The SQL analogy would be
SELECT field.* from field inner join zeros on field.h +1 = zeros.h and field.v -1 = zeros.v...


or instead, and this would get the whole thing with one hard-to-read line...
SELECT field.* from field inner join zeros on abs(field.h - zeros.h) <=1 and abs( field.v - zeros.v ) <=1


and LOL regarding freecell, et al.


Sean



From: David Carlisle <davidc@xxxxxxxxx>
Subject: Re:  all-XSLT implementation of Minesweeper
Message-Id: <200503171212.MAA04822@xxxxxxxxxxxxxxxxx>

regarding speed, the performance seem to benefit when I changed 2 expressions from "//square" to "SweeperMap/square". But the performances varies a lot by how much free space there is on the map.

similarly you have lots of expresions like this

+ count(//bomb[@h=$rowH -1 and @v=$rowV +1 ])

which are likely to be slow. Even if you change // to a more specific
path this cries out to use a key which would probably change the time
complexity of the algorithm completely as basically it tells the system
to use some space to make some kind of lookup table to find these things
quickly.

something like

<xsl:key name="bomb" match="bomb" use="concat(@h,':',@v)"/>

then replace the above by

+ count(xsl:key('bomb',concat($rowH -1,':',$rowV +1)))

Current Thread

PURCHASE STYLUS STUDIO ONLINE TODAY!

Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
Email
First Name
Last Name
Company
Subscribe in XML format
RSS 2.0
Atom 0.3
Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.