CSE 341, Fall 2011, Assignment 2Due: Monday October 17, 11:00PMYou will write 11 SML functions (not counting local helper functions), 4 having to do with “name substitu-tions” and 7 having to do with a made-up solitaire card game.Your solutions must use pattern-matching. You may not use the functions null, hd, or tl, nor may you useanything containing a # character or features not used in class (such as mutation).The sample solution is roughly 130 lines, including all the code provided to you.Download hw2provided.sml from the course website. The provided code defines several types for you. Youwill not need to add any additional datatype bindings or type synonyms.Do not miss the “Important Caveat” after the “Type Summary.”1. This problem involves using first-name substitutions to come up with alternate names. For example,Fredrick William Flintstone could also be Fred William Flintstone or Freddie William Flintstone. Only part(d) is specifically about this, but the other problems are helpful.(a) Write a function all_except_option, which takes a string and a string list. Return NONE if thestring is not in the list, else return SOME lst where lst is like the argument list except the string is notin it. You may assume the string is in the list at most once. Use same_string, provided to you, tocompare strings. Sample solution is 8 lines.(b) Write a function get_substitutions1, which takes a string list list (a list of list of strings, thesubstitutions) and a string s and returns a string list. The result has all the strings that are insome list in substitutions that also has s, but s itself should not be in the result. Example:get_substitutions1([["Fred","Fredrick"],["Elizabeth","Betty"],["Freddie","Fred","F"]],"Fred")(* answer: ["Fredrick","Freddie","F"] *)Assume each list in substitutions has no repeats. The result will have repeats if s and another string areboth in more than one list in substitutions. Example:get_substitutions1([["Fred","Fredrick"],["Jeff","Jeffrey"],["Geoff","Jeff","Jeffrey"]],"Jeff")(* answer: ["Jeffrey","Geoff","Jeffrey"] *)Use part (a) and ML’s list-append (@) but no other helper functions. Sample solution is 6 lines.(c) Write a function get_substitutions2, which is like get_substitutions1 except it uses a tail-recursivelocal helper function.(d) Write a function similar_names, which takes a string list list of substitutions (as in parts (b) and(c)) and a full name of type {first:string,middle:string,last:string} and returns a list of fullnames (of type {first:string,middle:string,last:string} list). The result is all the full namesyou can produce by substituting for the first name (and only the first name) using substitutions andparts (b) or (c). The answer should always begin with the original name (then have 0 or more othernames). Example:similar_names([["Fred","Fredrick"],["Elizabeth","Betty"],["Freddie","Fred","F"]],{first="Fred", middle="W", last="Flintstone"})(* answer: [{first="Fred", last="Flintstone", middle="W"},{first="Fredrick", last="Flintstone", middle="W"},{first="Freddie", last="Flintstone", middle="W"},{first="F", last="Flintstone", middle="W"}] *)Hint: Use a local helper function. Sample solution is 9 lines.12. This problem involves a solitaire card game invented just for this question. You will write a program thattracks the progress of a game; writing a game player is a challenge problem. You can do parts (a)–(e) beforeunderstanding the game if you wish.A game is played with a card-list and a goal. The player has a list of held-cards, initially empty. The playermakes a move by either drawing, which means removing the first card in the card-list from the card-list andadding it to the held-cards, or discarding, which means choosing one of the held-cards to remove. The gameends either when the player chooses to make no more moves or when the sum of the values of the held-cardsis greater than the goal.The objective is to end the game with a low score (0 is best). Scoring works as follows: Let sum be the sumof the values of the held-cards. If sum is greater than goal, the preliminary score is three times sum − goal,else the preliminary score is goal − sum. The score is the preliminary score unless all the held-cards are thesame color, in which case the score is the preliminary score divided by 2 (and rounded down as usual withinteger division; use ML’s div operator).(a) Write a function card_color, which takes a card and returns its color (spades and clubs are black,diamonds and hearts are red). Note: One case-expression is enough.(b) Write a function card_value, which takes a card and returns its value (numbered cards have theirnumber as the value, aces are 11, everything else is 10). Note: One case-expression is enough.(c) Write a function remove_card, which takes a list of cards lst, a card c, and an exception e. It returnsa list that has all the elements of lst except c. If c is in the list more than once, remove only the firstone. If c is not in the list, raise the exception e. You can compare cards with =.(d) Write a function all_same_color, which takes a list of cards and returns true if all the cards in the listare the same color. Hint: An elegant solution is very similar to one of the functions we looked at in thelecture on deep pattern-matching.(e) Write a function sum_cards, which takes a list of cards and returns the sum of their values. Use a locallydefined helper function that is tail recursive.(f) Write a function score, which takes a card list (the held-cards) and an int (the goal) and computesthe score as described above.(g) Write a function officiate, which “runs a game.” It takes a card list (the card-list) a move list(what the player “does” at each point), and an int (the goal) and returns the score at the end of thegame after processing (some or all of) the moves in the move list in order. Use a locally defined recursivehelper function that takes several arguments that together represent the current state of the game. Asdescribed above:• The game starts with the held-cards being the empty list.• The game ends if there are no more moves. (The player chose to stop since the move list is empty.)• If the player discards some card c, play continues (i.e., make a recursive call) with the held-cardsnot having c and the card-list unchanged. If c is not in the held-cards, raise the IllegalMoveexception.• If the player draws and the card-list is empty, the game is over. Else if drawing causes the
View Full Document
Unlocking...