text:
Divide Two Numbers Using Long Division
Your challenge is to divide two numbers using long division. The method we used to use in old days of school to divide two numbers.
Example here
You should NOT use / or any other division operator in your code.
Also, this is not ascii-art
Example:
Input  : 4 2 (4 divided by 2)

Output : 2 0 (here 2 is quotient and 0 is remainder)

Another example
Input  : 7182 15 (7182 divided by 15)

Output : 478 12 (7170 is quotient and 12 is remainder)

The answer with most up-votes after 24 hours wins because this is a popularity contest.

Even using the hand method I still mentally divide each grouping. I guess you could subtract in a loop or multiply by the inverse, but those just seem like trivial workarounds. Also, you might want to give better examples than single-digit numbers if you want the "long-hand" method to show clearly.

@Geobits is right, everyone still uses division (mostly mentally) even when performing long division. I suggest the modifying the requirement like "division operators may only be used if the result is less than 10". All that long division serves to do is break a large division problem into a bunch of smaller division problems where each quotient is guaranteed to be in the range of 0 through 9.

please explain the requirement in simple words (sorry, I am not so good at english !)

In the old days of school, computers were expensive, so we had calculators instead.  I used the fingers on my hands to type division calculations into my calculator.  Is this the "hand" method you refer to?

@DigitalTrauma NOOO the one we used ti do by pen/pencil and a paper!

@ The downvoter, please explain the reason of your down-vote!

24 hours is too little time. It is recommended that you wait for a while (maybe a week), and update the winner every now and then.

The previous long division of integers question had a spec and required output which made clear what calculations had to be performed. The long division of polynomials question would be most easily implemented by long division even if that weren't specified. This one is so imprecise that you're praising answers which don't even pretend to follow what little instruction it gives.

Aww, too bad it is put on hold just as I finished my answer :)

Reopen! F#:
let d a b = -1+Seq.find((*)b>>(<)a)[1..a]

It should have stayed closed if you are going to Accept an answer which does not follow spec and only a short time after re-opening. What a waste.

C
Not exactly a long division - this answer uses the method used in the real old days.
#include <stdio.h>
#include <stdlib.h>
int main() {
    int a,b;
    scanf("%d %d", &a, &b);
    int *p=calloc(b, sizeof(int));
    int *q=p;
    while(a--) {
        (*p)++;
        if(p-q<b-1) p++;
        else p-=b-1;
    }
    p=q;
    int r=0, i;
    for(i=0; i<b; i++) r+=p[i]-p[b-1];
    printf("%d %d\n", p[b-1], r);
    return 0;
}

Explanation:
Suppose you are given a number of sheep and you need to split them up into b number of groups. The method used here is to assign each sheep into a different group until the total number of groups reaches b, then start from the first group again. This repeats until there are no more sheep. Then, the quotient will be the number of sheep in the last group, and the remainder will be the sum of the differences between each group and the last group.
An illustration for 8/3:
       |Group 1 | Group 2 | Group 3
-------------------------------------
       | 1      | 2       | 3        // first sheep in group 1, second sheep in group 2, etc
       | 4      | 5       | 6
       | 7      | 8       |
-------------------------------------
total: | 3      | 3       | 2

So the quotient is 2 and the remainder is (3-2)+(3-2)=2.

This one is good!

Actually i would divide the Sheep into group of size b. If i have less than b sheeps left thats the remainder.

Bash + coreutils
Forget what you learned in school.  Nobody uses long division.  Its always important to chose the right tool for the job.  dd is known by some as the swiss army knife of the command-line tools, so it really is the right tool for every job!:
#!/bin/bash

q=$(dd if=/dev/zero of=/dev/null ibs=$1 count=1 obs=$2 2>&1 | grep out | cut -d+ -f1)
r=$(( $1 - $(dd if=/dev/zero of=/dev/null bs=$q count=$2 2>&1 | grep bytes | cut -d' ' -f1) ))
echo $q $r

Output:

$ ./divide.sh 4 2
2 0
$ ./divide.sh 7182 15
478 12
$

Sorry, I know this is a subversive, trolly answer, but I just couldn't resist.  Cue the downvotes...

Hurray (and +1) for dd!

C
Long division! At least how a standard computer algorithm might do it, one binary digit (bit) at a time. Handles negatives, too.
#include <stdio.h>

#define INT_BITS (sizeof(int)*8)

typedef struct div_result div_result;
struct div_result {
    int quotient;
    int remainder;
};

div_result divide(int dividend, int divisor) {
    int negative = (dividend < 0) ^ (divisor < 0);

    if (divisor == 0) {
        result.quotient = dividend < 0 ? INT_MIN : INT_MAX;
        result.remainder = 0;
        return result;
    }

    if ((dividend == INT_MIN) && (divisor == -1)) {
        result.quotient = INT_MAX;
        result.remainder = 0;
        return result;
    }

    if (dividend < 0) {
        dividend = -dividend;
    }
    if (divisor < 0) {
        divisor = -divisor;
    }

    int quotient = 0, remainder = 0;

    for (int i = 0; i < sizeof(int)*8; i++) {
        quotient <<= 1;

        remainder <<= 1;
        remainder += (dividend >> (INT_BITS - 1)) & 1;
        dividend <<= 1;

        if (remainder >= divisor) {
            remainder -= divisor;
            quotient++;
        }
    }

    div_result result;
    if (negative) {
        result.quotient = -quotient;
        result.remainder = -remainder;
    } else {
        result.quotient = quotient;
        result.remainder = remainder;
    }
    return result;
}

int main() {
    int dividend, divisor;
    scanf("%i%i", &dividend, &divisor);

    div_result result = divide(dividend, divisor);
    printf("%i %i\r\n", result.quotient, result.remainder);
}

It can be seen in action here. I chose to handle negative results to be symmetrical to positive results, but with both the quotient and remainder negative.
Handling of edge cases is done with best effort. Division by zero returns the integer of highest magnitude with the same sign as the dividend (that's INT_MIN or INT_MAX), and INT_MIN / -1 returns INT_MAX.

@ The downvoter, a reason would be appreciated!

This a good answer, and completely within spec as far as I can see.  Downvoters gonna downvote I suppose.  +1 from me though.

Julia
Here is an entry that not only is free from division but doesn't employ any multiplication either. It does the long division quite literally by using more string manipulation than arithmetic. It also prints out an ASCII version of what the long-division would look like on a sheet of paper (at least the way I learned it)
function divide(x,y)
    if y > x
        return 0, x
    end

    x = "$x"
    q = ""
    r = ""

    workings = ""

    for i = 1:length(x)
        r = "$(r)0"
        num = int(r) + int(x[i:i])
        sum = 0
        m = 0
        while sum+y <= num
            m += 1
            sum += y
        end
        r = string(num-sum)
        q = "$q$m"
        ls = length(string(sum))
        workings *= repeat(" ", i-ls) * "-$sum\n"
        workings *= repeat(" ", i+1-ls) * repeat("-", ls) * "\n"
        workings *= repeat(" ", i+1-length(r)) * r * (i >= length(x) ? "" : x[i+1:i+1]) * "\n"
    end

    workings *= repeat(" ", length(x)-length(r)+1) * repeat("=", length(r)) * "\n"

    print(" $x : $y = $(int(q)) R $r\n$workings")
    int(q), int(r)
end

Results (the (q,r) line at the end is just Julia printing the result of the function call):
> divide(5,3)         > divide(4138,17)           > divide(7182,15)

 5 : 3 = 1 R 2         4138 : 17 = 243 R 7         7182 : 15 = 478 R 12
-3                    -0                          -0
 -                     -                           -
 2                     41                          71
 =                    -34                         -60
                       --                          --
(1,2)                   73                         118
                       -68                        -105
                        --                         ---
                         58                         132
                        -51                        -120
                         --                         ---
                          7                          12
                          =                          ==

                      (243,7)                     (478,12)

I suppose I could get rid of the remaining arithmetic by using a unary number system, repeat and length but that feels more like multiplying than not using arithmetic.
Don't even try dividing by zero! (Seriously, who would do long division for that?) Also don't try negative numbers.

Python
def divide(a, b):
    q = 0
    while a >= b:
       a -= b
       q += 1
    return (q, a)

This is just the same as the C answer by Kninnug

Too right you are, I don't know C so I missed that. Have given him an upvote.

C#
Not exactly golfing, but IMO it's pretty easy to follow. It only uses the / operator after it has broken the dividend down into smaller sections. It performs division in the "old" way. For example, for 1907 / 12, it takes 19 and divides it by 12, then carries the remainder 7 over, divides 70 (from 707) by 12, etc.
string divisor = "12";
string dividend = "1907";
string output = "";
do
{
    double dd = Convert.ToDouble(dividend.Substring(0, divisor.Length));
    double dr = Convert.ToDouble(divisor);
    if (dd >= dr)
    {
        string s = (dd / dr).ToString();
        output += s.Substring(0, s.Contains(".") ? s.IndexOf(".") : s.Length);
        dividend = dd % dr + dividend.Substring(divisor.Length);
    }
    else
    {
        double d2 = Convert.ToDouble(dividend.Substring(0, divisor.Length + 1));
        string s = (d2 / dr).ToString();
        output += s.Substring(0, s.Contains(".") ? s.IndexOf(".") : s.Length);
        dividend = d2 % dr + dividend.Substring(divisor.Length + 1);
     }
 } while (Convert.ToDouble(dividend) >= Convert.ToDouble(divisor))
 for (int i = 0; i < dividend.Length - 1; i++ )
     if (dividend[i].ToString() == "0") output += "0";
 dividend = Convert.ToInt32(dividend).ToString();
 Console.WriteLine("result: " + output + " r." + dividend);

64 characters in Ruby
def d a,b;x=0;while((x+1)*b<=a);x+=1;end;puts"#{x} #{a-x*b}";end

Example:
pry(main)> d 31,6
5 1
=> nil

This looks identical to the answers by Kninnug and justinfay? (It's shorter of course)

Oh... I didn't know we had to have a unique approach. I just wanted to write a super short one.

No that's fair enough. I was just wondering whether I overlooked something else that sets this answer apart from the other two (except its shortness). Although neither of these three answers technically implements long division. ;)

Oh, well. It was fun to write either way.

C 371 with whitespaces
Includes cases for div by zero and divisor<0. Uses subtraction loop.
#include <stdio.h>
int a, b, n, r;
void e(int i, int j){ printf("Output: %d %d\n", i, j); }
void g()
{
    if (scanf_s("%d %d", &a, &b))
    {
        r = 1;
        if (b < 0){ r = -1; b = r*b; }
        if (!b) e(0, 0);
        else{
            if (b>a){
                n = 0;
            }
            else{
                n = 1;
                while ((a -= b) >= b){
                    n++;
                }

            }
            e(r*n, a);
        }
    }
}

int main(){ g();}

Brainfuck
works only for numbers between 1 and 9
Do not fit the rules, so I don't expect to win but answers in brainfuck are always awesome.
++++++++>,>,<<[>------>------<<-]>[->-[>+>>]>[+[-<+>]>+>>]<<<<<]++++++++[>>++++++>++++++<<<-]>>>.<.

Based on divmod method
Test it here (and try to change input) : http://ideone.com/9L2yYf
Some tests :

74 returns 13
  82 returns 40
  92 returns 41

 C
Sorry for the bulky code, I am still a noob. The idea is to grab the first piece of bits from n such that k < bits, then extract each bit of n from that point on and update remainder and quotient along the way.
#include <stdio.h>

unsigned int rightMostBit(unsigned int n){
   unsigned int bitmask=0x1 << 31;
   int position=31;
   while((bitmask & n)==0 && position>=0){
        position-=1;
        bitmask = bitmask>>1;
   }
   return position;
}

unsigned int extractBits(unsigned int n, unsigned int start, unsigned int end){
    unsigned int unitMask=0x1;
    unsigned int mask=unitMask << start;
    for(int i=start;i<end;i++){
        mask= (mask | (mask << 1));
    }
    return  ((mask &  n) >> start);
}

void longDivision(unsigned int n, unsigned int k)
{
      unsigned int q=0;
      unsigned int head=rightMostBit(n);
      int tail=head;
      unsigned int r=extractBits(n,tail,head);
      while(k>r && tail>=0){
            tail-=1;
            r=extractBits(n,tail,head);
      }

      unsigned int pointMask= 0x1 << tail;

      while(pointMask>0) //scan all bits of n
      {
           if(k<= r){ //If k less than r, we can do division
              r-= k ; //subtraction
              q=q << 1; //make space
              q = q | 0x1;  //add a 1 to quotient
           }else{
                q=q << 1; //make space
                q= q | 0x0; //k > r, so add 0 to quotient
           }
           pointMask=pointMask >> 1;
           if(pointMask!=0){
                if((pointMask & n)){
                     r=((r << 1) | 1);
                }else{
                     r=((r << 1) | 0);
                }
           }
      }
  printf("quotient: %d, remainder: %d \n",q,r);
}

Edited:170 with Excel VBA:
Sub Long_Div(n As Integer, d As Integer)
j = 1
If d <> 0 Then
If (n * d) < 0 Then
j = -1
End If
Do While (Abs(n) >= Abs(d))
n = Abs(n) - Abs(d)
i = i + 1
Loop

MsgBox i * j & " " & n
Else:
MsgBox "can't divide by zero"
End If
End Sub

D
Horribly roundabout method that has more steps than is probably necessary to divide a number, but there you are.
import std.stdio;
import std.traits : isIntegral, isUnsigned;
import std.conv   : to;

TNum divide( TNum )( TNum dividend, TNum divisor, out TNum remainder ) if( isIntegral!TNum )
{
    TNum quot = 0,
         rem  = dividend,
         prod = divisor,
         t    = 1,
         max  = ( ( TNum.sizeof * 8 ) - 1 ) ^^ 2;

    while( t < max  && prod < rem )
    {
        prod = prod * 2;
        t    = t    * 2;
    }

    while( t >= 1 )
    {
        if( prod <= rem )
        {
            quot = quot + t;
            rem  = rem - prod;
        }

        static if( isUnsigned!TNum )
        {
            prod >>>= 1;
            t    >>>= 1;
        }
        else
        {
            prod >>= 1;
            t    >>= 1;
        }
    }

    remainder = rem;
    return quot;
}

void main( string[] args )
{
    if( args.length < 3 )
        return;

    long dividend  = args[1].to!long;
    long divisor   = args[2].to!long;
    long remainder = 0;
    long result    = divide( dividend, divisor, remainder );

    if( remainder == 0 )
        "%s / %s = %s".writefln( dividend, divisor, result );
    else
        "%s / %s = %s (r %s)".writefln( dividend, divisor, result, remainder );
}

Obviously / appears in the code, but it's in a string and is just for output. There's no string interpolation in D, so it's not diving anything.

Python
Advantages:

Go as Precise as you want or can handle
Find out the repetitiveness from the quotient
Fast

Late to the party but here you go:
def ManualDivision(Dividend, Divisor, acQPrecision, BreakOnRepetitive):

    Repetitive = False
    RepetitiveIndex = 0
    bcQComplete = False
    acQComplete = False
    bcQ = ''   #before comma Quotient
    acQ = ''   #after comma Quotient
    history = []
    a = 0
    b = 0

    while (not bcQComplete or not acQComplete):
        if not bcQComplete:
            for digit in map(int, str(Dividend)):
                a = int(str(a) + str(digit))
                if a in history:
                    if not Repetitive:
                        Repetitive = True
                        RepetitiveIndex = len(history) - len(bcQ)
                    if BreakOnRepetitive:
                        break
                else:
                    history.append(a)
                if a < Divisor:
                    b = 0
                    bcQ += '0'
                else:
                    pQ = 0
                    result = a - Divisor
                    while result >= 1:
                        pQ += 1
                        result -= Divisor
                    b = pQ * Divisor
                    bcQ += str(pQ)
                a -= b
            bcQComplete = True

        if not acQComplete:
            acQPrecision -= 1
            if acQPrecision <= 0:
                acQComplete = True
            a = int(str(a) + str('0'))
            if a in history:
                if not Repetitive:
                    Repetitive = True
                    RepetitiveIndex = len(history) - len(bcQ)
                if BreakOnRepetitive:
                    break
            else:
                history.append(a)
            if a < Divisor:
                b = 0
                acQ += '0'
            else:
                pQ = 0
                result = a - Divisor
                while result >= 1:
                    pQ += 1
                    result -= Divisor
                b = pQ * Divisor
                acQ += str(pQ)
            a-=b
       return '{0}.{1} \nRepetitive: {2} from position {3} acQ \nHistory:{4}'.format(bcQ, acQ, Repetitive, RepetitiveIndex, history)

Result
Quotient = ManualDivision(91,256,100,False) #Dividend = 91, Divisor = 256, precision= 100, breakonrepetitive=False
print(Quotient)

00.3554687499999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
Repetitive: True from position 9 acQ
History:[9, 91, 910, 1420, 1400, 1200, 1760, 2240, 1920, 1280, 2560]

Python
Using recursion
def divide(a, b, q=0):
    if a < b:
        return (q, a)
    return divide(a - b, b, q+1)


text:
Taking the dog for a walk
My dog is barking at me, but I'm too lazy to take him for a walk. I have an idea! I'll get the people at Code Golf to do it for me!
Your challenge is to simulate a dog's walk. Here are the rules for walking the dog:

The human (H) will start at 0,0 on a (Cartesian) coordinate plane, and will randomly go one space either up, left, right, or down every second.
The dog (D) will start at the same location, and will go either zero, one, two, or three spaces either up, left, right, or down every second (randomly, of course). The dog is less predictable and will sometimes run faster or stop completely.
The dog will never get more than a certain amount of units away from the human (in Euclidean distance), which is the length of the leash (L). For example, if L is 6, a valid position would be H(0,0) D(4,4) (since the distance is about 5.65 units), but not H(0,0) D(5,4) (about 6.4 units).

If, when the dog moves, it would violate the leash distance requirement, it must go the farthest it can in its determined direction that does not violate the distance requirement. For example, if the position is H(0,0) D(3,4) and the dog is randomly decided to move 3 spaces to the right, it will go to D(4,4), since that's the farthest it can go without getting more than 6 units away. (Note that this might result in a movement of 0 spaces, i.e. no movement at all!)

Miscellaneous rules: the human moves first. The human must not exceed the leash length on its move. If it does, it must choose another direction. "Random" means "with an even distribution and with no patterns."

The input will be given in this format (can be STDIN, function parameter, file, etc.):
"<amount of seconds the walk will last> <leash length>"

For example:
300 6 // a 5 minute walk with a 6 yard leash

You must give output in this format (can be STDOUT, function return value, file, etc.):
H(0,0) D(0,0)
H(0,1) D(2,0)
H(1,1) D(2,1)
H(1,0) D(2,-1)
...

(The amount of lines output will be seconds + 1, since the H(0,0) D(0,0) line doesn't count.)
This is code-golf, so the shortest code in bytes will win!

Things you obviously meant, but it's probably good to state them explicitly anyway: 1. Distance means Euclidean distance, 2. The coordinate plane is Cartesian, not polar (or Boeing 777); Things that aren't clear: 3. What does human do if their move would exceed the leash length? 4. On each turn, who moves first, dog or human?

In case the chosen direction does not allow a valid move: Should no move be done or another direction be chosen?

How should input be gotten? STDIN? Is a function parameter fine too?

My dog only barks at me if I'm about to take him for a walk.

@Tim Edited for clarity; thanks.

@TheDoc My dog seems to bark for an endless amount of reasons ;-)

Nice challenge.  Much more demanding than it first appears to be.

GolfScript, 140 characters
~.*:L;)[0.].@{['H('1$','*') D('4$','*')'n]@@{[@~]}+[{)}{(}{\(\}{\)\}]:^%{{~2$~@-.*@@-.*+L>!},}:F~.,{rand}:R~=\[.;{.[~}^4R=+{]}+4R*]F-1=\}*;;

Example run (try online):
> 10 3
H(0,0) D(0,0)
H(0,1) D(0,0)
H(0,0) D(0,2)
H(0,1) D(-1,2)
H(1,1) D(-1,2)
H(1,2) D(-1,4)
H(1,3) D(-1,5)
H(0,3) D(-1,5)
H(-1,3) D(1,5)
H(-1,4) D(1,5)
H(0,4) D(-1,5)

CoffeeScript - 324 + function call
Demo (Using Leash 10):
H(0,0) D(0,0)
H(0,-1) D(0,3)
H(-1,-1) D(0,3)
H(-1,-2) D(-1,3)
H(-1,-3) D(-4,3)
H(-1,-2) D(-4,4)
H(-1,-3) D(-5,4)
H(-1,-2) D(-2,4)
H(-1,-3) D(-2,5)
H(-1,-4) D(-2,5)
H(-1,-3) D(-3,5)
H(0,-3) D(-4,5)
H(-1,-3) D(-4,6)
H(-1,-4) D(-2,6)
H(-2,-4) D(-2,6)
H(-3,-4) D(-5,6)
H(-4,-4) D(-5,6)
H(-4,-3) D(-5,8)
H(-5,-3) D(-2,8)
H(-5,-2) D(-2,8)
H(-5,-3) D(-2,5)

Code:
w=(i)->
    [s,l]=i.split ' ';m=Math;h=[0,0];d=[0,0];r=->(4*m.random())|0
    a=->m.abs(h[0]-d[0])**2+m.abs(h[1]-d[1])**2<=l**2
    b=(x)->if x%2 then 1else-1
    for i in[0..s]
        console.log "H(#{h}) D(#{d})"
        loop
            H=h.slice();x=r();h[(x/2)|0]+=b x;break if a();h=H
        D=r();x=r();(d[(x/2)|0]+=b x;d[(x/2)|0]-=b x if!a())while D-->0

Long Code:
human = [ 0, 0 ]
doge = [ 0, 0 ]
randomDirection = -> [ 'u', 'd', 'l', 'r' ][(4*Math.random())|0]
allowed = -> Math.abs(human[0] - doge[0]) ** 2 + Math.abs(human[1] - doge[1]) ** 2 <= leash**2
leash = 0
walk = (input) ->
    [ seconds, leash ] = input.split ' '
    for i in [0..seconds]
        console.log "H(#{human}) D(#{doge}) #{Math.sqrt Math.abs(human[0] - doge[0]) ** 2 + Math.abs(human[1] - doge[1]) ** 2}"
        valid = no
        loop
            oldHuman = human.slice()
            switch randomDirection()
                when 'u'
                    human[0]--
                when 'd'
                    human[0]++
                when 'l'
                    human[1]--
                when 'r'
                    human[1]++

            if allowed()
                break
            else
                human = oldHuman

        dogeDistance = (Math.random() * 4)|0
        switch randomDirection()
            when 'u'
                while dogeDistance-- > 0
                    doge[0]--
                    doge[0]++ if !allowed()
            when 'd'
                while dogeDistance-- > 0
                    doge[0]++
                    doge[0]-- if !allowed()
            when 'l'
                while dogeDistance-- > 0
                    doge[1]--
                    doge[1]++ if !allowed()
            when 'r'
                while dogeDistance-- > 0
                    doge[1]++
                    doge[1]-- if !allowed()
walk "10 2"

Ruby, 189 177
I can possibly drop this a bit.  I don't love j.
h=d=0;e,l=$*
def j;[1,-1,?i,'-i'].sample.to_c end
0.upto(e.to_i){puts'H(%d,%d) D(%d,%d)'%(h.rect+d.rect)
1 while((g=h+j)-d).abs>l.to_i
h,s=g,j
3.times{d+=s if(d+s-h).abs<=l.to_i}}

Ungolfed:
h=d=0 # use complex numbers since it has distance built in
time,leash=$*

def randomDirection
  [1,-1,'i','-i'].sample.to_c
end

0.upto(time.to_i) { # (1 + time) times
  puts"H(%d,%d) D(%d,%d)"%(h.rect+d.rect) # that's [h.real, h.imag, d.real, d.imag]

  # find a newH that doesn't violate the leash
  newH = h + randomDirection
  while((g-d).abs > leash.to_i)
    newH = h + randomDirection
  end

  h = newH

  newD = randomDirection
  3.times{
    # keep adding newD until you hit the leash
    d += newD if(d + newD - h).abs <= leash.to_i
  }
}

Mathematica 285
Golfed
r=RandomChoice;k=False;
s:=r[{{0,1},{-1,0},{1,0},{0,-1}}]
w:=r[{0,1,2,3,4}]
f[{-1,___}]:="";
f[{n_,l_,{h_,d_}}]:=
(Print["H(",h,")\t","D(",d,")"];
m[i_,u_,v_]:=EuclideanDistance[u+i,v]<l;
z=k;While[z==k,t=s;z=m[t,h,d]];
y=h+t;t=w*s;z=k;While[z==k,t=t-Sign@t;z=m[t,d,y]];
dp=d+t;f[{n-1,l,{y, dp}}])

Example
f[{17,7,{{0,0},{0,0}}}]

H({0,0})   D({0,0})
H({1,0})   D({0,0})
H({2,0})   D({0,2})
H({2,-1})  D({0,-1})
H({1,-1})  D({-3,-1})
H({1,0})   D({-3,1})
H({1,1})   D({0,1})
H({1,2})   D({0,2})
H({1,1})   D({0,2})
H({1,0})   D({-2,2})
H({2,0})   D({1,2})
H({2,-1})  D({-2,2})
H({2,0})   D({-2,3})
H({2,1})   D({-2,0})
H({1,1})   D({-2,3})
H({2,1})   D({-2,6})
H({1,1})   D({-3,6})
H({0,1})   D({-4,6})

UnGolfed
There are some comments in the text below.
I've also included a printout which makes it possible to follow some of the calculations.
step:=RandomChoice[{{0,1},{-1,0},{1,0},{0,-1}}]
dogWander:=RandomChoice[{0,1,2,3,4}]

f[{-1,___}]:="";

f[{n_,l_,{humanPos_,dogPos_}}]:=
Module[{tempStep,moveOK,hp,hp1,dp,p,test},

(* human imagines step, checks with leash, chooses another step if would choke the dog *)
moveOK[intendedStep_,pos1_,pos2_]:=EuclideanDistance[pos1+intendedStep,pos2]<l;
test=False;While[test==False,tempStep=step;test=moveOK[tempStep,humanPos,dogPos]];
hp=humanPos+tempStep;
Print["humanPos before: ", humanPos,"\t","human step: ",tempStep,"\thumanPos after: ",hp,"\tdistance from dog: ",N@EuclideanDistance[hp,dogPos]];

(*move closer to human if needed *)
tempStep=dogWander*step;
test=False;While[test==False,tempStep=tempStep-Sign[tempStep];test=moveOK[tempStep,dogPos,hp]];
dp=dogPos+tempStep;
Print["dog's intended step: ",tempStep,"\tdogPos before: ",dogPos,"\t","dog actual step: ",tempStep, "\t","dogPos after: ",dp,"\tdistance: ",N@EuclideanDistance[hp,dp],"\n"];
f[{n-1,l,{hp, dp}}]]

Example
f[{17,5,{{0,0},{0,0}}}]

[Part of the printout is shown to give a sense of how the code works. ]

source: Stack Exchange

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

sort: votes


text:
Print a specific value in this generated binary matrix
Suppose we define an infinite matrix M, on N^2 -> {0, 1} (where N starts from 1 instead of 0) in this manner:

M(1, 1) = 0.
For every x > 1, M(x, 1) = 1 if x is prime, and 0 otherwise.
For every y > 1, M(1, y) = the yth term in the Thue-Morse sequence.
For every x, y > 1, M(x, y) = M(x, y-1) + M(x-1, y) mod 2.

The top-left 16x16 section of this matrix looks like (with x being rows and y being columns):
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
1 0 1 1 0 0 0 1 0 0 0 1 1 0 1 1
1 1 0 1 1 1 1 0 0 0 0 1 0 0 1 0
0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 1
1 0 1 1 0 0 1 0 1 0 1 1 1 1 0 1
0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1
1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1
0 1 1 1 1 1 0 0 0 0 1 0 0 0 0 1
0 1 0 1 0 1 1 1 1 1 0 0 0 0 0 1
0 1 1 0 0 1 0 1 0 1 1 1 1 1 1 0
1 0 1 1 1 0 0 1 1 0 1 0 1 0 1 1
0 0 1 0 1 1 1 0 1 1 0 0 1 1 0 1
1 1 0 0 1 0 1 1 0 1 1 1 0 1 1 0
0 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1
0 1 0 1 1 1 0 0 0 1 1 0 1 1 0 1
0 1 1 0 1 0 0 0 0 1 0 0 1 0 0 1

Your task is to build a program that will evaluate the value of an arbitrary entry in this matrix as accurately as possible.
Your program will take two integers x and y as input, in any form you choose, and return M(x, y), which will be either 0 or 1.
Your code may be written in any language, but must not exceed 64 kilobytes (65,536 bytes) of source code size or 2 MB (2,097,152 bytes) of total memory usage. Your program must start with empty memory (i.e. it cannot load data from somewhere else) and run independently for each input (that is, it may not store common data for multiple runs). Your program must also be able to evaluate all the entries in the top-left 8192x8192 square in a reasonable amount of time.
The program that evaluates the most entries correctly in the top-left 8192 x 8192 square will be the winner, with shorter code acting as a tie-breaker.

I'm probably going to update the testing case to something slightly more elegant in a moment, so hang on with the testing until I edit the question again.

@mbuettner Yes, it does.

I fail to see how we need a new tag for "accuracy." This is just a [code-challenge]. Please run new challenge genre ideas through meta first (there's one thing we learned from [code-trolling]).

^ Noted. I'll remove that tag.

You posted a comment on a now deleted answer saying "You need to create a function that computes the value of that matrix with two coordinates without computing the entire matrix." I can't find in your question the "without computing the entire matrix" part. Perhaps you think that the memory constraints enforce that, but perhaps it isn't so.

Since any valid answer will be "accurate" (or it's buggy), isn't this just code golf?

@intx13: The point is that an answer may produce incorrect results but still be considered valid. An answer that simply says print 1 would still be right about 50% of the time, but would be beaten by an answer that gave the correct answer 90% of the time.

@belisarius It would also be prohibitively expensive time-wise to actually test it if you computed the entire matrix at once. The point I was trying to make was that Kaya had created a literal matrix, and not a function that evaluates values in that matrix.

@JoeZ I guess. But since I have a solution that is 100% accurate and the challenge goes first by who is most accurate, it's now code golf.

That being said, if you can find a way to encode the entire matrix in just 2 MB of memory, go right ahead. That would count as a 100% accurate answer.

I presume that you're of the school of thought that N doesn't include 0, but since there are two schools of thought it's worth making that clear. It's also worth making it clear when you first mention them rather than three lines later that for some reason you've chosen to use x for the row and y for the column, confusing anyone who's used to Cartesian coordinates.

Actually, usually to me N does include 0, but for the purposes of this question it didn't work out. And I already put in the latter clarifier about x and y. Perhaps it would be better to use a and b so they're not confused with Cartesian coordinates?

@TheDoctor It's not too uncommon. The accepted answer changes over time.

@JoeZ. - I usually wait till the interest on the question has declined

I believe the memory restriction unnecessarily complicates this. It's also hard to ensure accuracy.

@qwr to be honest, I think the memory restriction is the most interesting thing about this problem. just computing the entire table in rows or columns seems quite trivial.

r and c for row and column? I edited my comment when I saw that you had put in a clarification, but I didn't see it immediately because I read the bullet points and then went straight to the table.

J - 42 38 char
Pretty fast, 100% accurate, and well within the memory constraints.
([{+2&(~:/@#:@#@],~:/\,(p:>:)&#)0:)&<:

The strategy is as follows: we will calculate successive antidiagonals of this matrix, performing a pairwise XOR to move along and adding the current Thue-Morse and prime bits to the ends. We then pull the required digit out of the antidiagonal when we get there.
Explanation by explosion:
(                                 )&<:  NB. decrement each of x and y
     &(                        )        NB. apply the following function...
   +                                    NB. ... (x-1)+(y-1) times...
                                0:      NB. ... starting with a zero:
    2             ~:/\                  NB.   pairwise XOR on the argument
                      ,(p:>:)&#         NB.   append prime bit (is 1+length prime?)
       ~:/@#:@#@],                      NB.   prepend TM bit (XOR of binary)
 [{                                     NB. take the x-th bit (at index x-1)

Usage of this verb is x m y for M(x, y) as specified in the question, where m is the verb.
   5 ([{+2&(~:/@#:@#@],~:/\,(p:>:)&#)0:)&<: 8
0
   m =: ([{+2&(~:/@#:@#@],~:/\,(p:>:)&#)0:)&<:
   1+i.16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
   m/~ 1+i.16
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
1 0 1 1 0 0 0 1 0 0 0 1 1 0 1 1
1 1 0 1 1 1 1 0 0 0 0 1 0 0 1 0
0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 1
1 0 1 1 0 0 1 0 1 0 1 1 1 1 0 1
0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1
1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1
0 1 1 1 1 1 0 0 0 0 1 0 0 0 0 1
0 1 0 1 0 1 1 1 1 1 0 0 0 0 0 1
0 1 1 0 0 1 0 1 0 1 1 1 1 1 1 0
1 0 1 1 1 0 0 1 1 0 1 0 1 0 1 1
0 0 1 0 1 1 1 0 1 1 0 0 1 1 0 1
1 1 0 0 1 0 1 1 0 1 1 1 0 1 1 0
0 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1
0 1 0 1 1 1 0 0 0 1 1 0 1 1 0 1
0 1 1 0 1 0 0 0 0 1 0 0 1 0 0 1

To save keystrokes we don't try to tell if we still need more prime or Thue-Morse bits, so we compute the entire antidiagonal to get the bit we want. However, 8192 m 8192 still runs in less than 0.07 s and about 100 KiB on my modest laptop.

Mathematica – 100% accuracy,  223 193 189 bytes
f=(r=Array[0&,Max@##];For[s=2,s<=#+#2,++s,For[i=Max[1,s-#2],i<=Min[s-1,#],++i,j=s-i;r[[j]]=Which[i==1,PrimeQ@j,j==1,OddQ@Total@IntegerDigits[i-1,2],0<1,Xor@@r[[j-1;;j]]]]];If[r[[#2]],1,0])&

Here is a legible version:
f[x_,y_] := (
   r = Array[0 &, Max[x,y]];
   For[s = 2, s <= x + y, ++s,
    For[
     i = Max[1, s - y],
     i <= Min[s - 1, x],
     ++i,

     j = s - i;
     r[[j]] = Which[
       i == 1,
       PrimeQ@j,
       j == 1,
       OddQ@Total@IntegerDigits[i - 1, 2],
       0 < 1,
       r[[j - 1]]~Xor~r[[j]]
       ]
     ]
    ];
   If[r[[y]], 1, 0]
   );

I basically precompute along diagonals of constant x+y.
Features:

It's accurate.
It runs in O(x*y).
f[8192,8192] takes about 400 seconds. I suppose there is room for improvement (maybe RotateLeft could replace the inner loop).
It only uses one array of up to max(x,y) intermediate results in memory. So there is no necessity to use more than about 32k (assuming 32-bit integers) for the algorithm itself (plus, whatever Mathematica uses). In fact, Mathematica uses 31M by itself on my system, but this works without an issue:
MemoryConstrained[f[8192, 8192], 2^21]

Well, looks like you got it. I'll be making harder ones in the future, though :P

Hm, in one of the changes I must have screwed up the runtime performance. The inner loop is still called O(x*y) times, but the total execution time increases faster than that. I'm not quite sure what's happening. If some Mathematica Guru could enlighten me, which operation in the loop is not O(1) that would be very helpful! :) (well, PrimeQ and Total@IntegerDigits aren't, but I've had them in there from the beginning, and they only called O(y) and O(x) times respectively)

Python, 192 characters
100% accuracy, calculates M(8192,8192) in ~10 seconds on my machine.
R=range
def M(X,Y):
 X+=1;c=[1]*X;r=[0]
 while len(r)<Y:r+=[i^1 for i in r]
 for i in R(2,X):
  if c[i]:
   for j in R(i+i,X,i):c[j]=0
  r[0]=c[i]
  for i in R(1,Y):r[i]^=r[i-1]
 return r[Y-1]

Perl, 137
Not to 'win' :-), but since there's no Perl here yet and code was written anyway, here it is.
sub f{($n,$m)=@_;@a=0;@a=(@a,map{0+!$_}@a)while@a<$n;for$k(2..$m){$p=0;O:{$k%$_?1:last O for 2..sqrt$k;$p=1}$p=$a[$_]^=$p for 1..$n-1}$p}

Takes several seconds if called print f(8192,8192), stores single line of matrix in memory (array of 8192 integers (scalars)), about 3.5 Mb whole Perl process. I tried to do it with string instead of array (either with regexps or accessing with substr), takes less memory and can be golfed further, but runs much slower.
Indented:
sub f{
    ($n,$m)=@_;
    @a=0;                                  # @a will be current line.
    @a=(@a,map{0+!$_}@a)while@a<$n;        # Fill it with Thue-Morse sequence.
    for$k(2..$m){                          # Repeat until required line number.
        $p=0;                              # Find out if current line number
        O:{                                # is a prime.
            $k%$_?1:last O for 2..sqrt$k;
            $p=1                           # Store result (0 or 1) in $p.
        }
        $p=$a[$_]^=$p for 1..$n-1          # XOR previous value in current position
    }                                      # with $p and store in $p.
    $p                                     # Return $p.
}

Haskell, 223
g n=div(filter(>=n)(iterate(*2)1)!!0)2
1%1=0>1
1%n=not$1%(n-g n)
n%1=and[rem n x>0|x<-[2..n-1]]
a%b=g[0<1]where g s|foldr seq(0>1)s=0<1|n==a+b=s!!(b-1)|0<1=g$n%1:zipWith x s(tail s)++[1%n]where n=length s+1
x p|p=not|0<1=id

this has fast runtime (5.7 seconds with -O3). memory wasn't checked yet, though it should be linear.
this uses the diagonal algorithm seen here before.
as far as speed is concerned, the only things that matter are the diagonal algorithm, -O3 , and the |foldr seq(0>1)s=0<1 guard, which makes the list strict. everything else is implemented rather inefficiently - prime checking is done by checking all the lesser numbers for division, the Morse sequence's elements are recomputed constantly. but it is still fast enough :-).

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


text:
Would this number make a good 2048 combo?
Inspired by xkcd.
Your challenge is to determine whether a number would make a good combination in the game 2048. Your input will be a number, such as:
8224

And the output will be whether that number would make a good 2048 combo, which for this input would be true or yes or 1 or any other way of indicating a positive result.
For those not familiar with the game, here's a simple explanation: powers of two are arranged on a grid, like this: [2] [2]. Tiles can be moved in any direction, and if two identical tiles meet, they become the next power of two (so [2] [2] when moved left or right becomes [4]). Or, you could just try the game here.
What does "a good 2048 combination" mean? It means any number that, if it was in the game "2048", it could be combined into one single number. (A zero means an empty space, and can be ignored if needed.) Note that numbers could possibly be multiple digits! However, the numbers must not change between moves. Here are some examples/test cases (with "Good" indicating a good combination, and "Bad" meaning not good):

Good: 8224 (8224 -> 844 -> 88 -> 16)
Good: 2222 (2222 -> 44 -> 8)
Good: 22048 (22048 -> 448 -> 88 -> 16)
Bad: 20482 (cannot combine the outer 2's, nor can you combine a 2048 and a 2)
Good: 20482048 (20482048 -> 4096)
Bad: 210241024 (210241024 -> 22048, but this is now [2] [2048] and cannot be combined since numbers cannot change between moves)
Good: 2048 (it's already one number)
Bad: 2047 (it's not a power of 2)
Bad: 11 (there are no 1's in the game)
Good: 000040000000 (zeroes are empty spaces)

Miscellaneous rules:

Input can be from anywhere reasonable, i.e. STDIN, function argument, file, etc.
Output can also be anywhere reasonable, i.e. STDOUT, function return value, file, etc.
Ignore the grid size - 22222222 should still output true.
The is no maximum to what s number could be, as long as it's a power of two. Therefore the possible numbers are any power of two greater than 0.
For those worried about zeroes causing ambiguity, that is not the case. For example, 22048 can be parsed as either [2] [2048] or [2] [2] [0] [4] [8]. The first one doesn't work, but the second one does, so it should output true.
This is code-golf, so the shortest code in bytes will win!

can I have a server supplying answer and just upload input download answer from it? total downloaded bytes will be 1

"Bad: 11 (there are no 1's in the game)" There's no 4096 in the game, either. If it was me, I'd allow 1 in the input as 2^0. Not that it's a massive deal, but you know.

@undergroundmonorail If 1 was legal you could parse 164 as 16 4 or 1 64.

@Geobits Hm, I misread the input specs. You're correct, I wasn't accounting for multiple digit blocks.

@Geobits 2048 is already ambiguous as either one number or four.

But yeah... the network rule is wrong.

A zero should not mean an empty space; is 1024 a legal number or not? Empty spaces should be unambiguous... and therefore having them at all does not contribute to the question, in my opinion.

Your third example shows 22048 should output good but thats not true. You cant combine 2 with 2048 and the grid is 4x4 if all numbers should be seperate you'll get 5 cells. so maybe you should remove the 0? Also your 5th example seems to be invalid since the game stops at 2048 :)

Surely we can come up with new puzzles without constantly basing them on xkcd jokes? :)

@TimSeguine probably, but why would we? :P

@TeunPronk touche

@m.b How? Does the game not end at 2048, as the name suggests? (As you can probably guess, I've never beaten it.)

@undergroundmonorail I can confirm there is a 4096 tile in the game.

@undergroundmonorail, there is a "keep going"button when you reach 2048.

@m.buettner Edited for clarity.

@Teun /cc ^. I never mentioned any restriction on grid size; apparently that was ambiguous, so I'll just state it explicitly.

@Doorknob ok but what is the max value we should work with? is it 4096 or higher?

@Teun z There is no maximum. I'll edit that in as well.

@hosch 20482048 could also be 8 tiles, but it wouldn't work that way, so it's assumed to be 2.

Is "88222288888" valid. I ask because if you collapse to the left (like the game), this becomes 16,4,4,16,16,8->16,8,16,16,8 - which doesn't collapse further. But if you collapse lowest pairs first instead, this will collapse completely. (I think my solution probably has bugs to do with incomplete collapses, and collapsing to the right)

I think there's a bit of a problem in that every answer on this question seems to do something different :P

@Tal Well, yours violates the rules, so I'm not surprised that it's different from the others...

@bazzargh in your case, you could collapse to the right: 8 8 2 2 2 2 8 8 8 8 8 -> 16 4 4 8 16 16 -> 16 8 8 32 -> 16 16 32 -> 32 32 -> 64. But I don't doubt that it would be possible to come up with a case that would no longer work on the board but only by collapsing some inner pair first.

@m.buettner fair point. I've fixed mine up to collapse simultaneously in pairs to left or right, exactly like the game. Turned out to need less code!

@m.buettner found a nice test case which can't be collapsed without cheating, by reflecting the previous example: "88888222288646488222288888". If you slide left, you get 8 32 8 16 128 64; or the reverse if you slide right; so it's not game-legal. But if you pick pairs to collapse, you can get 256.

...and a much simpler one: "222244442222"

I'm not going to code, I'm going to keep playing this game! :D

GolfScript, 137 characters
[0`]1$,4*,{2\)?`}%+:W;[]\]][]\{{:A;W{A 1=\?!},{[.A~@,>\@~+\].~!{0-.,/@+\0}*;}%~}%.}do+.{~}%,{{.-1%}%.&{[{.2$={+)}*}*]{1|(}%}%}*{,1=},!!

Input must be given on STDIN. The output is 0/1 for bad/good numbers. Most of the code is necessary for parsing the possible inputs.
This shorter version (113 characters) performs a simple shift test which would not work correctly for input like 224422.
[0`]1$,4*,{2\)?`}%+:W;[]\]][]\{{:A;W{A 1=\?!},{[.A~@,>\@~+\].~!{0-.,/@+\0}*;}%~}%.}do+{W{~[.:S]/[S.+]*}/,1=},!!

All test cases can be checked online.

Python: 457 422 characters
z=range
def c(n):
 for x in z(1,12):
  if int(n)==2**x:return 1
 return 0
def p(s):
 if s=='':return[]
 for i in z(len(s),0,-1):
  if c(s[:i])>0and p(s[i:])!=1:return [int(s[:i])]+p(s[i:])
 return 1
def r(a):
 if len(a)==1:return 1
 i,t=1,a[:1]
 while i<len(a):
  if a[i]==t[-1]:t[-1]*=2
  else:t+=[a[i]]
  i+=1
 if len(t)==len(a):return 0
 return r(t)
def f(s):
 if p(s)==1or r(p(s))==0:print('bad')
 else:print('good')

The function f(s) gets a string of digits and outputs 'good' or 'bad' accordingly.
I chose not to use 0 as spaces because spaces are meaningless in the game and they create ambiguity when parsing strings (is 22048 good or bad?). This only uses numbers up to 2048, but that can be changed without adding characters.
At the cost of 10 characters or so I can also print all the steps of combining the numbers.
And I realize that this code isn't golfed enough yet; don't worry, edits are coming.

You can use the space and tab trick to save some characters on the indentation. SO markdown will break it though.

I think it doesn't work on Python 3.x. There's quite a lot I can do, but not sure I could compete with that Haskell answer :)

Yep, i forgot about that.

Haskell: 285 254 253 237 230 227
usage - just load it into ghci, and pass the string to h.
*Main> h "210241024"
False
*Main> h (replicate 1024 '2') -- very long string
True
*Main> h (replicate 1023 '2') -- odd one out
False

Code:
t=i 0
i n=mod n 2<1&&(n<3||i(div n 2))
a%[]|i a=[[a]]|t=[];a%(b:c)=[a:d|d<-b%c,i a]++(a*10+b)%c
c(0:a)=c a;c(a:b:d)|a==b=(a+a):c d|t=a:c(b:d);c a=a
l a=c a/=a&&(g.c)a
g[a]=t;g a=l a||(l.reverse)a
h b=any g$0%(map(read.(:[]))b)

Commentary: i is the check if a number is a power of 2, this will be outplayed by languages with bit twiddling. % recursively generates all parses that are lists of powers of 2 or 0. c collapses tiles. l recursively tests if tiles are collapsible left or good. g tests if tiles are collapsible left or right. There is no limit to the numbers on the tiles - eg h ((show (2^200))++(show (2^200))) returns true for 2 tiles marked "1606938044258990275541962092341162602522202993782792835301376".
Edited to fix a bug that it didn't correctly collapse "88222288888" to the right, but also found more golfing opportunities.

Perl, 175-336 bytes
while(<>){chomp;$n="nothing";$\=("."x(1+/^[2048]+$/+/^((\d+)0*\2)+$/+((sprintf"%b",
$_)!~/1.*1/)))."\n";($o=$\)=~y/.\n/oh/;print$o;$m=length;for$i(1..$m){$a=$_;$r=
qr((\d*[2468])0*\2)0*/;($b=substr$a,0,$i,"")=~s/$r/$2+$2/ge;@n=$"="$b$a";push@n,$"while$"
=~s/$r/$2+$2/ge;($"%2&&next)||($">>=1)while$">1;$n="nice";(print)for@n;last}print$n}

Keeping just the essentials intact:
$_=shift;$m=length;for$i(1..$m){$a=$_;$r=qr/((\d*[2468])0*\2)0*/;($b=substr$a,0,$i,"")=~
s/$r/$2*2/ge;$"="$b$a";1while$"=~s/$r/$2*2/ge;($"%2&&next)||($">>=1)while$">1;exit}die;

1

ooh..
    1..
    nice..

2

oooh...
    2...
    nice...

22

oooh...
    22...
    4...
    nice...

42

ooh..
    nothing..

422

ooh..
    422..
    44..
    8..
    nice..

322

oh.
    nothing.

336

oh.
    nothing.

4224

ooh..
    nothing..

4228

ooh..
    4228..
    448..
    88..
    16..
    nice..

16022481602248

ooh..
    1604481602248..
    16088160448..
    1601616088..
    3216016..
    3232..
    64..
    nice..

[64 and 256 lead to some poorly resolvable ambiguities that greedy matching can't cope with... but these are nice byte counts.]

2048

oooh...
    2048...
    nice...

Delphi 572582 characters
Edited code, limit is set to 2^30 so it wont exceed the MaxInt value in Delphi.
Golfed
uses SysUtils,Classes;var t,j,c:integer;s,n:string;L:TStringList;function p(x:string):boolean;var r,i:int64;begin if x='0'then exit(1>0);i:=2;r:=StrToInt(x);while i<r do i:=i*2;p:=i=r;end;begin read(s);t:=0;L:=TStringList.Create;j:=1;while j<=Length(s)do begin for c:=9downto 1do begin n:=copy(s,j,c);if p(n)then break;end;if n>'0'then L.Add(n);j:=j+Length(n);end;for j:=0to L.Count-1do t:=t+StrToInt(L[j]);j:=0;repeat if j=L.Count-1then break;if L[j]=L[j+1]then begin L[j]:=IntToStr(StrToInt(L[j])*2);L.Delete(j+1);j:=0;end else inc(j);until L.Count=1;write(strtoint(L[0])=t);end.

Ungolfed
uses
  SysUtils,
  Classes;

var
  t,j,c:integer;
  s,n:string;
  L:TStringList;
  function p(x:string):boolean;
  var
    r,i:int64;
  begin
    if x='0'then exit(1>0);
    i:=2;r:=StrToInt(x);
    while i<r do
      i:=i*2;
    p:=i=r;
  end;
begin
    read(s);
    t:=0;L:=TStringList.Create;
    j:=1;
    while j<=Length(s)do
    begin
      for c:=9downto 1do
      begin
        n:=copy(s,j,c);
        if p(n)then break;
      end;
      if n>'0'then L.Add(n);
      j:=j+Length(n);
    end;
    for j:=0to L.Count-1do
      t:=t+StrToInt(L[j]);
    j:=0;
    repeat
      if j=L.Count-1then break;
      if L[j]=L[j+1]then
      begin
        L[j]:=IntToStr(StrToInt(L[j])*2);
        L.Delete(j+1);j:=0
      end
      else
        inc(j);
    until L.Count=1;
    write(strtoint(L[0])=t);
end.

EDIT
So I got curious and wondered how many of these combinations would fit the puzzle and ran a test one it.
For others that are also curious, make a test too ;)
But ok here are the results:
20736 combinations were tested and 1166 were great combinations
I must say combinations with 3 or more zeroes were skipped (makes sense right?)
Combinations are almost unique, meaning the combinations 2248,8224,8422 and 4228 were all counted as a great combination.

Mathematica - 218 bytes
f=MemberQ[DeleteCases[Map[FromDigits,l~Internal`PartitionRagged~#&/@Join@@Permutations/@IntegerPartitions@Length[l=IntegerDigits@#],{2}],{___,x_,___}/;!IntegerQ[2~Log~x]||x<2]//.{a___,x_,x_,b___}:>{a,2x,b},{_Integer}]&

Ungolfed version:
f[n_] := MemberQ[
  DeleteCases[
      Map[
        FromDigits,
        Internal`PartitionRagged[l, #] & /@
          Join @@ Permutations /@ IntegerPartitions[Length[l = IntegerDigits[n]]],
        {2}
      ],
      {___, x_, ___} /; x < 2 || ! IntegerQ[2~Log~x]
    ]
  ] //. {a___, x_, x_, b___} :> {a, 2 x, b},
  {_Integer}
]

The Internal\PartitionRagged` magic is taken from this question.
This solution handles arbitrary grid sizes and arbitrarily large numbers.
Here is a 195 byte version that works like the actual game with up to 4 tiles only (so f[22222222] is False):
f=MemberQ[(d=DeleteCases)[d[ReplaceList[IntegerDigits@#,{a__,b___,c___,d___}:>FromDigits/@{{a},{b},{c},{d}}],0,2],{___,x_,___}/;!IntegerQ[2~Log~x]||x<2]//.{a___,x_,x_,b___}:>{a,2x,b},{_Integer}]&

where I've replaced
Map[
  FromDigits,
  Internal`PartitionRagged[l, #] & /@
    Apply[
      Join,
      Permutations /@ IntegerPartitions[Length[l = IntegerDigits@#]]
    ],
  {2}
]

with
ReplaceList[
  IntegerDigits[n],
  {a__, b___, c___, d___} :> FromDigits /@ {{a}, {b}, {c}, {d}}
]

Just wondering if this has the same bug my code did - the DeleteCases looks like it removes leftmost pairs, so f[88222288888] would fail?

@bazzargh no, the DeleteCases just remove zeros and numbers that aren't power of two. The actual collapsing of pairs is done by the rule //. {a___, x_, x_, b___} :> {a, 2 x, b}, which works for that number and the reverse of it. I'm actually not entirely sure about the order Mathematica applies those replacements in, but it works.

Haskell - 260 263
import Data.Bits
p[x]=[[[x]]]
p(x:s)=do r@(h:t)<-p s;[[x]:r,(x:h):t]
q=filter(and.map(\n->(n::Integer)/=1&&n.&.(-n)==n)).map(filter(/=0)).map(map read).p
c(x:y:s)
 |x==y=2*x:c s
 |True=x:(c$y:s)
c x=x
r[x]=True
r l=c l/=l&&(r(c l)||r(c$reverse l))
f=or.map r.q

f is the function. Examples:
> f"22228"
True
> f"20482044"
False

A little explanation:
p returns all ways to split a list.
q filters those that consist of only powers of 2 (excluding 1 but including 0).
c tries to collapse a string.
r iterates right and left collapsion until there's only 1 element left, or the string is incollapsable.

Nice. There's a bug in c though, try "222244442222" - it returns true, but that's not collapsable in the game. Needs to recurse with (2*x):c s.

@bazzargh fixed

authors: Игорь Барабашкин


text:
The poet's quine
Write a quine with 1 or more rhyme scheme from http://en.wikipedia.org/wiki/Rhyme_scheme when read. The following characters are spoken aloud:

any alphanumeric words or characters not in a comment;
comparison and arithmetic characters (+ plus; - minus; * times, / divided by, | or, || or, & and, && and, ! not, = equals, == equals, === equals).

The following is not accounted for (is not spoken aloud):

any characters which signify the beginning or end of string literals ("');
any characters which signify the beginning or end of logical blocks ((){}[]);
any characters which signify the delineation of a variable, function or line of code (.,;).
any characters in comments;

The "spoken aloud" rules always apply. the "not spoken aloud" rules apply to all languages, except Brainfuck, K, J, APL, Befunge and Sclipting. In the case of APL, Brainfuck, Befunge, K and J, any character not mentioned in "spoken aloud rules" are subject to the "choose consistently" rule outlined above. Sclipting characters are pronounced like they would be if they were that Chinese character, with free choice of which pronounciation you use.
Any characters which are not explicitly allowed or denied pronounciation are free to be pronounced or kept silent. However, a specific character is either always pronounced or always kept silent. You may not pronounce # as hashtag in one line and keep # silent in the next.
Words may be pronounced in any dialect or language, but it needs to be consistent within the same stanza (no having the first word be pronounced in a Scottish way and the second in a Welsh way).
Contest type is popularity contest. The deadline is April 23rd in honor of one of the most well known bards, William Shakespeare, who was born and allegedly died on that day. Winner is he who gets the most votes.
Edit: because I don't think there will be any more submissions, I've decided to end the contest early. I'll mark the winner momentarily.

+1, well formulated. I like how you called out Sclipting as a special case.

Batch AABBA (Limerick)
This is my best try, but I have never been any good at poems.
Code:
@Echo off || cd \.
If "this"=="a largeish" pot
Type %0 || chef
Color 7f
Goto :eof || shallot

In english:

Echo off else CD slash dot
If this equals a largeish pot
Type zero else chef
Color seven f
Go to EOF else shallot

Fortran 95 (McCarron Couplet)

McCarron Couplet: "AABBABCCDDCDEEFFEF" a contemporary take on a
classic rhyming pattern, introduced by the academic James McCarron.

My code (which should be saved as all.f95 in order for it to work):
character (LEN=100) :: &
bend; logical :: wondered
inquire(file="superstar &
&car",exist=wondered,number=i_r)

open(unit=100, &
file="superstar car")
if (.NOT.(.NOT.(wondered))) then
i_sum = 1; read(100,*) n

i_sum = n + i_sum
rewind(100); else; i_sum = 1
endif; write(100,*) i_sum, 10
codingThis = fun

write(bend,"(I5)") n; call &
SYSTEM ("copy all.f95 all"//&
TRIM(TRIM(ADJUSTL(bend)))//&

".f95"); open(access="append", &
unit=10,file="waterfall")
write(10,*) "foo bar"; end

It will copy itself to numbered files, starting with all0.f95, then all1.f95, all2.f95, and so on...
It reads:
character len equals hundred
bend logical wondered
inquire file superstar
car exist wondered, number equals IR

open unit equals hundred
file equals superstar car
if not not wondered then
I sum equals one, read hundred N

I sum equals N plus I sum
rewind hundred else I sum equals one
endif write hundred I sum ten
conding this equals fun

write bend I five N call
system copy all F point ninety five all
trim trim adjust L bend

point ninety five access append
open unit ten file waterfall
write ten foo bar end


text:
Make a word cloud from a text
The code should take text from standard input:
The definition of insanity is quoting the same phrase again and again and not expect despair.

The output should be a PNG file containing the word cloud corresponding to that text:

The above word cloud was created using a specialized online application and it filtered the word The and other common words (of, is, and, not, and the). Since this is code golf, the common words will not be filtered and I leave secondary aesthetics of the word cloud to the choice of each coder. Unlike the image exampled here, no words should be excluded, common or otherwise. The definition of a word is defined below.
In this case a word is anything alpha-numeric; numbers are not acting as separators. So, for example, 0xAF qualifies as a word. Separators will be anything that is not alpha-numeric, including .(dot) and -(hyphen). Thus i.e. or pick-me-up would result in 2 or 3 words, respectively. Should be case sensitive - This and this would be two different words,  ' would also be separator so wouldn and t will be 2 different words from wouldn't.
The tags should appear clustered but not overlapping and the font size should be directly proportional to the number of occurrences of that word in the text. The word should appear only once. Specific font color is not required in this case. Semantic association is not a requirement.
Hint - This other code golf could help:
Count the words in a text and display them

Please explain what you consider a word cloud. Also I don't understand your output definitions. Can you please clarify what you mean by output should be printed with new line after each character?

@Howard sorry the paragraph you mentioned was wrong I edited the question to exclude that and add more specification in order to make the requirements clear, thanks for bringing that up

The sample image doesn't seem to match the requirements. It also creates a question about how many times each word should appear in the cloud, which you don't answer anywhere.

@PeterTaylor You are right, I edited the question

This seems kinda "I need code for this, but it is off topic at SO, so I will make it a code golf instead."

@TimSeguine I don't think code-golf submissions have any kind of reusability...

@WanderNauta I think that depends on your definition of usable. Desperate times call for desperate measures. Anyway, I only meant it half serious. :)

@TimSeguine Legitimate concern, but why would I need it when there are scores of free apps to do that.

Personally I can't image any valid use of such PNG. Usually word clouds need to be interactive.

Your word cloud creator also seems to have filtered of, is, and, not, and the.

Read from stdin? Expot a PNG? How am I supposed to do this in Emacs?? :)

I think getting rid of the common words would make an excellent bonus, personally.

Python 3, 363 308 293 274 characters
import os,sys,re,collections as C
c=C.Counter()
n=sys.argv[1]
o="graph d{"
for w in re.findall("\w*",open(n).read()):c[w]+=1
for w,x in c.most_common(75)[1:]:o+="%s[fontsize=%s,shape=none];"%(w,x/5)
open(n+'.dot','w').write(o+"}")
os.system("fdp -Tpng %s.dot>%s.png"%(n,n))

Call it like this: python cloud.py file.txt. The script uses Graphviz's fdp force-directed graph generator to generate the image (it will spit out a GraphViz file to file.txt.dot and a PNG image file to file.txt.png). This means you'll need to have Graphviz installed.
The image above is the cloud it makes of Shakespeare's Hamlet - you can tell, since it contains "To be or not to be". There's also some delightful nonsense to be found:

It is, to You and I, the Ham of Not thatO lord have us, what now...

You may need to tweak the constant /5 in the second-to-last line depending on how large your text is. 5 works well for Hamlet-sized texts, 500 for Bible-length input and so on.

JAVASCRIPT 473
var wordCloud=function(e){var t=e.split(/[\s-.,;]+/);var n={},r;for(r in t){var i=t[r];n[i]=n[i]+1||1}var s=document;var o=s.createElement("canvas");o.width=600;o.height=400;o.style.display="none";s.body.appendChild(o);var u=o.getContext("2d");var a=0,f=50;for(var i in n){u.font=n[i]*50+"px monospace";u.fillText(i,a,f+n[i]*5);a+=i.length*n[i]*50;if(a>o.width*.6){a=0;f+=n[i]*5+100}}var l=o.toDataURL("image/png");var c=s.createElement("img");c.src=l;s.body.appendChild(c)}

Ungolfed demo
wordCloud("string;abc,test-omg shouldn't test omg lalala. s2 s2 s2")

Are you sure this produces a PNG file?

Now it does !!!

Cool. (As possible, please update the live demo too.)

already did! thx @manawork

Regarding the golfing, this shortened version seems to do it in 360 characters: http://pastebin.com/C4dpYLP8

...296 characters: http://pastebin.com/5BUPavYH

just realized there's no need to append/hide the canvas

I'm also going to golf this even more into 405 bytes. Try it here!