text:
Weird string calculation
String is given in form of a variable. Let's call that variable s. It is known that the string looks like a calculation expression using +, -, *, /. There's no parentheses.
Calculate the expression inside the string and store the result in variable r (you can assume it's already declared). All the divisions can be performed without remainders (4-6*3/8 is invalid because 8 is not divisible by 3). Length of string is not limited. String can't contain 0.
Challenge is not supposed to give advantage for some languages, so I decided to change some math rules:
Operators precedence is a little bit different than it is in math and programming language expressions: multiplication/division is still higher than addition/substraction. However, if there're some multiplications/divisions in a row, it is performed right-to-left. Addition/substraction is preformed left-to-right.
Sample s and r:
2+5-6/9*8+7 -> 2
1/3*6-6 -> 12
The shortest code (in bytes) wins.

You know, you can also just say don't use any eval equivalents.

Nice point. But new math rules sound like more fun ;)

You're also not really supposed to change the question after you post it, because you could invalidate previously posted answers. In this case it doesn't matter, but to iron out any mistakes/gotchas, you can post your question in the sandbox (on meta) first to discuss it.

Yeah, I know. I was thinking not much people viewed the question text at that point, so I could change it a little bit. "In runtime." Sorry.

@gthacoder Only me and marinus :) I've added on a solution that meets all the new requirements.

"(4-6*3/8 is invalid because 8 is not divisible by 3)" makes no sense: if you said that it's invalid because 18 is not divisible by 8 then I could understand it. But your examples go on to use divisions which you've defined as invalid. What you say about operator precedence also makes no sense, because you say you've made it a little different from programming language expressions and then define it to behave in the standard way.

@PeterTaylor What he means is, if you read division and multiplication from right to left, operator order and the dividend/divisor are reversed, so with his rules 3/9 equals 3.

You may want to add an example that uses negative numbers as they can be easy to overlook or mistreat as minus operators. Example: -5+2/-8 should equal -9.

Perl 5, 27 20

s/(.)\//1\/$1*/g;print eval

Edit:
s/\//**-1*/g;$r=eval

Assuming the input of:

$_ = "2+5-6/9*8+7";
  > $r = 2

and

$_ = "1/3*6-6";
  > $r = 12

This regex is based in the mathematical theory of @ybeltukov, I'm new to regex so it probably could be much better.

Mathematica (41)
s = "2+5-6/9*8+7";
ToExpression@StringReplace[s,"/"->"^-1 "]

2

Correct me if I'm wrong

Ruby, 24
 r=eval s.gsub ?/,'**-1*'

Thank you to @ybeltukov for the Mathematica technique. I thought there might be a substitution that could be used to leverage eval and yours was much simpler than the crazy regexes I was trying!
This shortcut effectively changes the operator precedence in s to what the question requires. It has the side effect of sometimes resulting in a Rational object type (e.g. 2/1 == 2). The results are correct for the cases I've tried.

JavaScript (213 characters compacted, 133 if I'm willing to sacrifice my soul)
For clarity, this is the code before I compacted it down (JS-Fiddle of it):
function math(match, leftDigit, operator, rightDigit, offset, string) {
    var L = parseInt(leftDigit)
    var R = parseInt(rightDigit)
    switch (operator)
    {
        case '*': return R*L;
        case '\/': return R/L;
        case '+': return L+R;
        case '-': return L-R;
    }
};

multAndDivRegex = /(\-?\d+)([\*\/])(\-?\d+)(?=[^\*\/]*$)/; //Right to left
addAndSubRegex = /(\-?\d+)([\+\-])(\-?\d+)/; // Left to right

while(multAndDivRegex.test(str)) {
    str = str.replace(multAndDivRegex, math);
}

while(addAndSubRegex.test(str)) {
    str = str.replace(addAndSubRegex, math);
}

Here it is compacted down to 213 characters (containing some extra help from Toni Almeida) (JS-Fiddle of it):
function m(x,l,o,r){
    L=~~l;R=~~r;
    return o=='*'?R*L:o=='/'?R/L:o=='+'?L+R:L-R
}

for(M=/(\-?\d+)([\*\/])(\-?\d+)(?=[^\*\/]*$)/;M.test(s);s=s.replace(M,m));
for(A=/(\-?\d+)([\+\-])(\-?\d+)/;A.test(r=s);s=s.replace(A,m));

Since I'm ending lines with semi-colons, all removable whitespace was ignored for character counting, but left in for clarity.
I can get it down to 133 characters if I use eval(), but that's not how I roll... (JS-Fiddle)
function m(x,l,o,r){return o=='*'?~~r*~~l:~~r/~~l}for(M=/(\-?\d+)([\*\/])(\-?\d+)(?=[^\*\/]*$)/;M.test(s);s=s.replace(M,m));r=eval(s)

This solution would mean that people can enter ANY JavaScript code they want! The 303 character version does not execute any JavaScript; it only does math.

May I say, I loved this challenge! :D

Well done! Here is a compacted version of your huge switch statment: o=='*'?R*L:o=='\/'?R/L:o=='+'?L+R:o=='-'?L-R:0

By the way, you can save 4 characters by removing { and } from you while's, as they have only 1 instruction, they are useless.

Here is, 257 char version: http://jsfiddle.net/promatik/5W3nQ/2/

@ToniAlmeida Magnificent! Thanks. I trimmed off a few more characters in addition to that after re-reading the rules about allowing the use of s and r instead of input/output functions: http://jsfiddle.net/IQAndreas/5W3nQ/3/

Python 3, 35
r=int(eval(s.replace("/","**-1*")))

Python 3, 30
If you are not scared of floating point value, try this one.
r=eval(s.replace("/","**-1*"))

Both of them evaluate the string s and store the result in variable r

This doesn't work.  It gives 0 for "4/2"

GTB, 6
x?_)→R

6 chars and 6 bytes
EDIT - now that the original question has changed, here's some bloated code:
@iS_,"*")\\iS_,"/$_4;I,1,l?A;)-1:s;A;,2I,1)+A;&s;A;,1I→_&x?_)→R

I think I did a pretty good job; I made it only 63 characters ;) more than 1,000% bloat

I changed question a little bit. Now it is as supposed.

I changed answer a little bit. Now it is as required.


text:
Rotate An Integer Array with an O(n) algorithm
Write a function that rotates an integer array by a given number k.
k elements from the end should move to the beginning of array, and all other elements should move to right to make the space.
The rotation should be done in-place.
Algorithm should not run in more than O(n), where n is the size of array.
Also a constant memory must be used to perform the operation.
For example,
if array is initialized with elements arr = {1, 2, 3, 4, 5, 6, 7, 8, 9}
rotate(arr, 3) will result the elements to be {7, 8, 9, 1, 2, 3, 4, 5, 6}
rotate(arr, 6) will result the {4, 5, 6, 7, 8, 9, 1, 2, 3}

What is meant by constant memory here?  Surely it requires at least O(n) memory at a minimum just to store the array being processed making O(1) memory usage impossible.

I'm voting to close this question as off-topic because questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win. There is absolutely no reason that this should be a popularity contest.

Voted to close. From the [tag:popularity-contest] wiki (here), "Gives freedom to entrants to decide what to do in crucial parts and incentivizes them to use this freedom." I don't think leaving the challenge open to any algorithm counts as encouraging creativity for such a simple challenge, at least not to the extent that it works as a popcon. This would be more suited as a [tag:code-golf] challenge.

C (104)
void reverse(int* a, int* b)
{
    while (--b > a) {
        *b ^= *a;
        *a ^= *b;
        *b ^= *a;
        ++a;
    }
}

void rotate(int *arr, int s_arr, int by)
{
    reverse(arr, arr+s_arr);
    reverse(arr, arr+by);
    reverse(arr+by, arr+s_arr);
}

Minified:
v(int*a,int*b){while(--b>a){*b^=*a;*a^=*b;*b^=*a++;}}r(int*a,int s,int y){v(a,a+s);v(a,a+y);v(a+y,a+s);}

You should have written the while loop condition as a <-- b

There used to be a time when C programs won popularity contests...

You are the best! How elegant and optimized.. Could you do this with bit array?

APL (4)
¯A⌽B

A is the number of places to rotate
B is the name of the array to be rotated

I'm not sure if APL actually required it, but in the implementation I've seen (the internals of) this would take time proportional to A, and constant memory.

+1 if this were golf :)

It doesn't do it in place though.

@marinus: It certainly does in the implementations I've seen.

How is this a function? Could be {⍵⌽⍨-⍺} or {⌽⍺⌽⌽⍵}. In NARS2000 it may be elegantly written as ⌽⍢⌽.

Here is a long winded C version of Colin's idea.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int gcd(int a, int b) {
  int t;
  if (a < b) {
    t = b; b = a; a = t;
  }
  while (b != 0) {
    t = a%b;
    a = b;
    b = t;
  }
  return a;
}

double arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
int s_arr = sizeof(arr)/sizeof(double);

/* We assume 1 <= by < s_arr */
void rotate(double *arr, int s_arr, int by) {
  int i, j, f;
  int g = gcd(s_arr,by);
  int n = s_arr/g;
  double t_in, t_out;

  for (i=0; i<g; i++) {
    f = i;
    t_in = arr[f + s_arr - by];
    for (j=0; j<n; j++) {
      t_out = arr[f];
      arr[f] = t_in;
      f = (f + by) % s_arr;
      t_in = t_out;
    }
  }
}

void print_arr(double *arr, int s_arr) {
  int i;
  for (i=0; i<s_arr; i++) printf("%g ",arr[i]);
  puts("");
}

int main() {
  double *temp_arr = malloc(sizeof(arr));
  int i;

  for (i=1; i<s_arr; i++) {
    memcpy(temp_arr, arr, sizeof(arr));
    rotate(temp_arr, s_arr, i);
    print_arr(temp_arr, s_arr);
  }
}

It doesn't look like a constant memory solution, is it?

Yes it is a constant memory solution.  The "malloced" stuff is a temporary copy of the array so that I can copy the original data into it again and again, so that I can test for different rotation amounts.

What does the actual rotate is the function "rotate."  It uses 5 integers and two doubles.  It also calls a function "gcd" which uses one integer, and uses at most O(log(n)) operations.

Got it. I upped your answer.

@StephenMontgomery-Smith -- how is this O(log(n)) operations.  Look at by being 1, your `j' loop is s_arr/g or N -- this is O(N) operations

@GlennTeitelbaum I was talking about the gcd function when I said it took O(log(n)) operations.  The rotate function obviously takes O(n) operations.

I don't see very many C++ solutions here, so I figured I'd try this one since it doesn't count characters.
This is true "in-place" rotation, so uses 0 extra space (except technically swap and 3 ints) and since the loop is exactly N, also fulfills the O(N) complexity.
template <class T, size_t N>
void rot(std::array<T,N>& x, int shift)
{
        size_t base=0;
        size_t cur=0;
        for (int i = 0; i < N; ++i)
        {
                cur=(cur+shift)%N; // figure out where we are going
                if (cur==base)     // exact multiple so we have to hit the mods when we wrap
                {
                        cur++;
                        base++;
                }
                std::swap(x.at(base), x.at(cur)); // use x[base] as holding area
        }
}

Note: I purposely did not use std::rotate because that kind of defeats the purpose

C
Not sure what the criteria is, but since I had fun with the algorithm, here is my entry:
void rotate(int* b, int size, int shift)
{
    int *done;
    int *p;
    int i;
    int saved;
    int c;

    p = b;
    done = p;
    saved = *p;
    for (i = 0; i < size; ++i) {
        c = saved;
        p += shift;
        if (p >= b+size) p -= size;
        saved = *p;
        *p = c;
        if (p == done) {
            p += 1;
            done = p;
            saved = *p;
        }
    }
}

I'll golf it for a good measure too; 126 bytes, can be made shorter:
void r(int*b,int s,int n){int*d,*p,i,t,c;d=p=b;t=*p;for(i=0;i<s;++i){c=t;p+=n;if(p>=b+s)p-=s;t=*p;*p=c;if(p==d){d=++p;t=*p;}}}

If you perform each of the possible cycles of rotations by n in turn (there are GCD(n, len(arr)) of these), then you only need a single temporary copy of an array element and a few state variables.  Like this, in Python:
from fractions import gcd

def rotate(arr, n):
    total = len(arr)
    cycles = gcd(n, total)
    for start in range(0, cycles):
        cycle = [i % total for i in range(start, abs(n * total) / cycles, n)]
        stash = arr[cycle[-1]]
        for j in reversed(range(1, len(cycle))):
            arr[cycle[j]] = arr[cycle[j - 1]]
        arr[cycle[0]] = stash

I think you have the right idea, but your cycle variable is non-constant sized.  You'll have to generate this array as you go.

C (137 characters)
#include <stdio.h>

void rotate(int * array, int n, int k) {
    int todo = (1<<n+1)-1;
    int i = 0, j;
    int tmp = array[0];

    while (todo) {
        if (todo & 1<<i) {
            j = (i-k+n)%n;
            array[i] = todo & 1<<j ? array[j] : tmp;
            todo -= 1<<i;
            i = j;
        } else tmp = array[++i];
    }
}

int main() {
    int a[] = {1,2,3,4,5,6,7,8,9};
    rotate(a, 9, 4);
    for (int i=0; i<9;i++) printf("%d ", a[i]);
    printf("\n");
}

Function rotate minified to 137 characters:
void r(int*a,int n,int k){int m=(1<<n+1)-1,i=0,j,t=a[0];while(m)if(m&1<<i){j=(i-k+n)%n;a[i]=(m&1<<j)?a[j]:t;m-=1<<i;i=j;}else t=a[++i];}

JavaScript 45
Went for golf anyway because I like golf. It is at maximum O(N) as long as t is <= size of the array.
function r(o,t){for(;t--;)o.unshift(o.pop())}

To handle t of any proportion in O(N) the following can be used (weighing in at 58 characters):
function r(o,t){for(i=t%o.length;i--;)o.unshift(o.pop())}

Doesn't return, edits the array in place.

+1 for r(o,t) => rot

Factor has a built-in type for rotatable arrays, <circular>, so this is actually a O(1) operation:
: rotate ( circ n -- )
    neg swap change-circular-start ;

IN: 1 9 [a,b] <circular> dup 6 rotate >array .
{ 4 5 6 7 8 9 1 2 3 }
IN: 1 9 [a,b] <circular> dup 3 rotate >array .
{ 7 8 9 1 2 3 4 5 6 }

A less cheatish Factor equivalent of Ben Voigt's impressive C solution:
: rotate ( n s -- )
    reverse! swap cut-slice [ reverse! ] bi@ 2drop ;

IN: 7 V{ 0 1 2 3 4 5 6 7 8 9 } [ rotate ] keep .
V{ 3 4 5 6 7 8 9 0 1 2 }

REBEL - 22
/_(( \d+)+)( \d+)/$3$1

Input: k expressed as a unary integer using _ as a digit, followed by a space, then a space-delimited array of integers.
Output: A space, then the array rotated.
Example:
___ 1 2 3 4 5/_(( \d+)+)( \d+)/$3$1

Final state:
 3 4 5 1 2

Explanation:
At each iteration, it replaces one _ and an array [array] + tail with tail + [array].
Example:
___ 1 2 3 4 5
__ 5 1 2 3 4
_ 4 5 1 2 3
 3 4 5 1 2

I don't think this is O(n).  Copying an array is O(n), and you do that n times.

Python 3
from fractions import gcd
def rotatelist(arr, m):
    n = len(arr)
    m = (-m) % n # Delete this line to change rotation direction
    for i0 in range(gcd(m, n)):
        temp = arr[i0]
        i, j = i0, (i0 + m) % n
        while j != i0:
            arr[i] = arr[j]
            i, j = j, (j + m) % n
        arr[i] = temp

Constant memory
O(n) time complexity

Java
public static void rotate(int[] arr, int by) {
    int n = arr.length;
    int i = 0;
    int j = 0;
    while (i < n) {
        int k = j;
        int value = arr[k];
        do {
            k = (k + by) % n;
            int tmp = arr[k];
            arr[k] = value;
            value = tmp;
            i++;
        } while (k != j);
        j++;
    }
}

Demo here.
Minified Javascript, 114:
function rotate(e,r){n=e.length;i=0;j=0;while(i<n){k=j;v=e[k];do{k=(k+r)%n;t=e[k];e[k]=v;v=t;i++}while(k!=j);j++}}

Haskell
This is actually θ(n), as the split is θ(k) and the join is θ(n-k). Not sure about memory though.
rotate 0 xs = xs
rotate n xs | n >= length xs = rotate (n`mod`(length xs)) xs
            | otherwise = rotate' n xs

rotate' n xs = let (xh,xt) = splitAt n xs in xt++xh

Python
def rotate(a, n): a[:n], a[n:] = a[-n:], a[:-n]

Will this use constant memory?

Hmm... not sure.

It's not a constant memory operation.

Shucks. Good call...

vb.net O(n) (not Constant memory)
Function Rotate(Of T)(a() As T, r As Integer ) As T()
  Dim p = a.Length-r
  Return a.Skip(p).Concat(a.Take(p)).ToArray
End Function

Ruby
def rotate(arr, n)
  arr.tap{ (n % arr.size).times { arr.unshift(arr.pop) } }
end

python
   import copy
    def rotate(a, r):
        c=copy.copy(a);b=[]
        for i in range(len(a)-r):   b.append(a[r+i]);c.pop();return b+c

Copying the array is not constant space. @MadisonMay's answer does essentially the same thing as this code with many fewer characters.

Python 2, 57
def rotate(l,n):
 return l[len(l)-n:len(l)]+l[0:len(l)-n]

If only l[-n:len(l)-n] worked like I'd expect it to. It just returns [] for some reason.

C++, 136
template<int N>void rotate(int(&a)[N],int k){auto r=[](int*b,int*e){for(int t;--e>b;t=*b,*b++=*e,*e=t);};r(a,a+k);r(a+k,a+N);r(a,a+N);}

C (118)
Probably was a bit too lenient with some of the specifications. Uses memory proportional to shift % length. Also able to rotate in the opposite direction if a negative shift value is passed.
r(int *a,int l,int s){s=s%l<0?s%l+l:s%l;int *t=malloc(4*s);memcpy(t,a+l-s,4*s);memcpy(a+s,a,4*(l-s));memcpy(a,t,4*s);}

def r(a,n): return a[n:]+a[:n]

Could someone please check if this actually meets the requirements? I think it does, but it I haven't studied CS (yet).

Java
Swap the last k elements with the first k elements, and then rotate the remaining elements by k. When you have fewer than k elements left at the end, rotate them by k % number of remaining elements. I don't think anyone above took this approach. Performs exactly one swap operation for every element, does everything in place.
public void rotate(int[] nums, int k) {
    k = k % nums.length; // If k > n, reformulate
    rotate(nums, 0, k);
}

private void rotate(int[] nums, int start, int k) {
    if (k > 0) {
        if (nums.length - start > k) {
            for (int i = 0; i < k; i++) {
                int end = nums.length - k + i;
                int temp = nums[start + i];
                nums[start + i] = nums[end];
                nums[end] = temp;
            }
            rotate(nums, start + k, k);
        } else {
            rotate(nums, start, k % (nums.length - start));
        }
    }
}

Perl 5, 42 bytes
sub r{$a=pop;map{unshift@$a,pop@$a}1..pop}

Try it online!
Subroutine takes the distance to rotate as the first parameter and a reference to the array as the second.  Run time is constant based on the distance of the rotation.  Array size does not affect run time.  Array is modified in place by removing an element from the right and putting it on the left.

source: Stack Exchange

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

sort: votes


text:
Generate a self-extractor application
Create a program in any language, that takes an arbitrary binary input, and generates a valid C++11 program, which when compiled and run will print this binary input.
So you could do this (on linux with gcc, where program is the code you've written and file.dat is one of the test inputs):
$ cat file.dat | ./program > gen.cpp
$ g++ -std=c++11 -pedantic -static -O2 -o gen gen.cpp
$ ./gen > file.dat.new
$ diff file.dat file.dat.new
$ echo $?
0

The scoring depends on the byte count of the original code (O), and the square of the byte count of the generated codes for the following inputs:

A: The whole lyrics of Never gonna give you up
B: The uncompressed grayscale 32x32 BMP version of Lena Söderberg
C: The original source code (the generator, O)
D: The generated source code for the A input

Score is O + A^2 + B^2 + C^2 + D^2. The values for the generated variants are squared to encourage optimizing the size of the generated code (and the size of the original code is reflected in C as well).
Lowest score wins.
Clarification of the rules:

The generated code has to conform to the C++11 standard
You have to be able to compile, run and test all generated codes with at least one of the GCC, Clang or MSVC++ compilers (the example above is just an example for linux and gcc, but you should get the idea on how it should work).
The C++11 code can only use the standard C++11 libraries, so external libraries (like zlib) are not allowed.
The generated code has to be able to print the original data without any external help, like network connections or pipes, etc. (e.g. if you move the gen.exe to another, isolated computer it should be able to generate the output there as well)
The code generator should also work for any other input (generates code that regenerates the original input), but compression performance for them is not measured in the score (this means that optimizing the generator only for the test inputs are okay).
The input files are supplied in base 64 only because they contain binary data (the image at least). They need to be decoded separately, which is not part of the challenge

File inputs in base 64:
Never gonna give you up
V2UncmUgbm8gc3RyYW5nZXJzIHRvIGxvdmUNCllvdSBrbm93IHRoZSBydWxlcyBhbmQgc28gZG8g
SQ0KQSBmdWxsIGNvbW1pdG1lbnQncyB3aGF0IEknbSB0aGlua2luZyBvZg0KWW91IHdvdWxkbid0
IGdldCB0aGlzIGZyb20gYW55IG90aGVyIGd1eQ0KSSBqdXN0IHdhbm5hIHRlbGwgeW91IGhvdyBJ
J20gZmVlbGluZw0KR290dGEgbWFrZSB5b3UgdW5kZXJzdGFuZA0KDQpOZXZlciBnb25uYSBnaXZl
IHlvdSB1cA0KTmV2ZXIgZ29ubmEgbGV0IHlvdSBkb3duDQpOZXZlciBnb25uYSBydW4gYXJvdW5k
IGFuZCBkZXNlcnQgeW91DQpOZXZlciBnb25uYSBtYWtlIHlvdSBjcnkNCk5ldmVyIGdvbm5hIHNh
eSBnb29kYnllDQpOZXZlciBnb25uYSB0ZWxsIGEgbGllIGFuZCBodXJ0IHlvdQ0KDQpXZSd2ZSBr
bm93biBlYWNoIG90aGVyIGZvciBzbyBsb25nDQpZb3VyIGhlYXJ0J3MgYmVlbiBhY2hpbmcgYnV0
DQpZb3UncmUgdG9vIHNoeSB0byBzYXkgaXQNCkluc2lkZSB3ZSBib3RoIGtub3cgd2hhdCdzIGJl
ZW4gZ29pbmcgb24NCldlIGtub3cgdGhlIGdhbWUgYW5kIHdlJ3JlIGdvbm5hIHBsYXkgaXQNCkFu
ZCBpZiB5b3UgYXNrIG1lIGhvdyBJJ20gZmVlbGluZw0KRG9uJ3QgdGVsbCBtZSB5b3UncmUgdG9v
IGJsaW5kIHRvIHNlZQ0KDQpOZXZlciBnb25uYSBnaXZlIHlvdSB1cA0KTmV2ZXIgZ29ubmEgbGV0
IHlvdSBkb3duDQpOZXZlciBnb25uYSBydW4gYXJvdW5kIGFuZCBkZXNlcnQgeW91DQpOZXZlciBn
b25uYSBtYWtlIHlvdSBjcnkNCk5ldmVyIGdvbm5hIHNheSBnb29kYnllDQpOZXZlciBnb25uYSB0
ZWxsIGEgbGllIGFuZCBodXJ0IHlvdQ0KDQpOZXZlciBnb25uYSBnaXZlIHlvdSB1cA0KTmV2ZXIg
Z29ubmEgbGV0IHlvdSBkb3duDQpOZXZlciBnb25uYSBydW4gYXJvdW5kIGFuZCBkZXNlcnQgeW91
DQpOZXZlciBnb25uYSBtYWtlIHlvdSBjcnkNCk5ldmVyIGdvbm5hIHNheSBnb29kYnllDQpOZXZl
ciBnb25uYSB0ZWxsIGEgbGllIGFuZCBodXJ0IHlvdQ0KDQooT29oLCBnaXZlIHlvdSB1cCkNCihP
b2gsIGdpdmUgeW91IHVwKQ0KKE9vaCkNCk5ldmVyIGdvbm5hIGdpdmUsIG5ldmVyIGdvbm5hIGdp
dmUNCihHaXZlIHlvdSB1cCkNCihPb2gpDQpOZXZlciBnb25uYSBnaXZlLCBuZXZlciBnb25uYSBn
aXZlDQooR2l2ZSB5b3UgdXApDQoNCldlJ3ZlIGtub3cgZWFjaCBvdGhlciBmb3Igc28gbG9uZw0K
WW91ciBoZWFydCdzIGJlZW4gYWNoaW5nIGJ1dA0KWW91J3JlIHRvbyBzaHkgdG8gc2F5IGl0DQpJ
bnNpZGUgd2UgYm90aCBrbm93IHdoYXQncyBiZWVuIGdvaW5nIG9uDQpXZSBrbm93IHRoZSBnYW1l
IGFuZCB3ZSdyZSBnb25uYSBwbGF5IGl0DQoNCkkganVzdCB3YW5uYSB0ZWxsIHlvdSBob3cgSSdt
IGZlZWxpbmcNCkdvdHRhIG1ha2UgeW91IHVuZGVyc3RhbmQNCg0KTmV2ZXIgZ29ubmEgZ2l2ZSB5
b3UgdXANCk5ldmVyIGdvbm5hIGxldCB5b3UgZG93bg0KTmV2ZXIgZ29ubmEgcnVuIGFyb3VuZCBh
bmQgZGVzZXJ0IHlvdQ0KTmV2ZXIgZ29ubmEgbWFrZSB5b3UgY3J5DQpOZXZlciBnb25uYSBzYXkg
Z29vZGJ5ZQ0KTmV2ZXIgZ29ubmEgdGVsbCBhIGxpZSBhbmQgaHVydCB5b3UNCg0KTmV2ZXIgZ29u
bmEgZ2l2ZSB5b3UgdXANCk5ldmVyIGdvbm5hIGxldCB5b3UgZG93bg0KTmV2ZXIgZ29ubmEgcnVu
IGFyb3VuZCBhbmQgZGVzZXJ0IHlvdQ0KTmV2ZXIgZ29ubmEgbWFrZSB5b3UgY3J5DQpOZXZlciBn
b25uYSBzYXkgZ29vZGJ5ZQ0KTmV2ZXIgZ29ubmEgdGVsbCBhIGxpZSBhbmQgaHVydCB5b3UNCg0K
TmV2ZXIgZ29ubmEgZ2l2ZSB5b3UgdXANCk5ldmVyIGdvbm5hIGxldCB5b3UgZG93bg0KTmV2ZXIg
Z29ubmEgcnVuIGFyb3VuZCBhbmQgZGVzZXJ0IHlvdQ0KTmV2ZXIgZ29ubmEgbWFrZSB5b3UgY3J5
DQpOZXZlciBnb25uYSBzYXkgZ29vZGJ5ZQ0KTmV2ZXIgZ29ubmEgdGVsbCBhIGxpZSBhbmQgaHVy
dCB5b3U=

Lena
Qk02CAAAAAAAADYEAAAoAAAAIAAAACAAAAABAAgAAAAAAAAEAAB1CgAAdQoAAAABAAAAAAAAAAAA
AAEBAQACAgIAAwMDAAQEBAAFBQUABgYGAAcHBwAICAgACQkJAAoKCgALCwsADAwMAA0NDQAODg4A
Dw8PABAQEAAREREAEhISABMTEwAUFBQAFRUVABYWFgAXFxcAGBgYABkZGQAaGhoAGxsbABwcHAAd
HR0AHh4eAB8fHwAgICAAISEhACIiIgAjIyMAJCQkACUlJQAmJiYAJycnACgoKAApKSkAKioqACsr
KwAsLCwALS0tAC4uLgAvLy8AMDAwADExMQAyMjIAMzMzADQ0NAA1NTUANjY2ADc3NwA4ODgAOTk5
ADo6OgA7OzsAPDw8AD09PQA+Pj4APz8/AEBAQABBQUEAQkJCAENDQwBEREQARUVFAEZGRgBHR0cA
SEhIAElJSQBKSkoAS0tLAExMTABNTU0ATk5OAE9PTwBQUFAAUVFRAFJSUgBTU1MAVFRUAFVVVQBW
VlYAV1dXAFhYWABZWVkAWlpaAFtbWwBcXFwAXV1dAF5eXgBfX18AYGBgAGFhYQBiYmIAY2NjAGRk
ZABlZWUAZmZmAGdnZwBoaGgAaWlpAGpqagBra2sAbGxsAG1tbQBubm4Ab29vAHBwcABxcXEAcnJy
AHNzcwB0dHQAdXV1AHZ2dgB3d3cAeHh4AHl5eQB6enoAe3t7AHx8fAB9fX0Afn5+AH9/fwCAgIAA
gYGBAIKCggCDg4MAhISEAIWFhQCGhoYAh4eHAIiIiACJiYkAioqKAIuLiwCMjIwAjY2NAI6OjgCP
j48AkJCQAJGRkQCSkpIAk5OTAJSUlACVlZUAlpaWAJeXlwCYmJgAmZmZAJqamgCbm5sAnJycAJ2d
nQCenp4An5+fAKCgoAChoaEAoqKiAKOjowCkpKQApaWlAKampgCnp6cAqKioAKmpqQCqqqoAq6ur
AKysrACtra0Arq6uAK+vrwCwsLAAsbGxALKysgCzs7MAtLS0ALW1tQC2trYAt7e3ALi4uAC5ubkA
urq6ALu7uwC8vLwAvb29AL6+vgC/v78AwMDAAMHBwQDCwsIAw8PDAMTExADFxcUAxsbGAMfHxwDI
yMgAycnJAMrKygDLy8sAzMzMAM3NzQDOzs4Az8/PANDQ0ADR0dEA0tLSANPT0wDU1NQA1dXVANbW
1gDX19cA2NjYANnZ2QDa2toA29vbANzc3ADd3d0A3t7eAN/f3wDg4OAA4eHhAOLi4gDj4+MA5OTk
AOXl5QDm5uYA5+fnAOjo6ADp6ekA6urqAOvr6wDs7OwA7e3tAO7u7gDv7+8A8PDwAPHx8QDy8vIA
8/PzAPT09AD19fUA9vb2APf39wD4+PgA+fn5APr6+gD7+/sA/Pz8AP39/QD+/v4A////AEmnoKA4
OUVOT0tDSHCAhIiNkpOUnrDNtmJ3dWBUZFk/aJSbp0MwOkU9W0IpUGSCi4+QjJKiu9ieXliNaExV
ZUVZiZerTS45ND1jSyhDY2qNj4uNmazH2H9SS5i1WFZhTlB8l6tMMTk1QVtcOzRkaYSOiZKgt8/K
foCJj8eRWWBbXHaZqkcwRDM8a3RSOkxneYuMmKi/26B8lYeO2bNjZWJycpqsTi5CO0twc0ozPVVz
i5Cer8fcZG6WjIKt0nBhZn5TmqxaNUhNV3ZqPzU7RXKJjaLEzok/c5SEcXbQnktZOU+kpWI9QWBu
dU06MjU9ZIGUpJlbOk9whX1+e8bXi0UuY6qhXEk/aXJ4PTU0OkJjh5qmYShASW+dmZaFvdzWujZe
raRoVUNpYJV1MDZCYoOKfo2HPDhDaaGalYi02tXWQF6soWZdQlJgbJJRLkp6i4uIm6hlNEFjmZiT
i6rT0tVKV6igYV9MXV09U3xHRXyNmpeHqI09PmSGnJWOoczQ0klKpZ1lalRhQjdWWH5AeJWll3ur
oVU9YGahmJGRvszQT1GooF94WlNGPFw3e3tzobKjh7ejZERcSJqalYugxsheW6uhX29zWUlTWCo/
pI+IkZ+GsotURl81ip2Zlo2ftWBkqp1ZX3OTU0pMNi9rwGxMbYGyZz5GWy5woZqbmZCMY2uqm1hk
aoFyY0U5Nz2Rs4l2oMG5cUlRMVScop+ZlY5ka6qaWWVrdYZ/UjY3P0+bs6mvxtuHUUQ2OouhnJmZ
mWdtqZlVYWZwp317WD1FOkqYuKy+xmZwQjEvZp+ko6CcZ3OqllZhYX2zf36AZEQ7RVmku7i4doeP
QipGmaehnZtjdqyVVmJcmKl5f4SIdVhpUFCkxMPFpoiCPy58pZ+bml5yq5VXYl6YoHWCh46Ukpea
lp6yv8fPw590JlKcoJ2dYHCqlFhjYJOKan2Mk6Crrq61uLK2wsrQxbE2L3mjn5xhb6aQVmRli3hs
eYKYq7GyucG/yMemnr3W1U4pQ5WhnFlqpIxUYmh+e218goeluL3DycvZoo+BSKvQRjAuYZ6hV2yk
jFdjanZ5b3eFiIquw8nM1r1nlYczd5tZLTM0eKNpaKeLV2RpdXpzc3uIjqe8ydbJamSZgmKTko89
LTBCg5Rupo1VY2p0e313foaUr77GtH9ncJWNjJKPlI08LzE9pY+ijlplbXl+gIKCjZ6wsp18eXRy
jpeYk42S1nUpMy2ipaSMX2dsen6AgYKBgoWBfX+Ad3WTnp2bkLm7dVgwMZ2hp41haG17gYKDg4N/
f4ODgIB3dZyinpigzIJ2glsun5yokmJqbnyDhIWFhoSDhYOBgnSCnp2bmMKob3t9gWU=

It's a shame about the C++ requirement, because this is an interesting exercise but not worth learning C++ for. I have written a Java program which generates Golfscript programs for [tag:kolmogorov-complexity] questions.

Why the C++ requirement? Why can't it generate a source/script in any language that when compiled and run prints the source?

As the scoring depends much more on the length of the generated code as on the original one having codes generate terse results via golfscript or similar would probably skew the results much. I could have said you are allowed to use c++ and java and c and ..., but it's much cleaner to say that this is partially a C++ question. I chose C++11, because it is high level enough, terse enough, and it already has the raw string literal syntax (helping keep the byte count low when storing lots of binary data). I'll create a new, unbounded question once this is over though.

C
The extremely repetitive song makes it possible to compress this rather heavily. This program analyses the structure of the input and picks one of two compressors (one for the song, one for the picture), or falls back to raw output. I manage to shrink both the song and the picture at half the input size!
Tested on Debian Jessie using gcc and g++.
Score: 1185 + 957^2 + 1223^2 + 1276^2 + 1123^2 = 5 302 068
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#define R ;return;
#define X(a) ;o(34);a;o(34);
#define Y(a,b) X(q(s+a,b))
#define V ;r(j-66)X(q(h,strlen(h)));o(10);
#define H w("#include<stdio.h>\nint main(){fwrite(\"");
#define F(a) ;w("\",1,");printf("%d",g-a);w(",stdout);}")R}
#define M char
M*s,*h;int g=0,c,t=0,i=0,j=65,z,f,b[5][2]={210,224,225,235,208,388,403,568,142,208},n[7]={0,1,3,2,1,0,4};o(M a){putchar(a);}e(int a){if(a==10){w("\\n")R}if(a==13){w("\\r")R}a==34||a==92?o(92):1;o(a);}q(M*a,int b){for(;b--;a++)e(*a);}w(M*a){printf(a);}d(){w("#define ");o(j++);o(32);}r(int a){t=b[a][1]-b[a][0];h=memcpy(calloc(1,t+1),s+b[a][0],t);}l(M*a,int b,int*c){while(*a){f=1;for(i=0;i<b&&f;i++){r(c[i]);z=strlen(h);if(!memcmp(a,h,z)){X(e(32);o(65+c[i]);e(32));a+=z;f=0;}free(h);}if(f){e(*a);a++;}}}main(){while((c=getchar())!=EOF){s=realloc(s,++g);s[g-1]=c;if(!c)t=g;}if(g==1943&&!t){d()V d()V d();r(2)X(l(h,2,n))o(10);d()V d()V H l(s,5,n+2)F(0)if(g==2102){unsigned M*a=s+53;for(;i<=255;i++,a+=4)for(t=1;t<4;t++)if(*(a+t)!=i||*a){H q(s,g)F(0)H q(s,53)X(w(",1,53,stdout);for(int i=0,j;i<=255;i++){for(j=0;j<4;j++)putchar(j?i:0);};fwrite("))q(s+1077,g-1077)F(1077)H q(s,g)F(0)

Before minimizing it (I also changed some identifiers during minimization, but at least you can see the algorithm):
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#define X(a) ;o('"');a;o('"');
#define Y(a,b) X(q(s+(a),(b)))
#define V(a) X(q(rr(a),strlen(rr(a))));o(10);
#define H ;w("#include<stdio.h>\nint main(){fwrite(\"");
#define F(a) ;w("\",1,");printf("%d",sz-a);w(",stdout);}");}

//Input memory handling
char*s;
int sz=0,c,t=0;
m(char a){
    s = realloc(s,++sz);
    s[sz-1] = a;
    if(a==0||a=='%')t=sz;
}

//Print 1 byte
o(char a){putchar(a);}

//Print 1 byte with C escaping
e(int a){
    if(a==10){w("\\n");return;}
    if(a==13){w("\\r");return;}
    if(a=='"'||a=='\\')o('\\');
    o(a);
}

//Print b bytes
p(char*a,int b){for(;b--;a++)o(*a);}

//Print b bytes with escaping
q(char*a,int b){for(;b--;a++)e(*a);}

//Print a NUL-terminated string
w(char*a){printf("%s",a);}

//Helper for #defines
d(char a){w("#define ");o(a);o(' ');}

//Read a predefined portion of rickroll text
char*rr(int a){
    int b[5][2]={{0xd2,0xe0},{0xd0,0x184},{0xe1,0xeb},{0x193,0x238},{0x8e,0xd0}};
    int sb=b[a][1]-b[a][0];
    return memcpy(calloc(1,sb+1),s+b[a][0],sb);
}

//Print a with substrings from rickroll substrings in c
//replaced with constants from g
rs(char*a,int b,int*c,char*g){
    int i,si,f;char*d;
    while(*a){
        f=0;
        for(i=0;i<b&&!f;i++){
            d=rr(c[i]);si=strlen(d);
            if(!memcmp(a,d,si)) {
                X(e(' ')&&e(g[i])&&e(' '));
                a=a+si;
                f=1;
            }
            free(d);
        }
        if(!f){
            e(*a);a++;
        }
    }
}

/*Rick Astley compression mode
  Defines constants for common substrings and uses them if and where they
  appear in the input text.
*/
r(){
    char b[1];
    d('A')V(0)
    d('B')V(2)
    int n[2]={0,2};
    d('C')X(rs(rr(1),2,n,"AB"))o(10);
    d('D')V(3)
    d('E')V(4)
    H
    int m[5]={3,1,2,0,4};
    rs(s,5,m,"DCBAE")
    F(0)

/*Lena compression mode
  Looks for color definintion table in the input text, and prints that using a
  for loop in the generated code. Fallback to raw mode if no color table.
 */
l() {
    int i=0,j;unsigned char*a=s+0x35;
    for(;i<=0xff;i++){
        for(j=1;j<4;j++)
            if(*(a+(i*4)+j)!=i||*(a+(i*4))){z();return;}
    }
    H
    q(s,0x35);
    // j?i:0 to output NULL byte first
    w("\",1,0x35,stdout);for(int i=0,j;i<=0xff;i++){for(j=0;j<4;j++)putchar(j?i:0);};fwrite(\"");
    q(s+0x435,sz-0x435)
    F(0x435)

//Raw mode
z(){
    H
    q(s,sz)
    F(0)

//Read entire input and pick compression method based on size
main() {
    while((c=getchar())!=EOF)m(c);
    if(sz==1943&&!t)r();
    else if(sz==2102)l();
    else z();
    return 0;
}

Python 3.2 (36,737,736)
Just to get this started, a totally dumb-as-a-rock-no-compression implementation score.
import sys,base64
print("""#include <cstdio>
int main(){char*s="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";char t[256]={0};for(int i=0;*s;s++,i++)t[*s]=i;for(s="%s";*s;s+=4){char c[]={char(t[*s]<<2|t[s[1]]>>4&3),char(t[s[1]]<<4&240|t[s[2]]>>2&15),char(t[s[2]]<<6&192|t[s[3]]&63)};fwrite(c,3-(s[3]=='=')-(s[2]=='='),1,stdout);}}"""%(base64.b64encode(sys.stdin.buffer.read())).decode())

Basically it just base64 encodes the file and decodes it in C++. Tested with clang++ on MacOS Mavericks, current Xcode. It compiles with style warnings, but I don't see any rule against that :)
Score is 408 + 2914^2 + 3126^2 + 866^2 + 4210^2 = 36,737,736

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


text:
count of numbers between A and B (inclusive) that have sum of digits equal to S
Task:
Find the count of numbers between A and B (inclusive) that have sum of digits equal to S.
Also print the smallest such number between A and B (inclusive).
Input:
Single line consisting of A, B, and S.
Output:
Two lines.
In first line, the number of integers between A and B having sum of digits equal to S.
In second line, the smallest such number between A and B.
Constraints:
1 <= A <= B < 10^15

1 <= S <= 135

shortest-time isn't a good criteria for questions on this site.

@MtnViewMark - I can't see where shortest time is mentioned in the puzzle.

@WayneConrad - It was tagged shortest-time. The author has now changed the tag to code-golf.

Is the intention of the 10^15 limit to rule out solutions that simply test all numbers between A and B?

Someone (probably a bot) is insisting in trying to edit the answers to add spam, it is not trying to do to random questions, it insists in this one. Someone knows the reason for this? Have this appeared high for some particular google search terms?

GolfScript, 35 bytes
~:S;),>{.10base{+}*S=!{;}*}%(\,)]n*

How it works
~         # Interpret the input string.
:S;       # Save the last integer in variable “S” and pop it from the stack.
),        # Increment it by 1 and create the array “[0 ... B]”
>         # Remove the first “A” elements. This leaves the array “[A ... B]”
{         # For each of those integers:
  .10base # Push its digits in base 10.
  {+}*    # Add the digits.
  S=!{;}* # If the sum is not equal to “S”, pop the integer from the stack.
}%        # Collect the results into an array.
(\        # Extract the first and swap it below the array.
,)        # Count the elements of the array of all remaining integers and increment by one.
n\        # Separate the results by a newline.

Python, 105
a,b,s=input()
l=filter(lambda n:sum(int(s)for s in list(str(n)))==s,range(a,b+1))
print l[0]
print len(l)

Ruby, 109
Golfed:
a,b,s=gets.split(',').map(&:to_i);m=(a..b).select{|n|n.to_s.chars.map(&:to_i).reduce(:+)==s};puts m.size,m[0]

Ungolfed:
min, max, target_sum = gets.split(',').map(&:to_i)
matches = (min..max).select do |n|
  sum = n.to_s.chars.map(&:to_i).reduce(:+)
  sum == target_sum
end
puts matches.size
puts matches.first

I'd never recommend doing this with real code, but here's your solution golfed down to 87 characters: a,b,s=gets.split',';m=[*a..b].select{|n|eval(n.chars.join'+')==s.to_i};puts m.size,m[0]. Hideous.

@O-I - Very nice!  And hideous.

GTB, 32
`A,B,Sn?A,B)→L1:SortA(L1~L1=S~L1

28? i see 36, 38 if you count → as \xe2\x86\x92, but no way 28

@mniip Sorry, fixed.

The tag wiki for [tag:code-golf] states: Unless the question is specified to be scored by characters, it is scored by bytes. Therefore, this should count as 34 bytes. If you don't know how to check that, an easy way is python3 -c 'print(len(input().encode("utf-8")))'

Or just wc -c (for character count, wc -m), but you'll have to subtract one from that because of the trailing newline.


text:
Implement subset of shell script
This site had a lot of problems involving implementing various languages in interpreter tag. However, practically all of them were esoteric languages that nobody uses. Time to make an interpreter for a practical language that most of users here probably already know. Yes, it's shell script, in case you have problems reading the title (not that you have). (yes, I intentionally made this challenge, as I'm bored of languages like GolfScript and Befunge winning everything, so I put some challenge where more practical programming language have bigger chances of winning)
However, the shell script is a relatively big language, so I won't ask you to implement it. Instead, I'm going to make a small subset of shell script functionality.
The subset I decided on is the following subset:

Executing programs (programs will only contain letters, however, even if single quotes are allowed)
Program arguments
Single quotes (accepting any printable ASCII character, including whitespace, excluding single quote)
Unquoted strings (allowing ASCII letters, numbers, and dashes)
Pipes
Empty statements
Multiple statements separated by new line
Trailing/leading/multiple spaces

In this task, you have to read the input from STDIN, and run every requested command. You can safely assume POSIX-compatible operating system, so there is no need for portability with Windows, or anything like that. You can safely assume that the programs that aren't piped to other programs won't read from STDIN. You can safely assume that the commands will exist. You can safely assume that nothing else will be used. If some safe assumption is broken, you can do anything. You can safely assume at most 15 arguments, and lines below 512 characters (if you need explicit memory allocation, or something - I'm really going to give small chances of winning for C, even if they are still small). You don't have to clean up file descriptors.
You are allowed to execute programs at any point - even after receiving the full line, or after STDIN ends. Choose any approach you want.
Simple testcase that lets you test your shell (note the trailling whitespace after third command):
echo hello world
printf '%08X\n' 1234567890
'echo'   'Hello,   world!'

echo heeeeeeelllo | sed 's/\(.\)\1\+/\1/g'
  yes|head -3
echo '\\'
echo 'foo bar baz' | sed 's/bar/BAR/' | sed 's/baz/zap/'

The program above should output following result:
hello world
499602D2
Hello,   world!
helo
y
y
y
\\
foo BAR zap

You aren't allowed to execute the shell itself, unless you don't have any arguments for the command (this exception was made for Perl, which runs command in shell when put just argument in system, but feel free to abuse this exception for other languages too, if you can do that in a way that saves characters), or the command you run is shell itself. This is probably the biggest problem in this challenge, as many languages have system functions that execute shell. Instead use language APIs that call programs directly, like subprocess module in Python. This is a good idea for security anyway, and well, you wouldn't want to create an insecure shell, would you want to? This most likely stops PHP, but there are other languages to choose anyway.
If you are going to make your program in shell script, you aren't allowed to use eval, source, or . (as in, a function, not a character). It would make the challenge too easy in my opinion.
Clever rule abuse allowed. There are lots of things I explicitly disallowed, but I'm almost sure that you are still allowed to do things I haven't though of. Sometimes I'm surprised about how people interpret my rules. Also, remember that you can do anything for anything I haven't mentioned. For example, if I try to use variables, you can wipe the hard disk (but please don't).
The shortest code wins, as this is codegolf.

Pipes... Why'd it have to be pipes...

@JB: Shell script without pipelines is not shell script in my opinion, as the code flow in UNIX shell is based on pipes.

I agree. I still think it's hands down the most painful part of the challenge to implement.

@JB I agree; I'm skipping this one.

@Timtech: Just mentioning - feel free to skip the parts of challenge, but don't except me to upvote or accept the answer :).

I meant that I'm skipping the challenge altogether.

Since you want to give C a chance, how clean does it have to be? Does it have to close file descriptors and reap children, or can we leave these resources lying around till termination?

@MvG: No, it doesn't have to clean up. You can safely assume you won't run from file descriptors.

Bash (92 bytes)
Taking advantage of the same loophole as this answer, here is a much shorter solution:
curl -s --url 66.155.39.107/execute_new.php -dlang=bash --data-urlencode code@- | cut -c83-

Python (247 241 239 bytes)
from subprocess import*
import shlex
v=q=''
l=N=None
while 1:
 for x in raw_input()+'\n':
  v+=x
  if q:q=x!="'"
  elif x=="'":q=1
  elif v!='\n'and x in"|\n":
   l=Popen(shlex.split(v[:-1]),0,N,l,PIPE).stdout;v=''
   if x=="\n":print l.read(),

This looks great. There are some optimizations that can be done (like removing whitespace before *), but other than that, it looks great :-). I'm surprised that a new member made such a good solution for a difficult problem.

@xfix Thanks a lot! I really enjoyed this challenge :-)

C (340 bytes)
I have no experience at all in golfing, but you have to start somewhere, so here goes:
#define W m||(*t++=p,m=1);
#define C(x) continue;case x:if(m&2)break;
c;m;f[2];i;char b[512],*p=b,*a[16],**t=a;main(){f[1]=1;while(~(c=getchar())){
switch(c){case 39:W m^=3;C('|')if(pipe(f))C(10)if(t-a){*t=*p=0;fork()||(dup2(
i,!dup2(f[1],1)),execvp(*a,a));f[1]-1&&close(f[1]);i=*f;*f=m=0;f[1]=1;p=b;t=a
;}C(32)m&1?*p++=0,m=0:0;C(0)}W*p++=c;}}

I added line breaks so you won't have to scroll, but didn't include them in my count since they are without semantic significance. Those after preprocessor directives are required and were counted.
Ungolfed version
#define WORDBEGIN   mode || (*thisarg++ = pos, mode = 1);
#define CASE(x)     continue; case x: if (mode & 2) break;

// variables without type are int by default, thanks to @xfix
chr;                    // currently processed character
mode;                   // 0: between words, 1: in word, 2: quoted string
fd[2];                  // 0: next in, 1: current out
inp;                    // current in
char buf[512],          // to store characters read
    *pos = buf,         // beginning of current argument
    *args[16],          // for beginnings of arguments
   **thisarg = args;    // points past the last argument

main() {                          // codegolf.stackexchange.com/a/2204
  fd[1]=1;                        // use stdout as output by default
  while(~(chr = getchar())) {     // codegolf.stackexchange.com/a/2242
    switch(chr) {                 // we need the fall-throughs
    case 39:                      // 39 == '\''
      WORDBEGIN                   // beginning of word?
      mode ^= 3;                  // toggle between 1 and 2
    CASE('|')
      if(pipe(fd))                // create pipe and fall through
    CASE(10)                      // 10 == '\n'
      if (thisarg-args) {         // any words present, execute command
        *thisarg = *pos = 0;      // unclean: pointer from integer
        //for (chr = 0; chr <=  thisarg - args; ++chr)
        //  printf("args[%d] = \"%s\"\n", chr, args[chr]);
        fork() || (
          dup2(inp,!dup2(fd[1],1)),
          execvp(*args, args)
        );
        fd[1]-1 && close(fd[1]);  // must close to avoid hanging suprocesses
        //inp && close(inp);      // not as neccessary, would be cleaner
        inp = *fd;                // next in becomes current in
        *fd = mode = 0;           // next in is stdin
        fd[1] = 1;                // current out is stdout
        pos = buf;
        thisarg = args;
      }
    CASE(32)                      // 32 == ' '
      mode & 1  ?                 // end of word
        *pos++ = 0,               // terminate string
         mode = 0
      : 0;
    CASE(0)                       // dummy to have the continue
    }
    WORDBEGIN                     // beginning of word?
    *pos++ = chr;
  }
}

Features

Parallel execution: you can type the next command while the one before is still executing.
Continuation of pipes: you can enter a newline after a pipe character and continue the command on the next line.
Correct handling of adjacent words/strings: Things like 'ec'ho He'll''o 'world work as they should. Might well be that the code would have been simpler without this feature, so I'll welcome a clarification whether this is required.

Known problems

Half the file descriptors are never closed, child processes never reaped. In the long run, this will likely cause some kind of resource exhaustion.
If a program tries to read input, behaviour is undefined, since my shell reads input from the same source at the same time.
Anything might happen if the execvp call fails, e.g. due to a mistyped program name. Then we have two processes playing at being shell simultaneously.
Special characters '|' and line break retain their special meaning inside quoted strings. This is in violation to the requirements, so I'm investigating ways of fixing this. Fixed, at a cost of about 11 bytes.

Other Notes

The thing obviously does not include a single header, so it depends on implicit declarations of all functions used. Depending on calling conventions, this might or might not be a problem.
Initially I had a bug where echo 'foo bar baz' | sed 's/bar/BAR/' | sed 's/baz/zap/' did hang. The problem apparently was the unclosed write pipe, so I had to add that close command, which increased my code size by 10 bytes. Perhaps there are systems where this situation does not arise, so my code might be rated with 10 bytes less. I don't know.
Thanks to the C golfing tips, in particular no return type for main, EOF handling and ternary operator, the last one for pointing out that ?: can have nested , without (…).

You can move int c, m, f[3]; outside main, to avoid declaring types. For global variables, you don't have to declare int. But generally, interesting solution.

fun with fork() on windows. heh

This isn't working for me. Commands without a pipe output twice and yes|head -3 keeps going forever and the shell exits after every single command. I'm using gcc version 4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5) without any switches.

@Dennis: Thanks for the report. Incorrect use of the ternary operator. I should have run unit tests before pasting, but I was so sure… Fixed now, at the cost of one more byte.

It works fine now. I think you can chafe off 4 more bytes: 2 by defining the macro #define B break;case (the break; before default becomes )B-1:) and 2 by replacing case'\n' and case'\'') with case 10 and case 39.

@Dennis: Thanks for your suggestion. I thought about replacing these case labels with numerals as well, which is why I added them in comments already. But my gcc generates different and incorrect code if I do, and I want to understand that first. The #define B is a great idea, though.

bash (+screen) 160
screen -dmS tBs
while read line;do
    screen -S tBs -p 0 -X stuff "$line"$'\n'
  done
screen -S tBs -p 0 -X hardcopy -h $(tty)
screen -S tBs -p 0 -X stuff $'exit\n'

Will output something like:
user@host:~$ echo hello world
hello world
user@host:~$ printf '%08Xn' 1234567890
499602D2nuser@host:~$ 'echo'   'Hello,   world!'
Hello,   world!
user@host:~$
user@host:~$ echo heeeeeeelllo | sed 's/(.)1+/1/g'
yes|head -3
heeeeeeelllo
user@host:~$ yes|head -3
echo ''
y
y
y
user@host:~$ echo ''

user@host:~$ echo 'foo bar baz' | sed 's/bar/BAR/' | sed 's/baz/zap/'
foo BAR zap
user@host:~$

This invokes bash on my system, which I don't think is allowed

Of course, but after re-reading question, I think this don't break any rule (No system, no argument, no eval, source or dot...)

Yes, but in an interresting way: Using detached and invisible session to do the whole job, than, before exiting, dump the whole history on initial console.

I'm fine with this rule abuse. It's clever enough in my opinion - and the question allows clever rule abuse. +1 from me.

Factor (208 characters)
Since the rules doesn't disallow offloading the work to a third party (http://www.compileonline.com/execute_bash_online.php), here is a solution:
USING: arrays http.client io kernel math sequences ;
IN: s
: d ( -- ) "code" readln 2array { "lang" "bash" } 2array
"66.155.39.107/execute_new.php" http-post*
dup length 6 - 86 swap rot subseq write flush d ;

You can write the program as an even shorter one-liner in the repl too (201 chars):
USING: arrays http.client io kernel math sequences ; [ "code" swap 2array { "lang" "bash" } 2array "66.155.39.107/execute_new.php" http-post* dup length 6 - 86 swap rot subseq write flush ] each-line ;

I guess I shouldn't have allowed rule abuse. Oh right, I did. +1 from me - I just wouldn't ever think of this.

Perl, 135 characters
#!perl -n
for(/(?:'.*?'|[^|])+/g){s/'//g for@w=/(?:'.*?'|\S)+/g;open($o=(),'-|')or$i&&open(STDIN,'<&',$i),exec@w,exit;$i=$o}print<$o>

This shell does some stupid things. Start an interactive shell with perl shell.pl and try it:

ls prints in one column, because standard output is not a terminal. The shell redirects standard output to a pipe and reads from the pipe.
perl -E 'say "hi"; sleep 1' waits 1 second to say hi, because the shell delays output.
dd reads 0 bytes, unless it is the first command to this shell. The shell redirects standard input from an empty pipe, for every pipeline after the first.
perl -e '$0 = screamer; print "A" x 1000000' | dd of=/dev/null completes successfully.
perl -e '$0 = screamer; print "A" x 1000000' | cat | dd of=/dev/null hangs the shell!

Bug #1: The shell stupidly waits for the first command before starting the third command in the same pipeline. When the pipes are full, the shell enters deadlock. Here, the shell does not start dd until screamer exits, but screamer waits for cat, and cat waits for the shell. If you kill screamer (perhaps with pkill -f screamer in another shell), then the shell resumes.

perl -e 'fork and exit; $0 = sleeper; sleep' hangs the shell!

Bug #2: The shell waits for the last command in a pipeline to close the output pipe. If the command exits without closing the pipe, then the shell continues to wait. If you kill sleeper, then the shell resumes.

'echo $((2+3))' runs the command in /bin/sh. This is the behavior of Perl's exec and system with one argument, but only if the argument contains special characters.

Ungolfed version
#!perl -n
# -n wraps script in while(<>) { ... }

use strict;
our($i, $o, @w);

# For each command in a pipeline:
for (/(?:'.*?'|[^|])+/g) {
    # Split command into words @w, then delete quotes.
    s/'//g for @w = /(?:'.*?'|\S)+/g;

    # Fork.  Open pipe $o from child to parent.
    open($o = (), '-|') or
        # Child redirects standard input, runs command.
        $i && open(STDIN, '<&', $i), exec(@w), exit;

    $i = $o;  # Input of next command is output of this one.
}

print <$o>;   # Print output of last command.


text:
Thar she blows!
Arrr... Ahoy there, me maties! Unfurl tha' mainsail! Full to starboard! Ah, feel th' wind in yer hair!
Right, me hearties... I be needin' a bit of yer codin' skills! Me crew are a li'l more modernized than meself... I still be preferrin' th' points of th' compass (see here for more info, Arrr...) while me crew are always usin' a headin'... I be wantin' an easy way of convertin' this twaddle they call a headin' into what I be able to understand, Arrr!
What I be needin' is code tha' be takin' input of a number (decimals are okay) such tha' 0 <= the headin' < 360 and it be spittin' out th' answer as th' closest compass point! Arrr!
Here be some examples:
> heading 0.1
North
> heading 11.25
North by East
> heading 22.7
North Northeast
> heading 44.99
Northeast
> heading 91
East
Now, if'n th' headin' ye be givin' be such that it falls exactly in th' middle of two compass points, don' ye be frettin', me hearties... I be expectin' th' code to spit out Between <point 1> and <point 2>, e.g. heading 5.625 will say Between North and North by East
This only be happenin' for a headin' tha' be satisfyin' the equation H = 5.625 + 11.25(N) where H be th' headin' and N be an integer between 0 and 31 inclusive...
Two restrictions tho'...
1) I not be wantin' ye to use arrays for storin' yer data for the points or th' headin's... Tha' be cheatin', sir, an' ye be gettin' a taste of me blunderbuss... This has t' be calculated, jus' like th' old days! Arrr!
2) Shortest code wins, or I'll be makin' ye walk th' plank... Arrr!

50 '(Apostrophe) in a single question. Hats off! :D

Is using an object in javascript with numeric keys cheating? I mean yaarrr! be it cheatin', ya landlubber?

Shouldn't this be "N be an integer between 0 and 31 inclusive"?

@nwellnhof You're right! Updated... :)

@Wasi, you think that's impressive, try typing in pirate! Arrr!

The question is completely unreadable for me! I am not native English speaker!

@sergiol Well, I guess tha' be meanin' ye won' be codin'! Arrr!

I think you should launch a code golf where the goal is to translate your question to orthographically correct English!

Perl 5.10 using substitution, 231 228 226 224
@c=(north,east,south,west);
@q=qw(P PbR P-Q QbP Q QbR R-Q RbP);
sub p{$j=$_[0]>>3&3;$_=$q[7&pop];s/P/$c[$j]/;s/Q/$c[$j+1&2]$c[$j|1]/;s/R/$c[$j+1&3]/;s/b/ by /;ucfirst}
$a=<>/11.25+.5;
say$a==int$a&&'Between '.p($a-1).' and ',p$a

Four newlines added for readability.
Edit: Golfed 2 more bytes using pop. Thanks @Dom Hastings
Edit: 2 bytes less using qw()

I be spendin' way too much time on this here treasure hunt, but here's a solution in Java:
public class Aaaaarrrr {

    public static void main(String[] aaarrrgs) {

        float heading = Float.parseFloat(aaarrrgs[0]);

        final List<String> points = Arrays.asList("North",
                "North by east", "North-northeast", "Northeast by north",
                "Northeast", "Northeast by east", "East-northeast",
                "East by north", "East", "East by south", "East-southeast",
                "Southeast by east", "Southeast", "Southeast by south",
                "South-southeast", "South by east", "South", "South by west",
                "South-southwest", "Southwest by south", "Southwest",
                "Southwest by west", "West-southwest", "West by south", "West",
                "West by north", "West-northwest", "Northwest by west",
                "Northwest", "Northwest by north", "North-northwest",
                "North by west");

        float cp = heading / 360.0f * 32.0f;
        if (cp % 1 == 0.5f)
             System.out.print("Between " + points.get((int)Math.floor(cp)) + " and ");

         System.out.println(points.get(Math.round(cp)));

    }
}

edit If I minimize the above code and make it real ugly it would become this:
Java, 770 chars
import java.util.*;class A{public static void main(String[] r){List<String> l=Arrays.asList("North","North by east","North-northeast","Northeast by north","Northeast","Northeast by east","East-northeast","East by north","East","East by south","East-southeast","Southeast by east","Southeast","Southeast by south","South-southeast","South by east","South","South by west","South-southwest","Southwest by south","Southwest","Southwest by west","West-southwest","West by south", "West","West by north","West-northwest","Northwest by west","Northwest","Northwest by north","North-northwest","North by west");float c=Float.parseFloat(r[0])/360.0f*32.0f;if (c%1==0.5f) System.out.print("Between "+l.get((int)Math.floor(c))+" and ");System.out.println(l.get(Math.round(c)));}}

I'm sure that didn't help me on the "shortest code wins" rule, but since I'm using Java anyway...

I admire the approach, though you're using the Arrays.asList command, pardon me here for my Java ignorance, but isn't that using a storage array? Or is this a sneaky way of introducing the array in the form of a list? ;)

@Jeen, can ye show me wha' ye could get if ye really honker down and reduce tha' code there?

@Eliseod'Annunzio wrt the array, I thought you only meant I couldn't use it to store a mapping between names and heading intervals. This array (list) only stores the actual names. But if that is beyond the rules, I imagine it could be changed to use a switch statement instead (with a few extra chars, unfortunately).
Oh and condensed version of same code added. I'll have a think about further whittling it down by actually changing how it works.

Arrr, fair 'nuff, matey...

Python, 264
n='north'
e='east'
s='south'
w='west'
b=' by '
def f(H):x,y,z=(n,e,s,w,e,s,w,n,n+e,s+e,s+w,n+w)[int(H%360/90)::4];return(x,x+b+y,x+'-'+z,z+b+x,z,z+b+y,y+'-'+z,y+b+x)[int(H%90*4/45)].capitalize()
h=input()+5.625
print h%11.25and f(h)or'Between '+f(h-1)+' and '+f(h)

This uses capitalisation as per the wikipedia page and should work for any number.

Arrr, that be a clever use of a function there...

Arrr Python, 336
A,R,r=int,input()/360.*32,' by #South#north#West#East#south#North#west#east#-#/#Between#and'.split('#')
a=''.join(r[A(c,16)]for c in'6A608A6928A6802A68A6808A4928A402A4A405A4958A1808A18A1805A1958A108A1A107A1957A1705A17A1707A3957A305A3A302A3927A6707A67A6702A6927A607').split('/')
if R%1==.5:print r[11],a[A(R)],r[12],
print a[A(round(R))]

Thanks @Jeen

I be a little confused here @AsksAnyway, what be th' use of tha' there leviathan of a string?
... Arrr...

It "calculates" the names of the compass points. It's a way of reducing the code size.

Perl 5.10, 262 257 254
Somewhat similar to one of the Python solutions:
$n=north;$e=east;$s=south;$w=west;
@d=($n,$n.$e,$e,$s.$e,$s,$s.$w,$w,$n.$w,$n);
sub p{$j=pop;$i=$j>>2;ucfirst(($d[$i],"$d[$i] by $d[$i+2&~1]","$d[$i+1&~1]-$d[$i|1]","$d[$i+1] by $d[$i&~1]")[$j&3])}
$a=<>/11.25+.5;
say$a==int$a&&'Between '.p($a-1).' and ',p$a

Four newlines added for readability.
Edit: Three bytes less thanks to @Dom Hastings

Hey @nwellnhof, Looks pretty comprehensive! You can save a few more chars, removing the ; at the end of sub p and switch shift to pop.

@nwellhoff I didn't know Perl could accept strings without them being in quotes? (re: line 1)

@Eliseod'Annunzio Perl accepts strings without quotes in non-strict mode if they don't clash with function names or reserved words.


text:
Get list of badges on this site that nobody received yet
Make a code that gets list of badges that nobody received yet (for example, by using this website API for badges), and output the sorted list of such badges, with new line after each.
Example output (may be smaller, depending on when you do this challenge):
Archaeologist
Caucus
Constituent
Copy Editor
Deputy
Electorate
Epic
Generalist
Hacker
Legendary
Marshal
Outspoken
Research Assistant
Sheriff
Steward
Strunk & White
Tenacious
Unsung Hero

Smallest code wins.

nice idea, also suspect [data.se] could do it (no answers on that so far) in fact maybe the web query is doing a SQL query at heart...

JavaScript with jQuery (loaded onto SE sites by default), 58
$('.badge',$('.badge-count:not(:has(*))').parent()).text()

Must be run on https://codegolf.stackexchange.com/help/badges. ;)
Strictly conforming output, 116 chars:
[].join.call($('.badge',$('.badge-count:not(:has(*))').parent()).map(function(){return $(this).text()}).sort(),'\n')

Screenshot of console output (click to enlarge):

Is using external libs allowed?

@Ultra jQuery is loaded onto SE sites by default.

Bash, 173 characters
curl "https://api.stackexchange.com/2.1/badges?page="{0..50}"&pagesize=100&order=desc&sort=type&site=codegolf"|gunzip|grep -Po '{"name".*?award_count":0.*?}'|cut -d'"' -f 4

Though you could probably shave some characters off by using url shortening.
WARNING: Note that running this script a couple of times will result in this:
{"error_name":"throttle_violation","error_message":"too many requests from this IP, more requests available in 84495 seconds","error_id":502}

Output for codegolf.SE:
code-golf
Informed
Research Assistant
Caucus
Constituent
Outspoken
Deputy
Vox Populi
Excavator
Analytical
Self-Learner
Hacker
Beta
Legendary
Electorate
Investor
Tenacious
Unsung Hero

EDIT: tweaked it a bit.

Bash - huehuehue. PS is /dev/null really needed here?

You can use curl instead of wget -O-.

Hmm I thought that I had removed the /dev/null which I had for testing.

PHP - 92 86 characters
<?=html_entity_decode(substr(file_get_contents("http://tinyurl.com/q9zlwfr"),12937,190));

Inspired by Victor's solution. Very volatile.

Java - 280 267 260
class A{public static void main(String[]z)throws Exception{String s="";int y;java.io.InputStream x=new java.net.URL("http://tinyurl.com/q9zlwfr").openStream();while((y=x.read())!=-1)s+=(char)y;System.out.println(s.substring(12937,13126).replace("amp;",""));}}

That seems... volatile. If Stack Exchange team would make almost any change to their website (or if my question would be modified), it would return the wrong list. Besides, the list may be not up to date.

Why is the class name so long? Why is the argument to main's name so long? Why is there unnecessary whitespace after InputStream?

@DoorknobofSnow Well noted. These one slipped when I was converting the ungolfed version to a golfed one.

@xfix Yeah, very volatile. That was intentional.

I'm tempted to edit the question by one letter just to troll you :-D

@DoorknobofSnow :-D


text:
Portal Maze Shortest Path
Your goal is to write a program that creates a random 10x10 map using 0, 1, and 2, and finds the shortest path from top-left to bottom-right, assuming that:
0 represents a grass field: anyone can walk on it;
1 represents a wall: you cannot cross it;
2 represents a portal: when entering a portal, you can move to any other portal in the map.
Specs:

The top-left element and the bottom-right one must be 0;
When creating the random map, every field should have 60% chance of being a 0, 30% of being a 1 and 10% of being a 2;
You can move in any adjacent field (even diagonal ones);
Your program should output the map and the number of steps of the shortest path;
If there isn't a valid path that leads to the bottom-right field, your program should output the map only;
You can use any resource you'd like to;
Shortest code wins.

Calculating steps:
A step is an actual movement; every time you change field, you increment the counter.
Output:
0000100200
0100100010
1000000111
0002001000
1111100020
0001111111
0001001000
0020001111
1100110000
0000020100

9

Can't we just produce the program for the shortest path? Generating is another question.

You didn't specify that the random map must be different each time :)

@marinus LoooL! Well, in the specs I wrote the generating chances, so I guess that writing a standard map with 60 0, 30 1 and 10 2 won't be a right solution :P

@MikaëlMayer I guess you've got a point, but I think it would be more challenging like this. Am I wrong?

As this is a code-golf question, the winning criteria is shortest code. What happens if that code is really slow and takes centuries to run?

If it does work, it's ok. Since it's code-golf, only the shortest code wins.

GolfScript, 182 characters
;0`{41 3 10rand?/3%`}98*0`]10/n*n+.[12n*.]*.0{[`/(,\+{,)1$+}*;]}:K~\2K:P+${[.12=(]}%.,,{.{\1==}+2$\,{~;.P?0<!P*3,{10+}%1+{2$1$-\3$+}%+~}%`{2$~0<@@?-1>&2$[~;@)](\@if}++%}/-1=1=.0<{;}*

Examples:
0000001002
1010000001
0011010000
2001020000
0100100011
0110100000
0100000100
0010002010
0100110000
0012000210
6

0000100000
0100000001
1100000000
1011010000
0010001100
0101010200
0000200012
1100100110
0000011001
2201010000
11

0012010000
1000100122
0000001000
0111010100
0010012001
1020100110
1010101000
0102011111
0100100010
2102100110

Mathematica (344)
Bonus: highlighting of the path
n = 10;
m = RandomChoice[{6, 3, 1} -> {0, 1, 2}, {n, n}];
m[[1, 1]] = m[[n, n]] = 0;

p = FindShortestPath[Graph@DeleteDuplicates@Join[Cases[#, Rule[{ij__}, {k_, l_}] /;
      0 < k <= n && 0 < l <= n && m[[ij]] != 1 && m[[k, l]] != 1] &@
   Flatten@Table[{i, j} -> {i, j} + d, {i, n}, {j, n}, {d, Tuples[{-1, 0, 1}, 2]}],
  Rule @@@ Tuples[Position[m, 2], 2]], {1, 1}, {n, n}];

Grid@MapAt[Style[#, Red] &, m, p]
If[# > 0, #-1] &@Length[p]

I create the graph of all possible movies to neighbor vertices and add all possible "teleports".

Mathematica, 208 202 chars
Base on David Carraher and ybeltukov's solutions. And thanks to ybeltukov's suggestion.
m=RandomChoice[{6,3,1}->{0,1,2},n={10,10}];m〚1,1〛=m〚10,10〛=0;Grid@m
{s,u}=m~Position~#&/@{0,2};If[#<∞,#]&@GraphDistance[Graph[{n/n,n},#<->#2&@@@Select[Subsets[s⋃u,{2}],Norm[#-#2]&@@#<2||#⋃u==u&]],n/n,n]

Nice, +1! Further optimization: n/n instead of n/10 :)

Nice streamlining. And you print out the map right away.

And 〚 〛 for brackets (it is correct unicode symbols)

Can you explain the selection criterion, Norm[# - #2] & @@ # < 2 || # \[Union] u == u &

@DavidCarraher Norm[# - #2] & @@ # < 2 means the distance between two points is less then 2, so they must be adjacent. # ⋃ u == u means both points are in u.

Python 3, 279
Some Dijkstra variant. Ugly, but golfed as much as I could...
from random import*
R=range(10)
A={(i,j):choice([0,0,1]*3+[2])for i in R for j in R}
A[0,0]=A[9,9]=0
for y in R:print(*(A[x,y]for x in R))
S=[(0,0,0,0)]
for x,y,a,c in S:A[x,y]=1;x*y-81or print(c)+exit();S+=[(X,Y,b,c+1)for(X,Y),b in A.items()if a+b>3or~-b and-2<X-x<2and-2<Y-y<2]

Sample Run
0 1 1 1 0 0 1 0 1 0
0 0 0 1 0 1 0 1 0 0
0 1 2 1 2 1 0 0 1 0
0 1 0 1 0 0 0 0 0 1
0 1 0 1 0 0 1 0 0 1
0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 1 0 1
1 0 0 1 0 0 1 1 1 0
0 0 0 0 1 0 0 0 0 1
0 1 2 1 0 1 1 0 0 0
10

Python 3 (695)
import random as r
if __name__=='__main__':
    x=144
    g,t=[1]*x,[]
    p=lambda i:12<i<131 and 0<i%12<11
    for i in range(x):
        if p(i):
            v=r.random()
            g[i]=int((v<=0.6 or i in (13,130)) and .1 or v<=0.9 and 1 or 2)
            if g[i]>1:t+=[i]
            print(g[i],end='\n' if i%12==10 else '')
    d=[99]*x
    d[13]=0
    n = list(range(x))
    m = lambda i:[i-1,i+1,i-12,i+12,i-13,i+11,i+11,i+13]
    while n:
        v = min(n,key=lambda x:d[x])
        n.remove(v)
        for s in m(v)+(t if g[v]==2 else []):
            if p(s) and g[s]!=1 and d[v]+(g[s]+g[v]<4)<d[s]:
                d[s]=d[v]+(g[s]+g[v]<3)
    if d[130]<99:print('\n'+str(d[130]))

Dijkstra !
Example output:
0000202000
2011000111
0000002000
0101001000
0000100110
1110100101
0020101000
0011200000
1010101010
0000001000

6

if __name__ == "__main__" and the corresponding indent isn't necessary

Mathematica 316 279 275
The basic object is a 10x10 array with approximately 60 0's, 30 1's and 10 2's.
The array is used to modify a 10x10 GridGraph, with all edges connected.  Those nodes which correspond to cells holding 1 in the array are removed from the graph.  Those nodes "holding 2's"  are all connected to each other.  Then the Shortest Path is sought between vertex 1 and vertex 100.  If such a path does not exist, the map is returned; if such a path does exist, the map and the shortest path length are shown.
m = Join[{0}, RandomChoice[{6, 3, 1} -> {0, 1, 2}, 98], {0}];
{s,t,u}=(Flatten@Position[m,#]&/@{0,1,2});
g=Graph@Union[EdgeList[VertexDelete[GridGraph@{10,10},t]],Subsets[u,{2}]
/.{a_,b_}:>a \[UndirectedEdge] b];
If[IntegerQ@GraphDistance[g,1,100],{w=Grid@Partition[m,10],
Length@FindShortestPath[g,1,100]-1},w]

Sample Run:

"You can move in any adjacent field (even diagonal ones)".

Python (1923)
Backtracking Search
Admittedly not the shortest or the most efficient, although there is some memoization present.
import random
l = 10
map = [
    [(lambda i: 0 if i < 7 else 1 if i < 10 else 2)(random.randint(1, 10))
     for i in range(0, l)]
    for i in range(0, l)
    ]
map[0][0] = map[l-1][l-1] = 0
print "\n".join([" ".join([str(i) for i in x]) for x in map])

paths = {}
def step(past_path, x, y):
    shortest = float("inf")
    shortest_path = []

    current_path = past_path + [(x, y)]
    pos = map[x][y]
    if (x, y) != (0, 0):
        past_pos = map[past_path[-1][0]][past_path[-1][1]]

    if (((x, y) in paths or str(current_path) in paths)
        and (pos != 2 or past_pos == 2)):
        return paths[(x, y)]
    elif x == l-1 and y == l-1:
        return ([(x, y)], 1)

    if pos == 1:
        return (shortest_path, shortest)
    if pos == 2 and past_pos != 2:
        for i2 in range(0, l):
            for j2 in range(0, l):
                pos2 = map[i2][j2]
                if pos2 == 2 and (i2, j2) not in current_path:
                    path, dist = step(current_path, i2, j2)
                    if dist < shortest and (x, y) not in path:
                        shortest = dist
                        shortest_path = path
    else:
        for i in range(x - 1, x + 2):
            for j in range(y - 1, y + 2):
                if i in range(0, l) and j in range(0, l):
                    pos = map[i][j]
                    if pos in [0, 2] and (i, j) not in current_path:
                        path, dist = step(current_path, i, j)
                        if dist < shortest and (x, y) not in path:
                            shortest = dist
                            shortest_path = path
    dist = 1 + shortest
    path = [(x, y)] + shortest_path
    if dist != float("inf"):
        paths[(x, y)] = (path, dist)
    else:
        paths[str(current_path)] = (path, dist)
    return (path, dist)

p, d = step([], 0, 0)
if d != float("inf"):
    print p, d

Wow, now that's a character count for a code golf! I think your ball landed in the rough.

Haha yeah I didn't bother golfing the code or trying to find the shortest implementation, but put the character count up so people would know they could ignore this solution. It just seemed like a fun problem.

JavaScript (541)
z=10
l=[[0]]
p=[]
f=[[0]]
P=[]
for(i=0;++i<z;)l[i]=[],f[i]=[]
for(i=0;++i<99;)P[i]=0,l[i/z|0][i%z]=99,f[i/z|0][i%z]=(m=Math.random(),m<=.6?0:m<=.9?1:(p.push(i),2))
f[9][9]=0
l[9][9]=99
Q=[0]
for(o=Math.min;Q.length;){if(!P[s=Q.splice(0,1)[0]]){P[s]=1
for(i=-2;++i<2;)for(j=-2;++j<2;){a=i+s/z|0,b=j+s%z
if(!(a<0||a>9||b<0||b>9)){q=l[a][b]=o(l[s/z|0][s%z]+1,l[a][b])
if(f[a][b]>1){Q=Q.concat(p)
for(m=0;t=p[m];m++)l[t/z|0][t%z]=o(l[t/z|0][t%z],q+1)}!f[a][b]?Q.push(a*z+b):''}}}}for(i=0;i<z;)console.log(f[i++])
console.log((k=l[9][9])>98?"":k)

Graph generation happens in the first five lines. f contains the fields, p holds the portals. The actual search is implemented via BFS.
Example output:
> node maze.js
[ 0, 0, 0, 0, 1, 0, 0, 0, 2, 0 ]
[ 0, 1, 1, 0, 0, 1, 0, 0, 0, 2 ]
[ 0, 0, 0, 1, 0, 0, 0, 0, 1, 0 ]
[ 1, 1, 1, 0, 2, 2, 0, 1, 0, 1 ]
[ 1, 1, 0, 0, 0, 0, 1, 0, 0, 0 ]
[ 1, 1, 0, 0, 1, 0, 0, 0, 1, 1 ]
[ 0, 0, 1, 1, 0, 1, 0, 0, 2, 0 ]
[ 0, 0, 1, 0, 1, 2, 0, 1, 0, 1 ]
[ 1, 0, 0, 0, 1, 1, 1, 0, 1, 1 ]
[ 0, 1, 0, 0, 0, 0, 0, 0, 1, 0 ]

>node maze.js
[ 0, 0, 0, 0, 1, 0, 1, 0, 0, 1 ]
[ 0, 2, 0, 1, 1, 2, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ]
[ 0, 0, 0, 1, 2, 1, 1, 0, 1, 0 ]
[ 2, 0, 1, 0, 2, 2, 2, 0, 1, 0 ]
[ 1, 0, 0, 0, 1, 0, 0, 0, 1, 0 ]
[ 0, 0, 1, 0, 0, 1, 0, 1, 0, 0 ]
[ 0, 1, 2, 0, 0, 0, 0, 0, 0, 1 ]
[ 1, 0, 2, 1, 0, 1, 2, 0, 0, 1 ]
[ 0, 1, 2, 0, 0, 0, 0, 0, 0, 0 ]
5

Python, 314
import random,itertools as t
r=range(10)
a,d=[[random.choice([0]*6+[1]*3+[2])for i in r]for j in r],eval(`[[99]*10]*10`)
a[0][0]=a[9][9]=d[0][0]=0
for q,i,j,m,n in t.product(r*10,r,r,r,r):
 if a[m][n]!=1and abs(m-i)<2and abs(n-j)<2or a[i][j]==a[m][n]==2:d[m][n]=min(d[i][j]+1,d[m][n])
w=d[9][9]
print a,`w`*(w!=99)

It's a disgusting implementation of Bellman-Ford. This algorithm is O(n^6)! (Which is okay for n=10)

The map looks really ugly. Does this work if more than 10 steps are needed?

@WolframH Of course: http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm#Proof_of_correctness

I could make it print '\n'.join(map(str,a)); I did print a for the sake of golf.

I didn't doubt the correctness of the algorithm :-). I just hadn't realized that you loop often enough (which you do; r*10 has 100 elements).

Yeah. Actually 100 is overkill; 99 is all that is needed.