Code Golf: The wave

Question

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).

Testudinal

Just curious what does the rosetta-stone have to do with this? – Magnificent

From another question's comment: "If you want as many answers, in as many languages as possible, you could add the tag [rosetta-stone]" – Testudinal

@jdelator, it implies submission is welcome and sought from as many languages as possible. Refers to the original 'rosetta stone' not Apple's implementation of the same-named code. – Cerebritis

This is taken from here: golf.shinh.org/p.rb?wave+line Check that site out for solutions that blow the pants off these comparatively amateur hack jobs. – Xenolith

"comparatively amateur hack jobs"? The J solution blows /those/ up! – Testudinal

I should have put a smiley in. :) – Xenolith

Some of those shinh.org waves are small, for sure. There are two Ruby waves there both scoring a really impressive sub-80 bytes. However, each one has at least two problems, one even producing wrong output. Mine may be 122 bytes but I would argue that it is most certainly not the amateur hack job. You know, because it, uhh, works? – Gutsy

Answer 1

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

Yolande

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. – Utu

@Jonas Gulle: Some people dislike it when others touch their entries. – Testudinal

@LiraNuna: That's true, but those people probably don't belong here. ;) – Tram

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. – Ftc

@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... – Velites

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. – Ftc

@Velites - 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. – Hanlon

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." – Wolverine

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. – Ftc

@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. – Utu

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. – Ftc

And a byte of compiled/assembled binary is not the same as a character of source. – Ftc

@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. – Utu

"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.) – Utu

@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. – Velites

Answer 2

J

54 characters, if you let the interpreter handle input/output.

e=:|:@((#&' '@],[)"0[:(-<./)0,[:+/\[:(}:(>-<)}.)a.i.])

65 to explicitly read from stdin and write to stdout.

(|:((#&' '@],[)"0[:(-<./)0,[:+/\[:(}:(>-<)}.)a.&i.)~1!:1[3)1!:2[4

   e '1234567890qwertyuiopasdfghjklzxcvbnm'
                             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

   e '31415926535897932384626433832795028841971693993751058209749445923078164062862'
            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

---

   NB. Look up ASCII codes
   ord =: a. i. ]
   ord 'p4ssw0rd'
112 52 115 115 119 48 114 100

   NB. Going up?
   up =: }: < }.
   up ord 'p4ssw0rd'
0 1 0 1 0 1 0

   NB. Going down?
   down =: }: > }.
   down ord 'p4ssw0rd'
1 0 0 0 1 0 1

   NB. Combine to get ±1
   updown =: }: (> - <) }.
   updown ord 'p4ssw0rd'
1 _1 0 _1 1 _1 1

   NB. Start with 0, follow up with partial sums
   sum =: 0 , +/\
   sum updown ord 'p4ssw0rd'
0 1 0 0 _1 0 _1 0

   NB. Subtract the minimum to get sequence with base at 0
   fix =: - <./
   fix sum updown ord 'p4ssw0rd'
1 2 1 1 0 1 0 1

   NB. For convenience, name this chain of functions
   d =: [: fix [: sum [: updown ord

   NB. Make spaces before the characters
   push =: (#&' ' @ ] , [)"0 d
   push 'p4ssw0rd'
 p
  4
 s
 s
w
 0
r
 d

   NB. Turn it on its side
   |: push 'p4ssw0rd'
    w r
p ss 0 d
 4

   NB. Combine into one named function…
   e =: |: @ push
   NB. …and inline everything
   e =: |:@((#&' '@],[)"0[:(-<./)0,[:+/\[:(}:(>-<)}.)a.i.])

Velites

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

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. – Bemuse

that doesn't even look like a language so much as yosemite sam shouting at bugs bunny. – Duad

looks like you're just making a bunch of smileys. let me have a try at J: :(:[[[:(:o:pO_O&i-:)$$. Did I make a program? – Divinize

I don't even see the code anymore. All I see now is blonde, brunette, redhead... – Ftc

@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. – Velites

I think that's what's called an orgicon (an emoticon orgy). – Ftc

J is similar to a language called APL (which stands for A Programming Language of course!) wikipedia has a good entry on it. – Dalessio

Answer 3

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

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

Adelina

@strager: no kidding, it's longer than the my answer (if you count just the code and not the boilerplate). – Velites

The question was enough of a joke by itself without a totally offtopic response. – Jaipur

+1: shortest answer so far. -1: puts "a 'wave' from the input string." is far shorter. – Hecto

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. :-) – Stretcher

@Alec: It won't compile, but it will run as is in Snippy: csharpindepth.com/Downloads.aspx – Ftc

Console.Write("a 'wave' from the input string."); ;) – Rizo

Answer 4

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"for@a

94 characters from further optimization:

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

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.

Jokjakarta

Some of those parenthesis and spaces can be cut quite easily. – Hanlon

Thank you for the edit. Good job and I learned few things about perl :-) – Jaban

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. – Hanlon

Bravo, A. Rex! I don't know why I forgot about $" and friends. – Hanlon

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. – Jokjakarta

I think my favorite part is the s/./CODE/ge instead of CODE for split//. =) – Jokjakarta

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. – Hanlon

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 :) – Castellated

Answer 5

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?

Ftc

Most Unices have a printf command, so you could just do printf "\n\n\n\n\n". – Hanlon

And it might be even shorter in another language, I'm not positive. – Tarnation

Answer 6

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.

Festschrift

Didn't think the space was important. 166 chars without the space. – Festschrift

It is because else you don't compare apples to apples. – Testudinal

Answer 7

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

Gutsy

save 10 bypes with >>r[q]||=""<< instead of >>r[q]=""if r[q].nil?<< – Ockeghem

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. – Gutsy

Also saved 2 bytes by bumping q within the subscript, so now < 100 – Gutsy

Answer 8

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);

Juieta

(I deleted my prior comment) -- I wasn't aware the closing ?> was optional! Learn something new every day... :-) – Karyogamy

Not only is the closing ?> optional, but the last semicolon is too. – Spooky

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. – Juieta

Answer 9

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)

Womb

Answer 10

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

Keli

Does not work on 321. (putStr.p) and (y:x) do not need brackets. – Ottar

Answer 11

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);}

Porty

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) – Stedman

@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. – Velites

Of course, given the limited range of the characters to be given, (c=getchar())&' ' would be an easy way to prevent the newline from getting into the mix too. – Velites

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. – Porty

You can combine the putchars 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. – Ftc

Even better, instead of *l[v]?putchar(c<r?32|l[v][c]:10):0, make it *l[v]&&putchar(c<r?32|l[v][c]:10), saving 1 more character for a total of 149. – Ftc

@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...) – Porty

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. – Ftc

@ephemient, much thanks, Ctrl-D twice (On Linux) did the trick. – Stedman

Answer 12

Perl, 85 chars with switches, 96 without

Invoke with   -F// -an   switches

$q=$"x($n=@F);$,=$/;for(@F){/
/&&print@O;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($n=@C=split//,<>);$,=$/;for(@C){/
/&&print@O;substr($O[$n+=$*cmp$_]|=$q,$i++,1)=$_;$*=$_}

Downing

Answer 13

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.

Metalliferous

Needs to have I/O to fit the specifications. – Porty

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. – Metalliferous

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? – Metalliferous

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. – Porty

No, the most fair way it to just ask for a function. – Metalliferous

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. – Divinize

Maybe "fair" was the wrong word. Perhaps "focused" would be better. – Metalliferous

Answer 14

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?)

Tarnation

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)? – Downing

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. – Tarnation

Answer 15

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)

Unbound

(x>y)-(x<y) is a short way to compare elevation. – Testudinal

(x>y)-(x<y) is the sign of the difference, no? – Porty

Elevation is either down (-1), none (0) or up (+1), so yes. – Testudinal

you can move the |'s to their own lines to shorten the code (in a). – Simpkins

heightDiff x y = signum $ x-y, or a x=signum.(x-). You can save characters by inlining this. – Ottar

Answer 16

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.

Ftc

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. – Hanlon

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. – Ftc

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. – Porty

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. – Porty

@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. – Ftc

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. – Ftc

Answer 17

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

Bellerophon

Answer 18

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

Lovely

Answer 19

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);}}

Mitzimitzie

You can save 7 characters by not making P static. – Shriver

Answer 20

ASL: 73

args1[,;{ch},1_]@1]o o>:><-0 0a:/+,/&-;{()@:'{" "`}}@;{};;{(){`}#`}" ":|P

I just translated the J solution into ASL.

Gattis

Answer 21

Golfscript - 65 chars

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

Generate the wave line by line

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

Filter out the blank lines

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

Wane

Answer 22

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);

Saccharify

Answer 23

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})

Frankhouse

Answer 24

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

Gutsy

I get [E:\ruby]wavegolf.rb abcdefgh E:/ruby/wavegolf.rb:3: undefined method 'chars' for "abcdefgh\n":String (NoMethodError) Any idea what could be wrong ? – External

Sounds like you are running 1.8.6 or earlier. – Gutsy

Answer 25

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);
    }
}

Anklebone

Answer 26

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   

Bellerophon

Answer 27

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.

Hanlon

Ahem, the Ruby entry is now 122, currently beating all Perl versions. – Gutsy

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. – Hanlon

Answer 28

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]:' ');}}

Mourant

args can be rewritten as a or something. Also, can't you define i, r, and c along with M and X? – Porty

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;" – Orianna

Console.WriteLine() can also be replaced with Console.Write('\n') – Orianna

Pulling I.Length into a variable saves a lot of space – Orianna

Uh, isn't WriteLine() exactly the same length as Write('\n')? :-) – Stretcher

Answer 29

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);
   }
  }
 } 
}

Setscrew

Answer 30

Haskell, 170

main=getLine>>=putStr.p
p s=unlines[[if m==i then c else ' '|(m,c)<-zip n s]|i<-[minimum n..maximum n]]
 where o=map fromEnum s;n=scanl(+)0$map signum$zipWith(-)o$tail o

168 if you join two last lines. Based on Greg M's solution.

Ottar

Answer 31

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)
  }
}

English

Answer 32

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))))

Lacker

Answer 33

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.

Orianna