Mike and I now both have code (his is Python, mine is Haskell) that come up with the same values for between 2 and 6 landmark types (not run on larger n, the Haskell code isn't very clean and is quite slow). We're using the same memory optimisation though so it would be good to get an independent set of figures. Anybody else up for writing some code to brute force it to check the equations against? If Mike and I are correct then the equations proposed so far undercount the actual number of locations (but not by much).
In a final effort, i revisited my formula and I have this now:
def loc(x):
return (x**8 + x**4 + 4*x**5 - 2*x**3 + 4*x**2)/8
Output:
2 : 50
3 : 949
4 : 8728
Mike just told me that my numbers are very close, but I just cannot get it right. The next step would be to actually generate the values and compare with the brute forced ones.
JordiB saidCould you perhaps comment on how you arrived at this formula?
I will try to explain my model:
The basic formula is
L = L1 + L2 + L4a + L4s + L8a + L8s
where
L: Total number of locations
L1: Locations that can be expressed with one repeated landmark (r-r-r-r-r-r-r-r)
L2: … two repeated landmarks (r-h-r-h-r-h-r-h) and not L1
L4s: … a repeated string of four landmarks with symmetry (r-h-o-h-r-h-o-h) and none of the above
L4a: … without symmetry (r-h-o-o-r-h-o-o) and none of the above
L8s: … eight landmarks with symmetry (r-r-h-h-o-h-h-r) and none of the above
L8a: … without symmetry (r-h-h-h-h-o-o-o) and none of the above
Keeping these groups mutually exclusive is the tricky part, but here's my shot at it (x is number of distinct landmarks):
L1 = x
No problem here
L2 = x^2 - x
We have to subtract x so we don't count L1 twice
L4s = (x^3 - x^2) / 2
In a repeating 4-tuple with symmetry, the second and fourth (and sixth and eighth) landmark will always be the same, hence there are x^3 representations to fit this characteristic. After we subtract L1 and L2, every location in this set will have exactly 2 representations, therefore we divide by 2.
L4a = (x^4 - x^3) / 4
Basically I'm taking all possible 4-tuples and subtract the ones where the second and fourth position are the same. Note that those already include all of the above sets. The remaining set of locations is represented 4 times each (rotated and mirrored), so I divide by 4. Quick example:
r-o-o-r-r-o-o-r
o-r-r-o-o-r-r-o
r-r-o-o-r-r-o-o
o-o-r-r-o-o-r-r
L8s = (x^5 - x^3)
An 8-tuple that is symmetric will have spots 2, 3 and 4 mirrored in 8, 7 and 6. Therefore there is a total of x^5 combination with this characteristic. Subtract any representations for locations in L4s (x^3 - x^2), L2 (x^2 - x) and L1 (x), and we should be left with a nice exclusive group of locations that have one representation each, so we don't divide by anything.
L8a = ((x^8 - x^4) - 4 * (x^5 - x^3)) / 8
This is where keeping the set exclusive gets a real pain in the ass, but luckily it's the last step. (x^8 - x^4) are all representations that are not repeated 4-tuples. These also contain 4 (rotated) representations of every element of L8s, so we subtract 4 * (x^5 - x^3). The remaining set of locations is represented 8 times (mirrored and rotated) so we divide by eight.
Putting it all together and contracting the formula, we get the values above.
