text:
Generating a Student Timetable
Introduction
You are the computer science teacher in a large high school and have been tasked to create a system to generate the student timetables. You must, given a JSON dictionary of student names and the subjects they are taking, you must generate a timetable for each of the students.
Specifications
Each student takes seven subjects (English Literature, English Language and Maths are compulsory but don't count towards the seven subjects):
Subject name - Abbreviation

Art - Ar
Biology - Bi
Business Studies - Bu
Chemistry - Ch
Computer Science - CS
French - Fr
Geography - Gg
History - Hi
IT - IT
Mandarin - Cn
Music - Mu
PE - PE
Physics - Ph
Spanish - Sp

Compulsory:

English Language - La
English Literature - Li
Maths - Ma

Other:

Tutor - Tu
Free - Ac

All abbreviations must be in the same case as above.
Each day has ten periods of lessons. A lesson can either span a single period or a double period. There must be three lessons of each subject with each having one double lesson (double period length) and two single lessons. The only exception to this rule is English Language which only occurs once a week and is a double.
There must be only one lesson of the same subject a day.
A school day is Monday to Friday.
Between periods 3 and 4 and between periods 5 and 6, there is a break. Lessons must not be placed over a break. From period six inclusive on a Wednesday to the end of the day, there are free periods. Period 1 on a Tuesday is Tutor period. Period 10 on a Friday is also Tutor. Period 10 on a Thursday is a free period.
Lessons must not be split into multiple groups meaning that people studying the same subject must be together in those subjects. Students may have any number of frees.
You must use the subject's abbbreviation in the timetable.
Data input
The JSON data must either be read from a local file or placed as a string variable in your code. The file will be a list of students with their names and a list of subjects. For example:
[
{"name":"Sarah","subjects":["physics","it","biology","history","art","business studies","french"]},
{"name":"Jim","subjects":["history","business studies","biology","computer science","geography","chemistry"]},
{"name":"Mary","subjects":["it","computer science","biology","physics","chemistry","art"]},
{"name":"Chris","subjects":["biology","chemistry","physics","french","computer science","geography"]}
]

Your program should then generate a timetable for each of the students, fitting all of the subjects in.
If there are multiple solutions, choose the first.
Note: The JSON file above has not been tested to see if it has a valid answer, it was just created to describe the formatting.
Output
The output must be a JSON file or CSV with the format detailed in your answer. You can either make a file for each of the students or have the timetables for all students in the same file.
Winning
The winning code is the shortest that successfully creates working timetables.

Congrats on posting question no. 2,500. ;)

@Martin Nice! ;)

"three lessons including one double". Is that exactly one double, plus two singles? Is two doubles of an equivalent time not valid? what about 2 doubles plus a single? 2. Are all students studying the same subject expected to attend lessons in that subject at the same time? I assume so, but it is not explicitly stated. 3. If the answer to 2 is yes, is there an exception to this rule for free periods? (I haven't calculated whether a student will have any additional free periods other than the ones you have mentioned explicitly.)

I propose the required output is just an ASCII table, maybe a CSV file. Drawing an image is a trivial task if there is a nice image library available for your language. The drawing of an image is not the hardest part of a challenge like this, but the requirement rules some languages out. PNG output could be a bonus.

Is this from your actual job? =P. It's remarkably specific and an actual problem to have.

@Claudiu Nah, this is inspired from my school (I'm a student there) and thought it would make a nice puzzle.

Nostalgia:  I actually wrote a program that did this for me when I was a student.  The university offered many many possibilities for each class so I wrote a program to generate all the possible timetables for my classes that met my rules (no 8am classes, etc)  It was awesome - I tried to get the university to give me a soft copy of the multi hundred page book containing the full list of course sessions so I didn't have to type in all the sessions manually and they refused.  I used it anyway because it was so useful.

@Jerry Haha nice! Which language did you write it in (and do you still have the code)?

Wow! :D It's kind of interesting and I can't stop thinking about a neat solution :) 21 hours left :O Do you want a special language? I can try in PHP or JS...

@Wikunia Haha, I'm happy with anything! :)

One question: "Between periods 3 and 4 and between periods 5 and 6, there is a break. Lessons must not be placed over a break" means there is neither a double lesson 3+4 nor 5+6?

@Wikunia That is correct

Are you sure that there is a solution for your json time table?

@Wikunia Oh sorry, no, that was something I mocked up quickly to show the format

Let us continue this discussion in chat.

NodeJS
Edit
The algorthim is much faster now!
There is definitely no solution for the given example!
I tried some algorithms to generate a time table and I am pretty sure that your example has no solution.
So I changed the example to
students.json:
[
{"name":"Sarah","subjects":["physics","it","biology","history","art","business studies","french"]},
{"name":"Jim","subjects":["history","business studies","biology","computer science","geography","chemistry"]},
{"name":"Mary","subjects":["it","computer science","biology","physics","chemistry","art"]},
{"name":"Chris","subjects":["biology","chemistry","physics","french","computer science","geography"]}
]

(I only deleted the pe)
which generates this timeTable.json
 {
 "mon":
   [["Bi"],["Bi"],["Ar","Gg"],["La"],["La"],["Ch"],["Ch"],["CS"],["CS"],["Ph"]],
 "tue":
   [["Tu"],["Bi"],["Ar","Gg"],["Ma"],["Ma"],["Ch"],["CS"],["Ph"],["Ph"],["Bu"]],
 "wed":
   [["Bi"],["Ar","Gg"],["Ar","Gg"],["Li"],["Li"],["Fr"],["Fr"],["IT"],["IT"],["Hi"]],
 "thu":
   [["Li"],["Ma"],["Ch"],["CS"],["Bu"],["Ph"],["Fr"],["IT"],["Hi"],["Ac"]],
 "fri":
   [["Li"],["Ma"],["Fr"],["Bu"],["Bu"],["IT"],["Hi"],["Hi"],[],["Tu"]]
 }

And yes my programm is very long but I think code which is shortened afterwards makes it really hard to read and nowadays it isn't important to save bytes but time!
If you have any suggestions or you found a bug => comment!
You can start the file (timeTable.js) with node timeTable.js students.js
    var fs = require('fs');

console.log('Timetable');
var json = JSON.parse(fs.readFileSync(process.argv[2], 'utf8'));

var backTracks = 0;
var lessons =
    ["art","biology","business studies","chemistry","computer science","french","geography","history","it","mandarin","music","pe","physics","spanish"];
var abbr = ["Ar","Bi","Bu","Ch","CS","Fr","Gg","Hi","IT","Cn","Mu","PE","Ph","Sp"];
var single = [2,2,2,2,2,2,2,2,2,2,2,2,2,2];
var double = [1,1,1,1,1,1,1,1,1,1,1,1,1,1];

var days = ["mon","tue","wed","thu","fri"];
var nrOfStudents = json.length;
var q = 0;

// convert json into correct position
for (var i = 0; i < json.length; i++) {
    var subjects = json[i].subjects;
    for (var s = 0; s < subjects.length; s++) {
        var pos = lessons.indexOf(subjects[s].toLowerCase());
        if (pos >= 0) {
            subjects[s] = pos;
        }
    }
}

// Special lessons
var timeTable = {"mon":[],"tue":[],"wed":[],"thu":[],"fri":[]};
timeTable.tue[0] = ["Tu"];
timeTable.fri[9] = ["Tu"];
timeTable.thu[9] = ["Ac"];
// one english double (Monday 4-5)
timeTable.mon[3] = ["La"];
timeTable.mon[4] = ["La"];
// one double two single for math and literature (Tue 4-5,Wed 4-5,Thu 1,2,Fri 1,2)
timeTable.tue[3] = ["Ma"];
timeTable.tue[4] = ["Ma"];
timeTable.wed[3] = ["Li"];
timeTable.wed[4] = ["Li"];
timeTable.thu[0] = ["Li"];
timeTable.thu[1] = ["Ma"];
timeTable.fri[0] = ["Li"];
timeTable.fri[1] = ["Ma"];

var timeTableBackup = {0:[],1:[],2:[],3:[],4:[]};

for (var i = 0; i < 5; i++) {
    var day = timeTable[days[i]];
    for (var j = 0; j < 10; j++) {
        if (!(j in day) || !Array.isArray(day[j])) {
            day[j] = [];
        }
    }
}

// sort subjects
var sortedSubs = [];
// 14 subjects
for (var i = 0; i < 14; i++) {
    sortedSubs[i] = {t:0,students:[],n:i};
}

for (var i = 0; i < json.length; i++) {
    var subjects = json[i].subjects;
    var student = json[i].name;
    for (var s = 0; s < subjects.length; s++) {
        sortedSubs[subjects[s]].t ++;
        sortedSubs[subjects[s]].n = subjects[s];
        sortedSubs[subjects[s]].students.push(student);
    }
}
console.log(sortedSubs);

sortedSubs = sortByKey(sortedSubs,"t");

var k = sortedSubs.length-1;
// remove all subs that weren't choosen by anyone
while(sortedSubs[k].t == 0) {
    var sub = sortedSubs.pop();
    single[sub.n] = 0;
    double[sub.n] = 0;
    k--;
}

var goBack = false;
var start = false;
var d = 0;
while (d < 5) {
    // 10 lessons per day
    var l = 0;
    while(l < 10) {
        var day = timeTable[days[d]];
        // if there is no subject
        if (day[l].length == 0) {
            var next = false;
            var s = start === false ? 0 : start;
            var firstChoice = false;
            while (!next && s < sortedSubs.length) {
                if (possibleToAdd(day,l,s)) { // different lessons on one day and possiblity to add lesson
                    goBack = false;
                    next = true;
                    if (!firstChoice) firstChoice = s;
                    // get the number of students that don't have this lesson
                    var except = nrOfStudents - sortedSubs[s].t;
                    if (except > 0) {
                        // get the first lesson which none of the students have
                        var breaked = false;
                        var tempL;
                        for (var ss = s+1; ss < sortedSubs.length; ss++) {
                            if (sortedSubs[ss].t <= except && possibleToAdd(day,l,ss)) {
                                var intersection = arrIntersect(sortedSubs[s].students,sortedSubs[ss].students);
                                // no student has both classes
                                if (intersection.length == 0) {
                                    if (!breaked) { // fill the current lesson (s) only once
                                        tempL = addLesson(day,l,s);
                                    }
                                    tempL = addLesson(day,l,ss);
                                    breaked = true;
                                }
                            }
                        }

                        if (breaked) {
                            l = tempL;
                        } else { // it wasn't possible to have two classes at this time
                            next = false;
                            var found = false;
                            // maybe there are other lessons which can be added => found = true
                            for (var z = s+1; z < sortedSubs.length; z++) {
                                if (possibleToAdd(day,l,z)) {
                                    found = true;
                                    break;
                                }
                            }
                            // otherwise fill this lesson with the first choice
                            if (!found) {
                                l = addLesson(day,l,firstChoice);
                            }
                        }
                    } else {
                        // everyone has this lesson :)
                        // on day lesson no. l: subject no. s
                        l = addLesson(day,l,s);
                    }
                } else {
                    if (start) goBack = true;
                }
                s++;
            }
            start = false;
        }
        // Friday last lesson
        if ((d == 4 && l == 9) || goBack) {
            // how many lessons are missing?
            var sum = double.reduce(function(pv, cv) { return pv + cv; }, 0)*2 + single.reduce(function(pv, cv) { return pv + cv; }, 0);
            if (sum > 0) {
                remove = removeLesson(d,l);
                if (remove) {
                    backTracks++;
                    if (backTracks % 50000 == 0) {
                        console.log('backTracks: '+backTracks+'...');
                    }
                    d = remove.back.day;
                    l = remove.back.lesson;
                    start = remove.start;
                } else {
                    console.log('I could not find a solution for this problem :( ');
                    console.log('backtracks: '+backTracks);
                    process.exit();
                    l = 10;
                    d = 5;
                }
            } else {
                l = 10;
                d = 5;
            }
        } else {
            l++;
        }
    }
    d++;
}

function removeLesson(d,l) {
    var day = timeTable[days[d]];
    var back = true;
    // what is the latest subject
    var latestSub = sortedSubs[sortedSubs.length-1].n;

    // backtrack
    while(back) {
        // if there is no lesson before => back to the last lesson the day before
        if (l == -1) {
            if (d == 0) {
                return false; // not possible at all
            }
            d--;
            day = timeTable[days[d]];
            l = day.length-1;
        }

        // if there is a non default lesson
        if (day[l].length > 0 && parseInt(day[l][0]) == day[l][0]) {
            // if the latestSub isn't part of this lesson we don't need to backtrack more
            if (day[l].indexOf(latestSub) < 0) { back = false; }
            var intersection = [];
            // if we are not in the first lesson => get double lessons
            if (l > 0) {
                intersection = arrIntersect(day[l],day[l-1]);
            }
            // if there are double lessons
            if (intersection.length > 0) {
                for (var i = 0; i < day[l].length; i++) {
                    // check if current lesson is a double lesson
                    if (intersection.indexOf(day[l][i]) >= 0) {
                        double[day[l][i]]++;
                    } else {
                        single[day[l][i]]++;
                    }
                }
                // remove all single lessons the lesson before
                for (var i = 0; i < day[l-1].length; i++) {
                    if (intersection.indexOf(day[l-1][i]) < 0) {
                        single[day[l-1][i]]++;
                    }
                }
                day[l] = [];
                l--;
            } else {
                for (var i = 0; i < day[l].length; i++) {
                    single[day[l][i]]++;
                }
            }
            // delete the day if the current lesson was the least possible solution
            if (back) {
                day[l] = [];
            }
        } else {
            l--;
        }
    }
    var start = false;
    // get start subject for this lesson d,l
    for (var s = 0; s < sortedSubs.length-1; s++) {
        if (day[l].indexOf(sortedSubs[s].n) >= 0) {
            start = ++s;
            day[l] = [];
            break;
        }
    }
    if (!start) {
        console.log('there is a bug');
        process.exit();
    }
    return {back:{day:d,lesson:l},start:start};
}

function addLesson(day,l,s) {
    // is a double lesson possible?
    if (double[sortedSubs[s].n] > 0 && l != 2 && l != 4 && l+1 < 10 && (day[l+1].length == 0 || parseInt(day[l+1][0]) == day[l+1][0])) {
        double[sortedSubs[s].n]--;
        for (var i = l; i <= l+1; i++) {
            if (Array.isArray(day[i])) {
                day[i].push(sortedSubs[s].n);
            } else {
                day[i] = [sortedSubs[s].n];
            }
        }
        l++;
    } else if (single[sortedSubs[s].n] > 0) { // put it into a single lesson
        single[sortedSubs[s].n]--;
        if (Array.isArray(day[l])) {
            day[l].push(sortedSubs[s].n);
        } else {
            day[l] = [sortedSubs[s].n];
        }
    } else {
        console.log('ERROR');
        process.exit();
    }
    return l;
}

function possibleToAdd(day,l,s) {
    // it is not allowed to have the same lesson twice on a day
    var notSet = true;
    for (var i = 0; i < l; i++) {
        if (day[i].indexOf(sortedSubs[s].n) >= 0) {
            notSet = false;
            break;
        }
    }
    if (!notSet) return false;

    // no double lesson 3+4 and (starting with 1)
    if (double[sortedSubs[s].n] > 0 && l != 2 && l != 4 && l+1 < 10 && (day[l+1].length == 0 || parseInt(day[l+1][0]) == day[l+1][0])) {
        return true;
    } else if (single[sortedSubs[s].n] > 0) {
        return true;
    } else {
        return false;
    }
}

function arrIntersect(array1,array2) {
    return array1.filter(function(n) {
        return array2.indexOf(n) != -1
    });
}

function sortByKey(array, key) {
    return array.sort(function(a, b) {
        var x = a[key];
        var y = b[key];
        return ((x < y) ? 1 : -1);
    });
}

// convert lesson numbers into abbr
for (var d = 0; d < 5; d++) {
    var day = timeTable[days[d]];
    // 10 lessons per day
    for (var l = 0; l < 10; l++) {
        for (var ll = 0; ll < day[l].length; ll++) {
            if (parseInt(day[l][ll]) == day[l][ll]) {
                day[l][ll] = abbr[day[l][ll]];
            }
        }
    }
}

console.log(timeTable);
console.log('Backtracks: '+backTracks);

fs.writeFile("timeTable.json", JSON.stringify(timeTable), function(err) {
    if(err) {
        console.log(err);
    } else {
        console.log("The file was saved (timeTable.json)!");
    }
});

I've implemented your suggested example in the question


text:
Moore Iteration
Info
The numbers 1 to 9 each represent a cell in the Moore's Neighbourhood, with 5 being the central cell.
So:
123
456
789

1={-1,-1} 2={-1, 0} 3={-1, 1}
4={ 0,-1} 5={ 0, 0} 6={ 0, 1}
7={ 1,-1} 8={ 1, 0} 9={ 1, 1}

The Challenge
You may take input via STDIN, ARGV or function argument and either return the result or print it to STDOUT. Input is a N x N grid (torus topology, meaning if x or y is < 1 then x or y = N, and if x or y > N then x or y = 1), and your program must output one interation of that grid by replacing each cell with the value at its Moore's Neighbourhood cell.
Example Input grid (2 x 2):
13
79

Output:
97
31

Explanation:
Starting at position 1,1 we have the value 1, since value 1={-1,-1} we have to retrieve 1+(-1),1+(-1) = 0,0. And because it's a torus 0,0 we wrap around to N. So we retrieve the cell value at position 1,1 (1) with the cell value at position 2,2 (9).
For the next cell 1,2 we have value 3 (=-1, 1) so 1+(-1),2+(1) = 0,3. Wraps around to 2,1 which is value 7.
Next cell value at 2,1 is 7 (= 1,-1) so 2+(1),1+(-1) = 3,0. Wraps around to 1,2 which is value 3.
Next cell value at 2,2 is 9 (= 1, 1) so 2+(1),2+(1) = 3,3. Wraps around to 1,1 which is value 1.
More Examples
Input Grid (3 x 3):
123
456
789

Expected Output:
987
654
321

Input Grid (5 x 5):
77497
81982
32236
96336
67811

Expected Output:
28728
37337
11923
73369
77433

Final Notes
If you have any question, don't hesitate to comment. This is a code golf challenge, shortest code wins!

How do you define the position of an element? I don't understand how the input set of cells are indexed.

@Rainbolt The input is indexed by rows then columns. So in the last example (input) cell value at 2,3 is 9. row 2 = 81982, and the third column of that is 9.

related: http://codegolf.stackexchange.com/q/36839/15599

Could not help but read "Moore examples".

APL (33)
APL was made for this. This is a function that takes the input grid as an N-by-N matrix and returns the output grid as an N-by-N matrix.
{(⍳⍴⍵)⌷¨(,∆∘.⊖(∆←2-⌽⍳3)∘.⌽⊂⍵)[⍵]}

Test:
      ⍝ define input matrices
      ∆1 ← ↑(1 3)(7 9)
      ∆2 ← ↑(1 2 3)(4 5 6)(7 8 9)
      ∆3 ← ↑(7 7 4 9 7)(8 1 9 8 2)(3 2 2 3 6)(9 6 3 3 6)(6 7 8 1 1)
      ⍝ show input matrices
      ∆1 ∆2 ∆3
 1 3  1 2 3  7 7 4 9 7
 7 9  4 5 6  8 1 9 8 2
      7 8 9  3 2 2 3 6
             9 6 3 3 6
             6 7 8 1 1
      ⍝ apply function to input matrices giving output matrices
      {(⍳⍴⍵)⌷¨(,∆∘.⊖(∆←2-⌽⍳3)∘.⌽⊂⍵)[⍵]} ¨ ∆1 ∆2 ∆3
 9 7  9 8 7  2 8 7 2 8
 3 1  6 5 4  3 7 3 3 7
      3 2 1  1 1 9 2 3
             7 3 3 6 9
             7 7 4 3 3

Python, 174
def t(b):b=b.split("\n");E=enumerate;C=[-1]*3+[0]*3+[1]*3+[-1,0,1]*3;print"\n".join("".join(b[(i+C[int(x)-1])%len(b)][(j+C[int(x)+8])%len(y)]for j,x in E(y))for i,y in E(b))

Python was not made for this... APL was!

Python, 105
Takes and returns a list of lists:
def f(a):e=enumerate;n=len(a);return[[a[(y+(v-1)/3-1)%n][(x+(v-1)%3-1)%n]for x,v in e(u)]for y,u in e(a)]

Takes and returns a string (148 characters):
def f(s):
 a=[map(int,l)for l in s.split()];n=len(a);e=enumerate
 for y,u in e(a):print''.join(`a[(y+(v-1)/3-1)%n][(x+(v-1)%3-1)%n]`for x,v in e(u))

MATLAB - 121 bytes
function O=X(I),m=size(I,1);n=3*m;o=-1:1;c=o<2;M=c'*o+n*o'*c;D=repmat(I,3);C=D;C(:)=1:n*n;t=m+(1:m);O=C+M(D);O=D(O(t,t));

MATLAB was slightly less made for this than APL, but slightly more made for this than Python. ;)
Test Output
X( [1 2 3; 4 5 6; 7 8 9] )

ans =

     9     8     7
     6     5     4
     3     2     1

X( [7 7 4 9 7; 8 1 9 8 2; 3 2 2 3 6; 9 6 3 3 6; 6 7 8 1 1] )

ans =

     2     8     7     2     8
     3     7     3     3     7
     1     1     9     2     3
     7     3     3     6     9
     7     7     4     3     3

source: Stack Exchange

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

sort: votes


text:
Distribution of Variables
I was annoyed the other day when I got a point off in math class because I didn't distribute the factors of my function.
That is, I put (x+2)(x-3) when I should have put x^2 - x - 6.
Your job is to write a program that takes a string with the expression and convert it to the expanded form so I don't miss future points.
Rules

Any letters within the lowercase English alphabet can be used as "x" (for example: (a+1)(c+3)).
All exponents in answer must be in the form (variable)^n where n is the power
variables can be assumed to be 1 character long. That is, ab == a * b
Your answer should not contain the "*" character
The spaces before and after a + or - must be present. Otherwise, no spaces are permitted, except for trailing spaces.
You must account for exponents outside of parentheses, so (x+1)^n.

Specifications

You may create a program or function that takes a string parameter
Your program must output the correct expression to STDOUT or a text file
You may assume that all factors will be surrounded by parentheses. For example, x(x+1) will always be (x)(x+1).
There will never be any other operation besides multiplication between parenthesis. This will never happen: (x)+(x+1).
You may assume there will never be any nested parentheses/exponents.
Order of the resulting expression should be highest exponents first, as per usual math standards. Otherwise, order does not matter.
You may assume single digit exponents
Built in expansion libraries/functions are not allowed, as the comments mention below

Examples
(x+1)(x+2) --> x^2 + 3x + 2
(a)(a-4) --> a^2 - 4a
(c+1)^3 --> c^3 + 3c^2 + 3c  + 1
(a+1)(f-2) --> af - 2a + f - 2
(x-2)(x+4)(x-5)(x+10) --> x^4 + 7x^3 - 48x^2 - 140x + 400
(x+a+c)(b+g) --> xb + xg + ab + ag + cb + cg
(r+4)^2(b) --> br^2 + 8br + 16b

This is code-golf, so shortest program wins!
Bonus
-25 bytes to anyone who makes their program compatible with complex numbers

This would be pretty easy in languages like Matlab and Mathematica that have algebraic simplification built in.

Seems too easy in some languages: http://reference.wolfram.com/language/ref/Expand.html

usual math standards? I must have skipped that class...

You might want to disallow using built-in CAS functions to make this challenge a bit more fair for all languages.

I voted for closing as duplicate, but in fact the requirements are quite different, so I'm not so sure.

I think the rules currently allow x^2 - 3x + 2x - 6 as output.

About the order by high exponent first, what if there are 2 variables (x^2+xy+y^2? x^2+y^2+xy? ). And 3 or more?

The spaces before and after a + or - must be present. So (1-x)(x-1) -> " - x^2 + 2x - 1" (ugly). Space before but not after would be better: " -x^2 +2x -1"

JavaScript (E6) 834
While waiting for some clarification by OP, I start recycling my answer from  this other question
It's more than what is required here, so it could be golfed more.
I have modified the spacing and added sorting by higher exponent (of any variable).
G=x=>x.replace(/\d/g,n=>' '.repeat(n-2)).length,
K=x=>Object.keys(x).sort((a,b)=>G(b)-G(a)),
A=(p,q,s,t,c)=>[(c=(s+1)*q[t]+~~p[t])?p[t]=c:delete(p[t])for(t in q)],
M=(p,q,t,c,o,u,f,r,v={})=>([A(v,(r={},[(c=p[f]*q[t])&&(r[o={},(u=f+t)&&(u.match(/[a-z]\^?\d*/ig).map(x=>o[x[0]]=~~o[x[0]]+(~~x.slice(2)||1)),K(o,u=k).map(i=>u+=o[i]>1?i+'^'+o[i]:i)),u]=c)for(f in p)],r),k)for(t in q)],v),
E=(p,n)=>--n?M(p,E(p,n)):p,
O=n=>{for(l=0;h(o=s.pop())>=h(n);)a=w.pop(b=w.pop()),o=='*'?a=M(a,b):o>d?a=E(a,b[k]):A(a,b,o),w.push(a);s.push(o,n)},
X=e=>(l=k='',w=[],s=[d='@'],h=o=>'@)+-*^('.indexOf(o),
(e+')').match(/\D|\d+/g).map(t=>(u=h(t))>5?(l&&O('*'),s.push(d)):u>1?O(t):~u?s.pop(s.pop(O(t)),l=1):(l&&O('*'),l=1,w.push(v={}),t<d?v[k]=t|0:v[t]=1)),
K(p=w.pop()).map(i=>(k+=(c=p[i])>1?s+c+i:c<-1?c+i:(c-1?'-':s)+(i||1),s=' + ')),k.replace(/-/g,' - ')||0)

Test in FireFox/FireBug console
;["(x+1)(x+2)","(a)(a-4)","(c+1)^3","(a+1)(f-2)","(x-2)(x+4)(x-5)(x+10)","(x+a+c)(b+g)","(r+4)^2(b)"]
.map(x => console.log(x + " -> " + X(x)))

Output
(x+1)(x+2) -> x^2 + 3x + 2
(a)(a-4) -> a^2 - 4a
(c+1)^3 -> c^3 + 3c^2 + 3c + 1
(a+1)(f-2) -> af + f - 2a - 2
(x-2)(x+4)(x-5)(x+10) -> x^4 + 7x^3 - 48x^2 - 140x + 400
(x+a+c)(b+g) -> xb + ab + cb + xg + ag + cg
(r+4)^2(b) -> r^2b + 8rb + 16b

Mathematica 11-25=-14 40-25=15 characters
Really too easy in this language:
f=TraditionalForm@Expand@ToExpression@#&

Usage:
f["(x+2)(x-3)"]

Output:
x2 - x - 6
And it's even shorter if you allow input that isn't a string (and don't care about term order):
f=Expand@ToExpression@#&

Used as follows for the same output:
f[(x+2)(x-3)]

Mathematica can natively support complex numbers.
EDIT: technically this answer fails because it will take ab (without spaces) as a single variable instead of a*b as per the rules.
EDIT2:Changed so it will output in the required order

I thought about posting this as well. I don't think the ab is a problem, because it doesn't seem to be part of the input. However, (and this is the reason I didn't post it) the order of the terms needs to be the opposite.

Good point, ab will be more difficult to solve, but at least the order of the terms can be fixed.

Oh, actually the rules changed since I saw the challenge: "Built in expansion libraries/functions are not allowed." So this approach isn't allowed anyway.

Ah dang, missed that... whoops. well, maybe I'll update it later to a form that doesn't use it, but I don't think I will.

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


text:
Little Chandler is sad. Draw him a cloud to cheer him up
Little Chandler is sad. Draw him a cloud to cheer him up.
Note: Drawing a cloud won't actually cheer him up.
A circle can be defined as a 3-tuple (x,y,r) where x is the x position of the circle on a Cartesian plane, y is the y position of the circle on a Cartesian plane, and r is the radius of the circle. x and y may be negative. r is always positive. The input is a list of circles in the form of space separated 3-tuples. For instance:
3,1,1 3,2,1.5 1,2,0.7 0.9,1.2,1.2 1,0,0.8

The 3,1,1 means "A circle with centre point at 3,1 with 1 radius. 3,2,1.5 means "A circle with centre point at 3,2 with 1.5 radius.
If we draw all of these circles of the input on a graph, it looks like this (I've included grid lines and labels for clarity only; they are not required):

Notice how all the circles are cohesive. That is, they're all overlapped together such that it forms one large group without any small groups of circles separated from the rest. The input is guaranteed to be cohesive.
Suppose now we draw a line that travels around the "border" formed by these circles, without any of the other lines. It would be like drawing the border of the silhouette formed by all the circles. The resulting cloud would look something like this:

So this cloud has been formed by drawing only the arcs of the circles in the input that form a border, resulting in a single shape. In other words, the cloud is formed by only drawing the arcs that are not within another circle. Your program will take in input in the form explained above, and output an image that displays the resulting cloud. The overall shape of the cloud must be correct, but the scale, colour, line thickness, and how it looks at vertexes is up to you. Note that the cloud must be visible, so you can't pull something like "This program draws a white cloud on a white background", "This program draws a cloud at a infinitesimally small scale", "This program draws a cloud with 0 line thickness", etc. Also note that the colour of the border must be different from the colour of the fill or background.
Another example. Input:
1,4,2 5,2,1 3,1,1 3.5,2,1.2 3,3,0.7 1,2,0.7

Output:

If there is a "hole" in the cloud, you should draw the hole as well. Input:
0,5,4 3,4,4 4,3,4 5,0,4 4,-3,4 3,-4,4 0,-5,4 -3,-4,4 -4,-3,4 -5,0,4 -4,3,4 -3,4,4

Output:

Here is an important rule: your program must draw only the lines that form the border. This means that you CANNOT simply draw the circles fully, and then draw the circles slightly smaller with a white fill -- because that method still draws lines that don't form a border, it just covers them up afterwards. The purpose of the rule was to prevent the "draw the circles, then draw the circles again with a white fill" implementations, or anything similar to that. The answer is expected to actually calculate where to draw things before drawing it.
This is code golf, so the shortest character count wins.

+1 for an graphical-output question with an objective winning criterion (and the first paragraph).

How can you tell if we draw a line and erase it afterwards? Is rendering said lines onto internal bitmaps OK? If not, where is the border, between a vector and a bitmap representation? If yes, why not let us do the same with the primary canvas (that we know is double-buffered, so that the user can't see our temporary lines)?

@JanDvorak The purpose of the rule was to prevent the "draw the circles, then draw the circles again with a white fill" implementations, or anything similiar to that. The answer is expected to actually calculate where to draw things  before drawing it. I'll edit to make it more clear.

When you say the colour of the cloud is up to us, does that include the interior or only the outline? Also what about axes? Do we need to omit those?

Does it have to be a full program, or a functions allowed?

@MartinBüttner You may omit axes. Both the interior and the outline may be whatever colour you choose. Functions are not allowed - I use the diction "your program" in the question.

@Lilac I doubt it would win a code golf, but would drawing the circles against a background of a different colour, and then performing edge detection be allowed? It only draws the circles once, and that is an intermediate stage that allows the line drawing function to create a new image as the output. Does this count as similar to the 2x circles method?

In the last example there is a radius -4. A typo?

This question is absolutely hilarious with Cloud to Butt (https://chrome.google.com/webstore/detail/cloud-to-butt-plus/apmlngnhgbnjpajelfkmabhkfapgnoai?hl=en) installed.

Can I "output" a svg file ?

@Erty I've got that!  I read through the example and was thinking "That doesn't look like a butt at all..."

@edc65 That's a typo, yes. It's supposed to be 4. Will edit.

@user80551 Yes.

@SomeKittens I lost it at "If there is a "hole" in the cloud, you should draw the hole as well."

@Baldrickk - That's okay. As long as it's not the drawing circles with a slightly smaller radius method.

By "as long as it's not the drawing circles with a slightly smaller radius method" do you mean that I can make a black background and draw white borderless circles on it?

@ace No. That's not really in the spirit of the question - I'll edit for a new rule to exclude that.

@SomeKittens I was going to say, those are some horribly deformed butts it's drawing!

Mathematica 177 126 121 119
Solving by Disk Regions: the mathematician's approach
The logic is to

Create Region 1 (R1), the circles (without their interiors);
Create Region 2 (R2),  the disks (without the circle borders).
Create Region 3 (R3 = R1-R2).
 -

This is precisely the approach taken below.  It produced the 3 figures above.
input = "3,1,1 3,2,1.5 1,2,0.7 0.9,1.2,1.2 1,0,0.8";
circles = ((x - #)^2 + (y - #2)^2 == #3^2) & @@@
     ToExpression[#~StringSplit~","] &@(StringSplit@input);
R1 = ImplicitRegion[Or @@ circles, {x, y}];
r1 = RegionPlot[R1, PlotLabel -> "R1: circles containing borders",
   AspectRatio -> 1, PlotRange -> {{-1, 5}, {-1, 5}}];

innerDisks = ((x - #)^2 + (y - #2)^2 < #3^2) & @@@
     ToExpression[#~StringSplit~","] &@(StringSplit@input);
R2 = ImplicitRegion[Or @@ innerDisks, {x, y}];
r2 = RegionPlot[R2, PlotLabel -> "R2: disks within circle borders",
   AspectRatio -> 1, PlotRange -> {{-1, 5}, {-1, 5}}];
R3 = RegionDifference[R1, R2]
r3 = RegionPlot[R3, PlotLabel -> "R3 = R1-R2", AspectRatio -> 1,
   PlotRange -> {{-1, 5}, {-1, 5}}];
GraphicsGrid[{{r1, r2, r3}}, ImageSize -> 600]

Implicit region #1 is the union of the circles.
Implicit region #2 is the union of the disks lying within the circles.
Their difference is the border.

RegionDifference[
   ImplicitRegion[(-3 + x)^2 + (-1 + y)^2 ==
      1 || (-3 + x)^2 + (-2 + y)^2 == 2.25 || (-1 + x)^2 + (-2 + y)^2 ==
       0.49 || (-0.9 + x)^2 + (-1.2 + y)^2 ==
      1.44 || (-1 + x)^2 + y^2 == 0.64, {x, y}],
   ImplicitRegion[(-3 + x)^2 + (-1 + y)^2 <
      1 || (-3 + x)^2 + (-2 + y)^2 < 2.25 || (-1 + x)^2 + (-2 + y)^2 <
      0.49 || (-0.9 + x)^2 + (-1.2 + y)^2 < 1.44 || (-1 + x)^2 + y^2 <
      0.64, {x, y}]]

Solving by Disk Regions: the engineer's approach (119 chars)
The following takes the union of the disk regions,
discretizes that region, and finds it's boundary.  The points in the diagram demarcate the intervals of the Delaunay mesh.  We display the discretized region below to highlight the object that furnishes the boundary of interest (the outline of the cloud).
s = StringSplit;RegionBoundary@DiscretizeRegion[RegionUnion[Disk[{#, #2}, #3] &@@@
ToExpression[#~s~","] &@(s@InputString[])]]

"3,1,1 3,2,1.5 1,2,0.7 0.9,1.2,1.2 1,0,0.8"
The region boundary is discretized.

Solving by Detecting Edges: The Photographer's Approach - 121 chars

It draws the disks in black, rasterizes the image, detects the edges, and inverts black and white.
s=StringSplit;ColorNegate@EdgeDetect@Rasterize@Graphics[Disk[{#,#2},#3]&@@@
((ToExpression/@s[#,","])&/@s[InputString[]])]

Shaved off 5 bytes: RegionBoundary@DiscretizeRegion@RegionUnion[{#,#2}~Disk~#3&@@@ToExpression[#~s~","]&@s@InputString[s=StringSplit]]

Potentially the s=StringSplit inside the prompt? Try moving that in front again, should still be shorter than your current version.

T-SQL 235 234 229 212 171 73 bytes
This makes use of spatial functionality in SQL Server 2012+.  When it is run in SSMS (SQL Server Management Studio) is produces a spatial results pane.
The input is from variable @i.  I could reduce it further if the input could be taken from a table.
Since table input is now allowed.
SELECT Geometry::UnionAggregate(Geometry::Point(X,Y,0).STBuffer(R))FROM A

I've left the previous solution below.
DECLARE @ VARCHAR(999)='WITH a AS(SELECT *FROM(VALUES('+REPLACE(@i,' ','),(')+'))A(X,Y,R))SELECT Geometry::UnionAggregate(Geometry::Point(X,Y,0).STBuffer(R))FROM a'EXEC(@)

Edit: Remove stray space, surplus into and subquery
171: Replaced table creation with CTE and @s with @.

Break down of the Dynamic SQL
DECLARE @i VARCHAR(100) = '1,4,2 5,2,1 3,1,1 3.5,2,1.2 3,3,0.7 1,2,0.7' -- Input
DECLARE @ VARCHAR(999) = '
WITH a AS(                                       --CTE to produce rows of x,y,r
    SELECT *FROM(VALUES('+
        REPLACE(@i,' ','),(')                    --Format @i to a value set
        +'))A(X,Y,R)
)
SELECT Geometry::UnionAggregate(                 --Aggregate Buffered Points
    Geometry::Point(X,Y,0).STBuffer(R)           --Create point and buffer
    )
FROM a                                           --from the table variable
'
EXEC(@)                                          --Execute Dynamic sql

I'm getting an error saying 'A' has fewer columns than were specified in the column list

@JesanFafon Make sure your input variable @i is set correctly. DECLARE @i VARCHAR(100) = '1,4,2 5,2,1 3,1,1 3.5,2,1.2 3,3,0.7 1,2,0.7'.  Unfortunately I can't test at he moment and SQLfiddle isn't playing nicely for 2012.

Nice work with SQL geometry functions. Good news! Input by pre-existing table is now explicitly allowed. Table creation and population need not be included in the byte count.

I golfed a few characters. The link doesn't produce a result. But it works in ms-sql server management studio. Script is here, enjoy. Feel free to use it

@t-clausen.dk thanks for that, but since I am going to update it I will change it to allowed table input.  I wasn't going to dredge this one back up, but...

Mathematica, 175 158 149 bytes
s=StringSplit;l=ToExpression[#~s~","]&@s@InputString[];RegionPlot[Or@@(Norm@{x-#,y-#2}<#3&@@@l),{x,m=Min@(k={{##}-#3,{##}+#3}&@@@l),M=Max@k},{y,m,M}]

I remember from discussion in the sandbox that this approach was supposed to be valid, but I'm not entirely sure how it sits with the new wording of the rules, so @Lilac, let me know if you think this violates the rules.
Basically, I'm creating a logical condition which is true for all points inside the cloud and false for all points outside it. I'm feeding that to RegionPlot which then renders the region of all points where the expression is True as well as an outline around it.

Ungolfed:
s = StringSplit;
l = ToExpression[#~s~","] &@s@InputString[];
RegionPlot[
 Or @@ (Norm@{x - #, y - #2} < #3 & @@@ l),
 {x, m = Min@(k = {{##} - #3, {##} + #3} & @@@ l), M = Max@k},
 {y, m, M}
]

ImplicitRegion automatically finds the proper x and y values for plotting. 122 chars: s = StringSplit; RegionPlot@  ImplicitRegion[   Or @@ (((x - #)^2 + (y - #2)^2 < #3^2) & @@@ (ToExpression[#~s~","] &@(s@InputString[]))), {x, y}]

@DavidCarraher Unfortunately, this distorts the aspect ratio of the image. (Nice to know all those region functions though - also the ones you used - I've only seen RegionPlot so far.)

You probably already noted that ,AspectRatio-> 1 brings the code back to 149 bytes, exactly where it stands now.

Is it me or does this image look like Marvin the Paranoid Android?

Python 3.3 (183 177 164 160 bytes)
B=list(map(eval,input().split()))
print("".join(" ## "[sum(any(r*r>(x-d%80/4+10)**2+(y+d//80/4-10)**2for
x,y,r in B)for d in[i,i+1,i+80])]for i in range(6400)))

It requires an 80 character wide console, which I know is the default in Windows.  It works best if your console has a square font.  Here are some excerpts from some of the test inputs.
Original:
           ########
          ##       #
         ##         #
     #####          #
    ##   #          #
   ##               #
  ##                #
 ##                 #
 #                  #
 #                 ##
  #               ##
  #       ##      #
   #      # #    ##
   #      #  #####
   #      #
    #    ##
     #  ##
      ###

Another:
    ########
  ###       ##
 ##           #
 #            #
##             #
#              #
#              #
#              #
#              #
#               ##
#                 #
 #                 ##
 #                   ######
  #                        #
   ##      ###             #
     #    ## #             #
     #    #  #             #
      #  ## ##             #
       ###  #             ##
            #       #######
            #      ##
            #      #
             #    ##
              #####

Hole:
                              ############
                            ###           ##
                          ###               ##
                         ##                   #
                  ########                     #######
                ###                                   ##
              ###                                       ##
             ##                                           #
            ##                                             #
           ##                                               #
          ##                                                 #
         ##                                                   #
        ##                                                     #
       ##                                                       #
      ##                                                         #
      #                                                          #
     ##                                                           #
     #                                                            #
    ##                                                             #
    #                                                              #
    #                                                              #
    #                                                              #
    #                                                              #
    #                                                              #
    #                                                              #
   ##                                                               #
  ##                                                                 #
  #                                                                  #
 ##                                                                   #
 #                                                                    #
##                                                                     #
#                                 ####                                 #
#                                ##   #                                #
#                               ##     #                               #
#                              ##       #                              #
#                              #        #                              #
#                              #        #                              #
#                               #      ##                              #
#                                #    ##                               #
#                                 #  ##                                #
#                                  ###                                 #
 #                                                                    ##
 #                                                                    #
  #                                                                  ##
  #                                                                  #
   #                                                                ##
    #                                                              ##
    #                                                              #
    #                                                              #
    #                                                              #
    #                                                              #
    #                                                              #
    #                                                              #
     #                                                            ##
     #                                                            #
      #                                                          ##
      #                                                          #
       #                                                        ##
        #                                                      ##
         #                                                    ##
          #                                                  ##
           #                                                ##
            #                                              ##
             #                                            ##
              #                                          ##
               ##                                      ###
                 ##                                  ###
                   #######                    ########
                          #                  ##
                           ##              ###
                             ##          ###
                               ###########

I love that this is the only ascii art solution.

no imports... impressive!

Python - 253 249 215 199
This is an advertisement for the awesome shapely library, whose geometry operations made writing the solution straightforward by drawing the outline(s) of the union of overlapping circles (=buffered points):
from pylab import*
from shapely.geometry import*
c=Point()
for s in raw_input().split():
 x,y,r=eval(s)
 c=c.union(Point(x,y).buffer(r))
plot(*c.exterior.xy)
for i in c.interiors:
 plot(*i.xy)
show()

Output:

Edit(s):

249: Replaced sys.argv[1:] by raw_input().split(), saving a import sys
215: Removed k={'color':'k'} luxury, replaced savefig by show
199: Replaced map(float,s.split(',')) by eval(s)

Python – 535
import math as m
import matplotlib.pyplot as l
c = "3,1,1 3,2,1.5 1,2,0.7 0.9,1.2,1.2 1,0,0.8"
a = [[float(y) for y in x.split(",")] for x in c.split(" ")]
for a2 in a:
    for x in xrange(0,200):
        q=x*m.pi/100.0
        p=(a2[0]+m.sin(q)*a2[2], a2[1]+m.cos(q)*a2[2])
        cc = []
        for z in a:
            if z != a2:
                if ((z[0] - p[0]) ** 2 + (z[1] - p[1]) ** 2 ) < (z[2] ** 2) :
                    cc.append(z)
        if not cc:
            l.scatter(p[0],p[1])
l.show()

This has a lot potential for being golfed down further, e.g., by from math import* removing unneded spaces, using one-letter variable names only, using list comprehension (e.g., cc=[z for z in a if z!=a2 and (z[0]…)]). Also take a look at the tips for golfing in Python.

You could save some characters by using a one-letter variable name instead of a2.

thanks wrzl... I will probably start golfing tonight (other things to do right now but wanted to put a stake in the ground)

yes @ProgramFOX ... this was a version that worked and that I could debug.. will get it shorter tonight...

Had a play with this and managed to get it down to 320 chars.

@JamesWilliams if you want to take the baton... please do .. I'm not protective of the code !! Feel free to add it as your own entry (as long as you credit the original !)

Sure, I'll add it as my own answer, and credit you in there. I'm sure it can be golfed further but I'm new to this and I think I have got it as far as I can go. Thanks!

I've golfed your code down to 418 characters. You should also use single character variables in golfing.

@RichardGreen it's usually nice to have both an un-golfed version (usually what you develop to get the logic right and so people can see the logic), then crush it down to a golfed version that you score.

Thanks @NickT .. I handed the baton over to JamesWilliams .. I don't think I'll beat his golf score

Python – 296 249 231 223 212
from pylab import*
a=map(eval,raw_input().split())
for x,y,r in a:
 for i in range(200):
  q=i*pi/100;p=x+r*sin(q);t=y+r*cos(q);[z for z in a if z!=(x,y,r)and(z[0]-p)**2+(z[1]-t)**2<z[2]**2]or scatter(p,t)
show()

Credit goes to @richard-green (permission was given) for the original solution, I've just whittled it down a bit.

well that gets my vote...

You might be able to save some more by importing pylab instead of matplotlib.pyplot.

@odjo Currently on mobile, if I used from pylab import * would I still be able to call show() and scatter() without any references?

@JamesWilliams confirmed! Pylab is a namespace polluter, including many MATLAB-like functions :-)

You can shorten this by using [eval(i)for i in raw_input().split()] as python's eval turns 1,2,3 into a tuple. You will also of course have to change the [x,y,r] to a (x,y,r).

You can also reduce the count by reducing the indentation to one space, and you may be able to remove it entirely.

Python 274 bytes
This takes input from stdin and checks every point on the display, drawing the pixels one by one as it goes. Not exactly efficient but it follows all the rules.
c=[eval(s)for s in raw_input().split()]
import pygame
S=pygame.display.set_mode((500,500))
S.fill([255]*3)
for p in((x,y)for x in range(500)for y in range(500)if 0<min((((x-250)/25.-a)**2+((y-250)/25.-b)**2)**.5-r for(a,b,r)in c)<.1):S.set_at(p,[0]*3)
pygame.display.update()

Note that the pygame display will terminate as soon as the drawing is complete, I wasn't sure if I should include it as part of my answer but to view it you can either throw a raw_input in at the end or add a little loop if you want to stop the OS from complaining about it not responding and such:
alive = True
while alive:
    pygame.display.update()
    for e in pygame.event.get():
        if e.type == pygame.QUIT:
            alive = False

Example images:
1,4,2 5,2,1 3,1,1 3.5,2,1.2 3,3,0.7, 1,2,0.7

0,5,4 3,4,4 4,3,4 5,0,4 4,-3,4 3,-4,4 0,-5,4 -3,-4,4 -4,-3,4 -5,0,4 -4,3,4 -3,4,4

@edc65 I'm not quite sure what you mean. What it does precisely is fill in any pixel that is between 0 and 0.1 units (between 0 and 2.5 pixels) outside the circles. Are you saying it should mathematically find the correct arcs to draw? From reading the question it didn't seem like that was a restriction to me.

JavaScript (E6) + HTML 322
JSFiddle
Each circle is subdivided in about 100 small arcs, and each arc is drawn if its middle point is not inside any of the other circles.
<canvas id='c'/>
<script>
t=c.getContext("2d"),z=99,c.width=c.height=400,
l=prompt().split(' ').map(c=>c.split(',').map(v=>40*v)),
l.map(c=>{
  for(i=z;--i+z;)
    s=4/z,r=c[2],x=c[0]+r*Math.cos(a=i*s),y=c[1]+r*Math.sin(a),
    t.beginPath(),
    l.some(q=>c!=q&(d=x-q[0],e=y-q[1],d*d+e*e<q[2]*q[2]))||t.arc(z+c[0],z+c[1],r,a-s,a+s),
    t.stroke()
})
</script>

Perl - 430
@e=map{[map{int($_*32)}split',']}(split' ',<>);for$g(@e){for(0..3){($a[$_]>($q=$$g[$_&1]+(($_>>1)*2-1)*$$g[2]))^($_>>1)&&($a[$_]=$q)}}for(2,3){$a[$_]-=$a[$_-2]-1}for(@e){($x,$y,$r)=@$_;$x-=$a[0];$y-=$a[1];for$k($x-$r..$x+$r){for$l($y-$r..$y+$r){$i=(int(sqrt(($x-$k)**2+($y-$l)**2)+0.5)<=>$r)-1;$f[$l][$k]=($j=$f[$l][$k])<-1||$i<-1?-2:$i||$j;}}}print"P1
$a[2] $a[3]
".join("
",map{join' ',map{$_+1?0:1}@$_,('0')x($a[2]-@$_)}@f)."
"

Writes a pbm file to stdout.
Test image (converted to png):

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


text:
Un-round fractions
When you convert a fraction to a decimal number and you want to store that number, you often have to round it, because you only want to use a certain amount of memory. Let's say you can only store 5 decimal digits, then  5/3 becomes 1.6667. If you can store only 2 decimal digits it will be 1.7 (now assuming that it is always between 0 and 9.99...).
If you now try to reverse that process with 1.7 and you want to get your fraction back, that can be difficult, since you know that 1.7 is only a rounded number. Of course you can try 17/10 but that is rather an 'ugly' fraction compared to the 'elegant' 5/3.
So the goal is now finding the fraction a/b with the least denominator b, that results in the rounded decimal number when correctly rounded.
Details
The input contains a string with a number of 1 up to 5 digits that is between 0 (including) and 10 (not including) with a '.' after the first digit. Let's say n denotes the number of digits. The output must be a list/array of two integers [numerator, denominator] or a rational datatype (you can create your own or use built-in) where the numerator is non-negative and the denominator is positive.  The fraction numerator/denominator must be equal to the input when correctly rounded to n digits (which means n-1 digits after the decimal point).
Restriction: only one loop statement allowed. This means that you can use only one single looping statement (like for or while or goto etc. as well as functional loops like map or fold that apply code to every element of a list/array) in your whole code, but you are free to 'abuse' it or use recursion etc.
You should write a function. If your language does not have functions (or even if it does), you can alternatively assume that the input is stored in a variable (or input via stdin) and print the result or write it to a file. The lowest number of bytes wins.
Rounding
The rounding should follow the 'conventional' rounding rules, i.e. if the last digit that will be cut off is 5 or greater, you will round up, and you will round down for any other cases, so e.g:
4.5494 will result when rounding to

1 digit:  5
2 digits: 4.5
3 digits: 4.55
4 digits: 4.549

Examples
Please include following test cases and other 'interesting' ones:
Input 1.7     Output 5/3
Input 0.      Output 0/1
Input 0.001   Output 1/667
Input 3.1416  Output 355/113

Thank you for these thougths: Since I am not used to both I ask you: What would you recommend? I think I have to allow functions like map etc but I'd disallow the output of a rational type. @ rounding: I will specify this, thanks.

Thank you for the assistance, I think that should make sense now. Do you think that is an acceptable 'definition' I wrote down of functions like map?

Yes, sounds good. Alternatively "... that apply a named or anonymous function repeatedly." E.g. Mathematica has Nest, which isn't applied to a list, but still creates a loop.

But in functional languages there is no such a thing as a loop. Foe example in haskell repeat creates an infinite list of its argument. I t seems to loop but it actually has time complexity of O(1). But i guess sorting each case individually is better than not allowing functional languages.

I don't like the current definition of "loop".  In Python, for example, for n in numbers: f(g(n)) is equivalent to map(f, map(g, numbers)).  The functional version uses map twice, should that really be disallowed?

maybe have a bonus for no loops at all?

@proudhaskeller As I read it, functional loops aren't disallowed, but are allowed exactly once like any other loop.

@MartinBüttner I talked about the case that functional languages would be disallowed because of ambiguity

I am sorry that I cannot really contribute to that discussion since my knowledge about functional programming is basically zero. If you have a solution of which you are unsure about whether it complies with the 'rules' please submit it anyway! In the end it is supposed to be a fun and educational challenge!

I'm curious: Why does it have to be a function? Why can't we submit programs?

@Dennis No that was unfortunate wording, you can submit it in any form you like, the main idea behind that paragraph was that you should not have a disadvantage if your language takes more bytes for 'reading' the input number.

@proudhaskeller I even thought about that in the first place but was too lazy to figure out a way of making that bonus happen. I suggest that you can pat yourself on your shoulder twice if you make it without any loops? =)

@flawr I did infact

Do implicit loops count? In array languages like J or APL, each verb introduces an implicit loop. If implicit loops counted, this would be impossible to do in APL.

CJam, 41 40 36 bytes
Q'./1=,:L0\{;)_Qd*mo_d2$/LmOQd-}g'/@

Asuumes the input string is stored in Q, which is explicitly allowed by the question. Try it online.
Test cases
$ for d in 1.7 0. 0.001 3.1416; do cjam <(echo "\"$d\":Q;
> Q'./1=,:L0\{;)_Qd*mo_d2$/LmOQd-}g'/@
> "); echo; done
5/3
0/1
1/667
355/113

How it works
Q'./1=,:L  " Count the number of characters after the dot and store it in L.     ";
0\         " Push 0 (denominator) and swap it with L (dummy value).              ";
{          "                                                                     ";
  ;        " Discard the topmost item from the stack (numerator or dummy value). ";
  )        " Increment the denominator.                                          ";
  _Qd*mo   " Multiply a copy by Double(Q) and round.                             ";
  _d2$/    " Cast a copy to Double and it divide it by the denominator.          ";
  LmO      " Round to L digits.                                                  ";
  Qd       " If the result is not Double(Q),                                     ";
}g         " repeat the loop.                                                    ";
./@        " Push a slash and rotate the denominator on top of it.               ";

T-SQL 254
While T-SQL isn't really suited to this sort of thing, it wa fun to try. The performance gets real bad the higher the denominator.  It is limited to a denominator of 1000.
Input is a float variable @
WITH e AS(SELECT *FROM(VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9),(0))n(n)),t AS(SELECT ROW_NUMBER()OVER(ORDER BY(SELECT \))N FROM e a,e b,e c,e d)SELECT TOP 1concat(n.n,'/',d.n)FROM t d,t n WHERE round(n.n/(d.n+.0),len(parsename(@,1)))=@ ORDER BY d.n,n.n

A breakdown of the query
WITH                                      -- Start CTE(Common Table Expression)
 e AS(                                    --Create a set of 10 rows
   SELECT *
   FROM(VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9),(0))n(n)
 ),
 t AS(
   SELECT ROW_NUMBER()OVER(ORDER BY(SELECT \))N
   FROM e a,e b,e c,e d                   --Cross join e to produce 1000 numbered rows
 )
SELECT
  TOP 1                                   --Grab first result
  concat(n.n,'/',d.n)                     --Build output
FROM t d,t n                              --Cross join t against itself for denominator and numerator
WHERE round(
  n.n/(d.n+.0),                           --Force float division with +.0
  len(parsename(@,1))                     --Get rounding length
  )=@                                     --Filter where the rounded result = input
ORDER BY d.n,n.n                          --Order by denominator then numerator

+1. I love it. I put in 3.14159 and it duly gave me 355/113

+1 I never expected to see an SQL language here!!!

@TomChantler I suspect you mean eventually :)

@flawr To be honest I didn't think it was going to work .. very brute force method though.

Haskell, 62 59
if only the names weren't so long...
import Data.Ratio
f s=approxRational(read s)$50/10^length s

this is a function returning a Rational value.
explanation:
the function approxRational is a function which takes a float number and a float epsilon and returns the most simple rational which is in distance epsilon of the input. basically, returns the most simple approximation of the float to a rational in a "forgivable error" distance.
let's exploit this function for our use. for this we will need to figure out what is the area of the floats that round up to the given number. then getting this into the approxRational function will get us the answer.
let's try 1.7, for example. the lowest float that rounds to 1.7 is 1.65. any lower will not round to 1.7. similarly, the upper bound of the floats that round to 1.7 is 1.75.
both limits are the bounds are the input number +/- 0.05. it can be easily shown that this distance is always 5 * 10 ^ -(the length of the input - 1) (the -1 is because there is always a '.' in the input). from here the code is quite simple.
test cases:
*Main> map f ["1.7", "0.001", "3.1416"]
[5 % 3,1 % 667,355 % 113]

unfortunately it doesn't work on "0." because Haskell's parser function doesn't recognize a . at the end of a float. this can be fixed for 5 bytes by replacing read s by read$s++"0".

It's an interesting function to have. Ordinarily such functions exist for the purpose of finding the best rational approximation to a number in the fewest steps, which is provably accomplished using truncated continued fraction representations. Alternatively, finding a fraction with the lowest denominator is more an academic curiosity. One ordinarily wouldn't expect to find it as a standard library function.

@COTO Well, this is Haskell, it is full of academic research.

Ruby, 127 125 bytes
f=->n{b=q=r=(m=n.sub(?.,'').to_r)/d=10**p=n.count('0-9')-1
b=r if(r=(q*d-=1).round.to_r/d).round(p).to_f.to_s==n while d>1
b}

Defines a function f which returns the result as a Rational. E.g. if you append this code
p f["1.7"]
p f["0."]
p f["0.001"]
p f["3.1416"]

You get
(5/3)
(0/1)
(1/667)
(355/113)

The loop is over denominators. I'm starting with the full fraction, e.g. 31416/10000 for the last example. Then I'm decrementing the denominator, proportionally decrement the numerator (and round it). If the resulting rational rounds to the same as the input number, I'm remembering a new best fraction.

Python 2.7+, 111 characters
Proof that you can write horrible code in any language:
def f(s):
 t,e,y=float(s),50*10**-len(s),1;n=d=x=0
 while x|y:n,d=n+x,d+y;a=1.*n/d;x,y=a<t-e,a>t+e
 return n,d

Output
>>> [f(s) for s in ("1.7", "0.", "0.001", "3.1416")]
[(5, 3), (0, 1), (1, 667), (355, 113)]

Mathematica, 49 53 characters
Rationalize[ToExpression@#,5 10^(1-StringLength@#)]&@

Usage:
Rationalize[ToExpression@#,5 10^(1-StringLength@#)]&@"1.7"

Output:
5/3

Test cases:
input: 1.7     output: 5/3
input: 0.      output: 0
input: 0.001   output: 1/999
input: 3.1416  output: 355/113

The 0.001 case strikes me as odd; as the rationalize function didn't work according to its description, when it didn't find the 1/667 case.
It should output the number with the smallest denominator that is within specified bounds.

haha I used the exact same solution. too bad in Haskell it's longer. btw, it doesn't look like your solution takes a string as an input as is required by spec.

Wait, the input was a string?
Dang, that means I can pull some stuff out of the code.

Your output for 0.001 doesn't match the OP because Rationalize isn't under the constraint to minimize the denominator. As I mentioned to proud haskeller, a rational approximation function subject to minimizing the denominator is highly esoteric (in short because it's a lousy and inefficient way to approximate numbers). I ordinarily wouldn't expect it to be a standard library function.

@COTO According to the docs it does minimise the denominator though.

@MartinBüttner: It is kind of interesting that it outputs 1/999. 999 becomes the (acceptable) lowest denominator only for an error between roughly 1e-6 and 2e-6. The error bound is clearly 5e-4. So whatever Mathematica is doing in that case, it definitely isn't working to spec. :P

@COTO I guess this would be a useful function if you calculated some floating point math and wanted to get the result as a rational. If we calculated, lets say, 2/3, then although 6666667/1000000 or whatever is closer to the float in memory but 2/3 is much more likely to be the true result

@COTO i mean if we wanted to get a 100% correct rational from a math expression which is a rational

This is just a guess, but perhaps the error is due to the decimal point being included in the string length?

@Martin You are correct, I forgot that the first part needed to be converted from a string as well... Changing stuff again...

@proudhaskeller: I agree with you on why the spec selects the lowest denominator, and Mathematica is the kind of academically-oriented language that I'd expect to have such a function. For most languages, the only things that would matter are 1) whether the rational approximation meets the error spec, and 2) speed. And finding the rational with the lowest denominator is most definitely not a fast approach. There are other approaches that will find fractions with "reasonably" low denominators in a tiny fraction of the time.

@COTO well, the implementation of approxRational doesn't Just check every Rational, it has a specific algorithm. I haven't worked out how it works though. so I don't really know what is the time Complexity, but it seems to be efficient.

@COTO it seems to have some similarities to the gcd algorithm

APL, 50
2↑⍎⍕(⍎x←⍞){50>|(10*⍴x)×⍺-⍵÷⍨n←⌊.5+⍺×⍵:n ⍵⋄''}¨⍳1e5

As long as you don't count eval and toString as loops
Explanation
The approach is to iterate over 1 to 10000 as denominator and calculate the numerator that most closely match the float, then check if the error is within bounds. Lastly, select the smallest pair from all the fractions found.
(⍎x←⍞) Take string input from screen, assign to x, and eval
⍳1e5 Generate array from 1 to 10000
{...}¨ For each element of the array, call function with it and (⍎x←⍞) and arguments (loop)
⍺×⍵ Multiply the arguments
⌊.5+ Round off (by adding 0.5 then rounding down)
n← Assign to n
⍺-⍵÷⍨ Divide by right argument, then subtract from left argument
(10*⍴x)× Multiply by 10 to the power of "length of x"
| Take absolute value
50> Check if less than 50 (length of x is 2 more than the no. of d.p., so use 50 here instead of 0.5)
:n ⍵⋄'' If the previous check returns true, then return the array of n and the right argument, else return empty string.
⍎⍕ toString and then eval to get an array of all the numbers in the array
2↑ Select only the first 2 elements, which is the first numerator-denominator pair found

BC, 151 148 bytes
Edit - faster and shorter version
define f(v){s=scale(x=v);for(i=r=1;i<=10^s;i+=1){t=v*i+1/2;scale=0;p=t/=1;scale=s+1;t=t/i+10^-s/2;scale=s;t=t/1-v;if((t*=-1^(t<0))<r){r=t;n=p;d=i}}}

same test case.
A lot is similar to the previous version, but instead of trying all possible n / d combinations, we hill-climb over the residues of v and backward quotients of multiples m==v*d and denominators d. Again the precision of the computation is the same.
Here is it untangled:
define f(v)
{
    s= scale(x=v)
    for( i=r=1; i <= 10^s; i+=1 ){
        t= v * i +1/2
        scale=0
        m=t/=1 # this rounded multiple becomes nominator if
               # backward quotient is first closest to an integer
        scale=s+1
        t= t / i +10^-s/2 # divide multiple back by denominator, start rounding again...
        scale=s
        t= t/1 - v # ...rounding done. Signed residue of backward quotient
        if( (t*= -1^(t < 0)) < r ){
            r=t
            n=m
            d=i
        }
    }
}

This version really has a mere single loop and does only $\Theta\left(\operatorname{fractional_decimals}(v)\right)$ arithmetic operations.
Original - slow version
This functions computes the smallest nominator n and denominator d such that the fraction n / d rounded to fractional_decimals(v) digits is equal to a given decimal value v.
define f(v){s=scale(v);j=0;for(i=r=1;j<=v*10^s;){scale=s+1;t=j/i+10^-s/2;scale=s;t=t/1-v;if((t*=-1^(t<0))<r){r=t;n=j;d=i};if((i+=1)>10^s){i=1;j+=1}};v}

test case:
define o(){ print "Input ",x,"\tOutput ",n,"/",d,"\n" }
f(1.7); o()
> 0
> Input 1.7       Output 5/3
> 0
f(0.); o()
> 0
> Input 0 Output 0/1
> 0
f(0.001); o()
> 0
> Input .001      Output 1/667
> 0
f(3.1416); o()
> 0
> Input 3.1416    Output 355/113
> 0

And here is it untangled:
define f(v)
{
    s=scale(x=v) # save in global for later print
    j=0
    # do a full sequential hill-climb over the residues r of v and all possible
    # fractions n / d with fractional_decimals(v) == s precision.
    for( i=r=1; j <= v * 10^s; ){
        scale=s+1
        t= j / i +10^-s/2 # start rounding...
        scale=s
        t= t/1 - v # ...rounding done. New residue, but still signed
        if( (t*= -1^(t < 0)) < r ){ # absolute residue better?
            # climb hill
            r=t
            n=j
            d=i
        }
        if( (i+=1) > 10^s ){ # next inner step. End?
            # next outer step
            i=1
            j+=1
        }
    }
    v
}

I admit, I cheated a little by emulating a second inner loop inside a single outer loop, but without using any further loop statements. And that's why it actually does $\Theta\left(v \operatorname{fractional_decimals}(v)^2\right)$ arithmetic operations.

you should probably move the new version to the front of the post

@proudhaskeller done

GNU dc, 72 bytes
No loops - dc doesn't even have them.  Instead the control comes from a single tail-recursive macro - idiomatic for dc.
?dXAr^d2*sf*sq1sd0[ld1+sd]sD[r1+r]sN[dlf*ld/1+2/dlq>Ndlq<Dlq!=m]dsmxpldp

Output:
$ for n in 1.7 0. 0.001 3.1416; do echo "    n = $n:"; dc unround.dc <<< $n; done
    n = 1.7:
5
3
    n = 0.:
0
1
    n = 0.001:
1
667
    n = 3.1416:
355
113
$

Phew.  Partial explanation in this answer.

Mathematica, 111 characters
f=Module[{a=0,b=1,k},While[Round[a/b,10^-(StringLength[#]-2)]!=(k=ToExpression)@#,If[N[a/b]>k@#,b++,a++]];a/b]&

Pretty simple really, and I don't think it converges anywhere as fast as the other solutions, since the numerator and denominator only increment by one. I mostly wanted to find the simple solution to this. I'll have to see the other answers and see what clever stuff happens there.
Output
f/@{"1.7","0.0","0.001","3.1416","3.14"}
{5/3, 0, 1/667, 355/113, 22/7}

Does anyone here celebrate Pi Approximation Day?

No, I am only celebrating tau approximation day.=P But i just noticed that |355/113 - pi|<10^-6 =)

Applescript, >300 bytes
I wanted to do this in a language that natively does the type of rounding required.  Turns out Applescript fits the bill.  Then I saw the enum rounding as taught in school, and couldn't resist the using it, despite the blatant uncompetitiveness of Applescript for golfing purposes:
on u(q)
    set n to 0
    set d to 1
    set x to 0
    set AppleScript's text item delimiters to "."
    set f to 10 ^ (q's text item 2's length)
    repeat until x = q as real
        set x to (round n * f / d rounding as taught in school) / f
        if x < q then set n to n + 1
        if x > q then set d to d + 1
    end repeat
    return {n, d}
end u

log my u("1.7")
log my u("0.")
log my u("0.001")
log my u("3.1416")

This can be golfed a bit more, but probably not worth it.
Output:
(*5, 3*)
(*0, 1*)
(*1, 667*)
(*355, 113*)

C, 233
This works by calling a rationalization function r() with a starting denominator of 1. The function begins incrementing a numerator, and checking at every increment whether the resulting number, when rounded to the same number of digits as the original, has the same string representation as the original. Once the numerator has been incremented so much that the result is greater than the original, the function increments the denominator and calls itself.
This of course uses much more code, but I think the spirit of the problem exonerates this bare-bones approach; for all we know, the internal rationalize() functions of modern languages have lots of internal loops.
Note that this doesn't work for an input of "0." because that is not a standard way to write a float, so when it re-writes the float to string, the result will never be a "0.".
The specs want a function that returns values instead of just printing to screen, hence the argument-passing.
Code (ungolfed):
void r(char* x, int* a, int* b) {
    int i = -1;
    char z[32];
    double v =atof(x);
    while(1) {
        i++;
        double y = ((double)i)/((double)(*b));
        double w;
        sprintf(z, "%.*f", strlen(strchr(x,'.'))-1, y);
        if(strcmp(x, z)==0) {
            *a = i;
            return;
        }
        w = atof(z);
        if(w > v) {
            (*b)++;
            r(x, a, b);
            return;
        }
    }
}

Usage:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char* argv[]) {
    int num;
    int denom = 1; // start with a denominator of 1
    r(argv[1], &num, &denom);
    printf("%d/%d\n", num, denom);
    return 0;
}

Golfed code:
typedef double D;
void r(char*x,int*a,int*b){int i=-1;char z[32];D v=atof(x);while(1){i++;D y=((D)i)/((D)(*b));D w;sprintf(z,"%.*f",strlen(strchr(x,'.'))-1,y);if(!strcmp(x,z)){*a=i;return;}w=atof(z);if(w>v){(*b)++;r(x,a,b);return;}}}

actually, in the Haskell library implementation (http://hackage.haskell.org/package/base-4.7.0.1/docs/src/Data-Ratio.html#approxRational), the definition of approxRational has Just one recursive helper function, and no more looping than that.

well, I was wrong, it actually has two recursive helper functions, but by the spec it is okay

I wasn't trying to say that anyone's solutions were invalid, just wanted to post one without built-in rationalization :)

of course, but the fact that the definition itself has no loops is nice, and infact, you wrote in your post "for all we know, the internal rationalize() functions of modern languages have lots of internal loops." so I checked it.

anyway, how does the solution work?

Added a section that explains how it works.

@flawr i'm not sure that having the function expect a 1 is legal. is it?

@proudhaskeller Sorry, I cannot follow what you mean? In what way does his function expect what? (Or has his post changed in meantime?)

@flawr if you will read carefully you will notice that in order for the function to work the third parameter must be initialized to 1

Pure Bash, 92 bytes
As a partial explanation for this answer, here it is ported to bash:
f=${1#*.}
q=${1//.}
for((n=0,d=1;x-q;x=2*10**${#f}*n/d+1>>1,n+=x<q,d+=x>q));{ :;}
echo $n/$d

Notably:

bash has integer-only arithmetic.  So we appropriately scale everything up by 2*10^(number of fractional digits).
bash rounds down to nearest integer; the 2 in the expression above is so we can instead round to nearest integer (up or down).
Just one loop
we check if the rational overshoots or undershoots the decimal and increment the denominator or numerator accordingly.

Output:
$ for n in 1.7 0. 0.001 3.1416; do echo "    n = $n:"; ./unround.sh $n; done
    n = 1.7:
5/3
    n = 0.:
0/1
    n = 0.001:
1/667
    n = 3.1416:
355/113
$

Should be a fairly straightforward int-only port to c

JavaScript (E6) 85
F=r=>(l=>{for(n=r,d=1;l&&r!=((n=r*d+1/2|0)/d).toFixed(l);d++);})(r.length-2)||[n|0,d]

Ungolfed
F=r=>{
  l = r.length-2; // decimal digits
  if (l==0) return [r|0, 1] // if no decimal return the same (conv to number) with denominator 1

  // loop for increasing denominator
  for(d = 2;
      r != ( // loop until find an equal result
      // given R=N/D ==> N=R*D
      (n=r*d+1/2|0) // find possible numerator, rounding (+0.5 and trunc)
      /d).toFixed(l); // calc result to given decimals
      d++);
  return [n,d]
}

Test In FireFox/FireBug console
;["1.7","0.","0.001","3.1416","9.9999"].forEach(v => console.log(v,F(v)))

Output
1.7 [5, 3]
0. [0, 1]
0.001 [1, 667]
3.1416 [355, 113]
9.9999 [66669, 6667]


text:
Pirrational Numbers
Pi is an irrational number, which means that its decimal representation never terminates or repeats itself.
Pi truncated to 41 decimal digits (40 places) is 3.1415926535897932384626433832795028841971.
If we ignore the decimal point and list the digits as a sequence of positive integers, avoiding duplicates, we get 3 1 4 15 9 2 6 5 35 8 97 93 23 84 62 64 33 83 27 950 28 841 971 (OEIS A064809).
(Notice that 15 appears in the sequence instead of 1 5 because 1 had already occurred.
Also note that 0 does not occur because it is not positive; 950 contains the first zero.)
To construct the first pirrational number we use this sequence to index into the digits of Pi (the first digit being 3, the second 1, etc.).
So the first digit of the first pirrational number is the 3rd digit of Pi,
the second digit is the 1st digit of Pi,
the third digit is the 4th digit of Pi,
the fourth is the 15th digit of Pi,
and so on.
A decimal point is added after the first digit to mimic Pi.
Thus the first pirrational number to 41 digits is 4.3195195867462520687356193644029372991880.
(Note that for the 30th digit I had to go all the way to the 974th digit of Pi.)
To construct the second pirrational number the process is repeated using the first pirrational number instead of Pi. (Pi itself may be called the zeroth pirrational number.) So the new sequence is 4 3 1 9 5 19 58 ... and the first piirational number is indexed to produce the second, which starts 9.14858....
Further pirrational numbers are created in the same way, each being generated from the one before.
Challenge
Your task is to write the shortest program possible that takes in two integers, N and D, and outputs the Nth pirrational number truncated to D decimal digits.
D is always positive but N is non-negative, and D digits of Pi should be output when N is 0.
When D is 1 it does not matter if the decimal point is present or not.
The input should come from stdin or the command line and output should go to stdout (or your language's closest alternatives).
Your program should work for all input values of N and D below 216, but it needn't be timely or efficient.
The shortest code in bytes wins.
(Note that pirrational numbers exits in other bases but everything in this challenge is done in base 10.)

Can we use built-in arbitrary-precision representations of Pi to get its digits?

@MartinBüttner Sure. You could even get pi's digits online if you want as long as you are only getting pi's digits.

@Calvin'sHobbies: Ah nice so I can just have the first 64ki digits of pi in a file? Should I add +1 for the filename?

Is that input range correct? For N=1, D=13393 for example, you'd need the 31 millionth digit of PI

The first 1 billion digits of pi only gets you 42,598 digits of the 1st pirrational number

@Claudiu Yes I suppose you could have a file of the digits of pi, but as you discovered you'd need a heck of a lot of them to cover the range I'm asking for. The point is more to be able to generate the pirrational numbers, given unlimited time and memory. And for that a method to generate arbitrarily many digits of pi would be more certain to work than a file. (Though perhaps the constraints I'm asking for are a bit steep.)

@Claudiu Perhaps I should have made the challenge to generate the most digits for the highest N. Oh well.

@Calvin'sHobbies: That might have been interesting. I'm working on a version that can generate a sequence reasonably quickly. There is a way to generate the nth digit of pi without any of the preceding methods, but sadly it only works in base 16... I tried a solution which uses the base 16 method and converts it to base 10 but the conversion process is taking too long.

@Claudiu There are spigot algorithms that operate in base 10 - I used one in my post!

@calvin'shobbies If the goal is to write a program that can generate the numbers indicated given unlimited time and memory, and if I load the digits of pi from a file, must I actually have the (full) file I'm claiming to load from?

@Matt Yes. I know I can't verify that but it would be unfair to the current answers that generate the digits on the fly.

@calvin'shobbies I disagree. A ridiculously large file seems to fit with the other rules allowing infinite time and memory. Assuming the rules always allowed loading from a file (which it seems like they did), the people who answered by generating the numbers themselves would have handicapped themselves by adding the requirement that numbers are generated in-program. Solutions that are not likewise handicapped aren't unfair as they arent doing anything the other solutions couldnt do. But its more interesting to generate the digits yourself. Perhaps add that as a requirement.

Python 292 bytes
Quite inefficient, I've only been able to get a few digits of N=3 and none of N=4.
import sympy
def P(N,D,s=''):
 if N<1:return'3'+`sympy.pi.evalf(D+9)`[2:-9]
 for i in range(D):
    h=[];l='';j=i;x=0
    while-~j:
     x+=1;d=P(N-1,x)[-1];l+=d
     while'1'>P(N-1,x+1)[-1]:x+=1;l+='0'
     if(l in h)<1:h+=[l];l='';j-=1
    s+=P(N-1,int(h[i]))[-1]
 return s
s=P(*input())
print s[0]+'.'+s[1:]

Sample input:
0,20
3.1415926535897932384

1,20
4.3195195867462520687

2,10
9.148583196

3,5
9.9815

Golfs: Change =="0" to <"1". Make the inner while loop one line. Remove spaces around x += 1. if l not in h -> if(l in h)<1: N==0 -> N<1

@isaacg Thanks for those, I was in a bit of a rush when I posted and missed some obvious things. I probably wouldn't have realized you could do the string comparison though and the if(l in h)<1 is also pretty clever.

Some more: Initialize s as a parameter of P (def P(N,D,s=''):).  str(...) can probably be written with backticks.  while'1'>... saves the space.  Make h a set and initialize with h=l,={''}, then write l in h as {l}<h.

@flornquake That's pretty clever, especially the way you initialize it so python doesn't think its a dict. As I was putting this in though, I realized a fairly big optimization which unfortunately required h to be ordered. Still, that's a neat trick I'll try and remember.

@KSab That's even better. :)
while j+1: can be shortened to while-~j, btw.

Haskell, 431 400 369
import Data.List
g(q,r,t,k,n,l)|4*q+r-t<n*t=n:g(q#0,(r-n*t)#0,t,k,div(r#(30*q))t-n#0,l)|1<2=g(q*k,(2*q+r)*l,t*l,k+1,div(q*(7*k+2)+r*l)(t*l),l+2)
u w@(x:y:xs)=x:v y xs 0 w
v a(r:s)n w|a`elem`take n(u w)||r==0=v(a#r)s n w|1<2=a:v r s(n+1)w
m p=map(genericIndex p.pred)$u p
a#b=a*10+b
(x:s)%n=show x++'.':show(foldl1(#)$n`take`s)
f n d=print$iterate m(g(1,0,1,1,3,3))!!n%d

Gotta love infinite lists! Given enough time and memory, this program will eventually calculate the right answer for any N and D (I assume).
I'm generating the digits of pi with g using a spigot algorithm (shamelessly stolen from a guy called Stanley Rabinowitz), grouping the digits/creating the sequence using v and generating a pirrational number from these using m.
Here it is in action:
λ> f 0 10
"3.1415926535"
λ> f 1 10
"4.3195195867"
λ> f 2 10
"9.Interrupted. --didn't have the time to wait for this to finish
λ> f 2 4
"9.1485"

I thought "Haskell!" when I saw the question, scrolled down, and smiled.


text:
Fake the forecast
The new weather predicting supercomputer has arrived, and it doesn't work.
In the meantime your boss wants you to buy the technicians some time by faking the daily wind maps.
Your task is to draw a grid of arrows representing wind direction.
The grid is:

made up of 15px square tiles
8 tiles by 8 tiles
120px square total
000 background

Each grid tile has 8 potential orientations, representing wind direction:

North
Northeast
East
Southeast
South
Southwest
West
Northwest

Which must be depicted as follows:
N
NE
E
SE
S
SW
W
NW
The maps must vary gradually, in order to be believable.
This means each tile may only differ from its neighbour by one step. Specifically:

A tile can only differ by one increment or decrement from each of the 4 adjoining tiles. (or 3 for side tiles, 2 for corner tiles).
e.g. a tile with neighbour E could be NE, E or SE (assuming it accords with its other neighbours).
Orientations can loop back around, i.e. N -> NW and NW -> N.

To illustrate, the following map is valid :
NW  N NE NE NE NE NE NE
 N NE NE NE NE NE NE  E
NE NE NE NE NE NE  E SE
 E NE NE NE NE  E SE  S
SE  E  E  E  E SE  S SE
 S SE SE SE SE  S SE  E
SW  S  S  S  S SE  E NE
SW SW  S  S SE  E NE  N

Maps must be unique, don't generate the same map for different inputs.

Input is an integer corresponding to the days between now and your forecast (e.g. 1 is tomorrow's forecast, 365 is a year's time).
Output is the map as an image.
Output should be reproducible, the same input will always give the same output
You must give unique maps for at least 8 years - i.e. no identical output for any input between 1 and 2920 (I'm ignoring leap years).
There is no defined output for any input greater than 2920.

The winning submission will produce valid maps (up to day 2920) with the fewest bytes of source code.

What is the maximum input that needs to be handled? Is there any restriction on, e.g., the forecasts of two consecutive ways having to only differ by a maximum amount as well?

The maximum input that needs to be handled is 2920. There is no restriction on consecutive forecasts (except that they must be unique)

Oh, sorry, I must've overlooked the last bullet point. :)

Do we have to use exactly those arrows? (In which case, please provide 8 individual 15x15 images.) Or can we use any arrow as long as it fits in 15x15?

I've provided the seperate images but since it was ambiguous at the time of setting the question I'll allow any arrow.

Slightly off topic: Just showed this to a friend who is weather forecaster and he told me that some of those weather apps you can get aren't much better than what we are doing here, since they apparently just take the free weather data from the big airports and interpolate them, more often than not those interpolations just suck.

"The new weather predicting supercomputer has arrived, and it doesn't work." Submit it to the International Journal of Climate Science. It'll be par for the course. :P

@flawr I live near a big airport and they're not much more accurate here. Happy smiley suns and a few clouds but no suggestion there'd be heavy rain 6 hours later on.  Best forecast I can think of is "it'll be the same tomorrow as it is today"; more accurate over a year than any site/app!

BBC Basic, 83 ASCII characters, tokenised filesize 72
Download emulator at http://www.bbcbasic.co.uk/bbcwin/bbcwin.html
  INPUTn:VDU23,48,516;543;4;0;23,49,783;5,9;0;0:WIDTH8FORi=1TO64PRINT;1ANDn;:n/=2NEXT

This is basically a port of Martin's concept, but the implementation in BBC basic is very different. I reprogram the font for the numbers 0 and 1 then output the binary digits of n in reverse order.
Ungolfed code is below. In BBC basic you can print individual ASCII characters using the VDU command, but the language has a series of machine-specific codes similar to escape sequences but starting with unprintable characters. For reprogramming the font, we start with ASCII 23. Normally 8-bit values are taken, but if you use a semicolon as a separator instead of a comma, it takes 16-bit little endian values (as used in the golfed version.)
  INPUTn
  VDU23,48,4,2,31,2,4,0,0,0         :REM redefine font for "0" as an east facing arrow, with an 8x8 bitmap
  VDU23,49,15,3,5,9,0,0,0,0         :REM redefine font for "1" as a northeast facing arrow, with an 8x8 bitmap
  WIDTH8                            :REM set print width to 8 characters
  FORi=1TO64PRINT;1ANDn;:n/=2:NEXT  :REM print the binary digits of n in reverse order from least significant to most significant.

Output
For the numbers 0 to 7. Note that the font is not reset at the end of the program, hence the numbers 0 and 1 appear as arrows in the first two examples.

Nice idea! :) But are the tiles 15x15?

@MartinBüttner BBC basic allows you to redefine a font on an 8x8 grid. To keep numbers small, I did the smallest recognisable east arrow (5x5 squeezed into the top right corner of the grid) and made the most similar looking northeast arrow. In the screenmode used here, the definition has a 1:1 correspondence with pixels (and leaves an ample gap between rows) but I doubled the grid size in Windows Paint to get a better size image on SE. Some of the other screen modes in BBC basic have more than 1 pixel per grid element, and user defined characters are noticeably more grainier than regular font.

Matlab (182*)
It is assumed that the input is stored in n. hen looking at the algorithm, it is not sure that the results will be unique, but I checked for n=1 upto 3000 that they are unique and satisfy the rules. I basically just use complex numbers of the unit circle and 'smoothen' them by conv2 with a gaussian filter. After that they get 'rounded' to the 8 possible directions.
*I know no way how to scale the output to a certain number of pixels, so that has to be done manually=/
EDIT: I just discovered that there are cases where my checking program didn't recognise wrong solutions (changes by more than 1 step), but I am trying to find another solution.
Input:
n = 1

Code:
rand('seed',0);
for x=1:n
    b = exp(1i*rand(8)*2*pi);
end
for k=1:12
    b = conv2(b,[1,2,1]'*[1,2,1],'same');b=b./abs(b);
end
c = exp(1i*round(angle(b)*4/pi)*pi/4)/3;
quiver(real(c),imag(c));

What do you mean by "scale the output to a certain number of pixels," scale the arrows, or the image?

@krs013 I mean scaling the whole image, I didn't found out yet how to do that such that it has e.g. a width of exactly 8*16 pixels.

Mathematica, 116 115 bytes
f@n_:=Graphics[Array[(d=n~BitGet~#;Arrow@{1+{w=15#~Mod~8+6.5d,h=15Floor[#/8]},14+{w-13d,h}})&,64,0],ImageSize->120]

I suppose a good horse never jumps higher than it has to. 2920 different grids are very easily achieved with using only two directions (I'm using N and NE), which makes satisfying the continuity rule trivial. I'm simply choosing between N and NE based on the bits of n, so this will actually produce 264 different wind maps.
Here are the first ten maps:

PS: My original idea was to enumerate all 84 combinations for the 4 corners and "linearly" interpolation the rest of the grid. That probably would have resulted in nicer maps, but this is code golf after all, so I went with the what fulfils the minimum requirements.

I should haved asked for 2^64+1 grids. :)

@jsh I'd got 8 choices for two adjacent directions. It would have made the code somewhat longer, but it would still have been similarly easy, and would allow for 2^67 unique grids. But don't worry, I think it's still a nice code golf - doing graphical output golf is hard (due to the required objectivity) and I think you've done a fairly good job with it.

I like the idea of the interpolation, but how would you have interpolated when each of the four corners would point to the center?

@flawr hmmm, very good point, I guess I would have had to exclude a few combinations there.

@MartinBüttner: Although this technically meets the spec, it does seem to be contrary to the spirit of the challenge, which is to make the map believable. Just an observation.

@COTO Very true, but its also code golf and not a popularity contest, and "believability" is not an objective validity criterion.

PHP 5.4, 549 bytes
Somewhat hindered by the need to define arrows as graphics, here is my PHP code:
<? $i=$argv[1];$p="R0lGODdhBQAFAIAAAP///wAAACwAAAAABQAFAAAC";$a=[$p."BwRiicGsDwoAOw",$p."CEQeoLfmlhQoADs",$p."CARiF8hnmGABADs",$p."CIwDBouYvGIoADs",$p."BwRil8Gs+QoAOw",$p."CIQRYcqrnkABADs",$p."CARihscYn1YBADs",$p."CAx+Bmq6HWIBADs"];$c=[$i&7,$i>>3&7,$i>>6&7,$i>>9];$m=imagecreate(120,120);imagecolorallocate($m,255,255,255);foreach($a as$_)$z[]=imagecreatefromstring(base64_decode($_));for($y=0;$y<8;$y++)for($x=0;$x<8;$x++)imagecopy($m,$z[($c[0]*(7-$x)*(7-$y)+$c[1]*$x*(7-$y)+$c[2]*(7-$x)*$y+$c[3]*$x*$y)/49%8],$x*15+5,$y*15+5,0,0,5,5);imagepng($m);

Takes its argument from the command line, such as:

php windmap.php 123

This solution will use the input as the definition of the four corners. The rest of the map will be smoothly interpolated between values. It has defined results for all values from 0 to 4095, a grand total of ~11.25 years of fake forecast, which should be more than enough time to fix the weather software!
Here's a GIF of all the results:

And a ZIP containing each map can be downloaded here
(Small note: My domain recently expired because I wasn't paying attention. I've renewed it, but the above image and link may not work until the DNS updates)
Unsquishified:
<?php
$input = $argv[1];
$prefix = "R0lGODdhBQAFAIAAAP///wAAACwAAAAABQAFAAAC";
$arrows = [
    $prefix."BwRiicGsDwoAOw", // E
    $prefix."CEQeoLfmlhQoADs", // NE
    $prefix."CARiF8hnmGABADs", // N
    $prefix."CIwDBouYvGIoADs", // NW
    $prefix."BwRil8Gs+QoAOw", // W
    $prefix."CIQRYcqrnkABADs", // SW
    $prefix."CARihscYn1YBADs", // S
    $prefix."CAx+Bmq6HWIBADs", // SE
];
$points = [
    $input & 7,
    $input >> 3 & 7,
    $input >> 6 & 7,
    $input >> 9 // input beyond 0o7777 (4095) will be undefined due to lack of & 7 here
];
$img = imagecreate(120,120);
imagecolorallocate($img,255,255,255);
$arrowimgs = [];
foreach($arrows as $src) {
    $arrowimgs[] = imagecreatefromstring(base64_decode($src));
}
for($y=0; $y<8; $y++) {
    for($x=0; $x<8; $x++) {
        $point = (
              $points[0] * (7-$x)/7 * (7-$y)/7
            + $points[1] *   $x  /7 * (7-$y)/7
            + $points[2] * (7-$x)/7 *   $y  /7
            + $points[3] *   $x  /7 *   $y  /7
        ) % 8;
        imagecopy($img,$arrowimgs[$point],$x*15+5,$y*15+5,0,0,5,5);
    }
}
imagepng($img,"out.png");

How does the interpolation work?

@flawr It takes an approximation of the distance to each corner and uses that as a weight for how much that corner's value should affect the current point's value.

But in this case every arrow should point to the middle in frame 1647? http://tinyurl.com/o7z9grl

@flawr Look down the leftmost column to see how it's "interpolating" from 7 (SE) to 1 (NE) by going through all the values 6, 5, 4, 3, 2... as opposed to the shorter "7, 0, 1" that you might expect. The algorithm isn't sophisticated enough to interpolate with rotation like that.

Ah thats how you solved it! This is really a nice, since the interpoation with '7,0,1' would have resulted in an invalid arrow field=) +1 for the arrow graphics!