On this page:
Instructions
Problem 1: Knitted fabric
Problem 2: A Strange Sequence of Numbers
8.3

Assignment 8: Iterators, Analysis, and Sameness

Goals: Further practice with ArrayLists; mutable worlds.

Instructions

The submissions will be organized as follows:

Due Date: Tuesday, March 29th at 9:00pm

Problem 1: Knitted fabric

In this problem you are going to design two distinct but related data definitions: one to describe knitted fabric, and another to describe the instructions needed to actually make a fabric. Read the entire problem carefully before starting; you might otherwise jump to conclusions that are not warranted.

A knitted fabric is made up of two basic kinds of stitches: knits and purls. On the front side of the fabric, a knit stitch looks like a V, while on the back side it looks like a -. Purl stitches are the opposite: on the front side of the fabric they look like a -, while on the back side they look like a V. A knitted fabric is made up of rows of these stitches, typically starting from the bottom and working upward (e.g. from the waistband of a sweater up to the neck), and combining different stitches in different pattern on different rows naturally produces different textures of results.

Design a class KnittedFabric (and any helper classes) to represent a knitted fabric. (Hint: your design should not need any fields of type String.) Your KnittedFabric class must include a constructor with zero arguments, to create an empty fabric.

Design a method KnittedFabric addRow(Iterator<IStitch> rowIter) that takes in an iterator of stitches, from left to right on the front side of the fabric, and adds that row of stitches to the current fabric — and then returns the current fabric, so that you can add another row to it easily.

Design a method String renderFabric that draws your fabric as a string of text. You can see some examples of rendered fabrics below.

Design a method sameFabric that checks if two knitted fabrics look the same. Keep in mind, you might be looking at the front side of one fabric and the back side of the other, but they might be the same fabric if you turn them both to face forward — the following two fabrics are the same:

VVV----V    and     -VVVV---
---VVVV-            V----VVV

Knitting instructions are a bit trickier. They follow a few rules:
  • Instructions are written for right-handed knitters, so the first instruction in a row is on the right edge of the fabric, and the last instruction in a row is on the left edge of the fabric.

  • A simple instruction for a row of fabric might say something like “Knit 3, purl 3, knit 1, purl 3.” This will produce the fabric ---V---VVV.

  • A fancier set of instructions might include grouping: “Knit 4, (purl 2, knit 2) 3 times, purl 4” would produce the fabric ----VV--VV--VV--VVVV. We can actually think of this grouping as extending to individual stitches: the simple instruction “Knit 3, purl 3” could be written as “(knit) 3 times, (purl) 3 times” instead. So there are really three kinds of instructions: knit, purl and repeat.

  • Knitting is typically worked from the bottom up, so the first row of instructions is the bottom of the fabric.

  • At the end of every row, knitters turn the fabric around, so that they’re now looking at the other side of the fabric. This swaps the left and right edges of the fabric, so that the first instruction of the next row produces a stitch that sits above the last stitch of the previous row. So for example, the instructions “row 1: knit 1, purl 5; row 2: knit 2, purl 4” will produce the fabric (looking at the front of the fabric):

    --VVVV
    -----V

    The first row is on the bottom, and is worked from right to left; the second row is above it, is worked from left to right, and the stitches are all backwards in appearance.

Design the class KnitFabricInstructions (and any helper classes needed) to represent knitting instructions for a full fabric. You should at minimum have classes that represent the three kinds of instructions, single rows of instructions, and an entire fabric’s worth of instructions. Your KnitFabricInstructions class must have a zero-argument constructor that creates an empty set of instructions.

Design a method KnitFabricInstructions addRow(Iterator<IInstruction> instructions) that adds a row of instructions to the growing fabric. Note that the instructions should be interpreted based on whichever side of the fabric is next: either right-to-left instructions for a front-side row, or left-to-right instructions for a back-side row. Like the other addRow method, this one will return the current set of instructions, so that you can continue add more rows of instructions.

Design the method KnittedFabric makeFabric() that follows the instructions and generates the knitted fabric result. (Hint: you will likely want an accumulator parameter in a helper method somewhere; that accumulator likely will be a boolean; you may need other accumulators or other helpers as well.)

Design the method boolean sameInstructions(KnitFabricInstructions other) that decides whether this set of instructions and that set of instructions will produce the same final fabric. As a tiny example, “knit 3, purl 3, knit 3, purl 3” will produce the same fabric as “((knit) 3 times, (purl) 3 times) 2 times.”

Problem 2: A Strange Sequence of Numbers

In this problem, you’ll design an Iterator<Integer> that will produce a non-negative sequence of numbers like the following:

\(20\), \(0\), \(0\), \(1\), \(0\), \(2\), \(0\), \(2\), \(2\), \(1\), \(6\), \(0\), \(5\), \(0\), \(2\), \(6\), \(5\), \(4\), \(0\), \(5\)

Here are the rules for generating the sequence \(A(n)\):

Looking at the sequence above:

\(m\)

    

\(A(m)\)

    

Reason

\(0\)

    

\(20\)

    

Initial value

\(1\)

    

\(0\)

    

Value \(A(0)=20\) not found before index 0

\(2\)

    

\(0\)

    

Value \(A(1)=0\) not found before index 1

\(3\)

    

\(1\)

    

Found \(A(2)=0\) at index 1, so \(A(3)=(2 - 1)=1\)

\(4\)

    

\(0\)

    

Value \(A(3)=1\) not found before index 3

\(5\)

    

\(2\)

    

Found \(A(4)=0\) at index 2, so \(A(5)=(4 - 2)=2\)

\(6\)

    

\(0\)

    

Value \(A(5)=2\) not found before index 5

\(7\)

    

\(2\)

    

Found \(A(6)=0\) at index 4, so \(A(7)=(6 - 4)=2\)

\(8\)

    

\(2\)

    

Found \(A(7)=2\) at index 5, so \(A(8)=(7 - 5)=2\)

\(9\)

    

\(1\)

    

Found \(A(8)=2\) at index 7, so \(A(9)=(8 - 7)=1\)

\(10\)

    

\(6\)

    

Found \(A(9)=1\) at index 3, so \(A(10)=(9 - 3)=6\)

\(11\)

    

\(0\)

    

Value \(A(10)=6\) not found before index 10

\(12\)

    

\(5\)

    

Found \(A(11)=0\) at index 6, so \(A(12)=(11 - 6)=5\)

\(13\)

    

\(0\)

    

Value \(A(12)=5\) not found before index 12

\(14\)

    

\(2\)

    

Found \(A(13)=0\) at index 11, so \(A(14)=(13 - 11)=2\)

\(15\)

    

\(6\)

    

Found \(A(14)=2\) at index 8, so \(A(15)=(14 - 8)=6\)

\(16\)

    

\(5\)

    

Found \(A(15)=6\) at index 10, so \(A(16)=(15 - 10)=5\)

\(17\)

    

\(4\)

    

Found \(A(16)=5\) at index 12, so \(A(17)=(16 - 12)=4\)

\(18\)

    

\(0\)

    

Value \(A(17)=4\) not found before index 17

\(19\)

    

\(5\)

    

Found \(A(18)=0\) at index 13, so \(A(19)=(18 - 13)=5\)

...

    

...

    

...