views:

4370

answers:

31
+36  Q: 

Code Golf: The wave

The challenge

The shortest code by character count to generate a wave from the input string.

A wave is generated by elevating (line-1) a higher character, and degrading (line+1) a lower character. Equal characters are kept on the same line (no elevating or degrading done).

Input is made of lower case characters and numbers only, letters are considered higher than numbers.

Test cases:

Input:
    1234567890qwertyuiopasdfghjklzxcvbnm

Output:
                                 z
                                l x v n
                               k   c b m
                              j
                             h
                            g
                   y   p s f
                  t u o a d
               w r   i
            9 q e
           8 0
          7
         6
        5
       4
      3
     2
    1

Input:
    31415926535897932384626433832795028841971693993751058209749445923078164062862

Output:
                9 9   8 6 6
         9 6   8 7 3 3 4 2 4  8   9   88
    3 4 5 2 5 5     2       33 3 7 5 2  4 9   9 99 7
     1 1     3                  2   0    1 7 6 3  3 5   8              8 6
                                            1        1 5 2 9      9 3 7 1 4 6 8
                                                      0   0 7 9  5 2 0     0 2 6
                                                             4 44               2

Code count includes input/output (i.e full program).

+27  A: 

The shortest code by character count to print a 'wave' from the input string.

Console.WriteLine("a 'wave' from the input string.");

codymanix
Definitely not the shortest.
strager
+1 because I dont think it deserves -4
Daniel
-1 this answer is not in the spirit of the question.
Will Bickford
+1 because I enjoy a good smart-ass remark.
Ed Swangren
@strager: no kidding, it's longer than the my answer (if you count just the code and not the boilerplate).
ephemient
The question was enough of a joke by itself without a totally offtopic response.
caspin
Great answer. Breaks up the seriousness of code golf.
Christian
+1 for the lulz
Justicle
+1: shortest answer so far. -1: `puts "a 'wave' from the input string."` is *far* shorter.
dbr
+1 for being funny.
Randolpho
It's customary to put the language and character count. If this is C#, then (a) this won't compile (because it's not in a class), and (b) is only one character shorter than the J solution that actually solves the problem. :-)
Alec
@Alec: It won't compile, but it will run as is in Snippy: http://csharpindepth.com/Downloads.aspx
P Daddy
yawn......................
Epaga
Console.Write("a 'wave' from the input string.");;)
tim
+1  A: 

A Java solution, not particularly compressed (now modified to read from stdin).

public class W
{ 
 public static void main(String[] x)
 {
  String s = new java.util.Scanner(System.in).nextLine();
  int i,j;
  int t = s.length();
  char[] b = s.toCharArray();
  char[][] p = new char[2*t][t];
  int q = t;
  char v = b[0];
  for (i=0; i<2*t; i++)
  {
   for (j=0; j<t; j++)
   {
    p[i][j] = ' ';
   }
  }
  p[q][0] = v;
  String z = new String(p[0]);
  for (i=1; i<t; i++)
  {
   char c = b[i];
   int d = (c == v) ? 0 : (c > v ? -1 : 1);
   q += d;
   p[q][i] = c;
   v = c;
  }
  for (i=0; i<2*t; i++)
  {
   String n = new String(p[i]);
   if (!n.equals(z))
   {
    System.out.println(n);
   }
  }
 } 
}
Simon Nickerson
+10  A: 

Python (161 chars)

v,s="",raw_input()
m=n=len(s)
r=[' ']*n
q=[r[:]for i in range(2*n)]
for j,i in enumerate(s):
 m+=(i<v)-(i>v)
 q[m][j],v=i,i
for i in q:
 if i!=r:print''.join(i)

I haven't done much to compress it yet though. Porting it to something with a spaceship operator now.

ACoolie
Didn't think the space was important. 166 chars without the space.
ACoolie
It is because else you don't compare apples to apples.
LiraNuna
+4  A: 

C#:

using System;
static class A
{ 
    static void Main(string[] a)
    {
        var s=a[0];var r="";
        int i=1,h=0,d=0,c=0,n=s.Length;
        var m=new int[n];
        m[0]=0;
        for(;i<n;i++)
        {
            c+=Math.Sign(s[i]-s[i-1]);
            h=(c>h)?c:h;
            d=(c<d)?c:d;
            m[i]=c;
        }
        for(;h>=d;h--)
        {    
            for (c=0;c<n;c++)
                r+=(m[c]==h)?s[c]:' ';  
             r+="\n";
        }
       Console.Write(r);
    }
}

Weighs in at 287 compressed.

Joel Coehoorn
Needs to have I/O to fit the specifications.
strager
Yeah, I just saw that. What an odd request: normally you just want the function to remove stupid boilerplate code that detracts from the process. Anyway, brining it up to snuff over the next few edits.
Joel Coehoorn
I mean: what if I wanted to use javascript? How would you do the "IO" there? Would you want me to build a whole html doc with a text input?
Joel Coehoorn
Joel, You can use `prompt()` in Javascript. Also, in some languages, the I/O code may change depending on the requirements, and it's more fair to have them in all languages rather than present in some or not present in others.
strager
No, the most fair way it to just ask for a function.
Joel Coehoorn
If this was really about WINNING then anyone using J and its two (or, 56, in this case) unbeatable character solutions for about any weird problem anyone can come up with would ALWAYS win. So no bad blood about the IO req.
Alex
Maybe "fair" was the wrong word. Perhaps "focused" would be better.
Joel Coehoorn
+35  A: 
ephemient
Impressive!
fbrereto
Wha... O_O
strager
"Code count includes input/output (i.e full program)."
LiraNuna
I'd really love to have that program explained... I don't know J at all. I can't even guess at what it's doing.
rmeador
that doesn't even look like a language so much as yosemite sam shouting at bugs bunny.
Jason
Alex
I don't even see the code anymore. All I see now is blonde, brunette, redhead...
P Daddy
@rmeador: J is a bit esoteric, so I usually add explanations when I have the time to. It's there now. @Alex: Nope, `(:` is not a legal word.
ephemient
I think that's what's called an **orgicon** (an emoticon orgy).
P Daddy
J is similar to a language called APL (which stands for A Programming Language of course!) wikipedia has a good entry on it.
Chii
I tested it and it works
Jader Dias
+2  A: 

A first shout in C#. The input must be supplied as first command linie argument.

using System;
using C = System.Console;

static class P
{
    static void Main(string[] a)
    {
        var b = a[0];
        var l = b.Length;

        int y = 0, z = 0;
        for (int i = 0; i < l - 1; i++)
        {
            y += Math.Sign(b[i] - b[i + 1]);
            z = Math.Min(y, z);
        }

        y = 0;
        for (int i = 0; i < l - 1; i++)
        {
            C.SetCursorPosition(i, y - z);
            C.Write(b[i]);

            y += Math.Sign(b[i] - b[i + 1]);
        }
    }
}

This yields 280 bytes in compressed from.

using System;using C=System.Console;static class P{static void Main(string[]a){var b=a[0];var l=b.Length;int y=0,z=0;for(int i=0;i<l-1;i++){y+=Math.Sign(b[i]-b[i+1]);z=Math.Min(y,z);}y=0;for(int i=0;i<l-1;i++){C.SetCursorPosition(i,y-z);C.Write(b[i]);y+=Math.Sign(b[i]-b[i+1]);}}}

Attempt number two with a different approach.

using System;
using System.Collections.Generic;

static class P
{
    static void Main(string[] a)
    {
        var b = a[0] + "$";
        var l = new List<string>();    
        var y = -1;

        for (int i = 0; i < b.Length - 1; i++)
        {
            if ((y == -1) || (y == l.Count))
            {
                y = y < 0 ? 0 : y;
                l.Insert(y, b.Substring(i, 1).PadLeft(i + 1));
            }
            else
            {
                l[y] = l[y].PadRight(i) + b[i];
            }
            y += Math.Sign(b[i] - b[i + 1]);
        }

        foreach (var q in l) Console.WriteLine(q);
    }
}

The loop can further be rewritten to use a try/catch block.

for (int i = 0; i < b.Length - 1; i++)
{
    try
    {
        l[y] = l[y].PadRight(i) + b[i];
    }
    catch
    {
        y = y < 0 ? 0 : y;
        l.Insert(y, b.Substring(i, 1).PadLeft(i + 1));
    }

    y += Math.Sign(b[i] - b[i + 1]);
}

This yields slightly modified and compressed 321 bytes - a bit more then the first attempt, but much robuster.

using System;static class P{static void Main(string[]a){var b=a[0]+"$";var r=new System.Collections.Generic.List<string>();var y=-1;for(int i=0;i<b.Length-1;i++){try{r[y]=r[y].PadRight(i)+b[i];}catch{y=y<0?0:y;r.Insert(y,b[i].ToString().PadLeft(i+1));}y+=Math.Sign(b[i]-b[i+1]);}foreach(var l in r)Console.WriteLine(l);}}

Daniel Brückner
You can save 7 characters by not making `P` static.
Robert Rossney
+1  A: 

C# (564 characters of code)

using System;
class Program {
    static void Main(string[] args) {
     var input = args[0];
     int min = 0, max = 0;
     var heights = new int[input.Length];

     for (var i = 1; i < input.Length; i++) {
      heights[i] = heights[i-1] + (input[i] > input[i-1] ? 1 : (input[i] < input[i-1] ? -1 : 0));
      min = Math.Min(min, heights[i]);
      max = Math.Max(max, heights[i]);
     }

     for (var row = max; row >= min; row--, Console.WriteLine())
      for (var col = 0; col < input.Length; col++)
       Console.Write(heights[col] == row ? input[col] : ' ');
    }
}

Compacted: (324 characters of code)

using System;class A{static void Main(string[] args){var I=args[0];int M=0,X=0;var H=new int[I.Length];for(var i=1;i<I.Length;i++){H[i]=H[i-1]+(I[i]>I[i-1]?1:(I[i]<I[i-1]?-1:0));M=Math.Min(M,H[i]);X=Math.Max(X,H[i]);}for(var r=X;r>=M;r--,Console.WriteLine())for(var c=0;c<I.Length;c++)Console.Write(H[c]==r?I[c]:' ');}}

Using tricks from comments (283 characters):

using System;class A{static void Main(string[] a){var I=a[0];int M=0,X=0,i=1,r,h,c=0,l=I.Length;var H=new int[l];for(;i<l;i++){h=H[i-1]+(I[i]>I[i-1]?1:(I[i]<I[i-1]?-1:0));H[i]=h;M=M<h?M:h;X=x>h?X:h;}for(r=X;r>=M;r--,Console.Write('\n'))for(;c<l;c++)Console.Write(H[c]==r?I[c]:' ');}}
David
`args` can be rewritten as `a` or something. Also, can't you define `i`, `r`, and `c` along with `M` and `X`?
strager
You can shave 7 characters by replacing "M=Math.Min(M,H[i]);X=Math.Max(X,H[i]);" with "var h=H[i];M=M<h?M:h;X=x>h?X:h;"
Oliver Hallam
Console.WriteLine() can also be replaced with Console.Write('\n')
Oliver Hallam
Pulling I.Length into a variable saves a lot of space
Oliver Hallam
Uh, isn't WriteLine() exactly the same length as Write('\n')? :-)
Alec
+5  A: 

C89 (151 characters)

l[999][999];p;v=500;r;main(c){for(;(c=getchar())>0;
)l[v+=c>p,v-=c<p][++r]=*l[v]=p=c;for(v=999;v--;)for
(c=0;c++<=r;)*l[v]&&putchar(c<=r?32|l[v][c]:10);}
strager
compiled with c89, wrote something, pressed enter, and it just want down a line, still in the program. am I missing something? (had to remove the // at the end)
Liran Orevi
@Liran: You probably need to hit Ctrl-D (on UNIX-like platforms) or Ctrl-Z (on Windows-like platforms) to trigger an EOF so that `getchar()` returns NUL.
ephemient
ephemient
Basically I assume input is from a file, not terminal. Yes, you need to enter EOF for it to work. Also, any newlines you enter will be part of the wave.
strager
You can combine the `putchar`s into one with `putchar(c<r?32|l[v][c]:10)` (move the `++` into the `for` loop like so: `for(c=0;c++<r;)`. Then you can get rid of the curly braces for the `if` block. In fact, you can get rid of the `if` altogether, with `*l[v]?putchar(c<r?32|l[v][c]:10):0;`. The `v` loop doesn't need the comarison to `0`. It can be just `for(v=999;v--;)`. And I found that `v=+c>p,v-=c<p` is one char shorter than `v+=(c>p)-(c<p)`. All these changes can get your code down to 150 characters. I verified it still works.
P Daddy
P Daddy
@P Daddy, Many thanks for your suggestions! Sadly, with your `c<r?:0` idea, I have to resort to `<=` because otherwise the last character is chopped off. (Only two extra bytes, but still...)
strager
Yeah, I realized that, but since the last character it chops off is just the newline (translated to '*' by your translation routine), I didn't figure it was a travesty.
P Daddy
@ephemient, much thanks, Ctrl-D twice (On Linux) did the trick.
Liran Orevi
+3  A: 

Haskell (285 characters):

heightDiff x y | x == y = 0
           | x < y = -1
           | True = 1

heights h (x:y:z)= (x,h):(heights (h+(heightDiff x y) ) (y:z))
heights h [y] = [(y,h)]

makech ((x,h):xs) i = (if i==h then x else ' '):makech xs i
makech [] _ = []

printAll xs = mapM_ (putStrLn . (makech xs)) [(minimum $ map snd xs)..(maximum $ map snd xs)]

main = getLine >>= (printAll . heights 0)

Some compression (260 characters):

a x y|x==y=0
     |x<y= -1
     |True=1
c h (x:y:z)=(x,h):(c(h+(a x y))(y:z))
c h [y]=[(y,h)]
d ((x,h):xs)i=(if i==h then x else ' '):d xs i
d [] _=[]
p xs = mapM_ (putStrLn .(d xs)) [(minimum $ map snd xs)..(maximum $ map snd xs)]
main = getLine >>= (p . c 0)
Khoth
`(x>y)-(x<y)` is a short way to compare elevation.
LiraNuna
(x>y)-(x<y) is the sign of the difference, no?
strager
Elevation is either down (-1), none (0) or up (+1), so yes.
LiraNuna
`a x=pred.fromEnum.compare x`... but that doesn't really save any characters...
ephemient
`a x y = signum$x-y` `a x = signum.(x-)` `a = (signum.).(-)`
Tordek
you can move the `|`'s to their own lines to shorten the code (in `a`).
trinithis
+13  A: 

Perl (94 characters)

144 characters originally by barnaba:

chop($_=<>);$l=length;push(@a," "x$l)for(1..$l*2);$l+=(ord $p<=>ord $_),substr($a[$l],$r++,1)=$p=$_ for(split //);/^\s+$/||print "$_\n" for(@a)

121 characters from optimization by Chris Lutz:

$_=<>;chop;$a[@a]=" "x$l for 1..($l=length)*2;$l+=$p cmp$_,substr($a[$l],$r++,1)=$p=$_ for split//;/\S/&&print"$_\n"[email protected]

94 characters from further optimization:

$_=<>;@a=($"x($l=y///c).$/)x(2*$l);s/./substr$a[$l+=$"cmp$&],"@-",1,$"=$&/ge;/\S/&&print [email protected]

Note that in traditional Perl golf, one usually adds the number of switches and the length of the code (which would help here by a few strokes), but here we're using stand-alone programs with no switches.

Some of those parenthesis and spaces can be cut quite easily.
Chris Lutz
Thank you for the edit. Good job and I learned few things about perl :-)
No problem. You don't have much to learn - your approach turned out shorter than mine even before we optimized yours. I hope there's yet another approach we might be able to use to make this shorter still, because if the Ruby solution gets much smaller we won't be able to catch up.
Chris Lutz
Bravo, A. Rex! I don't know why I forgot about `$"` and friends.
Chris Lutz
I optimized it more using golf tricks: `y///c` instead of `length`, `$"` instead of `" "`, list context `x` instead of the first for loop, four-argument version of `substr`, `$"` again to avoid a space, `s/.//ge` to replace the for over `split//` and to avoid `chop`.
A. Rex
I think my favorite part is the `s/./CODE/ge` instead of `CODE for split//`. =)
A. Rex
I agree. I'll have to remember the `s/./CODE/ge/` trick. What's better is that, with the right regex in the first part, you can replace almost any `for split` loop with it. I knew there was a reason I liked the `/e` switch.
Chris Lutz
If it saves enough, you can have a standalone program using switches by starting with `#!perl -switches\n` :) It doesn't have to be a valid shebang line to the OS; perl will find the switches itself as long as the line contains `#!` and `perl`. Of course, it doesn't look like the final version needs it :)
hobbs
+70  A: 

x86 machine code (37 bytes)

Hexdump:

6800B807BF8007BE8200B40EAC3C0D741338D8740A720481EF400181C7A000AB86C3EBE8C3

Run in MS-DOS with 50 line console, the input is taken from the command line.

E.g.

wave.com 1234567890qwertyuiopasdfghjklzxcvbnm

Download binary here

Update: Shaved off three bytes thanks to jrandomhacker

Jonas Gulle
Source code: http://pastie.org/605198
LiraNuna
You clearly won, why is this not the first answer???
Loren Pechtel
Nice. You can shave off 3 more bytes by deleting the `JMP` instruction at offset 0x1b, and changing the previous `SUB al,0xa0` to `SUB al,0x140` so that it "absorbs" the following `ADD`.
j_random_hacker
Nice, feel free to patch it :) It's community wiki
Jonas Gulle
@Jonas Gulle: Some people dislike it when others touch their entries.
LiraNuna
@LiraNuna: That's true, but those people probably don't belong here. ;)
gnovice
Isn't measuring the length of the binary kind of cheating? If you were to measure the length of the assembly source, it would be quite a bit longer.
P Daddy
@P Daddy: I think it's quite fair; I've known individuals who have memorized enough 8086 instructions to be able to read and write assembly directly in hex. OTOH this is only made possible due to DOS+COM; I bet the same thing in Linux/i386+ELF would necessarily be at least 300kB. Maybe I'll give that a shot...
ephemient
Even if one memorizes the opcodes, I don't think each assembled byte counts as one character ("The shortest code by **character** count"). In order to enter the bytes into memory, you'll have to enter them in hex, *probably* separated by spaces. Making the character count two or three times the byte count, at least. And that's given that someone wrote and tested a program purely in machine code, going by memory—OR served as a human assembler from asm source to binary code, either from memory or from a book. Questionable, at any rate.
P Daddy
@ephemient - Your ELF estimate is way high. You can make a Linux Hello World program in a little over 50 bytes if you really cut out a lot. Granted, this is more complex than Hello World, but not 299.9 kB more.
Chris Lutz
I made this entry using "copy con wave.com", no assembly source, because that would be cheating, right? According to the rules "The shortest code by character count to generate a wave from the input string."
Jonas Gulle
How did you type in 0D and the 0A separately? As far as I know, there's no way to do that from the console. ^J is ignored and ^M generates 0D and 0A.
P Daddy
@P Daddy: Hold down Alt while typing an ASCII code in decimal on the numeric keypad to generate that character. Also, I don't think your "cheating" argument holds water: a byte is a character is a byte.
j_random_hacker
Alt+13 has the same effect as Ctrl+M has the same effect as Enter. It generates 0D 0A, not 0D alone, and Alt+10 has the same effect as Ctrl+J. Nothing. I call shenanigans.
P Daddy
And a byte of compiled/assembled binary is *not* the same as a character of source.
P Daddy
@P Daddy: In fairness, I wasn't able to generate just 0x0D this way, even using `copy /b con wave.com` -- a following 0x0A is always generated too. (0x0A can be generated by itself however.) But I think the point remains that a byte is a character -- nowhere does it say that the program must be enterable via specific means (e.g. typing at a console). I'd consider compiled JVM/.NET/etc. bytecodes to be just as admissible.
j_random_hacker
"And a byte of compiled/assembled binary is not the same as a character of source." 2 things: (1) Why, because you say so? and (2) Who said anything about source? Not the OP. (But BTW, a CPU is an interpreter, and machine code is its source code.)
j_random_hacker
@Chris Lutz: You can't just directly scribble to the screen in Linux, not like this does... when I made the estimate, I was thinking about loading `ncurses`, but that's pretty dumb; a few hard-coded VT100 escape sequences for movement would be good enough.
ephemient
+4  A: 

Python 2.x, now down to 156 chars:

s=raw_input()
R=range(len(s))
m=[0]
for i in R[1:]:m+=[m[-1]-cmp(s[i],s[i-1])]
for x in range(min(m),max(m)+1):print''.join(m[i]==x and s[i]or' 'for i in R)
Anon
A: 

XQuery

(257 bytes)

declare variable$i external;let$c:=string-to-codepoints($i),$h:= for$x at$p in$c
return sum(for$x in 1 to$p let$d:=$c[$x]-$c[$x -1]return(-1[$d>0],1[$d<0]))return
codepoints-to-string(for$p in min($h)to max($h),$x at$q
in($c,10)return(32[$h[$q]!=$p],$x)[1])

Since XQuery is purely declarative, I've had to fake the input as being passed in in an external variable. Here is the command line to run this with XQSharp:

xquery wave.xq !method=text i='1234567890qwertyuiopasdfghjklzxcvbnm'

If the string was passed in as the context item, then this could be reduced further, but setting the context item to a non-node value is not supported with all XQuery implementations (and not by the XQSharp command line tool):

let$c:=string-to-codepoints(.),$h:= for$x at$p in$c return sum(for$x in 1 to$p
let$d:=$c[$x]-$c[$x -1]return(-1[$d>0],1[$d<0]))return codepoints-to-string(for$p
in min($h)to max($h),$x at$q in($c,10)return(32[$h[$q]!=$p],$x)[1])

Just 228 bytes.

Oliver Hallam
+10  A: 

Ruby: 99 bytes

r,a,q,i=[],"",99,0
gets.chars{|x|t=r[q+=a<=>x]||=""
a=x
r[q]+=" "*(i-t.size)+x
i+=1}
puts r.compact

Uncompressed:

r,a,q,i = [],"",99,0
gets.chars { |x|
  t = r[q+=a<=>x] ||= ""
  a = x
  r[q] += " "*(i-t.size)+x
  i += 1
}
puts r.compact
DigitalRoss
save 10 bypes with >>r[q]||=""<< instead of >>r[q]=""if r[q].nil?<<
glenn jackman
and initialize a=""
glenn jackman
Yeah, I figured out a few things including that first one and got it down to 109, for some reason I posted it as a second answer down below. I don't think I understood what community wiki meant or something. You are certainly right about "", it really doesn't need the first string character twice, which means we can kill off ***s*** too. Good job.
DigitalRoss
Also saved 2 bytes by bumping q within the subscript, so now < 100
DigitalRoss
+1  A: 

Perl 5.10

159 characters, most "user friendly" version:

perl -nE'chop;@l=split//;$l{$_}=$l{$_-1}+($l[$_]cmp$l[$_-1])for 0..$#l;%e=();for$x(sort{$b<=>$a}grep{!$e{$_}++}values%l){say map{$l{$_}==$x?$l[$_]:" "}0..$#l}'

The following version is 153 characters, but you can only enter one line. To enter more than one, you have to restart the program. The rules are unclear as to whether or not this is allowed, but I figured it would be best to post both versions anyway:

perl -nE'chop;@l=split//;$l{$_}=$l{$_-1}+($l[$_]cmp$l[$_-1])for 0..$#l;for$x(sort{$b<=>$a}grep{!$e{$_}++}values%l){say map{$l{$_}==$x?$l[$_]:" "}0..$#l}'

And here is a 149 character version - this one is a script rather than a shell one-liner, and also works for only one line of input, but won't continue to accept input after that first line, which is probably a good thing:

$_=<>;chop;@l=split//;$l{$_}=$l{$_-1}+($l[$_]cmp$l[$_-1])for 0..$#l;for$x(sort{$b<=>$a}grep{!$e{$_}++}values%l){say map{$l{$_}==$x?$l[$_]:" "}0..$#l}

None of these are quite as short as the Perl solution already posted, but they certainly seem to beat Python and Ruby. And besides, There's More Than One Way To Do It.

Chris Lutz
Ahem, the Ruby entry is now 122, currently beating all Perl versions.
DigitalRoss
At the time I posted, Ruby was at 179 or so. The other Perl enterer seems reluctant to trim his entry at all, so I'm taking it upon myself to do it for him.
Chris Lutz
+2  A: 

PowerShell

Am sure this can be done with much less code, if anyone wants to edit that would be excellent. I'm leaving it readable.

$v = (Read-Host).ToCharArray()
$r = @(0)
for($i = 1; $i -lt $v.length; $i++) {
    $p = $i - 1
    $r += $r[$p] + [System.Math]::Sign($v[$i] - $v[$p])
    $t = [System.Math]::Max($t, $r[$i])
    $b = [System.Math]::Min($b, $r[$i])
}
for($i = $t; $i -ge $b; $i--) {
    for($x = 0; $x -lt $r.length; $x ++) {
        if($r[$x] -eq $i) {
            $o += $v[$x]
        }
        else {
            $o += " "
        }
    }
    $o += "`n"
}
$o
spoon16
+4  A: 

Haskell, 215 characters. I'm posting this because I don't like Khoth's version at all. Just by writing in a reasonably functional style I ended up with a significantly shorter and IMO more readable program. I haven't actually tried to make it short apart from the variable names and spacing. Destructively updating an array might make it shorter than replicating spaces.

import Char    
import List    
main=getLine>>=(putStr.p)    
p s=unlines$transpose[z++(y:x)|(m,y)<-zip n s,let(x,z)=splitAt m$replicate(maximum n)' ']
    where o=map ord s
    n=scanl(+)0$map signum$zipWith(-)(tail o)o
+7  A: 

PHP (138 characters)

<?for($lc=$i=$h=0;"\n"!=$c=fgetc(STDIN);$o[$h]=sprintf("%- {$i}s%s",@$o[$h],$lc=$c),$i++)$h+=$c<$lc?-1:$c>$lc;krsort($o);echo join($c,$o);

'Readable' version:

<?
for (
    $last_ch = $i = $level = 0;
    "\n" != $ch = fgetc(STDIN);
    $out[$level] = sprintf("%- {$i}s%s", @$out[$level], $last_ch = $ch), $i++
    )
    $level += $ch < $last_ch ? -1 : $ch > $last_ch;
krsort($out);
echo join($ch,$out);
searlea
(I deleted my prior comment) -- I wasn't aware the closing ?> was optional! Learn something new every day... :-)
Jeffrey Berthiaume
Not only is the closing ?> optional, but the last semicolon is too.
ryeguy
I think you can only omit the semi-colon in the <?= ... ?> short-tag; but if you do, you can't omit the closing ?> anyway.However, I could have shaved another 4 characters by using $l instead of $lc.. making the solution 134 characters.
searlea
+2  A: 

F#, 242 characters:

let F(s:string)=(fun L->let a=Array.init(L*3)(fun _->Array.create L ' ')in Seq.fold(fun(r,p,c)n->let r=r+sign(int p-int n)in a.[r].[c]<-n;r,n,c+1)(L,s.[0],0)s;for r in a do if Array.exists((<>)' ')r then printfn"%s"(new string(r)))s.Length

With whitespace added for easier reading, it's

let F(s:string) = 
   (fun L->
    let a = Array.init (L*3) (fun _ -> Array.create L ' ') in 
    Seq.fold (fun (r,p,c) n ->
            let r = r + sign(int p-int n) in 
            a.[r].[c]<-n;
            r, n, c+1)
        (L, s.[0], 0)
        s;
    for r in a do 
        if Array.exists ((<>) ' ') r then 
            printfn "%s" (new string(r))
   ) s.Length
Brian
+1  A: 

F#, 235 characters

A completely different strategy saved a few chars compared to my other solution.

let F(s:string)=(fun L->let _,_,h=Seq.fold(fun(p,h,l)n->let r=h-sign(int n-int p)in n,r,r::l)(s.[0],0,[0])s in for r in Seq.min h..Seq.max h do printfn"%s"(new string(Array.init L (fun c->if r=h.[L-1-c]then s.[c]else ' '))))s.Length

With whitespace:

let F(s:string) = 
   (fun L->
    let _,_,h = Seq.fold (fun (p,h,l) n ->
        let r = h - sign(int n-int p) in 
        n,r,r::l) (s.[0],0,[0]) s in 
    for r in Seq.min h..Seq.max h do 
        printfn "%s" (new string(Array.init L (fun c -> 
            if r=h.[L-1-c] then s.[c] else ' ')))
   ) s.Length
Brian
+1  A: 

C# 545 byte uncompressed

using System;
using System.Linq;
class Program{
    static void Main(string[] b){
        var s = b[0];
        var t = new System.Collections.Generic.Dictionary<int, string>();
        int y=0, p=0;
        for (int i = 0; i < s.Length; i++){
            y += Math.Sign(s[i] - p);
            p = s[i];        
            if (!t.ContainsKey(y))
                t.Add(y, "");
            t[y] = t[y].PadRight(i) + s[i];
        }
        foreach (var v in t.OrderBy(a => -a.Key))
            Console.WriteLine(v.Value);
    }
}
+2  A: 

C (157 characters)

I'm stuck there for the time being. I don't think C will beat J on this one. Thanks to strager for helping trim 8 characters, though.

char*p,a[999][80];w,x,y=500;main(c){for(gets(memset(p=*a,32,79920));*p;
a[y][x++]=c=*p++)y+=*p<c,y-=*p>c;for(;++w<998;strspn(p," ")-79&&puts(p))
79[p=a[w]]=0;}

Formatted:

char *p,         /* pointer to current character (1st) or line (2nd) */
     a[999][80]; /* up to 998 lines of up to 79 characters */

w, x, y = 500;   /* three int variables. y initialized to middle of array */

main(c){
    for(gets(memset(p=*a, 32, 79920));
    /* 999 * 80 = 79920, so the entire array is filled with space characters.
     * memset() returns the value of its first parameter, so the above is
     * a shortcut for:
     *
     *     p = *a;
     *     memset(p, 32, 79920);
     *     gets(p);
     *
     * Incidentally, this is why I say "up to 998 lines", since the first
     * row in the array is used for the input string.
     *
     * **** WARNING: Input string must not be more than 79 characters! ****
     */

    *p;a[y][x++] = c = *p++)  /* read from input string until end;
                               * put this char in line buffer and in prev
                               */
        y += *p < c,          /* if this char < prev char, y++ */
        y -= *p > c;          /* the use of commas saves from using { } */

    for(;++w < 998;         /* will iterate from 1 to 998 */
    strspn(p, " ") - 79 &&
    /* strspn returns the index of the first char in its first parameter
     * that's NOT in its second parameter, so this gets the first non-
     * space character in the string.  If this is the NULL at the end of
     * the string (index 79), then we won't print this line (since it's blank).
     */
    puts(p))  /* write the line out to the screen (followed by '\n') */
        79[p = a[w]] = 0;    /* same as "(p = a[y])[79] = 0",
                              * or "p = a[y], p[79] = 0", but shorter.
                              * Puts terminating null at the end of each line
                              */
}

I didn't bother supporting input of more than 79 characters, since that would cause confusing wrap on most terminals.

P Daddy
If you're not supporting more than 79 input characters, why do you support 999 positions? They can only increment one at a time, so the range can't be larger than 80. Setting the vertical width to 99 can save you a lot of characters and, while not safe or strictly correct, will "do" for most inputs.
Chris Lutz
Most, but not all. I have to support 79 up and 79 down, plus the center, plus the input line, with makes it 160. I suppose, for efficiency, I could have made it 160, then, but 999 takes the same number of characters and takes less forethought. You're right, though, that making the height 99 would support *most* input and would save 4 characters.
P Daddy
At the beginning, you can write `char*p,...` instead of `char a[999]...`. You can write the `p=*a` inside the `memset` call, then put the `memset` call in the first part of the first `for`. You don't use x at all in your code (I think), so why not use it as the loop var? (`y=0` takes more bytes than `x;`.) In the for loop, put the ?: part in the third part of the `for` loop to save a byte.
strager
I have to say that, while your code is pretty short, it's nonstandard because it passes `int` where a pointer is expected for some library calls. I'll have to employ some of the techniques you use in my own answer to trim it down. ;P +1 still.
strager
@strager: ooh! You got some good catches. Thanks. I do use `x` (`a[y][x++]=c=*p`), but you're right that declaring another variable is cheaper than zeroing out one I already have. **put the ?: part int the `for` loop":** I had thought about moving the loop body into the third part of the `for` loop, but it doesn't actually save anything, because I still have to have a semicolon after the `for`. So I opted for less obfuscation at the same size. **"it's nonstandard":** Oh, it's horrible! Still, it's less horrid than the Morse Code challenge, I think.
P Daddy
No, you're right. I can put the ?: part in the `for` loop and leave the the `79[p=a...` part outside and save a character. I didn't see it.
P Daddy
+11  A: 

C on a VT100 terminal (76 characters)

This works in my test on FreeSBIE:

o;main(c){for(;(c=getchar())-10;o=c)printf("\33[1%c%c",c<o?66:c>o?65:71,c);}

But in order to see the output clearly, you have to run it with something like this:

clear ; printf "\n\n\n\n\n" ; echo the quick brown fox jumps over the lazy dog | ./a.out ; printf "\n\n\n\n\n"

Does this count?

P Daddy
Most Unices have a `printf` command, so you could just do `printf "\n\n\n\n\n"`.
Chris Lutz
Thanks, I put that in.
P Daddy
+1 just because it's an impressive hack, by the way.
Chris Lutz
And it might be even shorter in another language, I'm not positive.
+1  A: 

Ruby: 109 bytes, counting newline characters!!

s=gets
r,a,q,i=[],s[0,1],99,0
s.chars{|x|q+=a<=>x
a=x
t=r[q]||=""
r[q]+=" "*(i-t.size)+x
i+=1}
puts r.compact

Uncompressed:

s = gets
r,a,q,i = [],s[0,1],99,0
s.chars { |x|
  q += a<=>x
  a  = x
  t = r[q] ||= ""
  r[q]  += " "*(i-t.size)+x
  i += 1
}
puts r.compact
DigitalRoss
I get [E:\ruby]wavegolf.rbabcdefghE:/ruby/wavegolf.rb:3: undefined method 'chars' for "abcdefgh\n":String (NoMethodError)Any idea what could be wrong ?
Gerhard
Sounds like you are running 1.8.6 or earlier.
DigitalRoss
A: 

A Clojure version:


(def a "1234567890qwertyuiopasdfghjklzxcvbnm")
(defn sign [x] (cond (pos? x) 1, (neg? x) -1, :else 0))
(def cmp (cons 0 (map (comp sign compare) a (rest a))))
(def depths (loop [depth 0, remaining cmp, built []]
              (if (first remaining)
                (recur (+ depth (first remaining)) (rest remaining) (conj built depth))
                built)))
(let [top (apply min depths), bottom (apply max depths)]
  (doseq [line (range top (inc bottom)), col (range 0 (count a))]
    (if (= line (depths col))
      (print (get a col))
      (print \space))
    (if (= col (dec (count a)))
      (print \newline))))
Timothy Pratley
A: 

Scala (pre-2.8): 275 chars, when inlined and whitespace removed.

object W {
  def main(r:Array[String]){
    var(a,l,i,c,b)=(r(0),r(0).size,0,0,99999)
    val h=a.drop(1)./:(List(0)){(x,y)=>c=if(a(i)<y)c-1 else if(a(i)>y)c+1 else c;b=b min c;i+=1;c::x}.reverse
    val z=((" "*l+"\n")*l).toArray
    a./:(0){(x,y)=>z((h(x)-b)*(l+1)+x)=y;x+1}
    print(z.mkString)
  }
}
DonMac
+4  A: 

Perl, 88 characters

Now, edited to 88 characters:

$_=<>;
s/.(?=(.))/($"x40).$&.$"x(39+($1cmp$&))/ge;
@_=/.{80}/g;
{say map{chop||die}@_;redo}

Was:

$_=<>;
s/.(?=(.))/$&.$"x(79+($1cmp$&))/ge;
s/^.{40}|.{80}/$&\n/g;
print $& while /.$/gm || s/.$//gm * /\n/;

97 characters (omitting spaces). It's not that short, but I wonder if someone with more experience with PERL may be able to shorten it further. And also spot any bugs. The second line uses spaces to make a wave that falls vertically instead of horizontally, on an 80-width wrapping screen. The third line inserts linebreaks. The last line flips X/Y axes.

I'd originally wondered if the last two lines could be something like interleave(s/.{80}/g) where interleave interleaves an array of strings. But there seems not to be that function I'd hoped for. (Or is there in a library?)

Nice! I don't see the last char in the output, though. Does my system need to use `"\r\n"`-style newlines or perhaps something was lost in the `say` --> `{local $/="\n";print}` translation (for my v5.8)?
mobrule
Thanks. I don't know. I think it definitely relies on having one or two blank characters at the end of the input string that aren't '\n', but I've not thought it through. It may depend on the exact input string, whether the last character is printed above or below the first. (Or even miss more characters -- I've not properly tested it.) Adding 's' flag at the end of the first regex fixes it in some situations where there's a trailing '\n', but ideally it should work even if there isn't trailing input.
+2  A: 

Perl, 85 chars with switches, 96 without

Invoke with   -F// -an   switches

$q=$"x([email protected]);$,=$/;for(@F){/
/&&[email protected];substr($O[$n+=$*cmp$_]|=$q,$i++,1)=$_;$*=$_}

There is a newline in between the 2nd and 3rd slash characters. Without switches you can do

$q=$"x([email protected]=split//,<>);$,=$/;for(@C){/
/&&[email protected];substr($O[$n+=$*cmp$_]|=$q,$i++,1)=$_;$*=$_}
mobrule
+1  A: 

Groovy (195 chars)

test

s="1234567890qwertyuiopasdfghjklzxcvbnm"

short

=(s=~/./).collect{(char)it}
e=' ';x=0;l=[];u=[]
w.eachWithIndex({it,n->
if(l.size()>x){l[x]+=e*(n-u[x]-1)+it;u[x]=n}else{l+=e*n+it;u+=n}
if(w[n+1]>it)x++else x--;})
l.reverse().each({println it})
codedevour
+1  A: 

PHP: 108 chars

<?while(-1<$a=fgetc(STDIN)){$d+=$a<$b^-($a>$b);$r[$d].=' ';$r[$d][$k++]=$b=$a;}ksort($r);echo join("\n",$r);

Readable version:

<?
while(-1<$a=fgetc(STDIN)){
  $d+=$a<$b^-($a>$b);
  $r[$d].=' ';
  $r[$d][$k++]=$b=$a;
}
ksort($r);
echo join("\n",$r);
runish
A: 

Golfscript - 65 chars

' ': :c;1/:a,.+,{:N;a,a{:@c<[email protected]:c<-.N=[ c]\=}%.[n+'']\$-1= ==\;}%

Generate the wave line by line

{:N;a,a{:@c<[email protected]:c<-.N=[ c]\=}%

Filter out the blank lines

.[n+'']\$-1= ==\
gnibbler