Count unrooted, unlabeled binary trees of n nodes

JavaScript (ES6), 265 bytes
This code actually builds all possible trees and filters out isomorphic results. This is quite slow for \$n>9\$ but \$a(10)=18\$ was checked locally.

n=>(K=A=>A.map(a=>[...a].sort()).sort(),g=(A,k)=>k>n-3?g[K(A)]||(N--,P=(p,a)=>a.map((v,i)=>P([...p,v],a.filter(_=>i--)))+a?1:g[K(A.map(a=>a.map(v=>~p[v])))]=1)(i=[],A.map(_=>--i)):A.map((a,i)=>a.some((v,j)=>~v?0:a[g([...A,[i,v,v]],a[j]=-~k),j]=v)))([[N=-1,N,N]])|~N

Try it online!
How?
Tree representation
Only internal nodes are stored explicitly as triplets \$[n_0,n_1,n_2]\$ where each value is either the 0-indexed ID of another internal node, or \$-1\$ for a leaf.
The final list of triplets can be normalized with the helper function \$K\$ which first sorts each triplet and then the entire list:
K = A => A.map(a => [...a].sort()).sort()

Main algorithm
The main recursive function \$g\$ builds all possible trees with \$n-1\$ internal nodes1. We start with an arbitrary root node \$[-1,-1,-1]\$ and attach each new internal node to the first available slot in one of the previous nodes.
For the first iteration, there's only one possible option:
$$\big[[-1,-1,-1]\big] \rightarrow \big[[1,-1,-1],[0,-1,-1]\big]$$
The underlying object of \$g\$ is also used to store all normalized trees that were already found.
Whenever a new tree is generated, we use the helper function \$P\$ to generate all permutations of the vertex identifiers. This allows us to store in \$g\$ all normalized trees that are isomorphic to the one we've found.

1: For obscure golfing reasons, the code actually generates at least 2 internal nodes. This is inconsistent for \$n<3\$ but leads to only one possible tree anyway, which is the expected result.


JavaScript (ES6), 368 bytes

f=(s,r=[],i='',j=i+'  ',a=[])=>s<'['?([,,r[0]]=s.match(s<'0'?/("(?:\\.|[^"])*")(.*)/:/(\d+)(.*)/))[1]:s<'{'?(_=>{for(;s<']';s=r[0])a.push(f(s.slice(1),r,j));r[0]=s.slice(1)})()||/\n/.test(a)?`[
${j+a.join(`,
`+j)}
${i}]`:`[${a.join`, `}]`:(_=>{for(a=[];s<'}';s=r[0])a.push(f(s.slice(1),r,j)+': '+f(r[0].slice(1),r,j));r[0]=s.slice(1)})()||`{
${j+a.join(`,
`+j)}
${i}}`

Less golfed:

function j(s, r=[], i='') { // default to no indentation
    if (s < '0') { // string
        let a = s.match(/("(?:\\.|[^"])*")(.*)/);
        r[0] = a[2]; // pass the part after the string back to the caller
        return a[1];
    } else if (s < '[') { // number
        let a = s.match(/(\d+)(.*)/);
        r[0] = a[2]; // pass the part after the string back to the caller
        return a[1];
    } else if (s < '{') { // array
        let a = [];
        while (s < ']') { // until we see the end of the array
            s = s.slice(1);
            a.push(j(s, r, i + '  ')); // recurse with increased indentation
            s = r[0]; // retrieve the rest of the string
        }
        r[0] = s.slice(1); // pass the part after the string back to the caller
        if (/\n/.test(a.join())) { // array contained object
            return '[\n  ' + i + a.join(',\n  ' + i) + '\n' + i + ']';
        } else {
            return '[' + a.join(', ') + ']';
        }
    } else { // object
        let a = [];
        while (s < '}') { // until we see the end of the object
            s = s.slice(1);
            let n = j(s, r, i + '  ');
            s = r[0].slice(1);
            let v = j(s, r, i + '  ');
            a.push(n + ': ' + v);
            s = r[0]; // retrieve the rest of the string
        }
        r[0] = s.slice(1); // pass the part after the string back to the caller
        return '{\n  ' + i + a.join(',\n  ' + i) + '\n' + i + '}';
    }
}


Python, 602 559 614 chars

import sys
S=sys.stdin.readlines()
X=max(len(s)for s in S)
I='#'*X+''.join(t[:-1]+' '*(X-len(t))+'\n'for t in S)+'#'*X
L=len(I)
R=range(L)
B=[0]*L
C=[0]*L
for p in R:
 if'@'!=I[p]:continue
 for d in(1,-1,X,-X):
  q=p;c=7;b=100.
  while 1:
   q+=d;a=I[q];B[q]+=b;C[q]|=c
   if a in'\/':d=(ord(a)/30-2)*X/d;b*=.8
   elif a in'RGB':c&=ord(a)/5-12
   elif a in'><^V':d={'>':1,'<':-1,'^':-X,'V':X}[a];b/=2
   elif' '!=a:break
print''.join(I[p]if' '!=I[p]else' bgcrmyw'[C[p]]for p in R[X:-X])
i=0
for p in R:
 if'?'==I[p]:i+=1;print'#%d:'%i,'%.0f%%'%B[p],[0,'Blue','Green','Cyan','Red','Magenta','Yellow','White'][C[p]]

Edit: fixed so it doesn't need trailing spaces.


PHP, period 2,100,000,000

Who would've thought that this is possible in PHP?! :-)

This is actually my first ever quine and it's 99 bytes long:

<?$i=1;$i*=21e8>$i;printf($a='<?$i=%d;$i*=21e8>$i;printf($a=%c%s%c,++$i,39,$a,39);',++$i,39,$a,39);

Although PHP supports bigger numbers than 2 * 10^8 by switching from integer to double, the increment no longer works (leads to an infinite loop) and I haven't found another solution which fits into the 100 bytes. Yet.

Proof is fairly simple, since it's just counting up on each iteration until it reaches the reset point at 2.1 billion.

Credits to dave, who posted the approach in pseudo code in the comments and to Bob Twells, from whom I copied the code for a minimal PHP quine.

Test program (sloooooow):

<?php
$o = file_get_contents('quine.php');
for ($i = 0; $i < 22e8; $i++) {
    if ($i%2==0) exec('php q > p'); else exec('php p > q');
    $a = file_get_contents(($i%2==0) ? 'p' : 'q');
    echo "\r" . str_pad($i,6,' ') . ":\t$a";
    if ($a == $o) {
        die;
    }
}

Well, at least I'm the first one to answer.


JavaScript (ES6), 72 bytes
Alternate formula suggested by @ceilingcat
Takes input as 5 distinct parameters (x0, y0, x1, y1, r).
with(Math)f=(x,y,X,Y,r)=>-(sin(d=2*acos(hypot(x-X,y-Y)/r/2))-d)*r*r*2>>1

Try it online!

JavaScript (ES7), 81 80 77 bytes
Saved 3 bytes thanks to @Neil
Takes input as 5 distinct parameters (x0, y0, x1, y1, r).
(x,y,X,Y,r,d=Math.hypot(x-X,y-Y))=>(r*=2)*r*Math.acos(d/r)-d*(r*r-d*d)**.5>>1

Try it online!
How?
This is based on a generic formula from MathWorld for non-congruent circles:
A = r².arccos((d² + r² - R²) / 2dr) +
    R².arccos((d² + R² - r²) / 2dR) -
    sqrt((-d + r + R)(d + r - R)(d -r + R)(d + r + R)) / 2

where d is the distance between the two centers and r and R are the radii.
With R = r, this is simplified to:
A = 2r².arccos(d / 2r) + d.sqrt((2r - d) * (2r + d)) / 2

And with r' = 2r:
A = (r'².arccos(d / r') + d.sqrt(r'² - d²)) / 2

Note: If d is greater than 2r, Math.acos() will return NaN, which is coerced to 0 when the right-shift is applied. This is the expected result, because d > 2r means that there's no intersection at all.


For this challenge, I am posting five programs in this answer, all in Java.
Program 1

You can't simply print/echo 'trololologram' (case insensitive)

public class JustPrintIt {
    public static void main(String[] args) {
        System.out.println("trololologram");
    }
}

Program 2

You can't [...] pre-rendered ([...] and any form of ascii art).

public class AsciiArt {
    public static void main(String[] args) {
        System.out.println(
            "    ########################       \n" +
            "  ##                        #      \n" +
            "  #                          #     \n" +
            " #                            ##   \n" +
            " #                              #  \n" +
            " #                              #  \n" +
            "  #                            #   \n" +
            "  #                          ##    \n" +
            "  #                     #####      \n" +
            "  #            #########           \n" +
            "   ############                    \n");
    }
}

Program 3

You can't use any network resource or external file (except the source-code)
You can't have it stored in any image format or pre-rendered (including base64 data:// uri's [...]).
You can't store the image in any database.
The code must render the trolologram on the screen [...].
The image must show in the screen. It can't output the code to a file [...].

import java.awt.image.BufferedImage;
import java.io.ByteArrayOutputStream;
import java.io.File;
import java.io.IOException;
import java.net.URL;
import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.PreparedStatement;
import java.sql.SQLException;
import java.util.Base64;
import javax.imageio.ImageIO;

public class DownloadAndStore {
    public static void main(String[] args) throws IOException, ClassNotFoundException, SQLException {
        String url = "http://img171.imageshack.us/img171/8555/trolologramw400.jpg";
        BufferedImage im = ImageIO.read(new URL(url));
        ImageIO.write(im, "png", new File("trolologram.png"));
        ByteArrayOutputStream baos = new ByteArrayOutputStream();
        ImageIO.write(im, "png", baos);

        String d = "data://" + new String(Base64.getEncoder().encode(baos.toByteArray()));
        Class.forName("com.mysql.jdbc.Driver");
        try (Connection con = DriverManager.getConnection("jdbc:mysql://localhost:3306", "root", "root")) {
            try (PreparedStatement ps = con.prepareStatement("CREATE DATABASE troll")) {
                ps.executeUpdate();
            } catch (SQLException e) {
                if (!e.getMessage().contains("database exists")) throw e;
            }
            try (PreparedStatement ps = con.prepareStatement("CREATE TABLE troll.image (imagedata text not null)")) {
                ps.executeUpdate();
            } catch (SQLException e) {
                if (!e.getMessage().contains("already exists")) throw e;
            }
            try (PreparedStatement ps = con.prepareStatement("INSERT INTO troll.image (imagedata) VALUES (?)")) {
                ps.setString(1, d);
                ps.executeUpdate();
            }
        }
    }
}

Program 4

Your challenge here is to draw a trololologram.
You can't use any network resource or external file (except the source-code)
You can't post someone else's answer
You can't have it stored in any image format or pre-rendered [...].
[...] (minimum size of 90x90) and must be with a black border and white background. [...].

import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.image.BufferedImage;
import java.io.IOException;
import java.net.URL;
import javax.imageio.ImageIO;
import javax.swing.JComponent;
import javax.swing.JFrame;
import javax.swing.SwingUtilities;

public class ShowTheAnswerOfSomebodyElse {
    public static void main(String[] args) throws IOException {

        // See this: http://codegolf.stackexchange.com/a/20085/3755
        String url = "http://placehold.it/99/png&text=Hello+world!";

        BufferedImage im = ImageIO.read(new URL(url));
        BufferedImage im2 = new BufferedImage(89, 89, BufferedImage.TYPE_INT_ARGB);
        im2.createGraphics().drawImage(im, 0, 0, null);
        SwingUtilities.invokeLater(() -> createAndShowGUI(im2));
    }

    private static void createAndShowGUI(BufferedImage im) {
        JFrame frame = new JFrame("");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        JComponent panel = new JComponent() {
            @Override
            public Dimension getPreferredSize() {
                return new Dimension(im.getWidth(), im.getHeight());
            }

            @Override
            public Dimension getMinimumSize() {
                return new Dimension(im.getWidth(), im.getHeight());
            }

            @Override
            public Dimension getMaximumSize() {
                return new Dimension(im.getWidth(), im.getHeight());
            }

            @Override
            public void paintComponent(Graphics g) {
                g.drawImage(im, 0, 0, null);
            }
        };
        frame.add(panel);

        frame.pack();
        frame.setVisible(true);
    }
}

Program 5

You can't use any network resource or external file (except the source-code)
You can't have it stored in any image format or pre-rendered [...].
The code must render the trolologram on the screen [...] and must be with a black border and white background. The rendered version can't "be invisible" or [...].
The image must show in the screen. [...].

import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.image.BufferedImage;
import java.io.IOException;
import java.net.URL;
import javax.imageio.ImageIO;
import javax.swing.JComponent;
import javax.swing.JFrame;
import javax.swing.SwingUtilities;

public class ShowTheTrolologramOnScreenButNot {
    public static void main(String[] args) throws IOException {
        String url = "http://img171.imageshack.us/img171/8555/trolologramw400.jpg";
        BufferedImage im = ImageIO.read(new URL(url));
        for (int i = 0; i < im.getHeight(); i++) {
            for (int j = 0; j < im.getWidth(); j++) {
                int rgb = im.getRGB(j, i);
                int r = 255 - (rgb >> 16 & 0xff);
                int g = 255 - (rgb >> 8 & 0xff);
                int b = 255 - rgb & 0xff;
                im.setRGB(j, i, 0xFF000000 + (r << 16) + (g << 8) + b);
            }
        }
        SwingUtilities.invokeLater(() -> createAndShowGUI(im));
    }

    private static void createAndShowGUI(BufferedImage im) {
        JFrame frame = new JFrame("");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        JComponent panel = new JComponent() {
            @Override
            public Dimension getPreferredSize() {
                return new Dimension(im.getWidth(), im.getHeight());
            }

            @Override
            public Dimension getMinimumSize() {
                return new Dimension(im.getWidth(), im.getHeight());
            }

            @Override
            public Dimension getMaximumSize() {
                return new Dimension(im.getWidth(), im.getHeight());
            }

            @Override
            public void paintComponent(Graphics g) {
                g.drawImage(im, 0, 0, null);
            }
        };
        frame.add(panel);
        panel.setVisible(false); // :)

        frame.pack();
        frame.setVisible(true);
    }
}

And finally...

Explain your answers and what holes you exploited.

So here it is:

The answer with more upvotes and the one that exploits more holes wins.

There is hole in this: you did not said that it must be a valid answer to be accepted!


Python 2.x - 679 543 443 417 406 383 372 361 bytes

I'm actually pretty sad about this one. I am sure I missed something obvious. I'll be looking at this again later. Starting to feel good about this one.

543 - Edit 1: Discarding efficiency in favor of code length.
443 - Edit 2: Made the algorithm a lot simpler, fixed it (it couldn't handle flips) and
              removed ungolfed code because it wasn't relevant anymore.
417 - Edit 3: Rotate was only being used once anymore. Inlined it. Something else too.
406 - Edit 4: Made it accept only four shapes, as the spec says. Also reduced efficiency again.
383 - Edit 5: Ultimate abuse of exec. Shorter code and longer execution time!
372 - Edit 6: Every recursion now makes a copy of the current board, which is removed if
              the pieces don't fit. No more master board and no more emptying placed pieces.
361 - Edit 7: Removed unnecessary stuff. Also added the byte counts to changelog.

(q,g),O,s=input()
O=[x*6for x in sum(O,[])]
A='z,k=s[i];'+('z,k=z[::-1],zip(*k[::-1]);r=r or c(i+1,z,k,O);'*4+'k=map(reversed,k);')*2
def c(i,(w,h),p,o,r=0):
 for x in range(g*q):O=o[:];f=1;I=0;exec"P=x+I/w*q+I%w;exec('f=0','O[P]=i')[g*q>P>=0and O[P]>4]*p[I/w][I%w];I+=1;"*w*h;exec(i<4*f)*A;r=O*(i*f>3)or r
 return r
i=r=0;exec A+'print`r[i:i+q]`[1::3];i+=q;'*g

It takes the input in an array format. Example:

In:  [5,5],[[1,1,0,0,0],[1,1,0,0,0],[1,1,1,0,1],[1,1,1,1,1],[0,0,1,1,1]],[[[2,4],[[1,0],[1,0],[1,1],[1,0]]],[[1,2],[[1],[1]]],[[2,3],[[0,1],[1,1],[0,1]]],[[2,3],[[0,1],[1,1],[1,1]]]]
Out: 12000
     12000
     11304
     13344
     00344

In:  [6,5],[[0,1,1,1,1,0],[1,1,1,1,1,0],[1,1,1,1,1,0],[0,1,1,1,1,0],[0,0,1,1,1,1]],[[[2,4],[[1,0],[1,0],[1,1],[1,1]]],[[3,3],[[1,1,0],[0,1,1],[0,1,1]]],[[3,3],[[0,0,1],[1,1,1],[1,0,0]]],[[2,4],[[0,1],[1,1],[0,1],[0,1]]]]
Out: 033110
     223110
     223310
     022410
     004444 (thanks, edc65)

Quick explanation, if you can't read it. The function checks every possible position for a piece. Whenever the piece fits, it recursively checks that all other pieces fit too. When all pieces fit, the board is filled (pieces are placed on the board when checking) and it can be outputted straight away.


Ruby, 344 characters
q=->n{r=0...n;n%2>0?(m=r.map{[]*n};x=n/2;y=i=0;r.map{r.map{m[y%=n][x%=n]=i+=1;x+=1;y-=1};x-=1;y+=2};m):n<5?[[16,3,2,13],[5,10,11,8],[9,6,7,12],[4,15,14,1]]:(d=q[n/2];r.map{|y|r.map{|x|4*d[b=y/2][a=x/2]-[0,3,2,1,3,0,2,1,3,0,1,2][(n/2%2<1?b<n/4?0:8:a==n/4&&b==n/4?4:a==n/4&&b==n/4+1?0:b<=n/4?0:b==n/4+1?4:8)+y%2*2+x%2]}})}
Q=->n{q[n].map{|s|p s}}

You can use it e.g. like
Q[3]

and the output will be
[8, 1, 6]
[3, 5, 7]
[4, 9, 2]

The solution is not yet fully golfed. Also huge squares are generated reasonably fast. It uses a recursive function q to generate the squares unless n is odd in which case the square is generated directly or n==4 which is hard-coded.


Generate ordered combinations with repetition

Python 2, 56 bytes
n is the maximum length and s is expected to be a list of characters. It is not clear to me whether n = 0 or an empty character list are valid inputs, but this function also handles them correctly.

f=lambda s,n:n*s and s+[x+c for x in f(s,n-1)for c in s]


Haskell, 184 182 201 199 155
s&t|(a,'|':b)<-f t,(x,'|':y)<-f$r s,x#b,a#y=r(y!r a)++b!r x|0<1=""
r=reverse
a!b=a++drop(length a-1)b
(#)a=and.zipWith(==)(r a).filter h
f=span h
h=(/='|')

example run:
"|a|"&"|b|" -- returns "|ab|"
"|a|x"&"|b|" -- returns ""

if there isn't a match an empty string will be returned. otherwise the result would be returned.
partial explanation:
# is a function which gets two strings, and returns whether or not they match.
! gets two strings and returns the first one concatenated with extra character from the second (if there are any).
the main function & uses span (/='|') to split the inputs into two parts, a|b|c to a, b|c, checks if the contexts match, and then uses ! twice to assemble the output.
Edit: mage-late regolfing seems to be pretty effective.


Vim, 27, 26, 25 bytes
DJqqYp:s/.\zs[^<C-r>-]<CR>@qq@qD

Try it online!
Input comes in this format:
e
codegolf.stackexchange.com

My naive first approach is three bytes longer:
i:s/.\zs[^<Right>]<Esc>"addqqYp@a@qq@qdd

I'm also happy with this answer because it starts with my name.
DJqq:t$|s/.\zs[^<C-r>"]<CR>@qq@qD
DJMcMayhem

See the similarity? Eh?
Less successful approaches:
i:s/.\zs[^<Right>]<Esc>"addqqYp@a@qq@qdd
i:s/.\zs[^<Right>]<CR>@q<Esc>"adkqqYp@aq@qdd
DJ:s/.\zs[^<C-r>"]<CR>uqqYp@:@qq@qdd
DJqq:t.|$s/.\zs[^<C-r>"]<CR>@qq@qdd

Explanation:
D                                   " Delete everything on this first line
 J                                  " Remove this empty line
  qq                                " Start recording into register 'q'
    Y                               " Yank this line
     p                              " And paste it
      :s/                           " Run a substitute command on the last line in the buffer. Remove:
         .                          "   Any character
          \zs                       "   Move the selection forward (so we don't delete the first one)
             [^<C-r>-]              "   Followed by anything *except* for the character we deleted
                      <CR>          " Run the command
                          @q        " Call register 'q'
                            q       " Stop recording
                             @q     " Run the recursive macro
                               D    " Delete our extra line


How many ways to write numbers as sums of squares?

Python 3, 125 bytes

n,d=eval(input())
W=[1]+[0]*n
exec("W=[sum(-~(j>0)*W[i-j*j]for j in range(int(i**.5)+1))for i in range(n+1)];"*d)
print(W[n])

Try it online!

Finishes the last testcase in 0.078 s. Naive complexity is O(d n 2).


PowerShell, 3 bytes, score 3637

2e4

Try it online!

Very naive, boring, implementation; just returns 20000 no matter the input. Experimentation with things like special-casing the sun or using floating-point values instead of 2 all resulted in worse scores because the length of code increased enough to offset any size-comparison gains.


Mathematica 40
Note: Not to be taken as a serious answer.  ;)
Just for fun:
ExampleData@{"Text","GettysburgAddress"}

Four score and seven years ago, our fathers brought forth upon this
continent a new nation: conceived in liberty, and dedicated to the
proposition that all men are created equal. Now we are engaged in a
great civil war...testing whether that nation, or any nation so
conceived and so dedicated. . . can long endure. We are met on a
great battlefield of that war. We have come to dedicate a portion of
that field as a final resting place for those who here gave their
lives that this nation might live. It is altogether fitting and
proper that we should do this. But, in a larger sense, we cannot
dedicate...we cannot consecrate... we cannot hallow this ground. The
brave men, living and dead, who struggled here have consecrated it,
far above our poor power to add or detract. The world will little
note, nor long remember, what we say here, but it can never forget
what they did here. It is for us the living, rather, to be dedicated
here to the unfinished work which they who fought here have thus far
so nobly advanced. It is rather for us to be here dedicated to the
great task remaining before us...that from these honored dead we take
increased devotion to that cause for which they gave the last full
measure of devotion... that we here highly resolve that these dead
shall not have died in vain...that this nation, under God, shall have
a new birth of freedom...and that government of the people, by the
people, for the people, shall not perish from this earth.


Check over hand values for single-suited Mahjong


C#, n=128 in about 2:40

using System;
using System.Collections.Generic;
using System.Linq;

namespace Sandbox
{
    class PPCG137436
    {
        public static void Main(string[] args)
        {
            if (args.Length == 0) args = new string[] { "1", "2", "4", "8", "16", "32", "64", "128" };

            foreach (string arg in args)
            {
                Console.WriteLine(Count(new int[(int)(0.5 + Math.Log(int.Parse(arg)) / Math.Log(2))], 0));
            }
        }

        static int Count(int[] periods, int idx)
        {
            if (idx == periods.Length)
            {
                //Console.WriteLine(string.Join(", ", periods));
                return 1;
            }

            int count = 0;
            int p = idx == 0 ? 1 : periods[idx - 1];
            for (int q = p; q <= 1 << (idx + 1); q++)
            {
                periods[idx] = q;
                if (q == p || q > 1 << idx || p + q - Gcd(p, q) > 1 << idx && UnificationPasses(periods, idx, q)) count += Count(periods, idx + 1);
            }

            return count;
        }

        private static int Gcd(int a, int b)
        {
            while (a > 0) { int tmp = a; a = b % a; b = tmp; }
            return b;
        }

        private static bool UnificationPasses(int[] periods, int idx, int q)
        {
            UnionSet union = new UnionSet(1 << idx);
            for (int i = 0; i <= idx; i++)
            {
                for (int j = 0; j + periods[i] < Math.Min(2 << i, 1 << idx); j++) union.Unify(j, j + periods[i]);
            }

            IDictionary<int, long> rev = new Dictionary<int, long>();
            for (int k = 0; k < 1 << idx; k++) rev[union.Find(k)] = 0L;
            for (int k = 0; k < 1 << idx; k++) rev[union.Find(k)] |= 1L << k;

            long zeroes = rev[union.Find(0)]; // wlog the value at position 0 is 0

            ISet<int> onesIndex = new HashSet<int>();

            // This can be seen as the special case of the next loop where j == -1.
            for (int i = 0; i < idx; i++)
            {
                if (periods[i] == 2 << i) onesIndex.Add((2 << i) - 1);
            }
            for (int j = 0; j < idx - 1 && periods[j] == 2 << j; j++)
            {
                for (int i = j + 1; i < idx; i++)
                {
                    if (periods[i] == 2 << i)
                    {
                        for (int k = (1 << j) + 1; k <= 2 << j; k++) onesIndex.Add((2 << i) - k);
                    }
                }
            }

            for (int i = 1; i < idx; i++)
            {
                if (periods[i] == 1) continue;

                int d = (2 << i) - periods[i];
                long dmask = (1L << d) - 1;
                if (((zeroes >> 1) & (zeroes >> periods[i]) & dmask) == dmask) onesIndex.Add(periods[i] - 1);
            }

            long ones = 0L;
            foreach (var key in onesIndex) ones |= rev[union.Find(key)];

            if ((zeroes & ones) != 0) return false; // Definite contradiction!

            rev.Remove(union.Find(0));
            foreach (var key in onesIndex) rev.Remove(key);

            long[] masks = System.Linq.Enumerable.ToArray(rev.Values);

            int numFilteredMasks = 0;
            long set = 0;
            long M = 0;
            for (int i = 1; i <= idx; i++)
            {
                if (periods[i - 1] == 1) continue;

                // Sort the relevant masks to the start
                if (i == idx) numFilteredMasks = masks.Length; // Minor optimisation: skip the filter because we know we need all the masks
                long filter = (1L << (1 << i)) - 1;
                for (int j = numFilteredMasks; j < masks.Length; j++)
                {
                    if ((masks[j] & filter) != 0)
                    {
                        var tmp = masks[j];
                        masks[j] = masks[numFilteredMasks];
                        masks[numFilteredMasks++] = tmp;
                    }
                }

                // Search for a successful assignment, using the information from the previous search to skip a few initial values in this one.
                set |= (1L << numFilteredMasks) - 1 - M;
                M = (1L << numFilteredMasks) - 1;
                while (true)
                {
                    if (TestAssignment(periods, i, ones, masks, set)) break;
                    if (set == 0) return false; // No suitable assignment found

                    // Gosper's hack with variant to reduce the number of bits on overflow
                    long c = set & -set;
                    long r = set + c;
                    set = (((r ^ set) >> 2) / c) | (r & M);
                }
            }

            return true;
        }

        private static bool TestAssignment(int[] periods, int idx, long ones, long[] masks, long assignment)
        {
            for (int j = 0; j < masks.Length; j++, assignment >>= 1) ones |= masks[j] & -(assignment & 1);
            for (int i = idx - 1; i > 0; i--) // i == 0 is already handled in the unification process.
            {
                if (Period(ones, 2 << i, periods[i - 1]) < periods[i]) return false;
            }

            return true;
        }

        private static int Period(long arr, int n, int min)
        {
            for (int p = min; p <= n; p++)
            {
                // If the bottom n bits have period p then the bottom (n-p) bits equal the bottom (n-p) bits of the integer shifted right p
                long mask = (1L << (n - p)) - 1L;
                if ((arr & mask) == ((arr >> p) & mask)) return p;
            }

            throw new Exception("Unreachable");
        }

        class UnionSet
        {
            private int[] _Lookup;

            public UnionSet(int size)
            {
                _Lookup = new int[size];
                for (int k = 0; k < size; k++) _Lookup[k] = k;
            }

            public int Find(int key)
            {
                var l = _Lookup[key];
                if (l != key) _Lookup[key] = l = Find(l);
                return l;
            }

            public void Unify(int key1, int key2)
            {
                int root1 = Find(key1);
                int root2 = Find(key2);

                if (root1 < root2) _Lookup[root2] = root1;
                else _Lookup[root1] = root2;
            }
        }
    }
}

Extending to n=256 would require switching to BigInteger for the masks, which probably kills the performance too much for n=128 to pass without new ideas, let alone n=256.

Under Linux, compile with mono-csc and execute with mono.

Basic explanation

I'm not going to do a line-by-line dissection, just an overview of the concepts.

As a rule of thumb, I'm happy to iterate through on the order of 250 elements in a brute-force combinatoric program. To get to n=128 it is therefore necessary to use an approach which doesn't analyse every bitstring. So rather than working forwards from bit strings to period sequences, I work backwards: given a period sequence, is there a bitstring which realises it? For n=2x there's an easy upper bound of 2x(x+1)/2 period sequences (vs 22x bitstrings).

Some of the arguments use the string periodicity lemma:

  Let p and q be two periods of a string of length n. If p + q ≤ n + gcd(p, q) then gcd(p, q) is also a period of the string.

Wlog I will assume that all of the bitstrings under consideration start with 0.

Given a period sequence [p1 p2 ... pk] where pi is the period of the prefix of length 2i (p0 = 1 always), there are some easy observations about possible values of pk+1:

pk+1 ≥ pk since a period of a string S is also a period of any prefix of S.
pk+1 = pk is always a possible extension: just repeat the same primitive string for twice as many characters.
2k < pk+1 ≤ 2k+1 is always a possible extension. It suffices to show this for pk+1 = 2k+1 because an aperiodic string of length L can be extended to an aperiodic string of length L+1 by appending any letter which isn't its first letter.

Take a string Sx of length 2k whose period is pk and consider the string SxyS of length 2k+1. Clearly SxyS has a period 2k+1. Suppose its period q is smaller.

Then 2k+1 + q ≤ 2k+1+1 ≤ 2k+1 + gcd(2k+1, q) so by the periodicity lemma gcd(2k+1, q) is also a period of SxyS, and since the greatest divisor is less than or equal to its arguments and q is the smallest period, we require q to be a proper factor of 2k+1. Since its quotient cannot be 2, we have q ≤ (2k+1)/3.

Now, since q ≤ 2k is a period of SxyS it must be a period of Sx. But the period of Sx is pk. We have two cases:

gcd(pk, q) = pk, or equivalently pk divides exactly into q.
pk + q > 2k + gcd(pk, q) so that the periodicity lemma doesn't force a smaller period.

Consider first the second case. pk > 2k + gcd(pk, q) - q ≥ 2k+1 - q ≥ 2k+1 - (2k+1)/3 ≥ 2q, contradicting the definition of pk as the period of Sx. Therefore we are forced into the conclusion that pk is a factor of q.

But since q is a period of Sx and pk is the period of Sx, the prefix of length q is just q/pk copies of the prefix of length pk, so we see that pk is also a period of SxyS.

Therefore the period of SxyS is either pk or 2k+1. But we have two options for y! At most one choice of y will give period pk, so at least one will give period 2k+1. QED.
The periodicity lemma allows us to reject some of the remaining possible extensions.
Any extension which hasn't passed a quick-accept or a quick-reject test needs to be tested constructively.

The construction of a bitstring given a period sequence is essentially a satisifiability problem, but it has a lot of structure. There are 2k - pk simple equality constraints implied by each prefix period, so I use a union set data structure to combine bits into independent clusters. This was enough to tackle n=64, but for n=128 it was necessary to go further. I employ two useful lines of argument:

If the prefix of length M is 01M-1 and the prefix of length L > M has period L then the prefix of length L must end in 1M. This is most powerful precisely in the cases which would otherwise have most independent clusters, which is convenient.
If the prefix of length M is 0M and the prefix of length L > M has period L - d with d < M and ends in 0d then it must in fact end in 10d. This is most powerful at the opposite extreme, when the period sequence starts with a lot of ones.

If we don't get an immediate contradiction by forcing the cluster with the first bit (assumed to be zero) to be one then we brute force (with some micro-optimisations) over the possible values for the unforced clusters. Note that the order is in descending number of ones because if the ith bit is a one then the period cannot be i and we want to avoid periods which are shorter than the ones which are already enforced by the clustering. Going down increases the chances of finding a valid assignment early.


Federal income tax calculator for procrastinators

Python 3, 427 382 317 309 308 275 bytes

-45 bytes by figuring ternary expression out (wow that's a long line); thanks Maltysen

-65 bytes, now with iteration for DRYer code!

-8 bytes by in-lining tuple variables; thanks Majora

-1 byte by using a dict rather than ternary chain; thanks again Maltysen

-33 bytes by reusing MFS step as half of MFJ/QW and calculating tax an order of magnitude larger; thanks Neil

def f(i,s):
 t=i;k={'MFS':(9225,28225,38150,39625,90525,26675),'S':(9225,28225,53300,98550,222200,1700),'HH':(13150,37050,79400,80250,201650,27500)}
 for x in range(6):
  i-=k[s][x]if s in k else k['MFS'][x]*2
  if i>0:t+=(.5,1,.3,.5,.2,.46)[x]*i
 return'{:.2f}'.format(t*.1)

If I had been thinking I would have made the function signature t(a,x), but I guess I'll stick with function(income, status).

When code is barely undertstood by the writer, is that when you win at golf?


CJam, 28 bytes

r__&,a\2*e`0f=_2ew::+]::e>S*

Try it online.

How it works

r    e# Read a whitespace-separated token from STDIN.
__   e# Push two copies.
&    e# Intersect two of the copies (removes duplicates).
,a   e# Calculate the length and wrap it in an array.
\    e# Swap the array with the input string.
2*   e# Repeat the input string two times.
e`   e# Perform run-length encoding.
0f=  e# Keep only the repetitions.
_2ew e# Copy and push the overlapping slices of length two.
::+  e# Add the integers in the resulting slices.
]    e# Wrap the entire stack in an array.
::e> e# Compute the maximum of each of the three arrays.
S*   e# Join, separating by spaces.


Python, 29 bytes

lambda s:ord(s[-1])-ord(s[0])

The sum of the differences forms a telescopic series, so most summands cancel out and
(s1 - s0) + (s2 - s1) + … + (sn-1 - sn-2) + (sn - sn-1) = sn - s0.

If taking a byte string as input is allowed

lambda s:s[-1]-s[0]

will work as well for 19 bytes.

Test both on Ideone.


Pre-rule-change answer:

C# / ECMAScript 6 - 12

r=>r

Because overlapping rectangles are allowed, we need at most r rectangles.

Proof:

With a circle of radius 10, it can be filled with 10 rectangles. Each rectangle has been highlighted in a distinct colour.

Older pre-rule-change answer:

C# / ECMAScript 6 - 0.444

r=>1

I believe this meets all the rules as of the time of this writing.

It evaluates to the number of rectangles required to fill a circle, rasterized with this algorithm:

inCircle = max(|x|,|y|) <= radius

This algorithm doesn't yield very high-quality results, but it can still be useful. The popular video game Minecraft uses this algorithm.


JavaScript (ES6),  49  47 bytes
Takes input as (a)(b,n).

a=>g=(b,n)=>n*b?g(g(b-1,n),n-1):-~[b,a-1,-1][n]

Try it online!
Commented
a =>                  // main function taking a
  g = (b, n) =>       // g = recursive function taking b and n
    n * b ?           // if neither n nor b is equal to 0:
      g(              //   go recursive:
        g(b - 1, n),  //     b = g(b - 1, n)
        n - 1         //     decrement n
      )               //   end of recursive call
    :                 // else:
      -~[             //   this is a leaf node:
        b,            //     if n = 0, return b + 1
        a - 1,        //     if n = 1, return (a - 1) + 1 = a
        -1            //     if n = 2, return -1 + 1 = 0
      ][n]            //     if n > 2, return -~undefined = 1


Convert Salesforce 15-character ID to 18-character

Pyth, 23 22 bytes
1 byte saved by FryAmTheEggman.
sm@s+JrG1U6i}RJ_d2c3pz

Try it online. Test suite.
This might be the first time I've used the print instruction in golfing.
Explanation
     JrG1                   save uppercase alphabet in J
                     z      input string
                    p       print it without newline
                  c3        split into 3 parts
 m              d           for each part:
               _              reverse
            }R                map characters to being in
              J                 uppercase alphabet (saved in J)
           i     2            parse list of bools as binary
  @                           get correct item of
     J                          uppercase alphabet (saved in J)
   s+    U6                     add nums 0-5 to it
s                           concatenate and print


All non-empty finite sets of positive integers

GolfScript, 21 characters
;]]0{)\{.2$+.p}%\1}do

A GolfScript version which prints all generated sets. It basically does the same as my Python version although not by recursion but instead collecting all possible sets in an array.
;        // clear the stack
]]       // put [[]] on the stack - the array of generated sets
            (initially an array with only the empty set)
0        // counter starts with zero
{        // start of infinite loop
  )      // increase counter
  \{     // map for each item of the array
    .    // duplicate item (i.e. this is a set)
    2$+  // append counter
    .p   // print the newly generated set
  }%\    // end of map => now the array contains all sets with max. up to counter
1} do    // end of infinite loop


CJam, 65 bytes

q'"/La+2%{0s*}:Z~_,:L')*+{L{4{)_Z+s/Z}/L{'(\Z')++/Z}/}*')-}2*0s-!

Gosh, I wish CJam had Regex, this could have been completed in less than 50 bytes then

The main idea is to keep reducing stuff to 0 i.e. 10 to 0, 200 to 0 and so on. Once that is done, we reduce all matched brackets to 0, i.e. () to 0, (0) to 0, (00) to 0 and so on. The we repeat the cycle L times, where L is the input length.

The input string initially goes through extra processing where we adjust for unmatched " and add lots of ) to compensate for unmatched (

This ensures that after all the iterations, we should only have 0 (and no-op )) left in the string.

Update - fixed a bug where top level ) no-op are considered harmful

Code expansion

q'"/La+2%{0s*}:Z~_,:L')*      "Part 1 - Preprocessing";
q'"/                          "Read the input and split it on quote";
    La+                       "Add an extra empty array to the split array to compensate";
                              "for unmatched ending quote";
        2%                    "Take every other splitted part, ignoring the contents";
                              "of the strings in the code";
          {0s*}:Z~            "Join the parts by string 0. Also create a function Z";
                              "that does that for future use. We are now done with";
                              "reducing "XYZ" to 0 ";
                  _,:L        "Store the length of the remaining code in L";
                      ')*     "Append L ) to the string to compensate for unmatched (";

{L{4{)_Z+s/Z}/L{'(\Z')++/Z}/}*')-}2*   "Part 2 - the reducing loop";
 L{                         }*         "Run the reduction logic L times";
   4{)_Z+s/Z}/                         "Part 2a - reducing arities";
   4{       }/                         "Run the iteration for 0, 1, 2 and 3";
     )_                                "Increment the iteration number and make a copy";
       Z+s                             "Get that many 0 and append it to the number";
          /Z                           "Split the code onto this number and convert it";
                                       "to 0. This successfully reduces 10, 200, ";
                                       "3000 and 4000 to 0";
              L{'(\Z')++/Z}/           "Part 2b - reducing groups";
              L{          }/           "Run the iteration for 0 through L - 1";
                '(\Z')++               "Get the string '(<iteration number of 0>)'";
                        /Z             "split on it and join by 0. This successfully";
                                       "reduces (), (0), (00) and so on .. to 0";
                              ')-      "After running the part 2 loop L times, all";
                                       "reducible arities and brackets should be reduced";
                                       "except for cases like '30)00' where the no-op )";
                                       "breaks the flow. So we remove ) from the code";
                                       "and run Part 2 L times again";

0s-!                          "Now, if the code was valid, we should only have 0 in the";
                              "remaining code. If not, the code was invalid";

Try it online here or run the whole suite


Use lmap instead foreach. This requires Tcl 8.6.

The syntax is the same, but lmap returns a list with the result of each loop.


Haskell, 184 characters

main=putStr.unlines$zip[1..](s>>=g)>>=h
s=(1,1):(s>>=f)
f(a,b)=[(a,a+b),(a+b,b)]
g x@(a,b)=[x,(-a,b)]
h(i,(a,b))=(i^2)%(u a++'/':u b):map(%"0")[i^2+1..i*(i+2)]
i%s=u i++": "++s
u=show

This does a breadth-first traversal of the Calkin-Wilf Tree, yielding all positive rational numbers in reduced form exactly once. It then alternates between positive and negative to cover all the non-zero rational numbers and pads with zeroes between the square entries.

Output (excluding zero lines for brevity):

1: 1/1
4: -1/1
9: 1/2
16: -1/2
25: 2/1
36: -2/1
49: 1/3
64: -1/3
81: 3/2
100: -3/2
...


Python 2, 215 192 184 183 bytes

-8 bytes thanks to Raphaël Côté
-1 byte thanks to Jonathan Frech

a,b=input()
j=' '.join
s=b-set(a)
print"""  +---+
  |   |
  %s   |
 %s%s%s  |
 %s %s  |
      |
=========
"""%tuple('O/|\/\\'[:len(s)].ljust(6)),j(['_',i][i in b]for i in a),'\n',j(s)

Try it online!


Haskell, 214 199 188 175 bytes

 g 0=[]
 g n=mod n 5:g(div n 5)
 d#s=sum[n|c<-d,(i,n)<-zip['0'..]$g s,c==i]
 f s=(s#0x300BBD37F30B5C234DE4A308D077AC8EF7FB328355A6,s#0x2D5E73A8E3D345386593A829D63104FED5552D080CA)

Try it online!

The numbers of lines and curves are the digits of base-5 numbers and stored as base-16 numbers. Function g translates back to base-5.

Edit: -13 bytes thanks to @cole.


Calculate to how many cubes one cube can be cut

Mathematica, 62 bytes (or 52)

It's hardcoded answer, nothing interesting.

  If[EvenQ@BitShiftRight[164015534735101,n],Print@n]~Do~{n,1000}

This one is 52 bytes long but violates my rules - it uses large integers (powers of 2) and lists (Range).

  Select[Range@1000,EvenQ@Floor[164015534735101/2^#]&]


05AB1E (legacy), 5 bytes
.œþOà

Try it online or verify a few more test cases. (Times out for the larger test cases due to the .œ builtin.)
05AB1E, 11 6 bytes
þмS¡þO

Try it online or verify a few more test cases.
Explanation:

.œ      # Get all partitions of the (implicit) input-string,
        # which are all possible ways of dividing the input-strings into substrings
  þ     # Only leave the items consisting of digits for each partition
        # (in the new version of 05AB1E, an explicit `€` is required)
   O    # Sum each inner list
    à   # Pop and push its maximum
        # (after which the result is output implicitly)

þм      # Only leave the non-digits of the (implicit) input-string
        #  i.e. "the 5is 108 seCONd4 a" → "the is  seCONd a"
  S     # Split it into a list of characters
        #  → ["t","h","e"," ","i","s"," "," ","s","e","C","O","N","d"," ","a"]
   ¡    # Split the (implicit) input-string by each of these characters
        #  → ["","","","","5","","","108","","","","","","","4","",""]
    þ   # Remove the empty strings by only leaving the digits
        #  → ["5","108","4"]
     O  # And sum these numbers (which is output implicitly)
        #  → 117


Pyth, 23 21 20 bytes

e.ff!-sMT^R2Z./`^Z2Q

Thanks to @isaacg for golfing off 1 byte!

Try it online.

How it works

                      (implicit) Store the evaluated input in Q.
 .f                Q  Filter; find the first Q positive integers Z such that:
                ^Z2     Compute the square of Z.
               `        Cast to string.
             ./         Compute all partitions of the string.
   f                    Filter; find all partitions T such that:
      sMT                 Cast all elements of T to integer.
         ^R2Z             Compute the squares of all integers in [0, ..., Z-1].
     -                    Remove the squares from the integers in T.
    !                     Compute the logical NOT of the result. This returns True
                          iff all integers in T are squares of numbers less than Z.
                        Keep T if `!' returned True.
                      Keep Z if `!' returned True for at least one T.
e                     Retrieve the last of the Q matches.


Perl 6, 45 bytes

{({[+] @_.join.uninames>>.comb X-6}...*)[$_]}

Try it online!
No need for fancy moduloing when you can get the name of the digit directly! Anonymous code block that returns the nth value of the sequence, or you can pass in a range to get a list of values
Explanation:
{(                                     )[$_]}  # Index input into:
  {                               }...*        # An infinite sequence
                                               # Where each element is
   [+]   # The sum of
       @_.join  # All previous elements joined together
              .uninames  # The unicode names for each character
                         # These are names in the form "DIGIT ONE"
                       >>.comb  # Split each to lists of characters
                               X-6  # Subtract 6 from each


Mathematica, 95 bytes

Another implementation of the Cooley–Tukey FFT with help from @chyaong.

{n=Length@#}~With~If[n>1,Join[+##,#-#2]&[#0@#[[;;;;2]],#0@#[[2;;;;2]]I^Array[-4#/n&,n/2,0]],#]&

Ungolfed

FFT[x_] := With[{N = Length[x]},
  If[N > 1,
    With[{a = FFT[ x[[1 ;; N ;; 2]] ],
          b = FFT[ x[[2 ;; N ;; 2]] ] * Table[E^(-2*I*Pi*k/N), {k, 0, N/2 - 1}]},
      Join[a + b, a - b]],
    x]]


J, 17

*/<:$&q:(<:,],>:)

Returns booleans encoded as process return codes: zero for true, nonzero for false.  Sample use:

   */<:$&q:(<:,],>:) 7
0
   */<:$&q:(<:,],>:) 8
0
   */<:$&q:(<:,],>:) 15
3


J: 40 26 29 22

=,&(+/)(~:#[)e.&~.~:#]

change: don't laminate, but work truly dyadically, eliminating need for explicit ranks ("1), lamination(,:) and between (/)
change: don't count duplicate characters twice
change: Strings are more efficient as they don't need parsing

This verb takes a left and right argument a string from '0000' to '9999'.
It takes care of doubles and excludes exact matches from checking correct numbers but wrong place.

Test cases:

NB. Give the beast a name
mm=: =,&(+/)(~:#[)e.&~.~:#]
NB. make 6 by 4 arrays of the inputs
secret =: (, ;. _2) '1254 1234 5441 5441 5441 5441 '
guess  =: (, ;. _2) '1342 1111 1234 4531 4441 5441 '

NB. Apply the verb on each pair of secret/guess
'1111' mm '1231'
2 0

NB. A whole bunch of test cases with formatting and printing of the inputs:
secret ([,' ',(":@mm),' ',])"1 guess

NB. output:
1254 1 2 1342
1234 1 0 1111
5441 0 2 1234
5441 1 2 4531
5441 3 0 4441
5441 4 0 5441

A little bit of explanation, reading from right to left:

NB.   ExactMatch: checks where digits correspond:
ExactMatch =: =

NB.   GoodDigitWrongPlace: Copies non-matched numbers from both arguments (left and right
NB.   pairs of parentheses, and checks them for same elements(e.), after eliminating
NB.   doubles in both (&~.)
GoodDigitWrongPlace =: (~: # [) (e.&~.) (~: # ])

NB.   Piecing the conditions together, after summing the booleans:
mm =: ExactMatch ,&(+/) GoodDigitWrongPlace


All non-ordered pairs between the elements of an array

Haskell, 29 bytes

f(a:b)=map((,)a)b++f b
f _=[]

Try it online! Example usage: f ["a","b","c"] yields [("a","b"),("a","c"),("b","c")].

With the flag -XTupleSections this can be shortened to 27 bytes, however the flag would need to be counted:

f(a:b)=map(a,)b++f b
f _=[]

Try it online!


C
I will take a stab at it with a textbook-like example:
#include <stdio.h>
#include <stdlib.h>

int main()
{
    char a[] = {1,2,3,4,5,6,7,8};
    if (sizeof(&a) > sizeof(int)) {
        printf("foo %d %d\n", *(int *)a, *(long *)a);
    } else {
        printf("bar %d %d\n", *(int *)a, *(long *)a);
    }
}

64-bit Platform prints: foo
32-bit Platform prints: bar
Little Endian Platforms: 67305985
Big Endian Platforms: 16909060
So there is at least 4 combinations.
On top of that, some very old platforms has int defined as 16-bits. And some platform has long defined as 64-bits. So the result will be different as well.
C has been quite platform specific, if you dig deep enough. It is not hard to come up with thousands of combinations (2^10+).


Extending OEIS: Counting Diamond Tilings

Algebra, graph theory, Möbius inversion, research, and Java

The symmetry group of the hexagon is the dihedral group of order 12, and is generated by a 60 degree rotation and a mirror flip across a diameter. It has 16 subgroups, but some of them are in non-trivial conjugacy groups (the ones which only have reflections have 3 choices of axis), so there are 10 fundamentally different symmetries which a tiling of the hexagon can have:

The number of diamond tilings of a subset of a triangular lattice can be calculated as a determinant, so my initial approach was to set up one determinant for each of the symmetries of the hexagon, to calculate the number of tilings which have at least those symmetries; and then use Möbius inversion in the incidence algebra of their poset (basically a generalisation of the inclusion-exclusion principle) to work out the number of tilings whose symmetry group is exactly each of the 10 cases. However, some of the symmetries have nasty edge conditions, so I was forced to sum over exponentially many determinants. Fortunately, the values obtained for n < 10 gave me enough data to be able to identify relevant sequences in OEIS and piece together a closed form (for some value of "closed" which allows finite products). There's a bit of discussion of the sequences, and references to proofs, in the formal writeup which I prepared to justify the OEIS sequence updates.

Once the double-counting is taken care of, it turns out that four of the ten values cancel out neatly, so we only have to calculate the remaining six and then do a weighted sum.

This code takes under 30 seconds for N=1000 on my machine.

import java.math.BigInteger;

public class OptimisedCounter {
    private static int[] minp = new int[2];

    public static void main(String[] args) {
        if (args.length > 0) {
            for (String arg : args) System.out.println(count(Integer.parseInt(arg)));
        }
        else {
            for (int n = 0; n < 16; n++) {
                System.out.format("%d\t%s\n", n, count(n));
            }
        }
    }

    private static BigInteger count(int n) {
        if (n == 0) return BigInteger.ONE;

        if (minp.length < 3*n) {
            int[] wider = new int[3*n];
            System.arraycopy(minp, 0, wider, 0, minp.length);
            for (int x = minp.length; x < wider.length; x++) {
                // Find the smallest prime which divides x
                for (wider[x] = 2; x % wider[x] != 0; wider[x]++) { /* Do nothing */ }
            }
            minp = wider;
        }

        BigInteger E = countE(n), R2 = countR2(n), F = countF(n), R3 = countR3(n), R = countR(n), FR = countFR(n);
        BigInteger sum = E.add(R3);
        sum = sum.add(R2.add(R).multiply(BigInteger.valueOf(2)));
        sum = sum.add(F.add(FR).multiply(BigInteger.valueOf(3)));
        return sum.divide(BigInteger.valueOf(12));
    }

    private static BigInteger countE(int n) {
        int[] w = new int[3*n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= i + n; j++) w[j]--;
            for (int j = i + n + 1; j <= i + 2*n; j++) w[j]++;
        }
        return powerProd(w);
    }

    private static BigInteger countR2(int n) {
        int[] w = new int[3*n];
        for (int i = 0; i < n; i++) {
            w[3*i+2]++;
            for (int j = 3*i + 1; j <= 2*i + n + 1; j++) w[j]--;
            for (int j = 2*i + n + 1; j <= i + n + n; j++) w[j]++;
        }
        return powerProd(w);
    }

    private static BigInteger countF(int n) {
        int[] w = new int[3*n];
        for (int i = 0; i < n; i++) {
            for (int j = 2*i + 1; j <= 2*i + n; j++) w[j]--;
            for (int j = i + n + 1; j <= i + 2*n; j++) w[j]++;
        }
        return powerProd(w);
    }

    private static BigInteger countR3(int n) {
        if ((n & 1) == 1) return BigInteger.ZERO;
        return countE(n / 2).pow(2);
    }

    private static BigInteger countR(int n) {
        if ((n & 1) == 1) return BigInteger.ZERO;
        int m = n / 2;
        int[] w = new int[3*m-1];
        for (int i = 0; i < m; i++) {
            for (int j = 1; j <= 3*i+1; j++) w[j] += 2;
            for (int j = 1; j <= i + m; j++) w[j] -= 2;
        }
        return powerProd(w);
    }

    private static BigInteger countFR(int n) {
        if ((n & 1) == 1) return BigInteger.ZERO;
        int m = n / 2;
        int[] w = new int[3*n-2];
        for (int j = 1; j <= m; j++) w[j]--;
        for (int j = 2*m; j <= 3*m-1; j++) w[j]++;
        for (int i = 0; i <= 2*m-3; i++) {
            for (int j = i + 2*m + 1; j <= i + 4*m; j++) w[j]++;
            for (int j = 2*i + 3; j <= 2*i + 2*m + 2; j++) w[j]--;
        }
        return powerProd(w);
    }

    private static BigInteger powerProd(int[] w) {
        BigInteger result = BigInteger.ONE;
        for (int x = w.length - 1; x > 1; x--) {
            if (w[x] == 0) continue;

            int p = minp[x];
            if (p == x) result = result.multiply(BigInteger.valueOf(p).pow(w[p]));
            else {
                // Redistribute it. This should ensure we avoid negatives.
                w[p] += w[x];
                w[x / p] += w[x];
            }
        }

        return result;
    }
}


GolfScript, 219 characters
Basic approach using a lookup table:
"Total key presses "0@1/{"1adgjmptw °behknqux\n.°cfilorvy0,\"°ADGJMsTz'-/°BEHKNPUW?(:&°CFILOQVX!)_%>°23456R8Y@;*£¤°SZ+=€[~°79<$]^§°¥{¡#°}¿|°`°".2$?)\1$<"°"/,{"Invalid character  in source"18/*puts'"#{''exit}"'+~}if\;+}/

Try here.


Java (JDK 10), 66 bytes

a->b->{for(int i=a.length,t;i-->0;b[i]^=t)a[i]^=t=(a[i]^b[i])&32;}

Try it online!

Explanations

a->b->{                           // Curried lambda
 for(int i=a.length,t;i-->0;      //  Descending loop on i,
                                  //  Declare t
     b[i]^=t                      //   Apply the case difference to b[i]
   )
  a[i]^=t=(a[i]^b[i])&32;         //   Assign the case difference of the two letters to t, and apply it to a[i].
}


CJam, 46 44 43 42 bytes

l~),{_A%g1$s_6890s-!\_69s_W%erW%=!&&'.*N}/

I think there's some room for improvement.

Test it here.

Explanation

l~),{_A%g1$s_6890s-!\_69s_W%erW%=!&&'.*N}/
l~                                         "Read an eval input.";
  ),                                       "Get range from 0 to n.";
    {                                   }/ "For each...";
     _                                     "Get a copy of the integer.";
      A%g                                  "Ends with digit other than 0?";
         1$s_                              "Get another copy, convert to string, get a copy.";
             0689s-!                       "Contains rotation-safe digits?";
                    \                      "Swap with other copy.";
                     _                     "Get another copy.";
                      69s_W%er             "Swap 6 and 9.";
                              W%           "Reverse.";
                                =!         "Is different from original?";
                                  &&       "AND all three conditions.";
                                    '.*    "If true, push a period (else, an empty string).";
                                       N   "Push a newline.";


Sort the unique numbers in a multiplication table

Python 2, 61 51 bytes

lambda n:sorted({~(i%n)*~(i/n)for i in range(n*n)})

Thanks to xnor for shortening some syntax.


Write a program that outputs the number of times it has been run

bash (+ wc + id), 16 bytes

wc -l<$0;id>>$0

Counts its lines, then appends a line of garbage to itself.

Needs a trailing newline.

Crashes on line 2 with a syntax error, which thankfully prints to STDERR and exits.

After three invocations, the script looks like this for me:

wc -l<$0;id>>$0
uid=1000(lynn) gid=1000(lynn) groups=1000(lynn),4(adm),24(cdrom),27(sudo),30(dip),46(plugdev),113(lpadmin),128(sambashare)
uid=1000(lynn) gid=1000(lynn) groups=1000(lynn),4(adm),24(cdrom),27(sudo),30(dip),46(plugdev),113(lpadmin),128(sambashare)
uid=1000(lynn) gid=1000(lynn) groups=1000(lynn),4(adm),24(cdrom),27(sudo),30(dip),46(plugdev),113(lpadmin),128(sambashare)


Javascript (ES6), 1216 1206 1131 + 180 => 1311 bytes

a=>{a=a.replace(/\s/g,'');b=[];d={};e=[];f=[];g=[];h='.';[].concat.apply([],a.split('.').filter(k=>k).map(k=>k.match(/([^.])(\1*)/g)||k)).forEach(k=>k.length>1?(b.push(k[0]),(k.length<3?g:f).push(k[0])):(!e.includes(k)&&e.push(k),d[k]=d[k]?d[k]+1:1));Object.keys(d).forEach(k=>(d[k]<3?g:f).push(k));j=(l,m,n)=>l.substr(0,m)+n+l.substr(m+n.length);o=(p,q)=>~q.indexOf(p);I=(s,r,c)=>s.charAt(r*6+c)||'@';t=(s,r,c,F,G)=>{k=0;while(I(s,r+k*F,c+k*G)==h)k++;return k};u={};w=[];x={};x=(y,z,A)=>u[y]===[][0]?(u[y]=z,x[y]=A,w.push(y)):0;C=B=>{var z=u[B];return (!z?'':C(z))+x[B]};D=(B,r,c,q,E,F,G,n)=>{r+=E*F;c+=E*G;H=I(B,r,c);if(!o(H,q))return;L=o(H,f)?3:o(H,g)?2:[][0];J=B;for(i=0;i<n;i++){r-=F;c-=G;J=j(J,r*6+c,H);J=j(J,(r+L*F)*6+c+L*G,h);x(J,B,H+(!~F?'v':F?'^':!~G?'>':'<'));B=J}};x(a,null,'');K=!1;while(w.length) {B=w.splice(0,1)[0];if(I(B,2,5)=='R'&&!K){K=!0;break}for(r=0;r<6;r++){for(c=0;c<6;c++){if(I(B,r,c)!=h)continue;nU=t(B,r,c,-1,0);nD=t(B,r,c,1,0);nL=t(B,r,c,0,-1);nR=t(B,r,c,0,1);D(B,r,c,e,nU,-1,0,nU+nD-1);D(B,r,c,e,nD,1,0,nU+nD-1);D(B,r,c,b,nL,0,-1,nL+nR-1);D(B,r,c,b,nR,0,1,nL+nR-1)}}}return C(B).replace(/(R.)+$/,'Rx')}

I followed the algorithm and example from here. Rewriting the algorithm and input in the example to output moves cost a lot of bytes. I'm planning on rewriting the answer using an algorithm specifically designed for outputting moves instead of outputting board states.

Ungolfed:

func = inp => {
    inp = inp.replace(/\s/g, '');

    HORZS = [];
    tVERTS = {};
    VERTS = [];
    LONGS = [];
    SHORTS = [];
    EMPTY = '.';

    [].concat.apply([], inp.split('.').filter(k => k).map(k => k.match(/([^.])(\1*)/g) || k)).forEach(k =>
        k.length > 1 ? (
            HORZS.push(k[0]),
            (k.length < 3 ? SHORTS : LONGS).push(k[0])
        ) : (
            !VERTS.includes(k) && VERTS.push(k),
            tVERTS[k] = tVERTS[k] ? tVERTS[k] + 1 : 1
        )
    );
    Object.keys(tVERTS).forEach(k => (tVERTS[k] < 3 ? SHORTS : LONGS).push(k));

    setCharAt = (str, index, character) => str.substr(0, index) + character + str.substr(index + character.length);

    isType = (entity, type) => ~type.indexOf(entity);

    at = (state, r, c) => state.charAt(r * 6 + c) || '@';

    countSpaces = (state, r, c, dr, dc) => {
        k = 0;
        while (at(state, r + k * dr, c + k * dc) == EMPTY) k++;
        return k;
    };

    pred = {};
    queue = [];
    moves = {};

    propose = (next, prev, move) => pred[next] === [][0] ? (pred[next] = prev, moves[next] = move, queue.push(next)) : 0;

    trace = current => {
        var prev = pred[current];
        return (!prev ? '' : trace(prev)) + moves[current];
    };

    slide = (current, r, c, type, distance, dr, dc, n) => {
        r += distance * dr;
        c += distance * dc;
        car = at(current, r, c);
        if (!isType(car, type)) return;
        L = isType(car, LONGS) ? 3 : isType(car, SHORTS) ? 2 : [][0];
        sb = current;
        for (i = 0; i < n; i++) {
            r -= dr;
            c -= dc;
            sb = setCharAt(sb, r * 6 + c, car);
            sb = setCharAt(sb, (r + L * dr) * 6 + c + L * dc, EMPTY);
            propose(sb, current, car + (!~dr ? 'v' : dr ? '^' : !~dc ? '>' : '<'));
            current = sb;
        }
    };

    propose(inp, null, '');
    solved = !1;
    while (queue.length) {
        current = queue.splice(0, 1)[0];
        if (at(current, 2, 5) == 'R' && !solved) {
            solved = !0;
            break;
        }

        for (r = 0; r < 6; r++) {
            for (c = 0; c < 6; c++) {
                if (at(current, r, c) != EMPTY) continue;
                nU = countSpaces(current, r, c, -1, 0);
                nD = countSpaces(current, r, c, 1,  0);
                nL = countSpaces(current, r, c, 0, -1);
                nR = countSpaces(current, r, c, 0,  1);
                slide(current, r, c, VERTS, nU, -1, 0, nU + nD - 1);
                slide(current, r, c, VERTS, nD, 1,  0, nU + nD - 1);
                slide(current, r, c, HORZS, nL, 0, -1, nL + nR - 1);
                slide(current, r, c, HORZS, nR, 0,  1, nL + nR - 1);
            }
        }
    }

    return trace(current).replace(/(R.)+$/, 'Rx');
}

Example usage and output:

func(`......
11..22
RRC...
..C..3
..C..3
..66..`); // ==> "6<6<CvRx"

func(`11...C
D..E.C
DRRE.C
D..E..
2...33
2.FFF.`); // ==> "1>D^2^Cv3<3<3<CvCvEvF<F<EvRx"

func(`112.33
442..C
DRR..C
DEEE.C
D..566
77.588`); // ==> "3<C^R>R>2vE>E>2v2v2v1>4>D^D^R<R<E<E<E<5^5^5^Cv6<Cv8<Cv3>5^Rx"

func(`C.1DDD
C.12..
CRR2..
3344.E
.....E
5566.E`); // ==> "4>3>CvCvD>2^Rx"

func(`C11.2.
C34.2D
C34RRD
EEE5.D
..6577
88699.`); // ==> "D^9>5vE>E>E>E>Cv1<4^R<3v3vR<5^5^5^5^R>R>E<E<Dv7<Dv9<DvRx"


Javascript, 14325 14311 calls
We start with an empty string and go our way recursively by adding a new letter at the end or at the beginning of the current string while we still have at least one match.
All previous results from numOccur() are saved in the sym object and we use this data to reject immediately any new string that can't possibly be a candidate.
EDIT: Because we always start with 'a', we always know the exact number of a in the string. We use this information to end the process earlier when we detect that only a sequence of a is missing. Also fixed the regular expression which was invalid in Chrome and IE.
var test = [
  'ccccbcbbbbacbaaababbccaacbccaaaaccbccaaaaaabcbbbab',
  // etc.
];
var call = 0;

function guess(S, len) {
  var sym = {};
  recurse(S, len, "", sym);
  return sym.result;
}

function recurse(S, len, s, sym) {
  var dictionary = [];

  if(s == '' || (isCandidate(s, sym) && (sym[s] = numOccur(S, s)))) {
    if(s.length == len) {
      sym.result = s;
    }
    else if(sym['a'] && count(s, 'a') == sym['a'] - (len - s.length)) {
      dictionary = [ Array(len - s.length + 1).join('a') ];
    }
    else {
      dictionary = [ "a", "b", "c" ];
    }
    dictionary.some(function(e) {
      return recurse(S, len, s + e, sym) || recurse(S, len, e + s, sym);
    });
    return true;
  }
  return false;
}

function isCandidate(s, sym) {
  return sym[s] === undefined && Object.keys(sym).every(function(k) {
    return count(s, k) <= sym[k];
  });
}

function count(s0, s1) {
  return (s0.match(new RegExp(s1, 'g')) || []).length;
}

function numOccur(S, s) {
  call++;
  return count(S, s);
}

test.forEach(function(S) {
  if(guess(S, S.length) != S) {
    console.log("Failed for: '" + S + "'");
  }
});
console.log(call + " calls");

Full executable snippet below.

var test = [
  'ccccbcbbbbacbaaababbccaacbccaaaaccbccaaaaaabcbbbab',
  'caccbbababbaaaccbcabbaabaabcacabacaababcabcbbacaac',
  'bbbbaacabcabacaccaaaabaaacaacabbcbacabaccbbcbabbcbc',
  'abbcbcbccbccaacaccaccaabaccbbcabaaccabccbbbabbbcabc',
  'aabacbbbcaaabcccaccccbcaabcacaccbabbbcccacabaaababca',
  'bccbbaaccaaccacabaaaabbbbaababacabaaabacbcacbbbbabaa',
  'bbbcbcabbacbaacbacabcbabbacacbbcbcabbaabbbccbacaaacac',
  'ccbcbbbaaaaaccbaacbabbbcbccbabaabccbcbcbcbabcbbccacba',
  'aacbcbcabcbcbccbabbacacbcaaababbbcacaacaccbabbbbabcaac',
  'bcabacaabbacccacaabcaaacbcbcbacabbababcabbbbacbaaaabbb',
  'abbaccccabbbcbbaacccacbcaacababaccabbabbacbbbaabaacbaba',
  'cabbacabacccabcabacbaacbaababcaccbacbaaaacbbabbbccabbbb',
  'bcabccaaabcbaaccaabccbbcbabaccababbbaccccacaaccaccacbcab',
  'abbcbabaacbcbbabbccccbccabcbbaccacbabcacbaacbccbcabcccbc',
  'bcbacabbaabcccabccacbcbccbcbbbccacbbccaabaacccccbcabaaccc',
  'baccbcacaccacbbbcccbaaacbaccacbbacbbbaccccacbabcbbbaacabb',
  'bcccabaaaabcbbbaaccbcaccbaabacccaaacbaabaccccacabaccacbcac',
  'baabcbbcaabcacbabbcacccbcabbabaacbbbababbbbbccccccbcbbcbcc',
  'bacacbbabbcbbcaacabcccccbbacabcaabbbcbbabaacbcbbaccaaacbbac',
  'ccabccbccbaaacbcccccabacbbabbbbccbccccabaabaabbaacbabcabbcb',
  'abbaccbcaabacbbacabaabbcbacbacacabccbbcccaccbbacbbbaacbaccab',
  'bbbbaaabababcccbbbababacbacbaabbabccacccaaacabaccababaccbcac',
  'bbcbbbbcccaccbbbcbcaaccbcacaabbbbabaaabbbaaacbbaaccbacaccabbb',
  'cacabcabcbcbbbbcabbbccccccccacaaabaacbcaabbabcacbcbcccccacaab',
  'babbcacabaabbccabcbbaacccaaccbabcbbcbcbbbcabbcccbcacbabccaccac',
  'ccbbcbcbcaacbcaaccacbcaabbbcbbaccbbabacacccccaccaababcacccccba',
  'bcccbcacccccabccabccbcbccaccaaacbcacabaabcbcccaccaaaabbcacbbcaa',
  'cbbcacbbacaacbabccaabbaabacacbcbcbabcaccabbbbcabbbabaaacccaabcc',
  'aabbaacccaaacbcaabcabaabbbaababbbbcbacabbbbbbbbccaccccbbaccbbaaa',
  'abbcccabbabbaccccaacbabbccccbbbbccaaacaabacbabbabcabacbaabcbcacb',
  'bcacbccccaacbbcaccbcbcbbabacabacabbcaaabbccabcccbaacabcbbcacababb',
  'acabacaabcabbcccccbcacaccccbccaaaacacbbbccbcaabaacbbbacabcbcaabca',
  'caabbaccaacbbcbaacbcabccacacabbcbcbbacabbbaacccaacccabaaaccbbacbaa',
  'baaabbcbbbaacabacbcaaacabbacaacbacabbcabcccbabcbbacacbbababccacabc',
  'abbbacbaabcabbcabbbabaababbaabcacbabbaababcabbbccccbcaacbbcccabaccb',
  'caaababcacccaccababaccbabbccaabbbbbabaabcabccbabbbbbbcbacbabcbcccbb',
  'abbbcaaaaacaaacbbbcbacabbcbbbccacaccacacabacacbbccbbbcbaccabbcbaabbc',
  'bacacbcccabcabaabacccbcaaabcabbbcccaacbabacbaabbcccacaacbabbcacbaabb',
  'bacaaaccbaababbbbbcaabcabaacccabacccbabcbccbbcbcaacbbaabcaccaaaacaabb',
  'bbacaacccaaacacccbbacbcbbaaaccccabbbbcbbbabaaaaccbccaababaccbbccacaca',
  'aacccccbabaccbcbcbbaccbacbcbacaababaaaccbaaabaabcccccacbbaabcccaababcc',
  'babacacbbbacbbbbbabbabababacabacaaacbbccaccabacaacbabbbaccacccbcaaabbb',
  'bcaccabbabbcbcabccbbcaacbbcbacbcabaaaaaacaaacaccbcaaccaaccacbaccacaabbc',
  'acbcbbcbbaacbbbabbaabacabbcccabacabcabacccacbcaacacabcaaaabbabcccbcbabb',
  'ccbcbcccbccbbbabaabbaababbcbacacbcbaacaccccccbcbacacbcabaaaacaacbbbbacba',
  'cccbcbaaabcbbcbabbbaccabbabcacbaccbcababbababcbcaccabbbccabaabaaccccacbb',
  'bbabcbcaabbacaabcababbbccbccccaaaabaccbbbbababbcabbabbaccaaaabbcbbbcbaccc',
  'cbacaccaaaacaacbbcbbacaccabacaacacaacaacabccaaaccccacaaaaabcbcabaabaacccb',
  'bcacbccabcccabababbbbcabaacabcbbaacaaaabbbacccaaabccbaabcbbabbbcccabaabbbb',
  'cbccacabaaacabbccbacabccacabcbaccbababcccabbabbbbbbccbaabbaacaacaaaabcbabb',
  'abcbcabbcabaababccbcacabbcbcabcaabbbabbcaaabaaaaacbaabaaababccacbabcbaccbab',
  'aabbabbbcacaaaabcbcabccccacbacbccacacaabccacccaaacacbcccaabbbccacacbbccbbac',
  'caacbbccacaaaacabaacbcaaaccbbabbcacababbbabcbccbaabccaababbcbacbccababbcbbbc',
  'aaabaaaabbbbbcbbbacabccbaaaaabaacbacbcccbccacccacaaacaccbbabcbcccbbccccabbcb',
  'cccccacacbacbbcbbcabcbaabbcbbbacabcbbccccaaacabcababbcaaccaabccabaccbcaccbaba',
  'ccaaaccbccacabcacaccbccaabacacabaabbbaacbcacaacbaaabbbbabbabcccabcabbaccacacc',
  'cbbbcaccbcacccbacccaaaabacaacccbcbcbabbbaababacccccccabbaaabbcbaabbbbbbaaaaaaa',
  'ccbcbcbaabbccabbabbccbacbabacbcacbccacaabbcacaaccabbbbcbacbbcaaabaabccaacccacb',
  'caaabcabaacbbabcbccabcacbbcccabcacbbcaabaacaaabbbcacaaccaccaaaacaaccbbaaaacaaac',
  'bbacacbbaaaacbcabbbbbaabacaccabcbabbccbbbabbbacccababbcababcbbcacbababbbaaabcca',
  'bbacbbacacaccccbabbbbcabbcccbcacaabbcabbccaaaaabcbbcccaccbcbbbccabcbaccacbacbaba',
  'baccbcababbacabcbabacaababbaabcabbcbcbccabacbbaaaaabacaaacaacbacbcabacabaaccbcab',
  'accacccabccbabcbcbaababacabcabbcaccbccabbabcbcabbaabccacbbbbcaacbccaababbababbaba',
  'bbcccbcbcbccccbcaaccaaacacbbaacbcccbbcabbbccabaacbacaaaccbcbaacababaccacbcbaaccac',
  'acbccccaabcabbbcbbccbccbacbcabcccacbcabbaacbababbbcbbccacbacccbbbaccbaaaabbbabaccb',
  'babcacaccbccbaaabaabbbaabcaabaaccccacaacbaccbcbabbbbbbabcbbbbacbacbabcbbbacbbbbbbc',
  'caabcaaaaabacccacbbbaabaabccaabcbaabbcbcbbbccbabbccbcbabbbbccacbcbcbacaaccccacbbabc',
  'bbaaabbabccaccacbcbbccaaaaababbacccbabcbacabacbaacbcabaaacacaaaaacaaacabbbbccabbbca',
  'bbcbccababbbaabbabcbbaacbccbaacbababbabcbaaccbcbcabacaabacaacabcababbaaabbbbbbccccbb',
  'acabcabccaaccccacbcaabaccacaaabcbabbabbaccbbaaacacabcabbcabababaccccbcbabaacbbcccbab',
  'bacaaaaacbcacbbbaaaaabbbbcbbcbbbcaccccbacaccbbcbabbbccbaaabbcbaccacacbcbcacbcbaaabacc',
  'bbcaabccbcaccbabbacbaacacccccaabbbccbccbbbcccbacaaaccccbccbbbbabccaaacaabbbbacaacabab',
  'aaaccccbbabbcacabaacacbabbcacbcccbcbaaacaabaabacbbaabcbbbbbcacbaccaacaacbccacbbcacbbaa',
  'bbcacabcbbcbabbabbbacaaabcabbbbacbacbabacbbbbbabacabbabaabcabbaabbbaaccbcabcababcaaacc',
  'ccccbaacbbcaccaccbaaacaccbabbabaabbababcacacaaccbbcbccaaaaaaacbccacbacbabbbabcabaabaabb',
  'abacacbaccacaaacaccbcbabcaacbccaccbbacbabcababcaabcaabcbcabbcbacabaaaaaabaccccbbbcbabac',
  'ccccacbaaabaaacabbabacbbacbabcbbcaaaaacaccacabcaacabcbcbcaccabcaaccbaccabcccbccacccbacbc',
  'bcaabcaacacccbcababccacacbccccccbbaaabacabbcbbbcbaaacbbacababbaccccacbbcbacaacbabcbaccbc',
  'cbcbbaabacbaacbbcabbbbaccbaabbacbcccaaabbabacabbbababcaabcacbaccacacaccbbbbcbcbbaaacbcbba',
  'ccbcabcaabcbabbbcbcbbabacabacbbaccbbcbcabcaccaaccbaccbaacacacbbaacaaaaabcaaaacbcccbcccaaa',
  'cbbababacbbabbabaabaaaabcacbacbcccbacbccbbcaabcabaccacccbbcaacacccccaccabaabccacbaccabaaba',
  'cbbbaaacaccbcabccacbccabacbcbcccccacaccbbcccbcbbbaababcaaaacaabbbccbacbaccabccccbbbcaaaabb',
  'bbabbacaaccacccbbcabbacbcbabcccaccacbacbccababbbcacbabbbcabbbbacabcabcbaacbaabcbccacaaaccbc',
  'babcbaabccabcabaaabcaaaabaaaaccbcbcacbbbccaccccaacbcbabbbaaaccacaaabacbbabbcacbcaaaaabaabab',
  'acbabbccacaccabccbcbabacccbabbaacbccbcaabccbcbababccacbbbaabbaaaababbcaaaaabccbacbbcacbcacba',
  'cbccbbaacacccacacacbbbcbbccabcaaaabbcacacacaccbacaacbcbcbccaacaaaaaacbacacbabbbcccabbbbababa',
  'cabaabaccbbcccabaccbbacbcabbbbbaccccccbcbcbcbbccbaaabbbbcabacabccaacbcbcbabccbbcabacababccaab',
  'bccaacbabcbccaccbabcbbcbaaccbaacabbcabbbacbbccabcabccabccbacbaacbccabccaabaaabcaababacacccaac',
  'aacabcccaaccacbbcbbbbacaacacbcbcaabbcbbacbabcbccaabcbbbbaabccbbbacaababcabaacaccababacbcbccbba',
  'caaabbcbcbcabccccacacaaababbacbabacbaaccbcbabbaaacbbccccaaaabbccbcabcbccbbaaccbbbabcaabcbbbcab',
  'aacbbcbbcbaccccbaaaabcbaaabaaacaacaaacacacabaaabacbaaaacccbaaabbbcbbbacbcbccabccaabbaabcbcbccba',
  'abaccbcacabbbbacabaacaccbcbaabbaccaabbbbbababbbcbbbbacaacabbbabcaccbacabbabcbbacbbaaccbcbacaabc',
  'aacaaaacccabcccacacbaaccccababcaccaccacbbbacabccbbcbbbacaccbbbbbaabacbacbcbcabccaaccababacaabcbb',
  'baabbabaaccabcbbabcacccccaabbccbccbcaacbbbccccbbcbacaabcccccbbabbabbcacbbccbcacabbbbaaaaccbcacca',
  'aabacbaacbbccabbbacbcbbbabacaacccabbcabacacaaaabbcbbbcbbbcababbccbbacbbabcaacbacbbcaabbbcbaaaccaa',
  'aacabaaccaaabcacccabbaabbcacbabccacabaccaaaaccccccaabcbbbaabcbcccacaccbcaaacaaaabaababccbbbcccaac',
  'bcaccbcacaccbacbcccbcbbcabaabbabcccbaaababbbabbcbcbcaabbabbccccbabccabbccccabaaabccbacabccabbbacaa',
  'ccaacbabcccbabacabaccccbcbbcccbbbacbbbcccacababccbbaaaaababbabccbccabcccbccabaccbcbcacbbbaacabccaa',
  'caccbababcbcbabccabcbbaccbbbabcbacbcbcbcabcbacbcacabbcaabbbbbbbcbbaabcacccbcaabccacbccbbcccaabcbcac',
  'bbcccaabacbacbccbbbbbaabccaaabbaabcaabbcbabbbaabcbcbacbaccabacacaaaababccaaaccacaabaabcacbcaccbaabb'
];
var call = 0;

function guess(S, len) {
  var sym = {};
  recurse(S, len, "", sym);
  return sym.result;
}

function recurse(S, len, s, sym) {
  var dictionary = [];

  if(s == '' || (isCandidate(s, sym) && (sym[s] = numOccur(S, s)))) {
    if(s.length == len) {
      sym.result = s;
    }
    else if(sym['a'] && count(s, 'a') == sym['a'] - (len - s.length)) {
      dictionary = [ Array(len - s.length + 1).join('a') ];
    }
    else {
      dictionary = [ "a", "b", "c" ];
    }
    dictionary.some(function(e) {
      return recurse(S, len, s + e, sym) || recurse(S, len, e + s, sym);
    });
    return true;
  }
  return false;
}

function isCandidate(s, sym) {
  return sym[s] === undefined && Object.keys(sym).every(function(k) {
    return count(s, k) <= sym[k];
  });
}

function count(s0, s1) {
  return (s0.match(new RegExp(s1, 'g')) || []).length;
}

function numOccur(S, s) {
  call++;
  return count(S, s);
}

test.forEach(function(S) {
  if(guess(S, S.length) != S) {
    console.log("Failed for: '" + S + "'");
  }
});
console.log(call + " calls");


Python 2, 50 bytes

print["Code\40Golf","Programming Puzzles"][" ">""]

Try it online!

With all spaces removed:

print["Code\40Golf","ProgrammingPuzzles"]["">""]

Try that online!

Thanks to Stephen S for 3 bytes, and Erik the Outgolfer for 1


Print 1 to 1000 in C++ without semi-colons

The semicolon is not needed if you know the magic word. And no need to go obfuscated.

My solution has the additional fanciness that it doesn't use any comma either ;)

#include <iostream>
#define Please(x) if (x) {}

int Number(int x)
{
    if (x > 1)
        Please(Number(x-1))
    Please(std::cout << " " << x)
}

int main()
{
    Please(Number(1000))
}


Python 3 + SymPy, 480 455 452 bytes

lambda w,h:len({min(I(D(H(V(x)))for x in o)for H,V,D in Q((lambda p:(w+~p[0],p[1]),I),(lambda p:(p[0],h+~p[1]),I),(lambda p:p[::-1],I)))for o in permutations(Q(range(w),range(h)))for s in[[*zip(o,o[1:])]]if any(x-~X-w|y+Y-h+1for(x,y),(X,Y)in zip(o,o[::-1]))+any(gcd(x-X,y-Y)>1for(x,y),(X,Y)in s)+any((len({*u,*v})>3)*intersection(S(*u),S(*v))for u,v in Q(s,s))<1})
from math import*
from sympy import*
from itertools import*
Q=product
S=Segment
I=tuple

Try it online!

Inlined version of the previous answer below. -3 bytes thanks to Kevin Cruijssen's tip.

Python 3 + SymPy, 480 bytes

from math import*
from sympy import*
from itertools import*
Q=product
S=Segment
I=tuple
def f(w,h):
 a={1}
 for o in permutations(Q(range(w),range(h))):
  s=[*zip(o,o[1:])]
  if any(x+X-w+1|y+Y-h+1for(x,y),(X,Y)in zip(o,o[::-1]))+any(gcd(x-X,y-Y)>1for(x,y),(X,Y)in s)+any((len({*u,*v})>3)*intersection(S(*u),S(*v))for u,v in Q(s,s))<1:a.add(min(I(D(H(V(x)))for x in o)for H,V,D in Q((lambda p:(w-1-p[0],p[1]),I),(lambda p:(p[0],h-1-p[1]),I),(lambda p:p[::-1],I))))
 return~-len(a)

Try it online!

The golfed version takes too long to check the nontrivial answers. The version below has a shortcut in the conditional, so you can check that the results up to (2,4) are correct.

Python 3 + SymPy, 483 bytes

from math import*
from sympy import*
from itertools import*
Q=product
S=Segment
I=tuple
def f(w,h):
 a={1}
 for o in permutations(Q(range(w),range(h))):
  s=[*zip(o,o[1:])]
  if(any(x+X-w+1|y+Y-h+1for(x,y),(X,Y)in zip(o,o[::-1]))or any(gcd(x-X,y-Y)>1for(x,y),(X,Y)in s)+any((len({*u,*v})>3)*intersection(S(*u),S(*v))for u,v in Q(s,s)))<1:a.add(min(I(D(H(V(x)))for x in o)for H,V,D in Q((lambda p:(w-1-p[0],p[1]),I),(lambda p:(p[0],h-1-p[1]),I),(lambda p:p[::-1],I))))
 return~-len(a)

Try it online!

Ungolfed, with comments

from math import*
from sympy import*
from itertools import*
def pass_point(p1,p2): # test if the segment passes through another point
 return gcd(p1[0]-p2[0],p1[1]-p2[1]) > 1
def f(w,h):
 pts = [(i,j) for i in range(w) for j in range(h)]
 ans = set()
 for orders in permutations(pts):
  # test if the ordering has 180 degrees rotational symmetry
  if any(x1+x2!=w-1or y1+y2!=h-1for (x1,y1),(x2,y2) in zip(orders, orders[::-1])):continue
  segments = [*zip(orders, orders[1:])]
  # test if a segment passes through another point or two segments intersect
  if any(pass_point(*p)for p in segments)+any(len({*s1,*s2})==4and intersection(Segment(*s1),Segment(*s2))for s1 in segments for s2 in segments):continue
  # take minimum of 8 possible rotations/reflections
  flipH = lambda p:(w-1-p[0],p[1]); flipV = lambda p:(p[0],h-1-p[1]); flipD = lambda p:p[::-1]; nop = lambda p:p
  flipmin = min(tuple(map(lambda o:d(h(v(o))),orders))for h in (flipH,nop)for v in (flipV,nop) for d in (flipD, nop))
  ans.add(flipmin)
 print(len(ans))

Try it online!

SymPy has Geometry module that includes an intersection checker intersection that works for line segment Segment objects. This is much shorter than rolling a hand-written intersection checker based on coordinates. The intersection of two Segments is either an empty array (if they don't intersect) or an array that contains a single object (either Point or Segment, depending on the input).


Pyth
Encoder:
Jf-\'T'jdm@JdjswlJ

Takes two arguments: a dictionary on one line, and the date, in DDMMYYYY form on the next.
Filters out words with apostrophes from the dictionary, then converts the current date into a number with base equal to the dictionary length, and then chooses words from the filtered dictionary with indexes of the digits, and prints them out, space separated.
Today's result:
$ pyth -c "Jf-\'T'jdm@JdjswlJ" <<< '/usr/share/dict/words
30102014'
Annam pals

Future results:
31102014
Antarctica economical

01112014
Abernathy carousels

02112014
Acadia unsnarled

03112014
Actaeon oversimplifying

04112014
Adela dugouts

0511204
Adolph Maude

To decode, run the date through the program and see if the output matches the name given. I'm not going to list any more band names, but from how the program works it should be clear there are no repeats.


Python 2, 503 496 487 485 479 476 bytes

for l in[a+'86'[i<2:1+i%2][::2*('v'in a)-1]+b for i in(0,1,2,3)for a,b in[l.split('~')for l in('~11~'[i<2::2]+'0|Spring ~Vegetable |73~|13~|03~|:3~|Mixed 3~|~7|~27|~17|;4~|;42~|;45~|~Tomato 1|~21|~Chutney |2'+'45~|~20|~:0|~0|Jain ~|Pav Bhaji ~|5~|59~|'[i<3:]+'<~~<'[i%2::2]).split('|')]]+['682:0','69','698']:
 for i in range(13):l=l.replace(chr(48+i),'Masala Onion Schezwan Uttappam Corn Mushroom Paneer Sada Cheese Chilli Mysore Sweet Kerala'.split()[i]+' ')
 print l+'Dosa'

Try it online!

Every dosa is of the form a [Paneer, Cheese] b Dosa

Each dosa is then encoded in a list of tuples of (a,b). There are many dosa where a or b is empty.

For each of these tuples, every combination of Paneerand Cheese is added in between them.

.. '86'[i<2:1+i%2] .. for i in(0,1,2,3) ..

The few special cases which are slightly different are:

Kerala Dosa, Kerala Cheese Dosa vs Paneer Kerala Dosa, Paneer Cheese Kerala Dosa

Kerala is moved from a to b if we have Paneer
.. '<~~<'[i%2::2] .. which gives ['Kerala',''] or ['','Kerala']

Schezwan Corn Mushroom Paneer Cheese Dosa

Corn is inserted if we have Paneer Cheese
.. '4..'[i<3:] ..

Onion Masala Dosa, Onion Paneer Masala Dosa vs Cheese Onion Masala Dosa, Paneer Cheese Onion Masala Dosa

Onion is moved from a to b if we have Cheese
.. '~11~'[i<2::2] .., similar to Kerala above

Pav Bhaji Cheese Paneer Dosa

Paneer and Cheese are swapped if a is Pav Bhaji
.. '86'[i<2:1+i%2][::2*('v'in a)-1] ..

Paneer Cheese Schezwan Mysore Masala,Paneer Chilli,Paneer Chilli Cheese

These are too different to account for, and are just added to the list at the end.
.. +['682:0','69','698']

At the end, the numbers are replaced with the correct words:

0123456789:;< -> Masala Onion Schezwan Uttappam Corn Mushroom Paneer Sada Cheese Chilli Mysore Sweet Kerala


ABAA/ABBB: Generate this recursive 2D pattern

APL (Dyalog Classic), 29 25 bytes

'|-'[{a,⊖⌽⍉~a←⍪⍨⍵}⍣⎕⍉⍪⍳2]

Try it online!

⍳2 is the vector 0 1

⍪ turns it into a 2x1 matrix

⍉ transposes it, so it becomes 1x2

⎕ evaluated input

{ }⍣⎕ apply a function that many times

⍪⍨⍵ concatenate the argument on top of itself - a 2x2 matrix

a← remember as a

~ negate

⍉ transpose

⌽ reverse horizontally

⊖ reverse vertically

a, concatenate with a on the left

'|-'[ ] use the matrix as indices in the string '|-', i.e. turn 0 into | and 1 into -


Hexagony, 166 126 124 bytes

\\;;;;33rr''22DD..));;;;;;oo;;}}eeoo\\@@nn;;;;ee;;;;aass&&;;uuoo;;;;..\\\\;;ttee..pp;;tt;;;;..rr;;''ll..'';;;;..;;}}ff..}}yy

Inserting the implicit no-ops and whitespace, this corresponds to the following source code:

       \ \ ; ; ; ; 3
      3 r r ' ' 2 2 D
     D . . ) ) ; ; ; ;
    ; ; o o ; ; } } e e
   o o \ \ @ @ n n ; ; ;
  ; e e ; ; ; ; a a s s &
 & ; ; u u o o ; ; ; ; . .
  \ \ \ \ ; ; t t e e . .
   p p ; ; t t ; ; ; ; .
    . r r ; ; ' ' l l .
     . ' ' ; ; ; ; . .
      ; ; } } f f . .
       } } y y . . .

I'm sure it's possible to shorten this even more, and maybe even solve it in side-length 6, but it's getting tricky...

How it works

Diagram generated with Timwi's Hexagony Colorer.

The code is completely linear. The \ right at the start redirects the IP into a diagonal, such that we don't need to worry about the doubled characters at all. The coloured paths are executed in the order orange/red, blue/grey, green, purple (when there are two paths of the same colour, the left-hand path is executed first, before wrapping around to the right-hand one).

If we ignore no-ops, mirrors and commands which are overridden by others, the linear code comes down to this:

D;o;&32;}n;o;t;';}r;e;p;e;a;t;';}y;o;u;r;s;e;l;f;');@

Letters in Hexagony just set the current memory edge's value to the letter's character code. ; prints the current memory edge as a character. We use & to reset the memory edge to 0 and print a space with 32;. } moves to a different edge, so that we can remember the 32 for further spaces. The rest of the code just prints letters on the new edge, and occasionally moves back and forth with ';} to print a space. At the end we move to the space edge again with ', increment the value to 33 with ) and print the exclamation mark. @ terminates the program.


JavaScript (Node.js), 80 bytes

a=>{s='';for(i=0;i<a+1;i++)s+=(i%2==0?'yeah':'no')+(i<a?'\nbut\n':'.');return s}

Try it online!


Perl - 85

BEGIN{$d=-<>}$d?s/X /X./g:s/ X/.X/g;s/ /substr($p,$+[0]+$d,1)eq'.'?'.':$&/ge;$p=$_;

EDIT: I totally forgot about the -p flag this needs to be run with. Added 2 to char count.
The flag specified at the first line is 0 for shadows going left and 2 for shadows going right.


Python 3, 226 215 211 209 179 bytes

def f(s):
 S=dict(map(eval,i.split(":"))for i in s.split("\n"));r="";L=[min(S)];i=0
 while L[i:]:a=S[L[i]];L+=set(a)-set(L);r+="%%d:%d,%d\n"%tuple(map(L.index,a))%i;i+=1
 return r

Try it online!


Javascript (E6) 137 160 175 190

Less than 2*Golfscript. Moral victory ...

F=a=>[...a].some((e,p,b)=>(Q=(p,n)=>p>29||b[p]!=b[n]||(b.r|=!b[++n])||(b[p]=b[n+~[1,5,6,7].map(q=>Q(p+q,n)|Q(p-q,n),b[p]=0)]))(p,30)&b.r)

Edit Golfed code reorganization. Again and again

Ungolfed Last version, a bit tricky to follow

F = a =>
  [...a] // input string to array, 30 chars of board then the target word
  .some ( // use some to scan the board, return true when found
      (e,p,b)=> // params to callback: element, position, complete array
      (         // NB array b has no .r property, so use it for return value (it's undefined at start)
        Q = (p,n) =>         // Scan function, p=position in board, n=nth char of target word
          p > 29 ||          // Chaek if going outside the board to the target word
          b[p] != b[n] ||    // if invalid char at current position, return
          (b.r |= !b[++n]) ||  // if at end of target, set r to 1 and return (also increment n )
          (                  // else... (NB next tree lines are coalesced in golfed code)
            b[p] = 0,        // remove current char (to avoid reusing)
            [1,5,6,7].map( q => Q(p+q,n)|Q(p-q,n)), // recursive call for + - 1,5,6,7
            b[p] = b[n-1]    // put current char into array again
          )
      )(p,30) & b.r // initial position 0 in target word is 30 in the array
  )

Ungolfed First version , should be clearer

F = a => (
  b = a.split('\n'),
  w = b.pop(),
  r = 0,
  Q = (p, n) =>
    (r |= !w[n]) ||
    (
      b[p] = 0,
      [1,5,6,7,-1,-5,-6,-7].map( q => b[q+=p]==w[n] && Q(q,n+1)),
      b[p] = w[n-1]
    ),
  b = [...b+''],
  b.map((e, p) => e==w[0] && Q(p,1)),
  r
)

Usage

F("AJNES\nTNFTR\nLSAIL\nUDNEX\nEQGMM\nLIFTS\nDAFTER")

Test

['DAFTER', 'STANDS', 'LIFTS', 'FATE', 'DATING' ,
 'SADDEN','SULTANS', 'EXIST', 'SUEDE', 'QUEST']
.map(w => [w, F("AJNES\nTNFTR\nLSAIL\nUDNEX\nEQGMM\n" +w)])

Output:

[["DAFTER", true], ["STANDS", true], ["LIFTS", true], ["FATE", true], ["DATING", true],
["SADDEN", false], ["SULTANS", false], ["EXIST", false], ["SUEDE", false], ["QUEST", false]]


Python 3 + mozjpeg + /dev/urandom, 720×720: avg. score 102%
Depends on the mozjpeg package, the code assumes it's installed into /usr/local/opt/mozjpeg. (on OS X it's trivial to install, just run brew install mozjpeg)
Also it depends on /dev/urandom special file, it's used for generating random data.
The code simply feeds random data to mozjpeg compressor (in TGA format, because cjpeg understands it and it has very simple header), and lets it create an optimized jpeg file. Quality is set to the maximum because it makes DCT coefficients the least compressable, and it doesn't matter much what algorithm is used to compress uncompressable data.
I checked that the jpeg->lepton->jpeg cycle is lossless — it is true.
import subprocess
from subprocess import PIPE

c_mozjpeg_path = '/usr/local/opt/mozjpeg/bin/cjpeg'
cjpeg_params = '-quality 100 -dc-scan-opt 2 -dct float -targa'
image_size = 720

def write_random_tga_image(w, h, of, rf):
    def wb(value, size):
        of.write(int.to_bytes(value, size, 'little'))

    wb(0, 2)
    wb(3, 1)
    wb(0, 9)
    wb(w, 2)
    wb(h, 2)
    wb(8, 1)
    wb(0, 1)

    data_size = w * h
    while data_size > 0:
        data_size -= of.write(rf.read(data_size))

def main():
    with open('/dev/urandom', 'rb') as rf:
        with open('oops.jpg', 'wb') as f:
            p = subprocess.Popen((c_mozjpeg_path,) + tuple(cjpeg_params.split(' ')), stdin=PIPE, stdout=f)
            write_random_tga_image(image_size, image_size, p.stdin, rf)
            p.communicate()

if __name__ == '__main__':
    main()

Code is not golfed, obviously.
Example image:
Fun fact: generated JPEG file is larger than the source uncompressed TGA image, even though JPEG uses lossy compression.
Fun fact 2: Imgur (the default image hosting for SO) does very bad job at this file — for some reason it recompresses it to lower quality, even though it's less than 1MB. So I used Github to upload the example image.
Fun fact 3: In general, mozjpeg indeed does better JPEG compression while staying compatible with existing JPEG decoders. And it also has tool to losslessly optimize JPEG files, too — jpegtran.


How many countries are in the European Union?

Javascript, 85 83 Bytes
a=d=>d<0?0:d<180?6:d<276?9:d<336?10:d<444?12:d<556?15:d<588?25:d<666?27:d<745?28:27

It takes an input as a float as the months / fractions of months passed since 1958-01-01
(0 for 1958-01-01T00:00:00 and a negative number for any previous date)
(Since number of days from some epoch is allowed, I assume that also a number of months is valid, as well)
Try it Online

80 Bytes
(credits: Arnauld)
a=d=>d<0?0:d<180?6:d<276?9:d<336?10:d<444?12:d<556?15:d<588?25:27+(d>=666&d<745)

Sad to see you go, UK


Brachylog, 145 bytes

p~c[A:B:C],Bl1,A:CcP@pz:cahgB,P:1a~@nw|lL,?:laot:" "rjg:Ljb:sa:?z:cap~c[A:B:C],Bl1,A:Cc@pz:caZ:LmgB,Zl-yM,Z:M:Lz:2az:ca~@nw
bB,?h@u:Bc
b#=,?h@u|h

Try it online!

(Takes half a minute, so be patient.)


Python, 207 bytes

import re
h=lambda x:"a"+str(ord(x))
def g(a,b):
 c,d="",set()
 for e in a:
  c+=["(?P<"+h(e)+">.+)","(?P="+h(e)+")"][e in d]
  d.add(e)
 f=re.search(c,b)
 return f and":".join(f.group(h(e))for e in a)or":("

Call with g(pattern, string)

Uses the re module to do most of the work.


Javascript, 275 279

Not a winner by any means, but this should get things started. Uses a trick with eval() and defining 100 as a "constant" to shave off a few bytes. Ungolfed version below.

function D(){return Math.sqrt((x-n)*(x-n)+(y-m)*(y-m))}
H=100;
n=~~(Math.random()*H);m=~~(Math.random()*H);
P="s=prompt().split(' ')";
eval(P);
x=~~s[0];y=~~s[1];i=0;
while(x!=n||y!=m)
{
    if(i)alert(i>j?"hotter":"colder");
    i=D();
    eval(P);
    x=(x+~~s[0])%H;
    y=(y+~~s[1])%H;
    j=D()
}
alert("correct")

Edit: I fell victim to Javascript's string + number operations, hence why D() wasn't working properly. I also fixed a bug where "hotter" was displayed before "correct". This adds 4 bytes.


Output the first position in your program for each input character

Python2, 55 Bytes

a=" )dfi(+m,nprut.';";print map(('a="'+a).find,input())

Starts with a string that contains all the characters used in the code, and then search the indexes


Matlab 2013, 150 bytes

Here is my attempt in Matlab. Definitely won't be the shortest code, but it's a start.

Warning, this overwrites the original image, so make a copy first.

Golfed Version

function  mi(f,n)
o=imread(f);
s=size(o);
imwrite([imresize(o(:,1:((s(2)-n)/2),:),[s(1),s(2)/2]) imresize(o(:,((s(2)+n)/2):end,:),[s(1),s(2)/2])], f);
end

Ungolfed Code, with improvements for odd image sizes and odd number of columns

function  monitorizeImage( filename, num_columns )

orig = imread(filename);
orig_size = size(orig);

f = factor(orig_size(2));
origsize_iseven = f(1)==2;

f = factor(num_columns);
num_columns_iseven = f(1)==2;

odd_even_size_mismatch = xor(origsize_iseven,num_columns_iseven);

img_resized = imresize(orig,[orig_size(1) orig_size(2)+odd_even_size_mismatch]);

leftimg = img_resized(:,1:((orig_size(2)+odd_even_size_mismatch-num_columns)/2),:);
leftimg = imresize(leftimg,[orig_size(1),floor(orig_size(2)/2)]);
rightimg = img_resized(:,((orig_size(2)-odd_even_size_mismatch+num_columns)/2):end,:);
rightimg = imresize(rightimg,[orig_size(1),floor(orig_size(2)/2)]);

monitorized_image = [leftimg rightimg];
monitorized_image = imresize(monitorized_image,[orig_size(1),orig_size(2)+ ~origsize_iseven]);

[~, ~, ext] = fileparts(filename);

imwrite(monitorized_image,strcat(filename(1:end-length(ext)),'_',num2str(num_columns),ext));

end