41
votes

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

7
  • Just curious what does the rosetta-stone have to do with this?
    – jdelator
    Sep 3, 2009 at 23:40
  • 4
    From another question's comment: "If you want as many answers, in as many languages as possible, you could add the tag [rosetta-stone]"
    – LiraNuna
    Sep 3, 2009 at 23:47
  • 7
    @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. Sep 4, 2009 at 0:01
  • 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.
    – recursive
    Sep 4, 2009 at 0:04
  • 2
    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? Sep 4, 2009 at 18:20

33 Answers 33

76
votes

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

15
  • 4
    @Jonas Gulle: Some people dislike it when others touch their entries.
    – LiraNuna
    Sep 4, 2009 at 9:44
  • 7
    @LiraNuna: That's true, but those people probably don't belong here. ;)
    – gnovice
    Sep 4, 2009 at 14:43
  • 41
    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
    Sep 4, 2009 at 19:18
  • 8
    @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
    Sep 4, 2009 at 21:01
  • 9
    "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.) Sep 5, 2009 at 4:50
40
votes

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.])
8
  • 5
    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
    Sep 3, 2009 at 22:29
  • 6
    that doesn't even look like a language so much as yosemite sam shouting at bugs bunny.
    – Jason
    Sep 3, 2009 at 23:50
  • 29
    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?
    – Alex
    Sep 4, 2009 at 0:06
  • 4
    @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
    Sep 4, 2009 at 21:17
  • 7
    I think that's what's called an orgicon (an emoticon orgy).
    – P Daddy
    Sep 5, 2009 at 1:05
35
votes

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

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

6
  • 1
    @strager: no kidding, it's longer than the my answer (if you count just the code and not the boilerplate).
    – ephemient
    Sep 3, 2009 at 22:36
  • 1
    The question was enough of a joke by itself without a totally offtopic response.
    – deft_code
    Sep 3, 2009 at 23:29
  • 1
    +1: shortest answer so far. -1: puts "a 'wave' from the input string." is far shorter.
    – dbr
    Sep 4, 2009 at 14:09
  • 1
    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
    Sep 5, 2009 at 17:39
  • 2
    Console.Write("a 'wave' from the input string."); ;)
    – tim
    Sep 24, 2009 at 12:38
14
votes

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.

8
  • Some of those parenthesis and spaces can be cut quite easily.
    – Chris Lutz
    Sep 4, 2009 at 0:30
  • Thank you for the edit. Good job and I learned few things about perl :-)
    – Barnaba
    Sep 5, 2009 at 1:41
  • 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
    Sep 5, 2009 at 1:45
  • Bravo, A. Rex! I don't know why I forgot about $" and friends.
    – Chris Lutz
    Sep 5, 2009 at 22:09
  • 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
    Sep 5, 2009 at 22:09
12
votes

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?

2
  • Most Unices have a printf command, so you could just do printf "\n\n\n\n\n".
    – Chris Lutz
    Sep 5, 2009 at 0:55
  • And it might be even shorter in another language, I'm not positive.
    – Jack V.
    Sep 24, 2009 at 15:40
11
votes

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.

2
  • Didn't think the space was important. 166 chars without the space.
    – ACoolie
    Sep 3, 2009 at 22:10
  • It is because else you don't compare apples to apples.
    – LiraNuna
    Sep 3, 2009 at 22:13
10
votes

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
3
  • 1
    save 10 bypes with >>r[q]||=""<< instead of >>r[q]=""if r[q].nil?<< Sep 14, 2009 at 1:17
  • 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. Sep 14, 2009 at 3:47
  • Also saved 2 bytes by bumping q within the subscript, so now < 100 Sep 14, 2009 at 4:24
7
votes

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);
3
  • 1
    (I deleted my prior comment) -- I wasn't aware the closing ?> was optional! Learn something new every day... :-) Sep 4, 2009 at 16:43
  • Not only is the closing ?> optional, but the last semicolon is too.
    – ryeguy
    Sep 24, 2009 at 15:09
  • 2
    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
    Sep 25, 2009 at 17:30
6
votes

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

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
1
  • Does not work on 321. (putStr.p) and (y:x) do not need brackets.
    – sdcvvc
    May 11, 2012 at 18:27
5
votes

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);}
9
  • 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) Sep 3, 2009 at 22:41
  • 1
    @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
    Sep 3, 2009 at 22:44
  • 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.
    – ephemient
    Sep 3, 2009 at 22:48
  • 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
    Sep 3, 2009 at 22:53
  • 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.
    – P Daddy
    Sep 5, 2009 at 15:30
4
votes

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.

7
  • Needs to have I/O to fit the specifications.
    – strager
    Sep 3, 2009 at 22:17
  • 3
    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. Sep 3, 2009 at 22:19
  • 1
    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? Sep 3, 2009 at 22:24
  • 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
    Sep 3, 2009 at 22:31
  • 7
    No, the most fair way it to just ask for a function. Sep 3, 2009 at 22:37
4
votes

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)=$_;$*=$_}
3
votes

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)
5
  • (x>y)-(x<y) is a short way to compare elevation.
    – LiraNuna
    Sep 3, 2009 at 22:37
  • (x>y)-(x<y) is the sign of the difference, no?
    – strager
    Sep 3, 2009 at 22:57
  • Elevation is either down (-1), none (0) or up (+1), so yes.
    – LiraNuna
    Sep 3, 2009 at 23:13
  • you can move the |'s to their own lines to shorten the code (in a). Jun 13, 2010 at 16:14
  • heightDiff x y = signum $ x-y, or a x=signum.(x-). You can save characters by inlining this.
    – sdcvvc
    May 10, 2012 at 4:21
3
votes

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

2
  • 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)?
    – mob
    Sep 27, 2009 at 6:16
  • 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.
    – Jack V.
    Sep 28, 2009 at 9:33
2
votes

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

1
  • You can save 7 characters by not making P static. Oct 25, 2009 at 0:29
2
votes

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
2
votes

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
0
2
votes

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.

6
  • 2
    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
    Sep 5, 2009 at 0:15
  • 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
    Sep 5, 2009 at 0:41
  • 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
    Sep 5, 2009 at 1:56
  • 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
    Sep 5, 2009 at 1:58
  • @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
    Sep 5, 2009 at 3:05
1
vote

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);
   }
  }
 } 
}
0
1
vote

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]:' ');}}
5
  • args can be rewritten as a or something. Also, can't you define i, r, and c along with M and X?
    – strager
    Sep 3, 2009 at 22:16
  • 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;" Sep 4, 2009 at 0:01
  • Console.WriteLine() can also be replaced with Console.Write('\n') Sep 4, 2009 at 0:11
  • Pulling I.Length into a variable saves a lot of space Sep 4, 2009 at 0:15
  • 3
    Uh, isn't WriteLine() exactly the same length as Write('\n')? :-)
    – Alec
    Sep 5, 2009 at 17:41
1
vote

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.

2
  • 1
    Ahem, the Ruby entry is now 122, currently beating all Perl versions. Sep 4, 2009 at 14:43
  • 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
    Sep 4, 2009 at 23:37
1
vote

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   
1
vote

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

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
2
  • 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 ?
    – Gerhard
    Jun 29, 2010 at 11:35
  • Sounds like you are running 1.8.6 or earlier. Jun 30, 2010 at 8:58
1
vote

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

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

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= ==\
1
vote

ASL: 73

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

I just translated the J solution into ASL.

0
votes

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.

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