Seeing as its thst time of year again and everyone is posting their homework, has anyone got any good puzzles to do? I wouldn't mind having a go at something a bit tricky. Tom
G'day all. On Fri, Aug 22, 2003 at 03:41:14PM +1000, thomas_bevan@aardvark.net.au wrote:
Seeing as its thst time of year again and everyone is posting their homework, has anyone got any good puzzles to do? I wouldn't mind having a go at something a bit tricky.
OK, here's a tricky problem. Take a list S. Delete some elements from the list. What you have left is a subsequence of S. For example, [1,3,2] is a subsequence of [2,1,2,1,3,2,1,3]. Consider the following list: [1,2,3,1,2,3,1] This list contains all permutations of the list [1,2,3] as subsequences. It is also minimal, in the sense that there is no shorter subsequence which will do (though there are potentially many minimal subsequences). We will call such a list a shortest supersequence over the alphabet [1..3]. The challenge is multi-part. You may answer as many or as few questions as you want. 1. Write a function sss :: Int -> [Int] where sss n is a shortest supersequence over the alphabet [1..n]. Make this as efficient as possible. Prove an upper-bound complexity on your function. 2. Write a function sss_length :: Int -> Int where sss_length n is the length of a shortest supersequence over the alphabet [1..n]. Make this as efficient as possible. Prove an upper-bound complexity on your function. If you can't solve this problem efficiently, write a function sss_length_bounds :: Int -> (Int,Int) which returns the best upper and lower bounds that you can. (Hint: n is a trivial lower bound, n^2 is a trivial upper bound. A tighter upper bound is n^2-n+1. Prove this as an exercise.) 3. Write a function sss_count :: Int -> Int where sss_count n is the number of shortest supersequences over the alphabet [1..n]. Make this as efficient as possible. Prove an upper-bound complexity on your function. (Hint: sss_count n must be a multiple of n factorial. Why?) If you can't solve this problem efficiently, write a function sss_count_bounds :: Int -> (Int,Int) which returns the best upper and lower bounds that you can. Incidentally, I don't have sub-exponential answers to any of these questions. You did ask for something "a bit tricky". Cheers, Andrew Bromage
- I leave this morning for ICFP. - My laptop is broken, so I can't work on code for this on the plane. - The delights of Sweden will go less noticed, since the number theorist in me will not let me forget. (It's already saying, "It's such a simple description, how hard can it be? Just give it some thought.") This was cruel timing. ;-) ---Frank On Friday, Aug 22, 2003, at 02:25 US/Eastern, Andrew J Bromage wrote:
G'day all.
On Fri, Aug 22, 2003 at 03:41:14PM +1000, thomas_bevan@aardvark.net.au wrote:
Seeing as its thst time of year again and everyone is posting their homework, has anyone got any good puzzles to do? I wouldn't mind having a go at something a bit tricky.
OK, here's a tricky problem.
Take a list S. Delete some elements from the list. What you have left is a subsequence of S. For example, [1,3,2] is a subsequence of [2,1,2,1,3,2,1,3].
Consider the following list:
[1,2,3,1,2,3,1]
This list contains all permutations of the list [1,2,3] as subsequences. It is also minimal, in the sense that there is no shorter subsequence which will do (though there are potentially many minimal subsequences). We will call such a list a shortest supersequence over the alphabet [1..3].
The challenge is multi-part. You may answer as many or as few questions as you want.
1. Write a function sss :: Int -> [Int] where sss n is a shortest supersequence over the alphabet [1..n]. Make this as efficient as possible. Prove an upper-bound complexity on your function.
2. Write a function sss_length :: Int -> Int where sss_length n is the length of a shortest supersequence over the alphabet [1..n]. Make this as efficient as possible. Prove an upper-bound complexity on your function.
If you can't solve this problem efficiently, write a function sss_length_bounds :: Int -> (Int,Int) which returns the best upper and lower bounds that you can.
(Hint: n is a trivial lower bound, n^2 is a trivial upper bound. A tighter upper bound is n^2-n+1. Prove this as an exercise.)
3. Write a function sss_count :: Int -> Int where sss_count n is the number of shortest supersequences over the alphabet [1..n]. Make this as efficient as possible. Prove an upper-bound complexity on your function.
(Hint: sss_count n must be a multiple of n factorial. Why?)
If you can't solve this problem efficiently, write a function sss_count_bounds :: Int -> (Int,Int) which returns the best upper and lower bounds that you can.
Incidentally, I don't have sub-exponential answers to any of these questions. You did ask for something "a bit tricky".
Cheers, Andrew Bromage _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Thanks, Let's hope you don't ruin my weekend. Tom On Fri, 22 Aug 2003 04:25 pm, Andrew J Bromage wrote:
G'day all.
On Fri, Aug 22, 2003 at 03:41:14PM +1000, thomas_bevan@aardvark.net.au wrote:
Seeing as its thst time of year again and everyone is posting their homework, has anyone got any good puzzles to do? I wouldn't mind having a go at something a bit tricky.
OK, here's a tricky problem.
Take a list S. Delete some elements from the list. What you have left is a subsequence of S. For example, [1,3,2] is a subsequence of [2,1,2,1,3,2,1,3].
Consider the following list:
[1,2,3,1,2,3,1]
This list contains all permutations of the list [1,2,3] as subsequences. It is also minimal, in the sense that there is no shorter subsequence which will do (though there are potentially many minimal subsequences). We will call such a list a shortest supersequence over the alphabet [1..3].
The challenge is multi-part. You may answer as many or as few questions as you want.
1. Write a function sss :: Int -> [Int] where sss n is a shortest supersequence over the alphabet [1..n]. Make this as efficient as possible. Prove an upper-bound complexity on your function.
2. Write a function sss_length :: Int -> Int where sss_length n is the length of a shortest supersequence over the alphabet [1..n]. Make this as efficient as possible. Prove an upper-bound complexity on your function.
If you can't solve this problem efficiently, write a function sss_length_bounds :: Int -> (Int,Int) which returns the best upper and lower bounds that you can.
(Hint: n is a trivial lower bound, n^2 is a trivial upper bound. A tighter upper bound is n^2-n+1. Prove this as an exercise.)
3. Write a function sss_count :: Int -> Int where sss_count n is the number of shortest supersequences over the alphabet [1..n]. Make this as efficient as possible. Prove an upper-bound complexity on your function.
(Hint: sss_count n must be a multiple of n factorial. Why?)
If you can't solve this problem efficiently, write a function sss_count_bounds :: Int -> (Int,Int) which returns the best upper and lower bounds that you can.
Incidentally, I don't have sub-exponential answers to any of these questions. You did ask for something "a bit tricky".
Cheers, Andrew Bromage _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.2 (GNU/Linux)
iD8DBQE/Rm7SYha8TWXIQwoRAvCrAJ4hN2Fh2auX8Sw9yv9jyuvGKYgPyQCcCtj0 2pHxw0tuysC1t54haq0dIOo= =furR -----END PGP SIGNATURE-----
thomas_bevan wrote:
Seeing as its thst time of year again and everyone is posting their homework, has anyone got any good puzzles to do? I wouldn't mind having a go at something a bit tricky.
Here's one: figure out what the following does :-) puzzle = (!!) $ map (1:) $ iterate (s (lzw (+)) (1:)) [] where s f g x = f x (g x) lzw op xs [] = xs lzw op [] ys = ys lzw op (x:xs) (y:ys) = op x y : lzw op xs ys (No fair trying it out in Hugs first...) --Joe English jenglish@flightlab.com
| Seeing as its thst time of year again and everyone is posting their | homework, has anyone got any good puzzles to do? | I wouldn't mind having a go at something a bit tricky. Here is another one: figure out what `unknown' is.
unknown = mysterious unknown
mysterious ks = 0 : weird ks weird (k : ks) = (k + 1) : mysterious ks
Cheers, Ralf
On Friday 22 August 2003 04:29 pm, Ralf Hinze wrote:
| Seeing as its thst time of year again and everyone is posting their | homework, has anyone got any good puzzles to do? | I wouldn't mind having a go at something a bit tricky.
Here is another one: figure out what `unknown' is.
unknown = mysterious unknown
mysterious ks = 0 : weird ks weird (k : ks) = (k + 1) : mysterious ks
Cool! That leads me to this contraption:
tricky = 0 : enigma tricky tricky enigma (k : ks) = (k :) . labyrinth (enigma ks) labyrinth f (k : _ : ks) = (k + 1) : f ks
Figure out what `tricky' is, and what its relationship is to `unknown'. Enjoy! Matt Harden
Am Dienstag, 26. August 2003 05:54 schrieb Matt Harden:
Cool! That leads me to this contraption:
tricky = 0 : enigma tricky tricky enigma (k : ks) = (k :) . labyrinth (enigma ks) labyrinth f (k : _ : ks) = (k + 1) : f ks
Figure out what `tricky' is, and what its relationship is to `unknown'.
Well, `tricky' can be defined much simpler:
tricky = [0 ..] \/ tricky
where `\/' denotes ... (I leave this to the imagination of the reader). Cheers, Ralf
participants (7)
-
Andrew J Bromage -
Frank Seaton Taylor -
Joe English -
Matt Harden -
Ralf Hinze -
Thomas L. Bevan -
thomas_bevan＠aardvark.net.au