[SOLVED] algorithm Haskell parallel COMP 3120 Fall 2019 Assignment 1

COMP 3120 Fall 2019 Assignment 1
Develop a Pasturez solver in Haskell.
The Pasturez problem:
You are a farmer. You want to divide your farmland into fenced areas, each with its own water source. You have just enough water to support all of your needs, so this isnt easy.
Your farm is represented as a grid of numbers:
0: a section without its own water source.
1+: a section with a water source. The number denotes how many sections this source can supply.
For example, if this is your farm:
0
2
0
0
0
3
0
4
0
Then you could fence the farm like this:
0
2
0
0
0
3
0
4
0
In Haskell, this would correspond to this function call:
> pasturez [ [0,2,0], [0,0,3] , [0,4,0] ]
[ aab, ccb, ccb ]
Each letter in the output refers to a different fenced area, e.g. a in the example is the orange area in the picture.

Here are the FOUR MAIN REQUIREMENTS for dividing up your farm into fenced areas:
1. Every individual grid section must be included as a part of a fenced area.
2. Each fenced area can have only one water source
3. The size of a water source must exactly match the size of its fenced area.
4. Fenced areas must be connected.
Main requirement (15 marks):
Implement a Haskell program that can generate a solution that fulfills the 4 requirements in a reasonable time, e.g. a 44 grid in less than one minute.
Only implementing part of this is worth partial marks. Requirement #4 is probably the most difficult to implement, but that can vary depending on how you approach the problem.
Additional Functionality (2 marks each, maximum total grade: 20):
Completing the main requirement will achieve a passing grade. For a higher mark, complete some or all of the following:
1. Display the input and output as a grid (not a list).
2. Make your program computationally efficient, i.e., improve its speed, particularly for difficult puzzles. Being able
to compute a solution for a 55 grid in under a minute is worth 1 mark, a 66 grid is worth 2 marks.
3. Only allow square or rectangular fenced areas in a solution.
4. Implement the program to compute the solution (at least partially) in parallel.
Note that some of these are options can be challenging and/or time-consuming to implement. Do not feel like you need to complete any or all of them. If there is something else youd like to try and get credit for as additional functionality, let me know in advance, and we can see if it qualifies.
YOU MUST have a comment in your code that lists which of the 4 main requirements you can fulfill, as well as any of the bonuses you have implemented.
Coding Style
Clarity matters. Appropriate function names, function types/signatures, and comments (where necessary) are all expected. Marks will be reduced if the code is hard to understand.
Integrity
If you include any code from any source other than yourself, you must cite the source. Usually a weblink is sufficient. Do not overdo this, but it is okay to use a small amount of code that helps you solve a specific problem. It is definitely better to learn from outside code and write it on your own, however. Any other form of copying will be dealt with formally.

Hints
As with anything, start small. Try out your program on a 2 2 grid and work upwards. Even a 5 5 grid takes a long time for a naive algorithm.
Keep your functions simple. A long statement that maps and filters and includes lots of function composition is very difficult to debug. Try not to do too many things in one function.
Test driven development is great with Haskell. For any function, think of tests to ensure it does what you expect. Those tests do not have to be related to the main problem. Just make sure that new bit of code is working properly on its own.
You only need to return 1 legal solution! (Not all of them)
How many ways can you fence an area that includes a water source of value 1?
Sample Puzzles for Testing
> pasturez [ [0,2] , [0,2] ]
[ aa, bb ]
> pasturez [ [ 0, 2, 0, 0 ], [ 0, 0, 3, 0 ], [ 0, 4, 0, 0 ], [ 0, 0, 0, 7 ] ] [ bddc, bbcc, abaa, aaaa ]
> pasturez [ [0,2,0,0,0], [0,0,3,0,0], [0,4,0,0,0], [0,0,0,7,0], [9,0,0,0,0] ] [ ceeda, ccdda, bcbba, bbbba, aaaaa]