Description
Your exceedingly wealthy uncle, Sir Capitus Tet, from whom you eventually hope to
obtain a significant inheritance has asked for your help with a problem. He has in his
possession a large supply of various carpet pieces – each consists of four squares joined
side to side, and they are in various colours as shown below. He also has, in his vast
mansion, various hallways which he’d like to carpet by sewing the pieces together side
to side to form an unbroken rectangle. As a matter of intellectual curiosity, he would
like to know – given the dimension of a carpet (measured in units of the squares that
make up the individual pieces), how many different ways are there to fit together some
pieces to form such a carpet?
The carpet pieces:
A completed carpet of width 4 and length 6:
For these purposes, two carpets are considered different if they look different from the
perspective of an observer at one end. That is, a carpet will (generally, though not
always) be different from its rotation by 180 degrees. As seen in the example, pieces
can be rotated, though of course they can’t be flipped over.
Task
This task uses the standard input/output format. A scenario consists of two numbers
– a width (which will be at most 6 squares) and a length (at most 100 squares). The
output for the scenario is the exact number of possible carpets of that width and length.
This may well require extended precision arithmetic (i.e., the answer may not fit in a
standard machine-sized integer), and you may use libraries such as BigInteger to
allow for this (or your own package from etude 8). ´
(3 point, Group)
