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.

In informatics, we often use trees in lots of different forms and representations. The three major methods of serialising binary trees are prefix, infix and postfix notation. For example, the following binary tree:

Tree, infix: rbxabde   (source: Dutch Olympiad in Informatics, finals, 2012/13)

can be represented in prefix notation as abrxdbe, in infix as rbxabde and in postfix as rxbbeda.

In this case, you are confronted with a complete binary tree represented in infix notation. Your task is to convert this tree to prefix notation. Your input on stdin will be 2n-1 lowercase alphabet characters, a-z and no more, ended with a newline character, for any integer n such that 1 ≤ n ≤ 16. Thus, the maximum number of characters you will get is 65535. Output the tree to stdout in the same way, but then in prefix format.

This is code golf, so the shortest code, counted in bytes, will win. Votes will act as a tie breaker, and if those tie up as well, submission date and time.

share|improve this question
    
possible duplicate of Convert from Infix Notation to Prefix Notation –  Peter Taylor Apr 25 at 11:11
    
@PeterTaylor Thanks for mentioning, but I think this challenge is actually different because you don't need to evaluate an entire expression, just a simple 2<sup>_n_</sup>-1 binary tree. –  tomsmeding Apr 25 at 11:14
    
Ok, the restriction to complete binary trees does simplify things quite a lot. –  Peter Taylor Apr 25 at 11:50

6 Answers 6

GolfScript, 23 chars

.,\{;).2base{)!}do}$/n-

This solution uses a different approach than Howard's: basically, it sorts the input characters according to the list of branches needed to reach that character from the root of the tree.

Note that the newline at the end of the input is required (i.e. the input length must be a power of two). The n- at the end of the code is required to suppress an extra newline at the beginning of the output; if such a newline is acceptable, those characters can be omitted for a score of 21 chars.

As usual, you can test this code online.

Explanation:

  • .,\ calculates the length of the input, and moves it below the input string on the stack. It will be used as the starting value of the loop counter used to construct the sort keys below. (The code relies on this being a power of two; otherwise the bit manipulation below will not produce the expected results. Any sufficiently large power of two would work, though.)

  • { }$ sorts the characters in the input string according to the sort key computed inside the block:

    • ; just throws away the character given as input to the block; we don't care about the actual character values here, just about their positions within the string.

    • ). increments the loop counter on the stack (which was initialized to the length of the input string) and makes a copy of it.

    • 2base converts this copy to an array of bits (omitting leading zeros; that's why we need to start counting from a large enough power of two, rather than simply from zero).

    • {)!}do repeatedly chops off the lowest bit from the array until the chopped-off bit is a 1.

    Since the resulting sort keys are arrays, the $ compares them lexicographically. Thus, for example, the array [1] (which corresponds to the root node) sorts before [1 0] (which corresponds to the left child of the root node) and [1 1] (the right child of the root node).

  • At the end, / gets rid of the loop counter by using it as the length of chunks to split the output string into (thanks, Peter!), and n- strips the newline off the sorted input string. (The GolfScript interpreter will append another newline to the output after printing the contents of the stack.)

share|improve this answer
2  
Nicely done! You can still save one more: instead of \; to get rid of the loop counter, you can / to split the string into sections larger than it is. (The n- will even then pull it back out of the array so created). –  Peter Taylor Apr 25 at 19:20

GolfScript, 28 characters

{.,1>{.,)2//([)\c]\~c+}*}:c~

You may test the code online.

Annotated code:

# define an operator c acting on the top of stack which does the conversion
{
  # if the input string is more than a single character
  .,1>{
    # split string into two halves (rounded up)
    .,)2//   
    # take first part last character
    ([)
    # take first part rest and call c recursively
    \c]
    # get second part
    \~
    # call c recursively on second part
    c
    # join all three together 
    +
  }*
}:c
# call c
~       
share|improve this answer

GolfScript (29 chars)

{.,1>{.,)2//~\[)](f@f++}*}:f~

Online demo

Works with or without the trailing newline in input.

share|improve this answer
    
It took me too much time to write down my solution... As expected the solutions look quite similar. –  Howard Apr 25 at 12:33

APL (48)

(Yes, the APL charset does fit in a byte.)

{1=⍴⍵:⍵⋄(⊃a),⊃,/∇¨1↓a←1⌽⌽⍵⊂⍨(⍳⍴⍵)∊1,0 1+⌈.5×⍴⍵}⍞

Explanation:

  • {...}⍞: read input, feed to function
  • 1=⍴⍵:⍵: if the input length is one, we're done
  • : otherwise:
  • (⍳⍴⍵)∊1,0 1+⌈.5×⍴⍵: make a bitfield of places to split the input (first character, middle character and character past the middle character)
  • ⍵⊂⍨: split the input at these places
  • a←1⌽⌽: rotate the sub-arrays so that the middle character is first, the left hand is second and the right hand is third, and store in a.
  • ⊃,/∇¨1↓a: run the function again on the last two elements of a and concatenate the results
  • (⊃a),: and concatenate that to the first item in a
share|improve this answer

Python 3 - 76

def f(x):a=len(x)//2;return x and x[a]+f(x[:a])+f(x[a+1:])
print(f(input()))
share|improve this answer

C, 108 chars

My code uses a recursive function, which always prints the character in the middle of the buffer, and calls itself with the part of the string before and the part of the string after the character printed. (Divide and Conquer)

char b[65536];d(s,e){int c=s+(e-s)/2;putchar(b[c]);if(c^s)d(s,c-1),d(c+1,e);}main(){gets(b);d(0,strlen(b));}

ungolfed:

char b[65536];
d(s,e){
    int c=s+(e-s)/2;
    putchar(b[c]);
    if(c^s)d(s,c-1),d(c+1,e);
}
main(){
    gets(b);
    d(0,strlen(b));
}
share|improve this answer
    
That's also the approach I took in my personal non-golfed solution. Doesn't seem to be the shortest though... –  tomsmeding Apr 29 at 10:54

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.