CMU 15-112: Fundamentals of Programming and Computer Science
Homework 2 (Due Sat 13-Feb at 8pm ET (Pittsburgh-time))

This homework is solo. You must not collaborate with anyone (besides current course TA's and faculty) in any way. See the syllabus for more details.
To start:
1. Create a folder named 'week2'
2. Download both hw2.py and cs112_s21_week2_linter.py to that folder
3. Edit hw2.py using VSCode
4. When you have completed and fully tested hw2, submit hw2.py to Autolab. For this hw, you may submit up to 8 times, but only your last submission counts.

Do not use string indexing, lists, list indexing, or recursion this week.
Do not hardcode the test cases in your solutions.

Homework2 overview:

Part 0 Required Small-Group or Large-Group Meetings [10 pts]
Attend and participate in at least one small group or large group covering Week 2 content. This must be live (synchronous) attendance, and not by viewing a recording (if this is genuinely impractical for you, email the course faculty with why and we will respond on a case-by-case basis). As usual, to receive points you have to be on time, stay the whole time, uni-task (not multi-task), and be attentive and participate fully.

Part 1 Standard or Spicy [45 pts]
Either do the (smaller) part1-standard problems or the (larger, somewhat more challenging) part1-spicy problem (below), your choice.
- Part 1 Standard [45 pts]
  1. longestDigitRun [15 pts]
  2. nthCircularPrime [15 pts]
  3. nthPalindromicPrime [15 pts]
- Part 1 Spicy [45 pts]
  1. play112 [45 pts]

Part 2 Required [45 pts]
Everyone must do these problems. We suggest completing part1 before attempting part2.
1. carrylessAdd [15 pts]
2. findZeroWithBisection [15 pts]
3. nthKaprekarNumber [15 pts]

Part 3 Bonus/Optional [up to 2 bonus pts]
These are bonus/optional. They are fun, interesting problems that are worth very few points. If you attempt these, do them for the fun and the learning, not the points.
1. carrylessMultiply [1 bonus pt]
2. nearestKaprekarNumber [1 bonus pt]

Part 4 Spicy-Bonus/Optional [up to 4 bonus pts]
This is also optional, but more challenging. It is a fascinating problem, and we very much hope that quite a few of you give it a go. Enjoy!!!
1. Integer Data Structures [4 bonus pts]

Standard Problems
Either do the (smaller) part1-standard problems or the (larger, somewhat more challenging) part1-spicy problem (below), your choice, but not both.

longestDigitRun [standard, 15 pts]
Write the function longestDigitRun(n) that takes a possibly-negative int value n and returns the digit that has the longest consecutive run, or the smallest such digit if there is a tie. So, longestDigitRun(117773732) returns 7 (because there is a run of 3 consecutive 7's), as does longestDigitRun(-677886).

nthCircularPrime [standard, 15 pts]
Write the function nthCircularPrime that takes a non-negative int n and returns the nth Circular prime, which is a prime number that does not contain any 0's and such that all the numbers resulting from rotating its digits are also prime. The first Circular primes are 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 197... To see why 197 is a Circular prime, note that 197 is prime, as is 971 (rotated left), as is 719 (rotated left again).

nthPalindromicPrime [standard, 15 pts]
Write the function nthPalindromicPrime(n), where a palindromic prime is a number that is both prime and palindromic (same forwards as backwards). See here for details. So nthPalindromicPrime(0) returns 2, and nthPalindromicPrime(10) returns 313.

Spicy Problem
You should either do all the standard problems (above) or this spicy problem, but not both.

play112 [spicy, 45 pts]
See "The 112 Game" here (skip to Part B). Be sure to follow the spec exactly, so the autograder can properly grade your work! Also, note that the test function in that writeup uses Python 2, but the one in the hw2.py file we provided uses Python 3.

Required Problems
Everyone must do all these required problems.

carrylessAdd [required, 15 pts]
First, you may wish to read the first page (page 44) from here about Carryless Arithmetic. Or, just understand that carryless addition is what it sounds like -- regular addition, only with the carry from each column ignored. So, for example, if we carryless-ly add 8+7, we get 5 (ignore the carry). And if we add 18+27, we get 35 (still ignore the carry). With this in mind, write the function carrylessAdd(x, y) that takes two non-negative integers x and y and returns their carryless sum. As the paper demonstrates, carrylessAdd(785, 376) returns 51.

findZeroWithBisection [required, 15 pts]
Write the function findZeroWithBisection(f, x0, x1, epsilon) as described here.

nthKaprekarNumber [required, 15 pts]
Background: a Kaprekar number is a positive integer, the representation of whose square can be split into two possibly-different-length parts (where the right part is not zero) that add up to the original number again. For instance, 45 is a Kaprekar number, because 45**2 = 2025 and 20+25 = 45. You can read more about Kaprekar numbers here. The first several Kaprekar numbers are: 1, 9, 45, 55, 99, 297, 703, 999 , 2223, 2728,...

With this in mind, write the function nthKaprekarNumber(n) that takes a non-negative int n and returns the nth Kaprekar number, where as usual we start counting at n==0.

Bonus Problems
Bonus problems are entirely optional and worth few points. Do them for the fun and the learning.

carrylessMultiply [bonus, 1 pt]
Write the function carrylessMultiply(x, y), that works similarly to carrylessAdd(x, y), based on this paper on Carryless Arithmetic. This paper shows that carrylessMultiply(643, 59) returns 417. Hint: it may help if you do this differently than usual long multiplication. Instead of working by rows in the output, work by columns. So first compute all the ones digit values, and sum those mod 10. Then compute all the tens digit values, and sum those mod 10. And so on. You may assume x and y are non-negative.

Hint #1: do not solve carrylessMultiply(x, y) by simply calling carrylessAdd(x, result) a total of y times. That is wrong on two levels. First, it is simply too inefficient (what if we are multiplying 20-digit numbers?). Second, it is also wrong algorithmically! CarrylessMultiply is not like normal multiply, and if we take + to be carrylessAdd and * to be carrylessMultiply, then it is not necessarily true that (x * y) is the same as (x + x + ... + x + x) for a total of y x's. Yikes. So: stick with the next hint (see below). It also uses carrylessAdd and is fairly straightforward, but it is reasonable efficient and algorithmically correct. Good luck with it.

Hint #2: Here's a hint on one way to solve this problem (there are many ways, and this way is not the most efficient, to be sure, but it is efficient enough and it is perhaps among the clearest and easiest ways).

Consider multiplying 123 * 456. Observe that:

123 * 456 = 123 * 4 * 100 + 123 * 5 * 10 + 123 * 6

in this way, we actually only have to multiply 123 times a single digit each time, then multiply that result by the right power of 10. Right?

Ok, so now, to multiply by a single digit, we can instead just add that many times. That is:

123 * 6 == 123 + 123 + 123 + 123 + 123 + 123

Why is that interesting? Because we already have carrylessAdd, so we can just use that to do all this addition.

Of course, multiplying by simply adding is very inefficient. But since we are only doing it for multiplying by a single digit, there's a max of 9 additions (8 if you think about it), and so it's not so inefficient. It's actually acceptable, if not ideal, and certainly good enough for hw2, though again better approaches do exist.

Hope this helps. And, again, you can safely ignore all of this and solve this problem any way you wish.

nearestKaprekarNumber [bonus, 1 pt]
Bearing in mind the definition of Kaprekar Number from above, write the function nearestKaprekarNumber(n) that takes an int or float value n and returns the Kaprekar number closest to n, with ties going to smaller value. For example, nearestKaprekarNumber(49) returns 45, and nearestKaprekarNumber(51) returns 55. And since ties go to the smaller number, nearestKaprekarNumber(50) returns 45.

Note: as you probably guessed, this also cannot be solved by counting up from 0, as that will not be efficient enough to get past the autograder. Hint: one way to solve this is to start at n and grow in each direction until you find a Kaprekar number.

Spicy Bonus Problem
This is a bonus problem, only quite spicy. We sure hope you consider it! Enjoy!!!

Integer Data Structures [bonus, up to 4 pts]
This is a fun and instructive exercise that combines some elements from 15-112, 15-122, 15-150, and 15-251. We will use normal Python integers to represent lists, sets, maps, strings, and finite state machines. While there are more efficient ways to represent all those things, it is fascinating that arbitrary-length Python integers alone are sufficient for all of that and more!

Note: don't be daunted by the long writeup. You can do this!

Since this problem has many parts, and it would not be fair if you only got credit if you completed ALL of them, there are several checkpoints that you can complete to get chunks of the 4 points available from this problem:
- [1 pt] lengthEncode, lengthDecode, lengthDecodeLeftmostValue
- [1 pt] Lists
- [1 pt] Sets, Strings, Maps
- [1 pt] FSMs
1. Background
  Since we plan to include multiple integers in a single integer, we will start by encoding integers with a prefix of the number of digits in that integer. For example, we might encode 25 as 225, where the first 2 says there are 2 digits. But then we'd have to encode 1234567890 with a count of 10. But then we'd have to know how many digits our count itself has! And we are now recursing. Oh no!
  
  Our solution, which is not fully general but which is good enough for our purposes, is to first have a count-count of the number of digits in the count. That first count-count will always be exactly one digit, so the count itself can be between 1 and 9 digits. So the largest digit count is 999,999,999. So this approach does not allow numbers with one billion or more digits. We can live with that restriction.
  
  We also have to deal with the sign (+/-) of the number. Normally this might be 0 for positive and 1 for negative, but leading 0's can cause confusion, so we'll use 1 for positive and 2 for negative.
  
  Thus, we will encode numbers as such: [sign-digit] [count-count] [count] [number]. So, for example, to encode 789, the sign-digit is 1 (positive). The count is 3, so the count-count is 1. Thus, the entire encoding of 789 is 113789.
  
  For another example, to encode -1234512345, the sign-digit is 2 (negative). The count is 10, so the count-count is 2. Thus, the entire encoding of -1234512345 is 22101234512345.
2. lengthEncode(n)
  Time to write some code! Write the function lengthEncode(n) that takes a possibly-negative Python integer and returns the length prefix encoded integer as described above. Here is a test function:
```
def testLengthEncode():
    print('Testing lengthEncode()...', end='')
    assert(lengthEncode(789) == 113789)
    assert(lengthEncode(-789) == 213789)
    assert(lengthEncode(1234512345) == 12101234512345)
    assert(lengthEncode(-1234512345) == 22101234512345)
    assert(lengthEncode(0) == 1110)
    print('Passed!')
```
  Hint: while not required, we found it very helpful to write the helper function intCat(n, m) that took two non-negative integers and returned their concatenation. So, for example, intCat(123, 45) returns 12345.
3. lengthDecode(n)
  Now write lengthDecode(n) that performs the inverse operation of lengthEncode(n), so:
```
def testLengthDecode():
    print('Testing lengthDecode()...', end='')
    assert(lengthDecode(113789) == 789)
    assert(lengthDecode(213789) == -789)
    assert(lengthDecode(12101234512345) == 1234512345)
    assert(lengthDecode(22101234512345) == -1234512345)
    assert(lengthDecode(1110) == 0)
    print('Passed!')
```
4. lengthDecodeLeftmostValue(n)
  The whole point of using the length prefix was to allow us to place multiple integers one after another inside a single larger integer. For example, we encode 2 as 1112 and we encode 789 as 113789, so we can encode a 2 followed by a 789 as simply 1112113789.
  
  Thus, we need a way to decode just the leftmost value. For that, write the function lengthDecodeLeftmostValue(n) that takes a number with one-or-possibly-more encoded values and decodes just the leftmost value. This function has to return two values: the decoded value, and also the rest of the encoded values! So lengthDecodeLeftmostValue(1112113789) returns (2, 113789), meaning that 2 was the leftmost value, and after removing the 2, 113789 still remains.
  
  Thus, we call this function using this pattern:
```
encodedValues, nextValue = lengthDecodeLeftmostValue(encodedValues)
```
  With that in mind, write lengthDecodeLeftmostValue(n) so that the following test function passes:
```
def testLengthDecodeLeftmostValue():
    print('Testing lengthDecodeLeftmostValue()...', end='')
    assert(lengthDecodeLeftmostValue(111211131114) == (2, 11131114))
    assert(lengthDecodeLeftmostValue(112341115) == (34, 1115))
    assert(lengthDecodeLeftmostValue(111211101110) == (2, 11101110))
    assert(lengthDecodeLeftmostValue(11101110) == (0, 1110))
    print('Passed!')
```
  Hint: you may want to think carefully about the case where the second-to-leftmost value is a 0. The last two tests above deal with that case.
  PS: We highly reccomend completing this function BEFORE lengthDecode
5. Lists
  We can now use a sequence of length-prefix-encoded integers to represent a list of integers. We will just prefix the entire list with the length of that list. So, for example, the Python list [9, 8888]. This list is of length 2, so we will encode it as the values 2, 9, 8888. Since these are encoded as 1112, 1119, and 1148888, respectively, we will encode the entire list as 111211191148888. Note that an empty list is just a list of length 0, and so it is just the length-prefix-encoded value of 0, which is 1110 (the result of calling lengthEncode(0)).
  
  With that, here are the functions you need to write:
  - newIntList(): takes no argument, returns an empty list.
  - intListLen(L): takes a list, returns its length (the leftmost encoded value).
  - intListGet(L, i): takes a list and an index, and returns the decoded value at that index. Returns the string 'index out of range' as needed.
  - intListSet(L, i, v): takes a list and an index, and returns a new list with the value at the given index changed to be the encoded value of v. Returns the string 'index out of range' as needed.
  - intListAppend(L, v): takes a list and a value, and returns a new list with that value (encoded) appended.
  - intListPop(L): takes a list and removes the last value ("pops" it). It then returns two values: the list without that popped value, and that popped value itself.
  And here is the test function to pass:
```
def testIntList():
    print('Testing intList functions...', end='')
    a1 = newIntList()
    assert(a1 == 1110) # length = 0, list = []
    assert(intListLen(a1) == 0)
    assert(intListGet(a1, 0) == 'index out of range')

    a1 = intListAppend(a1, 42)
    assert(a1 == 111111242) # length = 1, list = [42]
    assert(intListLen(a1) == 1)
    assert(intListGet(a1, 0) == 42)
    assert(intListGet(a1, 1) == 'index out of range')
    assert(intListSet(a1, 1, 99) == 'index out of range')

    a1 = intListSet(a1, 0, 567)
    assert(a1 == 1111113567) # length = 1, list = [567]
    assert(intListLen(a1) == 1)
    assert(intListGet(a1, 0) == 567)

    a1 = intListAppend(a1, 8888)
    a1 = intListSet(a1, 0, 9)
    assert(a1 == 111211191148888) # length = 2, list = [9, 8888]
    assert(intListLen(a1) == 2)
    assert(intListGet(a1, 0) == 9)
    assert(intListGet(a1, 1) == 8888)

    a1, poppedValue = intListPop(a1)
    assert(poppedValue == 8888)
    assert(a1 == 11111119) # length = 1, list = [9]
    assert(intListLen(a1) == 1)
    assert(intListGet(a1, 0) == 9)
    assert(intListGet(a1, 1) == 'index out of range')

    a2 = newIntList()
    a2 = intListAppend(a2, 0)
    assert(a2 == 11111110)
    a2 = intListAppend(a2, 0)
    assert(a2 == 111211101110)
    print('Passed!')
```
6. Sets
  A set is similar to a list, only with the restriction that values can only appear once, even if they are added multiple times. While there are more efficient approaches, we can represent sets using lists. In particular, when you add a value, we can first check if it is already in the set, and if so, do nothing. So we only add values that are not already in the set. That's it!
  
  With that, here are the functions you need to write:
  - newIntSet(): returns a new empty set (which is the same as a new empty list, which is the same as the length-prefix-encoded value for 0).
  - intSetAdd(s, v): takes a set and a value, and returns the same set if the value is already in it, or a new set that appends the value to the end of the set s.
  - intSetContains(s, v): takes a set and a value, and returns True if that set contains that value, and False otherwise.
  And here is the test function to pass:
```
def testIntSet():
    print('Testing intSet functions...', end='')
    s = newIntSet()
    assert(s == 1110) # length = 0 
    assert(intSetContains(s, 42) == False)
    s = intSetAdd(s, 42)
    assert(s == 111111242)  # length = 1, set = [42]
    assert(intSetContains(s, 42) == True)
    s = intSetAdd(s, 42) # multiple adds --> still just one
    assert(s == 111111242) # length = 1, set = [42]
    assert(intSetContains(s, 42) == True)
    print('Passed!')
```
7. Strings
  We can convert individual characters into numbers using the Python function ord(c), and we can undo that and convert those numbers back into characters using chr(n). Thus, we can store a Python String as a single integer by creating an encoded list of those ord values.
  
  With that, here are the functions you need to write:
  - encodeString(s): takes a Python string s and returns a length-prefixed list of the ord values of the characters in s.
  - decodeString(L): takes a length-prefixed list L and returns the corresponding Python string.
  And here is the test function to pass:
```
def testEncodeDecodeStrings():
      print('Testing encodeString and decodeString...', end='')
      assert(encodeString('A') == 111111265) # length = 1, str = [65]
      assert(encodeString('f') == 1111113102) # length = 1, str = [102]
      assert(encodeString('3') == 111111251) # length = 1, str = [51]
      assert(encodeString('!') == 111111233) # length = 1, str = [33]
      assert(encodeString('Af3!') == 1114112651131021125111233) # length = 4, str = [65,102,51,33]
      assert(decodeString(111111265) == 'A')
      assert(decodeString(1114112651131021125111233) == 'Af3!')
      assert(decodeString(encodeString('WOW!!!')) == 'WOW!!!')
      print('Passed!')
```
8. Maps
  A map is a data structure that converts keys into values (in Python this is called a "dictionary"). For example, we could use a map m to store country capitals. We could call intMapSet(m, 'France', 'Paris') to set the capital of 'France' to 'Paris'. Then, we could retrieve the capital by calling intMapGet(m, 'France'), which should return 'Paris'. Maps convert keys to values. So in this example, 'France' is the key, and 'Paris' is the value.
  
  Here, we are only using integers, but the idea is the same: a map will convert keys to values. And while there are more efficient approaches, we will store a map as a list of alternating values: key1, value1, key2, value2,...
  
  Thus, an empty map is just an empty list. Then, if we map the value 42 to 73, we get the list [42, 73], which is encoded as 11121124211273. Then, if we re-map the value 42 to 98765, since 42 can only be present once as a key, we change the 73 to instead be 98765, so we get the list [42, 98765].
  
  With that, here are the functions you need to write:
  - newIntMap(): takes no arguments and returns an empty map, which is an empty list.
  - intMapContains(m, key): takes a map and a key, and returns True if that map contains that key (as a key, not a value), and False otherwise.
  - intMapGet(m, key): takes a map and a key, and returns the value associated with that key in that map, or the string 'no such key' as appropriate.
  - intMapSet(m, key, value): takes a map, a key and a value, and returns a new map which is the same as m only with the given key mapped to the given value. If the key was already in m, this involves modifying the value the key maps to. Otherwise, this involves adding the key and value to the end of the list.
  And here is the test function to pass:
```
def testIntMap():
    print('Testing intMap functions...', end='')
    m = newIntMap()
    assert(m == 1110) # length = 0
    assert(intMapContains(m, 42) == False)
    assert(intMapGet(m, 42) == 'no such key')
    m = intMapSet(m, 42, 73)
    assert(m == 11121124211273) # length = 2, map = [42, 73]
    assert(intMapContains(m, 42) == True)
    assert(intMapGet(m, 42) == 73)
    m = intMapSet(m, 42, 98765)
    assert(m == 11121124211598765) # length = 2, map = [42, 98765]
    assert(intMapGet(m, 42) == 98765)
    m = intMapSet(m, 99, 0)
    assert(m == 11141124211598765112991110) # length = 4, map = [42, 98765, 99, 0]
    assert(intMapGet(m, 42) == 98765)
    assert(intMapGet(m, 99) == 0)
    print('Passed!')
```
9. Finite State Machines (FSM's)
  A Finite State Machine (FSM) is a theoretical machine that is useful for modeling certain kinds of limited computation. You can read about them online. The basic ideas are these:
  - An FSM has states. Ours will be numbered.
  - An FSM has a special start state. Ours will be state 1.
  - An FSM has transitions, which are rules about how to move from one state to another. A transition is specified by 3 values -- a startState, a symbol, and an endState. If the FSM is in the startState when it sees that symbol, it will transition to the endState. In our case, the startState and the endState will both be integers, and the symbol will be a single digit.
  - An FSM has accepting states. If the FSM finishes reading symbols and it is in an accepting state, we say that the FSM accepts those symbols. Our FSM will work in this way.
  We will represent our FSM as a list of two values: a map of transitions, and a set of accepting states. Each transition itself maps a startState to yet another map, that second map mapping symbols (digits) to endStates. This is a bit complicated, and you may need to read this a few times, think about it, and carefully study the examples in the test code below to fully understand it.
  
  With that, here are the functions you need to write:
  - newIntFSM(): takes no arguments and returns an empty FSM, which contains an empty map of transitions and an empty set of accepting states.
  - isAcceptingState(fsm, state): takes an fsm and a state, and returns True if that state is in the set of accepting states, and False otherwise.
  - addAcceptingState(fsm, state): takes an fsm and a state, and returns a new FSM that is the same except that the given state is added to the set of accepting states.
  - setTransition(fsm, fromState, digit, toState): returns a new FSM that is the same as the given fsm except with this new transition added. This involves updating two maps -- the outer map (mapping each fromState to its own map), and the inner map (mapping each digit to its toState). Look closely at the examples in the test function for details.
  - getTransition(fsm, fromState, digit): returns the toState that is mapped to by this fromState on this digit, or the string 'no such transition' as appropriate.
  - accepts(fsm, inputValue): takes an fsm and an inputValue, and returns True if the FSM accepts that inputValue, and False otherwise. To do this, it starts the FSM in its startState (1), then it transitions on each symbol from left-to-right in the inputValue. When it is done with all the values, it checks if it is in an accepting state. Note that if any transition is missing, this is not an error, it just means that the FSM does not accept the input.
  - states(fsm, inputValue): takes an fsm and an inputValue, and does basically the same thing as accepts(fsm, inputValue), only here instead of returning True or False, this returns a list (length-encoded-prefix list) of all the states that the FSM visited while computing the solution. This is mainly for testing purposes, so the autograder can verify your machine is working properly. Again, see the test code for details.
  And here is the first test function to pass:
```
def testIntFSM():
    print('Testing intFSM functions...', end='')
    fsm = newIntFSM()
    assert(fsm == 111211411101141110) # length = 2, [empty stateMap, empty startStateSet] 
    assert(isAcceptingState(fsm, 1) == False)

    fsm = addAcceptingState(fsm, 1)
    assert(fsm == 1112114111011811111111)
    assert(isAcceptingState(fsm, 1) == True)

    assert(getTransition(fsm, 0, 8) == 'no such transition')
    fsm = setTransition(fsm, 4, 5, 6)
    # map[5] = 6: 111211151116
    # map[4] = (map[5] = 6):  111211141212111211151116
    assert(fsm == 1112122411121114121211121115111611811111111)
    assert(getTransition(fsm, 4, 5) == 6)

    fsm = setTransition(fsm, 4, 7, 8)
    fsm = setTransition(fsm, 5, 7, 9)
    assert(getTransition(fsm, 4, 5) == 6)
    assert(getTransition(fsm, 4, 7) == 8)
    assert(getTransition(fsm, 5, 7) == 9)

    fsm = newIntFSM()
    assert(fsm == 111211411101141110) # length = 2, [empty stateMap, empty startStateSet] 
    fsm = setTransition(fsm, 0, 5, 6)
    # map[5] = 6: 111211151116
    # map[0] = (map[5] = 6):  111211101212111211151116
    assert(fsm == 111212241112111012121112111511161141110)
    assert(getTransition(fsm, 0, 5) == 6)

    print('Passed!')
```
  That test function verifies that the FSM is setup properly. This next test function verifies that it runs properly:
```
def testAccepts():
    print('Testing accepts()...', end='')
    fsm = newIntFSM()
    # fsm accepts 6*7+8 => See the diagram
    fsm = addAcceptingState(fsm, 3)
    fsm = setTransition(fsm, 1, 6, 1) # At state 1, receive 6, move to state 1
    fsm = setTransition(fsm, 1, 7, 2) # At state 1, receive 7, move to state 2
    fsm = setTransition(fsm, 2, 7, 2) # At state 2, receive 7, move to state 2
    fsm = setTransition(fsm, 2, 8, 3) # At state 2, receive 8, move to state 3
    assert(accepts(fsm, 78) == True)
    assert(states(fsm, 78) == 1113111111121113) # length = 3, list = [1,2,3]
    assert(accepts(fsm, 678) == True)
    assert(states(fsm, 678) == 11141111111111121113) # length = 4, list = [1,1,2,3]

    assert(accepts(fsm, 5) == False)
    assert(accepts(fsm, 788) == False)
    assert(accepts(fsm, 67) == False)
    assert(accepts(fsm, 666678) == True)
    assert(accepts(fsm, 66667777777777778) == True)
    assert(accepts(fsm, 7777777777778) == True)
    assert(accepts(fsm, 666677777777777788) == False)
    assert(accepts(fsm, 77777777777788) == False)
    assert(accepts(fsm, 7777777777778) == True)
    assert(accepts(fsm, 67777777777778) == True)
    print('Passed!')
```
  Here is a diagram explaining this FSM:
  
  And another diagram visualizing the integer data structure form of the FSM and its relationship to the various states and transitions.
10. In Summary
```
11241112421124211242112321128911311111311711232113109112971131001131011123211310511311611233112321127111311411310111297113116112321131061131111129811233112321128711311111311111310411311111311111233112331123311232112421124211242
```

CMU 15-112: Fundamentals of Programming and Computer Science Homework 2 (Due Sat 13-Feb at 8pm ET (Pittsburgh-time))

CMU 15-112: Fundamentals of Programming and Computer Science
Homework 2 (Due Sat 13-Feb at 8pm ET (Pittsburgh-time))