No such thing as a small change 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??

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

(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.

Create A New User
Node Status?
node history
Node Type: note [id://904017]
help
Chatterbox?
and a kettle whistles...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (7)
As of 2017-08-22 17:19 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Who is your favorite scientist and why?

Results (337 votes). Check out past polls.

Notices?