PS4: Iterate Until Done
 Due: 11:59pm Monday, February 29. This is a hard deadline (to give you sufficient time to work on your takehome exam 1, which will be posted that day and due on Monday March 7.)

Notes:
 The problems needn’t be done in order. Feel free to jump around.
 The problem set is worth 130 points.
 We’re asking you to keep track of the time estimates for each problem/subproblem.
 Submission:
 Write all your Racket code in a single file
yourAccountNameps4.rkt
and all your Python code in a single fileyourAccountNameps4.py
 In the yourFullName CS251 Spring 2016 Folder that you created for PS1, create a Google Doc named yourFullName CS251 PS4.
 For each problem and subproblem, please indicate at the beginning of each writeup approximately how long that problem took you to solve and write up.
 Include all answers, including copies of code from your
.rkt
and.py
files in your PS4 google doc. Please format your simplifications Problem 1b so that they’re easy to read. Format the derivation using the fixedwidth Courier New font (can use a small font size if that helps).  Drop copies of your
yourAccountNameps4.rkt
andyourAccountNameps4.py
files in your~/cs251/drop/ps04
drop folder on cs.wellesley.edu.
 Write all your Racket code in a single file
1. Simplifying Inside Lambdas (15 points)
The smallstep evaluation rules we have studied do not perform any evaluation of subexpressions inside the body of a lambda
expression. The body is only ``opened up’’ for evaluation when the lambda
expression is applied to argument values, at which point the argument values are substituted for the parameters in the body, and evaluation of the body proceeds.
However, it is possible to perform limited simplification of subexpressions inside the body of a lambda
expression for purposes of optimization. Such simplifications can also make the body of a lambda
expression easier to understand.
For example, consider the expression
(λ (w)
((λ (x y) (+ (* x x) (* y y)))
(+ 1 2) w))
According to our smallstep evaluation rules, this is a value, and cannot be reduced more.
However, there are simplifications inside (λ (w) ...)
we can perform that will not change its meaning:

We can simplify
(+ 1 2)
to3
. Performing an operation on two operand values within a function body is called constant folding. This yields the simplified expression:(λ (w) ((λ (x y) (+ (* x x) (* y y))) 3 w))

We can apply the function
(λ (x y) ...)
to the values3
andw
, where for the purposes of simplification we will extend the set of values to include identifiers (w
in this case). This yields the simplified expression. We’ll call this simplification value propagation.(λ (w) (+ (* 3 3) (* w w)))

Finally we can perform one more constant folding step to yield
(λ (w) (+ 9 (* w w)))
This final
lambda
expression is much easier to understand than the original. Furthermore, the simplification steps we have performed avoid evaluation steps that would otherwise need to be performed later, so the simplification steps are actually optimizations that can improve the efficiency of the function (assuming it would be called more than once).
We will use the curvy arrow ↝
to indicate simplification steps within lambda
bodies, as distinct from evaulation steps designated by ⇒
. So the simplification steps shown above can be written:
(λ (w)
((λ (x y) (+ (* x x) (* y y)))
(+ 1 2) w))
↝ (λ (w)
((λ (x y) (+ (* x x) (* y y)))
3 w))
↝ (λ (w) (+ (* 3 3) (* w w)))
↝ (λ (w) (+ 9 (* w w)))
In this problem you will explore some of the benefits and limitations of such simplifications.

(2 points) We will call a simplification step within a
lambda
expression safe if (1) it does not change the meaning of the function denoted by thelambda
or (2) the simplified function does not do more work than the unsimplified one when called. Otherwise it is unsafe.Even in simplification, substitution can only be performed when
lambda
expressions are applied to values, not to arbitrary expressions. Using the following expressions, show that substituting arbitrary expressions forlambda
parameters in thelambda
body can be unsafe:
(λ (a) ((λ (b) (* b b)) (+ a a)))

(λ (c) ((λ (d) (+ c 1)) (/ 1 0)))


(10 points) We have studied functions like the following in lecture:
(define curry2 (λ (binop) (λ (y) (λ (z) (binop y z))))) (define uncurry2 (λ (curriedbinop) (λ (a b) ((curriedbinop a) b)))) (define flip2 (λ (binop) (λ (s t) (binop t s)))) (define o (λ (f g) (λ (x) (f (g x)))))
The goal in this subproblem is to understand the meaning of this mystery function:
(define mystery (uncurry2 (o (curry2 map) (curry2 (flip2 )))))
We will begin by applying evaluation steps until we can’t get any further:
(uncurry2 (compose (curry2 map) (curry2 (flip2 )))) # Replace uncurry2, o, curry2, and flip by definitions ⇒* ((λ (curriedbinop) (λ (a b) ((curriedbinop a) b))) ((λ (f g) (λ (x) (f (g x)))) ((λ (binop) (λ (y) (λ (z) (binop y z)))) map) ((λ (binop) (λ (y2) (λ (z2) (binop y2 z2)))) # Rename y & z to y2 and z2 for clarity ((λ (binop) (λ (s t) (binop t s))) )))) # Apply (λ (binop) (λ (y) (λ (z) (binop y z)))) to map ⇒ ((λ (curriedbinop) (λ (a b) ((curriedbinop a) b))) ((λ (f g) (λ (x) (f (g x)))) (λ (y) (λ (z) (map y z))) ((λ (binop) (λ (y2) (λ (z2) (binop y2 z2)))) ((λ (binop) (λ (s t) (binop t s))) )))) # Apply (λ (binop) (λ (s t) (binop t s))) to  ⇒ ((λ (curriedbinop) (λ (a b) ((curriedbinop a) b))) ((λ (f g) (λ (x) (f (g x)))) (λ (y) (λ (z) (map y z))) ((λ (binop) (λ (y2) (λ (z2) (binop y2 z2)))) (λ (s t) ( t s))))) # Apply (λ (binop) (λ (y2) ...)) to (λ (s t) ( t s)) ⇒ ((λ (curriedbinop) (λ (a b) ((curriedbinop a) b))) ((λ (f g) (λ (x) (f (g x)))) (λ (y) (λ (z) (map y z))) (λ (y2) (λ (z2) ((λ (s t) ( t s)) y2 z2))))) # Apply (λ (f g) ...) to (λ (y) ...) and (λ (y2) ...) ⇒ ((λ (curriedbinop) (λ (a b) ((curriedbinop a) b))) (λ (x) ((λ (y) (λ (z) (map y z))) ((λ (y2) (λ (z2) ((λ (s t) ( t s)) y2 z2))) x)))) # Apply (λ (curriedbinop) ...) to (λ (x) ...) ⇒ (λ (a b) (((λ (x) ((λ (y) (λ (z) (map y z))) ((λ (y2) (λ (z2) ((λ (s t) ( t s)) y2 z2))) x))) a) b))
Evaluation steps get us partway toward our goal, but leave us with a complicated mess that is very difficult to understand! But you can use the simplification steps described above to further simplify it into something that is understandable.
Being very careful, start with the last expression in the evaluation sequence and apply one simplification step at a time until you cannot simplify the function any more. You should end up with a function that is very easy to understand. In addition to producing the simplified function expression, explain in English what the function does.

(3 points) If simplifications within
lambda
expressions are so helpful, why don’t we always apply them as part of evaluation? There is a good reason. Based on the following example, explain why simplifying the body oflambda
expressions is not allowed in smallstep evaluation:(λ (n) (if (> n 0) (+ n 1) ((λ (y) (y y)) (λ (z) (+ 1 (z z))))))
2. Compositional Programming (30 points)

(4 points) Many functions can be express by nesting invocations of higherorder functions like
foldr
,map
, andfilter
. Below is an example. Explain in English what theintrigue
function does. Do not explain in words the Racket code or algorithm. Rather, given inputn
, describe the output in declarative terms, like you might see in a contract for theintrigue
function without seeing its implementation.It may be helpful to use the mathematical notation for summation in your solution. For example, the following notation means the sum of the squares of all integers i between 1 and 10:
(define (intrigue n) (foldr + 0 (map (λ (row) (foldr + 0 row)) (map (λ (hi) (range 1 (+ hi 1))) (range 1 (+ n 1))))))

(10 points) Consider the following helper functions:
(define (o f g) (λ (x) (f (g x)))) (define (oall funs) (foldr o (λ (x) x) funs)) (define (curry2 binop) (λ (x) (λ (y) (binop x y)))) (define (curry3 ternop) (λ (x) (λ (y) (λ (z) (ternop x y z))))) (define (flip2 binop) (λ (x y) (binop y x)))
Using such functions, we can express nested invocations like those in
intrigue
using compositions of combinators, which are expressions that denote functions without using explicitlambda
s. For example, here is a definition for a function that sums the squares of odd integers from 1 up to (and including) a given limit:(define sumofsquaresofoddsupto (oall (list (((curry3 foldr) +) 0) ((curry2 map) ((curry2 (flip2 expt)) 2)) ((curry2 filter) (o ((curry2 =) 1) ((curry2 (flip2 remainder)) 2))) ((curry2 range) 1) ((curry2 +) 1) ))) > (sumofsquaresofoddsupto 9) 165 ; 1^2 + 3^2 + 5^2 + 7^2 + 9^2
Give an alternative definition of
intrigue
that has the following pattern, where each of the functions<fun_1>
through<fun_k>
is expressed without using any explicitlambda
s:(define intriguecomposed (oall (list <fun_1> ... <fun_k>)))

(7 points) In mathematics, the nfold composition of a function f, written f^{ n} is f composed with itself n times. Thus, f^{ 2} = f ◦ f, f^{ 3} = f ◦ f ◦ f, and so on. Note that f^{ 1} = f, and f^{ 0} = the identity function.
Define a Racket function
(nfold n f)
that takes a nonnegative integern
and a unary functionf
and returns the nfold composition off
. In your definition, you may not use explicit recursion. There are many different ways to definenfold
without recursion! You are allowed to use higherorder functions we’ve studied (e.g.,map
,foldr
,foldl
,genlist
,iterate
) as well as standard Racket functions likerange
.Here are some examples of using
nfold
:(define (id x) x) (define (inc x) (+ x 1)) (define (dbl y) (* y 2)) > ((nfold 2 inc) 0) 2 > ((nfold 17 inc) 100 117 > ((nfold 3 dbl) 1) 8 > ((nfold 2 (o inc dbl)) 5) 23 > ((nfold 2 (o dbl inc)) 5) 26 > ((nfold 17 id) 42) 42

(9 points) The curried
nfold
operatorcnfold
, defined below has some interesting properties.(define cnfold (curry2 nfold)) (define twice (cnfold 2)) (define thrice (cnfold 3)) > ((twice inc) 0) 2 > ((thrice inc) 0) 3 > ((twice dbl) 1) 4 > ((thrice dbl) 1) 8
In the following questions suppose that
a
andb
are nonnegative integers andf
is a unary function. Justify your answer to each question.(1)
(o (nfold a f) (nfold b f))
is equivalent to(nfold p f)
for what numberp
?(2)
(o (cnfold a) (cnfold b))
is equivalent to(cnfold q)
for what numberq
?(3)
((cnfold a) (cnfold b))
is equivalent to(cnfold r)
for what numberr
?Note: In Church’s λcalculus, it turns out that a function equivalent to
(cnfold n)
can be used to represent the nonnegative integern
. As you can see above, you can even do arithmetic on these representations! In fact, these representations are called Church numerals for this reason.
3. Iterating with foldl
and iterate
(15 points)

(5 points) A naive approach to evaluating a polynomial like x^{4} + 5x^{3} + 4x^{2} + 7x + 2 at input like 3 is to independently raise 3 to the powers 4, 3, 2, 1, 0, multiply each of the 5 coefficients by the 5 powers and finally add the results:
1*(3*3*3*3) + 5*(3*3*3) + 4*(3*3) + 7*3 + 2*1 = 1*81 + 5*27 + 4*9 + 21 + 2 = 81 + 135 + 36 + 21 + 2 = 275
But there is a more efficient approach, known as Horner’s method, that uses only (n + 1) multiplications and (n + 1) additions that calculates the result as:
((((0*3 + 1)*3 + 5)*3 + 4)*3 + 7)*3 + 2 = ((((0 + 1)*3 + 5)*3 + 4)*3 + 7)*3 + 2 = (((1*3 + 5)*3 + 4)*3 + 7)*3 + 2 = (((3 + 5)*3 + 4)*3 + 7)*3 + 2 = ((8*3 + 4)*3 + 7)*3 + 2 = ((24 + 4)*3 + 7)*3 + 2 = (28*3 + 7)*3 + 2 = (84 + 7)*3 + 2 = 91*3 + 2 = 273 + 2 = 275
Horner’s method for polynomial evaluation is remarkably simple to express using
foldl
on the lists of coeffcients. Show this by completing the following skeleton for thepolyeval
function:(define (polyeval coeffs x) (foldl {combining function} {initial value} coeffs))
For example:
> (polyeval (list 1 5 4 7 2) 3) 275 > (polyeval (list 1 5 4 7 2) 0) 2 > (polyeval (list 1 5 4 7 2) 1) 19 > (polyeval (list 1 5 4 7 2) 10) 15472 ;; Use map to test a bunch of inputs in parallel > (map ((curry2 polyeval) (list 1 5 4 7 2)) (range 11)) '(2 19 88 275 670 1387 2564 4363 6970 10595 15472) ;; Hey, can use this to convert binary numbers to decimal! > (polyeval (list 1 0 1 0 1 0) 2) 42 > (polyeval (list 1 1 1 1 1 0 1 1) 2) 251 ;; Or to convert hex to decimal: > (polyeval (list 6 1) 16) 97 > (polyeval (list 1 7 4 9) 16) 5961

(10 points) The iterative process of converting a decimal number to a sequence of binary bits is illustrated by the following iteration table for the conversion of the decimal number 38 to binary bits:
num bits Notes 38 () 19 (0) 38 mod 2 = 0 9 (1 0) 19 mod 2 = 1 4 (1 1 0) 9 mod 2 = 1 2 (0 1 1 0) 4 mod 2 = 0 1 (0 0 1 1 0) 2 mod 2 = 0 0 (1 0 0 1 1 0) 1 mod 2 = 1 Based on this idea, use either
iterate
oriterateapply
from lecture to define a function(bits n)
that takes a nonnegative integern
and returns a list of the bits for the binary representation ofn
. For example:> (bits 46) '(1 0 1 1 1 0) > (bits 251) '(1 1 1 1 1 0 1 1) > (bits 1729) '(1 1 0 1 1 0 0 0 0 0 1) > (bits 1) '(1) > (bits 0) '(0) ; Special case!
Notes:
 Here are the definitions of
iterate
anditerateapply
(define (iterate next done? finalize state) (if (done? state) (finalize state) (iterate next done? finalize (next state)))) (define (iterateapply next done? finalize state) (if (apply done? state) (apply finalize state) (iterateapply next done? finalize (apply next state))))

Handle an input of 0 as a special case.

As noted above, you can use
polyeval
to test your results!
 Here are the definitions of
4. Pair Generation (35 points)
Consider the following Python pairs
function, whose single argument n
you may asssume is a positive integer
def pairs(n): # Assume n is a positive integer
result = []
for diff in range (1, n+1):
for start in range(0, n+1diff):
result.append((start, start+diff))
return result

(4 points) The
pairs
function generates a list of pairs of integers related to inputn
, in a very particular order. Carefully describe in English exactly what the function does. Do not describe the Python code or algorithm. Rather, given inputn
, describe the output in declarative terms, like you might see in a contract for thepairs
function without seeing its implementation. 
(8 points) Define a Racket function
pairshof
that has the same inputoutput behavior as the Pythonpairs
function but is expressed in terms of nestings of higher order list functions likefoldr
andmap
. (``hof” means higherorder function). Do not usefilter
,foldl
,genlist
,iterate
, oriterateapply
in this part. Also, a Python pair (v1, v2) should be represented a the dotted pair conscell (v1 . v2) in Racket. 
(10 points) Recall the
genlist
function presented in lecture for generating lists:(define (genlist next done? seed) (if (done? seed) null (cons seed (genlist next done? (next seed)))))
Define a Racket function
pairsgenlist
that has the same inputoutput behavior as the Pythonpairs
function but is defined usinggenlist
by fleshing out the missing expressions in curly braces in the following skeleton:(define (pairsgenlist n) ; Assume is n a positive integer (genlist {next function goes here} {done? function goes here} {seed goes here}))

(13 points) Define a Racket function
pairsiter
that has the same inputoutput behavior as the Pythonpairs
function but is expressed iteratively in terms of one or more tailrecursive functions. Unlike the Pythonpairs
function and Racketpairsgenlist
function, which add pairs from the front of the list to the end, yourpairsiter
implementation should add pairs from the end of the list to the beginning.Notes:

You should not use
iterate
oriterateapply
in this problem! Instead, you should define one or more tailrecursive functions specialized for this particular problem. 
You should not perform any list reversals in your
pairsiter
definition. 
There are many solution approaches, but some involve more than one tail recursive function. (Two nested loops in the Python
pairs
function naturally correspond to a pair of mutually recursive tail recursive functions.) 
The
pairsiter
function need not itself be recursive; it can call one or more tailrecursive functions. 
It is helpful to use iteration tables involving concrete examples to help you define your tail recursive function(s).

5. List Processing with Tail Recursion and Loops (35 points)
One or more tailrecursive functions can be used to describe iterations that have complex termination and/or continuation conditions that are challenging to express with traditional looping constructs. In this problem we describe a complex iteration and then ask you (1) to flesh out a collection of tail recursive functions in Racket that implements it and (2) to write an equivalent loop in Python.
The iteration is invoked by a function process
that takes one argument, which is a list of integers. If the list contains any elements other than integers, the behavior of process
is unspecified. The elements of the list are processed left to right as follows:

Processing starts in add mode. In this mode each integer encountered is added to an accumulator that is initially 0, and the final value of the accumulator is return when the end of the list is reached. So in this mode,
(process ints)
just sums the integers inints
. For example:> (process (list 1 2 3 4 5)) 15 ; 1 + 2 + 3 + 4 + 5 > (process (list 1 7 2 9)) 19 ; 1 + 7 + 2 + 9

If the integer
42
is encountered in add mode, processing of the list immediately stops, and the answer accumulated so far is returned. For example:> (process (list 1 2 3 4 5 42 6 7)) 15 > (process (list 1 2 3 42 4 5 42 6 7)) ; only leftmost 42 matters 6 > (process (list 42 1 2 3 4 5 6 7)) 0

If a negative integer i is encountered in add mode, processing enters subtract mode, in which subsequent numbers are subtracted from the accumulator until another occurrence of same negative integer i is encountered, at which point processing switches back to add mode. The values of i for entering and leaving subtract mode do not affect the accumulator. If the end of the list is encountered before the matching i is found, the result of the accumulator is returned. In subtract mode, negative integers other than i are added to the accumutor and 42 does not end the computation but is simply subtracted from the accumulator. For example:
> (process (list 1 2 3 17 4 5 17 6 7)) 10 ; 1 + 2 + 3 + 4 + 5 + 6 + 7 > (process (list 1 2 1 4 6 1 7 8 5 9 5 10 11)) 20 ; 1 + 2 + 4 + 6 + 7 + 8 + 9 + 10 + 11 > (process (list 1 2 3 1 4 5 6 1 7 8 5 9)) 7 ; 1 + 2 + 3 + 4 + (5) + 6 + 7 + 8 + 9 (sequence ends before matching 5 encounterd) > (process (list 1 2 1 4 42 5 1 6 7)) 35 ; 1 + 2 + 4 + 42 + 5 + 6 + 7

If the integer
0
is encountered in add mode, call the very next integer the skip value, and let a be the absolute value of the skip value. The next a integers after the skip value will be ignored, as if they aren’t there, and the values after these will be processed in add mode. Any occurrence of ‘42’, ‘0’, or a negative number in the next a integers will have no effect. If the list ends before processing the skip value after a0
or before processing alla
values after the skip value, the final value of the accumulator is returned. Note that0
has no special effect in subtract mode, only add mode. For example:> (process (list 4 5 0 2 6 7 8 9)) 26 ; skips 0 2 6 7, so treated like (process (list 4 5 8 9)) > (process (list 7 2 0 3 6 1 8 5 0 4 9 10)) 14 ; skips 0 3 6 1 8 and 0 4 9 10, so treated like (process (list 7 2 5)) > (process (list 7 3 0)) 10 ; skips 0, so treated like (process (list 7 3)) > (process (list 7 3 0 4 1 0 8 42 5 1 4 9)) 2 ; skips 0 4 1 0 8 42, so treated like (process (list 7 3 5 1 4 9))

(15 points) Below is the skeleton for a collection of tailrecursive functions in Racket that implements the
process
function described above. Flesh out the missing parts in curly braces so thatprocess
behaves correctly.(define (process ints) (addmode 0 ints)) (define (addmode ans ints) (if (null? ints) ans (let ((fst (first ints)) (rst (rest ints))) (cond [(< fst 0) (subtractmode fst ans rst)] [(= fst 0) (skipmodestart ans rst)] {Add a clause to handle 42 here} [else {Process the remaining elements in add mode}])))) (define (subtractmode end ans ints) {Subtract elements in ints until negative integer end is encountered, and then switch back to add mode. If ints runs out, return ans.} (define (skipmodestart ans ints) (if (null? ints) ans (skipmode (abs (first ints)) ans (rest ints)))) (define (skipmode numberofelementstoskip ans ints) {Skip the specified number of elements in ints one at a time, and then return to add mode. If ints runs out, return ans.}
Notes:

Your
process
function should work for very large lists. E.g.> (process (range 43 1000000)) 499999499097 > (process (range 43 4000000)) 7999997999097 > (process (append (range 43 1000000) (list 17) (range 0 1000000) (list 17) (range 1 43))) 42 > (process (append (range 43 1000000) (list 17) (range 0 1000000) (list 17 42) (range 1 43))) 903 > (process (append (range 43 1000000) (list 17) (range 0 1000000) (list 17 0 42) (range 1 50))) 581
Racket may run out of memory for very large arguments to
range
, but that’s because very large lists created byrange
take a lot of memory storage. Theprocess
function itself should require constant stack space, so should work on arbitrarily large lists. 
You should test your resulting function on all of the above test cases to verify that it works correctly. You can do this by copying the following code into your Racket program and executing
(testall)
:(define (testcase expected nums) (let ((ans (process nums))) (if (= ans expected) (display (stringappend "process passed test with answer " (number>string expected) "\n")) (display (stringappend "*** ERROR: process got" (number>string ans) "but expected" (number>string expected) "\n"))))) (define (testall) (testcase 15 '(1 2 3 4 5)) (testcase 19 '(1 7 2 9)) (testcase 15 '(1 2 3 4 5 42 6 7)) (testcase 6 '(1 2 3 42 4 5 42 6 7)) (testcase 0 '(42 1 2 3 4 5 6 7)) (testcase 10 '(1 2 3 17 4 5 17 6 7)) (testcase 20 '(1 2 1 4 6 1 7 8 5 9 5 10 11)) (testcase 7 '(1 2 3 1 4 5 6 1 7 8 5 9)) (testcase 35 '(1 2 1 4 42 5 1 6 7)) (testcase 26 '(4 5 0 2 6 7 8 9)) (testcase 14 '(7 2 0 3 6 1 8 5 0 4 9 10)) (testcase 10 '(7 3 0)) (testcase 2 '(7 3 0 4 1 0 8 42 5 1 4 9)) (testcase 499999499097 (range 43 1000000)) (testcase 7999997999097 (range 43 4000000)) (testcase 42 (append (range 43 1000000) '(17) (range 0 1000000) '(17) (range 1 43))) (testcase 903 (append (range 43 1000000) '(17) (range 0 1000000) '(17 42) (range 1 43))) (testcase 581 (append (range 43 1000000) '(17) (range 0 1000000) '(17 0 42) (range 1 50))) )


(20 points) Implement the same
process
function in Python, where it will take a Python list as an argument. The body ofprocess
should include a singlewhile
orfor
loop that performs the iteration performed by the functionsaddmode
,subtractmode
,skipmodestart
andskipmode
in the Racket version. Since a function like Racket’srest
would be prohibitively expensive in Python (taking Θ(n) rather than Θ(1) time for a list of length n), instead use list indexing (or afor
loop) to process the integers in the list from left to right. Your Python function should work like the Racket function, even on large integers:In [16]: process(range(43, 1000000)) Out[16]: 499999499097 In [17]: process(range(43, 4000000)) Out[17]: 7999997999097 In [18]: process(range(43, 1000000) + [17] + range(0,1000000) + [17] + range(1,43)) Out[18]: 42 In [20]: process(range(43, 1000000) + [17] + range(0,1000000) + [17, 42] + range(1,43)) Out[20]: 903 In [21]: process(range(43, 1000000) + [17] + range(0,1000000) + [17, 0, 42] + range(1,50)) Out[21]: 581
Add the following code to your Python file and use
testAll()
to test all the test cases from above.def testCase(expected, nums): ans = process(nums) if expected == ans: print "process passed test with answer", expected else: print "*** ERROR: process got", ans, "but expected", expected def testAll(): testCase(15, [1,2,3,4,5]) testCase(19, [1,7,2,9]) testCase(15, [1,2,3,4,5,42,6,7]) testCase(6, [1,2,3,42,4,5,42,6,7]) testCase(0, [42,1,2,3,4,5,6,7]) testCase(10, [1,2,3,17,4,5,17,6,7]) testCase(20, [1,2,1,4,6,1,7,8,5,9,5,10,11]) testCase(7,[1,2,3,1,4,5,6,1,7,8,5,9]) testCase(35, [1,2,1,4,42,5,1,6,7]) testCase(26, [4,5,0,2,6,7,8,9]) testCase(14, [7,2,0,3,6,1,8,5,0,4,9,10]) testCase(10, [7,3,0]) testCase(2,[7,3,0,4,1,0,8,42,5,1,4,9]) testCase(499999499097, range(43, 1000000)) testCase(7999997999097, range(43, 4000000)) testCase(42, range(43, 1000000) + [17] + range(0,1000000) + [17] + range(1,43)) testCase(903, range(43, 1000000) + [17] + range(0,1000000) + [17, 42] + range(1,43)) testCase(581, range(43, 1000000) + [17] + range(0,1000000) + [17, 0, 42] + range(1,50))