Next To Last Item In A List
July 28, 2015
Today’s exercise is a reminder about the importance of writing good test code. We have two tasks. The first is to extract the next-to-last item from a linked list; for instance, given the list (1 2 3 4 5) the next-to-last item is 4. The second task is to extract the nth-from-last item from a linked last; for instance, given the same list, the second-from-last item is 4. In addition to writing the two functions, you should write test code that exercises the functions thoroughly.
Your task is to write the two functions and test code. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
In Python. I assumed that n cannot exceed the length of the list. I did use a list for the linked list, but did not use len and slicing.
For testing I use the hopthesis library.
from hypothesis import given, Settings, Verbosity import hypothesis.strategies as st from itertools import tee, islice def slidingwindow(iterable, n=2): """example: [1,2,3,4,5],3) -> (1,2,3), (2,3,4), (3,4,5)""" its = tee(iter(iterable), n) for i, it in enumerate(its): next(islice(it, i, i), None) return zip(*its) def bf(seq, n): """for testing assumption is that n cannot exceed the length of the sequence """ if len(seq) < n: return None return seq[-n] # use list as linked list - you cannot use seq[-2] and len def next_to_last_n(seq, n): a = None # slidingwindow(s,2) returns (s1,s2), (s2,s3), ....., (s_n-1, s_n) for a, *b in slidingwindow(seq, n): pass return a def next_to_last(seq): return next_to_last_n(seq, 2) # generate random lists of integers with random lengths, and generate a random n @given(st.lists(st.integers(), average_size=20), st.integers(min_value=1, max_value=20), settings=Settings(verbosity=Verbosity.normal)) def test_next_to_last_n(seq, n): exp = bf(seq, n) act = next_to_last_n(seq, n) assert act == exp, "{} {} {}".format(act, exp, seq[-4:]) @given(st.lists(st.integers())) def test_next_to_last(seq): exp = bf(seq, 2) act = next_to_last(seq) assert act == exp, "{} {} {}".format(act, exp, seq[-4:]) if __name__ == "__main__": test_next_to_last() test_next_to_last_n() print("OK")In Python. A simpler version.
from collections import deque def next_to_last_n(seq, n): d = deque(seq, n) # d contains the last n values of seq return d[0] if len(d) == n else NoneWith Lisp-style lists in Python, and a verbose option in the test function for checking that no news is any news at all.
Backwards indexing has always been tricky for me, including this time. Oh, and I let Python raise an exception when the list is too short, and then I test for that.
from functools import reduce def nest(flat): return reduce((lambda rest, elt: (elt, rest)), reversed(flat), ()) def tail(nested, n = 1): '''Tail starting at index n.''' for k in range(n): _, nested = nested return nested def nthtolast(nested, n = 0): '''Head of the tail of length n + 2.''' slow, fast = nested, tail(nested, n + 2) while fast: _, slow = slow _, fast = fast elt, _ = slow return elt def test(n, verbose = False): for data in ('abcdef'[:e] for e in range(7)): if n + 1 < len(data): x = nthtolast(nest(data), n) assert x == data[-2-n] ( verbose and print('nthtolast(({}), n = {}) => {}' .format(' '.join(data), n, x)) ) else: try: nthtolast(nest(data), n) assert False except ValueError: ( verbose and print('nthtolast(({}), n = {}) => ValueError' .format(' '.join(data), n)) ) test(0) test(1) test(2)A solution in (Racket) Scheme.
nfl0 is the inefficient but clear functional specification, nfl is the implementation (using the double pointer approach). Both assume n is non-negative.
Test just compares the two functions over a suitable set of inputs.
nfl0 n s | n >= length s = Nothing | otherwise = Just (s !! (length s - n - 1)) f 0 s t = g s t f n s (_:t) = f (n-1) s t f _ _ _ = Nothing g (a:_) [] = Just a g (_:s) (_:t) = g s t nfl n s = f (n+1) s s test0 m n = nfl n [1..m] == nfl0 n [1..m] test1 m = all (test0 m) [0..m+1] test = all test1 [0..5] main = print testfun next_to_last_item [] = ~1 (* return -1 on error *) | next_to_last_item (x::y::nil) = x | next_to_last_item (x::xs) = next_to_last_item xs val test_valid_list = (next_to_last_item [1, 2, 3, 4, 5]) = 4 val test_empty_list = (next_to_last_item []) = ~1 val test_single_elem_list = (next_to_last_item [1]) = ~1 fun nth_from_last_item n [] = ~1 | nth_from_last_item n lst = let val len = List.length lst fun loop counter [] = ~1 (* counter goes past end of list *) | loop counter (x::xs) = if len - counter = n then x else loop (counter + 1) xs in loop 0 lst end val test_1st_from_last = (nth_from_last_item 1 [1, 2, 3, 4, 5]) = 5 val test_2nd_from_last = (nth_from_last_item 2 [1, 2, 3, 4, 5]) = 4 (* rewriting next_to_last_item using nth_from_last_item *) fun next_to_last_item2 xs = nth_from_last_item 2 xs; val test_valid_list2 = (next_to_last_item2 [1, 2, 3, 4, 5]) = 4 val test_empty_list2 = (next_to_last_item2 []) = ~1 val test_single_elem_list2 = (next_to_last_item2 [1]) = ~1 val all_test_pass = List.all (fn x => x) [test_valid_list, test_empty_list, test_single_elem_list, test_1st_from_last, test_2nd_from_last, test_valid_list2, test_empty_list2, test_single_elem_list2];