HELP WITH HASKELL Hercules has a job to do. He has to slay the Hydra. The Hyrdra

Question

HELP WITH HASKELL

Hercules has a job to do. He has to slay the Hydra. The Hyrdra has nine heads. These are not just any heads; they are “level-9” heads. If one of them is cut off, eight level-8 heads grow to replace it. If you chop one of these, seven level-7 heads show up. This continues as you would imagine, until you get to a level-1 head. If you chop that one off, nothing else grows to take its place. The question is this: how many head-choppings does Hercules have to perform to kill the Hydra?1 There are closed-form solutions to this, but this is a lecture about recursion, so use recursion to solve this. We will use a list to represent the hydra’s heads. The initial hydra head count will be represented by [9,0,0,0,0,0,0,0,0]. It shows nine heads of level nine, an no heads of the lower levels. Write a function chop that will take a representation of the Hydra, chop of the highest level head it can get, and return the resulting hydra. Note that chop should run in O(n) time. You can always, always, and forever make helper functions. Unless, of course, we tell you not to. Sample run: ( chop [9,0,0,0,0,0,0,0,0], chop [0,0,2,0,0,0,0,0,0]) yields ([8,8,0,0,0,0,0,0,0], [0,0,1,6,0,0,0,0,0])

Explanation / Answer

We need to figure out how many chops Hercules needs to make in order to kill all heads of the Hydra. The Hydra has 9 heads. When a head is chopped off, it spawns 8 more heads. When one of these 8 heads is cut off, each one spawns out 7 more heads. Chopping one of these spawns 6 more heads, and so on until the weakest head of the hydra will not spawn out any more heads.

The basic instruction need to know before programming:

List Creation: You can create a list / array using the : operator. This can even be done lazily to get an infinite list

Defining Function: Defining a variable, and takes parameters. Define a method that sums all the elements of a list.

More List Foo: Adding lists can be done with ++. ,If a list is empty can be done with null. You can use replicate to create a list with the same elements over and over.

Choose a simple data structure to represent the hydra. Code an array to represent the heads of the Hydra, using thelevel of each head as the value. The initial state of the Hydra (with 9 level 9 heads) can be represented as follows: [9, 9, 9, 9, 9, 9, 9, 9, 9].

Build the chop function. It takes a single argument, and the current levels of the all live heads. It will return the state of the heads after chopping the first one.

The three lines of code below map to these rules:

If there are no heads left, just return[].

We find that there is a level 1 head at the start of our list, just chop it off and return the rest of the array.

We find that there is a higher level head at the start of our list, spawn n - 1 heads in its place.

Chop is pure function; we can safely call it over and over. Build a list where each element is the result of chopping the previous element.

We can use a simple empty check (null) to test if the hydra is still alive and keep items as long as the Hydra is alive.

The patterns are so common, that we can replace the entire thing with a single line.

Finishing up

The sequence of chops needed to kill that Hydra, figuring out the number of chops is just a matter of figuring out how long the sequence is.

Create a function willHerculesDie which takes two parameters, n and the Hydra.If the count is more than n at any point, then we return true, and Hercules dies.

Program based on the above explanation

Import Data.List

Import Data.Array

Import Control.Concurrent

let firstArray = 0:1:[2, 3] // list creation *[0, 1, 2, 3]

let infiniteOnes = 1:infiniteOnes //*[1, 1, 1, 1, 1, ........................]

*never stops, hit ctrl-C to get your interpreter back

Main = do

sumOfElements []     = 0

sumOfElements (x:xs) = x + sumOfElements xs

[1] ++ [3]     //*[1, 3] More List Foo

null []        //* True

null [1]       //*False

replicate 2 3 //*[3, 3]

chop []       = []

chop (1:xs)   = xs

chop (n:xs)   = (replicate (n - 1) (n - 1)) ++ xs

chop [1] //* -- []

chop [4] //* -- [3, 3, 3]

chop [3, 3, 3] //* -- [3, 3, 3]

-- [2, 2, 3, 3]

chop [9,9,9,9,9,9,9,9,9] //* -- [8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9]

repeatedlyChop heads = heads:repeatedlyChop (chop heads)

repeatedlyChop [3] //* -- [[3],[2,2],[1,2],[2],[1], [], [], [] ...]

-- this is an infinite list

repeatedlyChop heads = iterate chop heads

takeWhileAlive (x:xs) = if null x then [] else x:(takeWhileAlive xs)

repeatedlyChopTillDead heads = takeWhileAlive (repeatedlyChopTillDead heads) // Putting together

repeatedlyChopTillDead [4] // * [4],[3,3,3],[2,2,3,3],[1,2,3,3],[2,3,3],[1,3,3],[3,3],[2,2,3],[1,2,3],[2,3],[1,3],[3],[2,2],[1,2],[2],[1]]

repeatedlyChopTillDead heads = takeWhile (not.null) (iterate chop heads)

countOfChops heads = length (repeatedlyChopTillDead heads)

countOfChops [1] //* 1

countOfChops [3] //*5

countOfChops [9,9,9,9,9,9,9,9,9] //*986409 (this takes a while)

willHerculesDie n heads = any (> n) (map length (repeatedlyChopTillDead heads))

willHerculesDie 37 [9,9,9,9,9,9,9,9,9]//* False

willHerculesDie 36 [9,9,9,9,9,9,9,9,9] //* True

We can run the program in ghci, by saving the contents of the into a .hs file, loading up ghci and running :load file.hs.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.