text:
Robot roadie needed to pack the truck
As the band's roadie, you have to pack the truck. Your program will place the packages so that they fit in the smallest height.
A badly packed truck

Rules
Packages may be rotated through multiples of 90 degrees. Packages may touch but must not overlap.
The output is the repacked image (to file or stdout). Your program may use any input or output raster image format.
Your program must accept any number of packages of various shapes in images up to 4000x4000 pixels. It must not be hardcoded for this test image. If I suspect any submission to be tailored towards this specific image, I reserve the right to replace it by a new test image.
Score
Your score is the smallest height of a rectangle that will contain your arrangement (the width is the input rectangle width). In the case of a tie, the earliest entry wins.
Standard loopholes are prohibited as usual.

Sam has a very good solution and gets the 'accepted' tick.

Language : Java
Score : 555 533
I just went for trying to brute force a solution by iterating over the shapes in order of decreasing area (perimeter in case of tie) and trying out all packing possibilities until a valid packing is found for that shape at which point the shape's position is fixed and the algorithm goes on to the next shape. In order to hopefully improve the quality of the result when searching for a valid packing first all possible positions are tried with the shape rotated such that it is taller than it is wider.
Note: this assumes that the input image(s) have all of the shapes separated by white space. It takes the maximum width of the output as the first argument and a list of shape images as the other arguments (each shape image can have one or more shape separated by at least one line of white pixels)
import java.awt.Color;
import java.awt.Graphics;
import java.awt.geom.AffineTransform;
import java.awt.geom.Point2D;
import java.awt.image.BufferedImage;
import java.io.File;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

import javax.imageio.ImageIO;

public class Packer {
    public static void main(String[] args) throws Exception {
        long t1 = System.currentTimeMillis();

        int width = Integer.valueOf(args[0]);
        List<Item> itemList = new ArrayList<Item>();
        for (int i = 1; i < args.length; i++) {
            itemList.addAll(getItems(ImageIO.read(new File(args[i]))));
        }

        File outputFile = new File("output.png");
        if (outputFile.exists()) {
            outputFile.delete();
        }
        outputFile.createNewFile();

        ImageIO.write(pack(itemList, width), "PNG", outputFile);
        long t2 = System.currentTimeMillis();
        System.out.println("Finished in " + (t2 - t1) + "ms");
    }

    private static BufferedImage pack(List<Item> itemList, int width) {
        System.out.println("Packing " + itemList.size() + " items");
        Collections.sort(itemList, new Comparator<Item>() {

            @Override
            public int compare(Item o1, Item o2) {
                return o1.area < o2.area ? 1 : (o1.area > o2.area ? -1
                        : (o1.perimiter < o2.perimiter ? 1
                                : (o1.perimiter > o2.perimiter ? -1 : 0)));
            }
        });
        Packing packing = new Packing(width);
        PackedItem.Rotation[] widthRots = { PackedItem.Rotation.ZERO,
                PackedItem.Rotation.ONE_EIGHTY };
        PackedItem.Rotation[] heightRots = { PackedItem.Rotation.NINETY,
                PackedItem.Rotation.TWO_SEVENTY };
        int count = 0;
        for (Item item : itemList) {
            count++;
            int minSize = Math.min(item.width, item.height);
            int maxSize = Math.max(item.width, item.height);
            int x = 0;
            int y = 0;
            int rot = 0;
            PackedItem.Rotation[] rots = widthRots;
            if (item.width > item.height) {
                rots = heightRots;
            }
            boolean rotsSwitched = false;

            PackedItem packedItem = new PackedItem(item, rots[rot], x, y);
            System.out.format("Packing item %d which is %d by %d\n", count,
                    item.width, item.height);
            while (!packing.isValidWith(packedItem)) {
                if (rot == 0) {
                    rot = 1;
                } else {
                    rot = 0;
                    if (x + minSize >= width) {
                        x = 0;
                        y++;
                        if (!rotsSwitched
                                && y + maxSize > packing.height) {
                            rotsSwitched = true;
                            if (item.width > item.height) {
                                rots = widthRots;
                            } else {
                                rots = heightRots;
                            }
                            y = 0;
                        }
                    } else {
                        x++;
                    }
                }
                packedItem.set(x, y, rots[rot]);
            }
            packing.addItem(packedItem);
            System.out.format("Packed item %d\n", count);
        }
        return packing.getDrawing();
    }

    private static List<Item> getItems(BufferedImage image) {
        List<Item> itemList = new ArrayList<Item>();
        boolean[][] pointsProcessed = new boolean[image.getWidth()][image
                .getHeight()];

        for (int i = 0; i < image.getWidth(); i++) {
            for (int j = 0; j < image.getHeight(); j++) {
                if (pointsProcessed[i][j]) {
                    continue;
                }
                ImagePoint point = ImagePoint.getPoint(i, j, image);
                if (point.getColor().equals(Color.WHITE)) {
                    pointsProcessed[point.x][point.y] = true;
                    continue;
                }
                Collection<ImagePoint> itemPoints = new ArrayList<ImagePoint>();
                Queue<ImagePoint> pointsToProcess = new LinkedList<ImagePoint>();
                pointsToProcess.add(point);
                while (!pointsToProcess.isEmpty()) {
                    point = pointsToProcess.poll();
                    if (pointsProcessed[point.x][point.y]) {
                        continue;
                    }
                    pointsProcessed[point.x][point.y] = true;
                    if (point.getColor().equals(Color.WHITE)) {
                        continue;
                    }
                    itemPoints.add(point);
                    pointsToProcess.addAll(point.getNeighbors());
                }
                itemList.add(new Item(itemPoints));
            }
        }

        return itemList;
    }

    private interface Point {
        int getX();

        int getY();

        Color getColor();
    }

    private static final class ImagePoint implements Point {
        private static final Map<BufferedImage, Map<Integer, Map<Integer, ImagePoint>>> POINT_CACHE = new HashMap<BufferedImage, Map<Integer, Map<Integer, ImagePoint>>>();
        private final int x;
        private final int y;
        private final Color color;
        private final BufferedImage image;
        private Collection<ImagePoint> neighbors;

        private ImagePoint(int x, int y, BufferedImage image) {
            this.x = x;
            this.y = y;
            this.image = image;
            this.color = new Color(image.getRGB(x, y));
        }

        static ImagePoint getPoint(int x, int y, BufferedImage image) {
            Map<Integer, Map<Integer, ImagePoint>> imageCache = POINT_CACHE
                    .get(image);
            if (imageCache == null) {
                imageCache = new HashMap<Integer, Map<Integer, ImagePoint>>();
                POINT_CACHE.put(image, imageCache);
            }
            Map<Integer, ImagePoint> xCache = imageCache.get(x);
            if (xCache == null) {
                xCache = new HashMap<Integer, Packer.ImagePoint>();
                imageCache.put(x, xCache);
            }
            ImagePoint point = xCache.get(y);
            if (point == null) {
                point = new ImagePoint(x, y, image);
                xCache.put(y, point);
            }
            return point;
        }

        Collection<ImagePoint> getNeighbors() {
            if (neighbors == null) {
                neighbors = new ArrayList<ImagePoint>();
                for (int i = -1; i <= 1; i++) {
                    if (x + i < 0 || x + i >= image.getWidth()) {
                        continue;
                    }
                    for (int j = -1; j <= 1; j++) {
                        if ((i == j && i == 0) || y + j < 0
                                || y + j >= image.getHeight()) {
                            continue;
                        }
                        neighbors.add(getPoint(x + i, y + j, image));
                    }
                }
            }
            return neighbors;
        }

        @Override
        public int getX() {
            return y;
        }

        @Override
        public int getY() {
            return x;
        }

        @Override
        public Color getColor() {
            return color;
        }
    }

    private static final class Item {
        private final Collection<ItemPoint> points;
        private final int width;
        private final int height;
        private final int perimiter;
        private final int area;

        Item(Collection<ImagePoint> points) {
            int maxX = Integer.MIN_VALUE;
            int minX = Integer.MAX_VALUE;
            int maxY = Integer.MIN_VALUE;
            int minY = Integer.MAX_VALUE;
            for (ImagePoint point : points) {
                maxX = Math.max(maxX, point.x);
                minX = Math.min(minX, point.x);
                maxY = Math.max(maxY, point.y);
                minY = Math.min(minY, point.y);
            }
            this.width = maxX - minX;
            this.height = maxY - minY;
            this.perimiter = this.width * 2 + this.height * 2;
            this.area = this.width * this.height;
            this.points = new ArrayList<ItemPoint>(points.size());
            for (ImagePoint point : points) {
                this.points.add(new ItemPoint(point.x - minX, point.y - minY,
                        point.getColor()));
            }
        }

        private static final class ItemPoint implements Point {
            private final int x;
            private final int y;
            private final Color color;

            public ItemPoint(int x, int y, Color color) {
                this.x = x;
                this.y = y;
                this.color = color;
            }

            @Override
            public int getX() {
                return x;
            }

            @Override
            public int getY() {
                return y;
            }

            @Override
            public Color getColor() {
                return color;
            }
        }
    }

    private static final class PackedItem {
        private final Collection<PackedPoint> points;
        private Rotation rotation;
        private int x;
        private int y;
        private AffineTransform transform;
        private int modCount;

        PackedItem(Item item, Rotation rotation, int x, int y) {
            this.set(x, y, rotation);
            this.points = new ArrayList<PackedPoint>();
            for (Point point : item.points) {
                this.points.add(new PackedPoint(point));
            }
        }

        void set(int newX, int newY, Rotation newRotation) {
            modCount++;
            x = newX;
            y = newY;
            rotation = newRotation;
            transform = new AffineTransform();
            transform.translate(x, y);
            transform.rotate(this.rotation.getDegrees());
        }

        void draw(Graphics g) {
            Color oldColor = g.getColor();
            for (Point point : points) {
                g.setColor(point.getColor());
                g.drawLine(point.getX(), point.getY(), point.getX(),
                        point.getY());
            }
            g.setColor(oldColor);
        }

        private enum Rotation {
            ZERO(0), NINETY(Math.PI / 2), ONE_EIGHTY(Math.PI), TWO_SEVENTY(
                    3 * Math.PI / 2);

            private final double degrees;

            Rotation(double degrees) {
                this.degrees = degrees;
            }

            double getDegrees() {
                return degrees;
            }
        }

        private final class PackedPoint implements Point {
            private final Point point;
            private final Point2D point2D;
            private int x;
            private int y;
            private int modCount;

            public PackedPoint(Point point) {
                this.point = point;
                this.point2D = new Point2D.Float(point.getX(), point.getY());
            }

            @Override
            public int getX() {
                update();
                return x;
            }

            @Override
            public int getY() {
                update();
                return y;
            }

            private void update() {
                if (this.modCount != PackedItem.this.modCount) {
                    this.modCount = PackedItem.this.modCount;
                    Point2D destPoint = new Point2D.Float();
                    transform.transform(point2D, destPoint);
                    x = (int) destPoint.getX();
                    y = (int) destPoint.getY();
                }
            }

            @Override
            public Color getColor() {
                return point.getColor();
            }
        }
    }

    private static final class Packing {
        private final Set<PackedItem> packedItems = new HashSet<PackedItem>();
        private final int maxWidth;
        private boolean[][] pointsFilled;
        private int height;

        Packing(int maxWidth) {
            this.maxWidth = maxWidth;
            this.pointsFilled = new boolean[maxWidth][0];
        }

        void addItem(PackedItem item) {
            packedItems.add(item);
            for (Point point : item.points) {
                height = Math.max(height, point.getY() + 1);
                if (pointsFilled[point.getX()].length < point.getY() + 1) {
                    pointsFilled[point.getX()] = Arrays.copyOf(
                            pointsFilled[point.getX()], point.getY() + 1);
                }
                pointsFilled[point.getX()][point.getY()] = true;
            }
        }

        BufferedImage getDrawing() {
            BufferedImage image = new BufferedImage(maxWidth, height,
                    BufferedImage.TYPE_INT_ARGB);
            Graphics g = image.getGraphics();
            g.setColor(Color.WHITE);
            g.drawRect(0, 0, maxWidth, height);
            for (PackedItem item : packedItems) {
                item.draw(g);
            }
            return image;
        }

        boolean isValidWith(PackedItem item) {
            for (Point point : item.points) {
                int x = point.getX();
                int y = point.getY();
                if (y < 0 || x < 0 || x >= maxWidth) {
                    return false;
                }
                boolean[] column = pointsFilled[x];
                if (y < column.length && column[y]) {
                    return false;
                }
            }
            return true;
        }
    }
}

The solution this produces (takes about 4 minutes 30 seconds on my machine) is:

Looking at this picture it seems like the result can be improved by iterating over all of the shapes post packing and trying to move them all up a bit. I might try doing that later.


text:
Curator's Dilemma
Introduction
You are a friend of a curator for an art museum, who has had the recent delight of getting modern art from four artists (some of which may give the curator zero pieces of art, young scoundrels).  As this is modern art, all of any given artist's pieces look exactly the same.  Your friend wants to use a computer to help decide which order to place these pieces in.
Program Requirements
Your program must take five integers (passed to a function or inputted through stdin (or someway else)).  The first four are the number of paintings supplied by each of the four artists.  The last value is an permutation index i (counting from 1, not 0). The curator wishes to see the ith permutation by lexicographic order of the paintings.
Your program must output this permutation in any reasonable format: e.g. abbccd or [0 1 1 2 2 3].  The runtime for input totalling fewer than ten paintings  must take less than an hour (this should hopefully be no problem).
You are not allowed to use any in-built functions to work out permutations
Examples
Input: 0 1 2 0 2
Given that we have one painting by artist B and two by artist C (and they all look the same), the permutations in lexicographic order are:

['bcc', 'cbc', 'ccb']

The highlighted permutation would be the correct output, because it is the second in lexicographic order.
Input: 1 2 0 1 5

['abbd', 'abdb', 'adbb', 'babd', 'badb', 'bbad', 'bbda', 'bdab', 'bdba', 'dabb', 'dbab', 'dbba']

Testing
Here are some tests that should be correct.
1 2 4 1 5    - ABBDCCCC
2 2 3 1 86   - ABBCACDC
4 1 2 0 24   - AACACBA
1 4 3 2 65   - ABBCBBDCDC

A short piece of code in Python3 that should randomly generate inputs and outputs is available here (not valid for entry, this uses the Python import of permutations):
from itertools import permutations
from random import randint
a,b,c,d,n = randint(1,2),randint(1,2),randint(1,3),randint(1,3),randint(1,15)
print(str(a) + " " + str(b) + " " + str(c) + " " + str(d) + " " + str(n) + " - " + str(sorted(set([''.join(p) for p in permutations(a * "a" + b * "b" + c * "c" + d * "d")]))[n-1]))

Scoreboard
Optimizer - CJam       - 39  - Confirmed - Bruteforce
EDC65     - JavaScript - 120 - Confirmed - Bruteforce
Jakube    - Python2    - 175 - Confirmed - Algorithmic

You say, " all of the pieces look exactly the same".  Do you mean "all the the pieces from a given artist look exactly the same, but pieces from different artists look different"?

This wouldn't be a valid entry, but I think it might still be useful for someone: {:A.a.{~97+[:I.}: is valid J and works, but uses A. for most of the work, so it isn't valid. If you could write a function that replaces A. and subsitute it in this function, you'd have a valid answer.

@ɐɔıʇǝɥʇuʎs - You don't have to use "ABCD", you can use any character/numerical/symbolic system at all.  I'm afraid I don't know J, and so cannot tell the exact problem, but hope this helps =)

@PopeyGilbert Well, a version that just spits out numbers would be {:A.[:I.}:... The thing is that, but I still don't think A. would be valid: http://www.jsoftware.com/help/dictionary/dacapdot.htm

What if the required permutation does not exists? 1 0 0 0 100 ?

Hm, that's a tough one @edc65 - When I'm testing it, that will never happen.  It's upto you what your program does when something like that happens.  I'd suggest, to conserve characters, you just have the default error your programming language gives you when you try for said value that doesn't exist.

Say contributor A gives two paintings and contributor B gives one.
Would a1,a2,b1 be the same as a2,a1,b1 (basically the same person's paintings in a different order)?

Yes @DaemonOfTheWest - Two paintings by the same contributor are identical.

Python 2: 175 163 chars
This is not a serious golfing answer. With a different algorithm I reached 138 byte.
Just wanted to post this here, because it doesn't use brute force. Complexity is Theta(#pictures).
f=lambda x:0**x or x*f(x-1)
def g(Q,n):
 while sum(Q):
  for j in 0,1,2,3:
   p=f(sum(Q)-1)*Q[j]
   for k in Q:p/=f(k)
   if p<n:n-=p
   else:print j;Q[j]-=1;break

Usage:
g([1, 4, 3, 2], 65)

edit:
Same algorithm, just some golfing: don't import the factorial method and little changes in the order of the calculations.
Pyth translation: 61 characters
Lu*GhHUb1WsPQV4J*@QNytsPQFZPQ=J/JyZ)I<JeQ XQ4-eQJ)EN XQNt@QNB

Nothing special here, exact translation of my python code. Way too long though. I had too use a few ugly (long) things. The first 9 letter alone is the definition of the factorial.
Lu*GhHUb1    def y(b): G=1; for H in range(b): G*= H+1; return G

Also stuff like Q[j]-=1 is way too long: XQNt@QN (1 character more than Python!!!)
Usage:
Try it here: Pyth Compiler/Executor. Disable debug mode and use [2, 2, 3, 1, 86] as input.

It works! Congratulations on coming up with the first Python solution!  However, I did find that in my environment I have to move from math import* outside the function.  Adding you to the leaderboard!

Wow... Your solution is incredibly efficient - For 32 paintings it takes only 0.034 seconds o.0.

CJam, 50 43 39 bytes
q~(])\{W):Wa*}%s:X{Xm*:s_&}X,(*{$X=},$=

This can be golfed a lot.
Takes input from STDIN in following format:
4 1 2 0 24

Outputs the painting. For example for above input:
0020210

Try it online here
Do note that the online compiler gives up for larger painting sizes. You will have to try larger inputs on the Java version

Congratulations on being the first solver!  50 bytes is certainly a hard value to beat.  I'll add you as the top of the leaderboard!

@PopeyGilbert you should at least wait for 1 week or so before accepting an answer

Ah, okay, I'm very sorry!  In my previous challenge I just changed the accepted answer when someone got beaten.  My bad.

@PopeyGilbert That's very noble of you (and I wish all challenger authors did), and in principle there's nothing wrong with accepting early if you do, but some people seem to get offended if a challenge around here accepts an answer early (because, I guess, no one expects the author to change the accepted answer).

I personally think that there should be at least 2 answers to choose between before accepting, even if its done early. Of course if there is only 1 answer till a week or so, accept it.

Wow, very organised!  Changing the leaderboard yourself =)

JavaScript (ES6) 120  138 147
As a function with the required five parameters, output via console.
Using symbols 0,1,2,3. I calc the total of symbols, then build and check every base 4 number having the required number of digits. Numbers with the wrong number of any digit are discarded.
Note: with JavaScript 32 bit integer this works for up to 15 paintings.
Edit Shorter (avoid .toString) and way faster (modified exit condition). Time for each test below 1 sec.
Edit2 no algorithm change, golfed more (indentation added for readability)
F=(w,x,y,z,n)=>{
  for(a=0;n;n-=l=='0,0,0,0')
    for(l=[w,x,y,z],t=w+x+y+z,v='',b=a++;t--;b/=4)--l[d=b&3],v=d+v;
  console.log(v)
}

Ungolfed And no FireFox required
F=function(w,x,y,z,n) {
  for(a=0; n; a++) // exit when solution found (if wrong parameters, run forever)
  {
    l=[w,x,y,z]; // required number of each symbol
    t=w+x+y+z; // total of digits
    v=''; // init output string
    for(b=a;
      t--; // digit count down
      b >>= 2) // shift for next digit
    {
        d = b & 3; //get digit
        --l[d]; // decrement for the current digit
        v = d + v; // add to output string
    }
    l[0]|l[1]|l[2]|l[3] // if digits ok
    ||--n // decrement counter
  }
  console.log(v) // when found, exit for and print the answer
}

Test In FireBug/FireFox console
F(1, 2, 4, 1, 5)
F(2, 2, 3, 1, 86)
F(4, 1, 2, 0, 24)
F(1, 4, 3, 2, 65)

Output
01132222
01120232
0020210
0112113232

Hello!  Having a bit of trouble running it.  I'm downloading FireFox to see if that will help.  I'll add you to the leaderboard!

I found rather a nice table here - I'll assume Firefox is necessary.  Tested and it works!  Changed leaderboard to confirmed.

Leaderboard but no upvote ... you really don't like it! :(

Agh!  I'm so sorry =(  It's upvoted now =)

I wonder how long this algorithm will be in CJam. But as of now, I have no idea how this works :P

Nice to see an ungolfed solution, nice algorithm!  @Optimizer I'm also interested to see how long that would be in CJam =)  Probably a lot shorter (who would of guessed a primarily code golfing language would be shorter...)

Pyth, 20
@fqPQm/TdU4^U4sPQteQ

Try it here.
Input is in Python list form, e.g. [1, 2, 4, 1, 5]
Output is also in Python list form, e.g. [0, 1, 1, 3, 2, 2, 2, 2] for the above input.
The solution is brute force, and takes about 10 seconds, worst case, on my machine.
How it works:
@fqPQm/TdU4^U4sPQteQ
           ^U4sPQ         All permutations of [0, 1, 2, 3] with length equal to the number
                          of paintings.
     m/TdU4               Find the count (/) of paintings by painter in the input list.
 fqPQ                     Filter the permutations on the counts being the desired counts
                          in the input.
                          This gives all possible orderings of the paintings.
@                teQ      Index into this list at the given location - 1. (0-indexing)

source: Stack Exchange

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

sort: votes


text:
A Skittish Program
Objective
You are to write a program that receives an integer n as input (from the command line), and embeds itself (the program) n directories down the directory tree. Example with n=5:

The folder names may be whatever you wish. The only requirements are that the depth is correct, and that the program can then be ran again from its new spot in the directory tree, and that the new source file retains the same filename.
Bonuses:

Score * 0.9 If the directories all have a different name (must be true at least to depth 1 000 000)
Score * 0.5 If you do not directly or indirectly read or move the source file, or access the source code of the program

What counts as "reading the source"? You mean the file? Or the real source code?

The file. Will clarify in post @GiantTree

@globby What do you mean by 'do not read the source file of the program'?

Copying the exact source into the directory, without explicitly reading the file that your source code is in. Basically make a quine that drops itself into another directory. Sorry if I'm not explaining it well

@globby So execution of the CMD command move does not count as reading the source file?

@unclemeat It does, because to move the file you (or the system) has to access the data in the file.

Seems like you are just trying to hide your porn stash.

I'm not paying enough attention to tell; is the [quine] tag appropriate?

@globby how about the ln command in *nix? If I'm not mistaken, it's just creating another entry to the file inode, and no content is read at all.

Seriously don't need to write a quine this late...

@globby As far as I'm aware, moving a file does not read the contents, unless you're moving between hard drives or partitions. It's basically just changing some pointers in the file system.

@MartinBüttner fair. Updated the original post.

Unique names up to depth 1 000 000? If I see code which promises to do that, but looks like the cat danced on the keyboard, I would never dare test it on my computer. Not with an input above 10, anyway.

The logic just needs to work up to depth 1000000. You can modify the code to print the directory names instead of making them, or work out the logic on paper.

A million nested subfolders? Hey man, some of us use Windows!

@MarkReed Look a few comments up

Bash, 30*0.9*0.5 = 13.5
mkdir -p `seq -s/ $1`;ln $0 $_

Takes depth as the first argument. Creates a hard link to itself into the following directory structure:
1/2/3/4/5/.../n

The script may then be run from the new location, even if rm is run on the old script.
Explanation:
seq -s/ $1 outputs the numbers from 1 to $1 (the first argument), separated by a forward slash.
mkdir -p `seq -s` $1 creates the directory specified by seq, with -p creating all intermediate directories.
ln $0 $_ create a hard link to the current running script in the newly created directory.
Old (30 * 0.9 = 27):
mkdir -p `seq -s/ $1`;cp $0 $_

Example run (with ln):
$ ls -lGR
.:
total 1
-rwx------+ 1 ducks 41 Jan  5 15:00 test.sh

$ ./test.sh 4

$ ls -lgR
.:
total 1
drwxr-xr-x+ 1 ducks  0 Jan  5 15:01 1
-rwx------+ 2 ducks 41 Jan  5 15:00 test.sh

./1:
total 0
drwxr-xr-x+ 1 ducks 0 Jan  5 15:01 2

./1/2:
total 0
drwxr-xr-x+ 1 ducks 0 Jan  5 15:01 3

./1/2/3:
total 0
drwxr-xr-x+ 1 ducks 0 Jan  5 15:01 4

./1/2/3/4:
total 1
-rwx------+ 2 ducks 41 Jan  5 15:00 test.sh

$ rm ./test.sh

$ ls -lg
total 0
drwxr-xr-x+ 1 ducks 0 Jan  5 15:01 1

$ ls -lg 1/2/3/4
total 1
-rwx------+ 1 ducks 41 Jan  5 15:00 test.sh

Thanks to @DigitalTrauma for suggestion to replace $(..) with `..`
Thanks to @h.j.k. for suggestion to use ln.

Brilliant use of $_!

Save a char - use backticks instead of $( ): http://codegolf.stackexchange.com/a/25572/11259

Depending on the answer to my comment on the question, maybe replace cp with ln to get the 0.5 bonus too...

Wells, there's the update from the OP now, and mv is also restricted from that 0.5 bonus. That still leaves ln in the clear, yes?

Yes, ln (you don't need -s) would actually place the program in the new directory, so that it can be executed from there, without ever reading, moving, or accessing its original source. I say go for the FALCON PUNCH score of 13.5!

C, 225 * 0.9 * 0.5 = 101.25
My solution in C:
$ cat d.c
#define R(x)#x
#define T(x)R(x)
#define S(p)b[9];main(i,v)char**v;{for(i=atoi(v[1]);i--;sprintf(b,"%i",i),mkdir(b),chdir(b));fputs("#define R(x)#x\n#define T(x)R(x)\n#define S(p)"p"\nS(T(S(p)))",fopen("d.c","w"));}
S(T(S(p)))

Here in a somewhat more readable form:
#define R(x) #x
#define T(x) R(x)
#define S(p) char b[9];\
             main(int i,char**v) { \
                for(i=atoi(v[1]); i--; sprintf(b,"%i",i), \
                                       mkdir(b), \
                                       chdir(b)); \
                fputs("#define R(x) #x\n" \
                      "#define T(x) R(x)\n" \
                      "#define S(p) " p "\n" \
                      "S(T(S(p)))", \
                      fopen("d.c", "w")); \
             }
S(T(S(p)))

The check if it works:
$ gcc -o d d.c
# a lot of warning and notes from gcc ...
$ ./d 10
$ diff -s d.c 9/8/7/6/5/4/3/2/1/0/d.c
Files d.c and 9/8/7/6/5/4/3/2/1/0/d.c are identical

There most probably is a lot of golfing potential in the source code.

Great use of the preprocessor!

Zsh, 63 60 58 52 * 0.9 = 56.7 54 52.2 46.8
s=$(<$0);for i in {1..$1};{mkdir $i;cd $i};echo $s>f

Example:
llama@llama:...Code/misc/foo$ zsh f 5
llama@llama:...Code/misc/foo$ ls -R
.:
d1  f

./d1:
d2

./d1/d2:
d3

./d1/d2/d3:
d4

./d1/d2/d3/d4:
d5

./d1/d2/d3/d4/d5:
f
llama@llama:...Code/misc/foo$ cat d1/d2/d3/d4/d5/f
s=$(cat $0);for i in {1..$1};do;mkdir d$i;cd d$i;done;echo $s>f
llama@llama:...Code/misc/foo$ cat f
s=$(cat $0);for i in {1..$1};do;mkdir d$i;cd d$i;done;echo $s>f
llama@llama:...Code/misc/foo$ diff f d1/d2/d3/d4/d5/f
llama@llama:...Code/misc/foo$

UUOC s=$(<$0) (Just for the record, it fails for me with bash 4.3.11: “syntax error near unexpected token `;'”. But works fine with zsh 5.0.2)

Could you save a character by removing the d before $i?

@CanadianLuke Huh, I never knew you could have a directory named 1. Thanks

I think you should be able to use curly brackets: for i in {1..$1};{mkdir $i;cd $i};echo $s>f.

@U2744SNOWFLAKE Thanks, that saved a few bytes. Edited.

Batch - 48 * 0.9 = 43.2
for /l %%a in (1,1,%1)do md %%a&cd %%a&move..\%0

This script simply creates a new directory, and moves the source file to it - n times.
H:\MyDocuments\uprof\top>embed.bat 5

     ...

H:\MyDocuments\uprof\top>tree /f
Folder PATH listing for volume DATA009_HOMES
Volume serial number is B88B-384C
H:.
└───1
    └───2
        └───3
            └───4
                └───5
                        embed.bat

Rebol - 114 * 0.9 * 0.5 = 51.3
do b:[d: copy %./ repeat n do input[mkdir repend d[n"/"]]write join d s: system/options/script join"do b: "mold b]

Ungolfed:
do b: [
    d: copy %./
    repeat n do input [
        mkdir repend d [n "/"]
    ]
    write join d s: system/options/script join "do b: " mold b
]

Original non-quine version - 90 * 0.9 = 81
d: %./ repeat n do input[mkdir repend d[n"/"]write join d s: system/options/script read s]

Ungolfed:
d: %./
repeat n do input [
    mkdir repend d [n "/"]
]
write join d s: system/options/script read s

Bash 167*0.5*0.9 = 75.15
Borrowing heavily from @es1024's great answer, but this one is a true quine, so it qualifies for both bonuses.
b=\' c=\\ a='d=`seq -s/ $1`;mkdir -p $d;echo b=$c$b c=$c$c a=$b$a$b>>$d/$0;echo $a>>$d/$0'
d=`seq -s/ $1`;mkdir -p $d;echo b=$c$b c=$c$c a=$b$a$b>>$d/$0;echo $a>>$d/$0

Also, shell quine techniques from here.

AutoIt3, 106 * 0,9 = 95,4 bytes

A bit long but I can't help with those long function/variable names:
$f = @WorkingDir
For $i = 1 To $CmdLine[1]
    $f &= "\" & $i
Next
DirCreate($f)
FileCopy(@ScriptFullPath, $f)

Simply call it with <script/.exe name> <depth> eg. script.exe 5.
It will work for any amount of directories; maybe even more than your file system can handle. :D
How it works:
It's just a simple loop that adds the index to a string. Then the directory (and all parent directories, too) get created and the file copies itself to that directory.

Node.js, 136 133 * 0.9 * 0.5 = 61.2 59.85
r=require,f=r('fs'),p=__dirname;while(i=process.argv[2]--)f.mkdirSync(p+='/'+i);f.linkSync(a=__filename,p+'/'+r('path').basename(a))

fs.linkSync maps to the POSIX call link, which creates a hard link. An invalid argument will cause the program to crash.

J, 82 * 0.9 = 73.8
This is mostly a port of the top-voted answer.
exit (1!:1[1{A) 1!:2 <] (s,'/',>1{A)[fpathcreate s=:' /'charsub":1+i.".>{:A=:ARGV

Save as skittish.ijs or whatever you want, and call it from the command line using your version of jconsole. Mine is symlinked to jc:
$ jc skittish.ijs 20
$ ls 1/2/3/4/5/6/7/8/9/10/11/12/13/14/15/16/17/18/19/20/skittish.ijs
1/2/3/4/5/6/7/8/9/10/11/12/13/14/15/16/17/18/19/20/skittish.ijs

Zsh, 55 * 0.9 * 0.5 = 24.75 bytes
I had my eyes on this challenge for a long time, but I wanted to complete it in Zsh without calling any external programs like mkdir and ln (otherwise, it would be identical to the bash solution). Turns out, Zsh can provide its own versions of those programs!
zmodload zsh/files
mkdir -p ${(j:/:):-{1..$1}}
ln $0 $_

Try it online!

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

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


text:
Build a program to analyze coin flip sequence choices
In a puzzle in an old book of mine, a game is defined in which two players choose sequences of coin flips that they believe will appear first when a coin is repeatedly flipped. (It was actually odd and even dice rolls, but this little detail doesn't matter in terms of problem equivalence.)
It is noted that if player 1 chooses TTT and player 2 chooses HTT, that player 2 has a 7/8 chance of winning the game, since the only way TTT can come before HTT is if the first three flips are all tails.
Your job is to create a program or function that will deduce the probability that one of two chosen sequences will comes first. Your program will take two lines of input (or two strings as arguments), each representing a sequence of length 10 or less:
HTT
TTT

And output the probability that the first player will win, in either fraction or decimal form:
7/8
0.875

The shortest code to do this in any language wins.

Are the sequences always the same length as each other?

@UriZarfaty No, not necessarily.

Though presumably the sequences have to be distinct (since the output can't specify a tie).

Yes, the sequences must be distinct.

More specifically, one cannot be a terminal substring of the other.

Can they be arguments to a program?

Yes. Usually I specify that way at first, although for some reason this time around it was specifically a program.

Sorry for asking but I dont get the comment where it says one cannot be a terminal substring of the other what exactly does that mean? is it so that the 2nd string cannot be the same as the start or end of the other string since that could result in a tie?

By "terminal substring", I mean that one string cannot be the same as the end portion of another string. (It can be the same start portion; that just means that the substring will win 100% of the time.)

Python 3 (139 136 134 132 126 115 143)
Uses Conway's Algorithm as described at here. Handles all sequence pairs as long as the first is not a terminating subsequence of the second (as per instructions).
def f(a,b):c=lambda x,y=a:sum((x[~i:]==y[:i+1])<<i for i in range(len(x)));return 0 if b in a else(1/(1+(c(a)-c(a,b))/(c(b,b)-c(b))),1)[a in b]

Thanks xnor for shaving 6 bytes off. Thanks Zgarb for spotting a bug with subsequences.

The current version doesn't work for me. For the input "HTT" and "TTT", o has the value -1 and it divides it by 0.

Nice golf! I like the default argument trick. A couple of (untested) tips: you can multiply by 2**i with <<i, and the output probability can be written as 1/(1/o + 1), into which you can put the reciprocal of o directly.

Thanks. Good spot re o/(1+o). Somewhat embarrassed to have missed <<!

@Jakube Sorry, didn't spot your comment! Current version works fine for me with "HTT" and "TTT".

I changed the spec to say "program or function" so you don't have to take input and print stuff.

This gives a nonzero answer for HTH and T, even though the first player cannot win. The other answer has the same problem.

Good spot. It fails for any two sequences where one is a non-initial subsequence of the other. Before I patch it up, can you think of any issues or test cases?

Joe Z said in the comments that you won't have one string be a terminal substring of the other,  since that would allow a tie.

Thanks, I saw. My code gives wrong results for these, except the cases where one string is also a non-terminal substring of the other (e.g. T and TT) where it gives the correct result since a tie isn't possible.

Been checking out your code but when I run it like f('HHH','THH') it returns 0, if I swap them it returns 1. Not familiar with python been running it online http://repl.it/languages/Python am I doing something wrong?

The code requires Python 3 to work correctly, while the repl you're using is Python 2.7.2 (for example / in Python 2 is integer division rather than float division).

@UriZarfaty Thanks for the tip, do you know any online tools for python 3?

Here's one: http://www.tutorialspoint.com/execute_python3_online.php. Web searches will find others.

CJam, 44 38 36 bytes
Using the same Conway's Algorithm as in here.
ll]_m*{~1$,,@f>\f{\#!}2b}/\-:X--Xd\/

Input is the two distinct sequences in two lines. The output is the probability of first winning over second. The inputs need not be of same lengths
I am using the formula for winning odds (p) for first player A as

Then the probability is defined as

which, after simplifying becomes

and after some simplification, becomes

Example input:
HTT
TTT

Output:
0.875

Try it online here

Joe said in comments (after this was posted) that the strings are not necessarily the same length. Still, +1 because I don't understand CJam.

@mdc32 fixed, 1 byte longer now :(

You already let me believe that codegolfSE now supports LaTeX... =(

@flawr HAHA. Sorry about that :( . These are PNGs from online LaTeX editor.

This gives a nonzero answer for HTH and T, even though the first player cannot win. The other answer has the same problem.

@Zgarb One string cannot be a terminal sub string of the other. But I wonder if the algorithm really works for non similar lengths...

@Optimizer I understood terminal substring as suffix, so this should be a valid input. As for the algorithm, at least the linked article does not specify how exactly it should be generalized to inputs of differing lengths. I tried to do it in one way, but realized later that my solution gave wrong results in many cases.

@Zgarb I will have to specially manage these cases, I think. Let me see if any non-substring cases fail too.

Lua 211 190 184
Also using Conway's Algorithm.
Still new to Lua so this can be golfed more for sure.
z=io.read;e=function(s,t)r='';for d in s:gmatch"."do r=r..(d==t:sub(1,1)and 1 or 0);end;return tonumber(r,2);end;a=z();b=z();print((e(a,a)-e(a,b))/(e(b,b)-e(b,a))/(1/((1/2)^b:len())));

Ungolfed
z=io.read;
e=function(s,t)
r='';
    for d in s:gmatch"."do
        r=r..(d==t:sub(1,1)and 1 or 0);
    end;
    return tonumber(r,2);
end;
a=z();
b=z();
print((e(a,a)-e(a,b))/(e(b,b)-e(b,a))/(1/((1/2)^b:len())));

First version
z=io.read;
e=function(s,t)
    r=0;
    for d in s:gmatch"."do
        r=r*10;
        if d==t:sub(1,1)then r=r+1 end;
    end
    return tonumber(r,2);
end;
f=function(n,o)
    return ((e(n,n)-e(n,o))/(e(o,o)-e(o,n)))/(1/((1/2)^3));
end;
print(f(z(),z()));


text:
Calculate the square of an integer with restrictions
The Puzzle
You have to write a program or function p(n) that returns the square of what is entered into it and you may assume that the input is a non-negative integer. Put in simpler terms, return n2.
Rules

You are not allowed to use * or / (or any other power or square root operator, such as POW or SQRT, if your language contains such functions)
You may not use a loop, or use a constructions that is similar to a loop.  Example of loop like constructions are GOTO and recursion.

Example
Function p(n)
Dim r()
ReDim r(n)
p = Len(Join(r, Space(n)))
End Function

Be creative and (ab)use the functions and features given to  you by your language of choice.
*edit
Loop like structures are loops that allow you to repeat 1 or more instructions
-if you could add an stdout "1" to your code and you would end up with repeating that output n times, it will count as a loop

A power of two of would be 2^n. Do you mean the square of n? Also n>-1? Is n an integer or a float? And what's your winning criterion? The two tags you used are contradictory.

What programming language is the example in?

@MartinBüttner Ty for the input, I'll edit it

@Deformyer Looks like some Basic dialect to me.

@dwana Aren't the second part of the first rule and the third rule the same?

The restrictions are much too vague, especially about what's a "loop-like construction".

@xnor probably goto statements and such

This shouldn't have been reopened, because it still lacks clarity on what counts as "loop-like". E.g. what about folds?

@PeterTaylor or maps for that matter.

@dwana Can you be specific about these things in your rules : (1) Are in built functions which inherently have loops in them, like maps, iterators, folds, reduce etc allowed ? (2) Is evaluating string as a code using eval/exec allowed ?

@dwana Is recursion allowed?

Also, I see that some of the programs below, since they only use integers, they can only find n^2 if n is less than the sqrt of Integer.MAX_VALUE (not using longs). Is this acceptable?

recursion is not allowed, int only is acceptable

This seems overdue for a meta post

Also, many of the functions called by people in their programs use loops inside the native code to accomplish the task.

This is largely a duplicate of a previous codegolf challenge, which asked for the more general m*n instead of n*n without using the *. See http://codegolf.stackexchange.com/a/18283/14485

CJam, puts on his glasses
q~33c

(*_*)

(*_")>⌐■-■

(⌐■_■)

"]sG>4%,)

Input via STDIN
Try the code here
Note that * in the code is not used as multiplying, but as a join operator
Also note that the cool part of the code is not just string, half of it is actually the code involved in finding the square. So.. DEAL WITH IT
This will help you in dealing with it:
q~33c                    "Read the number and put ASCII character 33 on stack with it"
(                        "Decrease it to get ASCII code 32 character, which is a space";
 *_                      "Repeat the space input number times and make another copy";
   *                     "Put that many spaces in between each space. Now we have";
    )                    "n*n spaces string. We take out the last space out of it";
(                        "Decrement the space to get ASCII 31 character";
 *                       "Fill the n*n - 1 spaces with that to get 2*n*n - 3";
  _                      "string. Then copy it again.";
   ")>⌐■-■               "Put the sun glasses in";
(⌐■_■)                   "Wear the sun glasses. Be cool.";
"]s                      "Add everything to a single string of 4*n*n - 6 + 16"
   G>                    "length. Remove first 16 characters";
     4%                  "Take every 4th character from that string to get n*n - 1"
       ,)                "length string. Take length and increment to get n*n";

Ruby
def square(n)
  case n
  when 0..1
    n
  when 2..36
    '100'.to_i(n)
  else
    raise RangeError, 'Integer overflow!'
  end
end

This is really clever.

For the record, in Mathematica this works far arbitrary integers (including 0 and negative), without having to handle any cases specially: FromDigits[{1, 0, 0}, Input[]]. Same in CJam: 4Ybl~b

APL? ∊⍵⍵
{+/ ∊⍵⍵ ⍴1}

This answer is dedicated to all those people who go "∊⍵⍵" whenever they see the APL symbols :-)
Examples
      {+/∊⍵⍵⍴1} 3
9
      {+/∊⍵⍵⍴1}¨⍳20
1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400

Explanation
{       }   This function takes a number ⍵,
{   ⍵⍵⍴1}   builds a matrix of ⍵ by ⍵ all filled with ones,
{+/∊    }   and sums all its elements together.

eww...

Isn't summing all elements of a matrix pseudo looping ? Summing over is done via reduce or fold , both are looping

+/ in other languages is called sum() and I see many answers using it. By the same reasoning you couldn't use * in CJam.

I see your point, but joining does not require reading the value of each and every element, so it can be done without a loop at a low level itself. Summing the elements of the matrix actually needs to iterate over all elements to add. Alternatively, you can do something like flattening the matrix and getting its length.

That looks like the symbol for a pressed ham!?

Abusing some functions in Mathematica
Twice the area of an isosceles right triangle
a =RegionMeasure@SASTriangle[n,ArcSin[1], n]
a+a

The area of a square.  Of course!
RegionMeasure[Rectangle[{0, 0}, {n, n}]]

The same idea, in a different form:
Integrate[n, {x, 0, n}]  (* thx to DigitalTrauma *)

The number of elements in a square matrix:
 Length[Flatten[Normal[AdjacencyMatrix[RandomGraph[{n, RandomInteger[n]}]]]]]

or
 Plus@@Flatten[ConstantArray[1, {n, n}]]

or
 Length@Flatten[Outer[f,Range[n],Range[n]]]

or
 Length[Distribute[p[Range[n],Range[n]],List]]

etc...

Another one: k[n_] := Integrate[n, {x, 0, n}] ?

DigitalTrauma, Integrate very nice but it iterates, which I believe is a form of looping.

True, though I think it is only implicit looping.  By the same argument I would claim Area and friends are implicit multiplication (but also allowed)

C
p(n){int a[n];return(&a)[n]-a;}

Note:

Variable-length arrays are a conditionally-supported feature since C99.
Implicit int is used to reduce character count and for style points.

http://stackoverflow.com/q/27828822/1530508

Python 2
Purely mathematical, avoiding any of the banned operations:
import cmath
n=input()
if n:
  l=complex(0, -cmath.log(n) - cmath.log(n))
  print int(round(abs(complex(cmath.cos(l),cmath.sin(l)))))
else:
  print 0

This is the usual exp(ln(x)*y) trick tailored to this problem:

Because y is 2, then we can simply do ln(x)+ln(x) to get rid of the multiplication.
I felt that math.exp() was a bit too close to the banned "POW" for fair play, so instead the whole thing is converted to complex and Euler's identity is used to replace the exp() with cos() and sin()
To avoid the situations where explicit multiplication/division by i is needed, the complex() function is used instead.

If you change math.log to cmath.log you can handle negative numbers. You also don't need to import math then.

input doesn't do what you think in Python 2, and in Python 3 print is a function instead of a statement.

@CristianCiupitu What do I think input does in Python 2? ;-).  I would certainly write this differently if this was to be production code, but for the purposes of this challenge it is just fine, so long as the input is a well-formed numeric expression.  I understand there is an implicit eval in there, and its potential evilness.

Mathematica
Another answer using some funny Mathematica features
n = Input[];
g = EdgeCount@CompleteGraph@n;
g + g + n

A complete graph with n vertices has binom(n,2) = n(n-1)/2 edges (which is also the n'th triangular number). So the result is simply twice that, plus the input.

Very clever, using graphs.

Pure Bash
No explicit loops or arithmetic:
(($1))||{ echo 0;exit;}
eval a=({1..$1}{1..$1})
echo ${#a[@]}

Uses bash expansions to create two lists 1-n and brace-expand them and display the size of the resulting array.

Similar method, but making use of coreutils instead:
join <(seq -f "1 %g" $1) <(seq -f "1 %g" $1) | wc -l

R, delicious inefficiency with Monte Carlo
The expectation E[x] for the shape/scale parametrization of the Gamma Distribution is shape*scale.
I don't see mean being banned, so here is the sample solution with mean()
f = function(n, k = 1e9){round((mean(rgamma(k, shape = n, scale = n))))}
f(99)

Without using mean(), it is possible to use mode[x], which is equal to (shape-1)*scale, but this involves writing a add.one function to bypass +1 then writing another Mode function to tabulate the mode.
add.one = function(x) length(c(seq(x),NA))
Mode = function(x) (u<-unique(x))[which.max(tabulate(match(x,u)))]
f.mode = function(n, k = 1e9){Mode(round(rgamma(k, shape = add.one(n), scale = n)))

Accuracy not guaranteed, but law of large number should kick in for 1,000,000,000 samples, which has given me the right results for all my test cases.

I was thinking of a similar hack, +1

Java
First entry, is this how it works?
int g(int n){
    int[] a = new int[n];
    Arrays.fill(a,n);
    return IntStream.of(a).sum();
}

... not funny u_u

C#
Creates a string with n characters and then replaces each character with the n-character string. This produces a string with a length of n*n.
using System;

public class Test
{
    public static void Main()
    {
        int n = Int32.Parse(Console.ReadLine());
        String s = "".PadLeft(n, 'X');
        Console.WriteLine(s.Replace("X", s).Length);
    }
}

Test it here: http://ideone.com/lubIFg.

That's creative!

Matlab
a warning: this is primarly math based, so do not expect fancy source code
Note that a = n^2 iff log(a) = log(n)*2 iff log(log(a)) = log(log(n))+log(2). So this function is just finding the zero of the function f(a) = log(log(n))+log(2) - log(log(a)) which obviously is at a = n^2.
function s = g(n)
    f = @(a) log(log(n))+log(2)-log(log(a));
    s = fnzeros(f);
end

Here some other not very creative functions:
Here the program wil sum sum the number 1+2+3+...+n = 1/2 * (n^2+n) twice and substract n, so the result is always n^2
g=@(n)sum(1:n)+sum(1:n)-n

This function creates a n x n matrix of random numbers (between 0 and 1) and then returns the number of elements.
g=@(n)numel(rand(n));

The following functin creates a vandermonde matrix of the vector (0,0,n) and outputs the entry that consists of n^2
function s = g(n)
    a = vander([0,0,n]);
    s = a(3,1)
end

This function creates the inverse of a hilbert matrix of size n where the top left element is always n^2
function s = g(n)
    a = invhilb(n);
    s = a(1);
end

Ad#3: Of course in real life applications one would use g=@(n)nnz(nan(n)); for the sake of efficiency and brevity. ;-)

When it comes to efficiency I think calculating the inverse of the hilbert matrix explicitly will be more efficient: function s = g(n); a = inv(hilb(n)); s = a(1); end. But then again, your solution is shorter ;P

C
sizeof(char[n][n])

It works up to INT_MAX in constant time and without memory allocation.
Example:
#include <stdio.h>
#include <limits.h>
int main(){
    for( int n=0 ; n<10 ; n++ ){
        printf("%d: %ld\n", n, sizeof(char[n][n]));
    }
    int n = INT_MAX;
    printf("%d: %ld\n", n, sizeof(char[n][n]));
}

displays
0: 0
1: 1
2: 4
3: 9
4: 16
5: 25
6: 36
7: 49
8: 64
9: 81
2147483647: 4611686014132420609

maybe make it obvious that the loop is just a wrapper to show the program running on multiple values

Java
This is the first answer that truly does not use loops or recursion.
int square(int n){
    if (n > 0){
        n = -n;
    }
    return m(n,0) + m(n,1) + m(n,2) + m(n,3) + m(n,4) + m(n,5) + m(n,6) + m(n,7) + m(n,8) + m(n,9) + m(n,10) +
            m(n,11) + m(n,12) + m(n,13) + m(n,14) + m(n,15) + m(n,16) + m(n,17) + m(n,18) + m(n,19) + m(n,20) +
            m(n,21) + m(n,22) + m(n,23) + m(n,24) + m(n,25) + m(n,26) + m(n,27) + m(n,28) + m(n,29) + m(n,30) + m(n,31);
}

int m(int number, int index){
    if (number >> index << 31 >>> 31 == 0){
        return 0;
    } else {
        return number << index;
    }
}

@FlorianF All other answers call functions that use loops. As far as I know, calling a function 32 times and then adding the results does not count as using loops. If I added the statement System.out.print(1) to m, the program would print 1 exactly 32 times, not n times.

GolfScript
Histocrat has shown one way of using base conversion: here's another.
{.,1base.++}:p;

Dissection
{       # Function boilerplate
  .     # Duplicate the input. Stack: x x
  ,     # Turn the second one into an array [0 1 ... x-1]
  1base # Sum the elements of the array. Stack: x x(x-1)/2
  .+    # Double. Stack: x x(x-1)
  +     # Add. Stack: x*x
}:p;    # Question asks for the function to be called p
        # The fact that this destroys the built-in p is unfortunate, but required

Emacs Lisp
(defmacro square-it (n)
  (cons '+ (make-list n n)))

(square-it 11) ;; => 121

A simple macro that expands (square-it 5) into (+ 5 5 5 5 5). Of course, the input must be a compile time constant.

Javascript
function square(i) {
    return new Array(++i).join(new Array(i).join(' ')).length;
}

Haskell
There a lot of possibilities if ranges [x..y] are allowed, some of them are:
f n|x<-sum[1..n]=x+x-n
f n=sum$take n[n,n..]
f n=length$[1..n]>>[1..n]
f n=sum$[1..n]>>[1..n]>>[1]

The two latter ones use the Monad instance of lists. for lists xs, ys holds that xs>>ys is ys appended to itself length xs times.
another trick is just
import Data.Monoid
f x=x<>x

this function, when given an 'appropriate' argument (which are of course from the typeclass Num) return it's square. Product 3 :: Num a => Product a is an example of such an argument.
basically, this function when applied on Product a, (which in the Num class iff a is in i) mappends it with itself and returns Product (a*a).
if we are more strict about what is a number / what numbers should our function work on, we can define f as
import Data.Monoid
f n|x<-Product n=getProduct$x<>x

Java
This is too long to put in the answer, but basically one of the lines of code occurs an amount of times roughly equal to the sqrt of Integer.MAX_VALUE (which is 46340). :D
With no comments or line breaks, the code typed out would be 1,112,155 characters.
int s(int n){
    if(n==0|n==1)return n;
    int c=2,r=n+n;
    if(n==c++)return r;r+=n;
    if(n==c++)return r;r+=n;
    if(n==c++)return r;r+=n;
    if(n==c++)return r;r+=n;
    if(n==c++)return r;r+=n;
    if(n==c++)return r;r+=n;
                            //... (same line of code a total of 46336 times)
    if(n==c++)return r;r+=n;
    if(n==c++)return r;
    return n==c?r+n:r+n+n; //r = 46340^2
}

R
This function is based on counting all possible combinations of two sequences ranging from 1 to n. The value 0 is treated separately.
f <- function(n) if (n) nrow(expand.grid(s <- seq(n), s)) else 0

Clojure
(def squares (lazy-cat [0] (map (fn [sq x] (+ sq x x 1)) squares (range))))

Infinite sequence of all squares starting from 0. The function:
(defn square [n] (nth squares n))

J
Some ascii art...
p =. ( $ @,@  ( ($*) ([-])"*/ ($*) ))

Python
Uses simple math. Based on the sum of an arithmetic progression.
s=lambda n:(sum(range(n))<<1)+n

Explanation:
a = sum(range(n)) # sum of arithmetic progression from 1 to n-1:  n*(n-1)/2
b = a<<1          # bitshift left by 1 (multiply by 2):  n*n - n
c = b+n           # add n:  n*n

Although sum and range probably contains implicit loops,
but as per question spec, there's no way to insert a print statement here to make it repeat, so ... :)

perl :
$n=8;
$x = "$n +" x $n;
$x =~ s/\+$//;
print eval $x;

SQL(PostGIS)
Making use of the area and make envelope functions in the PostGIS extension to PostGreSQL to create a square geometry and return it's area.  Could be changed to return the square of floats as well.
CREATE FUNCTION square(n int)RETURNS int AS $$
BEGIN
    RETURN ST_Area(ST_MakeEnvelope(0,0,n,n));
END;
$$LANGUAGE plpgsql;

In use;
SELECT square(150);

Square Integer
--------------
22500

Bash
yes|xargs -L$1|xargs -L$1|head -n1|iconv -futf16|wc -m

Only works if n < 256.

PHP
function square($v) {
    return array_sum(array_fill(0, $v, $v));
}

works with integer in the range [0;46340]
Edit: I've just seen @thebestone code and it is basically the same

Perl
$_=<>;chop;s/./$_/g;print

the program expects the input number to be squared in unary form (i.e. base 1). Output is also unary. It simply replaces every digit with the whole number.
Example usage:
perl -e '$_=<>;chop;s/./$_/g;print'
000                                   # <- user input
000000000                             # <- output

Scala:
scala> val q = (n:Int) =>(List.fill (n)(n)).sum
q: Int => Int = <function1>

scala> q(9)
res21: Int = 81

Scala:
scala> val s=(n:Int)=>(("x"*(n))*n).size
s: Int => Int = <function1>

scala> s(7)
res22: Int = 49

Really? Does it look like a loop or do you know, that there must be some hidden loop?

Clojure
(fn [n] (apply + (repeat n n)))

Java 8
Makes a list n units long of n and then sums. At first I thought I would have to use bit operations or reflection to complete the task. Please comment if using generate is considered using "loops".
IntFunction square=(n)->IntStream.generate(()->n).limit(n).sum();

Example program:
import java.util.function.IntFunction;
import java.util.stream.IntStream;

class N{
    public static void main(String[]a){
        IntFunction square = (n)->IntStream.generate(()->n).limit(n).sum();
        System.out.println(square.apply(new Integer(a[0])));
    }
}

Erlang
f(N) ->
  L=lists,
  L:sum(L:duplicate(N, N)).

J
This doesn't directly use a divition or a power...
+~ &.: ^.

or: double under ln.

Clojure:
(defn sq [n] (let [init (repeat n ".")] (count (flatten (map (fn [_] init) init))))

I'm sure it can be written shorter, but I'm out of inspiration.
Credit due to hetzi for inspiration.

lambda calculus
λx.n (n x)

where n is a Church numeral.
By definition of Church numerals:
1 := λf.λx.f x
2 := λf.λx.f (f x)
3 := λf.λx.f (f (f x))

It happens that m n (apply m to n) evaluates to the Church numeral of n^m.  So you can square n with:
2 n

But arguably, 2 is the square function, so I expanded 2's definition.


text:
That's almost Lisp!
Challenge
Your challenge is to design an interpreter for a lisp-like language, which will from hence forth be coined: GLisp. The program code for GLisp will consist of an arbitrary amount of nested expressions denoted by brackets, in the following form:
(func arg1 arg2 ...)

Note that the interpreter must allow for extraneous whitespace characters before and after brackets, functions, and arguments.
Types
You will implement four types, Integer, List, Boolean, and Function. Integers and Boolean values can be explicitly inserted into source code with their own syntax. Your interpreter must assume that a run of numeric characters denotes an Integer (you do not have to implement a syntax to explicitly insert negative integers). Your interpreter must also assume that true and false are designated Boolean values. Functions can not be explicitly defined by the user, and will always return a single value (a List of any length counts as a single value).
Functions
The following functions are required to be implemented, and are in the format Function, Arity. If an Arity n is proceeded by a plus sign, then that denotes n or more arguments. You may assume that all arguments given to a function are of the same type, unless specificed otherwise. You may also assume that if no behaviour is specified for a certian type, then you may assume that no argument of that function will ever be of that type. Arguments will be referred to as in the following diagram:
(func argument1 argument2 ... argumentn)

+, 2+

If all arguments are of the type Integer, you must return the sum of the arguments
If all arguments are of the type List, you must return the concatenation of the arguments in ascending order (arg1+arg2+ ...)
If all arguments are of the type Boolean, you must return the logical All of the sequence of arguments
(+ 1 2 3 4 5)  -> 15
(+ (list 1 2) (list 3 4))  -> (list 1 2 3 4)
(+ true true true)  -> true

-, 2+

If all arguments are of the type Integer, you must return the difference of the arguments (arg1-arg2- ...)
If all arguments are of the type Boolean, you  must return the logical Any of the sequence of arguments
(- 8 4 3)  -> 1
(- 0 123)  -> -123
(- true false false true false)  -> true

*, 2+

If all arguments are of type Integer, you must return the product of the arguments
If one argument is of type List and the other is of type Integer (you may assume that these will only be the only arguments given), you must return a new List with the items in arg1 repeated arg2 times.
(* 1 2 3 4 5)  -> 120
(* (list 1 2 3) 2)  -> (list 1 2 3 1 2 3)

/, 2+

If all arguments are of the type Integer, you must return the quotient of the arguments (arg/arg2/ ...) (you may assume that division is done sequentially, and that the decimal portion at every step is truncated)
If one argument is of type List and the other is of type Function, then you must return the resulting List after arg2 has been mapped over every value
(/ 100 10 3)  -> 3
(/ (list 1 2 3) inc)  -> (list 2 3 4)

%, 2

If all arguments are of the type Integer, you must return the modulus of the arguments
(% 4 2)  -> 0

=, 2+

If both the type and value of all arguments is the same, you must return true. Otherwise, return false.
(= 0 0 0)  -> true
(= 0 false (list))  -> false

list, 0+

You must return a list of all arguments, regardless of type. If no arguments are given, then you must return an empty list
(list 3 4 (list 5))  -> (list 3 4 (list 5))

inc, 1

If argument is of type Integer, you must return the Integer incremented by one
If argument is of type List, you must return the List rotated clockwise a single rotation
(inc 1)  -> 2
(inc (list 1 2 3))  -> (list 3 1 2)

dec, 1

If argument is of type Integer, you must return the Integer decremented by one
If argument is of type List, you must return the List rotated counter-clockwise a single rotation
(dec 1)  -> 0
(dec (list 1 2 3)) -> (list 2 3 1)

if, 3

If given three arguments of any type: If the truth value of arg1 is true, return arg2, else return arg3
(if (not (list 1)) 8 false)  -> false

not, 1

If given an argument of any type, if the truth value of arg1 is False, return true, else return false.
(not (list))  -> true

len, 1

If given an argument of type List, return the length of arg1
(len (list 4 2 true (list 3) (list)))  -> 5

Truth table:
0, (list), false  -> false, where (list) denotes an empty list. Everything else is true.
Your interpreter can either be a full program that reads the source input from stdin or a file, or a function which takes the source as a string and returns the output value.
If choosing the former, the output for Integers is simply numbers, for Booleans is true or false, and for lists is a space separated sequence of values enclosed in brackets (eg. (1 2 3 4 (5 6 7)) denotes (list 1 2 3 4 (list 5 6 7))).
If choosing the latter, the value must be returned in the implementation language's corresponding type, or, if no similar type exists, a custom type. Lists can be returned as Arrays or Vectors if the language doesn't have a List type, Booleans should be returned as a Boolean type in the language, or a custom type if the language does not support them.
Test cases
(list 1 2 3 (list 4 5 true))  -> (1 2 3 (4 5 true))
(/ 4000 (+ 1 2 3 4 (* 5 8)))  -> 80
(+ (not (- (len (list 5 6 7)) (/ 10 3))) true)  -> true
(if (           len (list )  ) 4 (if    (+ (= 8 8    8) (not (list 4))) 8 5))  -> 5

Clarifications

Your interpreter may deal with invalid input in any way you choose, but it must not throw an exception (though, it may print an error message and exit smoothly)
Functions will always evaluate arguments left to right
Invalid input is any input which is syntactically incorrect. This includes, but is not limited to, mismatched brackets, division by zero, and partially applied functions (unless going for the bonus)
For =, if any of the values are different or any of the types are different, return false

Bonuses

Score * 0.8 if you support partially applied functions. For example, ((+ 2) 3) would be the same as (+ 2 3), but allows for things such as (/ (list 1 2 3) (+ 2)). You may assume that a function is partially applied if it receives less than its minimum number of arguments
Score * 0.85 if you do not evaluate the arguments applied to if unless they are going to be returned

This is code-golf, so the interpreter with the lowest byte count wins!

How does one interpret (if (not (array 1)) 8 false) -> false?

@feersum good catch, is supposed to be 8.

I was wondering more about the undefined term array, and how the truth value of anything other than a boolean is determined.

@feersum array is also my sleep deprivation showing, and the truth table is below the functions.

How should we evaluate (+ 3 (if false 5))? Generally speaking, what really is "returning nothing"? You didn't specify any unit type to be retuned

I'm still a little confused about the last part. For example, do we return true/false as strings or as our language's corresponding bools?

also, is % applied left-to-right or right-to-left?

Why is (+ bool bool...) logical AND and (- bool bool...) logical OR? The standard ring notation would use + for OR and * for AND. 2. Is "invalid input" intended to cover cases like (/ 2 0) which are syntactically correct? 3. For =, if the values are not all the same, should it return false? 4. The definition of not appears to be backwards. 5. What are the tokens? You say that the interpreter must handle extra whitespace, but you don't say what whitespace it can rely on. For complex questions like this, you really should use the sandbox so that the spec can be checked.

@proudhaskeller (+ 3 (if false 5)) is the same as (+ 3), which you may treat as invalid output. % is applied left to right.

@Sp3000 If you're printing the output to stdout, you return the strings. Otherwise, you return it in your language's boolean type.

@PeterTaylor 1) Will change. 2) Yes, and cases in which you may have mismatched brackets, or a value being used as a function, etc. 3) Yes 4) Fixed 5) whitespace between brackets, functions, and arguments. and I agree, I should have used the sandbox.

it isn't clear how partial application should work: is ((+ 2 3) 4) equal to 9 or an error? Notably, for var-arg functions, it isn't clear when one should consider the application partial. It gets even muddier with things like ((if true (+ 2 3) (- 5)) 4)

@MtnViewMark it is an error. If a function is given less than its minimum number of arguments, then it is partially applied

The example for if is wrong: (not (list 1)) is false, so the expected answer is false, not 8.

Can someone clarify what kind of "crash" isn't allowed? The way it's worded currently suggests to me that a language exception isn't allowed, but a custom exception is. Which seems a bit silly because, for instance, one could just rebrand any language exception as a "custom" exception by catching and rethrowing it.

@Runer112 rephrased.

Haskell, 1370 1263 1179 1128 1163 1107 1084 bytes * 0.8 * 0.85 = 737.12
import Text.Parsec
data V=I Int|L[V]|T|F|P[V]|X|A|S|M|D|U|E|Q|J|K|C|N|W deriving Eq
m Q=0;m C=3;m f|f`elem`[J,K,N,W]=1;m _=2
l=length
x v=[n|I n<-v]
y v=[l|L l<-v]
z v=[0<1|T<-v]++[1<0|F<-v]
(&)f=l.f>>=(.l).(==)
b a|a=T|0<1=F
s(I n)=show n
s(L v)='(':tail(v>>=(' ':).s)++")"
s T=d!!0;s F=d!!1;s _="error"
i(L v)=e$i%v
i v=v
e(P v:a)=e$v++a
e(f:a)|m f>l a=P(f:a)
e(A:a)|x&a=I$sum$x a|y&a=L$concat$y a|z&a=b$and$z a
e(S:a)|x&a=I$f$x a|z&a=b$or$z a
e(M:a)|x&a=I$product$x a
e[M,v,I n]=e$A:replicate n v
e(D:a)|x&a=I$v$x a
e[D,L v,f]=L$map(\a->e[f,a])v
e[U,I a,I b]=I$a`mod`b
e(E:a:v)=b$all(==a)v
e(Q:a)=L a
e[J,I a]=I$a+1
e[J,L[]]=L[]
e[J,L v]=L$last v:init v
e[K,I a]=I$a-1
e[K,L v]=L$drop 1 v++take 1 v
e[C,a,b,c]|a`elem`[I 0,L[],F]=c|0<1=b
e[N,a]=e[C,a,F,T]
e[W,L v]=I$l v
e _=X
f(a:b)=a-sum b
v(a:b)=foldl div a b
(%)f=fmap f
p=k$choice$try%([(I .read)%many1 digit,L%between(w"(")(k$w")")(many$try p)]++zipWith((.return).(>>).w)d[T,F,A,S,M,D,U,E,Q,J,K,C,N,W])
k=(spaces>>)
w=string
d=words"true false + - * / % = list inc dec if not len"
g=either show(s.i).parse p""
main=interact g

Full program, reading stdin and writing to stdout. g is the function version, as well.
Implements both partial functions, and lazy evaluation of if.
Sample runs (of the function version):
λ: g "(list 1 2 3 (list 4 5 true))"
(1 2 3 (4 5 true))

λ: g "(/ 4000 (+ 1 2 3 4 (* 5 8)))"
80

λ: g "(+ (not (- (len (list 5 6 7)) (/ 10 3))) true)"
true

λ: g "(if (           len (list )  ) 4 (if    (+ (= 8 8    8) (not (list 4))) 8 5))"
5

λ: g "(if false (/ 1 0) 5)"
5

λ: g "((+ 2) 3)"
5

λ: g "(/ (list 1 2 3) (+ 2))"
(3 4 5)

Now has all unit tests from the description:
λ: runTests
passed: g "(+ 1 2 3 4 5)" ==> 15
passed: g "(+ (list 1 2) (list 3 4))" ==> (1 2 3 4)
passed: g "(+ true true true)" ==> true
passed: g "(- 8 4 3)" ==> 1
passed: g "(- 0 123)" ==> -123
passed: g "(- true false false true false)" ==> true
passed: g "(* 1 2 3 4 5)" ==> 120
passed: g "(* (list 1 2 3) 2)" ==> (1 2 3 1 2 3)
passed: g "(/ 100 10 3)" ==> 3
passed: g "(/ (list 1 2 3) inc)" ==> (2 3 4)
passed: g "(% 4 2)" ==> 0
passed: g "(= 0 0 0)" ==> true
passed: g "(= 0 false (list))" ==> false
passed: g "(list 3 4 (list 5))" ==> (3 4 (5))
passed: g "(inc 1)" ==> 2
passed: g "(inc (list 1 2 3))" ==> (3 1 2)
passed: g "(dec 1)" ==> 0
passed: g "(dec (list 1 2 3))" ==> (2 3 1)
passed: g "(if (not (list 1)) 8 9)" ==> 9
passed: g "(not (list))" ==> true
passed: g "(len (list 4 2 true (list 3) (list)))" ==> 5
passed: g "(list 1 2 3 (list 4 5 true))" ==> (1 2 3 (4 5 true))
passed: g "(/ 4000 (+ 1 2 3 4 (* 5 8)))" ==> 80
passed: g "(+ (not (- (len (list 5 6 7)) (/ 10 3))) true)" ==> true
passed: g "(if (           len (list )  ) 4 (if    (+ (= 8 8    8) (not (list 4))) 8 5))" ==> 5
passed: g "(if false (/ 1 0) 5)" ==> 5
passed: g "((+ 2) 3)" ==> 5
passed: g "(/ (list 1 2 3) (+ 2))" ==> (3 4 5)

b the cases  e[K,L _] you could use drop 1  as a safe version of tail and use take for a safe version of head joining the two definitions of e[K,L _]

you can use the function notElem .another tip: you can do s=string and use it instead of both string and char (s"C" vs. char 'C'). another tip: use guards instead of ifs

Another thing I thought of: you can encode Maybe values by lists. Nothing is [] and Just x is [x]. This gets rid of the long constructors and adds some more functionalities: if p then Just x else Nothing is [x|p], (==Nothing) is null, the list monad becomes the same as the maybe monad, and so forth.

@proudhaskeller Thanks, all applied!

Python 2, 1417 * 0.8 * 0.85 = 963.56
from operator import*
A=type;K="list"
def E():print"E";exit()
def R(G):
 len(G)or E();T=G.pop(0);L=[]
 if"("==T:
  G or E()
  while")"!=G[0]:L+=[R(G)];G or E()
  G.pop(0);return L
 if")"==T:E()
 try:
  x=eval(T.title())
  if Q(x)<2:return x
  E()
 except:return T
H="+ - * / = % if inc dec not len"
Z=lambda y:lambda x:reduce(y,x)
D=dict(zip(H.split(),[[sum,any,0,lambda x:sum((y[1:]for y in x),[K])],[Z(sub)],[Z(mul),all,0,lambda x:x[0][:1]+x[0][1:]*x[1]],[Z(div),lambda x:[K]+map(lambda z:S([x[1],z]if Q(x[1])==2else x[1]+[z]),x[0][1:])],[lambda x:len(set(map(str,x)))<2]*6,[lambda x:x[0]%x[1]],[lambda x:S(x[2])if S(x[0])in[0,[K]]else S(x[1])]*6,[lambda x:x[0]+1,0,0,lambda x:x[0][:1]+x[0][-1:]+x[0][1:-1]],[lambda x:x[0]-1,0,0,lambda x:x[0][:1]+x[0][2:]+[x[0][1]]],[lambda x:x[0]in[0,[K]]]*6,[0]*3+[lambda x:len(x)-1]]))
H=H[:15]+H+" if"
def Q(x):
 t=A(x);w=int,bool,str
 if t in w:return w.index(t)
 if t==list and x:return 5-(2*(x[0]==K)+(str==A(x[0])and len(x)<H.count(x[0])+1))
 E()
def S(G):
 if Q(G)<2:return G
 G or E();c=G[0];r=G[1:];c==K or r or E()
 if c!="if":r=[x if Q(x)in{2,4}else S(x)for x in r]
 if c==K:return[c]+r
 k=map(Q,r);m=min(k);M=max(k);v=[m,[-1,3][{m,M}=={4,5}]][m!=M]
 try:return D[c][v](r)
 except:E()
def C(x):return"(%s)"%" ".join(map(C,x))if A(x)==list else str(x).lower()
def I(G):
 for c in"+-*/%=()":G=G.replace(c," %s "%c)
 return C(S(R(G.strip().split())))
print I(raw_input())

Complete overhaul. If you want to see the previous versions, check out the edit history.
There's a lot more to be golfed. I'm slowly working on it.
With zlib/base64 we get 1093 * 0.8 * 0.85 = 743.24:
import base64,zlib
exec zlib.decompress(base64.b64decode("eJx9VE1P4zAQvedXGEuV7MbttgX2kOADAtSugANbTljWKqSuNku+5Lg0BfHfd8ZJCwjt9tLpdN6bmTczXtuqIFVtbOIqS7KirqwbBufS7WoTX0uaZ42jwcqsyRXjUW2z0tErGps2c4x7/08251FAclOCARwQF9/L+biuajbh8Y1UOiDZmjIq5T0EkjnposDc/s5yQzk9knM10dFNKBXS6fhDzIHJGrexJbnxbNyz+Qhnd0jbSvOc5Ox+7DKXG8YRm63JHWv52SzqwS04Pci0qand3n0fLCQNyYgMyTciyQCBWZmSlUlJWTlsjgYPMk+Kx1VCdlFvtIBfbVLDdqLlwaVcZaljL1nNFuOmzlEhoVSzKURS7sREHFDgYmynppFeQ5s7SEVaCL3WXAv1wJrNY2cUm5yLJM8/YlsQSkVTHXoDKIatmmofvsqe+Xsg0IVFUrPe8RItmcJQ8aI7WcDmUs5M3hiCP0L1ornY02IFBy4cbmMcQ77GWeiWg6h6+P1DDAIHfS0H5xLSzDSHhGhNwCrVBDvVPu2yq+IrUTiFnv/Z9Qjq2/c/+pwQvaP/gmeAVR1Yf4EeyvMlTfTwOPysQssxISzXQi6A81SHi5DiQvpbwGWDXXTyHIx4K+FaxGNV5QJEw7UlDme93a/ddpyVK9Myx7s/pcRzI0m58qvlY05HbDb02kl5zUOUXyI9iomBXVFni3FabUrX+cMpbv9Vf6DL7kD90OcfbmEeHE4xTv0Bxha+QFv4Ka/xL3s4Q0CnR5JCo5GVqt1fVla+zsTJ236YHPe5xR6t7jBA1OdTqQ5BhCeJS3QnLI8LWWQle+LxLfhaNJ6lKgSMVxxr9VqI2zcpX0/E6ZvWqjiSt7o79r7+S2BUz5rZ93Pet3yBc+jCKBs0nA4ooeM/FaTD7Be4wFAdTqnX3HcA2oJnnFdbY3umH5142FcKfdFwNPw2kIzTaA5vnDV1nsD9p4KSQUPoIIVa+vIu2JLBYzYGUngR+P5FgE/gn1Ggtsn2V1bWG3T/BUW+qRU="))

Note: If you see my score going up, it's probably because I found a few bugs

more of a code challenge than a code golf but still,  4872*0.8=3897,6

Common Lisp, 868 bytes * 0.85 = 737.8
Is it cheating to implement Lisp with Lisp? Lots to optimize here, still.
(SETF (READTABLE-CASE *READTABLE*) :PRESERVE)(PRINC(LABELS((B(X)(FIND X'(true false)))(R(X)(IF X'true'false))(V(X)(MEMBER X'(0()false)))(A(&REST X)(R(NOTANY #'V X)))(O(&REST X)(R(NOTEVERY #'V X)))(E(X &KEY N)(IF(LISTP X)(ECASE(FIRST X)(+(APPLY(IF(EVERY'NUMBERP #1=(MAPCAR(IF N #'IDENTITY #'E)(CDR X)))'+(IF(EVERY'LISTP #1#)'APPEND #'A))#1#))(-(APPLY(IF(EVERY'NUMBERP #1#)'- #'O)#1#))(*(IF(LISTP #2=(CAR #1#))(LOOP FOR I TO(1-(CADR #1#))APPEND #2#)(APPLY'* #1#)))(/(IF(LISTP #2#)(LOOP FOR I IN #2#COLLECT(E `(,(CADR #1#),I):N T))(REDUCE'FLOOR #1#)))(%(APPLY'MOD #1#))(=(R(LOOP FOR I IN(CDR #1#)ALWAYS(EQUAL I #2#))))(list #1#)(inc(IF(LISTP #2#)(APPEND(LAST #2#)(BUTLAST #2#))(1+ #2#)))(dec(IF(LISTP #2#)(APPEND(CDR #2#)`(,(FIRST #2#)))(1- #2#)))(if(IF(V(E(CADR X)))(E(CADDDR X))(E(CADDR X))))(not(R(V #2#)))(len(LENGTH #2#)))X)))(OR(IGNORE-ERRORS(OR(E(READ))"()")):E))

Prints out an E in case of an error in input. Sample runs:
$ sbcl --script glisp.lisp
(list 1 2 3 (list 4 5 true))
(1 2 3 (4 5 true))

$ sbcl --script glisp.lisp
(/ 4000 (+ 1 2 3 4 (* 5 8)))
80

$ sbcl --script glisp.lisp
(+ (not (- (len (list 5 6 7)) (/ 10 3))) true)
true

$ sbcl --script glisp.lisp
(if (           len (list )  ) 4 (if    (+ (= 8 8    8) (not (list 4))) 8 5))
5

$ sbcl --script glisp.lisp
(this is an error)
E

$ sbcl --script glisp.lisp
(if (% 4 2) (this is an error) 42)
42

as long as it isn't a kind of eval function...

Haskell, 972
r=fst.f
f('(':s)|(f:a,b)<-g s=(f%filter(/="")a,b)
f s=span(`notElem`" ()")s
j=dropWhile(==' ')
g""=([],"")
g s|')':l<-r=([x],l)|(y,t)<-g$j r=(x:y,t)where(x,r)=f$j s
"%"%c=show$foldr(mod.read)(maxBound::Int)c
"+"%c|t(c!!0)<1="(list "++tail(c>>=(' ':).drop 6.init)++")"|t(c!!0)<2=show$sum$map read c|0<1=i$all((=='t').head)c
"-"%c|t(c!!0)<2=show$foldl1(-)$map read c|0<1=i$any((=='t').head)c
"*"%c=fst$f$"(+ "++unwords([1..read$last c]>>init c)++")"
"="%c=i$all(==c!!0)c
"/"%c|t(c!!0)<1,[a,b]<-c="list"%map(\x->b%[x])(fst$g$drop 6 a)|0<1=show$foldl1 div$map read c
"if"%[p,a,b]|elem p["0","()","false"]=b|0<1=a
"list"%c="(list "++unwords c++")"
"len"%[c]=show$length(words c)-1
"inc"%[c]|t c>0=show$read c+1|([],_)<-g$drop 6 c="(list)"|(x,_)<-g$drop 6 c="list"%(last x:init x)
"dec"%[c]|t c<1,(x,_)<-g$drop 6 c="list"%(drop 1 x++take 1 x)|0<1=show$read c-1
"not"%[c]="if"%[c,"false","true"]
s%c="?"
i p|p="true"|0<1="false"
t('(':_)=0
t(c:s)|c<':',c>'/'=1|elem c"th"=2
t _=3

quite a hacky solution. this stores everything as strings in output-ready form - their types can be distinguished by their first letter - 0..9 for numbers, ( for  lists, t or f for booleans, and everything else for functions.
to run use the r function.


text:
Golf me some cash from the ATM
The task is simple. Get me some 1000, 500 and 100 notes.
How ? you might ask. Don't worry, no need of robbing a bank as there is an ATM nearby which accepts your credit card. But your credit limit is just enough for the task so you have to be careful with the withdrawals.
Challenge
Given the number of 1000, 500 and 100 notes required, calculate the specific withdrawals needed to get at least those many notes. In each withdrawal, the ATM can spit out each of the note based on the following rules:

Amount withdrawn (A) is less than 5000

If A%1000 == 0, then ATM spits 1 500 note, 5 100 notes and rest 1000 notes
Else if A%500 == 0, the ATM spits 5 100 notes, rest 1000 notes
Else if A%1000 < 500, the ATM spits floor(A/1000) 1000 notes and rest 100 notes
Else if A%1000 > 500, the ATM spits floor(A/1000) 1000 notes, 1 500 and rest 100 notes

Amount withdrawn is greater than equal to 5000

If A%1000 == 0, then the ATM spits 2 500 notes and rest 1000 notes
Else if, A%500 == 0, the ATM spits 1 500 note and rest 1000 notes
Else if A%1000 < 500, the ATM spits floor(A/1000) 1000 notes and rest 100 notes
Else if A%1000 > 500, the ATM spits floor(A/1000) 1000 notes, 1 500 and rest 100 notes

For clarification, here is a complete table of notes withdrawn for all possible amounts up to 7000 (you can withdraw more, but the pattern does not change afterwards). The order is <1000> <500> <100>:
 100 => 0 0 1                  2500 => 2 0 5                   4800 => 4 1 3
 200 => 0 0 2                  2600 => 2 1 1                   4900 => 4 1 4
 300 => 0 0 3                  2700 => 2 1 2                   5000 => 4 2 0
 400 => 0 0 4                  2800 => 2 1 3                   5100 => 5 0 1
 500 => 0 0 5                  2900 => 2 1 4                   5200 => 5 0 2
 600 => 0 1 1                  3000 => 2 1 5                   5300 => 5 0 3
 700 => 0 1 2                  3100 => 3 0 1                   5400 => 5 0 4
 800 => 0 1 3                  3200 => 3 0 2                   5500 => 5 1 0
 900 => 0 1 4                  3300 => 3 0 3                   5600 => 5 1 1
1000 => 0 1 5                  3400 => 3 0 4                   5700 => 5 1 2
1100 => 1 0 1                  3500 => 3 0 5                   5800 => 5 1 3
1200 => 1 0 2                  3600 => 3 1 1                   5900 => 5 1 4
1300 => 1 0 3                  3700 => 3 1 2                   6000 => 5 2 0
1400 => 1 0 4                  3800 => 3 1 3                   6100 => 6 0 1
1500 => 1 0 5                  3900 => 3 1 4                   6200 => 6 0 2
1600 => 1 1 1                  4000 => 3 1 5                   6300 => 6 0 3
1700 => 1 1 2                  4100 => 4 0 1                   6400 => 6 0 4
1800 => 1 1 3                  4200 => 4 0 2                   6500 => 6 1 0
1900 => 1 1 4                  4300 => 4 0 3                   6600 => 6 1 1
2000 => 1 1 5                  4400 => 4 0 4                   6700 => 6 1 2
2100 => 2 0 1                  4500 => 4 0 5                   6800 => 6 1 3
2200 => 2 0 2                  4600 => 4 1 1                   6900 => 6 1 4
2300 => 2 0 3                  4700 => 4 1 2                   7000 => 6 2 0
2400 => 2 0 4

List provided by Martin
The Catch
Since the credit limit in your credit card is just enough, you need to make sure that the total amount withdrawn across the withdrawals is the minimum possible for the given input/requirement of notes.
Input
Input can be in any favorable format for three numbers corresponding to the number of notes required of value 1000, 500 and 100. Not necessarily in that order.
Output
Output is the amount to be withdrawn in each transaction separated by a new line.
Examples
Input (format <1000> <500> <100>):
3 4 1

Output:
600
600
600
3600

few more:
7 2 5
5000
3500

1 2 3
600
1700

21 14 2
600
600
600
1600
5000
5000
5000
5000
5000

Assumptions

You may assume that the ATM has infinite number of notes of each amount.
You may also assume that you can make any number of transactions.
Furthermore, the solution to some input values might not be unique, so you can output any 1 of the solution which fulfills the minimum amount possible and minimum notes required conditions.

As usual, you may write a full program reading input via STDIN/ARGV and printing output to STDOUT or a function taking input via arguments and returns either a list of integer corresponding to the amounts or a string with amounts separated by a new line.
This is code-golf so shortest code in bytes wins.

@nutki indeed . Edited.

Are there any speed restrictions? Should the last test case 21 14 2 finish in a reasonable time?

@Jakube In a reasonable time - yes (say less than 5-6 hours). But as such, no limit as this is code-golf.

So, if I withdraw 0, it will give me five 100 notes?

@AJMansfield of course not. You cannot withdraw 0 amount

JavaScript, 184 148
function g(a,b,c){x=[];while(a>0||b>0||c>0){i=b<3||a<4?a:4;a-=i;if(i>3&&b>1){b-=2;i++}else{i+=(c--<b&&i>4?0:.1)+(b-->0?.5:0)}x.push(i*1e3)}return x}

http://jsfiddle.net/vuyv4r0p/2/
returns a list of integers corresponding to the withdrawal amounts

Try g(5,1,1). One better solution: 5600.

should be fixed now

g(5,1,0), solution: 5500.

that should now also be fixed ^^ thanks for pointing that out, i must be too sleepy

g(5,2,0), solution: 6000.

fixed, also shortened code by quite some bytes

You can save a few bytes by saying x.p=x.push

actually, it would be 2 bytes longer... x.p=x.push; is 11 bytes, bytes saved would be 3*3 = 9 bytes

Pretty sure [2,1,4] should give [2900], right? Also with ES6 you can golf this to 131 bytes

@RedwolfPrograms: [2900], [2800,100], [2700,100,100] and [2600,100,100,100] are all valid solutions for the input [2,1,4]. Note how there is no requirement for minimizing the number of transactions, only the sum total. // Nice solution, sadly ES6 hadn't yet been around when I wrote this answer.

@hoffmale Oh, I didn't notice that was allowed, sorry :p. I think some of the changes in the ES6 one might have been possible in 2015, but this is a really impressive answer either way.

Perl 5: 223
Edit
This solution was done with a wrong assumption that 7K is the ATM limit. This actually made the task more interesting as it required dynamic programming (the move pattern was quite regular, but hard-coding it would be likely longer than calculating live as I did). With any amount possible the move pattern is so regular that it is trivial to hard-code it. I don't know if the solution by @hoffmale is now correct, but it will be among these lines. So sadly it will be another task where first somebody comes with a solution and then it gets ported to a golfing language for a win.
A bit slower than the original solution (but still sub-second for parameters below 100).
#!perl -pa
$c{0,0}=$f=($a,$b,$c)=@F;for$i(0..$b){for$j(0..$a){
/.(?=.$)/>($n=$c{$i-$`,$j-$'})||${$r=\$c{$i,$j}}<($x=$n+$&)&&$$r
or$f=$$r="$x $n".($'.$&+5*$`)."00
"for 204..206,105,106,11..15,110..114}}$_=$f."100
"x($c-$f+3);s/.*\b3//

Faster 259 solution.
#!perl -pa
$c{0,0}=($a,$b,$c)=@F;for$i(0..$b){for$j(0..$a){
/\B./<($%=$c{$i-$&,$j-$'}+$`)&&(!${$r=\$c{$i,$j}}||$$r>$%)and$d{$i,$j}=$_,$$r=$%for
qw/024 025 026 015 016/,101..105,110..114}}
$d{$b,$a}=~/\B./,$c-=$`,$b-=$&,$a-=$',print$'.$`+5*$&,"00
"while$a+$b;$_="100
"x$c

Uses STDIN:
$perl atm.pl <<<"21 14 2"
5000
5000
5000
5000
5000
600
600
600
1600

Try 10 0 0. Better solution: 10100.

@user23013 oops, I misunderstood the question. I assumed 7k is the maximum amount :( I hope I will be able to fix it.


text:
Find the Straightest Path in a Maze
In this challenge, your job is to find the straightest path from point A to point B in a two-dimensional maze. This is very similar to finding the shortest path, which has been done to death, but instead of minimizing the length of the path, you minimize the number of turns (or angles or corners, whatever you want to call them).
Input
A single string, divided into rows of equal lengths by either newlines or hyphens - (your choice). The rows form a rectangular maze, with . representing an empty space, # representing an impassable wall, and A and B representing the starting point and the goal. There is guaranteed to be exactly one A and exactly one B, and a path between them.
Output
The minimal number of turns in a path from A to B. The paths can only go in the four cardinal directions, not diagonally. Note that the number of turns is 0, if there is an unobstructed straight path from A to B.
Example
The shortest path in the maze on the left below is shown in the middle, while the straightest path is shown on the right. The turns are shown as plus signs +.
##......#  ##...+-+#  ##+--+..#
...#.B#.#  ...#.B#|#  ..|#.B#.#
.#.####.#  .#.####|#  .#|####.#
.#...#...  .#...#++.  .#|..#...
...#...#.  ...#..|#.  ..|#...#.
#......A#  #.....+A#  #.+----A#

The shortest path has length 10 and 5 turns, while the straightest path has length 14 and 3 turns. The correct output would be 3.
Additional Rules
You can write either a full program (STDIN to STDOUT) or a function. The shortest byte count wins, and standard loopholes are disallowed.
Your program need not be efficient, so brute forcing is allowed. However, there is a bonus of -20 % for being able to compute the final test case in a reasonable time (max. 15 minutes on my 6-year-old computer).
Test Cases
A trivial maze:
A..B

Output 0

A small maze:
##......#
...#.B#.#
.#.####.#
.#...#...
...#...#.
#......A#

Output 3

A medium-sized maze:
.....#..#.........##.
#.........#....##....
#..B#....##..........
...#...#.....##.....#
..#..##....##.....#..
#........#..........#
####....######.......
..A#......###...#####
..######..........###
........###........##
#....................
##...........########

Output 9

Another medium-sized maze, but slightly more complex:
......#####...#####............####.....
......#.....#.#...#....###...#..........
........#.#.#.#...#....#.....#....#...##
##....#...#..............##..#.#.##...##
#.....##.######.#.#..#####...#.......###
#..##.......#...#....#.....###....#...##
#...###...#.#.###....#.#.....###..#....#
#.....###.#...#......#.#####...##.#.....
##......#.##.......#...##...........#...
....#.....#.....#......#....#...........
A.........#..#......#..#B..........#####

Output 12

A large maze (A and B are in the corners):
##..#...#.##....#.#....###...##....#.....#........#....##..#...#......###..#........#.#..#.......#.A
###....##....##..#.......##...##......#.......#...#..#..........#.#........#...#..##.....#....##.#.#
..........#...#.#..#...##.#..#.###............#.##...#.#........#...#.#...####......#.#..#..........
.......##.....#.............#..##.....###.....#...#......##...#....#..##....######.#.##.......#.....
...##.#.......#..#.#.#...#......#....#..#.#.............................#.#.##..#.....#.#........#..
##.#..#..##......#...#..........#..#...##........#..#.....##.##...##.....#.##..###..#..#............
....#.#...#...#.#....##....#......#..##.....#.###..#..#.....#....#.#...#..###.#...###.....#...#...#.
...#..#.........##...#.....#..#..#.#.....#...........##...#.##..#.............#...#...##...#........
....#####..#..#..#...#..#.#........##...........#####...#.......##.#...##......#.....#.....#.##.....
.#..........#....#.##.....###.........#...........#......#.#.#..##.....#........#.#.##....##....#...
..#.....#....#....#....#......##.#...#..###...............#..............#....#..#..#.#..###...#....
...........##.##..#...#.#.#..........#..#.........#.##...######......................#..............
.....#.....#..#..........#..##..#.#..###...#..#.......#..#............#..#.#.##.......#.....##...#..
...###....#........#.##......#.#............#..##......#..###...##..#......#..#.#.#..#..#.#..##....#
......#.....#..#.#......##..#......#................#..####..#....#...........#..............#..#.#.
......#............#...#.#..#...#..##..............#....#..#........##..##.......#.....#...#.#......
........#...........##...............#.....#.#.....#.#.####.##..#...#.###.....#.....#...#.......#...
........##..###.....#.#...#....##......#.#..#......................#.#.##.#.#......#..#...#.##..#..#
.........#......#.......###............#.#.##...#...#........#..#..#.....#.#.......#....#...........
.##.......#.....#.##.#..#...###..........#......#..........#.....#.......#...#....##.#.......#.....#
..#.#....##..##......#..#.........#....#...#....#..#.#.#.....#..#.#..#..##....#.......#.##..#......#
.......##.....#....#.##.....##....#..........#.....##.........#........#...##......#.#....#....#....
....#.............#.#...........#.#.#......##......#.......###......#......#.##..#...#...#.#....#...
#...#....#.#.#...#..#.##..#.....##.......#.#......#....#..#.#.#.#....#.........#...#............#...
....#.......#.......#.#...............##........#.#..#..#.#..###.#..#.......##.#...#..##..#.#.......
...#....#..#..##.##..##.##.#....#......##.###..#.....#...##...........#.#..........##..#..#.#.......
...........#.#.#.##.#.#.##.##..###...#......#.#.#.......####.......#....###.........#.#.......##....
.........##.....#..#.#....#..##...#....###.....#......#..##.#.....#....#....##.#.......#........#..#
####.#....###......#..#....#..#.....#....#......#....#....#...#...............#....#.....#.##.##..#.
#..#.#...#...................#.#.#...........#....#.......#..............##...##.#......#....#.##...
#..#........#....#..............###..####...##.##..#...#....#...#....#.....#.........#..#..#..#.....
.....##.......##.......#.#....#...#.......#...##....#.......#....#...#.#........##...#.....##...####
.......##........#......##.....##...#..........##........#.....#..#.#.#.......#......##.......#.....
......##..#...#..........#....#......#..#....#...#.#...#..#....#.#.##...............#.....#.##...#.#
.#..##............###.#....#..#.......##...#...#.#...#...........##.........##.#.#........#..##.....
.............#....#....#..#.#.......#......#..##..#...#............#.#........##..####...#..........
..#....#####.#...##.#.#...........##.##...#.#.......#.##.###...#..#.#.......#....#..#......##.......
.........#..#....#..###.........#..#..#.##........#...................#.##.........###.........#.##.
..#..#..#.........#..#...........#...#.......#.##.......##.........#.#.....#...#.#...###...#...#..#.
B##.#..........#...........#.#.##...#......##....###.#..#.......................#....#.....#..#..#.#

Output 21

@FryAmTheEggman Good point, I updated the condition.

This isn't very similar to finding the shortest path: it is finding the shortest path, which as you rightly state has been done to death.

@PeterTaylor And an almost exact duplicate too... should've done my research. :/

Too bad, that this question got closed. Found a 255 char solution in Python (and I still see a few golfing opportunities). Way shorter solution than the other answers. But too lazy to implement printing of the directions.

@PeterTaylor even though this is a dupe, finding straightest path is still not exactly equal to finding the shortest one.

@Optimizer, it is, it's just that the graph isn't the one normally associated with the textual representation.

@PeterTaylor I am talking wrt ASCII based maze (like this question). Lets not change the context please.

@Optimizer, I'm not changing the context, just explaining what I meant by my original comment. In fact, if someone wants to get a non-dupe question out of this one it would be to take the grid and output some nice representation of the graph over which it requires running a shortest path calculation. (I'm about to go to bed, so I'm not going to try to check my intuition that it's not always planar, but if it were then a planar representation ready to pass into http://codegolf.stackexchange.com/q/153/194 would be very cool).

@PeterTaylor I think you and I are not talking about the same thing here. The very first example in this question clearly proves that shortest path is not always the straightest. I am still not sure about what you meant in your original comment.