text:
Programming Pac-Man
Programmin' Pac-Man
Setting
You play as Pac-Man.  You want to collect pellets, fruit, and power pellets before anybody else, all while avoiding ghosts.
Rules

Every valid Pac-Man will be in a single maze.  The player with the highest cumulative score after 10 games will win.
A game is over when all Pac-Men are dead, all pellets are gone, or 500 turns have passed
If a Pac-Man dies, he continues to play as a ghost
Eating a Power pellet will make you invincible for 10 turns, and allows you to eat Ghosts
Eating a Ghost will teleport the ghost to a random location
Ghosts cannot eat anything except Pac-Men, and do not get any points
Eating the following items as Pac-Man will get you the following points:

Pellet: 10
Power Pellet: 50
Fruit: 100
Ghost: 200

The Maze
If there are n Pac-Men, then a maze of size sqrt(n)*10 by sqrt(n)*10 will be generated using Prim's algorithm (due to it's low river factor), then braided completely, giving preference to already existing dead ends.  Furthermore, this braiding can be done across the edges, so that there are a few pathways from top to bottom and from left to right.
There will be:

2n Ghosts
4n Power Pellets
2n Fruit
n Pac-Men in spots where connected neighbors squares are empty.
All remaining empty spots will be filled with pellets

Hence, an initial map with 10 players will look something like this (Ghosts = green, Pellets = aqua, fruit = red, Pac-Man = yellow):

Input/Output
At the beginning of the game, You will be given a single line of characters, representing the walls in every square of the map. For each square, starting with the top left, moving right, and wrapping to the next line, you will be given a hex digit representing the wall situation:
0: No walls
1: North wall
2: East wall
3: East & North wall
4: South wall
5: South & North wall
6: South & East wall
7: Won't occur
8: West wall
9: West & North wall
A: West & East wall
B: Won't occur
C: West & South wall
D: Won't occur
E: Won't occur
F: Won't occur

Put simply, North=1, East=2, South=4, and West=8, added together.
Then, each turn, you will be given your current position and the items in your line of sight (if you are a Pac-Man.  All ghosts receive all squares from -5 to +5 from their relative position).  Your line of sight will be based on the direction you travelled last turn.  If you travelled north, you will be given all squares directly North, East, and West of you until a wall cuts off your view plus a single square Northwest and Northeast, if no wall cuts off your view.  If you choose not to move, you will be given the squares in all 8 directions.
For the visual, I means invisible, V means visible, P means Pac-Man(assuming Pac-Man is facing north):
|I I|V|I|
|I V|V V|
|V V P|I|
|I I|I|I|

Each square will be given by a coordinate, and then it's contents.  It's contents are represented by the following characters:

P: 1 or more Pac-Man
G: 1 or more Ghosts
o: Pellet
O: Power pellet
F: Piece of Fruit
X: Nothing

If there is a ghost and something else on a square, G will be returned.
Hence, if you were on square 23,70, you just moved north, the square above you is a dead end and contains a Power pellet, and you have walls on both sides of you, your input would be:
23,70X 22,70O

On your current square, it will show a G if you are a Ghost, a P if there is another Pac-Man on your square, otherwise an X
Then you will return the following items via STDOUT:
A single character representing a direction (North, East, South, West, or XStay).
Previous to passing in a direction, you may also pass in any coordinate as x,y, and the walls of that square will be passed back (as described above)
The program must be continuously running until Q is passed to it via STDIN.
Programs will be restarted for each game.
Accessing other information outside of what is passed to STDIN (including other Pac-Men's data or the data held by the host program) is not allowed.
Failure to return a move within 1000 ms will terminate the program (Running on my fairly decent Win8 machine).
You will be given 2 seconds to process the initial maze layout when it is given
Host will be written in Python, and code to test your bot is forthcoming.
Exceptional cases

If multiple Pac-Men end up on the same location, neither get the contents of the current square, unless exactly 1 of them is invincible, in which case, the invincible Pac-Man will receive the pellet.
A Pac-Man eaten by a Ghost will not be teleported somewhere else.  If two Pac-Men are on a square, and one is invincible, the ghost will be teleported.
Being teleported as a Ghost prevents you from moving for 1 turn.  When playing as a Ghost, you simply will have your turn skipped
Attempting to move through a wall will be interpreted as "Stay"
Each of the initial ghosts will receive one of the 4 personality traits, as described here, with the following modification:

The bugs described will not be duplicated
They will all be active from the beginning
They are vulnerable only to the player who ate the pellet
They will indefinitely switch from scatter to chase, each having a fixed number of turns before switch
Upon switching to chase, they will find the nearest Pac-Man to chase, and will chase that Pac-Man for the duration of their chase. (If there is a tie for closeness, the Pac-Man will be picked pseudorandomly)
Blinky won't speed up
Inky will pick the nearest ghost to base his calculations off of after switching to chase.
Clyde will find all players 8 squares away, then follow the furthest player.
All ghosts except Clyde won't target a player farther than 5 squares away

I will accept compilable code from a standard language or an .exe (with accompanying code).
Programming Tips
You may with my controller.  You need to put a /bots/your_bot_name/ folder in the same directory as the program.  Within the folder, you need to add a command.txt containing a command to execute your program (ex: python my_bot.py), and the your bot.
The controller code is on Github (Python code, requires Pygame if you want graphics.)  Tested on windows and linux
SCORES

ghostbuster: 72,840 points
pathy: 54,570 points
shortsighted: 50,820 points
avoidinteraction: 23,580 points
physicist: 18,330 points
randomwalk: 7,760 points
dumbpac: 4,880 points

+1. This is the first time I see the word "Pacmen"

#!/usr/bin/env python

Looks like a fun challenge! By the way: (1) They're actually called "energizers" and not "power pellets." (2) The "M" in Pac-Man is capitalized, and it's hyphenated as "Pac-Man" and not "Pacman" or "PacMan". Here is a great resource for Pac-Man information: http://home.comcast.net/~jpittman2/pacman/pacmandossier.html

There are a few disparities between the spec here and the controller code. Also I'm working on fixing the IO concerns.

Here's an updated controller. First, I replaced the threaded queues for I/O with select.poll and interruptingcow.timeout which should eliminate a lot of problems with I/O exceptions and problems. I also fixed a bug with "X" moves being rejected. I removed the "0x" prefix from hex chars in the maze description. And finally I send a "Q" to all the bots at the end of the match so they know to terminate their processes.
https://gist.github.com/sparr/f4269be18c933b3b7aa5

"You will be given the characters for each square, starting with the top left, moving right, and wrapping to the next line." what is this supposed to mean, other than the same as the next sentence about getting the wall info for the maze?

@Sparr: The first sentence describes the order of characters, the next sentence describe what each character means.

Is there a way to find out where the pacman the program controls is at (as x,y coordinates)?

@es1024 the first coordinate in the info you're given is where your pacman currently is. I think. I'm still figuring out exactly how the controller works, particularly while I'm confusing X/Y coords.

I think scoring for eating ghosts needs to be diminished. It is, by far, the biggest random factor in the game. I've run a few dozen tests between my bots and the usual score spread is about 1000-2000 for shortsighted, 500-800 for a random bot that doesn't walk into walls, and 50-500 for dumbpac. However, every 10 or 20 tests I encounter a run where one bot got a power pellet while adjacent to a bunch of ghosts. I saw a score of 420000 with a second place of 1200.

@Sparr: Yes, I envisioned that too when I saw the imbalanced exponential score on eating ghost. I think OP should just give it constant scores, like 500 or 1000. After all, the ghosts of the same personality will more likely to be in close vicinity of the same player.

By the way, I expect the bots can do something like this: http://www.youtube.com/watch?v=xOCurBYI_gY#t=859 (at 14:22) =D

The controller needs to be improved, there should be no expected exception in I/O.

Maybe we should have a repo in github for the controller.

@Moop Have you tried Sparr 's code? You may start from it.

I did, but he uses select.poll() which is non-windows compatible

the poll may be optional. however, I think interruptingcow ALSO doesn't work on Windows. If someone can come up with a windows-compatible way to do peeked-or-timeout-monitored blocking IO, we'd love to have it incorporated.

Anyone working on this challenge should join us in the chat room for codegolf. http://chat.stackexchange.com/rooms/240/the-nineteenth-byte

This seems like a possible answer: http://stackoverflow.com/questions/375427/non-blocking-read-on-a-subprocess-pipe-in-python

Ok.  The controller now works on windows and linux, but will freeze on windows if your bot doesn't respond.

I am colorblind and cannot tell the PacMen from the Ghosts, could we change the colors?

@Moop: On line 444 of the code, change the very last number from 0 to 255.  It will make all PacMen white. Line: circle_color = (((0, 0, 0), (255, 0, 0), (100, 200, 200), (100, 200, 200))[square.contents] if not square.ghosts else (0, 255, 0)) if not square.players else (255, 255, 255)

@NathanMerrill Yeah, i had done something similar. Just was looking out for the other 10%

I feel like if you are a ghost and you eat a PacMan you should get some points

@Moop, you can think of eating a PacMan as a ghost as an "indirect" bonus since your enemy Pacmen won't get more points. Also, not giving points as a Ghost would give much more value to keeping alive.
I'm not saying your suggestion is bad. I'm just saying that the current system emphasizes the part where a living Pacman is top priority.

How do a player know if itself is invincible? Consider this case: two players step on the same grid which contains a power pellet but none of them got the power pellet. If one of them was a invincible player, then it got the pellet but the other one can't tell if the other is invincible or noet.

I don't think the FOV information being sent to the players is correct. I loaded only my bot and stepped through each turn and if i was moving North up a long hallway, i would only get something like (5,4X 5,4P) even through 5,3 5,2 5,1 etc.. were in the line of site and no walls blocking.

Here is an example of me moving east (http://imgur.com/nq4GYQM and http://imgur.com/Vn49y0q), but the message sent doesn't included the expected 1,9o and 1,8G (and possibly 1,0o)

@Moop I will take a look.

I found a vital bug in the Player.move method. In the first while condition. I profiled the function and code inside the this while loop was never reached.

@Ray I found the bug.  Pushed the fix, and I am rerunning the tests now.

I get a bug where the game freezes after all the pellets have been eaten.

I've never gotten to that point @Moop.  Let me try to figure out what happens.

I think I fixed it Moop.

Latest version isn't working at all on windows. Looks like you send the maze description twice now

Are you sure?  I'm running it just fine here.

@NathanMerrill appears to be a merging issue, not your code. Sorry for the false alarm

New Pac-Man joined, please update the scoreboard.

GhostBuster - Python
Picks a random spot on the map, uses A* algorithm to find the best path forward. Once it reaches its destination, it will pick a new one and continue. It will try to avoid ghosts, but with the limited FOV, it will occasionally run into them. It will avoid walking on spots already visited.

Added logic for ghost. Picks a close (<8) random point and moves there, disregarding scores other than pacmen
Added invincibility logic
Adjusted point values of squares
Bug (if he is too good and eats all the pellets, the game freezes for some reason)

Uses some code of Sparr's, thank you for the logic.

Windows 7, Visual Studios with Python Tools. Should work on linux boxes.
#!/usr/bin/env python

import os
import re
import sys
import math
import random

sys.stdout = os.fdopen(sys.stdout.fileno(), 'w', 0) # automatically flush stdout

P,G,o,O,F,X = 5,600,-10,-100,-100,10
PreviousSquarePenalty = 10

# read in the maze description
maze_desc = sys.stdin.readline().rstrip()
mazeSize = int(math.sqrt(len(maze_desc)))

North,East,South,West = range(4)
DIRECTIONS = ['N','E','S','W']
Euclidian,Manhattan,Chebyshev = range(3)

sign = lambda x: (1, -1)[x<0]
wrap = lambda v : v % mazeSize

class Node(object):

    def __init__(self, x, y, value):
        self.x, self.y = x,y
        self.wallValue = int(value, 16); #Base 16
        self.nodes = {}
        self.item = 'o' # Start as normal pellet

    def connect(self, otherNode, dir):
        if dir not in self.nodes:
            self.nodes[dir] = otherNode
            otherNode.nodes[(dir+2)%4] = self

    def distance(self, otherNode, meth = Manhattan):
        xd = abs(otherNode.x - self.x)
        yd = abs(otherNode.y - self.y)
        xd = min(xd, mazeSize - xd)
        yd = min(yd, mazeSize - yd)
        if meth == Euclidian:
            return math.sqrt(xd * xd + yd * yd)
        if meth == Manhattan:
            return xd + yd
        if meth == Chebyshev:
            return max(xd, yd)

    def direction(self, otherNode):
        for key, value in self.nodes.iteritems():
            if value == otherNode:
                return DIRECTIONS[key]
        return 'ERROR'

    def getScore(self):
        score = eval(self.item)
        for node in self.nodes.values():
            score += eval(node.item)
        return score

    def nearbyGhost(self):
        if self.item == 'G':
            return True
        for node in self.nodes.values():
            if node.item == 'G':
                return True
        return False

    def __hash__(self):
        return  (391 + hash(self.x))*23 + hash(self.y)

    def __eq__(self, other):
        return (self.x, self.y) == (other.x, other.y)

    def __ne__(self, other):
        return (self.x, self.y) != (other.x, other.y)

    def __str__(self):
        return str(self.x)+","+str(self.y)

    def __repr__(self):
        return str(self.x)+","+str(self.y)

# Make all the nodes first
nodes = {}
i = 0
for y in range(mazeSize):
    for x in range(mazeSize):
        nodes[x,y] = Node(x,y,maze_desc[i])
        i+=1

# Connect all the nodes together to form the maze
for node in nodes.values():
    walls = node.wallValue
    x,y = node.x,node.y
    if not walls&1:
        node.connect(nodes[x,wrap(y-1)], North)
    if not walls&2:
        node.connect(nodes[wrap(x+1),y], East)
    if not walls&4:
        node.connect(nodes[x,wrap(y+1)], South)
    if not walls&8:
        node.connect(nodes[wrap(x-1),y], West)

toVisit = set(nodes.values())
currentNode = None
destinationNode = None
previousNode = None
testInvincibilty = False
invincibility = 0
isGhost = False
turns = 0

def aStar(startNode, endNode):
    openSet = set([startNode])
    closedSet = set()
    gScores = {startNode: 0}
    cameFrom = {}
    curNode = startNode
    while openSet:
        minF = 100000000
        for node in openSet:
            g = gScores[node]
            h = node.distance(endNode)
            f = g+h
            if f < minF:
                minF = f
                curNode = node

        if curNode == endNode:
            path = []
            while curNode != startNode:
                path.insert(0, curNode)
                curNode = cameFrom[curNode]
            return path

        openSet.remove(curNode)
        closedSet.add(curNode)
        for node in curNode.nodes.values():
            if node in closedSet:
                continue
            g = gScores[curNode]
            if isGhost:
                g += 1
                if node.item == 'P':
                    g -= 10 # prefer PacMen
            else:
                s = node.getScore();
                if invincibility > 1:
                    g -= abs(s) # everything is tasty when invincible
                else:
                    g += s
                if previousNode and node == previousNode:
                    g += PreviousSquarePenalty # penalize previous square
            isBetter = False
            if node not in openSet:
                openSet.add(node)
                isBetter = True
            elif g < gScores[node]:
                isBetter = True
            if isBetter:
                gScores[node] = g
                cameFrom[node]=curNode

# regex to parse a line of input
input_re = re.compile('(?:([-\d]+),([-\d]+)([PGoOFX]?) ?)+')

while True:
    info = sys.stdin.readline().rstrip()
    if (not info) or (info == "Q"):
        break

    turns += 1

    # break a line of input up into a list of tuples (X,Y,contents)
    info = [input_re.match(item).groups() for item in info.split()]

    # update what we know about all the cells we can see
    for cell in info:
        nodes[int(cell[0]),int(cell[1])].item = cell[2]

    currentNode = nodes[int(info[0][0]),int(info[0][1])]

    if turns == 1:
        print 'X'
        continue

    if not isGhost and currentNode.item == 'G':
        isGhost = True
        destinationNode = random.sample(nodes.values(), 1)[0]

    if isGhost:
        while destinationNode == currentNode or currentNode.distance(destinationNode) > 8:
            destinationNode = random.sample(nodes.values(), 1)[0]
    else:

        if invincibility > 0:
            invincibility -=  1

        if testInvincibilty:
            testInvincibilty = False
            if currentNode.item == 'X':
                invincibility += 10

        while not destinationNode or destinationNode == currentNode:
            destinationNode = random.sample(toVisit, 1)[0]

        if currentNode.item == 'X':
            toVisit.discard(currentNode)

    bestPath = aStar(currentNode, destinationNode)

    nextNode = bestPath[0]

    direction = currentNode.direction(nextNode)

    if not isGhost and nextNode.item == 'O':
        testInvincibilty = True

    previousNode = currentNode

    print direction

shortsighted
This pac avoids adjacent ghosts unless he can eat them, moves onto adjacent fruit or pellets, and walks at random as a last resort.
#!/usr/bin/env python

import os
import re
import sys
import math
import random

sys.stdout = os.fdopen(sys.stdout.fileno(), 'w', 0) # automatically flush stdout

# read in the maze description
maze_desc = sys.stdin.readline().rstrip()
maze_size = int(math.sqrt(len(maze_desc)))

# turn the maze description into an array of arrays
# [wall bitmask, item last seen in square]

def chunks(l, n):
    for i in xrange(0, len(l), n):
        yield l[i:i+n]
maze = []
for row in chunks(maze_desc, maze_size):
    maze.append([[int(c,16),'X'] for c in row])

# regex to parse a line of input
input_re = re.compile('(?:([-\d]+),([-\d]+)([PGoOFX]?) ?)+')

turn = 0
invincibility_over = 0
last_move = None

while True:
    info = sys.stdin.readline().rstrip()
    if (not info) or (info == "Q"):
        break

    # break a line of input up into a list of tuples (X,Y,contents)
    info = info.split()
    info = [input_re.match(item).groups() for item in info]

    # update what we know about all the cells we can see
    for cell in info:
        maze[int(cell[1])][int(cell[0])][1] = cell[2]

    # current location
    x = int(info[0][0])
    y = int(info[0][1])

    # which directions can we move from our current location?
    valid_directions = []
    # we might consider sitting still
    # valid_directions.append('X')
    walls = maze[y][x][0]
    if not walls&1:
        valid_directions.append('N')
    if not walls&2:
        valid_directions.append('E')
    if not walls&4:
        valid_directions.append('S')
    if not walls&8:
        valid_directions.append('W')

    # which direction has the highest value item?
    best_value = 0
    best_direction = 'X'
    for c in [(x,y-1,'N'),(x+1,y,'E'),(x,y+1,'S'),(x-1,y,'W')]:
        if c[2] in valid_directions:
            # am I a ghost?
            if maze[y][x][1] == 'G':
                if maze[c[1]%maze_size][c[0]%maze_size][1] == "P":
                    best_value = 999
                    best_direction = c[2]
            else:
                if maze[c[1]%maze_size][c[0]%maze_size][1] == 'F':
                    if best_value < 100:
                        best_value = 100
                        best_direction = c[2]
                elif maze[c[1]%maze_size][c[0]%maze_size][1] == 'O':
                    if best_value < 50:
                        best_value = 50
                        best_direction = c[2]
                elif maze[c[1]%maze_size][c[0]%maze_size][1] == 'o':
                    if best_value < 10:
                        best_value = 10
                        best_direction = c[2]
                elif maze[c[1]%maze_size][c[0]%maze_size][1] == 'G':
                    if turn < invincibility_over:
                        # eat a ghost!
                        if best_value < 200:
                            best_value = 200
                            best_direction = c[2]
                    else:
                        # avoid the ghost
                        valid_directions.remove(c[2])

    # don't turn around, wasteful and dangerous
    if last_move:
        reverse = ['N','E','S','W'][['S','W','N','E'].index(last_move)]
        if reverse in valid_directions:
            valid_directions.remove(reverse)

    if best_value == 50:
        invincibility_over = turn + 10
    if best_direction != 'X':
        # move towards something worth points
        # sys.stderr.write("good\n")
        last_move = best_direction
    elif len(valid_directions)>0:
        # move at random, not into a wall
        # sys.stderr.write("valid\n")
        last_move = random.choice(valid_directions)
    else:
        # bad luck!
        # sys.stderr.write("bad\n")
        last_move = random.choice(['N','E','S','W'])
    print last_move

    turn += 1

avoider
Avoid all ghosts as a pacman, and all pacmen when a ghost. Tries to avoid any of its own kind if possible, and then avoids turning 180 if possible.
#!/usr/bin/env python
import os
import re
import sys
import math
import random

sys.stdout = os.fdopen(sys.stdout.fileno(), 'w', 0) # automatically flush stdout

# read in the maze description
maze_desc = sys.stdin.readline().rstrip()
maze_size = int(math.sqrt(len(maze_desc)))

# turn the maze description into an array of arrays of numbers indicating wall positions

def chunks(l, n):
    for i in xrange(0, len(l), n):
        yield l[i:i+n]
maze = []
for row in chunks(maze_desc, maze_size):
    maze.append([[int(c,16),'X'] for c in row])

# regex to parse a line of input
input_re = re.compile('(?:([-\d]+),([-\d]+)([PGoOFX]?) ?)+')

last_moved = 'X'

while True:
    info = sys.stdin.readline().rstrip()
    if (not info) or (info == "Q"):
        break

    # break a line of input up into a list of tuples (X,Y,contents)
    info = info.split()
    info = [input_re.match(item).groups() for item in info]

    # location
    x = int(info[0][0])
    y = int(info[0][1])

    # update what we know about all the cells we can see
    for cell in info:
        maze[int(cell[1])][int(cell[0])][1] = cell[2]

    # which directions can we move from our current location?
    valid_directions = []
    walls = maze[y][x][0]
    if not walls&1:
        valid_directions.append('N')
    if not walls&2:
        valid_directions.append('E')
    if not walls&4:
        valid_directions.append('S')
    if not walls&8:
        valid_directions.append('W')

    bad_directions = []
    for c in [(x,y-1,'N'),(x+1,y,'E'),(x,y+1,'S'),(x-1,y,'W')]:
        if c[2] in valid_directions:
            # am I a ghost?
            if maze[y][x][1] == 'G':
                # it's a pacman, run. interaction is always a risk.
                if maze[c[1]%maze_size][c[0]%maze_size][1] == "P":
                    valid_directions.remove(c[2])
                # another ghost? let me move away.
                elif maze[c[1]%maze_size][c[0]%maze_size][1] == "G":
                    bad_directions.append(c[2])
            else:
                # it's a ghost, run. ghosts are evil.
                if maze[c[1]%maze_size][c[0]%maze_size][1] == "G":
                    valid_directions.remove(c[2])
                # its another pacman, move away!
                elif maze[c[1]%maze_size][c[0]%maze_size][1] == "P":
                    bad_directions.append(c[2])

    # if possible to avoid normal contact, do so
    good_directions = list(set(valid_directions) - set(bad_directions))
    if len(good_directions) > 0:
        valid_directions = good_directions

    # if not the only option, remove going backwards from valid directions
    if len(valid_directions) > 1:
        if last_moved == 'N' and 'S' in valid_directions:
            valid_directions.remove('S')
        elif last_moved == 'S' and 'N' in valid_directions:
            valid_directions.remove('N')
        elif last_moved == 'W' and 'E' in valid_directions:
            valid_directions.remove('E')
        elif 'W' in valid_directions:
            valid_directions.remove('W')

    # if possible, continue in the same direction
    if last_moved in valid_directions:
        print last_moved
    # prefer turning left/right randomly instead of turning 180
    #   backwards has been removed from valid_directions if not
    #   the only option
    elif len(valid_directions) > 0:
        last_moved=random.choice(valid_directions)
        print last_moved
    # can't move, so stay put. desire to continue in original
    #   direction remains.
    else:
        print 'X'

This answer throws an error.  You haven't defined x or y

File "avoider.py", line 42, in
maze[int(cell[1])][int(cell[0])][1] = cell[2]
TypeError: 'int' object does not support item assignment

valid_directions.remove('W')
ValueError: list.remove(x): x not in list

@NathanMerrill Should be fixed now.

Physicist, Haskell

The physicist Pac-Man believe that Newton's law of universal gravitation can help him win the game. Then he just apply it to all other objects he know during the game. Since the physicist is old and has bad memory, he can only remember things in 5 rounds. Hooooly, the bad memory actually helps him to score better.
This answer has two fille:

Main.hs, contains the interesting part.
Pacman.hs, just some boring code the handle the protocol. You may use it to write your own haskell solution. It doesn't contain any AI code.

Oh, wait, we have a Makefile, too.
Here they comes:
Main.hs
import Pacman
import Data.Complex
import Data.List
import Data.Function
import qualified Data.Map as Map
import Data.Maybe
import System.IO

data DebugInfo = DebugInfo {
  debugGrid :: Grid
, debugForce :: Force
, debugAction :: Action
} deriving (Show)

data Physicist = Physicist [(Int, Object)] (Maybe DebugInfo)

type Force = Complex Double

calcForce :: Int -> Position -> PlayerType -> Object -> Force
calcForce n p1 t1 object = if d2 == 0 then 0 else base / (fromIntegral d2 ** 1.5 :+ 0)
  where
    (x1, y1) = p1
    (x2, y2) = p2
    wrap d = minimumBy (compare `on` abs) [d, n - d]
    dx = wrap $ x2 - x1
    dy = wrap $ y2 - y1
    Object t2 p2 = object
    d2 = dx * dx + dy * dy
    base = (fromIntegral dx :+ fromIntegral dy) * case t1 of
      PacmanPlayer -> case t2 of
        Pellet -> 10.0
        PowerPellet -> 200.0
        Ghost -> -500.0
        Pacman -> -20.0
        Fruit -> 100.0
        Empty -> -2.0
      GhostPlayer -> case t2 of
        Pellet -> 10.0
        PowerPellet -> 200.0
        Ghost -> -50.0
        Pacman -> 500.0
        Fruit -> 100.0
        Empty -> -2.0

instance PlayerAI Physicist where
  findAction player info = (action, player') where
    Player {
      playerType = type_
    , playerField = field
    , playerMemory = Physicist objectsWithAge _
    } = player

    n = fieldSize field
    NormalRound pos _ objects = info
    objectsWithAge' = combineObjects objectsWithAge objects
    objects' = map snd objectsWithAge'
    directionChoices = filter (not . gridHasWall grid) directions4
    totalForce = sum $ map (calcForce n pos type_) objects'
    grid = fromMaybe (error $ "invalid position " ++ show pos) $ (fieldGetGrid field) pos
    action = if magnitude totalForce < 1e-10
      then if null directionChoices
        then Stay
        else Move $ head directionChoices
      else Move $ maximumBy (compare `on` (projectForce totalForce)) directionChoices
    debugInfo = Just $ DebugInfo grid totalForce action
    player' = player {
      playerMemory = Physicist objectsWithAge' debugInfo
    }

  -- roundDebug player _ = do
  --   let Physicist objects debugInfo = playerMemory player
  --       type_ = playerType player
  --   hPrint stderr (objects, debugInfo)

combineObjects :: [(Int, Object)] -> [Object] -> [(Int, Object)]
combineObjects xs ys = Map.elems $ foldr foldFunc initMap ys where
  foldFunc object@(Object type_ pos) = Map.insert pos (0, object)
  addAge (age, object) = (age + 1, object)
  toItem (age, object@(Object _ pos)) = (pos, (age, object))
  initMap = Map.fromList . map toItem . filter filterFunc . map addAge $ xs
  filterFunc (age, object@(Object type_ _))
    | type_ == Empty = True
    | age < maxAge = True
    | otherwise = False

maxAge = 5

projectForce :: Force -> Direction -> Double
projectForce (fx :+ fy) (Direction dx dy) = fx * fromIntegral dx + fy * fromIntegral dy

main :: IO ()
main = runAI $ Physicist [] Nothing

Pacman.hs
module Pacman (
    Field(..)
  , Grid(..)
  , Direction(..)
  , directions4, directions8
  , Position
  , newPosition
  , Player(..)
  , PlayerType(..)
  , ObjectType(..)
  , Object(..)
  , RoundInfo(..)
  , Action(..)
  , runAI
  , PlayerAI(..)
  ) where

import Data.Bits
import Data.Char
import Data.List
import Data.Maybe
import qualified Data.Map as Map
import qualified System.IO as SysIO

data Field = Field {
  fieldGetGrid :: Position -> Maybe Grid
, fieldSize :: Int
}

data Grid = Grid {
  gridHasWall :: Direction -> Bool
, gridPos :: Position
}

instance Show Grid where
  show g = "Grid " ++ show (gridPos g) ++ ' ':reverse [if gridHasWall g d then '1' else '0' | d <- directions4]

data Direction = Direction Int Int
  deriving (Show, Eq)

directions4, directions8 :: [Direction]
directions4 = map (uncurry Direction) [(-1, 0), (0, 1), (1, 0), (0, -1)]
directions8 = map (uncurry Direction) $ filter (/=(0, 0)) [(dx, dy) | dx <- [-1..1], dy <- [-1..1]]

type Position = (Int, Int)
newPosition :: (Int, Int)  -> Position
newPosition = id

data Player a = Player {
  playerType :: PlayerType
, playerField :: Field
, playerRounds :: Int
, playerMemory :: a
}
data PlayerType = PacmanPlayer | GhostPlayer
  deriving (Show, Eq)

class PlayerAI a where
  onGameStart :: a -> Field -> IO ()
  onGameStart _ _ = return ()

  onGameEnd :: a -> IO ()
  onGameEnd _ = return ()

  findAction :: Player a -> RoundInfo -> (Action, Player a)

  roundDebug :: Player a -> RoundInfo -> IO ()
  roundDebug _ _ = return ()

data ObjectType = Pacman | Ghost | Fruit | Pellet | PowerPellet | Empty
  deriving (Eq, Show)
data Object = Object ObjectType Position
  deriving (Show)

data RoundInfo = EndRound | NormalRound Position PlayerType [Object]

data Action = Stay | Move Direction
  deriving (Show)

parseField :: String -> Field
parseField s = if validateField field
  then field
  else error $ "Invalid field: " ++ show ("n", n, "s", s, "fieldMap", fieldMap)
  where
    field = Field {
      fieldGetGrid = flip Map.lookup fieldMap
    , fieldSize = n
    }
    (n : _) = [x | x <- [0..], x * x == length s]
    fieldMap = Map.fromList [
        ((i, j), parseGrid c (newPosition (i, j)))
        | (i, row) <- zip [0..n-1] rows,
          (j, c) <- zip [0..n-1] row
      ]
    rows = reverse . snd $ foldr rowFoldHelper (s, []) [1..n]
    rowFoldHelper _ (s, rows) =
      let (row, s') = splitAt n s
      in (s', row:rows)

validateField :: Field -> Bool
validateField field@(Field { fieldGetGrid=getGrid, fieldSize=n }) =
  all (validateGrid field) $ map (fromJust.getGrid) [(i, j) | i <- [0..n-1], j <- [0..n-1]]

validateGrid :: Field -> Grid -> Bool
validateGrid
  field@(Field { fieldGetGrid=getGrid, fieldSize=n })
  grid@(Grid { gridPos=pos })
  = all (==True) [gridHasWall grid d == gridHasWall (getNeighbour d) (reverse d) | d <- directions4]
  where
    reverse (Direction dx dy) = Direction (-dx) (-dy)
    (x, y) = pos
    getNeighbour (Direction dx dy) = fromJust . getGrid . newPosition $ (mod (x + dx) n, mod (y + dy) n)

parseGrid :: Char -> Position -> Grid
parseGrid c pos = Grid gridHasWall pos
  where
    walls = zip directions4 bits
    bits = [((x `shiftR` i) .&. 1) == 1 | i <- [0..3]]
    Just x = elemIndex (toLower c) "0123456789abcdef"
    gridHasWall d = fromMaybe (error $ "No such direction " ++ show d) $
      lookup d walls

parseRoundInfo :: String -> RoundInfo
parseRoundInfo s = if s == "Q" then EndRound else NormalRound pos playerType objects'
  where
    allObjects = map parseObject $ words s
    Object type1 pos : objects = allObjects
    objects' = if type1 `elem` [Empty, Ghost] then objects else allObjects
    playerType = case type1 of
      Ghost -> GhostPlayer
      _ -> PacmanPlayer

parseObject :: String -> Object
parseObject s = Object type_ (newPosition (x, y)) where
  (y, x) = read $ "(" ++ init s ++ ")"
  type_ = case last s of
    'P' -> Pacman
    'G' -> Ghost
    'o' -> Pellet
    'O' -> PowerPellet
    'F' -> Fruit
    'X' -> Empty
    c -> error $ "Unknown object type: " ++ [c]

sendAction :: Action -> IO ()
sendAction a = putStrLn name >> SysIO.hFlush SysIO.stdout where
  name = (:[]) $ case a of
    Stay -> 'X'
    Move d -> fromMaybe (error $ "No such direction " ++ show d) $
      lookup d $ zip directions4 "NESW"

runPlayer :: PlayerAI a => Player a -> IO ()
runPlayer player = do
  roundInfo <- return . parseRoundInfo =<< getLine
  case roundInfo of
    EndRound -> return ()
    info@(NormalRound _ type_' _) -> do
      let
        updateType :: Player a -> Player a
        updateType player = player { playerType = type_' }
        player' = updateType player
        (action, player'') = findAction player' info
      roundDebug player'' info
      sendAction action
      let
        updateRounds :: Player a -> Player a
        updateRounds player = player { playerRounds = playerRounds player + 1}
        player''' = updateRounds player''
      runPlayer player'''

runAI :: PlayerAI a => a -> IO ()
runAI mem = do
  field <- return . parseField =<< getLine
  let player = Player {
    playerType = PacmanPlayer
  , playerField = field
  , playerRounds = 0
  , playerMemory = mem
  }
  runPlayer player

Makefile
physicist: Main.hs Pacman.hs
    ghc -O3 -Wall Main.hs -o physicist

command.txt
./physicist

I'm unable to run this.  I get "File name does not match module name: Saw Main' Expected Pacman'" when I try to make it.  Also, in order to run it, do I just need to make it, or is there another command I need to run?

@NathanMerrill You should first make it then run the physicist executable. Edited and added command.txt, now.

I am making it.  The error I listed is thrown when I make it.  Also assume you are in the physicist directory.  Wouldn't it be ghc physicist in the command.txt?

@NathanMerrill That's strange. Maybe due to different behaviour of GHC on Windows. Renaming physicist.hs to Main.hs may work. I've updated the answer.

@NathanMerrill Did you combined these two files? That wouldn't work.

I didn't combine the files, they are separate.  Are you running on Windows?  How did you run the makefile on windows?

Let us continue this discussion in chat.

I cannot run this on Windows 7. I have haskell and did the ghc -o physicist -O3 physicist.hs command which produce physicist.exe, but it doesn't work with the controller

@Moop So how's the problem?

Looks like the command.txt doesn't work on windows. I had to change it to: bots/physcist/physicist.exe to work. If you name your executable physicist.exe on linux, and fully specify the path, i think it should work on both platforms

@Moop The controller will set the subprocess CWD to bots/physicist, so I don't know why changing command file like that works. Also I remember that Windows don't need to specify the exe suffix to run it.

@Ray, good point about not including the .exe The bug I was seeing was a file not file exception, when I fully qualified the path, it worked.

I had a problem running it on windows as well.  Now, my  controller will make the exe, and then it will replace ./ with the directory if you are on windows.

@NathanMerrill I don't have a Windows machine to test, but I think this may work: In the controller code, instead of using shlex, use the OS shell to run the command file. That is,  use cmd on Windows and use sh on Linux.

dumbpac
This pac just moves at random, with no regard for the maze layout or ghosts or any other factors.
Perl:
#!/usr/bin/perl
local $| = 1; # auto flush!
$maze_desc = <>;
while(<>) {
    if($_ eq "Q"){
        exit;
    }
    $move = (("N","E","S","W","X")[rand 5]);
    print ($move . "\n");
}

Python:
#!/usr/bin/env python

import os
import sys
import random

sys.stdout = os.fdopen(sys.stdout.fileno(), 'w', 0) # automatically flush stdout

maze_desc = sys.stdin.readline().rstrip()
while True:
    info = sys.stdin.readline().rstrip()
    if (not int) or (info == "Q"):
        break
    print random.choice(['N', 'E', 'S', 'W', 'X'])

randomwalk
this pac walks at random, but not into walls
#!/usr/bin/env python

import os
import re
import sys
import math
import random

sys.stdout = os.fdopen(sys.stdout.fileno(), 'w', 0) # automatically flush stdout

# read in the maze description
maze_desc = sys.stdin.readline().rstrip()
maze_size = int(math.sqrt(len(maze_desc)))

# turn the maze description into an array of arrays of numbers indicating wall positions
def chunks(l, n):
    for i in xrange(0, len(l), n):
        yield l[i:i+n]
map = []
for row in chunks(maze_desc, maze_size):
    map.append([int(c,16) for c in row])

# regex to parse a line of input
input_re = re.compile('(?:([-\d]+),([-\d]+)([PGoOFX]?) ?)+')

while True:
    info = sys.stdin.readline().rstrip()
    if (not info) or (info == "Q"):
        break

    # break a line of input up into a list of tuples (X,Y,contents)
    info = info.split()
    info = [input_re.match(item).groups() for item in info]

    # this pac only cares about its current location
    info = info[0]

    # which directions can we move from our current location?
    valid_directions = []
    # we might consider sitting still
    # valid_directions.append('X')
    walls = map[int(info[1])][int(info[0])]
    if not walls&1:
        valid_directions.append('N')
    if not walls&2:
        valid_directions.append('E')
    if not walls&4:
        valid_directions.append('S')
    if not walls&8:
        valid_directions.append('W')

    # move at random, not into a wall
    print random.choice(valid_directions)

Pathy, Python 3
This bot use path finding a lot. Given a start position and end condition, it use the simple BFS to find the shortest path. Path finding is used in:

Find power pellets, fruits or pellets.
If it's invincible, chase ghosts
If it's ghost, chase Pac-Men
Flee from ghosts
Calculate distance between a given pair of positions.

command.txt
python3 pathy.py

pathy.py
import sys
import random
from collections import deque

DIRECTIONS = [(-1, 0), (0, 1), (1, 0), (0, -1)]
GHOST = 'G'
PACMAN = 'P'
FRUIT = 'F'
PELLET = 'o'
POWER_PELLET = 'O'
EMPTY = 'X'

PACMAN_PLAYER = 'pacman-player'
GHOST_PLAYER = 'ghost-player'

class Field:
    def __init__(self, s):
        n = int(.5 + len(s) ** .5)
        self.size = n
        self.mp = {(i, j): self.parse_grid(s[i * n + j]) for i in range(n) for j in range(n)}

    @staticmethod
    def parse_grid(c):
        x = int(c, 16)
        return tuple((x >> i) & 1 for i in range(4))

    def can_go_dir_id(self, pos, dir_id):
        return self.mp[pos][dir_id] == 0

    def connected_neighbours(self, pos):
        return [(d, self.go_dir_id(pos, d)) for d in range(4) if self.can_go_dir_id(pos, d)]

    def find_path(self, is_end, start):
        que = deque([start])
        prev = {start: None}
        n = self.size

        def trace_path(p):
            path = []
            while prev[p]:
                path.append(p)
                p = prev[p]
            path.reverse()
            return path

        while que:
            p = x, y = que.popleft()
            if is_end(p):
                return trace_path(p)
            for d, p1 in self.connected_neighbours(p):
                if p1 in prev:
                    continue
                prev[p1] = p
                que.append(p1)
        return None

    def go_dir_id(self, p, dir_id):
        dx, dy = DIRECTIONS[dir_id]
        x, y = p
        n = self.size
        return (x + dx) % n, (y + dy) % n

    def distance(self, p1, p2):
        return len(self.find_path((lambda p: p == p2), p1))

    def get_dir(self, p1, p2):
        x1, y1 = p1
        x2, y2 = p2
        return (self.dir_wrap(x2 - x1), self.dir_wrap(y2 - y1))

    def dir_wrap(self, x):
        if abs(x) > 1:
            return 1 if x < 0 else -1
        return x

class Player:
    def __init__(self, field):
        self.field = field

    def interact(self, objects):
        " return: action: None or a direction_id"
        return action

    def send(self, msg):
        print(msg)
        sys.stdout.flush()

class Pathy(Player):
    FLEE_COUNT = 8

    def __init__(self, field):
        super().__init__(field)
        self.type = PACMAN_PLAYER
        self.pos = None
        self.mem_field = {p: GHOST for p in self.field.mp}
        self.power = 0
        self.flee = 0
        self.ghost_pos = None
        self.ghost_distance = None

    @property
    def invincible(self):
        return self.type == PACMAN_PLAYER and self.power > 0

    def detect_self(self, objects):
        ((x, y), type) = objects[0]
        self.type = GHOST_PLAYER if type == GHOST else PACMAN_PLAYER
        self.pos = (x, y)

    def update_mem_field(self, objects):
        for (p, type) in objects:
            self.mem_field[p] = type

    def find_closest_ghost_pos(self, objects):
        try:
            return min(
                (p for (p, t) in objects if t == GHOST),
                key=lambda p: self.field.distance(self.pos, p)
            )
        except:
            return None

    def chase(self, types):
        is_end = lambda p: self.mem_field[p] in types
        path = self.field.find_path(is_end, self.pos)
        if not path:
            return None
        return DIRECTIONS.index(self.field.get_dir(self.pos, path[0]))

    def interact(self, objects):
        self.detect_self(objects)
        self.update_mem_field(objects)

        action = None
        if self.invincible:
            self.debug('invincible!!!')
            action = self.chase((GHOST,))
            if action is None:
                action = self.chase((POWER_PELLET,))
            if action is None:
                action = self.chase((FRUIT, PELLET,))
        elif self.type == GHOST_PLAYER:
            action = self.chase((PACMAN,))
        else:
            # PACMAN_PLAYER
            ghost_pos = self.find_closest_ghost_pos(objects)
            if ghost_pos:
                ghost_distance = self.field.distance(ghost_pos, self.pos)
                if not self.flee or ghost_distance < self.ghost_distance:
                    self.flee = self.FLEE_COUNT
                    self.ghost_distance = ghost_distance
                    self.ghost_pos = ghost_pos

            if self.flee > 0:
                self.flee -= 1
                action = max(
                    self.field.connected_neighbours(self.pos),
                    key=lambda dp: self.field.distance(dp[1], self.ghost_pos)
                )[0]
                # self.debug('flee: ghost_pos {} pos {} dir {} dist {}'.format(
                #     self.ghost_pos, self.pos, DIRECTIONS[action], self.field.distance(self.pos, self.ghost_pos)))
            else:
                self.ghost_pos = self.ghost_distance = None
                action = self.chase((POWER_PELLET, FRUIT))
                if action is None:
                    action = self.chase((PELLET,))
                if action is None:
                    action = random.choice(range(5))
                    if action > 3:
                        action = None

        # Detect power pellet
        if action is None:
            next_pos = self.pos
        else:
            next_pos = self.field.go_dir_id(self.pos, action)
        if self.mem_field[next_pos] == POWER_PELLET:
            self.power = 9
        elif self.invincible and self.mem_field[next_pos] == GHOST:
            self.debug('Got a ghost!')
        else:
            self.power = max(0, self.power - 1)
        return action

    def debug(self, *args, **kwargs):
        return
        print(*args, file=sys.stderr, **kwargs)

def start_game(player_class):
    field = Field(input())
    player = player_class(field)
    while True:
        line = input()
        if line == 'Q':
            break
        objects = [(tuple(map(int, x[:-1].split(',')))[::-1], x[-1]) for x in line.split(' ')]
        action = player.interact(objects)
        player.send('NESW'[action] if action is not None else 'X')

if __name__ == '__main__':
    start_game(Pathy)

objects = [(tuple(map(int, x[:-1].split(',')))[::-1], x[-1]) for x in line.split(' ')] throws a ValueError: invalid literal for int() with base 10: '8o'

What did the controller send? Does it fail every time? It works here and I think this statement should work well.


text:
Minimal cover of bases for quadratic residue testing of squareness
Challenge
Find the smallest cover of bases (e.g., moduli) whose sets of quadratic residue can be tested via table-lookup to definitively determine whether or not a given non-negative integer n is a perfect square. The bases must all be less than or equal to the square root of the maximum value of n.
The answer with the smallest set of bases for a given category of n wins the challenge. (This means there may potentially be more than one winner.) The categories of n are:
         Category       Maximum allowed n    Maximum allowed modulus/base
    -------------    --------------------    ----------------------------
     8-bit values                     255                              15
    16-bit values                   65535                             255
    32-bit values              4294967295                           65535
    64-bit values    18446744073709551615                      4294967295

In the event of a tie with two sets having equal cardinality, the tie will go to the set having the greater ability to detect non-squares earlier in the sequence.
In the event that no complete covers are found (which is entirely likely for the 32-bit and 64-bit categories), the winner will be the set of bases which statistically or provably rules out the highest percentage of non-squares (without incorrectly reporting squares as non-squares). See below for a discussion of incomplete covers.
Background
In many number theory applications, the question arises whether or not some number n is a perfect square (0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, etc.).  One way to test whether n is square is to test whether floor(√n)² = n, that is, whether the rounded-down square root of n, when squared, gives back n. For example, floor(√123)² = 11² = 121, which is not 123, so 123 is not square; but floor(√121)² = 11² = 121, so 121 is square. This method works fine for small numbers, especially when a hardware square-root operation is available. But for large numbers (hundreds or thousands of bits) it can be very slow.
Another way to test for squareness is to rule out non-squares using quadratic residue tables. For example, all squares in base 10 must have a final (ones-place) digit that is either 0, 1, 4, 5, 6, or 9. These values form the set of quadratic residue for base 10. So if a base-10 number ends in 0, 1, 4, 5, 6, or 9, you know that it might be square, and further examination will be required. But if a base-10 number ends in 2, 3, 7, or 8, then you can be certain that it is not square.
So let's look at another base. All squares in base 8 must end in 0, 1, or 4, which conveniently is only 3 of 8 possibilities, meaning a 37.5% chance of a random number being possibly square, or 62.5% chance of a random number definitely not being square. Those are much better odds than what base 10 gives.  (And note that a base-8 modulus operation is simply a logical-and operation, as opposed to base-10 modulus, which is a division by 10 with remainder.)
Are there even better bases? Well, yes, actually. Base 120 has 18 possibilities (0, 1, 4, 9, 16, 24, 25, 36, 40, 49, 60, 64, 76, 81, 84, 96, 100, and 105), which represents only a 15% chance of possibly being square. And base 240 is better yet, with only 24 possibilities, representing only 10% chance of possibly being square.
But no single base alone can definitively determine squareness (unless it is larger than the maximum number being tested, which is eminently impractical). A single base alone can only rule out squareness; it cannot conclusively verify squareness. Only a carefully selected set of bases, working together, can conclusively verify squareness over a range of integers.
So, the question becomes: What set of bases forms a minimal cover which together permit the definitive deduction of squareness or non-squareness?
Example of a correct but non-minimal cover
The cover 16-base cover { 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 29, 31, 37 } is sufficient to definitively determine squareness or non-squareness of all 16-bit values 0 to 65535. But it is not a minimal cover, because at least one 15-base cover exists that is also easily discoverable. In fact, it is likely that far smaller covers exist — perhaps with as few as 6 or 7 bases.
But for illustration, let's take a look at testing a sample value of n using this 16-base cover set. Here are the sets of quadratic residues for the above set of bases:
Base m   Quadratic residue table specific to base m
------   ----------------------------------------------------
   3     {0,1}
   4     {0,1}
   5     {0,1,4}
   7     {0,1,2,4}
   8     {0,1,4}
   9     {0,1,4,7}
  11     {0,1,3,4,5,9}
  13     {0,1,3,4,9,10,12}
  16     {0,1,4,9}
  17     {0,1,2,4,8,9,13,15,16}
  19     {0,1,4,5,6,7,9,11,16,17}
  23     {0,1,2,3,4,6,8,9,12,13,16,18}
  25     {0,1,4,6,9,11,14,16,19,21,24}
  29     {0,1,4,5,6,7,9,13,16,20,22,23,24,25,28}
  31     {0,1,2,4,5,7,8,9,10,14,16,18,19,20,25,28}
  37     {0,1,3,4,7,9,10,11,12,16,21,25,26,27,28,30,33,34,36}

Now let's test the number n = 50401 using this set of bases, by converting it into each base. (This is not the most efficient way examine residue, but it is sufficient for explanatory purposes.)  It's the 1's place that we're interested in here (marked below in parentheses):
 Base                               "Digits" in base m
   m          m^9   m^8   m^7   m^6   m^5   m^4   m^3   m^2   m^1  ( m^0 )
 ----      -----------------------------------------------------------------
   3           2     1     2     0     0     1     0     2     0   (  1 ) ✓
   4                       3     0     1     0     3     2     0   (  1 ) ✓
   5                             3     1     0     3     1     0   (  1 ) ✓
   7                                   2     6     6     6     4   (  1 ) ✓
   8                                   1     4     2     3     4   (  1 ) ✓
   9                                         7     6     1     2   (  1 ) ✓
  11                                         3     4     9     5   ( 10 )
  13                                         1     9    12     3   (  0 ) ✓
  16                                              12     4    14   (  1 ) ✓
  17                                              10     4     6   ( 13 ) ✓
  19                                               7     6    11   ( 13 )
  23                                               4     3     6   (  8 ) ✓
  25                                               3     5    16   (  1 ) ✓
  29                                               2     1    26   ( 28 ) ✓
  31                                               1    21    13   ( 26 )
  37                                                    36    30   (  7 ) ✓

So we can see that in 13 of these bases, the residue matches a known quadratic residue (call this a "hit" in the table), and in 3 of these bases, the residue does not match a known quadratic residue (call this a "miss").  All it takes is 1 miss to know that a number is non-square, so we could stop at 11, but for illustrative purposes, we've examined all 16 of the bases here.
Example of an incomplete cover
Technically, an incomplete cover is not a cover, but that's beside the point. The set of bases { 7, 8, 11, 15 } nearly covers all the 8-bit values of n from 0 to 255 correctly, but not quite. In particular, it incorrectly identifies 60 and 240 as being square (these are false positives) — but it does correctly identify all of the actual squares (0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, and 225) and makes no other false positives. So this is a 4-set which almost succeeds as a solution, but ultimately fails, because an incomplete cover is not a valid solution.
For 8-bit n, the set of bases { 7, 8, 11, 15 } is one of two sets of 4 bases which produce two errors, and there are seven sets of 4 bases which only produce one error.  No sets of 4 bases actually exist which form a complete and accurate cover of 8-bit values. Can you find a set of 5 bases which produce no errors, covering all 8-bit values correctly? Or do you need 6 or more? (I do know the answer for 8-bit n, but I'm not going to give it away. I do not know the answer for 16-bit, 32-bit, or 64-bit, and I believe even the 16-bit case is impossible to solve via brute-force searching. Solving the 32-bit and 64-bit cases will certainly require genetic, heuristic, or other search techniques.)
A comment on cryptographically large numbers
Beyond 64-bit numbers — up in the hundreds or thousands of binary digits — this is where a quick squareness check really comes in most handy, even if the cover is incomplete (which it most certainly will be for really large numbers). How could a test like this still be useful even if it is insufficiently decisive? Well, imagine you had an extremely fast test for squareness which worked correctly 99.9% of the time and gave false negatives the remaining 0.1% of the time and never gave false positives. With such a test, you would be able to determine non-squareness of a number nearly instantly, and then in the exceptional cases of indecisiveness, you could then resort to a slower method to resolve the unknown a different way. This would save you quite a bit of time.
For example, the set { 8, 11, 13, 15 } is correct 99.61% of the time for 8-bit values of n from 0 to 255, is correct 95.98% of the time for 16-bit values of n from 0 to 65535, and is correct 95.62% of the time for 24-bit values of n from 0 to 16777215. As n goes to infinity, the percentage of correctness for this set of bases goes down, but it asymptotically approaches and never drops below 95.5944% correctness.
So even this very tiny set of 4 small bases is useful to nearly immediately identify about 22 out of 23 arbitrarily large numbers as being non-squares — obviating the need for further inspection of those numbers by slower methods. The slower methods then need only be applied in the small percentage of cases which could not be ruled out by this quick test.
It is interesting to note that some 16-bit bases achieve better than 95% all on their own. In fact, each of the bases below is able to weed out better than 97% of all numbers up to infinity as not being square. The quadratic residue set for each of these bases can be represented as a packed-bit array using only 8192 bytes.
Here are the 10 most powerful single bases less than 2^16:
 Rank   Base    Prime factorization       Weeds out
 ----   ------------------------------    ---------
  1.    65520 = 2^4 x 3^2 x 5 x 7 x 13      97.95%
  2.    55440 = 2^4 x 3^2 x 5 x 7 x 11      97.92%
  3.    50400 = 2^5 x 3^2 x 5^2 x 7         97.56%
  4.    52416 = 2^6 x 3^2 x 7 x 13          97.44%
  5.    61200 = 2^4 x 3^2 x 5^2 x 17        97.41%
  6.    44352 = 2^6 x 3^2 x 7 x 11          97.40%
  7.    63360 = 2^7 x 3^2 x 5 x 11          97.39%
  8.    60480 = 2^6 x 3^3 x 5 x 7           97.38%
  9.    63840 = 2^5 x 3 x 5 x 7 x 19        97.37%
 10.    54720 = 2^6 x 3^2 x 5 x 19          97.37%

See anything interesting that these bases all have in common? There's no reason to think they might be useful in combination together (maybe they are, maybe they aren't), but there are some good clues here as to what bases are likely to be most influential for the larger categories of numbers.
Side challenge: One of the most influential bases (if not the most) up to 2^28 is 245044800, which alone can correctly weed out 99.67% of non-squares, or about 306 of 307 random numbers thrown at it. Can you find the most influential single base less than 2^32?
Related
There are some very nice ideas in the following questions that are closely related, as well as several micro-optimization tricks for making certain operations faster. Although the linked questions do not specifically set out to find the strongest set of bases, the idea of strong bases is implicitly central some of the optimization techniques used there.

Fastest way to determine if an integer's square root is an integer
Detecting perfect squares faster than by extracting square root

How will you determine the tie-breaker short of testing every single number in the given range and counting how many checks were made in total?

I'll look at the cardinality of the sets of quadratic residues for each base. For example, 4 is a better base than 3, because only half of the values modulo 4 are quadratic residues, whereas two-thirds of the values modulo 3 are quadratic residues. Thus, 4 has a greater ability to weed out numbers earlier. The worst base is 2, because it cannot rule out any number, and the best base less than 256 is 240, which is capable of ruling out 90% of numbers. Might have to do Monte Carlo sampling for really large bases.

Yeah, that makes sense. But will you decide the tie just by the first base whose probability differs, or how will you figure out the efficiency of the entire set based on the probabilities? I'm also thinking that the probabilities aren't independent any more once you've checked other bases.

In the case of large n spaces, I think I will have to decide the tie based on the overall estimated efficiency, as calculated by multiplying the probabilities predicted by each residue set. For example, the bases {8,11,13,15} have probabilities of 0.375, 0.545455, 0.538462, and 0.4, respectively, which multiply to 0.044056. Subtracting from 1, this gives 0.955944, which agrees very closely with the exhaustive counting result of 95.62% as measured over all n in [0,2^24-1].

Mathematica
I don't really know a lot about number theory (unfortunately), so this is a rather naive approach. I'm using a greedy algorithm which always adds the base that has the most misses for the remaining numbers.
bits = 8
Timing[
 maxN = 2^bits - 1;
 maxBase = 2^(bits/2) - 1;
 bases = {
     #,
     Union[Mod[Range[0, Floor[#/2]]^2, #]]
     } & /@ Range[3, maxBase];
 bases = SortBy[bases, Length@#[[2]]/#[[1]] &];
 numbers = {};
 For[i = 0, i <= Quotient[maxN, bases[[1, 1]]], ++i,
  AppendTo[numbers, # + i*bases[[1, 1]]] & /@ bases[[1, 2]]
  ];
 While[numbers[[-1]] > maxN, numbers = Most@numbers];
 numbers = Rest@numbers;
 i = 0;
 cover = {bases[[1, 1]]};
 lcm = cover[[-1]];
 Print@cover[[1]];
 While[Length@numbers > maxBase,
  ++i;
  bases = DeleteCases[bases, {b_, r_} /; b\[Divides]lcm];
  (*bases=SortBy[bases,(Print[{#,c=Count[numbers,n_/;MemberQ[#[[2]],
  Mod[n,#[[1]]]]]}];c)&];*)
  bases = SortBy[
    bases,
    (
      n = Cases[numbers, n_ /; n < LCM[#[[1]], lcm]];
      Count[n, n_ /; MemberQ[#[[2]], Mod[n, #[[1]]]]]/Length@n
      ) &
    ];
  {base, residues} = bases[[1]];
  numbers = Cases[numbers, n_ /; MemberQ[residues, Mod[n, base]]];
  AppendTo[cover, base];
  lcm = LCM[lcm, base];
  Print@base
  ];
 cover
 ]

It solves 8 bits in no time with the following 6 bases:
{12, 13, 7, 11, 5, 8}

16 bits takes 6s and results in the following 6-base cover:
{240, 247, 253, 119, 225, 37}

For the larger cases this approach obviously runs out of memory.
To go beyond 16 bit, I'll need to figure out a way to check for a cover to be complete without actually keeping a list of all numbers up to Nmax (or go and learn about number theory).
Edit: Reduced runtime for 16 bits from 66s to 8s by prepopulating the list of numbers with only those which are not ruled out by the most effective base. This should also significantly improve the memory footprint.
Edit: I added two minor optimisations to reduce the search space. It's not one of the official categories, but with that I found an 8-base cover for 24 bits in 9.3 hours:
{4032, 3575, 4087, 3977, 437, 899, 1961, 799}

As for the optimisations, I am now skipping all bases which divide the LCM of the bases already in the cover, and when I test a base's efficiency I only test it against numbers up to the LCM of that new base and all the bases I already have.

Martin, this is great!!!!! Wow!! So happy to see that a greedy approach produces a reasonable answer. The 8-bit case is not minimal but that is certainly a very, very impressive result for only 0.02s of CPU time. I'm not sure about the 16-bit case, but it's very encouraging that you've found an answer with only 6 bases. Nice work!

@ToddLehman I don't know if you saw my first solution before I edited it with the greedy one. (Have a look at the edit history if you didn't.) There I was just picking bases by their general hit/miss ratio until I had a complete cover. That yielded 8 bases for 8 bits and 29 bases for 16 bits. :D

I just ran a test of your 6-base set over the the range n ∈ [0,10⁸] (notably outside the set's defined range of operation) and was happy to see that it still achieves 99.946539% accuracy on that range. That is, up to 10⁸, only 1 non-square in every 1870 so sneaks by without being ruled out by this test. And up near 2⁶⁴ range, it's still about 99.944% accurate, which is remarkable. I imagine it never gets worse than about 99.94% as n goes to infinity.

@ToddLehman Thanks for the tests! :) I wonder what people with actual number theory knowledge might come up with. I have a couple of ideas to speed it up, so I could go to 24 bits, but I think I need to focus on getting my own next challenge on track.

Interesting: 240 = 2⁴ x 3 x 5; 247 = 13 x 19; 253 = 11 x 23; 119 = 7 x 17; 225 = 3² x 5²; and 37 is prime. The set of prime numbers that are factors of one or more bases are: { 2, 3, 5, 7, 11, 13, 17, 19, 37 } — e.g., all primes up to 19, with 37. Good luck with your next challenge!

@ToddLehman There's a 24-bit cover for you. I was already wondering if I could make use of the prime factors, but I haven't come up with the decent heuristic yet. All I could do is improve the order in which bases are tested, but I'm not sure yet when I could abort that.

Martin — Thanks for updating with the 8-base cover for 24 bits. That is very nice. Interestingly, again, the prime factorizations of the bases include a nice set of small primes: 4032 = 2 x 2 x 2 x 2 x 2 x 2 x 3 x 3 x 7; 3575 = 5 x 5 x 11 x 13; 4087 = 61 x 67; 3977 = 41 x 97; 437 = 19 x 23; 899 = 29 x 31; 1961 = 37 x 53; 799 = 17 x 47. I am going to run a test to see how much faster, on average, this set of bases is than computing the square root and squaring it. It really comes down to division/modulus speed vs. square root hardware speed.

p.s. For some reason, I'm having trouble tagging you as @Martin Büttner when replying.

@ToddLehman You don't need to tag me in my own posts as I will be notified anyway. That's why SE disables the autocompletion until there are comments from multiple users, where it might make sense to address the OP specifically.

Timings: For the interval [0,2²⁴), this set of bases is 47% faster than hardware square root on my system. For the interval [2⁶⁴-10⁹,2⁶⁴), it is 55% faster. In the former range it is of course 100% perfect. In the latter range it is still correct 99.999787% of the time, and in the remaining 0.000213% of the time (1 chance in ~470000) falling back to hardware square root is quite acceptable.

The reason for my curiosity about quadratic residue testing, by the way, is because there exists an extremely simple and remarkably efficient factorization method which uses a squareness test in a tight loop, and I've been curious how much possible it is to speed up that test: http://wrap.warwick.ac.uk/54707/1/WRAP_Hart_S1446788712000146a.pdf

Just found a 9-base cover for 28 bits: { 15840, 15827, 16211, 12549, 14911, 15111, 9869, 14647, 16043 }. Runtime was 36.5 minutes, using a C program optimized to do evaluate fitness using packed bitwise operations using greedy algorithm. This 9-base set is a perfect cover for numbers less than 2²⁸, and is 99.999983% accurate for numbers up in the 2⁶⁴ range.

source: Stack Exchange

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

sort: votes


text:
Fill the Screen with Wang Tiles
It has been proven that the following 13 square Wang tiles always tile the plane aperiodically. This means that when the squares are arranged in a grid with all neighboring sides the same color, a translation of the pattern will never match up with itself.

We'll represent each tile textually by a 3×3 grid filled with spaces at the center and corners, and the numbers 1 through 5 instead of the colors red, green, blue, yellow, grey, at the edges:
 2      2      2      1      1      1      4      3      2      2      4      3      2
1 2    1 3    2 3    2 1    3 1    3 2    4 4    4 4    4 5    4 5    5 5    5 5    5 4
 3      2      3      2      3      2      1      2      1      4      1      2      2

Goal
Your task is to write a program that takes in a width and height and outputs a valid Wang tile grid with those dimensions. A valid tiling is one in which all the adjacent tile edges have the same color (or number). The smallest program in bytes wins.
Your input should come from stdin or command line arguments and output should go to stdout. The exact input format can be anything reasonably obvious, like >>> wangtiler 3 2. The width and height are always positive integers.
Example (width = 3, height = 2)
Notice that when we layout the textual tiles the neighboring edges form necessary redundant pairs of digits:
 1  2  1
2 11 22 1
 2  3  2
 2  3  2
4 55 55 4
 1  2  2

(This is NOT the proper output format.)
We can compress these horizontally and vertically to get:
 1 2 1
2 1 2 1
 2 3 2
4 5 5 4
 1 2 2

This compressed format is the proper output format you must use. The odd numbered lines must include their trailing space.
Graphical Bonus
Instead of having any textual output, your program may output an image of the tiled grid. The graphical tiles must be made up of four 45-45-90 triangles arranged in a square and use five easily distinguishable colors like the tiles above. The black borders are not required. The graphical tiles must be at least 32×32 pixels in size. No "compression" is applied to them.
Example bonus image: (same grid as example above)

The bonus is worth minus 150 bytes.
Notes

You must use this set of 13 tiles.
Tiles may not be rotated.
Tiles may appear any number of times (including none at all).
You may assume a valid tiling with any dimensions is possible.

I suppose tiles cannot be rotated?

@MartinBüttner No. You must use the set of 13 tiles provided exactly as they appear.

Is there a limit to how many times you can use each tile? I see in your example you used one tile twice.

@TeunPronk Nope. Use them however many times you want (of course you may be forced to use more of some to properly match the edges).

@Calvin'sHobbies Is it safe to assume there is always a possible solution?

@TeunPronk Yes. I don't quite know the math behind it but they are definitely able to fill an infinite plane, so all finite planes are possible.

Fun fact: the current record is 11 tiles, which is also optimal. Source

GolfScript, 200 characters
~\:W*):R;1,{)\:C"=QCy_~{MTKAis]?OyJE?~WvM"[64 2400]{base}/@{>}+,{:T;[C,W<!{C W~)=T 64/^8/8%}*C,W%0>{C-1=64/T^8%}*]0-!},1<.!!{1,+}*+.,R<}do);W/.0={' '\512/8%`}%n@{.[.0=8%\{' '\64/8%}/n]\{' '\8/8%`}%n}/

ASCII version with no graphic output. Give the input on STDIN - try here. The code uses a plain backtracking approach and fills the space line by line.
Examples:
> 3 2
 1 2 1
2 1 2 1
 2 3 2
5 4 4 5
 2 2 1

> 8 5
 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2
 2 3 2 3 2 3 2 3
5 4 4 5 5 4 4 5 5
 2 2 4 2 2 2 4 2
5 4 5 5 4 5 4 4 5
 2 1 1 2 1 2 1 1
1 3 2 1 2 1 3 2 1
 2 2 2 3 2 2 2 2
5 4 5 4 4 5 4 5 4
 2 1 2 2 1 2 1 2

Graphical Bonus, score 122, 272 characters - 150 bonus
~\:W*):R;1,{)\:C"=QCy_~{MTKAis]?OyJE?~WvM"[64 2400]{base}/@{>}+,{:T;[C,W<!{C W~)=T 64/^8/8%}*C,W%0>{C-1=64/T^8%}*]0-!},1<.!!{1,+}*+.,R<}do);W["P3\n"32W*" "3$,32*n 1n]\{{:^;512:X;16,{[^8%]1$*[^X/8%]31*@.+>[^64/8%]31*++32<}:F%8:X;16,-1%{F}%+}%zip{{+}*{8+2base(;~}%' '*n}/}/

Same basic code with a different output formatter. The output is an image in PPM format (i.e. simply redirect the output to a file image.ppm). The colors are slightly different than the tiles in the question, but clearly distinguishable (1->blue, 2->green, 3->cyan, 4->red, 5->magenta).
16x12 example:

Python (565 - 150 = 415)
Btw... it seems that we can't naively just decide the next tile by the its left and top tile. There's some combination of tiles that will fit each other.
This solution fills in left->right, top->down brute forces through all possible combinations and backtracks if a tile cannot fit in.
For more info about the 13 tile proof: An aperiodic set of 13 Wang tiles
Width and Height are specified by W and H
Red, Green, Blue, Yellow and Noir specified by R, G, B, Y and N
import Image,sys
W,H=map(int,sys.argv[1:])
R=99
G=R<<8
B=G<<8
Y=G+R
N=0
s="RGB";u=32;g=[[0,0]]*W*H;k=f=0
def t(c):i=Image.new(s,(2,2));k=i.load();q=16;k[1,0],k[1,1],k[0,1],k[0,0]=c;return i.resize([64]*2).rotate(45).crop((q,q,q+u,q+u))
while k<H*W:
 z=g[k][1];v=-1;j=k/W;i=k%W
 while z<13:
    l=map(eval,"GGGRRRYBGGYBGGBBRRGYYNNNNYBGBGBGRGRYRGGRRGGBBYYYYNNN"[z::13])
    if(j<1or g[(j-1)*W+i][0][2]==l[0])and(i<1or g[j*W+i-1][0][1]==l[3]):g[k]=[l,z+1];v=1;z=99
    z+=1
 g[k][1]*=(v>0);k+=v
m=Image.new(s,(W*u,H*u))
for e in g:m.paste(t(e[0]),(f%W*u,(f/W)*u));f+=1
m.show()

Output. Not the actual color scheme... cuz too glaring. This might make some interesting interior decor patterns...:

Neopolitan Minecraft...

can you add a bigger picture? i'm curious how it would look

@proudhaskeller Larger image: Imgur. Wallpaper maker: link

This sure looks periodic - what am i missing?

Almost periodic.. example with more contrast here: Imgur

Haskell, 208 bytes
p x|x<2/3=(3!x)3"3212"3
p x=(0.5!x)1"45423"2
f=floor
(k!x)l s m=do{i<-[0,x..];[' ',s!!(2+f(i+x)-f i)]}:do{i<-[0,l*x..];s!!mod(f i)m:" "}:p(k*x)
t n=take$2*n+1
main=do(w,h)<-readLn;putStr.unlines.t h$t w<$>p 1

No searching, just math. Example run: given (8,5) on stdin, outputs
 2 2 2 2 2 2 2 2
4 5 4 5 4 5 4 5 4
 1 2 1 2 1 2 1 2
3 2 3 2 3 2 3 2 3
 2 3 2 3 2 3 2 3
4 5 5 4 4 5 5 4 4
 4 2 2 2 4 2 2 2
4 4 5 4 5 5 4 5 4
 1 1 2 1 1 2 1 2
3 2 1 3 2 1 3 2 3
 2 2 2 2 2 2 2 3

Run online at Ideone

If you ported this to something golfier like Perl, it might beat golfscript, which would be funny.

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


text:
Compress and Decompress sentence using vowel based encryption cipher
The aim is to parse a sentence and compress/encrypt it according to the rules below and then decrypt it using the key:

Remove all letters in a word before the first vowel is encountered. Example: pigeon becomes igeon.
All characters except alphabets should be kept in the sentence including numerals, punctuations, etc. Example: 200-storey building becomes 200-orey uilding.
Generate the shortest key array char[] = {a,b,x,<your data>} and write code to generate the original sentence using this key.

You need to write two functions: encrypt() and decrypt() which works for every sentence minimising the key-size.
Example 1:

Input: The most technologically efficient machine man has ever
  invented is the book. -Northrop Frye-
Output: e ost echnologically efficient achine an as ever invented is e
  ook. -orthrop e-
Example key: {T,m,t,m,h,b,N,F,14,2,5}

Example 2:

Input: "I need your clothes, your boots and your motorcycle. " - The
  T-800 in Terminator 2: Judgment Day
Output: "I eed our othes, our oots and our otorcycle. " - e -800 in
  erminator 2: udgment ay
Example key: {n,y,c,2,b,2,m,T,J,D,15}

Winning Criteria:

Write function encrypt() with input from stdin or file which generates output sentence and a key on stdout or file or memory.
Write function decrypt() with inputs the generated sentence and key from encrypt() and produces the original sentence.
This is code-golf so cumulative size of the two functions should be minimum. In case of tie-breaker, the generated key-size should be minimum.

Is there any specific format for the key array?

You can make key in any format of your choice, there is no rules for generating the key

In your first example, how does the key restore the 'Fry' of 'Frye'?

@githubphagocyte the key format and decoding logic entirely depends on you. You can form key in whatever format suitable for accurate decryption.

missing 'h' in the first example?

Define "vowel". Is y a vowel? How about ü? Or ij in Dutch texts? Or the Turkish dotless i?

Perl5 61 + 30 = 91 122 211
This is based on the same idea as Comperendinous' Haskell answer where the key is indeed the whole cleartext and I cannot see anywhere in the rules that prevent this so kudos to Comperendinous :)
sub encrypt{$k=$_=<>;s/(.*?)\b[^\W\daeiou]+/$1/gi;print$_.$k}
sub decrypt{$i=<>;$_=<>;print}

Perl5 - 91 + 31 = 122
Here the key is slightly larger, but it actually prrduces the cleartext from the chipertext with the key so I find this more kosher.
sub encrypt{$_=<>;$k="s/(.{$+[1]})/\$1$+/;$k"while s/(.*)\b([^\d\Waeiou]+)/$1/i;print$_.$k}
sub decrypt{$_=<>;eval<>;print}

Ungolfed (though  I've changed it to take parameters instead of two lines of text):
sub encrypt {
  my ($str) = @_;
  my $key = '';
  while( $str =~ s/(.*)\b([^\d\Waeiou]+)/$1/i ){
    $key = "\$str=~s/(.{$+[1]})/\$1$2/;$key";
  }
  ($str, $key);
}

sub decrypt {
  my ($str, $key) = @_;
  eval $key;
  $str;
}

Perl5 - 114 + 75 + 22 (shared) = 211
sub encrypt{$_=<>;@k=m/\b$x/ig;push@_,$+[1] while s/(.*?)\b$x/$1/i;print$_.join'',(@_,@k)[map{$_,$_+@k}0..$#k],$/}
sub decrypt{$i=<>;$_=<>;%k=m/(\d+)$x/g;print map{$k{$%++}|(),$_}split//,$i}
$x='([^\d\W\daeiou]+)'

With both functions chipertext is always output/input first, then the key.
Examples:
Input:
The most technologically efficient machine man has ever invented is the book. -Northrop Frye-

Output:
e ost echnologically efficient achine an as ever invented is e ook. -orthrop e-
0Th2m6t31m38m41h61th63b69N77Fry

Input:
"I need your clothes, your boots and your motorcycle. " - The T-800 in Terminator 2: Judgment Day

Output:
"I eed our othes, our oots and our otorcycle. " - e -800 in erminator 2: udgment ay
3n7y11cl18y22b31y35m50Th52T60T73J81D

Ungolfed code:
# credit: http://stackoverflow.com/a/71895/1565698
sub zip {
    my $pivot = @_ / 2;
    return @_[ map { $_, $_ + $pivot } 0 .. $pivot-1 ];
}

my $consonants = '([^\d\W\daeiou]+)';

sub encrypt {
  my $str = <>;
  my @matches = $str =~ m/\b$consonants/ig;
  my @indexes = ();
  while( $str =~ s/(.*?)\b$consonants/$1/i ) {
    push @indexes, $+[1]; # @+ has the match positions starting at 1
  }
  my $key = join('', zip(@indexes, @matches));
  print "$str$key\n";
}

sub decrypt {
 my $str =<>;
 my $key =<>;
 my %map = ( $key =~ m/(\d+)$consonants/g );
 my $index = 0;
 my @result = map{ $map{$index++} || (), $_ } split //, $str;
 print join '', @result;
}

Your output has deleted the numerals from the input viz. T-800 and Terminator 2

@Manav fixed. All 3 versions work correctly with numbers :)

Perl (126+67=193 characters)
Key contains each character removed along with its offset.
Encrypt reads one line from STDIN
Decrypt reads two: first the ciphered string then the key

sub encrypt{$_=<>;s(.)(++$j,$q|=$&=~/[aeiou]/i,$q^=$&eq$",!$q&$&=~/[a-z]/i&&(push@d,($&,$j-1))||print$&)ge;print$/.join',',@d}
sub decrypt{$q=<>,$_=<>;s/(.),(\d+)/substr($q,$2,0)=$1/gie;print$q}

Examples:
(encrypting)
The most technologically efficient machine man has ever invented is the book. -Northrop Frye-
> e ost echnologically efficient achine an as ever invented is e ook. -orthrop e-
> T,0,h,1,m,4,t,9,m,35,m,43,h,47,t,68,h,69,b,72,N,79,F,88,r,89,y,90

"I need your clothes, your boots and your motorcycle. " - The T-800 in Terminator 2: Judgment Day
> "I eed our othes, our oots and our otorcycle. " - e -800 in erminator 2: Judgment ay
> n,3,y,8,c,13,l,14,y,22,b,27,y,37,m,42,T,58,h,59,T,62,T,71,D,94

(decrypting)
e ost echnologically efficient achine an as ever invented is e ook. -orthrop e-
T,0,h,1,m,4,t,9,m,35,m,43,h,47,t,68,h,69,b,72,N,79,F,88,r,89,y,90
> The most technologically efficient machine man has ever invented is the book. -Northrop Frye-

"I eed our othes, our oots and our otorcycle. " - e -800 in erminator 2: Judgment ay
n,3,y,8,c,13,l,14,y,22,b,27,y,37,m,42,T,58,h,59,T,62,T,71,D,94
> "I need your clothes, your boots and your motorcycle. " - The T-800 in Terminator 2: Judgment Day

Ungolfed with comments

sub encrypt{
    # get input
    $_=<>;
    # for each character
    s(.)(
        # increment j
        ++$j,
        # set q to 1 if vowel
        $q |= $&=~/[aeiou]/i,
        # set q to 0 if space
        $q ^= $& eq $",
        # if q==0 and is a letter (consonant, because q=1 if vowel)
        !$q & $&=~/[a-z]/i &&
            # push both the letter and the offset to @d
            (push @d,($&,$j-1))
        # otherwise print
        || print$&
    )ge;
    # print a newline, then @d
    print$/.join',',@d
}
sub decrypt{
    # read a line to $q, and another to $_
    $q=<>,$_=<>;
    # for each [character],[number] in key
    s/(.),(\d+)/
        # add character back into string
        substr($q,$2,0)=$1
    /gie;
    # print deciphered string
    print$q
}

why have you hardcoded $_="s,4,t,5,b,11";. Can you make a generalized solution.

@Manav fixed. Forgot to remove that when posting.

Haskell: 119 = 111 + 8
Since there's no restriction on the key, I'm going agile and not getting any more complex until someone has a shorter answer:

e t=(unwords.map((\(a,b)->filter(not.(`elem`['a'..'z']++['A'..'Z']))a++b).break(`elem`"aeiouAEIOU")).words$t,t)
d(c,k)=k

I can make this at least 6 characters shorter if I import isAlpha from Data.Char. It's part of the standard distribution, so is it allowed?

How do I test this?

Install Haskell, use ghci for a console, paste in the functions (in GHCi you'll need to precede each with let , call as e "200-storey building" and d ("200-orey uilding", "200-storey building"), which is what e should give you.