text:
Help Indiana Jones to get the treasure
Story
Indiana Jones was exploring a cave where a precious treasure is located. Suddenly, an earthquake happened.
When the earthquake ended, he noticed that some rocks that had fallen from the ceiling blocked his way to the treasure. He also noticed that he could push a stone, but since stones were very heavy, he couldn't push two consecutive stones.
Your objective is to help Indiana Jones get the treasure. Since it's very hard to push even a single stone, the number of pushes is very important.
Problem

Find the best way (where Indiana Jones pushes stones as little as possible), to find the treasure.

Map (input)
The map is an m by n (both larger than 1) matrix which can contain five kinds of cell:

0 which means the blank cell,
1 which means the wall,
2 which Indiana Jones is located in (only one exists),
3 which the treasure is located in (only one exists),
and 4, which means a rock.

In the first row of the map, the dimension of the map is specified like 4 6, and from the second row to the last row of the map, the structure of the cave is specified something like this.
110131
104040
100101
200000

Therefore, the full map is:
4 6
110131
104040
100101
200000

which means

The map is given by stdin, a file (you can specify the name of the file), or an array in the code which contains only above information.
Output
The minimum amount Indiana Jones should push. If there's no such way, output X.
In above case, he can push a stone in the left upward, then he can push a stone in the right rightward to get the treasure. Therefore, the output in this case is 2.
However. in this case :
4 6
111131
104040
100101
200000

(look below section) he can't push right stone because it will destroy the treasure. Also, pushing left stone rightward changes nothing. Therefore, the output is X.
Rules

He can move in only four direction, up, down, left, and right.
He can't push two consecutive stones.
He can't pull any stone, and he can push a stone only in one direction('forward').
He can't go through walls. Only places he can go are blank cells and the treasure cell.
The stone can't be placed on the treasure. That will destroy the treasure. :(
He can't go outside of the map.

Goals
Program which can handle the most maps (provided at the 'Example' section + others) in a reasonable time (specifically, 10 seconds) and outputs the right answer wins.
Here 'others' means example inputs provided in answers. This means you should make a smart algorithm so that other programs can't solve maps that your program can solve, and maps solved by other programs can be solved by your program. However, putting solutions in the code will not considered as valid.
Note
This was originally a mid-term project of an AI class which I listened to, only one thing was different : it was said that there were only two rocks.
It was said that this problem is NP, but it was also said that a good heuristic algorithm can solve the problem quite efficiently. I used some ideas and heuristics to solve the problem efficiently, and my code could find all solutions of samples very quickly (less than a second).
However, when there were more than two rocks, there were some cases where the code couldn't find the answer in a reasonable time. I had some ideas, but some of those were 'wrong', and I couldn't express other ideas to the code. I wanted to see what smart algorithms exist to solve this problem, so I wrote this.
Since I already completed the project (btw, images are not mine - I googled those), you don't have to worry about that.
Examples
Examples can be seen at here. You can also see examples, and test your results at here (this should work in modern browsers). You can get the map in the format described above, by typing whatisthis() in the JS console.
http://bit.sparcs.org/~differ/sokoban/#0 ~ http://bit.sparcs.org/~differ/sokoban/#19 contains examples which it was originally the class provided.
Result
Sorry, I was late.. quite a lot actually. :P
(I was quite too lazy to score. Sorry.)
Below is the result. (X: wrong, O: right, ?: takes at least 10s, halted)
Map#: 0 1 2 3 4 5 12 15 19 T1 T2 T3 T4 T5 T6 T7
Ruby: X O O ? O O  O  X  ?  ?  O  ?  ?  ?  ?  ?
Java: O O X O X X  O  O  ?  ?  O  O  O  X  O  O

(Java 19: took 25s, the result was correct.)
(I used ruby 1.9.3 and javac 1.7.0_13)
It seems that the Java algorithm was indeed better. (By the way, I thought of a similar method, but I realized that maps like test map 5 exist.)

That's a difficult one.

This makes me want to write a random number generator based on the complexity of the puzzle, always undershooting... people would make up hard puzzles, then scratch their heads for days wondering how my program solved it with only 4 pushes... :)

@NathanWheeler, yeah, build a indeterminstic solver.  It works, but you have to run it in a quantum computer.  :P

It'd have to compute it starting Indiana Jones at the treasure and working backwards, like you would solve a maze.  The difference being that state isn't determined only by position but also by rock positioning (I can pass same place twice if rocks have since been moved).  Hmm, I'll have to think more about this..

Java - A bit smarter / faster
Quite a bit of code there. I's trying to be faster by evaluating the pushes in order of "how likely is this to free a way to the treasure", which itself is based on two Dijkstra traversals (one stops when encountering rocks, the other ignores rocks). It's working pretty nicely, and the one example from the pastebin that appears to be troublesome for the author is solved in circa 2 seconds by this implementation. Some other examples take up to 30-40 seconds, which I still find too long, but I couldn't find a way to improve on that without breaking the stuff :)
I've split my stuff in several files to get a better structure out (also why I switched to Java from ruby):
Entry point:
import java.util.Date;
public class IndianaJones {
    public static void main(final String[] args) throws Exception {
        final Maze maze = new Maze(System.in);
        final Date startAt = new Date();
        final int solution = maze.solve();
        final Date endAt = new Date();
        System.out.printf("Found solution: %s in %d ms.",
                          solution < Integer.MAX_VALUE ? solution : "X",
                          endAt.getTime() - startAt.getTime());
    }
}

Direction helper enum:
enum Direction {
    UP(-1, 0), DOWN(1, 0), LEFT(0, -1), RIGHT(0, 1);

    public final int drow;
    public final int dcol;

    private Direction(final int drow, final int dcol) {
        this.drow = drow;
        this.dcol = dcol;
    }

    public final Direction opposite() {
        switch (this) {
        case UP:
            return DOWN;
        case DOWN:
            return UP;
        case LEFT:
            return RIGHT;
        case RIGHT:
            return LEFT;
        }
        return null;
    }
}

An abstract class to represent a located part of the "maze":
abstract class PointOfInterest {
    public final int row;
    public final int col;

    protected PointOfInterest(final int row, final int col) {
        this.row = row;
        this.col = col;
    }

    public final boolean isAt(final int row, final int col) {
        return this.row == row && this.col == col;
    }

    @Override
    public final String toString() {
        return getClass().getSimpleName() + "(" + row + ", " + col + ")";
    }

    @Override
    public final int hashCode() {
        return row ^ col;
    }

    @Override
    public final boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (!(obj instanceof PointOfInterest))
            return false;
        if (!getClass().equals(obj.getClass()))
            return false;
        final PointOfInterest other = (PointOfInterest) obj;
        return row == other.row && col == other.col;
    }
}

And finally, the maze itself:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.EnumSet;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;

public class Maze {
    private static final char WALL = '1';
    private static final char INDY = '2';
    private static final char GOAL = '3';
    private static final char ROCK = '4';

    private final Maze parent;
    private final Set<Maze> visited;
    private final boolean[][] map;
    private final int[][] dijkstra;
    private int[][] dijkstraGhost;
    private String stringValue = null;

    private int shortestSolution = Integer.MAX_VALUE;

    private Goal goal = null;
    private Indy indy = null;
    private Set<Rock> rocks = new HashSet<>();

    private Maze(final Maze parent, final Rock rock, final Direction direction) {
        this.parent = parent;
        this.visited = parent.visited;
        map = parent.map;
        dijkstra = new int[map.length][map[rock.row].length];
        for (final int[] part : dijkstra)
            Arrays.fill(part, Integer.MAX_VALUE);
        goal = new Goal(parent.goal.row, parent.goal.col);
        indy = new Indy(rock.row, rock.col);
        for (final Rock r : parent.rocks)
            if (r == rock)
                rocks.add(new Rock(r.row + direction.drow, r.col + direction.dcol));
            else
                rocks.add(new Rock(r.row, r.col));
        updateDijkstra(goal.row, goal.col, 0, true);
    }

    public Maze(final InputStream is) {
        this.parent = null;
        this.visited = new HashSet<>();
        try (final BufferedReader br = new BufferedReader(new InputStreamReader(is))) {
            String line = br.readLine();
            final String[] sizeParts = line.split(" ");
            final int height = Integer.parseInt(sizeParts[0]);
            final int width = Integer.parseInt(sizeParts[1]);
            map = new boolean[height][width];
            dijkstra = new int[height][width];

            int row = 0;
            while ((line = br.readLine()) != null) {
                for (int col = 0; col < line.length(); col++) {
                    final char c = line.charAt(col);
                    map[row][col] = c == WALL;
                    dijkstra[row][col] = Integer.MAX_VALUE;
                    if (c == INDY) {
                        if (indy != null)
                            throw new IllegalStateException("Found a second indy!");
                        indy = new Indy(row, col);
                    } else if (c == GOAL) {
                        if (goal != null)
                            throw new IllegalStateException("Found a second treasure!");
                        goal = new Goal(row, col);
                    } else if (c == ROCK) {
                        rocks.add(new Rock(row, col));
                    }
                }
                row++;
            }

            updateDijkstra(goal.row, goal.col, 0, true);
        } catch (final IOException ioe) {
            throw new RuntimeException("Could not read maze from InputStream", ioe);
        }
    }

    public int getShortestSolution() {
        Maze ptr = this;
        while (ptr.parent != null)
            ptr = ptr.parent;
        return ptr.shortestSolution;
    }

    public void setShortestSolution(int shortestSolution) {
        Maze ptr = this;
        while (ptr.parent != null)
            ptr = ptr.parent;
        ptr.shortestSolution = Math.min(ptr.shortestSolution, shortestSolution);
    }

    private final boolean isRepeat(final Maze maze) {
        return this.visited.contains(maze);
    }

    private final void updateDijkstra(final int row, final int col, final int value, final boolean force) {
        if (row < 0 || col < 0 || row >= dijkstra.length || col >= dijkstra[row].length)
            return;
        if (map[row][col] || isRockPresent(row, col))
            return;
        if (dijkstra[row][col] <= value && !force)
            return;

        dijkstra[row][col] = value;
        updateDijkstra(row - 1, col, value + 1, false);
        updateDijkstra(row + 1, col, value + 1, false);
        updateDijkstra(row, col - 1, value + 1, false);
        updateDijkstra(row, col + 1, value + 1, false);
    }

    private final void updateDijkstraGhost(final int row, final int col, final int value, final boolean force) {
        if (row < 0 || col < 0 || row >= dijkstra.length || col >= dijkstra[row].length)
            return;
        if (map[row][col] || isRockPresent(row, col))
            return;
        if (dijkstraGhost[row][col] <= value && !force)
            return;

        dijkstraGhost[row][col] = value;
        updateDijkstraGhost(row - 1, col, value + 1, false);
        updateDijkstraGhost(row + 1, col, value + 1, false);
        updateDijkstraGhost(row, col - 1, value + 1, false);
        updateDijkstraGhost(row, col + 1, value + 1, false);
    }

    private final int dijkstraScore(final int row, final int col) {
        if (row < 0 || col < 0 || row >= dijkstra.length || col >= dijkstra[row].length)
            return Integer.MAX_VALUE;
        return dijkstra[row][col];
    }

    private final int dijkstraGhostScore(final int row, final int col) {
        if (dijkstraGhost == null) {
            dijkstraGhost = new int[map.length][map[indy.row].length];
            for (final int[] part : dijkstraGhost)
                Arrays.fill(part, Integer.MAX_VALUE);
            updateDijkstraGhost(goal.row, goal.col, 0, true);
        }
        if (row < 0 || col < 0 || row >= dijkstra.length || col >= dijkstra[row].length)
            return Integer.MAX_VALUE;
        return dijkstraGhost[row][col];
    }

    private boolean isRockPresent(final int row, final int col) {
        for (final Rock rock : rocks)
            if (rock.isAt(row, col))
                return true;
        return false;
    }

    public boolean isEmpty(final int row, final int col) {
        if (row < 0 || col < 0 || row >= map.length || col >= map[row].length)
            return false;
        return !map[row][col] && !isRockPresent(row, col) && !goal.isAt(row, col);
    }

    public int solve() {
        return solve(0);
    }

    private int solve(final int currentDepth) {
        System.out.println(toString());
        visited.add(this);
        if (isSolved()) {
            setShortestSolution(currentDepth);
            return 0;
        }
        if (currentDepth >= getShortestSolution()) {
            System.out.println("Aborting at depth " + currentDepth + " because we know better: "
                               + getShortestSolution());
            return Integer.MAX_VALUE;
        }
        final Map<Rock, Set<Direction>> nextTries = indy.getMoveableRocks();
        int shortest = Integer.MAX_VALUE - 1;
        for (final Map.Entry<Rock, Set<Direction>> tries : nextTries.entrySet()) {
            final Rock rock = tries.getKey();
            for (final Direction dir : tries.getValue()) {
                final Maze next = new Maze(this, rock, dir);
                if (!isRepeat(next)) {
                    final int nextSolution = next.solve(currentDepth + 1);
                    if (nextSolution < shortest)
                        shortest = nextSolution;
                }
            }
        }
        return shortest + 1;
    }

    public boolean isSolved() {
        return indy.canReachTreasure();
    }

    @Override
    public String toString() {
        if (stringValue == null) {
            final StringBuilder out = new StringBuilder();
            for (int row = 0; row < map.length; row++) {
                if (row == 0) {
                    out.append('\u250C');
                    for (int col = 0; col < map[row].length; col++)
                        out.append('\u2500');
                    out.append("\u2510\n");
                }
                out.append('\u2502');
                for (int col = 0; col < map[row].length; col++) {
                    if (indy.isAt(row, col))
                        out.append('*');
                    else if (goal.isAt(row, col))
                        out.append("$");
                    else if (isRockPresent(row, col))
                        out.append("@");
                    else if (map[row][col])
                        out.append('\u2588');
                    else
                        out.append(base64(dijkstra[row][col]));
                }
                out.append("\u2502\n");
                if (row == map.length - 1) {
                    out.append('\u2514');
                    for (int col = 0; col < map[row].length; col++)
                        out.append('\u2500');
                    out.append("\u2518\n");
                }
            }
            stringValue = out.toString();
        }
        return stringValue;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (!obj.getClass().equals(getClass()))
            return false;
        final Maze other = (Maze) obj;
        if (other.map.length != map.length)
            return false;
        for (int row = 0; row < map.length; row++) {
            if (other.map[row].length != map[row].length)
                return false;
            for (int col = 0; col < map[row].length; col++)
                if (other.map[row][col] != map[row][col])
                    return false;
        }
        return indy.equals(other.indy) && rocks.equals(other.rocks) && goal.equals(other.goal);
    }

    @Override
    public int hashCode() {
        return getClass().hashCode() ^ indy.hashCode() ^ goal.hashCode() ^ rocks.hashCode();
    }

    private final class Goal extends PointOfInterest {
        public Goal(final int row, final int col) {
            super(row, col);
        }
    }

    private final class Indy extends PointOfInterest {
        public Indy(final int row, final int col) {
            super(row, col);
        }

        public boolean canReachTreasure() {
            return dijkstraScore(row, col) < Integer.MAX_VALUE;
        }

        public SortedMap<Rock, Set<Direction>> getMoveableRocks() {
            final SortedMap<Rock, Set<Direction>> out = new TreeMap<>();
            @SuppressWarnings("unchecked")
            final Set<Direction> checked[][] = new Set[map.length][map[row].length];
            lookForRocks(out, checked, row, col, null);
            return out;
        }

        private final void lookForRocks(final Map<Rock, Set<Direction>> rockStore,
                                        final Set<Direction>[][] checked,
                                        final int row,
                                        final int col,
                                        final Direction comingFrom) {
            if (row < 0 || col < 0 || row >= checked.length || col >= checked[row].length)
                return;
            if (checked[row][col] == null)
                checked[row][col] = EnumSet.noneOf(Direction.class);
            if (checked[row][col].contains(comingFrom))
                return;
            for (final Rock rock : rocks) {
                if (rock.row == row && rock.col == col) {
                    if (rock.canBeMoved(comingFrom) && rock.isWorthMoving(comingFrom)) {
                        if (!rockStore.containsKey(rock))
                            rockStore.put(rock, EnumSet.noneOf(Direction.class));
                        rockStore.get(rock).add(comingFrom);
                    }
                    return;
                }
            }
            if (comingFrom != null)
                checked[row][col].add(comingFrom);
            for (final Direction dir : Direction.values())
                if (comingFrom == null || dir != comingFrom.opposite())
                    if (isEmpty(row + dir.drow, col + dir.dcol) || isRockPresent(row + dir.drow, col + dir.dcol))
                        lookForRocks(rockStore, checked, row + dir.drow, col + dir.dcol, dir);
        }
    }

    private final class Rock extends PointOfInterest implements Comparable<Rock> {
        public Rock(final int row, final int col) {
            super(row, col);
        }

        public boolean canBeMoved(final Direction direction) {
            return isEmpty(row + direction.drow, col + direction.dcol);
        }

        public boolean isWorthMoving(final Direction direction) {
            boolean worthIt = false;
            boolean reachable = false;
            int emptyAround = 0;
            for (final Direction dir : Direction.values()) {
                reachable |= (dijkstraScore(row, col) < Integer.MAX_VALUE);
                emptyAround += (isEmpty(row + dir.drow, col + dir.dcol) ? 1 : 0);
                if (dir != direction && dir != direction.opposite()
                    && dijkstraScore(row + dir.drow, col + dir.dcol) < Integer.MAX_VALUE)
                    worthIt = true;
            }
            return (emptyAround < 4) && (worthIt || !reachable);
        }

        public int proximityIndice() {
            final int ds = min(dijkstraScore(row - 1, col),
                               dijkstraScore(row + 1, col),
                               dijkstraScore(row, col - 1),
                               dijkstraScore(row, col + 1));
            if (ds < Integer.MAX_VALUE)
                return ds;
            else
                return min(dijkstraGhostScore(row - 1, col),
                           dijkstraGhostScore(row + 1, col),
                           dijkstraGhostScore(row, col - 1),
                           dijkstraGhostScore(row, col + 1));
        }

        @Override
        public int compareTo(Rock o) {
            return new Integer(proximityIndice()).compareTo(o.proximityIndice());
        }
    }

    private static final char base64(final int i) {
        if (i >= 0 && i <= 9)
            return (char) ('0' + i);
        else if (i < 36)
            return (char) ('A' + (i - 10));
        else
            return ' ';
    }

    private static final int min(final int i1, final int i2, final int... in) {
        int min = Math.min(i1, i2);
        for (final int i : in)
            min = Math.min(min, i);
        return min;
    }
}

Ruby - Huge & blostered
Somewhat naive implementation that brute-forces it's way through the labyrinth. It's not super fast in some (not so) weird cases. It can be improved by finding better heuristics than just "if it's closer to the treasure, we'll want to investigate first", but the general ideas are there.
It'll also show you how Indiana got his hands on the treasure in case he can, that's bonus.
EMPTY = '0'
WALL = '1'
INDY = '2'
GOAL = '3'
ROCK = '4'

map=%q|8 8
00001000
00000100
00000010
00000010
03004040
10000010
10000100
10000102|

def deep_dup(arr)
  dupl = arr.dup
  (0..dupl.size-1).to_a.each do |i|
    dupl[i] = dupl[i].dup
  end
  return dupl
end

class Map
  @@visited = []
  attr_reader :mapdata, :indy_r, :indy_c, :prev

  def self.parse(str)
    lines = str.split("\n")
    mapdata = []
    indy_r = -1
    indy_c = -1
    lines[1..-1].each_with_index do |line, idx|
      row = ((mapdata ||= [])[idx] ||= [])
      line.split(//).each_with_index do |c, cidx|
        if c==INDY
          indy_r = idx
          indy_c = cidx
          row[cidx] = EMPTY
        else
          row[cidx] = c
        end
      end
    end
    return Map.new(mapdata, indy_r, indy_c)
  end

  def initialize(mapdata, indy_r, indy_c, prev = nil, pushed = false)
    @mapdata = mapdata
    @mapdata.freeze
    @mapdata.each {|x| x.freeze}
    @indy_r = indy_r
    @indy_c = indy_c
    @prev = prev
    @pushed = pushed
  end

  def visit!
    @@visited << self
  end

  def visited?
    @@visited.include?(self)
  end

  def pushes
    pushes = @pushed ? 1 : 0
    if @prev
      pushes += @prev.pushes
    end
    return pushes
  end

  def history
    return @prev ? 1+@prev.history : 0
  end

  def next_maps
    maps = []
    [[-1, 0], [1, 0], [0, -1], [0, 1]].each do |dr, dc|
      new_i_r = self.indy_r + dr
      new_i_c = self.indy_c + dc
      if new_i_r >= 0 && new_i_r < @mapdata.size && new_i_c >= 0 && new_i_c < @mapdata[0].size
        new_map = nil
        pushed = false
        case @mapdata[new_i_r][new_i_c]
        when EMPTY, GOAL then new_map = @mapdata
        when ROCK then
          if @mapdata[new_i_r+dr] && @mapdata[new_i_r+dr][new_i_c+dc] == EMPTY
            new_map = deep_dup(@mapdata)
            new_map[new_i_r][new_i_c] = EMPTY
            new_map[new_i_r+dr][new_i_c+dc] = ROCK
            pushed = true
          end
        end
        if new_map && !@@visited.include?(new_map = Map.new(new_map, new_i_r, new_i_c, self, pushed))
          maps << new_map
        end
      end
    end
    return maps
  end

  def wins?
    return @mapdata[@indy_r][@indy_c] == GOAL
  end

  def to_s
    str = ''
    @mapdata.each_with_index do |row, r|
      row.each_with_index do |col, c|
        if r == @indy_r and c == @indy_c then
          str += 'I'
        else
          case col
          when EMPTY then str += '_'
          when WALL then str+= '#'
          when ROCK then str += 'O'
          when GOAL then str += '$'
          end
        end
      end
      str += "\n"
    end
    return str
  end

  def ==(other)
    return (self.mapdata == other.mapdata) &&
      (self.indy_r == other.indy_r) &&
      (self.indy_c == other.indy_c)
  end

  def dist_to_treasure
    if @distance.nil?
      @mapdata.each_with_index do |r, ri|
        r.each_with_index do |c, ci|
          if c == GOAL
            @distance = Math.sqrt((ri - @indy_r)**2 + (ci - @indy_c)**2)
            return @distance
          end
        end
      end
    end
    return @distance
  end

  def <=>(other)
    dist_diff = self.dist_to_treasure <=> other.dist_to_treasure
    if dist_diff != 0
      return dist_diff
    else
      return self.pushes <=> other.pushes
    end
  end
end

scored = nil
root = Map.parse(map)
to_visit = [root]
until to_visit.empty?
  state = to_visit.pop
  next if state.visited?
  if state.wins? && (scored.nil? || scored.pushes > state.pushes)
    scored = state
  end
  state.visit!
  to_visit += state.next_maps
  to_visit.reject! {|x| x.visited? || (scored && scored.pushes <= x.pushes) }
  to_visit.sort!
  to_visit.reverse!
end

puts scored ? scored.pushes : 'X'
exit(0) unless scored
steps = [scored]
curr = scored
while curr = curr.prev
  steps << curr
end
puts "\nDetails of the path:"
steps.reverse.each_with_index do |step, idx|
  puts "Step ##{idx} (history: #{step.history}, pushes so far: #{step.pushes})"
  puts step
  puts
end

Edit: I though of ways to possibly greatly improve the performance of this in non-obvious situations (where it currently sucks green eggs) by dropping simple movement evaluation (e.g. only care about when indy pushes rocks and/or gets to the treasure). I'll probably update the code later, once I've had time to implement.

C++ 14 out of 16
The algorithm is inefficient and memory hungry.
Additionally I couldn't afford the time to tidy it up, but I will when I have more time ;)
An interesting point is that my algorithm fails at the same test maps as the questioner's. On my ancient notebook the process starts swapping for the T4 and T6 maps. Map 3 takes quite long, but is solved in time. All others are solved nearly instant.
So I'll have to figure out how to solve T4 and T6 and try the algorithm on a machine with more memory. Eventually I can solve T4 and T6 there.
I'll keep the post updated...
Below is the result. (X: wrong, O: right, ?: takes at least 10s, halted)
Map#         : 0 1 2 3 4 5 12 15 19 T1 T2 T3 T4 T5 T6 T7
C++  (foobar): O O O O O O  O  O  O  O  O  O  ?  O  ?  O
Ruby (Romain): X O O ? O O  O  X  ?  ?  O  ?  ?  ?  ?  ?
Java (Romain): O O X O X X  O  O  ?  ?  O  O  O  X  O  O

As the source code is quite long and not really nice to read...
Basically it just looks for all rocks that can be reached by Indiana Jones.
For the rocks that can be reached, it stores the information into which directions it can be moved. So a list of possible moves for the current map is created. For each of these possible moves a copy of the map is created and the move applied. For the newly created maps, the algorithm will check again which moves can be applied... This is done until either no further moves are possible or a way to the treasure chest is found. As the algorithm first tries all moves that would only take one movement to reach the chest, then all that would take two, and so on... the first way found is also automatically the shortest.
To prevent loops, the algorithm remembers for every map what moves could be applied. If another map is created that results in a list of moves that were already found before, then they're silently dropped, as they're already being processed. Unfortunately it's not possible to execute every move only once, as there could be maps that require a rock to be moved over the same field several times. Otherwise I could save a lot of memory.
Additionally to solve maps like map 3 in time, the algorithm ignores all rocks that can be walked around... So on map 3 the rock in the middle of nowhere will be moved around, but only until there are no more walls around it.
The code can be compiled with g++ --std=c++0x with g++ version 4.4.3 or newer.
#include <vector>
#include <iostream>
#include <iterator>
#include <sstream>
#include <unordered_set>
#include <utility>

enum class dir : char {
    up, down, left, right
};

enum class field : char {
    floor, wall, indiana, treasure, rock, border, visited
};

class pos {
    private:
        int x, y;
        field f_type;

    public:
        pos() : x{-1}, y{-1}, f_type{field::border} {}
        pos(int x, int y, field f_type) : x{x}, y{y}, f_type{f_type} {}

        const field& get() {
            return f_type;
        }

        friend class map;
        friend class move;

        bool operator==(const pos& other) const {
            return x == other.x && y == other.y && f_type == other.f_type;
        }
};

class move {
    private:
        pos position;
        dir direction;

    public:
        move(pos& position, dir&& direction) : position(position), direction(direction) {}

        bool operator==(const move& other) const {
            return position == other.position && direction == other.direction;
        }

        int int_value() const {
            return static_cast<char>(direction) + position.x + position.y + static_cast<char>(position.f_type);
        }

        std::string str() const;

        friend class map;
};

std::string move::str() const {
    std::string direction_str;
    switch(direction) {
        case dir::up: direction_str = "up"; break;
        case dir::down: direction_str = "down"; break;
        case dir::left: direction_str = "left"; break;
        case dir::right: direction_str = "right"; break;
    }
    std::ostringstream oss{};
    oss << "move x" << position.x << " y" << position.y << " " << direction_str;
    return oss.str();
}

std::ostream& operator<<(std::ostream& os, const move& move_object) {
    return os << move_object.str();
}

namespace std {
    template<> struct hash< ::move> {
        size_t operator()(const ::move& o) const {
            return hash<int>()(o.int_value());
        }
    };
}

class constellation {
    private:
        const std::unordered_set<move> moves;

    public:
        constellation(const std::unordered_set<move>& moves) : moves(moves) {}

        bool operator==(const constellation& other) const {
            if (moves.size() != other.moves.size()) return false;
            for (auto i = moves.begin(); i != moves.end(); ++i) {
                if (!other.moves.count(*i)) return false;
            }
            return true;
        }

        int int_value() const {
            int v = 0;
            for (auto i = moves.begin(); i != moves.end(); ++i) {
                v += i->int_value();
            }
            return v;
        }
};

namespace std {
    template<> struct hash< ::constellation> {
        size_t operator()(const ::constellation& o) const {
            return hash<int>()(o.int_value());
        }
    };
}

class map {

    private:
        pos* previous;
        pos start, border;
        std::vector< std::vector<pos> > rep;
        void init(const std::string&);

    public:
        map(std::istream& input) : previous{} {
            init(static_cast<std::stringstream const&>(std::stringstream() << input.rdbuf()).str());
        }

        map& move(const move& m) {
            pos source = m.position;
            pos& target = get(source, m.direction);
            target.f_type = source.f_type;
            source.f_type = field::indiana;
            rep[start.y][start.x].f_type = field::floor;
            start = source;
            rep[start.y][start.x].f_type = field::indiana;
            return *this;
        }

        std::string str() const;

        pos& get() { return start; }

        pos& get(pos& position, const dir& direction) {
            int tx = position.x, ty = position.y;
            switch(direction) {
                case dir::up: --ty; break;
                case dir::down: ++ty; break;
                case dir::left: --tx; break;
                case dir::right: ++tx; break;
            }
            previous = &position;
            if (tx >= 0 && ty >= 0 && static_cast<int>(rep.size()) > ty && static_cast<int>(rep[ty].size()) > tx) {
                pos& tmp = rep[ty][tx];
                return tmp;
            }
            border.x = tx;
            border.y = ty;
            return border;
        }

        pos& prev() {
            return *previous;
        }

        void find_moves(std::unordered_set< ::move>& moves, bool& finished) {
            map copy = *this;
            auto& rep = copy.rep;
            bool changed = true;

            while (changed) {
                changed = false;
                for (auto row = rep.begin(); row != rep.end(); ++row) {
                    for (auto col = row->begin(); col != row->end(); ++col) {
                        // check if the field is of interest
                        if (col->f_type == field::floor || col->f_type == field::treasure || col->f_type == field::rock) {
                            // get neighbours
                            pos& up = copy.get(*col, dir::up);
                            pos& down = copy.get(*col, dir::down);
                            pos& left = copy.get(*col, dir::left);
                            pos& right = copy.get(*col, dir::right);
                            // ignore uninteresting rocks
                            if (col->f_type == field::rock && (up.f_type == field::floor || up.f_type == field::indiana || up.f_type == field::visited) && (down.f_type == field::floor || down.f_type == field::indiana || down.f_type == field::visited) && (left.f_type == field::floor || left.f_type == field::indiana || left.f_type == field::visited) && (right.f_type == field::floor || right.f_type == field::indiana || right.f_type == field::visited)) {
                                pos& upper_left = copy.get(up, dir::left);
                                pos& lower_left = copy.get(down, dir::left);
                                pos& upper_right = copy.get(up, dir::right);
                                pos& lower_right = copy.get(down, dir::right);
                                if ((upper_left.f_type == field::floor || upper_left.f_type == field::indiana || upper_left.f_type == field::visited) && (lower_left.f_type == field::floor || lower_left.f_type == field::indiana || lower_left.f_type == field::visited) && (upper_right.f_type == field::floor || upper_right.f_type == field::indiana || upper_right.f_type == field::visited) && (lower_right.f_type == field::floor || lower_right.f_type == field::indiana || lower_right.f_type == field::visited)) {
                                    continue;
                                }
                            }
                            // check if the field can be reached
                            if (up.f_type == field::visited || up.f_type == field::indiana) {
                                if (col->f_type == field::rock && (down.f_type == field::visited || down.f_type == field::floor || down.f_type == field::indiana)) {
                                    auto insertion = moves.insert( ::move(*col, dir::down));
                                    if (insertion.second) {
                                        changed = true;
                                    }
                                }
                                else if (col->f_type == field::floor) {
                                    changed = true;
                                    col->f_type = field::visited;
                                }
                                else if (col->f_type == field::treasure) {
                                    finished = true;
                                    return;
                                }
                            }
                            if (down.f_type == field::visited || down.f_type == field::indiana) {
                                if (col->f_type == field::rock && (up.f_type == field::visited || up.f_type == field::floor || up.f_type == field::indiana)) {
                                    auto insertion = moves.insert( ::move(*col, dir::up));
                                    if (insertion.second) {
                                        changed = true;
                                    }
                                }
                                else if (col->f_type == field::floor) {
                                    changed = true;
                                    col->f_type = field::visited;
                                }
                                else if (col->f_type == field::treasure) {
                                    finished = true;
                                    return;
                                }
                            }
                            if (left.f_type == field::visited || left.f_type == field::indiana) {
                                if (col->f_type == field::rock && (right.f_type == field::visited || right.f_type == field::floor || right.f_type == field::indiana)) {
                                    auto insertion = moves.insert( ::move(*col, dir::right));
                                    if (insertion.second) {
                                        changed = true;
                                    }
                                }
                                else if (col->f_type == field::floor) {
                                    changed = true;
                                    col->f_type = field::visited;
                                }
                                else if (col->f_type == field::treasure) {
                                    finished = true;
                                    return;
                                }
                            }
                            if (right.f_type == field::visited || right.f_type == field::indiana) {
                                if (col->f_type == field::rock && (left.f_type == field::visited || left.f_type == field::floor || left.f_type == field::indiana)) {
                                    auto insertion = moves.insert( ::move(*col, dir::left));
                                    if (insertion.second) {
                                        changed = true;
                                    }
                                }
                                else if (col->f_type == field::floor) {
                                    changed = true;
                                    col->f_type = field::visited;
                                }
                                else if (col->f_type == field::treasure) {
                                    finished = true;
                                    return;
                                }
                            }
                        }
                    }
                }
            }
        }

};

void map::init(const std::string& in) {
    bool first = true;

    for(auto i = in.begin(); i != in.end(); ++i) {
        if (*i == '\n') {
           first = false;
            rep.push_back({});
            continue;
        }
        else if (first) continue;

        field tmp(static_cast<field>(*i - '0'));
        pos current(rep.back().size(), rep.size() - 1, tmp);
        switch(tmp) {
            case field::indiana:
                start = current;
            case field::floor:
            case field::wall:
            case field::treasure:
            case field::rock:
                rep.back().push_back(current);
                break;
            default: std::cerr << "Invalid field value '" << (char) (static_cast<char>(tmp) + 48) << '\'' << std::endl;
        }
    }
}

std::string map::str() const {
    std::string t{};
    for (auto row = rep.begin(); row != rep.end(); ++row) {
        for (auto col = row->begin(); col != row->end(); ++col) {
            t += static_cast<char>(col->f_type) + '0';
        }
        t += '\n';
    }
    return t;
}

std::ostream& operator<<(std::ostream& os, const map& map_object) {
    return os << map_object.str();
}

int solve(map&& data) {
    int moves_taken = -1;
    bool finished = false;
    std::vector<map> current_maps{data}, next_maps;
    std::unordered_set<constellation> known_constellations;

    while (!finished && !current_maps.empty()) {
        for (auto i = current_maps.begin(); i != current_maps.end(); ++i) {
            std::unordered_set<move> moves;
            i->find_moves(moves, finished);
            auto result = known_constellations.insert(constellation(moves));
            if (!result.second) {
                continue; // this map constellation was already seen. prevent loops...
            }

            if (finished) break;
            for (auto m = moves.begin(); m != moves.end(); ++m) {
                map map_copy = *i;
                map_copy.move(*m);
                next_maps.push_back(map_copy);
            }

        }
        ++moves_taken;
        current_maps = std::move(next_maps);
    }
    if (!finished && current_maps.empty()) return -1;
    return moves_taken;
}

int main(int argc, char* argv[]) {
    map data{std::cin};

    int moves_taken = solve(std::move(data));
    if (moves_taken == -1) std::cout << "X" << std::endl;
    else std::cout << moves_taken << std::endl;

    return 0;
}

Edit: The program takes its input from stdin and ignores the first line containing the size of the map. It checks if only allowed characters in the map are used, but doesn't verify that there's only one Indiana Jones and one treasure chest. So it's possible to place more than one and the least moves required to reach one of the chests is printed to stdout. Any invalid characters in the map are skipped and the program will try to calculate the least amount of moves for the resulting map.
The calculation will start when stdin is closed (on my system ctrl + d).

Nice resurrection :). It's always fun to see a clever heuristic.

I'm kind of sad about my upvote.  It pushed your reputation 10 higher than a perfect 1000


text:
Write a better BCS computer ranking
Input
A CSV file, read from standard input, containing the 2011 college football scores with the 4 columns: Winner, Winner Score, Loser, Loser Score.  For example,
Cincinnati,35,Connecticut,27
Pittsburgh,33,Syracuse,20
Baylor,48,Texas,24

This file was generated by a script I have that screen-scrapes rivals.yahoo.com.  Teams that played fewer than 3 games were omitted.
Output
Print to standard output a newline-separated ranking of teams, ordered from "best" to "worst".
It is permitted to output a "truncated" ranking (e.g., Top 25 or Top 50), but this is discouraged.
Scoring
The ranking produced by your program will be scored on its ability to predict the winners of bowl games.
A victory for Team A over Team B is considered "predicted" by your ranking if either:

You ranked Team A higher than (i.e., earlier in the output than) Team B.
You ranked (i.e., listed anywhere in the output) Team A but not Team B.

You get 1 point for each bowl game "predicted" by your ranking.
Highest score gets the accepted answer.  In case of a tie, the earliest submission wins.
Rules

Deadline for entries is Friday, December 16, at 17:00 CST (23:00 UTC).
You may use the language of your choice.
You may use third-party open-source math libraries such as SciPy.
You may submit multiple entries.
The output must be a pure function of the input.  (So if you need an arbitrary tiebreaker in your ranking, don't use rand(), use alphabetical order.)

Scores: It's a tie!
(Based on results from rivals.yahoo.com)
dan04: 11 points

Auburn > Virginia
Baylor > Washington
Boise St. > Arizona St.
Oklahoma > Iowa
Oklahoma St. > Stanford
Oregon > Wisconsin
South Carolina > Nebraska
Southern Miss > Nevada
TCU > Louisiana Tech
Texas > California
Texas A&M > Northwestern

AShelly: 11 points

Arkansas > Kansas St.
Baylor > Washington
Boise St. > Arizona St.
Cincinnati > Vanderbilt
Houston > Penn St.
Michigan > Virginia Tech
Oklahoma St. > Stanford
Rutgers > Iowa St.
South Carolina > Nebraska
Southern Miss > Nevada
TCU > Louisiana Tech

Anyone who has messed around with this problem in the past will tell you that it is harder than it looks. I may still have a code around here somewhere...it'll need work to deal with the input format, but that should be easy.

Care to post the data somewhere, for testing, or the scraper code?

Also, there's a difference between BCS ranking and bowl results prediction, so the title of this question may need to be revised.

"Top 25" seems ill-defined - at what point in time, by what measure?  There are also more than 25 bowl games in the list referenced.  So, it seems important to predict winners for all of the games.

@iterator - (1) Data is now posted.  See link above.  (2) By your measure.  But you should rank all 118 teams if you can.

I see no winner chosen yet. Would you select one or push the deadline?

@dan04, are you planing on computing the results?  I believe all the games are completed.

Sorry for the delay.  I was waiting for the games to finish on January 9, and then I just got distracted.  Will post the results tonight.

I'll give it a shot.   Here's some ugly Ruby that bases its ranking on how well each team scored compared to the opponent's average points against.  It weights scores based on the opponent's rank in the list, and iterates until it is stable.
class Team
  attr_accessor :wins,:loss,:for,:agn,:rank,:old_rank
  attr_reader :beat,:fell, :name
  def initialize nm
    @name = nm
    @wins=0
    @loss=0
    @for = 0
    @agn = 0
    @beat = []
    @fell  = []
  end
  def win pts,opp,opts
    @wins+=1
    @for+=pts
    @agn+=opts
    @beat << [opp,pts,opts]
  end
  def lose pts,opp,opts
    @loss+=1
    @for+=pts
    @agn+=opts
    @fell << [opp,pts,opts]
  end
  def avgPtsFor
    @for.to_f/(@wins+@loss)
  end
  def avgPtsAgn
    @agn.to_f/(@wins+@loss)
  end
  def score teams
    #most points for scoring above opponents average, scaled by opponent's rank.
    x = @beat.inject(0){|sum,game|opp = teams[game[0]]
      sum+(game[1]/opp.avgPtsAgn*(1-(opp.rank/teams.size)))/@beat.size
      }
    y = @fell.inject(0){|sum,game|opp = teams[game[0]];
      sum+(game[1]/opp.avgPtsAgn*(opp.rank/teams.size))/@fell.size
      }
    (x+y)*(@wins/@loss.to_f)++(@rank/teams.size)/8
  end

end

#read the file
teams = Hash.new
ARGF.each_line{|l|
  result = l.split(',')
  team = teams[result[0]]||Team.new(result[0])
  team.win(result[1].to_i,result[2],result[3].to_i)
  teams[result[0]]=team
  team = teams[result[2]]||Team.new(result[2])
  team.lose(result[3].to_i,result[0],result[1].to_i)
  teams[result[2]]=team
}
#initial ranking by w/l,pts for, pts against
rankings = teams.map{|n,t|t}.sort_by{|t|[t.wins.to_f/t.loss,t.for,t.agn]}
rankings.each_with_index{|a,i|a.rank = (i+1.0)}

#loop
stable = false
loops = 0
while !stable and loops < 1000 do
  stable = true
  n = rankings.size.to_f
  rankings = rankings.sort_by{|t|
  t.score(teams)
  }
  rankings = rankings.each_with_index{|t,i|
    t.old_rank = t.rank
    t.rank = (i+1.0)
    stable = false if (t.rank != t.old_rank)
  }
  loops+=1
end

i=0
puts rankings.reverse.map{|t|"#{i+=1}: "+t.name}

Here's the output:
1: Oklahoma St.
2: LSU
3: Boise St.
4: Houston
5: Stanford
6: Oregon
7: Alabama
8: Arkansas
9: Wisconsin
10: TCU
11: Michigan
12: Georgia
13: South Carolina
14: Arkansas St.
15: Southern Miss
16: Michigan St.
17: West Virginia
18: Baylor
19: USC
20: Georgia Tech
21: Clemson
22: Tulsa
23: BYU
24: Oklahoma
25: Kansas St.
26: Nebraska
27: Virginia Tech
28: Penn St.
29: Notre Dame
30: Cincinnati
31: Northern Illinois
32: LA Lafayette
33: San Diego St.
34: Toledo
35: Florida Intl.
36: Texas A&M
37: Louisiana Tech
38: Ohio
39: Florida St.
40: North Carolina
41: Nevada
42: Iowa
43: Temple
44: Washington
45: West. Kentucky
46: Rutgers
47: Air Force
48: Auburn
49: Wyoming
50: California
51: Texas
52: Ohio St.
53: W. Michigan
54: Virginia
55: Utah St.
56: Florida
57: Missouri
58: Northwestern
59: SMU
60: Vanderbilt
61: Mississippi St.
62: Pittsburgh
63: Ball St.
64: Louisville
65: Purdue
66: East Carolina
67: UCLA
68: Wake Forest
69: Marshall
70: North Texas
71: N.C. State
72: Arizona St.
73: Utah
74: South Florida
75: Hawaii
76: San Jose St.
77: Texas Tech
78: Illinois
79: Kent St.
80: UTEP
81: UCF
82: Tennessee
83: East. Michigan
84: Connecticut
85: Navy
86: Duke
87: Rice
88: New Mexico St.
89: LA Monroe
90: Washington St.
91: Bowling Green
92: Kentucky
93: Syracuse
94: Arizona
95: Fresno St.
96: Troy
97: Oregon St.
98: Army
99: Colorado
100: Iowa St.
101: UNLV
102: UAB
103: Buffalo
104: Middle Tenn. St.
105: Minnesota
106: Boston Coll.
107: Cent. Michigan
108: Colorado St.
109: Mississippi
110: Tulane
111: Florida Atlantic
112: Memphis
113: Idaho
114: Kansas
115: New Mexico
116: Indiana
117: Maryland
118: Akron

Here's an example program.  It assigns each team a rating equal to the least-squares solution of winner_rating - loser_rating = 1 across all games:
import sys
import csv
from scipy import linalg

def read_csv(input_file):
    """Return a list of (winner, loser) tuples from the CSV file."""
    return [(row[0], row[2]) for row in csv.reader(input_file)]

def lstsq_ratings(data):
    """
    data = a list of (team1, team2, margin) tuples.
    Returns a dictionary of {team: rating}
    """
    # Extract the team names from the data
    teams = set()
    for winner, loser in data:
        teams.add(winner)
        teams.add(loser)
    teams = sorted(teams)
    team_indices = dict(zip(teams, xrange(len(teams))))
    # Construct the matrix equation for the teams
    num_teams = len(teams)
    lhs = []
    rhs = []
    for winner, loser in data:
        rhs.append(1)
        lhs_row = [0] * num_teams
        lhs_row[team_indices[winner]] = 1
        lhs_row[team_indices[loser]] = -1
        lhs.append(lhs_row)
    # Solve equation and return results
    ratings = linalg.lstsq(lhs, rhs)[0]
    return dict((team, rating) for team, rating in zip(teams, ratings))

if __name__ == '__main__':
    ratings = lstsq_ratings(read_csv(sys.stdin))
    output = sorted(ratings.items(), key=lambda x: (-x[1], x[0].lower()))
    for team, rating in output:
        print(team)

The output is:
Oklahoma St.
LSU
Alabama
Oklahoma
Stanford
Oregon
Baylor
Arkansas
South Carolina
Kansas St.
USC
Georgia
Wisconsin
Virginia Tech
Boise St.
Houston
Michigan
Nebraska
Texas
Texas A&M
Michigan St.
Missouri
Clemson
Penn St.
Auburn
TCU
Notre Dame
West Virginia
Southern Miss
Georgia Tech
Arkansas St.
North Carolina
Iowa
Tulsa
Washington
Cincinnati
California
Mississippi St.
Florida
Rutgers
Utah
BYU
UCLA
Florida St.
LA Lafayette
Northern Illinois
Ohio St.
Louisville
Texas Tech
San Diego St.
Vanderbilt
Arizona St.
Iowa St.
Tennessee
West. Kentucky
Virginia
Louisiana Tech
Illinois
Wyoming
Kentucky
Purdue
Toledo
Marshall
Pittsburgh
Arizona
N.C. State
Florida Intl.
Wake Forest
SMU
Northwestern
Ohio
Nevada
South Florida
Air Force
Utah St.
Oregon St.
Kansas
Syracuse
W. Michigan
North Texas
Temple
East Carolina
Ball St.
Washington St.
Kent St.
Colorado
Minnesota
Connecticut
Rice
Navy
Duke
East. Michigan
San Jose St.
Mississippi
UTEP
UCF
Hawaii
LA Monroe
Fresno St.
Bowling Green
New Mexico St.
Boston Coll.
Troy
UNLV
Army
UAB
Colorado St.
Cent. Michigan
Indiana
New Mexico
Middle Tenn. St.
Buffalo
Florida Atlantic
Maryland
Idaho
Memphis
Tulane
Akron

source: Stack Exchange

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

sort: votes


text:
position of the only 1 in a number in binary format
Every number of the form 2i (where i is a non-negative integer) has a single 1 in its binary representation. Given such a number, output the 1-based position of the 1.
Examples:
DECIMAL   BINARY    POSITION
--------------------------
1            0001      1
2            0010      2
4            0100      3
8            1000      4

N         0...1...0     ?

Related: an SO C++ question, but that doesn't have the simplifying factor that only a single bit is set.

Is it expected that number fits into numeric format? Or we should process decimal string?

This is tagged [tag:fastest-code] but it's not at all clear how the speed of answers is going to be measured.

Seems that almost all answers assume this is [tag:code-golf].

@Adám: Look at how old the question is.  [fastest-code] was probably really new then, and probably people missed the tag.

@MartinEnder: I think latency in clock cycles is an pretty obvious metric here, and probably the most likely to be relevant.  Throughput would be the other main possibility.  The big problem here is that there can't be an overall winner since no single implementation strategy is optimal across all architectures.  Even within x86, there are big differences across microarchitectures.  (e.g. AMD Bulldozer vs. Intel Haswell vs. Prescott).  My micro-optimization answer would fit a lot better on SO than here on ppcg, so that's probably a sign that this question is off-topic for this site.

@PeterCordes Normally (these days, anyway), [tag:fastest-code] challenges are scored by being measured on a single machine (the OP's usually) or they are held on a very specific architecture to ensure comparability. Alternatively, the OP could provide a benchmark script to assess the participant's machine's speed which can be used to scale a timing they obtain themselves, but that requires a certain level of trust (and doesn't account for architecture-specific optimisations).

@MartinEnder: Scaling timing results according to some other benchmark is not a good enough way to normalize for most uses.  Different memory / cache / CPU speed ratios are another error source.  I actually answered an SO question about that fairly recently.  Thanks for the GOLF architecture link.  Interesting.  I suggested using Knuth's MMIX (for which compilers and cycle-accurate simulators already exist) in my SO answer about creating a platform for speed comparisons.

Stolen wholesale from Bit twiddling hacks:
uint8_t f(uint32_t v)
{
    static const uint8_t MultiplyDeBruijnBitPosition2[32] = {
          0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
            31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
    };
    return MultiplyDeBruijnBitPosition2[(uint32_t)(v * 0x077CB531U) >> 27];
}

+1 Excellent. Given that this is a [tag:fastest-code] challenge, I'd give this a +2 if I could.

@llmariKaronen I'll help you.

R, 14 or 22 characters
p=function(x)log2(x)+1

It remains fully vectorized, so not only can you do it for one number you can do it for any vector of numbers:
> n <- 2^seq(0,10)
> n
 [1]    1    2    4    8   16   32   64  128  256  512 1024
> p(n)
 [1]    1    2    3    4    5    6    7    8    9   10   11

Doesn't seem terribly slow either:
Unit: microseconds
   expr   min    lq median    uq    max
1 p(16) 4.749 4.749   4.75 5.029 33.524

As an expression, it can be cut down to 14 characters: log2(scan())+1
> log2(scan())+1
1: 1
2: 2
3: 4
4: 8
5: 16
6:
Read 5 items
[1] 1 2 3 4 5

GNU C, POSIX C, or MSVC: usually 2 instructions with low latency (see below for perf)
You can do the same thing even more portably with Rust, where foo.trailing_zeros() is a language built-in for all integer primitive types.
Performance varies a lot with hardware, but this inlines to whatever the hardware is capable of.  This works on any architecture that has a GNU or POSIX compiler.
Most CPU architectures can count leading zeros or trailing zeros in one instruction.  (See Wikipedia's Find First Set article).  We can use either, since there's only one set bit.  Knowing that our input is always non-zero also simplifies things.  (Especially for x86 where BSF and BSR leave their output undefined when the input is zero).
The trick is to write something that will compile to that for the target architecture.  Since pure C unfortunately doesn't provide a portable way to express this, we use macros to detect language extensions.
#define _GNU_SOURCE  // request that string.h define ffsl
#include <stdint.h>
#include <stdlib.h>

#ifdef __unix__
// https://stackoverflow.com/questions/11350878/how-can-i-determine-if-the-operating-system-is-posix-in-c
#include <unistd.h>  // for _POSIX_VERSION
#endif

#ifdef _POSIX_VERSION
#include <strings.h>
#include <string.h>  // for GNU-extension ffsl in case we want that
int bit_position_posix(uint32_t v) {
#ifdef __GNUC__
  // tell the compiler about the assumption that v!=0
  // unfortunately doesn't help gcc or clang make better ffs() code :(  And ICC makes worse code
  if (v == 0)
    __builtin_unreachable();
#endif

  return ffs(v);
}
#endif

#ifdef __GNUC__
int bit_position_gnu(uint32_t v) {
  // v is guaranteed to be non-zero, so we can use a function that's undefined in that case

  // we can count from the front or back, since there's only one bit set
  // but the compiler doesn't know this so we use macros to select a method that doesn't e.g. require an RBIT instruction on ARM

  // TODO: tweak this for more architectures
#if (defined(__i386__) || defined(__x86_64__))
  return __builtin_ctz(v) + 1;
#else
  return 32 - __builtin_clz(v) + 1;
#endif
}
#endif

#ifdef _MSC_VER
// https://msdn.microsoft.com/en-us/library/wfd9z0bb.aspx
#include <intrin.h>
int bit_position_msvc(uint32_t v) {
  unsigned long idx;
  int nonzero = _BitScanForward(&idx, v);
  return idx + 1;
}
#endif

static inline
  int bit_position(uint32_t v)
{
#ifdef __GNUC__
  return bit_position_gnu(v);
#elif defined(_MSC_VER)
  return bit_position_msvc(v);
#elif defined(_POSIX_VERSION)
  return bit_position_posix(v);
#else
  #error no good bitscan detected for this platform
#endif
}

sample asm output from the Godbolt compiler explorer:
# gcc6.2 for x86-64 -O3
bit_position_gnu:
    xor     eax, eax    # break BSF/TZCNT's false dependency on destination
    rep bsf eax, edi    # 3 cycle latency   # runs as BSF on CPUs that don't support TZCNT
    add     eax, 1      # 1 cycle latency
    ret

#MSVC: same thing but without the xor-zeroing
# yes, beta Godbolt has cl.exe installed
bit_position_msvc PROC
    bsf      eax, ecx
    inc      eax
    ret      0
bit_position_msvc ENDP

Using count leading vs. count trailing zeros shouldn't hurt the code on x86, but it does.  With count-leading, gcc doesn't fold the 33-... part into the 32-bsr() that it does as part of implementing the builtin (since BSR produces the bit-index of the high bit, rather than counting leading zeros).  See comments on this question and my answer there for more discussion about using reg_width - __builtin_clzl vs. using __builtin_ctz on power-of-2 integer.

Perf analysis: (see Agner Fog's instruction tables and microarch pdf, and the SO x86 tag wiki).
ADD is always 1c latency on all x86 CPUs worth mentioning.  On Intel Core2, BSF is 2c latency with one per clock throughput.  On Nehalem and later (up to Skylake at least), it's 3 cycle latency.
BSF is slow on Atom (16c) and Silvermont (10c), and on P4 Prescott (16c).  Some of the pure-C sequences may be faster on those CPUs, since gcc still uses BSF even with -march=atom (which implies -mtune=atom).
BSF is fairly slow on all AMD CPUs, but TZCNT is fast (2c latency).  This is why gcc uses rep bsf (which will decode as TZCNT on CPUs which support it, but as just plain BSF on CPUs which don't, ignoring prefixes which don't apply).  So on AMD Piledriver and later, this sequence has 3c total latency.  But on AMD Bulldozer (which only has LZCNT, not TZCNT), we should have used 32 - lzcnt(v) + 1 (but BSR vs. LZCNT produce different results even for non-zero inputs, so that binary would only be usable on CPUs that support LZCNT).
This is not limited to x86, either:
bit_position_gnu:  # ARM gcc5.4 -O3 -mcpu=cortex-a53
    clz     r0, r0
    rsb     r0, r0, #33
    bx      lr

bit_position_gnu:  # ARM64 gcc5.4 -O3
    mov     w1, 33
    clz     w0, w0
    sub     w0, w1, w0
    ret

Performance: 2 cycle total latency from clz and sub.  This implies CLZ is always single-cycle on CPUs that support it (ARMv5T and later).  I also found info for ARM9E-S specifically that clz is single cycle, in my first google hit for arm clz cycles.
Reverse-subtract with an immediate, and regular sub with a register, are both almost certainly single-cycle latency.  (The mov of the constant in AArch64 is off the critical path, but for in-order CPUs is farther from being free.)

When an architecture doesn't have a bit-scan instruction that gcc knows how to use, it emits a call to a library function.  e.g.
# gcc5.4 for MIPS el with -O3.  Maybe there's an option to enable using clz if it's not baseline?
bit_position_gnu:
    lui     $28,%hi(__gnu_local_gp)
    addiu   $sp,$sp,-32
    addiu   $28,$28,%lo(__gnu_local_gp)
    sw      $31,28($sp)

    lw      $25,%call16(__clzsi2)($28)   ## function address of __clzsi2
    jalr        $25
    nop

    li      $3,33                 # 0x21
    lw      $31,28($sp)
    addiu   $sp,$sp,32
    j       $31
    subu    $2,$3,$2

I don't have any compilers that support POSIX but not GNU, so I was only able to see if / how the ffs() version compiled by making it non-inline.  It basically sucks because it accounts for the input=0 case even though we know that can't happen.

Related: an SO C++ question, but that doesn't have the simplifying factor that only a single bit is set.

Update: C++20 finally got around to providing #include <bit> for countr_zeros(T) to count trailing zeros like _mm_tzcnt or bsf.

J - 4 characters
2&^.

Test:
i=: 2^ i. 10
2&^. i
    0 1 2 3 4 5 6 7 8 9

Haskell 65 characters
import List
main=n<-readLn;print$findIndices(>n)[2^n|n<-[0..]]!!0

If you like to make performance tests, I guess you need really big values for 2^i, so I use BigInt:
@annotation.tailrec
def binexp (n: BigInt, sofar: Int = 0): BigInt =
  if (n < 2) 1 + sofar else binexp (n/2, sofar + 1)

The annotation is only to check, whether the compiler can perform a tailcall optimization.
I'm curios how you measure this challenge.

Python, 38 bytes
import math
print int(math.log(input(),2)+1)

Ruby 20
No input or output is necessary because N is given and the question asks for "code":
Math::log2(N).to_i+1

Math.log2 will spare you a character. (This is also the convention for calling class/module methods.) Although this is a fastest-code question, anyway. :)

K, 8
1+&|0b\:

.
k)(1+&|0b\:)'(2*)\[10;1]
1
2
3
4
5
6
7
8
9
10
11

Mathematica
I was surprised to find that Method #2 is much faster than Method #1.
Some data
 t = Table[2^k, {k, 0, 10^5}];

Method #1 Log base 2
 Log[2, t]; // AbsoluteTiming

{0.203758, Null}

Method 2: where is the 1 bit?
 Length[IntegerDigits[#, 2]] & t; // AbsoluteTiming

Break up the base 2 representation of the number into bits.
Find how many bits there are. (The 1 will always be farthest left.)

{0.100730, Null}

Python, 39 chars
f=lambda n:len(bin(n))-bin(n).find('1')

btw, this isn't code-golf...

JavaScript (ES6), 19 17 bytes
a=>Math.log2(a)+1

@MartinEnder, got it.

Actually, I just noticed that this isn't code golf at all.

n = n - 1; //n is the input no.
count = 0; //count of set bits
while(n = (n & (n-1)))
  count++;
return count + 1;

Did some characters get lost to markup? At present you have a while loop which either never executes or runs forever.

@PeterTaylor Looks good to me.  Language is unspecified, but assuming a rather classical = is assignment not equality test, coercing to boolean is testing for nonzero, then the while loop clears the rightmost bit at each iteration, and stops after it cleared the whole of it.

@JB, you're right, I was probably reading it as == without realising.

That's a popcount, not a trailing zero count.  It will return 1 for every test input in this problem.  And it's not fast in the general case with lots of bits set.  (It is a maybe-useful strategy for popcount on numbers that are often sparse, on machines without hardware popcnt instructions, especially low-performance machines with low penalty for branch mispredictions.  Otherwise with a fast multiplier, bithacks typically win: How to count the number of set bits in a 32-bit integer?)

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:
write a code the find n-th number of Gray Code list
Write a function that, given N >= 0, finds the Nth number in a standard Gray code.
Example input:
1
2
3
4

Example output:
1
3
2
6

Additional reference

This isn't much of a challenge, IMHO

Welcome to CodeGolf.SE! According to our FAQ, every challenge is expected to have a objective winning criteria. If you mean "shortest code" you should tag [code-golf] instead of [code-challenge], otherwise you need to be explicit.

According to your linked source, the first graycode is 0, not 1. How do you measure the speed? Based upon what did you accept Ilmari Karonen's answer?

Perl, 7 chars
$_^$_/2

This is an expression that returns the Gray code, given the input in $_.  You can use it on the command line with the -n switch:
perl -nE 'say $_^$_/2'

or use it in a map:
perl -E 'say for map $_^$_/2, 1 .. 10'
1
3
2
6
7
5
4
12
13
15

If you specifically want a function, I can do that too (in 20 chars):
sub g{$_[0]^$_[0]/2}

Edit: Since this challenge is now tagged fastest-code, let me include the equivalent C preprocessor macro, which should be about as fast as this can be done:
#define g(i) ((i)^(i)>>1)

A faster solution, if one exists, is likely to require hand-optimized assembly code.  Even then, a good optimizing C compiler may be hard to beat.  Looking at the disassembly of the benchmark code below, it seems gcc compiles this into three Intel assembly instructions:
 8048428:       89 c2                   mov    %eax,%edx
 804842a:       d1 ea                   shr    %edx
 804842c:       31 c2                   xor    %eax,%edx

This (a register copy, a shift and an XOR) is about what I'd expect any decent compiler to produce.  Of course, a good compiler might also be able to interleave the operations with surrounding code to improve pipelining.  (In the benchmark, the inner loop is tight enough that there's not much room for that.)
Testing just how fast this is can be a bit tricky, since we need to make sure the compiler won't just optimize away the Gray code calculation, or even the entire testing loop.  Here's a piece of code that sums up all unsigned 32-bit integers eight times over, either in Gray code order or, if NOGRAY is defined, in normal binary order.  Obviously, the output should be zero in either case, but at least gcc isn't smart enough to realize that.
#include <inttypes.h>
#include <stdio.h>

#ifdef NOGRAY
#  define g(i) (i)
#else
#  define g(i) ((i)^(i)>>1)
#endif

int main (void) {
    uint32_t k, i, n = 0;
    for (k = 0; k < 8; k++) {
        for (i = 1; i != 0; i++) n += g(i);
    }
    printf("%lu\n", (unsigned long) n);
    return 0;
}

On my 2.2GHz AMD Athlon 64 X2 CPU, compiled with gcc 4.4.3 with -O3 for i486-linux-gnu, running this code takes about 46.9 seconds, compared to about 31.2 second with NOGRAY defined.  That gives about 15.7 seconds for 235−8 Gray code calculations, which comes down to about 0.457 nanoseconds, or almost exactly one CPU cycle per calculation.
However, it's worth noting that that's the marginal cost of including the Gray code calculation in the loop.  The total time to execute the benchmark loop (which includes two adds and a conditional jump in addition to the three lines of assembly I showed above) is about 1.365 nanoseconds, or three cycles per iteration.

a) It's not a code golf. b) How fast is it?

a) It wasn't [tag:fastest-code] either when I posted this answer, that tag was added later. b) About as fast as it can be done in Perl, which is to say, probably many times slower than the equivalent code in C.

Yes, but it was never marked as code-golf, so your headline is a bit misleading. And I would like to measure the speed of your code to compare it to mine - but I would have to write the timing-code myself, or use a single invocation, measured by time. Still I had to write the main-method myself.

A good compiler could auto-vectorize that and produce 4 (SSE) or 8 (AVX2) Gray codes per iteration.

Golfscript, 4 chars
.2/^

@Taylor: please don't get me wrong, I'm not looking for  gray code for given N, but looking for N-th number in gray code list. (check the edit section)

@mohammadshamsi, it's in no way clear what difference you're intending to draw.

a) It's not a code golf. b) How fast is it?

@userunknown, a) See Ilmari's comment. b) As fast as possible in GolfScript. c) This was primarily a protest answer against a "code challenge" which can be done efficiently in 4 characters.

For protesting, I would suggest a) downvoting b) commenting and c) vote to close the question. 2.) See my comment to Ilmari's comment.

@userunknown, I also downvoted the question and upvoted the comment saying it wasn't a challenge. Protest answers aren't too uncommon here, but if you don't like them open a discussion on meta. I didn't vote to close, but most questions which get a downvote or two are then deleted by the poster: this one is very unusual.

scala:
It's not a code-golf!
However - if you like to golf:
def g(n:Int)=n^(n/2)

20 chars, according to my set of natural numbers.
But since speed matters, I produce a compilable form:
object Graycode extends App {

  def graycode (n: Int) = n^(n/2)

  def test (max: Int) {
    var i = 0
    val start = System.nanoTime ()
    while (i < max) {
      graycode (i)
      i += 1
    }
    val stop = System.nanoTime ()

    val diff = (stop-start)*1.0 / (1000*1000*1000)
    println ("Time: " + diff + "s\tn: " + max + "\tspeed: " + max * 1.0/diff + " /s")
  }

  override def main (args: Array[String]) = {
    var max = args(0).toInt
    val graycode = Graycode
    graycode.test (max)
  }
}

You can compare it against your solution this way:
scala Graycode 1000000000
Time: 23.882410496s n: 1000000000   speed: 4.1871820274066865E7 /s

About 4 million ints per second on my machine.
If I comment out the call to graycode, I get as speed: 7.683713972447292E8 /s, so it is not mainly the time used to loop, which is measured above.
Of course your absolute times will vary, but you may compare it to measurements of your code. Please provide measurement methods with your solutions too.


text:
Interpret your lang, but not yourself?
There are many challenges that say "interpret X", where X is a simple language. In my opinion, that is way too boring. To give all the procrastinating people on the internet something interesting to do, you can try to do this challenge:
Challenge
Choose a language $LANG. $LANG can be any turing complete programming language or a turing complete subset of a programming language. Beware that if you omit a feature of your language in $LANG for interpretation, you must not use it for your own program, too, since your submission must be written in $LANG, too.
Write a compiler / interpreter for $LANG written in $LANG. You may use all facilities (including eval and friends) of your language that are available to write this compiler. To make the task more challenging, there is one restriction: You program should be able to interpret / compile all valid programs of $LANG except your interpreter / compiler itself. If it occurs that the program to be interpreted / compiled is your interpreter or compiler itself (regardless of the filename), your program should do something completely unrelated to the functionality of an interpreter or compiler (such as barfing or printing Hello, world!).
To make this task even more complex, your program must not read its own source when compiling or interpreting.
Specifications

This task is code golf. The submission with the least characters that is correct wins. In case of a tie, the solution that was submitted first wins.
Your program / script should read the program to be interpreted from a file. You may hardcode its path and name. When the file is read, you may either compile the file to another file (That must be executable on your system) or run it directly. If $LANG lacks file-reading capabilities, you can choose another way to read in the code that fits $LANG. You may not choose $LANG as a subset of another language but with file-reading capabilites removed.
Usual code-golf rules apply. That is: your personal pet-language that you made up just to solve this challenge is forbidden, if the solution becomes trivial using it (Such as defining a single-char program that exactly implements the solution). Abuse of rules is encouraged.

Are we allowed to define a language for this, so long as it's turing complete?

@Cruncher Yes, you are. See the last bullet point of the specifications for more details.

Ruby, 63
b=$<.read
t="b=$<.read\nt=%p\nb!=t%%t&&eval(b)"
b!=t%t&&eval(b)

Answer accepted as long as there is no smaller solution.

Perl, 89 chars, no cheating
$_=q($_=q(Q);s/Q/$_/;($q=join"",<>)eq$_?die:eval$q);s/Q/$_/;($q=join"",<>)eq$_?die:eval$q

Note that this code is extremely picky about what counts as "itself".  In particular, it will not recognize itself if there are any trailing newlines or other extra whitespace in the input.  To test it, save it into a file named (for example) unquine.pl and do this:
$ perl unquine.pl unquine.pl
Died at unquine.pl line 1, <> line 1.

Remember, the unquine.pl file should be exactly 89 bytes long, no more, no less.  Running it with some other Perl script as input just executes the other script, as it should:
$ perl unquine.pl hello.pl
Hello, world!

As the name might suggest, the implementation is based on a quine — specifically, this one:
$_=q($_=q(Q);s/Q/$_/);s/Q/$_/

This code sets $_ equal to itself; the rest of the program (which, of course, must be duplicated inside $_) just compares $_ to the input, dies if they match and evaluates the input otherwise.

You can replace that &&/; pair with a ternary (one char off, doubled by quining). Great idea and implementation!

@JB: Good catch! Down to 89 chars now.

GolfScript, 30 chars
{`".~"+"#{$<.read}".@=!{~}*}.~

This program reads the contents of a file named on the command line and, if it does not exactly equal the code above, interprets it as GolfScript.  If the input is exactly equal to the code above, it will simply be printed unchanged (except for a newline appended to the end).
This is a fairly straightforward adaptation of this self-identifying program.  Specifically:

{ } is a code block literal in GolfScript.
.~, applied to a code block, duplicates the block and executes the copy.

Inside the code block:

` stringifies the copy of the code block.
".~"+ appends the characters .~ to it, yielding a string containing the source code of the program.
"#{$<.read}" is a documented hack that allow the execution of Ruby code within GolfScript.  In this case, it executes the Ruby statement $<.read (shamelessly stolen from Lowjacker's Ruby solution), which reads and returns the contents of any files specified on the command line.  This hack is needed because GolfScript itself provides no explicit file I/O capabilities.
.@ duplicates and shuffles the elements on top of the stack so that the stack contains two copies of the file contents followed by the source code of this program.
=! compares the top two items on the stack (i.e. the file contents and the source), returning 1 if they are different and 0 if they are the same.
{~}* evaluates the remaining copy of the file contents as GolfScript code, but only if the result of the comparison is 1.  (Technically, it executes the code block {~} as many times as given by the number on the stack, i.e. 0 or 1 times. Inside the block, ~ is the GolfScript eval operator.)

Ps. If reading the code to execute from stdin is allowed, this challenge can be solved in 21 characters without having to shell out to Ruby:
{`".~"+1$=!{""\~}*}.~

This program will read an input string from stdin and, if it does not match its own source, executes it (with an empty input).  Like the program above, input that does match the source is simply echoed back.

Looks nice, but it doesn't seem like you read input from a file.

Fixed, now it reads from a file (exactly) like Lowjacker's solution.

Python, 167 130 118 bytes
This is my first attempt at golfing, so here goes! It interprets any program except itself
Improved version:
i=open(raw_input()).read();q='i=open(raw_input()).read();q=%s;i==q%%repr(q)and a;exec(i)\n';i==q%repr(q)and a;exec(i)

If it gets itself then it barfs with:
Traceback (most recent call last):
  File "pygolf.py", line 1, in <module>
    i=open(raw_input()).read();q='i=open(raw_input()).read();q=%s;i==q%%repr(q)and a;exec(i)\n';i==q%repr(q)and a;exec(i)
NameError: name 'a' is not defined

I think this solution works pretty much the same way as Ilmari Karonen's, the basic idea is something like:
input = read_some_file()
if input == some_quine()
    barf()
interpret(input)

The quine I used was based on this one:
(lambda x: x + repr((x,)))('(lambda x: x + repr((x,)))',)

But I since realized a much shorter quine is:
q='q=%s;q%%repr(q)';q%repr(q)

And that can be even shorter if you allow the interactive python shell, in which case you can do:
'%s;_%%repr(_)';_%repr(_)

Since python doesn't have a short way to get command line args, I went with raw_input() (which is still pretty long, but not as long as
import sys;sys.argv[1]

Usage is:
echo "foobar.py" | python quinterpretter.py

or
python quinterpretter.py
<type filename and hit enter>

I found a shorter quine to use, but here is my old version (for posterity):
i=open(raw_input()).read();a if i==(lambda x,y:x+repr((x,y))+y)('i=open(raw_input()).read();a if i==(lambda x,y:x+repr((x,y))+y)', ' else 1;exec(i)\n') else 1;exec(i)

Replace the %s with %r and remove the repr. %r means raw and it's basically he same thing.

I can't exactly read from a file using Javascript (ok, I could, using the HTML5 FileReader thing, but that makes things a lot more complicated than I need). So, this is a function that accepts a Javascript program as a string and runs it.
This probably isn't as golfed as it could be, but here it is anyway:
Javascript, 252
function c(p){q='\"';s='\\';a="function c(p){q='\"';s='\\';a=%;a=a.slice(0,17)+s+a.slice(17,24)+a[23]+a.slice(24);a=q+a.replace('%',q+a+q)+q;alert(a);}";a=a.slice(0,17)+s+a.slice(17,24)+a[23]+a.slice(24);a=a.replace('%',q+a+q);alert(a);if(p!=a)eval(p)}

Let me know if anybody knows a better technique for forming a quine in Javascript.

I posted a 135-char JS solution below, based on your code and my Perl solution.  +1 for the inspiration!

Common Lisp, 59
#+~ #.(#:a)(defun L(p)(compile-file p))(push :~ *features*)

In a fresh Lisp REPL, compile your file (e.g. sbcl --load)
You now have a function L, which can compile Common Lisp files
However, if you call (L <your file>), an error is signaled while reading the file.

Why?
Because the first time, you pushed the :~ keyword into *features*. Now, your environment knows about the ~ feature, and the reader macro #+, upon evaluating the ~ feature expression,  will succeed and read the following form instead of skipping it as it did the first time. In your file, the following form is #.(#:a), which asks to evaluate (#:a) at read-time and use the resulting value as the code being read. But (#:a) calls the function associated with the uninterned symbol #:a. Since #:a is uninterned, it is a fresh symbol which is not bound to any function (i.e. not fboundp). Error.

Javascript ES6, 45 bytes
$=(_=prompt())=>eval(_==`$=${$};$()`?0:_);$()

Still competitive! (thx @Downgoat)

See http://chat.stackexchange.com/transcript/message/28761481#28761481.

Ah, I was going off of the standard's release. I didn't know there was a working implementation in 2011. You might want to include an explanation and a link to the commit in the answer text.

read p<p;read c<c;[ "$p" = "$c" ]||. ./c

45 characters of sh (POSIX shell). The code to be run must be in the file ./c.
The code for the interpreter itself must be in the file ./p, so I guess I kind of cheated, although the challenge doesn't seem to forbid it. Or would this disqualify my "language" from being a "turing-complete programming language"?
Using a tool that's normally an external executable, but might theoretically be built into the shell, the code can be shortened:
cmp -s p c||. ./c

That's 18 characters, and the -s bit is just to suppress a line that would otherwise always be printed for valid (non-self) programs.
And then you can always build a version of the shell language that does the above with more concise syntax.
And then you can always build a program that, when the input consists of a single '.' --or hell, the empty string-- evaluates the contents of another file as normal code, and call this a programming language. So the empty string would be your solution to the challenge, in the language you built.
In fact, here's an interpreter for such a language:
read code; if [ "$code" ]; then eval "$code"; else . ./othercode; fi

Using the language the above script interprets, the solution is the empty string. And the code location needn't be hardcoded anymore.
Problem?

The challenge does say that "your program must not read it's own source".

Darnit, wasted some time then. And I see it even says you mustn't use features that you will omit. This would go against the empty string feature. Then again, the interpreter must be omitting/changing functionality if the code for the compiler/interpreter itself causes different behaviour in the new language. In any case, i had fun writing fallacy.

@TaylanUB Well, you actually have to interpret all valid $lang programs except the interpreter itself.

@FUZxxl Yes, the "sh + empty string" language is otherwise equivalent to sh (if the code is not the empty string), and the empty string program written in it also interprets sh code (which must be put in ./othercode), and does nothing when the code is the empty string. I shouldn't have called the file ./othercode, it's misleading; it's just the code that the interpreter written in the empty string language will interpret.

JavaScript, 135 chars
function c(p){q='function c(p){q=%27Q%27;p!=unescape(q).replace(/Q/,q)?eval(p):alert()}';p!=unescape(q).replace(/Q/,q)?eval(p):alert()}

Peter Olson's JavaScript solution inspired me to try porting my Perl solution to JS.  Like his solution, this code defines a function c that accepts a string, and evals it if it's not equal to the code above.
It took me a while to figure out a good way to deal with the absence of balanced string delimiters in JavaScript, until I found what in hindsight is the obvious solution: unescape().
Conveniently, my code doesn't contain any backslashes or double quotes, so it can be safely stored in a double quoted strings.  This makes it easy to test:
e = "function c(p){q='function c(p){q=%27Q%27;p!=unescape(q).replace(/Q/,q)?eval(p):alert()}';p!=unescape(q).replace(/Q/,q)?eval(p):alert()}"
h = "alert('Hello, world!')"

eval(e)  // defines the function c()

c(h)     // evaluates h
c(e)     // does not evaluate e, alerts "undefined" instead

You could replace alert() with 0 to make it not do anything instead of alerting undefined and save 13 chars.

@PeterOlson: Yeah, but the task does say that "your program should do something completely unrelated" if it detects itself.  I interpret that as meaning that it should do something -- preferably something visible to the user, I'd presume.  Besides, I just like it better this way. :)  (Ps. Yay, it's snowing outside! Winter's finally here!)

@Ilmari Doing nothing is unrelated to interpreting Javascript IMHO.

You could go p=>... instead of function c(p)

Scheme, 48 or 51 characters
Scheme is a language with many different implementations. Despite implementations having to conform to the latest RnRS, the latest working standard (R6RS) has been unpopular due to its lack of minimalism. R7RS is soon to be released as a remedy, while splitting the language in 2. The first language being powerful and minimalistic and the second, a superset of the first intended to provide feature extensions for interoperability between implementations. Until then, we rely on SRFIs (Scheme Requests For Implementation), which provide (if implemented in the host implementation or manually (as is common in scheme)) a means to portably accomplish common tasks. All this to say that the first code snippet (51 characters), while remaining as portable as it can, relies on SRFI-22 (executing scheme scripts in UNIX) for access to command-line arguments:
(define(main x y)(case y(x => error)(else => load)))

or more readably:
(define (main current-file arg)
  (case arg
    [current-file => error]
    [else => load]))

The second (48 characters) is an file-less means to interpretation which cannot evaluate itself (in a null environment):
(define(e)(write(eval(read)null-environment))(e))

or more readably:
(define (interpret)
  (write (eval (read) null-environment))
  (interpret))

Your code does not work if you copy your interpreter.

Leave it to a scheme answer to contain nested parentheticals in its prose.

Groovy, 13 bytes
{Eval.me(it)}

This should interpret a subset of Groovy.
test cases:
p={Eval.me(it)}

p'''
    (0..37).each{println"1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU"[it..it+2]}
'''

p'''
    {Eval.me(it)}
'''

Unfortunately while it certainly barfs, it does so in a completely interpreter-like way, and it does it for quite a lot of input.

In which line do you read the program to be interpreted? Your code is interesting although it is not a valid submission for this task.

I assume the error is something like "recursion limit exceeded"?