Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Re^2: Find Length Of Longest Ascending/Descending Sequence

by Fletch (Chancellor)
on May 10, 2011 at 19:08 UTC ( #904017=note: print w/ replies, xml ) Need Help??


in reply to Re: Find Length Of Longest Ascending/Descending Sequence
in thread Find Length Of Longest Ascending/Descending Sequence

My haskell approach. Only prints the length and the longest substring which I think was the original problem. And there's probably a module function that does take2While that I just don't know about.

import Data.List (sort,tails) isAscP x y | succ x == y = True isAscP x y | x == '9', y == '0' = True isAscP _ _ = False isDescP x y | succ y == x = True isDescP x y | x == '0', y == '9' = True isDescP _ _ = False take2While :: (a -> a -> Bool) -> [a] -> [a] take2While _ [] = [] take2While _ (x:[]) = [x] take2While p (x:xs@(y:ys)) | p x y == True = x : take2While p xs | otherwise = [x] longestSeq p s = last . sort . map (\x -> (length x, x)) . map (take2W +hile p) $ tails s longestAsc s = longestSeq isAscP s longestDesc s = longestSeq isDescP s main = do mapM_ print $ map ( \x -> last $ sort [ longestAsc x, longestDesc x +] ) test_data test_data = ["46177162136821098372191324396358023311290325514995512037 +4576", "41218287161128572793732981048741734764567889966242600855 +8163", "80644516862271572985414541535685057678903372416444198119 +0358", "73799320594284321094463204375578307048769141937606874852 +0835", "79783673261130165104915794140267749392590890126803346772 +1123", "80034367333583441342569006349963696554752767153578901036 +0222", "36455695473823274009541290542819284921805886986823415432 +1153", "65688601631846538985084526162069491656561155920969515432 +1950", "43982308548391881824360236063248675793848336789046458690 +9210", "27501082572643841973404198765708516277381582187277161932 +2197", "36286200318698643562895639299746227057153878528789011116 +5953", "86578896980048397890987639695689642805948383465444378364 +0994", "08494326244468225664919617082669975678940469991751181340 +4654", "03802243561219785083513947890147183878904240719985858365 +4421", "24471232554189661569782092544273572763854030957460498432 +1042", "79927259366563301479296432100629590729754503939144233930 +9443", "87513484093393755250506962456969217890137276421097350124 +0868", "16060437323320876543354855484294170848344644764967947362 +3104", "78796640372485356789004027625810549218342470476191585852 +4942", "23456532982436100867707549226413076264717737053820267894 +9041" ]

Produces the same strings as the first response for the same test data.

$ runhaskell ascruns.hs (5,"21098") (5,"45678") (5,"67890") (6,"432109") (5,"89012") (5,"78901") (5,"54321") (5,"54321") (5,"67890") (5,"98765") (5,"78901") (5,"09876") (5,"56789") (5,"78901") (5,"43210") (5,"43210") (5,"78901") (6,"876543") (6,"567890") (5,"23456")

Update: Revised version that produces offsets as well as being a bit shorter terser (thanks ambrus for maximum vice last . sort)

longestSeq p s = maximum tuples where ts = tails s runs = map (take2While p) ts tuples = zip3 (map length runs) [0..] runs $ runhaskell ascruns.hs | head -n 4 (len,pos,str) (5,12,"21098") (5,37,"45678") (5,35,"67890")

Further Duh: isDescP is really just flip isAscP . . .

The cake is a lie.
The cake is a lie.
The cake is a lie.


Comment on Re^2: Find Length Of Longest Ascending/Descending Sequence
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://904017]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (6)
As of 2015-08-01 00:49 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (285 votes), past polls