Generate an ascii-art non-intersecting path

Befunge, 344 bytes
&v>>>#p_:63p:43g`\!+v>/*53g+\01g:2%2*1-\2/!*63g+\0\:v
 40$ v++!\`g14:p35:\<^2\-1*2%2p10::%4+g00:\g36\g35-1_v
#11^$_83p73v >1+:41g`!#v_$,1+:43g`!#v_@>->2>+00p+141^_
<p1^     vp< ^,g+7g36:<<<<1+55p36:<<<< ^1?0^#7g36g35*
8&p|!++!%9#2g+7g10\*!-g38g10!-g37:g00!!*<>3^
443>:!#v_>>1-::3%1-:53g+00p\3/1-:63g+01p^
^>^>>$#<"#"53g63g7+p41g53g-43g63g-+!#^_

Try it online!
As @flawr mentioned in their MATLAB answer, this may take some time if the field size is of any non-trivial size. In fact it's quite easy to get into a situation where it's really not worth trying to wait for it to finish, because you're quite likely to be waiting until the end of time.
To understand why this happens, it helpful to view the program as it's executing in one of Befunge's many "visual debuggers". Since data and code are the same thing in Befunge, you'll get to view the path as it changes over time. For example, here is a short animation showing what a part of a run on a slow path might look like.

Once the algorithm decides to make that fateful turn to the left at the bottom of the field boundary, it has essentially condemned itself to a lifetime of aimless wandering. From that point on it has to follow every single possible path in that fenced off area before it can back out and try the turn to the right. And the number of potential paths in these cases can easily become astronomical.
Bottom line: If it seems to be taking a long time, it's probably a good idea to just abort the execution and start again.
Explanation
This is basically a recursive algorithm, trying every possible path through the field, and then unwinding steps that have already been followed whenever it gets stuck. Since Befunge doesn't have the concept of functions, a recursive function is out of the question, but we can emulate the process by tracking the state on the stack.
This works by populating the stack with potential coordinates that we may want to follow. Then we pull one set from the stack and check whether it is suitable (i.e. in range and not overlapping with an existing path). Once we've got a good spot, we write a # into the playfield at that location, and add those details to the stack in case we need to backtrack later.
We then push an additional four sets of coordinates onto the stack (in random order) indicating the potential paths we can take from this new location, and jump back to the start of the loop. If none of the potential paths are feasible, we'll get to the point on the stack where we saved the location of the # we wrote out, so we'll undo that step and continue trying potential coordinates from one step prior.
This is what the code looks like with the various component parts highlighted:

 Read the width and height of the field, and push the start coordinates along with a 0 type marker to indicate a potential path rather than a backtracking location.
 Check for backtracking locations (indicated by a 1 type marker) which are reverted with a simple p command, since they're stored in the exact format needed to write a space back into the playfield.
 Check if the coordinates are still inside the playfield. If they're out of range, drop them from the stack and loop back to try the next potential coordinates.
 If they are in range, get the next two values from the stack, which is the location of the previous step (required in the test that follows this).
 Check if the coordinates are going to come into contact with an existing segment of the path. The location of the previous step is obviously ignored from this check.
 If all test are successful, write a # into the playfield, and check if we've reached the destination location.
 If we have, write out the final path,  and exit.
 Otherwise save the coordinates onto the stack with a 1 type marker for later backtracking.
 This is interrupted with a random number calculation which we're going to need soon.
 Push four potential destinations that can be reached from the current location. The random number determines the order in which they're pushed and thus the order that they will be followed.
 Wrap back to the start of the main loop and process the next values on the stack.


Find the number in the Champernowne constant

LabVIEW, 29 LabVIEW Primitives

This uses strings for now. It matches the input as a pattern and outputs the offset - (input lenght -1).


Mathematica, 78 bytes

Image@Apply[16#+#2&,Mod[IntegerDigits[#~ImageData~"Byte",16,2]+1,16]/255,{3}]&

Takes and returns an image object (to create an image object, just paste the image into Mathematica).

Result for the test case:

Taking input and returning output as a 3D array of integer channel values, this reduces to 51 bytes:

Apply[16#+#2&,Mod[IntegerDigits[#,16,2]+1,16],{3}]&

But those meta posts don't have an overwhelming amount of support yet, so I'm going with the 78-byte version for now.


Julia, 160 157 154

x->(c=count_ones;l=[119;36;93;109;46;107;123;37;127;111];m=l[x+1];n=map(a->c(a)==mean(map(c,m))?sum(map(b->c(a$b),m)):1/0,l);find(n.==minimum(n).!=1/0)-1)

This is a lambda function. Assign it to a variable to call it. Accepts a vector of integers in range 0-9 of any length and returns a (possibly empty) vector of results.

Test cases

julia> clock = x->(c=co...        # assign function to variable
(anonymous function)

julia> clock([1 2 3])
1-element Array{Int64,1}:
 4

julia> clock([1 2 1 2])
0-element Array{Int64,1}

julia> clock([6 5 4])
1-element Array{Int64,1}:
 5

clock([6 0 9])
3-element Array{Int64,1}:
 0
 6
 9

Explanation

Enumerate the seven segments and represent them as a bit vector.

+---+                     +-0-+
|   |      Enumerate      1   2
+---+   >  the seven  >   +-3-+
|   |      segments       4   5
+---+                     +-6-+

Example: 1 (segments 2 + 5 enabled) becomes 36 (bits 2 + 5 set).
Here are the representations for digits 0-9.

l=[119;36;93;109;46;107;123;37;127;111];
m=l[x+1];

We can use the digit as index to get it's bit vector representation. +1 because of 1-based indexing in julia.

The function c=count_ones; counts the number of 1-bits in an integer. We assign an alias because we need it more often.

The full program, somewhat ungolfed:

x->(
  c=count_ones;
  l=[119;36;93;109;46;107;123;37;127;111];
  m=l[x+1];
  n=map(a->c(a)==mean(map(c,m))?sum(map(b->c(a$b),m)):1/0,l);
  find(n.==minimum(n).!=1/0)-1
)

Now, the last two lines in detail:

mean(map(c,m)) calculates the average number of lines per input digit.

n=map(a->...,l) loops over the vector representation of all digits.

If the number of lines of our current digit a is unequal to the average linecount of the input, return inf.

c(a)==mean(map(c,m))?...:1/0

If not, return the sum of the Hamming Distances between our current and all input digits.

sum(map(b->c(a$b),m))

We now have a vector n of length 10 representing the numbers 0-9 that gives us the total number of additions/deletions we have to perform to tranform all input digits to that number, or inf, if such a transformation is impossible without changing the number of lines.

find(n.==minimum(n).!=1/0)-1

Finally, output the locations (0-based) of all minima that are not inf.


Write a square program that outputs the number of times it has been "unrolled"

Golfscript, N <- [5,7..]

.   .
 . .
 ..
.  .#
],9\-

Fully unrolled:

],9\-#  .   .  .  . . ...

Explanation:

. (multiple times) - duplicate the input
] - collect the stack into a single array
, - take its length
9\- - subtract it from 9
# - line comment

Whitespace is a NOP, but any other NOP would have worked just as well.

Fully rolled up, it uses nine copies of the input (contents ignored) as the stack; 9 - 9 = 0; it has not been unrolled.

Each unroll hides one more dot (duplicate) behind the comment, shrinking the stack once, incrementing the output.

Fully unrolled, it uses only the input (contents ignored) as the stack; 9 - 1 = 8; it has been unrolled 8 times.

The same approach works for any N > 4: Change 9 to the appropriate value of 2*N+1, then extend the pattern of dots (duplicate) using the same spiral pattern that ensures exactly one dot gets unrolled during each unroll.


Modified Boggle-able Code and Output: CnR Edition (Robbers)


APL, 19 chars/bytes*

{(↑⍳⍨1∘↓)⌽⍵|10x*⍳⍵}

Nars2000. The previous version was wrong on some numbers, this should be right. I manually checked it on all numbers up to 50.

Again, credit goes to Ben Reich for the idea of looking at the period of 10^i (mod x)

Exploded view

{                     ⍳⍵}   generate all naturals up to the argument ⍵
                 10x*       raise 10 to each of them, with unlimited precision
              ⍵|            compute the respective remainders mod ⍵
            ⌽               reverse the list
 (  ⍳⍨    )                 (fork) find the position of the first occurrence
  ↑                         of the fist element of the list
       1∘↓                  in the remainder of the list

Examples

      {(↑⍳⍨1∘↓)⌽⍵|10x*⍳⍵}¨1 2 3 7 13 14 123 345 654 12345 67890
1 1 1 6 6 6 5 22 108 822 120

⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
*: APL can be written in its own (legacy) single-byte charset that maps APL symbols to the upper 128 byte values. Therefore, for the purpose of scoring, a program of N chars that only uses ASCII characters and APL symbols can be considered to be N bytes long.


MATL, 52 51 bytes
t2Y6~Z+*ssGt3Y6Z+*tt1=z2=wssGzqE=*Gz1=+?}_q]ssy-h2/

Input is a matrix of zeros and ones.
Output is B, then A. Non-curves give a negative A.
Try it online! Or verify all test cases.
Explanation
Computing the length of the curve uses two 2D convolutions1: one with the Moore mask, and another with a mask containing only the diagonal neighbours. The results are two matrices with the same size of the input, which will be denoted as M and D respectively. M gives the total number of neighbours for each point, whereas D gives the number of diagonal neighbours.
The results in M and D must be filtered to discard points that don't belong to the curve. Also, they must be divided by 2, because "being neighbour of" is a a symmetric relation, so each point in the curve is counted twice.
Determining if the curve is valid is more cumbersome than I expected. To do this, the code tests three conditions:

Does the number of ones in M equal 2? (That is, are thre exactly two points with a single neighbour?)
Does the total sum of M equal the number of points in the input curve times 2 minus 2? (Together with condition 1, this tests if all non-zero values in M except two of them equal 2)
Does the input curve contain a single point?

The curve is valid if conditions 1 and 2 are true, or if condition 3 is.
t       % Implicit input matrix of zeros and ones. Duplicate
2Y6~    % Push [1 0 1; 0 0 0; 1 0 1]
Z+      % 2D convolution, keeping size
*       % Multiply to zero out results for non-curve points. Gives matrix D
ss      % Sum of matrix D
Gt      % Push input again wtice
3Y6     % Push [1 1 1; 1 0 1; 1 1 1]
Z+      % 2D convolution, keeping size
*       % Multiply to zero out results for non-curve points. Gives matrix M
tt      % Duplicate twice
1=z     % Number of ones
2=      % Does it equal 2? This is condition 1
wss     % Swap. Sum of matrix
G       % Push input again
zqE     % Number of nonzeros values minus 1, and then multiplied by 2
=       % Are they equal? This is condition 2
*       % Multiply. This is a logical AND of conditions 1 and 2
G       % Push input again
z1=     % Does it contain exactly one nonzero value? This is condition 3
+       % Add. This is a logical OR with condition 3
?}      % If result was false
  _q    %   Negate and subtract 1. This makes sure we get a negative value
]       % End
ss      % Sum of matrix M
y       % Duplicate sum of matrix D from below
-       % Subtract
h       % Concatenate horizontally
2/      % Divide by 2. Implicitly display

1 Convolution is the key to success.


More fun with case-(very)-sensitive strings

Retina, 19 bytes

Retina doesn't have a direct way to reverse a string, but we can do it by exploiting the sorting stage:

O^#`[a-z]
O^#`[A-Z]

Sort (O), reading them as numbers (#), and then reverse the ordering (^), of all the strings matching the given regex (lowercase letters for the first line, and uppercase letters for the second).

This works because when we try to read strings without numeric characters as numbers they get treated as 0, so all the characters have the same value for sorting. Since sorting is stable they are left in the same order, and reversing them returns the original string reversed.

Try it online!


Jelly, 6 4 3 5 4 bytes

rÆPE

Try it online! or Try all test cases.

How it works

rÆPE    Main link. Arguments: N, M
r       Yield the range of integers between N and M, inclusive.
 ÆP     For each integer, yield 1 if it is prime, 0 otherwise.
   E    Yield 1 if all items are equal (none in the range were prime,
        or there's only one item).

Works because two numbers have different prime clusters iff there is a prime between them, or either number is itself prime; unless both numbers are the same, in which case E returns 1 anyway (all items in a single-item array are equal).


R, 86 bytes

function(a,b,d=a*(1-a))runif(1)<="if"(d,"if"(d>999e-6,a,1-round(a)),"if"(b,.9-.8*a,a))

Try it online!

a is P' and b is 1 or 0 for "in the climax" or not.

If a is 0 or 1, then d will be 0, in which case if b is 0 just return a, otherwise .9 minus .8*a.

Otherwise if a is not near 0 or 1, d will be "far" from 0 so return a. Otherwise 1-round(a) will take a to the "opposite" 0 or 1.

Then see if a random selection from [0,1] is less than or equal to the resulting probability.

The link does a little simulation for all the possible scenarios to demonstrate that it all seems to work.


perl/perl, unlimited score under original rule with unlimited range

Here's some code which doesn't win:

$l=-2**5-1;
$h=2**5;
sub p{print@_}
p"sub add {(\$i,\$j)=\@_;\n";
for($i=$l;$i<=$h;++$i){
  for ($j=$l;$j<=$h;++$j){
    p" return ".($i*$j)." if (\$i == $i) && (\$j == $j);\n";
  }
}
p"}print add(<>,<>)\n";

The output has this form:

sub add {($i,$j)=@_;
 return 1089 if ($i == -33) && ($j == -33);
 return 1056 if ($i == -33) && ($j == -32);
 return 1023 if ($i == -33) && ($j == -31);
 return 990 if ($i == -33) && ($j == -30);
...
 return 928 if ($i == 32) && ($j == 29);
 return 960 if ($i == 32) && ($j == 30);
 return 992 if ($i == 32) && ($j == 31);
 return 1024 if ($i == 32) && ($j == 32);
}print add(<>,<>)

the output file is 181030 bytes long, but after stripping spaces and newlines, it is only 133109 bytes long. so, the score is 133109/248 = 536.7289...

Here's some other code that doesn't win - it is the same program except the first 2 lines:

$l=-2**6-1;
$h=2**6;

the output file is 718138 bytes long, but after stripping spaces and newlines, it is only 532233 bytes long. so, the score is 532233/248 = ~2146. better! using 7 yields a score of ~8750, 8 yields ~35347, 9 yields ~149129, 10 yields 151100000 non-space / 250 = 604,400 ....

of course we can do this as long as we want. the size of the source program, n, will increase as O(log(n)). the size of the output program is O(2*n). The limit of 2*n/log(n) as n goes to infinity is clearly infinity, so if I just substitute in my favorite large number, a googolplex, I win (until someone suggests googolplex+1).


Python, 3 bytes

min

Try it online!

Takes a number string, outputs its smallest digit as a smallest character. For example, 254 gives 2. The decimal with these digits starts

0.0123456789011111111101222222220123333333012344444401234555550123456666012345678801234567

This is OEIS A054054.

Claim: This number c is transcendental

Proof:  Note that c is very sparse: almost all of its digits are zero. That's because large n, there's high probability n has a zero digit, giving a digit min of zero. Moreover, c has long runs of consecutive zeroes. We use an existing result that states this means c is transcendental.

Following this math.SE question, let Z(k) represent the position of the k'th nonzero digit of c, and let c_k be that nonzero digit, a whole number between 1 and 9. Then, we express the decimal expansion of c, but only taking the nonzero digits, as as the sum over k=1,2,3,... of c_k/10^Z(k).

We use the result of point 4 of this answer by George Lowther: that c is transcendental if there are infinitely many runs of zeroes that are at least a constant fraction of the number of digits so far. Formally, there must be an ε>0 so that Z(k+1)/Z(k) > 1+ε for infinitely many k. We'll use ε=1/9

For any number of digits d, take k with Z(k) = 99...99 with d nines.  Such a k exists because this digit in c is a 9, and so nonzero. Counting up from 99...99, these numbers all contain a zero digit, so it marks the start of a long run of zeroes in c. The next nonzero digit isn't until Z(k+1) = 1111...11 with d+1 ones. The ratio Z(k+1)/Z(k) slightly exceeds 1+1/9.

This satisfies the condition for every d, implying the result.


Generate all combinations of given list of elements, sorted

Jelly, 1 byte

ṗ

TryItOnline

Cartesian power built-in atom, as a dyadic link with left argument the items and right argument the count, or as a full program with first argument the items and second argument the count.


Minkolang 0.13, 12 bytes
nd1+?.n~Lr$N

Try it here.
Explanation
n      Take number from input (-1 if input is devoid of numbers)
d1+    Duplicate and add 1
?.     If this is 0, stop.
n~     Get number from input and negate it (because of the '-')
L      Pops b,a and pushes a,a+1,a+2,...,b-1,b
r      Reverses list
$N     Outputs whole stack as numbers


JavaScript, 360

Edit Modified interactive game, should run even in MSIE

As requested, text based game, input via popup, output in console (so to have a monospaced font).

Quit game with 'q' or clicking 'cancel' at prompt.

Not using ES5 features, it should run on any moder browser (where you can have a JS console panel)

b='\n......'.repeat(6).split('');
for(h=t=0;!h&t<36;)
{
  i=prompt();
  if(i=='q')i=null;
  i=i.match(/([0-5]) ([0-5]) ([XO])/);
  m='INVALID';
  if(b[p=i?i[2]*7-~i[1]:0]=='.')
  {
    ++t;
    b[p]=i[3];
    m=b.join('');
    for(x=z='',c=0;c++<6;)
      for(x+='_',z+='_',r=0;r<6;r++)
        x+=b[c+r*7],z+=b[c<4?c-1+r*8:c+1+r*6];
    h=(/X{5}|O{5}/.test(b.join('')+x+z))
  }
  console.log(m);
}
console.log("P"+(2-h)+" WINS")

Now, some more fun Interactive and graphic version, run snippet to play.

function start() {
  b=Array(7).join('\n......').split('');
  t=0;
  $('#O').text('');
  $('table')[0].className='';
  show();
  $('th').eq(1).html('Left-click: O
Right-click: X');
  $('#B')
  .off('mouseup')
  .on('mouseup','td.F',function(ev){
    var x,y, p=~~this.id.slice(1)
    x=p%7-1
    y=p/7|0
    b[p]=ev.which > 1 ?'X':'O';
    ++t
    for(x=z='',c=0;c++<6;)
      for(x+='_',z+='_',r=0;r<6;r++)
        x+=b[c+r*7],z+=b[c<4?c-1+r*8:c+1+r*6];
    show()
    if (/X{5}|O{5}/.test(b.join('')+x+z))
      end(1)
    else if(t==6*6)
      end(2)
    return false
  })
}

function end(w) {
  var n=['Order','Chaos'][w-1]
  $('th').eq(0).text('P'+w+' '+n+' Wins')
  $('th').eq(1).text('Click to play again')

  $('table')[0].className=$('tr')[0].className =n[0];
  $('#B').off('mouseup').on('mouseup', start)
}
function show() {
  var w,p
  p=t&1
  $('tr')[0].className=$('#B')[0].className='OC'[p];
  w=b.map(function(c,i){
    return c>' '?''+c+'	':'

'
  }).join('');
  $('th').eq(0).text('Playing: '+['Order','Chaos'][p]);
  $('#B').html('
' + w +'
');
}

start()
th {
  font-size: 12px;
}
.C th { color: #807; }
.O th { color: #047; }
.C td.F:hover { background: #f0e; }
.O td.F:hover { background: #0fe; }
table.C td { background: #f0e; }
table.O td { background: #0fe; }

td {
  font-family: monospace;
  font-size: 12px;
  width: 1.2em;
  height: 1em;
  text-align: center;
}


Charcoal, 106 95 92 91 79 77 bytes

”∨+!rþW∕oc	σ�<7↗OKd↶!(⊞”«5βＧ◨“Ｏ�c∕)ÿ6T”‖Ｂ←→→→,Ｆ³‖ＭＪ⁹¦³Ｆ6137542«ιＭ⁸→»↑Ｆ⁸«Ｍ⁸←←'

Try it online! Edit: Saved 11 bytes by looping over the shirt numbers. Saved 3 bytes by working out how Ｊ worked. Saved a further byte by using separate mirror instructions. Saved 12 bytes thanks to @ASCII-only by compressing the half player string. Saved 2 bytes by repeating the mirror in a loop. Explanation:

”∨+!rþW∕oc	σ�<7↗OKd↶!(⊞”«5βＧ◨“Ｏ�c∕)ÿ6T”
            Print the right half of a player as a compressed string
‖Ｂ←         Butterfly to create the left half of the player
→→→,        Fix up the left foot
Ｆ³‖Ｍ        Mirror three times to end up with 8 footballers
Ｊ⁹¦³Ｆ6137542«ιＭ⁸→»↑
            Fix up the shirt numbers
Ｆ⁸«Ｍ⁸←←'    Fix up the right eyes

Edit: The above code no longer works in current Charcoal; the string compression appears to have changed and the reflect command now accepts a multidirection and leaves the cursor in a different position. However it's possible to adapt the code to run in current charcoal for the same byte count. Try it online! Link is to verbose version of code. (Note that the deverbosifier tries to compress 6137542 for some reason although it's unnecessary.) It then becomes possible to golf a further byte off. Try it online! Link is to verbose version of code.


Hurricane Matthew and the Lightning Bolts

Perl, 92 90 89 84 bytes

Includes +1 for -n

Give height on STDIN:

perl -M5.010 bolt.pl <<< 15

bolt.pl:

#!/usr/bin/perl -n
map{$_=$;until$;=$_,s/.6|3.?/53|16*rand/eg,/3|6/>/36/;say y|3615|\\/ |r}(1x$_.6)x$_

Explanation

If you call the offset of the starting point 0 (a point is at the corner of a character box), then on the next row you can have gone left or right (or not) and can end up with points on offsets -1,1. The next row gives -2,0,2 as possible offsets etc. They all differ by 2. If you then call the character to the lower left of a point even and the character to the lower right odd you can extend that to assigning even or odd to each character position on a row such that even and odd alternate (in fact the whole plane is tiled in a checkerboard pattern). An even position can have a / or , an odd position can have \ or .

The character just before a / is in an odd position so it could be either \ or , but \/ is forbidden so only  is possible. Similarly the character after a \ must be a  (assuming the row is padded with enough spaces to the left and the right so the row boundaries are no issue). So a lightning bolt continues on the next row always directly below a \ or below a /. In either case the lower point is in the middle and the next row can have one of , /, \ or /\ directly below the top 2 characters. So to generate the next row I can simply replace any \ or / by any of these 4 expansions with equal probability (you could also independently replace the first character by  or / and the second character by  or \). In perl you could do this with something like:

s#\\ | /#("  "," \\","/ ","/\\")[rand 4]#eg

If the resulting row however contains \/ (forbidden join) or no / or \ at all (bolt dies and does not reach the bottom) the result is invalid. In that case I throw away the whole row and simply try again. A valid continuation always exists and if you try often enough one will be found (e.g everything dies except for 1 flow). This is a slightly different probability distribution from the suggested anti-overlap algorithm, but I think this is in fact better since it has no directional bias. Validity can be testing in a golfish way using

m#\\|/#>m#\\/#

The problem here is that the random substitution is so looooong and all these \ escapes also eat bytes. So I decided to build my rows using strings of digits and replace the appropriate digits by , / and \ just before printing. The basic random replacement is

53|16*rand

which gives one of 53, 55, 61 or 63 with equal probability. I then interpret 5 and 1 as , 3 as \ and 6 as /. That explains the row print:

say y|3615|\\/ |r

In a serious golf competition I would now start to systematically explore alternative magic formulas, but this should be pretty good (within 3 bytes of optimal)

The rest of the components of the program:

1x$_.6

This initializes $_ (see the next map) to height spaces followed by a /. This is an invisible row above the first one being printed and makes sure the field is wide enough so the bolt can never run out of space at the left

map{ ... ; say ...}(1x$_.6)x$_

I will process this same initial string height times printing a new row each time

$_=$;until$;=$_,...

Save the current row in $;. If the replacement turns out to be invalid restore $_ from $;

s/.6|3.?/53|16*rand/eg

Do the actual substitution. I don't have to check what is before / or after \ since it must be a space. This is convenient since space can be represented by either 1 or 5. Since I only padded the string to the left the space after the \ can still be absent, so make that character optional

/3|6/>/36/

Check if the new row is valid


Python 3, 57 61 bytes

lambda x:"s='s=%r;print(s%%s)';print(s%s)".replace('s',x+'x')

Takes a basic python 3 quine from here and replaces the variable name with the input.

Note: As pointed out by Hyper Neutrino in comments, this does not work for reserved keywords like for, if, etc.

Appending a character that none of the reserved keywords ends with such as 'x' or any number fixes this. (Ørjan Johansen).


Ruby, 220 characters
s,n=$*
w=IO.binread(n).unpack r='s<*'
x=[];t=[g=0]*c=w[11]
w[u=22..-1].each_slice(c){|f|g+=v=1.0/s.to_f
c.times{|h|t[h]+=f[h]*v}
(c.times{|h|x<<=m=t[h]/g;t[h]-=m};g-=1)until 1>g}
w[u]=x;IO.binwrite'stretch.wav',w.pack(r)

This version works with ruby 1.9.3 with basic 16 bit files (e.g. no additional chunks) for any sample rate or number of channels.


Sort all the pixels of an image by the number of occurrences

Mathematica, 125 123 bytes

Export["a"<>#,i=ImageData@Import@#;Image@ArrayReshape[Join@@ConstantArray@@@SortBy[Tally[Join@@i],-Last@#&],Dimensions@i]]&

This defines an unnamed function which takes the file name in any common image format and writes the result to the a file with the same name but prepended with a. The result looks a bit different from the OP's, since Mathematica's SortBy breaks ties by default sort order, so the bottom bits where loads of ties occur look a bit neater:

The implementation itself is really straightforward:

ImageData to get a grid of colour values.
Join to flatten the array.
Tally to count the occurrence of each colour.
SortBy[...,-Last@#&] to sort by frequencies from highest to lowest.
ConstantArray and Join to expand the tallies again.
ArrayReshape to recover the original image shape (obtained with Dimensions).
Image to convert the data back to an image object.

FYI, 22 bytes are used on file I/O. An equivalent version that takes and returns an image object comes in at 103 bytes:

(i=ImageData@#;Image@ArrayReshape[Join@@ConstantArray@@@SortBy[Tally[Join@@i],-Last@#&],Dimensions@i])&


C# 803 579bytes

Complete program, reads from STDIN, should cope with any common new-line scheme as long as it has line feeds. Thanks to HackerCow for pointing out that I don't have to append a new line in a different question, prompting me to remove it here and save 4 bytes

Golfed code:

using C=System.Console;class P{static void Main(){var D=C.In.ReadToEnd().Replace("\r","").Split('\n');int w=D[0].Length+2,h=D.Length+1,i=0,j,c,T=0,O=1,o,z,R=0;var B=new int[w,h];var S=new int[w*h*9];for(;i++<w-2;)for(j=0;j<h-2;B[i,j]=c)if((c=(D[j++][i-1]-8)%10)>5){c=5;T++;S[0]=i+j*w;}for(i=0;++i<w-1;)for(j=0;++j<h-1;)R=(i%2+j%2>1&(o=B[i,j-1]%2+B[i-1,j]%2+B[i+1,j]%2+B[i,j+1]%2)>0&o!=2)|((c=B[i,j])<4&c!=o)?7:R;for(o=h=0;o<O;B[i,j]=0)if(B[i=(c=S[o++])%w,j=c/w]>4){h++;S[O++]=(S[O++]=c-w-1)+2;S[O++]=(S[O++]=c+w-1)+2;z=j%2<1?w*2:2;S[O++]=c-z;S[O++]=c+z;}C.Write(h-R<T?"n":"y");}}

The code performs 3 checks, first checking the number of lines around each number and that each junction has 0 or 2 lines leading from it, then that all the lines are joined together.

Formatted code:

using C=System.Console;

class P
{
    static void Main()
    {
        var D=C.In.ReadToEnd().Replace("\r","").Split('\n');
        int w=D[0].Length+2,h=D.Length+1,i=0,j,c,T=0,O=1,o,z,R=0;
        var B=new int[w,h]; // this is the grid
        var S=new int[w*h*9]; // this is a list of joined up lines (stored as x+y*w)

        for(;i++<w-2;)
            for(j=0;j<h-2;B[i,j]=c)
                if((c=(D[j++][i-1]-8)%10)>5)
                { // we are a line
                    c=5;
                    T++; // increment line counter
                    S[0]=i+j*w; // set start of loop
                }

        for(i=0;++i<w-1;) // this loop checks the numbers and that every + has 0 or 2 lines leading from it
            for(j=0;++j<h-1;)
                R=(i%2+j%2>1&(o=B[i,j-1]%2+B[i-1,j]%2+B[i+1,j]%2+B[i,j+1]%2)>0&o!=2)|((c=B[i,j])<4&c!=o)?7:R; // set R to 7 (no significance) if check fails

        for(o=h=0;o<O;B[i,j]=0) // this loops through the list of joined lines adding more until the whole loop has been seen
            if(B[i=(c=S[o++])%w,j=c/w]>4)
            {
                h++; // increment "seen" counter
                S[O++]=(S[O++]=c-w-1)+2;
                S[O++]=(S[O++]=c+w-1)+2;
                z=j%2<1?w*2:2; // special for | and -
                S[O++]=c-z;
                S[O++]=c+z;
            }

        C.Write(h-R<T?"n":"y"); // check if R is greater than 0 or h is less than T and output appropriately
    }
}


Bash, 251 246 bytes

r=$RANDOM
((r%5<4))||exit
[[ $1 =~ PIG ]]||(echo "File must contain the string 'PIG'.";exit)
s=(GRUNT MOAN OINK BURP GROAN WHINE)
m=("${1#*PIG}" ${s[r%6]}
"Your pig has unfortunately died. Please try again." "$1")
echo -n "${m[r%5]}">"${1%%PIG*}"

This would be a lot shorter if deaf pigs could at least read...


Design a commutative injective function between any (restricted) infinite set and unordered pairs thereof

Haskell, 65 + 30 = 95 bytes

a#b=length.fst$span(<(max a b,min a b))[(a,b)|a<-[1..],b<-[1..a]]

Try it online!

([(a,b)|a<-[1..],b<-[1..a]]!!)

Try it online!

Note: When the two functions may share code, this is only 75 bytes:

(l!!)
a#b=length.fst$span(<(max a b,min a b))l
l=[(a,b)|a<-[1..],b<-[1..a]]

Try it online! The domain is the positive integers. The function (#) performs the pairing, the function (l!!) its inverse. Usage example: Both (#) 5 3 and (#) 3 5 yield 12, and (l!!) 12 yields (5,3).

This works by explicitly listing all sorted pairs in an infinite list l:

l = [(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4),(5,1),(5,2),(5,3),(5,4),(5,5),(6,1), ...`

The encoding is then just the index in this list.


Missing Integer Sequence Detection -- Filesystem

Python 2, 101 bytes

2 bytes thanks to @xnor.

import os
t=-1
for n in range(input(),input()+1):
 if~-os.path.isfile(str(n)):
  if~t+n:print n
  t=n


Mathematica - 120 bytes

g=CellularAutomaton[{(l=Flatten@#;c=l[[14]];n=Total@Drop[l,{14}];Which[n<2||n>7,0,n==5||c==1,1,0<1,0])&,{},{1,1,1}},##]&

Certainly not a contender for the win, but that was not my intention. Also, this could probably be golfed down significantly by just figuring out the rule number. I just really wanted to write a visualisation (although I'm actually sure there are already tons out there). So here we go):

animateGol3d[size_, i_, n_] :=
  ListAnimate[
    Graphics3D[
      Cuboid /@ Position[#, 1],
      PlotRange -> {{0, size}, {0, size}, {0, size}} + 1
    ] & /@ g[i, n]
  ];

And after experimenting with a bunch of initial conditions, I got things like the following:

And here is one with a grid size of 20x20x20. This took a few seconds to simulate and render:

By the way, this assumes periodic boundary conditions.


Output a text that doesn't output any of the characters used in the instructions to output the text

Jelly, 0 bytes, score: 1/0 = ∞

Try it online!
That's right, the empty program in Jelly prints 0.
Jelly, 5 bytes, score: 1000.6
⁶³ȷ³x

Try it online!
Jelly, 2 bytes, score: 95 / 2 = 47.5
ØṖ

Try it online!
This yields the set of all printable ASCII: !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ and a space (95 bytes)


Mathematica, 302 bytes

(b=Prepend;i=1;n=15#&@@#-15+Range@5&;g=#~b~{N,0};o={#2,#3,#,##4}&@@#&;While[(l=Length@Union[t=(k=Take)[#&@@@g,i]])<5&&Max[#2&@@@Tally@t]<5,i++];If[l<5,m=#&@@Commonest@t;If[m===#,o[g~k~i/.{m,x_}->x/.{_,_}->Nothing],n@#2]&,o@DeleteDuplicates@b[n@#2,<|#->#2&@@@Reverse@g|>@#]~k~5&]~MapIndexed~{B,I,N,G,O})&

Unnamed function taking as its argument a list of ordered pairs, such as {{N,42},{N,34},{O,66},{N,40},...} (note that the first element in each ordered pair is not a string but rather a naked symbol), and returning a 2D list of integers, where the sublists represent columns (not rows) of the bingo board.

Output for the first test case:

{{1,3,2,4,5},{17,18,16,19,20},{31,32,0,33,34},{46,48,47,49,50},{62,63,61,64,65}}

In general, when the earliest possible bingo occurs because of a number called in each of the B/I/G/O rows, then those numbers will be in the center row; each column will otherwise contain the four smallest possible numbers (taking the already used number into account). For example, if the first test case is changed so that the second number called is B12 rather than B2, then the first column of the output board will be {1,2,12,3,4}.

Output for the second test case:

{{1,2,3,4,5},{16,17,18,19,20},{42,34,0,40,41},{46,47,48,49,50},{61,62,63,64,65}}

In general, when the earliest possible bingo occurs because of five numbers called in a single column (or four called in the N column), then the remaining four columns contain their five smallest possible numbers in order.

If the second test case is changed from {{N,42},{N,34},{O,66},{N,40},...} to {{O,72},{O,74},{O,66},{N,40},...} (only the first two entries changed), then the output is:

{{1,2,3,4,5},{16,17,18,19,20},{31,32,33,34,35},{46,47,48,49,50},{74,66,72,65,63}}

Somewhat ungolfed version:

(b=Prepend;i=1;n=15First[#]-15+Range[5]&;g=b[#,{N,0}];o={#2,#3,#,##4}&@@#&;
While[
    (l=Length[Union[t=(k=Take)[Apply[#&,g,{1}],i]]])<5
  &&
    Max[Apply[#2&,Tally[t],{1}]]<5,
  i++];
MapIndexed[
  If[l<5,
    m=First[Commonest[t]];If[m===#,o[k[g,i]/.{m,x_}->x/.{_,_}->Nothing],n[#2]]&,
    k[
      o[DeleteDuplicates[b[n[#2],Association[Apply[#->#2&,Reverse[g],{1}]][#]]]]
    ,5]&
  ],{B,I,N,G,O}
])&

The first line is mostly definitions to shorten the code, although g prepends the center square {N,0} to the input to simplify the bingo-finding. (The n function gives the smallest five legal bingo numbers in the #th column, 1-indexed. The o function takes a 5-tuple and moves the first element so that it's third.)

The While loop in lines 2-6 finds the smallest initial segment of the input that contains a bingo. (The third line tests for one-in-each-column bingos, while the fifth line tests for single-column bingos).

For any function F, the operator MapIndexed[F,{B,I,N,G,O}] (starting in line 7) produces the 5-tuple {F{B,1},F{I,2},F{N,3},F{G,4},F{O,5}} (well, technically it's {F{B,{1}},...}); we apply a function F that creates a bingo-board column out of its two arguments. That function, however, depends on which type of bingo was found: line 8 is true when we have a single-column bingo, in which case the function (line 9) uses the relevant input numbers in the bingo column and default numbers in the other columns. In the other case, the function (lines 10-12) uses the relevant input numbers in the center of each column and default numbers elsewhere.


05AB1E, 9 4 bytes (A000040 and A040000)

Ø=>≠

Try it online!

!enilno ti yrT

Explanation:

Ø          # nth prime
 =         # output
  >≠       # ignored

:noitanalpxE

≠          # boolean negation (0 if n == 1, 1 otherwise)
 >         # increment
  =        # output
   Ø       # ignored


Bean, 116 121 118 bytes

Hexdump:

00000000 26 55 cd a0 62 80 40 a0 6f 53 d0 80 d3 d0 80 a0  &UÍ b.@ oSÐ.ÓÐ.
00000010 6f 20 80 0d 21 80 81 00 20 80 92 20 6f 53 d0 80  o ..!... .. oSÐ.
00000020 a0 78 20 80 83 40 a0 5d a0 5e 53 d0 80 d3 a0 62   x ..@ ] ^SÐ.Ó b
00000030 20 5d 20 80 8b 40 a0 5f a0 60 a0 65 a0 6e dd a0   ] ..@ _ ` e nÝ
00000040 61 50 84 d3 a0 62 20 5e 20 65 4e ce a0 5f 80 4c  aP.Ó b ^ eNÎ _.L
00000050 a0 60 8c 20 61 80 53 d0 80 d3 50 80 a0 60 20 80   `. a.SÐ.ÓP. ` .
00000060 b9 20 80 b3 53 50 80 a0 61 20 80 b9 a8 dc c4 aa  ¹ .³SP. a .¹¨ÜÄª
00000070 a9 a8 dc e4 aa 29                                ©¨Üäª)
00000076

Equivalent JavaScript (140 bytes, ignoring added whitespace for formatting):

f=s=>s.split(/(\D*)(\d*)/).concat(s),
_.sort(
  (a,b)=>f(a).reduce(
    (c,d,i,r,e=f(b)[i])=>
      c||d-e||d.toLowerCase().localeCompare(e.toLowerCase())
  )
)

Basically a golfed version of the example implementation given in the question.

Click here for the demo!


R, 54 50 41 bytes

order(-tabulate(combn(scan(),2,prod)))[1]

Try it online!

Alternatively, for 54 53 44 bytes:

names(sort(-table(combn(scan(),2,prod))))[1]

Try it online!

In principle, the latter version outputs the relevant result even without the names function, but followed by the count of such most frequent products, which isn't asked for...

Thanks to CriminallyVulgar  for -4 and -1, and Giuseppe for -9 on both.


Haskell, 97 96 95 bytes

-1 byte thanks to nimi

f s=all(r s/=)$foldr($)s<$>mapM(\_->[id,g,map g])[1..6]
g=r.foldr(zipWith(:))e
r=reverse
e=[]:e

Try it online!

Explanation

Ok, this is a bit mathy. It is well known that the group of rotations as described in the challenge (i.e. the group generated by rotations of 90 degrees around one of the three principal axes) is isomorphic to the symmetric group \$S_4\$, as described here. It is also well known that \$S_4\$ is generated by the elements \$(1\, 2\, 3\, 4),(1\, 3\, 2\, 4)\$.

What I am trying to say is this: fix two distinct axes, and call the 90 degrees rotations about those axes \$r_1\$ and \$r_2\$. Then we can generate all the rotations by repeatedly applying \$r_1\$ and \$r_2\$. A bit of bruteforce shows that we only need up to 6 applications of \$r_1\$ and \$r_2\$.

Thus we have the following algorithm: given a three-dimensional text \$s\$, we apply all possible rotations to \$s\$ and check whether any of those matches \$s\$ flipped along an axis. The rotations are generated by composing up to six 90 degrees rotations about two fixed axes.

g=r.foldr(zipWith(:))e
e=[]:e

g is a 90 degrees rotation of a 2D list (also works on 3D lists, as those can be seen as 2D lists of 1D lists). The foldr(zipWith(:))e is simply transpose from Data.List, but shorter.

f s=all(r s/=)$foldr($)s<$>mapM(\_->[id,g,map g])[1..6]

f checks whether its argument s is chiral.

mapM(\_->[id,g,map g])[1..6] generates a list of all sequences of length 6 whose elements are any of id (the identity transformation, i.e. do nothing), g (90 degrees rotation about an axis), map g (90 degrees rotations about a different axis).
given a list [f1,f2,...,f6] of transformations, foldr($)s computes f1(f2(...f6(s)...), and (r s/=) checks whether the result is equal to s reversed (i.e. a mirror image of s).

So what f does is check if any rotation of s matches its mirror image, returning False if it does and True otherwise.


SVG + Javascript

▶▶▶ Live demo here ◀◀◀
This uses SVG's built-in animation functions to turn the hands, with a bit of additional Javascript to fetch the local time and set the initial hand positions. It works OK in Chrome and Safari, and should be compatible with most modern browsers as it doesn't use any filter effects.
<?xml version="1.0"?>
<svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" viewBox="0 0 400 400" width="400" height="400" version="1.0">
  <defs>
    <linearGradient id="a" x1="0%" y1="100%" x2="0%" y2="0%">
      <stop offset="0%" style="stop-color:#777799"/>
      <stop offset="100%" style="stop-color:#ffffff"/>
    </linearGradient>
    <linearGradient id="b" x1="0%" y1="100%" x2="0%" y2="0%">
      <stop offset="0%" style="stop-color:#ffffff"/>
      <stop offset="25%" style="stop-color:#b6b6cc"/>
      <stop offset="40%" style="stop-color:#515177"/>
      <stop offset="48%" style="stop-color:#ffffff"/>
      <stop offset="56%" style="stop-color:#ffffff"/>
      <stop offset="75%" style="stop-color:#8b8baa"/>
      <stop offset="98%" style="stop-color:#efeff4"/>
      <stop offset="100%" style="stop-color:#fbfbfc"/>
    </linearGradient>
    <linearGradient id="c" x1="0%" y1="100%" x2="0%" y2="0%">
      <stop offset="0%" style="stop-color:#ffffff"/>
      <stop offset="100%" style="stop-color:#777799"/>
    </linearGradient>
    <radialGradient id="d" cx="50%" cy="50%" r="50%" fx="50%" fy="50%">
      <stop offset="0%" style="stop-color:#ffffff"/>
      <stop offset="40%" style="stop-color:#ffffff"/>
      <stop offset="70%" style="stop-color:#e6e6ee"/>
      <stop offset="92%" style="stop-color:#b6b6cc"/>
      <stop offset="100%" style="stop-color:#636388"/>
    </radialGradient>
    <radialGradient id="e" cx="50%" cy="150%" r="200%" fx="50%" fy="150%">
      <stop offset="0%" style="stop-color:#ffffff;stop-opacity:0"/>
      <stop offset="59%" style="stop-color:#ffffff;stop-opacity:0"/>
      <stop offset="60%" style="stop-color:#ffffff;stop-opacity:0.6"/>
      <stop offset="70%" style="stop-color:#ffffff;stop-opacity:0.3"/>
      <stop offset="100%" style="stop-color:#ffffff;stop-opacity:0.0"/>
    </radialGradient>
  </defs>
  <g transform="translate(200 200)">
    <circle cx="0" cy="0" r="200" fill="#cecedd"/>
    <circle cx="0" cy="0" r="196" stroke="url(#a)" stroke-width="5" fill="url(#b)"/>
    <circle cx="0" cy="0" r="170" stroke="url(#c)" stroke-width="4" fill="url(#d)"/>
    <circle cx="0" cy="0" r="172" stroke="#ffffff" stroke-width="0.5" fill="none"/>
    <circle cx="0" cy="0" r="193.5" stroke="#ffffff" stroke-width="0.5" fill="none"/>
    <g id="O">
      <polygon points="4,155 4,130 -4,130 -4,155" style="fill:#777799;stroke:#313155;stroke-width:1"/>
      <polygon points="4,-155 4,-130 -4,-130 -4,-155" style="fill:#777799;stroke:#313155;stroke-width:1"/>
    </g>
    <g transform="rotate(30)"><use xlink:href="#O"/></g>
    <g transform="rotate(60)"><use xlink:href="#O"/></g>
    <g transform="rotate(90)"><use xlink:href="#O"/></g>
    <g transform="rotate(120)"><use xlink:href="#O"/></g>
    <g transform="rotate(150)"><use xlink:href="#O"/></g>
    <polygon id="h" points="6,-80 6,18 -6,18 -6,-80" style="fill:#232344">
      <animateTransform id="ht" attributeType="xml" attributeName="transform" type="rotate" from="000" to="000" begin="0" dur="86400s" repeatCount="indefinite"/>
    </polygon>
    <polygon id="m" points="3.5,-140 3.5,23 -3.5,23 -3.5,-140" style="fill:#232344">
      <animateTransform id="mt" attributeType="xml" attributeName="transform" type="rotate" from="000" to="000" begin="0" dur="3600s" repeatCount="indefinite"/>
    </polygon>
    <polygon id="s" points="2,-143 2,25 -2,25 -2,-143" style="fill:#232344">
      <animateTransform id="st" attributeType="xml" attributeName="transform" type="rotate" from="000" to="000" begin="0" dur="60s" repeatCount="indefinite"/>
    </polygon>
    <circle cx="0" cy="0" r="163" fill="url(#e)"/>
  </g>
  <script type="text/javascript"><![CDATA[
    var d = new Date();
    var s = d.getSeconds();
    var m = d.getMinutes() + s/60;
    var h = (d.getHours() % 12) + m/60 + s/3600;
    document.getElementById('st').setAttribute('from',s*6);
    document.getElementById('mt').setAttribute('from',m*6);
    document.getElementById('ht').setAttribute('from',h*30);
    document.getElementById('st').setAttribute('to',360+s*6);
    document.getElementById('mt').setAttribute('to',360+m*6);
    document.getElementById('ht').setAttribute('to',360+h*30);
  ]]></script>
</svg>


J, 60 58 50 47 bytes
[:+/(*1,:1-(1<1#.+/=/+/)+{.(~:*[=i.{_,~])+/)^:_

Try it online!
Takes input as a matrix of complex numbers -- starting positions in the 1st row, steps to walk in the 2nd row.
Passes all test cases including those suggested by tsh and the cycle of 4 suggested by xnor.
tldr how
We iteratively adjust the steps to be 0 for impossible moves (same destination (1<1#.+/=/+/) or + swaps {.(~:*[=i.{_,~])+/) until they reach a fixed point ^:_.  Iteration is needed because some steps only become illegal after a walker changes from someone who will move to someone standing still.  There's a chain reaction.
After that iteration, impossible steps will have been converted to 0, and legal steps will remain what they were.
Once that's done, we just add those steps to the starting positions [:+/.


Python 3, 97 bytes

This script is based on @Mego's answer

a=0
for c in input():a-=c=='=';print({'+':'+-','>':'><','|':'[]'}.get(c,c)[a%-2]*(c!='='),end='')


Find the largest prime whose length, sum and product is prime


Python 2 - 80, 68, 64, 61, 58, 50, 48, 45, 44 42

Even though it's getting a little ridiculous now, I'll keep on making use of free library imports, even the __builtin__ library:

from numpy import diff as D
from pprint import pprint as P
from __builtin__ import all as A
from __builtin__ import raw_input as I
from __builtin__ import bytearray as B

So only the following short line counts towards the code length:

P(A(D([(o-o/112-o/59)/3for o in B(I())])))

Credits to Markuz for the ideas regarding input()! These free-import challenges always introduce you to some lesser known libraries. ;)

Alternative using only the operator library (98, 83 79):

from operator import ne as n
K=[(ord(c)-1-(c>'p')-(c>'w'))/3for c in input()]
print all(map(n,K[1:],K[:-1]))

I'll stop here. But you could further golf this version using sys, pprint and other libraries...

Alternative without libraries (105):

s=input()
n=lambda c:(ord(c)-1-(c>'p')-(c>'w'))/3
print all([n(s[i])!=n(s[i+1])for i in range(len(s)-1)])


05AB1E, 36 35 33 bytes

Saved 1 byte thanks to Mr.Xcoder
Saved 2 bytes thanks to KevinCruijssen

ć©¡®ì®D…IAO©â'D«‚˜®'U«âJskh2ôJHçJ

Try it online!
or as a Test Suite

Explanation

ć©¡                                 # extract the head ("B") and split input on it
   ®ì                              # prepend "B" to each
     ®D                            # push 2 copies of "B"
       …IAO©â                      # cartesian product with "IAO"
             'D«                   # append "D" to each
                ‚˜                 # add the leftover "B" to the list
                  ®'U«â            # cartesian product with "IAOU"
                       J           # join each to string
                        sk         # get the index of each word of the input in this list
                          h        # convert each to hex
                           2ôJ     # format as pairs of chars
                              H    # convert to int
                               çJ  # convert from ascii-codes to string


Find the \$\left(n^2\right)^\text{th }n\$-gonal number

Wolfram Language (Mathematica), 19 bytes

#(4-#-2#^2+#^3)#/2&

Try it online!

Just a golfy version of the second formula.

With PolygonalNumber built-in, 23 bytes

PolygonalNumber[#,#^2]&

Try it online!

As expected, the Mathematica built-in is longer than the golfed version.


GolfScript, 338 323 307 300 280 * 15 10 = 2800
{:x;.2$<)65-x+26%65+[]++\@>+}:d;
{[{}{4-4d}{);}{2 1d}{'A'\+}{-1%}{2$~}{....2<\[-2=]+\3>-2<+\[2=]+\-1>+}]=}:L;
1:i;
'RDLATIVE':&;
'"S<(hR\50%!iS[SA*v7qpq&={=kkkk."Y+iEpi5-]'{32-}%95base`8/
{1:j;0L.@{48-:^j*L@;.&\~:&;i'0'6*\+-6>': ''JDDIIIRSMEENNNEWPCLCSVPT'^>8%' '&n^0>:j;i):i;}%n@;@;}/

Newlines added for clarity only, and can be removed. Pretty sure the output is correct.
Test online
It probably can be golfed further.

I managed to chop off an entire 5 chunks of op-codes (although I did have to rewrite most of the algorithm).
Output:
000001: INC RELATIVE
000002: DEL RELATIV
000003: REP RELATI
000004: INS ARELATI
000005: DEC AREHATI
000006: INV ITAHERA
000007: JMP ITAHERA
000008: SWT ITAHERA

000009: DEC ITADERA
000010: INS AITADERA
000011: INV AREDATIA
000012: DEL AREDATI
000013: INC ASEDATI
000014: JMP ASEDATI
000015: SWT ASEDATI
000016: REP ASEDATI

000017: DEC ASEZATI
000018: INV ITAZESA
000019: DEL ITAZES
000020: SWT ITEZAS
000021: INS AITEZAS
000022: JMP AITEZAS
000023: INC AITEZAS
000024: REP AITEZAS

000025: DEC AITAZAS
000026: REP AITWZAS
000027: INS AAITWZAS
000028: INC ABITWZAS
000029: INV SAZWTIBA
000030: DEL SAZWTIB
000031: JMP SAZWTIB
000032: SWT SAZWTIB

000033: DEC SAZSTIB
000034: DEL SAZSTI
000035: INV ITSZAS
000036: SWT ITAZSS
000037: INS AITAZSS
000038: REP AAITAZSS
000039: JMP AAITAZSS
000040: INC AAITAZSS

000041: DEL AAITAZS
000042: INV SZATIAA
000043: INC SAATIAA
000044: REP SBATIAA
000045: INS ASBATIAA
000046: JMP ASBATIAA
000047: DEC ASBATIAA
000048: SWT ASAATIBA

000049: SWT ASBATIAA
000050: INS AASBATIAA
000051: INV AAITABSAA
000052: INC ABITABSAA
000053: DEL ABITABSA
000054: JMP ABITABSA
000055: DEC ABITABSA
000056: REP ABITABSA

000057: INV ASBATIBA
000058: DEL ASBATIB
000059: INS AASBATIB
000060: DEC AASXATIB
000061: JMP AASXATIB
000062: INC AASXATIB
000063: SWT AAIXATSB
000064: REP AASXATIB

000065: INV BITAXSAA
000066: DEL BITAXSA
000067: REP BITAXS
000068: SWT BIXATS
000069: INS ABIXATS
000070: INC ACIXATS
000071: JMP ACIXATS
000072: DEC ACIXATS

000073: INS AACIXATS
000074: INC ABCIXATS
000075: INV STAXICBA
000076: DEL STAXICB
000077: REP STAXIC
000078: JMP STAXIC
000079: SWT STAXIC
000080: DEC STATIC


J, 37 34 bytes

0<@|:' x'{~((i.@]e.#.~)1+>./) ::#:

Try it online!

                       1+>./          maximum for each coordinate + 1
             i.@]                     make an array with these dimensions filled with 0..x*y
                                      /* if the input is empty,
                                         1+>./ is negative infinity
                                         and i.@] throws an error  */
                   #.~                mixed base conversion of input
                 e.                   replace the elements of i.@]
                                        with 1 if it's present in the
                                        converted input, 0 otherwise
           (                ) ::      if there's an error do the other thing instead
                                #:    "to binary", for empty input this returns a 0x0 matrix
0<@|:' x'{~                           index into character string, transpose and put in a box


Calculate the average longest common substring exactly

C++, n = 21 (40s on an AMD Ryzen 5 2500U)
This used to be a fast brute force answer that got up to n=17. That is currently preserved in the revision history.
#include <cstring>
#include <omp.h>
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <bitset>
#include <random>

typedef unsigned uint;
typedef unsigned char byte;
const int threadnum = 8;
const int maxn = 22; //for 24 bytes total size of Row
struct Row; struct hasher { size_t operator ()(const Row& row) const; };
struct Row
{
    char max = 0;
    std::array<char, maxn+1> row {0};
    Row() { }
    Row(int nmax)
    {
        max = nmax;
    }
    bool operator ==(const Row& rhs) const
    {
        const uint64_t* x = reinterpret_cast<const uint64_t*>(this);
        const uint64_t* y = reinterpret_cast<const uint64_t*>(&rhs);
        return x[0] == y[0] && x[1] == y[1] && x[2] == y[2];
    }
};
uint64_t rotl(uint64_t x, char a)
{
    return (x << a) | (x >> (64 - a));
}
size_t hasher::operator() (const Row& row) const
{
    const uint64_t* mem = reinterpret_cast<const uint64_t*>(&row);
    //I tried really many different hashes...
    uint64_t h = mem[0]; h += rotl(h, 4);
    h         ^= mem[1]; h += rotl(h, 4);
    h         ^= mem[2]; h += rotl(h, 4);
    return h;
}
const short hashTableSize = 1009;
struct Map
{
    std::array<std::pair<Row, int>, hashTableSize> table {};
    Map()
    {
    }
    void add_or_add(const Row row, const int delta)
    {
        size_t hash = hasher()(row) % hashTableSize;
        while(table[hash].second != 0 && !(table[hash].first == row))
        {
            hash++;
            if(hash == hashTableSize) hash = 0; //just loop :)
        }
        if(table[hash].second == 0)
            table[hash].first = row;
        table[hash].second += delta;
    }
    void clear()
    {
        std::memset(table.data(), 0, sizeof(table));
    }
};

constexpr uint bitRev(uint n)
{
    n = ((n >> 1) & 0x55555555) | ((n << 1) & 0xaaaaaaaa);
        n = ((n >> 2) & 0x33333333) | ((n << 2) & 0xcccccccc);
        n = ((n >> 4) & 0x0f0f0f0f) | ((n << 4) & 0xf0f0f0f0);
        n = ((n >> 8) & 0x00ff00ff) | ((n << 8) & 0xff00ff00);
        n = ((n >>16) & 0x0000ffff) | ((n <<16) & 0xffff0000);
        return n;
}
constexpr bool is_substring(int target, char n, short subs, char m)
{
    //n=2, m=1 -> i from 0 to 1
    int max = n-m+1;
    bool flag = false;
    for(int i = 0; i < max; i++)
        flag |= (((target >> i) ^ subs) & ((1<<m) - 1)) == 0;
    return flag;
}
int supermax = 0;
int main()
{
    uint n; std::cin >> n;
    std::vector<uint64_t> sums(threadnum);
    uint64_t sum = 0;
#pragma omp parallel for num_threads(threadnum) schedule(dynamic)
    for(uint sa = 0; sa < 1<<~-n; sa++) //the second half is the bitwise complement of the first one
    {
        uint sb = bitRev(sa);
        sb ^= -(sb >> 31);
        sb >>= 32 - n;
        if(sb < sa) continue;
        //find a lower bound = len(the shortest non-substring of sa) - 1
        //if Row.max is immediately set to it, that reduces the number of states slightly
        char lb = 0; bool found = false;
        for(char len = 0; len < 10; len++)
        {
            for(short j = 0; j < (1<<len); j++)
                if(!is_substring(sa, n, j, len))
                {
                    lb = len - 1;
                    goto out;
                }
        }
        out:;
        Map dpcur;
        Map dpnext;
        dpcur.add_or_add(Row(lb), 1);
        int ans = 0;
        for(char j = 0; j < n; j++)
        {
            for(auto[row, cnt] : dpcur.table)
            {
                if(!cnt) continue;
                Row nr0 {}, nr1 {};
                nr0.max = nr1.max = row.max;
                for(char i = 0; i < n; i++)
                {
                    Row& r = (sa >> i)&1 ? nr0 : nr1;
                    r.row[i+1] = row.row[i] + 1;
                }
                char n0max = 0, n1max = 0;
                for(char i = 0; i < 23; i++)
                    n0max = std::max(n0max, nr0.row[i]);
                for(char i = 0; i < 23; i++)
                    n1max = std::max(n1max, nr1.row[i]);
                //possibly, cut an entire would-be branch that would never improve!
                if(n0max + n - j - 1 <= nr0.max)
                    ans += (cnt * nr0.max) << (n - j - 1);
                else
                    nr0.max = std::max(nr0.max, n0max), dpnext.add_or_add(nr0, cnt);
                if(n1max + n - j - 1 <= nr1.max)
                    ans += (cnt * nr1.max) << (n - j - 1);
                else
                    nr1.max = std::max(nr1.max, n1max), dpnext.add_or_add(nr1, cnt);
            }
            std::memcpy(dpcur.table.data(), dpnext.table.data(), sizeof(Map));
            dpnext.clear();
        }
        for(auto[row, cnt] : dpcur.table)
            ans += cnt * row.max;
        sums[omp_get_thread_num()] += ans;
        if(sb != sa)
            sums[omp_get_thread_num()] += ans;
    }
    for(uint64_t e : sums) sum += e;
    sum *= 2;
    printf("%ld\n", sum);
    uint64_t num = sum, denom = 1ll<<(2*n);
    while(num % 2 == 0) num /= 2, denom /= 2;
    printf("%ld/%ld\n", num, denom);
}

This uses OpenMP for multi-threading. To be compiled with clang++ -std=c++17 -Ofast -march=native -flto -fopenmp file.cpp.
Explanation I tried (please don't use it as a Rust translation guide)
The longest common substring can be found in \$O(n^2)\$ time via dynamic programming. That dynamic programming can be calculated (if the strings are \$s\$ and \$t\$) via the formula $$dp_{i,j} = \begin{cases}dp_{i-1,j-1} + 1& s_i = t_j\\0& \text{otherwise}\end{cases}$$
(and then the answer is just the highest value in \$dp\$). A naive solution would be to iterate over pairs of strings of length \$n\$ (resulting in \$O(4^n n^2)\$ time complexity). However, instead of simply doing that, my program only iterates over all possible values of the first string. Then, it simply does that, but instead of storing a proper dynamic programming array (that wouldn't be possible because there is no second string), it stores an array of all possible rows in it with counters of how many ways exist to reach this row. To calculate the next array of possible rows from the current array of possible rows, my program simply tries all of them with both possible values of the next bit in the second string. This leads to a speedup, because if two prefixes of the second string lead to the same state, they can be "merged" into one execution path.
I suspect this is similar to the optimization from the top answer in a similar challenge but for Levenshtein distance, but the explanation there is so bad I couldn't understand it at all.
The optimization that got this to 21: if at a certain point a possible row is encountered such that all its numbers are too small to ever improve the length of the longest substring in it, it can be directly calculated how much it will add to the answer.
Takes input as a single number from stdin. Outputs 734551/131072 for 13, 392340511/67108864 for 14, 1630366263/268435456 for 15, 6751032665/1073741824 for 16, 6967595579/1073741824 for 17, 114759115773/17179869184 for 18, 235733542633/34359738368 for 19, 1933121200141/27877906944 for 20 and 7912473298597/1099511627776 for 21.


Haskell, 207 206 (209?) characters

import Data.List
x![]=[x];(w:x)!(y:z)|w==y=x!z;_!_=[]
a@(w:x)%b=a!b++[w:e|e<-x%b];a%b=a!b
h=show
f n=[(c,n-c)|c<-[1..n-1],i<-inits$h c,s<-init$tails i,s/=h c,a<-h c%s,b<-h(n-c)%s,read a*(n-c)==read('0':b)*c]

If it's not allowable to return the same ratio more than once (400/400 = 40/40 = 4/4), use f n=nub[... to filter them out.
Returns a list of pairs. A list of two-element pairs costs the same. A list of actual fractions would require importing Data.Ratio or fully qualifying Data.Ratio.% (which also collides with the % function defined here)
test cases (with nub):
Prelude Data.List> f 80
[(10,70),(16,64),(20,60),(30,50),(40,40),(50,30),(60,20),(64,16),(70,10)]
Prelude Data.List> f 147
[(49,98),(98,49)]
Prelude Data.List> f 500
[(10,490),(20,480),(30,470),(40,460),(50,450),(60,440),(70,430),(80,420),(90,410
),(100,400),(110,390),(120,380),(130,370),(140,360),(150,350),(160,340),(170,330
),(180,320),(190,310),(200,300),(210,290),(220,280),(230,270),(240,260),(250,250
),(260,240),(270,230),(280,220),(290,210),(300,200),(310,190),(320,180),(330,170
),(340,160),(350,150),(360,140),(370,130),(380,120),(390,110),(400,100),(410,90)
,(420,80),(430,70),(440,60),(450,50),(460,40),(470,30),(480,20),(490,10)]

ungolfed and commented:
import Data.List

-- haystack ! needle - the haystack with the needle removed, wrapped in a single-element list
--                       or an empty array if the haystack does not start with the needle

x ! [] = [x]                        -- case: empty needle = match with the full haystack left
(h:hs) ! (n:ns) | h == n = hs ! ns  -- case: needle and haystack match
_ ! _ = []                          -- case: no match

-- haystack % needle - the haystack with the needle removed
--                       for all positions of the needle in the haystack

a@(h:hs) % b = a ! b ++ map (h:) (hs%b) -- either remove the needle here, or elsewhere
a % b = a                               -- empty haystack cannot be popped

-- f - the function we are interested in

f total = [ (num, total - num)
          | num   <- [1 .. total-1],            -- for each numerator in range
            i     <- inits $ show num,          -- for each postfix of the numerator
            sub   <- init $ tails i,            -- for each prefix of the postfix except the last (empty) one
            sub /= show num,                    -- that isn't equal to the numerator
            reNum <- show num % sub,            -- remove the substring from the numerator
            reDiv <- show (total - num) % sub,  -- as well as from the denominator.

                                                -- the resulting ratios must be equal by value:
            (read reNum) ^ (total - num) == (read '0':reDiv) * num]


PHP, 100

More efficient, 101

<?$a=$argv[0];$b=file_get_contents($a);file_put_contents($a,$b.substr($b,81,20));echo"Hello World\n";

This script is appending an echo"Hello World";, but because you said the size should also vary, and because it's shorter, I'm also having this script:

Shorter, 100

<?$a=$argv[0];$b=file_get_contents($a);file_put_contents($a,$b.substr($b,2,98));echo"Hello World\n";

This script is appending itself, in a way it adds one Hello World, but this version will overall take more space and takes longer to execute.

Example

But the scripts don't vary when it comes to the output:

root@raspberrypi:~/stack# php hello_expand.php
Hello World
root@raspberrypi:~/stack# php hello_expand.php
Hello World
Hello World
root@raspberrypi:~/stack# php hello_expand.php
Hello World
Hello World
Hello World


Python 2, 122 115 110 106 bytes

n=m=input()
s=0
for d in range(2,n):
 while n%d<1:n/=d;s+=sum(map(int,`d`))
print n<m>s==sum(map(int,`m`))

Saved 4 bytes thanks to Dennis

Try it on ideone.com

Explanation

Reads a number on stdin and outputs True if the number is a Smith number or False if it is not.

n=m=input()                  # stores the number to be checked in n and in m
s=0                          # initializes s, the sum of the sums of digits of prime factors, to 0
for d in range(2,n):         # checks all numbers from 2 to n for prime factors
 while n%d<1:                # while n is divisible by d
                             #   (to include the same prime factor more than once)
  n/=d                       # divide n by d
  s+=sum(map(int,`d`))       # add the sum of the digits of d to s
print                        # print the result: "True" if and only if
      n<m                    #   n was divided at least once, i.e. n is not prime
      >                      #   and m>s (always true) and
      s==sum(map(int,`m`))   #   s is equal to the sum of digits of m (the input)


Wolfram Language (Mathematica), 28 27 bytes

#~BoundingRegion~"MinDisk"&

Try it online!

Built-ins are handy here. Output is a disk object with the centre and radius. Like others, I’ve found the 2nd and 3rd test cases to be different to the question.

Thanks to @lirtosiast for saving a byte!

If a list is required as output, this can be done in 35 bytes (at the cost of an additional 8 bytes). Thanks to @Roman for pointing this out.


Mathematica 63 40 37
My earlier submission was incorrect. I had misinterpreted what ConnectedComponents returns.  The present approach relies on Belisarius' suggestion to useVertexOutComponent. 3 additional chars saved by alephalpha.
The following generates an 11 by 11 adjacency matrix of 0's and 1's, where 1 indicates that the vertex with the row number is connected directly to the vertex corresponding to column number of the cell. (SeedRandom ensures that your matrix a will match mine.)
SeedRandom[21]
a = Array[RandomChoice[{0.9, 0.1} -> {0, 1}] &, {11, 11}];

Example
(37 chars)
 AdjacencyGraph@a~VertexOutComponent~4

{4, 1, 7, 8, 9, 3}

Verifying
The directed graph displays how to reach vertices {1, 7, 8, 9, 3} from vertex 4.
AdjacencyGraph[a, ImagePadding -> 30, VertexLabels -> "Name"]


Python 2, 108 89 87 86 bytes

x=y=0
for m in map(int,raw_input()):x+=m*y and(m-y)%3*3/2;y^=m
print"--i"[~x%4::2]+`y`

(Thanks to @grc and @xnor for the help)

Explanation

Let's split up the coefficient and the base matrix. If we focus on the base matrix only, we get this multiplication table (e.g. 13 is -i2, so we put 2):

  0123

0 0123
1 1032
2 2301
3 3210

which just happens to be the same thing as doing bitwise xor.

Now let's focus on the coefficients. If we let 0123 denote 1,i,-1,-i respectively, we get:

  0123

0 0000
1 0031
2 0103
3 0310

For this we first check if either number is 0 by doing m*y, taking care of the left column and top row. Adding in (m-y)%3 then gives:

  0123

0 0000
1 0021
2 0102
3 0210

which is close, except that we have 2 instead of 3. We account for this by performing *3/2.

For indexing, we notice that if we take the string "--i" and select every second character starting from indices 0123 we get "-i","-","i","".


Identifying Sequences for Cellular Automata

Python 2: 93 byte

M,L,n=input();a=[]
while L:z=zip(L,L[1:]);a+=z;L=[M[i][j]for i,j in z]
print len(set(a))==n*n

Straightforward implementation: Find all pairs by zipping, memorize them for later and apply M to L. Repeat. Compare the number of unique pairs found.

Input is of the form [[0,1],[1,0]], [0,1,0,0], 2.


Jelly, 6 5 4 bytes

²Ɠxm

Try it online!

How it works

²Ɠxm  Main link. Argument: n (integer)

²     Yield n².
 Ɠ    Read and eval one line of input. This yields a string s.
  x   Repeat the characters of s in-place, each one n² times.
   m  Takes each |n|-th character of the result, starting with the first if n > 0,
      the last if n < 0.


ES6 JavaScript 2126 + 311 = 2437 score

m=Math;s=n=>[b=m.min(m.sqrt(n)+.5|0,15),n-b*b];f=n=>(n<0?'d':'i').repeat(m.abs(n));g=(n,t)=>n<4?f(n):g((t=s(n))[0])+'s'+f(t[1]);q=n=>((x=g(n)).length>(z=[...n+''].map((k,i,a)=>i?(a[i-1]==a[i]?'':(y=f((l=s(k))[0]-a[i-1])+(l[0]?'s':'')+f(l[1])).length>m.abs(Q=a[i]-a[i-1])?f(Q):y):g(k)).join('o')).length?z:x)+'o'

Semi-commented:

m = Math; // Keep a reference to math
// This function returns the closest perfect square and the distance from that square to the number
// E.g. s(10) --> [3, 1] because 3^2 + 1 = 10
s = n => [b = m.min(m.sqrt(n) + .5 | 0, 15), n - b * b];
// This creates a bunch of "d"s or "i"s
// E.g. f(3) --> "iii" or f(-2) --> "dd"
f = n => Array(m.abs(n) + 1).join(n < 0 ? 'd' : 'i');
// This constructs the number as a number rather than by digit
g = (n, t) => n < 4 ?
              // If n is less than 4, then we can just increment in normally (base case)
              f(n) :
              // Otherwise, build the square root recursively and shift
              g((t = s(n))[0]) + 's' + f(t[1]);
// This maps based on digits (constructs the number by digit)
// This has now been removed and replaced inline because it is only used once
d = n => (a = [...(n + '')]).map((k, i) => i ? (a[i - 1] == a[i] ? '' : f((l = s(k))[0] - a[i - 1]) + (l[0] ? 's' : '') + f(l[1])) : g(k)).join('o');
// For the official function, compare the digit-method and nondigit-method and return the best one
q = n => ((x = g(n)).length > (z = d(n)).length ? z : x) + 'o'

This takes advantage of the fact that in deadfish, you can print more than one character.

Example: 10 compiles to iodo which is "print one, decrement, print zero."

Usage:

q(10) // --> iodo
q(16) // --> iisso

Here's json data of output:

{
    "0": "o",
    "1": "io",
    "2": "iio",
    "3": "iiio",
    "4": "iiso",
    "5": "iisio",
    "6": "iisiio",
    "7": "iiisddo",
    "8": "iiisdo",
    "9": "iiiso",
    "10": "iodo",
    "11": "ioo",
    "12": "ioio",
    "13": "ioiio",
    "14": "ioiso",
    "15": "iissdo",
    "16": "iisso",
    "17": "iissio",
    "18": "iissiio",
    "19": "ioiiso",
    "20": "iioddo",
    "21": "iiodo",
    "22": "iioo",
    "23": "iioio",
    "24": "iioso",
    "25": "iisiso",
    "26": "iisisio",
    "27": "iisisiio",
    "28": "iioisdo",
    "29": "iioiso",
    "30": "iiiodddo",
    "31": "iiioddo",
    "32": "iiiodo",
    "33": "iiioo",
    "34": "iiioio",
    "35": "iiioiio",
    "36": "iisiiso",
    "37": "iisiisio",
    "38": "iiiosdo",
    "39": "iiioso",
    "40": "iisoddddo",
    "41": "iisodddo",
    "42": "iisoddo",
    "43": "iisodo",
    "44": "iisoo",
    "45": "iisoio",
    "46": "iisoiio",
    "47": "iisoiiio",
    "48": "iisodsdo",
    "49": "iisodso",
    "50": "iiisddsio",
    "51": "iiisddsiio",
    "52": "iisiodddo",
    "53": "iisioddo",
    "54": "iisiodo",
    "55": "iisioo",
    "56": "iisioio",
    "57": "iisioiio",
    "58": "iisioiiio",
    "59": "iisioddso",
    "60": "iiisdsddddo",
    "61": "iiisdsdddo",
    "62": "iiisdsddo",
    "63": "iiisdsdo",
    "64": "iiisdso",
    "65": "iiisdsio",
    "66": "iisiioo",
    "67": "iisiioio",
    "68": "iisiioiio",
    "69": "iisiioiiio",
    "70": "iiisdsiiiiiio",
    "71": "iiisdsiiiiiiio",
    "72": "iiisddodddddo",
    "73": "iiisddoddddo",
    "74": "iiisddodddo",
    "75": "iiisddoddo",
    "76": "iiisddodo",
    "77": "iiisddoo",
    "78": "iiissdddo",
    "79": "iiissddo",
    "80": "iiissdo",
    "81": "iiisso",
    "82": "iiissio",
    "83": "iiissiio",
    "84": "iiissiiio",
    "85": "iiissiiiio",
    "86": "iiisdoddo",
    "87": "iiisdodo",
    "88": "iiisdoo",
    "89": "iiisdoio",
    "90": "iiissiiiiiiiiio",
    "91": "iiisoddddddddo",
    "92": "iiisodddddddo",
    "93": "iiisoddddddo",
    "94": "iiisodddddo",
    "95": "iiisoddddo",
    "96": "iiisodddo",
    "97": "iiisoddo",
    "98": "iiisodo",
    "99": "iiisoo",
    "100": "iodoo",
    "101": "iodoio",
    "102": "iodoiio",
    "103": "iodoiiio",
    "104": "iodoiiso",
    "105": "iodoiisio",
    "106": "iodoiisiio",
    "107": "iodoiiisddo",
    "108": "iodoiiisdo",
    "109": "iodoiiiso",
    "110": "ioodo",
    "111": "iooo",
    "112": "iooio",
    "113": "iooiio",
    "114": "iooiso",
    "115": "iooisio",
    "116": "iooisiio",
    "117": "iooiisddo",
    "118": "iooiisdo",
    "119": "iooiiso",
    "120": "ioioddo",
    "121": "ioiodo",
    "122": "ioioo",
    "123": "ioioio",
    "124": "ioioso",
    "125": "ioiosio",
    "126": "ioiosiio",
    "127": "ioioisddo",
    "128": "ioioisdo",
    "129": "ioioiso",
    "130": "ioiiodddo",
    "131": "ioiioddo",
    "132": "ioiiodo",
    "133": "ioiioo",
    "134": "ioiioio",
    "135": "ioiioiio",
    "136": "ioiioiiio",
    "137": "ioiiosddo",
    "138": "ioiiosdo",
    "139": "ioiioso",
    "140": "ioisoddddo",
    "141": "ioisodddo",
    "142": "ioisoddo",
    "143": "ioisodo",
    "144": "ioisoo",
    "145": "ioisoio",
    "146": "ioisoiio",
    "147": "ioisoiiio",
    "148": "ioisodsdo",
    "149": "ioisodso",
    "150": "ioisiodddddo",
    "151": "ioisioddddo",
    "152": "ioisiodddo",
    "153": "ioisioddo",
    "154": "ioisiodo",
    "155": "ioisioo",
    "156": "ioisioio",
    "157": "ioisioiio",
    "158": "ioisioiiio",
    "159": "ioisioddso",
    "160": "ioisiioddddddo",
    "161": "ioisiiodddddo",
    "162": "ioisiioddddo",
    "163": "ioisiiodddo",
    "164": "ioisiioddo",
    "165": "ioisiiodo",
    "166": "ioisiioo",
    "167": "ioisiioio",
    "168": "iissdddsdo",
    "169": "iissdddso",
    "170": "iissdddsio",
    "171": "iissdddsiio",
    "172": "iissdddsiiio",
    "173": "iissdddsiiiio",
    "174": "ioiisddodddo",
    "175": "ioiisddoddo",
    "176": "ioiisddodo",
    "177": "ioiisddoo",
    "178": "ioiisddoio",
    "179": "ioiisddoiio",
    "180": "ioiisdoddddddddo",
    "181": "ioiisdodddddddo",
    "182": "ioiisdoddddddo",
    "183": "ioiisdodddddo",
    "184": "ioiisdoddddo",
    "185": "ioiisdodddo",
    "186": "ioiisdoddo",
    "187": "ioiisdodo",
    "188": "ioiisdoo",
    "189": "ioiisdoio",
    "190": "iissddsddddddo",
    "191": "iissddsdddddo",
    "192": "iissddsddddo",
    "193": "iissddsdddo",
    "194": "iissddsddo",
    "195": "iissddsdo",
    "196": "iissddso",
    "197": "iissddsio",
    "198": "ioiisodo",
    "199": "ioiisoo",
    "200": "iioddoo",
    "201": "iioddoio",
    "202": "iioddoiio",
    "203": "iioddoiiio",
    "204": "iioddoiiso",
    "205": "iioddoiisio",
    "206": "iioddoiisiio",
    "207": "iioddoiiisddo",
    "208": "iioddoiiisdo",
    "209": "iioddoiiiso",
    "210": "iiododo",
    "211": "iiodoo",
    "212": "iiodoio",
    "213": "iiodoiio",
    "214": "iiodoiso",
    "215": "iiodoisio",
    "216": "iiodoisiio",
    "217": "iiodoiisddo",
    "218": "iiodoiisdo",
    "219": "iiodoiiso",
    "220": "iiooddo",
    "221": "iioodo",
    "222": "iiooo",
    "223": "iiooio",
    "224": "iiooso",
    "225": "iissdso",
    "226": "iissdsio",
    "227": "iissdsiio",
    "228": "iiooisdo",
    "229": "iiooiso",
    "230": "iioiodddo",
    "231": "iioioddo",
    "232": "iioiodo",
    "233": "iioioo",
    "234": "iioioio",
    "235": "iioioiio",
    "236": "iioioiiio",
    "237": "iioiosddo",
    "238": "iioiosdo",
    "239": "iioioso",
    "240": "iiosoddddo",
    "241": "iiosodddo",
    "242": "iiosoddo",
    "243": "iiosodo",
    "244": "iiosoo",
    "245": "iiosoio",
    "246": "iiosoiio",
    "247": "iiosoiiio",
    "248": "iiosodsdo",
    "249": "iiosodso",
    "250": "iiosiodddddo",
    "251": "iiosioddddo",
    "252": "iiosiodddo",
    "253": "iiosioddo",
    "254": "iiosiodo",
    "255": "iiosioo"
}

That was generated by this code:

var c = {}, result = 0;
for (var i = 0; i <= 255; ++i) result += (c[i] = q(i)).length;

which prints result = (the result) and c = the thing above.

This gets a remarkably high score despite being pretty simple. It searches for the nearest perfect square, calculates the square root of that perfect square, adds 's', and increments/decrements appropriately.

Old version which didn't use the fact that "10" = "print one, print zero"

m=Math;s=n=>[b=m.sqrt(n)+.5|0,n-b*b];f=(n)=>Array(m.abs(n)+1).join('id'[+(n<0)]);g=(n,t)=>n<4?f(n):g((t=s(n))[0])+'s'+f(t[1]);q=n=>g(n)+'o'


Pyth, 6 bytes

haDQSE

Test suite

Input in the following form on STDIN:

num
array

Explanation:

haDQSE
          Implicit: Q = eval(input()) (num)
     E    Evaluate input (array)
    S     Sort (smaller values to the front)
 aDQ      Sort by absolute difference with Q.
h         Take the first element of the sorted list, the min.
          Print implicitly.


Python 2, 105 bytes

lambda b:sum(b[i+d::d][:(8,7-i%8,i%8)[d%8%5]].find('1')*int(c)>0for i,c in enumerate(b)for d in[1,7,8,9])

Try it online!

Explanation

We take the input as a string of 64 characters '0' or '1'. Using step slices, we cast four "lines of sight" from every queen we encounter. For example, when i = 10 and d = 7, marking the queen as ♥ and the tiles selected by b[i+d::d] as █:

1 0 1 1 1 0 0 0
1 0 ♥ 0 1 0 1 1
1 █ 1 0 1 1 0 1
█ 1 0 1 0 1 0 █
0 1 1 0 0 1 █ 1
1 0 0 0 1 █ 0 0
0 1 0 0 █ 1 1 1
0 1 1 █ 0 1 0 1

Clearly, we don't actually want vision to wrap around the board like this. So we compute how far away the edge of the board is in each direction, and view the tiles at b[i+d::d][:…].

For each tile-direction pair we count:

ray.find('1')*int(c)>0

This will fail whenever

c is not a queen; or
the queen this ray sees is too close (find returns 0); or
this ray sees no queen (find returns −1).

Each pair of queens is only checked once, since rays are always casted forward in reading order, from an "earlier" queen to a "later" one.


C, 5 characters

main;

It's a variable declaration - int type is implied (feature copied from B language) and 0 is default value. When executed this tries to execute a number (numbers aren't executable), and causes SIGSEGV.

Try it online!


Jelly, 6 bytes

JṡFṢị⁸

Try it online!

How it works

JṡFṢị⁸  Main link. Arguments: s (string), n (integer)

J       Get the indices of s.
 ṡ      Split the indices into overlapping chunks of length n.
  F     Flatten the array of chunks.
   Ṣ    Sort the resulting array of indices.
    ị⁸   Get the characters of s at these indices.

Sample run

JṡFṢị⁸  "abalone", 3

J       [1, 2, 3, 4, 5, 6, 7].
 ṡ      [[1, 2, 3], [2, 3, 4], [3, 4, 5], [4, 5, 6], [5, 6, 7]]
  F     [1, 2, 3, 2, 3, 4, 3, 4, 5, 4, 5, 6, 5, 6, 7]
   Ṣ    [1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 7]
    ị⁸  "abbaaalllooonne"


Radiation hardened cyclic quine polyglot

Gol><> and ><>, (117 bytes + 117 bytes)/1 = 234
Gol><>
\\<<'3d*}}}}~}:r0<}!o::! ?>~~a<o>Hr~Kl a}}:?%2l}}}ss2"<<\\
\\<<'3d*}}}}~}:r0<}!o::! ?>~~a<o>Hr~Kl a}}:?%2l}}}ss2"<<\\

Try it online!
><>
\\<<"2ss}}}l2%?:}}a lK~rH>o<a~~>? !::o!}<0r:}~}}}}*d3'<<\\
\\<<"2ss}}}l2%?:}}a lK~rH>o<a~~>? !::o!}<0r:}~}}}}*d3'<<\\

Try it online!
Verification!
These two programs are the same, just reversed. They both follow the same general code structure.
Explanation (Gol><> on top, ><> on the bottom)
\\<<                           <<\\  Transition to the copy of the code that is not radiated
\\<<                           <<\\

                              "    Wrapping string literal over the rest of the code
                              '

                           ss2     Push the string character
                           *3d

                        }}}        Rotate the "<<\" to the correct end of the stack
                        }}}

                 }}:?%2l           Use the extra \ to replace a possible irradiated copy
                    }~}:

       ~     lK                    Duplicate the code
        ~~>? !::o!}<0r             Print a copy of the code in reverse

                a                  Push a newline
       a
    Hr                             Reverse, print the rest of stack and terminate
    >o<                            Print the rest of the stack and terminate


Ruby

def esc chr
  '\\[]'.index(chr) ? "\\#{chr}" : chr
end

def reverse_regex str
  ords = str.chars.to_a.uniq.map(&:ord).sort
  prev = ords.first
  ranges = ords.slice_before{|x|
    prev, prev2 = x, prev
    prev2 + 1 != x
  }.map{|x| x[0]..x[-1]}

  reversed = "[#{ranges.map{|c|esc(c.min.chr) + (c.min == c.max ? '' : (c.min + 1 == c.max ? '' : '-') + esc(c.max.chr))}*''}]{#{str.size}}"
  reversed.size > str.size * 3 ? /#{Regexp.escape str}/ : /#{reversed}/
end

Sample outputs:

reverse_regex 'dogs are delicious'
  => /[ ac-egilorsu]{18}/
reverse_regex 'a'
  => /a/
reverse_regex ''
  => //
reverse_regex 'This is a test: []{}.*potato'
  => /[ *.:T\[\]aehiopst{}]{28}/

Now with ranges!

These regexen match the entire string (if you added ^...$ it would still match, but I'm too lazy to do that and add the required length check). Also, I'm assuming the /s don't count for length. (If they did, it would be impossible for input of empty string.)


GolfScript (30 29 chars)

As xxd output:

0000000: 2207 1113 171d 2f3b 3d61 6d22 7b2e 2831  "...../;=am"{.(1
0000010: 305c 3f2e 402f 2b60 283b 6e7d 25         0\?.@/+`(;n}%

This illustrates the importance of making codegolf problems take input so that the results can't be effectively hard-coded.


Python, 332

def s(m,l,p):
 if not m:return 1
 b=m[0]+'-';z=filter(lambda i:(b[i]=='-')==(i==l),[l,l-1,l+1])
 if not z:return 0
 g=lambda i:s(m[1:],i,0)+[0,1,3,3,5,9]['-PBNRQ'.index(b[i])];i=max(z,key=g)
 if p:print m[0][:i]+'X'+m[0][i+1:];s(m[1:],i,p)
 return g(i)
import sys
t=sys.stdin.read().split('\n')
print t[0]
s(t[1:],t[0].index('L'),1)


Generate a valid equation using user-specified numbers

Python 2.7 (284), Python 3.x (253)

from __future__ import division #(Remove for Python 3.x)
from itertools import *
a=raw_input().split()
for i in permutations(a[:-1],5):
 for j in product('+-*/',repeat=5):
  for k,l in combinations(range(1,12,2),2):
   d=''.join(sum(zip(i,j),()))[:-1];d='('+d[:l]+')'+d[l:]
   if eval(d)==int(a[-1]):print d;b

It gives an error (calling unknown function b) on solution.

Basically, it's a gigantic brute force. It takes in the input, splits it by its spaces (1 2 -> [1,2]), and then permutes through that list. With every permutation, it will iterate through all possible strings of length 5 using the characters +-*/. With each of those iterations, it will generate the combinations of length 2 of the list [1,3,5,7,9,11], interweave the permutation and the string together (12345 *-/+- -> 1*2-3/4+5-), and put in the parentheses. Finally, it will evaluate it, and if the answer and equation are true, then it prints the equation and stops.

This is horribly inefficient, about O(n!/(n-5)!)=O(n^5), but it runs in a reasonable time for the test inputs.


CJam, 25 23 22 bytes

ri1e>2be`z($W%a\+ze~2b

Just a bit of run-length encoding. -1 thanks to @MartinBüttner.

Try it online / Test suite.

Explanation

ri        Read n from input as int
1e>       Take max with 1 (special case for n = 0)
2b        Convert n to binary
e`        Run length encode
z         Zip, giving a pair [<counts> <10101.. array>]
($W%      Drop the counts array and sort decending
a\+z      Add it back to the 10101.. array and re-zip
e~        Run length decode
2b        Convert from binary


HTML/JavaScript, 170 168 167 bytes

setInterval('o.textContent=i.value.replace(/./g,(c,i)=>new Date-d>++i*1e3?c:String.fromCharCode(Math.random()*95+32))',d=50)
<input id=i oninput=d=Date.now()><pre id=o>

Edit: Saved 2 bytes thanks to @ETHproductions. Saved 1 byte thanks to @jrich.


Partitioning Digits into Distinct Integers

Jelly, 14 bytes

ŒṖḌD$ƑƇḌQƑƇLÞṪ

Try it online!

A monadic link taking a list of base-10 digits and returning a list of integers.

Added a byte (and switched to numbers) because of the zero padding issue.

Added 5 bytes to fix a further issue with zeros pointed out by @KevinCruijssen - thanks!

Explanation

ŒṖ             | Partitions of list
  ḌD$ƑƇ        | Keep only those invariant when converted to integers and back to lists of digits
       Ḍ       | Convert from lists of lists of lists of decimal digits to lists of lists of integers
        QƑƇ    | Keep only those invariant when uniquified
           LÞ  | Sort by ascending length
             Ṫ | Tail


Ruby, 316 295 bytes

require 'open-uri'
s,h=*$*
r=[]
s.size.times{|i|r<<(s[i]==' '?'':?|*(h.to_f*Math.log10((URI.parse("http://google.com/search?q=#{URI::encode ?"+s[0..i]+?"}").read[/About [\d,]+ results/]||?0).gsub(/\D/,'').to_i+1)).floor)+s[i]}
puts r.map{|l|l.rjust(r.map(&:size).max).chars}.transpose.map &:join

Unfortunately, the requests just stopped working on the online tester I was using, so I need to golf this down further tonight or tomorrow.

Explanation: I'm taking the input via ARGV. Then I'm just sending a request for each substring that doesn't end in a space, find the results via regex (and default to 0 if the regex doesn't match), and then build the histogram with horizontal bars. At the end, I'm reversing all lines and transposing them to create the vertical histogram.


JavaScript (ES6), 102 82 80 86 80 bytes

Bug fix and 1 byte saved thanks to @edc65

(a,m)=>eval("for(i=0;m;a[j=i-1]>(b=a[i])?a[a[i]=a[j],j]=b:0)1/a[++i]?m--:i=0;a")

Recursion may not be is definitely not is probably the best approach, but I'm sticking with a loop for now.

Try it out:

f=(a,m)=>eval("for(i=0;m;a[j=i-1]>(b=a[i])?a[a[i]=a[j],j]=b:0)1/a[++i]?m--:i=0;a")
Enter your numbers:

<input id=A rows=10 value="5 1 4 2 8">

Enter the number of steps:

<input type="number" min=0 id=B rows=10 value="1">

<button onclick="C.innerHTML=f((A.value.match(/-?\d+/g)||[]).map(Number),B.value)">Run</button>


Deadfish, all 35 characters, 444 bytes
Uses s, d, and c, which are allowed, plus i as an extra.
6 iisiiisiiiiic
7 iisiiisiiiiiic
8 iisiiisiiiiiiic
9 iiisdsdddddddc
0 iisiiisdc
- iisiiisddddc
= iiisdsdddc
y iiisiisc
u iiisiisddddc
i iiisisiiiiic
o iiisisiiiiiiiiiiic
p iiisiisdddddddddc
[ iiissiiiiiiiiiic
] iiisisdddddddc
h iiisisiiiic
j iiisisiiiiiic
k iiisisiiiiiiic
l iiisisiiiiiiiic
; iiisdsdddddc
' iisiisiiic
\ iiisisddddddddc
v iiisiisdddc
b iiisisddc
n iiisisiiiiiiiiiic
m iiisisiiiiiiiiic
^ iiisisddddddc
& iisiisiic
* iisiisiiiiiic
( iisiisiiiic
) iisiisiiiiic
_ iiisisdddddc
+ iisiisiiiiiiic
: iiisdsddddddc
" iisiisddc
| iiisiisiiic

Unless I did my coding wrong, I believe these are necessarily optimal.
Here is the meta-golfer
Explanation
I do a pretty simple BFS by creating a priority queue that orders by length first (so the golfiest solution is always found) and state second (so that it doesn't waste time on ridiculously large numbers caused by repeated application of s). Also, I track a visited set to prevent revisiting values with suboptimal-length code.
Then, each time, I just add the state transitions (L,x,c)->(L+1,x+1,c+"i"), (L,x,c)->(L+1,x-1,c+"d"), and (L,x,c)->(L+1,x*x,c+"s") where L is the code length, x is the current number, and c is the current code.
My meta-golfer code is fully commented if you want a more detailed explanation.


Scala, 406/377 Bytes

I offer two golfed versions of my implementation, one that chooses the value randomly and one that (somehow) abuses the task description and always returns the first legal value. It's up to you, with one to consider (the latter one is shorter, obviously):

trait A[X]{def g=scala.util.Random.shuffle(l).head;def l:Seq[X];def -(d:X)};class M{def a[X](e:Seq[X])=new A[X]{var s=e;def l=s;def -(d:X)=s=s.filter(_!=d)};def r(v:A[Boolean])=v-false;def p[X,Y](a:A[X],b:A[Y])=new A[(X,Y)]{var x=List[Any]();def l=(for(e<-a.l;f<-b.l)yield(e,f)).diff(x);def -(d:(X,Y))=x::=d};def o[X,Y](v:A[X],f:X=>Y)=new A[Y]{def l=v.l.map(f);def -(d:Y)=v.l.filter(f(_)==d).foreach(v.-)}}
trait A[X]{def g=l(0);def l:Seq[X];def -(d:X)};class M{def a[X](e:Seq[X])=new A[X]{var s=e;def l=s;def -(d:X)=s=s.filter(_!=d)};def r(v:A[Boolean])=v-false;def p[X,Y](a:A[X],b:A[Y])=new A[(X,Y)]{var x=List[Any]();def l=(for(e<-a.l;f<-b.l)yield(e,f)).diff(x);def -(d:(X,Y))=x::=d};def o[X,Y](v:A[X],f:X=>Y)=new A[Y]{def l=v.l.map(f);def -(d:Y)=v.l.filter(f(_)==d).foreach(v.-)}}

This versions are more or less just golfed versions of my initial submission (some implementations have changed slightly, but the interfaces were quite stable). Therefore I will not explain it any further but refer to my initial post. Just have in mind that everything that was "for convenience" now disappeared. And a lot of renaming happened. The only difference is that pairs are now a bit like new amb-values: If you define conditions on top of pairs this will never effect the underlying values (nevertheless, manipulating the underlying values will still affect the pairs).

To give you a hint on how to use this versions, here is a short testing code I used while golfing:

  val m = new M
  val a1 = m.a(List(1, 2, 3, 4, 5))
  val a2 = m.a(List(4, 5, 6))
  val a12 = m.p(a1, a2)
  m.r(m.o(a12, (p:(Int, Int)) => p._1 > p._2))
  m.r(m.o(a1, (e: Int) => e%2==1))

  println(a1.l)
  println(a2.l)
  println(a12.l)
  println(a12.g)

As you can see, the offered functions are now instance-methods, hence, you need an instance of M to interact with my library (this saved me one glorious byte).

Note that my ungolfed version (which I will not update any more) now includes natural syntax for the most common Int- and Boolean-operations.

(my initial submission)

Right before posting this answer the Mathematica answer was stated and it looks as if my solution is based on similar assumptions. Nevertheless, I will offer my solution, too, because I didn't copied the former answer as it wasn't there when I started.

I didn't tried to recreate a natural syntax (like: (amb(1, 2, 3) + 3) * 5, etc), but this would be possible if you like to implement the necessary implicit conversions. I chose the functional way as you will see later.

Let's start with the two keywords:

import ambiguous.AmbOps.op

object Amb {
  def amb[A](args: A*): AmbType[A] =
        new BasicAmb[A](args.toList)
  def require(amb: AmbType[Boolean]): Unit =
        amb.del(false)
  def require[A](amb: AmbType[A], predicate: A => Boolean): Unit =
        require(op(amb, predicate))
  def require[A, B](amb: AmbType[(A, B)], predicate: (A, B) => Boolean): Unit =
        require(op(amb, predicate))
}

The amb-method is quite straight forward, you provide some values and get some container, that may return a value back (more on that later).
I offer three require methods but they are all based on the first one, so the others are just for convenience. Let me explain the first one (the others will become clear as you read on): If you have some boolean amb-Container and call require, all false values are eliminated.

But how is an amb-value of arbitrary type converted into a boolean value? By offering a conversion-policy:

object AmbOps {
  def op[A, B](amb: AmbType[A], op: A => B): AmbType[B] =
        new OpAmb[B, A](amb, op)
  def op[A, B, C](amb: AmbType[(A, B)], op: (A, B) => C): AmbType[C] =
        new OpAmb[C, (A, B)](amb, p => op(p._1, p._2))
  def pair[A, B](ambA: AmbType[A], ambB: AmbType[B]): AmbType[(A, B)] =
        new AmbPair[A, B](ambA, ambB)
}

Assume we have some numerical amb-value and want to square each element, then just call op with a corresponding function: op(amb(1, 2, 4), (e: Int) => e * e) // returns a value equivalent to amb(1, 4, 16) Following the same scheme you can convert the elements to boolean values for example with op(amb(1, 2, 4), (e: Int) => e%2 == 0)

If you have several amb-values and you want to define conditions between them, it isn't that easy to do with my approach when only using amb, require and op. Therefore I defined the method pair. With pair you can create tuples/pairs out of two amb-values (or any number if you again pair pairs with other values or pairs). If you then define conditions on top of this tuples, the illegal pairs will be eliminated. But the original values aren't always manipulated. Only if this process leads to the situation that one element from one of the initial amb-values is no longer legal in any tuple, than this value is completely eliminated from the initial amb-value. If now some other amb-value (or pair) is based on this manipulated amb-value, the dependent value will also miss the deleted element.

That means that if you need a pair of values fulfilling a condition, you have to get an element from the pair-value and you cannot always rely on the original values, but I think this is a acceptable limitation.

Just for convenience there is an additional op-method for tuples.

Now we have to dig deeper into the technical details of the amb-containers:

import scala.util.Random

trait AmbType[A] {
  def get: A = {
    if (list.isEmpty)
      throw new IllegalStateException("no value left")
    else list(Random.nextInt(list.length))}
  private[ambiguous] def list: List[A]
  private[ambiguous] def del(a: A): Unit
}

class BasicAmb[A](private var args: List[A]) extends AmbType[A] {
  override private[ambiguous] def list: List[A] = args
  override private[ambiguous] def del(a: A): Unit = { args = args.filterNot(_ == a)}
}

class OpAmb[A, B](amb: AmbType[B], op: B => A) extends AmbType[A] {
  override private[ambiguous] def list: List[A] = amb.list.map(op)
  override private[ambiguous] def del(a: A): Unit = amb.list.filter(op(_) == a).foreach(amb.del)
}

class AmbPair[A, B](ambA: AmbType[A], ambB: AmbType[B]) extends AmbType[(A, B)] {
  private var deleted: List[(A, B)] = List()
  override private[ambiguous] def list: List[(A, B)] =
    ambA.list.flatMap(a => ambB.list.map(b => (a, b))).diff(deleted)
  override private[ambiguous] def del(a: (A, B)): Unit = {
    deleted ::= a
    ambA.list.filter(a => !list.exists(_._1 == a)).foreach(a => {ambA.del(a); deleted = deleted.filterNot(_._1 == a)})
    ambB.list.filter(b => !list.exists(_._2 == b)).foreach(b => {ambB.del(b); deleted = deleted.filterNot(_._2 == b)})
  }
}

I don't want to say too much about the classes but one thing is worth mentioning: If you create pairs of two amb-values and define some conditions on top of them and afterwards define some further conditions on top of one of the original values, the pair-class misses to check if an element of the not-changed original value may be deleted as it doesn't appear as part of one pair any more. So some further observer-pattern would be great.

Now let's take a look on how to use this:

// create amb-values by invoking amb
val a = amb(1, 2, 3, 4)

// do some maths on a value
val b = op(a, (e: Int) => e + 2)

// define some conditions
require(b, (e: Int) => e%3 == 0)
// or first apply the condition to the value and afterwards pass the value to require
val filtered = op(b, (e: Int) => e%3 == 0)
require(filtered)

// pair values
val paired = pair(a, amb("hello", "welcome"))
// note that the amb-value a now only contains the elements 1 and 4 as the former requirement eliminated the other two

// state a condition on pairs
require(paired, (a: Int, b: String) => b.length % a == 0)
// now the amb-value a only contains the element 1 as there was no string with length divisible by 4

// query a value from our pairs (by calling get)
val selected = paired.get
// at this point only two pairs are left, so selected will always be either (1, "hello") or (1, "welcome")
val number = selected._1
val greetings = selected._2


How many squares, cubes, fourth powers, etc. do I need to sum to n?

Mathematica 61 50 bytes
With 11 bytes saved by LegionMammal978.
When restricted to powers of counting numbers, this problem is straightforward (in Mathematica).  When extended to include powers of integers, it's a nightmare.
(k=0;While[PowersRepresentations[#,++k,#2]=={}];k)&

Test Cases
(k = 0; While[PowersRepresentations[#, ++k, #2] == {}]; k) &[7, 2]
(k = 0; While[PowersRepresentations[#, ++k, #2] == {}]; k) &[4, 2]
(k = 0; While[PowersRepresentations[#, ++k, #2] == {}]; k) &[7, 3]
(k = 0; While[PowersRepresentations[#, ++k, #2] == {}]; k) &[23, 3]

4
1
7
9

PowersRepresentationsp[n,k,p] finds all the cases in which n can be expressed as a sum of k positive integers raised to the p-th power.

For example,
PowersRepresentations[1729, 2, 3]

{{1, 12}, {9, 10}}

Checking,
1^3 + 12^3

1729

9^3 + 10^3

1729


Haskell, 258 characters

a§b|a<b='*'|1<3=a
z=[-1..1]
l m=zipWith(§)m$(iterate(b.q)$b(\_ _->'9'))!!(w*h)where
 w=length m`div`h
 h=length$lines m
 q d i=max$minimum[d!!(i+x+w*y)|x<-z,y<-z]
 b f=zipWith(\n->n`divMod`w¶f n)[0..]m
 (j,i)¶g|0<i&&i<w-2&&0<j&&j<h-1=g|1<3=id
main=interact l

Example run:

$> runhaskell 2638-Lakes2D.hs <<TEST
> 8888888888
> 5664303498
> 6485322898
> 5675373666
> 7875555787
> TEST
8888888888
566*****98
6*85***898
5675*7*666
7875555787

Passes all unit tests. No arbitrary limits on size.

Edit (281 → 258): don't test for stability, just iterate to the upper bound; stop passing constant argument m


Perl, 181

/ /;use String::CRC32;use Compress::Zlib;sub k{$_=pop;pack'Na*N',y///c-4,$_,crc32$_}$_="\x89PNG\r\n\cZ\n".k(IHDR.pack NNCV,$',$',8,6).k(IDAT.compress pack('CH*',0,$`x$')x$').k IEND

Size is 180 bytes and option -p is needed (+1). Score is then 181.

The arguments are given via STDIN in a line, separated by a space,
the color as hex value (16 chars) and the number of pixels for width/height, e.g.:

 echo "FFFF00FF 200" | perl -p solidpng.pl >yellow200.png

The file size is 832 bytes. The maximal sized image (n=999) with the same color has 6834 bytes (way below 10 MB).

The solution uses two libraries:

use Digest::CRC crc32; for the CRC32 values at the chunk ends.
use IO::Compress::Deflate deflate; to compress the image data.

Both libraries are not related to images.

Ungolfed:

# Perl option "-p" adds the following around the program:
#     LINE:
#     while (<>) {
#         ... # the program goes here
#     } continue {
#         print or die "-p destination: $!\n";

/ /;    # match the separator of the arguments in the input line
        # first argument, color in hex:  $`
        # second argument, width/height: $'                              #'

# load the libraries for the CRC32 fields and the data compression
use String::CRC32;
use Compress::Zlib;

# function that generates a PNG chunk:
#   N (4 bytes, big-endian: data length
#   N:                      chunk type
#   a* (binary data):       data
#   N:                      CRC32 of chunk type and data
sub k {
    $_ = pop; # chunk data including chunk type and
              # excluding length and CRC32 fields
    pack 'Na*N',
        y///c - 4,   # chunk length                                      #/
                     # netto length without length, type, and CRC32 fields
        $_,          # chunk type and data
        crc32($_)    # checksum field
}

$_ =                      # $_ is printed by option "-p".
    "\x89PNG\r\n\cZ\n"    # PNG header
        # IHDR chunk: image header with
        #   width, height,
        #   bit depth (8), color type (6),
        #   compresson method (0), filter method (0), interlace method (0)
    . k('IHDR' . pack NNCV, $', $', 8, 6)
        # IDAT chunk: image data
    . k('IDAT' .
          compress        # compress/deflate data
          pack('CH*',     # scan line with filter byte
              0,          # filter byte: None
              ($` x $')   # pixel data for one scan line                 #'`
          ) x $'          # n lines                                      #'
      )
        # IHDR chunk: image end
    . k('IEND');

Edits

use IO::Compress::Deflate':all'; is replaced by use Compress::Zlib;. The latter does export the deflate function compress by default. The function
does not need references as arguments and also returns the
result directly. That allows to get rid of variable $o.

Thanks for Michael's answer:

Function k: A call of pack could be removed by using template Na*N for the first pack in the function.
pack template NNCV with four values optimizes NNC3n with six values.

Thanks for VadimR's comment with lots of tips:

use String::CRC32; is shorter than use Digest::CRC crc32;.
y///c-4 is shorter than -4+y///c.
The scan line is now constructed by the template CH* with the repetition in the value.
Removal of $i by using a value reference.
Bare words instead of strings for the chunk types.
Options now read by matching a STDIN input line (option -p) with matching
the space separator / /. Then the first option is in $` and the second argument goes in $'.
Option -p also automatically prints $_.
"\cZ" is shorter than "\x1a".

Better compression

At the cost of code size the image data can be further compressed, if filtering is applied.

Unfiltered file size for FFFF0FF 200: 832 bytes
Filter Sub (horizontal pixel differences): 560 bytes

$i = (                            # scan line:
         "\1"                     # filter "Sub"
         . pack('H*',$c)          # first pixel in scan line
         . ("\0" x (4 * $n - 4))  # fill rest of line with zeros
      ) x $n;                     # $n scan lines

Filter Sub for the first line and Up for the remaining lines: 590 bytes

$i = # first scan line
     "\1"                     # filter "Sub"
     . pack('H*',$c)          # first pixel in scan line
     . ("\0" x (4 * $n - 4))  # fill rest of line with zeros
     # remaining scan lines
     . (
           "\2"               # filter "Up"
           . "\0" x (4 * $n)  # fill rest of line with zeros
       ) x ($n - 1);

First unfiltered line, then filter Up: 586 bytes

$i = # first scan line
     pack('H*', ("00" . ($c x $n)))  # scan line with filter byte: none
     # remaining scan lines
     . (
           "\2"               # filter "Up"
           . "\0" x (4 * $n)  # fill rest of line with zeros
       ) x ($n - 1);

Also Compress::Zlib can be tuned; the highest compression level can be set by additional option for the compression level in function compress at the cost of two bytes:

compress ..., 9;

File size of example yellow200.png without filtering decreases from 832 bytes to 472 bytes.
Applied to the example with Sub filter, the file size shrinks from 560 bytes to 445 bytes (pngcrush -brute can't compress further).


05AB1E, 36 bytes

"34çs«DJā·<£õK.cJ?"34çs«DJā·<£õK.cJ?

Try it online!

If trailing characters are allowed also means at the end of the output, 0"D34çýā·<£.c"D34çýā·<£.c is a layer shorter at 25 bytes.