go back Vanya's Website

CS019 from Brown University

modified 20/04/2024 22:53

Intro

I’ve started doing this like 8 months ago, but then got a job and didn’t have the time/motivation to work on this. Today ([2023-10-19 Thu]), I’ve decided to continue working on this, since a lot of the things it teaches are things that I’ve used and have benefited from, as well as prerequisites to more interesting courses that I plan to continue doing (simple data structures, big-oh analysis, well-known cs conepts & so on). I’ll pick up from where I left off – big-oh analysis, specifically the big-oh lab, and the data scripting assignment. I’ll also be writing here as I work through the assignments and readings. Let’s go!

Big-oh notation

TODO Big-O lab

Sortacle

not sure if what i did passes all tests, but it passes all tests i could’ve came up with. however, i think i’m cheating by making is-valid just sort and check? oh, so reading OP’s solution, it seems that he just assumes that the functions will be sorted, and he just checks instead that everything matches.. ok, after reading the paper, it seems that my solution is actually incorect, as it will only work for testing one kind of sorting – ascending, based only on age. instead, the point was to test that ANY sorter function works. i should probably go back and change it…

Tables

Virtual Art Store

First assignment requires making a program that will find and calculate the price of a artwork using two tables. The code itself doesn’t differ a lot accross them, though, since the logic is essentially the same for all of the tasks.

All of the assignments require a “program plan” (they don’t really mention what that means, so I just did some thinking and came up with a pseudo-code implementation of what I’m supposed to do an went from there, researching the table functions that will allow me to filter data, how to access the values of the rows etc.)

https://dcic-world.org/2023-02-21/processing-tables.html#%28part._task-plans%29 Seems like good advice.

1

For this, we don’t need to handle exceptions in any way. This means we’re not supossed to specifically treat cases where the artwork or the currency isn’t in the table isn’t in the table.

  1. Find artwork by id in artwork table
  2. If artwork has same currency as the one we need, return artwork["cost"]
  3. Otherwise, find the currency in the currency table where currency["from-c"] \== artwork["currency"] && currency["to-c"] \== required-currency. Return artwork["cost"] * currency.

Here’s my implementation:

fun get-first(predicate :: (Row -> Boolean), table :: Table) -> Row:
      table.filter(predicate).row-n(0)
where:
      get-first((lam(x): x["foo"] == 1 end), table: foo row: 1 end) is [T.raw-row: {"foo"; 1}]
      # duplicate
      get-first((lam(x): x["foo"] == 1 end), table: foo row: 1 row: 1 end) is [T.raw-row: {"foo"; 1}]
      # not found
      get-first((lam(x): x["foo"] == 2 end), table: foo row: 1 end) raises "row-n-too-large"
end

fun get-art-in-1(art-table :: Table, currency-table :: Table, art_id :: Number, curr :: String) -> Number:
      artwork = get-first((lam(a): a["id"] == art_id end), art-table)
      art-curr = artwork["currency"]
      art-cost = artwork["cost"]
      if art-curr == curr:
              art-cost
      else:
              conv-curr = get-first((lam(c): (c["from-c"] == art-curr) and (c["to-c"] == curr) end), currency-table)
              conv-curr["conv-rate"] * art-cost
end
where:
      # we don't have to worry about these 2 cases:
      # 1. the article isn't in the table
      # get-art-in-1(artt(1, 10, "eur"), curt("usd", "mdl", 18), 2, "eur") is ???
      # 2. the currency isn't in the table
      # get-art-in-1(artt(1, 10, "eur"), curt("usd", "mdl", 18), 1, "usd") is ???
      get-art-in-1(one-art-table, no-curr-table, 1, "usd") is 10
      get-art-in-1(one-art-table, one-curr-table, 1, "mdl") is 10 * 18
end

I defined a generic get-first that will not handle duplicates/missing rows in any way.

2

This is esentially the same as the previous task but we’re supposed to raise an exception if some rows are duplicated or no row is found. The only thing that changes here is the function we use to do the actual lookup – get-first-or-raise.

  1. Find artwork by id in artwork table
    • If not found or duplicated, raise an error
  2. If artwork has same currency as the one we need, return artwork["cost"]
  3. Otherwise, find the currency in the currency table where currency["from-c"] \== artwork["currency"] && currency["to-c"] \== required-currency.

Return artwork["cost"] * currency

fun get-first-or-raise(predicate :: (Row -> Boolean), table :: Table) -> Row:
      matching-rows = table.filter(predicate)
      if matching-rows.length() == 0:
              raise("Row matching predicate not found")
      else if matching-rows.length() > 1:
              raise("Multiple rows matched the predicate")
      else:
              matching-rows.row-n(0)
      end
where:
      get-first-or-raise((lam(x): x["foo"] == 1 end), table: foo row: 1 end) is get-first((lam(x): x["foo"] == 1 end), table: foo row: 1 end)
      get-first-or-raise((lam(x): x["foo"] == 1 end), table: foo end) raises "Row matching predicate not found"
      get-first-or-raise((lam(x): x["foo"] == 1 end), table: foo row: 1 row: 1 end) raises "Multiple rows matched the predicate"
end

fun get-art-in-2(art-table :: Table, currency-table :: Table, art_id :: Number, curr :: String) -> Number:
      artwork = get-first-or-raise((lam(a): a["id"] == art_id end), art-table)
  art-curr = artwork["currency"]
  art-cost = artwork["cost"]
  if art-curr == curr:
    art-cost
  else:
    conv-curr = get-first-or-raise((lam(c): (c["from-c"] == art-curr) and (c["to-c"] == curr) end), currency-table)
    conv-curr["conv-rate"] * art-cost
  end
where:
  get-art-in-2(one-art-table, no-curr-table, 1, "usd") is get-art-in-1(one-art-table, no-curr-table, 1, "usd")
  get-art-in-2(one-art-table, one-curr-table, 1, "mdl") is get-art-in-1(one-art-table, one-curr-table, 1, "mdl")
  get-art-in-2(one-art-table, no-curr-table, 1, "mdl") raises "Row matching predicate not found"
end

I’m yet to find a way to generify this for all 3 cases.

3

This is a bit tricky because we can’t use our previously-defined functions, and can’t generify the structure of the function, because there’s additional logic in the case that the currency is not found the first time.

  1. Find artwork by id in artwork table
    • If not found or duplicated, raise an error
  2. If artwork has same currency as the one we need, return artwork["cost"]
  3. Otherwise, find the currency in the currency table where currency["from-c"] \== artwork["currency"] && currency["to-c"] \== required-currency.
  4. If found: Return artwork["cost"] * currency. If duplicated, raise an error.
  5. If not found: find a currency where (c["to-c"] \== art-curr) and (c["from-c"] \== curr) (reverse of the currency). If not found or duplicated, raise an error. Return (1 / rev-curr["conv-rate"]) * art-cost
fun get-art-in-3(art-table :: Table, currency-table :: Table, art_id :: Number, curr :: String) -> Number:
  artwork = get-first-or-raise((lam(a): a["id"] == art_id end), art-table)
  art-curr = artwork["currency"]
  art-cost = artwork["cost"]
  if art-curr == curr:
    art-cost
  else:
    maybe-curr = currency-table.filter((lam(c): (c["from-c"] == art-curr) and (c["to-c"] == curr) end))
    if maybe-curr.length() > 1:
      raise("Multiple rows matched the predicate")
    else if maybe-curr.length() == 1:
      maybe-curr.row-n(0)["conv-rate"] * art-cost
    else:
      (1 / (get-first-or-raise((lam(c): (c["to-c"] == art-curr) and (c["from-c"] == curr) end), currency-table)["conv-rate"])) * art-cost
  end
end
where:
  get-art-in-3(one-art-table, no-curr-table, 1, "usd") is get-art-in-2(one-art-table, no-curr-table, 1, "usd")
  get-art-in-3(one-art-table, one-curr-table, 1, "mdl") is get-art-in-2(one-art-table, one-curr-table, 1, "mdl")
  get-art-in-3(one-art-table, no-curr-table, 1, "mdl") raises "Row matching predicate not found"
  get-art-in-3(duplicate-art-table, no-curr-table, 1, "mdl") raises "Multiple rows matched the predicate"
  get-art-in-3(one-art-table, duplicate-curr-table, 1, "mdl") raises "Multiple rows matched the predicate"
  get-art-in-3(one-art-table, inverse-of-one-curr-table, 1, "mdl") is (1 / (1 / 18)) * 10
  get-art-in-3(one-art-table, duplicate-inverse-of-one-curr-table, 1, "mdl") raises "Multiple rows matched the predicate"
end

4

We’re not supposed to write any code for this one, only a Testing Plan. This eans we need to think of a list of cases to test, which will guarantee that our solution is correct. Or, as they put in the Sortacle assignment: suppose you were asked to grade a solution while giving partial credit; (…) decompose the problem into a set of sub-problems, so that the combination of these solves the problem as a whole

5

Again, no code required. We need to compare the strengths and weaknesses of representing the currency as a datatype.

Titanic

We’re also required to provide a Program Plan for the assignments.

Program plan

type NameFreq : name :: String, occurences :: Number end. Then sorting and displaying it is easy. We may not even need to know the fact that we’re dealing with a name, and rename NameFreq to something generic, like WordFreq. This way, we can also use it for titles and their frequencies, not only names.

map freq.name for every freq in rsort-freq(find-freq(set(filter(get-name if sex is male))))

We’ll have the same thing for females.

map freq.name for every freq in rsort-freq(find-freq(set(filter(get-name if sex is female))))

And for titles we’ll just do find-freq(set(get-title for every person)))

Sets

How to represent sets as lists: