Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Subway Trees
{-# LANGUAGE OverloadedStrings #-}
import Control.Arrow
import Data.List
import Data.Maybe
import Control.Applicative
import Data.Attoparsec.ByteString.Char8
import qualified Data.ByteString.Char8 as C
import qualified ScannerBS as S
data Subway = Subway [Subway]
deriving (Show,Ord,Eq)
cannonical :: Subway -> Subway
cannonical (Subway xs) = Subway $ sort (map cannonical xs)
parseSubway :: Parser Subway
parseSubway = Subway <$> (string "0" *> many parseSubway <* string "1")
str2sub :: C.ByteString -> Subway
str2sub s = fromJust $ maybeResult $ parse parseSubway (C.cons '0' (C.snoc s '1'))
main :: IO ()
main = C.interact $
S.runScanner (S.numberOf (S.two S.str))
>>> map solve >>> C.unlines
solve :: [C.ByteString] -> C.ByteString
solve = (["","same","different"] !!) . length . group . map (cannonical . str2sub)
@m4dc4p

This comment has been minimized.

Copy link

m4dc4p commented May 22, 2020

Any chance you could explain how parseSubway builds the tree from the input string? I suppose it hinges on what <* and *> do?

@blaisepascal

This comment has been minimized.

Copy link
Owner Author

blaisepascal commented May 22, 2020

Sure. The <* and *> are standard forgetful applicative combinators. They are of types (<*) :: f a -> f b -> f a and (*>) :: f a -> f b -> f b. They evaluate both arguments, and then forget about the side without the arrow. So the expression string "(" *> integer <* string ")" says to definitely parse an open paren (and fail if there isn't one), then parse an integer, then parse a close paren (and fail if there isn't one), and return just the integer.

So parseSubway can be interpreted as "To get a Subway from a string, look for a 0 (and ignore it), zero or more sub-Subways, and then a 1, and build the parsed Subway from the list of sub-Subways.

This was based on the observation that the in-order traversal of the subway tree will always have a "0" when entering a list of sub-trees, and a "1" when it is done with a list of sub-trees. It has the same structure as the Dyck Language, except using "0" and "1" instead of parenthesis.

I should have used a more standard definition parseSubway = Subway <$> many ( string "0" *> parseSubway <* string "1" ), which would have saved me a lot of grief with the need to wrap the input string in an extra 0....1.

@m4dc4p

This comment has been minimized.

Copy link

m4dc4p commented May 22, 2020

This was based on the observation that the in-order traversal of the subway tree will always have a "0" when entering a list of sub-trees, and a "1" when it is done with a list of sub-trees. It has the same structure as the Dyck Language, except using "0" and "1" instead of parenthesis.

Great insight. Thank you!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.