Long time no see. I have a puzzle that's eating me for more than a week and I think you'll like working on it Credits in "spoilers".
Assume you have a cylinder around which you've wrapped a rectangular grid of cells (R rows x C columns). Each cell contains an integer greater or equal to 1. Each integer is equal to the number of neighboring cells (neighbor = sharing an edge, not just a corner) having the same integer. E.g. a cell containing 1 can have exactly one neighbor cell with 1 inside, the other neighbors can have any other different integers.
Two decorations are the same if by rotating (around the cylinder's axis of symmetry) one of the cylinders (whole rectangular grid rotation - rotating rows/columns separately is not possible) and putting them side to side you can view them as identical from any viewpoint. Also, the top and bottom of the cylinder are considered as being different so if the rectangular grid is not symmetrical around the cylinder's half-full/half-empty axis, a cylinder decoration identical to the original turned up-side down would count as not the same as the original.
How many unique decorations can you make with such a RxC cylinder?
1. For R,C <=6.
2. A closed-form expression or algorithm for any R,C.
Note: I am stuck at 2. I have an algorithm, but I'm rather more interested if there is a closed-form expression i.e. using basic arithmetic operations (addition, subtraction, multiplication, and division), exponentiation to a real exponent, logarithms, and trigonometric functions.
Posted with more flavor during CodeJam2015 Round 2 Problem D which is licensed under the
Question
araver
Long time no see. I have a puzzle that's eating me for more than a week and I think you'll like working on it
Credits in "spoilers".
Assume you have a cylinder around which you've wrapped a rectangular grid of cells (R rows x C columns). Each cell contains an integer greater or equal to 1. Each integer is equal to the number of neighboring cells (neighbor = sharing an edge, not just a corner) having the same integer. E.g. a cell containing 1 can have exactly one neighbor cell with 1 inside, the other neighbors can have any other different integers.
Two decorations are the same if by rotating (around the cylinder's axis of symmetry) one of the cylinders (whole rectangular grid rotation - rotating rows/columns separately is not possible) and putting them side to side you can view them as identical from any viewpoint. Also, the top and bottom of the cylinder are considered as being different so if the rectangular grid is not symmetrical around the cylinder's half-full/half-empty axis, a cylinder decoration identical to the original turned up-side down would count as not the same as the original.
How many unique decorations can you make with such a RxC cylinder?
1. For R,C <=6.
2. A closed-form expression or algorithm for any R,C.
Note: I am stuck at 2. I have an algorithm, but I'm rather more interested if there is a closed-form expression i.e. using basic arithmetic operations (addition, subtraction, multiplication, and division), exponentiation to a real exponent, logarithms, and trigonometric functions.
Link to comment
Share on other sites
2 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.