text:
Visit each drifting tracker
Your job is to replace the battery packs on many floating fish tracking
devices in the shortest time. You must leave your base in the base helicopter
and visit each tracker once, then return to the base.
Finding the optimum route is known to be hard, but there is an additional
difficulty! Each tracker has a drift velocity (which will be assumed to be a
constant for the day).

This is the standard travelling salesman problem with the added challenge of moving nodes. It should be easy to find a valid tour. The primary challenge is in developing an algorithm to find a near-optimal tour. I predict that it will not be possible to find a perfect tour with the current N=300 (but I would love to be proved wrong).
Rules
Your program will be supplied with a string of tracker data on STDIN or via a
command line argument. You should find a route that visits each tracker exactly
once and returns to base. The output should be a white space separated list of
tracker ID:time pairs.

Position is given in Centimetres (cm).
Time is measured in seconds starting with t=0.
Velocity is given in cm/sec.
Each tracker ID is 1 to 8 upper case letters.
The base with ID "BASE" is located at (0,0).
All number values for input and output use signed integers.
The input is one or more white space or slash separated trackers.
Each tracker will have ID:x,y,vx,vy format (eg: A:566,-344,-5,11)
At time t, a tracker will be at (x+vx*t, y+vy*t).
The helicopter must never exceed 5000 cm/sec speed (180 km/hr).
The output should be white space separated visits in time order.
Each visit should be in ID:time format (eg: A:5723)
The last visit in your output must be the base (eg: BASE:6120)
If more than one tracker is at the same position, it takes zero time to move
between them.
The standard loopholes are forbidden.

Example dataset
A:77000,88000,-120,80 B:52000,-12000,0,-230 C:-140000,-23000,-270,110

Example non-optimal solution:
A:30 B:60 C:120 BASE:160

Note that A:30 B:60 C:120 BASE:130 would be invalid because the helicopter would
have to fly at 17268 cm/sec to get back to base in 10 seconds.
Test dataset
AA:-164247,-378265,182,113
AB:-1494514,-385520,-25,80
AC:-744551,832058,-13,-123
AD:-930133,1598806,97,177
AE:-280777,-904936,-48,305
AF:-855362,-10456,-21,-89
AG:880990,154342,175,-100
AH:-319708,-623098,172,-17
AI:620018,-626908,-19,-164
AJ:-990505,164998,18,-120
AK:379998,310955,191,59
AL:-977441,-130531,107,-234
AM:-766893,14659,162,-198
AN:-502564,-95651,261,306
AO:661306,-98839,231,263
AP:-788211,254598,24,-249
AQ:851834,-1004246,-45,75
AR:698289,-965536,-8,-134
AS:-128295,701701,180,-241
AT:1423336,1359408,-6,173
AU:445274,-527619,231,319
AV:358132,-781522,26,-132
AW:736129,807327,0,-137
AX:-174581,-337407,133,180
AY:-1533760,-215500,144,-111
AZ:-383050,82658,221,-14
BA:-1650492,548674,89,-63
BB:54477,-906358,440,181
BC:891003,623700,326,102
BD:-393270,1732108,155,-97
BE:411090,-859170,93,163
BF:554962,-298575,480,-100
BG:-695530,475438,244,283
BH:93622,-958266,153,-127
BI:-403222,389691,323,329
BJ:1585132,98244,-156,71
BK:713912,484912,158,97
BL:-1612876,317391,-5,-131
BM:-725126,-320766,30,-105
BN:-76091,-381451,-172,95
BO:-483752,970905,16,-170
BP:1585890,91873,-173,-19
BQ:-815696,-342359,-64,-121
BR:-129530,-606673,-66,-94
BS:-339974,-561442,-35,271
BT:1277427,1258031,13,-5
BU:1246036,-743826,144,-200
BV:494745,-522944,211,309
BW:776786,586255,6,-146
BX:-847071,-792238,-142,-199
BY:748038,863976,6,-109
BZ:-667112,634959,221,-174
CA:888093,900097,-107,-56
CB:113938,-1031815,-167,134
CC:-626804,504649,2,-151
CD:866724,941177,311,221
CE:-1632084,-1957347,38,116
CF:774874,804277,-4,-152
CG:468675,-239063,437,-141
CH:-1352217,-388519,-86,70
CI:-1006,921538,-6,-179
CJ:-1866469,68979,-1,133
CK:-1036883,1962287,124,-62
CL:760226,858123,478,56
CM:764838,493113,-27,-155
CN:-642231,-387271,48,198
CO:430643,646456,8,-138
CP:268900,-82440,294,-114
CQ:-1518402,-1782748,123,62
CR:5487,980492,-30,-151
CS:-749712,494682,-1,-113
CT:-1144956,124994,84,120
CU:-1855045,-612779,30,-35
CV:416593,-57062,-67,-140
CW:-1970914,-1984034,-27,153
CX:-606767,629298,-49,-144
CY:-792900,-696850,0,-123
CZ:1561820,-450390,37,21
DA:579688,355017,-186,-153
DB:1178674,1247470,-86,-54
DC:483389,-837780,321,27
DD:468021,-992185,20,253
DE:-38126,-386917,270,250
DF:707678,189200,-59,-179
DG:-1428781,1326135,-29,-148
DH:-1943667,1645387,22,140
DI:-399820,626361,29,-132
DJ:-2657,170549,94,-169
DK:-331601,917405,104,157
DL:1965031,350999,158,-114
DM:902640,986090,-66,-140
DN:540679,-544126,15,-121
DO:-524120,411839,-48,-120
DP:-134995,-876166,191,-128
DQ:359872,-991469,-164,-186
DR:-186713,-309507,14,-86
DS:1846879,-585704,133,64
DT:169904,945363,298,70
DU:-218003,-1001110,-70,109
DV:316261,266341,-63,-89
DW:551059,55754,-4,-94
DX:-514965,305796,304,-100
DY:162176,485230,-90,83
DZ:675592,-1508331,119,-20
EA:656886,38516,257,-111
EB:-201090,678936,5,-161
EC:-920170,-503904,-8,158
ED:-728819,-401134,-83,154
EE:-611398,-320235,-5,-102
EF:-612522,-259240,14,-154
EG:662225,-808256,478,165
EH:-468284,-720421,234,316
EI:-958544,-161691,-12,-97
EJ:839898,-631917,-25,-159
EK:745130,598504,-72,132
EL:412250,-456628,13,-104
EM:-737096,374111,172,35
EN:726052,-385153,-45,31
EO:-888906,-495174,24,-170
EP:-518672,-685753,-14,-102
EQ:440153,-211801,-46,-180
ER:464493,-1637507,-3,154
ES:701248,-512422,-33,-83
ET:-795959,426838,-29,-117
EU:307451,978526,445,124
EV:800833,66796,15,-176
EW:-623452,299065,-30,-117
EX:15142,-363812,445,245
EY:-701669,-556515,-8,-136
EZ:-1772225,890097,-140,-104
FA:-948887,-882723,-11,-157
FB:387256,-128751,151,7
FC:1066595,-641933,31,-23
FD:-823274,-812209,-67,-172
FE:923612,536985,21,-123
FF:-886616,-808114,-26,-153
FG:411924,-518931,-7,-138
FH:945677,-1038311,174,-59
FI:913968,81871,-5,-139
FJ:625167,708120,-44,-90
FK:-405348,893926,-10,-93
FL:-58670,415334,170,-155
FM:326285,671439,426,-237
FN:-775332,-81583,4,-164
FO:280520,360899,2,-150
FP:-406095,133747,26,170
FQ:-990214,-342198,30,-112
FR:938869,801354,397,198
FS:-7527,36870,-23,-111
FT:999332,-956212,143,16
FU:-86215,792355,-49,-87
FV:144427,378536,-4,-136
FW:-786438,638084,28,-77
FX:903809,903424,-102,-132
FY:-36812,-126503,16,-159
FZ:-1083903,1001142,-29,-110
GA:857943,-120746,135,-3
GB:545227,-151166,239,127
GC:-356823,674293,106,90
GD:977846,1003667,-53,106
GE:-866551,180253,-1,-170
GF:-688577,289359,-24,-161
GG:-256928,-481626,169,109
GH:590910,829914,25,-170
GI:568114,735446,-34,-172
GJ:1756516,-655660,140,138
GK:-1683894,-1417741,-163,-84
GL:-201976,-703352,201,217
GM:-271187,-836075,-24,-141
GN:809929,793308,70,324
GO:-403617,58364,432,-191
GP:-94316,227063,148,28
GQ:-930345,1587220,-129,-142
GR:-433897,58058,-75,255
GS:-780984,114024,-12,-160
GT:-403102,-1425166,158,-84
GU:-449829,-414404,-27,-125
GV:556480,72387,-34,306
GW:-959629,326929,327,-91
GX:250741,-992373,94,-121
GY:702250,1612852,-41,38
GZ:853191,857773,-62,-105
HA:674500,-225890,7,-152
HB:-1890026,-179534,-23,49
HC:398363,681200,31,-26
HD:-1896372,113239,-51,25
HE:599213,137473,10,-31
HF:-34537,750768,-18,-179
HG:-959544,-430584,-33,-117
HH:1283773,1606578,-8,-80
HI:-866804,108513,180,-74
HJ:765654,115993,23,-22
HK:554000,130015,18,-32
HL:-470089,-407430,38,191
HM:366977,556677,18,-134
HN:175829,545309,29,-146
HO:-263163,-235953,3,-169
HP:727495,567716,6,-135
HQ:121304,-9150,81,-157
HR:-1789095,-471348,-73,-9
HS:-799974,819873,51,-64
HT:-985175,1774422,70,-10
HU:516368,-227142,-33,-117
HV:655503,350605,-6,-92
HW:733506,-1967066,197,-62
HX:1339705,-1227657,-195,44
HY:-384466,-1932882,7,-93
HZ:-394466,-459287,132,95
IA:120512,-1673367,28,-167
IB:1294647,-1112204,35,133
IC:883230,734086,144,54
ID:-95269,435577,30,148
IE:-378105,-1147004,-6,190
IF:366040,-132989,339,-61
IG:-397775,-410802,-1,-84
IH:849353,-181194,-98,45
II:774834,-56456,-177,21
IJ:-441667,576716,-51,-82
IK:-309799,-673582,-34,-99
IL:605784,-903045,-179,103
IM:-379218,-958590,-6,262
IN:982984,947942,212,-28
IO:-477749,-472771,474,44
IP:-1381284,-1273520,131,139
IQ:672901,1298275,-116,150
IR:-816582,-693425,121,-265
IS:809060,-66216,-45,-165
IT:655913,723612,6,-102
IU:70578,-546308,496,219
IV:558122,41452,-20,-103
IW:237612,-1605017,154,170
IX:-1120980,-471873,-181,-134
IY:-1385384,36137,-14,15
IZ:1401932,-1692315,103,115
JA:1339559,1534224,123,46
JB:-963572,-554932,-13,-153
JC:1422496,-213462,-97,-63
JD:-74743,-909157,277,273
JE:-1364398,911720,185,-19
JF:831273,-645419,-61,-147
JG:-308025,-297948,-59,-107
JH:-737466,-424236,419,219
JI:234767,971704,375,89
JJ:-715682,-871436,395,-54
JK:-296198,-466457,11,227
JL:277311,-661418,27,-124
JM:113477,-763303,-61,-142
JN:198929,881316,358,67
JO:864028,-1735917,-168,-162
JP:193352,-46636,12,-171
JQ:-374301,967915,-27,-98
JR:-900576,1585161,-14,-154
JS:-855414,-201048,24,-150
JT:473630,412948,-80,68
JU:-358039,-730839,-18,47
JV:677652,-670825,-63,-146
JW:536063,-734897,-86,57
JX:344532,-594945,143,230
JY:218390,42085,406,-154
JZ:222495,-933383,440,-29
KA:993576,490730,448,13
KB:1383947,-1637102,-146,-175
KC:181730,-314093,-20,47
KD:1400934,502742,-77,-126
KE:1239862,1152873,144,102
KF:-156867,290487,5,-92
KG:947301,958346,-12,-124
KH:-1873578,815339,194,167
KI:1181091,882850,89,-122
KJ:-825910,-452543,369,9
KK:548963,-358292,390,117
KL:-940596,-200000,125,296
KM:463530,905548,-70,-95
KN:-7507,263613,-7,-145
KO:172069,-457358,-40,-113
KP:-206484,-214043,172,-4
KQ:620049,1844897,-158,192
KR:-988657,612294,452,-125
KS:-802234,611144,-34,-178
KT:231136,-858200,123,129
KU:1557166,943150,105,114
KV:-229389,-440910,-71,123
KW:-135216,1346978,15,136
KX:-43852,521638,-38,279
KY:112655,441642,-8,-105
KZ:525746,-216262,8,-124
LA:-985825,-345745,33,187
LB:-839408,-319328,-6,-136
LC:-12208,1899312,-168,149
LD:156476,-902318,69,325
LE:976731,-427696,310,165
LF:-809002,-255961,312,235
LG:-899084,484167,5,57
LH:-748701,426117,256,-21
LI:-711992,148901,-49,24
LJ:-519051,-440262,22,-105
LK:-310550,283589,88,151
LL:244046,-1751273,5,29
LM:1350149,-1524193,-96,-158
LN:-706211,-585853,-63,-122

Verifier
A program similar to the following verifier will be used to check the answers.
You can use this program to check your answers before posting.
# PPCG: Visiting each drifting tracker
# Answer verifier for Python 2.7
# Usage: python verify.py infile outfile [-v]
# Infile has the given input string. Outfile has the solution string.
# v1.0 First release.

import sys, re
VERBOSE = ('-v' in sys.argv)
fi, fo = sys.argv[1:3]

def error(*msg):
    print ' '.join(str(m) for m in ('ERROR at:',) + msg)
    sys.exit()

indata = open(fi).read().strip()
trackdata = [re.split('[:,]', node) for node in re.split('[ /]', indata)]
trackers = dict((node.pop(0), map(int, node)) for node in trackdata)
shouldvisit = set(trackers.keys() + ['BASE'])

visittexts = open(fo).read().split()
visitpairs = [node.split(':') for node in visittexts]
visits = [(label, int(time)) for label,time in visitpairs]

fmt = '%10s '*5
if VERBOSE:
    print fmt % tuple('ID Time Dist Tdiff Speed'.split())
prevpos = (0, 0)
prevtime = 0
visited = set()
for ID, time in visits:
    if ID in visited:
        error(ID, 'Already visited!')
    tdiff = time - prevtime
    if tdiff < 0:
        error(ID, 'Time should move forward!')
    if ID == 'BASE':
        newpos = (0, 0)
    else:
        if ID not in trackers:
            error(ID, 'No such tracker')
        x, y, vx, vy = trackers[ID]
        newpos = (x+vx*time, y+vy*time)
    if newpos == prevpos:
        dist = speed = 0
    else:
        dist = ((newpos[0]-prevpos[0])**2 + (newpos[1]-prevpos[1])**2) ** 0.5
        if tdiff == 0:
            error(ID, 'Helicopters shouldn\'t teleport')
        speed = dist / tdiff
        if speed > 5000:
            error(ID, 'Helicopter can\'t fly at', speed)
    if VERBOSE:
        print fmt % (ID, time, int(dist), tdiff, int(speed))
    visited.add(ID)
    prevpos = newpos
    prevtime = time

if ID != 'BASE':
    error(ID, 'Must finish at the BASE')
if visited != shouldvisit:
    error((shouldvisit - visited), 'Not visited')

print 'Successful tour in %u seconds.' % time

Scoring
Your score will be your final time in seconds. Lower is better.
The winner will be the answer with the fastest time on the test dataset after
the return to base. In the result of a tie, the earliest entry will win.
Please post solutions with a "Language, Score: NNN" title, the code, and the
output solution string (with several visits per line prefered).

If you know of any literature that mentions this variant of the travelling salesman problem, I would be grateful for a pointer.

A quick search yields http://www.cs.virginia.edu/~robins/papers/The_Moving_Target_Traveling_Salesman_Problem.pdf , I didn't read it in depth but one interesting thing is that they provide a proof that In any optimal Moving-Target TSP tour, the pursuer must always move at maximum speed.

Of course perhaps I shouldn't have posted that as I'm sure any implementation if their algorithm would easily beat mine :P

Is it guaranteed that there's always a solution? If a tracker moves away from the base at a higher speed than the helicopter, you could never reach it. Would it be a valid assumption that no tracker moves faster than the maximum speed of the helicopter?

@RetoKoradi, The helicopter always can move faster than the trackers. There is a solution to the test dataset.

Thanks. Yes, I didn't doubt that there's a solution for the test dataset. But I figure that answers should work for all legal inputs, not just this one. That's why I wanted clarification on the range of tracker speeds. I did a student project on a traveling salesman type problem once, and found a nifty approach in the literature that worked very well to find good solutions. But of course the targets weren't moving...

Python, Score: 20617 17461
I do not have much experience with these types of problems and don't really know what the best known methods are, but I used a method which I've had moderate success with in the past and I'm interested to see how it compares to other answers.
from __future__ import division
from math import *
import itertools

class Visitor:
    def __init__(self,data):
        self.trackers = self.parse(data)
        self.weights = {}
        avg = 0
        for key in self.trackers:
            x,y,vx,vy = self.trackers[key]
            w = hypot(vx,vy)**2
            self.weights[key] = w
            avg += w
        avg /= len(self.trackers)
        for key in self.weights:
            self.weights[key] += avg

    def parse(self,data):
        result = {}
        for line in data.split('\n'):
            id,vars = line.split(':')
            x_str,y_str,vx_str,vy_str = vars.split(',')
            result[id] = (int(x_str),int(y_str),int(vx_str),int(vy_str))
        return result

    def convert(self,path,final):
        result = ""
        total_time = 0
        for (id,time) in path:
            total_time+=time
            result += "%s:%s "%(id,total_time)
        return result + "BASE:"+str(final)

    def time_to(self,target,begin,offset=0):
        bx,by,dx,dy = begin
        tx,ty,vx,vy = target
        bx+=dx*offset
        by+=dy*offset
        tx+=vx*offset
        ty+=vy*offset

        t = 0
        for inter in [1000,100,20,10,4,1]:
            speed = 5001
            while speed > 5000:
                t += inter
                cx,cy = tx+vx*t,ty+vy*t
                speed = hypot(bx-cx,by-cy)/t
            if speed == 5000:
                return time
            t -= inter
        return t+1

    def path_initial(self):
        print 'Creating Initial Path'
        path = []
        tracks = self.trackers.copy()
        remaining = self.trackers.keys()
        px,py = 0,0
        distance = 0

        def score(id):
            if len(remaining) == 1:
                return 1
            t = self.time_to(tracks[id],(px,py,0,0))
            all_times = [self.time_to(tracks[id],tracks[k],t) for k in remaining if k != id]
            return t*len(all_times)/sum(all_times)/self.weights[id]

        while remaining:
            print "\t{0:.2f}% ".format(100-100*len(remaining)/len(tracks))
            next = min(remaining,key=score)
            t = self.time_to(tracks[next],(px,py,0,0))
            path.append((next,t))
            for k in tracks:
                ix,iy,ivx,ivy = tracks[k]
                tracks[k] = (ix+ivx*t,iy+ivy*t,ivx,ivy)
            px,py = tracks[next][:2]
            remaining.remove(next)

        return path

    def path_time(self,ids):
        path = []
        total_time = 0
        tracks = self.trackers.copy()
        px,py = 0,0
        distance = 0
        for i in ids:
            t = self.time_to(tracks[i],(px,py,0,0))
            path.append((i,t))
            total_time += t
            for k in tracks:
                ix,iy,ivx,ivy = tracks[k]
                tracks[k] = (ix+ivx*t,iy+ivy*t,ivx,ivy)
            px,py = tracks[i][:2]
        return path,total_time+int(hypot(px,py)/5000+1)

    def find_path(self,b=4):
        initial = self.path_initial()
        current_path,current_time = self.path_time([c[0] for c in initial])
        pos = None
        last_path = None
        last_time = None

        count = 1
        while last_path != current_path:
            print 'Pass',count
            best_path,best_time = [c[0] for c in current_path],current_time
            for i in range(len(current_path)-b):
                print "\t{0:.2f}% ".format(100*i/(len(current_path)-b))
                sub = best_path[i:i+b]
                for s in itertools.permutations(sub):
                    new = best_path[:]
                    new[i:i+b]=s
                    npath,ntime = self.path_time(new)
                    if ntime < best_time:
                        best_path = new
                        best_time = ntime

            last_path,last_time = current_path,current_time
            current_path,current_time = self.path_time(best_path)
            count += 1
        return self.convert(current_path,current_time)

import sys
in_fname,out_fname = sys.argv[1:3]
with open(in_fname) as infile:
    visitor = Visitor(infile.read())
s = visitor.find_path()
print s
with open(out_fname,"w") as file:
    file.write(s)

Firstly note that this always tries to maximize the speed between nodes, getting as close to 5000 cm/s as an integral value allows. I don't know if this is necessarily optimal, but removing a degree of freedom obviously makes things much simpler.
The initial step is to create an path by simply choosing one target after another. In this decision each target is weighted negatively by how far the target is from the current position and weighted positively by the average distance from the target to all the remaining possible nodes. This way it tries to go for targets that are closer to it relative to other nodes.
Once it has created an initial path, it loops through it, taking every consecutive b nodes and testing the new path time for every permutation of these nodes.* It repeats this process until doing so makes no change to the path.
*The default value of b is 4, however the value given as my score is my result for running it with b=6. I may run it with higher values and update my score accordingly later.
Edit:
I made a small modification to the deciding process of the initial path which now weights faster targets as higher priority. This seems to be a very significant improvement.

To run it simply use
visit.py infile.txt outfile.txt

(I would also suggest using pypy or something as it does take some time to run)
Example output:
FS:8 JY:58 CP:86 FB:110 IF:113 CG:149 BF:173 KK:179 BV:209 AU:218 IU:276 KC:314 EX:319 DE:340 IO:414 EH:445 BS:475 HZ:482 HL:514 JH:528 KJ:563 EE:577 EF:584 CN:601 LF:634 AM:645 GS:680 KL:693 GE:705 AP:725 HI:734 GW:775 CX:828 KR:836 EM:858 LH:871 BZ:890 IJ:896 BG:945 BO:959 FK:970 JQ:984 KX:1049 CR:1061 BI:1078 CI:1089 ID:1117 HF:1128 AN:1191 DX:1211 KF:1213 AZ:1238 KN:1257 GO:1324 HQ:1338 JP:1351 LD:1387 JD:1407 EQ:1424 BB:1500 JZ:1580 DC:1621 EG:1733 LE:1813 BJ:1901 KD:1911 FM:1934 AO:1977 CL:2152 KU:2195 FR:2206 CD:2270 KE:2282 EU:2333 JI:2380 JN:2412 DB:2436 DT:2450 GN:2553 AT:2646 JA:2708 BC:2860 KA:2988 DL:3098 GJ:3165 DS:3201 EA:3353 AG:3385 GA:3418 GB:3504 KI:3543 IN:3638 IC:3708 BK:3737 AK:3811 KG:3854 BY:3882 JX:3920 GL:3988 AA:4007 DD:4018 CO:4040 GI:4053 HM:4059 IH:4063 GG:4072 HN:4100 KP:4156 EN:4164 CM:4195 FL:4212 AS:4229 DW:4250 IV:4267 DJ:4302 DF:4314 AH:4338 HU:4352 EL:4393 ER:4403 HX:4419 FG:4447 JL:4464 JV:4487 AV:4506 AI:4518 JF:4531 EJ:4567 DP:4589 GX:4610 AR:4619 BH:4649 JJ:4760 IW:4839 EV:4861 FI:4900 JC:4919 KT:4984 BW:5001 HP:5014 HV:5041 HK:5058 HE:5061 GH:5075 BP:5082 CF:5094 AW:5110 IT:5132 DM:5160 GZ:5172 FJ:5204 FX:5211 AX:5298 HC:5315 GP:5358 BE:5441 HJ:5450 FE:5490 IB:5592 CZ:5649 FT:5756 IZ:5804 FH:5877 BU:5992 HW:6080 DZ:6256 GT:6431 LM:6552 KB:6630 IA:6652 IR:6739 JO:6832 HY:6887 DQ:6994 FA:7071 FF:7093 FD:7148 BX:7271 GK:7480 IX:7617 EZ:7938 HD:8064 HB:8115 CH:8125 GQ:8176 AB:8241 DG:8277 BN:8347 IY:8397 FZ:8437 CB:8446 JR:8512 II:8576 BA:8613 IL:8625 DU:8650 AC:8687 CS:8743 CC:8817 AJ:8864 EW:8898 DO:8919 ET:8942 AF:8981 KS:9021 DA:9028 EI:9035 GF:9077 JG:9101 FQ:9133 BR:9154 LB:9193 FN:9225 GU:9235 JS:9249 IK:9251 EP:9261 EY:9308 CY:9314 EO:9370 GM:9407 JM:9422 AL:9536 HO:9650 FY:9731 IS:9782 DN:9847 HA:9859 KZ:9922 LL:9985 ES:10014 FO:10056 FV:10106 KY:10182 DI:10215 DV:10263 EB:10340 CQ:10376 DR:10419 AY:10454 IG:10532 BM:10559 CV:10591 LJ:10594 KO:10616 JB:10820 LN:10903 HG:10947 BQ:10988 BL:11100 CU:11140 CE:11235 FU:11380 JU:11397 FW:11419 KM:11448 JW:11479 CA:11549 HS:11594 AQ:11709 IP:11813 JE:11964 HH:12033 BD:12095 BT:12223 GC:12376 LK:12459 DK:12611 KH:12690 AD:12887 GV:12938 KQ:13265 LC:13452 DH:13597 GR:13635 IQ:13748 AE:13763 KW:13967 JK:14080 IM:14145 LA:14232 EK:14290 FP:14344 GD:14395 GY:14472 CT:14532 IE:14650 EC:14771 DY:14807 CJ:14966 ED:15002 CW:15323 HR:15546 LI:15913 KV:16117 JT:16227 LG:16249 HT:16450 CK:16671 FC:17080 BASE:17461

Solution verified. It looks like a competitive result.

Python 3, score = 21553
The program uses a naive greedy approach. It always calculates where should it go to catch a tracker (any of them) in the shortest time possible. Runs in a couple seconds.
import re

class tracker:
    def __repr__(s):
        return str([s.id,s.x,s.y,s.vx,s.vy])

def dist2(e,t):
    return (e.x+t*e.vx-x)**2+(e.y+t*e.vy-y)**2

def closest(x,y,t,tr):
    tp=0
    while 1:
        min_dist2,min_ind=min((dist2(e,t+tp),ind) for ind,e in enumerate(tr))
        if min_dist2<(tp*5000)**2:
            be=tr[min_ind]
            return be.x+(t+tp)*be.vx,be.y+(t+tp)*be.vy,min_ind,t+tp
        tp+=1

tr=[] #x,y,vx,vy,id
with open('tracklist') as f:
    for l in f.read().split():
        a=tracker()
        a.id,data=l.split(':')
        a.x,a.y,a.vx,a.vy=[int(s) for s in data.split(',')]
        tr+=[a]
x,y,gx,gy=0,0,0,0
t=0
r=[] #id,time
while tr:
    x,y,ti,t=closest(x,y,t,tr)
    r+=[(tr[ti].id,t)]
    #print(len(tr),t,tr[ti].id)
    del tr[ti]
    if not tr and r[-1][0]!='BASE':
            a=tracker()
            a.id,a.x,a.y,a.vx,a.vy='BASE',0,0,0,0
            tr+=[a]
print(*[re[0]+':'+str(re[1]) for re in r])

Route:
FS:8 DJ:34 KN:53 GP:70 KF:89 LK:119 BI:149 IJ:181 DI:195 GC:218 EB:247 AS:272 KX:281 HF:301 FU:320 CI:348 CR:362 DK:420 JQ:443 FK:459 BO:475 BG:531 BZ:549 CX:567 KR:586 FW:600 KS:622 LG:638 CS:674 ET:694 GW:719 GF:738 LI:747 AP:769 HI:778 GS:797 KL:812 GE:818 AJ:841 AF:878 LA:903 EI:919 EC:942 AL:953 JS:962 ED:982 FN:990 AM:1026 CN:1028 HL:1061 BS:1078 KV:1094 BN:1105 JK:1119 JH:1127 HZ:1162 EH:1172 DR:1186 HO:1205 KJ:1228 JG:1231 IG:1249 AE:1261 IM:1284 JU:1294 IK:1322 DU:1336 IE:1353 GM:1386 JJ:1421 CB:1444 BR:1472 AH:1511 KO:1546 IL:1594 FG:1611 KT:1631 EL:1636 JW:1645 DD:1671 BE:1685 ES:1706 DN:1732 AI:1765 JV:1770 JF:1802 AQ:1815 EJ:1827 JZ:1880 HX:1916 AR:1976 IW:2005 ER:2027 GX:2045 BH:2054 AV:2087 JL:2118 DP:2166 JM:2229 DQ:2297 GT:2338 LL:2398 IA:2481 JO:2533 KB:2646 LM:2682 HW:2735 DZ:2861 FH:2975 BU:3027 IZ:3034 FT:3137 DC:3170 IB:3193 FC:3242 GO:3285 JC:3319 IO:3339 CP:3382 IF:3442 EA:3444 BB:3459 AG:3484 GA:3518 KD:3574 FE:3601 JD:3616 BP:3629 HJ:3651 BW:3662 HP:3673 HE:3698 HV:3701 HK:3704 DX:3720 CM:3731 FL:3755 EN:3776 DW:3784 IV:3799 KP:3824 FO:3857 FV:3892 KC:3899 DV:3911 II:3933 KY:3934 HN:3978 GG:4004 IH:4016 HM:4021 GI:4027 CO:4039 AZ:4056 AA:4073 GL:4096 GH:4115 CF:4131 AW:4145 IT:4162 DM:4185 GZ:4193 FX:4221 FJ:4229 LH:4250 AX:4272 LD:4289 HC:4312 CA:4340 LF:4376 DB:4444 AN:4505 GD:4548 GV:4616 BD:4660 EK:4681 ID:4755 FP:4831 DY:4845 JE:4885 CT:4943 JR:4995 FZ:5087 BA:5131 IY:5189 AB:5227 CH:5265 HB:5312 HD:5358 EZ:5433 CJ:5598 GQ:5642 DG:5705 AC:5877 DO:5960 EW:5980 CC:6018 IP:6026 DA:6055 AY:6124 EE:6135 BM:6156 LJ:6197 EF:6236 GU:6256 EP:6283 CQ:6313 EY:6319 CY:6334 EO:6357 JB:6420 LN:6456 HG:6495 BQ:6512 CE:6546 CU:6636 BL:6694 CW:6822 HR:6908 IX:7087 GK:7239 BX:7438 FD:7558 FF:7615 FA:7640 LB:7784 FQ:7826 CV:7955 FY:8018 JP:8058 IS:8090 KZ:8136 HQ:8177 EV:8210 HA:8254 FI:8340 HU:8471 DF:8495 EQ:8587 HY:8799 IR:8932 KG:9512 BY:9523 EM:9703 HH:9763 BT:9850 JX:9973 BK:10091 IC:10129 AK:10203 GB:10350 GJ:10436 IN:10463 DS:10577 DL:10789 JY:11049 FM:11146 CG:11213 BF:11363 KA:11783 EG:11886 CL:11966 IU:12107 EU:12210 EX:12271 FR:12418 CD:12652 AO:12901 AU:12976 BV:13022 DE:13154 KE:13262 KU:13303 JA:13366 DT:13620 JN:13804 LE:13831 BC:13879 JI:13914 KK:14134 FB:14869 CZ:14975 KI:15161 CK:15670 HT:15870 GY:15992 JT:16216 BJ:16275 HS:16636 KM:16813 KW:17719 AD:17965 AT:18082 KH:18226 GN:18841 DH:19723 IQ:19760 GR:19948 KQ:20117 LC:20351 BASE:21553

source: Stack Exchange

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

sort: votes


text:
ASCII Art of the Day #4 - Zodiac Signs
We all love horoscopes, don't we? But I have a serious problem in this Horoscope App installed on my Smart Phone that it only displays the icon of the Zodiac Sign for each day's horoscope. Now, I do remember my horoscope, but its hard to remember others' whose horoscope I am interested in.
Challenge
So here is your challenge for an another addition to the ASCII Art of the Day series. Given a date and month input, output the corresponding Zodiac sign in ASCII format as shown below. Each Zodiac Sign is followed after the name and date range (DD MM format) for the zodiac sign.
Aries - 21 03 - 20 04
 .-.   .-.
(_  \ /  _)
     |
     |
Taurus - 21 04 - 20 05
 .     .
 '.___.'
 .'   '.
:       :
:       :
 '.___.'
Gemini - 21 05 - 20 06
._____.
  | |
  | |
 _|_|_
'     '
Cancer - 21 06 - 20 07
   .--.
  /   _'.
 (_) ( )
'.    /
  '--'
Leo - 21 07 - 20 08
  .--.
 (    )
(_)  /
    (_.
Virgo - 21 08 - 20 09
 _
' ':--.--.
   |  |  |_
   |  |  | )
   |  |  |/
        (J
Libra - 21 09 - 20 10
     __
___.'  '.___
____________
Scorpio - 21 10 - 20 11
 _
' ':--.--.
   |  |  |
   |  |  |
   |  |  |  ...
         '---':
Sagittarius - 21 11 - 20 12
      ...
      .':
    .'
'..'
.''.
Capricorn - 21 12 - 20 01
        _
\      /_)
 \    /'.
  \  /   :
   \/ __.'
Aquarius - 21 01 - 20 02
.-"-._.-"-._.-
.-"-._.-"-._.-
Pisces - 21 02 - 20 03
'-.    .-'
   :  :
 --:--:--
   :  :
.-'    '-.

Input

You would be provided two integers corresponding to the date of month and
month of year (in that order) of the birthday.
The date and month will be 1 indexed like in normal calendars.
You can take input form STDIN/ARGV/function arguments or the closest equivalent

Output

Based on what date range the input date falls in, output to STDOUT, the corresponding Zodiac Sign.
You can have upto 4 trailing spaces in each line but no leading spaces that are not part of the output.
You can either write a full program or a named function.

This is code-golf so the shortest code in bytes wins!

Leaderboard
The first post of the series generates a leaderboard.
To make sure that your answers show up, please start every answer with a headline, using the following Markdown template:
# Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:
# Ruby, <s>104</s> <s>101</s> 96 bytes

Related: http://codegolf.stackexchange.com/q/35036/29750

@NinjaBearMonkey I know about it, but that one is more detailed and emphasized on date parsing

I know, I would definitely not consider it a duplicate, but I just thought I would mention it.

Are the trailing spaces on the last lines of Taurus and Pisces intentional?

@Siguza you can anyways have upto 4 trailing spaces. So it does not matter :)

That means I can have less trailing spaces than the example as well, I assume then.

@Siguza Yes, I updated anyways.

Are the simplified date ranges intentional?

@Dennis Yes. I wanted this to be more of ASCII art than Date parsing and partitioning.

CJam, 296 284 272 265 264 bytes
"03½åÙªWË#å¥ÜZ2ò'ýðDc}¦Ð£RÞ5ä<Üå§ÖÞYÏuäOe¤¶è2²|ZëßB«ô¬cm"257b2bSf*Qa/"®=&ðS¢Òpût£Ð`ç«^º,[öÄ©3¸YÝæ[%$>\D£(´õÓÆeUØRHáÄ¡ããîùK½ÊÆÇ:UBÍm¥·fèäBÓEwWOkQq×tÌVfè£g8·¨    q©ñäp-ÁgUÚ´Éõ'>r    Ê#"256bDb"
.\"'()-/:\_|J"f=.+sSN+/l~\K>+=

Try it online in the CJam interpreter.
Idea
We start by joining all twelve signs using the string <SP><LF> as separator. We opt for the zodiac signs not to contain trailing spaces, so this allows to separate them easily.
The joined string is 542 bytes long. 236 of these bytes are spaces, which is almost half of them. We build an array that contains a 1 for every space and a 0 for every non-space. This way, encoding a space will only cost 1 bit.
Removing all spaces from the joined string, we are left with the characters <LF>."'()-/:J\_|. Assigning each of them a value (e.g., the index in this string) between 0 and 12
Finally, we decode the above base 2 and base 13 arrays as byte arrays.
In the final program, for a given input DD MM, we compute (int(MM) + (int(DD) > 20)) % 12, reverse the above process to obtain the array of all zodiac signs and select the proper one.
Code
"03½åÙªWË#å¥ÜZ2ò'ýðDc}¦Ð£RÞ5ä<Üå§ÖÞYÏuäOe¤¶è2²|ZëßB«ô¬cm"

        e# Push the encoded space positions.

257b2b  e# Convert from base 257 to base 2.
Sf*     e# Replace 1's with spaces and 0's with empty strings.
Qa/     e# Split at empty strings.

"®=&ðS¢Òpût£Ð`ç«^º,[öÄ©3¸YÝæ[%$>\D£(´õÓÆeUØRHáÄ¡ããîùK½ÊÆÇ:UBÍm¥·fèäBÓEwWOkQq×tÌVfè£g8·¨ q©ñäp-ÁgUÚ´Éõ'>r    Ê#"

        e# Push the encoded non-space characters.

256bDb  e# Convert from base 256 to base 13.

"
.\"'()-/:\_|J"f=

        e# Replace each digit in base 13 by the corresponding character.

.+s     e# Interleave both arrays to create a string.
SN+/    e# Split at trailing spaces.
l~      e# Evaluate the input from STDIN.
\K>+    e# Add 1 to the month if the day is larger than 20.
=       e# Retrieve the corresponding element from the array.

Ð£RÞ? DERP. . .

Longest golf Lang solution I've ever seen.

CJam, 324 bytes
"%[hÿìs5!zaÆT=ªñ=Û]ÌUMàûÓ»¦f¼³ëµ1þÈUÑyéC4¬u1T9KÍü!+Úøöà&J~âZ®uRtkRÿ+*ÐFeÜPý¤SÙËU7óÎ?LXÝ2D@0¶ÆÀ¡kÚçaçªñÜ§#iµ3L®ó&Ë'iºyè½?JS÷SjS`ösÓò»zjRoaÃIYrµ&M>ÍKaaúcg®Ð\p¨²:LqÜÝ¶o¯ÆkµúÒ4Ezú©æ¼xP»¸¯gd^ßg±>ï ÃºDÎÅ§@3Bßt\<GÒcû)ËûwíUÑdØoiTv>¤&ý°mÊ13ÛUÿØjª¬Ì±(¦¿çÍX4tõãÜÑ*ÃmÜ9ãSÁ3IþÜìÙ,"{_'~>33*32+-}%191bEb428Et"
 \"'()-./:\_a|J"f='a/q~\K>+=

My first attempt. Try it online

Python 2, 961 698 692 687 Bytes
Definitely still going to golf further, just wanted to put an idea down. Now using a dictionary.
a,b=raw_input().split()
b=int(b)
c='.-"-._.-"-._.-'
print{0:c+'\n'+c,1:"'-.    .-'\n   :  :\n --:--:--\n   :  :\n.-'    '-.",2:" .-.   .-.\n(_  \ /  _)\n     |\n     |",3:" .     .\n '.___.'\n .'   '.\n:       :\n:       :\n '.___.'",4:"._____.\n  | |\n  | |\n _|_|_\n'     '",5:"   .--.\n  /   _'.\n (_) ( )\n'.    /\n  '--'",6:"  .--.\n (    )\n(_)  /\n    (_.",7:" _\n' ':--.--.\n   |  |  |_\n   |  |  | )\n   |  |  |/\n        (J",8:"     __\n___.'  '.___\n"+'_'*12,9:" _\n' ':--.--.\n   |  |  |\n   |  |  |\n   |  |  |  ...\n         '---':",10:"      ...\n      .':\n    .'\n'..'\n.''.",11:"        _\n\      /_)\n \    /'.\n  \  /   :\n   \/ __.'"}[[[b-2,11][b<2],b-1][int(a)>20]]

Old method, using interleaving.
d,m=raw_input().split()
m=int(m)
print'.\'  .       --.._  _ _  ".- _ .\n \n  - . _.-\' \'  .   _--     _   _-.\'_\'  .   ..\n:_:. -...\n\n -\n-. "--\n  (-_-._-\'.    ._.\n\n.\n\n\'|/ -_- \\_ (.   -.-  . __|  .\'.  -  _\n )\n \n  \n: _ _\n     . \\. \'( \'   -  \'|._ . . ":/\n \n)|_|\'/-\n  |   _ :_.  .\n(  _ \n)_-_\' _/|\n| \n.-) _)\n _   -:\n |   _  \\"-  _( |_|  -- \'|  __\n. .: ._) \n_ \' _- \n\n\n( _ \n .- :\'\'_ _ \'/-\n|  .. _|.\'  \n    |_ ..        _ \'\n        _|\n  :     |_ .     \'/    \'\\     \n   |\'  :|:   | \n.  \n \n       / . : \' )     -   - \n     \'   -   |       \'     :           \n       | |               \'           - :   | | \\ . \n       /               \'   | . _   .   / . _   _   \n . .   _     \n \'   _           .           \'                                                               (           J             \'           -           -           -           \'           :  '[[m-2,m-1][int(d)>21]::12].rstrip()

Python 2, 565 568 553 bytes
def z(d,m):b="\n "+"  |"*3;c=" _\n' ':--.--.";a="  ...\n      ";print["\      /_)\n \    /'.\n  \  /   :\n   \/ __.'",'.-"-._.-"-._.-\n'*2,"'-.    .-'\n   :  :\n --:--:--\n   :  :\n.-'    '-.",' .-.   .-.\n(_  \ /  _)'+'\n     |'*2," .     .\n '.___.'\n .'   '.\n:       :\n:       :\n '.___.'","._____.\n  | |\n  | |\n _|_|_\n'     '","   .--.\n  /   _'.\n (_) ( )\n'.    /\n  '--'",'  .--.\n (    )\n(_)  /\n    (_.',c+b+"_"+b+" )"+b+"/\n        (J","     __\n___.'  '.___\n"+"_"*12,c+b*3+a+"   '---':","    "+a+".':\n    .'\n'..'\n.''."][m%12-(d<21)]

So I was a bit lazy and decided not to golf this AAotD.
Instead, I decided to let python golf itself.
The above solution was created using the code below:
full_string = """
\      /_)
 \    /'.
  \  /   :
   \/ __.'
*
.-"-._.-"-._.-
.-"-._.-"-._.-
*
...               # The others in this list as well
*
      ...
      .':
    .'
'..'
.''.
"""

# Golf the input string
string_list = full_string.split('*')
# Remove begin and end \n
string_list = [s[1:-1] for s in string_list]
# Remove unnescessary repr characters
golf = repr(string_list).replace(r'\\ ', r'\ ').replace(r'\\/', r'\/').replace(', ', ',')
# Special case for the Aquarius as it's a full duplicate
middle = golf.find('\\n', 50)
end = golf.find(',', middle)
golf = golf[0:middle+2] + "'*2" + golf[end:]
# Special case for the 12 underscores
golf = golf.replace('____________"', '"+"_"*12')
# Replace the three bars and their whitespace
golf = golf.replace('\\n   |  |  |', '"+b+"')
# Replace the bar-cover
cover = '" _\\n\' \':--.--."'
golf = golf.replace(cover, 'c')
# Replaces aries' foot
golf = golf.replace("\\n     |\\n     |'", "'+'\\n     |'*2")
# Replace dots
golf = golf.replace('  ...\\n      ', '"+a+"')
# Remove empty strings and optimize b's
golf = golf.replace('""+', '').replace('b+b+b', 'b*3')

# Surround the lookup table with the function that that prints the correct zodiac sign for the day/month
golf = 'def z(d,m):a="  ...\\n      ";b="\\n "+"  |"*3;c=" _\\n\' \':--.--.";print' + golf + '[m%12-(d<21)]'

This doesn't produce the right output at all.. All of them need to be shifted, and if you go over 20,12 then the list index goes out of range. z(21,1) should produce Aquarius, yet it produces Picses, etc..

@Vioz- Wow, I'm getting sloppy. Thanks, it works properly now.

Perl, 414
Not a lot to do here, just applied dictionary compression:
#!perl -p
/ /;$i=$'%12-($`<21);
$_="cc_
\\ct_s \\c/'ga\\thlh\\/ __ijkee
keej'-.ck'n q:q:qnk'c'-gA k.hkg(_a\\ /a_sm|
m|j .mg oi
 ih'g:chl:chl oij.d__grr _|_|_
'm'jhk-gth_'g (_) ( s'.c/
a'q'jak-g (cs(_)t
c(_.f_b )b/
cc(Jjm__
diao
ddddfbbpm'q-':jcpailci
'.i
i'g";
1while s![a-t]!(split z,"  z
a |a|a|zaaz___z\"-._.-z
A _
' ':--.--.bz.
za z.'z
Az.-z:
zc z
h:alz'.dza..gcz--za| |
z)
za/")[(ord$&)%97]!e;$_=(split A)[$i]

Test me.

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


text:
Non-Palindromic Polyglot Boggle
Introduction
The number 101 is a palindrome, since it reads the same backwards and forwards. The number 105 is not. However, 105 in base eight is written as 151, which is palindromic. On the other hand, 103 is not a palindrome in any base from 2 to 101. Hence, 103 is strictly non-palindromic.
The precise definition is: A nonnegative integer n is strictly non-palindromic if it is not a palindrome in any base between 2 and n-2, inclusive.
The first few strictly non-palindromic numbers are 0, 1, 2, 3, 4, 6, 11, 19, 47, 53, 79, 103, 137, 139, 149, 163, 167, 179, 223, 263, 269... (A016038)
Write a full program that takes a number x from STDIN and prints the xth strictly non-palindromic number. For example, the input 5 would produce the output 4.
Challenge
The challenge is to write multiple (one or more) programs, each solving this task in a different language.
Then, you must put all of the programs in a rectangular grid of characters. The programs can be accessed Boggle-style. That is, go from one character to a neighboring character (including diagonally), never using the same character more than once.
For example, the following grid:
abc
bdc

includes the words abc, ccd, bbad, and bcdb, but not ac, bdd, bcb, or cbbc.
Each program must be found in the grid using these rules. However, you may use the same character in multiple programs.
Score
Your score is the number of characters in the grid, divided by the number of programs. Lowest score wins!
Rules

Two languages are considered different if they usually go by different names, ignoring version numbers. For example, C and C++ are different, but Python 2 and Python 3 are the same.
The characters in the grid must all be from printable ASCII, i.e., from  to ~, code points 20 through FE.
Each program must consist only of printable ASCII, plus newlines. When inserting a program into the grid, replace each newline with a space.

A space in the grid may represent a space in one program and a newline in another.

The grid must be a rectangle.
Not every character needs to be used in a program.

Aren't single digit numbers palindromic? They read the same backwards and forwards.

@RetoKoradi Correct. That's why we only consider bases less than n-1, so there will always be at least two digits.

19x2 = 38, 2 programs, Score: 26 19.5 19
Here is the board:
-:\~{.,><1\b_W%}}g}
1Wq{)_2W{$ase.=,do*

This contains the following programs:
CJam (27 bytes)
Wq~{{)_,2>W<{1$\b_W%=},}g}*

Test it here.
These are the characters of the board used for this code:
   ~{ ,><1\b_W%}}g}
 Wq{)_2W{$    =,  *

GolfScript (34 bytes)
-1:W\~{{).,2>W<{1$\base.W%=},}do}*

Test it here.
These are the characters of the board used for this code:
-:\~{.,><1\b W%}} }
1W {) 2W{$ase.=,do*


text:
XKCD: Keyboard Mash Anomalies
Another XKCD inspired competition.
This one is based on Keyboard Mash.
Given a input string, identify the anomalous characters, assuming that the majority have been typed on a single row of the standard US QWERTY keyboard.
Input strings can contain shifted key strokes, but they will not contain carriage returns (Enter), CTRL/ALT affected characters, spaces, tabs and backspaces (because that would be silly).
The number pad will not be considered as part of the keyboard for this challenge.
The challenge is to output the characters that aren't on the same keyboard row as the majority of individual characters in the single string.  The output should contain each anomalous character only once and no other characters.
In the case of a equal count of anomalous characters across two or more rows, the tie break is determined in this order:

Shortest unique list
Top most row

Input
A string through either STDIN, ARGV or a function parameter
Output
A string to STDOUT or a function return.  It should have each anomalous character only once, but does not need to be ordered.
Examples

Input: FJAFJKLDSKF7KFDJ  Output: 7
Input: ASDF11111 Output: ASDF
Input: lkjrhsDdftkjhrksRjd  Output: rtR
Input: }*3%&2098@$2k234#@$M  Output: }
Topmost row list returned  Input: ASD!@#Vcx  Output: !@#
Shortest unique list returned  Input: ASdf1233qwER  Output: 123
Topmost shortest list returned  Input: 12334QWTTSDFDSXVVBBX  Output: QWT

This is code golf, so shortest entry wins.

CJam, 111 89 88 86 84 83 bytes
la9*~"{}qwertyuiop ;':asdfghjkl ,./<>?zxcvbnm"{_32^}%_'ÿ,^a\S%+{[f&s\e|__|]:,}$0=&

Try it online in the CJam interpreter.
How it works
la9*~     e# Push the input 9 times on the stack.

"{}qwertyuiop ;':<STX>asdfghjkl ,./<>?zxcvbnm"

{_32^}%   e# XOR a copy of each character with 32.
_'<DEL>,^ e# Push a string of all ASCII characters that are missing.
a\        e# Wrap it in an array.
S%+       e# Split the string at spaces and concatenate with the array.
{         e# Sort the chunks according to the following:
  [       e#
    f&s   e# Push the string of characters from the input that are in this chunk.
    \e|   e# If the result is empty, replace it with the input.
    __|   e# Push a copy with duplicates removed.
  ]       e# Collect both strings in an array.
  :,      e# Replace each string with its length.
}$        e#
0=        e# Retrieve the minimum.
&         e# Intersect it with the input.

CJam, 90 88 86 84 83 bytes
This is just a straight forward implementation.
" qwertyuiop[] asdfghjkl;': zxcvbnm<>?,./"_32f^.\_'¦,^\+S%qf{_@--}{},{__&]:,}$0=_&

Try it online here . Pastebin


text:
Isn't It Ironic? A Little Too Ironic?
I made a joke the other day and sent it to some friends. One replied back "I love the irony!" and I looked at it and realized there was some irony in it. But that wasn't the irony she saw - the irony she was was the punchline of the joke, which wasn't ironic in the slightest.
And it got me thinking about a certain other instance that isn't ironic at all. And I have to admit, I love that song.
Have you read it's lyrics before? They're so deep!

An old man turned ninety-eight
He won the lottery and died the next day
It's a black fly in your Chardonnay
It's a death row pardon two minutes too late
And isn't it ironic... don't you think
It's like rain on your wedding day
It's a free ride when you've already paid
It's the good advice that you just didn't take
Who would've thought... it figures
"Mr. Play It Safe" was afraid to fly
He packed his suitcase and kissed his kids goodbye
He waited his whole damn life to take that flight
And as the plane crashed down he thought
"Well isn't this nice..."
And isn't it ironic... don't you think
It's like rain on your wedding day
It's a free ride when you've already paid
It's the good advice that you just didn't take
Who would've thought... it figures
Well life has a funny way
Of sneaking up on you
When you think everything's okay
And everything's going right
And life has a funny way
Of helping you out when
You think everything's gone wrong
And everything blows up in your face
A traffic jam when you're already late
A no-smoking sign on your cigarette break
It's like ten thousand spoons when all you need is a knife
It's meeting the man of my dreams
And then meeting his beautiful wife
And isn't it ironic...don't you think
A little too ironic...and, yeah, I really do think...
It's like rain on your wedding day
It's a free ride when you've already paid
It's the good advice that you just didn't take
Who would've thought... it figures
Life has a funny way of sneaking up on you
Life has a funny, funny way of helping you out
Helping you out

You know what I could really use? I could use a program that would spit out these lyrics. But, just like how this song has nothing ironic in it, you also will not be permitted to use anything ironic in your submission. That means no upper or lowercase i, r, o, n, or c may appear in your program.
The program requires no input, and will output the exact text in the quote. Newlines included, but any trailing whitespace is accidental and you should ignore that. Any punctuation is required.
The usual loopholes are obviously disallowed, and since this is code golf, the lowest score wins.
What would be ironic would be if the restrictions on this make any submission automatically longer than the actual dump of the text.

You are not using spaces consistently after "..." - for example there's both "And isn't it ironic... don't you think" and "And isn't it ironic...don't you think"

By the way, it looks like Alanis Morissette was born on the 1st of June :)

CJam, 922 bytes
0000000: 226d24ae 76dd5d8d d392ac33 f8d0411a e39f4a4d e06683df  "m$.v.]....3..A...JM.f..
0000018: 111b4840 812cd834 74417bdd 80a53e6d 7d821401 8dcca95d  ..H@.,.4tA{...>m}......]
0000030: b89cfb35 4cbab681 8c9388f1 671a4716 4cc4dbb7 bd140682  ...5L.......g.G.L.......
0000048: fe99dbee 429084d0 cd8b1a5e c9b45ad9 84a46cf6 ca92db54  ....B......^..Z...l....T
0000060: bd3946ba 8f1da9d6 7459e9bc 5b355308 11ca8980 93b89bc1  .9F.....tY..[5S.........
0000078: c99970a0 62095d5c 22775afc 9186a457 e560be57 f8802b5e  ..p.b.]\"wZ....W.`.W..+^
0000090: b6d1673a 2801fcca de4aa5f4 dcc1467c 85c2753b 34830614  ..g:(....J....F|..u;4...
00000a8: 98a450c1 0000f7a2 054164dd 03f7b0e1 fcbddaad 65fc061e  ..P......Ad.........e...
00000c0: e3f6ca3f 989db84b fe839256 cdfa77b6 faf437e4 4af60f6b  ...?...K...V..w...7.J..k
00000d8: 4264eabc 7aaceec4 ca8d4bfd 8b9b5c39 fa15d96a 0c36187e  Bd..z.....K...\9...j.6.~
00000f0: 5c220d89 e135beda 1c3b7ea8 1c5a76e5 7c26f929 a5405b1f  \"...5...;~..Zv.|&.).@[.
0000108: 81e4e48c 06139775 66c6d8f1 7be3f55f 70e11e2d f8e68407  .......uf...{.._p..-....
0000120: acce45d9 7b45864b 5c227ffe 3511097f f4df5fec 9fa51d02  ..E.{E.K\"..5....._.....
0000138: ed188eb4 d5f659f0 86ed7ef7 e4fb3d2c ab9b290b 648116db  ......Y...~...=,..).d...
0000150: 50793fea 1aea5dc7 35e40f94 85e8e923 76427675 838b930b  Py?...].5......#vBvu....
0000168: d41f5717 b4da8b45 04319e95 dea4c038 f7a31746 b0c2e427  ..W....E.1.....8...F...'
0000180: 48b7f974 a1a86a11 f1333294 349685f4 c2c19cf3 c2f72aef  H..t..j..32.4.........*.
0000198: e1960cd2 beee3eb0 283f0780 08af8afc 1758b3ca 289f3400  ......>.(?.......X..(.4.
00001b0: 44ede560 ada22ae4 b047cd0f 38c386ca 156544c7 9d1b0f8f  D..`..*..G..8....eD.....
00001c8: fa1a78bc add29de3 d164b548 19a7e766 7ff7a0d7 048b4a97  ..x......d.H...f......J.
00001e0: 5fe076cf ae5c2224 ab1cf23b 54e50911 35775489 deb0c744  _.v..\"$...;T...5wT....D
00001f8: 50958144 c6e5edc8 e72f8bd2 f6ead64d 37d6858a 05838c65  P..D...../.....M7......e
0000210: ddee157c 20a993da 5f2a3366 263d38ed 0e2f39ea 15862e7b  ...| ..._*3f&=8../9....{
0000228: e66426e8 eeb5e1d0 b3a69187 e576c185 c5d818fd 76a933b2  .d&..........v......v.3.
0000240: 1ea9b31a 20030048 81ea5c22 f6ba7e2c 9ab81f9e 5a9802f1  .... ..H..\"..~,....Z...
0000258: 1413edac dbc87a36 94c5a59c d80efd5f 36f70ee5 e6e8c40f  ......z6......._6.......
0000270: c27b3feb 99b18b1c bbe32b4c b080056d 5082ed6c 20135c11  .{?.......+L...mP..l .\.
0000288: 6098307e 9105f9c1 98fbef3c 7c18af20 e3d26dee e551c95b  `.0~.......<|.. ..m..Q.[
00002a0: c438dbd5 08ac18e9 53ee9db8 a9df7950 502e1077 efc23f28  .8......S.....yPP..w..?(
00002b8: fb3e7dee 2d254c2d 5fbd2a47 e0215ace 8a3b06f7 68bd9692  .>}.-%L-_.*G.!Z..;..h...
00002d0: 83e782c9 0f9827a0 0ad637ca d316ceaa 1c35aff6 d14d4024  ......'...7......5...M@$
00002e8: cd5a59b6 30f97e6c 18c6088e 07c17673 3a0b58b1 9bdde15b  .ZY.0.~l......vs:.X....[
0000300: a6f1cad0 ca8e3e8f bb8ffb60 e44867ea eb4a7d57 bebcb540  ......>....`.Hg..J}W...@
0000318: 7d37712d cc16dd7b 0e5b33f4 03dabc21 fae78a91 8df8eac6  }7q-...{.[3....!........
0000330: 3f231dd0 4b6b5c22 c5f1ae77 bc99c3b2 eb96bbf6 da7ab52b  ?#..Kk\"...w.........z.+
0000348: bdf913c6 e55f54cb 105015f2 c76d3cc4 2227ff2c 224b5451  ....._T..P...m<."'.,"KTQ
0000360: 50452232 662d5f65 6c2b2d66 23323435 62343362 220e2426  PE"2f-_el+-f#245b43b".$&
0000378: 2b303132 45474c4d 50515354 575b5d22 34666d32 352c2761  +012EGLMPQSTW[]"4fm25,'a
0000390: 662b2b66 3d27712f 292a                                 f++f='q/)*

The above is a reversible xxd dump. The source code contains way to many unprintable characters for the online interpreter...
The source code is generated by the following program:
q"

It's like rain on your wedding day
It's a free ride when you've already paid
It's the good advice that you just didn't take
Who would've thought... it figures

":X/Xa+'q*"^N$&+012EGLMPQSTW[]"4fm25,'af++f#43b245b'ÿ,"KTQPE"2f-_el+-f=`"'ÿ,\"KTQPE\"2f-_el+-f#245b43b\"^N$&+012EGLMPQSTW[]\"4fm25,'af++f='q/)*"

Here, ^N represents the control character with code point 14.
Verification
$ LANG=en_US
$ xxd -r -ps > gen.cjam <<< 71220a0a49742773206c696b65207261696e206f6e20796f75722077656464696e67206461790a49742773206120667265652072696465207768656e20796f7527766520616c726561647920706169640a497427732074686520676f6f6420616476696365207468617420796f75206a757374206469646e27742074616b650a57686f20776f756c642776652074686f756768742e2e2e20697420666967757265730a0a223a582f58612b27712a220e24262b30313245474c4d50515354575b5d2234666d32352c2761662b2b66233433623234356227ff2c224b545150452232662d5f656c2b2d663d602227ff2c5c224b545150455c2232662d5f656c2b2d6623323435623433625c220e24262b30313245474c4d50515354575b5d5c2234666d32352c2761662b2b663d27712f292a22
$ cjam gen.cjam < song | grep -i IRONIC
$ cjam gen.cjam < song | wc -c
922
$ cjam <(cjam gen.cjam < song) | md5sum - song
3b1a473c910233d91d0e283a43cbcab2  -
3b1a473c910233d91d0e283a43cbcab2  song

Explanation
The code starts by placing a string of characters (the encoded song) on the stack.
'ÿ,        e# Push the string of all characters with code points below 255.
"KTQPE"2f- e# Push "IRONC" by subtracting 2 from each code point.
_el+       e# Concatenate with the lowercase counterparts.
-          e# Remove these characters from the string.
f#         e# Replace each character from the encoded song by its index in this string.
245b43b    e# Convert the resulting array of integer from base 245 to base 43.
"^N$&+012EGLMPQSTW[]\"4fm
           e# Subtract 4 from each code point.
25,'af++   e# Append the lower case letters from a to y to that string.
f=         e# Replace each integer in the base 245 array by the corresponding character.
'q/        e# Split the result at all occurrences of 'q'.
)*         e# Pop the last string (chorus) and insert it between the remaining chunks.

How did you go about creating this?

@corsiKa: I've edited my answer.

i only count 179 bytes. Is something missing?

@steveverrill: Whoops. Looks like I compressed the wrong file (not sure which). Thanks for letting me know.

Ironic, Java, 4009 bytes, 312.49% 256.82% size of original.
publ\u0069\u0063 \u0063lass \u0049\u0072\u006F\u006e\u0069\u0063{publ\u0069\u0063 stat\u0069\u0063 v\u006F\u0069d ma\u0069\u006e(St\u0072\u0069\u006eg[]a\u0072gs){System.\u006Fut.p\u0072\u0069\u006et("A\u006e \u006Fld ma\u006e tu\u0072\u006eed \u006e\u0069\u006eety-e\u0069ght\\u006e"+"He w\u006F\u006e the l\u006Ftte\u0072y a\u006ed d\u0069ed the \u006eext day\\u006e"+"\u0049t's a bla\u0063k fly \u0069\u006e y\u006Fu\u0072 \u0043ha\u0072d\u006F\u006e\u006eay\\u006e"+"\u0049t's a death \u0072\u006Fw pa\u0072d\u006F\u006e tw\u006F m\u0069\u006eutes t\u006F\u006F late\\u006e"+"A\u006ed \u0069s\u006e't \u0069t \u0069\u0072\u006F\u006e\u0069\u0063... d\u006F\u006e't y\u006Fu th\u0069\u006ek\\u006e"+"\\u006e"+"\u0049t's l\u0069ke \u0072a\u0069\u006e \u006F\u006e y\u006Fu\u0072 wedd\u0069\u006eg day\\u006e"+"\u0049t's a f\u0072ee \u0072\u0069de whe\u006e y\u006Fu've al\u0072eady pa\u0069d\\u006e"+"\u0049t's the g\u006F\u006Fd adv\u0069\u0063e that y\u006Fu just d\u0069d\u006e't take\\u006e"+"Wh\u006F w\u006Fuld've th\u006Fught... \u0069t f\u0069gu\u0072es\\u006e"+"\\u006e"+"\"M\u0072. Play \u0049t Safe\" was af\u0072a\u0069d t\u006F fly\\u006e"+"He pa\u0063ked h\u0069s su\u0069t\u0063ase a\u006ed k\u0069ssed h\u0069s k\u0069ds g\u006F\u006Fdbye\\u006e"+"He wa\u0069ted h\u0069s wh\u006Fle dam\u006e l\u0069fe t\u006F take that fl\u0069ght\\u006e"+"A\u006ed as the pla\u006ee \u0063\u0072ashed d\u006Fw\u006e he th\u006Fught\\u006e"+"\"Well \u0069s\u006e't th\u0069s \u006e\u0069\u0063e...\"\\u006e"+"A\u006ed \u0069s\u006e't \u0069t \u0069\u0072\u006F\u006e\u0069\u0063... d\u006F\u006e't y\u006Fu th\u0069\u006ek\\u006e"+"\\u006e"+"\u0049t's l\u0069ke \u0072a\u0069\u006e \u006F\u006e y\u006Fu\u0072 wedd\u0069\u006eg day\\u006e"+"\u0049t's a f\u0072ee \u0072\u0069de whe\u006e y\u006Fu've al\u0072eady pa\u0069d\\u006e"+"\u0049t's the g\u006F\u006Fd adv\u0069\u0063e that y\u006Fu just d\u0069d\u006e't take\\u006e"+"Wh\u006F w\u006Fuld've th\u006Fught... \u0069t f\u0069gu\u0072es\\u006e"+"\\u006e"+"Well l\u0069fe has a fu\u006e\u006ey way \\u006e"+"\u004Ff s\u006eeak\u0069\u006eg up \u006F\u006e y\u006Fu\\u006e"+"Whe\u006e y\u006Fu th\u0069\u006ek eve\u0072yth\u0069\u006eg's \u006Fkay \\u006e"+"A\u006ed eve\u0072yth\u0069\u006eg's g\u006F\u0069\u006eg \u0072\u0069ght\\u006e"+"A\u006ed l\u0069fe has a fu\u006e\u006ey way \\u006e"+"\u004Ff help\u0069\u006eg y\u006Fu \u006Fut whe\u006e\\u006e"+"Y\u006Fu th\u0069\u006ek eve\u0072yth\u0069\u006eg's g\u006F\u006ee w\u0072\u006F\u006eg \\u006e"+"A\u006ed eve\u0072yth\u0069\u006eg bl\u006Fws up \u0069\u006e y\u006Fu\u0072 fa\u0063e\\u006e"+"\\u006e"+"A t\u0072aff\u0069\u0063 jam whe\u006e y\u006Fu'\u0072e al\u0072eady late\\u006e"+"A \u006e\u006F-sm\u006Fk\u0069\u006eg s\u0069g\u006e \u006F\u006e y\u006Fu\u0072 \u0063\u0069ga\u0072ette b\u0072eak\\u006e"+"\u0049t's l\u0069ke te\u006e th\u006Fusa\u006ed sp\u006F\u006F\u006es whe\u006e all y\u006Fu \u006eeed \u0069s a k\u006e\u0069fe\\u006e"+"\u0049t's meet\u0069\u006eg the ma\u006e \u006Ff my d\u0072eams\\u006e"+"A\u006ed the\u006e meet\u0069\u006eg h\u0069s beaut\u0069ful w\u0069fe\\u006e"+"A\u006ed \u0069s\u006e't \u0069t \u0069\u0072\u006F\u006e\u0069\u0063...d\u006F\u006e't y\u006Fu th\u0069\u006ek\\u006e"+"A l\u0069ttle t\u006F\u006F \u0069\u0072\u006F\u006e\u0069\u0063...a\u006ed, yeah, \u0049 \u0072eally d\u006F th\u0069\u006ek...\\u006e"+"\\u006e"+"\u0049t's l\u0069ke \u0072a\u0069\u006e \u006F\u006e y\u006Fu\u0072 wedd\u0069\u006eg day\\u006e"+"\u0049t's a f\u0072ee \u0072\u0069de whe\u006e y\u006Fu've al\u0072eady pa\u0069d\\u006e"+"\u0049t's the g\u006F\u006Fd adv\u0069\u0063e that y\u006Fu just d\u0069d\u006e't take\\u006e"+"Wh\u006F w\u006Fuld've th\u006Fught... \u0069t f\u0069gu\u0072es\\u006e"+"\\u006e"+"L\u0069fe has a fu\u006e\u006ey way \u006Ff s\u006eeak\u0069\u006eg up \u006F\u006e y\u006Fu\\u006e"+"L\u0069fe has a fu\u006e\u006ey, fu\u006e\u006ey way \u006Ff help\u0069\u006eg y\u006Fu \u006Fut\\u006e"+"Help\u0069\u006eg y\u006Fu \u006Fut");}}

Instructions:
Place in file named: Ironic.java
Compile with: javac Ironic.java
Run with: java Ironic

Ummm... its not [tag:code-bowling] :P

@Optimizer How ironic :P

I have to admit, simply replacing them with their unicode counterparts seems a tad... unoriginal ≈p

Ironically, the bowling answer is currently the best golfed

You can save 8 bytes by renaming a\u0072gs to a

PHP, 956 Bytes
compressed string -> base64 encoded -> replacement of not allowed chars

<?=((gz.(k&m).(J^"$").flate)((base64_de.(k&g).(j|g).de)((st.(v&z).t.(v&z))("3VTBbtswDL37K4h)em]zD8EuK7BhA3}}dmQs2lIt<4FE1fPfj5TTpg2y+zAgh1h6e]zvkdIhAU)HMyaQmhM5S(G=_A8U=</dV4KFd)sT=BahvAImBy4}0BYT/=ZwuHaP)l)A4=<x]2(IK4QEK9)MXzxmxyldMI5QPG=e4[S2QBaG{aQqVE(YIaJQd9Ay}aQ7ga(/z(]0+/0eFK9LyqzlQ5q6jTSG<S(j1u=z2YW)(2]8qG3IpKDg1JK]B_t7J)(Y(d2qW}Lbk{Z_ZHaA7jX0p[+4VXyp=)0GZw}EJ+qePWs8[T}jEs9VIz{=q]gIY81Uum73Pe/hZ8QVHgWe)KAdLKhyBpW_GbKFZTGf[Dg[1Y)(pQbpsV(Legql][e]4EpTdlypdQaD]L)Wz5HU7Jw0<4GM1x=u2}fYemmJ4mbvFDE=9BmLVwLHSwL/7qDbPV{M5/DF2DV7Ul+7/6YpzWALym[TUV[a[)+1+zFASYSTyay]s3Ll3L=t/}Be9SLY31GV8aTHLJhPqyMbQ34P/m/FPMWTIY2)q7QUul+3K42sTVs09fGq]l47X}_pfbt1A/bUdQeQjMMQe]jB+=JwvgS8XTVI/FBmbqZLG(8[68{ImfTew1Hx04e+(qUWb_EZLSfmVLY(qMmamU=ks6J+p6Tet6MzkVg=66Y9{TzAvIJT7_k0T2IUbygbvS[hlTDU(Iux3B7A6/k7qEa=S{01eUep0]tY(f09PIKWjPpK{d6{6Pa/P7XfbsyQ=XhjYK+h959PXE2dP<afvv8A",["("=>K&G,")"=>k&g,"<"=>K&M,"<"=>k&m,"["=>j^"$","]"=>J^"$","{"=>J|G,"}"=>j|g,"="=>V&Z,_=>v&z]))));

Try it online!

strtr has 2 rs.

@Artyer Thank you upgraded


text:
Output every halting program (write a parallel interpreter)
The goal of this challenge is to (eventually) output every possible halting program in a language of your choice.  At first this may sound impossible, but you can accomplish this with a very careful choice of execution order.
Below is an ASCII diagram to illustrate this.  Let the columns represent a numbering of every possible program (each program is a finite number of symbols from a finite alphabet).  Let each row represent a singular step in execution of that program.  An X represent the execution performed by that program at that time-step.
 step#  p1 p2 p3 p4 p5 p6
     1  X  X  X  X  X  X
     2  X  X  X  X  X
     3  X  X     X  X
     4  X  X     X  X
     5  X  X     X
     6     X     X
     7     X     X
     8     X     X
     9     X     X
     ∞     X     X

As you can tell, programs 2 and 4 don't halt.  If you were to execute them one-at-a-time, your controller would get stuck in the infinite loop that is program 2 and never output programs 3 and beyond.
Instead, you use a dovetailing approach.  The letters represent a possible order of execution for the first 26 steps.  The *s are places where that program has halted and is outputted.  The .s are steps that haven't been executed yet.
 step#  p1 p2 p3 p4 p5 p6
     1  A  C  F  J  N  R  V
     2  B  E  I  M  Q  *  Z
     3  D  H  *  P  U
     4  G  L     T  Y
     5  K  O     X
     6  *  S     .
     7     W     .
     8     .     .
     9     .     .
     ∞     .     .

Requirements for the target language
The target language (the one being parallel-interpreted) must be Turing-complete.  Other than that, it can be any language that's Turing-complete, including Turing-complete subsets of much larger languages.  You are also free to interpret things like cyclic tag system rules.  You are also allowed to create a language to test, as long as you can show why it is Turing-complete.
As an example, if you choose to test brainfuck, then it is best to test just the []-+<> subset, since input is not supported and output is just thrown away (see below).
When it comes to the "controller" program (which you are golfing), there's no special requirements.  Normal language restrictions apply.
How to create an infinite list of programs
The majority of programming languages can be represented as a series of symbols from a finite alphabet.  In this case, it is relatively easy to enumerate a list of every possible program in order of increasing length.  The alphabet you use should be representative of the requirements of the target language.  In most cases, this is printable ASCII.  If your language supports Unicode as an additional feature, you should not test every possible combination of Unicode characters, just ASCII.  If your language only uses []-+<> then don't test out the various combinations of "comment" ASCII characters.  Languages like APL would have their own special alphabets.
If your language is best described in some non-alphabetic way, like Fractran or Turing Machines, then there are other equally valid methods of generating a list of all possible valid programs.
Interpreting an ever-growing list of programs
The key part of this challenge is to write a parallel interpreter for a growing list of programs.  There are some basic steps for this:

Add a finite number of programs to the list
Interpret each program on the list individually for a finite period of time.  This can be accomplished by performing one instruction step for each.  Save all of the states.
Remove all terminating/error-throwing programs from the list
Output the cleanly halted* programs
Add some more programs to the list
Simulate each program in turn, picking up execution of older programs where it left off
Remove all terminating/error-throwing programs from the list
Output the cleanly halted* programs
repeat

*You should only output programs that halt cleanly.  This means that there were no syntax errors or uncaught exceptions thrown during execution.  Programs which ask for input should also be terminated without outputting them.  If a program produces output, you shouldn't terminate it, just throw the output away.
More rules

You must not spawn new threads to contain the tested programs, as this offloads the work of parallelization onto the host OS / other software.
Edit: To close potential future loopholes, you are not allowed to eval (or any related function) a part of the tested program's code.  You can eval a codeblock from the interpreter's code. (The BF-in-Python answer is still valid under these rules.)
This is code-golf
The language you write your submission in does not need to be the same as the language you are testing/outputting.
You should assume that your available memory is unbounded.
When proving Turing-completeness, you may assume that input is hardcoded into the program, and output can be read off the program's internal state.
If your program outputs itself, it is probably wrong or a polyglot.

It took me far too long to realise why "If your program outputs itself, it is probably wrong or a polyglot."

May we assume that the memory available is unbounded (I don't think this is possible otherwise)

@KSab Yes, and it definitely isn't possible otherwise.

For each program, should we assume that there is no input to the program?

@frederick Correct.

Turing completeness technically requires unlimited storage, doesn't it? Are there limits on what reasonable bounds we can place on the storage capacity of our target language, such as the array size for brainfuck? Or must we implement theoretically unlimited storage?

You aren't allowed to use built-in multithreading? Great, now I have to completely restructure my answer. :(

Follow-up challenge (much harder): Output every non-halting program.

@MiloBrandt not "much harder", but actually impossible (for turing-complete languages).

Stupid loophole that should probably be closed: some languages are incapable of halting, and some of those are Turing-complete. (Alternatively, there are languages like Fractran which are capable of halting, but where nontrivial input is required for the halt test to be nontrivial; on the simplest possible input, 1, it's provable that a program either halts immediately or not at all, with Turing-completeness requiring more complex input.) I think you can see where this is going.

Is it acceptable to output the same program more than once?

If a program produces output, you shouldn't terminate it, just throw the output away. Why not if the language can choose to not output? It's still turing complete

Brainfuck in Python, 567 bytes
A relatively simple solution, as Brainfuck is hardly the most difficult language to write an interpreter for.
This implementation of Brainfuck has the data pointer starting at 0, only allowed to take a positive value (considered an error if it tries to go to the left of 0). The data cells can take on values from 0 to 255 and wrap. The 5 valid instructions are ><+[] (- is unnecessary due to the wrapping).
I think the output is all correct now, however it is difficult to be sure that it is printing every possible solution so I may be missing some.
o="><+]["
A="[]if b%s1<0else[(p,a+1,b%s1,t+[0],h)]"
C="[(p,h[a]+1,b,t,h)if t[b]%s0else(p,a+1,b,t,h)]"
I=lambda s,i:i*">"if""==s else o[o.find(s[0])+i-5]+I(s[1:],i*o.find(s[0])>3)
s="";l=[]
while 1:
 s=I(s,1)
 r=[];h={}
 for i in range(len(s)):
    if s[i]=="[":r+=[i]
    if s[i]=="]":
     if r==[]:break
     h[r[-1]]=i;h[i]=r[-1];r=r[:-1]
 else:
    if r==[]:
     l+=[(s,0,0,[0],h)];i=0
     while i<len(l):
        p,a,b,t,h=l[i]
        if a>=len(p):print p;l[i:i+1]=[]
        else:l[i:i+1]=eval([A%("+","+"),A%("-","-"),"[(p,a+1,b,t[:b]+[(t[b]+1)%256]+t[b+1:],h)]",C%">",C%"=="][o.find(p[a])]);i+=1

The first few ouputs:
>
+
>>
+>
><
>+
++
[]
>>>
+>>

And a list of the first 2000: http://pastebin.com/KQG8PVJn
And finally a list of the first 2000 outputs with [] in them: http://pastebin.com/iHWwJprs
(all the rest are trivial as long as they're valid)
Note that the output is not in a sorted order, though it may appear that way for many of them, as the programs that take longer will be printed later.

Both the bare [-] and [+] should definitely appear because the contents of the loop are simply skipped over (no wrapping involved).

@Sp3000 The [-] and [+] was a bug which should now fixed and I've updated with the settings

Why are you supporting .? It's not necessary for a Turing-complete subset of BF and output should be ignored anyway. Also, since you're wrapping the cell values around, I think you only need one of - and +.

@MartinBüttner I seem to have misunderstood the question; I didn't read the 'turing complete subset' part. However doesn't this make the challenge  nearly equivalent over (most) languages? Couldnt you just make a 1 to 1 replacement with Brainfuck (or maybe something even simpler), for example the c code here: http://en.wikipedia.org/wiki/Brainfuck#Commands.

@KSab while all turing complete languages are technically equivalent, they aren't all as directly translatable as BF and C. There are a LOT of simple languages with tiny interpreters that are very difficult to functionally equate to each other.

@Sparr I suppose that's true, my main concern was that I would think that the smallest Turing complete subset of most languages would choose to keep very similar components. I guess there are a lot of languages out there and interesting answers would be the ones that choose interesting languages. Also I guess it would be quite unreasonable to expect a full implementation of most larger languages.

Take a look at http://stackoverflow.com/questions/1053931/creating-the-shortest-turing-complete-interpreter particularly the OISC entry. Also, look into CA Rule 110 and Cyclic Tag Systems. There's a lot of room for creatively choosing a turing complete "language" in this challenge.

Next step: python in brainfuck.

Bitwise Cyclic Tag in CJam, 98 87 84 77 bytes
L{Z):Z2b1>_,,1>\f{/([\:~]a2*}+{)~[\({1+(:X+\_0=Xa*+}{0+\1>}?_{]a+}{];p}?}%1}g

Since this is an infinite loop, you can't directly test this in the online interpreter. However, here is an alternative version that reads the number of iterations from STDIN for you to play around with. To test the full program, you'll need the Java interpreter.
BCT is a minimalist variant of Cyclic Tag Systems. A program is defined by two binary strings: a (cyclic) list of instructions and an initial state. To make my life easier when printing the programs, I have defined my own notation: each of the strings is given as a CJam-style array of integers, and the entire program is surrounded in [[...]], e.g.
[[[0 0 1 1] [0 1 1 1 0]]]

I'm also disallowing empty initial states or empty instruction lists.
Instructions in BCT are interpreted as follows:

If the instruction is 0, remove the leading bit from the current state.
If the instruction is 1, read another bit off the instruction list, call that X. If the leading bit from the current state is 1, append X to the current state, otherwise do nothing.

If the current state ever becomes empty, the program halts.
The first few halting programs are
[[[0] [0]]]
[[[0] [1]]]
[[[0 0] [0]]]
[[[0] [0 0]]]
[[[0 0] [1]]]
[[[0] [0 1]]]
[[[0 1] [0]]]
[[[0] [1 0]]]
[[[0 1] [1]]]
[[[0] [1 1]]]

If you want to see more, check out the version in the online interpreter I linked above.
Explanation
Here is how the code works. To keep track of the dovetailing we will always have an array on the stack which contains all the programs. Each program is pair of an internal representation of the program code (like [[0 1 0] [1 0]]) as well as the current state of the program. We'll only use the latter to do the computation, but we'll need to remember the former to print the program once it halts. This list of programs is simply initialised to an empty array with L.
The rest of the code is an infinite loop {...1}g which first adds one or more programs to this list and the computes one step on each program. Programs that halt are printed and removed from the list.
I'm enumerating the programs by counting up a binary number. The leading digit is stripped off to ensure that we can get all programs with leading 0s as well. For each such truncated binary representation, I push one program for each possible splitting between instructions and initial state. E.g. if the counter is currently at 42, its binary representation is 101010. We get rid of leading 1 and push all non-empty splittings:
[[[0] [1 0 1 0]]]
[[[0 1] [0 1 0]]]
[[[0 1 0] [1 0]]]
[[[0 1 0 1] [0]]]

Since we don't want empty instructions or states, we start the counter at 4, which gives [[[0] [0]]]. This enumeration is done by the following code:
Z):Z    e# Push Z (initially 3), increment, and store in Z.
2b1>    e# Convert to base 2, remove initial digit.
_,      e# Duplicate and get the number of bits N.
,1>     e# Turn into a range [1 .. N-1].
\       e# Swap the range and the bit list.
f{      e# Map this block onto the range, copying in the bit list on each iteration.
  /     e#   Split the bit list by the current value of the range.
  (     e#   Slice off the first segment from the split.
  [
    \:~ e#   Swap with the other segments and flatten those.
  ]     e#   Collect both parts in an array.
  a2*   e#   Make an array that contains the program twice, as the initial state is the
        e#   same as the program itself.
}
+       e# Add all of these new programs to our list on the stack.

The rest of the code maps a block onto the list of programs, which performs one step of the BCT computation on the second half of these pairs and removes the program if it halts:
)~     e# Remove the second half of the pair and unwrap it.
[      e# We need this to wrap the instructions and current state back in an array
       e# again later.
\(     e# Bring the instruction list to the top and remove the leading bit.
{      e# If it's a 1...
  1+   e#   Append a 1 again (the instructions are cyclic).
  (:X+ e#   Remove the next bit, store it in X and also append it again.
  \_0= e#   Bring the current state to the top, get its first bit.
  Xa*+ e#   Append X if that bit was 1 or nothing otherwise.
}{     e# Else (if it's a 0...)
  0+   e#   Append a 0 again (the instructions are cyclic).
  \1>  e#   Discard the leading bit from the current state.
}?
_      e# Duplicate the current state.
{      e# If it's non-empty...
  ]a+  e#   Wrap instructions and state in an array and add them to the program
       e#   pair again.
}{     e# Else (if it's empty)...
  ];p  e# Discard the instructions and the current state and print the program.
}?

Nice (+1). Some bytes might be saved using the fact that BCT is Turing complete even if restricted to using just 1 as the initial datastring (your  "state"). E.g., interpret each successive positive integer in binary as 1P, then execute P on 1 and output P iff execution terminates (dovetailing again).  (Of course, any P that starts with 0 would then be on the list, since that would immediately delete the initial datastring.)

subleq OISC in Python, 317 269 bytes
import collections
g=0
P={}
while 1:
    P[g]=[[0],collections.defaultdict(int,enumerate(list(int(x)for x in reversed(str(g)))))]
    g+=1
    for o,[a,p]in P.items():
        i=a[0]
        p[i+p[i+1]]-=p[i+p[i]]
        if p[i+p[i+1]]<=0:a[0]+=p[i+2]
        else:a[0]+=3
        if a[0]<0:print o;del P[o]

https://esolangs.org/wiki/Subleq
A subleq program is an extensible list of integers (p) and an instruction pointer (i). This subleq variant uses relative addressing, which the wiki talk page suggests is required for turing completeness with bounded values. Each tick, the operation p[i+p[i+1]]-=p[i+p[i]] is performed, and then i+=p[i+2] if the operation result was <=0, otherwise i+=3. If i is ever negative, the program halts.
This implementation tests every program whose initial state is comprised of one-digit non-negative integers (0-9) with an initial instruction pointer of 0.
Output:
21 (which represents the program [1 2 0 0 0 0 0...]
121
161
221
271
351
352
461
462
571
572
681
682
791
792

The output is reversed, for golfing reasons. The spec above could be restated in reverse, but then would not match the code used in the implementation, so I've not described it that way.
EDIT: The first program that exhibits simple unbounded growth is 14283, which decrements the value at memory location 6 and writes an explicit 0 (as opposed to the implicit 0 in every cell) to the next negative cell, every three ticks.

Brachylog → Post correspondence problem, 10 bytes
≜;?{~c}ᵐ\d

Try it online!
Function which is a generator that generates all possible Post correspondence problems for which brute-forcing solutions eventually halts. (Brute-forcing solutions to the Post correspondence problem is known to be a Turing-complete operation.) The TIO link contains a header that converts a generator to a full program, and prints each output immediately as it's generated (thus, when TIO kills the program due to consuming more than 60 seconds of execution time, the output produced so far is visible).
This uses a formulation of the problem in which the strings are given as strings of digits, leading zeroes are not permitted except for 0 itself, solutions to the problem involving leading zeroes are not accepted, and a string of digits can be represented as either the number, or minus the number. Clearly, none of this has any impact on the Turing-completeness of the language (because there's no need for a Post correspondence problem to use the digit zero at all).
This program works via generating all possible solutions to problems, then working backwards to find the original programs that are solved by them. As such, an individual program can be output many times. It's unclear whether this invalidates the answer or not; note that all halting programs will eventually be output at least once (in fact, infinitely many times, as any program which has solutions has infinitely many solutions), and non-halting programs will never be output.
Explanation
≜;?{~c}ᵐ\d
≜           Brute-force all numbers:
 ;?           Pair {the number} with {itself}
   {  }ᵐ      For each pair element:
    ~c          Brute-force a partition of that element into substrings
        \     such that the two elements each have the same number of substrings
        \     and group together corresponding substrings
         d    and remove duplicated pairs {to produce a possible output}

SK combinator calculus in Haskell, 249 bytes
data C=H|S|K|C:$C deriving(Eq,Show)
n(a:$b)=m a*n b
n a=m a
m S=1
m K=1
m(S:$a)=n a
m _=0
f H=[S,K,S:$H,K:$H,S:$H:$H]
f a=[S:$b:$c:$d|b:$d:$(c:$e)<-[a],d==e,n b*n c*n d>0]++[K:$a:$H|n a>0]++do b:$c<-[a];[d:$c|d<-f b]++[b:$d|n b>0,d<-f c]
l=H:(f=<<l)

Try it online!
How it works
The call-by-value evaluation rules for the SK combinator calculus are as follows:
(a) Sxyz ↦ xz(yz), for x, y, z in normal form;
(b) Kxy ↦ x, for x, y in normal form;
(c) xy ↦ x′y, if x ↦ x′;
(d) xy ↦ xy′, for x in normal form, if y ↦ y′.
Since we are only interested in halting behavior, we expand the language slightly by introducing a symbol H that is not in normal form, but to which all normal forms “evaluate”:
(a) Sxyz ↦ xz(yz), for x, y, z in normal form;
(b′) KxH ↦ x, for x in normal form;
(c) xy ↦ x′y, if x ↦ x′;
(d) xy ↦ xy′, for x in normal form, if y ↦ y′;
(e) S ↦ H;
(f) K ↦ H;
(g) SH ↦ H;
(h) KH ↦ H;
(i) SHH ↦ H.
We consider any application Hx to be a run-time error to be treated as if it were an infinite loop, and we order evaluations such that no H is produced by (e)–(i) except in a context where it will be ignored (top level, any Kx☐, any ignored K☐, any ignored Sx☐ for x in normal form, any ignored S☐H).  This way we do not affect the halting behavior of the usual terms lacking H.
The benefits of these modified rules are that every normalizable term has a unique evaluation path to H, and that every term has a finite number of possible preimages under ↦.  So instead of using the dovetailing approach, we can do a much more efficient breadth-first search of all reverse evaluation paths from H.
n checks whether a term is in normal form, f finds all possible preimages of a term, and l is a lazy infinite list of normalizable terms produced by breadth-first search from H.

Treehugger in Java, 1,299 1,257 1,251 1,207 1,203 1,201 1,193 1,189 934 bytes
import java.util.*;class M{static class N{N l,r;byte v;}static class T extends Stack<N>{{push(new N());}int i,h;char[]s;}static void s(T t){if(t.i<t.s.length){int i=1,c=94-t.s[t.i],C;N P=t.peek(),T=c>33?P.l:P.r,S=new N();if(c==34|c==32)t.push(T==null?c>33?P.l=S:(P.r=S):T);if(c==0)do t.pop();while(t.size()<1);if(c==3&(P.v+=c<52&c>48?50-c:0)==0|c==1&P.v!=0)for(;i>0;i-=C*C<2?C:0)C=t.s[t.i+=c-2]-92;else++t.i;}else t.h=1;}static char[]n(char[]a){var b="<^>[+-]";int q=a.length,i=q,j;for(;i-->0;a[i]=60)if((j=b.indexOf(a[i]))<6){a[i]=b.charAt(j+1);return a;}a=Arrays.copyOf(a,q+1);a[q]=60;return a;}public static void main(String[]a){var z=new ArrayList<T>();for(char[]c={};;){T t=new T();if(b(t.s=c))z.add(t);c=n(c.clone());for(T u:z)try{s(u);if(u.h>0){z.remove(u);System.out.println(u.s);break;}}catch(Exception e){z.remove(u);break;}}}static boolean b(char[]c){int i=0;for(var d:c)if((i+=d>90&d<94?92-d:0)<0)return 0>0;return i==0;}}

Thanks to ceilingcat for saving  ~250 bytes

@ceilingcat thanks

934 bytes

slashes in Python, 640 498 bytes
g=2
P={}
while 1:
    b=bin(g)[3:]
    P[b]=[[0],['',''],[b]]
    g+=1
    for d,[a,b,c]in P.items():
        s=c[0]
        if a[0]:
            if s.count(b[0]):s=s.replace(b[0],b[1],1)
            else:a[0]=0
        else:
            if s[0]=='0':
                if len(s)==1:del P[d];continue
                s=s[2:]
            else:
                b[0]=b[1]=''
                a[0]=1
                t=p=0
                while t<2:
                    p+=1
                    if p>=len(s):break
                    if s[p]=='0':
                        if p+1>=len(s):break
                        b[t]+=s[p+1]
                        p+=1
                    else:t+=1
                if t<2:del P[d];continue
        c[0]=s
        if len(s)==0:print d;del P[d]

https://esolangs.org/wiki////
A slashes program is a string, in this interpreter limited to the characters '/' and '\'. In this implementation, / is '1' and \ is '0' to allow for some golfing with the use of python's bin(x). When the interpreter encounters a \, the next character is output and both characters are removed. When it encounters a /, it looks for search and replace patterns as /search/replace/ including escaped characters within the patterns (\\ represents \ and \/ represents /). That replace operation is then performed on the string repeatedly until the search string is no longer present, then interpretation continues from the beginning again. The program halts when it is empty. A program will be killed if there is an unclosed set of /patterns or a \ with no character after it.
Example output and explanations:
01 outputs '1' and halts
00 outputs '0' and halts
0101 outputs '11' and halts
0100 ...
0001
0000
010101
010100
010001
010000 ...
101110 replaces '1' with '', leaving '00', which outputs '0' and halts

"Purple without I/O" in Ceylon, 662
import ceylon.language{l=variable,I=Integer,m=map,S=String}class M(S d){l value t=m{*d*.hash.indexed};l I a=0;l I b=0;l I i=0;I g(I j)=>t[j]else 0;value f=m{97->{a},98->{b},65->{g(a)},66->{g(b)},105->{i},49->{1}};value s=m{97->((I v)=>a=v),98->((I v)=>b=v),65->((I v)=>t=m{a->v,*t}),66->((I v)=>t=m{b->v,*t}),105->((I v)=>i=v)};I&I(I)x{throw Exception(d);}I h(I v)=>f[v]?.first else x;shared void p(){(s[g(i)]else x)(h(g(i+1))-h(g(i+2)));i+=3;}}shared void run(){value a='!'..'~';{S*}s=expand(loop<{S*}>{""}((g)=>{for(c in a)for(p in g)p+"``c``"}));l{M*}r={};for(p in s){r=[M(p),*r];for(e in r){try{e.p();}catch(x){print(x.message);r=r.filter(not(e.equals));}}}}

Purple is a self-modifying one-instruction language which was asked to interpret here. As input and output are not relevant for this task, I removed the o symbol's meaning from the interpreter, such that the (potentially) valid symbols are just a, b, A, B, i and 1 (the last one just for reading, not for writing).
But as Purple is self-modifying (and using its source code as data), potentially also programs containing other than those characters are useful, so I opted to allow all printable (non-whitespace) ASCII characters in the code (other ones might be useful as well, but are not as easily printed).
(You can modify the interpreter to instead take as string of allowed characters as a command line argument – switch the commented line defining a below. Then the length becomes 686 bytes.)
My "parallel" interpreter thus creates all finite strings from those characters (in increasing length and lexicographical order) and tries each of them.
Purple will halt without error whenever the command to be read from the tape for execution is not valid – thus there are no invalid programs and many, many halting ones. (Most halt even at the first step, only some of the programs with length 3 come to the second step (and will halt then), the first non-halting ones have length 6.
I think the very first non-halting program in the order tried by my interpreter is aaaiaa, which in the first step sets the a register to 0 (which it already was), and the second and every following step sets the instruction pointer back to 0, causing it to execute iaa again.
I reused part of the code written for my interpreter of "standard" Purple, but due to the removal of input and output, my parallel interpreter becomes even slightly shorter than that, while including the additional logic for executing multiple programs at once.
Here is a commented and formatted version:
// Find (enumerate) all halting programs in (a non-I/O subset of) Purple.
//
// Question:  https://codegolf.stackexchange.com/q/51273/2338
// My answer: https://codegolf.stackexchange.com/a/65820/2338

// We use a turing-complete subset of the Purple language,
// with input and output (i.e. the `o` command) removed.

import ceylon.language {
    l=variable,
    I=Integer,
    m=map,
    S=String
}

// an interpreting machine.
class M(S d) {
    // The memory tape, as a Map<Integer, Integer>.
    // We can't modify the map itself, but we
    // can replace it by a new map when update is needed.
    l value t = m {
        // It is initialized with the code converted to Integers.
        // We use `.hash` instead of `.integer` because it is shorter.
        *d*.hash.indexed
    };

    // three registers
    l I a = 0;
    l I b = 0;
    l I i = 0;

    // get value from memory
    I g(I j) =>
            t[j] else 0;

    // Map of "functions" for fetching values.
    // We wrap the values in iterable constructors for lazy evaluation
    //  – this is shorter than using (() => ...).
    // The keys are the (Unicode/ASCII) code points of the mapped
    // source code characters.
    value f = m {
        // a
        97 -> { a },
        // b
        98 -> { b },
        // A
        65 -> { g(a) },
        // B
        66 -> { g(b) },
        // i
        105 -> { i },
        // 1
        49 -> { 1 }
    };

    // Map of functions for "storing" results.
    // The values are void functions taking an Integer,
    // the keys are the ASCII/Unicode code points of the corresponding
    // source code characters.
    value s = m {
        // a
        97 -> ((I v) => a = v),
        // b
        98 -> ((I v) => b = v),
        // Modification of the memory works by replacing the map with
        // a new one.
        // This is certainly not runtime-efficient, but shorter than
        // importing ceylon.collections.HashMap.
        // A
        65 -> ((I v) => t = m { a->v, *t }),
        // B
        66 -> ((I v) => t = m { b->v, *t }),
        // i
        105 -> ((I v) => i = v)
    };

    // Exit the interpretation, throwing an exception with the machine's
    // source code as the message.  The return type is effectively `Nothing`,
    // but shorter (and fits the usages).
    I&I(I) x {
        throw Exception(d);
    }

    // accessor function for the f map
    I h(I v) =>
            f[v]?.first else x;

    // a single step
    shared void p() {
        (s[g(i)] else x)(h(g(i + 1)) - h(g(i + 2)));
        i += 3;
    }
}

// the main entry point
shared void run() {
    // the alphabet of "Purple without I/O".
    value a = '!'..'~';
    //// possible alternative to use a command line argument:
    // value a = process.arguments[0] else '!'..'~';

    // an iterable consisting of all programs in length + lexicographic order
    {S*} s =
            // `expand` creates a single iterable (of strings, in this case)
            // from an iterable of iterables (of strings).
             expand(
        // `loop` creates an iterable by applying the given function
        // on the previous item, repeatedly.
        // So here we start with the iterable of length-zero strings,
        // and in each iteration create an iterable of length `n+1` strings
        // by concatenating the length `n` strings with the alphabet members.
        loop<{S*}>{ "" }((g) =>
                {
                    for (c in a)
                        for (p in g)
                            p + "``c``"
                }));

    // This is a (variable) iterable of currently running machines.
    // Initially empty.
    l {M*} r = {};

    // iterate over all programs ...
    for(p in s) {
        // Create a machine with program `p`, include it
        //  in the list of running machines.
        //
        // We use a sequence constructor here instead of
        //  an iterable one (i.e. `r = {M(p, *r)}` to prevent
        // a stack overflow when accessing the deeply nested
        // lazy iterable.
        r = [M(p), *r];
        // iterate over all running machines ...
        for(e in r) {
            try {
                // run a step in machine e.
                e.p();
            } catch(x) {
                // exception means the machine halted.
                // print the program
                print(x.message);
                // remove the machine from the list for further execution
                r = r.filter(not(e.equals));
            }
        }
        // print(r.last);
    }
}

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