text:
Advanced Calculator
You must write a program that evaluates a string that would be entered into an advanced calculator.
The program must accept input using stdin and output the correct answer.  For languages that do no have functions to accept stdin, you may assume the functions readLine and print to handle these tasks.
Requirements:

Does not use any kind of "eval" functions
Can handle floating point and negative numbers
Supports at least the +, -, *, /, and ^ operators
Supports brackets and parenthesis for overriding the normal order
Can handle input containing one or more spaces between the operators and numbers
Evaluates the input using the standard order of operations

Test Cases
Input
10 - 3 + 2

Output
9

Input
8 + 6 / 3 - 7 + -5 / 2.5

Output
1

Input
4 + [ ( -3 + 5 ) * 3.5 ] ^ 2 - 12

Output
41

Is it ok if the outputted numbers have a trailing .0 at the end if they're integers? Also: how accurate does the calculator have to be (regarding floating point precision and such)?

The output can have a trailing .0 on the end.  I'm not too sure about the precision, but more is better.

The Stack Overflow version was Mathematical expression evaluator (full PEMDAS). Though many of the answer to that one are counting lines (?!?). Still there are several compact answers in c.

Bonus for PN/RPN calculators?

C++, 640 583
string k="[]()+-*/^";stack<double> m;stack<char> n;
#define C(o,x,y) ('^'==o?x<y:x<=y)
#define Q(a) double a=m.top();m.pop();
#define R(o) {Q(b)Q(a)m.push(o=='+'?a+b:o=='-'?a-b:o=='*'?a*b:o=='/'?a/b:o=='^'?pow(a,b):0);n.pop();}
while(!cin.eof()){string s;getline(cin,s,' ');if(s.empty())continue;if('\n'==*--s.end())s.erase(--s.end());(s.size()==1&&s.npos!=k.find(s[0]))?({char c=s[0]=='['?'(':s[0]==']'?')':s[0];while(!n.empty()&&'('!= c&&C(c,k.find(c),k.find(n.top())))R(n.top());')'==c?n.pop():n.push(c);}):m.push(strtod(s.c_str(),0));}while(!n.empty())R(n.top());cout<<m.top()<<endl;

Indented
string k="[]()+-*/^";
stack<double> m;
stack<char> n;
#define C(o,x,y) ('^'==o?x<y:x<=y)
#define Q(a) double a=m.top();m.pop();
#define R(o) {Q(b)Q(a)m.push(o=='+'?a+b:o=='-'?a-b:o=='*'?a*b:o=='/'?a/b:o=='^'?pow(a,b):0);n.pop();}
while(!cin.eof())
{
    string s;
    getline(cin,s,' ');
    if(s.empty())continue;
    if('\n'==*--s.end())s.erase(--s.end());
    (s.size()==1&&s.npos!=k.find(s[0]))?({
        char c=s[0]=='['?'(':s[0]==']'?')':s[0];
        while(!n.empty()&&'('!= c&&C(c,k.find(c),k.find(n.top())))
            R(n.top());
        ')'==c?n.pop():n.push(c);
    }):m.push(strtod(s.c_str(),0));
}
while(!n.empty())
    R(n.top());
cout<<m.top()<<endl;

My first code golf, so looking forward to comments & criticism!

Handles the right-associativity of the exponentiation operator, which J B's Perl solution doesn't seem to.

Neither the problem statement nor the linked wikipedia page mention exponentiation has to be right-associative.  Furthermore, the wikipedia page explicitely says both ways are found on commercial calculators.

+1 nicely golfed, but... just dropping includes, using namespace std and a main function isn't really ok, is it?

PHP - 394 354 312 characters
<?=e(!$s=preg_split('#\s+#',`cat`,-1,1),$s);function e($P,&$s){$S='array_shift';if(($a=$S($s))=='('|$a=='['){$a=e(0,$s);$S($s);}while($s&&($p=strpos(' +-*/^',$o=$s[0]))&&$p>=$P){$b=e($p+($S($s)!='^'),$s);if($o=='+')$a+=$b;if($o=='-')$a-=$b;if($o=='*')$a*=$b;if($o=='/')$a/=$b;if($o=='^')$a=pow($a,$b);}return$a;}

Indented:
<?
preg_match_all('#\d+(\.\d+)?|\S#',`cat`,$m);
$s=$m[0];
function e($P) {
        global $s;
        if (strpos(" ([",$s[0])){
                array_shift($s);
                $a=e(0);
                array_shift($s);
        } else {
                $a=array_shift($s);
                if ($a=='-')$a.=array_shift($s);
        }
        while ($s && ($p=strpos(' +-*/^',$o=$s[0])) && $p >= $P) {
                array_shift($s);
                $b = e($p+($o!='^'));
                switch($o){
                case'+':$a+=$b;break;
                case'-':$a-=$b;break;
                case'*':$a*=$b;break;
                case'/':$a/=$b;break;
                case'^':$a=pow($a,$b);
                }
        }
        return $a;
}
echo e(0);

Postscript, 446
This uses the shunting yard algorithm.
[/*[/p
2/e{mul}>>/d[/p
2/e{div}>>/+[/p
1/e{add}>>/-[/p
1/e{sub}>>/o[/p
9/e{}>>/c[/p
-1/e{}>>/^[/p
3/e{exp}>>/p
0>>begin/s(%stdin)(r)file 999 string readline pop def
0 1 s length 1 sub{s exch[0 1 255{}for]dup[(\(o)([o)(\)c)(]c)(/d)]{{}forall
put dup}forall
pop
3 copy pop
get
get
put}for{s token not{exit}if
exch/s exch store{cvr}stopped{load
dup/p get
p
le{currentdict end
exch begin/e get exec}{begin}ifelse}if}loop{{e end}stopped{exit}if}loop
=

Un-golfed and commented:
% We associate the operators with their precedence /p and the executed commend /e
[
  (*)[/p  2 /e{mul}>>
  (d)[/p  2 /e{div}>> % This is division
  (+)[/p  1 /e{add}>>
  (-)[/p  1 /e{sub}>>
  (o)[/p  9 /e{   }>> % This is open bracket
  (c)[/p -1 /e{   }>> % This is close bracket
  (^)[/p  3 /e{exp}>>
  /p 0
>>begin

% Let's read the input string
/s(%stdin)(r)file 999 string readline pop def

% If we want to use the token operator, we have to replace (, [, ), ] and / to get meaningful results
% We use kind of an encoding array (familiar to PostScripters) to map those codes to o, c, and d.
0 1 s length 1 sub{        % index
  s exch                   % string index
  [0 1 255{}for] dup       % string index translationArray translationArray
  [(\(o)  ([o)  (\)c)  (]c)  (/d)] % string index translationArray translationArray reencodeArray
  {                        % string index translationArray translationArray translationString
    {}forall               % string index translationArray translationArray charCode newCharCode
    put dup                % string index translationArray translationArray
  }forall                  % string index translationArray translationArray
  pop                      % string index translationArray
  3 copy pop               % string index translationArray string index
  get                      % string index translationArray charCode
  get                      % string index translatedCharCode
  put                      % -/-
}for

% Now we can actually start interpreting the string
% We use the stack for storing numbers we read and the dictionary stack for operators that are "waiting"
{                          % number*
  s token not{exit}if      % number* string token
  exch /s exch store       % number* token
  % We try to interpret the token as a number
  {cvr}stopped{            % number* token
    % If interpretation as number fails, we have an operator
    load                   % number* opDict
    % Compare operator precedence with last operator on dictstack
    dup /p get             % number* opDict opPrec
    p                      % number* opDict opPrec prevOpPrec
    le {                   % number* opDict
      % If the last operator on the stack has at least the same precedence, execute it
      currentdict end      % number* opDict prevOpDict
      exch begin           % number* prevOpDict
      /e get exec          % number*
    }{                     % number* opDict
      % If last operator doesn't have higher precedence, put the new operator on the dictstack as well
      begin
    }ifelse
  }if
}loop
% If we're finished with interpreting the string, execute all operators that are left on the dictstack
{{e end}stopped{exit}if}loop
=

TODO: Right-associativity of exponentation

Ah... The dictstack: brilliant!

I'm allowed to comment on stackoverflow, so I was a little confused. Is it normal that the reputation is managed separately, or did I screw up my logins?

I wanted to tell you that there must be something wrong with your solution because all three test cases given above fail. However, I didn't try to understand what you're doing yet (some comments would be cool ;-)).

Once you hit 200 on any site, you'll start at 101 on every site. Or hit 50 here. 2) AUGHH! I thought it was a quick extension of the Basic Calculator. I didn't even see that brackets are required! And I didn't test it very well. Oh, well; pants down, at least my undies are clean!

@luserdroog: "@ThomasW" does not invite me to comment.

Seemed worth a try.

Python 2,339 335 bytes
import re
x,s=input(),re.sub
def f(y):
 y,r=s('- ','+ -',y).split(),['^','*','/','+','-']
 for c in r:
  while c in y:d=y.index(c)-1;a,b=map(float,[y[d],y[d+2]]);y=y[:d]+[((a,-a)[a<0]**b,a*b,a/b,a+b,a-b)[r.index(c)]]+y[d+3:]
 return`y[0]`
w=lambda b:s("[([]+[\d+\-*/^ .]*[)\]]",lambda m:f(m.group()[1:]),s(' +',' ',b))
print f(w(w(x)))

Try it online!

-4 bytes by changing str(x) with backticks ``!

Postscript, 1000 695 665 494
Stole ideas from ThomasW. Added feature: accepts strings with or without spaces around operators.[feature removed]

Using ARGUMENTS is shorter than %stdin, and easier to test, to boot!

Simplified the substitution to just replace brackets with parens.
575(1)10:36 PM:ps 0> gsnd -q -- calc2bg.ps '10 - 3 + 2'
9
576(1)10:37 PM:ps 0> gsnd -q -- calc2bg.ps '8 + 6 / 3 - 7 + -5 / 2.5'
1.0
577(1)10:37 PM:ps 0> gsnd -q -- calc2bg.ps '4 + [ ( -3 + 5 ) * 3.5 ] ^ 2 - 12'
41.0

Code:
/T[/^[/C{exp}/P 4/X{le}>>/*[/C{mul}/P 3/X{lt}>>/[/C{div}/P
3/X{lt}>>/+[/C{add}/P 2/X{lt}>>/-[/C{sub}/P
2/X{lt}>>>>def[/integertype{}/realtype{}/stringtype{V}/nametype{cvlit/N
exch store{P T N get dup/P get exch/X get exec{exit}if C end}loop T N get
begin}91 40 93 41>>begin/V{0 1 2 index length 1 sub{2 copy get
dup where{exch get}if 3 copy put pop pop}for[/N 0/R 0/P 0/C{}>>begin{token
not{exit}if exch/R exch store dup type exec R}loop{P 0 eq{end exit}if C
end}loop}def ARGUMENTS{V ==}forall

Ungolfed and commented:
%!
%Shunting-Yard Algorithm using dictstack for operators
%invoke with %gsnd -q -- calc2bg.ps [ 'expr1' ]*

%The operator table. C:code P:precedence X:test(implements associativity)
/T[
    /^[/C{exp}/P 4/X{le}>>
    /*[/C{mul}/P 3/X{lt}>>
    /[/C{div}/P 3/X{lt}>>
    /+[/C{add}/P 2/X{lt}>>
    /-[/C{sub}/P 2/X{lt}>>
>>def

%The type-dispatch dictionary
%numbers: do nothing
%string: recurse
%name: process op
[%/integertype{}/realtype{} %now uses `where` below
/stringtype{V}/nametype{
pstack()=
    cvlit/N exch store %stash cur-op
    {
        P %prec(tos)
        T N get %prec(tos) cur-op-dict
        dup/P get %prec(tos) cur-op-dict prec(cur-op)
        exch/X get %prec(tos) prec(cur-op) test(cur-op)
        exec{exit}if %exit if prec(tos) < || <= prec(cur-op)
/C load ==
        C %pop-and-apply
        end
pstack()=
    } loop
    T N get begin %push cur-op
}>>begin

%substitutions
[91 40 93 41>>begin %replace brackets with parens
/V {
    %pre-process
    0 1 2 index length 1 sub {
        2 copy get
        dup where { exch get } if
        3 copy put pop pop
    } for
dup ==

    [/N 0/R 0/P 0/C{}>>begin %dummy base operator and storage
    { token not{exit}if exch /R exch store %extract token, stash Remainder
pstack(>)=
        %dispatch type procedure
        dup type dup where { pop exec }{ pop } ifelse
    R }loop
pstack()=
    {
        P 0 eq{end exit}if %hit dummy op: exit
/C load ==
        C end %pop and apply
    } loop
} def

ARGUMENTS{V ==}forall %iterate through the command-line arguments

@ThomasW I wonder if this works to invite you to comment. (?)

I've posted a fuller implementation of the same idea in comp.lang.postscript.

source: Stack Exchange

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

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

sort: votes


text:
Output nearby primes
Write a program which takes an input (which may or may not be prime), and lists the immediate prime following and preceding it.
Example input:
1259

Example output:
1249 1277

Shortest program wins. Must execute within 10 seconds on a modern desktop PC. Inputs will be limited to 10,000 maximum.

It seems somewhat odd to list a time limit without also limiting the range of possible inputs. Are we required to find several-thousand-digit primes within ten seconds?

@Anon. Assume I will not give ridiculous inputs, but the program must be somewhat optimised. I have clarified the question text.

my one-liner is anything but optimal, but it runs in ~1s for an input of 10000. You have to try really hard to need 10s.

@ninjalj Just to weed out absolutely awful algorithms.

so you don't consider testing a number n for primality  by creating a string n characters long and testing that against a regex absolutely awful?

10k isn't a reasonable limit, combined with 10s.

May we assume that the input is at least 3, so that the "preceding prime" is defined?

Perl 5.10 (perl -E), 65 chars
Half the credit (at least) should go to @J B.
$m=<>;for(-1,1){$n=$m;0while(1x($n+=$_))=~/^1$|(^11+)\1+$/;say$n}

nice! the prime test regex!

yeah, I learned about it  at http://stackoverflow.com/questions/3543811/code-golf-happy-primes

Seems like you could save a couple of characters with a quoted regex (+2 for the qr, -4 for not needing the delimiters later).

Actually, it works without qr.  LMGTFY: 81 chars $m=$n=<>;$p='^1$|(^11+)\1+$';0while(1x--$m)=~$p;0while(1x++$n)=~$p;print"$m $n$/"

Second round, factoring both pattern matches (66 chars): perl -E'$m=<>;for(-1,1){$n=$m;0while(1x($n+=$_))=~q<^1$|(^11+)\1+$>;say$n}'

Mathematica, 19
#~NextPrime~{-1,1}&

very clever :0)

Mathematica: 28 chars
(k=NextPrime;{k[#,-1],k@#})&

Usage
%[1259]
{1249, 1277}

%[121231313159]
{121231313129, 121231313191}

Python - 93
Based on answer by fR0DDY. I basically merged lines 4 and 5, and shortened line 2 by using a different method.
n=input()-1
m=n+2
f=lambda n:any(n%x<1for x in range(2,n))
exec"n-=f(n);m+=f(m);"*m
print n,m

J, 22 characters
(_4&p:,4&p:)(".stdin)_

9 years old but hey... :) _4 4 p:"+

Python 116 111 109 Characters
n=input()-1
m=n+2
f=lambda n:any(pow(b,n-1,n)>1for b in(3,5,7,13))
while f(n):n-=1
while f(m):m+=1
print n,m

use f=lambda n:not(all(pow(b,n-1,n)<2for b in(3,5,7,13)))

@fR0DDY, instead of the first 3 lines use n=input()-1 and m=n+2, saves 3 chars...i think.

and maybe you can replace not(all(...)) by any(...) reversing the booleans

You don't count new lines. Actual count is 108.

@fR0DDY Please don't list all your intermediate solutions as they're viewable in the edit history if anyone wants to see them.

Also, please count newlines in your character count. -1 for deceiving others.

After you've fixed your count you can try replacing line 2 with f=lambda n:not all(n%x for x in range(2,n)) and lines 3 and 4 with: exec"n-=f(n);m+=f(m);"*m

I paste the code in Ideone and copy the characteres count from there. Sorry about that.

Jelly, 5 bytes
Æp,Æn

Try it online!

APL (Dyalog Extended), 6 bytes
¯4 4⍭⊢

Try it online!
I wish I knew a way to shorten this further.
¯4 and 4 when passed to ⍭ give the closest primes to the right argument(⊢).

Swift 190 187 185 110
Swift is very bad in code-golf, but I tried it anyway :D
It's getting shorter and shorter...(Thanks to @HermanLauenstein for removing 75 bytes)
var a=Int(readLine()!)!;for b in[-1,1]{var n=a,c=0;while c<1{n+=b;c=1;for i in 2..<n{if n%i<1{c=0}}};print(n)}

-75 bytes with a lot of restructuring var a=Int(readLine()!)!;for b in[-1,1]{var n=a,c=0;while c<1{n+=b;c=1;for i in 2..<n{if n%i<1{c=0}}};print(n)} (I haven't tested it properly yet)

Thanks @HermanLauenstein. It's my first code-golf, so I can need every help :)

Haskell: 99
s(z:y)=z:s[x|x<-y,mod x z>0];f(x:y:z:w)=(x,z):f(y:z:w);p x=(head.filter(\(c,v)->c<x&&v>x).f.s)[2..]

Example
Main> p 1259
(1249,1277)

Python, 116 139 chars (double indent is tab-char)
Uses good ole Sieve of Eratosthenes
Edits and (thanks a TON @JPvdMerwe). Should work with primes now.
l=n=input();a=range(n*2)
for i in a[2:]:a=[k for k in a if k==i or k%i]
for g in a:
 if g>n:print l,g;break
 if i!=n:l=g

Original
a=range(9999)
j=lambda a,n:[i for i in a if i==n or i%n]
for i in a[2:]:a=j(a,i)
o=n=input();
for i in a:
 if o<n and i>n:
  print o,i
 o=i

-1 For not counting NECESSARY white space.

@JPvdMerwe My fault, I'm new here, and I realized I may have used the wrong metric from my editor.

@JPvDMerwe also thanks for the help on the edits

@DougT cool everyone makes a mistake :) +1 To reverse my down vote, just make sure next time.

One trick you can do is to move lines 1-3 below line 4 and replace a=range(9999) with a=range(n). Also in line 2 you don't need to pass a to the lambda, you can just use it. This should shave off a lot.

Also I just realised this doesn't work if n is a prime.

Thinking some more, you can use: for i in a[2:]:a=[j for j in a if j==i or j%i] To get rid of that long lambda.

Playing around you need a=range(n*2)

You didn't count line breaks, real tally is 120. Use: http://www.javascriptkit.com/script/script2/charcount.shtml but make sure that you don't have an extra new line at the end.

Then there are 2 things you can still do: break -> n*=n and i!=n -> l<n

But your solution does not run within 10 seconds for 9900 as stated in the question.

Scala 119:
def p(n:Int)=(2 to n-1).exists(n%_==0)
def i(n:Int,v:Int):Int=if(!p(n+v))n+v else i(n+v,v)
Seq(-1,1).map(i(readInt,_))

ungolfed:
def notPrime (n:Int) =
    (2 to n-1).exists (n % _ == 0)

def itPrime (n: Int, vector:Int) : Int =
    if (! notPrime (n+vector)) n+vector
    else itPrime (n+vector, vector)

def nearbyPrime (value: Int) =
    Seq (-1, 1).map (sign => itPrime (value, sign))

21.2s to run all 9998 ints from 3 to 10.000

Python (123)
import Primes as p
j=i=int(input())
n=p.primes(i*2)
while not i in n[:]:
 i+=1
print(i)
while not j in n[:]:
 j-=1
print(j)

NOTE: The Primes module was written by me but it existed before this question was asked.  It was NOT written for this.  Nevertheless, this was deemed unfair, so here is the updated version.
Python(215)
j=i=int(input())
import math as m
s=list(range(i*2))
for n in s[:]:
 for l in range(1,int(m.ceil(m.sqrt(n)))):
  if(n%l)==0and l!=1and n in s:s.remove(n)
while not i in s:i+=1
print(i)
while not j in s:j-=1
print(j)

I don't know how you managed to get your count wrong but it's actually: 123

Also, @John unless the module is now part of the language, in the interest of fairness you should include the code. But Kudos on the honesty.

I think it cheating to use Primes; against the spirit of code golf.

@JPv: Huh.  It was wrong.  I wonder how that happened.

@Thomas, @JPv: I have posted an updated version without the import.

@John you can remove a lot of white space by moving the i+=1 for example to the same line as the while. Similarly for the last if. And it makes sense to merge the 2 ifs.

@JPv: Ah, right.  Thanks.  That was done in a hurry so I didn't have time to think about it much.

Stax, 7 bytes
èëïy▌Ü╚

Run and debug it
ASCII equivalent:
^:Px:pLJ

Built-ins.

JavaScript (Node.js), 79 bytes
f=(n,d)=>d?p(n)?n:f(n+d,d):[f(n-1,-1),f(n+1,1)]
p=(n,i=1)=>++i*i>n||n%i&&p(n,i)

Try it online!

C (gcc), 98 89 87 bytes
-9 bytes thanks to ceilingcat
N,i;g(n,d){for(i=N=n+=d;--i>1;)N*=N%i>0;N?printf("%d ",n):g(n,d);}f(n){g(n,-1);g(n,1);}

Try it online!
Full program version, C (gcc), 116 107 105 bytes
-9 bytes thanks to ceilingcat
N,i;g(n,d){for(i=N=n+=d;--i>1;)N*=N%i>0;N?printf("%d ",n):g(n,d);}main(n){scanf("%d",&n);g(n,-1);g(n,1);}

Try it online!

@ceilingcat Nice one!

Arn, 22 bytes
ét█ï▀¢│B¬Ÿ6├¼òa¡b←Æ╚ÑÕ

Try it!
Explained
Unpacked: k:((v:#.^2):i)[v?--k v?(k+2
One of the major weaknesses of Arn (along with operator precedence lmao)
  :                     Assign variable
k                       with name of k
    (                   Begin expression
        (
            :
          v
              #.        List of primes from 0 to
                  _     Variable initialized to STDIN; implied
                ^       exponentiated by
                  2     Literal two
        )               End expression
      :i                Index of
        _               implied
    )
[                       Begin sequence
    v
  ?                     Indexed by
    --k                 k minus 1
    v
  ?
    (
        k
      +                 Plus
        2
    )                   implied
]                       End of sequence; implied

05AB1E, 6 bytes
ÅMsÅN»

Try it online!
ÅMsÅN»  # full program
     »  # join...
ÅM      # nearest prime less than...
        # implicit input...
     »  # with...
   ÅN   # nearest prime greater than...
  s     # implicit input...
     »  # by a newline
        # implicit output

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

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


text:
Interpret Befunge-93
The program will be provided as the first argument, stdin should be used for all
read requests by the program and stdout for all write requests.  It can be
assumed that the program is less than 80 characters wide and less than 25 lines
high.

~ should push -1 if there is nothing to read.
Any pop off the bottom of the list should simply return 0, including for any calculations.
For p and g, x and y are 0 based indices.
Input should be fully buffered, i.e. & and ~ block the program until EOF is encountered on stdin then any remaining input is kept to serve future requests.

The following commands must be available:

0-9
    Push this number on the stack
+
    Addition: Pop a then b, push a+b
-
    Subtraction: Pop a then b, push b-a
*
    Multiplication: Pop a then b, push a*b
/
    Integer division: Pop a then b, push b/a, rounded down. If a is 0, result is undefined
%
    Modulo: Pop a then b, push the remainder of the integer division of b/a. If a is 0, result is undefined
!
    Logical NOT: Pop a value. If the value is 0, push 1; otherwise, push 0.
`
    Greater than: Pop a then b, push 1 if b>a, otherwise 0.
>
    Start moving right
<
    Start moving left
^
    Start moving up
v
    Start moving down
?
    Start moving in a random cardinal direction
_
    Pop a value; move right if value=0, left otherwise
|
    Pop a value; move down if value=0, up otherwise
"
    Start string mode: push each character's ASCII value all the way up to the next "
:
    Duplicate value on top of the stack
\
    Swap two values on top of the stack
$
    Pop value from the stack
.
    Pop value and output as an integer
,
    Pop value and output as ASCII character
#
    Trampoline: Skip next cell
p
    A "put" call (a way to store a value for later use). Pop y then x then v, change the character at the position (x,y) in the program to the character with ASCII value v
g
    A "get" call (a way to retrieve data in storage). Pop y then x, push ASCII value of the character at that position in the program
&
    Input an integer (may be multiple characters and may be negative) and push it
~
    Input a single character from stdin and push its ASCII value
@
    End program

This is a code golf, shortest answer wins.  If there is a tie then the first answer wins.
You may use any language feature not specifically designed for Befunge to implement this, if you want to try and translate Befunge to native code and eval it good luck.
For test cases look at my recent answers.  The reference interpreter I have been using is http://www.quirkster.com/js/befunge.html.
One quick test case of some features from "egnufeB">:#,_@
1-0g:"Z"-#v_$91+"sparw tup/teG">:#,_$               v                          Z
          >:" "-#v_$91+"ecaps snruter teg BOO">:#,_$v
v                >0" snruter teg BOO">:#,_$.91+,    >
>8:+:*11p11g#v_91+"tib 8 dengis"01-11p11g!#v_"nu">" era slleC">:#,_v
vv           >91+"tib 8>"                  >     ^                 >91+"krow " #
 >        >"spmuj egdE">:#,_   91+"krow "04-3%1+#v_        >"sredniamer evitag"v
>"ton od "^                                      >"ton od "^
"eN">:#,_  91+"skrow edomgnirts ni @">:#,_@                                    >

What kind of input does an "ask what user wants" on division by zero take? Full integer parsing? 0 to 9 digit? ASCII value?

@J B: I'll remove that requirement.  That's what Wikipedia says it should do but none of the interpreters I've seen do that.  I'll just make it undefined.

Befunge-93 - 404 371 361 352 339 337 323 bytes
<xyXYvp01<>110vv5_v#`0+1:_v#+!-"g"\<v"<":::<>1v#p03-1_>! g20gp00g1+0v25p
v2g02 < p0 20p<+vp020p01-10$_:"p"-!^>>-!\ v^ <>0p20pv|!*-";"\+1::~p0<
v2-10<^v# ^#<  <<$<       < ^+!-"_"\+!-"?"<>#^_10v4p<:^00 _$20g1+20p^
v21p010>#<40g20v>\%:40p5+g:92p:75*1--00g!\#^_\$0 v   >91+-^
<3+g01g 03p04+g<^++g04g02:*54p03:%\++g03g01:"P"p0<

Try It Online!
Input program must have at most 20 lines. Input can be provided in same file as Befunge program by placing it after a ; character. Yes, it can interpret itself, but the *54 in the bottom line should be replaced by *53 if you do that. And if you ask that interpreted interpreter to interpret itself, change it to *52 etc. If run in a Befunge-97 interpreter, it will also support the a-f commands (but not ' or any new command that affects control flow or wrapping behavior).
Note that it basically asks the interpreter it runs in to handle all the stuff relating to I/O and stack, so its specific behavior is largely dependent on that of the interpreter running it. In other words, it is perfectly compliant if run in a compliant interpreter.
It works by reading in the program from input (until EOF or semicolon) directly into the playfield below it, then simulating the movement of a virtual instruction pointer through that program. It copies each command from the program into its own execution area (at position (9,2) on the grid) and runs its own instruction pointer through it after ensuring all of its own data has been removed from the stack (as all of the interpreted program's stack data is maintained at the bottom of the stack). This is the standard methodology for Befunge self-interpretation since the early 00s, but I don't think it has ever been done in such a small program.
A fuller explanation is in the annotations you can see by clicking the link above.

Perl, 515 525 532
Ok, so this might not be the most readable code I've ever written, but it does run all the examples in the reference implementation page properly, and use -1 as a ~-didn't-have-a-reply value.  (the programs in the page exercise the empty stack behavior extensively)
As usual, Perl 5.10 or later.  In this instance, -M5.010 is your best bet.  Newlines for presentation on CG.SE, you should remove them before trying.  (in this "edit 1.5" ragged-right version, it might actually work out of the box)
@p=map[/./g],<>;$h=1;$_="for(;;){for(D_=P[Y][X]){
when('\"BS=!S}when(!!S){IordW0'||/\\d/){ID_W+BIO+
OW-BEO;IO-MW*BIO*OW/BEO;Iint(O/M)W%BEO;IO% MW!BI!
OW`BEO;I(M<O)W?BD_=qw(< > ^ v)[rand 4]R_BD_=O?'<'
:'>'R|BD_=O?'^':'v'R>BH=1;V=0W<BH=-1;V=0W^BH=0;V
=-1WvBH=0;V=1W:BI0+S[-1]W\\\\BIO,OWDBOW.BsayOW,B
print chrOW#BFWpBEO;N=O;P[M][N]=chrOWgBEO;IordP[
M][O]W&BIE<>W~BIord<>||-1WABexit}}F}";s/B/'){/g;
s/I/pushAs,/g;s/E/M=/g;s/F/X=(X+H)%A{P[0]};Y=(Y+
V)%Ap/g;s/O/(popAs)/g;s/R/;redoW/g;s/W/}when('/g
;y/DA/$@/;s/[A-Z]/\$\l$&/g;eval

Improvements welcome :-D
Edit 1: fix integer division (+2), reorganize (-9)
Edit 2 1.5: read char by char (+4); halt on division by zero (-10)
Still missing char by char input, I'm not clear yet how it parses numbers and I'm too tired to be able to do it now.
Not motivated enough to make the cell size unsigned 8-bit as suggested by the compatibility test, and not sure how negative remainders are expected in an unsigned environment.

Wow, you're not kidding about the readability.  How do you get it working with input?  I just tried echo "-2 + 6 / 2 * 8 - 1 / 2 - 18" | perl -M5.010 pe calc.be, where pe contains this program and calc.be contains this answer of mine, and it just output the input string.

My first bet would be a different interpretation of the spec than the reference implementation: ~ reads by ascii value indeed, but line by line.  I'll look into it.

Yes, that would be it.  Just tried using "-2\n+\n6\n/\n2\n*\n8\n-\n1\n/\n2\n-\n18\n\n" as the input and it worked.  Although it gave -10.5 instead of -11, probably not rounding after /.

+1 now since the spec's ambiguous.  I'll try and find out what other cli interpreters do, all the javascript ones seem to just use a one-line textbox.

The integer division behavior is an unacceptable bug that will likely cost me 2 char.  I'm split on the line-by-line.  Is my interpretation of the spec valid? (oh, didn't see you'd answered in the meantime)

So far all I've seen do fully buffered input, they pause at & and ~ until an EOF is entered then keep the rest of the input for future requests.  I'll change the spec now, I've also found a quick test of a few features that I'll add as well.

16bit MSDOS .COM File - 1104 bytes
This is Base64 encoded (decoder here), save decoded file as a .com and execute from command line with name of program file to run as the only argument. Tested in WinXP command prompt.
yEAAADP/jNiAxBCJRv6JRvKAxBCJfuqJRuyJfvqJfviJfvSAxBCJRvbHRuiMAo7AM8C5AIDzq7Qs
zSGJVvC6RgWKHoAAMv+A6wF9Cei3ALQJzSHJw8aHggAAuAA9uoIAzSG6SAVy5YvYjkb+uQCAM8Dz
q7kBALpQBbQ/zSG6SgVyygvAdCWgUAU8CnQHPCBy4qrr34vHOkb5cgOIRvn+RviB5wD/gccAAevI
tD7NIQv/ukwFdJa4AwDNEDPb6FQAtAfNITxxdDk8cnQhPDF0DTwydBE8c3Xo6I8A6+CLRvaJRvLr
2ItG/olG8uvQi0b2iUby6B4A6HEAgH76AHTu67zoAgDJw7gAuI7AuCAHuQCA86vDYB6OXvK4ALiO
wLUZM/8z9rQHsVCsq/7JdfqBxrAA/s118FOLRvI7Rv6yz3QFi170svCA+1BzG4D/GXMWise0oPbk
ANiA1AAA2IDUAIv4R4rCqlsfYcOORv4migc8MHJVPDl3UbQALDDoKwD/ZugK23UDil75/svD/sM6
Xvl1+DLbwwr/dQOKfvj+z8P+xzp++HX4Mv/DBsR+6quJfuoHwwbEfuozwAv/dAmD7wImiwWJfuoH
w77uBIPGA4A8/3QOOAR19ItEAQvAdAP/4MO6TgXpZP7olP8migc8InSNtADos//r7+i4/4nB67To
9v8Dwel0/+ju/yvB6Wz/6Ob/9+npZP/o3v+Z9/npW//o1f+Z9/mLwulQ/+iF/wvAuAEAdAFI6UL/
6Lz/O8G4AQB/AUjpNP/HRuiMAukv/+hh/wvAdPHHRuiCAukg/+hS/wvAdAjHRuiWAukR/8dG6KAC
6Qn/i0bwuk189+IFGTaJRvAkBgWSA4vwrYlG6Ont/pYCoAKCAowC6Bf/6Ar/6dn+6FP/kegA/4nI
6c3+6AL/6cr+6Pz+C8B5CffYULAt6CYAWFO7UAUz0rkKAPfxgMIwiBdDC8B170uKB+gKAIH7UAV1
9Fvplf48CnQUBsR+9KqLxzxQdQSBx7AAiX70B8PGRvQA/kb1w+in/uja/+ls/uhp/ulm/ugOAOiV
/gaORv4miAQH6VX+6If+ik74C8B5BwLBgNQA6/X28YjhtQDocP5Rik75C8B5BwLBgNQA6/X28Yjg
WYjMi/DD6Mr/Bo5G/iaKBAe0AOkP/v928otG9olG8jP2Msnol/20B80hPC11CwrJdfH+wehc/+vq
PA11Do9G8ovGCsl0AvfY6dr9iMUsMDwJd9C0AFCwCvfmC9JadcT2xIB1vwHC9saAdbiJ1ojo6CH/
66//dvKLRvaJRvLoPf20B80hPCBy+FDoB/9YtACPRvLpkP3GRvoBwysAAy0IAyoQAy8YAyUhAyEs
A2A6Az5IAzxXA15mA3ZuAz92A19QA3xfAyLoAjqaA1yjAySvAy61AywKBCMTBHAZBGddBCZtBH7L
BEDsBCB/AgB/Av8xJDIkMyQ0JDUk

On startup, the display shows the program. Commands are:

r - runs the program (switches to output screen)
s - single steps the program
q - quits the interpreter
1 - shows output screen (white cursor is current output position)
2 - shows program screen (red cursors is current program position)

When an input command is executed, the display switches to the output screen. Input is echoed to the output screen. For ascii input, only characters in the range 32-255 are accepted. For numeric input, only values in the range -32768 to 32767 are allowed, press enter to complete input (sorry, no backspace).
I really should add a stack screen as well.
Update
Here's the original assembly source code, assembled using A86. It's quite long:
  enter 64,0
  xor di,di
  mov ax,ds
  add ah,10h
  mov [bp-2],ax   ; program
  mov [bp-14],ax  ; current display
  add ah,10h
  mov w[bp-22],di ; stack off
  mov [bp-20],ax  ; stack seg
  mov w[bp-6],di  ; exit status
  mov w[bp-8],di  ; size of field -8=lines,-7=columns
  mov w[bp-12],di ; output window position
  add ah,10h
  mov w[bp-10],ax; output segment
  mov w[bp-24],MoveRight

  ; clear output
  mov es,ax
  xor ax,ax
  mov cx,8000h
  rep stosw

  ; random seed
  mov ah,2ch
  int 21h
  mov w[bp-16],dx

  ; get filename
  mov dx,StrNoFile
  mov bl,[80h]
  xor bh,bh
  sub bl,1
  jge NoError

Error:
  call ClearScreen
  mov ah,9
  int 21h
  leave
  ret

NoError:
  ; open file
  mov b[82h+bx],0
  mov ax,3d00h
  mov dx,82h
  int 21h
  mov dx,StrBadFile
  jc Error
  mov bx,ax
  ; clear program
  mov es,[bp-2]
  mov cx,8000h
  xor ax,ax
  rep stosw
  ; read file
ReadLoop:
  mov cx,1
  mov dx,EOP
  mov ah,3fh
  int 21h
  mov dx,StrBadRead
  jc Error
  or ax,ax
  jz EOF
  mov al,b[EOP]
  cmp al,10
  je EOL
  cmp al,32
  jb ReadLoop
  stosb
  jmp ReadLoop
EOL:
  mov ax,di
  cmp al,[bp-7]
  jb l9
  mov [bp-7],al
l9:
  inc b[bp-8]
  and di,0ff00h
  add di,100h
  jmp ReadLoop
EOF:
  mov ah,3eh
  int 21h
  or di,di
  mov dx,StrEmptyFile
  jz Error
  ; initialise
  mov ax,3
  int 10h
  xor bx,bx ; PC
  ; execute
Redraw:
  call DisplayProgram
WaitForInput:
  mov ah,7
  int 21h
  cmp al,'q'
  je Quit
  cmp al,'r'
  je DoRun
  cmp al,'1'
  je ShowIO
  cmp al,'2'
  je ShowProgram
  cmp al,'s'
  jne WaitForInput
  ; single step
  call Execute
  jmp Redraw

ShowIO:
  mov ax,[bp-10]
  mov [bp-14],ax
  jmp Redraw

ShowProgram:
  mov ax,[bp-2]
  mov [bp-14],ax
  jmp Redraw

DoRun:
  mov ax,[bp-10]
  mov [bp-14],ax
  call DisplayProgram
  call Execute
  cmp b[bp-6],0
  je DoRun
  jmp Redraw

Quit:
  call ClearScreen
  leave
  ret

ClearScreen:
  mov ax,0b800h
  mov es,ax
  mov ax,720h
  mov cx,8000h
  rep stosw
  ret

DisplayProgram:
  pusha
  push ds
  mov ds,[bp-14]
  mov ax,0b800h
  mov es,ax
  mov ch,25
  xor di,di
  xor si,si
  mov ah,7
l1:
  mov cl,80
l2:
  lodsb
  stosw
  dec cl
  jnz l2
  add si,256-80
  dec ch
  jnz l1
  push bx
  mov ax,[bp-14]
  cmp ax,[bp-2]
  mov dl,0cfh
  je l33
  mov bx,[bp-12]
  mov dl,0f0h
l33:
  cmp bl,80
  jae l3
  cmp bh,25
  jae l3
  mov al,bh
  mov ah,160
  mul ah
  add al,bl
  adc ah,0
  add al,bl
  adc ah,0
  mov di,ax
  inc di
  mov al,dl
  stosb
l3:
  pop bx
  pop ds
  popa
  ret

Execute:
  mov es,[bp-2]
  mov al,es:[bx]

  cmp al,'0'
  jb NotPush
  cmp al,'9'
  ja NotPush

  ; push number
  mov ah,0
  sub al,'0'
PushValueUpdatePC:
  call PushValue
UpdatePC:
  jmp [bp-24]

MoveLeft:
  or bl,bl
  jnz MoveLeftNoWrap
  mov bl,[bp-7]
MoveLeftNoWrap:
  dec bl
  ret

MoveRight:
  inc bl
  cmp bl,[bp-7]
  jne ret
  xor bl,bl
  ret

MoveUp:
  or bh,bh
  jnz MoveUpNoWrap
  mov bh,[bp-8]
MoveUpNoWrap:
  dec bh
  ret

MoveDown:
  inc bh
  cmp bh,[bp-8]
  jne ret
  xor bh,bh
  ret

PushValue:
  push es
  les di,[bp-22]
  stosw
  mov [bp-22],di
  pop es
  ret

PopValue:
  push es
  les di,[bp-22]
  xor ax,ax
  or di,di
  jz PopValueZero
  sub di,2
  mov ax,es:[di]
  mov [bp-22],di
PopValueZero:
  pop es
  ret

NotPush:
  mov si,Functions-3
NextFunction:
  add si,3
FindFunction:
  cmp b[si],255
  je Endsearch
  cmp b[si],al
  jne NextFunction
  mov ax,[si+1]
  or ax,ax
  je EndSearch
  jmp ax
  ret

EndSearch:
  mov dx,StrEndSearch
  jmp Error

DoStringMode:
  call UpdatePC
  mov al,es:[bx]
  cmp al,'"'
  je UpdatePC
  mov ah,0
  call PushValue
  jmp DoStringMode

PopTwoValues:
  call PopValue
  mov cx,ax
  jmp PopValue

DoAdd:
  call PopTwoValues
  add ax,cx
  jmp PushValueUpdatePC

DoSub:
  call PopTwoValues
  sub ax,cx
  jmp PushValueUpdatePC

DoMultiply:
  call PopTwoValues
  imul cx
  jmp PushValueUpdatePC

DoDivide:
  call PopTwoValues
  cwd
  idiv cx
  jmp PushValueUpdatePC

DoModulo:
  call PopTwoValues
  cwd
  idiv cx
  mov ax,dx
  jmp PushValueUpdatePC

DoNot:
  call PopValue
  or ax,ax
  mov ax,1
  jz DoNotZero
  dec ax
DoNotZero:
  jmp PushValueUpdatePC

DoGreaterThan:
  call PopTwoValues
  cmp ax,cx
  mov ax,1
  jg DoGreaterThanIs1
  dec ax
DoGreaterThanIs1:
  jmp PushValueUpdatePC

DoMoveRight:
  mov [bp-24],MoveRight
  jmp UpdatePC

DoLeftRight:
  call PopValue
  or ax,ax
  jz DoMoveRight

DoMoveLeft:
  mov [bp-24],MoveLeft
  jmp UpdatePC

DoMoveUpDown:
  call PopValue
  or ax,ax
  jz DoMoveDown

DoMoveUp:
  mov [bp-24],MoveUp
  jmp UpdatePC

DoMoveDown:
  mov [bp-24],MoveDown
  jmp UpdatePC

DoRandomDirection:
  mov ax,[bp-16]
  mov dx,31821
  mul dx
  add ax,13849
  mov [bp-16],ax
  and al,6
  add ax,Movements
  mov si,ax
  lodsw
  mov [bp-24],ax
  jmp UpdatePC

Movements:
  dw MoveUp, MoveDown, MoveLeft, MoveRight

DoDuplicate:
  call PopValue
  call PushValue
  jmp PushValueUpdatePC

DoSwap:
  call PopTwoValues
  xchg ax,cx
  call PushValue
  mov ax,cx
  jmp PushValueUpdatePC

DoPop:
  call PopValue
  jmp UpdatePC

DoPopPrint:
  call PopValue
  or ax,ax
  jns Positive
  neg ax
  push ax
  mov al,'-'
  call PrintChar
  pop ax
Positive:
  push bx
  mov bx,EOP
DivLoop:
  xor dx,dx
  mov cx,10
  div cx
  add dl,'0'
  mov [bx],dl
  inc bx
  or ax,ax
  jnz DivLoop
PrintLoop:
  dec bx
  mov al,[bx]
  call PrintChar
  cmp bx,EOP
  jne PrintLoop
  pop bx
  jmp UpdatePC

PrintChar:
  cmp al,10
  je AsciiCR
  push es
  les di,[bp-12]
  stosb
  mov ax,di
  cmp al,80
  jne NoLF
  add di,256-80
NoLF:
  mov [bp-12],di
  pop es
  ret
AsciiCR:
  mov b[bp-12],0
  inc b[bp-11]
  ret

DoPopAsciiPrint:
  call PopValue
  call PrintChar
  jmp UpdatePC

DoTrampoline:
  call UpdatePC
  jmp UpdatePC

DoPut:
  call GetCoord
  call PopValue
  push es
  mov es,[bp-2]
  mov es:[si],al
  pop es
  jmp UpdatePC

GetCoord:
  call PopValue
  mov cl,[bp-8]
DoGet1:
  or ax,ax
  jns DecrementY
  add al,cl
  adc ah,0
  jmp DoGet1
DecrementY:
  div cl
  mov cl,ah
  mov ch,0
  call PopValue ; x
  push cx
  mov cl,[bp-7]
DoGet2:
  or ax,ax
  jns DecrementX
  add al,cl
  adc ah,0
  jmp DoGet2
DecrementX:
  div cl
  mov al,ah
  pop cx ; ax=x, cx=y
  mov ah,cl
  mov si,ax
  ret

DoGet:
  call GetCoord
  push es
  mov es,[bp-2]
  mov al,es:[si]
  pop es
  mov ah,0
  jmp PushValueUpdatePC

DoInput:
  push [bp-14]
  mov ax,[bp-10]
  mov [bp-14],ax
  xor si,si
  xor cl,cl
DoInput1:
  call DisplayProgram
  mov ah,7
  int 21h
  cmp al,'-'
  jne DoInputEnter
  or cl,cl
  jnz DoInput1
  inc cl
  call PrintChar
  jmp DoInput1

DoInputEnter:
  cmp al,13
  jnz DoInputDigit

  pop [bp-14]
  mov ax,si
  or cl,cl
  jz DoInput3
  neg ax
DoInput3:
  jmp PushValueUpdatePC

DoInputDigit:
  mov ch,al
  sub al,'0'
  cmp al,9
  ja DoInput1
  mov ah,0
  push ax
  mov al,10
  mul si
  or dx,dx
  pop dx
  jnz DoInput1
  test ah,80h
  jnz DoInput1
  add dx,ax
  test dh,80h
  jnz DoInput1
  mov si,dx
  mov al,ch
  call PrintChar
  jmp DoInput1

DoInputAscii:
  push [bp-14]
  mov ax,[bp-10]
  mov [bp-14],ax
  call DisplayProgram
DoInputAscii1:
  mov ah,7
  int 21h
  cmp al,32
  jb DoInputAscii1
  push ax
  call PrintChar
  pop ax
  mov ah,0
  pop [bp-14]
  jmp PushValueUpdatePC

DoExit:
  mov b[bp-6],1
  ret

Functions:
  db '+' ; Addition: Pop a then b, push a+b
  dw DoAdd
  db '-' ; Subtraction: Pop a then b, push b-a
  dw DoSub
  db '*' ; Multiplication: Pop a then b, push a*b
  dw DoMultiply
  db '/' ; Integer division: Pop a then b, push b/a, rounded down. If a is 0, result is undefined
  dw DoDivide
  db '%' ; Modulo: Pop a then b, push the remainder of the integer division of b/a. If a is 0, result is undefined
  dw DoModulo
  db '!' ; Logical NOT: Pop a value. If the value is 0, push 1; otherwise, push 0.
  dw DoNot
  db '`' ; Greater than: Pop a then b, push 1 if b>a, otherwise 0.
  dw DoGreaterThan
  db '>' ; Start moving right
  dw DoMoveRight
  db '<' ; Start moving left
  dw DoMoveLeft
  db '^' ; Start moving up
  dw DoMoveUp
  db 'v' ; Start moving down
  dw DoMoveDown
  db '?' ; Start moving in a random cardinal direction
  dw DoRandomDirection
  db '_' ; Pop a value; move right if value=0, left otherwise
  dw DoLeftRight
  db '|' ; Pop a value; move down if value=0, up otherwise
  dw DoMoveUpDown
  db '"' ; Start string mode: push each character's ASCII value all the way up to the next "
  dw DoStringMode
  db ':' ; Duplicate value on top of the stack
  dw DoDuplicate
  db '\' ; Swap two values on top of the stack
  dw DoSwap
  db '$' ; Pop value from the stack
  dw DoPop
  db '.' ; Pop value and output as an integer
  dw DoPopPrint
  db ',' ; Pop value and output as ASCII character
  dw DoPopAsciiPrint
  db '#' ; Trampoline: Skip next cell
  dw DoTrampoline
  db 'p' ; A "put" call (a way to store a value for later use). Pop y then x then v, change the character at the position (x,y) in the program to the character with ASCII value v
  dw DoPut
  db 'g' ; A "get" call (a way to retrieve data in storage). Pop y then x, push ASCII value of the character at that position in the program
  dw DoGet
  db '&' ; Input an integer (may be multiple characters and may be negative) and push it
  dw DoInput
  db '~' ; Input a single character from stdin and push its ASCII value
  dw DoInputAscii
  db '@' ; End program
  dw DoExit
  db ' ' ; NOP
  dw UpdatePC
  db 0 ; NOP
  dw UpdatePC
  db 255

StrNoFile:
  db "1$";"No File$"
StrBadFile:
  db "2$";"Bad File$"
StrBadRead:
  db "3$";"Bad Read$"
StrEmptyFile:
  db "4$";"Empty File$"
StrEndSearch:
  db "5$";"Bad Instruction$"
EOP:

Would you mind adding the assembly for this?

@FUZxxl: I've added the original source code.

C (gcc), 853 815 801 787 770 748 735 745 737 bytes
#define z(a,b);a(){b;}
#define Y*s
#define Z*s--
S[1<<20],Y=S,x,y,m,r,c=-1,t,n=80;char M[2000]z(b,Y=!Y)z(G,m=1)z(k,x&1?r-=x-2:(c-=x-1))z(H,Z)z(E,Y%=Z)z(K,scanf("%d",++s))z(B,Y*=Z)z(A,Y+=Z)z(i,putchar(Z))z(a,Y-=Z)z(I,printf("%d ",Z))z(d,Y/=Z)z(g,Y=Y++)z(L,x=2)z(R,x=0)z(w,Y++^=Z^=Y++^=Z)z(U,x=3)z(h,Z?L():R())z(e,Y=Z<Y)z(J,Y=M[Z*n+Y])z(j,M[Z*n+Z]=s[-2];Z)z(D,x=1)z(v,Z?U():D())z(l,*++s=getchar())F();(*f[])()={[33]=b,G,k,H,E,K,[42]=B,A,i,a,I,d,[58]=g,0,L,0,R,F,[92]=w,0,U,h,e,['g']=J,['p']=j,['v']=D,['|']=v,0,l}z(F,f["><^v"[rand()&3]]())main(C,V)int**V;{for(t=open(V[1],!memset(M,32,2000));read(t,&C,1);)C-10?M[y*n+x++]=C:(x=!++y);for(R();m|t-64;m?t-34?*++s=t:(m=0):t>47&t<58?*++s=t-48:f[t]&&f[t]())k(),t=M[(r=(r+25)%25)*n+(c=(c+n)%n)];}

Try it online!
The program is loaded into an array and the interpreter enters the main loop; the byte at the current program counter is the offset of an array of function pointers, each function performs the operation required by that instruction. String mode and numeric literals are special cases that are handled differently.
Slightly golfed less
#define z(a,b);a(){b;}
#define Y*s
#define Z*s--
S[1<<20],Y=S,x,y,m,r,c=-1,t;
char M[2000]
z(b,Y=!Y)                  /* ! */
z(G,m=1)              /* string mode */
z(k,x&1?r-=x-2:(c-=x-1))   /* # */
z(H,Z)                     /* $ */
z(E,Y%=Z)                  /* % */
z(K,scanf("%d",++s))       /* & */
z(B,Y*=Z)                  /* * */
z(A,Y+=Z)                  /* + */
z(i,putchar(Z))            /* , */
z(a,Y-=Z)                  /* - */
z(I,printf("%d ",Z))       /* . */
z(d,Y/=Z)                  /* / */
z(g,Y=Y++)                 /* : */
z(L,x=2)                   /* < */
z(R,x=0)                   /* > */
z(w,Y++^=Z^=Y++^=Z)        /* \ */
z(U,x=3)                   /* ^ */
z(h,Z?L():R())             /* _ */
z(e,Y=Z<Y)                 /*\` */
z(J,Y=M[Z*80+Y])           /* g */
z(j,M[Z*80+Z]=s[-2];Z)     /* p */
z(D,x=1)                   /* v */
z(v,Z?U():D())             /* | */
z(l,*++s=getchar())        /* ~ */
F();                       /* ? */
(*f[])()={[33]=b,G,k,H,E,K,
          [42]=B,A,i,a,I,d,
          [58]=g,0,L,0,R,F,
          [92]=w,0,U,h,e,
          ['g']=J,['p']=j,
          ['v']=D,['|']=v,0,l}
z(F,f["><^v"[rand()&3]]()) /* ? */
main(C,V)int**V;{
 /* load */
 for(t=open(V[1],!memset(M,32,2000));read(t,&C,1);)
  C-10?M[y*80+x++]=C:(x=!++y);
 /* execute */
 for(R();m|t-64;m?t-34?*++s=t:(m=0):t>47&t<58?*++s=t-48:f[t]&&f[t]())
  k(),
  t=M[(r=(r+25)%25)*80+(c=(c+80)%80)];
}

Edit: Improved test coverage and fixed bugs. Test suite largely lifted from esolang-park

Delphi, 970 842
Since I did the Fish golf first, I just copied that and changed the interpretation to use Befunge-93 specs (which are simpler than Fish) so I mainly had to strip things away.
In the next revision I won 64 characters by implementing the movement code using 2 instead of 4 variables. Oh, and I inverted the stack, removing the need for a length variable.
Another nice win is the '?' (random direction) instruction - I just change it into one of the four directions and let them handle it.
const X=80;var f:TextFile;c,s:String;i,p,d,A:Int16;procedure U(v:Int8);begin s:=Chr(v)+s;end;function O:Int8;begin if s=''then Exit(0);O:=Ord(s[1]);Delete(s,1,1)end;procedure E;begin i:=(p div X)+(d div X);p:=i*X+(p+d)mod X;i:=Ord(c[1+p])end;begin Assign(f,ParamStr(1));Reset(f);for A:=1to 26do begin ReadLn(f,s);c:=c+s+StringOfChar(' ',X-Length(s))end;d:=1;p:=-d;repeat E;A:=i;case i-32of1,63,92:A:=Ord(O=0);2:repeat E;U(i)until i=A;5,15,26,60:A:=O;31:i:=Ord('<>^v'[1+Random(4)]);71,80:A:=X*O+O+1;6:Read(A);94:Read(PChar(@A)^)end;if i=58then U(A);case i-32of 16..25:U(i-48);11:U(O+O);13:U(-O+O);10:U(O*O);15:U(O div A);5:U(O mod A);64:U(Ord(O<O));28,30:d:=i-61;62:d:=-X;86:d:=X;63:d:=2*A-1;92:d:=2*A*X-X;2,4:O;60:s:=Chr(O)+Chr(A)+s;14:Write(O,' ');12:Write(Chr(O));3:E;80:c[A]:=Chr(O);71:U(Ord(c[A]));32:Exit;1,6,26,94:U(A)end;until 0=1;end.

Here the indented and commented code :
{debug}uses Windows;{}
const
  X=80;
var
  // f is the source file
  f:TextFile;
  // c is the entire codebox (a 2-dimensional program)
  c,
  // s is the stack (kept as a string)
  s:String;
  // i is the current instruction read from the program
  i,
  // p is the position in the program
  p,
  // d is the delta for each step
  d,
  // A is a temporary variable (only uppercase var, to coincide with comments)
  A
  :Int16;

procedure U(v:Int8); // PUSH
begin
  // Push value onto the stack:
  s:=Chr(v)+s;
end;

function O:Int8; // POP
begin
  // Pop value from the stack :
  if s=''then Exit(0);
  O:=Ord(s[1]);
  Delete(s,1,1)
end;

procedure E; // STEP
begin
//{debug}Sleep(3);{}
  // Note : x-step needs to stay on same line, y-step needs to stay on same column
  i:=(p div X)+(d div X);
//  i:=i mod 25;// Enable this to wrap y-edge too
  p:=i*X+(p+d)mod X;
  i:=Ord(c[1+p])
end;

begin
  // Open file given at the command-line, and read & expand it's lines into our program buffer :
  Assign(f,ParamStr(1));
  Reset(f);
  for A:=1to 26do
  begin
    ReadLn(f,s);
    c:=c+s+StringOfChar(' ',X-Length(s))
    {debug};SetLength(c,A*X)
  end;
  // s:=''; Since we read 1 line too many above, s should always be empty now
  d:=1;
  p:=-d;
  repeat
    // Take a step (which gives a new 'i'nstruction) and make a copy of the stack :
    E;

    // Prevent begin+end pairs by handling instructions in 3 consecutive case blocks; This is applied to
    // all situations where this saves 1 or more characters, justifying the cost for another case-block.

    // Shorten '"' (>2) string-collecting, by remembering the quote character in A :
    A:=i;

    // Shorten a few cases by preparing variables so they can be shared with eachother and the 3rd case-block below :
    case i-32of // Note : The instruction is decreased by 32, resulting in less digits in the cases below!
      // Shorten '!' (>1), '_' (>63) and '|' (>92), by remembering Ord(O=0) in A :
      1,63,92:A:=Ord(O=0);
      // Shorten '"' string-collecting, by pushing the entire string here (the opening quote was remembered in A) :
      2:repeat E;U(i)until i=A; // Note :  We stop at the closing character, so the next block will still handle 'i'!
      // These instructions all need to Pop A, so write it just once here :
      5,15,26,60:A:=O;
      // Shorten '?' (>31): Choose a random direction instruction and let the 3rd case-block handle it :
      31:i:=Ord('<>^v'[1+Random(4)]);
      // Shorten 'g' (>71) and 'p' (>80): Calculate A so that the 3rd case-block doesn't need a begin+end pair :
      71,80:A:=X*O+O+1; // Note : This assumes Delphi evaluates leftmost call to O first!
      // Shorten '&' by reading a number from the input into A :
      6:Read(A);
      // Shorten '!' Prevent begin+end for input retrieval, by reading the input into A here :
      94:Read(PChar(@A)^) // Note : This case is last, because it ends on ')', which avoids a closing ';'
    end;

    // Shorten ':' (>58-32=26): Share implementation with '&' (>6) and '~' (>94) by pushing first copy of A (read above) here
    if i=58then U(A);

    // This 3rd case-block contains the final code for all statements :
    case i-32of // Note : The instruction is decreased by 32, resulting in less digits in the cases below!
      //'0'..'9': Push this number on the stack
      16..25:U(i-48);
      //'+': Addition: Pop A then B, push A+B
      11:U(O+O); // Note : A and B are inverted, but order is irrelevant here
      //'-': Subtraction: Pop A then B, push B-A
      13:U(-O+O); // Note : Delphi evaluates left-to-right, so we need to reverse the operation
      //'*': Multiplication: Pop a then b, push a*b
      10:U(O*O); // Note : A and B are inverted, but order is irrelevant here
      //'/': Integer division: Pop A then B, push B/A, rounded down. If A is 0, result is undefined
      15:U(O div A); // if A=0then U(0)else U(O mod A);
      //'%': Modulo: Pop A then B, push the remainder of the integer division of B/A. If a is 0, result is undefined
       5:U(O mod A); // if A=0then U(0)else U(O mod A);
      //'`': Greater than: Pop A then B, push 1 if B>A, otherwise 0.
      64:U(Ord(O<O)); // Note : Delphi evaluates left-to-right, so we need to reverse the test
      //'<': Start moving left
      //'>': Start moving right
      28,30:d:=i-61;
      //'^': Start moving up
      62:d:=-X;
      //'v': Start moving down
      86:d:=X;
      //'_': Pop a value; move right if value=0, left otherwise
      63:d:=2*A-1; // Note : A is already determined as Ord(O=0) in 1st case block
      //'|': Pop a value; move down if value=0, up otherwise
      92:d:=2*A*X-X; // Note : A is already determined as Ord(O=0) in 1st case block
      //'"': Start string mode: push each character's ASCII value all the way up to the next "
      //'$': Pop value from the stack
      2,4:O;
      //'\': Swap two values on top of the stack
      60:s:=Chr(O)+Chr(A)+s; // Note : A was Popped in 1st case block
      //'.': Pop value and output as an integer
      14:Write(O,' ');
      //',': Pop value and output as ASCII character
      12:Write(Chr(O));
      //'#': Trampoline: Skip next cell
      3:E;
      //'p': A "put" call (a way to store a value for later use). Pop y then x then v, change the character at the position (x,y) in the program to the character with ASCII value v
      80:c[A]:=Chr(O); // Note : A was Popped in 1st and 2nd case block, calculating y*width+x
      //'g': A "get" call (a way to retrieve data in storage). Pop y then x, push ASCII value of the character at that position in the program
      71:U(Ord(c[A])); // Note : A was Popped in 1st and 2nd case block, calculating y*width+x
      //'@': Rotates the top 3 values on the stack clockwise, respectively. (eg. if your stack is 1,2,3,4, would result in 1,4,2,3)
      32:Exit;
      //'!': Logical NOT: Pop a value. If the value is 0, push 1; otherwise, push 0.
      //'&':  Input a number from stdin and push its value
      //':': Duplicate value on top of the stack
      //'~':  Input a single character from stdin and push its ASCII value
      1,      // Note for '!' : A is already determined as Ord(O=0) in 1st case block
      6,
      26,     // Note for ':' : First A was already pushed once above
      94:U(A) // Note for '~' : Read() into A was done in 1st case block
    end;
  until 0=1;
end.

Output from compat.bf :
OOB get returns 0
Cells are unsigned 8 bit
Edge jumps work
Negative remainders work
@ in stringmode works

Output from b93 :
` works
: works
0-9 probably work
$ works
Westwards edge jump arrives at 79
0! is 1
5! is 0

Edit history:
(970-64=906) : Reimplemented movement, using 2 instead of 4 variables
(906-9=897) : Moved more calculations into 1st and 2nd case-blocks
(897-11=886) : Skip intermediate variable for all double-pop instructions
(886-6=880) : Read 1 input line extra to clear 's'tack
(880-14=866) : Simplified '?' by changing it into one of the 4 direction-instructions
(866-8=858) : Removed one case block
(858-13=845) : Fixed edge-jump, simplifying direction handling. Use 8 bit stack.
(845-3=842) : Combined left-right direction instruction into a single expression

Here's the fpc version, ready to run online : http://ideone.com/Pg259 (I did have to add a Delphi-compatibility line, and because ideone.com doesn't support file-uploads, I changed ReadLn into using stdin.)


text:
Word guessing game
A program should take an input on stdin, and guess what a word might be. It should run as a session. One example session is shown below. Characters are fed to it, with a * for a letter not revealed; it should remember letters already revealed. It shows possible words in a list if the total number words found is less than 20, otherwise it shows the count of words.
I recommend /usr/share/dict/words on any Linux/Unix for the list of words, or your favourite word list on other platforms.
Example session (yours may vary):
>>> *****
6697 matches
>>> G****
312 matches
>>> *u***
Trying Gu***
35 matches
>>> Gu**s
Gus's
Guy's
guess
gulfs
gulls
gulps
gum's
gun's
gurus
gusts
gut's
guy's
12 matches
>>> **e**
Trying Gue*s
Is it "guess"?

I did this some years ago in JavaScript, except that it was not golfed and was a real Hangman player following the usual rules, including guessing only one letter at a time.

To remove bias due to path lengths, can we assume that the word list is in a file named 'w' in the working directory?

@peter That would be fine, but make it clear.

Bash (171)

#!/bin/bash
s=`cat /dev/stdin | sed 's/\*/\./g'`;o=`cat /usr/share/dict/words | grep -x $s`;w=`echo "$o" | wc -l`;if [ $w -lt '20' ]; then echo "$o";fi;echo "$w match(es)"

That cat /dev/stdin | looks very no-op to me.  Are you sure you need it?

Similarly, the cat /usr/share/dict/words | could probably just turn into an input redirection </usr/share/dict/words

@JB: This was my first entry, so there's probably room for improvement.

Perl, 170 chars
open W,'</usr/share/dict/words';@D=<W>;
while(<>){@W=split//,$w;$w&&s/\*/$W[$-[0]]/ge;y/*/./;$w=$_;
($r=@R=grep/^$w$/i,@D)<20&&map{print}@R;print$r." matches\n";$r<2&&last}

Added (not counted) newlines for clarity.

PHP, 302
<?system('stty -icanon');$i=0;$s=explode(PHP_EOL,file_get_contents('/usr/share/dict/words'));while(1){$q.=fread(STDIN,1);system('clear');$x=0;$a='';$i++;for($j=0;$j<count($s);$j++){if(!strncasecmp($q,$s[$j],$i)){$x++;$a.="\n$s[$j]";}}echo str_pad($q,20,'*');echo$x<=20?"\n$a":'';echo"\n$x matches\n";}


text:
All Possible Matching Lists
Implement a function that takes a list that consists of 0, 1 or 2, the list is called "pattern". Your job is to return all possible lists that match the pattern.

0 matches 0
1 matches 1
2 matches 0 and 1

Examples:
f([0, 1, 1]) == [[0, 1, 1]]
f([0, 2, 0, 2]) == [[0, 0, 0, 0], [0, 1, 0, 0], [0, 1, 0, 1], [0, 0, 0, 1]]
f([2, 1, 0]) == [[0, 1, 0], [1, 1, 0]]

Order does not matter, you can use a {set} data structure instead.
You cannot use regular expressions or other string pattern matching mechanisms. You cannot use a brute-force search.
Shortest solution wins.

How do you define a brute force search?

Haskell, 49 characters
f[]=[[]]
f(2:r)=f(0:r)++f(1:r)
f(x:r)=map(x:)$f r

Interestingly this is exactly what I'd write even if this wasn't golf - except for removing spaces and calling the list's tail r rather than xs.

Haskell, 34 26 characters
Saved 8 characters thanks to Zgarb.
r 2=[0,1]
r n=[n]
f=mapM r

sequence.map is equivalent to mapM, which is 8 characters shorter.

Prolog, 62 characters
f([],[]). f([H|T],[A|B]):-((H=2,(A=0;A=1));(H<2,A=H)),f(T,B).

Example:
?- f([0,2,0,2],X).
X = [0, 0, 0, 0] ;
X = [0, 0, 0, 1] ;
X = [0, 1, 0, 0] ;
X = [0, 1, 0, 1] ;

Welcome to the site! :)

Mathematica, 30 chars
f=Tuples[{#}&/@#/.{2}->{0,1}]&

Examples:
f[{0, 1, 1}]

{{0, 1, 1}}

f[{0, 2, 0, 2}]

{{0, 0, 0, 0}, {0, 0, 0, 1}, {0, 1, 0, 0}, {0, 1, 0, 1}}

f[{2, 1, 0}]

{{0, 1, 0}, {1, 1, 0}}

Since the OP isn't asking for a named function you can even drop the f=.

Ruby - 76 characters
def f l;l==l-[2]?[l]:((j=l.dup)[k=l.index(2)]=0;(i=l.dup)[k]=1;f(j)+f(i))end

Testing script:
require_relative 'golf-lists'

[
  [0, 1, 1],
  [0, 2, 0, 2],
  [2, 1, 0]
].each do |list|
  puts "f([#{list.join(', ')}]) == #{f(list)}"
end

Result:
f([0, 1, 1]) == [[0, 1, 1]]
f([0, 2, 0, 2]) == [[0, 0, 0, 0], [0, 0, 0, 1], [0, 1, 0, 0], [0, 1, 0, 1]]
f([2, 1, 0]) == [[0, 1, 0], [1, 1, 0]]

Scheme (149) (148)
(define(f l)(if(null? l)'(())(let((t(f(cdr l)))(n(car l)))(if(< n 2)(map(lambda(m)`(,n,@m))t)`(,@(map(lambda(m)`(0,@m))t),@(map(lambda(m)`(1,@m))t]

With whitespace (the closing square brace closes all open parentheses on certain Scheme implementations; 154 chars without it):
(define (f l)
  (if (null? l)
      '(())
      (let ((t (f (cdr l)))(n(car l)))
        (if (< n 2)
            (map (lambda (m) `(,n ,@m)) t)
            `(,@(map (lambda (m) `(0 ,@m)) t)
              ,@(map (lambda (m) `(1 ,@m)) t]

CJam, 18 bytes
CJam is much younger than this challenge, so this is answer is not eligible for being accepted.
]]l~{2b\f{\f+~}}/p

Reads input from STDIN as a CJam style array.
Test it here.
Explanation
]]l~{2b\f{\f+~}}/p
]]                 "Push a nested empty array [[]] onto the stack. This is the base case.";
  l~               "Read and eval the input.";
    {          }/  "For each integer in the input.";
     2b            "Convert to base 2. This turns 0 into [0], 1 into [1] and 2 into [1 0].";
       \f{    }    "Swap with the current result and map this block onto the base-2 representation
                    copying in the current list of lists on each iteration.";
          \f+      "Swap the list of lists with the 0 or 1 and add the number to each list.";
             ~     "Unwrap the list of lists. They'll be regrouped by the surrounding f{...}.";
                 p "Pretty-print the result.";

Python 2, 156 bytes
def f(l):R,L=range(len(l)),[];exec"\n".join(" "*j+"for v%d in[[l[%d]],[0,1]][l[%d]>1]:"%(j,j,j)for j in R)+"L+=["+"".join("v%d,"%j for j in R)+"],";return L

Try it online!

J, 19 bytes
[:>@,[:{{&(0;1;0 1)

Try it online!
I had originally created a much longer version using amend and binary numbers, but user b_jonas suggested the above approach in IRC to me.
It essentially converts 0 and 1 to themselves, and 2 to the list 0 1, and the just cross products everything using catalog {.  Since catalog requires boxed data, and returns structured data, everything is (un)raveled and unboxed at the end: >@,.


text:
Work out change
You are writing a program for an automatic cash register. The user needs change with the least number of coins used. Write a program which takes an amount (say $1.53) and gives change in US denominations - in this instance: 1 x one dollar note, 1 x fifty cents and 3 x one cent. The shortest program shall be the winner. Bonus points for supporting other currencies (i.e. UK denominations) and unusual currencies (1, 2, 3 cents?)
You have these US denominations: 1 cent, 5 cents, 10 cents, 25 cents, 50 cents, 1 dollar (note or coin), 2 dollars, 5 dollars, 10 dollars.
You have these UK denominations: 1 pence, 2 pence, 5 pence, 10 pence, 20 pence, 50 pence, £1, £2, £5 (note or coin), £10.

This probably needs a little bit of clarification. Firstly you should probably specify we want the least number of coins (which makes the bonus question slightly more interesting, e.g. {1c,49c,50c} and 98c breaks a naive algorithm). Secondly, an input/output format is useful. Specifics of handling unobtainable values (for made-up currencies) would help. Lastly -- you might want to list the denominations here so people won't need to look it up if they're unfamiliar with it.

How do bonus points work? Just if there is a tie for the shortest program?

@gnibber, quoting Stephen Fry: "[points are] impartially determined by a demographically-selected customer service focus consultancy, broken down by age and sex – i.e. me."

I am going to ask for 50c as i have not seen a 50 cent coin yet. But aparently they exist: http://www.usmint.gov/kids/coinnews/circulating/50centCoin.cfm

Windows PowerShell, 108 111 117
Very first attempt, ungolfed so far:
$i=+("$input"-replace'[^\d.]')
$args|%{0d+$_}|sort -des|%{$a=[math]::floor($i/$_)
if($a){$i-=$a*$_
"$a×$_"}}

Implementation notes:

Accepts the quantity to return via the pipeline
Accepts the list of currency denominations via the command-line
The quantity can be given with a currency sign; that will be stripped (in fact, anything non-numeric).
The list of denominations does not need to be sorted.
The program will output the largest change smaller than the requested quantity achievable with the given denominations, i.e. 1.5 for 1.53 if the 1-cent coin is missing.

If 3 and 4 do not need to be satisfied (i.e. I control the input format ;-)), then the following program suffices (71):
$i=+"$input"
$args|%{$a=[math]::floor($i/$_)
if($a){$i-=$a*$_
"$a×$_"}}

Mathematica: 110 chars
Sort[IntegerPartitions[Rationalize@#,Infinity,{10,5,2,1,1/2,1/4,1/10,5/100,1/100}],
    Length@#1<Length@#2&][[1]]&

Usage
%[0.98]
{1/100, 1/100, 1/100, 1/10, 1/10, 1/4, 1/2}

Or
Tally@Sort[IntegerPartitions[Rationalize@#,Infinity,
                             {10,5,2,1,1/2,1/4,1/10,5/100,1/100}],
     Length@#1<Length@#2&][[1]]&

(6 chars more) gives
{{1/100, 3}, {1/10, 2}, {1/4, 1}, {1/2, 1}}

For other denominations, just change the rationals table {10,....,5/100,1/100}

D: 225 Characters
import std.algorithm,std.conv,std.stdio;void main(string[]args){auto m=args[1].findSplit(".");void p(T,S)(T t,T u,S s){foreach(v;[u,10,5,1]){writefln("%s %s%s",t/v,v,s);t-=(t/v)*v;}}p(to!int(m[0]),20,"");p(to!int(m[2]),25,"/100");}

More Legibly:
import std.algorithm,std.conv,std.stdio;

void main(string[] a)
{
    auto m = a[1].findSplit(".");

    void p(T, S)(T t, T u, S s)
    {
        foreach(v; [u, 10, 5, 1])
        {
            writefln("%s %s%s", t / v, v, s);
            t -= (t / v) * v;
        }
    }

    p(to!int(m[0]), 20, "");
    p(to!int(m[2]), 25, "/100");
}

Only handles US currency. Takes the value as a floating point value on the command line (must have the leading 0 for values under 1 dollar). Does not accept $ as part of value. Outputs the number of each type of bill/coin on a separate line.
E.g. an input of 1.53 results in:
0 20
0 10
0 5
1 1
2 25/100
0 10/100
0 5/100
3 1/100

Mathematica, 51 bytes
#~NumberDecompose~{10,5,2,1,.5,.25,.1,.05,.01}&

input

[1.53]

output

{0, 0, 0, 1, 1, 0, 0, 0, 3.}

Mathematica, 82 bytes --WITH BONUS--
(s=#~NumberDecompose~#2;Row@Flatten@Table[Table[#2[[i]]"+",s[[i]]],{i,Length@s}])&

Input

[37.6, {15, 7, 2.5, 1, 0.88, 0.2, 0.01}]

output

15 +15 +7 +0.2 +0.2 +0.2 +

Umm, this question uses different denominations from the duplicate.

OP doesn't specify input/output format.

This question doesn't use 100 dollar bills and there's no bonus.

ok.fixed and saved some bytes! As for the bonus, I am kindly requesting you to read the question again. Especially the part .."Bonus points for supporting other currencies"

Whoops, I guess I didn't see that then!

Javascript, 84 83 bytes

(n,v=[10,5,2,1,.5,.25,.1,.05,.01],l=[])=>{for(i in v)l[i]=n/v[i]|0,n%=v[i];return l}

(n,v=[10,5,2,1,.5,.25,.1,.05,.01],l=[])=>eval("for(i in v)l[i]=n/v[i]|0,n%=v[i];l")

Uses a greedy algorithm.

APL (Dyalog), 19 bytes
Prompts for desired amount and then for denominations expressed in smallest unit (pennies/cents).
⎕CY'dfns'
⎕ stamps⎕

Try it online!
⎕CY'dfns' Copy the dfns workspace
⎕ stamps⎕ ask for inputs and use as arguments to the stamps function


text:
Multiply without multiply
Write the fastest (best big-O) and smallest multiplication algorithm for positive integers, without using multiplication operators. You are only allowed addition, subtraction, logical functions (AND, OR, XOR, NOT), bit shift, bit rotate, bit flip/set/clear and bit test. Your program should be capable of multiplying 16-bit numbers to produce a 32-bit result. Take input on stdin, separated by commas, spaces or new lines (your choice), but make it clear how to input the data.
Example input/output:
734 929
681886

What about the division operator?

Is this codegolf or a challenge? :-\

@st0le you are only allowed the ops I name.

@st0le It is a combination of both - a challenge to figure it out, as well as the smallest being considered best.

@Thomas, You should specify if negative numbers are also to be handled...i don't think anyone is handling it at the moment.

@st0le from the question: "smallest multiplication algorithm for positive integers"

Fastest OR smalles - you can't have both, or you need a translation formular to calculate the trade off.

I marked for closing as "not a real question", since there still isn't given a solution, how to compare the fastest and the shortest code. Which is of priority? Or in what relation is the trade off? It could be healed if a some comparison algo in a portable lang was given - for example: if the std-algo reaches 500k operations in C, and your algo reaches 50k, you have to multiply the codelength *10. That way everybody could choose whether to shorten the code or to make it faster. The winner needn't be winner in both categories, but the winning criteria would be far more objective.

This question is insane as stated. The asymptotically fastest known multiplication algorithm for positive integers is Fürer's algorithm (http://en.wikipedia.org/wiki/F%C3%BCrer%27s_algorithm) and it's ridiculously complex and would take thousands of lines to implement in any language. I assume he actually just means your algorithm has to be O(n^2) (long multiplication).

C, 84 83 78 Characters
m;main(a,b){for(scanf("%d%d",&a,&b);a;b+=b)a&1?m+=b:0,a>>=1;printf("%d\n",m);}

In a more readable form
m;main(a,b)
{
    scanf("%d%d",&a,&b);
    while (a)
    {
        if (a&1)
           m+=b;
        a>>=1;
        b+=b;
    }
    printf("%d\n",m);
}

The algorithm is better known as the Ethiopian Multiplication or the Russian Peasant Multiplication.Here’s the algorithm :

Let the two numbers to be multiplied be a and b.
If a is zero then break and print the result.
If a is odd then add b to the result.
Half a, Double b. Goto Step 2.

not working without initializing m=0 (atleast for me)

@st0le It will work now, I have moved 'm' to begining in the main function. See here: http://www.ideone.com/XCz8C

Forgot about this one, here's a shorter one for(;(a&1&&m+=b)|a;a>>=1,b<<=1); Yes, i'm very ashamed. :)

for(m=0;(a&1&&m+=b)|a;a/=2,b*=2); why use shift,right?

@st0le It's written in the question not to use / and * operator.

@fR0DDY, true, doh!

@st0le for(;(a&1&&m+=b)|a;a>>=1,b<<=1); won't work I think.

@fR0DDY: You could say b+=b instead of b*=2 .  Of course, you'll still need the right shift.

Doesn't work - m is initialized to 1, not 0. This version fixes it, and saves 5 chars as well: m;main(a,b){for(scanf("%d%d",&a,&b);a;b+=b)a&1?m+=b:0,a>>=1;printf("%d\n",m);}

Also you might consider editing 'more readable form' :)

@Quixotic Probably the division operator is not allowed.

The division I don't know, but the b*=2 look suspiciously like a multiplication.

@fR0DDY very good answer with explanation.

APL (5)
Takes input on standard input separated by newlines.
+/⎕⍴⎕

Golfscript - 12 characteres
~0\{1$+}*\;

Please note that * here is not the multiplication operator, it's instead a repetition operator, see the second use here.

Golfscript - 27 chars
Peasants multiplication. There first * in there is a multiply, but only by 0 or 1
~2base-1%{1&\..+\@*}%{+}*\;

Here's on at 31 chars that doesn't multiply at all
~2base-1%{1&\..+\[0\]@=}%{+}*\;

Python, 64 chars
Probably not the most efficient though (or the most compliant, but I'm "adding", aren't I?):
a=int(raw_input())
print sum(a for i in range(int(raw_input())))

You could use input() in place of int(raw_input()) to save 18 characters.  You might consider this cheating, but print sum([input()]*input()) also works (* is being used for repetition, not multiplication).

r=input;a=r();print sum(map(lambda x:a,range(r()))) is much shorter

@JoelCornett r=input;a=r();r(sum(a for b in range(r()))) is even shorter (43 vs 51 bytes)

Ruby, 30
->(a){Array.new(*a).inject:+}

Based on GigaWat answer.

Golfscript - 43
~\:@;0 1{.3$&{\@+\}{}if@@+:@;.+.3$>!}do;\;

Implementation of the peasant multiplication. I think I may be able to golf it some more later on.

Python, also 64 chars
m=lambda x,n:0 if n==0 else x+m(x,n-1);print m(input(),input())

You could shorten it by assigning i=input and using i()

actually that works out to be exactly the same number of characters

could replace 0 if n==0 else with n and

J, 18 17 characters
+/({.${:)".1!:1]3

Input needs to be space separated.

A variation in Scala, optimized for size: 48 chars
def m(a:Int,b:Int):Int=if(b==1)a else a+m(a,b-1)

optimized for speed a bit:
def mul (a:Int, b:Int) : Int = {
  print (".")
  if (a == 1) b
  else if (a > b) mul (b, a)
  else if (a % 2 == 0) mul (a >> 1, b << 1)
  else b + mul (a - 1, b)
}

I swap (a, b) if (a > b), to reach the end more fast. The difference is 11 to 20 steps, when calling mul (1023,31), compared with omitting that line of code.
golfed: 95 chars:
def m(a:Int,b:Int):Int=if(a==1)b
else if(a>b)m(b,a)
else if(a%2==0)m(a>>1,b<<1)
else b+m(a-1,b)

Ruby, 35 bytes
def x(a)Array.new(*a).inject :+end

Usage: x([123, 456]) #=> 56088
Could probably be shortened if the numbers are read from ARGV, but it complains about them being the wrong format (strings, not ints).  Any suggestions would be great.

VBA, 70 chars
This is actually quite slow for large numbers, but it's small. I managed to improve the code size while improving speed. Calculation time varies, depending on argument position - not just size. (i.e. 1000, 5000 computes in about 4 seconds while 5000, 1000 calculates in about 19) Since the OP lists both fast and small, I figured I'd go with this one. Input is two numeric args, comma separated.
Sub i(j,k)
For m=1 To j:n=n & String(k," "):Next
MsgBox Len(n)
End Sub

This longer version (103 chars) will ensure it runs with the faster of the two possible arrangements:
Sub i(j,k)
If j<k Then a=j:b=k Else b=j:a=k
For m=1 To a:n=n & String(b," "):Next
MsgBox Len(n)
End Sub

You can loose quite a few bytes by removing whitespace before To and in concatenation, as well as by outputiing to the VBE immediate window via Debug.?

Perl: 52 chars
This is an old question, but Perl needs to be represented:
perl -pl '($m,$n,$_)=split;$_+=$m&1&&$n,$m>>=1,$n<<=1while$m'

(This is the binary algorithm; iterated addition is smaller but way too boring.)
This program includes an unintentional feature: if your input line contains a third number, the program will actually calculate A*B+C.

How fast is it?

It runs in O(log n), naturally. Are you asking about its actual speed? On my machine I measure roughly 2-3 times slower than Perl's builtin multiply, but I don't know how significant that is.

K, 18 16
{#,/(!y),\:/:!x}

.
k){#,/(!y),\:/:!x}[4;20]
80
k){#,/(!y),\:/:!x}[13;21]
273
k){#,/(!y),\:/:!x}[3;6]
18

Ruby, 35 chars
p $*.map!(&:to_i).pop*$*.inject(:+)
It's a program, which takes input and outputs, not just a function.
.-(~/virt)-----------------------------------------------------------------------------------------------------------------------------------------------------(ice@distantstar)-
`--> wc -c golf.rb
35 golf.rb
.-(~/virt)-----------------------------------------------------------------------------------------------------------------------------------------------------(ice@distantstar)-
`--> ruby ./golf.rb 734 929
681886

VB11, 101 Chars
   Dim m As Func(Of Integer, Integer, Integer, Integer) = Function(a, b, t) If(a = 0, t, m(a >> 1, b << 1, t + If(a Mod 2 = 1, b, 0)))

You used a few disallowed operations...

I don't think this uses disallowed operations (unless control flow is disallowed; the question is unclear on that, which is part of the reason it's on hold). "mod 2" is a bit test operation. I guess comparisons (==) aren't allowed by the question, but plenty of answers are using them.

Mathematica 12
The following sums #2 instances of #1.
Code
#1~Sum~{#2}&

Usage
#1~Sum~{#2} &[734, 929]

(* out *)

681886

9 chars?
If program parameters, a, b, may be used for input, the same result can be achieved with 9 chars.
a~Sum~{b}


text:
Find prime factors
A whole program to find the prime factors of a given number. The number will be given on standard input.

Should we make a function or a whole program? Any time constraints or limit to the input number?

given number? from STDIN I presume?

@dogbert yes, from STDIN

Output format? Space-separated, comma-separaed, each factor on a line? Sorted? With exponents?

space is fine for output, sorted wasn't specified and I wasn't thinking exponents would be used. just full number.

J - 2 characters
q:

Example:
   q: 31415
5 61 103

Bash Shell 6 Chars
factor
If rot13 can be allowed, i don't see why this one is an issue...I'm sorry but this is very trivial.

You could argue that this one is more permissible than rot13, as this one is part of coreutils which is completely standard, and rot13 is part of... bsdgames?

@Nabb: what? are you suggesting bsdgames is non-standard? I even have them on my DS (using DSLinux).

dc, 48 chars
[ldp0<x]sp?2sd[[dsrld~0=p]dsxxcld1+sdlrd1<y]dsyx

Ruby - 50 49 47 44 42 chars
2.upto(n=gets.to_i){|i|n/=p i while n%i<1}

the () for n=gets.to_i are superfluous...

@st0le, ah thanks, made the change.

In general, map is 1 character shorter than each. ;) But in this case, you can just use 2.upto(n=gets.to_i) to save 2 characters.

Crossed out 44 is still 44

Python: 58
n=input()
for i in range(2,n+1):
 while n%i<1:print i;n/=i

how about n%i<1?

Perl, 42 chars
map{$n/=$_,print$_,$/until$n%$_}2..($n=<>)

Using say instead of print$_ let you save 4 chars.

Windows PowerShell, 46
Naïve solution.
2..($x=+"$input")|%{for(;!($x%$_)){$_;$x/=$_}}

43 bytes: param($x)2..$x|%{for(;!($x%$_)){$_;$x/=$_}}

The number is given on standard input. Read the task first, please.

parm($x) is pure way to declare a standard input. Read the Powershell documentation first, please :)

Try it out for yourself: echo 35 | powershell -noprofile -command "param($x)2..$x|%{for(;!($x%$_)){$_;$x/=$_}}". param declares a parameter to a function/script/scriptblock which is given after the invocation, not as pipeline input. Standard input is a well-defined term and refers to one of the default streams available to console programs on many platforms.

You don't need to run a PowerShell script as command from cmd.exe. Save the text to a file (test.ps1, for example) and run it from Powershell PS> test.ps1 35 :)

To run a script text (not script file) with paramters you need to use a powershell call operator &. For example & {param($x)2..$x|%{for(;!($x%$_)){$_;$x/=$_}}} 35. If you insist on running a powershell scriptblock from cmd.exe then try powershell -noprofile -command "& {param($x)2..$x|%{for(;!($x%$_)){$_;$x/=$_}}} 35".

$input is one of several automatic variables. You do not have to use only it. There are other ways :)

@mazzy: The point is, that a command-line argument to the script/scriptblock/function is not standard input.

(oO) as you wish

Python (55)
based on marcog
n=input()
i=1
while~-n:
 i+=1
 while n%i<1:print i;n/=i

Pure Bash Solution (60 characters)
Based on F.Hauri's solution (thanks to him):
read p;for((i=2;p-1;));do((p%i++||(p/=--i)*0))||echo $i;done

*0 great idea!

Javascript (54)
n=prompt()*1;for(i=2;n>1;n/=n%i?(++i,1):(alert(i),i));

You can do prompt()*1 instead of parseInt(prompt()) to convert to an integer.

+prompt() is shorter.

C (68)
Not the shortest, but I was curious to see how a C solution could compare.
d=2;main(n){scanf("%d",&n);for(;n>1;)n%d?++d:printf("%d\n",d,n/=d);}

Nice. You can also take advantage of the fact that printf accepts a variable number of arguments to hide the n/=d in its argument list. I suspect you could also save a character or two by promoting d to a global variable.

Good ideas! That brings it to 68.

100% Pure bash: 72 chars
read p;for((i=1;p>i++;));do while((p%i<1));do echo $i;((p/=i));done;done

or
read p;i=1;while((p>i++));do while((p%i<1));do o+=$i\ ;((p/=i));done;done ;echo $o

This seem longer, but in replacing for by while, I could make an overall loop and using alias to reduce then code:
alias D=done W=while
prime() { W read p;do i=1 o=;W((p>i++));do W((p%i<1));do o+=$i\ ;((p/=i));D;D;echo $o;D;}
unalias D W

This way, my (written) code whith the loop is 77 char length.
Anyway, the function is memorized with full command names:
declare -f prime
prime ()
{
    while read p; do
        i=1 o=;
        while ((p>i++)); do
            while ((p%i<1)); do
                o+=$i\ ;
                ((p/=i));
            done;
        done;
        echo $o;
    done
}

Hi @F.Hauri :). Here's a shorter version: read p;for((i=2;p-1;));do((p%i==0&&(p/=i)))&&echo $i||((++i));done. Also, use declare -f prime instead of the ugly set | sed. Cheers :).

Even shorter: read p;for((i=2;p-1;));do((p%i&&++i))||{((p/=i));echo $i;};done (63 chars :)).

Hi @gniourf_gniourf, thanks for declare -f, sometime, re-reading man pages... Bravo for your shortest bash solution, if you publish I will upvote!

Mathematica, 26 chars
#&@@@FactorInteger@Input[]

R, 72 characters
Just for the kicks, an attempt without using any preexisting function to prime-factorize:
n=scan(n=1);m=1:n;M=m[!n%%m&!m%in%c(1,n)];M[rowSums(!outer(M,M,`%%`))<2]

Ungolfed with explanations:
n <- scan(n=1) #Take one number from stdin
m <- 1:n
#Of which of the integers from 1 to n is n a multiple (excluding 1 and himself):
M <- m[!n%%m & !m%in%c(1,n)]
#Trim that list by excluding integers that are multiples of others in the list:
M[rowSums(!outer(M,M,`%%`))<2]

NB: Instead of checking if n%%m==0, use the fact the 0 coerce as FALSE when using !.

Scala, 111 bytes:
def f(i:Int,c:Int=2):List[Int]=if(i==c)List(i)else
if(i%c==0)c::f(i/c,c)else f(i,c+1)
f(readInt).mkString(" ")

perl5.10:  36 chars
map{$p/=$_,say until$p%$_}2..($p=<>)

Haskell 74 chars
s n=f((==0).mod n)[2..n]
main=readLn>>=print.f((==1).length.s).s
f=filter

Example
12 -> [2,3]
128 -> [2]
60 -> [2,3,5]

Octave, 17 chars
factor(input(''))


text:
Decipher a Vigenère ciphertext
The Vigenère cipher was a simple polyalphabetic cipher that basically applied one of several Caesar ciphers, according to a key. Basically the letters in the key indicate which shifted alphabet to use. To that end there was a simple tool, called the Vigenère square:

Here each row is a separate alphabet, starting with the corresponding letter of the key. The columns then are used to determine the ciphered letter. Decryption works in very much the same fashion, only vice-versa.
Suppose we want to encrypt the string CODEGOLF. We also need a key. In this case the key shall be FOOBAR. When the key is shorter than the plaintext we extend it by repetition, therefore the actual key we use is FOOBARFO. We now look up the first letter of the key, which is F to find the alphabet. It starts, perhaps unsurprisingly, with F. Now we find the column with the first letter of the plaintext and the resulting letter is H. For the second letter we have O as the key letter and the plain text letter, resulting in C. Continuing that way we finally get HCRFGFQT.
Task
Your task now is to decipher messages, given a key. However, since we have outgrown the 16th century and have computers we should at least support a slightly larger alphabet:
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789

The construction of the Vigenère square is still very much the same and the cipher still works in the same way. It's just a bit ... unwieldy to give here in full.
Input
Input is given on standard input as two separate lines of text, each terminated by a line break. The first line contains the key while the second contains the ciphertext.
Output
A single line, containing the deciphered message.
Winning condition
Since encryption is sometimes regarded as a weapon, the code should be short to facilitate easy smuggling. The shorter the better, as it reduces the likelihood of discovery.
Sample input 1
Key
miQ2eEO

Sample output 1
Message

Sample input 2
ThisIsAKey
CoqKuGRUw29BiDTQmOpJFpBzlMMLiPb8alGruFbu

Sample output 2
ThisWorksEquallyWellWithNumbers123894576

A week has passed. The currently shortest solution has been accepted. For those interested, in our contest we had the following submissions and lengths:

130 – Python
146 – Haskell
195 – C
197 – C
267 – VB.NET

And our own solutions that weren't ranked with the others:

108 – Ruby
139 – PowerShell

It seems that this can be useful to print the Vigenère square.

Theoretically, using this cipher with a non-repeating key the same length as the message makes it completely and utterly unbreakable.

Golfscript -- 48 chars
n%~.,@*\{\(123,97>91,65>+58,48>+:|?@|?\-|=}%\0<+

No tricks in this one!

+1 I went to bed thinking there must be a way to get this down to ~50, now I see it's possible but I probably would not have managed it any time soon

MS-DOS 16bit .COM file - 87 bytes
Base64 encoded binary (following this link for a decoder)
v1cBi8/oQACJ/ovv6DkAi9msitAqF3MDgMI+gMJhgPp6dguA6jqA+lp2A4DqK80hO/d0IkM563TW69YsYXMIBCB9AgQrBBqqtAHNITwNdev+xLIKzSHD

Usually you write short source code yourself for golfing. While probably not impossible, I somehow doubt it with this.

@Joey: What, you've never hand encoded machine code instructions! Just what do they teach youngsters these days! ;-)

Skizz: I did. Not in Base64, though ;) (we had a class a few years ago where we had to write programs for a Siemens 80C167 in assembler – and in the exams also assemble them into machine code. I thought about digging out that knowledge for the Assembler Quine task, but we had no output facilities [at least, they varied]).

@Joey: The Base64 is just a convenience for the other users on this site, it's easy to decode and save as a binary file (the link in the answer has that option).

Aah, sorry. I thought you'd have given the length of the Base64. Well, Chris once included arbitrary characters into a solution and just gave a hexdump besides his answer. I did similar in Weather forecast.

APL (45)
∆[⍙⍳⍨¨⌽∘∆¨(⍴⍙←⍞)⍴1-⍨⍞⍳⍨∆←⎕D,⍨⎕A,⍨⎕UCS 96+⍳26]

Explanation:

∆←⎕D,⍨⎕A,⍨⎕UCS 96+⍳26: generate the alphabet (numbers (⎕D) follow letters (⎕A) follow lowercase letters (⎕UCS 96+⍳26, the unicode values from 97 to 122).
1-⍨⍞⍳⍨∆: read a line (the key), find the position of each character in the alphabet, and subtract one (arrays are one-based by default, so shifting by those values directly would shift the alphabet one too far).
(⍴⍙←⍞)⍴: read another line (the message), and repeat the indices of the key so that it has the length of the message.
⌽∘∆¨: rotate the alphabet by the indices belonging to the key
⍙⍳⍨¨: look up each character in the message in the corresponding shifted alphabet
∆[...]: look up the given indices in the normal alphabet, giving the corresponding characters.

Ruby - 132 127 122 109 100 characters
a,b=*$<
c=*?a..?z,*?A..?Z,*?0..?9
(b.size-1).times{|i|$><<c[c.index(b[i])-c.index(a[i%(a.size-1)])]}

Use *$< instead of $<.to_a and inline the lambda to save another few bytes. – Ventero 5 mins ago

Thanks @Joey, I pulled that lambda out to save characters and somehow missed that it actually cost more.

Python - 122 chars
from string import*
L=letters+digits
R=raw_input
K,T=R(),R()
F=L.find
print"".join(L[F(i)-F(j)]for i,j in zip(T,K*len(T)))

J, 65 characters
v=:4 : 'a{~x(62|[:-/"1 a i.[,.#@[$])y[a=.a.{~62{.;97 65 48+/i.26'

Doesn't completely meet the spec since it's defined as a verb rather than taking input, but I'm posting it anyway with the intention of fiddling with it at a later date.
Usage:
   'miQ2eEO' v 'Key'
Message
   'CoqKuGRUw29BiDTQmOpJFpBzlMMLiPb8alGruFbu' v 'ThisIsAKey'
ThisWorksEquallyWellWithNumbers123894576

Perl, 95 chars
Perl 5.010, run with perl -E:
%a=map{$_,$n++}@a=(a..z,A..Z,0..9);@k=<>=~/./g;
$_=<>;s/./$a[($a{$&}-$a{$k[$i++%@k]})%62]/ge;say

Golfscript - 65 chars
Still needs to be golfed more. For now, T is the text, K is the Key, L is the list of letters
n%):T,\~*:K;''26,{97+}%+.{32^}%10,{48+}%++:L;T{L\?K(L\?\:K;-L\=}%

Python - 144 143 140 136 125 characters
Probably not the best, but hey:
from string import*
l=letters+digits
r=l.find
q=raw_input
k=q()
print"".join(l[(r(j)-r(k[i%len(k)]))%62]for i,j in enumerate(q()))

Huh, I was about to post something just like that. You can assign raw_input to a variable, 3 or so chars.

K,81 61
k:0:0;,/$(m!+(`$'m)!+{(1_x),1#x}\m:,/.Q`a`A`n)[(#v)#k]?'v:0:0

.
k)k:0:0;,/$(m!+(`$'m)!+{(1_x),1#x}\m:,/.Q`a`A`n)[(#v)#k]?'v:0:0
ThisIsAKey
CoqKuGRUw29BiDTQmOpJFpBzlMMLiPb8alGruFbu
"ThisWorksEquallyWellWithNumbers123894576"

Perl, 115 chars
$a=join'',@A=(a..z,A..Z,0..9);$_=<>;chop;@K=split//;$_=<>;s/./$A[(index($a,$&)-index($a,$K[$-[0]%@K]))%@A]/ge;print

Golfscript - 92 characters
n%~\.,:l;{0\{1$+\)\}%\;}:&;26'a'*&26'A'*&+10'0'*&+\@.,,{.l%3$=4$?\2$=4$?\- 62%3$\>1<}%\;\;\;

Probably much longer than it needs to be. Still trying to get my head around GS.
Heres the "ungolfed" and commented version
n%~\.,:l;
{0\{1$+\)\}%\;}:&; # This would be sortof an equivalent for range applied to strings
26'a'*&26'A'*&+10'0'*&+\@., # This mess generates the dictionary string,
# l = len(key)
# 0 dictionary (letters + digits)
# 1 key
# 2 text
{
    # 3 index
    .   #+1 Duplicate the index

    # Find the index of the key letter
    l%  #+1 Indice modulo key
    3$  #+2 Duplicate the key
    =   #+1 Get the key letter
    4$? #+1 Search the letters index

    # Find the index of the text letter
    \   #+1 Get the index
    2$  #+2 Get the text
    =   #+1 Get the text letter
    4$? #+0 Search the letters index

    # 3 key index
    # 4 letter index

    \-   #+1 get the index of the new letter

    62% #+1 wrap the index around the dictionary

    3$ #+2 Get the dictionary

    \> #+1 remove the first part of the dict around the target letter

    1< #+1 remove everythin after
}%
\;
\;
\;

VBA, 288
Doesn't quite beat the listed VB.NET score (but I'm getting close):
Sub h(k,s)
v=Chr(0)
Z=Split(StrConv("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789",64),v)
a=Split(StrConv(s,64),v):b=Split(StrConv(k,64),v)
For l=0 To Len(s)-1
j=l Mod Len(k)
g=0
For i=0 To 62:g=g+i*((Z(i)=b(j))-(Z(i)=a(l))):Next
x=x &Z(IIf(g<0,g+62,g))
Next
s=x
End Sub

Usage:
Sub test()
k = "ThisIsAKey"
s = "CoqKuGRUw29BiDTQmOpJFpBzlMMLiPb8alGruFbu"
h k, s
MsgBox s
End Sub

Thanks to Joey for the tip!

g=g+IIf(Z(i)=c,i,0)-IIf(Z(i)=d,i,0) would be one candidate I can spot. As well as trying out whether LF line endings are understood by VBA. At least one space in x=x & Z(g) could be left out too, I guess.

Another way of writing the line: g=g+i*((Z(i)=d)-(Z(i)=c))  (because True is −1 in VB). Could be that it works.

Thanks for the feedback, @Joey. I'll look for any other improvements and add that in.

C,186
A bit late but .. (lines broken to avoid horizontal scrollbar).
char a[99],*s,*t;k,j;main(int m,char**v)
{for(;j<26;++j)a[j]=32|(a[j+26]=65+j),
a[52+j]=48+j;while(*v[2])
putchar(a[s=strchr(a,v[1][k++%strlen(v[1])])
,t=strchr(a,*v[2]++),s>t?t-s+62:t-s]);}

Nonbroken lines
char a[99],*s,*t;k,j;main(int m,char**v){for(;j<26;++j)a[j]=32|(a[j+26]=65+j),a[52+j]=48+j;while(*v[2])putchar(a[s=strchr(a,v[1][k++%strlen(v[1])]),t=strchr(a,*v[2]++),s>t?t-s+62:t-s]);}

A discussion about the process of golfing this code can be found here:
http://prob-slv.blogspot.com/2013/04/code-golf.html

JavaScript 248
var v= 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'
function d(k,c){var a,b,o,x
a=k.charAt(0)
x=v.indexOf(a)
b=v.substr(x)+v.substring(0,x)
o= v.charAt(b.indexOf(c.charAt(0)))
k=k.substr(1)+a
c=c.substr(1)
return (c)?o+d(k,c):o}

Uiua, 42 characters
A←⊂/⊂⊞+"aA"⇡26+@0⇡10
&p⊏-∩(⊗∶A)↯△,∶&sc&scA

-4 thanks to Unrelated String

You can get rid of the ◿⧻A since negative indices wrap around anyways, and turn the leftmost :A into just an A on the far right, since being forced to take STDIN has the mild upside that your input doesn't have to start on the bottom of the stack.

Thanks, that's useful to know

Haskell (169)
import List
main=do c<-y;t<-y;putStrLn$map((k!!).(`mod`62))$zipWith(-)(g t)(cycle$g c)
k=['a'..'z']++['A'..'Z']++['0'..'9']
y=getLine
f(Just x)=x
g=map$f.(`elemIndex`k)

J: 91 characters
[:{&{.&t({&t"0&(({.t=.1|.^:(i.62)a.{~(97+i.26),(65+i.26),48+i.10)&i.)"0@:$~#)|:@(i."1.,"0)]

For example:
    g=:[:{&{.&t({&t"0&(({.t=.1|.^:(i.62)a.{~(97+i.26),(65+i.26),48+i.10)&i.)"0@:$~#)|:@(i."1.,"0)]
    'ThisIsAKey' g 'CoqKuGRUw29BiDTQmOpJFpBzlMMLiPb8alGruFbu'
ThisWorksEquallyWellWithNumbers123894576

Scala, 156 bytes
Golfed version. Try it online!
(K,T)=>{val L=('a'to'z')++('A'to'Z')++('0'to'9');T.zip(Stream.continually(K).flatten).map{case(i,j)=>L((L.indexOf(i)-L.indexOf(j)+L.size)%L.size)}.mkString}

Ungolfed version. Try it online!
object Main extends App {
  def transform(K: String, T: String): String = {
    val letters = ('a' to 'z') ++ ('A' to 'Z')
    val digits = '0' to '9'
    val L = letters ++ digits
    (T.zip(Stream.continually(K).flatten))
      .map { case (i, j) =>
        L((L.indexOf(i) - L.indexOf(j) + L.length) % L.length)
      }
      .mkString
  }

  val K = "Key"
  val T = "miQ2eEO"
  val result = transform(K, T)
  println(result)
}

Vyxal s, 136 bitsv2, 17 bytes
LẎZƛ÷kr₀Ǔ:£~ḟǓ∇_ḟ¥i

Try it Online!
Bitstring:
0110000111010001100100100100100010010101101010000010110100010111011110111110110000101100000011001010100000111000011100111110110100111001

Takes message then key
Explained
LẎZƛ÷kr₀Ǔ:£~ḟǓ∇_ḟ¥i
LẎ                   # Repeat the key to the length of the message
  Z                  # Zip each character in the message to the extended key
   ƛ                 # To each pair:
     kr₀Ǔ            #   Push the string a-zA-Z0-9
         :£          #   and store a copy in the register
    ÷      ~ḟ        #   Find the position of the key character, not popping the alphabet string
             Ǔ       #   Rotate the alphabet string left that many times
    ÷         ∇_     #   Put the message character at the top of the stack, followed by the rotated alphabet
                ḟ    #   Find the index of the message character in that alphabet
                 ¥i  #   And index into the original alphabet string

Created with the help of Luminespire.

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


text:
How much snow did you get?
My apologies for the wordiness. We had fun with it at work in our internal golfing, but it required a few emails for clarification, so I hope I captured most of that the first time.
PROBLEM
Given a “simulated” snowfall snapshot (as a string, stdin or parameter to your function/method), report on 4 values: minimum depth, maximum depth, average depth, and duration.
Here’s a formatted example to illustrate the input:
* * **
** * ***
** *  *
*
--------

The ‘*’ is a snowflake and the ‘-‘ is the ground. Imagine all of those “snowflakes” falling toward the ground. This is the final “snapshot”:
*
*
** * **
********
--------

You need to report on:

Minimum depth - count the shortest “pile” (1, in example above)
Maximum depth - count the tallest “pile” (4, in example above)
Average depth - average count of all “piles” (1.9, in example above - rounding to tenths)
Duration - (each “fall” = 1 second) - time from the first snapshot to the last snapshot (3 seconds, in example above)

Another example for reference:
     *
   *   *
      *
*
--------

Final snapshot:
*  * ***
--------

INPUT
The starting “snapshot” will have 8 “rows”, 8 “columns”, and be pipe-delimited (the pipes separate the rows). For example (excluding quotes):
“        |        |        |        |     *  |   *   *|      * |*       |--------”

OUTPUT
The 4 values pipe-delimited on a single line: 0|1|.6|3 or 0|5|1|1

Can the ground have varying heights?

@Nemo157 - that wasn't in our original problem, so for the purposes here, no. That'd be an interesting variation to the problem.

Do you require rounding the average?

Perl, 128 chars
map{$d++;s/\*/$d{$-[0]}++;$t&&$t<$d or$t=$d/ge}split'\|',<>;map{$A+=$_/8}@m=sort values%d;printf"$m[0]|$m[-1]|%.1f|%d\n",$A,8-$t

Python, 153 characters
s=raw_input()
R=range(8)
C=[s[i::9].count('*')for i in R]
print"%d|%d|%.1f|%d"%(min(C),max(C),sum(C)/8.,max(8-s[i::9].find('*')-C[i]for i in R if C[i]))

Windows PowerShell, 180 189
$a=(0..7|%{$x=$_;-join(0..7|%{$s[$_*9+$x]})})
$b=$a-replace' '|%{$_.length}|sort
"{0}|{1}|{2:.0}|{3}"-f($b[-1..0]+(($b-join'+'|iex)/8),($a|%{($_-replace'^ +|\*').length}|sort)[-1])

Input comes in as $s.
History:

2011-02-10 01:53 (189) – First attempt.
2011-02-10 02:03 (180) – Format string to the rescue. Only downside: It outputs numbers in regional format, no longer strictly conforming to the task specification. Still, that's a problem shared by the C# solution as well so I guess that's ok.

A couple other language results from our internal golfing:
C#, 188 characters (easily readable)
int a = 0, b = 8, c = 0, d = 0, f, i, j, x;
for (i = 0; i < 8; i++)
{
      f = x = 0;
      for (j = 0; j < 8; )
            if (s[i + j++ * 9] == '*')
            {
                  x = x > 0 ? x : 9 - j;
                  f++;
            }

      d += f;
      a = f > a ? f : a;
      b = f < b ? f : b;
      c = x - f > c ? x - f : c;
}

Console.Write("{0}|{1}|{2:.0}|{3}", b, a, d / 8f, c);

Ruby, 173 characters
s=gets;n=8;a=o=l=0;8.times{|i|f=x=0;8.times{|j|if(s[i+j*9].chr=='*'):x=8-j if x==0;f+=1;end}
o+=f;a=f if f>a;n=f if f<n;l=x-f if x-f>l}
printf "%d|%d|%.1f|%d",n,a,o.to_f/8,l

PHP, 139 bytes
<?for(;$y<8;$y++)for($x=0;++$n[$x],$x<8;$x++)'!'>$argv[1][$y*9+$x]&&--$n[$x]?$b[$x]++:0;print_r([min($n),max($n),array_sum($n)/8,max($b)]);

for each column, count no. of snowflakes and no. of spaces below the first snowflake, then calculate
takes string as argument from command line
breakdown and golfing steps
$i=$argv[1];
for(;$y<8;$y++)         # $y=row
{
    for($x=0;$x<8;$x++) # $x=column
    {
        // loop body: 32+26=58 bytes
        if('*'==$i[$p=$y*9+$x])$n[$x]++;# if snowflake: increase snowflakes count
        elseif($n[$x]+=0)$b[$x]++;      # elseif has snowflakes: increase blanks count
                                        # +=0: min needs a value in every column

        // -> golf if/elseif to ternaries, 16+9+25+1 = 51 (-7)
#       '*'==$i[$y*9+$x]
#           ? $n[$x]++
#           : (($n[$x]+=0)?$b[$x]++:0)
#       ;

        // golfing on the ternary, 15+23+9+1 = 48 (-3)
#       '!'>$i[$y*9+$x]                 # -1: char<'!' <=> char==' '
#           ? ($n[$x]+=0)?$b[$x]++:0    # -2: inverted condition -> eliminated parens
#           : $n[$x]++
#       ; # 15+23+9+1-2=46

        // increase snowflakes count in any case (initialization)
        // (needs curlies; elminate them by moving increase to the for condition)
        // decrease snowflakes count for blank
#       ++$n[$x];if('!'>$i[$y*9+$x]&&--$n[$x])$b[$x]++; # if: 47
#       ++$n[$x];'!'>$i[$y*9+$x]&&--$n[$x]?$b[$x]++:0;  # ternary: 46
    }
}
print_r([min($n),max($n),array_sum($n)/8,max($b)]); # calculate and print results

add round(...,1) around array_sum($n)/8 for rounding (+9)

Mathematica, ~115
"        \n        \n* * **  \n        \n** * ***\n** *  * \n*       \n--------"

Most/@ToCharacterCode@%~Partition~9/10-16/5
Min@#|Max@#|Mean@#~Round~.1|Position[#,1][[{-1,1},1]].{1,-1}-1&@Total@%

1 | 4 | 1.9 | 4

In this post I had to resort to the escaped string form \n as paste and copy loses spaces.  In the Front End I can enter it like this:

JavaScript, 328 Bytes
Not particularly short, but it's what I've got.
var input = "        |        |        |* * **  |        |** * ***|** *  * |*       |--------";

(s=>{var l=s.split("|"),a=[0,0,0,0,0,0,0,0],o=[8,0,0,0],b;for(i=0;i<l.length;i++){if(!b&&l[i]!="        ")o[3]=7-i,b=1;for(j=0;j<l[i].length;j++){a[j]+=l[i][j]=="*"?1:0}}for(i=0;i<a.length;i++){if(a[i]<o[0])o[0]=a[i];if(a[i]>o[1])o[1]=a[i];o[2]+=a[i];}console.log(o[0]+"|"+o[1]+"|"+(o[2]/a.length).toFixed(1)+"|"+o[3]);})(input)

De-golfed:
var input = "        |        |        |        |     *  |   *   *|      * |*       |--------";

(s=>{
  var splits = s.split("|");
  var arr = [0,0,0,0,0,0,0,0];
  var b;
  var o=[8,0,0,0];
  for (var i = 0; i < splits.length; i++) {
    if (!b&&splits[i]!="        ") {
      o[3] = 7-i;b=1;
    }
    for (var j = 0; j < splits[i].length; j++) {
      arr[j]+=splits[i][j]=="*"?1:0;
    }
  }
  for (var i = 0; i < arr.length; i++) {
    if (arr[i]<o[0]) {
      o[0]=arr[i];
    }
    if (arr[i]>o[1]) {
      o[1]=arr[i];
    }
    o[2]+=arr[i];
  }
  console.log(o[0]+"|"+o[1]+"|"+(o[2]/arr.length).toFixed(1)+"|"+o[3]);
})(input)