#### Assignment 8: Iterators, Analysis, and Sameness

Goals: Further practice with ArrayLists; mutable worlds.

##### Instructions

The submissions will be organized as follows:

Homework 8 Problem 1: The Knitting.java file.

Homework 8 Problem 2: The StrangeIter.java file.

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 —

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 —

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

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)\):

Pick a starting value, e.g. \(A(0) = 20\)

For all \(n > 0\), look at the value of \(A(n - 1)\). Find the largest index \(m\) (less than \(n - 1\)) such that \(A(m) = A(n - 1)\). Then we define \(A(n) = (n - 1) - m\). If no such \(m\) exists, then \(A(n) = 0\).

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\) |

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

Design a class StrangeSequenceIter that generates this sequence of numbers. Provide two constructors: one constructor should allow you to specify the starting value for \(A(0)\), while the other should supply a default of \(2510\). Your implementation should be as efficient as you can manage, while remaining well-designed.

As a hint to check if you're on the right track, here is an excerpt of correct values for the sequence, when starting from a seed value of 5, at indices 300 through 310:

\(m\)

\(A(m)\)

Reason

\(0\)

\(5\)

Initial value

...

...

...

\(300\)

\(3\)

Found \(A(299)=0\) at index 296, so \(A(300)=(299 - 296)=3\)

\(301\)

\(16\)

Found \(A(300)=3\) at index 284, so \(A(301)=(300 - 284)=16\)

\(302\)

\(192\)

Found \(A(301)=16\) at index 109, so \(A(302)=(301 - 109)=192\)

\(303\)

\(0\)

Value \(A(302)=192\) not found before index 302

\(304\)

\(4\)

Found \(A(303)=0\) at index 299, so \(A(304)=(303 - 299)=4\)

\(305\)

\(12\)

Found \(A(304)=4\) at index 292, so \(A(305)=(304 - 292)=12\)

\(306\)

\(63\)

Found \(A(305)=12\) at index 242, so \(A(306)=(305 - 242)=63\)

\(307\)

\(0\)

Value \(A(306)=63\) not found before index 306

\(308\)

\(4\)

Found \(A(307)=0\) at index 303, so \(A(308)=(307 - 303)=4\)

\(309\)

\(4\)

Found \(A(308)=4\) at index 304, so \(A(309)=(308 - 304)=4\)

\(310\)

\(1\)

Found \(A(309)=4\) at index 308, so \(A(310)=(309 - 308)=1\)

...

...

...

Analyze the big-O performance of your iterator. In terms of the index \(idx\), the largest number \(MaxVal(idx)\) seen so far, the number of distinct values \(DistinctVals(idx)\), or any other quantity related to this problem that you can think of, give the tightest big-O bound you can for the hasNext and next methods, both for time complexity and for space complexity. (We have only just started big-O analysis in class, so I don’t expect your answers to be as formally perfect as an Algorithms class might expect. You can earn partial credit for your answer if (a) it is a looser bound than optimal but is nevertheless well-explained, or (b) is an optimal answer but has a vague explanation. If your bound is too low, or gratuitously too loose, that would not be an appropriate answer.)

- Extra credit: proofs!
The sequence above can be shown to contain the value \(0\) infinitely many times. Use this fact, and the definition of the sequence, to show that there is no maximum value for the sequence.

For a given value \(N\), give a formula for the earliest index where \(N\) could possibly appear. Give another formula for the largest possible index before you must have seen a value of at least \(N\).

Prove that the sequence must contain zero an infinite number of times.