Haskell, 186 bytes
p@(n,s)%(c:z)=maybe((n,s++[c])%z)(\i->p:(n+i,"")%z)$lookup c$zip"),("[-1..1];p%_=[p]
(n,w)&(i,s)|i>n=(i,show i++':':s)|i==n=(n,w++',':s);p&_=p
main=interact$snd.foldl(&)(0,"").((0,"")%)
Full program, takes tree on stdin
, produces spec'd output format on stdout
:
& echo '2(7(2,6(5,11)),5(9(4)))' | runhaskell 32557-Deepest.hs
3:5,11,4
& echo 'A(B(C,D(E)))' | runhaskell 32557-Deepest.hs
3:E
Guide to the golf'd code (added better names, type signatures, comments, and some subexpressions pulled out and named -- but otherwise the same code; an ungolf'd version wouldn't conflate breaking into nodes with numbering, nor finding deepest with output formatting.):
type Label = String -- the label on a node
type Node = (Int, Label) -- the depth of a node, and its label
-- | Break a string into nodes, counting the depth as we go
number :: Node -> String -> [Node]
number node@(n, label) (c:cs) =
maybe addCharToNode startNewNode $ lookup c adjustTable
where
addCharToNode = number (n, label ++ [c]) cs
-- ^ append current character onto label, and keep numbering rest
startNewNode adjust = node : number (n + adjust, "") cs
-- ^ return current node, and the number the rest, adjusting the depth
adjustTable = zip "),(" [-1..1]
-- ^ map characters that end node labels onto depth adjustments
-- Equivalent to [ (')',-1), (',',0), ('(',1) ]
number node _ = [node] -- default case when there is no more input
-- | Accumulate into the set of deepest nodes, building the formatted output
deepest :: (Int, String) -> Node -> (Int, String)
deepest (m, output) (n, label)
| n > m = (n, show n ++ ':' : label) -- n is deeper tham what we have
| n == m = (m, output ++ ',' : label) -- n is as deep, so add on label
deepest best _ = best -- otherwise, not as deep
main' :: IO ()
main' = interact $ getOutput . findDeepest . numberNodes
where
numberNodes :: String -> [Node]
numberNodes = number (0, "")
findDeepest :: [Node] -> (Int, String)
findDeepest = foldl deepest (0, "")
getOutput :: (Int, String) -> String
getOutput = snd
@close-voter: what are you unclear about? – Jwosty – 2014-06-25T20:15:38.360
3Perhaps the fact that there is no input or output specification, or test cases for those inputs and outputs. – Doorknob – 2014-06-25T20:20:43.543
Trying to fix it but my phone sucks... :P it is better so for though. – Jwosty – 2014-06-25T20:51:34.573
3Shouldn't the first tree be A(B(C,D(E))? – bakerg – 2014-06-25T21:14:34.833
1@bakerg right, my mistake. Fixed. – Jwosty – 2014-06-25T22:50:57.167
What is a legal identifier? The spec doesn't seem to rule out identifiers which contain parentheses and commas, so the grammar is ambiguous. – Peter Taylor – 2014-06-26T09:11:00.390
The nodes or the values of the nodes? – Adam Speight – 2014-06-26T11:11:26.707
@PeterTaylor thanks, restricted to one or more alphanumeric characters. – Jwosty – 2014-06-26T15:07:54.087
@AdamSpeight the nodes in this case do not have values; they only have an identifier. So the identifier. – Jwosty – 2014-06-26T15:08:37.603
@Jwosty If the question was return the nodes at depth 2
{2;6;9}
would be the value but the nodes would be{2; 6(5,11); 9(4,)}
. Cos 6 and 11 have sub nodes. So return the nodes isn't the same as, return the value of the nodes. – Adam Speight – 2014-06-26T15:49:48.133