This is a java project and I am really frustrated to work on this.

I know it is a heavy work and I really need help on this. Please help me. Thank you guys.

Packing shapes into fixed size containers is an old problem with continued applications, particularly in shipping and handling services. For example, online retailers may seek to pack as many items in an order as possible into a single box to reduce shipping costs. On a larger scale, packing shipping containers onto oceanic container ships that travel around the world devolves to the same basic problem of packing a set of objects into a fixed volume.

This project will focus on a problem in this class which has the following properties.

Spaces and Shapes

The space into which shapes will be packed is a rectangle comprised of blocks which are empty or filled. Each block in a space is referenced by its row/column coordinate which starts at 0 (in the upper-left corner).

........ .......| .....||| 

The dots (periods) represent empty blocks into which shapes may be put while the permanently filled blocks are drawn as vertical lines (pipes). For clarity, here is the same space with numbers around it to indicate the rows and columns.

 01234567 0 ........ 0 1 .......| 1 2 .....||| 2 01234567 

The space has height 3 and width 8. All blocks are empty except the following filled blocks: (1,7), (2,5), (2,6), (2,7).

There is no requirement that permanently filled blocks must exist on the edges of the space or be contiguous. The following is another valid space demonstrating the arbitrariness of filled block placement.

|....... ..|||..| ..|.|... ........ 

A shape is a rectangular grid of blocks which are filled or empty. For example here are a few all-too familiar shapes.

SHAPE T TTTT SHAPE e ..e eee SHAPE t .t. ttt SHAPE r rr rr SHAPE i i.. iii SHAPE s .ss ss. 

As with a space, a shape represents empty blocks with a period but filled blocks are represented using any other character aside from newlines. By convention, shapes will usually have a single display characterassociated with them which will be used for their filled blocks.

Note: Shapes will be restricted to contain a non-empty border: the 0th row, 0th column, last row, and last column must all contain at least one filled block. For more information refer to the section on illegal layout strings.

Placing Shapes in Spaces

Shapes may be placed into a space if there are no conflicts (overlaps) with any filled blocks (including other shapes). The placement locations indicates where the upper left (0,0) block of the shape would be located in the space. Consider the space and shape below.

SPACE |....... ..|||..| ..|.|... ........ SHAPE i i.. iii 

Placing the shape at block (2,5) would lead the space to look like the following

Shape at (2,5) 01234567 0 |....... 0 1 ..|||..| 1 2 ..|.|i.. 2 3 .....iii 3 01234567 

On the other hand, the shape might be placed at location (2,0).

Shape at (2,0) 01234567 0 |....... 0 1 ..|||..| 1 2 i.|.|... 2 3 iii..... 3 01234567 

Note that the block (2,2) is filled in the space. This is not a problem as the shape has an empty block in that position so it fits at (2,0) nicely. However, attempting to place the shape at (0,0) would lead to several filled blocks in the shape conflicting with filled blocks in the space and should result in an error.

Even if block (0,0) of a shape is empty, it is still used to indicate shape placement. Consider the space and shape below.

SPACE |....... ..|||..| ..|.|... ........ SHAPE t .t. ttt 

Block (0,0) of the shape is empty and can overlap with other filled blocks. The following are some of the valid locations where the shape may be placed. Note the row/column locations indicate where the upper left empty block of the shape will be placed.

Shape at (2,4) 01234567 0 |....... 0 1 ..|||..| 1 2 ..|.|t.. 2 3 ....ttt. 3 01234567 Shape at (2,5) 01234567 0 |....... 0 1 ..|||..| 1 2 ..|.|.t. 2 3 .....ttt 3 01234567 Shape at (1,5) 01234567 0 |....... 0 1 ..|||.t| 1 2 ..|.|ttt 2 3 ........ 3 01234567 Shape at (2,2) 01234567 0 |....... 0 1 ..|||..| 1 2 ..|t|... 2 3 ..ttt... 3 01234567 

Fitting Shapes into a Space

The central problem you will need to solve is whether a give list of shapes can all be fit together into a given space. For example consider the following space and shapes.

SPACE |....... ..|||..| ..|.|... ........ SHAPE T TTTT SHAPE e ..e eee SHAPE r rr rr SHAPE i i.. iii SHAPE s .ss ss. 

One possible fit of the shapes in the space is as follows.

|TTTT.ss rr|||ss| rr|e|i.. .eee.iii 

There may be other fits but you will primarily be responsible for determining if at least one exists and producing one. This is not always possible. For example if the shape

SHAPE t .t. ttt 

is added to the above, there is no way to fit all the shapes in the given space without changing the shapes (rotations are discussed in the next section).

Packing shapes into a space constitutes a computationally difficult problem and is almost certainly in the NP-hard complexity class. In simple terms, this means that to solve the problem, one may be reduced to searching every possible arrangement of shapes in a space to see if any works. While this is feasible for small numbers of shapes and spaces, it becomes intractable for large spaces and long lists of shapes as there are so many possibilities.

Shape Rotations

Shapes can be rotated in 90 degree increments to open up more potential packing solutions. Your implementation will be required to allow shapes to rotate clockwise in increments of 90 degrees. There are therefore 4 possible rotations of each shape referred to as follows.

CW0: no rotation

CW90: 90 degree rotation clockwise

CW180: 180 degree rotation clockwise

CW270: 270 degree rotation clockwise

Consider the following shape and its four valid rotations.

SHAPE t .t. ttt SHAPE t height: 2; width: 3; rotation: CW0 .t. ttt SHAPE t height: 3; width: 2; rotation: CW90 t. tt t. SHAPE t height: 2; width: 3; rotation: CW180 ttt .t. SHAPE t height: 3; width: 2; rotation: CW270 .t tt .t 

Notice that the height and width of the shape changes with rotations and the positions of the filled blocks change with each rotation.

If the initial orientation of the shape were different, then the rotations would be altered as is the case with the shape below.

SHAPE x x. xx x. SHAPE x height: 3; width: 2; rotation: CW0 x. xx x. SHAPE x height: 2; width: 3; rotation: CW90 xxx .x. SHAPE x height: 3; width: 2; rotation: CW180 .x xx .x SHAPE x height: 2; width: 3; rotation: CW270 .x. xxx 

It should be clear however that Shape t and Shape x are equivalent under rotations in terms of how they can be fit into a space.

Some shapes do not change on every rotation. This may lead to some redundancy in during search and among solutions to fitting problems but you are not required to deal with this in any special way. Examples:

SHAPE T TTTT SHAPE T height: 1; width: 4; rotation: CW0 TTTT SHAPE T height: 4; width: 1; rotation: CW90 T T T T SHAPE T height: 1; width: 4; rotation: CW180 TTTT SHAPE T height: 4; width: 1; rotation: CW270 T T T T SHAPE r rr rr SHAPE r height: 2; width: 2; rotation: CW0 rr rr SHAPE r height: 2; width: 2; rotation: CW90 rr rr SHAPE r height: 2; width: 2; rotation: CW180 rr rr SHAPE r height: 2; width: 2; rotation: CW270 rr rr 

The closing example of the last section involved the following space and shapes for which there was no fit without rotations.

SPACE |....... ..|||..| ..|.|... ........ SHAPE T TTTT SHAPE e ..e eee SHAPE t .t. ttt SHAPE r rr rr SHAPE i i.. iii SHAPE s .ss ss. 

However, with the introduction of rotations, a solution does exist. Some additional detail is given at the bottom indicating the state of each shape found.

FOUND FIT SPACE: height: 4 width: 8 |tTTTTss tt|||ss| it|.|err iiieeerr 6 shapes placed Shape at (0,2) SHAPE T height: 1; width: 4; rotation: CW0 TTTT Shape at (2,3) SHAPE e height: 2; width: 3; rotation: CW0 ..e eee Shape at (2,0) SHAPE i height: 2; width: 3; rotation: CW0 i.. iii Shape at (2,6) SHAPE r height: 2; width: 2; rotation: CW0 rr rr Shape at (0,5) SHAPE s height: 2; width: 3; rotation: CW0 .ss ss. Shape at (0,0) SHAPE t height: 3; width: 2; rotation: CW270 .t tt .t 

Implementation Issues

Representation of Spaces and Shapes

One of your primary tasks in solving this problem is to design classes that represent the notions of shapes and spaces. Unlike previous projects, you are not required to use any specific internal structure of the data for these classes. You should read the section Required Design Elements to keep in mind some required methods as specified in a few interfaces, but aside from the presence of the public methods mentioned there, you are free to implement your solution using any number of classes you feel is necessary. The public interfaces required give some guidance as to what should be done but you will need to do some planning about how to surmount the problems faced by these classes. Your solutions will need to be described in your design.txt document. Consider the following issues while designing your classes.

Shapes and Spaces need a way to keep track of their size (height and width) along with which blocks in their grid are filled and empty. There are several ways to do this such as using arrays, using lists of pairs, or other classes.

Shapes will need to be rotated (Spaces do not rotate). On rotation, the Shapes size (height/width) may change and its configuration of filled and empty blocks may also change. You only need to accommodate single clock-wise rotations by 90 degrees but this may happen multiple times. You will need to do some research to figure out how to transform the blocks in a Shape to reflect the rotation that was done. Some internet research may be helpful for this but make sure to include a comment string with any sources drawn from.

Spaces will need a way to detect whether a Shape can fit at a given location or if any filled blocks in the shape would be out of bounds, overlap with a permanently filled block, or overlap with the filled blocks of another shape that has been placed in the space. Code-wise this will look the following.

Shape shape = ...; Space space = ...; boolean fits = space.shapeFitsAt(1,3,shape); // true if the shape would fit, false otherwise 

Spaces will need a way to add shapes to themselves. Adding is done via placement of the shape in the space by passing in a shape along with its placement location. This uses the shape's current rotation.

Shape aShape = ...; Space space = ...; space.placeShapeAt(1,3,aShape); // space now contains aShape 

Spaces can produce string representations of themselves e.g. using the fitString() method and list out their currently placed shapes using the placedShapeInfo(). Placed shapes must be shown sorted by their display character.

Spaces can remove shapes by their display character. For example:

Shape aShape = ...; // display character is a Space bShape = ...; // display character is b space.placeShapeAt(1,3,aShape); space.placeShapeAt(4,0,bShape); space.removeShapeByDisplayChar(aShape.getDisplayChar()); // space no longer contains aShape space.removeShapeByDisplayChar('b'); // space no longer contains bShape 

Shapes and Spaces will be initialized using a layout string that is described in more detail in the Layout String Formats section.

Recursive Search for Fit

The primary objective of your implementation is to search for a fit of all of a given list of shapes into a space. You will specify a method in the FitIt class called

Space searchForFit(Space space, List unplaced) 

which will return either null if no fit exists or a space which is filled with the given list of shapes.

searcForFit() is best implemented recursively. It solves a search problem involving backtracking: while trying out candidate placement for shape X, another shape Y may not also be able to fit, in which case the method must back up and attempt to try another placement of shape X.

As an example, consider the following problem.

SPACE .. .. .| SHAPE a aa SHAPE b bbb 

An obvious strategy for an algorithm is to try placing Shape a at all possible locations with all possible rotations, then attempt the same for Shape b. For example a first attempt might place Shape a at (0,0)with no rotation (CW0).

Trying a rot:CW0 at (0,0)... Fits aa .. .| 

Unfortunately, this does not allow Shape b to be fit into the space. Consider all the possible location/rotation combinations which do not work.

Trying b rot:CW0 at (0,0)... No fit Trying b rot:CW90 at (0,0)... No fit Trying b rot:CW180 at (0,0)... No fit Trying b rot:CW270 at (0,0)... No fit Trying b rot:CW0 at (0,1)... No fit Trying b rot:CW90 at (0,1)... No fit Trying b rot:CW180 at (0,1)... No fit Trying b rot:CW270 at (0,1)... No fit Trying b rot:CW0 at (1,0)... No fit Trying b rot:CW90 at (1,0)... No fit Trying b rot:CW180 at (1,0)... No fit Trying b rot:CW270 at (1,0)... No fit Trying b rot:CW0 at (1,1)... No fit Trying b rot:CW90 at (1,1)... No fit Trying b rot:CW180 at (1,1)... No fit Trying b rot:CW270 at (1,1)... No fit Trying b rot:CW0 at (2,0)... No fit Trying b rot:CW90 at (2,0)... No fit Trying b rot:CW180 at (2,0)... No fit Trying b rot:CW270 at (2,0)... No fit Trying b rot:CW0 at (2,1)... No fit Trying b rot:CW90 at (2,1)... No fit Trying b rot:CW180 at (2,1)... No fit Trying b rot:CW270 at (2,1)... No fit 

At this point, there is no choice but to give up on the original placement of Shape a

Giving up on shape b in aa .. .| 

and try a different placement of it. Importantly, this is the notion of backtracking: one solution path did not work out so we must back up and try another direction to see if it leads to more success.

Trying a rot:CW90 at (0,0)... Fits a. a. .| 

To most humans, this placement for Shape a is equally as bad and will result in no fit being found for Shape b. This is because most humans are good at small constraint problems like this and recognize where Shape a should be placed. However, any such intuition would need to be encoded into an algorithm and it is far easier to simply enumerate all possible placements of shapes.

Eventually, the following placement of Shape a is made.

Trying a rot:CW90 at (0,1)... Fits .a .a .| 

This is the choice most humans would make right off the bat. After this, there is not much left in terms of search.

Trying b rot:CW0 at (0,0)... No fit Trying b rot:CW90 at (0,0)... Fits ba ba b| All shapes placed FOUND FIT SPACE: height: 3 width: 2 ba ba b| 2 shapes placed Shape at (0,1) SHAPE a height: 2; width: 1; rotation: CW90 a a Shape at (0,0) SHAPE b height: 3; width: 1; rotation: CW90 b b b 

Backtracking and Recursive Search

The notion of backtracking is rather easy to implement in a recursive method if you identify two base cases: a base case for success and a base case for failure. Complementing these two base cases is a recursivecase in which calls for further search via a recursive call. In a recursive implementation of searchForFit(space,unplacedShapes) these cases are roughly as follows.

Success Base Case

The list unplacedShapes is empty so all shapes have been placed and the space currently contains a solution that should be returned.

Failure Base Case

The list unplacedShapes is not empty. A single Shape S is removed from it but there is no place in space to fit S. No solution exists for the current configuration of space so a failure should be signaled by returning null. S should go back into the list of unplacedShapes.

Recursive Case

The list unplacedShapes is not empty. A single Shape S is removed from it and a valid placement is found for S in space. Place S at the valid location in space, remove it from the unplacedShapes list, and recursively call searchForFit(). If the recursive call results in a success, return it. If it results in a failure, try a different placement of S in space.

Do not be seduced into thinking that the above description can be mechanically translated into a code version of searchForFit(): you will need to master the ideas presented there and experiment with the ordering of operations in order to implement the method correctly. This will take some time and effort.

A great boon while coding this effort is the ability to see exactly what is going on at any given moment. You are highly encouraged to use debugging print statements that allow you to see the progress of your algorithm. As an example, here is the whole debugging output for the problem in the previous section. You may use this as a model for your own debugging output or use a different style. It is very likely that teaching staff will want to see debugging output if you need help on searchForFit() and you will expedite your help by providing it.

SPACE: height: 3 width: 2 .. .. .| 0 shapes placed 2 shapes read SHAPE a height: 1; width: 2; rotation: CW0 aa SHAPE b height: 1; width: 3; rotation: CW0 bbb Trying a rot:CW0 at (0,0)... Fits aa .. .| Trying b rot:CW0 at (0,0)... No fit Trying b rot:CW90 at (0,0)... No fit Trying b rot:CW180 at (0,0)... No fit Trying b rot:CW270 at (0,0)... No fit Trying b rot:CW0 at (0,1)... No fit Trying b rot:CW90 at (0,1)... No fit Trying b rot:CW180 at (0,1)... No fit Trying b rot:CW270 at (0,1)... No fit Trying b rot:CW0 at (1,0)... No fit Trying b rot:CW90 at (1,0)... No fit Trying b rot:CW180 at (1,0)... No fit Trying b rot:CW270 at (1,0)... No fit Trying b rot:CW0 at (1,1)... No fit Trying b rot:CW90 at (1,1)... No fit Trying b rot:CW180 at (1,1)... No fit Trying b rot:CW270 at (1,1)... No fit Trying b rot:CW0 at (2,0)... No fit Trying b rot:CW90 at (2,0)... No fit Trying b rot:CW180 at (2,0)... No fit Trying b rot:CW270 at (2,0)... No fit Trying b rot:CW0 at (2,1)... No fit Trying b rot:CW90 at (2,1)... No fit Trying b rot:CW180 at (2,1)... No fit Trying b rot:CW270 at (2,1)... No fit Giving up on shape b in aa .. .| Removing a rot:CW0 from (0,0) Trying a rot:CW90 at (0,0)... Fits a. a. .| Trying b rot:CW0 at (0,0)... No fit Trying b rot:CW90 at (0,0)... No fit Trying b rot:CW180 at (0,0)... No fit Trying b rot:CW270 at (0,0)... No fit Trying b rot:CW0 at (0,1)... No fit Trying b rot:CW90 at (0,1)... No fit Trying b rot:CW180 at (0,1)... No fit Trying b rot:CW270 at (0,1)... No fit Trying b rot:CW0 at (1,0)... No fit Trying b rot:CW90 at (1,0)... No fit Trying b rot:CW180 at (1,0)... No fit Trying b rot:CW270 at (1,0)... No fit Trying b rot:CW0 at (1,1)... No fit Trying b rot:CW90 at (1,1)... No fit Trying b rot:CW180 at (1,1)... No fit Trying b rot:CW270 at (1,1)... No fit Trying b rot:CW0 at (2,0)... No fit Trying b rot:CW90 at (2,0)... No fit Trying b rot:CW180 at (2,0)... No fit Trying b rot:CW270 at (2,0)... No fit Trying b rot:CW0 at (2,1)... No fit Trying b rot:CW90 at (2,1)... No fit Trying b rot:CW180 at (2,1)... No fit Trying b rot:CW270 at (2,1)... No fit Giving up on shape b in a. a. .| Removing a rot:CW90 from (0,0) Trying a rot:CW180 at (0,0)... Fits aa .. .| Trying b rot:CW0 at (0,0)... No fit Trying b rot:CW90 at (0,0)... No fit Trying b rot:CW180 at (0,0)... No fit Trying b rot:CW270 at (0,0)... No fit Trying b rot:CW0 at (0,1)... No fit Trying b rot:CW90 at (0,1)... No fit Trying b rot:CW180 at (0,1)... No fit Trying b rot:CW270 at (0,1)... No fit Trying b rot:CW0 at (1,0)... No fit Trying b rot:CW90 at (1,0)... No fit Trying b rot:CW180 at (1,0)... No fit Trying b rot:CW270 at (1,0)... No fit Trying b rot:CW0 at (1,1)... No fit Trying b rot:CW90 at (1,1)... No fit Trying b rot:CW180 at (1,1)... No fit Trying b rot:CW270 at (1,1)... No fit Trying b rot:CW0 at (2,0)... No fit Trying b rot:CW90 at (2,0)... No fit Trying b rot:CW180 at (2,0)... No fit Trying b rot:CW270 at (2,0)... No fit Trying b rot:CW0 at (2,1)... No fit Trying b rot:CW90 at (2,1)... No fit Trying b rot:CW180 at (2,1)... No fit Trying b rot:CW270 at (2,1)... No fit Giving up on shape b in aa .. .| Removing a rot:CW180 from (0,0) Trying a rot:CW270 at (0,0)... Fits a. a. .| Trying b rot:CW0 at (0,0)... No fit Trying b rot:CW90 at (0,0)... No fit Trying b rot:CW180 at (0,0)... No fit Trying b rot:CW270 at (0,0)... No fit Trying b rot:CW0 at (0,1)... No fit Trying b rot:CW90 at (0,1)... No fit Trying b rot:CW180 at (0,1)... No fit Trying b rot:CW270 at (0,1)... No fit Trying b rot:CW0 at (1,0)... No fit Trying b rot:CW90 at (1,0)... No fit Trying b rot:CW180 at (1,0)... No fit Trying b rot:CW270 at (1,0)... No fit Trying b rot:CW0 at (1,1)... No fit Trying b rot:CW90 at (1,1)... No fit Trying b rot:CW180 at (1,1)... No fit Trying b rot:CW270 at (1,1)... No fit Trying b rot:CW0 at (2,0)... No fit Trying b rot:CW90 at (2,0)... No fit Trying b rot:CW180 at (2,0)... No fit Trying b rot:CW270 at (2,0)... No fit Trying b rot:CW0 at (2,1)... No fit Trying b rot:CW90 at (2,1)... No fit Trying b rot:CW180 at (2,1)... No fit Trying b rot:CW270 at (2,1)... No fit Giving up on shape b in a. a. .| Removing a rot:CW270 from (0,0) Trying a rot:CW0 at (0,1)... No fit Trying a rot:CW90 at (0,1)... Fits .a .a .| Trying b rot:CW0 at (0,0)... No fit Trying b rot:CW90 at (0,0)... Fits ba ba b| All shapes placed FOUND FIT SPACE: height: 3 width: 2 ba ba b| 2 shapes placed Shape at (0,1) SHAPE a height: 2; width: 1; rotation: CW90 a a Shape at (0,0) SHAPE b height: 3; width: 1; rotation: CW90 b b b 

Required Design Elements

Top-level Methods: FitIt.java

There are four required methods in the FitIt class which you must implement, though two of these simply call constructors you will write in your own designed classes. These methods are shown below in the overview of FitIt.java. They reference several of the interfaces shown subsequently. The Layout String and File Format section describes in more detail the type of string that will be passed in to the the makeShape() and makeSpace() method and the file format for input to main().

public class FitIt{ // Factory methd to produce shapes. Call a constructor for one of // your own classes here. The layout given is be in the format // // ..e // eee // // Newlines ( ) show breaks in the rows of the Shape. The period // (.) is used to represent empty blocks. Any other character is a // filled block even if it does not match the given displayChar. // The Shape returned by this method should have the display // character displayChar even if that character does not appear in // the layout string. Shapes should be initialized to have rotation // CW0. If the shape contains any empty border sides, throw a // FitItException with an informative message. public static Shape makeShape(String layout,char displayChar); // Factory method to produce instances of space. Call a constructor // for one of your own classes here. The layout parameter will be in // the format // // |....... // ..|||..| // ..|.|... // ........ // // where vertical bars are filled blocks and periods are empty blocks. public static Space makeSpace(String layout); // Search for a fit of the given shapes in the given space. Return // null if no fit exists. If a fit is found, return a space with all // shapes placed in it. It is very useful for this method to be // recursive. public static Space searchForFit(Space space, List unplaced); // Search for a all fits accumulating answers in the answers // parameter list. public static void searchForAllFits(Space space, List unplaced, List answers); // Read an input file which contains a fitting problem in it. The // input file is the zeroth command line argument. The file format // contains records for SPACE and SHAPE. There should only be one // SPACE per file but potentially many SHAPEs. SHAPE is followed by // a display character for the shape. SPACE and SHAPE records // continue until a black line. Any line that does not start with // SPACE or SHAPE should be ignored. The main method should read // this file, initialize spaces and shapes using the methods // makeShape() and makeSpace(). It should then execute // searchforFit(space,shapes) and report the results as either // // NO FIT FOUND // // or // // FOUND FIT // then call the toString() method of space // // Main should take one or two arguments. The first argument is an // input problem file. If there is only one argument, print to the // screen. Example: // // > java FitIt problem.txt // // If there are two arguments, the second argument is the name of a // file that should be printed into rather than printing to the // screen. Example // // > java FitIt problem.txt output.txt // // If the first argument refers to a non-existant file, throw any // kind of exception. public static void main(String args[]) throws Exception; } 

Shape Interface

The Shape interface is provided in the code pack but like all interfaces, it specifies only what an implementing class can do, not how to do it. You will need to create a class or classes which implements Shapeand is returned by the FitIt.makeShape() method. Some methods refer to the Rotation enumeration which is described in a subsequent section. All classes implementing Shape must have the following methods.

// A shape is a rectangular grid of filled and empty blocks. They can // be rotated clockwise (CW) in increments of 90 degrees and track // their rotation using the Rotation enumeration. Shapes can be // displayed in text terminals and have a display character which // dictates how they are shown. public interface Shape{ // Return the number of rows of the shape public int getHeight(); // Return the number of columns of the shape public int getWidth(); // When drawing this shape in a text terminal, the character // returned by displayChar will be used public char getDisplayChar(); // Set how the shape will be displayed in text terminals public void setDisplayChar(char c); // Rotate this shape clockwise by 90 degrees. Adjust all internal // state required to achieve the rotation including height and width public void rotateCW(); // Return a value from the Rotations enumeration indicating how // much the shape has been rotated from its original position. public Rotation getRotation(); // Return true if the shape has a filled block at the given row/col // position and false if the block is empty. If the position is out // of bounds, raise a FitItException with an informative message. public boolean isFilledAt(int row, int col); // Create a string representation of the shape. The format must // follow this convention: // // SHAPE c // height: 2; width: 3; rotation: CW270 // ..c // ccc public String toString(); } 

Space Interface

The Space interface is also provided in the code pack and you will need to implement one or more classes which cooperate to fulfill the interface requirements.

// A Space is a rectangular grid of empty and filled blocks. On being // initialized, some blocks of a space are permanently filled. // Instances of Shape may be placed in the space so long as they are // in bounds and do not conflict with any filled blocks. Space classes // provide mechanisms to check whether shapes fit at a location in the // space, place shapes at a location, remove shapes, and display the // present contents of the space. public interface Space{ // Return the number of rows of the space public int getHeight(); // Return the number of columns of the space public int getWidth(); // Return true if the space has a filled block at the given row/col // position and false if the block is empty. A block may be filled // if it is permanently filled or if a shape has been placed in a // position such that the space's block is filled by the shape's block // If the position is out of bounds, return true as there is implicit // fill all around the space. DO NOT THROW EXCEPTIONS from this // method. public boolean isFilledAt(int row, int col); // Determine if the given shape may be placed at the indicated // row/col position. The row,col indicates where the upper left // corner [block (0,0)] of the shape would be placed. A shape would // not fit if one of its filled blocks would conflict with an // existing filled block in the space or would be out of bounds in // the space. public boolean shapeFitsAt(int row, int col, Shape shape); // Place the given shape at the given row/col position. The row,col // indicates where the upper left corner [block (0,0)] of the shape // would be placed. The shape should be removable and when // displaying info on the placed shapes, they must be shown in order // of their display characters (shape A before B before C...). // There may be more than one shape in a space with the same display // character. If the shape would not fit at the specified row/col // position, raise a FitItException with an informative message. public void placeShapeAt(int row, int col, Shape shape); // Remove the shape with the display character indicated by dc from this // space. Update all internal state so that blocks in the space that // were filled by the removed shape are emptied. public void removeShapeByDisplayChar(char dc); // Return how many shapes have been placed in this space. public int placedShapeCount(); // Return a string representing the space and the shapes that have // been fit into it. The following character conventions must be // used. // | : vertical bar for permanently filled blocks // . : period for empty blocks // displaychar : any space filled by a shape uses its display char // // Example: // aa.....e // aacddd.| // cccdd||| public String fitString(); // Give a listing of all the placed shapes. This should start with // the number of placed shapes, show the position of each shape, and // use the toString() of each shape. Shapes must be reported in // sorted order based on their display character (shape A before B // before C...). // // Example: // // 3 shapes placed // Shape at (0,0) // SHAPE a // height: 2 width: 2 rotation: CW90 // aa // aa // // Shape at (0,2) // SHAPE b // height: 1 width: 4 rotation: CW180 // bbbb // // Shape at (1,0) // SHAPE c // height: 2 width: 3 rotation: CW270 // ..c // ccc public String placedShapeInfo(); // Print a verbose string representation of the space. Start with // the string SPACE: then follow with the fitString() of the space // and finally the placedShapeInfo() string. // // Example: // // SPACE: // height: 3 width: 8 // aabbbbfe // aacdddf| // cccdd||| // // 6 shapes placed // Shape at (0,0) // SHAPE a // height: 2 width: 2 rotation: CW90 // aa // aa // // Shape at (0,2) // SHAPE b // height: 1 width: 4 rotation: CW180 // bbbb // ... public String toString(); } 

Rotation Enumeration

Rotation is a simple enumeration used to track the four valid clock-wise rotations: 0, 90, 180, and 270 degrees. It has four elements and a single method.

public enum Rotation{ CW0, CW90, CW180, CW270; // Calling rot.next() will return the next enumeration element // representing the next 90 degree clock-wise rotation after rot. public Rotation next(); } 

Exception Classes

Certain methods of Space must throw exceptions. In order to identify that you are identifying these situations and responding appropriately, throw the provided FitItException which can be simply initialized with a string message. Ensure that you are using messages that are informative and correspond to the situation that has arisen.

// Catch-all exception for Shapes and Spaces so that explicit // exception throwing can be checked public class FitItException extends RuntimeException{ public FitItException(String msg){ super(msg); } } 

Layout String and File Formats

Layout String Formats

The makeShape(String layout, char displayChar) method of FitIt (described in the FitIt section) takes a layout string as an argument and should produce a shape. This layout string (and the display character argument) will be passed into a constructor for a class you devise. Layout strings are identical the examples used elsewhere in the specification. Examples are below, each separated by a blank line.

..e eee .ss ss. b b b b aaaa a..a aaaa .....z ....z. ...z.. zz..z. 

All of these are valid layout strings which should produce valid shapes on a call to makeShape(layout,dc).

Shape layout strings have the following format.

Newlines ( ) show breaks in the rows of the Shape.

The period (.) is used to represent empty blocks.

Any other character is a filled block even if it does not match the given displayChar. By convention, no tests or input files will do this but it may be useful for your own testing.

All lines may be assumed to have the same number of characters on them. Your code may handle strings that violate this assumption however you wish (produce a shape, throw an exception, otherwise misbehave). An Example of a "ragged" format string that is illegal is

ppp p pp 

because it does not contain the period (.) to denote blank spaces at the ends of lines. A proper layout would be

ppp p.. pp. 

Layout strings for shapes must have at least one filled block in each of 0th row, 0th column, last row, and last column.

Shapes will be restricted to contain a non-empty border: the 0th row, 0th column, last row, and last column must all contain at least one filled block. This prevents problems when dealing with rotation andplacement in spaces. The following shapes are illegal due to having at least part of their border empty. This means the following layout strings are all illegal.

..b. bbb. ... .x. ... ..r .rr ..... .y... ..y.. ...y. 

If passed to makeShape(layout,dc) as the layout, a FitItException should be raised for such strings.

Space Layout Strings

The method makeSpace(String layout) of FitIt takes a layout string and returns a Space. The string will be formatted similarly to layouts for shapes except that filled blocks are always shown with the pipe/vertical bar (|) character. Examples are as follows (separated by blank lines).

.. .. .| ...... .....| ...||| |....... ..|||..| ..|.|... ........ 

Space layout strings have the following format.

Newlines ( ) show breaks in the rows of the Shape.

The period (.) is used to represent empty blocks.

The pipe (|) is used to represent permanently filled blocks.

All lines may be assumed to have the same number of characters on them.

Problem Input Formats

FitIt.main(String args[]) takes a command line argument which is an input file describing a problem to solve. The input files have the following format.

Space Records

Any line starting with SPACE denotes the beginning of a space. Subsequent lines constitute the layout string for a space ending with a blank line. Example:

SPACE ........ .......| .....||| 

The space layout string should be created by appending subsequent lines together and then passed to the makeSpace(layout) method. The space is used in a call to searchForFit(space,shapeList). If more than one SPACE record appears in an input file, your code may behave in any way (replace previous space, throw an exception, fail utterly).

Shape Records

Any line starting with SHAPE denotes the beginning of a shape record. On the line with SHAPE will be a single character which is the display character for the shape. Subsequent lines constitute the layout string for the shape ending with a blank line. Examples:

SHAPE b bbbb SHAPE c c. c. cc 

The lines after SHAPE should be appended to create a layout string which, along with the display character, is passed to a the makeShape(layout,displayChar) method. The shapes should be added into a list which is used in a call to searchForFit(space,shapeList).

Other Lines

Any line that that is not part of a Shape or Space record and does not start such a record by beginning with SPACE or SHAPE should be ignored. Lots of comments and solutions can appear in the files. The following lines will be ignored.

SOLUTION aadddffe aaddccc| bbbbc||| A = 0 0 CW0 B = 2 0 CW0 C = 1 4 CW90 D = 0 2 CW180 E = 0 7 CW0 F = 0 5 CW90 Some random text here which will be ignored 

Here is a complete example of an input file which is provided with the code as problem5.txt

SPACE .. .. .| SHAPE a aa SHAPE b bbb Any text that doesn't start with SPACE or SHAPE should be ignored. That includes these lines and the SOLUTION below which is for documentation purposes only. SOLUTION ba ba b| 

Sample Runs of FitIt.main()

The exact output FitIt.main() will not be closely checked but it gives a good sense of how the program behaves in terms of listing solutions or not. The input files are shown first, then the program is invoked on the problem file. In the instructor solution, a second argument is checked for the string debug in which case more output is produced. This is a pattern you should consider adopting in your own implementation.

lila [p6]% java FitIt usage: java FitIt input.txt lila [p6]% cat samples/sample-problem.txt SPACE .. .. .| SHAPE a aa SHAPE b bbb Any text that doesn't start with SPACE or SHAPE should be ignored. That includes these lines and the SOLUTION below which is for documentation purposes only. SOLUTION ba ba b| lila [p6]% java FitIt samples/sample-problem.txt Finished with input SPACE: height: 3 width: 2 .. .. .| 0 shapes placed 2 shapes read SHAPE a height: 1; width: 2; rotation: CW0 aa SHAPE b height: 1; width: 3; rotation: CW0 bbb FOUND FIT SPACE: height: 3 width: 2 ba ba b| 2 shapes placed Shape at (0,1) SHAPE a height: 2; width: 1; rotation: CW90 a a Shape at (0,0) SHAPE b height: 3; width: 1; rotation: CW90 b b b lila [p6]% cat samples/impossible-problem.txt This problem has no solution SPACE .. .. .| SHAPE a aaa SHAPE b bbb lila [p6]% java FitIt samples/impossible-problem.txt Finished with input SPACE: height: 3 width: 2 .. .. .| 0 shapes placed 2 shapes read SHAPE a height: 1; width: 3; rotation: CW0 aaa SHAPE b height: 1; width: 3; rotation: CW0 bbb NO FIT FOUND lila [p6]% java FitIt samples/sample-problem.txt debug Trying a rot:CW0 at (0,0)... Fits aa .. .| Trying b rot:CW0 at (0,0)... No fit Trying b rot:CW90 at (0,0)... No fit Trying b rot:CW180 at (0,0)... No fit Trying b rot:CW270 at (0,0)... No fit Trying b rot:CW0 at (0,1)... No fit Trying b rot:CW90 at (0,1)... No fit Trying b rot:CW180 at (0,1)... No fit Trying b rot:CW270 at (0,1)... No fit Trying b rot:CW0 at (1,0)... No fit Trying b rot:CW90 at (1,0)... No fit Trying b rot:CW180 at (1,0)... No fit Trying b rot:CW270 at (1,0)... No fit Trying b rot:CW0 at (1,1)... No fit Trying b rot:CW90 at (1,1)... No fit Trying b rot:CW180 at (1,1)... No fit Trying b rot:CW270 at (1,1)... No fit Trying b rot:CW0 at (2,0)... No fit Trying b rot:CW90 at (2,0)... No fit Trying b rot:CW180 at (2,0)... No fit Trying b rot:CW270 at (2,0)... No fit Trying b rot:CW0 at (2,1)... No fit Trying b rot:CW90 at (2,1)... No fit Trying b rot:CW180 at (2,1)... No fit Trying b rot:CW270 at (2,1)... No fit Giving up on shape b in aa .. .| Removing a rot:CW0 from (0,0) Trying a rot:CW90 at (0,0)... Fits a. a. .| Trying b rot:CW0 at (0,0)... No fit Trying b rot:CW90 at (0,0)... No fit Trying b rot:CW180 at (0,0)... No fit Trying b rot:CW270 at (0,0)... No fit Trying b rot:CW0 at (0,1)... No fit Trying b rot:CW90 at (0,1)... No fit Trying b rot:CW180 at (0,1)... No fit Trying b rot:CW270 at (0,1)... No fit Trying b rot:CW0 at (1,0)... No fit Trying b rot:CW90 at (1,0)... No fit Trying b rot:CW180 at (1,0)... No fit Trying b rot:CW270 at (1,0)... No fit Trying b rot:CW0 at (1,1)... No fit Trying b rot:CW90 at (1,1)... No fit Trying b rot:CW180 at (1,1)... No fit Trying b rot:CW270 at (1,1)... No fit Trying b rot:CW0 at (2,0)... No fit Trying b rot:CW90 at (2,0)... No fit Trying b rot:CW180 at (2,0)... No fit Trying b rot:CW270 at (2,0)... No fit Trying b rot:CW0 at (2,1)... No fit Trying b rot:CW90 at (2,1)... No fit Trying b rot:CW180 at (2,1)... No fit Trying b rot:CW270 at (2,1)... No fit Giving up on shape b in a. a. .| Removing a rot:CW90 from (0,0) Trying a rot:CW180 at (0,0)... Fits aa .. .| Trying b rot:CW0 at (0,0)... No fit Trying b rot:CW90 at (0,0)... No fit Trying b rot:CW180 at (0,0)... No fit Trying b rot:CW270 at (0,0)... No fit Trying b rot:CW0 at (0,1)... No fit Trying b rot:CW90 at (0,1)... No fit Trying b rot:CW180 at (0,1)... No fit Trying b rot:CW270 at (0,1)... No fit Trying b rot:CW0 at (1,0)... No fit Trying b rot:CW90 at (1,0)... No fit Trying b rot:CW180 at (1,0)... No fit Trying b rot:CW270 at (1,0)... No fit Trying b rot:CW0 at (1,1)... No fit Trying b rot:CW90 at (1,1)... No fit Trying b rot:CW180 at (1,1)... No fit Trying b rot:CW270 at (1,1)... No fit Trying b rot:CW0 at (2,0)... No fit Trying b rot:CW90 at (2,0)... No fit Trying b rot:CW180 at (2,0)... No fit Trying b rot:CW270 at (2,0)... No fit Trying b rot:CW0 at (2,1)... No fit Trying b rot:CW90 at (2,1)... No fit Trying b rot:CW180 at (2,1)... No fit Trying b rot:CW270 at (2,1)... No fit Giving up on shape b in aa .. .| Removing a rot:CW180 from (0,0) Trying a rot:CW270 at (0,0)... Fits a. a. .| Trying b rot:CW0 at (0,0)... No fit Trying b rot:CW90 at (0,0)... No fit Trying b rot:CW180 at (0,0)... No fit Trying b rot:CW270 at (0,0)... No fit Trying b rot:CW0 at (0,1)... No fit Trying b rot:CW90 at (0,1)... No fit Trying b rot:CW180 at (0,1)... No fit Trying b rot:CW270 at (0,1)... No fit Trying b rot:CW0 at (1,0)... No fit Trying b rot:CW90 at (1,0)... No fit Trying b rot:CW180 at (1,0)... No fit Trying b rot:CW270 at (1,0)... No fit Trying b rot:CW0 at (1,1)... No fit Trying b rot:CW90 at (1,1)... No fit Trying b rot:CW180 at (1,1)... No fit Trying b rot:CW270 at (1,1)... No fit Trying b rot:CW0 at (2,0)... No fit Trying b rot:CW90 at (2,0)... No fit Trying b rot:CW180 at (2,0)... No fit Trying b rot:CW270 at (2,0)... No fit Trying b rot:CW0 at (2,1)... No fit Trying b rot:CW90 at (2,1)... No fit Trying b rot:CW180 at (2,1)... No fit Trying b rot:CW270 at (2,1)... No fit Giving up on shape b in a. a. .| Removing a rot:CW270 from (0,0) Trying a rot:CW0 at (0,1)... No fit Trying a rot:CW90 at (0,1)... Fits .a .a .| Trying b rot:CW0 at (0,0)... No fit Trying b rot:CW90 at (0,0)... Fits ba ba b| All shapes placed lila [p6]% java FitIt samples/impossible-problem.txt debug Trying a rot:CW0 at (0,0)... No fit Trying a rot:CW90 at (0,0)... Fits a. a. a| Trying b rot:CW0 at (0,0)... No fit Trying b rot:CW90 at (0,0)... No fit Trying b rot:CW180 at (0,0)... No fit Trying b rot:CW270 at (0,0)... No fit Trying b rot:CW0 at (0,1)... No fit Trying b rot:CW90 at (0,1)... No fit Trying b rot:CW180 at (0,1)... No fit Trying b rot:CW270 at (0,1)... No fit Trying b rot:CW0 at (1,0)... No fit Trying b rot:CW90 at (1,0)... No fit Trying b rot:CW180 at (1,0)... No fit Trying b rot:CW270 at (1,0)... No fit Trying b rot:CW0 at (1,1)... No fit Trying b rot:CW90 at (1,1)... No fit Trying b rot:CW180 at (1,1)... No fit Trying b rot:CW270 at (1,1)... No fit Trying b rot:CW0 at (2,0)... No fit Trying b rot:CW90 at (2,0)... No fit Trying b rot:CW180 at (2,0)... No fit Trying b rot:CW270 at (2,0)... No fit Trying b rot:CW0 at (2,1)... No fit Trying b rot:CW90 at (2,1)... No fit Trying b rot:CW180 at (2,1)... No fit Trying b rot:CW270 at (2,1)... No fit Giving up on shape b in a. a. a| Removing a rot:CW90 from (0,0) Trying a rot:CW180 at (0,0)... No fit Trying a rot:CW270 at (0,0)... Fits a. a. a| Trying b rot:CW0 at (0,0)... No fit Trying b rot:CW90 at (0,0)... No fit Trying b rot:CW180 at (0,0)... No fit Trying b rot:CW270 at (0,0)... No fit Trying b rot:CW0 at (0,1)... No fit Trying b rot:CW90 at (0,1)... No fit Trying b rot:CW180 at (0,1)... No fit Trying b rot:CW270 at (0,1)... No fit Trying b rot:CW0 at (1,0)... No fit Trying b rot:CW90 at (1,0)... No fit Trying b rot:CW180 at (1,0)... No fit Trying b rot:CW270 at (1,0)... No fit Trying b rot:CW0 at (1,1)... No fit Trying b rot:CW90 at (1,1)... No fit Trying b rot:CW180 at (1,1)... No fit Trying b rot:CW270 at (1,1)... No fit Trying b rot:CW0 at (2,0)... No fit Trying b rot:CW90 at (2,0)... No fit Trying b rot:CW180 at (2,0)... No fit Trying b rot:CW270 at (2,0)... No fit Trying b rot:CW0 at (2,1)... No fit Trying b rot:CW90 at (2,1)... No fit Trying b rot:CW180 at (2,1)... No fit Trying b rot:CW270 at (2,1)... No fit Giving up on shape b in a. a. a| Removing a rot:CW270 from (0,0) Trying a rot:CW0 at (0,1)... No fit Trying a rot:CW90 at (0,1)... No fit Trying a rot:CW180 at (0,1)... No fit Trying a rot:CW270 at (0,1)... No fit Trying a rot:CW0 at (1,0)... No fit Trying a rot:CW90 at (1,0)... No fit Trying a rot:CW180 at (1,0)... No fit Trying a rot:CW270 at (1,0)... No fit Trying a rot:CW0 at (1,1)... No fit Trying a rot:CW90 at (1,1)... No fit Trying a rot:CW180 at (1,1)... No fit Trying a rot:CW270 at (1,1)... No fit Trying a rot:CW0 at (2,0)... No fit Trying a rot:CW90 at (2,0)... No fit Trying a rot:CW180 at (2,0)... No fit Trying a rot:CW270 at (2,0)... No fit Trying a rot:CW0 at (2,1)... No fit Trying a rot:CW90 at (2,1)... No fit Trying a rot:CW180 at (2,1)... No fit Trying a rot:CW270 at (2,1)... No fit Giving up on shape a in .. .. .| 

demo$ java FitIt usage: java FitIt input.txt demo$ cat samples/sample-problem.txt SPACE .. .. .| SHAPE a aa SHAPE b bbb Any text that doesn't start with SPACE or SHAPE should be ignored. That includes these lines and the SOLUTION below which is for documentation purposes only. SOLUTION ba ba b| demo$ java FitIt samples/sample-problem.txt Finished with input SPACE: height: 3 width: 2 .. .. .| 0 shapes placed 2 shapes read SHAPE a height: 1; width: 2; rotation: CW0 aa SHAPE b height: 1; width: 3; rotation: CW0 bbb FOUND FIT SPACE: height: 3 width: 2 ba ba b| 2 shapes placed Shape at (0,1) SHAPE a height: 2; width: 1; rotation: CW90 a a Shape at (0,0) SHAPE b height: 3; width: 1; rotation: CW90 b b b demo$ cat samples/impossible-problem.txt This problem has no solution SPACE .. .. .| SHAPE a aaa SHAPE b bbb demo$ java FitIt samples/impossible-problem.txt Finished with input SPACE: height: 3 width: 2 .. .. .| 0 shapes placed 2 shapes read SHAPE a height: 1; width: 3; rotation: CW0 aaa SHAPE b height: 1; width: 3; rotation: CW0 bbb NO FIT FOUND demo$ java FitIt samples/sample-problem.txt debug Trying a rot:CW0 at (0,0)... Fits aa .. .| Trying b rot:CW0 at (0,0)... No fit Trying b rot:CW90 at (0,0)... No fit Trying b rot:CW180 at (0,0)... No fit Trying b rot:CW270 at (0,0)... No fit Trying b rot:CW0 at (0,1)... No fit Trying b rot:CW90 at (0,1)... No fit Trying b rot:CW180 at (0,1)... No fit Trying b rot:CW270 at (0,1)... No fit Trying b rot:CW0 at (1,0)... No fit Trying b rot:CW90 at (1,0)... No fit Trying b rot:CW180 at (1,0)... No fit Trying b rot:CW270 at (1,0)... No fit Trying b rot:CW0 at (1,1)... No fit Trying b rot:CW90 at (1,1)... No fit Trying b rot:CW180 at (1,1)... No fit Trying b rot:CW270 at (1,1)... No fit Trying b rot:CW0 at (2,0)... No fit Trying b rot:CW90 at (2,0)... No fit Trying b rot:CW180 at (2,0)... No fit Trying b rot:CW270 at (2,0)... No fit Trying b rot:CW0 at (2,1)... No fit Trying b rot:CW90 at (2,1)... No fit Trying b rot:CW180 at (2,1)... No fit Trying b rot:CW270 at (2,1)... No fit Giving up on shape b in aa .. .| Removing a rot:CW0 from (0,0) Trying a rot:CW90 at (0,0)... Fits a. a. .| Trying b rot:CW0 at (0,0)... No fit Trying b rot:CW90 at (0,0)... No fit Trying b rot:CW180 at (0,0)... No fit Trying b rot:CW270 at (0,0)... No fit Trying b rot:CW0 at (0,1)... No fit Trying b rot:CW90 at (0,1)... No fit Trying b rot:CW180 at (0,1)... No fit Trying b rot:CW270 at (0,1)... No fit Trying b rot:CW0 at (1,0)... No fit Trying b rot:CW90 at (1,0)... No fit Trying b rot:CW180 at (1,0)... No fit Trying b rot:CW270 at (1,0)... No fit Trying b rot:CW0 at (1,1)... No fit Trying b rot:CW90 at (1,1)... No fit Trying b rot:CW180 at (1,1)... No fit Trying b rot:CW270 at (1,1)... No fit Trying b rot:CW0 at (2,0)... No fit Trying b rot:CW90 at (2,0)... No fit Trying b rot:CW180 at (2,0)... No fit Trying b rot:CW270 at (2,0)... No fit Trying b rot:CW0 at (2,1)... No fit Trying b rot:CW90 at (2,1)... No fit Trying b rot:CW180 at (2,1)... No fit Trying b rot:CW270 at (2,1)... No fit Giving up on shape b in a. a. .| Removing a rot:CW90 from (0,0) Trying a rot:CW180 at (0,0)... Fits aa .. .| Trying b rot:CW0 at (0,0)... No fit Trying b rot:CW90 at (0,0)... No fit Trying b rot:CW180 at (0,0)... No fit Trying b rot:CW270 at (0,0)... No fit Trying b rot:CW0 at (0,1)... No fit Trying b rot:CW90 at (0,1)... No fit Trying b rot:CW180 at (0,1)... No fit Trying b rot:CW270 at (0,1)... No fit Trying b rot:CW0 at (1,0)... No fit Trying b rot:CW90 at (1,0)... No fit Trying b rot:CW180 at (1,0)... No fit Trying b rot:CW270 at (1,0)... No fit Trying b rot:CW0 at (1,1)... No fit Trying b rot:CW90 at (1,1)... No fit Trying b rot:CW180 at (1,1)... No fit Trying b rot:CW270 at (1,1)... No fit Trying b rot:CW0 at (2,0)... No fit Trying b rot:CW90 at (2,0)... No fit Trying b rot:CW180 at (2,0)... No fit Trying b rot:CW270 at (2,0)... No fit Trying b rot:CW0 at (2,1)... No fit Trying b rot:CW90 at (2,1)... No fit Trying b rot:CW180 at (2,1)... No fit Trying b rot:CW270 at (2,1)... No fit Giving up on shape b in aa .. .| Removing a rot:CW180 from (0,0) Trying a rot:CW270 at (0,0)... Fits a. a. .| Trying b rot:CW0 at (0,0)... No fit Trying b rot:CW90 at (0,0)... No fit Trying b rot:CW180 at (0,0)... No fit Trying b rot:CW270 at (0,0)... No fit Trying b rot:CW0 at (0,1)... No fit Trying b rot:CW90 at (0,1)... No fit Trying b rot:CW180 at (0,1)... No fit Trying b rot:CW270 at (0,1)... No fit Trying b rot:CW0 at (1,0)... No fit Trying b rot:CW90 at (1,0)... No fit Trying b rot:CW180 at (1,0)... No fit Trying b rot:CW270 at (1,0)... No fit Trying b rot:CW0 at (1,1)... No fit Trying b rot:CW90 at (1,1)... No fit Trying b rot:CW180 at (1,1)... No fit Trying b rot:CW270 at (1,1)... No fit Trying b rot:CW0 at (2,0)... No fit Trying b rot:CW90 at (2,0)... No fit Trying b rot:CW180 at (2,0)... No fit Trying b rot:CW270 at (2,0)... No fit Trying b rot:CW0 at (2,1)... No fit Trying b rot:CW90 at (2,1)... No fit Trying b rot:CW180 at (2,1)... No fit Trying b rot:CW270 at (2,1)... No fit Giving up on shape b in a. a. .| Removing a rot:CW270 from (0,0) Trying a rot:CW0 at (0,1)... No fit Trying a rot:CW90 at (0,1)... Fits .a .a .| Trying b rot:CW0 at (0,0)... No fit Trying b rot:CW90 at (0,0)... Fits ba ba b| All shapes placed demo$ java FitIt samples/impossible-problem.txt debug Trying a rot:CW0 at (0,0)... No fit Trying a rot:CW90 at (0,0)... Fits a. a. a| Trying b rot:CW0 at (0,0)... No fit Trying b rot:CW90 at (0,0)... No fit Trying b rot:CW180 at (0,0)... No fit Trying b rot:CW270 at (0,0)... No fit Trying b rot:CW0 at (0,1)... No fit Trying b rot:CW90 at (0,1)... No fit Trying b rot:CW180 at (0,1)... No fit Trying b rot:CW270 at (0,1)... No fit Trying b rot:CW0 at (1,0)... No fit Trying b rot:CW90 at (1,0)... No fit Trying b rot:CW180 at (1,0)... No fit Trying b rot:CW270 at (1,0)... No fit Trying b rot:CW0 at (1,1)... No fit Trying b rot:CW90 at (1,1)... No fit Trying b rot:CW180 at (1,1)... No fit Trying b rot:CW270 at (1,1)... No fit Trying b rot:CW0 at (2,0)... No fit Trying b rot:CW90 at (2,0)... No fit Trying b rot:CW180 at (2,0)... No fit Trying b rot:CW270 at (2,0)... No fit Trying b rot:CW0 at (2,1)... No fit Trying b rot:CW90 at (2,1)... No fit Trying b rot:CW180 at (2,1)... No fit Trying b rot:CW270 at (2,1)... No fit Giving up on shape b in a. a. a| Removing a rot:CW90 from (0,0) Trying a rot:CW180 at (0,0)... No fit Trying a rot:CW270 at (0,0)... Fits a. a. a| Trying b rot:CW0 at (0,0)... No fit Trying b rot:CW90 at (0,0)... No fit Trying b rot:CW180 at (0,0)... No fit Trying b rot:CW270 at (0,0)... No fit Trying b rot:CW0 at (0,1)... No fit Trying b rot:CW90 at (0,1)... No fit Trying b rot:CW180 at (0,1)... No fit Trying b rot:CW270 at (0,1)... No fit Trying b rot:CW0 at (1,0)... No fit Trying b rot:CW90 at (1,0)... No fit Trying b rot:CW180 at (1,0)... No fit Trying b rot:CW270 at (1,0)... No fit Trying b rot:CW0 at (1,1)... No fit Trying b rot:CW90 at (1,1)... No fit Trying b rot:CW180 at (1,1)... No fit Trying b rot:CW270 at (1,1)... No fit Trying b rot:CW0 at (2,0)... No fit Trying b rot:CW90 at (2,0)... No fit Trying b rot:CW180 at (2,0)... No fit Trying b rot:CW270 at (2,0)... No fit Trying b rot:CW0 at (2,1)... No fit Trying b rot:CW90 at (2,1)... No fit Trying b rot:CW180 at (2,1)... No fit Trying b rot:CW270 at (2,1)... No fit Giving up on shape b in a. a. a| Removing a rot:CW270 from (0,0) Trying a rot:CW0 at (0,1)... No fit Trying a rot:CW90 at (0,1)... No fit Trying a rot:CW180 at (0,1)... No fit Trying a rot:CW270 at (0,1)... No fit Trying a rot:CW0 at (1,0)... No fit Trying a rot:CW90 at (1,0)... No fit Trying a rot:CW180 at (1,0)... No fit Trying a rot:CW270 at (1,0)... No fit Trying a rot:CW0 at (1,1)... No fit Trying a rot:CW90 at (1,1)... No fit Trying a rot:CW180 at (1,1)... No fit Trying a rot:CW270 at (1,1)... No fit Trying a rot:CW0 at (2,0)... No fit Trying a rot:CW90 at (2,0)... No fit Trying a rot:CW180 at (2,0)... No fit Trying a rot:CW270 at (2,0)... No fit Trying a rot:CW0 at (2,1)... No fit Trying a rot:CW90 at (2,1)... No fit Trying a rot:CW180 at (2,1)... No fit Trying a rot:CW270 at (2,1)... No fit Giving up on shape a in .. .. .|