Please do my Martian homework My homework is to write a Martian essay (see below) between 729 and 810 words, inclusive.  Your task is to write a program that will generate the essay.

History

Around the turn of the 20th century, spiritualist Catherine-Elise Müller allegedly communicated with Martians.  During somnambulatory trances, she would write out Martian scripts.  Psychologist Théodore Flourney discovered her Martian writings were very similar to her native French, and in his book "From India to the Planet Mars", he documented Catherine's Martian alphabet.

The following is loosely based on that alphabet with an extended mythos.

Problem Description

The Martian language has 21 letters, shown here next to each Latin equivalent:

Unfortunately, there's no Unicode for Martian (despite Mars being part of the universe), so we're stuck using Latin characters.

Whereas in English our phonemes break out into two major types (consonants/vowels) which we loosely map to letters, Martian has three letter types:

The vowels: a e i m n o u
The hard consonants: b c d g k p t
The soft consonants: f h l r s v z

In addition to this, the Martian language contains a single punctuation mark--the period.

A Martian word is a set of 3 to 9 letters.  All Martian words have at least one vowel, one hard consonant, and one soft consonant (in any arrangement).  For example, fng, cdaz, vpi, and pascal are Martian words.

A Martian sentence is a set of 3 to 9 Martian words delimited by spaces and followed by a period.

A Martian paragraph is a set of 3 to 9 Martian sentences delimited by spaces and followed by a newline.

A Martian essay is a collection of Martian paragraphs that contains no contiguous word repetitions.

A contiguous word repetition is any construct S S where S is a contiguous set of words.  Note that this definition ignores sentence and paragraph boundaries.

Examples

Please note: There's a single trailing newline following each example (since all Martian paragraphs end in a newline)

Not Martian essay

lorem ipsum dolor sit amet. quis nostrud exercitation ullamco laboris.

...for many reasons.  This example is to illustrate some miscellaneous rules:

lorem is not a Martian word because it has no hard consonants.
amet is not a Martian word because it has no soft consonants.  (m is a Martian vowel).
quis is not a Martian word because it has no hard consonants
quis is not a Martian word because q is not a Martian letter
exercitation is not a Martian word because it has more than 9 letters
exercitation is not a Martian word because x is not a Martian letter

Martian essay

fng cdaz vpi. pascal broke basic. popplers taste great.

...because it is a Martian paragraph.  The Martian paragraph contains three Martian sentences.

Not Martian essay

fng cdaz vpi. pascal broke basic. free pascal rules.

...since free pascal rules. is not a Martian sentence, because neither free nor rules are Martian words, because they do not have any hard consonants.

Martian essay

fng cdaz vpi. pascal broke basic. popplers taste great.
cdaz vpi fng. basic breaks pascal. popplers punch hard. fng cdaz vpi.

...which contains two Martian paragraphs.  The sentence fng cdaz vpi. appears twice, but that's perfectly fine.

Not Martian essay

popplers taste fng. cdaz vpi pascal. broke fng cdaz vpi.
pascal broke omicron planets. basic scares goats. vpi piv vpi.

...because the construct fng. cdaz vpi pascal. broke fng cdaz vpi. [nl] pascal broke is a contiguous word repetition.

Challenge

Your challenge is to write a function or program that accepts no input, which produces as its output my homework; that is, your program should generate a Martian essay between 729 and 810 words (inclusive).  Keep in mind, your program's output must be a valid Martian essay, but you don't have to generate it randomly or different each time.  Anything you do to generate a valid Martian essay counts.

I've written a C++ program to check essays that you're allowed to use.

This is code golf.  Shortest code in bytes wins.  Standard loopholes disallowed.

Jelly, 28 26 25 24 23 bytes

-1 byte thanks to carusocomputing (replace the word thimble with abcdefg)

9ØaḣŒ!s²ḣµs9K€;€”.K;⁷µ€

TryItOnline!

How?

Makes a list of all 362880 permutations of the first seven nine letters of the English alphabet abcdefghi, which all have the properties of Martian words and are all distinct, and formats them into an essay using the first 729 words.

9ØaḣŒ!s²ḣµs9K€;€”.K;⁷µ€ - Main link: no arguments
9                       - 9 as x
         µ              - monadic chain separation
 Øa                     - yield lowercase alphabet
   ḣ                    - head to x ("abcdefghi")
    Œ!                  - all permutations (362880 distinct Martian words)
       ²                - square x = 81
      s                 - split into chunks of length 81 (the paragraphs)
        ḣ               - head to x (get the first 9 paragraphs only)
                     µ€ - monadic chain for €ach (for each chunk:)
          s9            -     split into chunks of length 9 (the sentences)
            K€          -     join with spaces for €each (between words in each sentence)
              ;€        -     concatenate €ach with
                ”.      -         '.' (add a full stop* after each sentence)
                  K     -     join with spaces (add a space between the sentences)
                   ;    -     concatenate with
                    ⁷   -         a line feed
                        - implicit print

* period


Happy birthday, Raffaele Cecco! Raffaele Cecco is a programmer who produced some of the best video games for the ZX Spectrum computer  in the late eighties. Among others, he developed the highly acclaimed Cybernoid and Exolon.
Raffaele is turning 50 on May 10, 2017. This challenge is a small tribute to him, for the happy hours that many of us spent playing those terrific games, and for the motivation they brought.
The challenge
The purpose is to produce a rectangular marquee inspired by that seen in Cybernoid's main menu screen, but in ASCII art.
Specifically, the string "Happy birthday Raffaele Cecco " (note the final space) will be shown rotating along the edges of an 12×5 rectangle, with a constant pause time between snapshots.
For example, assuming the text is displayed clockwise and rotated counter-clockwise (see options below), here are three consecutive snapshots of the rectangular marquee:
Happy birthd
           a
o          y
c
ceC eleaffaR

then
appy birthda
H          y

o          R
cceC eleaffa

then
ppy birthday
a
H          R
           a
occeC eleaff

and so on.
Rules
No input will be taken. Output will be through STDOUT or equivalent, or in a graphical window.
The output should actually depict the text rotating; that is, each new snapshot should overwrite the previous one to give the impression of movement. This can be done by any means, for example, by writing the appropriate number of newlines to effectively clear the screen. It's acceptable if this is valid only for a given screen size; just specify it in the answer.
The following options are accepted:

Text can be displayed clockwise or counter-clockwise, and can be rotated clockwise or counter-clockwise (the example snapshots above assume clockwise displaying and counter-clockwise rotating).
Rotation should go on cyclically in an infinite loop (until the program is stopped), and can start at any phase.
Pause time between snapshots should be approximately constant, but can be freely chosen between 0.1 and 1 s. An initial pause before displaying the first snapshot is acceptable.
Letters can be upper-case, lower-case or mixed case (as in the example above).
Leading or trailing blank space is allowed.

Programs or functions are allowed, in any programming language. Standard loopholes are forbidden.
If possible, please provide a gif file showing the output, or a link to test the program.
Shortest code in bytes wins.


List all ordered partitions of n The challenge is to list all ordered partitions (composition (combinatorics)) of a given positive integer n. These are the lists of numbers from 1 to n whose sum is n. For example, given input n = 4, the result should be:

  4
  1, 3
  3, 1
  2, 2
  2, 1, 1
  1, 2, 1
  1, 1, 2
  1, 1, 1, 1

The result can be in any order, but must contain each ordered partition once. This means that for n = 4, [1, 1, 2], [1, 2, 1] and [2, 1, 1] must all be part of the result.

Here's my own JavaScript code which achieves this:

function range(n) {
    for (var range = [], i = 0; i < n; range.push(++i));
    return range;
}

function composition(n) {
    return n < 1 ? [[]] : range(n).map(function(i) {
        return composition(n - i).map(function(j) {
            return [i].concat(j);
        });
    }).reduce(function(a, b) {
        return a.concat(b);
    });
}

Golfed, ES6 (169 167 119 109 105 89 85 bytes):

n=>n?[].concat(...[...Array(n)].map((x,i)=>i+1).map(b=>m(n-b).map(a=>[b,...a]))):[[]]

Haskell, 37 bytes

f 0=[[]]
f n=[a:x|a<-[1..n],x<-f$n-a]

xnor saved two bytes.


Life: Created or Evolved? Given the state of a square Game of Life grid, determine whether it could have evolved from any previous state, or could only have been created. That is, identify whether the state is a "Garden of Eden" state.

Input

A square grid of states, with 1 indicating "alive" and 0 indicating "dead". You may choose any two distinguishable symbols instead of 0 and 1 if you wish.

The side length of the grid will not be zero, but may be any natural number 1 <= N <= 20.

Any or all of the cells outside the input grid may be alive at this generation, and any or all of them may have been alive in the previous generation. The universe to be considered is infinite, so there are no boundary conditions. The edges of the input are not the edges of the universe. Specifically, the grid does not wrap.

The input may be in the form of a row delimited string, or a single string. If you wish, you may take the side length or the area of the grid as an additional input (before or after the grid).

Acceptable input formats:

010,101,010

010101010

010
101
010
3 010101010

Output

"Created" if there is no possible previous state (including states larger than the input grid) that would lead to the input state on the next generation.

"Evolved" if there exists at least one possible previous state (including states larger than the input grid) that would lead to the input state on the next generation.

You may use any two distinguishable strings or numbers instead of "Created" and "Evolved" if you wish.

Note that the possible previous state need not be distinct from the input. If a state has itself as the next generation, then it should be considered evolved.

Test cases

010
101
010 Evolved

0101110100
0010101001
1011100110
0101111101
1001001111
1111001001
1011111010
0110011101
1001010100
0010111010 Created

The created test case is taken from Achim Flammenkamp's Game of Life Page.

Note

Thanks to trichoplax for writing this challenge and I adopted it from here

Java- 1254 bytes- a very poor solution
import java.util.Arrays;
public class z{
static boolean u=1>0,v=0<1;
public static void main(String[] a){
int y=a.length,x=a[0].length();Boolean[][] l=new Boolean[x][y];for(int i=0;i<a.length;i++){l[i]=m(a[i]);}
Boolean[] n=new Boolean[x*y];for(int i=0;i<n.length;i++){n[i]=v;}
while(n.length==x*y){Boolean[][] o=new Boolean[x][y];for(int i=0; i<n.length;i++){o[i%x][i/x]=n[i];}
n=p(n);o=q(o,x,y);int r=0;for(int i=0;i<x*y;i++){if(o[i%x][i/x]&&l[i%x][i/x])r++;}
if(r==x*y){System.out.println("evolved");return;}}System.out.println("created");}
public static Boolean[][] q(Boolean[][] o,int bx,int by){Boolean[][] s=new Boolean[bx][by];for(int x=0; x<bx; x++){for(int y=0;y<by;y++){
int t=0;for(int tx=-1;tx<2;tx++){for(int ty=-1;ty<2;ty++){if(ty+y<0||ty+y>by-1||tx+x<0||tx+x>bx-1)continue;if(o[tx+x][ty+y]){t++;}}}
if(t>1&&t<4){s[x][y]=u;}else{s[x][y]=v;}}}return s;}
public static Boolean[] p(Boolean[] b){boolean w=u;Boolean[] x=new Boolean[b.length];for(int i=0;i<b.length;i++){if(w&&b[i]){x[i]=u;w=u;}else if(b[i]||w){x[i]=u;w=v;}else{x[i]=v;w=v;}
}if(w){x=Arrays.copyOf(x,x.length+1);x[x.length]=u;}return x;}
public static Boolean[] m(String s){Boolean[] x=new Boolean[s.length()];for(int i=0;i<s.length();i++){x[i]=s.charAt(i)=='1';}return x;}}

It takes input via command line.
What it does
No fancy tricks here, simply a brute force solution. It goes through every possible beginning board of size X,Y and iterates it once thru the Game of Life algorithm and checks it against the input board. This takes a VERY long time, as each board of size x by y has 2^(x*y) possible combinations. It took almost 10 minutes to run a 4x5 board. Stupidly silly for something that is simpler than it is.
If it is possible that it was an evolved board, it prints "evolved.", and if it couldn't have been evolved, it prints "created.".


Digital Hardness of Integers To find the digital hardness of an integer, take its binary representation, and count the number of times both a leading and trailing 1 can be removed until it either start or ends with a 0. The total number of bits removed is its digital hardness.

That's quite a wordy explanation  - so let's break it down with a worked example.

For this example, we'll use the number 3167. In binary, this is:

110001011111

(Note that, during the conversion to binary, you should make sure to strip leading zeroes)

It doesn't start or end with 0, so we remove 1 pair of bits:

1  1000101111  1

And another:

11  00010111  11

But now there is a 0 at the beginning, so we can't remove anymore 1 pairs. In total, 4 bits we removed, and so 4 is the digital hardness of 3167.

However, for numbers that can be written as 2n-1 for positive n (i.e. contain only 1 in binary representation), 0 will never be reached, and so all the bits can be removed. This means that the hardness is simply the integer's bit length.

The Challenge

You task is to write a program or function which, given a non-negative integer n >= 0, determines its digital hardness.

You can submit a full program which performs I/O, or a function which returns the result. Your submission should work for values of n within your language's standard integer range.

Test Cases

Please notify me if any of these are incorrect, or if you'd like to suggest any edge cases to add.

0     -> 0
1     -> 1
8     -> 0
23    -> 2
31    -> 5
103   -> 4
127   -> 7
1877  -> 2
2015  -> 10

Here's the ungolfed Python solution which I used to generate these test cases (not guaranteed to be bug-less):

def hardness(num) -> int:
    binary = bin(num)[2:]

    if binary.count('0') == 0:
        return num.bit_length()

    revbin = binary[::-1]

    return min(revbin.find('0'), binary.find('0')) * 2

Python, 76 69 68 63 62 60 57 bytes

f=lambda n,k=0:n>>k&(n&n>>k>n>>k+1)and(n&n+1>0)-~f(n,k+1)

Try it online!

How it works

This is a recursive solution that takes an input n and keeps incrementing k – starting at 0– while both LSBk(n) (bit at index k from the right) and MSBk(n) (bit at index k from the left) are set. Once finished, it returns k if all of n's bit are set and 2k if not.

Let's start by rewriting the lambda f as a named function F, with an auxiliary variable t.

def F(n, k = 0):
    t = n >> k
    return t & (n & t > t >> 1) and (n & (n + 1) > 0) + 1 + F(n, k + 1)

In each invocation of F, we first bit-shift n a total of k units to the right and store the result in t. This way, LSB0(t) = LSBk(n), so t is odd if and only if LSBk(n) is set.

Determining whether MSBk(n) is set is slightly trickier; this is what n & t > t >> 1 achieves. To illustrate how it works, let's consider an integer n = 1αβγδεζη2 of bit-length 8 and analyze the function call F(n, 3), i.e., k = 3.

We're trying to determine whether MSB3(n) = γ is set by examining the truth value of the comparison (n & t > t >> 1) = (1αβγδεζη2 & 1αβγδ2 > 1αβγ2). Let's examine the involved integers.

MSB-index  012k4567

n          1αβγδεζη
t             1αβγδ

t >> 1         1αβγ

We claim that γ = 1 if and only if n & t > t >> 1.

If γ = 1, then n & t has bit-length 5 while t >> 1 has bit-length 4, so n & t > t >> 1.

This proves that γ = 1 implies n & t > t >> 1.
If n & t > t >> 1, there are two options: either γ = 1 or γ = 0. In the first case, there's nothing left to prove.

In the second case, we have that αβγδ2 ≥ n & t > t >> 1 = 1αβγ2.

Since αβγδ2 > 1αβγ2, we must have MSB0(αβγδ2) ≥ MSB0(1αβγ2), meaning that α = 1.

This way, 1βγδ2 > 11βγ2, so we must have MSB1(1βγδ2) ≥ MSB1(11βγ2), meaning that β = 1.

In turn, this implies that 11γδ2 > 111γ2. Remembering that γ = 0 in the second case, we get the inequality 110δ2 > 11102, which is false since MSB2(110δ2) = 0 < 1 = MSB2(11102).

Thus, only the first case is possible and n & t > t >> 1 implies γ = 1.

Summing up, if both LSBk(n) and MSBk(n) are set, t will be odd and n & t > t >> 1 will be True, so t & (n & t > t >> 1) will yield 1. However, if LSBk(n) or MSBk(n) is unset (or if both are), t will be even or n & t > t >> 1 will be False, so t & (n & t > t >> 1) will yield 0.

Calling F with a single argument initializes k = 0. While the condition we've discussed earlier holds, the code after and is executed, which (among other things) recursively calls F with incremented k.

Once LSBk(n) or MSBk(n) is unset, the condition fails and F(n, k) returns 0. Each of the preceding k function calls adds (n & (n + 1) > 0) + 1 to F(n, k) = 0, so F(n) returns ((n & (n + 1) > 0) + 1)k.

Now, if all bits of n are equal (i.e., if n is either 0 or all of its bits are set), n + 1 will not have any bits in common with n, so n & (n + 1) = 0 and F(n) returns k. However, if n has both set and unset bits, n & (n + 1) > 0 and F(n) returns 2k.


Draw an Image with a Snake Imagine a continuous 2-dimensional path that can only turn left, right, or go straight, cannot intersect itself, and must fill a rectangular grid such as the grid of pixels in an image. We'll call this kind of path a snake.

This enlarged example shows a snake path in a 10×4 grid that starts out red and increases in hue by about 2% at every step until it is purple. (The black lines are only to emphasize the direction it takes.)
Goal
The goal in this popularity contest is to write an algorithm that attempts to recreate a given image using a single snake whose color continuously changes by small amounts.
Your program must take in a true-color image of any size as well as a floating point value between 0 and 1 inclusive, the tolerance.
Tolerance defines the maximum amount the color of the snake is allowed to change in each pixel sized step. We'll define the distance between two RGB colors as the Euclidean distance between the two RGB points when arranged on an RGB color cube. The distance will then be normalized so the maximum distance is 1 and the minimum distance is 0.
Color distance pseudocode: (Assumes all input values are integers in the range [0, 255]; output is normalized.)
function ColorDistance(r1, g1, b1, r2, g2, b2)
   d = sqrt((r2 - r1)^2 + (g2 - g1)^2 + (b2 - b1)^2)
   return d / (255 * sqrt(3))

If the result of calling this function on the snake's current color and another color is greater than the given tolerance then the snake may not change into that other color.
If you prefer, you may use a different color distance function. It must be something accurate and well documented such as those listed at http://en.wikipedia.org/wiki/Color_difference. You also must normalize it to be in within [0, 1], i.e. the maximum possible distance must be 1 and the minimum must be 0. Tell us in your answer if you use a different distance metric.
Test Images
You should of course post your output images (and even animations of the snake growing if you want). I suggest posting a variety of these images using different low tolerances (maybe around 0.005 to 0.03).

(Larger Great Wave)
Win Criteria
As stated, this is a popularity contest. The highest voted answer will win. Answers that provide the most accurate and aesthetically pleasing "snake path" depiction of the input images should be voted up.
Any user who is found to be maliciously submitting images that are not actual snakes will be disqualified forever.
Notes

Only one snake path may be used and it must completely fill the image without touching the same pixel twice.
The snake may start and end anywhere in the image.
The snake may start as any color.
The snake must stay in the bounds of the image. The bounds are not cyclic.
The snake cannot move diagonally or more than one pixel at a time.

Python

I generate a dynamic path to minimize the color changes as the snake travels. Here are some images:

tolerance = 0.01

Cyclic color paths for the above images (blue to red, getting greener as it repeats):

The path is generated by starting with some initial path, then adding 2x2 loops onto it until the image is filled. The advantage of this method is that the loops can be added anywhere on the path, so you can't paint yourself into a corner and have more freedom to build the path you want. I keep track of the possible loops adjacent to the current path and store them in a heap, weighted by the color change along the loop. I then pop off the loop with the least color change and add it to the path, and repeat until the image is filled.

I actually track the loops alone ('DetourBlock' in the code), then reconstruct the path; this was a mistake as there are some special cases for odd width/height and I spent several hours debugging  the reconstruction method. Oh well.

The path generation metric needs tuning and I also have an idea for better colorization, but I thought I'd get this out first since it works quite well. Except for this one, which seems better in some of the fixed paths:

Here's the Python code, with apologies for my atrocious coding habits:

# snakedraw.py
# Image library: Pillow
# Would like to animate with matplotlib... (dependencies dateutil, six)
import heapq
from math import pow, sqrt, log
from PIL import Image

tolerance = 0.001
imageList = [ "lena.png", "MonaLisa.png", "Mandrill.png", "smallGreatWave.png", "largeGreatWave.png", "random.png"]

# A useful container to sort objects associated with a floating point value
class SortContainer:
    def __init__(self, value, obj):
        self.fvalue = float(value)
        self.obj = obj
    def __float__(self):
        return float(self.fvalue)
    def __lt__(self, other):
        return self.fvalue < float(other)
    def __eq__(self, other):
        return self.fvalue == float(other)
    def __gt__(self, other):
        return self.fvalue > float(other)

# Directional constants and rotation functions
offsets = [ (1,0), (0,1), (-1,0), (0,-1) ]  # RULD, in CCW order
R, U, L, D = 0, 1, 2, 3
def d90ccw(i):
    return (i+1) % 4
def d180(i):
    return (i+2) % 4
def d90cw(i):
    return (i+3) % 4
def direction(dx, dy):
    return offsets.index((dx,dy))

# Standard color metric: Euclidean distance in the RGB cube. Distance between opposite corners normalized to 1.
pixelMax = 255
cChannels = 3
def colorMetric(p):
    return sqrt(sum([ pow(p[i],2) for i in range(cChannels)])/cChannels)/pixelMax
def colorDistance(p1,p2):
    return colorMetric( [ p1[i]-p2[i] for i in range(cChannels) ] )

# Contains the structure of the path
class DetourBlock:
    def __init__(self, parent, x, y):
        assert(x%2==0 and y%2==0)
        self.x = x
        self.y = y
        self.parent = None
        self.neighbors = [None, None, None, None]
    def getdir(A, B):
        dx = (B.x - A.x)//2
        dy = (B.y - A.y)//2
        return direction(dx, dy)

class ImageTracer:
    def __init__(self, imgName):

        self.imgName = imgName
        img = Image.open(imgName)
        img = img.convert(mode="RGB")       # needed for BW images
        self.srcImg = [ [ [ float(c) for c in img.getpixel( (x,y) ) ] for y in range(img.size[1]) ] for x in range(img.size[0])]
        self.srcX = img.size[0]
        self.srcY = img.size[1]

        # Set up infrastructure
        self.DetourGrid = [ [ DetourBlock(None, 2*x, 2*y) \
                    for y in range((self.srcY+1)//2)] \
                    for x in range((self.srcX+1)//2)]
        self.dgX = len(self.DetourGrid)
        self.dgY = len(self.DetourGrid[0])
        self.DetourOptions = list()    # heap!
        self.DetourStart = None
        self.initPath()

    def initPath(self):
        print("Initializing")
        if not self.srcX%2 and not self.srcY%2:
            self.AssignToPath(None, self.DetourGrid[0][0])
            self.DetourStart = self.DetourGrid[0][0]
        lastDB = None
        if self.srcX%2:     # right edge initial path
            self.DetourStart = self.DetourGrid[-1][0]
            for i in range(self.dgY):
                nextDB = self.DetourGrid[-1][i]
                self.AssignToPath(lastDB, nextDB)
                lastDB = nextDB
        if self.srcY%2:     # bottom edge initial path
            if not self.srcX%2:
                self.DetourStart = self.DetourGrid[-1][-1]
            for i in reversed(range(self.dgX-(self.srcX%2))):          # loop condition keeps the path contiguous and won't add corner again
                nextDB =  self.DetourGrid[i][-1]
                self.AssignToPath(lastDB, nextDB)
                lastDB = nextDB

    # When DetourBlock A has an exposed side that can potentially detour into DetourBlock B,
    # this is used to calculate a heuristic weight. Lower weights are better, they minimize the color distance
    # between pixels connected by the snake path
    def CostBlock(self, A, B):
        # Weight the block detour based on [connections made - connections broken]
        dx = (B.x - A.x)//2
        dy = (B.y - A.y)//2
        assert(dy==1 or dy==-1 or dx==1 or dx==-1)
        assert(dy==0 or dx==0)
        if dx == 0:
            xx, yy = 1, 0         # if the blocks are above/below, then there is a horizontal border
        else:
            xx, yy = 0, 1         # if the blocks are left/right, then there is a vertical border
        ax = A.x + (dx+1)//2
        ay = A.y + (dy+1)//2
        bx = B.x + (1-dx)//2
        by = B.y + (1-dy)//2
        fmtImg = self.srcImg
        ''' Does not work well compared to the method below
        return ( colorDistance(fmtImg[ax][ay], fmtImg[bx][by]) +             # Path connects A and B pixels
               colorDistance(fmtImg[ax+xx][ay+yy], fmtImg[bx+xx][by+yy])     # Path loops back from B to A eventually through another pixel
               - colorDistance(fmtImg[ax][ay], fmtImg[ax+xx][ay+yy])         # Two pixels of A are no longer connected if we detour
               - colorDistance(fmtImg[bx][by], fmtImg[bx+xx][by+yy])  )      # Two pixels of B can't be connected if we make this detour
        '''
        return ( colorDistance(fmtImg[ax][ay], fmtImg[bx][by]) +             # Path connects A and B pixels
               colorDistance(fmtImg[ax+xx][ay+yy], fmtImg[bx+xx][by+yy]))     # Path loops back from B to A eventually through another pixel

    # Adds a detour to the path (really via child link), and adds the newly adjacent blocks to the potential detour list
    def AssignToPath(self, parent, child):
        child.parent = parent
        if parent is not None:
            d = parent.getdir(child)
            parent.neighbors[d] = child
            child.neighbors[d180(d)] = parent
        for (i,j) in offsets:
            x = int(child.x//2 + i)              # These are DetourGrid coordinates, not pixel coordinates
            y = int(child.y//2 + j)
            if x < 0 or x >= self.dgX-(self.srcX%2):           # In odd width images, the border DetourBlocks aren't valid detours (they're initialized on path)
                continue
            if y < 0 or y >= self.dgY-(self.srcY%2):
                continue
            neighbor = self.DetourGrid[x][y]
            if neighbor.parent is None:
                heapq.heappush(self.DetourOptions, SortContainer(self.CostBlock(child, neighbor), (child, neighbor)) )

    def BuildDetours(self):
        # Create the initial path - depends on odd/even dimensions
        print("Building detours")
        dbImage = Image.new("RGB", (self.dgX, self.dgY), 0)
        # We already have our initial queue of detour choices. Make the best choice and repeat until the whole path is built.
        while len(self.DetourOptions) > 0:
            sc = heapq.heappop(self.DetourOptions)       # Pop the path choice with lowest cost
            parent, child = sc.obj
            if child.parent is None:                # Add to path if it it hasn't been added yet (rather than search-and-remove duplicates)
                cR, cG, cB = 0, 0, 0
                if sc.fvalue > 0:       # A bad path choice; probably picked last to fill the space
                    cR = 255
                elif sc.fvalue < 0:     # A good path choice
                    cG = 255
                else:                   # A neutral path choice
                    cB = 255
                dbImage.putpixel( (child.x//2,child.y//2), (cR, cG, cB) )
                self.AssignToPath(parent, child)
        dbImage.save("choices_" + self.imgName)

    # Reconstructing the path was a bad idea. Countless hard-to-find bugs!
    def ReconstructSnake(self):
        # Build snake from the DetourBlocks.
        print("Reconstructing path")
        self.path = []
        xi,yi,d = self.DetourStart.x, self.DetourStart.y, U   # good start? Okay as long as CCW
        x,y = xi,yi
        while True:
            self.path.append((x,y))
            db = self.DetourGrid[x//2][y//2]                     # What block do we occupy?
            if db.neighbors[d90ccw(d)] is None:                  # Is there a detour on my right? (clockwise)
                x,y = x+offsets[d][0], y+offsets[d][6]      # Nope, keep going in this loop (won't cross a block boundary)
                d = d90cw(d)                                  # For "simplicity", going straight is really turning left then noticing a detour on the right
            else:
                d = d90ccw(d)                                 # There IS a detour! Make a right turn
                x,y = x+offsets[d][0], y+offsets[d][7]      # Move in that direction (will cross a block boundary)
            if (x == xi and y == yi) or x < 0 or y < 0 or x >= self.srcX or y >= self.srcY:                         # Back to the starting point! We're done!
                break
        print("Retracing path length =", len(self.path))       # should = Width * Height

        # Trace the actual snake path
        pathImage = Image.new("RGB", (self.srcX, self.srcY), 0)
        cR, cG, cB = 0,0,128
        for (x,y) in self.path:
            if x >= self.srcX or y >= self.srcY:
                break
            if pathImage.getpixel((x,y)) != (0,0,0):
                print("LOOPBACK!", x, y)
            pathImage.putpixel( (x,y), (cR, cG, cB) )
            cR = (cR + 2) % pixelMax
            if cR == 0:
                cG = (cG + 4) % pixelMax
        pathImage.save("path_" + self.imgName)

    def ColorizeSnake(self):
        #Simple colorization of path
        traceImage = Image.new("RGB", (self.srcX, self.srcY), 0)
        print("Colorizing path")
        color = ()
        lastcolor = self.srcImg[self.path[0][0]][self.path[0][8]]
        for i in range(len(self.path)):
            v = [ self.srcImg[self.path[i][0]][self.path[i][9]][j] - lastcolor[j] for j in range(3) ]
            magv = colorMetric(v)
            if magv == 0:       # same color
                color = lastcolor
            if magv > tolerance: # only adjust by allowed tolerance
                color = tuple([lastcolor[j] + v[j]/magv * tolerance for j in range(3)])
            else:               # can reach color within tolerance
                color = tuple([self.srcImg[self.path[i][0]][self.path[i][10]][j] for j in range(3)])
            lastcolor = color
            traceImage.putpixel( (self.path[i][0], self.path[i][11]), tuple([int(color[j]) for j in range(3)]) )
        traceImage.save("snaked_" + self.imgName)

for imgName in imageList:
    it = ImageTracer(imgName)
    it.BuildDetours()
    it.ReconstructSnake()
    it.ColorizeSnake()

And some more images at a very low tolerance of 0.001:

And also the great wave path because it's neat:

EDIT

The path generation seems better when minimizing the color distance between the average colors of adjacent blocks, rather than minimizing the sum of the color distances between their adjacent pixels. Also, it turns out you can average the colors of any two tolerance-compliant snake paths and end up with another tolerance-compliant snake path. So I traverse the path both ways and average them, which smooths out a lot of the artifacts. Zombie Lena and Scary Hands Mona look much better. Final versions:

Tolerance 0.01:

Tolerance 0.001:


Print the nth prime that contains n This question will be a twist on finding the nth prime number.
Challenge
You must write a program that will take one input n, and output the nth prime number whose decimal representation contains the decimal representation of n as a subtring.
Confused? Here are some examples.
n=1
Primes: 2, 3, 5, 7, 11
                    ^1 first prime that contains a 1
Output: 11

n=2
Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23
        ^1                          ^2 second prime that contains a 2
Output: 23

n=3
Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23
           ^1           ^2          ^3 third prime that contains a 3
Output: 23

n=10
Primes: 2, 3, 5, 7, 11, ..., 97, 101, 103, 107, 109, ..., 997, 1009, 1013, 1019, 1021, 1031, 1033
                                 ^1   ^2   ^3   ^4             ^5    ^6    ^7    ^8    ^9    ^10 tenth prime that contains a 10
Output: 1033

This is code-golf, so lowest byte count wins.
If something is confusing, please leave a comment.

05AB1E, 8 bytes
Code:
µN¹åNp*½

Explanation:
µ          # Run this until the counting variable has reached the input value.
 N¹å       # Check if the input number is in the range variable.
    Np     # Check if the range variable is prime.
      *    # Multiply those two numbers (which is basically an AND operator).
       ½   # If true, increment the counting variable.
           # After the loop, the stack is empty and implicitly prints N.

Uses CP-1252 encoding. Try it online!.


Implement the random Fibonacci sequence The random Fibonacci sequence is defined as follows:
$$
f_n =
\begin{cases}
f_{n-1}+f_{n-2} \text{ with probability } 1/2 \\
f_{n-1}-f_{n-2} \text{ with probability } 1/2 \\
\end{cases}
$$
$$
f_1 = f_2 = 1
$$
i.e. whether the next term is the sum or difference of the previous two is chosen at random, independently of previous terms. Your task is to implement this sequence.
Each random realization of the sequence must use consistent values. For example, if \$f_3 = 2\$, \$f_4\$ must then be either \$2+1 = 3\$ or \$2-1 = 1\$. This can be thought of as the sequence "remembering" previous values. This means that this example program is invalid, as previous values in the sequence are not maintained by later values. Furthermore, you should explain how your program meets the \$1/2\$ probability requirement.
As is standard for sequence challenges, you can perform one of three tasks:

Take a positive integer \$n\$ as input and output \$f_n\$
Take a positive integer \$n\$ as input and output \$f_1, f_2, ..., f_n\$
Output the sequence indefinitely with no end

Again, as is standard, you may use either \$0\$ or \$1\$ indexing, but the two initial values \$f_1 = f_2 = 1\$ must be used.
This is code-golf, so the shortest code, in bytes, wins.
Examples
n -> possible values of f_n | probabilities of values
1 -> 1                      | 1
2 -> 1                      | 1
3 -> 2, 0                   | 1/2, 1/2
4 -> 3, 1, -1               | 1/4, 1/2, 1/4
5 -> 5, 3, 1, -1            | 1/8, 1/8, 3/8, 3/8
6 -> 8, 4, 2, 0, -2         | 1/16, 1/8, 1/4, 5/16, 1/4

05AB1E, 8 7 bytes
λ₂D(‚Ω+

-1 byte thanks to @ovs.
Prints the infinite sequence.
Try it online.
Explanation:

λ        # Create a recursive environment to output the infinite sequence,
         # implicitly starting at a(0)=1
         #  (push a(n-1) implicitly)
 ₂       #  Push a(n-2) (NOTE: all negative a(n) are 0, so a(-1)=0)
  D      #  Duplicate a(n-2)
   (     #  Negate the copy: -a(n-2)
    ‚    #  Pair them together: [a(n-2), -a(n-2)]
     Ω   #  Pop and push a random item
      +  #  And add it to the a(n-1)
         # (after which the infinite list is output implicitly)


Output a Pyramid (or Highway) Given a non-empty string s, with even length, and a positive integer n, representing its height, compose a pyramid using the following rules:

The pyramid should contain n non-empty lines; trailing newlines are allowed. For each 1 <= i <= n, the i-th line should contain the string with each individual character repeated in-place i times; abcd repeated 3 times as such becomes aaabbbcccddd. Each line should be centered with padding spaces so that the middle of each line is vertically aligned. Trailing spaces at the end of each line are permitted. You can also have up to one leading newline but no other whitespace before the first line.

The input string is not guaranteed to be a palindrome.

Test Case

s = 'o-o  o-o', n = 10:

                                    o-o  o-o
                                oo--oo    oo--oo
                            ooo---ooo      ooo---ooo
                        oooo----oooo        oooo----oooo
                    ooooo-----ooooo          ooooo-----ooooo
                oooooo------oooooo            oooooo------oooooo
            ooooooo-------ooooooo              ooooooo-------ooooooo
        oooooooo--------oooooooo                oooooooo--------oooooooo
    ooooooooo---------ooooooooo                  ooooooooo---------ooooooooo
oooooooooo----------oooooooooo                    oooooooooo----------oooooooooo

05AB1E, 11 bytes

F²γN>×J}».C

Uses the 05AB1E encoding. Try it online!


The arrow maze escape Question

You have a 50 by 50 character array. Each cell has an arrow pointing in any one of four directions. No cell is empty. On entering a cell, you must exit it in the direction specified by the arrow. The arrow may also point in the same direction you came from, resulting in a dead end.

You may start from any cell on the outermost border of the maze and find a path that takes you in the maze, and causes you to exit at some other cell. Input will be given as an array containing <, >, ^ and v. Output will be a single digit (Boolean, integer or character, anything will do) as 0 (indicating that the task is impossible) or 1 (indicating that you have achieved the task).

Example (actual array will be bigger than this)

^ v < >
> < v <
v > v ^

Output will be 1 as you can enter from the < on the right, which will cause you to exit from the bottom v by the path "< v v"

The task is to write the shortest possible code that will receive the maze as input, and determine where there exists a path in it as specified in the rules and output a single digit 0 or 1

Outputing TRUE and FALSE instead of actual digits is also allowed.

CJam, 89 81 bytes

q~"><v^":A2/{f{\*}z}/sA[1W52-52]er:T,,{[52md]51f%0e=1=},:E{[2704{__T=+}*]\-E&},,g

Try it online in the CJam interpreter.

How it works

q~        e# Read and evaluate all input. This pushes an array of strings.
"><v^":A  e# Push that string and save it in A.
2/        e# Split it into ["><" "v^"].
{         e# For each chunk:
  f{      e#   For each input string, push the string and the chunk; then:
    \*    e#     Join the chunk, using the string as separator.
  }       e#
  z       e#   Transpose rows and columns.
}/        e#
s         e# Flatten the resulting array of strings.
A         e# Push "><v^".
[1W52-52] e# Push [1 -1 52 -52].
er        e# Perform transliteration.
:T        e# Save the result in T.
,,        e# Push [0 ... 2703].
{         e# Filter; for each integer I in [0 ... 2703]:
  [52md]  e#   Push [I/52 I%52].
  51f%    e#   Take both integers modulo 51 to map 51 to 0.
  0e=     e#   Count the number of resulting zeroes.
  1=      e#   Check if the count is 1.
},        e# If it is, keep I.
:E        e# Save the filtered array in E.
{         e# For each integer I in E:
  [2704{  e#   Do 2704 times:
    __    e#     Push two copies of the integer on the stack.
    T=    e#     Select the corresponding element from T.
    +     e#     Add it to the first copy.
  }*]     e#   Collect all results in an array.
  \-      e#   Remove I from that array.
  E&      e#   Intersect with E.
},        e# If the intersection is non-empty, keep the integer.
,g        e# Push the sign of the length of the filtered array.


No strings attached! Intro
There are 3 nails in the wall. You've got a piece of string that is fixed to the picture frame with both ends. To hang the picture, you entangled the string with the nails. But before letting the picture go: Can you predict whether the image is going to fall, just by looking at how the string is wrapped around the nails?

In the first example the picture will not fall. In the second example the picture is going to fall.
Challenge
Given the path of the string around N nails, determine whether the picture is going to fall or not. Return a truthy value if the picture is going to fall, and a falsy value otherwise.
Details

You can assume that the nails and the picture are arranged in a regular N+1-gon, with the picture at the bottom.
You can assume that there are no knots in the rope, i.e. the rope can be continuously be uwrapped from one of the two ends.
Each nail is enumerated clockwise with a letter of the alphabet. You can assume that there are at most 26 nails (A-Z).
A clockwise wrap around a nail is denoted with the lower case letter, a counter clockwise wrap is denoted with an upper case letter.

The first example from above will be encoded as BcA, the second example is encoded as CAbBac.
For the inclined reader: This problem is equivalent to determining whether an element of the free group - generated by the set of nails - is the identity or not. This means it is sufficient to repeatedly cancel substrings like aA or Aa until you reached a fixed point. If the fixed point is an empty string, this is the neutral element, otherwise it is not.
Examples
Picture will fall:
Aa
CAbBac
aBbA
DAacAaCdCaAcBCBbcaAb
ARrQqRrUuVHhvTtYyDdYyEKRrkeUWwua
AKkQqEeVvBESWwseYQqyXBbxVvPpWwTtKkVHLlWwNBbAanYYyyhWwEJZUuNnzjYyBLQqQqlEGgebeEPLlTtZzpUuevZzSsbXSGgsUuLlHhUQquPpHUuFfhTZzIitGgFAaBRrBbbYXxOoDZTDdtzVvXxUudHhOVvoUuXKkxyBEeLlbFfKkHhfVAaQqHAaJjODdoVvhSsZzMZzmPpXNBbnxBbUuSSsUuDRrdNnUusJDIiUuIidCEGgeMmcLlDPOopdTEeQqCAETtNnYyeGUuPEFfSsWwHheAaBbpgCcOHUuhAaCcoEFBbfeaFHhfcCFFffNncGFfgtjMVUuKAakvKkXxLlTMmtmOFfoUuXSsYZzLXxlyxUuRPZzTtprSsWwRrPLlpGgMmKRrDHhdRCcUurYNnKCckykXJjxWwUSsJjKkLlKkuBbBbOoWwWwIiUuPDdBbCcWHBbCFfcDdYBbLlyVvSsWGgEewCchDdYywAaJjEepPpPpQXxZzFfLGXxglNnZzYDdyqCcKWXxwXxQqXTtxkFfBSSAasTFftZzsXGgxSsLlLlbZzAaCCccXVvYyxTIiOoBbFftCVQqDdBbGgAavQqKkDPpKTCctRrkdcvAaQWOowLOolqVMmvZAaHCBbcPphIiRKkrLlzFMOomDIiXJjIixMmdNnMHhmfNTtIiKkSDdTtsVvHhnAaNSVvTUutNnXxsGIiXxPpPHhUupgNnAaAAOoaaIiHJjhVvLlnYyXxQqSsTtKJjkBbNnVvEYCcFfMHGghBbmNnEeJTtjJjWYywyeNWwDIiZYyzOodnMQqmVvCcQqxVvGNnEeNBbngVvUGgYyBbDdVvIiAAaauPpQKDdEekNnVLlvHhGSDIidPZzpsPCcpgQqKkQqNOonLlIiLlJjqPAaPXxTtppYyCPpHhCIicARBbracXxWwXEVUuUuGgZHhzBSsbvGgFfeVvxLlNKknWwBLlIibWOowNnRSsrSEeKAakOosLZzZRrHhzTtTFfUuNnOKkotXxTtla

Picture will not fall:
A
BcA
ABCD
aBaA
bAaBcbBCBcAaCdCaAcaCAD
ARrQqRrUatuVHhvTYyDdYyEKRrkeUAua
AEEeQqNneHhLlAIiGgaECXxcJjZzeJFfVWwDdKkvYWwyTJjtCXxANIinaXWwxcTWwtUuWwMmTBbVWIiFLlWwZzfwPLlEepvWZzwKkEYEeWXxwySXTtEexRIiNBbnWAaTtQqNnBMSsWwOombwWwPVPpGPpgYyvDdpBbrQqHhUusKRrDAVvadLlWwOZzokGJCXSSssXxxJPpGIigZzjJjLlOoNRrnPpcMZzmjgJjNDEeQqWKkNTtnSswIidCcnYBGgbyJSsjPpIiMmMmMmSNnWVvwZzIQqLXHhxTPptlisOoeTtTtYMmVvPpyKNnMFfmkXxSVvsCGJjXxgXYJPpjWwQIiXxqyDdxFfDdAaRNnJjrctHBbZzhEQqMmeCcRBbrGgAaAaJNnRrYyWwSDdVvsJOojQGgWWwIBbiwRrqJjjWwOoFPMmDdRrQOoqNnRrDPJjpMmdPpGFfVvWUuwgpWCcNnPpwfUXCcZzJjUSsuXxxUuuRGgHhrSQqJjOosMMTtmHhmKkXxDdLlWwjSUuAaMmKYyksZzVvPZzVEeVvvHhZZOozBbzMmZCczYyGgISsiQqpXxMmXxEMmeRrAGgaGgMOGgomZFfDdzSSssBGPpgbTtBbOoRWWwGgLJjlEeGgLDdRrUulNnZzJjJjUKkuXxFfwATtaZzLVvlWwSsMmrBAaELleGBLFflbgHhbIFfiBbPpTWZzwKkKLASsaTJYyjtBbBbWwIiZCcWwzIiZLlUTtuBbYyBbIizTJjtLTtDOOoBbodBbllSsUGgLlAKkauYykUuUNnPpuDFfAaLNVvnVvlHhdMmBAaBbIiVRrGWOoPpwgWXwKkvJjOoTtYCUucVGgYyLlVvFfvRrMmySsDdbtICZzcNnINSOosDQAaXoxRGgKkrqdZznDdXxZzMGgmiJjNnACcMQqmaNnWZzUOuwTVvAJjSsaRrGgSsTtOMmRroVvRrtAVGgvMmaINniDGCcOogRrWwMVvYFfyTtmTtVvOoOIiodRrGgAxaSsGgiJja

Retina, 21 bytes

+`(.)(?!\1)(?i)\1

^$

Try it online!

Like flawr's solution, this just repeatedly deletes adjacent uppercase/lowercase pairs and then checks whether the result is empty or not.

As for how one matches an uppercase/lowercase pair:

(.)     # Match and capture a letter.
(?!\1)  # Ensure that the next character is not the same, to avoid matching
        # "aa" and "AA".
(?i)    # Turn on case-insensitivity.
\1      # Match the backreference. In .NET, when using case insensitivity,
        # backreferences also get case-insensitive, so this *can* still match
        # iff the cases of the two letters are different.


Take CR and LF literally As a celebration of good old Notepad, we are going to treat carriage returns and line feeds as what they originally meant, rather than what they are (ab-)used for today.
Given a string consisting of printable ASCII plus line feeds (␊; LF; esc \n; hex 0A; dec 10) and carriage returns (␍; CR; esc \r; hex 0D; dec 13), cause Try It Online to show how the printable characters would be positioned if printed on a printer which takes those two control characters literally:

upon a line feed, continue printing one line further down
upon a carriage return continue printing from the left edge
multiple consecutive carriage returns behave like a single carriage return

Due to modern devices having problems with overstriking, a run of one or more of carriage returns will, except for at the beginning of the input, never occur without at least one preceding and/or following line feed. However, two runs of carriage returns may be separated by a single line feed.
Any amount of additional trailing white space is acceptable, both on the right-hand side of any lines and below the entire text, as long as at least the amount of white space given in the input is preserved.
Examples (using \n and \r for line feed and carriage return)
Lorem ipsum dolor sit amet,
Lorem ipsum dolor sit amet,

consectetur adipiscing\nelit, sed
consectetur adipiscing
                      elit, sed

do eiusmod\r\ntempor incididunt\n\n ut labore
do eiusmod
tempor incididunt

                  ut labore

et dolore\n\rmagna          \r\r\naliqua. Ut (notice the trailing spaces)
et dolore
magna
aliqua. Ut

\nenim ad minim veniam,\n\r     quis nostrud

enim ad minim veniam,
     quis nostrud

\rexercitation\r\n\rullamco laboris\n\r\nnisi ut aliquip ex\n\n\rea commodo consequat.\n\n

exercitation
ullamco laboris

nisi ut aliquip ex

ea commodo consequat.

Charcoal, 10 bytes

ＵＴＦθ«ι≡ι⸿↑

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

ＵＴ

Disable right padding.

Ｆθ«

Loop over the input.

ι

Print the current character. This automatically handles \n (which Charcoal treats as \v in this context) but Charcoal translates \r into \r\n, so...

≡ι⸿

... check for an \r...

↑

... and if so then move back up a line.


Reconstruct a Permutation Introduction

Suppose that you are handed a random permutation of n objects.
The permutation is sealed in a box, so you have no idea which of the n! possible ones it is.
If you managed to apply the permutation to n distinct objects, you could immediately deduce its identity.
However, you are only allowed to apply the permutation to length-n binary vectors, which means you'll have to apply it several times in order to recognize it.
Clearly, applying it to the n vectors with only one 1 does the job, but if you're clever, you can do it with log(n) applications.
The code for that method will be longer, though...

This is an experimental challenge where your score is a combination of code length and query complexity, meaning the number of calls to an auxiliary procedure.
The spec is a little long, so bear with me.

The Task

Your task is to write a named function (or closest equivalent) f that takes as inputs a positive integer n, and a permutation p of the first n integers, using either 0-based or 1-based indexing.
Its output is the permutation p.
However, you are not allowed to access the permutation p directly.
The only thing you can do with it is to apply it to any vector of n bits.
For this purpose, you shall use an auxiliary function P that takes in a permutation p and a vector of bits v, and returns the permuted vector whose p[i]th coordinate contains the bit v[i].
For example:

P([1,2,3,4,0], [1,1,0,0,0]) == [0,1,1,0,0]

You can replace "bits" with any two distinct values, such as 3 and -4, or 'a' and 'b', and they need not be fixed, so you can call P with both [-4,3,3,-4] and [2,2,2,1] in the same call to f.
The definition of P is not counted toward your score.

Scoring

The query complexity of your solution on a given input is the number of calls it makes to the auxiliary function P.
To make this measure unambiguous, your solution must be deterministic.
You can use pseudo-randomly generated numbers, but then you must also fix an initial seed for the generator.

In this repository you'll find a file called permutations.txt that contains 505 permutations, 5 of each length between 50 and 150 inclusive, using 0-based indexing (increment each number in the 1-based case).
Each permutation is on its own line, and its numbers are separated by spaces.
Your score is byte count of f + average query complexity on these inputs.
Lowest score wins.

Extra Rules

Code with explanations is preferred, and standard loopholes are disallowed.
In particular, individual bits are indistinguishable (so you can't give a vector of Integer objects to P and compare their identities), and the function P always returns a new vector instead of re-arranging its input.
You can freely change the names of f and P, and the order in which they take their arguments.

If you are the first person to answer in your programming language, you are strongly encouraged to include a test harness, including an implementation of the function P that also counts the number of times it was called.
As an example, here's the harness for Python 3.

def f(n,p):
    pass # Your submission goes here

num_calls = 0

def P(permutation, bit_vector):
    global num_calls
    num_calls += 1
    permuted_vector = [0]*len(bit_vector)
    for i in range(len(bit_vector)):
        permuted_vector[permutation[i]] = bit_vector[i]
    return permuted_vector

num_lines = 0
file_stream = open("permutations.txt")
for line in file_stream:
    num_lines += 1
    perm = [int(n) for n in line.split()]
    guess = f(len(perm), perm)
    if guess != perm:
        print("Wrong output\n %s\n given for input\n %s"%(str(guess), str(perm)))
        break
else:
    print("Done. Average query complexity: %g"%(num_calls/num_lines,))
file_stream.close()

In some languages, it is impossible to write such a harness.
Most notably, Haskell does not allow the pure function P to record the number of times it is called.
For this reason, you are allowed to re-implement your solution in such a way that it also calculates its query complexity, and use that in the harness.

J, 44.0693 22.0693 = 37 15 + 7.06931

If we can't call P on i. n, we can at least call P on each bit of i. n separately. The number of invocations of P is >. 2 ^. n (⌈log2 n⌉). I believe this is optimal.

f=:P&.|:&.#:@i.

Here is an implementation of the function P which uses the permutation vector p and saves the number of invocations into Pinv.

P =: 3 : 0"1
 Pinv =: Pinv + 1
 assert 3 > # ~. y    NB. make sure y is binary
 p { y
)

Here is a testing harness that receives a permutation and returns the number of invocations of p:

harness =: 3 : 0
 Pinv =: 0
 p =: y
 assert y = f # y     NB. make sure f computed the right permutation
 Pinv
)

And here is how you can use it on the file permutations.txt:

NB. average P invocation count
(+/ % #) harness@".;._2 fread 'permutations.txt'

Explanation

The short explanation is already provided above, but here is a more detailed one. First, f with spaces inserted and as an explicit function:

f =: P&.|:&.#:@i.
f =: 3 : 'P&.|:&.#: i. y'

Read:

  Let f be P under transposition under base-2 representation of the first y integers.

where y is the formal parameter to f. in J, the parameters to a  (function) are called x and y if the verb is dyadic (has two parameters) and y if it is monadic (has one parameter).

Instead of invoking P on i. n (i.e. 0 1 2 ... (n - 1)), we invoke P on each bit position of the numbers in i. n. Since all permutations permute in the same way, we can reassemble the permutated bits into numbers to get a permutation vector:

i. y – integers from 0 to y - 1.
#: y – y represented in base 2. This is extended to vectors of numbers in the natural way. For instance, #: i. 16 yields:

0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1

#. y – y interpreted as a base 2 number. Notably, this is the inverse to #:; y ~: #. #: always holds.
|: y – y transposed.
u&.v y – u under v, that is vinv u v y where vinv is the inverse to v. Notice that |: is its own inverse.
P y – the function P applied to each vector in y by definition.


Super fast sampling from a tricky random distribution This is a micro-optimization challenge.  The task is to sample from the maximally skewed stable distribution F(x;1,-1,Pi/2,0). See Table 1 of  http://arxiv.org/pdf/0908.3961v2.pdf . It is easiest to describe how to do this using the following C code which uses the Mersenne Twister RNG C code from  here .

#include <stdio.h>
#include <stdlib.h>
#include "mtwist.h"
#include <math.h>

int main(void) {
   int i;
   volatile double x;
   mt_seed();
   double u1;
   double u2;
   double w1;
   double w2;
   for(i = 0; i < 100000000; ++i) {
     u1 = mt_drand();
     u2 = mt_drand();
     w1 = M_PI*(u1-1/2.0);
     w2 = -log(u2);
     x = tan(w1)*(M_PI_2-w1)+log(w2*cos(w1)/(M_PI_2-w1));
   }
   return EXIT_SUCCESS;
}

I compile with

gcc -Wall -O3 random.c mtwist-1.5/mtwist.c -o random -lm

The running time is 20 seconds taking 5,000,000 iterations per second.

There are two obvious ways of making this fast. The first is to choose a very fast uniform random number generator.  If you choose to use anything but the Mersenne twister then you must run it through the Diehard tests and check the P-values provided. Use the code here http://www.stat.fsu.edu/pub/diehard/ to do this.  Your uniform random number generator must pass at least 15 of these tests.

The second way is to find fast micro-optimizations for the transcendental functions, perhaps using some CPU specific features. For example in my case these features of the AMD FX-8350 CPU.

Rules The code must maintain at least 32 bits of accuracy throughout. The code should be compilable on ubuntu using easy to install free software only.  Please provide full compile and run instructions.  You should also provide a diehard log for any non Mersenne twister RNGs as was done for Build a random number generator that passes the Diehard tests . Note the very simple RNG that passes 15 tests in that link.

Scores You can report your score as the time taken by the code above divided by the time taken by your code on your own machine. For running your code you can use any compiler and compilation options you like. To test the code above you should use gcc 4.8 or later with -O3.  If any submission take less than one second I will increase N by factors of 10 until the fastest submission takes longer than 1 second.

Test machine My test machine was a standard 8GB RAM ubuntu install on an AMD FX-8350 Processor.  Your machine can be anything that supports gcc 4.8 or later.

The Intel optimization manual says

  If there is no critical need to evaluate the transcendental functions
  using the extended precision of 80 bits, applications should consider
  an alternate, software-based approach, such as a look-up-table-based
  algorithm using interpolation techniques. It is possible to improve
  transcendental performance with these techniques by choosing the
  desired numeric precision and the size of the look-up table, and by
  taking advantage of the parallelism of the SSE and the SSE2
  instructions.

According to this very helpful table,fcos has latency 154 and fptan has latency 166-231 on my AMD FX 8350.

GMPY2
Abuse of GMP. @OP the slowest part of the code is printing the numbers, if leaving them in memory is fine the code would be much much faster.
import math
import random
import gmpy2
from gmpy2 import mpz, mpfr

gmpy2.get_context().precision = 11 # 32 bits of accuracy

N = 100000000
random_state = gmpy2.random_state()
pi = math.pi
half_pi = pi / 2
size = 0
for i in range(N):
    u1 = gmpy2.mpfr_random(random_state)
    u2 = gmpy2.mpfr_random(random_state)
    w1 = gmpy2.mul(pi, gmpy2.sub(u1,1/2))
    w2 = -gmpy2.log(u2)
    a = gmpy2.mul(gmpy2.tan(w1), gmpy2.sub(half_pi, w1))
    b = gmpy2.div(gmpy2.log(gmpy2.mul(w2, gmpy2.cos(w1))), gmpy2.sub(half_pi, w1))
    x = gmpy2.add(a, b)


Add two vectors modulo 5 Interpret a triple of 32-bit integers as a vector of 32 integers modulo 5.  Write an addition routine for these vectors.

Example:

def add32((a0,a1,a2),(b0,b1,b2)):
    c0 = c1 = c2 = 0
    m = 1
    for i in range(32):
        a  = ((a0//m)&1) + 2*((a1//m)&1) + 4*((a2//m)&1)
        b  = ((b0//m)&1) + 2*((b1//m)&1) + 4*((b2//m)&1)
        c  = (a+b)%5
        c0+= m*(c&1)
        c1+= m*((c&2)//2)
        c2+= m*((c&4)//4)
        m += m
    return c0,c1,c2

Note:

You only need to be internally consistent, not consistent with my sample code.  If you use a different representation of the integers mod 5, that's fine as long as you provide a translation table of the form:

0 = 000 or 101
1 = 001 or 110
2 = 010 or 111
3 = 011
4 = 100

Scoring:

Characters + number of arithmetic operations required.  The sample code takes 331 characters and 34 operations per bit (note that I'm not counting the function call or iteration, nor interpreter overhead); hence gets a score of 331+1056=1686.

Clarification:

This is a trick called bitslicing.  It's natural to pack integers mod 5 directly into words (spaces added for clarity:

0 1 2 3 4 -> 000 001 010 001 101

but you end up sacrificing a few bits at the end of each word.  To keep your data aligned but pack the most in, store the data in slices

                 0 0 0 0 1 = a2
a = 0 1 2 3 4 -> 0 0 1 1 0 = a1
                 0 1 0 1 0 = a0

Example 2

A language-agnostic example was requested, so here it is.  Suppose we use the representation

0 = 100
1 = 001
2 = 010 or 101
3 = 110
4 = 011

and 111 and 000 are meaningless.  Then, the following sum is valid according to our representation:

                  1 0 0 1 1 0 1 0
0 1 2 2 3 4 0 2 = 0 0 1 0 1 1 0 1
                  0 1 0 1 0 1 0 0
+
                  0 1 0 0 1 0 1 1
1 2 1 2 0 1 0 3 = 0 0 0 1 0 0 0 1
                  1 1 1 0 0 1 0 0
---------------------------------
                  0 1 1 0 1 1 1 1
1 3 3 4 3 0 0 0 = 0 1 1 1 1 0 0 0
                  1 0 0 1 0 0 0 0

Remark

As Keith Randall has demonstrated, this can be done with all bits in parallel using logical operators.  We can view such a solution as a circuit with a certain number of gates.  Perhaps I should call this "circuit golf".  I chose 5 instead of 3 because it's too easy to brute-force (optimal is 6 gates/trit).

Python, score=215 166 (167 118 chars, at most 48 ops)

def A(x,y,z,p,q,r):
 u,c=x^p,x&p;v,d=y^q^c,y&q|y&c|q&c;w,e=z^r^d,z&r|z&d|r&d
 if e:u,v,w=A(e,e,0,u,v,w)
 return u,v,w

Does addition in bit-parallel.  The c,d,e are the 32 carries from one position to the next.  e represents multiples of 8 that carry out of the vector, so if e has any bits set in it, we add 8%5=3 back in using a recursive call.

The translation table is the same as the one given in the question.


Elias omega coding: encoding Background
Elias omega coding is a universal code which can encode positive integers of any size into a stream of bits.
Given a positive integer \$N\$, the encoding algorithm is as follows:

Start with a single zero in the output.
If \$N=1\$, stop.
Prepend the binary digits of \$N\$ to the current output.
Let \$N\$ be the number of digits just prepended, minus one. Go back to step 2.

In Python-like pseudocode:
n = input()
s = "0"
while n > 1:
    # bin(n) is assumed to give a plain string of bits, without "0b" prefix
    s = bin(n) + s
    n = len(bin(n)) - 1
output(s)

Illustration
The number 1 gets encoded into a single 0.
The number 21 gets encoded into 10100101010, or 10 100 10101 0 in chunks, where each chunk is added to the output stream in the following order: first "0" by default, then the binary of 21, then 4 (the bit length of 21 minus 1), then 2, then stop.
Task
Given a positive integer \$N\$, output its Elias omega code.
You can take the input number \$N\$ in any convenient format, including its representation in binary.
The output must be a valid representation of a flat stream of bits, which includes:

a plain string or array of zeros and ones, or
a single integer whose binary representation corresponds to the stream of bits.

Outputting the bits in reverse or outputting a nested structure of bits (e.g. ["10", "100", "10101", "0"] for 21) is not allowed.
Shortest code in bytes wins.
Test cases
N     => Omega(N)
1        0
2        100
3        110
4        101000
5        101010
6        101100
7        101110
8        1110000
12       1111000
16       10100100000
21       10100101010
100      1011011001000
345      1110001010110010
1000     11100111111010000
6789     11110011010100001010
10000    111101100111000100000
1000000  1010010011111101000010010000000

This is OEIS A281193.

Husk, 16 13 11 bytes
ṁḋ↔Θ↑←¡ȯ←Lḋ

Try it online!
Outputs a flat boolean array.
-2 using the idea from Jonathan Allan's answer.
Explanation
ṁḋ↔Θ↑←¡ȯ←Lḋ
      ¡ȯ    create an infinite list using:
         Lḋ length of binary digits
        ←   decremented
    ↑       take the longest prefix with:
     ←       elements that aren't falsy when decremented(1)
   Θ        prepend 0 to that
  ↔         reverse
ṁḋ          convert each to binary and flatten


Counting in binary nybbles This challenge is to output to your terminal, window, canvas or screen the numbers zero to 10 inclusive. Each outputted number must be shown as a 4-bit wide nybble, so zero must show as 0000 and so on.

You may separate each number outputted with a space, comma or carriage return. Smallest solution wins but the numbers can be displayed in any order you like as long as there are no repeating numbers in your sequence.

Entries in low-level binary languages need not worry about the comma or white space separators if it is not possible to output with commas or white spaces (i.e., the standard output is limited to binary only, or your solution is for an early computer kit such as the KIM-1 which has a limited digital display).

MATL, 6 bytes
0:10YB

Try it at MATL Online
Explanation
0:10    % Create the array [0...10]
YB      % Convert this array to a binary string where each number is
        % placed on a new row
        % Implicitly display the result


Frequency Distribution of Mixed Dice Rolls A follow-up to this challenge
Given a set of mixed dice, output the frequency distribution of rolling all of them and summing the rolled numbers on each die.
For example, consider 1d12 + 1d8 (rolling 1 12-sided die and 1 8-sided die). The maximum and minimum rolls are 20 and 2, respectively, which is similar to rolling 2d10 (2 10-sided dice). However, 1d12 + 1d8 results in a flatter distribution than 2d10: [1, 2, 3, 4, 5, 6, 7, 8, 8, 8, 8, 8, 7, 6, 5, 4, 3, 2, 1] versus [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1].
Rules

The frequencies must be listed in increasing order of the sum to which the frequency corresponds.
Labeling the frequencies with the corresponding sums is allowed, but not required (since the sums can be inferred from the required order).
You do not have to handle inputs where the output exceeds the representable range of integers for your language.
Leading or trailing zeroes are not permitted. Only positive frequencies should appear in the output.
You may take the input in any reasonable format (list of dice ([6, 8, 8]), list of dice pairs ([[1, 6], [2, 8]]), etc.).
The frequencies must be normalized so that the GCD of the frequencies is 1 (e.g. [1, 2, 3, 2, 1] instead of [2, 4, 6, 4, 2]).
All dice will have at least one face (so a d1 is the minimum).
This is code-golf, so the shortest code (in bytes) wins. Standard loopholes are forbidden, as per usual.

Test Cases
These test cases are given as input: output, where the input is given as a list of pairs [a, b] representing a b-sided dice (so [3, 8] refers to 3d8, and [[1, 12], [1, 8]] refers to 1d12 + 1d8).
[[2, 10]]: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
[[1, 1], [1, 9]]: [1, 1, 1, 1, 1, 1, 1, 1, 1]
[[1, 12], [1, 8]]: [1, 2, 3, 4, 5, 6, 7, 8, 8, 8, 8, 8, 7, 6, 5, 4, 3, 2, 1]
[[2, 4], [3, 6]]: [1, 5, 15, 35, 68, 116, 177, 245, 311, 363, 392, 392, 363, 311, 245, 177, 116, 68, 35, 15, 5, 1]
[[1, 3], [2, 13]]: [1, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 37, 36, 33, 30, 27, 24, 21, 18, 15, 12, 9, 6, 3, 1]
[[1, 4], [2, 8], [2, 20]]: [1, 5, 15, 35, 69, 121, 195, 295, 423, 579, 761, 965, 1187, 1423, 1669, 1921, 2176, 2432, 2688, 2944, 3198, 3446, 3682, 3898, 4086, 4238, 4346, 4402, 4402, 4346, 4238, 4086, 3898, 3682, 3446, 3198, 2944, 2688, 2432, 2176, 1921, 1669, 1423, 1187, 965, 761, 579, 423, 295, 195, 121, 69, 35, 15, 5, 1]
[[1, 10], [1, 12], [1, 20], [1, 50]]: [1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 285, 360, 444, 536, 635, 740, 850, 964, 1081, 1200, 1319, 1436, 1550, 1660, 1765, 1864, 1956, 2040, 2115, 2180, 2235, 2280, 2316, 2344, 2365, 2380, 2390, 2396, 2399, 2400, 2400, 2400, 2400, 2400, 2400, 2400, 2400, 2400, 2400, 2400, 2399, 2396, 2390, 2380, 2365, 2344, 2316, 2280, 2235, 2180, 2115, 2040, 1956, 1864, 1765, 1660, 1550, 1436, 1319, 1200, 1081, 964, 850, 740, 635, 536, 444, 360, 285, 220, 165, 120, 84, 56, 35, 20, 10, 4, 1]

Jelly,  14  7 bytes

-3 bytes thanks to Mr. Xcoder (use of an implicit range to avoid leading R; replacement of reduce by the dyadic Cartesian product and flatten, p/F€, with the Cartesian product built-in for that very purpose, Œp.)

ŒpS€ĠL€

A monadic link taking a list of dice faces and returning the normalised distribution of the increasing sums.

Try it online!

How?

Goes through the list of dice "sizes" (implicitly) makes them into their list of faces, then gets the Cartesian product of those lists (all possible rolls of the set of dice), then sums up those rolls, gets the groups of equal indices (by ascending value) and takes the length of each group.

ŒpS€ĠL€ - Link: list of numbers, dice  e.g. [2,5,1,2]
Œp      - Cartisian product (implicit range-ification -> [[1,2],[1,2,3,4,5],[1],[1,2]])
        -                   -> [[1,1,1,1],[1,1,1,2],[1,2,1,1],[1,2,1,2],[1,3,1,1],[1,3,1,2],[1,4,1,1],[1,4,1,2],[1,5,1,1],[1,5,1,2],[2,1,1,1],[2,1,1,2],[2,2,1,1],[2,2,1,2],[2,3,1,1],[2,3,1,2],[2,4,1,1],[2,4,1,2],[2,5,1,1],[2,5,1,2]]
  S€    - sum €ach          -> [4,5,5,6,6,7,7,8,8,9,5,6,6,7,7,8,8,9,9,10]
    Ġ   - group indices     -> [[1],[2,3,11],[4,5,12,13],[6,7,14,15],[8,9,16,17],[10,18,19],[20]]
     L€ - length of €ach    -> [1,3,4,4,4,3,1]

Note: there is only ever one way to roll the minimum (by rolling a one on each and every dice) and we are not double-counting any rolls, so there is no need to perform a GCD normalisation.


Compress 8 bits to 6 when certain bit patterns will never occur Consider an eight bit number in which an even position bit will never be 1 if one of its neighbors is 0 (considering MSB and LSB as neighbors). There are fewer than 64 such numbers, so there is at least some reversible mapping of them to 6 bit numbers.

Your task is to write a pair of functions (or code blocks or your language equivalent), one of which takes an 8-bit number and returns a 6-bit number, the other which reverses the process. "Numbers" here can be literal numbers or a list of booleans or even a string of Xs and Os.

Put another way, the following bit patterns will never occur:

......01
.....10.
....01..
...10...
..01....
.10.....
01......
0......1

PS: I'd really love to see an answer in Lua :)

PPS: Bonus imaginary internet points if you can pack the 47 valid values into a 6-bit number with a maximum of value of 47

Python, 60 bytes

l=[n^170for n in range(256)if n&n*2<1]
l.index,l.__getitem__

Try it online!

l.index compresses and l.__getitem__ decompresses. We just make a list l of all valid patterns as 8-bit numbers, except we ignore wrapping around, which still leaves 55 options which fits in 6 bits.

A useful idea is that if we flip the bits at even positions, which ^170 does, then the condition just becomes "no two 1's are (cyclically) adjacent". This is easy to check without wrapping around using the bit condition n&(n*2)==0, or shorter, n&n*2<1.

Fibonacci numbers

Binary strings with no adjacent ones have interesting connections to Fibonacci numbers. The number of such 8-bit numbers is 55, a Fibonacci number, following the general result. Moreover, Zeckendorf's Theorem tell us that each number can be uniquely expressed in the Fibonacci base without using a pair of adjacent ones, that is as a sum of distinct Fibonacci numbers without two consecutive ones, as these can be merged into the next Fibonacci number.

Perhaps a base conversion to the Zeckendorf Representation can be used for a less brute-force answer than the one here. We've had challenges to convert from and to the Zeckendorf representation, which could be used as the basis of a decoder-encoder pair.

Bonus: 64 bytes

For imaginary internet points, we can tweak the algorithm to accounts for cyclically adjacent ones, so as to limit the compression to 48 valid bit patterns from 55. We do this by modifying the bit check to n&n*2%255<1, at the cost of 4 extra bytes.

64 bytes

l=[n^170for n in range(256)if n&n*2%255<1]
l.index,l.__getitem__

Try it online!

The modulo 255 changes the bit-shift n*2 to a cyclic shift

abcdefgh -> bcdefgha

by moving the post-doubling place value of 256*a to just a. This is, except for n=255, which where n*2%255 is zero, giving a false positive at 255^170=85. But, since the bonus for imaginary internet points gives use one spare slot, with 48 slots for 47 values, we can just live with this hole.


Knight's tour game (7x7) Your job is to solve this chess-related game.

The setup of the game is a 7x7 tile grid, you start on a random tile and you have to hop on each tile, until you hopped on all 49 tiles.

Top left corner is (0,0)

Rules:

you can hop on each tile once.
the only move allowed in the game is to hop two tiles horizontally and one tiles vertically, or two tiles vertically and one tiles horizontally, like a knight in a chess game.
your input should be a tuple representing the coordinates of the starting tile (stdin, file, what you prefer).
your output a list of tuples, representing the coordinates of each hop. If there's no valid combinations, return an empty list (same as above, any output is ok).

This is code-golf, so shortest code wins!

APL (Dyalog Extended), 39 bytes

7 7{3::0⋄(⍋,(⊢⊃⍨⍵⍳⍨⊃∘⍸¨∘=)¯1⌂kt⍺)⊇,⍳⍺}⊂

Try it online!

A version provided by @Adám.

Dyalog Extended has a shortcut to the dfns library ⌂, and a few convenience functions e.g. monadic = which is equivalent to 0∘=, and dyadic ⊇ for multiple indexing. Unfortunately an inner assignment is buggy, so we use a tacit inner function to reference the value of ¯1⌂kt⍺ twice. Otherwise we'd have a 38 byte solution:

7 7{3::0⋄(⍋,w⊃⍨⍵⍳⍨⊃∘⍸¨=w←¯1⌂kt⍺)⊇,⍳⍺}⊂

How the inner tacit function (⊢⊃⍨⍵⍳⍨⊃∘⍸¨∘=) works

This tacit function has 5 terms: `⊢`  `⊃⍨`  `⍵`  `⍳⍨`  `⊃∘⍸¨∘=`
A tacit function is grouped by 3 terms from the right:
  ⊢ ⊃⍨ (⍵ ⍳⍨ ⊃∘⍸¨∘=)
A group of 3 terms is interpreted as follows:
  (f g h)w → (f w) g (h w)     ⍝ f, g, h are functions
  (A g h)w → (A  ) g (h w)     ⍝ A is an array
Then we can interpret the above tacit function as
  (⊢ ⊃⍨ (⍵ ⍳⍨ ⊃∘⍸¨∘=))w
  → (⊢ w) ⊃⍨ (⍵ ⍳⍨ (⊃∘⍸¨∘= w))   ⍝ Expand tacit function
  → w ⊃⍨ ⍵ ⍳⍨ ⊃∘⍸¨∘= w           ⍝ ⊢ is identity function; simplify parens
  → w ⊃⍨ ⍵ ⍳⍨ ⊃∘⍸¨ = w           ⍝ (f∘g)w simply expands to f g w
So the code `(⊢⊃⍨⍵⍳⍨⊃∘⍸¨∘=)w` is equivalent to `w⊃⍨⍵⍳⍨⊃∘⍸¨=w`.

APL (Dyalog Unicode), 53 49 bytes

⎕CY'dfns'
7 7{3::0⋄(,⍳⍺)[⍋,w⊃⍨⍵⍳⍨⊃∘⍸¨0=w←¯1kt⍺]}⊂

Try it online!

Golfed 4 bytes by extracting some terms out of the dfn using a tacit form.

Original submission: APL (Dyalog Unicode), 53 bytes

⎕CY'dfns'
{3::0⋄(,⍳7 7)[⍋,w⊃⍨(⊃∘⍸¨0=w←¯1 kt 7 7)⍳⊂⍵]}

Try it online!

Because we've got a language that has a Knight's tour solver built in.

Since ¯1 kt 7 7 tries to find all solutions, it's infeasible to actually run the code as-is. For demonstration purposes, the TIO link uses 3x4 board instead.

How it works

The function dfns.kt finds a (possibly open) Knight's tour, where the right argument is the board's dimensions, and the optional left argument is the number of solutions to find. Giving -1 on the left causes the function to search all possible solutions.

⎕CY'dfns'  ⍝ Import the 'dfns' workspace

{3::0⋄(,⍳7 7)[⍋,w⊃⍨(⊃∘⍸¨0=w←¯1 kt 7 7)⍳⊂⍵]}  ⍝ ⍵←starting coordinates
                          w←¯1 kt 7 7        ⍝ Find ALL solutions of 7x7 knight's tour
                   (⊃∘⍸¨0=           )       ⍝ Extract the starting coordinates from each solution
                                      ⍳⊂⍵    ⍝ Find the index of the solution that starts at ⍵
               ,w⊃⍨                          ⍝ Fetch the solution and flatten it
      (,⍳7 7)                                ⍝ Take the flattened list of coordinates on 7x7 board
             [⍋                          ]   ⍝ Sort the coordinates by flattened solution
 3::0⋄                                       ⍝ If there's no solution starting with ⍵,
                                             ⍝ catch the Index Error and return 0 instead

Every black square on 7x7 board can be the starting location of a Knight's tour.

The following isn't directly related to the code above, but nevertheless here is a proof by example.

Starting at (0,0), Ending at (5,1)

0  11 22 45 2  13 24
21 46 1  12 23 44 3
10 27 34 39 36 25 14
47 20 37 26 33 4  43
28 9  40 35 38 15 32
19 48 7  30 17 42 5
8  29 18 41 6  31 16

Starting at (1,3), Ending at (6,4)

20 27 10 33 44 1  12
9  32 21 0  11 34 45
26 19 28 43 40 13 2
31 8  41 22 29 46 35
18 25 30 39 42 3  14
7  38 23 16 5  36 47
24 17 6  37 48 15 4

Starting at (2,2), Ending at (3,3)

30 19 40 3  28 17 38
41 2  29 18 39 4  27
20 31 0  13 10 37 16
1  42 11 48 15 26 5
32 21 14 9  12 47 36
43 8  23 34 45 6  25
22 33 44 7  24 35 46

By swapping heads and tails, reflection, and rotation, all black squares can be the starting point of some Knight's tour.

I found these three tours by splitting the board into four groups that can form a continuous loop:

O O O . O O O  |  . . . O . . .  |  . . . . . . .  |  . . . . . . .
O . O O O . O  |  . O . . . O .  |  . . . . . . .  |  . . . . . . .
O O . . . O O  |  . . . . . . .  |  . . O O O . .  |  . . . . . . .
. O . . . O .  |  O . . . . . O  |  . . O . O . .  |  . . . O . . .
O O . . . O O  |  . . . . . . .  |  . . O O O . .  |  . . . . . . .
O . O O O . O  |  . O . . . O .  |  . . . . . . .  |  . . . . . . .
O O O . O O O  |  . . . O . . .  |  . . . . . . .  |  . . . . . . .

and breaking and gluing the chains whenever needed. It's kind of a heuristic, so it would be usually shorter to hardcode the three boards or just run naive DFS.


Write a microwave timer! You are an employee of Microteque, a leading Silicon Valley startup creating smart microwave ovens for all kinds of strange places. Your customers can get their microwaves printed with patterns to match their kitchens, campers, man caves; even the kitchens of large nation-state facilities have shiny new branded microwave ovens.
Due to the cutting-edge nature of your microwave control board technology, you've ended up having to use the programming language MicrowaveX* and you're working out how to program the time counter. Your counter looks like this:

Your goal is to write a program that takes the input time and translates it into the number of seconds that the microwave needs to run.
As input, the function must take a string in the format ##:## (including the colon at position 3) and return an integer.
Please note that it should also be able to handle more than 60 seconds in the seconds slot.
Finally, due to some pesky regulations, you cannot have your microwave oven run for more than 100 minutes (6,000 seconds)
Sample inputs and outputs:
01:30 --> 90 seconds
00:66 --> 66 seconds
01:99 --> 159 seconds
02:39 --> 159 seconds
99:99 --> 6,000 seconds (capped at 100 minutes due to aforementioned regulations)
*: MicrowaveX happens to be identical to your programming language of choice, but Microteque has rebranded it to sound more appealing to their investors.

Bash + GNU utilities, 33 bytes

dc<<<[6000]sL${1/:/ 60*}+dlLx\<Lp

Try it online!

Or try the test suite.

The input string is passed as an argument, and the output is on stdout.

How it works

First bash expands ${1/:/ 60*} by taking argument 1 and replacing the : with 60* (there's a space before the 60 that StackExchange isn't displaying here).  For example, if the input is 01:30, the expansion is 01 60*30.

Also, \< gets used as the character < without its special meaning in the shell.

So what happens is that dc is run with

[6000]sLminutes60*seconds+dlLx<Lp

as its program (where "minutes" and "seconds" refer to the actual two-digit numbers).

This carries out the following operations:

[6000]               Definition of a macro which pushes 6000 on the stack.
sL                   Save the macro in register L.
minutes 60*seconds+  Compute minutes*60+seconds,
                        which is the total number of seconds.
d                    Duplicate the total number of seconds on the stack.
lLx                  Run macro L, which pushes 6000 on the stack.
                     The stack now looks like:
                        #seconds #seconds 6000
                        (top of stack on the right).
<L                   Pop 6000 and #seconds from the stack;
                        if 6000 < #seconds,
                          then run macro L to push 6000 on the stack again.
                     At this point, the item at the top of the stack is:
                        #seconds, if #seconds <= 6000,
                        6000, if #seconds > 6000.
p                    Print the top of the stack.


Monday Mini-Golf #5: Don't DO try this at home Monday Mini-Golf: A series of short code-golf questions, posted (hopefully!) every Monday.

Sometimes folks get tired of life's rules: "don't do this", "you can't do that", "we won't let you do this". It can seem really restricting at times! But every now and then, it's good to have a little fun, so let's write some code to modify these rules. And while we're at it, might as well modify other negativity as well. (Of course, these modifications won't WILL be only temporary, so we'll leave the original wording too.)

Challenge

Your challenge is to write a program or function that puts HTML <s>strikethroughs</s> around restrictive words—that is, words ending in n't or followed by not—and after each of these, inserts its positive equivalent in ALL CAPS. At the end, after a space, the number of replacements made should be included. For example:

Please don't jump into the pool.

becomes

Please <s>don't</s> DO jump into the pool. 1

For words ending in n't or followed by not (as well as cannot), the positive equivalent is everything up to the aforementioned not (excluding spaces). Here's what I mean:

do not speak becomes <s>do not</s> DO speak
it doesn't work becomes it <s>doesn't</s> DOES work
we cannot becomes we <s>cannot</s> CAN

However, there are a few exceptions. Make sure these are handled properly.

can't -> <s>can't</s> CAN
won't -> <s>won't</s> WILL
ain't -> <s>ain't</s> AM
shan't -> <s>shan't</s> SHALL
I'm not -> <s>I'm not</s> I AM
you're not -> <s>you're not</s> YOU ARE

Details

The input will never contain any whitespace except normal spaces (no tabs, newlines, etc.).
The input will never contain any double negatives (e.g. we can't not do this).
If a not appears immediately after a punctuation mark, or as part of another word, leave it be.
Be sure to preserve the original text, including upper/lowercase, between the <s></s> tags.
If you wish, you may use <strike></strike> in place of <s></s>.

Test-cases

Inputs:

I'm sorry, but you can't do that.
Driving on the beach isn't allowed.
Driving on the beach is not allowed.
Please don't jump in; I cannot imagine what might come of that.
Don't worry; we won't get into trouble.
I'm not perfect, but you're not either.
You shan't do it 'cause I ain't doin' it!
Can't we capitalize special cases?
I don't like the words can't, shan't, won't, don't, ain't, or ppcgn't.
Oh, this? It's nothing.
Tie a slipknot in the rope.
Would you like Pinot Noir?
This sentence contains none of the replacement words. Not even knot or ca't.
This sentence doesn't contain one of the replacement words.

Outputs:

I'm sorry, but you <s>can't</s> CAN do that. 1
Driving on the beach <s>isn't</s> IS allowed. 1
Driving on the beach <s>is not</s> IS allowed. 1
Please <s>don't</s> DO jump in; I <s>cannot</s> CAN imagine what might come of that. 2
<s>Don't</s> DO worry; we <s>won't</s> WILL get into trouble. 2
<s>I'm not</s> I AM perfect, but <s>you're not</s> YOU ARE either. 2
You <s>shan't</s> SHALL do it 'cause I <s>ain't</s> AM doin' it! 2
<s>Can't</s> CAN we capitalize special cases? 1
I <s>don't</s> DO like the words <s>can't</s> CAN, <s>shan't</s> SHALL, <s>won't</s> WILL, <s>don't</s> DO, <s>ain't</s> AM, or <s>ppcgn't</s> PPCG. 7
Oh, this? It's nothing. 0
Tie a slipknot in the rope. 0
Would you like Pinot Noir? 0
This sentence contains none of the replacement words. Not even knot or ca't. 0
This sentence <s>doesn't</s> DOES contain one of the replacement words. 1

Scoring

This is code-golf, so shortest valid code in bytes wins. Tiebreaker goes to submission that reached its final byte count first. The winner will not WILL be chosen next Monday, Oct 26. Good luck!

Pip, 138 140 bytes

Yeesh, that cannot/knot distinction is tricky.

x:"ca wo ai sha i'm you're"^sY"CAN0WILL0AM0SHALL0I AM0YOU ARE"^0OqR-`([\w']+)( no|n'|(?<=can)no)t\b`{++i"<s>".a."</s>".s.((yx@?LCb)|UCb)}s.i

Reads a line from stdin, outputs to stdout. The regex:

`([\w']+)( no|n'|(?<=can)no)t\b`

matches a word (including apostrophes) followed by one of three things:

 not
n't
not without a space, provided the first half of the word was can

The - operator on a regex makes it case-insensitive.

Matches are replaced with the result of the following function. (Note: within the function, a is the whole match and b is capture group 1.)

{++i"<s>".a."</s>".s.((yx@?LCb)|UCb)}
 ++i                                   Increment counter
    "<s>".a."</s>"                     Return entire match wrapped in HTML tags...
                  .s.(             )   plus space, plus the following:
                           LCb         Lowercase first capture group
                        x@?            Find its index in list x of special cases (nil if
                                         not in list)
                      (y      )        Use that as index into list y of replacements
                               |UCb    If it wasn't a special case, this is nil, and we
                                         instead use uppercase(b)

Once the modified string is done, we also output a space and the number of replacements i.


Explore a Klarner-Rado sequence One of the Klarner-Rado sequences is defined as follows:

the first term is \$1\$
for all subsequent terms, the following rule applies: if \$x\$ is present, so are \$2x+1\$ and \$3x+1\$
the sequence is strictly increasing

This is A002977.
The first few terms are:
1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...

(\$3\$ is present because it's \$2\times1+1\$, \$4\$ is present because it's \$3\times1+1\$, \$7\$ is present because it's \$2\times3+1\$, etc.)
Your task
Given \$n\$, you must return the \$n\$th element of the sequence. You may use either 0-based or 1-based indexing. (Please specify your choice in your answer.)
0-indexed example:
input = 10
output = 22

Let's see who can get less bytes...
Also featured on codewars

05AB1E, 15 14 bytes

$FDx>DŠ+)˜ê}sè

Try it online!


Recognize handwritten digits Your task is to read an image containing a handwritten digit, recognize and print out the digit.

Input: A 28*28 grayscale image, given as a sequence of 784 plain-text numbers from 0 to 255, separated by space. 0 means white and 255 means black.

Output: The recognized digit.

Scoring: I will test your program with 1000 of the images from the MNIST database training set (converted to ASCII form). I have already selected the images (randomly), but will not publish the list. The test must finish within 1 hour, and will determine n - the number of correct answers.
n must be at least 200 for your program to qualify. If the size of your source code is s, then your score will be calculated as s * (1200 - n) / 1000. Lowest score wins.

Rules:

Your program must read the image from the standard input and write the digit to the standard output
No built-in OCR function
No third-party libraries
No external resources (files, programs, web sites)
Your program must be runnable in Linux using freely available software (Wine is acceptable if necessary)
The source code must use only ASCII characters
Please post your estimated score and a unique version number every time you modify your answer

Example input:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 18 18 18 126 136 175 26 166 255 247 127 0 0 0 0 0 0 0 0 0 0 0 0 30 36 94 154 170 253 253 253 253 253 225 172 253 242 195 64 0 0 0 0 0 0 0 0 0 0 0 49 238 253 253 253 253 253 253 253 253 251 93 82 82 56 39 0 0 0 0 0 0 0 0 0 0 0 0 18 219 253 253 253 253 253 198 182 247 241 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 80 156 107 253 253 205 11 0 43 154 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14 1 154 253 90 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 139 253 190 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 190 253 70 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 35 241 225 160 108 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 81 240 253 253 119 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 45 186 253 253 150 27 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16 93 252 253 187 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 249 253 249 64 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 46 130 183 253 253 207 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 39 148 229 253 253 253 250 182 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 24 114 221 253 253 253 253 201 78 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 23 66 213 253 253 253 253 198 81 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 18 171 219 253 253 253 253 195 80 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 55 172 226 253 253 253 253 244 133 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 136 253 253 253 212 135 132 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

By the way, if you prepend this line to the input:

P2 28 28 255

you will obtain a valid image file in pgm format, with inverted/negated colors.

This is what it looks like with correct colors:

Example output:

5

Standings:

No.| Name         | Language   | Alg | Ver | n   | s   |  Score
----------------------------------------------------------------
 1 | Peter Taylor | GolfScript | 6D  | v2  | 567 | 101 |  63.933
 2 | Peter Taylor | GolfScript | 3x3 | v1  | 414 | 207 | 162.702

GolfScript 6D (v2: estimated score 101 * 0.63 ~= 64)

This is a very different approach to my earlier GolfScript answer, so it makes more sense to post it as a separate answer at v1 than to edit the other answer and make this v2.

~]:B;569'!EM,R.==|%NL2+^=1'{{32-}%95{base}:^~\^}:&~2/{~B=<}%2^10'#]8Y,;KiZfnnRsDzPsvQ!%4C&..z,g,$m'&=

Ungolfed

~]:B;
[30 183 21 378 31 381 7 461 113 543 15 568]
2/{~B=<}%2base
7060456576664262556515119565486100005262700292623582181233639882 10base
=

Explanation

The raw problem is classification of points in a 784-dimensional space. One standard approach is dimension reduction: identifying a small subset of dimensions which provide sufficient distinguishing power to do the classification. I evaluated each dimension and each possible threshold to identify 18 pairs of (dimension, range of threshold) which looked promising. I then picked the centre of each range of threshold, and evaluated 6-element subsets of the 18 pairs. Finally I optimised the threshold for each dimension of the best 6-D projection, improving its accuracy from 56.3% to 56.6%.

Because the projection is into 6 dimensions and for each dimension I apply a simple threshold, the final lookup table only needs 64 elements. It doesn't seem to be particularly compressible, so the main golfing is to base-convert both lookup tables (the list of dimension and thresholds; and the halfspace vector to digit map) and share the base-conversion code.


Make a number palindrome Write a function that takes a number as an argument and makes it a palindrome by appending minimum number of digits. The number will be at max of 100 digits.

Sample Inputs
12
122
232
2323
1012121
Sample Outputs
121
1221
232
23232
101212101

Perl, 32 chars

s/((.)(?1)\2|.?)$/$&.reverse$`/e

Needs Perl 5.10 or later for regex features, but no special command-line switch.

Sample use:

$ perl -pe 's/((.)(?1)\2|.?)$/$&.reverse$`/e' << EOT
> 12
> 232
> 2323
> 1012121
> EOT
121
232
23232
101212101

Uses Perl 5.10's recursive regex extensions to match the longest trailing palindrome as such:

m/
    (      # paren 1 - a palindrome is either:
      (.)  # paren 2 - a character
      (?1) # a palindrome as defined in paren 1
      \2   # the same character as in paren 2
    |        # or:
      .?   # a 0- or 1-character string
    )
    $      # at end of string
/x

It then replaces it with itself ($&) and appends whatever the string started with ($`), reversed.


Optimal Games of Tic Tac Torus This challenge is about the game Tic Tac Toe, but it's played on a torus.

How to play

To create the necessary game board, you start out with a regular Tic Tac Toe game board. First fold it into a cylinder by joining the left and the right edge. Then fold it into torus by joining the top and the bottom edge. Here's a simple visualization of such a game board with a few moves played (Sick Paint skills!).

The rules of Tic Tac Toe on a torus are the same as regular Tic Tac Toe. Each Player place alternating Xs and Os. The first one with 3 same symbols in a row, a column or a in a diagonal wins.

Since a torus is quite hard to visualize, we simply project the board back onto a paper. Now we can play the game as regular Tic Tac Toe. The only difference is, that you can also win with 3 same symbols in a broken diagonal. For instance Player 1 (X) wins the following board. You can see this easily by changing the view on the torus a little bit.

If your interested, you can play Tic Tac Toe on a Torus at Torus Games. There's a Windows, Mac and Android version.

Optimal Games

In this challenge were interested in optimal games. An optimal game is a game, where both players play an optimal strategy. On a regular Tic Tac Toe board optimal games always end in a draw. Fascinatingly on a torus board always the first player wins. In fact a game on a torus board can never end in a draw (also if the players play not optimal).

The optimal strategy is really easy:

If you can win by placing your symbol, do it.
Otherwise if your opponent has two symbols in one row/column/điagonal, try to block him. Otherwise, do what you want.
Otherwise do what you want.

Every optimal game consists of exactly 7 moves and these moves can be described in the following way:

Player 1 places a X anywhere on the board (9 choices)
Player 2 places an O anywhere on the board (8 choices)
Player 1 places a X anywhere on the board (7 choices)
Player 2's move may be forced (1 choice), if not, he places the O anywhere (6 choices)
Player 1's move is forced (1 choice)
Player 2 is caught in a fork (Player 1 can win in two different ways), so Player 2 has to block Player 1 in one way (2 choices)
Player 1 places the his last move and wins (1 choice)

There are 9*8*1*6*1*2*1 + 9*8*6*1*1*2*1 = 1728 different optimal games on our projected board. Here you can see one typical optimal game:

If we label each cell of the board with the digits 0-8, we can describe this game by the digits  3518207. First a X is places in the cell 3 (middle row, left column), than an O in cell 5 (middle row, right column), than a X in cell 1 (upper row, middle column), ...

Using this digit notation we automatically generated an order. Now we can sort all of the 1728 optimal games and we get the list:

Game 0000: 0123845
Game 0001: 0123854
Game 0002: 0124735
Game 0003: 0124753
Game 0004: 0125634
   ...
Game 0674: 3518207
   ...
Game 1000: 5167423
Game 1001: 5167432
Game 1002: 5168304
   ...
Game 1726: 8765034
Game 1727: 8765043

Challenge

This list is part of your job. You will receive one number k between 0 and 1727 and you have to return the kth game in digit notation of that sorted list.

Write a function or a program, that receives the number k (integer) computes the correspondent game. You can read the input via STDIN, command-line argument, prompt or function argument and print the result (7 digits) in a readable format (e.g. 0123845 or [0, 1, 2, 3, 8, 4, 5]) or return it using an string (human readable format) or an integer (containing all digits in base 10), or in any array/list format.

The challenge type is code-golf. Therefore the shortest code wins.

JavaScript (ES6), 266 308 317 334 341
A function returning a string.
Edit Found an arithmetic solution for function M (at last!)
F=(n,x=[],M=(a,b,t=-a-b)=>(a-b)%3?a<3&b<3?3+t:a>5&b>5?21+t:12+t:9+t+a%3*3)=>
[for(a of z='012345678')for(b of z)for(c of z)for(d of z)
a-b&&c-a&&c-b&&(b-(y=M(a,c))?d==y:d-a&&d-b&&d-c)&&(
f=M(c,e=M(b,d)),g=M(a,e),g<f?[f,g]=[g,f]:0,r=a+b+c+d+e,x.push(r+f+g,r+g+f))]
&&x[n]

Very naive , it can be shortened in many ways. It simply enumerates all the possible legal values and returns what find at place n.
The M function returns the position in between two cells, that is the mandatory move to block an opposite player.
More readable
F=(n,x=[],
  M=(a,b,t=-a-b)=>(a-b)%3?
     a<3&b<3?
       3+t // first row
       :a>5&b>5?
          21+t // last row
          :12+t // middle row and diags
     :9+t+a%3*3 // columns
  )=>
  [for(a of z='012345678') // enumerate the first 4 moves
     for(b of z)
       for(c of z)
         for(d of z)
           a-b&&c-a&&c-b // avoid duplicates
           &&(b-(y=M(a,c))?d==y:d-a&&d-b&&d-c) // and check if d must block a-c or it's free
           &&(
             e=M(b,d), // forced to block b-d
             f=M(c,e),g=M(a,e),g<f?[f,g]=[g,f]:0, // f and g could be in the wrong order
             r=a+b+c+d+e, // start building a return string
             x.push(r+f+g,r+g+f) // store all values in x
  )]&&x[n] // return value at requested position