Edit distance where a substitution only costs the first time This challenge is about the following variant of edit distance.  Say we have a cost of 1 for inserts, deletes and substitutions as usual with one exception. A substitution for a given letter x for a letter y only costs 1 the first time.  Any further substitutions of x for y cost 0.
As simple examples:
A = apppple
B = attttle

cost 1 (not 4) to transform A into B. This is because we change p for a t four times but we only charge for the first one.
A = apxpxple
B = atxyxtle

cost 2 (not 3) as the p to t substitution only costs 1 even though we do it twice.
A = apppple
B = altttte

cost 3. p -> l costs 1. p -> t costs 1 as does l -> t.
If we assume the total length of the input is n, you must give the big O() of your algorithm. The best time complexity wins.

We should assume the alphabet size can be as large as n.

Naive recursive algorithm \$ O(\frac{(1+\sqrt2)^n}{\sqrt{n}}) \$
The basic idea is try adding, removing and replacing one character and recursive.

def f(str1, str2):
  l1, l2 = len(str1), len(str2)
  mapping = set()
  def g(p1, p2):
    if l1 == p1 or l2 == p2:
      return l1 + l2 - p1 - p2
    cost1 = g(p1 + 1, p2) + 1
    cost2 = g(p1, p2 + 1) + 1
    if str1[p1] != str2[p2] and (str1[p1], str2[p2]) not in mapping:
      mapping.add((str1[p1], str2[p2]))
      cost3 = g(p1 + 1, p2 + 1) + 1
      mapping.discard((str1[p1], str2[p2]))
    else:
      cost3 = g(p1 + 1, p2 + 1)
    return min(cost1, cost2, cost3)
  return g(0, 0)

The function g will be invoked \$ O(\frac{(1+\sqrt2)^n}{\sqrt{n}}) \$ times[1]. While adding, discarding, or checking an element in the mapping cost \$ O(1) \$ on average.
[1]: Based on https://oeis.org/A027618 ; I don't know why actually...


Get the indices of an array after sorting Your challenge today is to write a program or function which takes a list l and gives the positions in l at which each successive element of l sorted appears.

In other words, output the index of the smallest value, followed by the index of the second smallest value, etc.

You can assume that the input array will contain only positive integers, and will contain at least one element.

Test cases:

Input                  | Output (1-indexed)
[7, 4, 5]              | [2, 3, 1]
[1, 2, 3]              | [1, 2, 3]
[2, 6, 1, 9, 1, 2, 3]  | [3, 5, 1, 6, 7, 2, 4]
[4]                    | [1]

When two or more elements with the same value appear, their indices should appear next to each other from smallest to largest.

This is code-golf, fewest bytes wins!

Dyalog APL, 1 byte

⍋

Dyalog APL has a built in operator function (thank you Zacharý for clearing this up) to do this.

Example

⍋11 2 4 15
    2 3 1 4
{⍵[⍋⍵]}11 4 2 15
    2 4 11 15

Here I'm indexing into the list by the sorted indices to return the list in ascending order.


Generate Recamán's sequence Recamán's sequence (A005132) is a mathematical sequence, defined as such:

A(0) = 0
A(n) = A(n-1) - n if A(n-1) - n > 0 and is new, else
A(n) = A(n-1) + n

A pretty LaTex version of the above (might be more readable):

$$A(n) = \begin{cases}0 & \textrm{if } n = 0 \\
A(n-1) - n & \textrm{if } A(n-1) - n \textrm{ is positive and not already in the sequence} \\
% Seems more readable than
%A(n-1) - n & \textrm{if } A(n-1) > n \wedge \not\exists m < n: A(m) = A(n-1)-n \\
A(n-1) + n & \textrm{otherwise}
\end{cases}$$

The first few terms are 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11

To clarify, is new means whether the number is already in the sequence.

Given an integer n, via function argument or STDIN, return the first n terms of the Recamán sequence.

This is a code-golf challenge, so shortest code wins.


Recreate the sentence This challenge consists of two parts. The winner will be the solution with the lowest total byte count. The same language must be used for both challenges.

Part 1:

Write a function or program that takes a sentence with only valid words as input, and outputs a list of the used characters, the number of times each letter is used, and the number of letters in each of the words in the original sentence. The output from this program must be valid input to the next program (exactly as it is outputted)

I'll add examples and detailed rules further down.

Part 2:

Write a function or program that takes the output from the first program as input and uses this list of English words and recreates a sentence with the information from the output. The sentence doesn't have to be the same as the original sentence.

More information. rules and restrictions:

Part 1:

The first input can be on any suitable format, with or without quotation marks, as function argument or from STDIN, with or without brackets etc.
The input sentence will not contain any punctuation or special characters, except for a period/dot in the end. Except for the period symbol, all characters that are in the input will be in the word list.
The first letter of the sentence will be upper case, the rest will be lower case.
The output of part 2 must start with the same upper case letter as the original sentence (so converting the input to lower case is not recommended (but OK).
The output can be on any suitable format:

It must be possible to copy-paste the output directly into the next program / function
No alterations can be made when copy-pasting, the entire output must be copied and pasted as a whole, not in parts.
You may for instance output a histogram of all letters in the alphabet, or only the ones used (in general, whatever is necessary to complete part 2)
You can not output a list of characters where multiple occurrences are repeated. For instance, The queue can't yield an output: Teeehquu (3,5), it should be something like: Tehqu, (1 3 1 1 2),(3 5).

Part 2:

The program / function must accept the input exactly as is from part 1 (one exception, see comment below about taking file name as input.).

If surrounding brackets, quotation marks or similar are necessary to parse the input then these must be part of the output from part 1.

The word list can be found here.

The word list can either be saved locally as w.txt, or it can be fetched from the url. The url will only count as 5 bytes, so you don't need a url-shortener.
If the program can't open a file without reading the name as an input from STDIN (I believe this is was the case for Pyth at least), then the file name can be taken as a separate input argument.

The output must be only a sentence (list of valid words), ending with a period and an optional newline.

The output must have words with the same number of letters as the original sentence in part 1 (in correct order)
All the letters that were used in the original sentence must be used in the new output.
The sentence must start with the same upper case letter as the original input sentence and end with a period.

Both parts:

Neither of the parts should take more than 2 minutes to execute (randomly picking out words until a solution is reached is not accepted).

With the rules listed above, there should be a fair chance that the exact same sentence is reproduced, however that is not a requirement.

Examples:

In the below examples, a few different input and output formats are shown. Many more are accepted.

Part 1:

Input:

Zulus win.

Output type 1:

Z i l n s u w
1 1 1 1 1 2 1
5 3

Output type 2:

(('Z',1),('i',1),('l',1),('n',1),('s',1),('u',2),('w',1)), (5,2)

Output type 3:

'Zilnsuuw',[1,1,1,1,1,2,1],[5,2]

Part 2:

Input: An exact copy of the output from part 1.
Output:

Zulus win.

Note that other word combinations are accepted as long as they start with a Z, and the first word has 5 letters and the second has 3.

The shortest code in bytes win.

LabVIEW, 166 LabVIEW Primitives

First of all i did not create 2 seperate programms because Labview does dataflow so theres really no need.

Saves the histogramm with first element = ascii code of first letter rest from 1-26 go by amount. Lenght simply gets saved in an array.

The first word has 3 checks, first letter, lenght and available letters in histogram. The first letter check stops after the first word.

I check the histogram by decrementing it for every letter and checking if it would fall below 0.

If i found my Nth word and there are no words that are buildable from the left over letters i will start deleting words from the dictonary and redo the Nth word and so on until i have found a solution.

This might or might not work for sentences there are, since that would take forever to compute (my example took a few seconds already).

What i tried

In: Zulus win.
Out: Zulus win.

In: Dovecot flagships oleander.
Out: Dolphin advocates forelegs.

In: Abash abel mammal test.
Out: Amass abbe hamlet malt.


Fix my IPv4 address's missing periods Sometimes when I'm typing out an IPv4 address, I get all the numbers right, but I forget to type one or more periods. I'd like to have a program (or function) that takes my broken IPv4 address and outputs all possible valid placements of the missing periods.

Input

The input will always be a string that is a transformation of a valid IPv4 address (see particulars below). It will always have been transformed solely by the elimination of one or more period characters.

You submission does not need to handle inputs outside of this format.

Output

A collection or list, in no particular order or format, of strings representing all valid IPv4 addresses that can be created from the input by the insertion of period characters into the input.

The output may be a language-native list or other ordered or unordered collection type.
Alternatively, it may be a string sequence of IPv4 address delimited in some clear way.

If you use a single-character delimiter to delimit your string, periods and digits are not allowed as that single-character delimiter. I realize that, unlike numbers, periods as delimiters are not ambiguous (since every fourth period would necessarily be a delimiter) but for the sake of readability, I am disallowing it.

IPv4 address format

While IPv4 addresses are really just a sequence of four binary octets, this challenge uses a restricted dotted decimal format.

An IPv4 address is a four decimal values separated by three periods.
Each of the four values are in the range 0 to 255, inclusive.
Leading zeros are not allowed in any number value. (Standalone one-character 0 is allowed; any other number beginning with a zero is not: 052, 00, etc.)

Test Cases

Input is on the first line, output on second line (here, structured as a comma-separated list of quoted strings, separated by commas, surrounded by [ ], but you may use any reasonable format or structure, as specified above). Some examples have notes on a third line to highlight the application of a particular rule.

192.168.1234
["192.168.1.234", "192.168.12.34", "192.168.123.4"]

192.1681234
["192.16.81.234", "192.168.1.234", "192.168.12.34", "192.168.123.4"]
(Note: 192.1681.2.34 (etc.) is illegal because 1681 is greater than 255)

1921681.234
["19.216.81.234", "192.16.81.234", "192.168.1.234"]

1921681234
["19.216.81.234", "192.16.81.234", "192.168.1.234", "192.168.12.34", "192.168.123.4"]

192.168.1204
["192.168.1.204", "192.168.120.4"]
(Note: 192.168.12.04 is illegal because of leading zero)

192.168.123
["1.92.168.123", "19.2.168.123", "192.1.68.123", "192.16.8.123", "192.168.1.23", "192.168.12.3"]

192.168.256
["192.168.2.56", "192.168.25.6"]
(Note: Any combination that would leave 256 intact is illegal)

120345
["1.20.3.45", "1.20.34.5", "1.203.4.5", "12.0.3.45", "12.0.34.5", "120.3.4.5"]
(Note: 12.03.4.5 (etc.) is illegal due to leading zero.)

012345
["0.1.23.45", "0.1.234.5", "0.12.3.45", "0.12.34.5", "0.123.4.5"]
(Note: the first segment must be 0, because `01` or `012` would be illegal.)

000123
["0.0.0.123"]

(I made these examples by hand, so please alert me to any mistakes you may find.)

C (gcc/linux), 125 121 bytes

i;f(char*a){do{char*y=a,s[99],*x=inet_ntop(2,&i,s,99);for(;*x&&!(*x^*y&&*x^46);++x)y+=*x==*y;*x|*y||puts(s);}while(++i);}

Loops over all possible IPv4 addresses, and does a custom comparison that skips over extra dots in the generated ip address (but not in the main comparison address) to decide whether to print or not. Very slow, but should finish within 1 hour on a reasonable PC.


Universal (rule-bending) Code Golf solver Code golf always involves some answers that bend the rules more or less by breaking constraints that the challengers took for granted or just haven't thought about and didn't list in the rules. One of these interesting loopholes is the possibility to output more than the challenge asks for to get a better result.

Taking this to extremes, we can write an universal code golf solver that prints the desired output — if you don't care that it might take ages and outputs lots of other stuff before and after it.

All we need to output is a sequence that is guaranteed to contain every possible subsequence. For this code golf, this will be the Ehrenfeucht-Mycielski sequence:

  The sequence starts with the three bits 010; each successive digit is
  formed by finding the longest suffix of the sequence that also appears
  earlier within the sequence, and complementing the bit following the
  most recent earlier appearance of that suffix.

  Every finite subsequence of bits occurs contiguously, infinitely often
  within the sequence

  The first few digits of the sequence are:

    010011010111000100001111... (sequence A038219 in OEIS).

Combining 8 bits of the sequence to a byte, we'll get ASCII output that we can output to the screen or to a file and that contains every possible finite output. The program will output parts of pi, the lyrics of “Never gonna give you up”, some nice ASCII art, its own source code, and everything else you could want it to output.

For testing correctness, here are hashes for the first 256 bytes of the sequence:

MD5: 5dc589a06e5ca0cd9280a364a456d7a4
SHA-1: 657722ceef206ad22881ceba370d32c0960e267f

The first 8 bytes of the sequence in hexadecimal notation are:

4D 71 0F 65 27 46 0B 7C

Rules:

Your program must output the Ehrenfeucht-Mycielski sequence (nothing else), combining 8 bits to a byte/ASCII character.
Shortest program (character count) wins. Subtract 512 from your character count if you manage to generate the sequence in linear time per generated byte.

C, –110 chars

This version of the program uses the linear-runtime algorithm to generate the sequence. Subtracting 512 from the 402 chars in the program gives a total of negative 110.

#define C v=calloc(7,8),v->p=p
#define G(F,K)u->F[d[K]]
#define S(F,T)G(f,T)=F,G(t,T)=T,G(n,T)=
struct{int p,f[2],t[2];void*n[2];}r,*u,*v,*w;char*d,c;p,b,h,i,j,k;
main(s){for(;d=++p-s?d:realloc(d,s*=2);){d[i=p]=b;c+=c+b;p%8||putchar(c);
for(u=&r;b=u->p,u->p=p,w=G(n,k=i);S(i,k)v=G(n,k),u=v)for(h=G(f,k),j=G(t,k);j>h;--i,--j)
if(d[i]-d[j]){S(i,k)C;u=v;S(h,j)w;S(0,i)C;b=w->p;goto x;}S(0,i)C;x:b=1-d[b+1];}}

As per the problem, the program runs in an infinite loop, which necessitates lots of memory allocation, and using realloc() to keep the sequence contiguous can contribute to heap fragmentation. You can improve the program's memory usage by replacing calloc(7,8) on the first line with calloc(1,sizeof*v). This will help especially on a 32-bit machine, where 56 is likely too large by a factor of two.

The code is kind of unreadable, and not in an interesting way; for that I apologize. Frankly, even the ungolfed version isn't terribly clear:

#include <stdio.h>
#include <stdlib.h>

typedef struct branch branch;
typedef struct node node;

struct branch {
    int from, to;
    node *next;
};

struct node {
    int pos;
    branch br[2];
};

static node root = { 0 };

static unsigned char *data = NULL;
static int endpos = 0;
static int size = 1;

static node *mknode(void)
{
    node *n;

    n = calloc(1, sizeof *n);
    n->pos = endpos;
    return n;
}

static branch *getbranch(node *n, int p)
{
    return &n->br[data[p]];
}

static void setbranch(node *n, int from, int to, node *next)
{
    n->br[data[to]].next = next;
    n->br[data[to]].from = from;
    n->br[data[to]].to = to;
}

int main(void)
{
    node *u, *v, *w;
    int follower, from, i, i0, j;
    int out, b;

    out = b = 0;
    for (;;) {
        ++endpos;
        if (endpos == size) {
            size *= 2;
            data = realloc(data, size);
        }
        data[endpos] = b;
        out = (out << 1) | b;
        if (endpos % 8 == 0) {
            putchar(out);
            out = 0;
        }

        i = endpos;
        u = &root;
        for (;;) {
            follower = u->pos + 1;
            u->pos = endpos;
            w = getbranch(u, i)->next;
            if (!w)
                break;
            i0 = i;
            from = getbranch(u, i0)->from;
            for (j = getbranch(u, i0)->to ; j > from ; --j) {
                if (data[i] != data[j]) {
                    /* divide branch */
                    v = mknode();
                    setbranch(u, i, i0, v);
                    u = v;
                    setbranch(u, from, j, w);
                    setbranch(u, 0, i, mknode());
                    follower = w->pos + 1;
                    goto bitfound;
                }
                --i;
            }
            v = getbranch(u, i0)->next;
            setbranch(u, i, i0, v);
            u = v;
        }
        /* extend branch */
        setbranch(u, 0, i, mknode());

      bitfound:
        b = 1 - data[follower];
    }
}

(The ungolfed code above is based on the code written by Grzegorz Herman and Michael Soltys, as referenced in the problem description, and from Soltys' home page.)

Thanks to @schnaader and @r.e.s. for reporting a bug in the initial version.


Black and White Rainbows Given an image that has only black and white pixels and an (x,y) location that's a white pixel, color the white pixels based on their minimal Manhattan distance from (x,y) in a path that only involves traversing other white pixels.
The hue of the colored pixels must be proportional to their distance from (x,y), so the pixel at (x,y) will have a hue of 0° (pure red) and the pixels farthest away from (x,y) will have a hue of 360° (also red), with the other hues blending seamlessly and linearly in between. The saturation and value must both be 100%.
If a white pixel is not connected to (x,y) through other white pixels then it must remain white.
Details

The input will consist of the file name of the image or the raw image data, plus the x and y integers.
The output image may be saved to a file or piped raw to stdout in any common image file format, or simply displayed.
The x value is 0 on the leftmost pixels, and increases going right. The y value is 0 in the topmost pixels and increases going down. (x,y) will always be in the image bounds.
Both full programs and functions are allowed.

The shortest code in bytes wins.
Examples
All these images have been downsized to save space. Click them to view at full size.
Input image:

(x,y) = (165,155) and (x,y) = (0,0)

Input image and output with (x,y) = (0,0):

Input image and output with (x,y) = (600,350):

Input image and output with (x,y) = (0,0):

Input image and output with (x,y) = (0,0):

Optional -30% bonus: use Euclidean distance. A suggestion for your algorithm is as follows (general outline):

Have a start pixel.
Flood-fill from that pixel.
For every pixel reached in the flood fill,
Move from the start pixel to that pixel in half-unit steps, in a straight line.
At each step, apply int() to the x and y coordinates. If the pixel at these coordinates is black, stop. Otherwise, continue. (This is a line-of-sight method.)
Any reached pixel that borders a white pixel and/or a pixel that was previously labeled with a significantly higher distance (i.e., +10) becomes a start pixel.

In a more meta sense, this algorithm spreads out to every pixel reachable in a straight line from start/already-colored pixels, then "inches" around edges. The "significantly higher distance" bit is intended to speed up the algorithm. Honestly, it doesn't really matter how you implement Euclidean distance, it just has to look pretty much like this.
This is what the first example looks like with Euclidean distance, using the algorithm above:
Input image and (x,y) = (165,155)

Many thanks to Calvin'sHobbies and trichoplax for helping write this challenge! Have fun!

Matlab, 255 245 231 bytes
This expects the image name first, then y and then x.
I=@input;i=imread(I('','s'));[r,c]=size(i);m=zeros(r,c);m(I(''),I(''))=1;M=m;d=m;K=[1,2,1];for k=1:r*c;d(m&~M)=k;M=m;m=~~conv2(m,K'*K>1,'s');m(~i)=0;end;z=max(d(:));v=[1,1,3];imshow(ind2rgb(d,hsv(z)).*repmat(m,v)+repmat(~d&i,v),[])

I implemented the flood filling (or 'dijkstra for 4-neighbourhoods' if you want) roughly by first creating a mask where the seed pixel is set to 1 and with a distance accumulator (both of the size of the image) and then repeating following steps:

convolute the mask with a 4 neighbourhood kernel (this is the very inefficient part)
set all nonzero pixels of the mask to 1
set all the black pixels of the image to zero
set all values in the accumulator where the mask has changed in this step to k
increase k
repeat until there are no more changes in the mask (I actually do not check this condition, but just use the number of pixels in the image as an upper bound, which is usually a very bad upper bound, but this is codegolf=)

This leaves us with the manhattan distances of every pixel to the seed pixel in the distance accumulator. Then we create a new image by going throu the given range of colours and map the "first" hue to the value zero and the "last" hue to the maximal distance.
Examples

As a bonus, here a pretty picture of how the distance gets calculated. brighter = farther away.


Give a permutation with no two consecutive integers next to each other Challenge

Given an integer n ≥ 4, output a permutation of the integers [0, n-1] with the property that no two consecutive integers (integers with absolute difference 1) are next to each other.

Examples

4 → [1, 3, 0, 2]
5 → [0, 2, 4, 1, 3]
6 → [0, 2, 4, 1, 3, 5]
7 → [0, 2, 4, 1, 5, 3, 6]

You may use 1-indexing instead (using integers [1, n] instead of [0, n-1]).

Your code must run in polynomial time in n, so you can't try all permutations and test each one.

Jelly, 3 2 bytes

ḂÞ

Sorts the integers in [1, ..., n] by their LSB.

Try it online!


Is it a Diff or not? Your program will be run an undetermined amount of times. On all but the last, there will be a file called data in the same directory of your program that has the same value each time. On the last run, the file will be there but will have different data in it. On all the times except the last, you can do whatever you want, as long as the following rules are met:

Don't output anything
Don't change data file

On the last run, you must print out the diff of the first data file and the current data file.

Rules:

You may save whatever you want in any files you want, just don't edit the data file

Scoring:

Lowest char score wins

Cheating encouraged. You have no indication of which run you're in except that the data file is changed.

Bash (31)

[ -e x ]&&diff data x;cp data x

Kinda obvious.


Alphabet without the alphabet You are tasked with displaying the string "ABCDEFGHIJKLMNOPQRSTUVWXYZ" and only that, except for trailing newlines if they're unavoidable.

You must not output any homoglyphic characters like Cyrillic A. You can use non-Unicode encodings, but just to be sure, only output the Latin letters.

Regardless of the encoding you pick, you must not use the characters from U+0041 to U+005A or from U+0061 to U+007A in your source.

No other cheats or loopholes are allowed.

This is a code golf challenge, so the shortest answer wins. However, I won't pick a winner answer since the shortest answer might change over time.

brainfuck, 35 bytes

+++++++++++++[>++>+++++<<-]>[>.+<-]

Try it online!

This is the first language I thought of because it is really good for no-letter no-number challenges lol.


Verify a solution for Conway Immobilizer Background

Conway immobilizer problem is a puzzle that reads like the following:

  Three positions, "left," "middle," and "right," are marked on a table.
  Three cards, an ace, a king, and a queen, lie face up in some or all
  three of the positions. If more than one card occupies a given
  position then only the top card is visible, and a hidden card is
  completely hidden; that is, if only two cards are visible then you
  don't know which of them conceals the missing card.

  Your goal is to have the cards stacked in the left position with the
  ace on top, the king in the middle, and the queen on the bottom. To do
  this you can move one card at a time from the top of one stack to the
  top of another stack (which may be empty).

  The problem is that you have no short-term memory, so you must design
  an algorithm that tells you what to do based only on what is currently
  visible. You can't recall what you've done in the past, and you can't
  count moves. An observer will tell you when you've succeeded. Can you
  devise a policy that will meet the goal in a bounded number of steps,
  regardless of the initial position?

The puzzle has got its name because it's said to have immobilized one solver in his chair for six hours.

The link above gives one possible answer (marked as spoiler for those who want to solve it by themselves):

   If there’s an empty slot, move a card to the right (around the
 corner, if necessary) to fill it. Exception: If the position is
 king-blank-ace or king-ace-blank, place the ace on the king.

 If all three cards are visible, move the card to the right of the
 queen one space to the right (again, around the corner if
 necessary). Exception: If the queen is on the left, place the king on
 the queen.

All solutions to the Immobilizer Problem (pdf) uses graph theory to show that there are 14287056546 distinct strategies that solve the problem.

Task

Given a strategy for Conway Immobilizer, determine if the strategy actually solves it, i.e. given any initial configuration, repeating the strategy will eventually place all cards into the winning state.

A strategy (the input) can be in any format that represents a set of pairs current visible state -> next move for every possible current visible state. A visible state represents what is visible on each of three slots (it can be one of A/K/Q or empty). A move consists of two values A, B which represents a move from slot A to slot B.

The input format can be e.g. a list of pairs, a hash table, or even a function, but it should not involve any external information, e.g. you cannot encode a "move" as a function that modifies the full game state (entire stacks of cards). You can use any four distinct values for A/K/Q/empty (the visible state of each slot) and three distinct values for left/middle/right (to represent a move from a slot to another).

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

Input: the solution above
Output: True

Input: the solution above, but the exception on 'K.A' is removed
       (at 'K.A', move K to the right)
Output: False ('QKA' -> 'K.A' -> 'QKA')

Input: if only one card is visible, move it to the right
       if Q and K are visible, move K on the top of Q
       if K and A are visible, move A on the top of K
       otherwise, move A to the empty slot
Output: False ('..A' where Q, K, A are stacked -> 'A.K' -> '..A')

JavaScript (ES7),  229 224  213 bytes
Input: a function (the solver) expecting an array of 3 values among 'Q', 'K', 'A' or undefined for empty, and returning a move as a pair [from, to] (0-indexed)
Output: 0 or 1

f=(F,n=162)=>!n--||(g=s=>(s[k=s.join`/`]^=1)?/A,K,/.test(k)|g(s,[x,y]=F(s.map(a=>a[0])),s[y].unshift(s[x].shift())):0)([0,1,2].map(i=>s[n/3**i%3|0].push('QKAKQAAQKQAKKAQAKQ'[3*~~(n/27)+i]),s=[[],[],[]])&&s)&f(F,n)

Try it online!


Egg dropping contest Your challenge:
You are on the 0th floor of a infinitely tall building. At any floor, you can walk to the window and drop an egg.  Your goal is to figure out the highest floor that the egg can withstand without breaking.  However, you have a maximum of 3 eggs to use to figure this out, but you need to minimize the number of tries.
In formal terms:

You are given a function f(n) which returns bool(n <= X) for an unknown X, where 0 <= X
You must return the value of X (without accessing it directly)
f(n) must only return False a maximum of 3 times (in a single test case).  If it returns False more than that, then your answer is disqualified.

Restrictions
Your score is the total number of calls you make to f(n) (in the test cases below)
If you wish, you may forgo passing in a function, and simply "simulate" the above situation.  However, your solving algorithm must know nothing of X.
Your algorithm should not hard code the test cases, or a maximum X.  If I were to regenerate the numbers, or add more, your program should be able to handle them (with a similar score).
If your language doesn't support arbitrary precision integers, then you may use the long datatype.  If your language doesn't support either, then you are out of luck.
The nth test case is generated using the following:
g(n) = max(g(n-1)*random(1,1.5), n+1), g(0) = 0, or approximately 1.25^n
Test cases:
0,1,2,3,4,6,7,8,10,14,15,18,20,27,29,40,57,61,91,104,133,194,233,308,425,530,735,1057,1308,1874,2576,3162,3769,3804,4872,6309,7731,11167,11476,15223,15603,16034,22761,29204,35268,42481,56238,68723,83062,95681,113965,152145,202644,287964,335302,376279,466202,475558,666030,743517,782403,903170,1078242,1435682,1856036,2373214,3283373,4545125,6215594,7309899,7848365,8096538,10409246,15103057,20271921,22186329,23602446,32341327,33354300,46852754,65157555,93637992,107681394,152487773,181996529,225801707,324194358,435824227,579337939,600264328,827690923,1129093889,1260597310,1473972478,1952345052,1977336057,2512749509,3278750235,3747691805,5146052509

This is a code-challenge, and the person with the lowest score wins!


Implement my method of adding numbers mentally Note: This challenge has been changed to eliminate the strict whitespace manipulation requirements that made this challenge low-quality. Some rules regarding whitespace have been changed.

I'm rather good at mental math, particularly adding positive integers in my head. Here is my method for adding the numbers together (n is a positive integer):

Arrange the numbers in a horizontal row
Reorder the numbers so the 2n-1th number in the sequence is the nth smallest number in the sequence and the 2nth number in the sequence is the nth largest number in the sequence.
Add the 2n-1th number to the 2nth number. Print the results of these additions on the next line.
Repeat the previous step until a final result is obtained.

Your challenge is to write a program or function that prints each of the above steps until the sum of all the inputted numbers is reached. The final result must be separated from the adding steps by an additional blank newline. You may assume that all numbers inputted are unique so as to avoid confusion with the second step (and that the input is not empty). Numbers can be inputted in any format. Numbers in rows should be separated from each other by one space.

Test cases

For each of these, the input and output start a newline after their labels.

Case 1

Input:
314 495 767 214 141

Output:
141 767 214 495 314   //Reordering the input
908 709 314           //Adding
1617 314

1931                  //Final result

Case 2

Input:
884

Output:
884   //Reordering the input

884   //Final result

Note that there is no adding step here because the reordering of the input produces the final result.

Case 3

Input:
5033 7825 2167 6374 5050 5389 3915 7231 3025 1954 7249 5143 7567 9857 462 3504 6165 6681 6361 6367

Output:
462 9857 1954 7825 2167 7567 3025 7249 3504 7231 3915 6681 5033 6374 5050 6367 5143 6361 5389 6165
10319 9779 9734 10274 10735 10596 11407 11417 11504 11554
20098 20008 21331 22824 23058
40106 44155 23058
84261 23058

107769

This is code golf. Standard rules apply. Answer with the fewest bytes wins.


Difference of expressions when evaluated in different orders We all know the standard order of operations for math functions
(PEMDAS),
but what if we instead evaluated expressions left-to-right?

The Challenge

Given a string through standard input or through command line args, find the difference between the traditional evaluation (PEMDAS) and the in-order (left-to-right) evaluation of that expression.

Details

You will be given a string in a format such as:

"1 + 2 * 3 ^ 2 - 11 / 2 + 16"

To simplify things, there will be:

a space between each number and operator
no leading or trailing spaces
no decimal numbers or negative numbers (non-negative integers only)
no operators beyond +(plus), -(minus), *(multiply), /(divide), ^(exponentiation)
no parens to worry about
you may remove the spaces if it's easier for you to handle, but no other modification of the input format will be allowed.

You must provide the absolute value of the difference between the two evaluations of the string
Your division can either be floating-point or integer division - both will be accepted
Your program can not use any sort of expression evaluation library.

To clarify - any sort of built-in eval function in which your language evaluates a string that is valid code for the same language IS acceptable
Explanations of your code are preferred
Shortest code by byte count wins
Winner will be chosen Saturday (July 19, 2014)

Examples:

A: 1 + 2 * 3 ^ 2 - 11 / 2 + 16 (using floating-point division)

In traditional order of operations:

1 + 2 * 3 ^ 2 - 11 / 2 + 16   -->   1 + 2 * 9 - 11 / 2 + 16   -->

1 + 18 - 5.5 + 16             -->   29.5

In-order traversal yields:

1 + 2 * 3 ^ 2 - 11 / 2 + 16   -->   3 * 3 ^ 2 - 11 / 2 + 16   -->

9 ^ 2 - 11 / 2 + 16           -->   81 - 11 / 2 + 16          -->

70 / 2 + 16                   -->   35 + 16                   -->

51

Resulting difference: 51 - 29.5 = 21.5

B: 7 - 1 * 3 ^ 2 + 41 / 3 + 2 * 9 * 2  (using integer division)

In traditional order of operations:

7 - 1 * 3 ^ 2 + 41 / 3 + 2 * 9 * 2   -->   7 - 1 * 9 + 41 / 3 + 2 * 9 * 2   -->

7 - 9 + 13 + 18 * 2                  -->   7 - 9 + 13 + 36                  -->

47

In-order traversal yields:

7 - 1 * 3 ^ 2 + 41 / 3 + 2 * 9 * 2   -->   6 * 3 ^ 2 + 41 / 3 + 2 * 9 * 2   -->

18 ^ 2 + 41 / 3 + 2 * 9 * 2          -->   324 + 41 / 3 + 2 * 9 * 2         -->

365 / 3 + 2 * 9 * 2                  -->   121 + 2 * 9 * 2                  -->

123 * 9 * 2                          -->   1107 * 2                         -->

2214

Resulting difference: 2214 - 47 = 2167

Haskell, 281 256 characters

(x:o:y:z)%p|p o=(show(m o(read x)$read y::Float):z)%p|1<3=x:o:(y:z)%p;z%_=z
m"+"=(+);m"-"=(-);m"*"=(*);m"/"=(/);m"^"=(**);m _= \a->abs.(a-)
l=(%(\_->1<3))
t e=foldl(%)e$map(\w->(`elem`w).head)["^","*/","+-"]
d e=l$l e++"~":t e
main=interact$concat.d.words

Brief explaintaion:

% reduces an expression, so long as the operator meets some predicate p
show(m o(read x)$read y::Float) applies an operator to the two string arguments, producing a string result
m maps a string to an operator; note the string "~" is mapped to absolute difference
l computes left-to-right order by applying % once, with a predicate that is always true
t computes traditional order by repeatedly applying % with tests that match operators first of higher precedence, then lower
d computes the two values, then forms a new expression with operator ~ and computes that

Runs:

& echo "1 + 2 * 3 ^ 2 - 11 / 2 + 16" | runhaskell 34599-EvalOrder.hs
21.5

& echo "7 - 1 * 3 ^ 2 + 41 / 3 + 2 * 9 * 2" | runhaskell 34599-EvalOrder.hs
2178.3333

(Second result differs from example above because this code always computes in floating point.)


Code golf edit distance 2 The edit distance between two strings is the minimum number of single character insertions, deletions and substitutions needed to transform one string into the other.

This task is simply to write code that determines if two strings have edit distance exactly 2 from each other.  The twist is that your code must run in linear time. That is if the sum of the lengths of the two strings is n then your code should run in O(n) time.

Example of strings with edit distance 2.

elephant elepanto
elephant elephapntv
elephant elephapntt
elephant lephapnt
elephant blemphant
elephant lmphant
elephant velepphant

Examples where the edit distance is not 2. The last number in each row is the edit distance.

elephant elephant 0
elephant lephant 1
elephant leowan 4
elephant leowanb 4
elephant mleowanb 4
elephant leowanb 4
elephant leolanb 4
elephant lgeolanb 5
elephant lgeodanb 5
elephant lgeodawb 6
elephant mgeodawb 6
elephant mgeodawb 6
elephant mgeodawm 6
elephant mygeodawm 7
elephant myeodawm 6
elephant myeodapwm 7
elephant myeoapwm 7
elephant myoapwm 8

You can assume the input strings have only lower case ASCII letters (a-z).

Your code should output something Truthy if the edit distance is 2 and Falsey otherwise.

If you are not sure if your code is linear time, try timing it with pairs of strings of increasing length where the first is all 0s and the second string is one shorter with one of the 0s changed to a 1.  These all have edit distance 2. This is not a good test of correctness of course but a quadratic time solution  will timeout for strings of length 100,000 or more where a linear time solution should still be fast.

Retina 0.8.2, 76 58 bytes

^(.*)(.*¶)\1
$2
(.*)(¶.*)\1$
$2
^.?¶.?$

^.?(.*).?¶.?\1.?$

Try it online! Takes the two strings on separate lines, but link includes test suite which takes space-separated strings instead, so that I can easily use the test cases. Explanation:

^(.*)(.*¶)\1
$2

Delete the common prefix.

(.*)(¶.*)\1$
$2

Delete the common suffix.

^.?¶.?$

Ignore an edit distance of less than two.

^.?(.*).?¶.?\1.?$

Check that only the first and last characters have been edited, so that the edit distance cannot be greater than two in this case.

From a code golf point of view this can be done in 51 bytes but then the regex becomes unbearably slow to execute for longer strings:

^(?!(.*).?(.*)¶\1.?\2$)(.*).?(.*).?(.*)¶\3.?\4.?\5$

Try it online! Takes the two strings on separate lines, but link includes test suite which takes space-separated strings instead, so that I can easily use the test cases. Explanation:

^

Match the whole input.

(?!(.*).?(.*)¶\1.?\2$)

Don't match strings with an edit distance less than two.

(.*).?(.*).?(.*)¶\3.?\4.?\5$

Match strings with an edit distance less than three.


Substandard deviation The mean of a population \$(x_1,\dots,x_n)\$ is defined as \$\bar x=\frac1n\sum_{i=1}^n x_i\$. The (uncorrected) standard deviation of the population is defined as \$\sqrt{\frac1n\sum (x_i-\bar x)^2}\$. It measures how dispersed the population is: a large standard deviation indicates that the values are far apart; a low standard deviation indicates that they are close. If all values are identical, the standard deviation is 0.
Write a program or function which takes as input a (non-empty) list of non-negative integers, and outputs its standard deviation. But check the scoring rule, as this is not code golf!
Input/Output
Input/Output is flexible. Your answer must be accurate to at least 2 decimal places (either rounding or truncating). The input is guaranteed to contain only integers between 0 and 255, and to not be empty.
Scoring
To compute your score, convert your code to integer code points (using ASCII or whatever code page is standard for your language) and compute the standard deviation. Your score is the number of bytes in your code multiplied by the standard deviation. Lower score is better. You should therefore aim for code which at the same time (a) is short and (b) uses characters with close codepoints.
Here is an online calculator to compute your score (assuming you use ASCII).
Test cases
Input              | Output
77 67 77 67        | 5
82                 | 0
73 73 73           | 0
83 116  97 116 115 | 13.336

A word of caution about built-ins: if your language has a built-in, that's fine (and good for you if it only uses one character!). But make sure that it uses \$n\$ and not  \$n-1\$ as the denominator in the formula, or else your answer won't be valid.

MATL, score 65.30697
tYmhZs

Try it online! Or verify all test cases.
How it works
The built-in function Zs with its default arity (1 input, 1 output) computes the corrected standard deviation:
\$\sqrt{\frac 1 {n-1}\sum (x_i-\bar x)^2}\$
The uncorrected standard deviation can be obtained with the 2-input version of Zs: 1&Zs, where 1 as second input means uncorrected. l or T could be used instead of 1 to reduce the score, but & is very far from the other characters. 2$ or H$ could be used instead of &, but $ is even farther.
So it is better to use the default version of Zs (corrected standard deviation) on the input with its mean appended. This increases the input length by 1 and contributes 0 in the numerator, which causes the corrected standard deviation to become uncorrected.
t     % Implicit input: numeric vector. Duplicate
Ym    % Mean
h     % Concatenate the input vector with its mean
Zs    % Corrected standard deviation


Generate four type-4 GUIDs for me The type 4 GUID is described by Wikipedia, quoth:

  Version 4 UUIDs use a scheme relying only on random numbers. This algorithm sets the version number (4 bits) as well as two reserved bits. All other bits (the remaining 122 bits) are set using a random or pseudorandom data source. Version 4 UUIDs have the form xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx where x is any hexadecimal digit and y is one of 8, 9, A, or B (e.g., f47ac10b-58cc-4372-a567-0e02b2c3d479).

Write a program that loads 488 bits (61 bytes) of cryptographic quality randomness and output them as 4 GUIDs using the format quoted above.

Do not waste randomness.

All random bits must appear in the encoded output.
All encoded bits must be traceable to either a single random bit or one of the six fixed bits that must appear in each GUID.

Use the cryptographic quality random number generator supplied by your language's standard library.
Do not use a library or external resource that generates GUIDs.
The hyphens must appear in their correct positions.
The fixed bits of this form of GUID must appear in their correct positions.
You may use a standard library function designed to output a GUID from 128 bits.
Normal code-golf rules apply.

For example...

> gentype4
6FA53B63-E7EA-4461-81BE-9CD106A1AFF8
856970E9-377A-458E-96A7-43F587724573
E4F859AC-0004-4AA1-A3D2-AECB527D1D24
766811C5-0C44-4CC8-8C30-E3D6C7C6D00B

Update:
I asked for four GUIDs in order to allow a whole number of random bytes to be gathered without leaving any remainder. I also specified that none of the bits should be wasted in order to avoid the easy answer of getting 16 random bytes and dropping the 4 in. (No, shift the other bits along first.)

Update 2:
If your language's standard library doesn't have a cryptographic quality random byte generator, you may instead assume that there is a 61 byte file present with enough random bytes for you to use when the program starts. The file should be called "/dev/urandom" or another filename with 12 characters.


Mark My Mail! - ASCII Barcodes 4-state barcodes

Many postal services (Royal Mail UK, Canada Post, US Mail, etc) use a 4-state barcode to encode information about their mail. Rendered in ASCII, it may look something like this:

|   | |   | | | |   |     |   |
| | | | | | | | | | | | | | | | |
    | |   |   | | |   |     |

A 4-state barcode is a row of bars. Each bar can be extended upwards, downwards, or both, allowing 4 possibilities. This means that each bar essentially represents a base 4 digit:

            |       |
Bar:    |   |   |   |
                |   |

Digit:  0   1   2   3

The problem with this symbology is that it each barcode is a valid, different barcode upside down: drastically changing the meaning if the orientation is incorrect. Therefore, a start and stop sequence are normally implemented so the scanner can calculate which way it is supposed to be read.

For the purpose of this challenge, we will be using the start/stop sequence specified by Australia Post: each barcode begins and ends with a 1 0 sequence.

The Challenge

Your task is to write a program or function which, given a positive integer N, converts it to an ASCII 4-state barcode, where each bar (except for the start/stop sequences) represents a digit in the base-4 representation of N.

Example:

Given the integer 19623, we would first convert it to its base-4 representation, 10302213.

We would then map each digit to the corresponding bar:

1 0 3 0 2 2 1 3

|   |       | |
| | | | | | | |
    |   | |   |

Finally, we would add the start/stop sequences:

Start:              End:
1 0                 1 0

|   |   |       | | |
| | | | | | | | | | | |
        |   | |   |

The resulting barcode should be the program's output.

Rules:

The input will be a positive integer, within the range of your language's standard integer size.
The output:

May be either a list of lines, or a string containing newlines.
May contain leading or trailing newlines/spaces, as long as the shape remains intact.
Should show the barcode with the above format - it must use the pipe character (|) and space character () when drawing bars, and there should be 1 space in between each upright bar.

This is code-golf, so the shortest program (in bytes) wins!

Test Cases

4095:

|   | | | | | | |
| | | | | | | | | |
    | | | | | |

4096:

|   |             |
| | | | | | | | | | |

7313145:

|   |   | |   | |   | |   | |
| | | | | | | | | | | | | | | |
      | | | |     | | | |

MATL, 34 30 29 28 bytes
TFiK_YAyhhH&\EQE+t~vB!P'|'*c

Try it online!
Explanation
TF      % Push array [1 0] (start sequence)
i       % Push input
K_YA    % Convert to base 4. Gives an array of 4-ary digits
y       % Duplicate from below: pushes [1 0] again (stop sequence)
hh      % Concatenate horizontally twice. Gives array of 4-ary digits
        % including start and stop sequences
H&\     % Two-output modulo 2: pushes array with remainders and array
        % with quotients of dividing by 2
EQE     % Times 2, plus 1, times 2, element-wise. This effectively
        % multiplies each entry by 4 and adds 2
+       % Add element-wise to the array of remainders. The stack now
        % contains an array of numbers 2, 3, 6 or 7. Each number
        % encodes, in binary form, a column of the output. The
        % previous multiplication of the quotients by 4 will have the
        % effect of shifting one row down (one binary digit upwards),
        % to make room for the central row. The addition of 2 will
        % create the central row, which is always full
t~      % Duplicate, logical negate. Gives an array of zeros of the
        % same length
v       % Concatenate vertically into a 2-row matrix
B       % Convert to binary. Gives a matrix, where each row is the
        % binary representation of one of the numbers of the input
        % matrix, read in column-major order
!P      % Transpose, flip vertically
'|'*    % Multiply by '|'. This transforms 1 into 124 (ASCII code of
        % '|') and leaves 0 as is
c       % Convert to char. Char 0 is shown as space. Implicitly display


Is this a submatrix? This is the 2-dimensional generalisation of this challenge.

For our purposes, one matrix (or 2D array) A is considered a submatrix of another matrix B, if A can be obtained by completely removing a number of rows and columns from B. (Note: some sources have different/more restrictive definitions.)

Here's an example:

A = [1 4      B = [1 2 3 4 5 6
     2 1]          6 5 4 3 2 1
                   2 1 2 1 2 1
                   9 1 8 2 7 6]

We can delete columns 2, 3, 5, 6 and rows 2, 4 from B to obtain A:

B = [1 2 3 4 5 6         [1 _ _ 4 _ _         [1 4  = A
     6 5 4 3 2 1   -->    _ _ _ _ _ _   -->    2 1]
     2 1 2 1 2 1          2 _ _ 1 _ _
     9 1 8 2 7 6]         _ _ _ _ _ _]

Note that A is still a submatrix of B if all rows or all columns of B are retained (or in fact if A = B).

The Challenge

You guessed it. Given two non-empty integer matrices A and B, determine if A is a submatrix of B.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

Input may be in any convenient format. The matrices can be given as nested lists, strings using two different separators, flat lists along with the dimensions of the matrix, etc, as long as the input is not pre-processed. You may choose to take B first and A second, as long as your choice is consistent. You may assume that the elements of the matrices are positive and less then 256.

Output should be truthy if A is a submatrix of B and falsy otherwise. The specific output value does not have to be consistent.

Standard code-golf rules apply.

Test Cases

Each test case is on a separate line, A, B.

Truthy cases:

[[1]], [[1]]
[[149, 221]], [[177, 149, 44, 221]]
[[1, 1, 2], [1, 2, 2]], [[1, 1, 1, 2, 2, 2], [3, 1, 3, 2, 3, 2], [1, 1, 2, 2, 2, 2]]
[[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[1, 2, 3], [4, 7, 6], [7, 8, 9], [1, 2, 3], [4, 5, 6], [7, 8, 9]]
[[228, 66], [58, 228]], [[228, 66], [58, 228]]
[[1, 2], [2, 1]], [[1, 2, 2], [2, 1, 2], [2, 2, 1]]
[[136, 196], [252, 136]], [[136, 252, 210, 196, 79, 222], [222, 79, 196, 210, 252, 136], [252, 136, 252, 136, 252, 136], [180, 136, 56, 252, 158, 222]]

Falsy cases:

[[1]], [[2]]
[[224, 15]], [[144, 15, 12, 224]]
[[41], [150]], [[20, 41, 197, 150]]
[[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[1, 2, 3], [7, 8, 9], [4, 5, 6]]
[[1, 2, 2], [2, 1, 2], [2, 2, 1]], [[1, 2], [2, 1]]
[[1, 2, 2], [2, 1, 2]], [[1, 2], [2, 1], [2, 2]]
[[1, 2], [3, 4]], [[5, 3, 4, 5], [2, 5, 5, 1], [4, 5, 5, 3], [5, 1, 2, 5]]
[[158, 112], [211, 211]], [[158, 211, 189, 112, 73, 8], [8, 73, 112, 189, 211, 158], [211, 158, 211, 158, 211, 158], [21, 158, 199, 211, 212, 8]]

Pyth, 10 bytes

}CQsyMCMyE

Test suite

This is fairly straightforward. First, we consider B as a list of rows, and take all subsets using yE. Then, each of those matrices is transposed with CM, and all subsets are taken of their rows, with yM. Concatenating these sublists with s gives all possible transposed submatrices. So we transpose A with CQ, and check if it is present with }.


Cartesian product of two lists Task

Given two lists of characters, output their Cartesian product, i.e. the list of pairings of each letter from the first list with each letter from the second list.

Example

"123456" and "abcd" give:

[["1","a"],["1","b"],["1","c"],["1","d"],["2","a"],["2","b"],["2","c"],["2","d"],["3","a"],["3","b"],["3","c"],["3","d"],["4","a"],["4","b"],["4","c"],["4","d"],["5","a"],["5","b"],["5","c"],["5","d"],["6","a"],["6","b"],["6","c"],["6","d"]]

Input

Two lists of characters or strings. The characters used will be alphanumeric a-z, A-Z, 0-9 and a character can occur both multiple times and in both inputs at the same time.

Output

The Cartesian product of the input lists. That is, a list of each possible ordered pair of a character from the first list and a character from the second list. Each pair is a list or string or similar of two characters, or of two length-one strings. The output's length will be equal to the product of the lengths of the inputs.

The pairs must be listed in order; first listing the first character of the first list with the first of the second list, followed by all the pairings of the first character of the first list. The last pair consists of the last character of the first list together with the last character of the second list.

The output must be a flat list of pairs; not a 2D matrix where pairs are grouped by their first or second element.

Test cases

inputs               output

"123456", "abcd"     [["1","a"],["1","b"],["1","c"],["1","d"],["2","a"],["2","b"],["2","c"],["2","d"],["3","a"],["3","b"],["3","c"],["3","d"],["4","a"],["4","b"],["4","c"],["4","d"],["5","a"],["5","b"],["5","c"],["5","d"],["6","a"],["6","b"],["6","c"],["6","d"]]
"abc", "123"         [["a","1"],["a","2"],["a","3"],["b","1"],["b","2"],["b","3"],["c","1"],["c","2"],["c","3"]]
"aa", "aba"          [["a","a"],["a","b"],["a","a"],["a","a"],["a","b"],["a","a"]]

Haskell, 12 bytes

(<*>).map(,)

Try it online!


Positional Awareness Positional Awareness

Your task is to generate a program that, for every permutation of its characters (which includes the original program), outputs the positions of every character relative to the original program.

If your program is

Derp

you must output

[0, 1, 2, 3]

(or some equivalent). This is because D is in the 0th position, e is in the 1st, r the 2nd, and p the 3rd.

Let's take another program which is the original program, but with its characters permuted:

epDr

You must output

[1, 3, 0, 2]

because e is in the 1st position of the original program, p is in the 3rd position, D the 0th, and r the 2nd.

If the original program has two repeating characters:

abcda -> [0, 1, 2, 3, 4]

Then for the permutation, the 0 and the 4 in the array must be in ascending order:

baadc -> [1, 0, 4, 3, 2] (0 first, then 4)

Rules:

Your program must contain at least two unique characters.
At most floor(n/2) characters are to be the same.

 aabb (acceptable)
 aaaabc (not acceptable, only floor(6/2) = 3 a's allowed)

Your program's output can be either an array (or something similar) containing all the characters' positions in order, or a string with any delimiter, so these are perfectly fine:

[0, 1, 2, 3]
0,1,2,3
0 1 2 3

Actually, 2 bytes

10

Try it online!

This prints

0
1

while the (only) other permutation

01

prints

1
0

How it works

In Actually, consecutive digits are parsed separately, so 10 pushes 1 on the stack, then 0 on top of it.

When the program finishes, the stack is printed top to bottom, so it prints 0 first, then a linefeed, then 1.

The derranged program 01 does the same, in the opposite order.


Tips for golfing ASCII art I think the ASCII art questions on PPCG are fun to do, but personally I think it can be pretty hard, especially when the question is tagged as code-golf.

I wonder if anyone here might have some tips that will be useful for producing ASCII art.

Simply arranging characters is easy, but with (short) algorithms, things will become more complicated.

I'm talking about ASCII art like:

Text to ASCII art (characters)
Images (logos or icons)

I'm just looking for general tips, but language-specific is allowed since most of them can be translated anyhow.

Compression algorithms

You can apply LZMA compression to the string.
Many languages support it.

Run-length encoding

You can use processing instructions such as [char][number] (e.g. b12).
This compression algorithm is used here: https://codegolf.stackexchange.com/a/20589/10920

Further reading: http://en.wikipedia.org/wiki/Run-length_encoding

Integer packing

You can use arrays of integers to store small shapes such as:

// This is an invader!
// (SE line height makes it looks awful)
// ~158 characters

    ##          ##
      ##      ##
    ##############
  ####  ######  ####
######################
##  ##############  ##
##  ##          ##  ##
      ####  ####

Each space will be translated into a 0.
Each sharp will be translated into a 1.

// ~58 characters
// Saved ~100 bytes!
[
  196656,  49344,   262128,  999228,
  4194303, 3407859, 3342387, 62400
]

Each bit is then read using bitwise operator &.

The above algorithm could be improved by using a bigger integer base:

// ~44 characters
// Integers are in base 36.
// Use `_` as a separator (or a line break).
"47qo_122o_5m9c_lf0c_2hwcf_211ir_1zn03_1c5c"


Generating a random alphanumeric string of length N What is the shortest way of generating a random string with a given length and with only alphanumeric characters allowed?

example of a random string: with N = 9 output would be aZua7I0Lk
the given length N can be assumed to be always greater than 0
if necessary you can assume 256 as a maximum value for N, but solutions with higher limits for N and still having a fast computation time are preferred
allowed characters: 0-9, a-z and A-Z
a character can occur more than once in the output string
each possible string should be equally likely (to the accuracy of your language's random number generator)

Taxi, 2577 bytes
Go to Post Office:w 1 l 1 r 1 l.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:s 1 l 1 r.Pickup a passenger going to Sunny Skies Park.Go to Sunny Skies Park:n 1 l 1 l 1 r.[a]Go to Heisenberg's:n 1 r 1 r 3 r.Pickup a passenger going to Cyclone.Go to Go More:n 1 l 3 l 3 l.Go to Starchild Numerology:e 2 r.62 is waiting at Starchild Numerology.Pickup a passenger going to Cyclone.Go to Cyclone:e 1 l 2 r.Pickup a passenger going to What's The Difference.Pickup a passenger going to Divide and Conquer.Pickup a passenger going to Divide and Conquer.Go to Divide and Conquer:n 2 r 2 r 1 r.Pickup a passenger going to Trunkers.Go to Trunkers:e 1 r 3 r 1 l.Pickup a passenger going to Multiplication Station.Go to Cyclone:w 2 r.Pickup a passenger going to Multiplication Station.Go to Multiplication Station:s 1 l 2 r 4 l.Pickup a passenger going to What's The Difference.Go to What's The Difference:n 2 l 1 r 3 l.Pickup a passenger going to Addition Alley.Go to Starchild Numerology:e 1 r 3 l 2 r.1 is waiting at Starchild Numerology.63 is waiting at Starchild Numerology.Pickup a passenger going to Addition Alley.Pickup a passenger going to The Underground.Go to Addition Alley:e 1 l 2 r 3 r 1 r.Pickup a passenger going to Joyless Park.Go to Writer's Depot:n 1 l 1 l.ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789- is waiting at Writer's Depot.Pickup a passenger going to Chop Suey.Go to Joyless Park:n 3 r 2 r 2 l.Go to Chop Suey:w 1 r 1 r 1 l.[b]Pickup a passenger going to Narrow Path Park.Go to Narrow Path Park:n 1 l 1 r 1 l.Go to The Underground:e 1 r.Switch to plan "c" if no one is waiting.Pickup a passenger going to The Underground.Go to Fueler Up:s.Go to Chop Suey:n 3 r 1 l.Switch to plan "b".[c]Go to Joyless Park:n 1 r.Pickup a passenger going to The Underground.Go to Narrow Path Park:w 1 r 3 l.[d]Pickup a passenger going to KonKat's.Go to KonKat's:e 1 r.Pickup a passenger going to KonKat's.Go to The Underground:s.Switch to plan "e" if no one is waiting.Pickup a passenger going to The Underground.Go to Fueler Up:s.Go to Narrow Path Park:n 4 l.Switch to plan "d".[e]Go to KonKat's:n.Pickup a passenger going to Riverview Bridge.Go to Riverview Bridge:n 1 l.Go to Narrow Path Park:e 1 l 1 r.Pickup a passenger going to Post Office.Go to Post Office:e 1 r 4 r 1 l.Go to Sunny Skies Park:s 1 r 1 l 1 r.Pickup a passenger going to The Underground.Go to The Underground:n 1 r 1 r 2 r.Switch to plan "f" if no one is waiting.Pickup a passenger going to Sunny Skies Park.Go to Sunny Skies Park:n 3 l 2 l 1 l.Switch to plan "a".[f]

Try it online!
Taxi is super not made for this but you can do it! I'll try to explain what's happening below the un-golfed version.
Go to Post Office: west 1st left 1st right 1st left.
Pickup a passenger going to The Babelfishery.
Go to The Babelfishery: south 1st left 1st right.
Pickup a passenger going to Sunny Skies Park.
Go to Sunny Skies Park: north 1st left 1st left 1st right.
[a]
Go to Heisenberg's: north 1st right 1st right 3rd right.
Pickup a passenger going to Cyclone.
Go to Go More: north 1st left 3rd left 3rd left.
Go to Starchild Numerology: east 2nd right.
62 is waiting at Starchild Numerology.
Pickup a passenger going to Cyclone.
Go to Cyclone: east 1st left 2nd right.
Pickup a passenger going to What's The Difference.
Pickup a passenger going to Divide and Conquer.
Pickup a passenger going to Divide and Conquer.
Go to Divide and Conquer: north 2nd right 2nd right 1st right.
Pickup a passenger going to Trunkers.
Go to Trunkers: east 1st right 3rd right 1st left.
Pickup a passenger going to Multiplication Station.
Go to Cyclone: west 2nd right.
Pickup a passenger going to Multiplication Station.
Go to Multiplication Station: south 1st left 2nd right 4th left.
Pickup a passenger going to What's The Difference.
Go to What's The Difference: north 2nd left 1st right 3rd left.
Pickup a passenger going to Addition Alley.
Go to Starchild Numerology: east 1st right 3rd left 2nd right.
1 is waiting at Starchild Numerology.
63 is waiting at Starchild Numerology.
Pickup a passenger going to Addition Alley.
Pickup a passenger going to The Underground.
Go to Addition Alley: east 1st left 2nd right 3rd right 1st right.
Pickup a passenger going to Joyless Park.
Go to Writer's Depot: north 1st left 1st left.
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789- is waiting at Writer's Depot.
Pickup a passenger going to Chop Suey.
Go to Joyless Park: north 3rd right 2nd right 2nd left.
Go to Chop Suey: west 1st right 1st right 1st left.
[b]
Pickup a passenger going to Narrow Path Park.
Go to Narrow Path Park: north 1st left 1st right 1st left.
Go to The Underground: east 1st right.
Switch to plan "c" if no one is waiting.
Pickup a passenger going to The Underground.
Go to Fueler Up: south.
Go to Chop Suey: north 3rd right 1st left.
Switch to plan "b".
[c]
Go to Joyless Park: north 1st right.
Pickup a passenger going to The Underground.
Go to Narrow Path Park: west 1st right 3rd left.
[d]
Pickup a passenger going to KonKat's.
Go to KonKat's: east 1st right.
Pickup a passenger going to KonKat's.
Go to The Underground: south.
Switch to plan "e" if no one is waiting.
Pickup a passenger going to The Underground.
Go to Fueler Up: south.
Go to Narrow Path Park: north 4th left.
Switch to plan "d".
[e]
Go to KonKat's: north.
Pickup a passenger going to Riverview Bridge.
Go to Riverview Bridge: north 1st left.
Go to Narrow Path Park: east 1st left 1st right.
Pickup a passenger going to Post Office.
Go to Post Office: east 1st right 4th right 1st left.
Go to Sunny Skies Park: south 1st right 1st left 1st right.
Pickup a passenger going to The Underground.
Go to The Underground: north 1st right 1st right 2nd right.
Switch to plan "f" if no one is waiting.
Pickup a passenger going to Sunny Skies Park.
Go to Sunny Skies Park: north 3rd left 2nd left 1st left.
Switch to plan "a".
[f]

Start: Get stdin
Pick up the stdin value as text, convert it to a number, and go stick it somewhere to wait.
Plan A Part 1: Get a random integer 1-62
Get a random integer and then get 62 as a number. Duplicate both the random integer and the 62 because we'll need them later. You can only carry 3 passengers at once so we end up with rand, rand, and 62. (The other 62 will wait around until we get back.) Go divide rand by 62 and truncate the result to get an integer. Go back to get the other copy of 62 and multiply it by the truncated integer from the division. Finally, subtract the product from the first copy of rand. This gives us a number 0-61. Now we have to go back to pickup a 1 and add it to the result to get a number 1-62. Yes, all those many lines of text are just mod(rand(),62)+1.
Plan A Part 2: Create an array of characters from which to choose
Pickup a string with all the valid characters and also one at the end we don't want (more on that later). The 63 we picked up earlier matches this string length. Take it over to Chop Suey to have it broken into individual passengers.
Plan B: Move the array so we can select a character
One by one, move every character over to Narrow Path Park. It's the only stack available and the only way to not have leftover passengers getting in the way. Everything else in Townsburg is FIFO so I would have to go back and clear out all the passengers every iteration of the overall loop. This way, I can just leave them at the park and they'll get pushed out of the way by the 63 new characters every time. The very first A is likely to never escape.
Plan C: Prepare to select a character
This is really just a few stops that didn't need to be in Plan D. Re-position the taxi in preparation.
Plan D: Get all the characters we dont want
Starting with the first character in the reversed "array" (this is the 63rd character we don't want), keep picking up and concatenating characters as we count down from the result of the mod function in Plan A. Once you hit zero, the next character is the one you want.
Plan E: Drown the ones you don't want and return the chosen one.
"[P]assengers dropped off at Riverview Bridge seem to always fall over the side and into the river..." Well, that gets rid of that concatenated string of losers. Go pick up the next character and send it to stdout. Finally, let's check how many characters we've printed thus far. Back to Sunny Skies to pick up the stdin value we left so long ago. Subtract one and, if the result is more than zero, send it back to wait and start over again at Plan A.


Simplified Train Set Many different types of train set exist, ranging from wooden tracks like Brio, to fully digital control perfect tiny metal replicas of real trains, but they all require a track to be designed, ideally using as many of your pieces as possible.

So, your task is to determine whether, given input of the available pieces, it is possible to build a complete closed circuit using all of the elements, and if not, how many pieces will be left from the maximum possible circuit.

Since this is a simplified train set, there are only 3 elements: big curve, little curve, and straight. These are all based on a square grid:

"Big Curve" is a 90 degree corner, covering 2 units in each dimension
"Little Curve" is a 90 degree corner, covering one unit in each direction
"Straight" is a straight element, 1 unit long

This means that the minimum circuit possible is formed of 4 little curves - it's a circle, of radius 1 unit. This can be extended by adding pairs of straight elements to form various ovals. There are other circuits possible by adding more curves, or by mixing the types of curve.

This train set doesn't include any junctions, or methods for tracks to cross, so it's not valid for two elements to connect to the same end of an other element (no Y formations) or to cross over one another (no X formations). Additionally, it's a train set, so any formation which doesn't allow a train to pass isn't valid: examples include straights meeting at 90 degree angles (there must always be a curve between perpendicular straights) and curves meeting at 90 degree angles (curves must flow).

You also want to use as many pieces as possible, ignoring what type they are, so you'll always opt for a circuit which has more bits in. Finally, you only have one train, so any solution which results in multiple circuits is unacceptable.

Input

Either an array of three integers, all greater than or equal to 0, corresponding to the number of big curves, little curves, and straights available, or parameters passed to your program, in the same order.

Output

A number corresponding to the number of pieces left over when the maximum possible circuit for the elements provided is constructed.

Test data

Minimal circuit using big curves
Input: [4,0,0]
Output: 0

Slightly more complicated circuit
Input: [3,1,2]
Output: 0

Incomplete circuit - can't join
Input: [3,0,0]
Output: 3

Incomplete circuit - can't join
Input: [3,1,1]
Output: 5

Circuit where big curves share a centre
Input: [2,2,0]
Output: 0

Bigger circuit
Input: [2,6,4]
Output: 0

Circuit where both concave and convex curves required
Input: [8,0,0] or [0,8,0]
Output: 0

Circuit with left over bit
Input: [5,0,0] or [0,5,0]
Output: 1

Notes

2 straights and a little curve are equivalent to a big curve, but use more pieces, so are preferred - should never be a situation where this combination is left, if there are any big curves in the circuit
4 little curves can usually be swapped for 4 straights, but not if this would cause the circuit to intersect itself
The train set is also idealised - the track elements take up the widths shown, so it is valid for curves to pass through a single grid square without intersecting, in some cases. The grid just defines the element dimensions. In particular, two big curves can be placed so that the grid square at the top left of the example diagram would also be the bottom right square of another big curve running from left to top (with the diagram showing one running from right to bottom)
A small curve can fit in the empty space under a big curve (bottom right grid square above). A second big curve could also use that space, shifted one across and one down from the first
A small curve cannot fit on the same grid space as the outside of a big curve - mostly because there is no way to connect to it which doesn't intersect illegally


Implement a Caesar Cipher with a Digit Shift I assume everyone here is familiar with the Caesar Cipher that shifts letters to a certain index. https://en.wikipedia.org/wiki/Caesar_cipher for those who still needs introduction.

But, we can all agree that plain Caesar is unfun and way too easy. So here's a version that also shifts characters around. This version first applies a cyclic position shift of a given amount to the string, for each character in the string separated with punctuations (space counts as character in this context, positive index means to the right).

For example, Hello world with shift +3 becomes rldHello wo.
Hello! World becomes lloHe!rld Wo with the same shift however because the ! separated the string.

After that, your program applies the Caesar cipher to the shifted text, and outputs the result. (easy enough)
The first example becomes uogKhoor zr after the Caesar cipher of +3.
The second example becomes iilEb!oia Tl after a Caesar shift of -3 (or +23 in alphabets)

As seen above, the index of the two shifts may or may not be equal.

Task

Write a encode and decode program or function (or whatever your language of choice calls them), they may or may not be the same one. It must implement the aforementioned rules of double shifting, and the decode function must successfully reverse it.

Conditions

Your program must at the very least function on ASCII characters, ASCII 0-9 (48-57, inclusive), A to Z (65-90), a to z (97-122) and Space (32) counts as characters in this context, with every other ASCII character counting as punctuation and breaking up the string.

Bonus points to those whose program functions on your language of choice's codebase. Since non-ASCII language contain special characters the "punctuation" rule is omitted in this use case. You only need to implement the cyclic shift and then the Caesar shift on your language's codebase.
¡¢£¤ in Jelly becomes ©¤¥¦ with a position shift of +1 and Caesar shift of -253.

You may assume:

The index input are integers. It may be negative or zero.
If only one number is provided, encode both shifts with that number.
If no number is provided, perform whatever default shifts your heart desire (except 0 and 0, that is boring).
Edit: Due to overwhelming demand, you may assume that there will be at least one number provided. Code that has defaults would still be preferred but no extra scoring.
The input string is in ASCII. Or in your language's codebase if you decide to input that to your program.

Scoring

Of course programs that successfully include their codebase will be prioritized. Include the shifted version of your program in your answer to reflect this.

The other criteria is lowest byte wins. This counts both the encoder and decoder. List the sum and respective length separately please.

Test cases

+3 -5 "Hello,world" becomes "ggjCz,mgyrj"
+10 "Implement a Caesar Cipher with a Digit Shift" becomes "sqsd Crspd Swzvowoxd k Mkockb mszrob gsdr k N"
-2 -11 "Caesar cipher, also known as Caesar's cipher, the shift cipher, Caesar's code or Caesar shift."
becomes "thpg rxewtgRp,ahd zcdlc ph Rpthpg p'rxewtgh ,wt hwxui rxewtg i,pthpg'h rdst dg Rpthpg hwxui R."

PS. Of course I am aware that the two shifts can be carried out in any order and produce the same result, it is just my way of visualizing things. Plus, the first input means position shift index.

PPS. If the test cases are wrong I apologize, I am not a good coder.

05AB1E, 23 (12+11) bytes
Uses the 05AB1E encoding for the Caesar-shifting.
Encoder:
žĆDII(._kI+è

Input order as string, shift, (optional Caesar-shift). I/O of the strings as character-list.
Try it online or try it online with debug step-by-step lines and single shift-input.
Decoder:
žĆDIkI-èI._

Input order as string, (optional Caesar-shift), shift. I/O of the strings as character-list.
Try it online or try it online with debug step-by-step lines and single shift-input.
Explanation:

              # ENCODER:
žĆ            # Push the 05AB1E codepage
  D           # Duplicate it
   I          # Push the first character-list input
    I         # Push the second shift integer
     (        # Negate it
      ._      # Shift the character-list that many times towards the left
        k     # Get the index of each character in the duplicated codepage
         I    # Push the second shift input again or the optional third Caesar-shift input
          +   # Add it to each index
           è  # And index it into the 05AB1E codepage
              # (after which the resulting character-list is output implicitly as result)

              # DECODER:
žĆ            # Push the 05AB1E codepage
  D           # Duplicate it
   I          # Push the first character-list input
    k         # Get the index of each in the duplicated codepage
     I        # Push the optional Caesar-shift or shift integer
      -       # Subtract it from each index
       è      # Index it into the 05AB1E codepage
        I     # Push the second/third shift integer
         ._   # And rotate the character-list that many times towards the left
              # (after which the resulting character-list is output implicitly as result)


Drive a hexadecimal 7-segment display using NAND logic gates The ubiquitous 7-segment numerical display can unambiguously display all 16 hexadecimal digits as show in this wikipedia .gif

Entries for this challenge will create a circuit diagram using NAND logic gates which transforms the four bits of a hex digit to the inputs for the seven segments.  The inputs for the 7 segment display are typically labelled as follows: (DP (decimal point) is ignored for this challenge)

Thus your circuit will need to conform to the following truth table:

Hex   | Hex Input Bit | Output to Segment line:
digit |  3  2  1  0   |  A  B  C  D  E  F  G
------+---------------+-----------------------
   0  |  0  0  0  0   |  1  1  1  1  1  1  0
   1  |  0  0  0  1   |  0  1  1  0  0  0  0
   2  |  0  0  1  0   |  1  1  0  1  1  0  1
   3  |  0  0  1  1   |  1  1  1  1  0  0  1
   4  |  0  1  0  0   |  0  1  1  0  0  1  1
   5  |  0  1  0  1   |  1  0  1  1  0  1  1
   6  |  0  1  1  0   |  1  0  1  1  1  1  1
   7  |  0  1  1  1   |  1  1  1  0  0  0  0
   8  |  1  0  0  0   |  1  1  1  1  1  1  1
   9  |  1  0  0  1   |  1  1  1  1  0  1  1
   A  |  1  0  1  0   |  1  1  1  0  1  1  1
   b  |  1  0  1  1   |  0  0  1  1  1  1  1
   C  |  1  1  0  0   |  1  0  0  1  1  1  0
   d  |  1  1  0  1   |  0  1  1  1  1  0  1
   E  |  1  1  1  0   |  1  0  0  1  1  1  1
   F  |  1  1  1  1   |  1  0  0  0  1  1  1

I think this table is accurate, but please let me know if you spot any errors.

Your score is determined by the number of 2-input NAND gates you use (1 point per gate).  To simplify things, you may use AND, OR, NOT, and XOR gates in your diagram, with the following corresponding scores:

NOT: 1
AND: 2
OR: 3
XOR: 4

Dominoes - Total Score: 243 NANDs

ORs used: 61 (3 NANDs each -> 183 NANDs)
NOTs used: 60 (1 NANDs each -> 60 NANDs)

This solution is in dominoes and required a collection of pieces of software I wrote in the course of answering Martin Büttner's two Domino related questions to produce (Golfing for Domino Day and Domino Circuits).

By modifying my Domino Circuit solver, I was able to produce a domino circuit (this file also contains the solver output and circuit skeleton) consisting of ORs, and IFNOTs where the first input is always TRUE (so it's essentially a NOT). Because there isn't much that will fit in this answer, I present the OR and NOT solutions to the truth table:

A: 1011011111101011
((-1 ifnot (2 or (1 or (-1 ifnot 0)))) or ((-1 ifnot ((-1 ifnot 1) or (-1 ifnot 2))) or ((-1 ifnot (3 or (-1 ifnot (0 or (-1 ifnot 1))))) or (-1 ifnot (0 or ((-1 ifnot 3) or (-1 ifnot (2 or 1))))))))
B: 1111100111100100
((-1 ifnot (3 or 1)) or ((-1 ifnot (3 or (2 or 0))) or (-1 ifnot ((-1 ifnot 3) or ((-1 ifnot (2 or (0 or (-1 ifnot 1)))) or (-1 ifnot ((-1 ifnot 0) or (-1 ifnot 2))))))))
C: 1101111111110100
((-1 ifnot (2 or (-1 ifnot 3))) or ((-1 ifnot (1 or (-1 ifnot 0))) or (-1 ifnot (0 or (-1 ifnot (3 or (1 or (-1 ifnot 2))))))))
D: 1011011011011110
((-1 ifnot (3 or (1 or 0))) or ((-1 ifnot (2 or ((-1 ifnot (3 or 0)) or (-1 ifnot (1 or 0))))) or (-1 ifnot ((-1 ifnot 2) or ((-1 ifnot (3 or 1)) or (-1 ifnot ((-1 ifnot 1) or (-1 ifnot 3))))))))
E: 1010001010111111
((-1 ifnot (3 or (-1 ifnot (2 or (-1 ifnot 1))))) or (-1 ifnot ((-1 ifnot 0) or (-1 ifnot (2 or 1)))))
F: 1000111011111011
((-1 ifnot (3 or (-1 ifnot 1))) or ((-1 ifnot (2 or (0 or (-1 ifnot (1 or (-1 ifnot 3)))))) or (-1 ifnot ((-1 ifnot 0) or (-1 ifnot (2 or (-1 ifnot 1)))))))
G: 0011111011110111
((-1 ifnot (2 or (0 or (-1 ifnot 1)))) or ((-1 ifnot (1 or (-1 ifnot (2 or 0)))) or (-1 ifnot ((-1 ifnot (3 or 2)) or (-1 ifnot (0 or (-1 ifnot 3)))))))

Note that the only binary operations used are OR and IFNOT, where I count each IFNOT as a NOT for scoring purposes

I added a 7-segment display to the end of the circuit and fed it into a domino simulator/gif generator. The resulting gif (which shows 'A' being displayed) took about 2 hours to generate. Because the final circuit is 1141 * 517 in size each "cell" is represented by a single pixel. A black cell is empty, a grey cell has a standing domino in it, and a white cell has a fallen domino in it. This means that you can't really tell what is going on, and it won't help if it's being squashed at all. Sparr kindly provided a much smaller version of my original gif (650kB), so here it is!

Below is the last frame of the animation for input 1010 ('A') as above. You can see the inputs on the far left, powerline at the top, the switchboard taking up most of the space, the 7 individual pieces of logic (these are domino representations of the functions above) to the left of the switch board, and to the far right is the 7-segment display itself. When this runs, the individual segments light up roughly at the same time, so you can't be looking at it for too long with some segments lit up waiting for others to light up.

See the animation in it's full glory here (36MB) or here (650kB, courtesy of Sparr) (the smaller copy is much smaller, but my browser seemed to like skipping frames marring the beauty so I've left the original thusly)

The detail of the 7-segment display can be seen here ('1' is shown)


Tips for golfing in Common Lisp What general tips do you have for golfing in Common Lisp? I'm looking for ideas which can be applied to code-golf problems and which are also at least somewhat specific to Common Lisp (e.g. "remove comments" is not an answer).

Please post one tip per answer.

Use ' (quote) as synonym for "" for single words.

Quote stops evaluation of symbol, allowing you to e.g. print it. Note that the casing is dependant on *print-case* variable (most of the time it's in the upcase).

(print"yes")
(print'yes) ; saved a byte!


Display Sentence in Alphabetical Order Write a program that takes a string and outputs all the characters in alphabetical order.
Spaces and symbols can be ignored or deleted, but the upper- and lowercase letters must remain the same case.

Sample input:

Johnny walked the dog to the park.

Sample output

aaddeeeghhhJklnnoooprtttwy

Rules:

• Any language

• Shortest code wins.

GolfScript, 24 / 6 characters
{26,{65+.32+}%?)},{31&}$

Example:
> Johnny walked the dog to the park.
aaddeeeghhhJkklnnoooprtttwy

If the input is restricted to printable ascii the code can be shortened by three characters using {95&.64>\91<&}, as filter.
Can be tested here.
The can-be-ignored version is even shorter (6 chars):
{31&}$

and yields output
> Johnny walked the dog to the park.
      aaddeeeghhhJkkl.nnoooprtttwy


Find the largest fragile prime Consider the function Remove(n, startIndex, count) that removes count digits from the number n starting from the digit at position startIndex. Examples:

Remove(1234, 1, 1) = 234
Remove(123456, 2, 3) = 156
Remove(1507, 1, 2) = 07 = 7
Remove(1234, 1, 4) = 0

We will call the prime number X fragile if every possible Remove operation makes it non-prime. For example, 80651 is a fragile prime because all of the following numbers are not prime:

651, 51, 1, 0, 8651, 851, 81, 8, 8051, 801, 80, 8061, 806, 8065

Goal

Write a program that finds the largest fragile prime. Edit: removed the time limit because there was a relatively fair way to circumvent it.

The score is the fragile prime number found by your program. In the event of a tie, the earlier submission wins.

Rules

You may use any language and any third-party libraries.
You run the program on you own hardware.
You may use probabilistic primality tests.
Everything is in base 10.

Leading entries

6629 digits by Qualtagh (Java)
5048 digits by Emil (Python 2)
2268 digits by Jakube (Python 2)

Edit: I've added my own answer.

28164 digits by Suboptimus Prime, based on Qualtagh's algorithm (C#)