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
d*(2^(d-1))
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:
Post a Comment