Misc 03

Reminder: Learning to write check-expects is a critical part of the problem solving process. A solution without check-expects cannot receive an A.

  • Using helper functions is good.
  • Add inputs to a function if you want. Just make that the “helper”.

Side note: in this assignment we will tackle 2023 AoC 03.

Computer programmers number positions in a list or string starting from zero. In the example, the letter at index 0 is “A”. The letter at index 22 is “d”.

 0         1         2
 0123456789012345678901234
"A long walk in the woods."

Locations in Strings

Your first goal is to turn the location information into a list, so to represent that the item at index 0 is an “A”, make the list (list 0 "A"). Similarly, index 22 being a “d” is represented by (list 22 "d").

We will start by building a helper function.

  1. (index-info-h) The helper function takes in number, the number to start counting at, and a list of strings.

     ; index-info-h: Number (Listof String)
     ;               -> (Listof (List Number String))
     (define (index-info-h start xs)
       empty)
    
     (check-expect (index-info-h 5 (list "A" "X"))
                   (list (list 5 "A") (list 6 "X")))
    
    1. Write a sequence of two good check-expects showing how the recursion could work.
    2. Write the function index-info-h following the plan of your check expects.
  2. (index-info) Now return to the original problem of recording the indices for each letter in a string. We call this type of list Index-Info later in the problem set. NOTE: You can use a posn instead of a list here (and everywhere else) if you prefer.

     (define (index-info str)
        empty)
    
     (check-expect (index-info "COW")
                   (list (list 0 "C") (list 1 "O") (list 2 "W")))
    
    1. Write down a short English language description of how you are going to make this function work. This is required. Include it as a string in your solution.

    2. Write another check-expect for index-info.

    3. Write the index-info function.

  3. (get-info) Using the output of index-info, return the string at a given index. If the index is not in the list, return the empty string.

     ;; get-info: Index-Info Number -> String
     (define (get-info idx-list num) "")
    
  4. (last-index) Using the output if index-info, return the largest index that is in the list.

     (define (last-index ys) 0)
     (check-expect (last-index (index-info "COW")) 2)
    

Stars and Numbers in the Grid

(Info only; no exercises in this section.)

In the string, star ("*") is used for a marker. We are first going to find all of the stars and then (in the next part) find all of the numbers that are next to stars.

For example, in the string below there are stars at indices 5 and 14. The numbers that are next to stars are 123 and 98.

String: "..123*98..574.*."
Index:   0123456789012345

Find Stars

We will start by making a helper function.

  1. (find-stars-a) Given the already paired up output from index-info, find the indices of the stars.

     ; find-stars-a: Index-Info -> (Listof Number)
     (define (find-stars-a info) empty)
     (check-expect (find-stars-a (list (list 1 "*") (list 5 "A") (list 6 "*")))
                   (list 1 6))
    
    1. Write at sequence of at least two more good check-expects that will help you write this function.

    2. Write the function.

Touching a Star

The function touching-star-right? takes in the Index-Info from index-info and a number (the index to start at), and it returns true if immediately after the number (not just digit) at that index is a star.

Here is an example:

; String: ..87*.12
; Index:  01234567

In the example above, there are two numbers: 87 and 12. The number 87 occupies index 2 and 3, and the number 12 occupies indices 6 and 7. The 87 is touching a star. That means that starting the touching-star-right? function at index 2 or 3 should give true. Starting at any other index (including 4) should give false.

Here are a sequence of checks for the example above.

(define ex1 (index-info "..87*.12"))

(define (touching-star-right? info-list pos) #false)

(check-expect (touching-star-right? ex1 1) #false)
(check-expect (touching-star-right? ex1 2) #true)
(check-expect (touching-star-right? ex1 3) #true)
(check-expect (touching-star-right? ex1 4) #false)
(check-expect (touching-star-right? ex1 5) #false)
(check-expect (touching-star-right? ex1 6) #false)
(check-expect (touching-star-right? ex1 7) #false)
  1. Make a completely different example and write two test cases for touching-star-right? using it - one call that should give #true and one that should give #false.

  2. Write touching-star-right? : Index-Info Number -> Boolean.

  3. Write touching-star?, which gives true if either end of the number has a star at it. (Both ends having stars should also return true.)

Numbers Touching Stars

Finally, given a string we want to make a list of all of the numbers that are touching stars.

In this section you will demonstrate that you understand how to design and test a function. Make sure you write good check-expects that will help create the function and find bugs in it.

It is Ok to struggle in this section. There is less help than in other sections. Write a sequence of check-expects. Do not delete any check-expects that you write.

  1. (find-nums) The find-nums function takes in the Index-Info and puts out a list of starting indices of all of the numbers.

    You should make a helper function.

    Recall from example 1, the numbers are 87 and 12, and they start at indices 2 and 6 respectively.

     (check-expect (find-nums ex1) (list 2 6))
    
  2. (nts) The nts function takes in a string and puts out a list of all of the numbers that are touching stars.

    Expect this function to require a few steps.

     (check-expect (nts "..85*37..203*..50..*")
                   (list 85 37 203))
    

Hints and Simplifications

You might want function to determine whether a single letter is a digit. You probably have one already, but if you do not:

(define (is-digit? s)
  (string<=? "0" s "9"))

You can make “local variables”, which are definitions inside a function. They look like this:

(define (info-end xs k)
  (if (empty? xs)
      k
      (local [(define x (first xs))
              (define rxs (rest xs))
              (define pos (first x))
              (define letter (second x))]
        (cond [(< x pos)  (info-end rxs k)]
              [else       (info-end rxs pos)]))))
Last modified April 26, 2024: Miscellaneous projects. (fd2412a)