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.
-
(
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")))
- Write a sequence of two good check-expects showing how the recursion could work.
- Write the function
index-info-h
following the plan of your check expects.
-
(
index-info
) Now return to the original problem of recording the indices for each letter in a string. We call this type of listIndex-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")))
-
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.
-
Write another check-expect for
index-info
. -
Write the
index-info
function.
-
-
(
get-info
) Using the output ofindex-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) "")
-
(
last-index
) Using the output ifindex-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.
-
(
find-stars-a
) Given the already paired up output fromindex-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))
-
Write at sequence of at least two more good check-expects that will help you write this function.
-
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)
-
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
. -
Write
touching-star-right? : Index-Info Number -> Boolean
. -
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.
-
(
find-nums
) Thefind-nums
function takes in theIndex-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))
-
(
nts
) Thents
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)]))))