text:
Finding limits of functions
A limit in math determines the value that a function f(x) approaches as x gets closer and closer to a certain value.
Let me use the equation f(x)=x^2/x as an example.
Obviously, f(x) is undefined if x is 0 (x=0, x2=0, 0/0 is undefined).
But, what happens when we calculate f(x) as x approaches 0?
x=0.1, f(x)=0.01/0.1 = 0.1
x=0.01, f(x)=0.0001/0.01 = 0.01
x=0.00001, f(x)=0.0000000001/0.00001 = 0.00001
We can easily see that f(x) is approaching 0 as x approaches 0.
What about when f(x)=1/x^2, and we approach 0?
x=0.1, f(x)=1/0.01=100
x=0.01, f(x)=1/0.0001=10000
x=0.00001, f(x)=1/0.0000000001=10000000000
As x approaches 0, f(x) approaches positive infinity.
You will be given two things in whatever input format you like:

f(x) as an eval-able string in your language
a as a floating point

Output the value that f(x) approaches when x approaches a. Do not use any built-in functions that explicitly do this.
Input Limitations:

The limit of f(x) as x approaches a will always exist.
There will be real-number values just before and just after f(a): you will never get f(x)=sqrt(x), a=-1 or anything of the sort as input.

Output Specifications:

If f(x) approaches positive or negative infinity, output +INF or -INF, respectively.
If f(a) is a real number, then output f(a).

Test Cases:
f(x)=sin(x)/x, a=0; Output: 1
f(x)=1/x^2, a=0; Output: +INF
f(x)=(x^2-x)/(x-1), a=1; Output: 1
f(x)=2^x, a=3; Output: 8

Shortest code wins. Good luck!

What would you like to have displayed in the case of f(x)=1/x and a=0

@Matt: You will never get that input. The limit of f(x) as x approaches a will always exist.

A mathematician wouldn't say "the limit exists" in a case like 1/x² | ₓ→₀, but I suppose it's clear what you mean.

@leftaroundabout: What would they call it then? Indeterminate? :) I'd like to know.

At least in standard analysis they'd just say "the function diverges for x → 0". The destinction between positive and negative infinity is quite cumbersome (and hardly worth it) when doing proper mathematical proofs.

Python 146 185
Figured I'd post the obvious answer before anyone else does.
Note, reads two lines from stdin with f(x) on the first
and a on the second.
Edit: Made it actually work, as per beary's comment
Edit 2: i is much smaller, so there are much fewer inputs that it should fail for.
from math import*
f,a,i=eval("lambda x:"+input()),eval(input()),2e-308
while 1:
 try:
     r=str(f(a+i)).upper()
     if'NAN'!=r:break
 except:
     i*=-2
print('I'==r[0]and'+'+r or r)

Can you put in the input format? Also, you seem to have neglected the sign on the INF (it should be +inf or -inf). I really don't mind "obvious" answers, as long as it works without any functions calculating it.

This is probably being overly picky, but this does not work for f(x) = 1/x, a = -1*10^-161 and f(x) = 1/(x-1*10^-161), a = 0

Darn, I guess I'll have to make i the smallest float possible, which should bandadge those problems.

python provides a machine epsilon as sys.float_info.epsilon, which is probably more accurate for what you're attempting

Thanks for that ardnew, though I think you meant sys.float_info.min? i in my code is nearly that on my machine (saving a few characters, sacrificing portability).

@walpen: No, the min value will provide the smallest possible representable number in the FPS, but your calculated values a+min may not necessarily be representable. Using epsilon will guarantee a value a+e that is not equal to a

Unfortunately, epsilon will give the wrong answer for the cases Matt gave (at least with the very basic algorithm I used), which is why starting at about min and working up to larger values seems to work in more cases. (Though the opposite, starting at epsilon and working down to the smallest representable in that case, is probably a more optimal algorithm).

@walpen i see. your code seems to be shorter then! (i cant get it to run any tests (saved source in file.py, run python file.py?))

Ex input: echo "1/x" > input; echo 0 >> input; cat input | python3 file.py

C, 402 bytes
Plenty of room for golfing, just proof of concept to begin with :P
Compiles under clang, osx.
Note: For linux you may have to change the code to use something like: "ld -shared f.o -o f.so -lm"
#include<dlfcn.h>
#include<stdio.h>
float e,r;
main(int i,char**v){
    // create and compile temporary c file for 'f(x)'
    // note: include offset within function
    FILE*s=fopen("f.c","w");
    fprintf(s,"#include<math.h>\nfloat f(float x){x+=%s;return %s;}",v[2],v[1]);
    fclose(s);
    system("cc -fPIC -c f.c;ld -bundle f.o -o f.so -lm");
    float(*f)(float)=dlsym(dlopen("f.so",0),"f");

    for(i=0;1;e=(e==0)?1e-37:e*2){
        r=f(e);
        if(isinf(r))i=1;else if(!isnan(r)){
            i?printf("%cINF\n",r>0?43:45):printf("%f\n",r);
            break;
        }
    }
}

Run as:
./a.out "sin(x)/x" 0
./a.out "1/(x*x)" 0
./a.out "(x*x-x)/(x-1)" 1
./a.out "pow(2,x)" 3

Results:
1.000000
+INF
1.000000
8.000000


text:
RPN calculator without pointers
Me and some other students were at a bar discussing programming languages, in particular the C programming language. At some point a first year student said he didn't need no damn pointers. Another student said that he couldn't use arrays either since "they're basically pointers".
This led to a programming challenge:
Implement a reverse polish notation calculator in C without using arrays and pointers.
Description
You must implement a RPN calculator that

operates on integers,
supports addition (+),
supports multiplication (*).

Your implementation

must not use pointers or arrays
you may use structs
the input is read from stdin
your lexer may use pointers and arrays (but it shouldn't be needed)
when EOF is read then print the top of the stack
the behavior can be as undefined as you want for malformed input
should be in a language sufficiently c-like that the "no-pointers and no-arrays" restriction has a sensible interpretation (please elaborate if you think people may not get it)

The lexer could have a signature a la thisNote: this is not taken from my own code. Please tell me if there's an error or it looks unreasonable
typedef enum {
  val,
  op,
  eof
} TYPE;

typedef enum {
  add,
  mul
} OPERATION;

typedef struct {
  TYPE type;
  union {
    int val;
    OPERATION op;
  } dat;
} token;

token next();

A solution using a stack with push() and pop() could look something like this:
token t;
while ((t = next()).type != eof) {
  switch (t.type) {
    case val:
      push(t.dat.val);
    case op:
      switch (t.dat.op) {
        case add:
          int v1 = pop();
          int v2 = pop();
          push(v1+v2);
        case mult:
          int v1 = pop();
          int v2 = pop();
          push(v1*v2);
      }
    case eof:
      printf("Result: %d\n", pop());
  }
}

Other languages than C are also accepted, but the constraints should be comparable. It is hard to state the constraints in a way that fits all languages, but something like »all used data structures must have fixed size and fixed "depth"«. If there's any doubt please ask in the comments.

I have a solution that I can post. After cleaning up the code a bit. I wrote it the morning after while hungover.

I don't see [language-agnostic] as compatible with a language tag such as [c] so I stripped one one them in keeping with the text "Implement a reverse polish notation calculator in C without using arrays and pointers."

Of course, now I notice that Peter did a Java implementation. ::sigh::

I see what you mean. The reason I put the C tag was because the problem is primarily defined in terms of C concepts. However, I will accept solutions in other languages (such as java) that satisfy "comparable" constraints, hence the [language-agnostic] tag. It is a bit difficult, I think, to define the constraints in a completely language agnostic way. I am therefore not sure if the [language-agnostic] tag applies here. I don't think [c] and [language-agnostic] are incompatible as such, though. Also, I can't sleep :-/

I think "c-like langauges" would be a good phrase and then [language-agnostic] is reasonable. Heck, you could even leave the [c]. And then it would be clear that Peter was playing fair. Is that in keeping with your intent?

By the way, the part you were quoting was the original challenge posed to the first year student. I can see how that could be "misinterpreted". Please edit the post if you can think of a better formulation. I don't want to restrict it to C only.

should I cheat, and use forth, where the answer would be . (1 char): test: 1 2 3 4 5 * * * * 2 +  ok.  . 122   ok

That's using the forth interpreter. You have to make a program that given a string of integers, + and * outputs the result. I tried the following: echo 1 2 + | gforth -e '.' which (obviously) doesn't work.

This is an intriguing puzzle. I may try it when I get home. As an aside, that first year student is so naïve in thinking he will get away with not learning pointers. :)

"first solution" is not a very nice winning criterion. Can't you make it a popularity contest?

@JanDvorak yea, that may have been a better idea. At the time I thought this would be a difficult task. You're welcome to restate the task (if the rules allow it - you have my permission in any case).

@ReyCharles Actually, now the second answer has 3 more votes than the first, so it should be declared winner

In tcl if you have namespace path {::tcl::mathop}, then you can do it directly without implementing anything: https://codegolf.stackexchange.com/a/106284/29325

I’m voting to close this question because not using pointers or arrays, and having a "lexer", is a completely unobservable requirement. This question would not be acceptable if posted today.

I am voting to leave this question open, as it is a legacy question which has been on the site for nearly a decade at this point, has been shared on the site twitter, and has multiple answers. This question should not be used as the basis for any future questions.

This is pretty ugly, but I think it works. I've avoided using null to make it as obvious as possible that the references could be passed on the stack. I may rewrite this in the morning to have an extra token type of NULL.
import java.io.IOException;

public class RPN
{
    public static void main(String[] args) throws IOException {
        Token result = depth0();
        if (result.type != Token.EOF) throw new IllegalStateException("Bad input");
        System.out.println(result.value);
    }

    private static Token depth0() throws IOException {
        Token tok = Lexer.lex();
        if (tok.type != Token.NUMBER) throw new IllegalStateException("Bad input");
        return depth1(tok);
    }

    private static Token depth1(Token s1) throws IOException {
        while (true) {
            Token s2 = Lexer.lex();
            switch (s2.type) {
                case Token.EOF:
                    return new Token(Token.EOF, s1.value);
                case Token.NUMBER:
                    s1 = depth2(s1, s2);
                    if (s1.type == Token.EOF) return s1;
                    break;
                default:
                    throw new IllegalStateException("Bad input");
            }
        }
    }

    private static Token depth2(Token s1, Token s2) throws IOException {
        while (true) {
            Token s3 = Lexer.lex();
            switch (s3.type) {
                case Token.EOF:
                    return new Token(Token.EOF, s2.value);
                case Token.OPERATOR:
                    return new Token(Token.NUMBER, s3.value == Token.OP_PLUS ? s1.value + s2.value : s1.value * s2.value);
                case Token.NUMBER:
                    s2 = depth2(s2, s3);
                    if (s2.type == Token.EOF) return s2;
                    break;
                default:
                    throw new IllegalArgumentException("Bug in lexer");
            }
        }
    }

    static class Lexer {
        private static boolean hasPushback = false;
        private static int pushback;

        private static int read() throws IOException {
            if (hasPushback) {
                hasPushback = false;
                return pushback;
            }

            // Assume input is in ASCII
            return System.in.read();
        }

        private static void pushback(int ch) {
            if (hasPushback) throw new IllegalStateException();
            hasPushback = true;
            pushback = ch;
        }

        public static Token lex() throws IOException {
            while (true) {
                int ch = read();
                switch (ch) {
                    case -1:
                        return new Token(Token.EOF, Token.EOF);
                    case '-':
                        return new Token(Token.NUMBER, -lexInteger(0));
                    case '0': case '1': case '2':
                    case '3': case '4': case '5':
                    case '6': case '7': case '8':
                    case '9':
                        return new Token(Token.NUMBER, lexInteger(ch - '0'));
                    case '+':
                        return new Token(Token.OPERATOR, Token.OP_PLUS);
                    case '*':
                        return new Token(Token.OPERATOR, Token.OP_TIMES);
                    default:
                        // Whitespace or comment
                        break;
                }
            }
        }

        private static int lexInteger(int value) throws IOException {
            while (true) {
                int ch = read();
                if (ch < '0' || ch > '9') {
                    pushback(ch);
                    return value;
                }

                value = value * 10 + (ch - '0');
            }
        }
    }

    static class Token {
        public static final int NUMBER = 0;
        public static final int OPERATOR = 1;
        public static final int EOF = -1;

        public static final int OP_PLUS = 0;
        public static final int OP_TIMES = 1;

        public final int type;
        public final int value;

        public Token(int type, int value) {
            this.type = type;
            this.value = value;
        }
    }
}

Sample usage:
$ javac RPN.java && java RPN <<<"1 2 3 4 5 ****2+"
122

Looks good! It's a bit more clever than my own solution :-) I will review it again tomorrow, it's a bit late here.

Congratulations! You win. I hope you found the puzzle fun.

This is a stand-alone C version, it doesnt require any external lexer. It works recursivly, like ratchet freaks solution.
All characters that are not +, *, - or numbers are treated as spaces. A - is treated as a space if it is not directly followed by a number.
#include <stdio.h>

int rpn(int n1, int n2) {
        int c, sign = 1, skip = 0;
        if(n1 < 0) sign = -1;
        do {
                c = getchar();
                if(c == '+') return n1+n2;
                if(c == '*') return n1*n2;
                if(c >= 48 && c <= 57) {
                        if(!skip) n1 = n1 * 10 + sign * (c - 48);
                        else n1 = rpn(sign * (c - 48), n1);
                } else {
                        skip = 1;
                        sign = 1;
                }
                if(c == '-') sign = -1;
        } while(c != EOF);
        return n1;
}

void main() {
        printf("%d\n", rpn(0, 0));
}

That's pretty cool! I never thought "inlining" the lexer would make it so much shorter.

use recursion:
enum TYPE {
  val,
  op,
  eof
};

enum OPERATION {
  add,
  mul
};

struct token{
  TYPE type;
  union {
    int val;
    OPERATIOIN op;
  }
}

token parse(int val1,int val2){
    token t;
    //next() is the lexer
    while((t=next()).type!=TYPE.EOF){
        if(t.type==TYPE.op){//calculate the value
            return token(TYPE.val,t.op==add?val1+val2:val1*val2);
        }else if(t.type==TYPE.val){
            //recurse and pass the top 2 values on the stack
            t= parse(val2,t.val);
            if(t.type==TYPE.eof)return t;
            else val2=t.val;
        }else{
             return token(eof,val2);
        }
    }
}

I returned token so I can stop the recursion cleanly

I don't think this quite works. You're missing the return statement in case of reading an EOF, and you need to handle the bootstrapping cases when you don't have two items on the stack.

First of all, what language is this? Secondly, how would you run this? Also, what Peter Taylor said.

it's D it's run with parse(0,0) (completely valid ;P ) and I forgot to handle the eof case...

2 uses of pointers are collected at the top, and are permitted by the rules as these are a necessary part of I/O at the level of file descriptors. Uses C99 compound literals and POSIX low-level file operations, reading and writing one byte at a time. There is also one implicit FILE * returned by tmpfile() which is immediately converted by fileno() to an integer.
This code implements the RPN calculator as a Semi-Thue system that works like a queue. ("Thue" is pronounced /too-ay/, like "2 A".) It uses iteration and a tempfile to evaluate the formula left-to-right, examining up to 3 tokens, possibly reducing, and writing into a new temp file for the next iteration.
It waits for enter before each pass. Terminate with an interrupt signal (ctrl-C). A simple extension would allow it to detect when a string is no longer reducing from one pass to the next, and terminate.
#define Read(f,x) read(f,&x,1)
#define Write(f,x) write(f,&x,1),write(1,&x,1)

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#include <unistd.h>

typedef union {
    enum tag {number, oper, eof} tag;
    struct {
        enum tag tag;
        int val;
    } num;
    struct {
        enum tag tag;
        char val;
    } op;
} token;

token input(int in){
    char b;
    int a;
    char o;
    a=0;
    o=0;
    do {
        if (!Read(in,b)) {
            return (token){.tag=eof};
        }
        if (b=='\n') {
            return (token){.tag=eof};
        }
        if (b>='0'&&b<='9') {
            a*=10;
            a+=b-'0';
        } else if (b=='+'||b=='*') {
            o=b;
        }
    } while(b!=32);

    if (o)
        return (token){.op.tag=oper, .op.val=o};
    else
        return (token){.num.tag=number, .num.val=a};
}

output(int out, token t){
    char b;
    int c;
    switch(t.tag){
    case number:
        c=t.num.val>9?(int)floor(log10((double)t.num.val)):0;
        //b = c + '0'; Write(out,b);
        for( ; c>=0; c--) {
            b = '0' + (t.num.val/(int)pow(10.0, c)) % 10;
            Write(out,b);
        }
        break;
    case oper:
        b = t.op.val;
        Write(out,b);
        break;
    case eof:
        b = '\n';
        Write(out,b);
        return;
    }
    b = 32;
    Write(out,b);
}

int rpn(int in, int out) {
    token x,y,z;
    char b;
read_x:
    //b='X';write(1,&b,1);
    x = input(in);
    //b='A'+x.tag;write(1,&b,1);
    switch (x.tag){
    case eof:
        output(out, x);
        return EOF;
    case oper:
        output(out, x);
        goto read_x;
    }
read_y:
    //b='Y';write(1,&b,1);
    y = input(in);
    //b='A'+y.tag;write(1,&b,1);
    switch (y.tag){
    case eof:
        output(out, x);
        output(out, y);
        return EOF;
    case oper:
        output(out, x);
        output(out, y);
        goto read_x;
    }
read_z:
    //b='Z';write(1,&b,1);
    z = input(in);
    //b='A'+z.tag;write(1,&b,1);
    switch(z.tag){
    case eof:
        output(out, x);
        output(out, y);
        output(out, z);
        return EOF;
    case number:
        output(out, x);
        x.num.val = y.num.val;
        y.num.val = z.num.val;
        goto read_z;
    case oper:
        switch(z.op.val){
        case '+':
            x.num.val = x.num.val + y.num.val;
            break;
        case '*':
            x.num.val = x.num.val * y.num.val;
            break;
        }
        output(out, x);
        goto read_x;
    }
    return 0;
}

main(){
    int i=0,o;
    char b;
    token t;
    do {
        o = fileno(tmpfile());
        rpn(i,o);
        i = o;
        lseek(i, 0, SEEK_SET);
    } while(Read(0,b));
}

In action:
./2A
1 2 3 4 5 6 7 8 9 10 + + + + + + + + +
1 2 3 4 5 6 7 8 19 + + + + + + + +

1 2 3 4 5 6 7 27 + + + + + + +

1 2 3 4 5 6 34 + + + + + +

1 2 3 4 5 40 + + + + +

1 2 3 4 45 + + + +

1 2 3 49 + + +

1 2 52 + +

1 54 +

55

55

55

RProgN, 2 Bytes
do

Evaluates as RProgN. Any valid RPN is valid Syntax is RProgN by design, And RProgN is stack based. However, this prints the entire stack after running, not just the top of the stack. This can be resolved with:
do p w{ }

Which prints the top of the stack, then empties the stack.
Try it online

source: Stack Exchange

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

sort: votes


text:
Balance chemical equations!
Bernd is a high school student who has some problems in chemistry. In class he has to design chemical equations for some experiments they are doing, such as the combustion of heptane C7H16:

C7H16 + 11O2 → 7CO2 + 8H2O

Since mathematics isn't exactly Bernd's strongest subject, he often has a hard time finding the exact ratios between the pro- and educts of the reaction. Since you are Bernd's tutor, it is your job to help him! Write a program, that calculates the amount of each substance needed to get a valid chemical equation.
Input
The input is a chemical equation without amounts. In order to make this possible in pure ASCII, we write any subscriptions as ordinary numbers. Element names always start with a capital letter and may be followed by a minuscule. The molecules are separated with + signs, an ASCII-art arrow -> is inserted between both sides of the equation:
Al+Fe2O4->Fe+Al2O3

The input is terminated with a newline and won't contain any spaces. If the input is invalid, your program may do whatever you like.
You may assume, that the input is never longer than 1024 characters. Your program may either read the input from standard input, from the first argument or in an implementation defined way at runtime if neither is possible.
Output
The output of your program is the input equation augmented with extra numbers. The number of atoms for each element must be the same on both sides of the arrow. For the example above, a valid output is:
2Al+Fe2O3->2Fe+Al2O3

If the number for a molecule is 1, drop it. A number must always be a positive integer. Your program must yield numbers such that their sum is minimal. For instance, the following is illegal:
40Al+20Fe2O3->40Fe+20Al2O3

If there is no solution, print
Nope!

instead. A sample input that has no solution is
Pb->Au

Testcases
Input->Output
C7H16+O2->CO2+H2O
C7H16+11O2->7CO2+8H2O

Al+Fe2O3->Fe+Al2O3
2Al+Fe2O3->2Fe+Al2O3

Pb->Au
Nope!

This is code-golf, so shortest code wins!
Your program must terminate in reasonable time for all reasonable inputs

I could be wrong, but this seems like a natural candidate for a programming challenge rather code golf.

The algorithm is not so dificult once you think about it. Hint: Vectors.

I once wrote a chemical equation solver on my TI-89 graphing calculator, using the built-in solve( function and eval( to interpret the input :)

@mellamokb why don't you post it, you'll get an upvote from me for originality

http://www.webqc.org/balance.php?reaction=Al%2BFe2O4%3DAl2O3%2BFe says that Al+Fe2O4->Fe+Al2O3 is 8Al+3Fe2O4->4Al2O3+6Fe

@baby-rabbit: The equation was wrong. Fixed.

"Since you are Bernds tutor, it is your job to help him!" - I would have thought a tutor should be teaching Bernd to think for himself, rather than write software for him so he doesn't have to :P

The equation under Input is still wrong, saying Al+Fe2O4 instead of Fe2O3

@KuilinLi It is not wrong, just different.

What about ion charges? Cu2+ +2e- ->Cu ?

@devRicher Out of scope.

C (gcc), 442 bytes
u,t[99];char*s,*m[99];c,v[99][99];i,j,n;
b(k){if(k<0)for(n=j=0;!n&&j<u;j++)for(i=0;i<=c;i++)n+=t[i]*v[i][j];else for(t[k]=0;n&&t[k]++<30;)b(k-1);}
main(int r,char**a){for(s=m[0]=a[1];*s;){if(*s==45)r=0,s++;if(*s<65)m[++c]=++s;j=*s++;if(*s>96)j=*s+++j<<8;for(i=0,t[u]=j;t[i]-j;i++);u+=i==u;for(n=0;*s>>4==3;)n=n*10+*s++-48;n+=!n;v[c][i]=r?n:-n;}b(c);for(i=0,s=n?"Nope!":a[1];*s;putchar(*s++))s==m[i]&&t[i++]>1?printf("%d",t[i-1]):0;putchar(10);}

Try it online!
Ungolfed version
// element use table, then once parsed reused as molecule weights
u,t[99];

// molecules
char*s,*m[99]; // name and following separator
c,v[99][99]; // count-1, element vector

i,j,n;

// brute force solver, n==0 upon solution - assume at most 30 of each molecule
b(k){
    if(k<0)for(n=j=0;!n&&j<u;j++)for(i=0;i<=c;i++)n+=t[i]*v[i][j]; // check if sums to zero
    else for(t[k]=0;n&&t[k]++<30;)b(k-1); // loop through all combos of weights
}

main(int r,char**a){
    // parse
    for(s=m[0]=a[1];*s;){
        // parse separator, advance next molecule
        if(*s==45)r=0,s++;
        if(*s<65)m[++c]=++s;
        // parse element
        j=*s++;
        if(*s>96)j=*s+++j<<8;
        // lookup element index
        for(i=0,t[u]=j;t[i]-j;i++);
        u+=i==u;
        // parse amount
        for(n=0;*s>>4==3;)n=n*10+*s++-48;
        n+=!n;
        // store element count in molecule vector, flip sign for other side of '->'
        v[c][i]=r?n:-n;
    }
    // solve
    b(c);
    // output
    for(i=0,s=n?"Nope!":a[1];*s;putchar(*s++))s==m[i]&&t[i++]>1?printf("%d",t[i-1]):0;
    putchar(10);
}
```

+1 this is much more respectable than the pres. debate

Try using commas as statement separators to avoid curly braces. Also try replacing if-then-else-constructs with ternary operators to shorten the code. t[i]>1?printf("%s",t[i]):0; is one byte shorter. Also: m[0] is the same as *m.

Wolfram Language (Mathematica), 510 bytes
I employed the augmented chemical composition matrix approach described in
L.R.Thorne, An innovative approach to balancing chemical - reaction equations : a simplified matrix - inverse technique for determining the matrix null space. Chem.Educator, 2010, 15, 304 - 308.
One slight tweak was added:  I divided the transpose of the null-space vector by the greatest common divisor of the elements to ensure integer values in any solutions.  My implementation does not yet handle cases where there is more than one solution to balancing the equation.
b@t_ :=Quiet@Check[Module[{s = StringSplit[t, "+" | "->"], g = StringCases, k = Length,
  e, v, f, z, r},
e = Union@Flatten[g[#, _?UpperCaseQ ~~ ___?LowerCaseQ] & /@ s];v = k@e;
s_~f~e_ := If[g[s, e] == {}, 0, If[(r = g[s, e ~~ p__?DigitQ :> p]) == {}, 1,
   r /. {{x_} :> ToExpression@x}]];z = k@s - v;
r = #/(GCD @@ #) &[Inverse[Join[SparseArray[{{i_, j_} :> f[s[[j]], e[[i]]]}, k /@ {e, s}],
Table[Join[ConstantArray[0, {z, v}][[i]], #[[i]]], {i, k[#]}]]][[All, -1]] &
   [IdentityMatrix@z]];
Row@Flatten[ReplacePart[Riffle[Partition[Riffle[Abs@r, s], 2], " + "],2 Count[r,_?Negative]->" -> "]]],"Nope!"]

Try it online!
Analysis
It works by setting up the following chemical composition table, consisting of chemical species by elements, to which an addition nullity vector is added (becoming the augmented chemical composition table:

The inner cells are removed as a matrix and inverted, yielding.

The right-most column is extracted, yielding:

{-(1/8), -(11/8), 7/8, 1}

Each element in the vector is divided by the gcd of the elements (1/8), giving:

{-1, -11, 7, 8}

where the negative values will be placed on the left side of the arrow.
The absolute values of these are the numbers needed to balance the original equation:

don't forget to add the exclamation point!

:} ok, and I upped the character count

I think you mean the right-hand column, not the left-hand one. I appreciate the explanation (+1) but I do wonder: if it weren't the case that the number of molecules is one more than the number of elements, how do you pad? Off to read the paper now.

For some reason, I only came across your comment today.  Yes, I did mean "right-hand column".   So much time has passed since I worked on this that I cannot see (or remember) where padding is used. Sorry.

Python 2, 879 bytes
import sys,re
from sympy.solvers import solve
from sympy import Symbol
from fractions import gcd
from collections import defaultdict

Ls=list('abcdefghijklmnopqrstuvwxyz')
eq=sys.argv[1]
Ss,Os,Es,a,i=defaultdict(list),Ls[:],[],1,1
for p in eq.split('->'):
 for k in p.split('+'):
  c = [Ls.pop(0), 1]
  for e,m in re.findall('([A-Z][a-z]?)([0-9]*)',k):
   m=1 if m=='' else int(m)
   a*=m
   d=[c[0],c[1]*m*i]
   Ss[e][:0],Es[:0]=[d],[[e,d]]
 i=-1
Ys=dict((s,eval('Symbol("'+s+'")')) for s in Os if s not in Ls)
Qs=[eval('+'.join('%d*%s'%(c[1],c[0]) for c in Ss[s]),{},Ys) for s in Ss]+[Ys['a']-a]
k=solve(Qs,*Ys)
if k:
 N=[k[Ys[s]] for s in sorted(Ys)]
 g=N[0]
 for a1, a2 in zip(N[0::2],N[1::2]):g=gcd(g,a2)
 N=[i/g for i in N]
 pM=lambda c: str(c) if c!=1 else ''
 print '->'.join('+'.join(pM(N.pop(0))+str(t) for t in p.split('+')) for p in eq.split('->'))
else:print 'Nope!'

Try it online!
Could be much less than 880, but my eyes are killing me already...

Python 2, 640 bytes
previous byte counts: 794, 776, 774, 765, 759, 747, 735, 734, 720, 683, 658, 655, 654, 653, 651, 640
The second indentation level is only a tab, the third is a tab then a space.
To be honest, this is jadkik94's answer, but so many bytes were shaved, I had to do it. Tell me if I can shave any bytes off!
from sympy import*
import sys,re
from sympy.solvers import*
from collections import*
P=str.split
L=map(chr,range(97,123))
q=sys.argv[1]
S,O,a,i,u,v=defaultdict(list),L[:],1,1,'+','->'
w=u.join
for p in P(q,v):
 for k in P(p,u):
  c=L.pop(0)
  for e,m in re.findall('([A-Z][a-z]*)(\d*)',k):
   m=int(m or 1)
   a*=m
   S[e][:0]=[c,m*i],
 i=-1
Y=dict((s,Symbol(s))for s in set(O)-set(L))
Q=[eval(w('%d*%s'%(c[1],c[0])for c in S[s]),{},Y)for s in S]+[Y['a']-a]
k=solve(Q,*Y)
if k:
 N=[k[Y[s]]for s in sorted(Y)]
 g=gcd(N[:1]+N[1::2])
 print v.join(w((lambda c:str(c)*(c!=1))(N.pop(0)/g)+str(t)for t in P(p,u))for p in P(q,v))
else:print'Nope!'

Try it online!

save three bytes: ''.join(map(chr,range(97,122))) :D

:(, that doesn't work. However, map(chr,range(97,123)) works for 12 bytes saved.

oh right! it's python 2!

JavaScript, 682 bytes

x=>{m=1;x.split(/\D+/g).map(i=>i?m*=i:0);e=new Set(x.replace(/\d+|\+|->/g,"").match(/([A-Z][a-z]*)/g));e.delete``;A=[];for(let z of e){t=x.split`->`;u=[];for(c=1;Q=t.shift();c=-1)Q.split`+`.map(p=>u.push(c*((i=p.indexOf(z))==-1?0:(N=p.substring(i+z.length).match(/^\d+/g))?N[0]:1)));A.push(u)}J=A.length;for(P=0;P<J;P++){for(i=P;!A[i][P];i++);W=A.splice(i,1)[0];W=W.map(t=>t*m/W[P]);A=A.map(r=>r[P]?r.map((t,j)=>t-W[j]*r[P]/m):r);A.splice(P,0,W)}f=e.size;if(!A[0][f])return"Nope!";g=m=-m;_=(a,b)=>b?_(b,a%b):a;c=[];A.map(p=>c.push(t=p.pop())&(g=_(g,t)));c.push(m);j=x.match(/[^+>]+/g);return c.map(k=>k/g).map(t=>(t^1?t:"")+(z=j.shift())+(z.endsWith`-`?">":"+")).join``.slice(0,-1);}

This is a much more golfed (decades of characters!) of Kuilin's answer. Might be noncompeting because certain JS features postdate the challenge.

Javascript, 705 bytes
(non-competing, some features postdate the challenge)
Other solutions all had elements of brute-forcing. I tried for a more deterministic approach by representing the chemical equation as a set of linear equations, and then solving using the Gauss-Jordan algorithm to take the reduced row-echelon form of that matrix. In order to isolate out the trivial case where everything is zero, I assume that one of the elements is a constant number - and that number is determined by just all the numbers multiplied together, in order to not have fractions. Then as a final step we'll divide each by the gcd to satisfy the last condition.
Ungolfed:

function solve(x) {
 //firstly we find bigNumber, which will be all numbers multiplied together, in order to assume the last element is a constant amount of that
 bigNumber = 1;
 arrayOfNumbers = new Set(x.split(/\D+/g));
 arrayOfNumbers.delete("");
 for (let i of arrayOfNumbers) bigNumber *= parseInt(i);

 //first actual step, we split into left hand side and right hand side, and then into separate molecules
 //number of molecules is number of variables, number of elements is number of equations, variables refer to the coefficients of the chemical equation
 //note, the structure of this is changed a lot in the golfed version since right is the same as negative left
 left = x.split("->")[0].split("+");
 righ = x.split("->")[1].split("+");
 molecules = left.length + righ.length;

 //then let's find what elements there are - this will also become how many equations we have, or the columns of our matrix minus one
 //we replace all the non-element characters, and then split based on the uppercase characters
 //this also sometimes adds a "" to the array, we don't need that so we just delete it
 //turn into a set in order to remove repeats
 elems = new Set(x.replace(/\d+|\+|->/g,"").match(/([A-Z][a-z]*)/g));
 elems.delete("");

 rrefArray = [];//first index is rows, second index columns - each row is an equation x*(A11)+y*(A21)+z*(A31)=A41 etc etc, to solve for xyz as coefficients
 //loop thru the elements, since for each element we'll have an equation, or a row in the array
 for (let elem of elems) {
  buildArr = [];
  //loop thru the sides
  for (let molecule of left) {
   //let's see how many of element elem are in molecule molecule
   //ASSUMPTION: each element happens only once per molecule (no shenanigans like CH3COOH)
   index = molecule.indexOf(elem);
   if (index == -1) buildArr.push(0);
   else {
    index += elem.length;
    numberAfterElement = molecule.substring(index).match(/^\d+/g);
    if (numberAfterElement == null) buildArr.push(1);
    else buildArr.push(parseInt(numberAfterElement));
   }
  }
  //same for right, except each item is negative
  for (let molecule of righ) {
   index = molecule.indexOf(elem);
   if (index == -1) buildArr.push(0);
   else {
    index += elem.length;
    numberAfterElement = molecule.substring(index).match(/^\d+/g);
    if (numberAfterElement == null) buildArr.push(-1);
    else buildArr.push(parseInt(numberAfterElement)*(-1));
   }
  }
  rrefArray.push(buildArr);
 }

 //Gauss-Jordan algorithm starts here, on rrefArray
 for (pivot=0;pivot<Math.min(molecules, elems.size);pivot++) {
  //for each pivot element, first we search for a row in which the pivot is nonzero
  //this is guaranteed to exist because there are no empty molecules
  for (i=pivot;i<rrefArray.length;i++) {
   row = rrefArray[i];
   if (row[pivot] != 0) {
    workingOnThisRow = rrefArray.splice(rrefArray.indexOf(row), 1)[0];
   }
  }
  //then multiply elements so the pivot element of workingOnThisRow is equal to bigNumber we determined above, this is all to keep everything in integer-space
  multiplyWhat = bigNumber / workingOnThisRow[pivot]
  for (i=0;i<workingOnThisRow.length;i++) workingOnThisRow[i] *= multiplyWhat
  //then we make sure the other rows don't have this column as a number, the other rows have to be zero, if not we can normalize to bigNumber and subtract
  for (let i in rrefArray) {
   row = rrefArray[i];
   if (row[pivot] != 0) {
    multiplyWhat = bigNumber / row[pivot]
    for (j=0;j<row.length;j++) {
     row[j] *= multiplyWhat;
     row[j] -= workingOnThisRow[j];
     row[j] /= multiplyWhat;
    }
    rrefArray[i]=row;
   }
  }
  //finally we put the row back
  rrefArray.splice(pivot, 0, workingOnThisRow);
 }

 //and finally we're done!
 //sanity check to make sure it succeeded, if not then the matrix is insolvable
 if (rrefArray[0][elems.size] == 0 || rrefArray[0][elems.size] == undefined) return "Nope!";

 //last step - get the results of the rref, which will be the coefficients of em except for the last one, which would be bigNumber (1 with typical implementation of the algorithm)
 bigNumber *= -1;
 gcd_calc = function(a, b) {
  if (!b) return a;
  return gcd_calc(b, a%b);
 };
 coEffs = [];
 gcd = bigNumber;
 for (i=0;i<rrefArray.length;i++) {
  num = rrefArray[i][molecules-1];
  coEffs.push(num);
  gcd = gcd_calc(gcd, num)
 }
 coEffs.push(bigNumber);
 for (i=0;i<coEffs.length;i++) coEffs[i] /= gcd;

 //now we make it human readable
 //we have left and right from before, let's not forget those!
 out = "";
 for (i=0;i<coEffs.length;i++) {
  coEff = coEffs[i];
  if (coEff != 1) out += coEff;
  out += left.shift();
  if (left.length == 0 && righ.length != 0) {
   out += "->";
   left = righ;
  } else if (i != coEffs.length-1) out += "+";
 }
 return out;
}
console.log(solve("Al+Fe2O4->Fe+Al2O3"));
console.log(solve("Al+Fe2O3->Fe+Al2O3"));
console.log(solve("C7H16+O2->CO2+H2O"));
console.log(solve("Pb->Au"));

Golfed

s=x=>{m=1;x.split(/\D+/g).map(i=>i!=""?m*=i:0);e=(new Set(x.replace(/\d+|\+|->/g,"").match(/([A-Z][a-z]*)/g)));e.delete("");A=[];for(let z of e){t=x.split("->");u=[];for(c=1;Q=t.shift();c=-1)Q.split("+").map(p=>u.push(c*((i=p.indexOf(z))==-1?0:(N=p.substring(i+z.length).match(/^\d+/g))?N[0]:1)));A.push(u)}J=A.length;for(P=0;P<J;P++){for(i=P;!A[i][P];i++);W=A.splice(i,1)[0];W=W.map(t=>t*m/W[P]);A=A.map(r=>!r[P]?r:r.map((t,j)=>t-W[j]*r[P]/m));A.splice(P,0,W)}f=e.size;if (!A[0][f])return "Nope!";g=m=-m;_=(a,b)=>b?_(b,a%b):a;c=[];A.map(p=>c.push(t=p.pop())&(g=_(g,t)));c.push(m);j=x.match(/[^+>]+/g);return c.map(k=>k/g).map(t=>(t==1?"":t)+(z=j.shift())+(z.endsWith("-")?">":"+")).join("").slice(0,-1);}

console.log(s("Al+Fe2O4->Fe+Al2O3"));
console.log(s("Al+Fe2O3->Fe+Al2O3"));
console.log(s("C7H16+O2->CO2+H2O"));
console.log(s("Pb->Au"));

Noncompeting, as some features postdate the challenge.

Oh wow I didn't notice how old this was. Thanks!

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

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


text:
Storing a DNS name as compactly as possible in memory (preferably in C#)
What is the most compact way to encode/save DNS names in memory?
For example, storing "www.google.com" as a string in .NET will result in the object being encoded as UTF-16, and it will consume twice as much memory as plain ASCII... but for the purpose of storing DNS names, ASCII is overkill.
The only characters that are needed are:

A..Z  (case insensitive)
0..9
Hyphen
underscore
period
Asterisk (not legal DNS, but used in ACLs such as *.google.com) always as a leading character, never elsewhere.

A total of 40 characters.. which fits within single byte with plenty room to spare.
My code golf question/challenge is what is the most compact way to store a string of characters in memory and maximizing in memory storage?
The inspiration for this challenge came from this blog entry.

How do you win the competition?

You meant UTF-16 for the .NET framework. In UTF-8, this name would take up just as much as ASCII.

Try http://cs.stackexchange.com/ - there's probably already a question about basic information theory which would tell you all you need to know.

http://en.wikipedia.org/wiki/Kolmogorov_complexity?

Actually, underscores are not allowed in DNS names. RFC 3696

As stated this looks like a question for Stack Overflow (that is, it is a question). CodeGolf.SE is a plce for playing certain programming games. It would be essentially trivial to turn this into a [code-golf]---you just add the tag (and probably the one @beary suggests as well) and resign yourself to getting answer many languages. But I am closing until that is done just to encourage you to read the FAQ before posting to a new Stack Exchange site. Flag when you are ready for this to be re-opened.

You could interpret it as a base 39 number. Since only the first character can be an asterisk, you can encode it as the sign. If i use the characters as digits in the order you named them, www.google.com would be 10903065870001232914011 in decimal and 24f0e6f41d8ecd3a65b in hex, which could be stored in 10 bytes.
*.google.com would be -310664672884413873 in decimal and fbb04c2040762a4f in hex, if you store it in 8 bytes.

Oh, that's easy. You just zip it.

gzip on a file containing www.google.com gives 42 bytes.

Ah... when you use Windows' built in zipping routines, you get a 132 byte file. Oh well.


text:
Find the Pisano Period
The Fibonacci sequence is a well know sequence in which each entry is the sum of the previous two and the first two entries are 1.  If we take the modulo of each term by a constant the sequence will become periodic.  For example if we took decided to compute the sequence mod 7 we would get the following:
1 1 2 3 5 1 6 0 6 6 5 4 2 6 1 0 1 1 ...

This has a period of 16.  A related sequence, called the Pisano sequence, is defined such that a(n) is the period of the fibonacci sequence when calculated modulo n.
Task
You will should write a program or function that when given n will compute and output the period of the Fibonacci sequence mod n.  That is the nth term in the Pisano sequence.
You must only support integers on the range 0 < n < 2^30
This is a code-golf competition so you should aim to minimize the size of your source code as scored by bytes.
Test cases
1  -> 1
2  -> 3
3  -> 8
4  -> 6
5  -> 20
6  -> 24
7  -> 16
8  -> 12
9  -> 24
10 -> 60
11 -> 10
12 -> 24

Limitation to 2^30 may ensure all intermediate values are less than 2^31 but it still doesn't guarantee that the Pisano Period will fit within a 32-bit signed integer. (I presume that's the reason for your limitation?) Pisano Periods can be significantly larger than their n. For example, the Pisano Period of 6 is 24. Powers of 10 above 100 come out 50 percent larger than n.

Pigeonhole principle says that f(i),f(i+1) can take at most n^2 values mod n.  Thus, n limited to 2^30 could wind up producing a period of up to 2^60.  Restricting n <= 2^16 would give P(n) <= 2^32.

@boothby I'm not quite sure I understand what you're saying, or if it's even properly addressing the same problem I am. Could you explain a bit further, perhaps with additional links? Feel free to pull me into chat if needed.

@Iszi Observe that f(i+2) = f(i+1)+f(i), so the 'state' of a machine looping over the period can be described with a pair of integers mod n.  There are at most n^2 states, so the period is at most n^2.  Oh!  Wikipedia claims that the period is at most 6n.  Nevermind my triviality.

Wait, where does it say 6n? I must have missed it. In any case, I'm pretty sure the math still says that 6n will blow out a signed 32-bit integer before we hit 2^30.

True, the Pisano period may be larger than 2^31.  Would it be better to modify the question to be as I originally intended (to allow 32-bit integers) or to keep it as I originally asked meaning the Fibonnacci numbers can be stored in 32 bits but the period itself may be greater?

https://oeis.org/A001175

"Eh, Paisano?" -Mario

GolfScript (28 25 24 23 chars)
~1.{(2$+}{.@+2$%}/+\-,)

Takes input in stdin, leaves it on stdout (or the stack, if you want to further process it...)
This correctly handles the corner cases (Demo).
As a point of interest to GolfScript programmers, I think this is the first program I've written with an unfold which actually came out shorter than the other approaches I tried.

GolfScript, 24 characters
~:&1.{.2$+&%.2$(|}do](-,

Next iteration of a GolfScript implementation. The second version now also handles 1 correctly. It became quite long but maybe someone can find a way to shorten this version. You can try above version online.

Does this handle input 1 correctly?

@PeterTaylor Nope, didn't test that corner case. Back to the drawing board.

@PeterTaylor The new code also works for input 1 - and still only 24 chars.

Python, 188 132 101 95 87 characters
n=input()
s=[]
a=k=0
b=1
while s[:k]!=s[k:]or k<1:s+=[a%n];k=len(s)/2;a,b=b,a+b
print k

Usage
$ echo 10 | python pisano.py
60

For example:
$ for i in {1..50}; do; echo $i | python pisano.py; done
1
3
8
6
20
24
16
12
24
60
10
24
28
48
40
24
36
24
18
60
16
30
48
24
100
84
72
48
14
120
30
48
40
36
80
24
76
18
56
60
40
48
88
30
120
48
32
24
112
300

Thanks, beary605, for the additional golfing!

You may want to count your chars again. My count of your response is below your count of your response.

@David: Are you counting whitespace?  I just double-checked (by catting to wc -c and I get the same number.

I use a routine furnished by Wolfram Research. It counts necessary white space, I think.

if k>0 and s[0:k]==s[k:]:break can be changed to if s and s[:k]==s[k:]:break. You can also cut down significantly by removing the iterator, changing the for loop to while 1:, and performing a,b=a,a+b at the end of the while loop.

@Strigoides: Thanks!  I've updated the code.

I went ahead and made an edit that avoids having to check for an empty list, since it would have been difficult to explain in a comment

Python 90 85 96 94 90 82
n=input();c=[1,1];a=[]
while(c in a)<1%n:a+=[c];c=[c[1],sum(c)%n]
print len(a)or 1

Edit: Implemented suggestions by beary and primo

85: a.append(c) -> a+=[c], while loop can be put onto a single line, ((n>1)>>(c in a)) -> (n>1)>>(c in a)

append actually has a different functionality than +=. Thanks for the tips though.

I think it works the same way in this case.

(n>1)>>(c in a) -> (c in a)<1%n for 3 bytes. And I agree with beary about the append. Whether you append a reference to c, or extend a by the value of c, it's exactly the same either way (as you immediately destroy your reference to c anyway).

Ah ok, my mistake was that I was using a+=c instead of a+=[c]

Mathematica 73
p = {1, 0}; j = 0; q = p;
While[j++; s = Mod[Plus @@ p, n]; p = RotateLeft@p; p[[2]] = s; p != q]; j

PHP - 61 57 bytes
<?for(;1<$a.$b=+$a+$a=!$i+++$b%$n+=fgets(STDIN););echo$i;

This script will erroneously report 2 for n=1, but all other values are correct.
Sample I/O, a left-truncable series where π(n) = 2n + 2 :
$ echo 3 | php pisano.php
8
$ echo 13 | php pisano.php
28
$ echo 313 | php pisano.php
628
$ echo 3313 | php pisano.php
6628
$ echo 43313 | php pisano.php
86628
$ echo 543313 | php pisano.php
1086628
$ echo 4543313 | php pisano.php
9086628
$ echo 24543313 | php pisano.php
49086628

1<$a.$b=+$a+$a=!$i+++$b%$n+=fgets(STDIN)
Oh god, that's some order of operation exploitation right there.

Husk, 9 bytes
LU_2M`%İf

Try it online!
Explanation
I'm not sure if I've ever used U with a negative argument before.
LU_2M`%İf  Implicit input, say n=8.
       İf  Infinite list of Fibonacci numbers:
             [1,1,2,3,5,8,13,21..
    M      Map
     `%    modulo n:
             [1,1,2,3,5,0,5,5,2,7,1,0,1,1,2..
 U_2       Cut at the start of first repeated sublist of length 2 (here [1,1]):
             [1,1,2,3,5,0,5,5,2,7,1,0]
L          Length: 12

PowerShell: 98
Golfed code:
for($a,$b=0,(1%($n=read-host))){$x++;if($a+$b-eq0-or("$a$b"-eq10)){$x;break}$a,$b=$b,(($a+$b)%$n)}

Ungolfed, with comments:
for
(
    # Start with $a as zero, and $b as 1%$n.
    # Setting $b like this at the start helps catch the exceptional case where $n=1.
    $a,$b=0,(1%
    (
        # Grab user input for n.
        $n=read-host
    ))
)
{
    # Increasing the counter ($x) and testing for the end of the period at the start ensures proper output for $n=1.
    $x++;

    # Test to see if we've found the end of the Pisano Period.
    if
    (
        # The first part catches $n=1, since $a and $b will both be zero at this point.
        $a+$b-eq0-or
        (
            # A shorter way of testing $a-eq1-and$b-eq0, which is the end of a "normal" Pisano Period.
            "$a$b"-eq10
        )
    )
    {
        # Pisano Period has reached its end. Output $x and get out of the loop.
        $x;break
    }

    # Pisano Period still continues, perform operation to calculate next number.
    # Works pretty much like a Fibonacci sequence, but uses ($a+$b)%$n for the new $b instead.
    # This takes advantage of the fact we don't really need to track the actual Fibonacci numbers, just the Fibonacci pattern of %$n.
    $a,$b=$b,(($a+$b)%$n)
}

# Variable cleanup - not included in golfed code.
rv n,a,b,x

Notes:
I'm not sure exactly what the maximum reliable limit is for $n with this script. It's quite possibly less than 2^30, as $x could possibly overflow an int32 before $n gets there. Besides that, I haven't tested the upper limit myself because run times for the script already hit around 30 seconds on my system for $n=1e7 (which is only a bit over 2^23). For the same reason, I'm not quickly inclined to test and troubleshoot whatever additional syntax may be needed to upgrade the variables to uint32, int64, or uint64 where needed in order to expand this script's range.

Sample output:
I wrapped this in another for loop:
for($i=1;;$i++)

Then set $n=$i instead of =read-host, and changed the output to "$i | $x" to get an idea of the script's general reliability. Here's some of the output:
1 | 1
2 | 3
3 | 8
4 | 6
5 | 20
6 | 24
7 | 16
8 | 12
9 | 24
10 | 60
11 | 10
12 | 24
13 | 28
14 | 48
15 | 40
16 | 24
17 | 36
18 | 24
19 | 18
20 | 60

...
9990 | 6840
9991 | 10192
9992 | 624
9993 | 4440
9994 | 1584
9995 | 6660
9996 | 1008
9997 | 1344
9998 | 4998
9999 | 600
10000 | 15000
10001 | 10212
10002 | 3336
10003 | 5712
10004 | 120
10005 | 1680
10006 | 10008
10007 | 20016
10008 | 552
10009 | 3336
10010 | 1680

Sidenote: I'm not really sure how some Pisano Periods are significantly shorter than $n. Is this normal, or is something wrong with my script? Nevermind - I just remembered that, after 5, Fibonacci numbers quickly become much larger than their place in the sequence. So, this makes total sense now.

Perl, 75, 61, 62 + 1 = 63
$k=1%$_;$a++,($m,$k)=($k,($m+$k)%$_)until$h{"$m,$k"}++;say$a-1

Usage
$ echo 8 | perl -n -M5.010 ./pisano.pl
12

Ungolfed
$k = 1 % $_;
$a++, ($m, $k) = ($k, ($m + $k) % $_) until $h{"$m,$k"}++;
say $a - 1

+1 byte for -n flag. Shaved off 13 bytes thanks to Gabriel Benamy.

You can get rid of $n=<>; (-6) and replace it with the -n flag (+1), then all instances of $n can be replaced with $_.  You can use -M5.010 for free, which lets you use the say command instead of print (-2).  Modifier while statements do not need parentheses around the condition (-2).  Instead of @{[%h]}/2, you can have a counter $a++, before ($m,$k)= and then just have say$a-1 at the end (-2).  Instead of "$m,$k" use $m.$k (-2).  This should come out to $k=1%$_;$a++,($m,$k)=($k,($m+$k)%$_)while!$h{$m.$k}++;say$a-1 with the -n flag, for 61 + 1 = 62 bytes.

Clearly I'm not as clever with Perl as I thought I was. Thanks for the tips.

There are a lot of useful pointers in the Tips for golfing in Perl thread!  Good luck! ^^

Actually, I was wrong -- you need "$m,$k" instead of $m.$k, (+2), but you can save 1 byte by changing while!$h to until$h (-1).  Sorry!

Hm? Under what input does $m.$k fail? It seemed to work on my end.

60 yields 77 but it should be 120.  At least, it did for me.

APL (Dyalog Extended), 21 bytes
{≢(⍵|1⌽+\)⌂traj⍵|1 1}

Try it online!
An anonymous function (dfn) that takes n as its right argument.
How it works
{≢(⍵|1⌽+\)⌂traj⍵|1 1}  ⍝ Anonymous function; Input ⍵←n
{                1 1}  ⍝ Two ones (initial two values of Fibonacci)
               ⍵|      ⍝ Modulo n (to handle special case)
  (      )⌂traj        ⍝ Repeat and collect until the same value appears...
     1⌽+\              ⍝   (a,b) → (a+b,a)
   ⍵|                  ⍝   Modulo n
 ≢                     ⍝ Count the iterations before the same value appears

Clojure, 102 bytes
Not too exciting, iterates the formula until we reach back [1 1] (I hope this is always the case). Special handling of (f 1) as it converges to [0 0].
#(if(< % 2)1(+(count(take-while(fn[v](not=[1 1]v))(rest(iterate(fn[[a b]][b(mod(+ a b)%)])[1 1]))))1))

05AB1E, 13 bytes
∞.Δ∞ÅfI%sô3£Ë

Try it online or verify all test cases.
Explanation:
∞.Δ            # Find the first positive integer which is truthy for:
   ∞           #  Push a positive infinite list
    Åf         #  Get the n'th Fibonacci number of each value `n` in this list
      I%       #  Take modulo the input on each Fibonacci number
        s      #  Swap so the current integer is at the top of the stack
         ô     #  Split the infinite modular Fibonacci list into parts of that size
          3£   #  Only leave the first 3 parts
            Ë  #  And check if all three sublist parts are the same
               # (after which the result is output implicitly)

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


text:
Dice from Changing Random Generator
Introduction
You are given a random integer generator with the following implementation

The first invocation always returns 1.
The second invocation returns a random integer between 1 and 2.
The third invocation returns a random integer between 1 and 3.
The nth invocation returns a random integer between 1 and n, inclusive.

Based on the above function, write a random dice generator that is perfectly random, returning a value between 1 and 6 (inclusive) with equal probability.
Rules

Your program/function should result in a random integer between 1 and 6, inclusive, in some usable form, i.e., to standard output or as a function return value.
The ascending random number generator above can be defined as a "free" function in your program (i.e., doesn't count toward your character count), or a separate script/program that is executed as needed, assuming the state (n) is persistent between calls.
Assume that no more than 1000 dice rolls will ever be requested in a single use case of your program, and the initial random number generator can be reset to 1 at the end of 1000 dice rolls to avoid overflow of n.
Your program may not use any other source of random numbers except the ascending random generator defined above.  You may of course request multiple random numbers from the random number generator for each single dice roll output.
This is code-golf, so winner is shortest answer or most votes in the event of a tie.  If you can generate 1000 dice rolls using less than 1000 generated random numbers, give yourself a 10-point efficiency bonus.

Example
./asc-rand
1 # random integer between 1 and 1
./asc-rand
1 # random integer between 1 and 2
./asc-rand
3 # random integer between 1 and 3
./asc-rand
4 # random integer between 1 and 4

# dice-gen generates random dice based on output of asc-rand program.
./dice-gen
3
./dice-gen
6
./dice-gen
5
./dice-gen
1

Is the program iterate(6):b=asc-rand(); print b illegal or does it not work? I might be misunderstanding the third rule.

@beary605: The random number generator can only be reset after the entire 1000 dice rolls, not between every dice roll.  The only reason I mention that is so dealing with possible overflows on the value returned by the random number generator is not one of the concerns in this challenge. Edit: I clarified the purpose of the rule, hope it helps.

When you say "random number" do you mean "random integer" or "random (truncated) real number"?  Perhaps there is some convention that I am not aware of.

@DavidCarraher: Very good point.  I was meaning random integer, and I see that's not clear.  I will update the question.  Edit: Updated.

Are we allowed to ask the randomizer how many times it has generated random numbers? I was under the impression that we could not.

@Matt: You can assume that when your program is invoked the very first time, the randomizer generates 1.  After that, you can only know if you keep track yourself of the number of times you have invoked the randomizer.

J - 13 char
This makes the same assumptions as Golfscript: that the number of dice is in stdin and we list the dice rolls that are to come out.
r=:1+?  NB. free random function
r>:i.".1!:1]1

Explained by explosion:
r=:1+?           NB. r(x) = 1 + a random number between 0 and n-1
           ]1    NB. input file handle
       1!:1      NB. read in a string
     ".          NB. convert to integer
 >:i.            NB. make a list of numbers, from 1 to that integer
r                NB. apply the random function

If that is somehow unsatisfactory, here is a longer, 21-char program, that can be called with f'' to generate random numbers, featuring a state and everything.
r=:1+?  NB. free random function
c=:0
f=:3 :'r c=:1+c'

K analogues: free random function r:{*1_draw x}, stdin version (10 char) r'1+!. 0:` , function version (14 char) c:0;f:{r@c+:1} called by f[].

Python, 31 chars
Similarly to scleaver, define the generator like this:
from random import randint
n=0
def r():
    global n;n+=1
    return randint(1,n)

Then a function to return dice rolls:
D=lambda:eval('r(),'*6)[-1]%6+1

Call D() any time you need a uniformly random dice roll.

Ah, clever use of eval, I like it.

Scala 23
def s={r;r;r;r;r;r%6+1}

The method r can be (approx.) implemented like this:
var cnt = 0
val rnd = new util.Random

def r = {
  cnt %= 1000
  cnt += 1
  rnd.nextInt (cnt)
}

a rough test:
scala> (1 to 6).map (i => ((1 to 600) map (_=>s)).filter (_ == i).size)
res26: scala.collection.immutable.IndexedSeq[Int] = Vector(110, 105, 91, 96, 106, 102)

Every 6th call should produce an equal distribution over the 6 values, so I throw away 5.

GolfScript (15 chars)
This assumes that the number of rolls required is supplied on stdin and lists that many results to stdout.
# The free increasing random function
0:N;{N):N rand)}:r;

~{r{;r}5*6%)n}*

Online demo
While I could get the 10 point bonus for using fewer than 1000 rolls to generate 1000 numbers, it would cost me far more than 10 characters. The trivial approach of extracting suitable entropy when N is a multiple of a power of 2 or 3 falls well short because the number of results available mod 3 is only 333 + 111 + 37 + 12 + 4 + 1 = 498. Therefore it's necessary to take a sample-and-reject approach. Using this approach you can get an expected 2242 rolls from 1000 calls to r, but there's extra overhead from the book-keeping and base is a very long function name.

"and base is a very long function name" You apparently don't use Mathematica.  We get such wonders as NegativeBinomialDistribution, ExponentialGeneratingFunction, MathieuCharacteristicExponent, InverseFourierSequenceTransform, and SemialgebraicComponentInstances. :-)

Python 65 63
i=7
while i>5:[R()for x in range(9)];i=int(`R()`[-1])
print i+1

The function R() is the ascending randomizer.
Usage:
$ ./rollDice.py
3
$ ./rollDice.py
5

Why not get rid of your for loop and just call R once before your while loop?

@KeithRandall The number I return as my dice roll is the last digit of the number that the ascending generator returns. I need to make 10 calls to the ascending generator to ensure equal probabilities for all possible digits.

Why 10 calls? In principle, if the generator random, shouldn't each call offer equal probability for any of the (ten) digits?  Of course, in practice, you can only expect to approach equal counts for each of the numbers.

@DavidCarraher The generator returns random numbers from 1 to n where n is the number of times you have called it. I'm looking at the last digit of this returned number. If n is not an integer multiple of 10 the probability will not be uniform. For example: If n=13 the probabilities will break down as follows: 1/9 for rolls 1,5,6 and 2/9 for rolls 2,3,4

@Matt: I assumed R() was returning a float and you were grabbing the least-significant digit.  Now that it has been clarified that R() returns an integer, it makes sense.

Python, 56
r is defined as:
from random import randint
n=0
def r(z):
    global n;n+=1
    return randint(1,n)

the dice generator d:
import math;d=lambda:math.ceil(6.*r(r(r(r(r(r(0))))))/n)

usage, eg, for 100 rolls:
for i in range(100):print d()

you can probably delete the import math if you replace math.ceil(...) with int(...)+1

I would, but it would produce 7 as a possible output.

Oh, yeah. I missed that.

mellamokb clarified a question I had about the ascending randomizer. You aren't allowed to ask it for n.

Mathematica 51
The random number generator, r, is reset by setting the global variable, n to 1.
n = 1; r[c_] := RandomInteger[{1, c}]

Code
Not in the running for the shortest code...
h := (n++; If[n < 4 \[Or] (y = r@n) > 6 Quotient[n, 6], h, y~Mod~6 + 1])

Usage
t = Table[h, {60000}];
n
SortBy[Tally[t], First]

60000 rolls of the dice required 60031 calls to h.
Tally shows the breakdown by numbers 1-6.

60031
{{1, 9923}, {2, 9966}, {3, 10016}, {4, 10028}, {5, 10009}, {6, 10058}}

Perl, 22 or 45
Implementation of the ascending random number generator:
my $n=0;
sub r { $n++; return 1+int(rand$n); }

Generating:
#copy of the Scala solution; short code; uses 6N rolls
sub s{r;r;r;r;r;1+r%6}
#more efficient implementation, uses approximately 6+N+lnN rolls
sub roll { do{$a=r-1}while($a>$n-$n%6);return 1+(1+$a)%6 }

Testing out:

n number   chisquare
1 10001867 0.348569
2 10004853 2.355161
3 9994395  3.141602
4 10000177 0.003133
5 9999227  0.059753
6 9999481  0.026936
T 60000000 5.935154
60000000 dice rolls took 60000042 calls to r and 570.432735 seconds

JavaScript (Node.js), 35 bytes
//random number generating function
g=1;f=()=>(1+g>1000?g++:5*Math.random())|0

i=0;while(i++<5)f();t=()=>f()%6+1|0

Try it online!

x86 opcode, 15 bytes
f:  mov cx, 6
    call r ; return in AX
    loop $-3
    cwd
    div word [f+1]
    inc dx
    ret ; return in DX

Apparently this is a low quality post ?

GolfScript, 8 bytes
f;3f*f(-

Try it online!
It pops the generator once, then gets rid of the result. Then it rolls f2, and multiplies it by 3 (3 or 6), then subtracts f3-1 (0, 1, 2) which results in (3-2, 3-1, 3-0) or (6-2, 6-1, 6-0) W5.
Golfscript and the random function existed before this question was posted, so is a legal submission.
This is the run-only-once submission. If you need to run it several times in one call,
GolfScript, 12 bytes
f;3f*f-)0:i;

Try it online!
This resets your i call to 0 so it resets accordingly. This TIO shows 50 random results.

C (gcc), 31 bytes
f(i){for(i=5;i--;)c;i=~-c%6+1;}

Every 6 calls, the probability of every number between 1 and 6 inclusive being generated is equal.
c is #defined as a call to a function that generates the perfect random numbers.
Try it online!


text:
m3ph1st0s's programming puzzle 3 (C): “Easy bug”
This is the 3rd of my series of C/C++ puzzles; in case you missed the first 2 they are here:
(1) m3ph1st0s's programming puzzle 1 (C++)
(2) m3ph1st0s's programming puzzle 2 (C++): "Call hard!"
I must say that my puzzles are 100% original. If not, I will always state so in the text.
 My 3rd puzzle has 2 parts as follows:
Puzzle 3.1
This part (3.1) is not an original puzzle of mine, it is collected from some internet page I've read a while ago. I use it here as a starting point and a warm-up for you. Solve this one and then move on to the 2nd part.
Some one tried to print the "+" sign 20 times and came up with the following program:
#include <stdio.h>
int main() {
   int i;
   int n = 20;
   for( i = 0; i < n; i-- )
      printf("+");
   return 0;
}

The fact that it did not have the expected result is obvious - the program never ends. Fix it!
Easy?
Now fix the program by changing ONLY ONE CHARACTER - non-space character of course! For this challenge there are 3 solutions. Find all 3 of them. Just to make it clear: the program must output 20 "+" signs and must end fast. Before criticizing me on what "fast" means, I'll say it means at most a couple of seconds (which by the way is too much but just to make it crystal clear).
Puzzle 3.2
EDITED
It was pointed to me earlier that the solution for the 3.2.2 puzzle might be compiler-dependent. In order to eliminate any possible discussion on the subject, I'll modify the idea and improve it on a next puzzle when I'll take extra care not to generate controversy.
 However, in order to keep this puzzle going, I'll make a small modification for 3.2.2 (the solution will be easier but cleaner).
When I first saw the puzzle I found it pretty awesome. I did manage to solve it but not immediately since it requires some careful attention.
 If you are here it means you too solved it. If you did so by writing a program to replace all possible characters with all possible values and test every solution, you are lost. Hard working guy though.
 Now having corrected the program that writes 20 "+" signs:
3.2.1: Insert one single letter and nothing more in the code so that the result is valid and outputs the same thing in all 3 corrected programs. Needless to say, the letter must be before the enclosing } of main (I say that because I don't want to hear people who just put a letter after the program and somehow their compiler was very friendly).
EDITED (see bellow) - For these final questions consider that the counter i starts from -1 instead of 0.
3.2.1.5: Repeat all previous problems with the condition that the output is at least 19 "+" signs (but still a finite output). Changing spaces is allowed. Now you might have found more solutions than in the first case. Some of these will most definitely fit for the 3.2.2 question.
3.2.2: Choose another value to initialize the variable n so that the resulting output will remain the same for at least one corrected programs in 3.2.1.5(not necessarily for all of them).
LAST EDIT1: changing the program so that it outputs 21 "+" signs is still a good solution, as the original text did not say "exactly" 20 signs. However, the infinite output is forbidden. Obviously this doesn't mean let's all start outputting hundreds of "+"signs since it's not forbidden. But eliminating a beautiful 21 output would not be in the spirit of this competition.
LAST EDIT2: considering LAST EDIT1 and accepting space changing it seems that now we have 5 possible solutions, four of which have already been pointed out in the responses. The last challenge however hasn't been touched and I must make it clear once more: n must be assigned another value, solutions that assign 20 to n by some tricks won't do it (like n=20L). Also I prefer to see the 3rd solution that does not change spaces.
LAST EDIT3: I've edited the last questions, please read!
The challenge is to solve both parts of the puzzle. The first one to do it wins.
I hope it's all clear, if not please post any questions and I'll edit as quickly as possible. Cheers.
emphasized text

I assume changing one character includes changing any spaces to non-space characters?  If so, I think I have found all 3 solutions for part 1.

oh..sorry..I had in mind to deny that explicitely but I forgot. I'll edit now. Thx for asking.

Oh good.  Because I can't find any answer for part 3.2.2 for my current 3 solutions... I guess that means I need to look for one more :)

yes :) good luck on that

I am not real strong on C, so I'm attacking this from a Java/C# background.  Does one of the three clever answers use a C-specific "hack" that I will have trouble finding?

I can't really give up on any clue for the third solution since I think the first two are easier to see.

anyway, keep those 3 solutions that allow spaces to be changed in mind. if eventually nobody comes up with the good solution I might allow the spaces to be converted in order to give a starting point to competition here :)

Feel free to create a new challenge, but please stop continuously changing the criteria. Spend some time analyzing your own questions before posting them.

@ardnew: I don't believe the OP has once changed the original intent of the question.  I agree there are better ways to fix the question than plumping a bunch of Edit's at the end... but it's still at the core the same question, with some things clarified.

@mellamokb I'm sure the intent hasn't changed, but unfortunately the specifications have. The fundamental task was to output 20 + symbols under certain restrictions. This was the one objective that drove all subsequent tasks. That requirement has apparently been tossed out the window (see: the comments to @mob 's submission, new task 3.2.1.5, and LAST EDIT1). Without that, the "correctness" of a submission is now left to the (clearly indeterminate) opinion of the author. -1

3.1
for( i = 0;-i < n; i-- )
for( i = 0; i < n; n-- )
for( i = 0; i + n; i-- )

Any of these changes will make the program output 20 '+' signs. This one is close:
for( i = 0;~i < n; i-- )

It outputs 21 '+' signs.
3.2.1
I found at least 112 ways to solve this problem inserting one letter. Not all of them may work on all compilers.
int n = 20L;
int n = 20f;
int n = 20d;
uint n = 20;

for( i = 0L; ... )
for( i = 0f; ... )
for( i = 0d; ... )

iprintf("+");
printf("+x");
printf("x+");

For the last two, substitute any letter for x to give you 104 possible solutions. Using either of the last two lines will change the output, but the output will still be the same for all 3 corrected programs.
3.2.2
All I've come up with are some things that get cast back to the number 20 on assignment to int.
int n = 20L;
int n = 20.001;
int n = 20.999;
int n = 20 + 0x100000000L;

Yep, you have the exact same answers I do (I didn't post them before because I didn't have everything answered).  I think the answer to 3.2.2 lies in the third solution to 3.1 that neither one of us has found (and obeys the rule of not allowing the space to be changed).

On 3.2.1, I'm not sure about the f and d suffixes for int types (well, d for any type for that matter), but there are a few others you've left off: int n = 20l, int n = 20U, and int n = 20u. Also I don't believe uint is a standard type identifier in C or C++. What compiler are you using for these anyway?

You've done a pretty good work here, but not complete! First of all, the ~i solution is still good! The requirement was to output 20 "+" signs so 21 is still a good solution (the only bad solution is infinite output). This means that you have now found 4 solutions! And the funny thing is, I still have one more :) About the 3.2.2, it is bad since I specifically required to change the VALUE of n, not to do some tricks to make it 20 :)

also what with the printf("+x") ??? it will print +X+X+X+X+X... which is not THE SAME output

and also, both the -i and ~i solutions change spaces so I'll consider them "partial" solutions. the 3rd complete solution must change a non-space character as specified in the quiz text

With printf("+x"), all three programs produce +x+x+x.... The output is valid and produces the same thing in all three programs.

you did not understand the problem. I said the modification will produce the same output as the coresponding modified program. that is, I have the corrected programs C1, C2, C3. after the character insertion I have P1, P2, P3. the requirement is: P1 has the same output as C1, P2 has the same output as C2, P3 has the same output as C3. It is NOT P1,P2,P3 having the same output

@BogdanAlexandru Please maintain an objective criteria. If outputting 21 chars is acceptable, what about 22 and 23 chars? Where do we draw the line?

like I said you can output any finite number of chars, but at least 20

3.1
Yet another puzzle. But normal solutions are boring, what about something special?
Solution one:
#include <stdio.h>
int main() {
   int i;
   int n = 20;
   for( i = 0; i < n; i++ )
      printf("+");
   return 0;
}

I decided to change ONLY ONE CHARACTER, that is, -. No characters other than - were changed.
Solution two:
#include <stdio.h>
int main() {
   int i=printf("++++++++++++++++++++");exit(0);
   int n = 20;
   for( i = 0; i < n; i-- )
      printf("+");
   return 0;
}

This changes exactly one character - the semicolon after int i into =printf("++++++++++++++++++++");exit(0);.
Solution three:
#include <stdix.h>
int main() {
   int i;
   int n = 20;
   for( i = 0; i < n; i-- )
      printf("+");
   return 0;
}

This loads the stdix.h system header. In the system include path, insert the following file, called stdix.h. It has to contain the following contents.
static inline void printf(const char *string) {
    int i;
    for(i = 0; i < 20; i--)
        putchar('+');
    exit(0);
}

3.2
Now to insert one letter. Well, that's simple, replace int main() with int main(a). This is not valid according to standards, but who cares?

Puzzle 3.1 Answers

Change i-- to n-- (demo: http://ideone.com/l0Y10)
Change i < n to i + n (demo: http://ideone.com/CAqWO)
Change [SPACE]i < n to -i < n. (demo: http://ideone.com/s5Z2r)

Puzzle 3.2.1
Change int n = 20 to int n = 20L (add an L to the end).
Puzzle 3.2.2
Haven't found an answer yet...

good, standard solution for 3.1 and 3.2.1.

3.1

Change i-- to n--
i<n to -i<n
(Unfortunately invalid answer because I wasn't checking with compiler before seeing other answers)

3.2.1
int n = 20

to
uint n = 20

(Compiler dependent...)
3.2.2
int n =-20L;

for(i = -1; i%n; i--)

prints 19 + signs, same as with int n = 20L;. However, I wouldn't have come up with it if I hadn't seen other answers to 3.2.1

#include <stdio.h>
int main() {
   int i;
   int n = 20;
   for( i = 0; i < n; i++  )
      printf("+");
        printf("\n");
   return 0;
}

Make sure to add the program language and character count into your answer.

@Timtech why character count? this is not code-golf

@Timtech also why to include the language? this is a language specific challenge.


text:
Recreate an xkcd graph procedurally with your favorite plotting tool
Lately there have been quite a number of questions regarding the recreation of xkcd-style graphs like the following one (1064) in various languages.

Your goal is to recreate any existing xkcd comic as close to the original as possible. The comic has to have at least one simple graph or pie chart or similar element.
The highest voted answer wins, not sooner than 10 days after the first valid answer.
Your entry must contain code that displays an xkcd-comic as described above in a graphing language, making at least some use of its plotting tool (Mathematica, MatLab, etc.)

the comic must not be stored as an image, it has to be generated procedulally
there must not be any link whatsoever to the original website, or a mirror of it, or its contents on your hard drive, etc.

Votes should evaluate the similarity of the results to the original, and to a lesser extent, the beauty of the solution. No code golf here, but a solution as short and simple as possible is expected.

Most votes isn't a suitable objective winning condition - and how are Boolean votes meant to take multiple elements into account to differing extents? I think this question can have an objective winning condition based on the average error per pixel divided by the code length or something similar, but as it stands it just encourages people to copy-paste the answers which have been heavily upvoted on other stacks.

@PeterTaylor: this is why I specified that it must be an existing xkcd comic, so there will be no copying. Most upvotes is a commonly used criteria (along with the "first solution", which I don't like that much), otherwise you would rarely find any problems here which are not code-golf (and not won by Golfscript)

Here's a stab.
Postscript
[Count deleted because this isn't a golf question.]

Added a "style" section to make it look more hand-drawn.

Edit: Helvetica responds better than Courier. Tweaked and enhanced this "style" section. And added comments.

%!

%futz with a coordinate pair
/f { 2 { rand 100 mod 100 div 1.47 mul
        dup .4 mul sub add
        exch } repeat } def

/op 2 array def %original point
/cp 2 array def %current point
/setcp { 2 copy cp astore pop } def %set current point
/difcp { cp aload pop %x' y' x y   %diff between cp and point on stack
    3 2 roll exch sub %x' x y'-y
    3 1 roll sub %y'-y x'-x
    exch %dx dy
} def
/scale2 { /n exch def  %scale two values
    n mul exch n mul exch
} def
/add2 {
    3 2 roll add
    3 1 roll add exch
} def
%futz with a path
/fpath {
    2 {
    %flattenpath
    % replace lines with curves
    [ { setcp cp op copy pop /moveto cvx }
        {
            %cp aload pop 4 2 roll 2 copy
            2 copy difcp %x3 y3 x30 y30
            2 copy 1 4 div scale2 %x3 y3 x30 y30 (1/3)x30 (1/3)y30
            cp aload pop add2 %x3 y3 x30 y30 x1 y1
            4 2 roll 3 4 div scale2 %x3 y3 x1 y1 (2/3)x30 (2/3)y30
            cp aload pop add2 %x3 y3 x1 y1 x2 y3
            6 4 roll %x1 y1 x2 y2 x3 y3
            setcp
            /curveto cvx }
        { setcp /curveto cvx }
        { op cp copy pop /closepath cvx } pathforall ] cvx newpath exec
    % chop the curves
    flattenpath
    % futz all the points
    [ { f
        /moveto cvx }
        { f
            /lineto cvx }
        { %f
            f 6 2 roll
            f 6 2 roll
            f 6 2 roll
            2 copy
            /curveto cvx
            3 1 roll
            3{f}repeat /lineto cvx % extra triple-futz'd line after each curve
        }
        { /closepath cvx } pathforall ] cvx newpath exec
    } repeat
} def

%futz with strokes
/oldstroke /stroke load def
/stroke { fpath oldstroke } def

%futz with fills
/oldfill /fill load def
/fill { fpath oldfill } def

%make sure rectstroke doesn't bypass being futzed with
/rectstroke {
    4 2 roll moveto
    1 index 0 rlineto
    0 exch rlineto
    neg 0 rlineto
    closepath
    stroke
} def

%futz with strings
%by making sure show uses our futz'd fill
/show { gsave currentpoint newpath moveto dup
    false charpath 1{fpath}repeat fill grestore stringwidth rmoveto } def

%fatter lines
1 setlinejoin %round joins
currentlinewidth 1.9 mul setlinewidth
%chop curves very small so there's lots of points for futzing
currentflat 6 div setflat

/Helvetica 10 selectfont

<<
/in{72 mul}
>>begin
1 in 1 in translate

0 0 6 in 4 in rectstroke
1 in 3 in moveto (WALKING BACK TO MY) show
1 in 2.8 in moveto (FRONT DOOR AT NIGHT:) show

36 3.5 in moveto
0 -2.8 in rlineto
5 in 0 rlineto
3.45 in .55 in moveto
0 20 rlineto
4.05 in .55 in moveto
0 20 rlineto
2.7 in .40 in moveto
(YARD  STEPS DOOR  INSIDE ) show
0 .05 in rmoveto
.4 in 0 rlineto
currentpoint
stroke
moveto
-10 3 rlineto
0 -6 rlineto fill

2.6 in .45 in moveto
-2 in 0 rlineto
currentpoint
stroke
moveto
10 3 rlineto
0 -6 rlineto fill

(FEAR) .9 in 2.3 in moveto show
(THAT THERE'S) .9 in 2.1 in moveto show
(SOMETHING) .9 in 1.9 in moveto show
(BEHIND ME) .9 in 1.7 in moveto show
1.8 in 1.86 in moveto
2 -26 rlineto
stroke

(FORWARD) 2.2 in 2.1 in moveto show
(SPEED) 2.2 in 1.9 in moveto show
2.75 in 2 in moveto
3 -13 rlineto
stroke

(EMBARRASSMENT) 4.5 in 2.5 in moveto show
4.6 in 2.65 in moveto
-2 20
-5 22
-27 25 rcurveto
stroke

.6 setgray %gray
40 1.6 in moveto
2.7 in 0
2.9 in 20
3.2 in 1.5 in rcurveto
10 20
20 20
30 0 rcurveto
15 -1.7 in
30 -1.8 in
1.4 in -2 in rcurveto
stroke

0 0 1 setrgbcolor %blue
40 1.2 in moveto
.9 in 27
.8 in 20
1.4 in 21 rcurveto
1 in -20
1.2 in 6
1.3 in 1.6 in rcurveto
    10 20
    20 20
    30 0 rcurveto
15 -1.8 in
30 -1.9 in
1.8 in -2.1 in rcurveto
stroke

1 0 0 setrgbcolor %red
40 .9 in moveto
3.3 in 0
3.5 in 20
3.6 in 1.5 in rcurveto
10 72
20 80
30 80 rcurveto
.7 in -10
.3 in -35
1.1 in -40 rcurveto
stroke

%thank you for scrolling all the way down to here. :)

can you add some of the "hand-drawn" stylization to it? :)

Yes. I completely overlooked that aspect at first. And then when I followed the links I was completely overwhelmed. Fat lines should be no biggie. And I've got a method from Casselman to reinterpret a path. So if I can understand those mathematica transforms, I should be able to replicate them. A much bigger task than I originally thought.

Even without those qualities, a very very good job.

And super great job on the styling!

Python
Makes use of the slightly cheat-y xkcd method in matplotlib:
import numpy as np
import matplotlib.pyplot as plt
from scipy.ndimage.filters import gaussian_filter1d

plt.xkcd()

x = np.linspace(0,10,1000)
unit = np.linspace(0,1,100)

speed = np.r_[np.ones(500)*3,3+5*unit**4.,np.ones(100)*8,1+7*unit[::-1]**2,np.ones(200)]
speed = gaussian_filter1d(speed,18)

fear = np.r_[np.linspace(0.5,2,450),2+6*unit**4,np.ones(100)*8,8*unit[::-1]**2,np.zeros(250)+0.1]
fear = gaussian_filter1d(fear,18)
fear_gauss_bump = 0.8*np.exp(-np.power(x-2.5,2.)/(2*np.power(1, 2.)))
fear += fear_gauss_bump

embarrassment = np.r_[np.zeros(600)+0.1, 9.5*unit**2, 9.5-np.linspace(0,1.5,300)]
embarrassment = gaussian_filter1d(embarrassment,60)

plt.figure(figsize=(12,6))
plt.plot(x,speed,c="gray")
plt.plot(x,fear,c="#1E9FDB")
plt.plot(x,embarrassment,c="r")

plt.plot([2.5,2.7],[3.9,2.3],c='k')
plt.plot([4.3,4.5],[3.6,3.1],c='k')
plt.plot(np.linspace(7.3,7.8,15),(0.25-(np.linspace(7.3,7.8,15)-7.3)**2)**0.5+7,c='k')

ax = plt.gca()
ax.spines['top'].set_visible(False)
ax.spines['right'].set_visible(False)
ax.get_xaxis().tick_bottom()
ax.get_yaxis().tick_left()
#plt.ylim([0,10])
ax.set_xticks([6,7])
ax.set_xticklabels(["STEPS","DOOR"])
ax.set_yticks([])

ax.text(2,4,"FEAR\nTHAT THERE'S\nSOMETHING\nBEHIND ME",horizontalalignment='center')
ax.text(3.9,3.4,"FORWARD\nSPEED",horizontalalignment='center')
ax.text(7.4,6.6,"EMBARRASSMENT")
ax.text(1,8,"WALKING BACK TO MY\nFRONT DOOR AT NIGHT:",bbox={'facecolor':'none', 'edgecolor':'black'})
ax.annotate("YARD", xy=(0.5,-0.3), xytext=(4.5,-0.4),annotation_clip=False,arrowprops={'facecolor':'black', 'shrink':0.01, 'width':0.5})
ax.annotate("INSIDE", xy=(10,-0.3), xytext=(7.5,-0.4),annotation_clip=False,arrowprops={'facecolor':'black', 'shrink':0.01, 'width':0.5})

plt.show()

Upvoted - literally never knew there was an xkcd function in matplotlib.

HTML5

@font-face {
  font-family: 'Humor Sans';
  font-style: normal;
  font-weight: 400;
  src: local('Humor Sans'), local('Humor Sans-Regular'), url("data:font/woff;base64,[encoded data, 14384 characters]") format('woff');
}
body {
    font-family: 'Humor Sans';
    margin: 2em;
    background: #DDD;
    text-shadow: 1px 1px 2px #FFF;
}
h1 {
    font-family:Lucida,Helvetica,sans-serif;
}
.h1d {
    display: inline;
    font-size: .8em;
}
path,rect { fill: none;
    stroke:#000000;
    stroke-width:0.00329859;
    stroke-linecap:butt;
    stroke-linejoin:round;
    stroke-miterlimit:10.43299961;
 }
text {
    text-align:start;
    letter-spacing:0px;
    word-spacing:0px;
    writing-mode:lr-tb;
    font-size:14px;
    text-anchor:start;
    fill:#000000;
    fill-opacity:1;
    stroke:none;
    font-family:Humor Sans;
}
text {
    font-size:0.01944444px;
    text-anchor:middle;
    fill:#000000;
    fill-opacity:1;
    stroke:none;
    font-family:Humor Sans;
}
<html xmlns="http://www.w3.org/1999/xhtml"><head>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<title>Front Door ( from xkcd.com 1064 )</title>
  </head>
<body><h1>Front Door <div class="h1d">( from xkcd.com 1064 )</div></h1>
<svg xmlns="http://www.w3.org/2000/svg" width="640" height="434"
   version="1.1" viewBox="0 0 0.7876308 0.53355077">
  <defs>
    <marker id="Aen" style="overflow:visible">
      <path d="M 0,0 5,-5 -12.5,0 5,5 0,0 z" transform="matrix(-0.4,0,0,-0.4,-4,0)"
         style="fill-rule:evenodd;fill:#000;stroke:#000000;stroke-width:1pt" />
    </marker>
    <marker orient="auto" id="Ast" style="overflow:visible">
      <path d="M 0,0 5,-5 -12.5,0 5,5 0,0 z"
         transform="matrix(-0.4,0,0,-0.4,-1.4,0)"
         style="fill-rule:evenodd;fill:#000;stroke:#000000;stroke-width:1pt" />
    </marker>
  </defs>
  <rect width="0.75612795" height="0.50201935" x="0.015758738" y="0.015780471" />
  <path d="m 0.08162198,0.08036774 c -3.384e-4,3.2166e-4 -7.6617e-4,0.35262886 -7.6617e-4,0.35262886 0,0 0.20318503,-6.6026e-4 0.29000566,-0.003213 0.0402085,3.6731e-4 0.0806898,-1.3866e-4 0.12100339,-4.2191e-4 0.0422491,-4.676e-5 0.0848177,0.001196 0.12714108,1.4026e-4 0.0292134,0.0012 0.0579496,7.8663e-4 0.0872307,8.041e-5" />
  <path d="M 0.45045642,0.44967094 C 0.45097434,0.43767424 0.44992661,0.42569324 0.4498655,0.41370014" />
  <path d="m 0.52462262,0.44857719 c 0.001364,-0.0112841 -0.001303,-0.022673 8.8508e-4,-0.0339046" />
  <path d="m 0.34455432,0.46185837 c -0.0838098,-0.00177 -0.16763839,9.02e-5 -0.25145536,-4.499e-4" style="marker-end:url(#Ast)" />
  <path d="m 0.36372087,0.26833529 c 3.15e-6,-3.093e-5 0.003925,0.021959 0.003958,0.0219625" />
  <path d="m 0.59455272,0.18635665 c 0.00168,-0.0249062 -0.0194278,-0.0449558 -0.0436226,-0.042955 -0.001466,-1.5486e-4 -0.002932,-3.0973e-4 -0.004398,-4.6459e-4" />
  <path d="m 0.08896568,0.31883844 c 0.0589995,-0.004388 0.11835478,4.8486e-4 0.17689559,-0.007727 0.0452821,-0.002558 0.0920316,-0.008761 0.13292997,-0.0296799 0.0495136,-0.0206019 0.0702543,-0.0754087 0.082167,-0.12423165 -0.001544,-0.0316524 0.0363005,-0.0771322 0.0574533,-0.031946 0.009799,0.0468904 0.0124403,0.0957944 0.0257953,0.14199884 0.0103229,0.0424564 0.0381648,0.0821154 0.0814383,0.0955288 0.0230248,0.006738 0.0463641,0.0136174 0.0701731,0.01698" style="stroke:#888" />
  <path d="m 0.08766361,0.36678952 c 0.0463076,-0.0161779 0.0920382,-0.0420708 0.14283849,-0.0357173 0.0467333,-0.004581 0.0974621,0.0266481 0.14082991,-0.00179 0.0400306,-0.0301432 0.041483,-0.0866619 0.0490443,-0.13214834 0.003929,-0.030081 -0.00375,-0.0999028 0.0422392,-0.0879794 0.0291414,0.0376662 0.0177989,0.0902038 0.0319018,0.1336763 0.009362,0.0507676 0.0330856,0.10817744 0.0871312,0.12415282 0.0508722,0.0193263 0.0767224,0.0174745 0.11889504,0.0257316" style="stroke:#00f" />
  <path d="m 0.08912193,0.4046365 c 0.10169167,1.097e-5 0.2041028,3.5438e-4 0.3047905,-0.0155419 0.0458292,-0.008171 0.0971567,-0.0242812 0.12178371,-0.0670869 0.025388,-0.0534434 0.0183231,-0.11451516 0.0333489,-0.17061477 -0.003977,-0.0433016 0.0436224,-0.0993166 0.0831427,-0.0568712 0.0246552,0.0226559 0.0477548,0.0560862 0.0858377,0.0521295" style="stroke:#f00" />
  <path d="m 0.70840577,0.46185837 c -0.002849,8.248e-5 -0.0849355,0.001616 -0.0849355,0.001616" style="marker-start:url(#Aen)" />
  <path d="m 0.24465913,0.2858699 c 9.6794e-4,0.0147144 0.001383,0.0294673 0.002814,0.0441494" />
  <text x="100.15588" y="48.485607" transform="scale(0.00138889,0.00138889)"
    style="font-size:14px;text-anchor:start">
    <tspan x="100.15588" y="48.485607" id="tspan7010">WALKING BACK TO MY</tspan>
    <tspan x="100.15588" y="65.285591" id="tspan7012">FRONT DOOR AT NIGHT:</tspan></text>
  <rect width="0.24843951" height="0.065260872" x="0.12345294" y="0.039088331" />
  <text x="0.23551519" y="0.20231472"><tspan x="0.23551519" y="0.20231472">fear</tspan>
    <tspan x="0.23551519" y="0.22564805">ThAT there's</tspan>
    <tspan x="0.23551519" y="0.24898137">something</tspan>
    <tspan x="0.23551519" y="0.2723147">behing me</tspan></text>
  <text x="0.36015913" y="0.22917171"><tspan x="0.36015913" y="0.22917171">fORWarD</tspan>
    <tspan x="0.36015913" y="0.25250503">SPEED</tspan></text>
  <text x="0.37393194" y="0.46812996"><tspan x="0.37393194" y="0.46812996">yarD</tspan>
    <tspan x="0.45037103" y="0.46812996">step</tspan>
    <tspan x="0.52267832" y="0.46812996">door</tspan>
    <tspan x="0.58878779" y="0.46812996">inside</tspan></text>
  <text x="0.63905853" y="0.20506927">
    <tspan x="0.63905853" y="0.20506927">emBARRASSMENT</tspan></text>
</svg>
</body></html>


text:
Make an HTML page goto infinite loop?
Write a code using HTML, JavaScript, jQuery to make the page go into infinite loop.
Restrictions:
No looping or control structures of javascript and jQuery allowed. You can only use alert, events, etc.

What's the winning condition? 2. What does it mean for a page to be in an infinite loop?

ok, Just edited the question including winning condition.

@grc: I'm not so sure it's ambiguous; a blank page doesn't require that the browser must be closed to continue.  However, I don't think it's possible to do this in modern browsers.  I'm not on Windows, but I can remember how to crash IE without using loops (though that may have been fixed in IE 9/10).

@Andy E: I don't really get what you mean by continue. Does it mean that you are able to use elements on the page, or that you are able to use other pages in the browser?

@grc: the OP makes it sound like he wants to lock up the browser and force it to be closed.  This is difficult/impossible in browsers with sandboxed tabs, but you can crash a tab (see Florian's example).

I am a bit too busy to work on this at the moment, but my idea would be some form of frame-busting script that triggers when a frame is detected in some loop? might be possible?

That's not a winning criterion, because multiple players might achieve this goal. It could be the criterion to enter the contest. But a stable browser will only need to close a single tab.

ok @userunknown I removed the winning condition. Cheers!

@DarshanThanki: You shouldn't remove the winning criterion but modify it, because every question should have a winning criterion.

$($);

May not meet your conditions, but I like it. (And it does crash your browser.)
More information about this: Why does $($) crash my page?

Yup, this locks up my tab in Chromium.

I see what you did there florian

@AndyE that locks up all browsers i have Safari , Opera , Chrome , Firefox , Aurora , Canary , RockMeIT , Maxathon ...... All hail jQuery .. they should put this as feature.!!
Creates cross browser crashes :D

Little but awesome solution. I just thought of this one for the first time I came up with this question. Bravo, @florin

How about a meta refresh?
<meta http-equiv=refresh content=1>

I removed the quotation marks around the parameter values because code golf.

This reloads the page as soon as it loads:
<html>
<head>
<script>window.location=window.location</script>
</head>
</html>

Or you could bring up infinite alert boxes (until the user disables them):
<html>
<body onfocus="alert('')"></body>
</html>

5 years ago I would have voted on this.  However, most modern browsers have a checkbox on the alert that will prevent further dialogs from appearing.

That's right. Even if you don't check it, the browser limits alerts to a specific number. Here is Google security policy  that explains more about it.

@DarshanThanki That's the extension security policy...

This will reload the browser indefinitely:
location.reload()

(Unless the browser specifically blocks repeated reloads.)


text:
The real knapsack problem
Given

the number of goods N
positive weight of each good weight[N]
positive profit of each good profit[N]
and a positive number W which is the knapsack capacity.

This problem is called “the zero-one knapsack” for choosing the most beneficial goods for the knapsack of limited capacity.
Example:

The number of goods (items)   :   5
Weight of each item (kg)  :   {2, 3, 5, 7, 8} which apply to item 1, item 2, ...... item 5 in that order
Value of each item (10,000 yen)   :   {2, 4, 8, 9, 10} which apply to item 1, item 2, .... item 5 in that order
Capacity of the knapsack  :   10 kg

Among the five goods:
Goods chosen            Total weight    Total value
Goods 1, 2 and 3    2 + 3 + 5 = 10  2 + 4 + 8 = 14   <- Maximum

What is the aim of the contest? This isn't going to make an interesting golf per se, and scoring a heuristic is going to require either a lot of test cases or some detailed analysis.

do we also assume there is only 1 of each item, because if I take 2 of item3, I get a profit of 16

I'm sorry if the problem I just read was not clear to indicate that there is only 1 of each item.

Python, 236 Charaters
Okay, I guess I'll bite.
from itertools import *
def k(w,p,c):
    n=len(w)
    r=range(n)
    return max(filter(lambda y:y[1]<=c,[(s,sum(map(lambda y:w[y],s)),sum(map(lambda y:p[y],s))) for s in chain.from_iterable(combinations(r,u) for u in r+[n])]),key=lambda y:y[2])[0]

Usage
The k function takes three arguments: a list containing the weights, a list containing the profits, and the capacity of the knapsack.  Here is how to call it given the example above:
> print k([2,3,5,7,8], [2,4,8,9,10], 10)
(0, 1, 2)

Meaning that items 0, 1, and 2 are the optimal solution.

Now how about if the number of items available for each item type is unlimited as hinted by Sean Cheshire?

If the number of items is unbounded then I'd have to use a different approach (e.g., constructing a search tree and solving the problem using something like BFS or A*).