Introduction to (Web) Programming

Spring Break Exercises: "gridstrings"

Due date: Monday, April 1 at 1:30pm

Instructions

shortcut to exercises


This assignment will not be graded!

Your goal is to to do as many of the exercises (roughly in order, though you need not follow the order strictly) as you can and email me for assistance at any point if you get stuck. After break I will schedule brief one on one meetings with you where we will go over what you have completed and attempted and I will offer feedback. This assignment is required and must be submitted but it will not be graded. It is for practice and to help motivate topics that we will cover after break.


Gridstrings

Informally, we can think of a "gridstring" as text that is meant to be displayed as a sequence of lines, each of the same length, rather than on one potentially long line. If we have a string like:

'ABCDEFGHIJKLMNOPQRST'

and we print it to the console (or display it with an alert box), all 20 characters appear in one row:

> let s = 'ABCDEFGHIJKLMNOPQRST';
> console.log(s);
ABCDEFGHIJKLMNOPQRST

Sometimes we might like to think of the same sequence of characters as being a group of strings of the same length, so for instance, four strings each of length five, which might be displayed as:

ABCDE
FGHIJ
KLMNO
PQRST

We can think of that collection of characters as a two-dimensional grid consisting of four rows each consisting of five characters. Later in the semester, we will see a serious motivation for doing this and see how JavaScript (and most programming languages) offer a convenient way to represent such two-dimensional collections of data. In this series of exercises, we show how we can represent the idea using tools we already have developed for working with our usual JavaScript strings.

The key idea for representing grid strings is to take advantage of the idea that individual characters correspond to (and are represented "under the hood") as numeric codes and so in the first position of our gridstrings, we will store the character corresponding the width of the given grid string.

Suppose we want to represent this grid of characters:

ABC
DEF

(i.e., two rows of three characters each with the characters being the first six uppercase letters). We can store that as a JavaScript string of length seven: the first character represents the width (three) and the next six characters are just 'ABCDEF'. In code, we can do that like:

> let gridString = String.fromCharCode(3);
> gridString = gridString + 'ABCDEF';

We can then access that like any other JavaScript string:

> gridString.length
7
> gridString.charAt(1)
"A"

though we should realize if we display the entire string (or the character at position 0), it might look a little strange:

> gridString
"\u0003ABCDEF"
> gridString.charAt(0)
"\u0003"
> gridString.charCodeAt(0)
3
> console.log(gridString);
´┐ŻABCDEF

The \u0003 means "the character corresponding to Unicode value 3". Small values (those less than 32) are generally what we call "nonprintable" characters meaning they do not correspond to standard keyboard character (nor standard alphabetic characters). Some of them do have standard meanings (most notably value 10 which is usually represented as '\n' and means "newline").

But we can write a few helpful functions to make it easier to build and display gridstrings such as:

// Returns a gridstring of width w corresponding to regular string s.
function makeGrid(s, w) {
    let filler = repeat(PAD_CHAR, s.length % w);
    return String.fromCharCode(w) + s + filler;
}

// Returns the width of gridstring gs.
function width(gs) {
    return gs.charCodeAt(0);
}

// Returns the overall character length of gridstring gs.
function size(gs) {
    return gs.length - 1;
}

// Returns the number of rows in gridstring gs.
function height(gs) {
    let h = 0;
    if (width(gs) > 0) {
        h = size(gs) / width(gs);
    }
    return h;
}

// Returns the sequence of characters in gridstring gs from left to
// right, top to bottom as a single string.
function raw(gs) {
    return slice(gs, 1, gs.length);
}

// Returns a columns-by-rows sized gridstring consisting entirely of
// fillChar. Assumes columns and rows are nonnegative integers and that
// fillChar is a character (string of length 1).
function fillGrid(columns, rows, fillChar) {
    return makeGrid(repeat(fillChar, rows * columns), columns);
}

// Displays gridstring in the console.
function showGrid(gs) { ... }

These functions (and more) are included in the starter file for this assignment. They can be used like this:

> let myGrid = makeGrid('Rectangles have more fun!', 4);
> width(myGrid)
4
> size(myGrid)
25
> height(myGrid)
7

We do not require that the size of a gridstring be a multiple of its width. We can think of the grid as filling its last row from left to right until there are no more characters left to display as in:

Rect
angl
es h
ave 
more
 fun
!___

The included showGrid and toString functions combine to let us display gridstrings to the console (to get the above output, for instance).


From rows and columns to string indexes

Lets consider rows and columns of grid counting from 0 starting at top left of the grid and working to the right and down:

              column #s
              0 1 2 3 4
            -----------
          0 | A B C D E
          1 | F G H I J
 row #s   2 | K L M N O
          3 | P Q R S T

It has four rows of five columns each, with row numbers runing from 0 through 3 and column numbers from 0 through 4. What character is at row 0, column 0? 'A'. And at row 1, columns 2? 'H'. And at row 3, column 1? 'Q'. If we think of the just the simple string 'ABCDEFGHIJKLMNOPQRST' we can associate each letter in that string to its position: 'A' is at position 0, 'B' is at position 1, and so on, up until 'T' being at position 19. So we can establish a pattern:

A: index  0, row 0, column 0
B: index  1, row 0, column 1
H: index  7, row 1, column 2
Q: index 16, row 3, column 1
T: index 19, row 3, column 4

From that we can observe that the index is five times the row number plus the column number, or as a JavaScript expression:

5*row + column

This works in general whenever we want to translate between one long line of something and a grid of a specified width:

width*row + column

In fact, we can use that idea to write a function get that returns the character in a gridstring at the specified row and column:

// Returns the character in gridstring gs at the specified column and
// row. Column and row are assumed to be integers, but if they are out
// of bounds, the function returns null.
function get(gs, column, row) {
    let c = null;
    if (0 <= column && column < width(gs) &&
        0 <= row && row < height(gs)) {
        let i = row * width(gs) + column + 1;   // why do we have to add 1?
        c = gs.charAt(i);
    }
    return c;
}

> let box = makeGrid('SQUAREPEG', 3);
> showGrid(box)
SQU
ARE
PEG
> get(box, 1, 2)
"E"

The same ideas, combined with versions of functions we have encountered earlier in the semester (see repeat, pad, and slice at the bottom of the starter code) will let us write many functions to manipulate gridstrings.


The exercises themselves

For all the examples provided in the description of each exercise, you can assume that g has been defined as in:

> let g = makeGrid('ABCDEFGHIJKL', 4);
> showGrid(g)
  ABCD
  EFGH
  IJKL

(It has been defined that way for you in the starter file, too.)

  1. Complete reflow(gs, newWidth) so that it returns a new gridstring that has the same contents of gridstring gs but is has the specified newWidth. Can be done in one line. Use raw and makeGrid. Example:

    > showGrid(reflow(g, 3))
      ABC
      DEF
      GHI
      JKL
    
    > showGrid(reflow(g, 5))
      ABCDE
      FGHIJ
      KL___
  2. Complete getRow(gs, row) so that it returns the string corresponding to the specified row number in gridstring gs. You can assume row is an integer, but if it is not a valid row number (at least 0 and less than the height of gs), it returns null. Use slice, width, and height. Examples:

    > getRow(g, 1)
      "EFGH"
    > getRow(g, 9)
      null
  3. Complete getColumn(gs, column) so that it returns the string corresponding to the specified column number in gridstring gs. You can assume column is an integer, but if it is not a valid column number (at least 0 and less than the width of gs), it returns null. Use get, width, and height. Examples:

    > getColumn(g, 2)
      "CGK"
    > getColumn(g, 6)
      null
  4. Complete transpose(gs) so that it returns a new gridstring that is like gridstring gs but where it columns have becomes its rows and its rows its columns. Use getColumn, makeGrid, width, and height. Example:

    > showGrid(transpose(myGrid))
      AEI
      BFJ
      CGK
      DHL

  5. Complete sliceRows(gs, startRow, stopRow) so that it returns a new gridstring derived from gridstring gs that is the same width but only contains the rows from startRow up to but not including stopRow. Assume that startRow and stopRow are nonnegative integers, but if startRow is not less than stopRow it should return the empty gridstring. If stopRow is more than the height of gs it should be treated as if is the height. Use slice, makeGrid, and width. Examples:

    > showGrid(sliceRows(g, 0, 2))
      ABCD
      EFGH
    > showGrid(sliceRows(g, 1, 7))  // past last row is ignored
      EFGH
      IJKL
    > sliceRows(g, 2, 2) === EMPTY_GRID
      true
  6. Complete sliceColumns(gs, startColumn, stopColumn) so that it returns a new gridstring derived from gridstring gs that is the same height but only contains the columns from startColumn up to but not including stopColumn. Assume that startColumn and stopColumn are nonnegative integers, but if startColumn is not less than stopColumn it should return the empty gridstring. If stopColumn is more than the width of gs it should be treated as if is the width. Use slice, makeGrid, and width. Examples:

    > showGrid(sliceColumns(g, 1, 3))
      BC
      FG
      JK
    > showGrid(sliceColumns(g, 1, 9))  // past last column is ignored
      BCD
      FGH
      JKL
    > sliceColumns(g, 3, 3) === EMPTY_GRID
      true
  7. Complete sliceRectangle(gs, x1, y1, x2, y2) so that it returns a new gridstring derived from gridstring gs that consists of the rectangular fragment starting at column x1 and row y1 and running up to but not including column x2 and row y2. Assume x1, y1, x2, and y2 are nonnegative integers. If x1 is not less than x2 or if y1 is not less than y2 then it should return the empty gridstring. If x2 is beyond the width of gs it should be treated as the width and if y2 is beyond the height of gs it should be treated as the height. This can be achieved with a simple combination of sliceRows and sliceColumns. Examples:

    > showGrid(sliceRectangle(g, 1, 0, 3, 2))
      BC
      FG
    > showGrid(sliceRectangle(g, 1, 1, 888, 999))
      FGH
      JKL
    > sliceRectangle(g, 1, 0, 1, 2) === EMPTY_GRID
      true
    > sliceRectangle(g, 1, 1, 3, 0) === EMPTY_GRID
      true

  8. Complete set(gs, column, row, ch) so that it returns a new gridstring that is just like gridstring gs except the character that occurs in gs at column, row is replaced with character ch. Assume ch is a character (a string of length 1). You can also assume column and row are integers, but if they are not valid (at least 0 and less than the width or height, respectively), the returned gridstring should be identical to gs. Use slice, makeGrid, width, and height. Examples:

    > showGrid(set(g, 2, 1, '?'))
      ABCD
      EF?H
      IJKL
    > showGrid(set(g, 5, 1, '!'))   // column out of bounds
      ABCD
      EFGH
      IJKL

  9. Complete padRows(gs, h) so that it returns a new gridstring that is like gridstring gs but consists of extra rows (filled with PAD_CHAR), if necessary so that it is of height h. If h is not more than the height of gs the returned gridstring is identical to gs. Use repeat, width, and height. Examples:

    > height(g)
      3
    > height(padRows(g, 5))
      5
    > size(padRows(g, 7))
      28
    > showGrid(padRows(g, 5))  // note two blank lines
      ABCD
      EFGH
      IJKL
      ____
      ____
    > showGrid(padRows(g, 2))  // just same old grid displayed here
      ABCD
      EFGH
      IJKL
  10. Complete padColumns(gs, w) so that it returns a new gridstrin that is like gridstring gs but consists of extra blank columns (filled with PAD_CHAR), if necessary so that it is of width w. If w is not more than the width of gs the returned gridstring is identical to gs. Use pad, makeGrid, width, and height. Examples:

    > width(padColumns(g, 7))
      7
    > showGrid(padColumns(g, 7))
      ABCD___
      EFGH___
      IJKL___
    > showGrid(padColumns(g, 2))   // same old grid
      ABCD
      EFGH
      IJKL
  11. Complete glueVertical(gs1, gs2) so that it returns a new gridstring that represents the combination of gridstring gs1 stacked above gridstring gs2. The width of the resulting gridstring should be as wide as the wider of the two argument gridstrings. Use padColumns, pad, getRow, width, and height. Examples:

    > showGrid(glueVertical(g, g))
      ABCD
      EFGH
      IJKL
      ABCD
      EFGH
      IJKL
    > showGrid(glueVertical(g, fillGrid(2, 4, '*')))
      ABCD
      EFGH
      IJKL
      **__
      **__
      **__
      **__
    > showGrid(glueVertical(g, fillGrid(5, 2, '*')))
      ABCD_
      EFGH_
      IJKL_
      *****
      *****
  12. Complete glueHorizontal(gs1, gs2) so that it returns a new gridstring that represents the combination of gridstring gs1 followed by gridstring gs2 to its right. The height of the resulting gridstring should be as high as the taller of the two argument gridstrings. Use padRows, getRow, width, and height. Examples:

    > showGrid(glueHorizontal(g, g))
      ABCDABCD
      EFGHEFGH
      IJKLIJKL
    > showGrid(glueHorizontal(g, fillGrid(7, 2, '*')))
      ABCD*******
      EFGH*******
      IJKL_______
    > showGrid(glueHorizontal(g, fillGrid(2, 7, '*')))
      ABCD**
      EFGH**
      IJKL**
      ____**
      ____**
      ____**
      ____**

Experimetning with my solutions

You can open up on a console while viewing this page and try examples such as:

> showGrid(reflow(g, 3))

> showGrid(glueHorizontal(g, fillGrid(7, 2, '*')))