9
\$\begingroup\$

Write a program that takes a binary tree as input, and outputs the deepest node and its depth. If there is a tie, print all involved nodes as well as their depths. Each node is represented as:

T(x,x)

T(x)

T

where T is the identifier of one or more alphanumeric characters and each x is another node.

Here's a simple definition of a binary tree:

  • At the head of a binary tree is a node.
  • A node in a binary tree has at most two children.

For example, the input A(B(C,D(E))) (below) would output 3:E.

Tree 1

While the following tree is a three-way tie between 5, 11, and 4, and their depth is also 3 (starting from 0):

The input 2(7(2,6(5,11)),5(9(4))) (below) would output 3:5,11,4.

Tree 2

This is code golf, so the shortest code measured in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ @close-voter: what are you unclear about? \$\endgroup\$ – Jwosty Jun 25 '14 at 20:15
  • 3
    \$\begingroup\$ Perhaps the fact that there is no input or output specification, or test cases for those inputs and outputs. \$\endgroup\$ – Doorknob Jun 25 '14 at 20:20
  • \$\begingroup\$ Trying to fix it but my phone sucks... :P it is better so for though. \$\endgroup\$ – Jwosty Jun 25 '14 at 20:51
  • 3
    \$\begingroup\$ Shouldn't the first tree be A(B(C,D(E))? \$\endgroup\$ – bakerg Jun 25 '14 at 21:14
  • 1
    \$\begingroup\$ @bakerg right, my mistake. Fixed. \$\endgroup\$ – Jwosty Jun 25 '14 at 22:50
6
\$\begingroup\$

CJam, 49 47

0q')/{'(/):U;,+:TW>{T:W];}*TW={U]',*}*T(}/;W':@

 

0                 " Push 0 ";
q                 " Read the whole input ";
')/               " Split the input by ')' ";
{                 " For each item ";
  '(/             " Split by '(' ";
  )               " Extract the last item of the array ";
  :U;             " Assign the result to U, and discard it ";
  ,               " Get the array length ";
  +               " Add the top two items of the stack, which are the array length and the number initialized to 0 ";
  :T              " Assign the result to T ";
  W>{             " If T>W, while W is always initialized to -1 ";
    T:W];         " Set T to W, and empty the stack ";
  }*
  TW={            " If T==W ";
    U]',*         " Push U and add a ',' between everything in the stack, if there were more than one ";
  }*
  T(              " Push T and decrease by one ";
}/
;                 " Discard the top item, which should be now -1 ";
W                 " Push W ";
':                " Push ':' ";
@                 " Rotate the 3rd item to the top ";
\$\endgroup\$
  • \$\begingroup\$ I've made a slight modification to the output format to make it consistent and less ambiguous, but it shouldn't too much of an inconvenience. \$\endgroup\$ – Jwosty Jun 25 '14 at 22:49
  • \$\begingroup\$ @Jwosty It shouldn't, if this is not code-golf. \$\endgroup\$ – jimmy23013 Jun 26 '14 at 0:38
  • \$\begingroup\$ Well, this is code-golf... But anyway, nice submission :) \$\endgroup\$ – Jwosty Jun 26 '14 at 0:39
  • \$\begingroup\$ Can you please explain how this works? \$\endgroup\$ – Jerry Jeremiah Jun 26 '14 at 5:06
  • \$\begingroup\$ @JerryJeremiah Edited. \$\endgroup\$ – jimmy23013 Jun 26 '14 at 11:01
5
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ That code terrifies me. \$\endgroup\$ – seequ Jun 26 '14 at 11:13
  • \$\begingroup\$ Expanded explanatory code added! Let the terror make you stronger!! \$\endgroup\$ – MtnViewMark Jun 26 '14 at 14:55
  • \$\begingroup\$ You deserve a +1 for that. \$\endgroup\$ – seequ Jun 26 '14 at 15:01
  • \$\begingroup\$ Oh my god, and I am struggling with lists :P \$\endgroup\$ – Artur Trapp Apr 10 '17 at 19:02
4
\$\begingroup\$

GolfScript (75 chars)

Not especially competitive, but sufficiently twisted that it has some interest:

{.48<{"'^"\39}*}%','-)](+0.{;.@.@>-\}:^;@:Z~{2$2$={@@.}*;}:^;Z~\-])':'@','*

The code has three phases. Firstly we preprocess the input string:

# In regex terms, this is s/([ -\/])/'^\1'/g
{.48<{"'^"\39}*}%
# Remove all commas
','-
# Rotate the ' which was added after the closing ) to the start
)](+

We've transformed e.g. A(B(C,D(E))) to 'A'^('B'^('C'^'D'^('E'^)''^)''^) . If we assign a suitable block to ^ we can do useful processing by using ~ to eval the string.

Secondly, we find the maximum depth:

0.
# The block we assign to ^ assumes that the stack is
#   max-depth current-depth string
# It discards the string and updates max-depth
{;.@.@>-\}:^;
@:Z~

Finally we select the deepest nodes and build the output:

# The block we assign to ^ assumes that the stack is
#   max-depth current-depth string
# If max-depth == current-depth it pushes the string under them on the stack
# Otherwise it discards the string
{2$2$={@@.}*;}:^;
# Eval
Z~
# The stack now contains
#   value1 ... valuen max-depth 0
# Get a positive value for the depth, collect everything into an array, and pop the depth
\-])
# Final rearranging for the desired output
':'@','*
\$\endgroup\$
1
\$\begingroup\$

Perl 5 - 85

Please feel free to edit this post to correct the character count. I use say feature, but I don't know about the flags to make it run correctly without declaring use 5.010;.

$_=$t=<>,$i=0;$t=$_,$i++while s/\w+(\((?R)(,(?R))?\))?/$1/g,/\w/;@x=$t=~/\w+/gs;say"$i:@x"

Demo on ideone

The output is space-separated instead of comma-separated.

The code simply uses recursive regex to remove the root of the trees in the forest, until it is not possible to do so. Then the string before the last will contain all the leaf nodes at the deepest level.

Sample runs

2
0:2

2(3(4(5)),6(7))
3:5

2(7(2,6(5,11)),5(9(4)))
3:5 11 4

1(2(3(4,5),6(7,8)),9(10(11,12),13(14,15)))
3:4 5 7 8 11 12 14 15
\$\endgroup\$
1
\$\begingroup\$

VB.net

Function FindDeepest(t$) As String
  Dim f As New List(Of String)
  Dim m = 0
  Dim d = 0
  Dim x = ""
  For Each c In t
    Select Case c
      Case ","
        If d = m Then f.Add(x)
        x = ""
      Case "("
        d += 1
        If d > m Then f.Clear() :
        m = d
        x = ""
      Case ")"
        If d = m Then f.Add(x) : x = ""
        d -= 1
      Case Else
        x += c
    End Select
  Next
  Return m & ":" & String.Join(",", f)
End Function

Assumption: Node Values can not contain ,,(,)

\$\endgroup\$
  • 1
    \$\begingroup\$ This doesn't seem to be golfed at all. Can't you remove most of that whitespace (I don't know VB)? \$\endgroup\$ – seequ Jun 26 '14 at 12:18
  • \$\begingroup\$ Depends some of the whitespace is significant. \$\endgroup\$ – Adam Speight Jun 26 '14 at 12:20
1
\$\begingroup\$

Javascript (E6) 120

Iterative version

m=d=0,n=[''];
prompt().split(/,|(\(|\))/).map(e=>e&&(e=='('?m<++d&&(n[m=d]=''):e==')'?d--:n[d]+=' '+e));
alert(m+':'+n[m])

Ungolfed and testable

F= a=> (
    m=d=0,n=[''],
    a.split(/,|(\(|\))/)
    .map(e=>e && (e=='(' ? m < ++d && (n[m=d]='') : e==')' ? d-- : n[d]+=' '+e)),
    m+':'+n[m]
)

Test In Firefox console:

['A', '2(7(2,6(5,11)),5(9(4)))', 'A(B(C,D(E)))']
.map(x => x + ' --> ' + F(x)).join('\n')

Output

"A --> 0: A

2(7(2,6(5,11)),5(9(4))) --> 3: 5 11 4

A(B(C,D(E))) --> 3: E"

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.