Chapter 4 Discussion V

Scrabble

In the game of Scrabble you try to fit a word into spaces with some letters already in place. In this question you will write a function to determine if a word fits into a certain space.

    wordFits :: String -> String -> Bool
    wordFits "jerk" "_or_" == False
    wordFits "work" "__r_" == True

Along the way you may want to use a helper function to determine if characters from the same place match.

    letterFits :: Char -> Char -> Bool
    letterFits 'j' '_' == True
    letterFits 'e' 'o' == False

Assume that the strings given to wordFits are the same length.

Game of 24

In the game of 24 you are supposed to find a way to combine four whole numbers using addition, subtraction, multiplication, and division, in order to get 24 as the final answer.

1. pairPossible produces all of the numbers that you can get from a single pair of numbers. Only consider the results of division when the answer is an integer.

      pairPossible 3 12 == [-9,9,15,36,4]
      pairPossible 3 4 == [-1,1,7,12]
      pairPossible 49 2 == [-47,47,51,98]
   

   Danger: 49/2 is not 24, so pairPossible 49 2 should not include 24 in the list! (Trouble? See the notes below.)

2. allPairs produces a list of all of the possible two number pairs given a list of four numbers.

      allPairs :: [Int] -> [(Int,Int)]
      allPairs [1,2,3] == [(1,2),(1,3),(2,3)]
      allPairs [1,2,3,4] == [(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]
   

3. allPossible1 produces a list of all numbers that can be produced by using any pair of numbers from the list. Duplicates are ok.

4. Finish the 24-solver. Given a list of 4 numbers, return True if is is possible to make 24 (somehow).

   Examples: $(49 - 1) / (5 - 3)$ and $((15 / 3)+1)*4$ are both 24… your method should have the ability to detect both of these possibilities.

      check_solve24 = [ solve24 [1,3,5,49] == True,
                        solve24 [1,3,4,15] == True,
                        solve24 [2,11,17,31] == False]
   

   Note: Working with fractions is optionl because it is more complex. Thanks to Sara J for pointing out that this means we will make mistakes in some circumstances, including the example [1,5,5,5].

   NOTE: There are two different groupings that could lead to 24: (((ab)c)d) and ((ab)(cd)).

   Advice: begin by considering the (((ab)c)d) case - the final result is built up by doing a single operation at a time on the previous result.

   You can use your allPairs function but as you build all of the possibilities for four numbers. (See the walkthrough suggestions if posted.)

Advanced

• Make choose k nums that gives all k item subsets of nums. For example, when k is 3 and nums is [1,2,3,4,5], the result should be

    choose 3 [1..5] == [[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],
                        [1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]]
  

Notes

Many people have problems determining when a fraction is an integer. A good way to solve this problem is to determine if division will produce a fraction before you do the division. Use the integer division (quotient) and remainder functions.

The bad way to do this is:

isInt :: Float -> Bool
isInt x =
   x == round x

Oops, that does not work because round produces an Integral output. Free that up with fromIntegral:

isInt x =
   x == fromIntegral (round x)

Edits 2022

The output from a “24-solver” is actually just a “24-tester”: it gives True or False, depending on whether you can make 24 with the given numbers. If you study more advanced Haskell, there is a straightforward way to convert our tester into something that actually gives a solution. (Read about the Writer monad if you want, maybe in a tutorial.

Overview

A strategy to write a “24-solver” is:

1. Produce a list of all possible permutations of [0,1,2,3], corresponding to an ordering of the four given numbers. For example, [3,2,1,0] and [3,0,1,2] should both appear in this list.
2. Try all of the arithmetic operations combining the items in order. The first step working with [a,b,c,d] would be to combine a and b using every possible arithmetic operation. Then similarly combine that result with c, etc. This step should produce a list of all of the possible outcomes from combining the numbers.
3. See the note above about (ab)(cd).
4. The result is True if 24 is in the list of all possibilities.

Details for Problem Solving Class

(This is a good discussion topic for an entire class period. Without a discussion it can be difficult to follow.)

The key step in this method is to generate a list of all possible permutations. We will call the function that creates this allOrder.

allOrder :: [Int] -> [Int]

Write out examples, beginning with an input of [a], then [a,b] and [a,b,c]. As you write the examples, look for a pattern you can use repeatedly. Discuss with classmates. Don’t quit until you have written out the results from allOrder [a,b,c,d].

I won’t write out the details here. They should come out of class discussion.

Side Projects

When the starting list is [100,250,600,900], then we use 0 to represent 100 (item 0 in the list), 1 to represent 250 (item 1 in the list), etc.

The subin function takes the original list of numbers (of length n) and a list with the representing numbers [0..n-1] in some order. It outputs the original numbers reordered to match the order given by the representing numbers.

subin :: [Int] -> [Int] -> [Int]
subin original representing = [0]
subin_checks = [
  subin [100,250,600,900] [2,0,3,1] == [600,100,900,250]
  ,subin [1000,800,600,500,400] [3,4,2,0,1] == [500,400,600,1000,800]
  ]

Postscript

The desperate approach would be to just type the list of all possible permutations of four elements, but that’s not educational.