Friday, November 06, 2020

[xqullteh] data representation of doors in a hypercubic maze

consider a d-dimensional hypercubic brick composed of unit hypercubes.  let there be a door between all pairs of adjacent hypercubes.  the doors pass through (d-1)-dimensional unit hypercubic facets.

how many doors are there?

key observation: in 1D, there are n-1 doors between n cells.

4D: (a-1)bcd + a(b-1)cd + ab(c-1)d + abc(d-1)

xyz=product(d=1, dimensions, e[d]); sum(d=1, dimensions, xyz*(e[d]-1)/e[d])

for a 2^d hypercube (edge length 2 in each direction):

1d = 1 door
2d = 4 doors
3d = 12 doors

create a data structure that doesn't waste space that can be used to quickly look up the state of each door (open, closed).  "doesn't waste space" means incorporates the n-1 terms, in contrast to d*xyz which wastes space.  address doors by cell coordinates and direction traveling (along which dimension).

this is probably not too difficult, just a little bit annoying.  figure out the direction, then treat that dimension specially.  maybe tricky if we want to support an arbitrary number of dimensions.

No comments :