# Module 05 Review exercises

# Part 1 - Warm up questions
### Accumulative recursion is covered by slides 1-29, but you should be able
### to attempt this problem if you covered through to slides 19

# Use accumulative recursion to write a Python function 
# count_chars that consumes chars, a list of strings, 
# and returns the total number of characters in chars. 
#
# For example, 
# count_chars([]) => 0
# count_chars(['','','','','']) => 0
# count_chars(['a', 'to', '123', 'cows', 'horse']) => 15

def count_chars(chars):
    pass

## This question can be done using structural or generative recursion. 
## Remember that you don't have to recurse on L[1:] - perhaps you
## might want to recurse on a different slice of the list ...

# Write a function divide, that consumes a list (L) and a positive
# natural number (div) and divides L into lists of len div 
# and puts them into a list, creating a list of lists. 
# For example, 
# divide([1,2,3,4,5,6,7,8], 4) => [[1,2,3,4], [5,6,7,8]]
# divide([1,2,3,4,5,6,7,8], 3) => [[1,2,3], [4,5,6], [7,8]]
# divide([1,2,3,4], 1) => [[1],[2],[3],[4]]

def divide(L, div):
    pass

## For this question, use the given algorithm to solve the problem. 
## (We will see a different implementation of this approach later on.)

# Write a function sorted_copy that consumes a list L of distinct integers, 
# and returns a copy of L which is in sorted order, by using the following technique:
# * find the smallest value in L
# * create a list containing all entries except the smallest, and sort it
# * combine the two pieces to create a copy of L in sorted order. 
#
# You may use abstract list functions and other list functions, except for sort and sorted :-)
# For example, sorted_copy([4,3,5,2,1]) => [1,2,3,4,5]

def sorted_copy(L):
    pass



## This problem is based on slides 1-12 of Module 6

# Write a Python function weird_print, that consumes a natural number, n, 
# and returns a string containing 0,1,2,...,n, with each
# number followed by " ... " all on one line. 
# For example
# weird_print(0) prints "0 ... "
# weird_print(5) prints "0 ... 1 ... 2 ... 3 ... 4 ... 5 ... "
# use a while loop.

def weird_string(n):
    pass

# Part 2 - Extra Practice


# Problem 1: 
# Use accumulative recursion to write the function duplicate_string
# that consumes a string s and a natural number n, and returns the
# new string containing n copies of s. Do not use the * operation.
# For example, duplicate_string("abc", 3) => "abcabcabc"
#
# Problem 2: 
# Use accumulative recursion to write the function count_upper_case 
# that consumes a string and returns the number of 
# uppercase characters in the string.
# For example, count_upper_case("Good Morning!") => 2
#
# Problem 3: 
# Use accumulative recursion to write the function spread
# that consumes a list of numbers, and returns the difference
# between the largest and smallest values in the list.
# For example,  spread([3,1,9,17,-4,2]) => 21, 
# spread([2]) => 0, spread([]) => 0. 
#
# Problem 4: 
# Use accumulative recursion to write a function majority that 
# consumes a list of booleans and determines if there are more
# True than False values in the list. 
# For example, majority([True, False, False]) => False, 
# majority([False, True, False, True]) => False,
# majority([False, True, True, True, True]) => True
#
# Problem 5: 
# Use accumulative recursion to write a function that consumes
# a list of Posns (lists with 2 integers for x and y) and a 
# positive number radius, and returns a 
# list of the posns which are less than radius away from the
# origin.  For example, 
# with([[2,3], [3,4], [1,1]], 5) => [[2,3],[1,1]]
#
# Problem 6:
# Write a function combine_neighbour_strings that consumes a list
# of strings and returns a new list with pairs of adjacent
# strings combined. For example, 
# combine_neighbour_strings(["abc", "123", "def", "456"]) 
#           => ["abc123", "def456"]
# combine_neighbour_strings(["abc", "123", "def", "456", "q"]) 
#           => ["abc123", "def456", "q"]
#
# Problem 7: 
# Write a generative solution is_palindrome that consumes a string
# and returns true if that string is a palindrome when spaces are
# ignored, and false otherwise.
# A palindrome is a string that is the same forwards and
# backwards, for example, "hannah" and "a man a plan a canal panama"
# are palindromes, as are "" and "a". 
# You can use string methods to eliminate the spaces, but try to 
# write a generatively recursive solution instead for practice. 
#
# Problem 8: 
# A string is simple_balanced_bracket if
# it contains no ( and no ) characters, or
# it is of the form (s), where s is bracket-balanced
# For example, "", "abc", "()", "(I was here)", "((a))"
# are all simple-bracket-balanced. However, 
# "(", ")(", "()a", "1(23)" are not.
#
# Problem 9:
# Consider the number guessing game between two players, A and B. 
# Player A thinks of a number between two values low and high, and 
# player B tries to guess it. Player A will provide a hint telling
# B if their guess is to high or too low, which allows B to 
# narrow the range for the secret number. 
# Assume that B is smart, and will always guess halfway between 
# the current range for low and high.
# For example, suppose A chooses 80 as the secret value between
# 0 and 100. B initially guesses 50 = (0+100)/2, and A indicates
# the guess is too low, so B now knows that the secret number is
# in the range [51,100], and will then guess midway between
# 51 and 100 (e.g. round down to 75), and proceed on until 80 
# is identified. 
# Write a function guesses_needed that consumes integers
# secret, low, and high and determines how many guesses B needs 
# to guess the secret number between low and high. 
# Assume that 0<=low<=high.
# How would you modify this to find the list of all the guesses,
# in order in which they would be made?
#
# Problem 10:
# Write a function consecutive-positives which consumes a list 
# of numbers, and returns the length of the longest consecutive
# sublist of positive numbers in the consumed list. 
# For example, consecutive_positives([0, 1, -1, 1, 2, 3, 0, 9]) => 3
# This is perhaps more naturally done accumulatively, but try to 
# find a non-accumulative, non-structural solution to this problem.

# Problem 11:
# Write a function remove_whitespace that consumes a string s
# and returns a new string with all "useless" whitespace removed:
# - no leading whitespace
# - no trailing whitespace
# - only one space between words 
# examples: 
# remove-whitespace ("    bears!! bears!") => "bears!! bears!"
# remove-whitespace ("bears!! bears!          ") => "bears!! bears!"
# remove-whitespace ("bears!!       bears!") => "bears!! bears!"
# remove-whitespace ("         ") => ""
# remove-whitespace ("    bears!!      bears!     ") 
#    => "bears!! bears!"
# Note that the string strip method only removes extra whitespace from
# the beginning and end of a string, not "inside". 
#
# Use the following approach:
# * Write a function remove_beginning_spaces that consumes a string t
#   and returns the same string with all leading spaces removed.
#   (Use any technique for this problem.)
# * Write a function reduce_middle_spaces that consumed a string t
#   and returns the same string with multiple spaces between "words"
#   reduced to a single space. Use remove_beginning_space in your
#   solution to reduce_middle_space. Use an accumulative approach
#   to create the string (the helper should use generative 
#   recursion with remove-beginning-space.
# * Use reduce_middle_spaces and and remove_beginning_spaces to
#   complete the solution. Be sure to pay special care to any
#   remaining trailing spaces.