Java Task:

Please help me with writing an interaface called "Shape" in this program.

This program is about 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 shipsthat travel around the world devolves to the same basic problem of packing a set of objects into a fixed volume.

Here is an overview of two of the interfaces in this program. Please help me with one of these "Shape.java".

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 character associated 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

-------Here is the task-----Please solve from below

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 Shape and 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(); }

-----Tester cases-----

Here is the link to tester cases for Shape.java: https://paste.ee/p/zDsgd

Here is the link to the summary of this program: https://paste.ee/p/dmDDy