Lab 10: Recursive Reporters

Due at: Tuesday, March 3rd, 23:59

Lab 10: Recursive Reporters

Instructions

This worksheet serves as a guide and set of instructions to complete the lab.

  • You must use the starter file, found here to get credit for the lab.
  • Additionally, here is the workbook that you can read through for further context and additional (non-required) material. All material was sourced from the CS10 version of The Beauty and Joy of Computing course.

Submitting

You will need to fill in the blocks under the starter file and submit this to Gradescope.

  • To receive full credit for the coding portion, you will need to complete the required blocks, and the required blocks must pass all tests from the autograder in Gradescope.
  • For instructions on how to submit to labs to Gradescope, please see this page.

Please note: you must use the starter file above, and you must NOT edit the name of any of the required blocks. Failing to do either will result in autograder failure.

Objectives

Recursion is arguably the second most important topic in this course (after abstraction of course). In today’s lab you will implement what you know about recursion into reporter blocks. By the end of the lab, you will:

  • Understand how reporters use combiners instead of sequences.
  • Practice planning and coding recursive reporters.
  • Implement higher order functions in non iterative solutions

Required Blocks:

It is highly recommended that you work with a partner for this assignment

  • Block 1: ends-e (input)
  • Block 2: numbers (input)
  • Block 3: count parking spots(n)

Important Topics mentioned in the Workbook

For better understanding of the lab we highly recommend going through these workbook pages! Topics that are important but not required for this lab will be indicated with an asterisk**. These topics are best reviewed in order and as you complete the lab.

Block 1: ends-e(input)

  • Objective:
    • Edit a reporter block, ends-e, that takes a list of words as input, and reports a list of those words from the input whose last letter is e
  • Note
    • You must use recursion, no HOFs or iteration
  • Inputs:
    • Input = anything
      • Input should be a list of words
  • Output:
    • Reports: a list
      • A list if all the words from the list that ends with e
      • If there are no words that end with e, the reporter reports an empty list
  • Examples:
    • example call to ends e with a 5 word list
    • example call to ends e an empty list
    • example call to ends e with a different 5 word list

Block 2: numbers (input)

  • Objective:
    • Edit a reporter block, numbers, that takes a list of mixed words and numbers as input, and reports a list of just the numbers from the input list.
  • Notes:
    • You must use recursion, no HOFs or iteration
  • Input = anything
    • Input should be a list of words, strings, and numbers
  • Output:
    • Reports: a list
      • A list if all the items in the list that are numbers
      • If there are no numbers in the list, the reporter reports an empty list
  • Examples:
    • example call to numbers with a 4 element list containing two numbers
    • example call to numbers with a list containing an element with the division operator
    • example call to numbers with a list containing an ellipse

Block 3: count parking spots (n)

  • Objective:
    • A straight parking lot has “n” contiguous spots in a single row. You have an unlimited supply of three vehicle types:
      • Scooter: occupies 1 spot
      • Car: occupies 2 spots
      • Van: occupies 3 spots
    • Vehicles must exactly fill the lot (no gaps and no overhang). Two parking spots are considered different if any spot in the row is covered by a different vehicle (i.e., order and placement matter).
    • Write a function count parking spots(n) that returns the number of distinct parking spots that exactly fill a lot of length n using scooters, cars, and vans.
  • Notes:
    • You must use recursion, no HOFs or iteration
    • Hints:
      • Think “first choice, rest of the problem.”
      • From the leftmost open spot, branch on placing:
        • a scooter (uses 1 spot),
        • a car (uses 2 spots),
        • a van (uses 3 spots)
        • Each choice reduces the remaining available parking spots to n−1, n−2, or n−3.
        • Base cases: if n == 0, that’s one valid way; if n < 0, that branch is impossible.
  • Inputs
    • N = number of available parking spots
  • Output:
    • Reports: Number
      • The number of combinations of vehicles we can use to park in the available spots
  • Examples:
    • count parking spots(0) → 1 (the empty layout)
    • count parking spots(2) → 2 because the valid parking combinations are:
      • Scooter, Scooter
      • Car
    • count parking spots(3) → 4 because the parking combinations are:
      • Scooter, Scooter, Scooter
      • Scooter, Car
      • Car, Scooter
      • Van

You can always check the validity of your solutions by using the local autograder. Remember to submit on Gradescope!

Submission

You may submit more than once before the deadline; only the final submission will be graded. It is your responsibility to check that the autograder on Gradescope runs as expected after you upload your submission.