current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.
up vote -1 down vote favorite
1

A string like this one:

"a, 4.25, ((true, 5), 3, (false, false, false)), abc"

Describes a tree with 13 nodes, 9 of which are leaf nodes. In C# the leaf nodes in this example would be of types string, float and bool, this differs between languages and depending on your implementation. The important structure forming symbols here are , ( and ) with spaces being ignored.

See the diagram in David Carrahers answer for a tree of the desired shape.

var a = new cake(4, "abc")

The above contains 8 symbols, I'm counting bracket and " pairs as a half and things like . as 1.

The goal is to write code with the fewest symbols which given a string like the one shown above, creates the tree it represents.

For example in the form of arrays inside each other, or interconnecting node objects.

60 extra points if you don't sort of cheat by adjusting the input string slightly then executing it.

I won't count the symbols that define the input string.

daniero
100 - (10 symbols)
+40 points for understanding numbers, strings, bools
    and any other basic types the language understands.
+20 points for using a reasonably general language.
150 total points

fejesjoco
100 - (est 37 symbols)
+20 points for it understanding numbers as well as strings.
+40 points for using a reasonably general language.
97 total points

tomas
100 - (10 symbols)
90 total points

David Carraher
100 - (est 19 symbols)
81 total points
share|improve this question
2  
Looks like homework, basic tokenizing as part of writing a script interpreter. –  Yimin Rong Feb 7 at 11:49
    
Please define the exact syntax of the string. –  fejesjoco Feb 7 at 13:00
    
I only see 12 nodes, can you explain it a bit better? –  Teun Pronk Feb 7 at 13:56
    
@TeunPronk I guess the 13th is the root node. –  Joel Bosveld Feb 7 at 14:27
    
The 13th node is the root, although this dosn't matter greatly. It's not homework or a part of a course. –  alan2here Feb 7 at 17:11
show 5 more comments

4 Answers

up vote 3 down vote accepted

JavaScript

s="a, 4.25, ((true, 5), 3, (false, false, false)), abc"
eval(("["+s+"]").replace(/\(/g,"[").replace(/\)/g,"]").replace(/([a-z]+)/g,"'$1'"))

The exact syntax, input and output format weren't exactly defined... I replace every a-z character to become a string, even true/false, which could be booleans, but there's no indication if there should be a distinction. I don't know if other characters are allowed or not (ő, $, \uFA20, ...), so my code doesn't care about that either.

share|improve this answer
    
I tried it in the Firebug console in Firefox. Also works in the developer console of IE. –  fejesjoco Feb 7 at 17:31
    
The result is a recursive array: ["a", 4.25, [["true", 5], 3, ["false", "false", "false"]], "abc"] –  fejesjoco Feb 7 at 17:39
    
It may be bit of cheating, but it's the most straightforward way I can imagine. Writing a parser is a big task, but many languages have eval-like functions, so there's a reusable parser right there. –  fejesjoco Feb 7 at 17:43
    
Oh, you replace some of the brackets in the string with another type then execute the string :P Impressive all the same :) You may win, particularly if no less cheaty solutions are posted. –  alan2here Feb 7 at 17:49
add comment
up vote 2 down vote

Mathematica

StringReplace replaces all instances of ( with List[; instances of ) with ].

The FullForm of List must be used (instead of {…}); otherwise ToExpression will not parse the string correctly.

f@t_:=ToExpression["List["<>StringReplace[t,{"("->"List[",")"->"]"}]<>"]"]

Example

f["a, 4.25, ((true, 5), 3, (false, false, false)), abc"]

{a, 4.25, {{true, 5}, 3, {false, false, false}}, abc}

Verification

TreeForm[<expression>] displays the Mathematica expression as a tree.

TreeForm[f["a, 4.25, ((true, 5), 3, (false, false, false)), abc"]]

tree form

share|improve this answer
add comment
up vote 2 down vote

R, 36 chars

plot(read.tree(,paste0("(",a,");")))

package ape must be loaded.

Output:

enter image description here

share|improve this answer
add comment
up vote 2 down vote

Common Lisp

I think it would count as something around 11 symbols?

Wrap parentheses around the string, remove the commas and evaluate it, and you have a LISP list.

(read-from-string (remove #\, (concatenate 'string "(" s ")" )))

s is the string.

For the given example it returns a list (A 4.25 ((TRUE 5) 3 (FALSE FALSE FALSE)) ABC)

share|improve this answer
1  
For those not familiar with lisp, it would be helpful to know that the internal representation of s-expressions is a tree. By striping the commas daniero has rendered the input into a s-expression. Then he just internalizes it and ::Bingo!:: –  dmckee♦ Feb 8 at 18:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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