Java 8, 47,867 changes total.

Uses the average of the image as the center point. It then draws all possible rays to the center and gives it the best radius to color. It then colors all invalid points black.

import javax.imageio.ImageIO;
import java.awt.Color;
import java.awt.image.BufferedImage;
import java.io.File;
import java.util.ArrayList;
import java.util.List;

public class MakeItStarry {

    private static final int RGB_RED = Color.RED.getRGB();
    static int[][] originalImage;

    static final int WHITE = 0;
    static final int BLACK = 1;
    static final int RGB_WHITE = Color.WHITE.getRGB();
    static final int RGB_BLACK = Color.BLACK.getRGB();
    static final int RGB_BLUE = Color.BLUE.getRGB();
    static final int RGB_YELLOW = Color.YELLOW.getRGB();

    public static void main(String[] args) throws Exception{
        originalImage = convert(ImageIO.read(new File(args[0])));
        Point center = findCenter(originalImage);
        int[][] nextImage = starry(originalImage, center);
        BufferedImage result = difference(originalImage, nextImage);
        result.setRGB(center.x, center.y, RGB_RED);
        String fileType;
        String fileName;
        if (args[1].split("\\.").length > 1){
            fileType = args[1].split("\\.")[1];
            fileName = args[1];
        } else {
            fileType = "PNG";
            fileName = args[1] + ".PNG";
        }
        ImageIO.write(result, fileType, new File(fileName));
        System.out.println(cost);
    }

    static int cost;

    private static BufferedImage difference(int[][] image1, int[][] image2) {
        cost = 0;
        int height = image1[0].length;
        int width = image1.length;
        BufferedImage result = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);
        for (int x = 0; x < width; x++){
            for (int y = 0; y < width; y++){
                if (image1[x][y] == image2[x][y]){
                    if (image1[x][y] == WHITE){
                        result.setRGB(x, y, RGB_WHITE);
                    } else {
                        result.setRGB(x, y, RGB_BLACK);
                    }
                } else {
                    cost++;
                    if (image1[x][y] == WHITE){
                        result.setRGB(x, y, RGB_BLUE);
                    } else {
                        result.setRGB(x, y, RGB_YELLOW);
                    }
                }
            }
        }
        return result;
    }

    private static int[][] starry(int[][] image, Point center) {
        int width = image.length;
        int height = image[0].length;
        int[][] result = new int[width][height];
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++){
                result[x][y] = BLACK;
            }
        }
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++) {
                Point endPoint = new Point(x, y, image);
                List<Point> line = Point.lineTo(center, endPoint, image);
                List<Point> newLine = starRay(line);
                newLine.stream().filter(point -> result[point.x][point.y] == BLACK).forEach(point -> {
                    result[point.x][point.y] = point.color;
                });
            }
        }
        int distance = 0;
        while (distance < height || distance < width){//This removes pixels that can't see the center.
            for (int x = Math.max(center.x - distance,0); x < center.x + distance && x < width; x++){
                for (int y = Math.max(center.y - distance, 0); y < center.y + distance && y < height; y++){
                    Point point = new Point(x, y, result);
                    if (Point.distance(center, point) != distance){
                        continue;
                    }
                    if (point.color == WHITE){
                        List<Point> line = Point.lineTo(center, point, result);
                        for (Point p : line){
                            if (p.color == BLACK){
                                point.color = BLACK;
                                break;
                            }
                        }
                        result[point.x][point.y] = point.color;
                    }
                }
            }//All white pixels can technically see the center but only if looking from the edge.
            distance++;
        }
        return result;
    }

    private static List<Point> starRay(List<Point> line) {
        int numOfWhites = 0;
        int farthestGoodPoint = 0;
        int blackCost = 0;
        int whiteCost = 0;
        for (int i = 0; i < line.size(); i++){
            if (line.get(i).color == WHITE){
                numOfWhites++;
                whiteCost++;
                if (numOfWhites + whiteCost > blackCost){
                    blackCost = 0;
                    whiteCost = 0;
                    farthestGoodPoint = i;
                }
            } else {
                blackCost++;
                numOfWhites = 0;
            }
        }
        List<Point> result = new ArrayList<>();
        for (int i = 0; i < line.size(); i++){
            Point p = line.get(i);
            if (i <= farthestGoodPoint){
                result.add(new Point(p.x, p.y, WHITE));
            } else {
                result.add(new Point(p.x, p.y, BLACK));
            }
        }
        return result;
    }

    private static Point findCenter(int[][] image) {
        double totalx = 0;
        double totaly = 0;
        int counter = 0;
        int width = image.length;
        int height = image[0].length;
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++){
                if (image[x][y] == WHITE){
                    totalx += x;
                    totaly += y;
                    counter++;
                }
            }
        }
        return new Point((int)(totalx/counter), (int)(totaly/counter), image);
    }

    private static int[][] convert(BufferedImage image) {
        int width = image.getWidth();
        int height  = image.getHeight();
        int[][] result = new int[width][height];
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++){
                if (image.getRGB(x, y) == RGB_WHITE){
                    result[x][y] = WHITE;
                } else {
                    result[x][y] = BLACK;
                }
            }
        }
        return result;
    }

    private static class Point {

        public int color;
        public int y;
        public int x;

        public Point(int x, int y, int[][] image) {
            this.x = x;
            this.y = y;
            this.color = image[x][y];
        }

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

        public static List<Point> lineTo(Point point1, Point point2, int[][] image) {
            List<Point> result = new ArrayList<>();
            boolean reversed = false;
            if (point1.x > point2.x){
                Point buffer = point1;
                point1 = point2;
                point2 = buffer;
                reversed = !reversed;
            }
            int rise = point1.y - point2.y;
            int run = point1.x - point2.x;
            if (run == 0){
                if (point1.y > point2.y){
                    Point buffer = point1;
                    point1 = point2;
                    point2 = buffer;
                    reversed = !reversed;
                }
                int x = point1.x;
                for (int y = point1.y; y <= point2.y; y++){
                    result.add(new Point(x, y, image));
                }
                if (reversed){
                    return reversed(result);
                }
                return result;
            }
            if (rise == 0){
                if (point1.x > point2.x){
                    Point buffer = point1;
                    point1 = point2;
                    point2 = buffer;
                    reversed = !reversed;
                }
                int y = point1.y;
                for (int x = point1.x; x <= point2.x; x++){
                    result.add(new Point(x, y, image));
                }
                if (reversed){
                    return reversed(result);
                }
                return result;
            }
            int gcd = gcd(rise, run);
            rise /= gcd;
            run /= gcd;
            double slope = (rise + 0.0) / run;
            if (Math.abs(rise) >= Math.abs(run)){
                if (point1.y > point2.y){
                    Point buffer = point1;
                    point1 = point2;
                    point2 = buffer;
                    reversed = !reversed;
                }
                double x = point1.x;
                for (double y = point1.y + .5; y <= point2.y; y++){
                    int px = (int) Math.round(x);
                    if (Math.abs(Math.abs(px - x) - .5) < Math.abs(1.0 / (rise * 4))){
                        x += 1/slope;
                        continue;
                    }
                    result.add(new Point(px, (int) Math.round(y - .5), image));
                    result.add(new Point(px, (int) Math.round(y + .5), image));
                    x += 1/slope;
                }
                if (reversed){
                    return reversed(result);
                }
                return result;
            } else {
                if (point1.x > point2.x){
                    Point buffer = point1;
                    point1 = point2;
                    point2 = buffer;
                    reversed = !reversed;
                }
                double y = point1.y;
                for (double x = point1.x + .5; x <= point2.x; x++){
                    int py = (int) Math.round(y);
                    if (Math.abs(Math.abs(py - y) - .5) < Math.abs(1.0 / (run * 4))) {
                        y += slope;
                        continue;
                    }
                    result.add(new Point((int) Math.round(x - .5), py, image));
                    result.add(new Point((int) Math.round(x + .5), py, image));
                    y += slope;
                }
                if (reversed){
                    return reversed(result);
                }
                return result;
            }
        }

        private static List<Point> reversed(List<Point> points) {
            List<Point> result = new ArrayList<>();
            for (int i = points.size() - 1; i >= 0; i--){
                result.add(points.get(i));
            }
            return result;
        }

        private static int gcd(int num1, int num2) {
            if (num1 < 0 && num2 < 0){
                return -gcd(-num1, -num2);
            }
            if (num1 < 0){
                return gcd(-num1, num2);
            }
            if (num2 < 0){
                return gcd(num1, -num2);
            }
            if (num2 > num1){
                return gcd(num2, num1);
            }
            if (num2 == 0){
                return num1;
            }
            return gcd(num2, num1 % num2);
        }

        @Override
        public String toString(){
            return x + " " + y;
        }

        public static int distance(Point point1, Point point2) {
            return Math.abs(point1.x - point2.x) + Math.abs(point1.y - point2.y);
        }
    }
}

Results

Image 1 - 0 changes, Image 2 - 13,698 changes

Image 3 - 24,269 changes, Image 4 - 103 changes

Image 5 - 5,344 changes, Image 6 - 4,456 changes

Without invalid pixels removed, 42,782 changes total

Green pixels are the first layer of invalid pixels.

Image 1 - 0 changes, Image 2- 9,889 changes

Image 3 - 24,268 changes, Image 4 - 103 changes

Image 5 - 4,471 changes, Image 6- 4,050 changes

All white pixels in all the pictures can have a line drawn to them from the center pixel if the line does not have to originate/end at the centers but rather anywhere on the pixel.

args[0] contains input file name.

args[1] contains output file name.

Prints to stdout number of changes.


Transpose a 3x3 matrix across the anti-diagonal

APL - 7
⌽⍉⌽3 3⍴

Example input:
⌽⍉⌽3 3⍴1 2 3 3 4 5 1 2 9
> 9 5 3
  2 4 2
  1 3 1

ngn APL demo


Converting Strings to Decimals (Gone Wrong)

Shakespeare Programming Language, 258 252 bytes
-6 bytes thanks to the default.
,.Ajax,.Puck,.Act I:.Scene I:.[Exeunt][Enter Ajax and Puck]
Ajax:Open mind.
Puck:Is I nicer zero?If soYou is the sum ofI twice the difference
     betweenthe product ofyou the sum ofa cat a big big cat the factorial
     ofa big big cat.
     If soLet usAct I.Open heart

Try it online!
The golfiest representation of the integer 48 is as twice the factorial of a big big cat, i.e. \$48=2\times (2\times2\times1)!\$.
This corresponds to
Ajax = 0
Puck = 0
Begin Act I
Puck = read_input (as ASCII codepoint value)
if(Puck>0){
    Ajax = Puck + 2 * (Ajax * (4+1) - 4!)
    Go to Act I
}
print(Ajax) (as an integer)


JavaScript (ES7),  33  29 bytes
This is A307485: one odd, two even, four odd, eight even, etc.
n=>n-~n-(4<<Math.log2(n))/3|0

Try it online!
For \$n\in\mathbb{N}^*\$, this is equivalent to:
$$a(n)=2n+1-\left\lceil\frac{2^{\lfloor log_2 n\rfloor+2}}{3}\right\rceil$$
It produces the sequence:
1
2 4
3 5 7 9
6 8 10 12 14 16 18 20
...

The ratio of odd values is 'bouncing' ad infinitum between \$1/3\$ and \$2/3\$, more and more slowly:


Python 3, 428 408 385 378 bytes

Working, but has a ton of potential to be golfed. I'm a bit rusty.

Assumes input is padded with spaces to make a rectangle.

EDIT: Thanks to @Artyer for 23 byte savings!

EDIT2: Wow I completely missed a 6 byte savings. Saved 1 more by swapping sides of an equals check.

*i,=map(list,input().split('\n'))
r=c=s=q=e=w=0
o=lambda y,x:len(i[0])>x>=0<=y<len(i)
d='\/_|'
for l in i:
 if'x'in l:r=i.index(l);c=l.index('x')
for a,b in(1,0),(0,1),(-1,0),(0,-1):
 y,x=r+a,c+b;f=o(y,x)and i[y][x]
 if f in d:s=f;w=d.index(f);q,e=y,x
k=lambda y,x,g=[1,1,0,1][w],v=[1,-1,1,0][w]:o(y,x)and s==i[y][x]and(exec('i[y][x]=0')or 1+k(y+g,x+v)+k(y-g,x-v))
print(k(q,e))

Expanded version with explanation:

inputtt='''  ______________.
 / ____________ \
 |/ __________ \|
 ||/ ________ \||
 |||/ ______ \|||
 ||||/      \||||
 |||||/  x  |||||
 |||||\_____/||||
 ||||\_______/|||
 |||\_________/||
 ||\___________/|
  \_____________/'''

# First, we get the input from STDIN and make it
# into a doubly-nested array

*input_text,=map(list,inputtt.split('\n'))

# A pretty cool Python trick to assign 0 to
# mulitple variables at once.

row=col=line_letter=line_row=line_col=line_char_index=0

# A function to check if a certian row and col is
# in bounds or not. Uses python's comparator chaining

in_bounds=lambda y,x:len(input_text[0])>x>=0<=y<len(input_text)

# A string to store all the line characters.
chars='\/_|'

# Search for the x
for line in input_text:

 # If this line contains the x...
 if'x'in line:

     # Mark the row and column
     row=input_text.index(line);col=line.index('x')

# For each direction...
for down,right in(1,0),(0,1),(-1,0),(0,-1):

 # Move in that direction
 y,x=row+down,col+right

 # If the position is in bounds, mark the char at that position
 line_found=in_bounds(y,x)and input_text[y][x]

 # If the char is a line char, set all the variables saying we found it
 if line_found in chars:
  line_letter=line_found
  line_char_index=chars.index(line_found)
  line_row,line_col=y,x

recur=lambda y,x,\
       # Find which directions we are supposed to recur in based on the line char
       g=[1,1,0,1][line_char_index],v=[1,-1,1,0][line_char_index]:\
       # If the char is in bounds and we are still on the line...
       in_bounds(y,x)and input_text[y][x]==line_letter and\
       # Set the spot to a 0, so we won't go back, increment,
       # and recur in both directions
       (exec('i[y][x]=0')or 1+recur(y+g,x+v)+recur(y-g,x-v))

# Finally, print the answer
print(recur(line_row,line_col))


APL (29 24)

(Thanks to Zgarb for the extra inspiration.)

{⌈/|-⌿⍺⍵∘.(+/≤÷(⍴⊣))∊⍺⍵}

This is a function that takes the arrays as its left and right arguments.

      8 9 9 5 5 0 3 {⌈/|-⌿⍺⍵∘.(+/≤÷(⍴⊣))∊⍺⍵} 4 9 0 5 5 0 4 6 9 10 4 0 9
0.1758241758

Explanation:

{⌈/                                maximum of
   |                               the absolute value of
    -⌿                             the difference between
      ⍺⍵∘.(         )∊⍺⍵          for both arrays, and each element in both arrays
            +/≤                    the amount of items in that array ≤ the element
               ÷                   divided by
                (⍴⊣)              the length of that array
                          }


Implement a sorting algorithm with no change.

Perl, 89 characters

sub t{return if!@_;my$c=shift;t(grep{$_ lt$c}@_),$c,t(grep{$_ ge$c}@_)}print t split//,<>

This exploits the fact that QuickSort is effectively equivalent to the recurrence relation:

sorted x = () if x is empty, otherwise
           sorted (elements in x less than x[0]) :: x[0] ::
           sorted (elements in x greater than or equal to x[0] except for x[0] itself)

Edit

I originally misread the question and thought I had to sort the input strings, not the characters within a string. Hence my solution grows from 80 to 89 characters.


Number of tilings on a triangular board with triangular tiles

JavaScript (Node.js), N =  22 25  32 in ~2 seconds
A recursive search using bit masks and a cache to keep track of patterns whose result is already known.
It doesn't make much sense to try go further in Node. Using a binary matrix is significantly slower and BigInts are even slower. It should rather be ported to a language natively supporting 64-bit integers.
'use strict';

let ts = new Date;

for(let n = 0; n <= 32; n++) {
  console.log(
    n.toString().padStart(2) + ' ' +
    solve(n).toString().padStart(10) + ' ' +
    '(' + ((new Date - ts) / 1000).toFixed(2) + ')'
  );
}

function solve(n) {
  // trivial cases
  if(![0, 2, 9, 11].includes(n % 12)) {
    return 0;
  }
  if(n == 0) {
    return 1;
  }

  // We work on a triangle stored as an array of bit masks:
  //   8 7 6 5 4 3 2 1 0 |
  //  -------------------+---  With this format, the tribones
  //   . . . . . . . . A | 0   are turned into the following
  //   . . . . . . . A A | 1   trominos:
  //   . . . . . . B B C | 2
  //   . . . . . D B C C | 3    X O    and    . X
  //   . . . . D D E E F | 4    O .           O O
  //   . . . G H H E F F | 5
  //   . . G G H I I J J | 6   where 'X' is the arbitrary anchor
  //   . K L L M I N J O | 7   point used in this code
  //   K K L M M N N O O | 8
  let a = Array(n).fill(0),
      cache = a.map(_ => new Object);

  // recursive search, starting at (x, y) = (0, 0)
  return (function search(x, y) {
    // if we've reached the last row, make sure it's complete
    if(y == n - 1) {
      if(a[y] == (1 << n) - 1) {
        return 1;
      }
      return 0;
    }

    // if we are beyond the last column, go on with the next row
    if(x < 0) {
      y++;

      // either return the result from the cache right away
      if(cache[y][a[y]] !== undefined) {
        return cache[y][a[y]];
      }
      // or do a full search
      return cache[y][a[y]] = search(y, y);
    }

    // if (x, y) is already set, advance to the next column
    if(a[y] >> x & 1) {
      return search(x - 1, y);
    }

    let res = 0;

    // try to insert X O
    //               O .
    if(x && !(a[y] >> x - 1 & 1)) {
      a[y] ^= 3 << x - 1;
      a[y + 1] ^= 1 << x;
      res += search(x - 2, y);
      a[y] ^= 3 << x - 1;
      a[y + 1] ^= 1 << x;
    }

    // try to insert . X
    //               O O
    if(!(a[y + 1] >> x + 1 & 1)) {
      a[y] ^= 1 << x;
      a[y + 1] ^= 3 << x;
      res += search(x - 1, y);
      a[y] ^= 1 << x;
      a[y + 1] ^= 3 << x;
    }

    return res;
  })(0, 0);
}

Try it online!
Output
 0          1 (0.00)
 1          0 (0.00)
 2          1 (0.00)
 3          0 (0.00)
 4          0 (0.00)
 5          0 (0.00)
 6          0 (0.00)
 7          0 (0.00)
 8          0 (0.00)
 9          2 (0.00)
10          0 (0.00)
11          8 (0.00)
12         12 (0.01)
13          0 (0.01)
14         72 (0.01)
15          0 (0.01)
16          0 (0.01)
17          0 (0.01)
18          0 (0.01)
19          0 (0.01)
20          0 (0.01)
21     185328 (0.05)
22          0 (0.05)
23    4736520 (0.24)
24   21617456 (0.60)
25          0 (0.60)
26  912370744 (2.18)
27          0 (2.18)
28          0 (2.18)
29          0 (2.18)
30          0 (2.18)
31          0 (2.18)
32          0 (2.18)


Golfscript, 75 bytes

Inspired by the article linked in the comments.

':'/{~}/5/:m;12%:h;"XXXXXXXXXXXX"{..318\%9/' '*@12%.h=2*\m=+'omhx'=@85/n*}%

The XXXXXXXXXXXX part represents 12 bytes of data, some of them unprintable, and should be replaced with the byte sequence 120 47 253 22 194 9 183 44 196 55 125 246.

For convenience, here is a base64 encoded version:

JzonL3t+fS81LzptOzEyJTpoOyJ4L/0Wwgm3LMQ3ffYiey4uMzE4XCU5LycgJypAMTIlLmg9Mipc
bT0rJ29taHgnPUA4NS9uKn0l

Example run:

$ echo -n "JzonL3t+fS81LzptOzEyJTpoOyJ4L/0Wwgm3LMQ3ffYiey4uMzE4XCU5LycgJypAMTIlLmg9MipcbT0rJ29taHgnPUA4NS9uKn0l" | base64 -d > saving-time.gs
$ ls -l saving-time.gs
-rw-r--r-- 1 ahammar ahammar 75 2012-01-29 17:31 saving-time.gs
$ ruby golfscript.rb saving-time.gs <<< "15:37"
        o
    o       o

 o             o

o               h

 o             o

    m       o
        o


Ruby, 210

a=$*.map.with_index{|a,i|[a.to_i%2<<i,a.to_i[1]<<i]}.transpose.map{|a|a.inject &:+}
$><<"#{%w(Fighting
Flying
Poison
Ground
Rock
Bug
Ghost
Steel
Fire
Water
Grass
Electric
Psychic
Ice
Dragon
Dark)[a[0]*15/63]} #{a[1]*40/63+30}"

First time golfing, so I guess this is pretty obvious solution.


Charcoal, 22 bytes

Ｆ⪪θ «↑⸿⸿ＦＬι«Ｍ¬﹪κＩη↙§ικ

Try it online! Link is to verbose version of code. Explanation:

  θ                      First input
 ⪪                      Split on spaces
Ｆ   «                   Loop over each word
     ↑⸿⸿                Move the cursor to the top row and two columns right*
          ι             Current word
         Ｌ              Length
        Ｆ  «            Loop over implicit range
               κ        Current index
                 η      Second input
                Ｉ       Cast to integer
              ﹪         Modulo
             ¬          Logical not
            Ｍ     ↙     Move that many characters down and left
                    ι   Current word
                     κ  Current index
                   §    Index into word and implicitly print

*More precisely, "move to the start of the next line twice, but as if the canvas was rotated." Edit: In between this challenge being set and this answer being accepted, Charcoal actually acquired a means of splitting a string into pairs of characters, reducing the code 16 bytes:
Ｆ⪪θ «↑⸿⸿Ｆ⪪ιＩη«κ↙ Try it online! Link is to verbose version of code. Explanation:

  θ                 First input
 ⪪                  Split on spaces
Ｆ   «               Loop over each word
     ↑⸿⸿            Move the cursor to the top row and two columns right
          ι         Current wordＩη
            η       Second input
           Ｉ        Cast to integer
         ⪪          Split into substrings of that length
        Ｆ    «      Loop over each substring
              κ     Print the substring
               ↙    Move the cursor down and left


Composition of permutations – the group product

Haskell, 157 148 bytes

EDIT:

-9 bytes: That could indeed be golfed more. Removed redundant parentheses around p++q. Swapped argument order of g. Got rid of d by starting iterate with p x, after which takeWhile no longer tied with fst + span. Made iterate infix.

Doing this while I'm late... probably can golf some more.

It was simpler, and seemed to be allowed, so the output includes single-element cycles.

q#p=g(p++q>>=id)$f q.f p
f p a=last$a:[y|c<-p,(x,y)<-zip(0:c)(c++c),x==a]
g(x:l)p|c<-x:fst(span(/=x)$p`iterate`p x)=c:g[x|x<-l,x`notElem`c]p
g[]p=[]

Try it online!

How it works:

# is the main function. q#p takes two lists of lists of numbers, and returns a similar list. The tests seem to have Q before P so I used the same order.
f p converts the permutation p from disjoint cycle form to a function, after which f q and f p can be composed with the usual composition operator ..

The list comprehension iterates through the cycles c, searching for a and finding its successor. If the comprehension finds nothing, a is just returned.
zip(0:c)(c++c) is a list of pairs of elements of c and their successors. Since the question lets us "start at one" we can use 0 as a dummy value; it's cheaper to prepend that to zip's first argument than to use tail on the second.

g l p takes a list l of elements, and a permutation function p, and returns the list of cycles touching the elements.

Here c is the cycle containing the first element x of the list, the other elements of c are found by iterating from p x until x is found again. When recursing to find the remaining cycles, all elements of c are first removed with a list comprehension.


Jelly, 8 bytes

ŒPIE$ÐfṪ

Try it online! or verify all test cases.

How it works

ŒPIE$ÐfṪ  Main link. Argument: A (list of integers)

ŒP        Powerset; generate all sublists of A, sorted by length.
     Ðf   Filter the powerset by the link to the left:
    $       Combine the two atoms to the left into a monadic link.
  I           Compute all increments.
   E          Test whether they're all equal.
          This returns all arithmetic subsequences, sorted by length.
       Ṫ  Tail; extract the last sequence.


JavaScript (ES6), 158 bytes

f=(a,x=0,y=0,d=3)=>a[x]&&(c=a[x][y])?(a[x][y]=c=='.'?c:c=='/'?(d^=3,'\\'):c=='\\'?(d^=1,'/'):'v>^<'[d][d='^<v>'.search(c),0],f(a,d<3?x+d-1:x,d?y+d-2:y,d)+1):1

Developed independently from @tsh's answer although strikingly similar.

The mapping of directions ^<v> to integers 0-3 is governed by the fact that .search('^') returns 0 since ^ is a regexp metacharacter.


Concatenate lists of strings item-wise in Python

20 chars

map(str.__add__,a,b)

Uses the build-in method string addition method __add__ that is invoked by + on strings in place of your anonymous function lambda x,y:x+y.


Sr. 4Der says make this shape! (Episode 1)

JavaScript (Node.js), 428 bytes
Uses 0 instead of #.

_=>Buffer('QaV6:)R/rEkQy|:|\\!8GG6Pzy}lO<:xv-q,GoKfhfkci;Br"? &]N9Xx[}~tvc1Z6;%Fq6>DO(9dGs&sG~n@z},=x7]+Qo4y}~8Tr~>45<y#J;_a-^"X=^:?`(8*QQh"GQ.V0>GBpa~ytaJYb^YJdo=/W&59kP#@pZ-pYt-uLLe-lDv/kV|}.ylnY<-$H@G&H{h4PPL%q&7t?1.?t}cI6Fcz-Nvo_wPUPP:Xh|tG0zp)lNIh`Ah-d"t.+0L8&}M6LK.Mr$4rH\'l(x4p4_v|[gdf-~9qo,c{U\\Vw(RCYJrd`^&G[{Tr$PGPkS\'$iaBKm{q').reduce((p,c)=>p*95n+BigInt(c-32),0n).toString(2).match(/.{62}/g).join`
`.split`1`.join` `

Try it online!
Not sure if it was intentional but, contrary to appearances, the tesseract is not symmetrical.
Storing only the upper part and encoding the differences for the lower part would most certainly be more efficient in some languages, but I didn't find a short enough way to do that in JS.
So this is just a binary to base-95 compression for now.
Note: With RegPack, we get 480 bytes. (Not a fully optimized version, but we could only shave a couple of bytes.)


MATLAB, 100 bytes

function X=o(m,s)
X=find(bintprog(-1*s(:,3),[s(:,2)';s(:,1)';-1*s(:,1)'],[m(2);m(1)+5;5-m(1)])==1);

The Binary Optimization problem is solved through the bintprog function, available in Matlab2013b; this function was replaced by intlinprog in newer Matlab versions.

Inputs are a vector (m), for movie constraints, and a matrix (s), for the scenes. In particular m is a two-element row vector [running_time budget], while s is a Nx3 matrix, where N is the number of the scenes and each row is made up of [running_time costs importance].


JavaScript (ES6), 99 bytes

f=(s,a,i=a.findIndex(w=>s.startsWith(w)))=>s?(~i?a[i+1]||a[0]:s[0])+f(s.replace(a[i]||s[0],''),a):s


Ruby, 94 96 bytes

Using loops to do concatenations that followed such a simple pattern felt cumbersome, so I utilized the creative use of join instead, further golfed by the fact that array*str is equivalent to array.join(str)

+2 bytes to fix a typo I made that just so happened to return the same result on the test example by chance.

I=->k{eval"->f#{[*0..k]*'{->f'}{f#{k}.times{f1=f0[f1]};f1#{"[f#{[*2..k]*'][f'}]"if k>1}"+?}*-~k}

Try it online!


JavaScript (ES6), 41 40 38 bytes
Saved 2 bytes thanks to @ETHProductions and 1 byte thanks to @Craig Ayre.
s=>s.map(e=>t+=e*(i^=2),t=i=1)|t%10==1

Takes input as a list of digits.
Determines the sum of all digits, including the checksum.
If the sum is a multiple of 10, then it's a valid barcode.
Test Cases

let f=

s=>s.map(e=>t+=e*(i^=2),t=i=1)|t%10==1

console.log(f([2,0,3,7,8,2,4,0]));
console.log(f([3,3,7,6,5,1,2,9]));
console.log(f([7,7,2,3,4,5,7,5]));
console.log(f([0,0,0,0,0,0,0,0]));

console.log(f([2,1,0,3,4,9,8,4]));
console.log(f([6,9,1,6,5,4,3,0]));
console.log(f([1,1,9,6,5,4,2,1]));
console.log(f([1,2,3,4,5,6,7,8]));


Who was the biggest "Weekend Update" host during that time period?

Python 2, 291 bytes

def f(b,e):
 s=''.join('A AB BC BCD BD BDE EFGH GHJ J JK KL L L L L L LM M M MN N N N O O OPQ PQ PQ PQ PQR QR QRS RS RS S S S S ST STUV UV UV UV'.split()[b-1975:e-1974]);C=s.count;return''.join({'CJDBCGBMCBCDKNCJTASCCMCCAMRMDGEHGMNMQFFPMSJC'[ord(h)-65::22]for h in s if C(h)==max(map(C,s))})

Try it online!


Mathematica, 32 bytes

1##&@@(1-2/(Prime@Range@#^2+1))&

An unnamed function that takes integer input and returns the actual fraction.

This uses the fact that (p2-1)/(p2+1) = 1-2/(p2+1). The code is then golfed thanks to the fact that Mathematica threads all basic arithmetic over lists. So we first create a list {1, 2, ..., n}, then retrieve all those primes and plug that list into the above expression. This gives us a list of all the factors. Finally, we multiply everything together by applying Times to the list, which can be golfed to 1##&.

Alternatively, we can use Array for the same byte count:

1##&@@(1-2/(Prime~Array~#^2+1))&


Making Future Posts Runnable Online with Stack Snippets

Python 2 (No STDIN)
Thanks to Skulpt, it has become very easy to write a Python interpreter.

function out(text) {
  var output = document.getElementById("output");
  output.innerHTML = output.innerHTML + text;
}

function builtinRead(x) {
  if(Sk.builtinFiles === undefined || Sk.builtinFiles["files"][x] === undefined)
    throw "File not found: '" + x + "'";
  return Sk.builtinFiles["files"][x];
}

function run() {
  var program = document.getElementById("python-in").value;
  var output = document.getElementById("output");

  output.innerHTML = "";

  Sk.canvas = "canvas";
  Sk.pre = "output";

  Sk.configure({
    output: out,
    read: builtinRead
  });

  try {
    Sk.importMainWithBody("<stdin>", false, program);
  }
  catch(e) {
    throw new Error(e.toString());
  }
}
#python-in {
  border-radius: 3px;
  background: rgb(250, 250, 250);
  width: 95%;
  height: 200px;
}

#output {
  border-radius: 3px;
  background: lightgray;
  width: 95%;
  height: 200px;
  overflow: auto;
}

#canvas {
  border: 1px solid gray;
  border-radius: 3px;
  height: 400px;
  width: 400px;
}

Python code:

<textarea id="python-in" name="python-in" rows="10" cols="80"></textarea>

<button id="run-code" onclick="run()">Run</button>

Output:

Canvas for turtles:

<canvas height="400" width="400" id="canvas">Your browser does not support HTML5 Canvas!</canvas>

No STDIN, but it's a pretty complete implementation of Python in JS. I would load the libraries from somewhere else but I can't find a host of them.


Ruby (188)

takes the filename to read words from as argument.

q=*$<
s=0
4.upto(12){|n|o=''+w=q.grep(/^#{?.*n}$/).sample
[*0..n-1].sample(c=n/3).map{|i|o[i]=?*}
puts"Level #{n-3}",?=*7,o
puts STDIN.gets==w ?(s+=c;"correct"):"wrong","score: #{s}0",""}


Revised answer for "better" scoring system
C89 / C99, Score: 0
My program is 52 characters long and uses the same mechanism as in my original answer to achieve the different output. This works because C89 doesnt treat // as a comment:
i=32;main(){putchar(i+++0//**/
+52)&&i<84&&main();}

The results:
$ ./diff2c89
 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRS
$ ./diff2c99
TUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~⌂Çüéâäàåç
$ ./diff2c99 | wc
      0       1      52
$ ./diff2c89 | wc
      0       1      52
$ wc diff2.c
      1       2      52 diff2.c

Old answer:
C89 / C99, Score: -Infinity?
I'm not entirely sure if this program doesn't break the rules, but never mind.
This program exploits the fact that in C89 // is not a valid comment but /* ... */ is.
Using the comment trick an other function is executed. In C89 the function just prints "trolololol..." until the stack overflows (so it might finish within 2 seconds).
f1(){printf("ol");f1();}
f2(){printf("oll");}
main(){
    printf("tr");
    void (*f[])() = {f1,f2};
    f[0 //* trollololol */
      +1]();
}

C99
$ ./diffc99
troll

C89
$ ./diffc89
trolololololololololololololololololololololololololololololololololololololololololo
lolololololololololololololololololololololololololololololololololololololololololol
ololololololololololololololololololololololololol ....


How many goals has Steven Gerrard scored?


Charcoal, 31 bytes

Ｆ⮌…⁰ＮＢ⁺²⊘×ι⁺³ι⭆α§α⁺λ÷×ι⊕×ι⁺⁹⊗ι⁶

Try it online! Link is to verbose version of code. Note: The deverbosifier outputs a trailing separator for some reason. Explanation:

Ｆ⮌…⁰ＮＢ

Draw boxes in reverse order of size (largest to smallest).

⁺²⊘×ι⁺³ι

Calculate the size of the box.

⭆α§α⁺λ

Draw the border of the box using a rotated alphabet.

÷×ι⊕×ι⁺⁹⊗ι⁶

Calculate the letter that would appear at the top left of the box (0-indexed).


Haskell, 77 71 62 bytes

f@(d:e)#(p:q)=f:[e,f++take d q]!!p#q
_#_=[]
a!b=tail$a#cycle b

Try it online!

Edit: -9 bytes thanks to @xnor.


Convert RGB integer value into RGB values

AVR ABI, 0

Quantities larger than the registers in the AVR's registers are represented with multiple registers. So, when passing in a 32-bit 'n' to a function, it is passed as 4x8-bit registers. Effectively R(r24),G(r23), and B(r22) are directly addressable without any additional work by virtue of the CPU's register addressing.

Here's some 'C' code for the unpacking operation:

unsigned char r( unsigned long n ){return n>>16&255;}
unsigned char g( unsigned long n ){return n>>8&255;}
unsigned char b( unsigned long n ){return n>>0&255;}

disassembled examples from avr-gcc 4.8:

.global r
.type   r, @function
r:
ret
.size   r, .-r

.global g
.type   g, @function
g:
mov r24,r23
ret
.size   g, .-g

.global b
.type   b, @function
b:
mov r24,r22
ret
.size   b, .-b

For red, GCC just emits the return code since the red byte just happens to be in the return register already. For green and blue it copies the corresponding register into the return register and returns. The actual packing/unpacking is handled by the ABI - when done somewhere other than a function call boundary, it's handled purely by the register addressing. Both the copies and return opcode are overhead required to view this happening in the CPU - the compiler can use these registers directly if not required to place the result in the return register. Free RGB packing/unpacking is available when handing any 32-bit integer.

Another way to think about it is that the AVR's registers represent large numbers as a list of 8-bit registers, and that list happens to unpack RGB for us.


Find the longest path, avoiding obstacles in a 2D plane

Python 3, 2619 bytes (90 LOC), ~6 seconds (20x20)

#!/usr/bin/env python

import networkx as nx

class input(object):
    def __init__(self,world_string):
        rows=world_string.split("\n")
        column_count=len(rows[0])
        blocked_cells=[]
        x=0
        y=-1
        for row in rows:
            if len(row)>column_count:
                column_count=len(row)
            y+=1
            for column in row:
                if column=='1':
                    blocked_cells.append((y,x))
                x+=1
            x=0
        self.matrix=world(len(rows),column_count)
        self.block_graph(blocked_cells)
        self.matrix.add_sink()

    def block_graph(self,block_list):
        for cell in block_list:
            self.matrix.block_cell(cell)

class world(object):
    SINK="END"

    def __init__(self, rows=3, columns=3):
        self.graph=nx.grid_2d_graph(rows, columns)
        for e in self.graph.edges():
            self.graph[e[0]][e[1]]["weight"]=-1.0

    def block_cell(self,node):
        neighbours=list(self.graph[node].keys())
        for linked_node in neighbours:
            self.graph.remove_edge(node,linked_node)

    def add_sink(self):
        matrix=self.graph.nodes()[:]
        self.graph.add_node(world.SINK)
        for source_cell in matrix:
            self.graph.add_edge(source_cell, world.SINK, weight=1.0)

class algorithm(object):
    SOURCE=(0,0)
    def find_path(graph):
        def _heuristic(current, target):
            if current==target:return 0.0
            cost=nx.astar_path(graph, algorithm.SOURCE,current,lambda x,y:1)
            return -1 * len(cost)
        path=nx.astar_path(graph, algorithm.SOURCE, world.SINK, _heuristic)
        return path[:-1]

class output(object):
    directions={
        ( 1,  0)  : "n",
        (-1,  0)  : "s",
        ( 0,  1)  : "w",
        ( 0, -1)  : "e"
    }

    def edge_to_direction(source_node, dest_node):
        row_delta=source_node[0]-dest_node[0]
        column_delta=source_node[1]-dest_node[1]
        return output.directions[(row_delta, column_delta)]

    def path_to_directions(path):
        result=""
        for step in range(len(path)-1):
            result+=output.edge_to_direction(path[step],path[step+1])
        return result

    def simplify_directions(directions):
        directions+="\0"
        count=0
        result=""
        last=""
        for d in directions:
            if d!=last or d is "\0":
                result+="{} {},".format(last, count)
                count=0
                last=""
            if count==0:
                last=d
                count=1
                continue
            if d==last:
                count+=1
        return result[3:-1]

if __name__=='__main__':
    contents="010\n000\n100"    #read from file?

    data=input(contents).matrix.graph
    result_path=algorithm.find_path(data)
    directions=output.path_to_directions(result_path)
    directions=output.simplify_directions(directions)
    print(directions+"\n")
    print(str(result_path)[1:-1].replace('), (',') --> (').replace(', ',','))

Performance

I ran this solution (on my old Core i3 laptop) on the 20x20 'performance' example input and it ran in around ~6 seconds (of course, YMMV).  I am SURE there are ways to do this faster, probably by orders of magnitude.  However, I didn't feel like re-writing my own A* algorithm in assembly and renting some time slices on a super computer!

About this Code

The Idea

The idea for this approach comes from my answer over here in Code Review.  You can also read a little bit more about it and the end of my answer here.

Dependencies

As you may have notice by the (rather prominent) line import networkx as nx - this code relies upon the Python NetworkX module to function.  So do >pip install networkx if you get import errors when running.

Breakdown of Solution Elements by Lines of Code

I also thought it would be interesting (and it was), after Don Muesli's comment (particularly the part "a significant part of the efffort[sic] is formatting the output"), to examine how much of the code is for various things.

      Breakdown:

39 lines (or 43.33%) of the lines of code in the program are concerned with parsing the input and constructing/weighting the graph data structure.
37 lines (approx. 41%) directly relate solely to displaying and formatting the desired output!
5 lines (5.5%) are 'other' stuff, which relates to running the program (shebang line, imports, the if __name__=="__main__"..., etc).
And 9 (yes.. nine) lines of code (or just 10%) actually relates to the algorithm usage.

      Obligatory Pie Chart:

About the Approach

As I mentioned above, most of the idea for this approach comes from my answer over on Code Review regarding this problem.

The process itself is relatively straightforward:

Transform the given matrix into an undirected graph data structure
Annotate (i.e. add weights) the edges of that graph
Add a "sink" node - to be used as a search target
Add (weighted) edges between all nodes and the sink node
Use a Graph Search Algorithm (in this case A*)

So, taking the 3x3 matrix from the question for example.  The transformation into a graph would yield something like the following:

(Note: the 'blocked' nodes do not have any edges)

Step 2; imagine each green line in the above picture has a weight of -1.

Next, for step 3 and 4 together (I didn't want to have to make another picture), take a look at the following graph:

And again imagine the edges are weighted, only red lines are weighted +1.

We can then apply the A-star algorithm from the NetworkX library to this graph, using the custom heuristic function.
This makes the search algorithm score paths in an inverse manner (longest path rather than shortest).  And the longest path will be the one that visits the most cells of the problem matrix!


PHP + JQuery + HTML + CSS, 1535 bytes

This is a submission leaning more towards what the OP deemed as 'the actual goal'. That is, a fully functional chat server, which may be hosted on just about any web server anywhere.

Functionality includes:

Notifications when users enter or leave the chat room.
Notifications when users change their alias.
Real time polling for new messages, without generating excess server traffic, or server load.
Layout and usability strongly resembling existing chat clients, such as X-Chat.

To being a session, enter an alias in the appropriate box, and press Tab or Enter to submit. If the alias is already in use, you will be notified. Sending messages is also done via Enter.

For your convenience, an archive of all files may be found here: chat.zip (choose Download from the File menu). To install, unpack to a web directory on any server running PHP 5.4 or higher.

Caveats:

IE 8 or lower will spin into an infinite loop while polling, because for some reason unknown to humanity, all Ajax requests are cached by default. It also prevents you from sending the same message twice, and updating the user list properly. This could be fixed by adding cache:false to every Ajax request.
In all version of IE, messages will not be sent by pressing Enter, because the change event is not triggered (pressing Tab, however, does work). This could be fixed by adding an onkeypress handler, checking if the key was Enter, and then calling $(v).blur().focus().

In short, IE is not supported.

Client

Positioning of elements could be a bit more robust, but it should look alright with a minimum window size of about ~800x600.

chat.htm (190 bytes)

<link rel=stylesheet href=c.css>
<select id=u multiple></select>

<input id=n onchange=u()><input id=v onchange=s()>

c.css (136 bytes)

i{color:#999}
#u{float:right;height:100%;width:200px;margin-left:10px}
#o{border:1px solid #999;height:93%;overflow-y:scroll}
#v{width:54%}

c.js (435 bytes)

var l
(function p(){
  $.ajax({url:'p.php',data:{n:$('#n').val()},success:function(d){
    $('#o').html(d).scrollTop(1e4);$('#u').load('n.php');
  },complete:p,timeout:2e4})
})()
function s(){
  $.get('s.php',{n:$(n).val(),v:$(v).val()})
  $(v).val('')
}
function u(){
  $.get('u.php',{l:i=l,n:l=$(n).val()}).fail(function(){
    alert("This name is already in use!")
    $(n).val(l=i)
  })
}
$(window).on('unload',function(){$.ajax({url:'l.php',data:{l:l},async:false})})

Server

I apologize for the server being broken up into so many tiny chunks. The alternative would be to use an adequate message protocol (via JSON encode/decode), or having a large if ... elseif ... according to which post variables are present. Making separate scripts, an just requesting from the one you need is a lot shorter, and perhaps simpler than both.

o.php (119 bytes) Opens as connection to the 'database'

<?$m=array_slice(unserialize(file_get_contents(m)),-300);
$u=unserialize(file_get_contents(u));$t=time();extract($_GET);

c.php (57 bytes) Commits changes to the 'database'

<?foreach([u,m]as$c)file_put_contents($c,serialize($$c));

p.php (151 bytes) Polls for new messages

<?for($t=time();@filemtime(m)<$t;usleep(1e3))clearstatcache();include('o.php');
foreach($m as$v)if($n&&$v[0]>=$u[$n])echo@date("[H:i]",$v[0])."$v[1]\n";

s.php (62 bytes) Send a message to the server

<?include('o.php');$m[]=[$t,"$n: $v"];include('c.php');

u.php (222 bytes) User registration or alias change

<?include('o.php');if(!trim($n)||$u[$n])exit(header('HTTP/1.1 418'));
$m[]=[$t,$u[$l]?
"$l is now known as $n.":
"$n has entered the chat."];
$u[$n]=$u[$l]?:$t;unset($u[$l]);include('c.php');

n.php (65 bytes) Retrieves the list of user names

<?include('o.php');foreach($u as$k=>$v)echo"<option>$k</option>";

l.php (98 bytes) User has left (closed their browser)

<?include('o.php');$m[]=[$t,"$l has left the chat."];
unset($u[$l]);include('c.php');


Calculate probability of getting half as many heads as coin tosses.

Pari/GP - 32 30 34 chars

print(binomial(n=input(),n\2)/2^n)


PMA/Snails, 130
.!(z\ |o{c..!(z\ }3){w=(..!(z\ )|b..!(z\ )o{..!(z\ }2|c{..!(z\ }1,2w..!(z\ )|w{..!(z\ }1,2c..!(z\ }4o..!(z\ )(..!(z\ )|n..!(z\ )`2

or more "readably",
?
.!(z\  | o{c..!(z\ }3  )
{w =( ..!(z\ ) | b ..!(z\ ) o {..!(z\ }2  | c {..!(z\ }1,2w..!(z\ ) | w {..!(z\ }1,2c..!(z\  }4
o  ..!(z\ ) ( ..!(z\ ) | n ..!(z\ ) `2

Unusually, a problem came along that can be handled by the limited amount of features implemented so far. The !(z\ ) pattern determines that the current position is at the space in the middle of a square using a negative assertion that there is a space in some "octilinear" direction. The general idea is to check for a pattern that places a square at each of the 5 necessary locations relative to the square that the match starts on. Also, it needs to check that it is not in a 2x2 block of squares. Before the program would work, I had to fix a bug with the parsing of parentheses.
If the hexomino does not map a cube, 0 is printed. If it does, some positive integer is printed (number of matches).
I adapted this polyomino generator to create all possible test cases:
n=input()
r=range
T=lambda P:set(p-min(p.real for p in P)-min(p.imag for p in P)*1j for p in P)
A=[]
for i in r(1<<18):
 P=[k%3+k/3*1j for k in r(18)if i>>k&1]
 C=set(P[:1])
 for x in P:[any(p+1j**k in C for k in r(4))and C.add(p)for p in P]
 P=T(P)
 if not(C^P or P in A or len(P)-n):
  #for y in r(4):print''.join(' *'[y+x*1j in P] for x in r(6))
  o = [ [' ']*13 for _ in r(9)]
  for y in r(4):
   for x in r(6):
    if y+x*1j in P: X=2*x;Y=2*y; o[Y][X]=o[Y+2][X]=o[Y][X+2]=o[Y+2][X+2]='+'; o[Y][X+1]=o[Y+2][X+1]='-';o[Y+1][X+2]=o[Y+1][X]='|'
  print '\n'.join(map(''.join,o))
  A+=[T([p*1j**k for p in P])for k in r(4)]


Compute the antipode of a point on curve

Python 2, 333 221 215 bytes

-17 bytes thanks to @JanDvorak

g=input()
y=map(max,g).index('P')
x=g[y].index('P')
m=[k[:]for k in g]
v=x;w=y
while'#'in sum(m,[]):x,y,(v,w)=v,w,[(x+a,y+b)for a,b in((1,0),(-1,0),(0,1),(0,-1))if'#'==m[y+b][x+a]][0];m[w][v]='_'
g[w][v]='A'
print g

Try it online!

Python 3, 402 288 282 bytes, String IO

g=[[*k]for k in open(0).read().split('\n')]
y=[max(k)for k in g].index('P')
x=g[y].index('P')
m=[k[:]for k in g]
v=x;w=y
while'#'in sum(m,[]):x,y,(v,w)=v,w,[(x+a,y+b)for a,b in((1,0),(-1,0),(0,1),(0,-1))if'#'==m[y+b][x+a]][0];m[w][v]='_'
g[w][v]='A'
print('\n'.join(map(''.join,g)))

Try it online!

Animation of the code running:


Python 2, 97 bytes + 237 matches = 334

lambda w:sum(map(('1ir'*2+'7lnu'*3+'4cfhjoy'*4+'235bdegpqsxz'*5+'069a'*6+'8'*7).count,w.lower()))

Try it online!

This works by generating a string where each buildable character appears the same amount of matchsticks required to build that character


Retina 0.8.2, 113 107 67 66 bytes

+`\(\)|(\()?(\(((\()|(?<-4>\))|[^()])*(?(4)@)\))(?(1)|(\)))
$5$2$1

Try it online! Includes 3 4 byte saving thanks to @MartinEnder. Explanation:

+`

Repeatedly apply the substitution until there are no matches.

\(\)|

Match an empty loop (in which case nothing is captured so the substitution simply deletes it) or:

(\()?

Optionally match a (. This is captured in group 1 if it matched, but not if it didn't.

(\(

Capture the main body of the match in group 2 and match a (.

(
 (\()
|
 (<-4>\))
|
 [^()]
)*

Repeatedly match either a (, capturing it in group 4, or a ), removing a capture from group 4 (failing if there isn't one), or something else.

(?(4)@)

Ensure that there are no spare captures left in group 4.

\))

End capture group 2 with another ).

(?(1)|(\)))

If capture group 1 was empty, then capture a ) in capture group 5. (So exactly one of those two groups will have a capture).

$5$2$1

Move the bracket captured in either group 1 or group 5 to the other side of group 2. This has the effect of moving the inner loop to the front or the end of the outer loop depending on which side it matched.


CJam (snapshot), 41 38 bytes

q~"<<^X^G"{imd\}%W%"wdhms":s.+_{0=}#><S*

The above uses caret notation, since two of the characters are unprintable.

Thanks to @Sp3000 for golfing off 2 bytes.

Testing

The latest stable release (0.6.5) has a bug that can cause {}# to return Integers instead of Longs. Quite paradoxically, this can be circumvented by casting to integer (i).

To run this with code with the online interpreter, click this permalink or copy the code from this paste.

Alternatively, you can download and build the latest snapshot by executing the following commands:

hg clone http://hg.code.sf.net/p/cjam/code cjam-code
cd cjam-code/
ant

You can create the CJam file like this:

base64 -d > game-time.cjam <<< cX4iPDwYByJ7aW1kXH0lVyUid2RobXMiOnMuK197MD19Iz48Uyo=

How it works

q~        e# Read an evaluate the input.
"<<^X^G"  e# Push the string corresponding to the array [60 60 24 7
{         e# For each character:
  i       e#   Replace it by its code point.
  md      e#   Push divisor and residue of the division by that code point.
  \       e#   Swap their order.
}%
W%        e# Reverse the resulting array.
"wdhms":s e# Push ["w" "d" "h" "m" "s"].
.+        e# Perform vectorized concatenation.
_         e# Push a copy.
{0=}#     e# Find the index of the first pair with positive integer.
>         e# Remove the preceding pairs.
<         e# Truncate to the number of pairs specified in the input.
S*        e# Join, separating by spaces.


R, 58 54 50 48 43 bytes

-2 bytes thanks to MickyT

function(n)diffinv(rep(1:n%%2*2-1,1:n*2-1))

Try it online!

function(n)
 diffinv(                           # take cumulative sum, starting at 0 of
             1:n%%2*2-1,            # a vector of alternating 1,-1
         rep(                       # repeated
                        1:n*2-1))   # 1, 3, 5, etc. times


Count characters, turn them into a cipher

Bash/coreutils, 91 chars
tr a-z `echo {a..z} $1|fold -w1|grep '[a-z]'|sort|uniq -c|sort -rn|awk '{printf $2}'`<<<$1

Save as cipher.sh, chmod +x it and run:
$ ./cipher.sh "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nunc sed dui at nisi euismod pellentesque ac sed enim. Nullam auctor justo quis diam faucibus, eu fringilla est porttitor. Pellentesque vel pharetra nisl. Vestibulum congue ultrices magna a fringilla. Quisque porttitor, risus suscipit pellentesque tristique, orci lorem accumsan nisi, scelerisque viverra turpis metus sit amet sapien. Fusce facilisis diam turpis, nec lobortis dui blandit nec. Vestibulum ac urna ut lacus commodo sollicitudin nec non velit. Nulla cursus urna sem, at tincidunt sem molestie vel. Nullam fringilla ante eu dolor bibendum, posuere iaculis nunc lacinia. Sed ac pretium est, vel scelerisque nisl. Phasellus lobortis dolor sodales sapien mollis hendrerit. Integer scelerisque tempor tellus, viverra varius neque mattis in. Integer porta vestibulum nisl, et feugiat tortor tincidunt vel. Aenean dignissim eleifend faucibus. Morbi nec neque vel ante pulvinar mollis eu in ipsum."
Lvgld rqfjd uvmvg frh edlh, svpflshlhjg eurqrfsrpn lmrh. Njps flu ujr eh prfr ljrfdvu qlmmlphlfbjl es flu lprd. Njmmed ejshvg ojfhv bjrf ured tejsrijf, lj tgrpnrmme lfh qvghhrhvg. Plmmlphlfbjl jlm qaeglhge prfm. Vlfhrijmjd svpnjl jmhgrslf denpe e tgrpnrmme. Qjrfbjl qvghhrhvg, grfjf fjfsrqrh qlmmlphlfbjl hgrfhrbjl, vgsr mvgld essjdfep prfr, fslmlgrfbjl jrjlgge hjgqrf dlhjf frh edlh feqrlp. Fjfsl tesrmrfrf ured hjgqrf, pls mvivghrf ujr imepurh pls. Vlfhrijmjd es jgpe jh mesjf svddvuv fvmmrsrhjurp pls pvp jlmrh. Njmme sjgfjf jgpe fld, eh hrpsrujph fld dvmlfhrl jlm. Njmmed tgrpnrmme ephl lj uvmvg irilpujd, qvfjlgl resjmrf pjps mesrpre. Slu es qglhrjd lfh, jlm fslmlgrfbjl prfm. Paeflmmjf mvivghrf uvmvg fvuemlf feqrlp dvmmrf alpuglgrh. Iphlnlg fslmlgrfbjl hldqvg hlmmjf, jrjlgge jegrjf plbjl dehhrf rp. Iphlnlg qvghe jlfhrijmjd prfm, lh tljnreh hvghvg hrpsrujph jlm. Alplep urnprffrd lmlrtlpu tejsrijf. Mvgir pls plbjl jlm ephl qjmjrpeg dvmmrf lj rp rqfjd.
$


Mathematica, 88 bytes

Last[f@n_:=n;(r=f@1;{f@a,f@b}={f[b=+##],f[a=Abs[#-#2]]};r)&@@f/@{#,#+1}&/@Range@Input[]]

This is a full program, reading the input from a prompt. It's a very direct implementation of the definition, where I'm keeping track of the current sequence in f (whose values f[n] default to n).

Here is a slightly more readable version:

Last[
  f@n_ := n;
  (
    r = f@1;
    {f@a,f@b} = {f[b=+##],f[a=Abs[#-#2]]};
    r
  ) & @@ f /@ {#,#+1} & /@ Range @ Input[]
]

Some analysis

I've plotted the first 2000 elements of the sequence (it doesn't really get more interesting afterwards):

So the sequence is essentially linear with slope 2 and always has a few of those steps. It seems that the steps grow sublinearly (if they aren't even bounded), since they become barely noticeable as you increase the number of points you plot.

We can justify the linear growth quite easily (this is a bit handwavy, but I think it would hold up to a rigorous proof by induction): initially, the maximum affected number of a permutation step at n is n + (n+1) = 2n + 1. Also note that these numbers will always be moved to 1, since |n - (n+1)| = 1. So it's not surprising that we get numbers which are approximately 2n in the sequence. However, we can also note that for steps up to n, Sn+1 is always bounded by n+1, which means that no swapping step can swap two numbers which are both greater than n. Hence, numbers that still need to be processed will be less than or equal to their initial value. Hence, 2n + 1 is also the bound for the sequence itself.

I think finding an argument for the length of the steps will be trickier.


Haskell 618 603 598 525 512 504 480 464

Cards taken as a line of input. I think I've golfed this to death, but will easily be beaten by ruby etc using the same trick: if you generate all permutations, you get the forward sorts you want to look for straights, plus the reverse sorts you want for testing N of a kind.

import Data.List
m=map
z=take 5
q=m(\x->head[n|(f,n)<-zip"A23456789TJQK"[1..],f==x!!0])
l=m length
v=" of a kind"
w="flush"
y="straight"
c f s p r|f&&r="9royal "++w|f&&s='8':y++" "++w|f='5':w|s||r='4':y|True=case p of 4:_->"7four"++v;3:2:_->"6full house";3:_->"3three"++v;2:2:_->"2two pair";2:_->"1one pair";_->"0high card"
d x=c([5]==l(group$m(!!1)x))(q x==z[head(q x)..])(l$group$q x)$q x==1:[10..13]
k h=tail$maximum$m(d.z)$permutations$words h
main=interact k

Edited to inline "pair" and use number prefixes after seeing @FDinoff's entry, also composed map functions to shave one more char.


APL (Dyalog Unicode), 29 28 bytesSBCS

-1 thanks to @Adám

{≢∪∨.∧⍨⍣≡2>+/↑|∘.-⍨⍸⍵}¨⊂,~∘⊂

Try it online!

⊂,~∘⊂ the matrix and its negation

{ }¨ for each of them do

⍸⍵ list of pairs of coords of 1s

+/↑|∘.-⍨ matrix of manhattan distances

2> neighbour matrix

∨.∧⍨⍣≡ transitive closure

≢∪ number of unique rows


Is this string a letter doing a cartwheel?

sed 4.2.2, 30 + 1 -r = 43 31 bytes

Saved 12 bytes thanks to @Neil by shortening the first line

/nu|wm|qb/!d
/^((.).)\1*\2$/!d

Try it online!

Deletes input if falsey, otherwise does nothing to the input.

Explanation

With the -r flag, we do not need to use \( and \) for capturing groups and this saves bytes.

/nu|wm|qb/!                # On every line that does not match this regex
           d               # Delete
/^((.).)\1*\2$/!           # On every line that does not math
 ^((.).)                   #  the first two characters at the beginning of the line
        \1*                #  repeated
           \2$             #  with the first character at the end of the line
                d          # Delete


Weighted average - the pressup trend problem

Python 3, 38 bytes

lambda x:sum(x+x[7:]+x[14:]+x[21:])/70

Try it online!


Convert arbitrary roman numeral input to integer output

Mathematica, 33 chars
FromDigits[InputString[],"Roman"]


><>, Score: 41+41 = 82

Edit: both contained a 3. Fixed

'd3*}>a!o-!<<8:5@lI55>@z:5ll55>>q:>|q::|,

and

"r00gr40g44++bb+0p64++?b6+0.22#eW4s )Z

Try it online! (swap the lines to get the other output) With verification this time!

><> is an especially hard language to use here, as there is only one way to output characters, the command o. Fortunately, we can use the put command to place an o in the source code during execution, like in my Programming in a Pristine World answer.

This one took a lot of trial and error. I started off with the two mutually exclusive programs:

'd3*}>N!o-!<<data

and

"r00gr40g8+X0pN+?Y0.data

Each one transforms itself and its data by N, the first one subtracting and the second adding. It then outputs this in reverse. The point is that the data after each program is the other program in reverse, shifted by N. (X is the cell number where the program needs to put the o and Y is the cell where the pointer loops back to. ? is where the o is put).

Both follow the same structure, represented in different ways. They run a string literal over the entire code, adding it to the stack. They recreate the string literal command they used and put it at the bottom of the stack. They loop over the stack, adding/subtracting N to each character and printing them.

The first program uses ' as the string literal, and the simple d3*} to create the value 39 and push it to the bottom of the stack. The second uses " as the string literal with the same function. It reverses the stack, gets the character at cell 0,0 and reverses the stack again. It then gets the value at cell 4,0 (g) and adds 8 to it to get o and puts that at X.

Both programs use a different method of looping. The first program uses the skip command (!) to run only half the instructions while going left, reverses direction and runs the other half. The second uses the jump command (.) to skip backwards to the start of the loop at cell Y. Both of these run until there are no more items on the stack and the program errors.

I ran into a number of problems with most of the lower values of N, because shifting one character would turn it into another character essential for that program (and therefore couldn't be used as data for the other program) or two characters from the two programs would shift into the same character. For example:

++1 = , = --1
.+2 = 0
* = --3
g+4 = k =  o-4

etc.

Eventually I got to 10 (a), where I was able to avoid these issues. There might be a shorter version where the shifts are reversed, and the first program is adding N while the second subtracts it. This might be worse off though, as the first program is generally on the lower end of the ASCII scale, so subtracting is better to avoid conflicts.


Python 2, 60 bytes

def f(l):z=zip(l,range(len(l)));print map(sorted(z).index,z)

Try it online!

Uses zero-indexing.

A fast algorithm with a simple idea. If we instead need to permute the input list to make it as close to \$(1,2,...,n)\$ as possible, we should just sort it, as proven below. Since we're instead permuting \$(1,2,...,n)\$, we choose the permutation that's ordered the same way as the input list, like in my challenge Imitate an ordering (except the input may have repeats). (Edit: miles pointed out this more identical challenge, where Dennis has this same answer.)

  Claim: A permutation of the list \$l\$ that minimizes its distance to \$(1,2,...,n)\$ is \$l\$ sorted.

  Proof: Consider some other permutation \$l'\$ of \$l\$. We'll prove it can't be better than \$l\$ sorted.

  Pick two indices \$i,j\$ that \$l'\$ has out-of-order, that is where \$i<j\$ but  \$l'_i > l'_j\$. We show that swapping them can't increase the distance to \$(1,2,...,n)\$. We note that swap changes the contribution these two elements as follows:
  $$ |l'_i - i | + |l'_j - j | \to |l'_i - j | + |l'_j - i|.$$

  Here's a neat way to show this can't be an increase. Consider two people walking on a number line, one going from \$l'_i\$ to \$i\$ and the other from \$l'_j\$ to \$j\$. The total distance they walk is the expression on the left. Since \$i<j\$ but \$l'_i > l'_j\$, they switch who is higher on the number line, which means they must cross at some point during their walks, call it \$p\$. But when they reach \$p\$, they could then swap their destinations and walk the same total distance. And then, it can't be worse for them to have walked to their swapped destinations from the start rather than using \$p\$ as a waypoint, which gives the total distance on the right-hand side.

  So, sorting two out-of-order elements in \$l'\$ makes its distance to \$(1,2,...,n)\$ smaller or the same. Repeating this process will sort \$l\$ eventually. So, \$l\$ sorted is at least as good as \$l'\$ for any choice of \$l'\$, which means it as optimal or tied for optimal.

Note that the only property of \$(1,2,...,n)\$ that we used is that it's sorted, so the same algorithm would work to permute any given list to minimize its distance to any fixed list.

In the code, the only purpose of z=zip(l,range(len(l))) is to make the input elements distinct, that is to avoid ties, while keeping the same comparisons between unequal elements. If the input we guaranteed to have no repeats, we could remove this and just have lambda l:map(sorted(l).index,l).


JavaScript (ES6), 73 72 64 63 54 42 39 bytes

Thanks to Neil for saving 13 bytes

a=>a.map(b=>b.split` `.length)=='5,7,5'

Explanation

This is a fat-arrow function that takes an array of strings as argument. It replaces each line by its word count. If it is a haiku-w, a now contains an array of a five, a seven and a five again. Since JavaScript doesn't allow us to compare 2 arrays at the same time, the array is converted to a string first, and then compared. This results in a boolean that is returned.


Make the Matrix Digital Rain using the shortest amount of code

HTML, Javascript and CSS: 1024 bytes, 47 points

Features:

Uses Unicode characters (don't think this scores any points though)
Trails fade from bright to dark green while they are being drawn (*)
Trails also fade from dark green to black after the drawing has finished (*)
Random text size in each trail (*)
Trails are randomly repositioned and resized each time they are drawn

(*) I'll claim +5 points for each of these, but let me know if you disagree :-)
Demo:
http://ruletheweb.co.uk/matrix.html
Source code:
Exactly 1024 bytes. It's a bit ugly, I'm afraid.
<head><style>*{margin:0;padding:0;line-height:1;overflow:hidden;}div{width:1em;position:absolute;}</style><script>
w=window;n=w.innerWidth;m=w.innerHeight;d=document;q="px";function z(a,b){return Math.floor(Math.random()*(b-a)+a)}f=" 0123456789";for(i=0;i<45;i++)f+=String.fromCharCode(i+65393);function g(){for(i=0;i<90;i++){r=d.createElement("div");for(j=z(20,50);j;j--){x=d.createElement("pre");y=d.createTextNode(f[z(0,56)]);x.appendChild(y);x.style.opacity=0;r.appendChild(x)}r.id="r"+i;r.t=z(-99,0);with(r.style){left=z(0,n)+q;top=z(-m,0)+q;fontSize=z(10,25)+q}d.body.appendChild(r);setInterval("u("+i+")",z(60,120))}}function u(j){e=d.getElementById("r"+j);c=e.childNodes;t=e.t+1;if((v=t-c.length-50)>0){if((e.style.opacity=1-v/32)==0){for(f in c)if(c[f].style)c[f].style.opacity=0;with(e.style){left=z(0,n)+q;top=z(-m/2,m/2)+q;opacity=1}t=-50}}e.t=t;if(t<0||t>c.length+12)return;for(f=t;f&&f>t-12;f--){s=1-(t-f)/16;if(f<c.length&&c[f].style){c[f].style.opacity=s;}}}
</script><body text=#0f0 bgcolor=#000 onload=g()>


Jelly, 9 bytes

÷400⁵*÷S$

Try it online! or View all test cases.

The input is an array [Ra, Rb] and the output is an array [Ea, Eb].

Explanation

÷400⁵*÷S$  Input: array [Ra, Rb]
÷400       Divide each by 400, makes [Ra/400, Rb/400]
    ⁵*     Raise 10 to that power, makes [10^(Ra/400), 10^(Rb/400)]
        $  Monadic chain operating on previous result
      ÷      Divide each by
       S     The sum of the whole
           Makes [10^(Ra/400)/(10^(Ra/400) + 10^(Rb/400)),
                  10^(Rb/400)/(10^(Ra/400) + 10^(Rb/400))]
               = [1/(1 + 10^((Rb-Ra)/400)), 1/(1 + 10^((Ra-Rb)/400))]


Calculate the lowest number where the sum of the sequence of numbers exceeds a given value

Jelly, 18 12 11 10 bytes

1Æs>¥#ḢṄÆs

Try it online!

-1 byte thanks to Mr. Xcoder!

How it works

1Æs>¥#ḢṄÆs - Main link. Argument: n (integer)
1   ¥#     - Find the first n integers where...
 Æs        -   the divisor sum
   >       -   is greater than the input
       Ṅ   - Print...
      Ḣ    -   the first element
        Æs - then print the divisor sum


After much trial and error, with the goal of not resorting to Assembly while achieving the best single-threaded performance, this is my entry:
#include <unistd.h>

#define unlikely(e)      __builtin_expect((e), 0)
#define mcpy(d, s, n)    __builtin_memcpy((d), (s), (n))

#define CACHELINE 64
#define PGSIZE 4096
#define ALIGNED_BUF 65536
#define FIZZ "Fizz"
#define BUZZ "Buzz"
#define DELIM "\n"

typedef struct {
    unsigned char offset;
    char data[CACHELINE - sizeof(unsigned char)];
} counters_t;

static inline void os_write(int out, void *buf, unsigned int n)
{
    while (n)
    {
        ssize_t written = write(out, buf, n);

        if (written >= 0)
        {
            buf += written;
            n -= written;
        }
    }
}

int main(void)
{
    const int out = 1;

    __attribute__((aligned(CACHELINE))) static counters_t counter = {
        sizeof(counter.data) - 1, "00000000000000000000000000000000000000000000000000000000000000"
    };
    __attribute__((aligned(PGSIZE))) static char buf[ALIGNED_BUF + (sizeof(counter.data) * 15 * 3)] = { 0 };
    char *off = buf;

    for (;;)
    {
        // Write chunks of 30 counters until we reach `ALIGNED_BUF`
        while (off - buf < ALIGNED_BUF)
        {
            #define NN (sizeof(counter.data) - 2)

            // Hand-rolled counter copy, because with non-constant sizes the compiler
            // just calls memcpy, which is too much overhead.
            #define CTRCPY(i) do { \
                const char *src = end; \
                char *dst = off; \
                unsigned _n = n; \
                switch (_n & 3) { \
                case 3: *dst++ = *src++; \
                case 2: \
                    mcpy(dst, src, 2); \
                    dst += 2; src += 2; \
                    break; \
                case 1: *dst++ = *src++; \
                case 0: break; \
                } \
                for (_n &= ~3; _n; _n -= 4, dst += 4, src += 4) { \
                    mcpy(dst, src, 4); \
                } \
                mcpy(off + n, i DELIM, sizeof(i DELIM) - 1); \
                off += n + sizeof(i DELIM) - 1; \
            } while (0)

            // Write the first 10 counters of the group (need to separate the
            // first 10 counters from the rest of the chunk due to possible decimal
            // order increase at the end of this block)
            {
                const char *const end = counter.data + counter.offset;
                const unsigned int n = sizeof(counter.data) - counter.offset - 1;

                CTRCPY("1"); // 1
                CTRCPY("2"); // 2

                mcpy(off, FIZZ DELIM, sizeof(FIZZ DELIM) - 1); // Fizz (3)
                off += sizeof(FIZZ DELIM) - 1;

                CTRCPY("4"); // 4

                mcpy(off, BUZZ DELIM FIZZ DELIM, sizeof(BUZZ DELIM FIZZ DELIM) - 1); // Buzz (5) Fizz (6)
                off += sizeof(BUZZ DELIM FIZZ DELIM) - 1;

                CTRCPY("7"); // 7
                CTRCPY("8"); // 8

                mcpy(off, FIZZ DELIM BUZZ DELIM, sizeof(FIZZ DELIM BUZZ DELIM) - 1); // Fizz (9) Buzz (10)
                off += sizeof(FIZZ DELIM BUZZ DELIM) - 1;

                // Carry handling on MOD 10
                for (unsigned d = NN; ; --d)
                {
                    if (counter.data[d] != '9')
                    {
                        ++counter.data[d];
                        break;
                    }
                    counter.data[d] = '0';
                }

                // Decimal order increases only when `counter MOD 30 == 10`
                if (unlikely(counter.data[counter.offset - 1] != '0'))
                {
                    if (unlikely(counter.offset == 1))
                    {
                        goto end;
                    }

                    --counter.offset;
                }
            }

            // Write the chunk's remaining 20 counters
            {
                const char *const end = counter.data + counter.offset;
                const unsigned int n = sizeof(counter.data) - counter.offset - 1;

                CTRCPY("1"); // 11

                mcpy(off, FIZZ DELIM, sizeof(FIZZ DELIM) - 1); // Fizz (12)
                off += sizeof(FIZZ DELIM) - 1;

                CTRCPY("3"); // 13
                CTRCPY("4"); // 14

                mcpy(off, FIZZ BUZZ DELIM, sizeof(FIZZ BUZZ DELIM) - 1); // FizzBuzz (15)
                off += sizeof(FIZZ BUZZ DELIM) - 1;

                CTRCPY("6"); // 16
                CTRCPY("7"); // 17

                mcpy(off, FIZZ DELIM, sizeof(FIZZ DELIM) - 1); // Fizz (18)
                off += sizeof(FIZZ DELIM) - 1;

                CTRCPY("9"); // 19

                mcpy(off, BUZZ DELIM FIZZ DELIM, sizeof(BUZZ DELIM FIZZ DELIM) - 1); // Buzz (20) Fizz (21)
                off += sizeof(BUZZ DELIM FIZZ DELIM) - 1;

                // Carry handling on MOD 10
                for (unsigned d = NN; ; --d)
                {
                    if (counter.data[d] != '9')
                    {
                        ++counter.data[d];
                        break;
                    }
                    counter.data[d] = '0';
                }

                CTRCPY("2"); // 22
                CTRCPY("3"); // 23

                mcpy(off, FIZZ DELIM BUZZ DELIM, sizeof(FIZZ DELIM BUZZ DELIM) - 1); // Fizz (24) Buzz (25)
                off += sizeof(FIZZ DELIM BUZZ DELIM) - 1;

                CTRCPY("6"); // 26

                mcpy(off, FIZZ DELIM, sizeof(FIZZ DELIM) - 1); // Fizz (27)
                off += sizeof(FIZZ DELIM) - 1;

                CTRCPY("8"); // 28
                CTRCPY("9"); // 29

                mcpy(off, FIZZ BUZZ DELIM, sizeof(FIZZ BUZZ DELIM) - 1); // FizzBuzz (30)
                off += sizeof(FIZZ BUZZ DELIM) - 1;

                // Carry handling on MOD 10
                for (unsigned d = NN; ; --d)
                {
                    if (counter.data[d] != '9')
                    {
                        ++counter.data[d];
                        break;
                    }
                    counter.data[d] = '0';
                }
            }
        }

        os_write(out, buf, ALIGNED_BUF);
        mcpy(buf, buf + ALIGNED_BUF, (off - buf) % ALIGNED_BUF);
        off -= ALIGNED_BUF;
    }

end:
    os_write(out, buf, off - buf);

    return 0;
}

Compiled as clang -o fizz fizz.c -O3 -march=native (with clang 11.0.0 on my Ubuntu 20.10 installation, running kernel version 5.8.0-26.27-generic 5.8.14 on an Intel Core i7-8750H mobile CPU while plugged into the wall), this produces ~3.8GiB/s when run as ./fizz | pv > /dev/null (not very steady due to write blocking every once in a while, but there's nothing I can do about that when single-threaded, I guess).
EDIT: Optimised the carry handling a bit, and now I'm getting ~3.9GiB/s on my machine (same configuration as above).


Proportion of self-avoiding walks on a square lattice

Haskell, 153 149 144 140 126 118 92 bytes
Here we represent the 2d coordinates as a single integer: We start at 0, and the directions N,E,S,W correspond to adding +n,+1,-n,-1 where n is the input (we could also use any larger number). Using this we generate all possible paths, and then just check for duplicate numbers in those paths.
Thanks @H.PWiz for -26 bytes!

g n|a<-scanl(+)0<$>mapM(\_->[1,-1,n,-n])[1..n]=sum[1|x<-a,[b|b<-x,c<-x,b==c]==x]/sum[1|x<-a]

Try it online!
Explanation
--generate all possible paths
    a<-scanl(+)0<$>mapM(\_->[1,-1,n,-n])[1..n]
--count the non-self intersecting paths, compute the ratio to the total
g n|a<- ... =sum[1|x<-a,[b|b<-x,c<-x,b==c]==x]/sum[1|x<-a]


Print all lexicographically increasing numbers under 10000

Python 2, 56 bytes

for n in range(9999):
 if eval('<'.join(`n`))**n:print n

Try it online!

Converts each number like 124 to an expression 1<2<4 and evaluates it to check if the digits are sorted,

A hiccup happens for one-digit numbers giving an expression that just is the number itself. This causes 0 to evaluate to a Falsey value even though it should be printed. This is fixed by a trick suggested by Erik the Outgolfer of doing **n, which gives truthy value 0**0 for n=0 and doesn't affect the truth value otherwise.


Find all the Anagrams, and the Subanagrams too!

Brachylog (2), 7 bytes

{sp}ᶠdb

Try it online!

Explanation

{sp}ᶠdb
{  }ᶠ    Find all
  p        permutations of
 s         a substring of {the input}
     d   Remove duplicates (leaving the list otherwise in the same order)
      b  Remove the first (the input itself)


To count the sum of all Unicode characters of a given input under an interesting constraint

Haskell, 20 18 bytes
Sheer luck!

sum.fmap(fromEnum)

Try it online!


><> (Fish), 95

Starting after the '  puts all characters onto the stack and at the end of the line it wraps around; closes the string with the same '; outputs the top of the stack as a number (n) and finish execution (;).

Characters for 13 and 10 were changed to space to not ruin the layout of the code (as fish is a 2D language.)

Some non-printable ASCII disappears in the answer. Correct program here.

'n;Y8Y9C-""NX(QN.`JY6%c--WP\1H  \LX `W&WX"9I;!H_PT%GM[140+M4@   &AET`NGPNa

Thanks for Martin Büttner and Sp3000 for improvements of 2 and 5 bytes.

Hex dump:

0000000: 276e 3b59 3859 3943 072d 2222 4e58 0e28  'n;Y8Y9C.-""NX.(
0000010: 5117 1a4e 2e08 600b 1c03 4a06 1759 3625  Q..N..`...J..Y6%
0000020: 0663 2d01 2d57 500c 5c14 3148 095c 0f4c  .c-.-WP.\.1H.\.L
0000030: 5803 0520 6057 2657 1f58 2208 3949 3b21  X.. `W&W.X".9I;!
0000040: 485f 5054 0b04 0b0b 2547 4d5b 3115 3430  H_PT....%GM[1.40
0000050: 2b0b 4d34 4003 0915 2641 4554 604e 0747  +.M4@...&AET`N.G
0000060: 504e 0361                                PN.a


D is JavaScript.

Obviously not. But, when dealing  with float, double and real, nan is a value which must be handled, and, as specified by IEEE 754, NaN does not compare equal with itself.

writeln(double.nan == double.nan); // false

Meaning,

writeln(value!=value); // only true for nan

is way shorter than

import std.math;
writeln(isNaN(value));

Obviously, always use math.isNaN for real code. ;)


Python 3, 129 127 bytes
def f(p):
 x=2
 while 1:
  for i in range(x*x):
   if i//x*((p-2)*i//x+4-p)/2==i%x*(i%x+1)*((p-2)*i%x+5-p)/6==x:return x
  x+=1

A function that takes input via argument and returns the output.
This is an extremely naïve brute force, and takes a very long time for even moderately large p; the execution time will be ridiculous for anything approaching the given maximum for p of 2^16, but there is no reason why the program would not work, given sufficient time.
There are probably far shorter and faster ways of doing this, but I thought it would be good to post something to get this started off.
How it works
The return value x is initialised to 2, and then the program simply loops over all the p-gonal and p-gonal pyramidal numbers up to order x. If the current p-gonal and p-gonal pyramidal numbers, calculated using the formulas, are equal to each other and to x, then x must be the relevant cannonball number and this is returned. Else, x is incremented, and the program tries again for the new value of x.
In terms of golfing, a Cartesian product is used to collapse the two for-loops for the p-gonal and p-gonal pyramidal numbers into a single loop, and the formulas were factorised further to save a few bytes.


JavaScript (ES7),  59  31 bytes
Returns the \$n\$-th term, 0-indexed. This is a closed-form formula.

n=>n*1.5^Math.log2(n)&n%4==2^!n

Try it online!
Formula
The only edge case is \$a(0)=1\$. For \$n\ge1\$:
$$a(n)=\cases{\left\lfloor\dfrac{3n}{2}\right\rfloor-1,&\text{if $\lfloor log_2(n)\rfloor$ is odd and $n\equiv 2\pmod 4$} \\
\left\lfloor\dfrac{3n}{2}\right\rfloor,&\text{otherwise}
}
$$


Taking inspiration from the comments and from the question, just by adding 3 characters I "fixed" the memory leak.

Granted, I broke everything else at the same time

import threading, time

# this class takes callback and calls it every 1 sec
class MyTimer:
    def __init__(self, callback):
        self.callback = callback
        self.th = threading.Thread(target=self.run,daemon=True)
        self.th.start()
    def run(self):
        while(True):
            self.callback()
            time.sleep(1)

class TestMyTimer:
    def __init__(self):
        self.timer = MyTimer(self.is_alive)
    def is_alive(self):
        print("I'm still alive")

# test code for MyTimer
#t = TestMyTimer()
#del t

# just to be sure to collect all dead objects
import gc
#gc.collect()

# if you are still seeing messages then we have memory leak!
time.sleep(60)

Edit: The challenge has now been properly updated :)


Community wiki for built-in solutions

This answer is intended to collect answers that are simply built-ins. It's a community wiki, so anybody can edit in without approval. Go ahead and include any built-in only solution here, following xnor's proposal and according to our consensus.

Jelly, 1 byte

!

Try it online!

J , 1 byte

!

Try it online!

2sable, 1 byte

!

Try it online!

Pyth, 2 bytes

.!

Try it online!

R, 9 bytes

factorial

Try it online!

Stax, 2 bytes

|F

Try and debug online!

Wolfram Language (Mathematica), 3 bytes

#!&

Try it online!


jimmy23013

Let's work backwards for this one. We first turn the digits into their binary representations. We go from VW626206555675126212043640270477001760465526277571600601 to VW++__+_++__+____++_+_++_++_+++_++++_+__+_+_++__+___+_+____+___++++_+______+_+++___+__++++++________++++++____+__++_+_++_+_+_++__+_+++++++_++++__+++_______++______+. Next, we keep applying the inverse of DCW:W+ and DW:W_ until we clear all symbols. Our result is now VDCDCDDDCDDCDCDDDCDDDDDCDCDDCDDCDCDDCDCDDCDCDCDDCDCDCDCDDCDDDCDDCDDCDCDDDCDDDDCDDCDDDDDCDDDDCDCDCDCDDCDDDDDDDCDDCDCDCDDDDCDDDCDCDCDCDCDCDDDDDDDDDCDCDCDCDCDCDDDDDCDDDCDCDDCDDCDCDDCDDCDDCDCDDDCDDCDCDCDCDCDCDCDDCDCDCDCDDDCDCDCDDDDDDDDCDCDDDDDDDCW. We now want to make this string match VD+C+W; that is, we want to move all of the Ds to the left of all of the Cs. This can be done by reversing DCC:CD. We do this by repeating the following algorithm:

Find the first D that is to the right of a block of Cs.
Move the D to the left of that block.
Double the number of Cs.

Through some math, we can determine that we will end up with 123 Ds and 4638704741628490670592103344196019722536654143873 Cs (you were right about this not fitting in an SE answer... I doubt this would fit if stored as states of all of the atoms in the Earth combined :P).

If we keep applying the reverse of V:VD, we can get rid of all of the Ds now, so we get VCCC.......CCCW. We convert the V back into YZ. Now we have YZCCC.......CCCW.

We want to be able to get rid of all of the Cs and have it in the form YAAA...AAABBB...BBBZW. Fortunately, this can be done by the following method. Firstly, we inverse-apply YB:Y 587912508217580921743211 times to get YBBB.......BBBZCCC.......CCCW. Then, we repeat the following sequence of steps (where [?*] means any number of ?, not necessarily greater than zero):

Inverse-apply CZ:ZC 587912508217580921743211 times to get Y[A*]BBB.......BBBCCC.......CCCZCCC.......CCCW
Inverse-apply CB:BC many times to get Y[A*]BCBCBC.......BCBCBCZCCC.......CCCW
Inverse-apply AZ:Z and AB:BCA many times to get Y[A*]ABBB.......BBBZCCC.......CCCW

Through induction, we see that we can move the BZ combination all the way to the end (except before the W) and then the number of As is 1/587912508217580921743211 of the number of Cs, leaving us with 7890127658096618386747843 As. We now have YAAA.......AAABBB.......BBBZW. Convert the ZW back to a U, then inverse-apply U:BU many times to keep only 2 Bs and then convert the BBU to a T, and you now have YAAA.......AAAT. Then, you can inverse-apply T:AAAAAT many times to get YAAAT because the number of As was 3 larger than a multiple of 5.

Thanks for the challenge!


Praming Puzles & Colf: Condense a String

JavaScript (ES6), 74 bytes

f=
(s,n=0,m=s.match(`(.).{${n}}\\1`))=>s[n]?m?f(s.replace(...m)):f(s,n+1):s
;
<input oninput=o.textContent=f(this.value)><pre id=o>


SKI calculus golf: Half of a Church numeral

40 combinators

S(S(SI(K(S(S(KS)K)(K(S(S(KS)(S(KK)S))(K(S(KK)(S(S(KS)K)))))))))(K(S(SI(K(KI)))(K(KI)))))(KK)

Try it online!

Generated with a little help from a slightly modified version of my answer to Combinatory Conundrum:

$$\begin{align*}
\textit{zero} &= λf. λx. x = KI \\
\textit{succ} &= λn. λf. λx. f\,(n\,f\,x) = S(S(KS)K) \\
\textit{zero-pair} &= λf. f\,\textit{zero}\,\textit{zero} = S(SI(K\,\textit{zero}))(K\,\textit{zero}) \\
\textit{next-pair-helper} &= λf. λm. λn. f\,n\,(\textit{succ}\,m) \\ &= S(S(KS)(S(KK)S))(K(S(KK)\,\textit{succ})) \\
\textit{next-pair} &= λp. λf. p\,(\textit{next-pair-helper}\,f) \\ &= S(S(KS)K)(K\,\textit{next-pair-helper}) \\
\textit{half} &= λn. n\,\textit{next-pair}\,\textit{zero-pair}\,K \\ &= S(S(SI(K\,\textit{next-pair}))(K\,\textit{zero-pair}))(KK)
\end{align*}$$


Lua, 219 chars

Done it all in 1 step, no need for an intermediate table. Plots the function too ;)

function I(f,x,X,y,Y,r,R)I=io.write N=0 for k=R-1,0,-1 do for l=0,r-1 do v=f(x+l*(X-x)/r) K=y+k*(Y-y)/R c=(K<0 and K>v)and'-'or(K>0 and K<v and'+')or' 'N=c=="+"and N+1 or(c=="-"and N-1 or N)I(c)end I'\n'end return N end

Test code:

assert(I(math.sin,1.0,8.0,-1,1,30,15)==19)


Build a NAND gate using multiple NAND gates

Three gates.  Compute (((A nand A) nand B) nand B).  Unlike the four-gate solution above in which three of the four gates compute A nand B, two of them simultaneously, and substituting one of the simultaneous outputs for the other would yield two consecutive inverters, the three-gate solution uses the three gates to compute different functions: "not A", "A or not B", and "A nand B".  Only the last gate computes the desired function.


Javascript (Cheating), Score = limitless?

I realized that the game timer was using setInterval, which is a very unreliable way of keeping time.  With that in mind, since js is single threaded, if we simply hog the thread, the timer can't update.  As a result, you can essentially get any score you want.  If you perform 1000 clicks in a single function call without releasing the thread, you guarantee a score of at least 60000 (in fact I did this and got 180000).  This is obviously cheating because the game lasts longer than 60 seconds, though the game doesn't realize it.  For this reason, any js solution at all is really sort of cheating.  Though the time increase is minimal for code that completes quickly, you can still potentially delay the timer for as long as your code runs.

var factor = 1000;

function findAndClick() {
  var array = document.getElementById("box").children;

  for(var j = 0; j < factor; j++){
      var one = array[0].style.cssText;
      var two = array[1].style.cssText;

      var color;
      if(one != two){
        color = array[2].style.cssText;
      } else {
        color = one;
      }

      for (var i=0; i < array.length; i++) {
        if (array[i].style.cssText != color) {
          array[i].click();
          break;
        }
      }
    }
}
$(".play-btn").click();
setInterval(findAndClick, 0);

Javascript (REALLY Cheating), Score = limitless?

The game's object is actually global.  As a result, you can tweak various properties to your advantage.  The easiest of which is to just set your score to whatever you want it to be:

$(".play-btn").click();
Game.lv = 1000000;


Compute the inverse of an integer modulo 100000000003

Pyth, 24 bytes

L-b*/bJ+3^T11Jy*uy^GT11Q

Test suite

This uses the fact that a^(p-2) mod p = a^-1 mod p.

First, I manually reimplement modulus, for the specific case of mod 100000000003. I use the formula a mod b = a - (a/b)*b, where / is floored division. I generate the modulus with 10^11 + 3, using the code +3^T11, then save it in J, then use this and the above formula to calculate b mod 100000000003 with -b*/bJ+3^T11J. This function is defined as y with L.

Next, I start with the input, then take it to the tenth power and reduce mod 100000000003, and repeat this 11 times. y^GT is the code executed in each step, and uy^GT11Q runs it 11 times starting with the input.

Now I have Q^(10^11) mod 10^11 + 3, and I want Q^(10^11 + 1) mod 10^11 + 3, so I multiply by the input with *, reduce it mod 100000000003 with y one last time, and output.


Python 2, 69 bytes

lambda n:[''.join('02'[x>'0']for x in`n`)+'0',n][set(`n`)<=set('05')]

The function is simple to describe:

If n consists of only 0's and 5's, output it unchanged.
Otherwise, replace each digit of n with 2, except 0 stays 0, and tack on a 0 to the end.

The golfing can be improved, I'm mostly posting to share the method. A language with native regex should allow a short solution.
An alternative statement of the function is

In n, replace each digit with a 5, except 0 stays as 0
If this changed n (it had a digit other than 0 or 5), multiply the result by 4


CJam, 13 bytes
q~,f#\fb::+$p

I think this can be improved, but lets get this started.
The input is in the following order : b a n
Example input:
3 2 4

Output:
[1 2 2 4]

Code expansion:
q~             "Read the input and parse it. Now we have on stack, b a and n"
  ,            "Get an array from 0 to n-1";
   f#          "Get all the powers of a present in the array, i.e. 0 to n-1";
     \         "Swap the array of a^i and bring the base on top";
      fb       "For each number in the array, convert it into its base representation array";
        ::+    "Calculate the sum of each of the sub arrays in the bigger array";
           $p  "Sort and print the sum of digits of base representation of n powers of a";

Try it online here


R, 150 142 127 119 bytes

function(A,N=nrow(A),k=1:(N/2)*2)sum(apply(gtools::permutations(N,N),1,function(r)prod(A[cbind(r[k-1],r[k])])))/prod(k)

Try it online!

Uses the same trick I discovered golfing down this answer to index the matrix P, and @Vlo suggested an approach to entirely remove the for loop for -6 bytes!

To create a new test case, you can do matrix(c(values,separated,by,commas,going,across,rows),nrow=2n,ncol=2n,byrow=T).

Explanation: (the code is the same; it uses an apply rather than a for loop but the logic is otherwise identical).

function(A){
N <- nrow(A)                   #N = 2*n
k <- 1:(N/2) * 2               #k = c(2,4,...,N) -- aka 2*j in the formula
P <- gtools::permutations(N,N) #all N-length permutations of 1:N
for(i in 1:nrow(P))
 F <- F + prod(A[cbind(P[i,k-1],P[i,k])]) # takes the product of all A_sigma(2j-1)sigma(2j) for fixed i and adds it to F (initialized to 0)
F / prod(k)                    #return value; prod(k) == n! * 2^n
}


Mathematica, 36 11 nodes

Thread@#@#2&

The FullForm of this program is:

Function[Thread[Slot[1][Slot[2]]]]

which has 4 symbols, 2 numbers, and 5 function applications.


Python, 134 bytes
Thanks Pietu1998 for the bytes saved
from random import*
def g(a,b,c):
 s,z=[],[c,b]
 while z[0]*z[1]:d=randint(1,20);z[a<d]-=[1,z[a<d]][d in[1,20]];s+=[d]
 return[z[0]]+s

Pretty simple, can probably be golfed a bit more, but we needed something to kick this off. Try it online.


05AB1E, 13 bytes

I think it has been 389 days since I last posted something here haha. There is definitely some golfing potential left in this program.

Code

Uses the 05AB1E-encoding.

∞æ¹ùʒPy.¿Q}²£

Try it online!

Explanation

It is worth noting that for two numbers \$n, m \in \mathbb{Z}^+\$ that:

$$
\tag{1} \label{1}
\gcd(n, m) \cdot \text{lcm}(n, m) = n \cdot m
$$

This means that for two numbers \$n, m \in \mathbb{Z}^+\$ where the \$\gcd(n, m) = 1\$, we can conclude that the \$\text{lcm}(n, m) = n \cdot m\$.

Furthermore, the \$\gcd\$ function is a multiplicative function, which means that if \$n_1\$ and \$n_2\$ are relatively prime, then:

$$
\gcd(n_1 \cdot n_2, m) = \gcd(n_1, m) \cdot \gcd(n_2, m)
$$

From this, we obtain the fact that:

$$
\tag{2} \label{2}
\gcd(a, bc) = 1 \iff \gcd(a, b) = 1 \wedge \gcd(a, c) = 1
$$

Let us denote a \$k\$-tuple of positive integers as \$S = \{x_1, x_2, \dots, x_k\}\$. A set \$S\$ is pairwise coprime, if and only if:

$$
\tag{3} \label{3}
\forall a, b \in S \wedge a \not = b \rightarrow \gcd(a, b) = 1
$$

Using Equations \$\eqref{1}, \eqref{2}\$ and \$\eqref{3}\$, we can conclude that a set \$S = \{x_1, x_2, \dots, x_k\}\$ is pairwise coprime, if and only if:

$$
\text{lcm}(x_1, x_2, \dots, x_k) = \prod_{x \in S} x
$$

Code Explanation

∞æ¹ùʒPy.¿Q}²£

∞æ              # Powerset of the infinite list [1, ..., ∞].
  ¹ù            # Keep only lists of length k.
    ʒ     }     # Filter. Keep lists where the
     P          #   product of the list
         Q      #   is equal to
      y.¿       #   the least common multiple of the list
           ²£   # Retrieve the first n elements.


Python 2 + PIL, simple colour scaling

from PIL import Image
import math

INFILE = "street.jpg"
OUTFILE = "output.png"
AVERAGE = (150, 100, 100)

im = Image.open(INFILE)
im = im.convert("RGB")
width, height = prev_size = im.size
pixels = {(x, y): list(im.getpixel((x, y)))
          for x in range(width) for y in range(height)}

def get_avg():
    total_rgb = [0, 0, 0]

    for x in range(width):
        for y in range(height):
            for i in range(3):
                total_rgb[i] += int(pixels[x, y][i])

    return [float(x)/(width*height) for x in total_rgb]

curr_avg = get_avg()

while tuple(int(x) for x in curr_avg) != AVERAGE:
    print curr_avg
    non_capped = [0, 0, 0]
    total_rgb = [0, 0, 0]

    for x in range(width):
        for y in range(height):
            for i in range(3):
                if curr_avg[i] < AVERAGE[i] and pixels[x, y][i] < 255:
                    non_capped[i] += 1
                    total_rgb[i] += int(pixels[x, y][i])

                elif curr_avg[i] > AVERAGE[i] and pixels[x, y][i] > 0:
                    non_capped[i] += 1
                    total_rgb[i] += int(pixels[x, y][i])

    ratios = [1 if z == 0 else
              x/(y/float(z))
              for x,y,z in zip(AVERAGE, total_rgb, non_capped)]

    for x in range(width):
        for y in range(height):
            col = []

            for i in range(3):
                new_col = (pixels[x, y][i] + 0.01) * ratios[i]
                col.append(min(255, max(0, new_col)))

            pixels[x, y] = tuple(col)

    curr_avg = get_avg()

print curr_avg

for pixel in pixels:
    im.putpixel(pixel, tuple(int(x) for x in pixels[pixel]))

im.save(OUTFILE)

Here's a naïve approach which should serve as a good baseline. At each iteration, we compare our current average with the desired average, and scale the RGB of each pixel by the according ratio. We have to be a bit careful though, for two reasons:

Scaling 0 still results in 0, so before we scale we add something small (here 0.01)
RGB values are between 0 and 255, so we need to adjust the ratio accordingly to make up for the fact that scaling capped pixels doesn't do anything.

The images save as PNG because saving as JPG seems to mess up the colour averages.

Sample output

(40, 40, 40)

(150, 100, 100)

(75, 91, 110), Starry Night palette


RProgN, 3 bytes
1
2

Thanks to @MartinEnder for reminding me about this answer.
Try it online!
How it works
This exploits a potential flaw in our definition of proper quine:

It must be possible to identify a section of the program which encodes a different part of the program. ("Different" meaning that the two parts appear in different positions.)
Furthermore, a quine must not access its own source, directly or indirectly.

That's obviously the case here, as the output is the reverse of the code and the code is not a palindrome.
RProgN – reverse programmer notation – uses a LIFO stack and prints the items on it in the order they are popped. The two tokens 1 and 2, separated by spaces and/or newlines, get popped in reverse order and are printed separated by a newline.
This prints the reversed program
2
1

which, in turn, prints the original one.
!enilno ti yrT


Perl, 933 characters

$m=<<'';$_='         ';
sub h{/^(?:...)*(\d)\1\1/|/^.?.?(\d)..\1..\1/|/(\d)...\1...\1/|/^..(\d).\1.\1/&&$1}
sub r{substr($_,$p-1,1)=pop}sub p{my$w=pop;my@b=(0,h==$w||h&&-1);if(!$b[1]&&/ /){$b[1]=-9;
while(/ /g){local($_,$p)=($_,pos);r$w;$r=-(p($w^1))[1];@b=($p,$r)if$r>$b[1]}}@b}
if(($w=h||!/ /)||!@ARGV){$w--&&print+(nobody,X,O)[$w]," wins\n";s/(...)/$1\n/g;
tr/ 23/.XO/;print}else{$w=3;$w^=1for/\d/g;($p=pop)?r($w^1)&&!h&&(($p)=p$w)&&r$w:s/ /2/;
print"\$m=<<'';\$_='$_';\n$m\n$m"}

sub h{/^(?:...)*(\d)\1\1/|/^.?.?(\d)..\1..\1/|/(\d)...\1...\1/|/^..(\d).\1.\1/&&$1}
sub r{substr($_,$p-1,1)=pop}sub p{my$w=pop;my@b=(0,h==$w||h&&-1);if(!$b[1]&&/ /){$b[1]=-9;
while(/ /g){local($_,$p)=($_,pos);r$w;$r=-(p($w^1))[1];@b=($p,$r)if$r>$b[1]}}@b}
if(($w=h||!/ /)||!@ARGV){$w--&&print+(nobody,X,O)[$w]," wins\n";s/(...)/$1\n/g;
tr/ 23/.XO/;print}else{$w=3;$w^=1for/\d/g;($p=pop)?r($w^1)&&!h&&(($p)=p$w)&&r$w:s/ /2/;
print"\$m=<<'';\$_='$_';\n$m\n$m"}

Please note that the blank line in the middle of the script is actually required to be there. (The line breaks at the end of the long lines are not required, other than for legibility, and are not included in the character count.)

Usage: When the program is run without arguments, it displays the current game state. Since at the start the board is empty, the output will be:

...
...
...

Run the program with an argument between 1 and 9 to claim that square as your move. The program will make its own move and then output a replacement script with the new state. Thus, for example:

$ perl ./qttt 5 > ./qttt-2
$ perl ./qttt-2
O..
.X.
...

On the very first turn only, you may give a move of 0 to indicate that the computer should take the first move. Note that the first player will always be X.

When the game is over, the display output will include a note to that effect:

$ perl ./qttt-4 6 > ./qttt-5
$ perl ./qttt-5
O wins
OXX
OOX
X.O

The program works by doing a standard minimax search of the game tree. (Tic-tac-toe is a small enough game that a full game tree can be generated on every run.) The exception to this is when the computer moves first -- in this case the initial move to the upper left corner is hard-coded.

Note that this program works in the fashion of a proper quine -- at no point does the script access its own source file in order to produce its output.