tag:blogger.com,1999:blog-6272748843257835470Sat, 29 Feb 2020 07:40:25 +0000pythonfsharpgoogleaimathprogrammingjavascriptlispA Mingled Cuphttp://mingledcup.dkjones.org/search/label/fsharpnoreply@blogger.com (Dave)Blogger6125tag:blogger.com,1999:blog-6272748843257835470.post-54685993395151840Thu, 14 Jul 2011 02:36:00 +00002011-07-14T06:43:20.152-04:00fsharpDFS for puzzle solving<p>I looked back at the <a href="http://mingledcup.dkjones.org/2010/09/one-to-nine-puzzle.html">one to nine puzzle</a>, and realized that we can
write a function to hold the main idea, and apply it to other puzzles.
</p>
<p>
The main idea is to solve the puzzle one step at a time. At each
step, we try every possible move, but only the moves that are still
valid. We return any solutions we find.
</p>
<p>
In the previous post, the searching was mixed with the puzzle specific
code. Here is a function that handles the recursion for us, and lets
us pass in problem-specific code for the details.
</p>
<pre class="example">let solve next_f done_f initial =
let rec search state =
seq {
if done_f state then
yield state
else
for state' in next_f state do
yield! search state'
}
search initial
</pre>
<p>
This function returns a sequence of answers. Some puzzles have one
solution, others have many. With sequences, the function caller has
more control over how many values are returned.
</p>
<p>
<code>done_f</code> has the type <code>('position -> bool)</code> and is the stopping
criteria. Our move generator <code>next_f</code> has the type <code>('position -> seq<'position>)</code>. <code>solve</code> is a higher order function because it takes
other functions as inputs.
</p>
<p>
Now, we can solve the one to nine puzzle with this function.
</p>
<pre class="example">let one_to_nine () =
let next_move (number, digits, idx) =
let idx' = idx + 1
seq {
for d in digits do
let number' = number * 10 + d
if number' % idx' = 0 then
yield number', Set.remove d digits, idx'
}
let finished (_, _, idx) = idx = 9
solve next_move finished (0, Set.ofList [1..9], 0)
|> Seq.head
|> fun (number, digits, idx) -> number
</pre>
<p>
<a href="http://fssnip.net/6m">see the code at fssnip.net</a>
</p>
<p>
A position is three things: the current number, the available digits,
and the index of the digit we are considering. If we make it to nine
digits, then we are done. Given a current state, we generate the next
state by trying each digit that remains. We test each of these to
make sure they follow the divisibility rule (two digit number must be
divisible by two, three by three, etc.) Then we create a new state to
hold the information.
</p>
<p>
We pass those two functions to <code>solve</code> along with the initial state,
and it finds our solution.
</p>
<p>
<code>solve</code> is meant to be general, and that was too much work for one
puzzle. Let's look next at the N-Queens problem. There are a ton of
possible positions we could try for all N queens, but each piece
reduces the number of options we have for the other pieces.
We will place the queens one column at a time. At each column, we
will compute which rows are valid based on the previous columns. A
row is valid if no previous column has a queen on the same row or
diagonal.
</p>
<p>
N-Queens has many solutions. With <code>solve</code>, we can find one, some, or
all of the solutions, given enough time or memory.
</p>
<p>
Here is the code.
</p>
<pre class="example">let n_queens n =
let all_rows = Set.ofList [1..n]
let next_f queens =
let column = List.length queens + 1
queens
|> List.fold (fun possible (row, col) ->
let distance = column - col
// Remove the current row, and diagonals from the
// possible set. The diagonals are just previous
// row +/- the column difference. This is safe here,
// because even if row - distance is negative, we are
// removing it from another set. No array access is
// involved.
Set.difference possible
(Set.ofList [row; row + distance;
row - distance])) all_rows
|> Set.map (fun (row) ->
(row, column)::queens)
let done_f queens =
List.length queens = n
solve next_f done_f []
</pre>
<p>
<a href="http://fssnip.net/6n">see the code at fssnip.net</a>
</p>
<p>
And some results from running the code.
</p>
<pre class="example">
n_queens 8 |> Seq.length;;
val it : int = 92
> n_queens 9 |> Seq.length;;
val it : int = 352
> n_queens 10 |> Seq.length;;
val it : int = 724
> n_queens 11 |> Seq.length;;
val it : int = 2680
> // Solve for N = 20, but just return one solution.
> n_queens 20 |> Seq.head;;
val it : (int * int) list =
[(11, 20); (6, 19); (14, 18); (7, 17); (10, 16); (8, 15); (19, 14); (16, 13);
(9, 12); (17, 11); (20, 10); (18, 9); (12, 8); (15, 7); (13, 6); (4, 5);
(2, 4); (5, 3); (3, 2); (1, 1)]
</pre>
<p>
This function also solves Sudoku, with the right inputs. By the time
all of the helper code is written, <code>solve</code> is a small fraction of the
code. But, it is still instructive to prune away the details of the
puzzles to find the essence of the search problem, even if only for
better understanding.
</p>
<p>
<a href="http://fssnip.net/6q"> Sudoku code </a></p>http://mingledcup.dkjones.org/2011/07/dfs-for-puzzle-solving.htmlnoreply@blogger.com (Dave)0tag:blogger.com,1999:blog-6272748843257835470.post-7202534557583301446Thu, 20 Jan 2011 11:19:00 +00002011-01-20T06:19:06.853-05:00fsharppythonStackoverflow -- finally answered a questionGot my first selected answer on <a href="http://stackoverflow.com/questions/4681434/f-facebook-hacker-cup-double-squares/4715378#4715378">stackoverflow</a>! I waited several days to post the full solution, in case the competition in question was still running. My hope was that people would down vote his question if that was the case.<br />
<br />
My solution isn't elegant, but I thought it was a nice example of a recursive function that goes beyond the factorial function you normally see. Ok, it isn't really a good example of recursion. It is an example of using tail recursion to eliminate mutable variables that you would use in a while loop. Oh well.<br />
<br />
<br />
<br />http://mingledcup.dkjones.org/2011/01/stackoverflow-finally-answered-question.htmlnoreply@blogger.com (Dave)0tag:blogger.com,1999:blog-6272748843257835470.post-8574704444686130901Wed, 01 Sep 2010 01:41:00 +00002010-09-01T19:47:36.853-04:00fsharpTesting with FsCheck<p> Now, we will try to test the sort function from <a href="http://mingledcup.dkjones.org/2010/08/simple-quicksort-in-f.html#links"> before </a> using <a href="http://fscheck.codeplex.com/">FsCheck</a>
<p> First, we download and build FsCheck. Then, in the F# interactive shell, (or an .fsx file), we run the following commands.
<pre>
#I "/home/dave/lib/fsharp/fscheck"
#r "FsCheck.dll"
</pre>
<p>
This sets the load path to where I built the FsCheck dll, and references the dll. The FsCheck Quick Start and documentation have a lot more information than I am about to give...
<p> First, we need a property to test. Since this is a sort function, we would like to see that the data is sorted. We need a function that given an array of data, sorts it, and checks if it is sorted. To keep things easier for now, we will use an integer array. Also, I have learned the hard way to make the tests fail first.. so this first version will be a bad test.
<pre>
let prop_is_sorted (data:int []) =
let N = Array.length data
[|1..N-1|]
|> Array.forall (fun i ->
data.[i] >= data.[i-1])
</pre>
<p>
This function takes an array of data, and checks that each element should be after the one before it. But, we didn't sort yet, so it should fail on some data. Let's run it to find out.
<pre>
> Check.Quick prop_is_sorted;;
Falsifiable, after 3 tests (3 shrinks) (StdGen (544801007,295317223)):
[|1; 0|]
val it : unit = ()
</pre>
<p> The test framework generated three different test cases. Two passed, and the third failed. Also, the framework shrank the failing test case three times, reducing the size of the data set that caused the failure. Shrinking doesn't always find a smaller data set, but when it does, it narrows the range of possible causes of the problem.
<p> Let's update the test function to call our sort function, before checking if the array is sorted.
<pre>
let prop_is_sorted (data:int []) =
let N = Array.length data
sort data
[|1..N-1|]
|> Array.forall (fun i ->
data.[i] >= data.[i-1])
</pre>
<p> And running it gives us...
<pre>
> Check.Quick prop_is_sorted;;
Ok, passed 100 tests.
val it : unit = ()
</pre>
<p> That is great! Except we don't know what kind of data really went into the tests... FsCheck provides ways to get some insight into the data going into the test. In this case, the default generators are probably doing a good enough job, but more complex cases will require more care.
<p>A bad sort function could still pass this test. Perhaps a function that given
an array of length N, returns an array with the numbers from 1 to N. We should write more tests on other properties of a sort function to make sure that our sort is doing what it is supposed to. In this case, we have a simple test we can use ... regression test against the system sort.
<pre>
let prop_compare_with_system (data:int[]) =
let a = Array.sort data // out of place
sort data // in place
a = data
</pre>
<p>This test passes again with 100 successes, and doesn't pass if we give a faulty sort function.
<p> This type of randomized testing is a nice alternative to unit testing. In some cases, it is much less verbose, and it can generate test cases that I would never think of trying myself.
<p> Now that we have some tests in place, we can implement some of the more advanced tweaks to the quicksort algorithm...http://mingledcup.dkjones.org/2010/08/testing-with-fscheck.htmlnoreply@blogger.com (Dave)0tag:blogger.com,1999:blog-6272748843257835470.post-5236881583733573741Fri, 27 Aug 2010 02:29:00 +00002010-08-27T07:44:21.359-04:00fsharpSimple Quicksort in F#<p> Here is a very simple quicksort function in F#. <a href="http://en.wikipedia.org/wiki/Quicksort">Quicksort</a> is a generally fast, general purpose sorting algorithm. It works well because it is a divide and conquer algorithm that does all of its work in place.
<p>
Quicksort implementations can be cache friendly because it keeps working on smaller and smaller portions of the data set. If the data is in an array, the computer won't have as many cache misses while the algorithm is running. In modern computers, memory bandwidth is one of the limiting factors in how fast things can go.
<p> F# is a multi-paradigm language, which is a good thing for Quicksort. Although I like working with functional code, this code looks a lot nicer when we use mutable state and arrays.
<p> This implementation does the bare minimum needed. The fanciest part of the code is the median-of-three pivot selection. The reason I included this pivot selection is because the rest of the code is simpler if we can assume that the first element of a subarray is smaller than the current pivot. The loops inside the main partition function get a little cleaner.
<p> In an F# program, code must be defined before it is used. So, the main function here is at the bottom of the listing. To get a top down view, read from the bottom up, or vice versa.
<p>
The main algorithm consists of two steps (besides checking for empty subarrays)
<ol>
<li> Pick a pivot element, and partition the sub-array into a chunk less than
or equal to the pivot, and a chunk greater than or equal to the pivot.
<li> Recursively sort the subarrays.
</ol>
<p>
The recursion stops when we have a subarray of length 1. In the code here, we have another case for when the subarray has length 2.
<p> There are many other improvements that we can make to the basic algorithm. In the future I may implement some of them, and also, I would like to show how to test this code with <a href="http://fscheck.codeplex.com/">FsCheck</a>, a randomized test framework.
<pre class="code">
let inline swap (data:'a[]) a b =
let t = data.[a]
data.[a] <- data.[b]
data.[b] <- t
/// Sort three values from an array. Put the smallest
/// at index a, biggest at c, and median at b.
let inline median_of_three (data:'a[]) a b c =
if data.[b] < data.[a] then
swap data a b
if data.[c] < data.[b] then
swap data c b
if data.[b] < data.[a] then
swap data a b
/// partition the data from index a to b (inclusive)
/// use the element at position b as the pivot, and
/// assume data.[a] is <= data.[b].
let inline partition (data:'a[]) a b =
// After this is called, return the new position
// of the pivot value. After the call, all values before
// the pivot position should be <= to the pivot, and all values
// after should be >= the pivot.
let mutable i = a - 1
let mutable j = b
let pivot = data.[b]
while i < j do
i <- i + 1
while data.[i] < pivot do
i <- i + 1
j <- j - 1
while data.[j] > pivot do
j <- j - 1
if i < j then
swap data i j
// Now, i is >= j. data.[i] is >= pivot.
// data.[j] <= pivot. So, move the pivot
// to the middle where it belongs, and move
// the value at i to the end of the array.
swap data i b
i
let inline sort (data:'a[]) =
let rec loop a b =
if a >= b then ()
elif a + 1 = b then
if data.[a] > data.[b] then swap data a b
else
let c = (a+b)/2
median_of_three data a b c
let p = partition data a b
loop a (p-1)
loop (p+1) b
loop 0 (data.Length - 1)
</pre>
<a href="http://ideone.com/CBAMC">Ideone.com | CBAMC</a>http://mingledcup.dkjones.org/2010/08/simple-quicksort-in-f.htmlnoreply@blogger.com (Dave)0tag:blogger.com,1999:blog-6272748843257835470.post-8209006214425050273Sun, 22 Aug 2010 01:14:00 +00002010-08-21T22:21:21.406-04:00fsharpmathGCD in F#<p>
Now we will write a function to calculate the greatest common divisor
of two numbers. The <a href="http://en.wikipedia.org/wiki/Euclidean_algorithm">Euclidean Algorithm</a> is an efficient, and ancient, method of finding the GCD.
<p>
Euclid's algorithm takes advantage of some properties of the gcd function and the modulus function. Here is a loose explanation of why the algorithm works
<pre>
gcd(a,b) = gcd(b, a - q*b) for any integer q
a % b = a - q*b from some integer q,
so gcd(a,b) = gcd(b, a % b)
</pre>
<p>
Then, we just stop the algorithm when b is zero. And now for the F# code.
<pre>
let rec gcd a b =
if b = 0 then a
else
gcd b (a % b)
</pre>
<p>
Aside from the syntax, and checking for the end condition, this looks like the math.
<p>
And now, a few tests.
<pre class="code">
let f a b =
printfn "gcd(%d,%d) = %d" a b (gcd a b)
f 10 9
f (13*61*2*2*2*3) (13*2*3*5*7)
f -10 12345
</pre>
<p>
With the output,
<pre>
gcd(10,9) = 1
gcd(19032,2730) = 78
gcd(-10,12345) = 5
</pre>
<a href="http://ideone.com/hHN7j">ideone.com/hHN7j</a>http://mingledcup.dkjones.org/2010/08/gcd-in-f.htmlnoreply@blogger.com (Dave)0tag:blogger.com,1999:blog-6272748843257835470.post-6786774449957375128Sat, 14 Aug 2010 01:23:00 +00002010-08-13T21:24:32.944-04:00fsharpmathSimple prime test in F#Here is the same algorithm as the last <a href="2010/08/simple-prime-test-in-python.html"> post </a>, but in F#. There is no way to break out of a for loop in F#, besides throwing an exception, so this code uses recursion instead.
<pre class="code">
let is_prime n =
if n < 2 then false
else
let limit = float n |> sqrt |> fun x -> x + 1. |> int
let rec loop d =
if d = limit then true
elif n % d = 0 then false
else loop (d + 1)
loop 2
> [1..100] |> List.filter is_prime;;
val it : int list =
[2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41;
43; 47; 53; 59; 61; 67; 71; 73; 79; 83; 89; 97]
</pre>http://mingledcup.dkjones.org/2010/08/simple-prime-test-in-f.htmlnoreply@blogger.com (Dave)0