Re: Specifying oxyd shuffling patterns, was: [Enigma-devel] Level "Crossfire in the making"

[Johannes Hüsing]

Ronald Lamprecht <address@hidden> [Thu, Apr 17, 2008 at 10:57:54PM CEST]:
> >>>>>To guarantee fair distributions and levels that are solvable the
> >>>>>author can declare minimum and maximum conditions and groups of
> >>>>>oxyds like:
> >>>>>
> >>>>>wo:shuffleOxyd({grp1, max=0}, {grp1, grp2, min=2},    {grp1, grp3, 
> >>>>>min=1, max=1})

According to your explanation this means that the maximum and minimum 
conditions specify the number of oxyd pairs split up between groups,
correct?

> Johannes Hüsing wrote:
> >There are several ways to restrict permutations. A more obvious one 
> >would be
> >to block the permutation, i.e. to form subgroups within which free 
> >permutation
> >is allowed. I don't know if this is what you mean by "groups".

This would be achieved by setting the maximum condition to 0.

> Minimum and maximum are arbitrary conditions concerning the given object 
> sets. Note that the some objects may even be part in several sets - 
> there are no restrictions at all!

You mean if there are eight oxyds at the corners and the sides, one
group can contain N, NW, W, SW, S, and the other S, SE, E, NE, N?
I'd be lost then at what permutations would be legal then.

Or do you mean that I can define several *partitions* of the set of 
oxyd at once, restricting the number of oxyd pairs shared between 
pairs of subsets in each partition? How does the algorithm determine
if there is a solution?

> Looking at real examples there are never problems. The algorithm will 
> calculate the number of remaining oxyd distributions for a check by the 
> author.

And these distributions will be stored, so the algorithm runs only
once?

> 
> >What do you mean by linear and circular groups?
> 
> A problem analysis from the practical real level world gives you the 
> following usage cases:
> 
> 1. a room/island with the oxyds at the border - the oxyds are arranged
>    on a "circle" and it is sufficient to avoid adjacent oxyd pairs.

OK -- I can imagine how to do this in O(n). 

> 2. a path along which the oxyds are aligned - a "linear" pattern, where
>    it is sufficient to avoid adjacent oxyd pairs, but the end oxyds
>    may match (e.g. your boulder oxyds).

How many times would you have to go back and forth along the path?

> 3. there is a critical path between two groups of oxyds that can only
>    be passed a few times (e.g. a crack) - a maximum condition let us
>    describe these patterns.
> 4. a fair distribution requires that you always have to travel between
>    two oxyd groups a minimum number of times - a minimum condition.
> 

This should also be doable with an O(n) algorithm, as long as there is
only one partition. 

> The further requirements on oxyd shuffling are:
> 
> Besides the 1.01 colored oxyd pairs, 1.10 will support 3 special oxyds 
> colors (fake, fart, bold - see refman). They occur in "any" number and 
> will take in the shuffling process.
> 

Ouch. As each of these stones may occur an arbitrary number of times, 
this means that storing all possible permutations is out of the question.

> Every single oxyd can be excluded from the shuffling process.

Sure, by putting it into a size 1 group.

> 
> At any point within the game the remaining not yet opened oxyds can be 
> reshuffled (by a bold oxyd or a message). All rules have still to be 
> observed.
> 
> All possible shuffling distribution have to occur with the same probability.
> 
> The shuffling has to be very, very fast! There is no requirement to 
> generate all distributions on a real run - we just need a single 
> distribution. 

ok, so no storing of all permutations.

> For test purposes the author should be able to request the 
> number of remaining distributions - this run may take several seconds.
> 

yep, as you cannot know the number without enumerating them. 

> 
> We did well analyse the problem from the mathematical aspect, but we do 
> not want to bother level authors with "permutations", etc.

You are already doing so, only that you say "distribution" instead of
"permutation".

> BTW the problem is mainly a graph theory subject. Andreas did do some 
> research. 

Well, it's combinatorics, which can be represented by graph theory,
though not exhaustively.

> But the published algorithms do either not fit the complex requirements 
> or they are to slow and fat (as they do calculate all distributions). My 
> algorithm is in praxis linear to the numbers of used oxyds :-)

I'd be interested as to how you achieve this with mutiple partitions
(if you use them). Maybe it's time to look at the source.



-- 
Johannes Hüsing               There is something fascinating about science. 
                              One gets such wholesale returns of conjecture 
mailto:address@hidden  from such a trifling investment of fact.                
http://derwisch.wikidot.com         (Mark Twain, "Life on the Mississippi")