Homework 3

Please email your solution to the TA, at league@cs.yale.edu, with cs429hw3 in the subject.

Problem 1: Tiling with Trominoes [35 pts]

a board, with n=2 (2n=4)	a tromino	a tiling

It will be convenient to treat the origin (0,0) as the upper left corner of the board. Just for kicks, here is a larger tiling (with n=3):

1.1  The Proof [15 pts]

Implementation

Orientation: We need a representation of the four possible orientations of a tromino. Notice how the tromino's shape resembles an "arrow." We will describe a tromino's orientation by using the direction in which the arrow points. The four possible directions are specified by the following datatype declaration:

    data Orientation = NW | NE | SW | SE 
      deriving Show

NW northwest	NE northeast	SW southwest	SE southeast

Location: We also need to specify a tromino's location on the board. We will do so using the coordinate of the "arrow point square," expressed as a pair of points (x,y) with type (int, int). The board's upper-left square has a coordinate value of (0,0).

For computing the board size, 2ⁿ, I suggest you define a function pow2 :: Int -> Int. The infix power operator in Haskell is (**), but it returns a Float, so you will need to convert it back to an Int.

Tromino representation: Thus, a tromino can be represented by its orientation and a pair of points indicating the coordinate of its "arrow point square." Such a representation can be expressed with the following declaration:

    type Tromino = (Int, Int, Orientation)

    [(0,0,NW),(3,0,NE),(3,3,SE),(0,3,SW),(1,1,NW)]

1.2  Translate [5 pts]

The first helper function to write is the translate function, which takes an (x,y) offset and a tromino list. The function shifts each of the given trominoes by the given offset, returning the resulting list of trominoes.

    translate :: (Int,Int) -> [Tromino] -> [Tromino]

1.3  Flip [10 pts]

Next we need to be able to flip the board about either axis. We will call these functions xflip and yflip. They will take the length of one side of the board as its first argument, then the list of trominoes. Each function returns the reflected tromino list.

    xflip :: Int -> [Tromino] -> [Tromino]
    yflip :: Int -> [Tromino] -> [Tromino]

t0	xflip 4 t0	yflip 4 t0

1.4  Tile [5 pts]

    tile :: Int -> [Tromino]

Problem 2: Rendering Trominoes [15 pts]

    import qualified SOEGraphics as G

The top-level function, render, will take the title of the window, a natural number n, and a list of trominoes. It will open a window and render the trominoes in different colors.

    render :: String -> Int -> [Trom] -> IO ()

    -- pixels per square
    pps = 30 :: Int

    render title n ts = G.runGraphics $
       do w <- G.openWindow title (dim,dim)
          ...other rendering operations...
       where dim = pow2 n * pps

    renderTiling :: Int -> IO ()
    renderTiling n = render ("tile "++show n) n (tile n)

You will probably find it useful to define an infinite stream of colors. The graphics library defines G.colorList :: [(Color,RGB)] where Color is a data type with constructors named Red, Blue, and so on. RGB is a triple of 8-bit words. The first color in the list is Black. Thus, the following code produces an infinite stream of all colors except for black.

    colors = tail (map fst G.colorList) ++ colors

I suggest rendering each tromino as a polygon. The library defines G.polygon :: [Point] -> Graphic for creating polygons from a list of points. Thus, the kernel of your program might be a function which generates polygon vertices for a given tromino:

    trominoPolygon :: Tromino -> [Point]

Problem 3: Game Show [50 pts]

Congratulations. You have just reached the final round of the game show "The Winner Takes It All". All you have to do is to decide is if the order of a line up of items that is presented to you on a conveyer belt follows certain rules. The show master has already acquainted you with them ahead of time (they may vary from game to game) and you are very lucky today! There are only two rules he asked you to memorize.

• Either you see a vehicle (V), followed by a kitchen appliance (K) followed by an entertainment item (E).
• Or you see vehicle (V) followed by a travel certificate (T).

Test Round 1:

 V K V E T

Test Round 2:

 V V T

Test Round 3:

The conveyer belt starts rolling and you see

 V K V E K E

Back to the homework! Please solve this problem for the general case by writing a Haskell program which decides for you if to say yes or no.

      type Rule = [Char]
      play :: [Rule] -> String -> Bool

Hint: Try to adopt and modify the code for matching regular expressions in class. Do not write more than 40 lines of code! If you do, something is likely to be wrong, or you haven't found an elegant solution.

Problem 4: Adding Negation to Regular Expressions [extra credit 20 pts]

With this problem we return to the world of algorithms that match regular expressions. In class we have discussed the standard set of operators of regular expressions, and we have discussed an algorithm that decides if a string is matched by a regular expression our not. You are asked to extend the regular expression language by a new constructors that can express negation.

  acc  "00" (Not (Star (Char "1"))) init 

  data Reg 
    = Zero
    | One
    | Char Char
    | Plus Reg Reg
    | Times Reg Reg
    | Star Reg
    | Not Reg
  deriving Show

  L(Not R)  = {s | s is not an element of L(R)}