text:
Yarr! A map to the hidden treasure!
Introduction
"Yarr!! We had a laddie who called himself a "programmer" make a map t' our hidden treasure! But 'tis written wit' weird numbers 'n letters! "E5, N2, E3"... what does it even mean? Madness! Can't even scribe a proper treasure map, t' useless cretin. Fix it fer us! We'll gift ye a share o' t' treasure!"
Challenge Description
A group of pirates are having trouble reading a treasure map. Can you write a program to convert it into a more... piratey form?
As input, you'll receive the original treasure map. It's a list of comma separated strings, each string which consists of a letter portion (which tells the pirates which direction they need to walk in), and a number portion (which tells the pirates how many steps to take in that direction). For instance, the following treasure map:
E2,N4,E5,S2,W1,S3

would mean, "walk two steps to the east, walk four steps to the north, walk five steps to the east, walk two steps to the south, walk one step to the west, then walk three steps to the south."
As output, you'll output the map in a graphical form, using the characters >, ^, v, and < as pointers. Here's the output for the above input:
  >>>>>v
  ^    v
  ^   v<
  ^   v
>>^   X

Notice that we've replaced the last step to the south with an X instead. This is because the last step is where the treasure is, and as we all know, pirates must have an X on their treasure maps, otherwise they won't know how to read it.
By the way, the map won't ever cross itself, so you don't need to worry about dealing with overlaps. Also, you are allowed to have a trailing new line at the end of the output.
Sample Inputs and Outputs
S5,W2

 v
 v
 v
 v
 v
X<

N1,E1,S1,E1,N1,E1,S2

>v>v
^>^X

N1

X

N6,E6,S6,W5,N5,E4,S4,W3,N3,E2,S2,W1,N2

>>>>>>v
^>>>>vv
^^>>vvv
^^^Xvvv
^^^^<vv
^^^<<<v
^^<<<<<

E21,S2

>>>>>>>>>>>>>>>>>>>>>v
                     X

N12,E11,S12,W2,N4

>>>>>>>>>>>v
^          v
^          v
^          v
^          v
^          v
^          v
^          v
^          v
^        X v
^        ^ v
^        ^ v
^        ^<<

Are we allowed to have trailing spaces on each line? Is the number always going to be less than ten?

@vihan You are not allowed to have trailing spaces on each line. The number is not always going to be less than ten.

@Sp3000 The number of steps can be more than one digit. I added a new test case for more than one digit steps.

@Sp3000 Leading spaces before lines are allowed (for some of the inputs, some of the lines need to be "padded" with spaces). Leading spaces after lines are not allowed. Leading spaces after or before the whole grid are allowed.

I really think the X should mark the step after the last move, like all other moves are counted. Imagine the last step is N3: you walk three steps to the north and dig, but there is nothing here, you had to walk 2 steps instead. I don't mind if you keep the existing rule, because it adds a little corner case to handle. But remember what happened to that laddie.

@coredump Or maybe we want to mislead the pirates, so that we can take the treasure for ourselves ;)
No, you're correct, the pirates are digging one step too soon. Given there are already three answers, I'll keep the rule as it is to avoid invalidating existing solutions.

Is there any limit to how long a certain direction will be?

@BassetHound There's no limit, but you don't need to handle integer overflow or anything like that.

What kind of pirates can't follow a compass? I don't think I'll be sailing with them anytime soon.

@jpmc26 Well, these pirates don't know much of the alphabet... they spent the last few years at C :)

Can we store the output in a global variable after the function is called? (to avoid having to return) Sorry if there is a standard rule for that or something, I'm new at this...

The fourth example is just trolling the pirates...

@UndefinedFunction No, you need to return a value.

Ruby, 213 209 198 186 178
M={};x=0,m=q=0
gets.scan(/.(\d+)/){?1.upto($1){m,y=x
x[d=$&.ord%10%7-2]+=1|($u=M[y]||={})[m]=d
m<q&&q=m}}
$u[m]=2
puts M.sort.map{|_,b|(q..b.max[0]).map{|k|">vX <^"[b[k]||3]}*""}

Pass input via stdin.
This uses a y -> x -> char dictionary to construct the map, where both x and y can be negative. Once the input has been parsed, the global minimum of the x coordinate is extracted. For each row, it then iterates over a range going from the global minimum to the maximum index for the current line, and prints the correct character for that index.
To stay with the theme, the expressions to turn NESW into the proper indices were shamelessly pirated from Sp3000's answer.
Original version that used a [x,y] -> char dictionary:
M={};x=0,0
gets.scan(/.(\d+)/){(?1..$1).map{x[d=$&.ord%10%7-2]+=1|M[$y=x+[]]=d}}
M[$y]=2
a,*q=M.minmax.flatten
M.map{|(x,y),v|($*[y-M.map{|a,|a[1]}.min]||=?\s.*q[2]-a)[x-a]=">vX<^"[v]}
puts$*.map &:rstrip

Python 2, 249 248 244 239 237 bytes
D={}
m=X=Y=0
for s in input().split(","):d=ord(s[0])%10%7;exec"a,b=X,Y;E=D[Y]=D.get(Y,{});E[X]='<^>v'[d];m=min(m,X);%c+=d-2|1;"%(88+d%2)*int(s[1:])
D[b][a]="X"
for Y in sorted(D):print"".join(D[Y].get(n," ")for n in range(m,max(D[Y])+1))

Input like "E2,N4,E5,S2,W1,S3".
NSEW is mapped to [1, 3, 2, 0] by d=ord(c)%10%7. Whether to change y or x is then decided by d%2, and whether to increment or decrement is decided by d-2|1. The first and third expressions were found by brute force.
Other than that, it's a simple usage of a nested dictionary of the form {y: {x: char}}.
(Thanks to @joriki for help with mapping)

(d + 1 & 2) - 1

@joriki Ah that's a nice expression - thanks!

Here's some code I wrote (in a different context) for finding simple expressions for integer functions. I didn't use it for this, but just thought that it might be interesting for you. (The relevant code starts where it says "This is the code that I used to optimize the encoding".)

@joriki Brute forcing's a great idea - just turned up 1|d%-3 (which is the negation, but I just realised that's okay too)!

Javascript (ES6), 260
This was an interesting one...
Thanks @ETHproductions, @edc65, and @vihan for the help!
s=>{z=o=""
m=[]
q=x=y=2e3
s.split`,`.map(v=>z+=v[0].repeat(+v.slice(1)))
for(i=0;d=z[i];q=x<q?x:q)(m[y]=m[y]||[])[x]=z[++i]?d=="N"&&--y?"^":d=="S"&&++y?"v":d=="W"&&--x?"<":++x?">":o:"X"
m.map(a=>a.map((b,j)=>o+=" ".repeat(-p-1+(p=j))+b,p=q-1,o+=`
`))
return o}

This defines an anonymous function, so to call it add f= to the beginning to give it a name.
To test: console.log(f("E2,N4,E5,S2,W1,S3"))
Explanation:
s=>{ //define function w/ parameter s
z=o=""      //z=modified input, o=final output
m=[]        //map of characters
q=x=y=2e3   //q=minimum value of x; x+y=coordinates. These start high to leave room to go backwards
s.split`,`.map(v=>z+=v[0].repeat(+v.slice(1)))    //change "N3,E4" -> "NNNEEEE", and put in z
for(i=0;d=z[i];q=x<q?x:q)   //for each direction d in z, while updating q:
    (m[y]=m[y]||[])[x]=     //in the right place on the map, put:
        z[++i]?                 //if last character of z, "X"
            d=="N"&&--y?"^":
            d=="S"&&++y?"v":    //otherwise get the right character and change x+y accordingly
            d=="W"&&--x?"<":
            ++x?">":o
        :"X"
m.map(a=>a.map((b,j)=>o+=" ".repeat(-p-1+(p=j))+b,p=q-1,o+=`
`)) //dump map to o, with correct padding
return o}   //return

That's an nice way to separate statements! It's certainly much more readable than putting everything on one line and separating them with semicolons. If I may offer my suggestion: you could save a byte by moving your i++ from the for loop to the last place it's used, in this case c=i++>r-2?"X":c.

Also, since you're using ES6, I would suggest using v[0].repeat(+v.slice(1)) in place of Array(v.slice(1)- -1).join(v[0]), and " ".repeat(j-p-1) in place of Array(j-p).join(" "), saving 11 bytes overall. I think you could also place F='forEach' at the beginning of the function, then change each .forEach from there on to [F], saving another 4.

@ETHproductions Thanks! It's down to 347!

Update: moving the F="forEach" declaration to the first place it is used saved another 2.

Try using .map instead of .forEach. It's so short you should not even shorten it to F

@edc65 Nice. Down to 317! Think it's about as golfed as it's going to get...

@UndefinedFunction you might want to use shorthands for the ifs, it might help if you decrement variables at the same time also

@vihan Down to 263! I changed the ifs to ternary, but couldn't figure out how to shorten it by incrementing or decrementing variables at the same time. If you could point out how, that would be nice. Thanks!

If my understanding is correct, does q=x=y=2e3 mean that the output would be incorrect if I did, say, W9999?

@Sp3000 easily solved at no cost ... 2e5 ... 2e9 ? The output string is limited anyway

@Sp3000 Correct, the program wouldn't work correctly in that case. However, as edc65 mentioned in theory this could be replaced with 9e9 at no cost. (I used 2e3 to make it run faster, although up to 9e5 seems to run reasonably quickly on my computer)

PHP, 431 417 bytes
$g=explode(',',$argv[1]);$x=$y=$a=$b=$c=$d=$e=$f=0;
foreach($g as$i=>$h){list($k,$l,$m)=
    ['N'=>[-1,0,'^'],'E'=>[0,1,'>'],'S'=>[1,0,'v'],'W'=>[0,-1,'<']][$h[0]];
    for($s=substr($h,1);$s--;){$z[$f=$y][$e=$x]=$m;$y+=$k;$x+=$l;}
    if($i==count($g)-1){$x=$e;$y=$f;}
    $a=min($a,$x);$b=max($b,$x);$c=min($c,$y);$d=max($d,$y);
}$z[$y][$x]='X';for($y=$c;$y<=$d;$y++)
{$o='';for($x=$a;$x<=$b;$x++)$o.=$z[$y][$x]?:' ';echo rtrim($o)."\n";}

Put it into a file (treasure.php), remove the indentation, join the lines (it is wrapped here for readability), put the <?php marker at the beginning of the file (not displayed here as it is technically not a part of the program).
Example of execution:
$ php -d error_reporting=0 treasure.php E2,N4,E5,S2,W1,S3
  >>>>>v
  ^    v
  ^   v<
  ^   v
>>^   X
$

The option -d error_reporting=0 is needed to suppress notices about values not found at specified indices in $z.
Update:
While I was preparing the ungolfed version of the code for posting I discovered it contained two unneeded assignments (12 bytes) and a whitespace that can be removed(as$i); also, by replacing a while with a for loop and squeezing an assignment into it (not possible using the while loop) I saved another byte.

I would love to see an ungolfed version.

@LarsEbert I updated the answer with a link to the ungolfed code. I checked your solution now (didn't do it before); we have basically used the same algorithm. Yours handles the last step better than mine. I can strip 25 more bytes if I implement $count --;.

$argn save 3 Bytes chop save 1 Byte "X" -> X use constants save more bytes

@JörgHülsermann I don't get the $argn hint. I am aware of the "X"->X trick but I probably forgot about it when I wrote this solution. I write PHP code since 2002 but until today I didn't notice that PHP provides the chop() function. Thank you for this hint.

Perl, 702 613 546 474 439 338 260 bytes
Thanks to Dom Hastings for his help and his supergolfed version.
The code uses a 2D array.
Version by Dom Hastings:
$x=$y=$a=$b=99;map{/^./;$a=($c=$x)<$a?$x:$a,$A=$x>$A?$x:$A,$b=($C=$y)<$b?$y:$b,$B=$y>$B?$y:$B,$q[$c][$C]={split'','W<E>N^Sv'}->{$&},$x+={W,-1,E,1}->{$&},$y+={N,-1,S,1}->{$&}for 1..$'}split',',pop;$q[$c][$C]=X;for$y($b..$B){print$q[$_][$y]||$"for$a..$A;print$/}

My lesser golfed version of 338 bytes (for reference):
@m=split(',',pop);$x=$y=$a=$b=99;map{($d,$s)=/^(.)(.+)$/;for(1..$s){$c=$x;$C=$y;if($x<$a){$a=$x}if($x>$A){$A=$x}if($y<$b){$b=$y}if($y>$B){$B=$y}if($d eq"W"){$r="<";$x--}if($d eq"E"){$r=">";$x++}if($d eq"N"){$r="^";$y--}if($d eq"S"){$r=v;$y++}$q[$c][$C]=$r}}@m;$q[$c][$C]=X;for$y($b..$B){for$x($a..$A){$t=$q[$x][$y];print$t?$t:$"}print$/}

Test
$ perl piratemap_golf.pl E4,N3,W6,S10,W1,S1,E5,N1,W2,N6,E6,N5,W10,S1,E2
v<<<<<<<<<<
>Xv<<<<<< ^
  v     ^ ^
  v     ^ ^
  v >>>>^ ^
  v >>>>>>^
  v ^
  v ^
  v ^
  v ^
  v ^
 v< ^<<
 >>>>>^

If you aren't using use strict;, you don't need all the mys, which will save you at least a few bytes. Also == is shorter than eq since the latter requires spaces.

Thanks Alex A. for the tips. That shaved some bytes off. A replacement with == didn't work, but the space after 'eq' was indeed removable. Also the initialization of the number variables to 0 wasn't needed either.

If I'm not mistaken, you're only calling $m once, so rather than storing the command line argument as a variable, you can call it directly in split, i.e. @m=split(',',$ARGV[0]).

Thanks. In hindsight that was an obvious one that slipped in because of habbit. I now also removed the initialization of the array with the spaces, and instead default the undefined values to space when I print.

Hey @LukStorms, glad to see more Perl golfers! A few things to help save some bytes! Your $d and $s variables can be grabbed using regex to save you some bytes ($d,$s)=/^(.)(.+)$/, and all foreachs can be for (as they're the same. You might also be able to save some chars replacing some of these with map{...}@x since you can ignore the parens around the iterated item (this works well if you have to contain other loops). If you're using $ARGV[0] you can replace that with pop, but if you use the script as in perl script.pl <<< "text" you can use <> instead!

If you want to keep the script using args, you can use pop to save a couple. Instead of use Swtich and the switch/case statements, you could do individual checks which might save you bytes. Something like $y-="N"eq$d will work as well (since true 1 and false is ''). Often, you can have words as barewords, so $y-=N eq$d will work! There are some magic variables you can use to save bytes, $/ is '\n' and $" is ' ', but sometimes a literal newline might help save a char too. Another (dirty!) trick is multiple assigns to save a few more, as in $a=0;$b=0; can be $a=$b=0.

Just a few more, I promise. I hope this is the kinda info you're after! Missing off parens on function calls is a pretty standard change, so substr($_,0,1) can be substr$_,0,1. Postfix for loops and if checks can be useful too as in for(@c){...} vs. ...for@c but you can't use ; in the code, you'd have to comma separate instead (which doesn't always work when you're calling functions). There are so many great tips also at http://codegolf.stackexchange.com/questions/5105/tips-for-golfing-in-perl. Good luck!

Thanks Dom for all those usefull tips. Can't believe how many bytes could still be shaved off like that. And I still have to look into that map and the postfix loop, but even then it trimmed down from 546 to 474 bytes!

I got rid of 101 bytes by assuming that pirates don't like to walk to far in north or west direction.  So now the code doesn't have to go 2 times through the moves array.

@LukStorms I worked on golfing this a bit more as I was enjoying the golf action! I got it down to 262 still using your main routines/approach. I wanted to share with you to review and see if there were any helpful snippets that weren't included in the Perl tips thread or anything: https://gist.github.com/anonymous/956afef36c14efec0e85
Happy to remove this if it's not appropriate!

Amazing. I thought I reached the limit of what could be done via the 2D array. And I had to ungolf your code just to grasp the tricks you used. Well done.  I changed the post accordingly.

@Dom. Your version in the post has 2 less bytes now. Using a FOR instead of a MAP at the end turned out to be smaller in this case.

Awesome! I hope some of those techniques were useful! I'm glad to be able to share! I probably should have provided more explanation with each of them, sorry about that... I do hope it was interesting though! Good spot on for vs. map too!

Python 2, 394 bytes
Run the program then paste into standard input as e.g. "E2,N4,E5,S2,W1,S3"
m=input().split(',')
def f(x,y,h,o,s=[]):
 for c in m:
  for _ in range(int(c[1:])):
   a,b,l={'E':(1,0,'>'),'W':(-1,0,'<'),'N':(0,1,'^'),'S':(0,-1,'v')}[c[0]]
   if o:o[h-y][x]=l
   s+=[(x,y)];x+=a;y+=b
 if o:o[h-y+b][x-a]='X'
 return s
p,q=zip(*f(*[0]*4))
w,h=max(p)-min(p),max(q)-min(q)
o=[[' ']*-~w for _ in range(h+1)]
f(-min(p),-min(q),h,o)
print'\n'.join(["".join(l).rstrip()for l in o])

This is not very optimized. First it runs through the input to record the path. Then it does some math to determine the right starting position and size of o. Then it runs through again and sets the appropriate entries of o as one of >v<^X. The main cleverness is in reusing the same function for both these traversals.

PHP, 496 514 528
I tried my luck in PHP, the result is rather long, I still want to post it, just for fun.
function a($c){global$a,$b;$a[$b[1]][$b[0]]=$c;}$c=explode(',',$argv[1]);$a=[];$b=[0,0];foreach($c as$d=>$e){$f=substr($e,1);if($d==count($c)-1)$f--;for($i=0;$i++<$f;){if($e[0]==N){a('^');$b[1]--;}elseif($e[0]==E){a('>');$b[0]++;}elseif($e[0]==S){a(v);$b[1]++;}else{a('<');$b[0]--;}}}a(X);$d=$e=$f=$g=0;foreach($a as$y=>$h){$f=min($f,$y);$g=max($g,$y);foreach($h as$x=>$i){$d=min($d,$x);$e=max($e,$x);}}for($y=$f;$y<=$g;$y++){for($x=$d;$x<=$e;$x++)echo isset($a[$y][$x])?$a[$y][$x]:' ';echo "
";}

Ungolfed
<?php

    function setInMap($char) {
        global $map, $position;
        $map[$position[1]][$position[0]] = $char;
    }

    $instructions = explode(',', $argv[1]);

    $map = [];

    $position = [0, 0];

    foreach($instructions as $index => $instruction) {
        $count = substr($instruction, 1);
        if($index === count($instructions) - 1) {
            $count--;
        }
        for($i = 0; $i < $count; $i++) {
            if($instruction[0] === 'N') {
                setInMap('^');
                $position[1]--;
            } elseif($instruction[0] === 'E') {
                setInMap('>');
                $position[0]++;
            } elseif($instruction[0] === 'S') {
                setInMap('v');
                $position[1]++;
            } else($instruction[0] === 'W') {
                setInMap('<');
                $position[0]--;
            }
        }
    }
    setInMap('X');

    $minX = $maxX = $minY = $maxY = 0;
    foreach($map as $y => $row) {
        $minY = min($minY, $y);
        $maxY = max($maxY, $y);
        foreach($row as $x => $cell) {
            $minX = min($minX, $x);
            $maxX = max($maxX, $x);
        }
    }
    for($y = $minY; $y <= $maxY; $y++) {
        for($x = $minX; $x <= $maxX; $x++) {
            if(isset($map[$y][$x])) {
                echo $map[$y][$x];
            } else {
                echo ' ';
            }
        }
        echo "\n";
    }

?>

Can be reduced a lot. For instance, you can just write for(;$i++<$f;), try to remove unnecessary brackets, use undefined constants (N) instead of strings ('N'),  …

Instead of ifs, try using trenary operators or logical ands. Also, it will help if you use PHP4.1 and use a GET array with the points.

XQuery 3.0, 498
declare variable $v external;let $m:=<v>{tokenize($v,',')!(for $j in(1 to xs:int(substring(.,2)))return<c>{translate(substring(.,1,1),'NESW','^>v<')}</c>)}</v>/c!(let $p:=./preceding-sibling::c return
'])-count($p[.='<'])}" y="{count($p[.='v'])-count($p[.='^'])}">{if(./following::*)then .else'X'}
)for $y in(min(xs:int($m/@y))to max(xs:int($m/@y)))return string-join(for $x in(min(xs:int($m/@x))to max(xs:int($m/@x)))let $d:=$m[@x=$x and @y=$y]return if($d)then$d else' ','')

XQuery isn't often even slightly competitive, so this was fun.
Ungolfed
declare variable $v external;
let $map := <vector>{ tokenize($v,',') !
        (for $j in (1 to xs:int(substring(.,2)))
            return <step>{ translate(substring(.,1,1),'NESW','^>v<') }</step> )
         }</vector>/step !
            (let $path_so_far := ./preceding-sibling::step
            return <point
                x="{ count($path_so_far[.='>']) - count($path_so_far[.='<']) }"
                y="{ count($path_so_far[.='v']) - count($path_so_far[.='^']) }">
                {if(./following::*) then string(.) else 'X'}
            </point>)
for $y in (min(xs:int($map/@y)) to max(xs:int($map/@y)))
return string-join(
    for $x in (min(xs:int($map/@x)) to max(xs:int($map/@x)))
    let $d := $map[@x=$x and @y=$y]
    return if($d) then string($d) else ' '
    ,'')

JavaScript (ES6), 244 249 274
Leading spaces and newlines added for clarity and not counted, except the newline near the end in the join call, that is significant and counted.
Test running the snippet (being ECMAScript 6, Firefox and Safari 9 only)

F=m=>(
  x=y=0,p=[],
  m.replace(/\w(\d+)/g,(d,z)=>{
    for(d='NWSE'.search(d[0]);
        z--&&(p=~x?~y?p:[y=0,...p]:p.map(r=>' '+r,x=0));
        p[u=y]=(w=r.slice(0,x))+'^<v>'[d]+(v=r.slice(x+1)),
        d&1?x+=d-2:y+=d-1)
      for(r=p[y]||'';!r[x];)r+=' ';
  }),
  p[u]=w+'X'+v,
  p.join`
`
)

// TEST

out=x=>O.innerHTML+=x.replace(/</g,'<')+'\n'

;['S5,W2','N1,E1,S1,E1,N1,E1,S2','N1','N6,E6,S6,W5,N5,E4,S4,W3,N3,E2,S2,W1,N2','E21,S2','N12,E11,S12,W2,N4']
.forEach(a=>out(a+'\n'+F(a)+'\n'))

C, 557
main(_,a,minX,maxX,minY,maxY,x,y,v,dir,dist)char**a;char*v;{char o[998][999];for(y=0;y-998;++y){for(x=0;x-998;++x)o[y][x]=32;o[y][998]=0;}y=x=minY=minX=maxY=maxX=499;v=a[1];while(*v){dir=*v++;dist=atoi(v);while(*v&&*v!=44)v++;v+=!!*v;if(dir==78){while(dist--)o[y--][x]=94;if(y<minY)minY=y;y+=!*v;}if(dir==69){while(dist--)o[y][x++]=62;if(x>maxX)maxX=x;x-=!*v;}if(dir==83){while(dist--)o[y++][x]=86;if(y>maxY)maxY=y;y-=!*v;}if(dir==87){while(dist--)o[y][x--]=60;if(x<minX)minX=x;x+=!*v;}}o[y][x]=88;for(y=minY;y<=maxY;++y){o[y][maxX+1]=0;puts(o[y]+minX);}}

Ungolfed version:
#include <stdio.h>

#define MAX_WIDTH 998
#define MAX_HEIGHT 998

int main(int argc, char *argv[]) {
    int minX,maxX,minY,maxY;
    int x,y;
    char output[MAX_HEIGHT][MAX_WIDTH+1];
    char *v;

    for (y=0; y<MAX_HEIGHT; ++y) {
        for (x=0; x<MAX_WIDTH; ++x)
            output[y][x] = ' ';
        output[y][MAX_WIDTH] = 0;
    }

    x = minX = maxX = MAX_WIDTH/2;
    y = minY = maxY = MAX_HEIGHT/2;

    v = argv[1];
    while (*v) {
        char dir; int dist;
        dir = *(v++);
        dist = atoi(v);
        while (*v && *v != ',') v++;
        if (*v) v++;

        switch (dir) {
            case 'N':case 'n':
                while (dist--) output[y--][x] = '^';
                if (y < minY) minY = y;
                if (!*v) y++;
                break;
            case 'E':case 'e':
                while (dist--) output[y][x++] = '>';
                if (x > maxX) maxX = x;
                if (!*v) x--;
                break;
            case 'S':case 's':
                while (dist--) output[y++][x] = 'v';
                if (y > maxY) maxY = y;
                if (!*v) y--;
                break;
            case 'W':case 'w':
                while (dist--) output[y][x--] = '<';
                if (x < minX) minX = x;
                if (!*v) x++;
                break;
        }
    }

    output[y][x] = 'x';
    for (y = minY; y <= maxY; ++y) {
        output[y][maxX+1] = 0;
        puts(output[y]+minX);
    }

    return 0;
}

Dynamic memory allocation isn't much harder, but malloc is far too long an identifier to be used in code golf. I feel like there should be some kind of PCG.h header legally auto-included for golfing in c, just to shorted some identifiers.

391 bytes

Jelly, 61 60 bytes
“ESWN”iⱮo)µịØ.,U;N$¤Wẋɗ/€Ẏḣ1;Ɗ+\ṖZṂ€ạƊ‘ŒṬ€a"Œṙ-0¦$Sị“>v<^X ”

Try it online!
A monadic link taking as its argument the directions as a list of lists, each of which has the compass direction character as its first member and the number of moves as an integer as its second. Returns a list of Jelly strings representing the map.

Groovy, 359
c=args[0].split(',').collect{[it[0],it[1..-1]as int]}
m=[[]]
x=y=0
d=["N":["^",0,1],"S":["v",0,-1],"E":[">",1,0],"W":["<",-1,0]]
c.each{z->(1..z[1]).each{if(x<0){m*.add(0," ");x=0};if(y<0){m.add(0,[]);y=0};m[y]=m[y]?:[];m[y][x]=d[z[0]][0];if(c.last()==z&&it==z[1])m[y][x]='X';y+=d[z[0]][2];x+=d[z[0]][1]}}
m.reverse().each{println it.collect{it?:" "}.join()}

Common Lisp - 603
(lambda(s)(do((x 0)i(y 0)j(p 0)r(q 0)(g(mapcar(lambda(x)`(,(aref x 0),(parse-integer x :start 1)))(split-sequence:split-sequence #\, s))(cdr g))c)((not g)(setf x 0 y 0)(dolist(e(stable-sort(sort r #'<= :key #'car)#'< :key #'cadr))(dotimes(_(-(cadr e)p y))(terpri)(incf y)(setf x 0))(dotimes(_(-(car e)q x))(princ" ")(incf x))(princ(caddr e))(incf x)))(case(caar g)(#\N(setf i 0 j -1 c #\^))(#\E(setf i 1 j 0 c #\>))(#\W(setf i -1 j 0 c #\<))(#\S(setf i 0 j 1 c #\v)))(dotimes(_(-(cadar g)(if(cdr g)0 1)))(push`(,x,y,c)r)(incf x i)(incf y j))(setf q(min q x)p(min p y))(unless(cdr g)(push`(,x,y #\X)r))))

Array-free implementation: prints from top to bottom, from left to right.

Parse and expands directions into a trace of (x y char) elements:
The simple "N3" input produces ((0 0 #\^) (0 -1 #\^) (0 -2 #\X))
Also, compute the minimal x and y
Sort the resulting trace by y first and then by x
Iterate over the sorted list while moving cursor

Add newlines and spaces to move current cursor at right position
When at position x - minx, y - miny, print the desired character

Examples
(loop for input in  '("N6,E6,S6,W5,N5,E4,S4,W3,N3,E2,S2,W1,N2"
                      "N1,E1,S1,E1,N1,E1,S2"
                      "N12,E11,S12,W2,N4")
      do (fresh-line)
         (terpri)
      (funcall *fun* input))

Result:
>>>>>>v
^>>>>vv
^^>>vvv
^^^Xvvv
^^^^<vv
^^^<<<v
^^<<<<<

>v>v
^>^X

>>>>>>>>>>>v
^          v
^          v
^          v
^          v
^          v
^          v
^          v
^          v
^        X v
^        ^ v
^        ^ v
^        ^<<

CoffeeScript, 303  285 bytes
Y=(s)->o=[];t=l=x=y=0;q='';q+=s[0]for[1..s[1..]]for s in s.split ',';q=q[..-2];(i='NWSE'.search c;(o[y]?=[])[x]='^<v>'[i];j=(i&2)-1;x+=j*(i&1);y+=j*(!(i&1));y<t&&t=y;x<l&&l=x)for c in q;(o[y]?=[])[x]='X';((o[y][x]||' 'for x in[l...o[y].length]).join ''for y in[t...o.length]).join '\n'

Charcoal, 32 bytes
ＷＳ«≔⌕ENW§ι⁰θ✳⊗θ×§>^<vθΣι»Ｍ✳⁺⊗θ⁴X

Try it online!
Input taken as a multiline string.
Link is to verbose version of code.
Golfed from 43 bytes with Neil's help.

Vyxal, 390 bitsv2, 48.75 bytes
⌐⌊›?Ǎf`NESW`kd√:£Ŀ:ṅ¥`^>v<`ĿfW∩vǔṫ⁽‹ẇwJ:tt\X1"pwJ⟑÷ø∧

Try it Online!
Bitstring:
000110000111010100000001000100000101011110110001100110111110111101111011001110011001001000011101100001111110011101110101110100100100110111110011000000010110101101110001011010011010000010011111100110010101010011010000110000010100000110001000100010100110010101010000110101110111100001000011001100000001110101110111000000101111101011000110101100100110111100111111000101110011110111110101001011

⌐⌊›?Ǎf`NESW`kd√:£Ŀ:ṅ¥`^>v<`ĿfW∩vǔṫ⁽‹ẇwJ:tt\X1"pwJ⟑÷ø∧
⌐⌊›                                                    # split by comma, get number part, increment
   ?Ǎf                                                 # get directions and flatten
      `NESW`                                           # Directions
            kd√                                        # "02468"
               :£                                      # duplicate and push to register
                 Ŀ                                     # transliterate directions to corresponding canvas numbers
                  :ṅ¥                                  # duplicate, join by nothing, push register
                     `^>v<`Ŀ                           # Transliterate each direction to corresponding arrow text
                            fW∩                        # flatten, wrap the stack and transpose
                               vǔ                      # rotate each sublist to order [text, length, direction] for canvas
                                 ṫ⁽‹ẇwJ                # decrement the middle of the last triplet
                                       :tt             # get the very last direction
                                          \X1"         # ["X", 1]
                                              pwJ      # prepend it to the direction and put it back (Draws the X)
                                                 ⟑÷ø∧  # draw each triplet to the canvas

Created with the help of Luminespire.

05AB1E, 37 35 (or 42 38) bytes
38 bytes: Input as comma-separated string, as mentioned in the challenge description:
',¡εć"NESW"skxs"^>v<"è)}øR`ā¤Ê+ŠΛ1'X0Λ

Try it online.
35 bytes: Input as a list of pairs of direction-character and distant-integer, by removing the first three bytes ',¡:
Try it online.
Explanation (of the strict I/O program):
',¡           '# Split the (implicit) input-string on commas
   ε           # Map over each string:
    ć          #  Extract its head; push distant and direction-char separately
     "NESW"sk  #  Get the 0-based index of the character in "NESW"
             x #  Double it (without popping)
     s         #  Swap so the index is at the top again
      "^>v<"è  #  Convert the index to the correct output character
     )         #  Wrap all three values into a list
    }ø         # After the map: zip/transpose the list of triplets; swapping rows/columns
      R        # Reverse the list of triplets
       `       # Pop and push all three lists separately to the stack
        ā      # Push a list in the range [1,length]
         ¤     # Push its last item (without popping the list)
          Ê    # Check for each that it's NOT equal to this last item
           +   # Add the values at the same positions
               # (so 1 is added to all distances, except the last one)
        Š      # Triple-swap the three lists on the stack
         Λ     # Canvas builtin with these three arguments
               # (which is output immediately)
1'X0Λ         '# And another Canvas builtin with arguments 1,"X",0
               # (which is done on top of the other Canvas and also output)

The Canvas builtin Λ takes three arguments:

Length(s): which are the modified distances (+1 for every distance except the last one, since the Canvas builtin draws with overlapping corners)
The characters we want to display
The directions to draw in, which is in this case is \$0\$=North; \$2\$=South; \$4\$=South; \$6\$=West.

For example: input E2,N4,E5,S2,W1,S3 will for ',¡εć"NESW"skxs"^>v<"è)}øR`ā¤Ê+Š result in the three lists:

Lengths: [3,5,6,3,2,3]
Characters: [">","^",">","v","<","v"]
Directions: [2,0,2,4,6,4]

And will print them as:
  >>>>>v
  ^    v
  ^   v<
  ^   v
>>^   v

After which the 1'X0Λ will overwrite the final v with X.
See this 05AB1E tip of mine for an in-depth explanation of the Canvas builtin.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Balance a set of weights on a seesaw
Balancing Act
Overview
Given an input of 3 single-digit positive integers representing a set of weights, output an ASCII representation of a seesaw with the weights placed on it so that it is in balance around a central pivot, taking lever effects into account.
Each number has a weight equal to its value. The torque of each number is the weight multiplied its the distance from the center in characters. For the seesaw to be in balance, the sum torque of the weights on the left of the seesaw must equal that of those on the right, like this.
Input
3 integers in the range of 1-9. You can input the integers however is convenient, e.g. a tuple, 3 comma-separated values etc. However your program must be able to handle numbers input in any order (i.e. no assuming the values will be sorted). Duplicate numbers may be input (e.g. 2,3,2).
The inputs will always mathematically allow for a valid output, otherwise the input is not valid.
Output
The output should be a 2-line ASCII representation of the seesaw with the weights placed on it. On the first line are the digits, spaced in order to balance them on the seesaw.
Numbers may not be placed in the very center of the scale, where the distance and therefore the torque would be zero. Valid distances from the center range from 1-10 characters inclusive to the left or right of the pivot.
In the spaces unoccupied by the numbers are 18 underscore characters (a center underscore and 10 on each side, minus the 3 positions occupied by the numbers). On the last line is a single caret character aligned with the center of the scale, representing the pivot.
Examples
Input:
4,7,2

Output:
________7___42_______
          ^

7*2 = 4*2 + 2*3
Numbers can be output on either side, for example this would also be valid:
_______24___7________
          ^

2*3 + 4*2 = 7*2
Numbers can be placed anywhere on the scale as long as they balance, e.g:
Input:
3,1,5

Output:
_____5________1__3___
          ^

5*5 = 1*4 + 3*7
or
____5________1_____3_
          ^

5*6 = 1*3 + 3*9
or
____5___________1_3__
          ^

5*6 = 1*6 + 3*8
etc
Your program only has to output one of the valid outputs. It does not have to output an error if the input is not valid.
Notes

This is code-golf so the shortest program in bytes wins
Program may be a stand-alone or a function that accepts the numbers as input and returns a string.
Trailing newline and white-space on last line is optional
If you don't know what a seesaw is, it's also known as a teeter-totter or a teeterboard.

Here's a paste showing valid inputs and solutions (with some duplication)

An excellent first challenge! An interesting problem and a thorough spec.

Algorithmically, given a whole-numbered vector, this asks you to find a whole-numbered orthogonal vector with all different entries.

CJam, 40 39 38 bytes
q~21Ue]e!{21,Af-Aest.*:+!}=0'_erNAS*'^

Try it online.
How it works
q~                                     e# Read and evaluate the input.
  21Ue]                                e# Append zeroes to achieve a length of 21.
       e!                              e# Push all unique permutations.
         {               }=            e# Find the first permutation such that:
          21,                          e#  Push [0 ... 20].
             Af-                       e#  Subtract 10 from each.
                Aest                   e#  Replace the element at index 10 with the
                                       e#  current time (ms since epoch) to push
                                       e#  [-10 ... -1 <big number> 1 ... 10].
                    .*                 e#  Multiply each number of the permutation
                                       e#  by the corresponding distance.
                      :+               e#  Add the products.
                                       e#  The timestamp makes sure that this sum
                                       e#  is non-zero for a non-zero element in
                                       e#  the middle of the permutation.
                        !              e#  Push the logical NOT of the sum.
                           0'_er       e# Replace zeroes with underscores.
                                NAS*'^ e# Push a linefeed, ten spaces and a caret.

Java, 519 414 321 bytes
static int f(int a,int b,int c){int i,j,k;for(i=-10;i<=10;i++)for(j=i+1;j<=10;j++)for(k=j+1;k<=10;k++){if(a*i+b*j+c*k==0&&i!=0&&j!=0&&k!=0){for(int q=0;q<21;q++){if(q==10+i)p(a);else if(q==10+j)p(b);else if(q==10+k)p(c);else p('_');}p("\n          ^\n");return 0;}}return 0;}static void p(Object a){System.out.print(a);}}

My first attempt at golfing.
You can call it with f(a,b,c).
Try it here
EDIT: Used izlin method of check (a*i+b*j+c*k)==0
EDIT: Thanks, J Atkin for the golfing suggestions.

You can save a few bytes by changing the signature of p to Object a and using it in place of the other 2 System.out.print(ln) s.

And since a is used only once, you could inline it.

Pyth, 67 58 53 49 bytes
This feels a little on the huge side for Pyth, but I'm not nearly familiar enough with the language to be able to get this much smaller. Sub 50 bytes, I'm finally happy with this!
V.c-KrT-011Z3FY.pQIqs*VNYZjkm?}dN@YxNd\_K+*dT\^.q

Input is expected as an array of integers, for example [1,2,3]. Try it here.
Explaination:
V.c-KrT-011Z3FY.pQIqs*VNYZjkm?}dN@YxNd\_K+*dT\^.q
                                                       Implicit: Q = eval(input())
     rT-011                                            Create range from 10 to -10
    K                                                  Store in K
   -       Z                                           Drop 0 from the above
V.c         3                                          For N in (combinations of the above of size 3)
             FY.pQ                                     For Y in (permutations of input)
                     *VNY                              Multiply each element in N by the corresponding element in Y
                    s                                  Take the sum
                  Iq     Z                             If it's equal to zero:
                            m           K              For d in K (K = [10, ..., -10])
                             ?}dN                      Is d in N?
                                 @YxNd                 If so, get corresponding value from Y
                                      \_               Otherwise, get '_'
                          jk                           Join the resulting array into a string (implicit print)
                                         +*dT\^        Join 10 spaces and '^', implicit print
                                               .q      Break all loops and exit

And finally, some example inputs and outputs:
[1,1,1] ->
1__________1_______1_
          ^

[2,9,5] ->
2____5_________9_____
          ^

[9,8,5] ->
5____8______________9
          ^

CJam, 46 44 bytes
'_21*q~K,Am3m*{___&=*Afm1$.*:+!}=.{\t}NAS*'^

Test it here.
Explanation
First, an observation: we never need to put two digits on the ends of the seesaw. Whenever that's a valid solution, there is at least one other valid solution (according to the pastebin in the comment on the challenge).
'_21*   e# Push a string of 21 underscores.
q~      e# Read and eval input.
K,      e# Push the array [0 1 .. 19 20]
Am      e# Remove the 10. This is now an array of all valid positions on the seesaw.
3m*     e# Get all 3-tuples of valid positions.
{       e# Select the first tuple for which the following block yields a truthy result.
  ___   e# Make three copies of the tuple.
  &=    e# Intersect the last two copies and check for equality with the first one.
        e# This yields 1 if all positions are distinct, and 0 otherwise.
  *     e# Repeat the original tuple that many times. That is, if the positions are
        e# distinct, leave the tuple unchanged. Otherwise, replace it with an empty array.
  Afm   e# Subtract 10 from each position to get its weight.
  1$    e# Copy the input digits.
  .*    e# Take the pairwise product of weights and digits. If the weights are empty
        e# (because they were not unique), this will just yield a list of the digits.
  :+    e# Sum the weighted digits. If the weights were not unique, this will just sum
        e# the digits and will always be positive.
  !     e# Logical NOT - give 1 if the sum was 0, or 0 otherwise.
}=
.{\t}   e# For each pair of digit and position, replace that position in the underscore
        e# string with the corresponding digit.
N       e# Push a newline.
AS*     e# Push ten spaces.
'^      e# Push a caret.

C - 237 228 Bytes
i,j,k;f(a,b,c){char o[]="_____________________\n          ^";for(i=-10;i<9;i+=i+1?1:2){for(j=i+1;j<11;j+=j+1?1:2){for(k=j+1;k<11;k+=k+1?1:2){if((a*i+b*j+c*k)==0){o[i+10]=a+48;o[j+10]=b+48;o[k+10]=c+48;printf("%s",o);return;}}}}}

You can call it with f(a,b,c).
Try it here.
Example outputs:
f(4,7,2):
4_____________7_2____
          ^

f(3,1,5)
3____1___________5___
          ^

199 bytes

Python 2.7 235 226 219 Bytes
def s(n,p=__import__("itertools").permutations):
 l=["_"]*21
 for p,q in[[(a,x+10),(b,y+10),(c,10-z)]for a,b,c in p(n,3)for x,y,z in p(range(1,11),3)if x!=y and a*x+b*y==c*z][0]:l[q]=`p`
 return`l`[2::5]+"\n"+" "*10+"^"

Testing it with some basic examples- (1,1,1),(1,2,1),(3,1,5),(4,7,2) results in- :
(1, 1, 1)
_______1___11________
          ^
(1, 2, 1)
_____1_____12________
          ^
(3, 1, 5)
________5__3_____1___
          ^
(4, 7, 2)
_2_________47________
          ^

Outputs for all possible inputs pasted here

"".join(l) -> 'l'[2::5] is one byte shorter (replace the quotes with backticks).

Also, if you're willing to change your approach from a function to a program, you can golf this down to 222 bytes.

@samgak oops. My bad, thought I read the question properly. 2 more bytes :(

@Vioz- Awesome tip. Didn't know about repr. :)

PHP, 278 bytes
A brute-force solution that uses a bunch of nested loops and a couple of tests.
$p=explode(',',$argv[$i=1]);for(;$i<=10;$i++)for($j=1;$j<=10;$j++)
for($k=1;$k<=10;$k++)if($j-$k)for($l=0;$l<3;$l++){$q=array_shift($p);
if($i*$q==$j*$p[0]+$k*$p[1]){$o=str_repeat('_',21);$o[10-$i]=$q;$o[10+$j]=$p[0];
$o[10+$k]=$p[1];echo($o."\n          ^\n");}array_push($p,$q);}

As always, put it into a file (let's name it seesaw.php), join the lines (split here for readability), put the PHP marker (<?php) at the beginning of the file (technically, it is not part of the program) and you're good to go.
An example of execution:
$ php seesaw.php 9,2,1
_________9_2_____1___
          ^
_________9__2__1_____
          ^
_________9_1__2______
          ^
________9_____2_____1
          ^
________9______2__1__
          ^
________9_____1__2___
          ^
________9___1_____2__
          ^
_______9_________1__2
          ^
____2______9_1_______
          ^
___2_______9___1_____
          ^
__2________9_____1___
          ^
_2_________9_______1_
          ^

It generates and displays all the solutions (without reflections), but it does not strip the duplicates (when the input values contain duplicates).

Julia, 154 bytes
f(a,b,c)=(x=replace(join(first(filter(p->p⋅[-10:-1,1:10]==0,permutations([a,b,c,zeros(Int,17)])))),"0","_");print(x[1:10]*"_"*x[11:20]*"\n"*" "^10*"^"))

Ungolfed + explanation:
function f(a,b,c)
    # Create a 20-element array of the input with 17 zeros
    z = [a,b,c,zeros(Int,17)]

    # Get the set of all permutations of z such that the dot product
    # of the permutation with the distances is 0
    d = filter(p -> p ⋅ [-10:-1,1:10] == 0, permutations(z))

    # Join the first element of d into a string and replace all of
    # the zeros with underscores
    x = replace(join(first(d)), "0", "_")

    # Print the output
    print(x[1:10] * "_" * x[11:20] * "\n" * " "^10 * "^")
end

C, 252 (214) bytes
Call with a,b,c as arguments on command line.
e=48;main(_,v,x,y,z,a,b,c)char**v;{char s[]="_____________________\n          ^";x=*v[1]-e;y=*v[2]-e;z=*v[3]-e;for(a=-1;a+11;--a)for(b=-10;b-11;++b)_=a*x+b*y,!b|b==a|_%z?0:(c=-_/z,c&c<11&c>-11?s[a+10]=x+e,s[b+10]=y+e,s[c+10]=z+e,puts(s),exit(0):0);}

If main can be ommitted, byte count drops to 214 for a function.
a,b,c;f(x,y,z){char s[]="_____________________\n          ^";for(a=-1;a+11;--a)for(b=-10;b-11;++b)!b|b==a|(a*x+b*y)%z?0:(c=-(a*x+b*y)/z,c&&c<11&&c>-11?s[a+10]=x+48,s[b+10]=y+48,s[c+10]=z+48,puts(s),b=10,a=-b:0);}

Both use the same strategy of placing the first weight on the left, then scanning along possible second weight positions and calculating the third weight. This allows the removal of an inner loop.

231 bytes and 199 bytes

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Cycle lengths for Perfect shuffles of decks of any size
Challenge
In the shortest amount of code:

Compute the length of the permutation cycle of a perfect shuffle on a deck of cards of any size n (where n ≥ 2 and n is even).
Output a table of all cycle lengths for 2 ≤ n ≤ 1000 (n even).

Note that there are two basic ways of defining a perfect shuffle. There is the out-shuffle, which keeps the first card on top and the last card on bottom, and there is the in-shuffle, which moves the first and last cards one position toward the center. You may choose whether you are doing an out-shuffle or an in-shuffle; the algorithm is almost identical between the two.

out-shuffle of 10-card deck: [1,2,3,4,5,6,7,8,9,10] ↦ [1,6,2,7,3,8,4,9,5,10].
in-shuffle of 10-card deck: [1,2,3,4,5,6,7,8,9,10] ↦ [6,1,7,2,8,3,9,4,10,5].

Graphical example
Here, we see that an out-shuffle on a 20-card deck has a cycle length of 18 steps. (This is for illustration only; your solution is not required to output cycles graphically.) The classic 52-card deck, on the other hand, has an out-shuffle cycle length of only 8 steps (not shown).

An in-shuffle on a 20-card deck has a cycle length of only 6 steps.

Tabular example of output
Your program should output something similar to this, although you may choose any tabular format that you like best. This is for an out-shuffle:
2 1
4 2
6 4
8 3
10 6
12 10
14 12
16 4
18 8
20 18
22 6
24 11
26 20
28 18
30 28
32 5
34 10
36 12
38 36
40 12
...many lines omitted...
1000 36

Questions

Does there seem to be any connection between the number input n and its cycle count, when n is a power of 2?
How about when n is not a power of 2?
Curiously, a 1000-card deck has an out-shuffle cycle count of only 36, while a 500-card deck has an out-shuffle cycle count of 166. Why might this be?
What is the largest number you can find whose cycle count c is vastly smaller than n, meaning that ratio n/c is maximized?

Very closely related.

Ya, that's more about displaying the results, though. This question is about generating a table for any value of n; it's more mathematical in nature.

confused me there with the 6/8 cycles in the demonstrated for a good while :) (i thought my imlementation was wrong). finally i looked at the image and saw it is a 6 cycle, so i edited it. funny

@proud haskeller — ah yes, thank you!

This is sequence A002326.

Haskell, 47 46 44 (in shuffle)
[[i|i<-[1..],mod(2^i)n<2]!!0|n<-[3,5..1001]]

the basic realization is that this is the order of 2 in the multiplicative group of modulus n+1.

You can remove the l= - the expression itself is enough. That's a valid program when run on the interactive command line.

Pyth, 16 bytes
mfq1%^2T+3yd)500

In-shuffle using A002326.

Pyth, 22 bytes
V500,JyhNl{.u.iFc2NJUJ

Try it online: Demonstration.  Replace 500 with a smaller number, if it is too slow.
Explanation:
V500                     for N in [0, 1, ..., 499]:
      yhN                   (N + 1) * 2
     J                      assign to J
           .u      JUJ      apply the following expression J times
                            to N, starting with N = [0, 1, ..., J - 1],
                            and return all intermediate results:
                c2N            split N into 2 halfs
             .iF               and interleave them
         l{                 remove duplicates and give length
    ,                       make a pair and print

It's kind of crazy that a pyth solution which does the actual work of shuffling and counting the decks is only half as long as the haskell solution which uses an easy formula the instantly predict the result

@Falco I know right

@Falco I actually tried to do a pyth portof my answer but I couldn't figure how to do it. So I just ended up playing with pyth for half an hour

Be glad you didn't try <><

Mathematica, 53 (in-shuffle)
Grid[{2#,MultiplicativeOrder[2,2#+1]}&/@Range[1,500]]

or, not antagonistically spaced
Grid[{2 #, MultiplicativeOrder[2, 2 # + 1]} & /@ Range[1, 501]]

Output:
   2    2
   4    4
   6    3
   8    6
  10   10
  12   12
  14    4
  16    8
  18   18
  20    6
 (* digits, digits, bo bidgits, banana fana, ... *)
  498  166
  500  166
 (* skip a bit, brother ...  *)
  998   36
 1000   60

Every entry in both columns is horizontally centered in their columns, but I don't have the fractional spaces   ...   here to replicate that.
Observations:

Out-shuffle is in-shuffle on a deck two cards smaller.  (Note that the first and last cards are in fixed position throughout the out-shuffle demonstration.)  Consequently, the two choices will lead to similar output lists -- the second column will be shifted by one row.  Regarding the "powers of two" hint, the in-shuffle of power of two decks has the pattern {2^n - 2, n}, {2^n, 2n}.  (Out-shuffle pairs 2^n with n.)
Observe in the in-shuffle example that the distance of 2 from the closest end of the deck doubles at each step.  {2, 4, 8, 15 = -5, -10, -20}.  In fact, this is true for every card.  We therefore only need to know which power of 2 is congruent to 1 mod n+1 where n is the number of cards.  (Note that in the example, the cards in the last column, column -1, are doubled to the penultimate column, -2, meaning that 0 is congruent to one more card than is in the deck, thus "mod n+1".)  Therefore, the MultiplicativeOrder[] function is the way to go (in Mathematica).
By default, one would try TableForm[] instead of Grid[], but the output is similar.

Your example output seems wrong

@proudhaskeller : for in-shuffle or out-shuffle?  Either is permitted.  (And as noted, the one is just a one row shift in the right column of the other.)

They both don't seem to fit. Look up the example output in the question. Maybe your example output is wrong and the actual code is right and the example is just outdated, I don't know, but it doesn't seem to fit.

proudhaskeller : I seem to have typoed my example output at "8".  And muddled in- and out- at least once.  Editing.  Thanks for being persistent.  :-)

C,86 (or 84)
Score excludes unnecessary whitespace, included for clarity.
i,j,n;
main(){
  for(;n<1002;printf("%d %d\n",n,j),n+=2)
    for(i=n,j=1;i=i*2%(n+1),i-n;)j++;
}

This is an in-shuffle, which as pointed out by others, is just the out shuffle with the stationary cards at both ends removed.
As pointed out by others, in the in-shuffle, the position of each card doubles each time, but this must be taken modulo n+1. I like to think of the extra card position being position zero to the left of the table (you can think of this as holding both the stationary cards from the out-shuffle too). Obviously the position of the card must always be positive, hence the zero position always remains empty for the in-shuffle case.
The code initialises i to the value of n. Then it multiplies by 2, takes the result mod (n+1) and checks to see if i has returned to its initial value (i-n is zero.) It increments j for each iteration, except the last one (hence the need initialise j to 1.)
In principle, i could be with any value in the range 1..n, so long as the comparison at the end checked if it was intialised to the same number. The reason for picking n was to make sure the program works for the case n==0. the problem was that any number modulo (0+1) is zero, so the loop never terminated in this case if i was initialised to a constant such as 1.
The question examples includes the equivalent case n==2 for the out shuffle, so it was interpreted that this case is required. If it isn't, two bytes n, could be saved by initializing i to 1, the same value as j.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
ASCII Game of Pong
Ascii Pong
The challenge is to recreate the classic game "pong" in ASCII characters in the shortest code possible.
Requirements/specifications

The "screen" should be 45x25 characters.
White space should actually be white space.
The paddles should be 9 equals signs: ========= and should be on the top-most and bottom-most rows (I know the original is played side-to-side instead of top-to-bottom, but I think this works better for ascii pong).
The ball can be a lower or upper case o or a zero.
Two input buttons of any kind (it is fine if the user presses a key that makes a letter show up in the input, that is fine, too) to move the player's paddle left and right one or two character at a time.
The ball needs to ricochet at the appropriate angle upon hitting a paddle or a wall (hint: negate the x or y difference value).
The score should be displayed somewhere in the output. The score is how many times the player successfully hits the ball.
If the ball misses the player's paddle, terminate the program.
There should be some sort of AI (even if the AI's paddle just matches the ball's x value).
The ball can't travel in a straight line vertically or horizontally.

The start screen/first frame should look something like this:
                  =========

                      o

                  =========
score: 0

Scoring
This is code-golf, so the shortest code wins ...
however, there are some bonuses to decrease your character count:

-30 characters: Change trajectory of ball depending on where it hits on the paddle
-10 characters: Make the game speed up over time
-20 characters: Make the AI beatable
-20 characters: Avoid any situation where the player stays still and the game goes on forever without winning or losing (caused by certain trajectories and AI patterns)
-20 characters: Make the ball start moving at a (semi-)random trajectory
-25 characters: Add a reset option

Here is an un-golfed example with no bonuses in JavaScript:

//init
var x = 22,
    y = 12,
    xd = Math.random() < 0.5 ? -1 : 1,
    yd = 1,
    player = opponent = 18,
    score = 0,

//interval that runs 10x per second (minus the runtimeof one cycle)
interval = setInterval(function() {
  //move ball
  x += xd;
  y += yd;

  //move opponent
  opponent = x - 4;

  //collision with walls
  if(x <= 0 || x >= 44) xd = -xd;

  //collision with paddles
  if(y == 1) {
    if(x >= opponent && x < opponent + 9) yd = -yd;
    else {
      //you win
      clearInterval(interval);
      document.body.innerHTML = "You win!
Your score was: " + score;
      return;
    }
  }
  else if(y == 23) {
    if(x >= player && x < player + 9) {
      yd = -yd;
      score++;
    }
    else {
      //you lose
      clearInterval(interval);
      document.body.innerHTML = "You lose!
Your score was: " + score;
      return;
    }
  }

  draw();
}, 100);

function draw() {
  var body = document.body;
  body.innerHTML = "";
  for(var i = 0; i < 25; i++) {
    for(var j = 0; j < 45; j++) {
      //white space is default
      var char = " ";

      //ball
      if(j == x && i == y) char = "o";

      //paddles
      if(i === 0) {
        if(j >= opponent && j < opponent + 9) char = "=";
      }
      else if(i == 24) {
        if(j >= player && j < player + 9) char = "=";
      }

      body.innerHTML += char;
    }
    body.innerHTML += "
";
  }
  body.innerHTML += "score: " + score;
}

//key press listener for left and right movement
window.onkeydown = function() {
  if (window.event.keyCode == 37) player -= 2;
  else if(window.event.keyCode == 39) player += 2;
};

Let the games begin!

Okay can somebody at least explain why they downvoted this? I am genuinely curious because I thought this would be fun but I don't have much experience.

Printing out ASCII stuff is okay but with keyboard interaction we'd have to build a whole app. Those type of challenges are frowned upon because many languages don't support i/o like that. Implementing an AI, physics. Almost like a full scale application. If you take a look at other challenges they have one task which takes an input (or not) and produces a relevant output. Adding an AI, physics, and keyboard knteraction is just way to much for a challenge

@vihan the AI for pong is extremely simple, it just has to follow the x value of the ball. Even making it beatable is not that hard, just limit the speed od the paddle. The only real issue with the concept is the keyboard interaction, which can be managed in a reasonable variety of languages. The brief is however rather vague and open (given that we are sticklers for unambiguity and fairness around here), and the vast array of bonuses don't help that.

relevant: http://meta.codegolf.stackexchange.com/q/5521/15599

Related: http://codegolf.stackexchange.com/q/10713

Keyboard interaction had to be solved in (Re)Implementing Tetris too, but that didn't diminished the task's popularity. (Yes, I know, that was actually [tag:popularity-contest], this is not.) The only thing personally I find disturbing, is the amount of bonuses. But certainly not has to be up to my taste.

possible duplicate of Pong in the shortest code

I looked at that challenge and decided it was different from what I wanted to do. That was to recreate pong as closely as possible, requiring a graphical output, possible 2 player modes, pause, etc. This was supposed to be something you could print in a command line or console with as simple code as possible. Maybe I didn't explain that well enough in my challenge. I'll keep that in mind for next time.

I think this just too much for a single challenge. But that's subject to opinion.

I can't open the snippet to Full page in time!

Perl, 760 611 592 535 515 (640-30-10-20-20-20-25)
A console solution with all the bonus stuff.
It should work on any terminal that understands the ANSI escape codes (\e[...). Tested on cygwin.
Keyboard controls:
Left: 4
Right : 6
Reset : 8
use Term::ReadKey;ReadMode 4;END{ReadMode 0}$|++;$a=$d=45;$b=25;$h=1;$j=$l=17;$p='='x9;sub P{print"\e[@_"}sub L{$%=$l+pop;if($%>0&$%+7<$a){P"25H\e[K\e[25;$%H$p ";$l=$%}}sub U{$%=$j+pop;if($%>0&$%+7<$a){P"1H\e[K\e[1;$%H$p ";$j=$%}}sub I{$}=int rand 42;$g=8;$i=1;P"2J\ec";L}I;while(1){if($c>0){$c--}else{$c=98;$d-=$d>6}if($c%9==0){U -1if$}<$j+4;U 1if$}>$j+6};if($c%$d==0){$m=$}+$h;$n=$g+$i;$h*=-1if$m<1||$m>$a;if($n>24&$}>=$l&$}<$l+9){$i*=-1;$h=-1if$m<$l+5;$h=1if$m>$l+5;$s++}if($n<2&$}>=$j&$}<$j+9){$i*=-1}P"$g;1H\e[K";$}+=$h;$g+=$i;P"$g;$}HO"}if($k=ReadKey -1){I,if$k>6;L$k<=>5}P"26;0Hscore:$s";exit,if$g>=$b;select($\,$\,$\,0.01);I,if$g<2}

Hey Luk, loving this! Thought I'd share a few ways you might be able to save some more chars... Since you're using print more than 4 times, it should be cheaper to set up a new sub and call that sub p{print@_}. If you don't mind other keys being used as well as those you specific, you can replace if(defined($k=ReadKey(-1))){L(-1)if's'eq$k;L(1)if'd'eq$k;I,if'r'eq$k} with L 114<=>ord$k if$k=ReadKey -1;. This just converts <r:-1,r:0,>r:1 which might not be what you're after. If you are happy with this, you could use [4][5][6] as the keys with: L$k<=>5 if$k=ReadKey -1;.

Also looks like you can replace a few if blocks with a postfix if check or replace with ternary for some more savings, but that might prove tricky with the nesting... You have another block $d--if$d>6 which you can change to $d-=$d>6 for a 2-byte saving which might work in a few more places too and another small saving is ;$p=H.'='x9 .$" instead of $p="H========= ". Hope some of these are useful!

Thanks, glad that you like it.  Your tips helped to golf it down further with 50 bytes! That trick with the ord is wicked. The $d-=$d>6 trick looked so weird.  I also discovered that when printing something like "$aH" is a problem, that "${a}H" works like it would in bash. :)

Ah yeah! A couple of ways around that using non-alphabetic variable names ($} or something) or using barewords ($a.H), not sure if that'll help you in this case or not. Something I did notice, is in sub P if you only ever have one argument to it, you could have print"\e[@_" instead of .pop since there won't be a field separator to worry about. Also, if you're using the numpad instead of letters, you don't need to use ord, as $k would be 4 or 6 so you could do 5<=>$k instead.

Thanks again. Didn't think perl would accept variables like that O_o.  But it does work and a few bytes were resqued by that. But don't try using a $! variable. Weird stuff happens then.

JavaScript, 618 bytes + HTML, 99 bytes
Well here is my golfed JavaScript answer even if it isn't feasible in other languages:

var x,y,xd,yd,p,o,s,n,i,j,c,k;function a(){x=22;y=12;xd=Math.random()<.5?-1:1;yd=1;p=o=18;s=0;n=setInterval(function(){x+=xd;y+=yd;o=x-4;if(x<=0||x>=44)xd=-xd;if(y==1){if(x>=o&&x<o+9)yd=-yd;else{clearInterval(n);b.innerHTML="You Win!
Score: "+s;return}}else if(y==23){if(x>=p&&x<p+9){yd=-yd;s++;}else{clearInterval(n);b.innerHTML="You Lose!
Score: "+s;return}}d();},100);}function d(){b.innerHTML="";for(i=0;i<25;i++){for(j=0;j<45;j++){c=" ";if(j==x&&i==y)c="o"; if(i==0&&j>=o&&j<o+9)c="=";if(i==24&&j>=p&&j<p+9)c="=";b.innerHTML+=c;} b.innerHTML+="
";}b.innerHTML+="score: "+s;}onkeydown=function(){ k=window.event.keyCode;if(k==37)p-=2;if(k==39)p+=2;};
<button onclick="a()">start</button>

-20 and -25 for bonuses

Hm, this doesn't look very golfed to me. You could still get rid of two-letter variable names, substitute a few && tokens for &, eliminate plenty of ; tokens, get rid of unnecessary spaces after { and even get rid of some quote characters in the HTML. And probably a lot more, even. This is just a guess, but you might want to try to avoid UglifyJS and minify by hand. :)

Quite cryptic posted this way. The reader has to search the 663 characters code for the key handling, then possibly STFW to find out which keys have code 37 and 39. (Anyway, there is no reaction on left and right arrow key in the latest Firefox I use.) So not being able to test it I will never find out for which of the 3 available bonuses you earned the -20.


text:
Simple portmanteau with longest overlap
I've been using a library called Djangular recently, which integrates Django and Angular.
After a while I thought 'Wouldn't it be fun to programmatically generate portmanteau?'
Here are some examples (e.g. testcases):
Django + Angular -> Djangular
Camel + Leopard -> Cameleopard
Spoon + Fork -> Spoork
Ham + Hammer -> Hammer
The general rule is to find the first common letter working backwards on first word, and working forwards on the last word. Not all portmanteau can be found this way though...
I've deliberately picked 'simple' ones to generate (for instance we're ignoring things like Zebra + Donkey = Zedonk, which is too arbitrary to generate programmatically - the correct behaviour).
Ties can be resolved eitherway - suppose you have cart + ante - both carte, (since t is the last common letter in the first word) and cante, (since a is the first common letter of the last word) are value.
Unfun loopholes are not allowed (including pulling 'solved' examples off wikipedia)
This is code golf, so shortest answer wins. I'll pick the winner a month from posting. Please post the output for all your code.

Could you elaborate on the rules for double letters? It seems that they are omitted if they appear in the first word but are kept if they appear in the second? Or is it that double vowels are omitted but double consonants are kept?

Why isn't the double letter in hammer shortened to hamer?

Shouldn't it be Cameopard? e is the first common letter in the first word.

Do I understand right that you want to get the longest portmanteau by finding a pair of matching letters in the two words that come as close as possible in the concatenated string?

@sp3000 is it not obvious they have to be common? Also I'll try and clarify double letters.

Read literally, "latest in first word, earliest in last word" would mean Spoon + Fork -> Spoork if we take the second o to be the latest in the first word. Similarly, the common t would mean Croissant + Donut -> Croissant. Another example, with earliest in last word this time, would be mock + cocktail = mococktail. I'm not sure if I'm just missing something major or...

@Sp3000 The "that are closest" part of the definition seems the most descriptive (even though there's an error in the sentence, it says "first" twice instead of "first" and "last"). The rest just makes it more confusing. By that definition, for Croissant and Donut, the solution would be Croissanut, since there's only 3 letters between the two n's of CroissantDonut.

@RetoKoradi I realise now that was a bad example. I've made edits appropriately

@Sp3000 both should be valid. I'll add that in.

Going back to mock + cocktail, is it mocktail (k is last common letter of first) or mococktail (c is first common letter of second)? Or does it not matter?

This question is still very confusing. The title asks for the longest overlap, and I'm not sure what the body of the question is asking for, but whatever it is seems to favour shorter overlaps.

Perhaps we could use a system like this for choosing which overlap is best: the final 'score' of each option is calculated with (final word length + letters overlapped) * (1 - abs(amount of first word used - amount of second word used)). For example, django + angular = djangular uses 5/6 of django and all of angular, a difference of 1/6. Subtract that from (the final length of 9 + the overlap of 3), and you get a total score of 10, by far the highest possible. I'd be glad to clarify any questions about this system!

I still don't understand this part: The general rule is to find the first common letter working backwards on first word, and working forwards on the last word. Does one of them take priority?

@xnor nope, neither takes precedence. 'Ties can be resolved eitherway...'

Python 3, 128 79 bytes
Let me know if I got anything wrong and critiques are always welcome.
def f(a,b):
    c=len(a)-1-a[::-1].find(b[1])
    if a[-1]==b[0]:return a[:-1]+b
    if a[c]==a[c-1]:c-=1
    return a[:c]+b[1:]

Called with f(word 1,word 2) and returns the portmanteau. Will throw an error if the inputs aren't compatible. Works for all test cases.
Edit:
If I've read the edits to this question correctly, this updated code should work
f=lambda a,b:a[:-1]+b if a[-1]==b[0] else a[:len(a)-1-a[::-1].find(b[1])]+b[1:]

CoffeeScript, 111 bytes/characters
Source:
l="toLowerCase";f=(a,b)->return a.substr(0,i)+b.substr(j)[l]()for c,j in b when(i=a[l]().lastIndexOf(c[l]()))>0

Try it online!
To use:
alert("
#{f("Django","Angular")}
#{f("Camel","Leopard")}
#{f("Spoon","Fork")}
#{f("Ham","Hammer")}
")

I hoped it will be shorter, but.... ok, still better than PHP :D
The examples result in (using the alert statement above):
Djangular Cameleopard Spoork Hammer

Explanation (Might not be valid coffescript):
l="toLowerCase"; # Keeps code shorter (and DRY :D )
f=(a,b)->
  return a.substr(0,i)+b.substr(j)[l]() # Return the result
     for c,j in b # Postfix for loop
       when(i=a[l]().lastIndexOf(c[l]()))>0
         # Run the return statement only when the
         # character `c` is found (also stores its last position in `i`)

Haskell, 61 bytes
Doesn't handle case, but that doesn't seem to be a big deal? Tell me if it is.
a!b=maybe(init a!b)((a++).(`drop`b))$last a`lookup`zip b[1..]

Then "Django"!"Angular" is "Djangular".

Oh my, I am horrible at this. Agree that case makes this challenge "ugly", so 61 vs my 99... I learn to use lookup now, and infixes. And I just confused myself cause infix operator notation in Haskell ^= code in markdown.

rs, 24 bytes
(.*)(.).* .*?(\2.*)/\1\3

To copy the initial post from @refi64 here's the live demo and all test cases. The only improvement is that you can spare the \2 back reference by including it in the third group.
I didn't want to pollute with an answer that's actually a comment, but some person on Stack Exchange decided that you can't comment when you're a newcomer and that edits should be refused, because that should obviously be a comment. Thus, sorry for that misplaced content.

Hello, and welcome to PPCG! I'll comment for you if you want, and when you get 50 rep, you can comment too. However, Stack Exchange has a Be Nice policy, and unfortunately calling someone retarded is against the policy.

P.S. You can comment on your own posts.

xD They thought it all through! Thanks for the comment :D

PHP (270 bytes)
function portmanteau($s1, $s2){ $r = ''; $y = false; foreach(str_split($s1) as $c1){ $r .= $c1; foreach(str_split($s2) as $c2){ if($y){ $r.= $c2; } if(strtolower($c1)==strtolower($c2)){ $y = true; continue; } } if($y){ break; } } if(!$y) $r .= $s2; return ucfirst($r); }

Ungolfed:
function portmanteau($str1, $str2){
    $resultingString = '';

    $letterMatched = false;
    foreach(str_split($str1) as $char){
        $resultingString .= $char;

        foreach(str_split($str2) as $char2){
            if($letterMatched){
                $resultingString.= $char2;
            }

            if(strtolower($char)==strtolower($char2)){
                $letterMatched = true;
                continue;
            }
        }
        if($letterMatched){
            break;
        }
    }
    if(!$letterMatched) $resultingString .= $str2;

    return ucfirst($resultingString);
}

Usage:
echo portmanteau('Croissant', 'Donut');

Tested and works with the examples in the question.

What will it output ? Coissonut ?

No, "Cronut". It iterates/loops the characters in the first word first, then the second word.

Haskell, 148 bytes
C/case isn't restored though. Without case this was 99...
import Data.Char
o a b=|a==""=b|0<1=a
p""b=""
p a""=""
p a b|last a==head b=a++tail b|0<1=o(p(init a)b)(p a(tail b))
z a b=p(t a)(t b)
t=map toLower

You can make o, p, and z infix operators (try !, #, %) to save some bytes everywhere (as a!b=... is shorter than o a b=...).

Perl, 138
I'm sure someone can optimize this further
($a,$b,$l,$r)=(@ARGV,0);for$A(split//,$a){$r.=$A;for$B(split//,$b){$r.=$B if$l;if($A=~/$B/i){$l=1;next;}}last if$l;}$r.=$b if!$l;
138 w/ optimizations and output
($a,$b,$l,$r)=(@ARGV,0);for$A($a=~/./g){$r.=$A;for$B($b=~/./g){$r.=$B if$l;if($A=~/$B/i){$l=1;next;}}last if$l;}$r.=$b if!$l;print"$r\n";

rs, 26 bytes
(.*)(.).* .*?\2(.*)/\1\2\3

Live demo and all test cases.
So far this is the shortest answer!
The underlying logic is pretty simple. It just matches greedily on the first word (to get the last common character) and non-greedily on the second (to get the first common character). It then replaces the string with everything but the text in between the two characters.

@CyrilLemaire posted this: (.*)(.).* .*?(\2.*)/\1\3 (but does not have enough rep to comment)


text:
Find the largest independent set in a high-dimensional lattice-like graph
For a given positive integer n, consider all binary strings of length 2n-1.  For a given string S, let L be an array of length n which contains the count of the number of 1s in each substring of length n of S. For example, if n=3 and S = 01010 then L=[1,2,1]. We call L the counting array of S.
We say that two strings S1 and S2 of the same length match if their respective counting arrays L1 and L2 have the property that L1[i] <= 2*L2[i] and L2[i] <= 2*L1[i] for all i.
Task
For increasing n starting at n=1, the task is to find the size of the largest set of strings, each of length 2n-1 so that no two strings match.
Your code should output one number per value of n.
Score
Your score is the highest n for which no one else has posted a higher correct answer for any of your answers.  Clearly if you have all optimum answers then you will get the score for the highest n you post. However, even if your answer is not the optimum, you can still get the score if no one else can beat it.
Example answers
For n=1,2,3,4 I get 2,4,10,16.
Languages and libraries
You can use any available language and libraries you like. Where feasible, it would be good to be able to run your code so please include a full explanation for how to run/compile your code in linux if at all possible.
Leading entries

5 by Martin Büttner in Mathematica
6 by Reto Koradi in C++. Values are 2, 4, 10, 16, 31, 47, 75, 111, 164, 232, 328, 445, 606, 814, 1086.  The first 5 are known to be optimal.
7 by  Peter Taylor in Java. Values are  2, 4, 10, 16, 31, 47, 76, 111, 166, 235.
9 by joriki in Java. Values are 2, 4, 10, 16, 31, 47, 76, 112, 168.

I think it's more natural to understand the inequality when notated as L1[i]/2 <= L2[i] <= 2*L1[i].

Also, matching is not an equivalence relationship. match(A, B) and match(B, C) does not imply match(A, C) (same for the inverse). Example: [1] and [2] match, [2] and [3] match, but [1] and [3] do not. Similarly, [1,3] and [3,1] do not match, [3, 1] and [2, 3] do not match, but [1, 3] and [2, 3] match.

2, 4, 10, 16, 31, 47, 76, 112, 168
For each n, this Java code determines the possible counting arrays and then finds non-matching sets of increasing size, for each size starting with a random set and improving it by randomized steepest descent. In each step, one of the elements of the set is randomly uniformly selected and replaced by another counting array randomly uniformly selected among the ones not in use. The step is accepted if it does not increase the number of matches. This latter prescription appears to be crucial; accepting steps only if they reduce the number of matches isn't nearly as effective. The steps leaving the number of matches invariant allow the search space to be explored, and eventually some space may open up to avoid one of the matches. After 2^24 steps without improvement, the previous size is output for the present value of n, and n is incremented.
The results up to n = 9 are 2, 4, 10, 16, 31, 47, 76, 112, 168, improving on the previous results for n = 8 by one and for n = 9 by two. For higher values of n, the limit of 2^24 steps may have to be increased.
I also tried simulated annealing (with the number of matches as the energy), but without improvement over steepest descent.
Code
save as Question54354.java
compile with javac Question54354.java
run with java Question54354
import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class Question54354 {
    static class Array {
        int [] arr;

        public Array (int [] arr) {
            this.arr = arr;
        }

        public int hashCode () {
            return Arrays.hashCode (arr);
        }

        public boolean equals (Object o) {
            return Arrays.equals (((Array) o).arr,arr);
        }
    }

    static int [] indices;
    static int [] [] counts;
    static boolean [] used;

    static Random random = new Random (0);

    static boolean match (int [] c1,int [] c2) {
        for (int k = 0;k < c1.length;k++)
            if (c1 [k] > 2 * c2 [k] || c2 [k] > 2 * c1 [k])
                return false;
        return true;
    }

    static int matches (int i) {
        int result = 0;
        for (int j = 0;j < indices.length;j++)
            if (j != i && match (counts [indices [i]],counts [indices [j]]))
                result++;
        return result;
    }

    static void randomize (int i) {
        do
            indices [i] = random.nextInt (counts.length);
        while (used [indices [i]]);
    }

    public static void main (String [] args) {
        for (int n = 1,length = 1;;n++,length += 2) {
            int [] lookup = new int [1 << n];
            for (int string = 0;string < 1 << n;string++)
                for (int bit = 1;bit < 1 << n;bit <<= 1)
                    if ((string & bit) != 0)
                        lookup [string]++;
            Set<Array> arrays = new HashSet<Array> ();
            for (int string = 0;string < 1 << length;string++) {
                int [] count = new int [n];
                for (int i = 0;i < n;i++)
                    count [i] = lookup [(string >> i) & ((1 << n) - 1)];
                arrays.add (new Array (count));
            }
            counts = new int [arrays.size ()] [];
            int j = 0;
            for (Array array : arrays)
                counts [j++] = array.arr;
            used = new boolean [counts.length];

            int m;
            outer:
            for (m = 1;m <= counts.length;m++) {
                indices = new int [m];
                for (;;) {
                    Arrays.fill (used,false);
                    for (int i = 0;i < m;i++) {
                        randomize (i);
                        used [indices [i]] = true;
                    }
                    int matches = 0;
                    for (int i = 0;i < m;i++)
                        matches += matches (i);
                    matches /= 2;
                    int stagnation = 0;
                    while (matches != 0) {
                        int k = random.nextInt (m);
                        int oldMatches = matches (k);
                        int oldIndex = indices [k];
                        randomize (k);
                        int newMatches = matches (k);
                        if (newMatches <= oldMatches) {
                            if (newMatches < oldMatches) {
                                matches += newMatches - oldMatches;
                                stagnation = 0;
                            }
                            used [oldIndex] = false;
                            used [indices [k]] = true;
                        }
                        else
                            indices [k] = oldIndex;

                        if (++stagnation == 0x1000000)
                            break outer;
                    }
                    break;
                }
            }
            System.out.println (n + " : " + (m - 1));
        }
    }
}

A very nice improvement!

2, 4, 10, 16, 31, 47, 76, 111, 166, 235
Notes
If we consider a graph G with vertices 0 to n and edges joining two numbers which match, then the tensor power G^n has vertices (x_0, ..., x_{n-1}) forming the Cartesian power {0, ..., n}^n and edges between matching tuples. The graph of interest is the subgraph of G^n induced by those vertices which correspond to the possible "counting arrays".
So the first subtask is to generate those vertices. The naïve approach enumerates over 2^{2n-1} strings, or on the order of 4^n. But if we instead look at the array of first differences of the counting arrays we find that there are only 3^n possibilities, and from the first differences we can deduce the range of possible initial values by requiring that no element in the zeroth differences is less than 0 or greater than n.
We then want to find the maximum independent set. I'm using one theorem and two heuristics:

Theorem: the maximum independent set of a disjoint union of graphs is the union of their maximum independent sets. So if we break a graph down into unconnected components we can simplify the problem.
Heuristic: assume that (n, n, ..., n) will be in a maximum independent set. There's a fairly large clique of vertices {m, m+1, ..., n}^n where m is the smallest integer which matches n; (n, n, ..., n) is guaranteed to have no matches outside that clique.
Heuristic: take the greedy approach of selecting the vertex of lowest degree.

On my computer this finds 111 for n=8 in 16 seconds, 166 for n=9 in about 8 minutes, and 235 for n=10 in about 2 hours.
Code
Save as PPCG54354.java, compile as javac PPCG54354.java, and run as java PPCG54354.
import java.util.*;

public class PPCG54354 {
    public static void main(String[] args) {
        for (int n = 1; n < 20; n++) {
            long start = System.nanoTime();

            Set<Vertex> constructive = new HashSet<Vertex>();
            for (int i = 0; i < (int)Math.pow(3, n-1); i++) {
                int min = 0, max = 1, diffs[] = new int[n-1];
                for (int j = i, k = 0; k < n-1; j /= 3, k++) {
                    int delta = (j % 3) - 1;
                    if (delta == -1) min++;
                    if (delta != 1) max++;
                    diffs[k] = delta;
                }

                for (; min <= max; min++) constructive.add(new Vertex(min, diffs));
            }

            // Heuristic: favour (n, n, ..., n)
            Vertex max = new Vertex(n, new int[n-1]);
            Iterator<Vertex> it = constructive.iterator();
            while (it.hasNext()) {
                Vertex v = it.next();
                if (v.matches(max) && !v.equals(max)) it.remove();
            }

            Set<Vertex> ind = independentSet(constructive, n);
            System.out.println(ind.size() + " after " + ((System.nanoTime() - start) / 1000000000L) + " secs");
        }
    }

    private static Set<Vertex> independentSet(Set<Vertex> vertices, int dim) {
        if (vertices.size() < 2) return vertices;

        for (int idx = 0; idx < dim; idx++) {
            Set<Set<Vertex>> p = connectedComponents(vertices, idx);
            if (p.size() > 1) {
                Set<Vertex> ind = new HashSet<Vertex>();
                for (Set<Vertex> part : connectedComponents(vertices, idx)) {
                    ind.addAll(independentSet(part, dim));
                }
                return ind;
            }
        }

        // Greedy
        int minMatches = Integer.MAX_VALUE;
        Vertex minV = null;
        for (Vertex v0 : vertices) {
            int numMatches = 0;
            for (Vertex vi : vertices) if (v0.matches(vi)) numMatches++;
            if (numMatches < minMatches) {
                minMatches = numMatches;
                minV = v0;
            }
        }

        Set<Vertex> nonmatch = new HashSet<Vertex>();
        for (Vertex vi : vertices) if (!minV.matches(vi)) nonmatch.add(vi);
        Set<Vertex> ind = independentSet(nonmatch, dim);
        ind.add(minV);
        return ind;
    }

    // Separates out a set of vertices which form connected components when projected into the idx axis.
    private static Set<Set<Vertex>> connectedComponents(Set<Vertex> vertices, final int idx) {
        List<Vertex> sorted = new ArrayList<Vertex>(vertices);
        Collections.sort(sorted, new Comparator<Vertex>() {
                public int compare(Vertex a, Vertex b) {
                    return a.x[idx] - b.x[idx];
                }
            });

        Set<Set<Vertex>> connectedComponents = new HashSet<Set<Vertex>>();
        Set<Vertex> current = new HashSet<Vertex>();
        int currentVal = 0;
        for (Vertex v : sorted) {
            if (!match(currentVal, v.x[idx]) && !current.isEmpty()) {
                connectedComponents.add(current);
                current = new HashSet<Vertex>();
            }

            current.add(v);
            currentVal = v.x[idx];
        }

        if (!current.isEmpty()) connectedComponents.add(current);
        return connectedComponents;
    }

    private static boolean match(int a, int b) {
        return a <= 2 * b && b <= 2 * a;
    }

    private static class Vertex {
        final int[] x;
        private final int h;

        Vertex(int[] x) {
            this.x = x.clone();

            int _h = 0;
            for (int xi : x) _h = _h * 37 + xi;
            h = _h;
        }

        Vertex(int x0, int[] diffs) {
            x = new int[diffs.length + 1];
            x[0] = x0;
            for (int i = 0; i < diffs.length; i++) x[i+1] = x[i] + diffs[i];

            int _h = 0;
            for (int xi : x) _h = _h * 37 + xi;
            h = _h;
        }

        public boolean matches(Vertex v) {
            if (v == this) return true;
            if (x.length != v.x.length) throw new IllegalArgumentException("v");
            for (int i = 0; i < x.length; i++) {
                if (!match(x[i], v.x[i])) return false;
            }
            return true;
        }

        @Override
        public int hashCode() {
            return h;
        }

        @Override
        public boolean equals(Object obj) {
            return (obj instanceof Vertex) && equals((Vertex)obj);
        }

        public boolean equals(Vertex v) {
            if (v == this) return true;
            if (x.length != v.x.length) return false;
            for (int i = 0; i < x.length; i++) {
                if (x[i] != v.x[i]) return false;
            }
            return true;
        }

        @Override
        public String toString() {
            if (x.length == 0) return "e";

            StringBuilder sb = new StringBuilder(x.length);
            for (int xi : x) sb.append(xi < 10 ? (char)('0' + xi) : (char)('A' + xi - 10));
            return sb.toString();
        }
    }
}

Mathematica, n = 5, 31 strings
I just wrote a brute force solution using Mathematica's built-ins to verify Lembik's example answers, but it can handle n = 5 as well:
n = 5;
s = Tuples[{0, 1}, 2 n - 1];
l = Total /@ Partition[#, n, 1] & /@ s
g = Graph[l,
  Cases[Join @@ Outer[UndirectedEdge, l, l, 1],
   a_ <-> b_ /;
    a != b && And @@ Thread[a <= 2 b] && And @@ Thread[b <= 2 a]]]
set = First@FindIndependentVertexSet[g]
Length@set

As a bonus, this code produces a visualisation of the problem as a graph where each edge indicates two matching strings.
Here is the graph for n = 3:

At first I thought the graph was nicely symmetric, but then I saw the slightly offset point on the left. Can not unsee :(

C++ (heuristic): 2, 4, 10, 16, 31, 47, 75, 111, 164, 232, 328, 445, 606, 814, 1086
This is slightly behind Peter Taylor's result, being 1 to 3 lower for n=7, 9 and 10. The advantage is that it's much faster, so I can run it for higher values of n. And it can be understood without any fancy math. ;)
The current code is dimensioned to run up to n=15. Run times increase roughly by a factor of 4 for each increase in n. For example, it was 0.008 second for n=7, 0.07 seconds for n=9, 1.34 seconds for n=11, 27 seconds for n=13, and 9 minutes for n=15.
There are two key observations I used:

Instead of operating on the values themselves, the heuristic operates on counting arrays. To do this, a list of all unique counting arrays is generated first.
Using counting arrays with small values is more beneficial, since they eliminate less of the solution space. This is based on each count c excluding the range of c / 2 to 2 * c from other values. For smaller values of c, this range is smaller, which means that fewer values are excluded by using it.

Generate Unique Counting Arrays
I went brute force on this one, iterating through all values, generating the count array for each of them, and uniquifying the resulting list. This could certainly be done more efficiently, but it is good enough for the kinds of values we're operating with.
This is extremely quick for the small values. For the larger values, the overhead does become substantial. For example, for n=15, it uses about 75% of the whole runtime. This would definitely be an area to look at when trying to go much higher than n=15. Even just the memory usage for building a list of the counting arrays for all values would start to become problematic.
The number of unique counting arrays is about 6% of the number of values for n=15. This relative count becomes smaller as n becomes larger.
Greedy Selection of Counting Array Values
The main part of the algorithm selects counting array values from the generated list using a simple greedy approach.
Based on the theory that using counting arrays with small counts is beneficial, the counting arrays are sorted by the sum of their counts.
They are then checked in order, and a value is selected if it is compatible with all previously used values. So this involves one single linear pass through the unique counting arrays, where each candidate is compared to the values that were previously selected.
I have some ideas on how the heuristic could potentially be improved. But this seemed like a reasonable starting point, and the results looked quite good.
Code
This is not highly optimized. I had a more elaborate data structure at some point, but it would have needed more work to generalize it beyond n=8, and the difference in performance did not seem very substantial.
#include <cstdint>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <sstream>
#include <iostream>

typedef uint32_t Value;

class Counter {
public:
    static void setN(int n);

    Counter();
    Counter(Value val);

    bool operator==(const Counter& rhs) const;
    bool operator<(const Counter& rhs) const;

    bool collides(const Counter& other) const;

private:
    static const int FIELD_BITS = 4;
    static const uint64_t FIELD_MASK = 0x0f;

    static int m_n;
    static Value m_valMask;

    uint64_t fieldSum() const;

    uint64_t m_fields;
};

void Counter::setN(int n) {
    m_n = n;
    m_valMask = (static_cast<Value>(1) << n) - 1;
}

Counter::Counter()
  : m_fields(0) {
}

Counter::Counter(Value val) {
    m_fields = 0;
    for (int k = 0; k < m_n; ++k) {
        m_fields <<= FIELD_BITS;
        m_fields |= __builtin_popcount(val & m_valMask);
        val >>= 1;
    }
}

bool Counter::operator==(const Counter& rhs) const {
    return m_fields == rhs.m_fields;
}

bool Counter::operator<(const Counter& rhs) const {
    uint64_t lhsSum = fieldSum();
    uint64_t rhsSum = rhs.fieldSum();
    if (lhsSum < rhsSum) {
        return true;
    }
    if (lhsSum > rhsSum) {
        return false;
    }

    return m_fields < rhs.m_fields;
}

bool Counter::collides(const Counter& other) const {
    uint64_t fields1 = m_fields;
    uint64_t fields2 = other.m_fields;

    for (int k = 0; k < m_n; ++k) {
        uint64_t c1 = fields1 & FIELD_MASK;
        uint64_t c2 = fields2 & FIELD_MASK;

        if (c1 > 2 * c2 || c2 > 2 * c1) {
            return false;
        }

        fields1 >>= FIELD_BITS;
        fields2 >>= FIELD_BITS;
    }

    return true;
}

int Counter::m_n = 0;
Value Counter::m_valMask = 0;

uint64_t Counter::fieldSum() const {
    uint64_t fields = m_fields;
    uint64_t sum = 0;
    for (int k = 0; k < m_n; ++k) {
        sum += fields & FIELD_MASK;
        fields >>= FIELD_BITS;
    }

    return sum;
}

typedef std::vector<Counter> Counters;

int main(int argc, char* argv[]) {
    int n = 0;
    std::istringstream strm(argv[1]);
    strm >> n;

    Counter::setN(n);

    int nBit = 2 * n - 1;
    Value maxVal = static_cast<Value>(1) << nBit;

    Counters allCounters;

    for (Value val = 0; val < maxVal; ++val) {
        Counter counter(val);
        allCounters.push_back(counter);
    }

    std::sort(allCounters.begin(), allCounters.end());

    Counters::iterator uniqEnd =
        std::unique(allCounters.begin(), allCounters.end());
    allCounters.resize(std::distance(allCounters.begin(), uniqEnd));

    Counters solCounters;
    int nSol = 0;

    for (Value idx = 0; idx < allCounters.size(); ++idx) {
        const Counter& counter = allCounters[idx];

        bool valid = true;
        for (int iSol = 0; iSol < nSol; ++iSol) {
            if (solCounters[iSol].collides(counter)) {
                valid = false;
                break;
            }
        }

        if (valid) {
            solCounters.push_back(counter);
            ++nSol;
        }
    }

    std::cout << "result: " << nSol << std::endl;

    return 0;
}

I had recursive solutions based on similar code that are guaranteed to find the maximum. But it took a while for n=4 already. It might have finished for n=5 with some patience. You must have used a better backtracking strategy to even make it to n=7. Was yours heuristic, or did it explore the whole solution space? I'm contemplating some ideas on how to make this better, either by fine tuning the sorting order, or by maybe not being purely greedy.

My understanding is that there is no backtracking in Peter Taylor's answer. It is purely greedy.  The main tricks are that he reduces the number of counting arrays to 3^n and the two heuristics he describes.

@Lembik My comment was in response to a comment that was deleted. The number of counting arrays should be the same, since I build that based on actual values, and reduce it to only the unique ones. I updated a backtracking version of the algorithm. Even though it does not terminate within a reasonable time, it finds 76 for n=7 quickly. But trying it for n=9, it was still stuck at 164 when I stopped it after 20 minutes. So extending this with a limited form of simple backtracking does not look generally promising.


text:
Golfing with User Agents
Usually when performing an internet challenge, there's no problem with having to specify a user agent, but when it comes to dealing with Google, it changes.
Google blacklists the Urllib user agent, presumably to stop spambots, so you have to specify a user agent. This takes up many bytes, and is frankly rather annoying.
Example 1. Example 2. Example 3.
Note: I have updated my Python answers to use the tip suggested below
So how do you get around this problem using the shortest number of bytes?

Are you sure this question isn't missing a language tag?

@PeterTaylor Well although the question is oriented towards Python, I was hoping that the solution could be used to help with other languages

The requests module, if allowed, is much shorter and easier than urllib in Python (2 and 3):
__import__('requests').get('url').text

On my computer, the user agent defaults to:
python-requests/2.3.0 CPython/3.4.3 Darwin/14.3.0


text:
Magic Square Challenge
For the purpose of this question, a magic square is an n×n square of (not necessarily distinct) positive integers, where all rows, columns, and main diagonals add to a "magic constant" m.
Your Task
Create a function or full program that, given the magic number m and a list representing a square with at most one wrong number in each row and column, will output a list with the entries rearranged to represent a correct square. Your program will be expected to handle any solvable square of any size. Your program should take less than twenty minutes for n=7 or smaller. Assume that all input is solvable.
Example Input (list, m)
[16, 16, 11, 9, 14, 17, 9, 29, 13, 1, 15, 5, 6, 16, 15, 7, 3, 17, 11, 12, 14, 17, 3, 8, 6], 58

which represents this square1:

16 16 11 09 14
17 09 29 13 01
   15 05 06 16 15
   07 03 17 11 12
   14 17 03 08 06

A compliant solution has to solve the following 7x7 square within the time limit.
[31, 19, 10, 13, 14, 32, 15, 6, 21, 17, 22, 30, 17, 7, 17, 30, 17, 24, 17, 11, 8, 7, 22, 33, 13, 15, 17, 11, 14, 16, 21, 22, 13, 11, 29, 16, 13, 3, 19, 12, 12, 43, 27, 13, 19, 13, 20, 18, 11], 123

Example Output
For the first test case, this is the only correct solution.
[16, 16, 3, 9, 14, 6, 9, 29, 13, 1, 15, 5, 6, 17, 15, 7, 11, 17, 11, 12, 14, 17, 3, 8, 16]

For a bonus of -10, format your output into a square and pad single digits with zeroes as below.2

16 16 03 09 14
06 09 29 13 01
   15 05 06 17 15
   07 11 17 11 12
   14 17 03 08 16

1 Bolded numbers are in incorrect cells.
2 Bolded numbers have switched cells.

There is no well-defined answer. I might as well always print out the same solved magic square, because I can argue that I corrected the input to it.

@orlp I updated my question to be more specific. Now it states that you can't change any of the numbers in the original list, only move them around, and not add any new ones.

Is the input guaranteed to be solveable? What should we do if it isn't?

Do we have to handle any dimensions or will it always be 5x5?

The golfiest approach I can think of is going to be sheer brute force on permutations. Is there a time constraint, or is this okay?

The value of n is redundant, right? It could easily be derived from the values. And I was just about to ask the same thing as @Geobits. If you don't constrain the runtime, you'll see solutions that theoretically solve this, but not before the sun burns out.

@RetoKoradi You can derive n by summing everything up and and dividing by the width/height of the square but I feel like it would be easier to take it as input. Also the rules say it's supposed to be taken as input

@Geobits I updated my question to have a time constraint since brute force permutations are boring and I'd like to see some better answers than that

@PeterTaylor I also said the time constraint only applies up to squares of size 7x7.

@PeterTaylor No I will not change it. I'm just putting a time constraint on it so people won't try all permutations of the square. That would be 49^49 permutations for a 7x7 square and I know for a fact that it doesn't run in less than 20 minutes. Even 5x5 squares wont meet the time constraint. If someone shows me an 8x8 or larger square then the time constraint won't matter for that square but if the same program for a 7x7 squares takes longer than 20 minutes then it is not a valid solution

Not that it matters, but there are at most 49! distinct permutations of a 7x7 square.

@Dennis 49! = 608281864034267560872252163321295376887552831379210240000000000. 49^49 = 66009724686219550843768321818371771650147004059278069406814190436565131829325062449.

just a slightly unreasonable number of recursive steps

Have you written a valid solution yourself? I'm not convinced this is even possible.

I've written a simple one but I know the logic behind a more complex one but I just can't figure out how to write it in code for the life of me. I have the grid simplified down to a point where permutations are a viable option but I have two separate lists that need to be compared while finding each new list of permutations and I can't figure out how to do that part.

I do have a solver that can handle one mismatched number in each row/column but not for multiple. I'm thinking about updating the problem to only handle the cases of one in each row/column since I can't figure out the multiple myself. Let me know what you think about that

@SirParselot Yes, I think you it would be good to restrict it to a single mismatch.

@xnor I did update so it is now a single mismatch although I left the multiple mismatch up if someone wants an extra challenge for some reason.

@SirParselot The update is easy to miss in the example input section. You should explain it clearly under "Your task", perhaps with an example to illustrate what a single mismatch is.

@SirParselot I removed the multiple-mismatch test cases, because that kind of broke "objective winning criterion"; please roll back any edits you disagree with.

What does "at most one wrong number in each row and column" mean? Is it that there exists a solution which changes at most one cell in each row and column, or is it that there exists a solution in which each solved row differs from the corresponding input row in at most a replacement of one entry and a permutation, and likewise for columns?

CJam, 73 70 bytes
q~:Q,mQ:Le!{QL/.{1$W$W*t_:+W*t}:Te_$Q$=Tz{W%_L,.=a\}2*++::+)-!*}=&T"%02d "ffe%N*

The above code is 80 bytes long and qualifies for the bonus.
Time complexity is O(n!) for n×n squares. For 9×9, this translates to 7 seconds on my machine.
Try it online: permalink for Chrome | permalink for Firefox

Nice work, +1. As a complete aside, the permalink for Chrome works in Safari but the Firefox one does not.