Data Scripting 1

For this homework, you are expected to do the work entirely on your own (without help from the course staff, whom you may only consult for help with names of library functions or other essential information of that sort).

Note that some of the problems use special values like 0 or -999 to delimit content. In general, you should not do this in your own programs: use properly structured data rather than embedding the shape in the data. However, sometimes you will confront real-world data sources that do this, and you may not have the freedom to change them. These problems give you a feel for working in such settings. There are two sets of three problems each. The first set [Programming Problems] requires you to write fresh programs. The second set [Review Problems] gives you solutions to problems and asks you to identify which ones you prefer and why.

1 Programming Problems

1.1 Palindrome Detection Modulo Spaces and Capitalization

A palindrome is a string with the same letters in each of forward and reverse order (ignoring capitalization). Design a program called is-palindrome that consumes a string and produces a boolean indicating whether the string with all spaces and punctuation removed is a palindrome. Treat all non-alphanumeric characters (i.e., ones that are not digits or letters) as punctuation.

1.2 Sum Over Table

Assume that we represent tables of numbers as lists of rows, where each row is itself a list of numbers. The rows may have different lengths. Design a program sum-largest that consumes a table of numbers and produces the sum of the largest item from each row. Assume that no row is empty.

1.3 Adding Machine

Design a program called adding-machine that consumes a list of numbers and produces a list of the sums of each non-empty sublist separated by zeros. Ignore input elements that occur after the first occurrence of two consecutive zeros.

2 Review Problems

Below you are given problem statements followed by multiple solutions to each problem. Assume that the solutions are correct; ignore any small deviations in behavior. Also assume that any missing helper functions are defined in the obvious way. Finally, ignore stylistic differences in naming. Instead, focus on the structure of the solutions.

Use this form to provide your answers. For each problem, rank the solutions in order (from most to least) of your preference. You are allowed to have ties. Below the ranking grid, explain why you picked that ordering, mentioning briefly all solutions in your response.

The solutions are labeled A, B, etc. Indicate your ordering by selecting the appropriate radio button for each solution. For instance, selecting “1st” for B, “2nd” for A and C, and “3rd” for D means you liked B the most, followed by A and C (tied), followed by D.

Remember to explain your choice!

2.1 Rainfall

Design a program called rainfall that consumes a list of real numbers representing daily rainfall readings. The list may contain the number -999 indicating the end of the data of interest. Produce the average of the non-negative values in the list up to the first -999 (if it shows up). There may be negative numbers other than -999 in the list (representing faulty readings). Assume that there is at least one non-negative number before -999.

Solution A:

fun rainfall(l :: List<Number>) -> Number:

fun helper(rds :: List<Number>, total :: Number, days :: Number) -> Number:

cases (List) rds:

| empty => total / days

| link(f, r) =>

ask:

| f == -999 then: total / days

| f < 0 then: helper(r, total, days)

| otherwise: helper(r, total + f, days + 1)

end

end

end

helper(l, 0, 0)

end

Solution B:

fun rainfall(l :: List<Number>) -> Number:

fun sum-rfs(shadow l :: List<Number>) -> Number:

cases (List) l:

| empty => 0

| link(f, r) =>

ask:

| f == -999 then: 0

| f < 0 then: sum-rfs(r)

| otherwise: f + sum-rfs(r)

end

end

end

fun count-days(shadow l :: List<Number>) -> Number:

cases (List) l:

| empty => 0

| link(f, r) =>

ask:

| f == -999 then: 0

| f < 0 then: count-days(r)

| otherwise: 1 + count-days(r)

end

end

end

total = sum-rfs(l)

days = count-days(l)

total / days

end

Solution C:

fun rainfall(l :: List<Number>) -> Number:

fun cleanse(shadow l :: List<Number>) -> List<Number>:

cases (List) l:

| empty => empty

| link(f, r) =>

ask:

| f == -999 then: empty

| f < 0 then: cleanse(r)

| otherwise:

link(f, cleanse(r))

end

end

end

actual = cleanse(l)

total = sum-of(actual)

days = actual.length()

total / days

end

2.2 Length of Triples

Solution A:

fun max-triple-length(l :: List<String>) -> Number:

fun break-into-triples(shadow l :: List<String>) -> List<Triple>:

link(triple(l.first, l.rest.first, l.rest.rest.first),

ask:

| is-empty(l.rest.rest.rest) then: empty

| otherwise: break-into-triples(l.rest)

end)

end

triple-lengths = map(lam(t): string-length(t.a) + string-length(t.b) + string-length(t.c) end,

break-into-triples(l))

max-of(triple-lengths)

end

Solution B:

fun max-triple-length(l :: List<String>) -> Number:

fun break-into-triples(shadow l :: List<Number>) -> List<Triple>:

link(triple(l.first, l.rest.first, l.rest.rest.first),

ask:

| is-empty(l.rest.rest.rest) then: empty

| otherwise: break-into-triples(l.rest)

end)

end

triples-as-nums = map(string-length, l)

triple-lengths = map(lam(t): t.a + t.b + t.c end,

break-into-triples(triples-as-nums))

max-of(triple-lengths)

end

Solution C:

fun max-triple-length(l :: List<String>) -> Number:

shadow l = map(string-length, l)

fun helper(shadow l :: List<Number>, max-so-far :: Number, prev-2 :: Number, prev-1 :: Number) -> Number:

cases (List) l:

| empty => max-so-far

| link(f, r) =>

prev-3 = prev-2 + f

helper(r,

if prev-3 > max-so-far: prev-3 else: max-so-far end,

prev-1 + f,

f)

end

end

helper(l.rest.rest.rest,

l.first + l.rest.first + l.rest.rest.first,

l.rest.first + l.rest.rest.first,

l.rest.rest.first)

end

2.3 Shopping Discount

Solution A:

fun checkout(cart :: Cart) -> Number:

shoes = filter(lam(c): c.name == "shoes" end, cart)

shoe-cost = sum-of(map(lam(c): c.cost end, shoes))

shoe-discount = if shoe-cost >= 100: shoe-cost * 0.20 else: 0 end

hats = filter(lam(c): c.name == "hat" end, cart)

hat-count = hats.length()

hat-discount = if hat-count >= 2: 10 else: 0 end

init-cost = sum-of(map(lam(c): c.cost end, cart))

init-cost - shoe-discount - hat-discount

end

Solution B:

fun checkout(cart :: Cart) -> Number:

fun helper(ct :: Cart, total :: Number, shoe-cost :: Number, hat-count :: Number) -> Number:

cases (List) ct:

| empty =>

shoe-discount = if shoe-cost >= 100: shoe-cost * 0.20 else: 0 end

hat-discount = if hat-count >= 2: 10 else: 0 end

total - shoe-discount - hat-discount

| link(f, r) =>

new-total = total + f.cost

ask:

| f.name == "shoes" then:

helper(r, new-total, shoe-cost + f.cost, hat-count)

| f.name == "hat" then:

helper(r, new-total, shoe-cost, hat-count + 1)

| otherwise:

helper(r, new-total, shoe-cost, hat-count)

end

end

end

helper(cart, 0, 0, 0)

end

3 Submission Guidelines

For the programming tasks, please create three files in code.pyret.org, one per problem. Name them palindrome.arr, sum.arr, and adding.arr. Please put the text provide * at the top of each file, like in previous stencils. After you finish writing your programs, submit using this link. For the ranking tasks, respond using the linked Web form.