C + GD library
Instead of just drawing circles any old where, I thought it would be fun to find something red in the picture and draw a circle around that.
Here are some examples of the results obtained with a few photos from Wikimedia Commons:

And here's the code. It's a bit messy, but not too difficult to follow, I hope:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <gd.h>

#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))

/* Used for image segmentation */
int floodfill(int *tmp, int i, int w, int id) {
  int np=1;
  tmp[i]=id;
  if (tmp[i-w-1]<0) np+=floodfill(tmp,i-w-1,w,id);
  if (tmp[i-w]<0) np+=floodfill(tmp,i-w,w,id);
  if (tmp[i-w+1]<0) np+=floodfill(tmp,i-w+1,w,id);
  if (tmp[i-1]<0) np+=floodfill(tmp,i-1,w,id);
  if (tmp[i+1]<0) np+=floodfill(tmp,i+1,w,id);
  if (tmp[i+w-1]<0) np+=floodfill(tmp,i+w-1,w,id);
  if (tmp[i+w]<0) np+=floodfill(tmp,i+w,w,id);
  if (tmp[i+w+1]<0) np+=floodfill(tmp,i+w+1,w,id);
  return np;
}

int main(int argv, char *argc[]) {
  FILE          *infile,*outfile;
  gdImagePtr    img;
  int           *t, *tmp;
  int           w,h,x,y,r,g,b;
  int           c,redness,rgb;
  int           i,np,max,min,thresh;
  int           xt,yt,n;
  int           areaID,size,maxID;
  double        xmin,ymin,xmax,ymax,rad,r0,th;
  gdPoint       v[33];

  /* Check command line and open source JPEG file */
  if (argv!=3) return printf("Usage: %s <in.jpg> <out.jpg>\n",argc[0]);
  if (!(infile=fopen(argc[1],"r"))) return printf("Can't open <%s>\n",argc[1]);
  if (!(img=gdImageCreateFromJpeg(infile))) return printf("Bad JPEG: <%s>\n",argc[1]);
  fclose(infile);

  /* Extract red pixels and auto-threshold */
  w=img->sx;
  h=img->sy;
  np=w*h;
  t=tmp=calloc(np,sizeof(int));
  for (max=0,min=255,y=1;y<h-1;y++) {
    for (x=1;x<w-1;x++) {
      rgb=gdImageGetTrueColorPixel(img,x,y);
      r = (rgb&0xff0000)>>16;
      g = (rgb&0xff00)>>8;
      b = rgb&0xff;
      redness = max(0,r-(max(g,b)+abs(g-b)));
      if (redness>max) max=redness;
      if (redness<min) min=redness;
      *t++ = redness;
    }
    t += 2;
  }
  thresh = (max+min)/2;
  for (t=tmp,i=0;i<np;i++,t++) *t=((*t>thresh)?-1:0);

  /* Label each area detected */
  areaID=1;
  maxID=0;
  max=-1;
  for (t=tmp,i=0;i<np;i++,t++) {
    if (*t<0) {
      size=floodfill(tmp,i,w,areaID);
      if (size>max) {
        max = size;
        maxID = areaID;
      }
      areaID++;
    }
  }

  /* Calculate centre coordinates and area */
  if (max>0) {
    xt=yt=n=xmax=ymax=0;
    xmin=w; ymin=h;
    for (t=tmp,y=0;y<h;y++) {
      for (x=0;x<w;x++) {
        if (*t++==maxID) {
          xt+=x;
          yt+=y;
          n++;
          if (x<xmin) xmin=x;
          if (y<ymin) ymin=y;
          if (x>xmax) xmax=x;
          if (y>ymax) ymax=y;
        }
      }
    }
    x = xt/(2*n) + (xmax+xmin)/4;
    y = yt/(2*n) + (ymax+ymin)/4;

    r0 = max(20,min(min(w,h),max(xmax-xmin,ymax-ymin))/2);
  }
  /* Default circle if nothing found */
  else {
    x=w/2; y=h/2; r0=min(w,h)/3;
  }

  /* Draw a red circle */
  for (th=4.0,i=0;i<33;i++) {
    rad = r0 * (1.2 + (" ,<MYZVSB>@EJIOSWZfgb^bbfgeZTOI@2"[i]-87)/160.0);
    v[i].x = x + rad * sin(th);
    v[i].y = y + rad * cos(th);
    th += 0.22;
  }
  gdImageSetThickness(img,7);
  c = gdImageColorAllocate(img,255,0,0);
  gdImageOpenPolygon(img,v,33,c);

  /* Output results to file */
  printf("Saving...\n");
  if (!(outfile=fopen(argc[2],"w"))) {
    return printf("Can't open <%s> for writing\n",argc[2]);
  }
  gdImageJpeg(img,outfile,85);
  fclose(outfile);
  gdImageDestroy(img);
  printf("Finished\n");
  return 0;
}

Note: Markdown messed up my link in the comments, so I'll just point out that the code uses segmentation to identify all the areas of red in the picture, and then draws a circle around the largest of these. For example, this image:

produces the following output:


MS-SQL, 51 Bytes
Works on SQL 2017 or above:
SELECT TRANSLATE(v,'AEIOUaeiou','EIOUAeioua')FROM t

The new function TRANSLATE performs individual character replacement, so is ideally suited for this challenge.
Input is via a pre-existing table t with varchar column v, per our IO rules.
In this case the table must be created using a case-sensitive collation, either by running on a case-sensitive server, or by using the COLLATE keyword (not counted toward character total):
CREATE TABLE t(v varchar(max) COLLATE Latin1_General_CS_AS)

EDIT: SSMS may cut off the lengthy quote above when returning the result in a "results to text" window, this is a client setting, not a bug in my program.
To fix, go to Tools > Options > Query Results > SQL Server > Results to Text and increase the "Maximum number of characters displayed in each column."


Retina, 39 38 32 30 bytes

M!`AUG|\B\G...
U(AA|AG|GA)\D*

The trailing linefeed is significant.

Output as a linefeed-separated list.

Try it online.

Explanation

M!`AUG|\B\G...

This is match stage which turns the input into a linefeed-separated list of all matches (due to the !). The regex itself matches every codon starting from the first AUG. We achieve this with two separate options. AUG matches unconditionally, so that it can start the list of matches. The second match can be any codon (... matches any three characters), but the \G is a special anchor which ensures that this can only match right after another match. The only problem is that \G also matches at the beginning of the string, which we don't want. Since the input consists only of word characters, we use \B (any position that is not a word boundary) to ensure that this match is not used at the beginning of the input.

U(AA|AG|GA)\D*

This finds the first stop codon, matched as U(AA|AG|GA) as well as everything after it and removes it from the string. Since the first stage split the codons into separate lines, we know that this match is properly aligned with the start codon. We use \D (non-digits) to match any character, since . wouldn't go past the linefeeds, and the input won't contain digits.


Are there any languages especially good at ASCII art?

Well, as a matter of fact, there is! One such language is one I have been working on for a while called V.

Under the hood, V is just vim, but all of the keystrokes are run automatically, and the contents of the vim buffer are printed to STDOUT when the program is over. This just makes running it more convenient.

Some history on the language. When I started using the vim text editor for code-golf, I discovered that it's actually pretty good at it, but has some annoying features that make it more difficult to compete it. For example, you can set up a "while loop" of sorts by doing

qq<foobar>@qq@q

which will repeat <foobar> until an error happens. This has 7 bytes of boilerplate code. In V, this is shortened to ò<foobar>ò.

Some of the things that make V great for ASCII-art:

It is 2d by nature. One feature is that is has a "cursor" position, where most of the commands do something based on where the cursor is in the text. The other commands move the location of the cursor. For example, x deletes a single character, but Wx moves forward a word and then deletes a character. Since most other languages are not intentionally 2 dimensional, this offers a nice edge when the challenge is about positioning text in 2D space
It is entirely string based. You can use some mathy operations, but these are usually the longer way to achieve things.
It uses regex compression to quickly change text.
All of it's internal memory, which is just a 2d array of characters, is implicitly printed when the program ends. Additionally, all inputs is implicitly added into it's internal memory, which is nice when most of the challenge is about changing the input in a certain way.

So I really enjoy using this language, and if you are looking for a specifically ascii-art language, I highly recommend it. However, I would also give a few disclaimers.

It is very confusing to learn. It's also very powerful, but because it's based on a very popular text editor that is 30 years old, there are lot's of obscure features that could very easily confuse new users.
Even though it is better at handling numbers than vim, it's number support is still not great. Personally, I think this makes it more fun to work in (kind of like using retina for tasks regex was never intended for). :D
It is still a WIP. There are some bugs, and some things I haven't gotten around to adding yet.
It doesn't have very many users. (Current number of users: 1).

If you are interested in learning more, here are some good resources:

A chat room where I would be happy to answer any questions you have, and help explain how it works to you.
A tips thread for golfing in vim, but most of the tips carry over.
A meta post describing V in some more detail.


Javascript - move stars towards most isolated point

(with an animation of the process)

The approach is very simple:

choose a large number of random points
find the nearest star to each
choose the point for which the nearest star is most distant
move that star nearer to that point

This process is repeated a large number of times, gradually decreasing the amount by which the stars are moved. This reduces the maximum distance from a point to the nearest star, indirectly reducing the mean distance from a point to the nearest star.

As required by the question, this does not use the built in random function, instead using xorshift.

Much of the code covers set up and animation - the part that applies the algorithm is the function adjustStars.

Code

You can watch the process in progress in the Stack Snippet below.

stars = [];
timeoutId = 0;

resetRandomNumberGenerator();

function resetRandomNumberGenerator() {
  rng_x = 114; // Numbers for the random number generator.
  rng_y = 342;
  rng_z = 982;
  rng_w = 443;
}

$(document).ready(function() {
  c = document.getElementById('canton');
  ctx = c.getContext('2d');
  resizeCanvas();
});

function stop() {
  clearTimeout(timeoutId);
}

function arrange() {
  clearTimeout(timeoutId);
  resetStars();
  resetRandomNumberGenerator();
  maxStepSize = Math.min(cantonWidth, cantonHeight) / 4;
  adjustStars(maxStepSize, 8000, 10000);
}

function resizeCanvas() {
  cantonWidth = parseFloat($('#width').val());
  cantonHeight = parseFloat($('#height').val());
  starRadius = cantonHeight / 20;
  document.getElementById('canton').width = cantonWidth;
  document.getElementById('canton').height = cantonHeight;
  ctx.fillStyle = 'white';
  resetStars();
}

function resetStars() {
  stop();
  stars = [];
  population = parseInt($('#stars').val(), 10);
  shortSide = Math.floor(Math.sqrt(population));
  longSide = Math.ceil(population / shortSide);
  if (cantonWidth < cantonHeight) {
    horizontalStars = shortSide;
    verticalStars = longSide;
  } else {
    horizontalStars = longSide;
    verticalStars = shortSide;
  }
  horizontalSpacing = cantonWidth / horizontalStars;
  verticalSpacing = cantonHeight / verticalStars;
  for (var i = 0; i < population; i++) {
    x = (0.5 + (i % horizontalStars)) * horizontalSpacing;
    y = (0.5 + Math.floor(i / horizontalStars)) * verticalSpacing;
    stars.push([x, y]);
  }
  drawStars();
  updateOutputText();
}

function adjustStars(stepSize, maxSteps, numberOfPoints) {
  $('#stepsRemaining').text(maxSteps + ' steps remaining');
  points = randomPoints(numberOfPoints);
  mostIsolatedPoint = 0;
  distanceToNearestStar = 0;
  for (var i = 0; i < numberOfPoints; i++) {
    point = points[i];
    x = point[0];
    y = point[1];
    star = stars[nearestStar(x, y)];
    d = distance(x, y, star[0], star[1]);
    if (d > distanceToNearestStar) {
      distanceToNearestStar = d;
      mostIsolatedPoint = i;
    }
  }
  point = points[mostIsolatedPoint];
  x = point[0];
  y = point[1];

  starToMove = nearestStar(x, y);

  star = stars[starToMove];
  separationX = x - star[0];
  separationY = y - star[1];
  if (separationX || separationY) {
    hypotenuse = distance(x, y, star[0], star[1]);
    currentStep = Math.min(stepSize, hypotenuse / 2);
    deltaX = currentStep * separationX / hypotenuse;
    deltaY = currentStep * separationY / hypotenuse;
    star[0] += deltaX;
    star[1] += deltaY;
    if (star[0] < 0) star[0] = 0;
    if (star[0] > cantonWidth) star[0] = cantonWidth;
    if (star[1] < 0) star[1] = 0;
    if (star[1] > cantonHeight) star[1] = cantonHeight;

    drawStars();
    updateOutputText();
  }

  if (maxSteps > 0) {
    timeoutId = setTimeout(adjustStars, 10, stepSize * 0.9992, maxSteps - 1, numberOfPoints);
  }
}

function updateOutputText() {
  starText = '';
  for (var i = 0; i < stars.length; i++) {
    starText += stars[i][0] + ', ' + stars[i][1] + '\n';
  }
  $('#coordinateList').text(starText);
}

function randomPoints(n) {
  pointsToReturn = [];
  for (i = 0; i < n; i++) {
    x = xorshift() * cantonWidth;
    y = xorshift() * cantonHeight;
    pointsToReturn.push([x, y]);
  }
  return pointsToReturn;
}

function xorshift() {
  rng_t = rng_x ^ (rng_x << 11);
  rng_x = rng_y;
  rng_y = rng_z;
  rng_z = rng_w;
  rng_w = rng_w ^ (rng_w >> 19) ^ rng_t ^ (rng_t >> 8);
  result = rng_w / 2147483648
  return result
}

function nearestStar(x, y) {
  var distances = [];
  for (var i = 0; i < stars.length; i++) {
    star = stars[i];
    distances.push(distance(x, y, star[0], star[1]));
  }
  minimum = Infinity;
  for (i = 0; i < distances.length; i++) {
    if (distances[i] < minimum) {
      minimum = distances[i];
      nearest = i;
    }
  }
  return nearest;
}

function distance(x1, y1, x2, y2) {
  var x = x2 - x1;
  var y = y2 - y1;
  return Math.sqrt(x * x + y * y);
}

function drawStars() {
  ctx.clearRect(0, 0, cantonWidth, cantonHeight);
  for (i = 0; i < stars.length; i++) {
    star = stars[i];
    x = star[0];
    y = star[1];
    drawStar(x, y);
  }
}

function drawStar(x, y) {
  ctx.beginPath();
  ctx.moveTo(x, y - starRadius);
  ctx.lineTo(x - 0.588 * starRadius, y + 0.809 * starRadius);
  ctx.lineTo(x + 0.951 * starRadius, y - 0.309 * starRadius);
  ctx.lineTo(x - 0.951 * starRadius, y - 0.309 * starRadius);
  ctx.lineTo(x + 0.588 * starRadius, y + 0.809 * starRadius);
  ctx.fill();
}
canvas {
  margin: 0;
  border: medium solid gray;
  background-color: blue;
}

<input id='stars' onchange='resetStars()' type='number' value='13' min='13' max='50' maxlength='2' step='1'>stars

<input id='width' onchange='resizeCanvas()' type='number' value='494' min='1' max='500' maxlength='3' step='any'>width

<input id='height' onchange='resizeCanvas()' type='number' value='350' min='1' max='500' maxlength='3' step='any'>height

<button type='button' onclick='resetStars()'>Reset Stars</button>
<button type='button' onclick='arrange()'>Arrange Stars</button>
<button type='button' onclick='stop()'>Stop</button>
<textarea id='stepsRemaining' rows='1' readonly></textarea>

<canvas id='canton' width='494' height='350'></canvas>

<textarea id='coordinateList' rows='50' cols='40' readonly></textarea>

Output for 50 stars

(width = 1.4, height = 1.0)

Mean distance estimated at 0.0655106697162357.

Coordinates:

0.028377044205135808, 0.2128159150679491
0.10116766857540277, 0.05156676609341312
0.2903566419069437, 0.07216263690037035
0.49154061258041604, 0.004436102736309105
0.6930026352073071, 0.07060477929576484
1.0988644764108417, 0.022979778480838074
1.1735677936511582, 0.18600858289592742
1.3056806950504931, 0.062239869036660435
0.3967626880807638, 0.24483447327177033
0.27004118129346155, 0.40467589936498805
0.4996665039421278, 0.13023282430440133
0.5148978532656602, 0.6161298793146592
0.5907056537744844, 0.2614323599301046
0.8853042432872087, 0.048123917861564044
0.7753680330575412, 0.22938793622044834
1.365432954694329, 0.2355377720528128
0.1985172068244217, 0.23551298706793927
0.4477558465270544, 0.4170264112485973
0.6084424566752479, 0.7764909501169484
0.6099528761580699, 0.4395002434593519
0.9506038166406011, 0.34903243854585914
1.1898331497634231, 0.5756784243472182
1.0933574395540542, 0.46422120794648786
1.1516574254138159, 0.2930213338333888
0.07646053006349718, 0.40665000611360175
0.0634456093015551, 0.5853189455014883
0.3470036636019768, 0.5938838331082922
0.7591083341283029, 0.4005456925638841
0.9745306853981277, 0.184624209972443
1.3552011948311598, 0.549607060691302
1.3334000268566828, 0.7410204535471169
1.2990417572304487, 0.39571229988825735
0.05853941030364222, 0.7734808757471414
0.19396697551982484, 0.5678753467094985
0.7103231124251072, 0.5955041661956884
0.6168410756137566, 0.948561537739087
0.8967624790188228, 0.5368666961690878
0.9751229155529001, 0.8323724819557795
0.9987127931392165, 0.652902038374714
1.3231032600971289, 0.9164326184290812
0.20785221980162555, 0.7566700629874374
0.3987967842137651, 0.7678025218448816
0.44395949605458546, 0.9137553802571048
0.775611700149756, 0.9029717946067138
0.806442448003616, 0.7328147396477286
0.9481952441521928, 0.9872963855418118
1.1528689317425114, 0.9346775634274639
1.1651295140721658, 0.7591158327925681
0.09316709042512515, 0.934205211493484
0.2769325337580081, 0.9341145493466471


Haskell, 12 bytes

f?g=(.f).g.f

Try it online!
Haskell was made for this.
Let's unpack it:
(f?g) x y =
(((.f).g.f) x) y =
(.f)(g (f x)) y =
((g (f x)).f) y =
g (f x) (f y)

If you're wondering what happens if we make this further pointfree in f and g, we can express (?) as:
\f->((.f).).(.f)
(.).(.).flip(.)<*>flip(.)

The flipped version of ? that's invoked as g?f is a little nicer:
((.).flip(.)<*>).(.)

(I used pointfree.io for these.)
Test cases copied from Unrelated String.

Haskell, 10 bytes

(.map).(.)

Try it online!
If the input [x,y] is a two-element list, and the binary function g accepts its two arguments as such a list. The main function takes is arguments as g then `f.


Japt, 13 12 bytes
Oh my gosh I was beating both Jelly and Pyth for a time :D
¢a1 ªJ +1+¢l

Test it online!
Here's the strategy I use: let x be the input integer, and let b be x's binary representation. The correct output is 1 + the length of b + the last index of a 1 in b, minus 1 if this index is 0.


vim 56 54 keystrokes
iclass Tuple1 {public Object _0;}<esc>qyYp<C-a>$y2bPr,<C-a>q98@y

Since V is backwards compatible, you can Try it online!
This is the perfect task for vim! I might golf it a little bit more later. Also note that <c-a> means Control-A, and it counts as one keystroke.
Explanation:
iclass Tuple1 {public Object _0;}<esc>         'Enter the starting text

qy                          'Start recording in register y
  Yp                        'Yank the current line, the print on the line below
     <C-a>                  'Increment the next digit to occur by one
          $                 'Move to the end of this line
           y2b              '(yank) 2 words (b)ack. This will grab '_0;'
              P             'Print the previously yanked word before the cursor.
               r,           '(r)eplace the char under the cursor with a comma.
                 <c-a>q     'Increment the current digit, then stop recording
                       99@y 'Playback macro 'y' 99 times.


Fastest alphabetical list sort given the following limitations:

C - B-tree sort
This sorts randomNames.csv in about 5.8ms on my Core 2 T5500 @ 1.66GHz.  My testing utility is here.
It isn't the fastest algorithm for sorting this quantity of data, but I didn't feel like trieing.
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Btree Btree;

static void btree_insert(Btree **btree, const char *key);
static void btree_emit_and_free(Btree *btree, const char ***out);

void sort(const char **strings, size_t count, const char **out)
{
    size_t i;
    Btree *tree = NULL;
    const char **out_start = out;

    for (i = 0; i < count; i++)
        btree_insert(&tree, strings[i]);

    btree_emit_and_free(tree, &out);

    assert(out - out_start == (ssize_t) count);
}

/*
 * Maximum (U) and minimum (L) number of *keys* per B-tree node.
 *
 * The maximum number of *branches* a B-tree may have is U+1 :
 *
 *       KEY   KEY
 *     /     |     \
 * branch  branch  branch
 */
#define U 20
#define L (U / 2)

struct Btree {
    /* Number of keys (rather than branches). */
    unsigned char count;

    /* 0 if node is a leaf, 1 if it has leaf children, etc. */
    unsigned char depth;

    const char *keys[U];

    /* Allocated to U+1 items if this is an internal node. */
    Btree *branches[];
};

static Btree *allocLeaf(void)
{
    return malloc(sizeof(Btree));
}

static Btree *allocInternal(void)
{
    return malloc(sizeof(Btree) + (U+1) * sizeof(Btree *));
}

static bool insert(Btree *node, const char *x,
                   const char **new_x, Btree **new_xr);
static bool insert_item(Btree *node, unsigned int k,
                        const char  *x,     Btree  *xr,
                        const char **new_x, Btree **new_xr);
static unsigned int
find_insertion_point(const char *keys[], unsigned int count, const char *x);

static void btree_insert(Btree **btree, const char *key)
{
    if (*btree == NULL) {
        Btree *root = allocLeaf();
        root->count = 1;
        root->depth = 0;
        root->keys[0] = key;
        *btree = root;
    } else {
        const char *new_x;
        Btree *new_xr;

        if (insert(*btree, key, &new_x, &new_xr)) {
            Btree *root = allocInternal();
            root->count = 1;
            root->depth = (*btree)->depth + 1;
            root->keys[0] = new_x;
            root->branches[0] = *btree;
            root->branches[1] = new_xr;
            *btree = root;
        }
    }
}

static bool insert(Btree *node, const char *x,
                   const char **new_x, Btree **new_xr)
{
    unsigned int k = find_insertion_point(node->keys, node->count, x);
    Btree *xr;

    if (node->depth == 0)
        xr = NULL;
    else if (insert(node->branches[k], x, new_x, new_xr))
        x = *new_x, xr = *new_xr;
    else
        return false;

    return insert_item(node, k, x, xr, new_x, new_xr);
}

static bool insert_item(Btree *node, unsigned int k,
                        const char  *x,     Btree  *xr,
                        const char **new_x, Btree **new_xr)
{
    unsigned int i;
    bool internal = xr != NULL;

    if (node->count < U) {
        /* Enough case */
        for (i = node->count; i-- > k;)
            node->keys[i + 1] = node->keys[i];
        node->keys[k] = x;
        if (internal) {
            for (i = node->count + 1; i-- > k + 1;)
                node->branches[i + 1] = node->branches[i];
            node->branches[k + 1] = xr;
        }
        node->count++;
        return false;
    } else {
        Btree *r = internal ? allocInternal() : allocLeaf();

        node->count = L;
        r->count = L;
        r->depth = node->depth;

        if (k < L) {
            /* Left case */
            *new_x = node->keys[L - 1];
            for (i = 0; i < L; i++)
                r->keys[i] = node->keys[i + L];
            for (i = L - 1; i-- > k;)
                node->keys[i + 1] = node->keys[i];
            node->keys[k] = x;
            if (internal) {
                for (i = 0; i <= L; i++)
                    r->branches[i] = node->branches[i + L];
                for (i = L; i-- > k + 1;)
                    node->branches[i + 1] = node->branches[i];
                node->branches[k + 1] = xr;
            }
        } else if (k == L) {
            /* Central case */
            *new_x = x;
            for (i = 0; i < L; i++)
                r->keys[i] = node->keys[i + L];
            if (internal) {
                r->branches[0] = xr;
                for (i = 1; i <= L; i++)
                    r->branches[i] = node->branches[i + L];
            }
        } else {
            /* Right case */
            *new_x = node->keys[L];
            for (i = 0; i < k - L - 1; i++)
                r->keys[i] = node->keys[i + L + 1];
            r->keys[k - L - 1] = x;
            for (i = k - L; i < L; i++)
                r->keys[i] = node->keys[i + L];
            if (internal) {
                for (i = 0; i < k - L; i++)
                    r->branches[i] = node->branches[i + L + 1];
                r->branches[k - L] = xr;
                for (i = k - L + 1; i <= L; i++)
                    r->branches[i] = node->branches[i + L];
            }
        }

        *new_xr = r;
        return true;
    }
}

static unsigned int
find_insertion_point(const char *keys[], unsigned int count, const char *x)
{
    unsigned int start = 0;
    unsigned int middle;

    while (count) {
        middle = count >> 1;
        if (strcmp(x, keys[start + middle]) < 0) {
            count = middle;
        } else {
            start += middle + 1;
            count -= middle + 1;
        }
    }

    return start;
}

static void btree_emit_and_free(Btree *btree, const char ***out)
{
    unsigned int i;

    if (btree->depth == 0) {
        for (i = 0; i < btree->count; i++)
            *(*out)++ = btree->keys[i];
    } else {
        for (i = 0; i < btree->count; i++) {
            btree_emit_and_free(btree->branches[i], out);
            *(*out)++ = btree->keys[i];
        }
        btree_emit_and_free(btree->branches[btree->count], out);
    }

    free(btree);
}


Print the previous answer in reverse - with a catch (pt. 2)

1 - 05AB1E

"Hello, World!"

SCORE: \$\frac{15}{1} - 0 = 15\$

Try it online!


MATL, 19 18 17 bytes
lyf!Gn:-H_^Xs&X<(

Try it online! Or verify all test cases (slightly modified code).
Explanation
It suffices to compute the distance from each potential new position to the already occupied ones. The remaining distances are do not depend on the potential new position, and so constitute a constant term, which can be ignored.
Let's take input [1 0 0 0 0 0 1] as an example.
l      % Push 1
       % STACK: 1
y      % Take input implicitly. Duplicate from below
       % STACK: [1 0 0 0 0 0 1], 1, [1 0 0 0 0 0 1]
f!     % Indices of nonzero elements, as a column array
       % STACK: [1 0 0 0 0 0 1], 1, [1 7]
Gn:    % Push [1 2 ... n], where n is input size (array of possible positions)
       % STACK: [1 0 0 0 0 0 1], 1, [1; 7], [1 2 3 4 5 6 7]
-      % Matrix with all pairs of differences
       % STACK: [1 0 0 0 0 0 1], 1, [1; 7], [0 -1 -2 -3 -4 -5 -6;
                                             6  5  4  3  2  1  0]
H_^    % Raise each entry to -2
       % STACK: [1 0 0 0 0 0 1], 1, [   Inf 1.0000 0.2500 0.1111 0.0625 0.0400 0.0278;
                                     0.0278 0.0400 0.0625 0.1111 0.2500 1.0000    Inf]
Xs     % Sum of each column
       % STACK: [1 0 0 0 0 0 1], 1, [Inf 1.04 0.3125 0.2222 0.3125 1.04 Inf]
&X<    % Index of minimum. Takes the first if there is a tie
       % STACK: [1 0 0 0 0 0 1], 1, 4
(      % Assign: write 1 at the position of the minimizer
       % STACK: [1 0 0 1 0 0 1]
       % Implicitly display


Abuse mixed.

Pike is unfortunately not exactly identical to C; for instance the type of a list of strings is array(string), not char[][] or even string[].

Any time you need a type declarator and it's not int, mixed (the "any" type, which gets promoted to the actual type of the RHS at runtime) is liable to be shorter.

A function that takes a list of ints and sorts it, then returns it, for a whopping 41 bytes:

array(int)s(array(int)l){return sort(l);}

Or, the type-inferencing version, which is 31 bytes:

mixed s(mixed l){return sort(l);}

My answer to Manage Trash So uses a lot of mixed.


My first try at a fatest-code question. Problem is, I didn't try any optimization…

If the rotation part isn't correct, please tell me.

Also, I don't know how to time test the code, so I tried to use timeit module to run 1000 times in order to have a correct timing. I am not sure if I have to do that, or if it is your part :þ

Anyway, here is my code:

import random
circumference = 1024
numberpoints = circumference/64
circleA = sorted(random.sample(range(circumference),numberpoints))
circleB = sorted(random.sample(range(circumference),numberpoints))

####
from  bisect import bisect_left

def find_next(a, x):
    i = bisect_left(a, x)
    if i != len(a):
        return i, a[i]
    raise ValueError

def dist1(cA, cB):
    l = []
    p = cA[0]
    cA = cA[1:]
    while True:
        try:
            (i, n) = find_next(cB, p)
            l.append(n-p)
            cB = cB[(i+1):]
            (i, p) = find_next(cA, n)
            cA = cA[(i+1):]
        except:
            break
    return (sum(l)/len(l))

def rotate(circleB,i):
    return sorted([(c+i)%circumference for c in circleB])

def distAll(circleA, circleB):
    l = [dist1(circleA, rotate(circleB,i)) for i in xrange(circumference)]
    return sum(l)/circumference

if __name__ == '__main__':
    import timeit
    print(timeit.timeit("distAll(circleA,circleB)", setup="from __main__ import *", number=1000))


i386 (16-bit mode) Bootsector, 512 bytes
All i386 bootsectors have to be 512 bytes, so... Without the padding required by i386, it is 137 bytes. Since I can't easily post a TIO link, here's a screenshot of it running:

This code registers the BIOS interrupt int 0x69 to take the number in the bx register and use it as input. Thus, doing
mov bx, 3
int 0x69

is equivalent to the last test case. The disassembled, Intel-syntax source is:
[org 0x7c00]

xor ax, ax
mov es, ax
cli
mov dx, interrupt
mov [es:0x69*4], dx
mov ax, cs
mov [es:0x69*4+2], ax
sti

xor bx, bx
int 0x69
call newline
mov bx, 1
int 0x69
call newline
mov bx, 2
int 0x69
call newline
mov bx, 3
int 0x69
cli
hlt

interrupt:
or bx, bx
jz special
push bx
mov ax, 0x0e20
int 0x10
mov al, '_'
.loop1:
int 0x10
dec bx
jnz .loop1
call newline
mov al, '/'
int 0x10
mov al, ' '
pop bx
push bx
.loop2:
int 0x10
dec bx
jnz .loop2
mov al, '\'
int 0x10
call newline
mov al, '|'
int 0x10
pop bx
mov al, ' '
.loop3:
int 0x10
dec bx
jnz .loop3
mov al, '|'
int 0x10
iret

newline:
mov ax, 0x0e0d
int 0x10
mov al, 0x0a
int 0x10
ret

special:
mov si, s
mov ah, 0x0e
.sloop:
lodsb
int 0x10
or al, al
jnz .sloop
iret

s: db '/', '\', 10, 13, '|', '|'

times 510-($-$$) db 0
dw 0xaa55

(Bit verbose, I know, but hey, it's assembly.)


I'm being pathetically lazy (pun intended), but why not... seems to fulfill the rules.

Haskell, 204

import Control.Monad
import Control.Monad.Omega
main=print.filter(\[(a,x),(b,y),(c,z)]
 ->and$(a^x+b^y==c^z):zipWith(((>1).).gcd)[a,b,c][b,c,a])
 .runOmega$mapM(\_->liftM2(,)(each[1..])$each[3..])"123"

This prints1 all combinations which fulfill the counterexample property. I used the control-monad-omega package for diagonalising ℕ6... might be considered library-cheating. But seeing as someone will later post an APL answer where all this stuff is built into the language (or isn't it?), I don't give too much about it...

Of course, the program is way too slow (naïve exhaustion, and linked-lists as data structure) to be expectable of actually yielding a counterexample, but Haskell itself can actually achieve decent performance.

1Since it prints the tuples in list format, i.e. in one line, you need to switch your terminal's buffering off or you won't see when a result comes in. Alternatively, you can replace print with mapM_ print so you get a newline after each result, flushing a line-buffered terminal.

To test the program, change each[3..] to each[2..], then you'll simply get all non-coprime pythagorean tuples as result.


Python, score = 138 1/6 = (79+108*2+178*3)/6

DFA

S,D,F=input()
s=1
for c in S:s=D[s,c]
print["Not a chance!","Accepted!"][F&s>0]

Input is a triple of string S, a delta function D, and final state mask F.  I number each state with a power of 2, so F is just the OR of each accepting state.  D is a map from (state,input char)->state.

example input (accepts all strings ending in b):

'abab',{(1,'a'):1,(1,'b'):2,(2,'a'):1,(2,'b'):2},2

NFA

S,D,F=input()
s=1
for c in S:
 t,s=s,0
 for a,b in D[c]:s|=t/a%2*b
print["Not a chance!","Accepted!"][F&s>0]

We number states as powers of 2 as before.  D is a map from input character to a list of transitions labeled by that character.

example input (accepts all strings ending in b):

'abab',{'a':[(1,1)],'b':[(1,1),(1,2)]},2

epsilon-NFA

S,D,F=input()
E={1:1}
for i in D[0]:
 for a,b in D[0]:E[a]=a|E.get(b,b)
s=E[1]
for c in S:
 t,s=s,0
 for a,b in D[c]:s|=t/a%2*E.get(b,b)
print["Not a chance!","Accepted!"][F&s>0]

Same as NFA, but with the additional 0 character listing the epsilon transitions.

example input (accepts all strings ending in b):

'abab',{'a':[(1,1)],'b':[(1,1),(1,2)],0:[(2,4)]},2


What is the fastest safe way down a mountain?

JavaScript (ES6),  223 ... 205  199 bytes

f=(m,x=o=0,y=0,n=2,V,s,p='',r=m[y]||0,v=r[x],h=V%32-v%32|0)=>63>>h+1&v<64&!p[o.length-1]?h<3||s*n--?1+r[x+!m[y+1]]?[...'LURD'].map((c,d)=>r[f(m,x+--d%2,y+~-d%2,n,r[x]+=32,6>>h&1,p+c),x]=v)&&o:o=p:0:0

Try it online!
Commented
The 5 least significant bits of the cells are left unchanged. The upper bits are used to count the number of times a cell has been visited in a given path.
We need quite a lot of variables to fully describe the skier status at any given time, notably the possibility to do a big steep slope.
Header
f = (                      // a recursive function taking:
  m,                       //   m[] = input matrix
  x =                      //   (x, y) = current position, starting at (0, 0)
  o = 0,                   //   o = output string, initialized to a numerical value
  y = 0,                   //
  n = 2,                   //   n = remaining number of big steep slopes
  V,                       //   V = value of the previous cell
  s,                       //   s = a flag that is set if a big steep slope is allowed
                           //       for this turn
  p = '',                  //   p = current path string
  r = m[y] || 0,           //   r[] = current row (using 0 as a fallback)
  v = r[x],                //   v = value of the current cell (or undefined)
  h = V % 32 - v % 32 | 0  //   h = height between the previous and the current cell
) =>                       //       (0 if V is undefined)
  (...)                    //

Tests
63 >> h + 1 &              // if the height is greater than or equal to -1 and less
                           // than or equal to 4 and
v < 64 &                   // v is defined and less than 64 and
!p[o.length - 1] ?         // the current path is shorter than the best solution or
                           // we don't have a solution yet (in which case o.length - 1
                           // is NaN):
  h < 3 ||                 //   if the height is less than 3 or
  s * n-- ?                //   a big steep slope is allowed and we can still do one:
    1 + r[x + !m[y + 1]] ? //     if we haven't reached the bottom-right cell,
                           //     i.e. m[y + 1] is defined or 1 + r[x + 1] is not NaN:
      (...)                //       process the recursive calls
    :                      //     else:
      o = p                //       update the solution to this path
  :                        //   else:
    0                      //     do nothing
:                          // else:
  0                        //   do nothing

Recursive calls
[...'LURD'].map((c, d) =>  // for each direction character c at index d:
  r[                       //   we will eventually restore r[x]
    f(                     //     recursive call:
      m,                   //       m[] is unchanged
      x + --d % 2,         //       add dx to x
      y + ~-d % 2,         //       add dy to y
      n,                   //       n is unchanged
      r[x] += 32,          //       add 32 to the current cell
      6 >> h & 1,          //       set s if h is either 1 or 2
      p + c                //       append c to the path
    ),                     //     end of recursive call
    x                      //     restore r[x] to ...
  ] = v                    //   ... v
) && o                     // end of map(); yield o


Perl 5, -ap 121 bytes / 56 bytes

This 121 byte solution has a uniform distribution over all valid arrangements of boxes. It tries to be somewhat efficient but still times out on TIO for size 4 or more

#!/usr/bin/perl -ap
@a=((0 x$_.$")x$_.$/)x$_."";s%0%/0(|.{@F}|(\X{@F}\X){@F})\G/+${$z="$`1$'"}++||push@a,$z;0%eg for@a;$_=$a[rand@a];$\=y/1//

Try it online!

If you don't care about uniformity it's of course easy to go shorter, e.g. this 56 bytes solution is very biased towards the origin (it probably gives more nice pictures for the motivating example though)

#!/usr/bin/perl -a
say map{\@$_[rand@;+1,$#{$_-1}];@;-$#$_.$"}@;for@;=1..$_

Try it online!

(checked for size 2 and 3 that it indeed generates all possible outputs)


Retina, 1 byte

x

Try it online!

Prints a positive integer when the input contains at least one "reversed" copy of the source and 0 otherwise.

Any character that isn't a backtick or a regex metacharacter ([()?*+\\^$.) would work.


05AB1E, 10 8 bytes

Saved 2 bytes thanks to Leo

ʒæså}éR`

Try it online!

Explanation

ʒ         # filter list, keep only members for which the following is true
  så      # input is in the
 æ        # powerset of the current word
    }     # end filter
     é    # sort by length
      R   # reverse
       `  # push separately (shortest on top)

I would have used head at the end saving a byte but that would output an empty list if there isn't a match.


Operator precedence: How wrong can I be?

Python 2, 171 156 bytes

lambda a:max(e(a))-min(e(a))
u=')%s('
def e(a,t=u):
 try:b=[eval(a)]
 except:b=[]
 return sum([e('(%s)'%a.replace(o,t%o),u%t)for o in"+-*/%"if' '+o in a],b)

Try it online!

How it works

We surround each operator with a different number of outward-facing pairs of parentheses to simulate different precedences (in all possible ways), and wrap enough inward-facing pairs of parentheses around the entire string, to get an expression we can eval.  For example, with

+ ↦ )+(
* ↦ ))*((
- ↦ )))-(((

we get

9 * 8 + 1 - 4 ↦ (((9 ))*(( 8 )+( 1 )))-((( 4))) = 77.


Avoid "normal" letters
Identifiers are normalized by the Python 3 parser. This implies that cursive (Unicode) letters such as  are interpreted as their ASCII-compliant equivalents abcDEF. So the following code works (as was exploited here):
=123
()

Python versions in which this behaviour is confirmed:

Works: 3.4, 3.5, 3.6, 3.7, 3.8
Doesn't work: 2.7

Example source restriction:

Use no characters abc···xyz, ABC···XYZ.


Python, 64 chars

This one is recursive, so will overflow the stack for really large input
01234567890123456789012345678901234567890123456789012345678901234567890
|         |         |         |         |         |         |         |
 B=lambda L,H:H>L+1 and B(*[L,L/2+H/2,H][test(L/2+H/2):][:2])or H

test run
def test(n):
    print "testing ", n
    return n<66

L,H=10,1000

B=lambda L,H:H>L+1 and B(*[L,L/2+H/2,H][test(L/2+H/2):][:2])or H

print B(L,H)

outputs
testing  505
testing  257
testing  133
testing  71
testing  40
testing  55
testing  62
testing  66
testing  64
testing  65
66


Python, 650 612 594 574 characters

n='\n'
S='_a/G\F I\n'
A=dict(zip(S,('III','   ','__/','  G','\  ','F__','   ','III','')))
B=dict(zip(S,('III','   ','\  ',' aF','/a ','  G','   ','III','')))
C=dict(zip(S,('___','aaa','/  ','GII','II\\','  F','   ','III','')))
def T(s):
 a=b=c=d=r=u''
 for k in s:
    a+=A[k];b+=B[k];c+=C[k]
    if k=='I':a=a[:-3]+('II\\'if'a '==d[1:3]else'GII'if' a'==d[:2]else 3*k)
    d=d[3:]
    if k==n:d=c.replace('____','__/F').replace('aaaa','aa  ').replace('/  a','/a  ').replace('a  F','  aF');r+=a+n+b+n+d+n;a=b=c=''
 return r
print T(T(T('__\n\G\n'))).translate({97:95,71:47,73:32,70:92})

This works by expanding the triangle by a factor of 3 each time.  To do that, we need to keep track of whether each symbol is a left or right boundary (e.g. how / is expanded depends on which side of the / is the inside).  We use different symbols for the two possible cases, as follows:

_: _, outside on the top
a: _, outside on the bottom
/: /, outside on the left
G: /, outside on the right
\: \, outside on the left
F: \, outside on the right
<space>: inside
I: outside

The d variable handles the special case where the expansion of an a needs to extend into the 3x3 in the next row.


Output integer given a digital clock style input

JavaScript (ES6),  105  104 bytes

Takes input as an array of 3 strings. Returns an array of digit characters.

a=>a.map(s=>s.match(/.../g).map(([a,b,c],n)=>'3789465021'[(o[n]=~~o[n]+[++a|7*++b^44*++c])%13]),o=[])[2]

Try it online!

How?

Finding a concise way to process the input

A common trick to turn an input string into an identifier is to use parseInt(). But it only works with alphanumeric strings and is therefore pointless here. Other than that, JS is not very good at processing ASCII codes in few bytes, so we'd better find another trick.

We can notice that each digit in this font can still be uniquely identified if we replace each character with a binary value: \$1\$ for space, \$0\$ for not space:

  0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9
-----+-----+-----+-----+-----+-----+-----+-----+-----+-----
  _  |     |  _  |  _  |     |  _  |  _  |  _  |  _  |  _
 | | |   | |  _| |  _| | |_| | |_  | |_  |   | | |_| | |_|
 |_| |   | | |_  |  _| |   | |  _| | |_| |   | | |_| |  _|
-----+-----+-----+-----+-----+-----+-----+-----+-----+-----
 101 | 111 | 101 | 101 | 111 | 101 | 101 | 101 | 101 | 101
 010 | 110 | 100 | 100 | 000 | 001 | 001 | 110 | 000 | 000
 000 | 110 | 001 | 100 | 110 | 100 | 000 | 110 | 000 | 100

That looks like a good golfing start: it means that we can abuse the fact that a space is coerced to \$0\$ and can be turned into a \$1\$ by applying the pre-increment operator to it, while it will result in NaN for the other characters.

Hence the idea to implement something along these lines:

s.match(/.../g)        // split each line into groups of 3 characters
.map(([a, b, c], n) => // for each group (a, b, c) of characters at position n:
  ???                  //   do some bitwise magic with ++a, ++b and ++c
                       //   and use it to update an identifier for the n-th digit
)                      // end of map()

Bitwise magic

After some experiments and brute-forcing, it turned out that a pretty short and efficient formula is:

o[n] = ~~o[n] + [++a | 7 * ++b ^ 44 * ++c]

Step-by-step example:

The 1st line of a "0" is " _ ". Therefore, we have ++a -> 1, ++b -> NaN and ++c -> 1.

So, ++a | 7 * ++b ^ 44 * ++c evaluates to 1 | 7 * NaN ^ 44 * 1, which is \$45\$.

Because o[n] is initially undefined, ~~o[n] evaluates to \$0\$. And because \$45\$ is coerced to a string, o[n] is updated to "045".
The 2nd line of a "0" is "| |". This time, we have ++a -> NaN, ++b -> 1 and ++c -> NaN. The bitwise expression evaluates to \$7\$ and o[n] is updated to "457". (Note that the leading 0 is thrown away by ~~o[n].)
The 3rd line of a "0" is "|_|", leading to ++a -> NaN, ++b -> NaN and ++c -> NaN. The bitwise expression evaluates to \$0\$ and the final value of o[n] is "4570".

Minimal perfect hash function

Of course, the parameters of the bitwise formula were not chosen at random (well ... at least no completely): by coercing the final identifier of a digit back to an integer and applying a modulo \$13\$, we get a unique value in \$[0..9]\$.

The following table summarizes the results for all digits:

  digit |   0   |   1   |   2   |   3   |   4   |   5   |   6   |   7   |   8   |   9
--------+-------+-------+-------+-------+-------+-------+-------+-------+-------+-------
     ID |  4570 |  4377 | 45144 |  4511 |  4307 | 45441 | 45440 |  4577 |  4500 |  4501
--------+-------+-------+-------+-------+-------+-------+-------+-------+-------+-------
 mod 13 |   7   |   9   |   8   |   0   |   4   |   6   |   5   |   1   |   2   |   3

Hence the 10-byte lookup table: '3789465021'.


APL (Dyalog Extended), 45 bytes (SBCS)

Full program. Prints all meeker numbers. Requires 0-based indexing (⎕IO←0).
1e6+⍸{(×⌿i⊇⍵)≡10⊥⍵[2+i←0 1,⍪3 4]}¨10⊤¨1e6…1e7

Try it online! (limited to upper bound of 2 000 000 ― above code works offline)
1e6…1e7 numbers 1 000 000 through 10 000 000
10⊤¨ base-10 representation of each (splits digits of numbers into lists of digits)
{…}¨ apply the following lambda to each:
 ⍵[…] index the digits of the current number using the following:
  ⍪3 4 the column-vector [[3],[4]]
  0 1, prepend a column consisting of [0,1] yielding [[0,3],[1,4]]
  i← assign to i (for indices)
  2+ increase by two; [[2,5],[3,6]]
 10⊥ evaluate as base-10, using the top row as tens place and bottom row as ones place
 (…)≡ check if it matches the following:
 i⊇⍵ select the elements from the digits at indices i
 ×⌿ multiply the elements of the top row with the elements of the bottom row
⍸ ɩndices where true
1e6+ offset to the first candidate


Java, 449 426 bytes

import java.util.*;interface P{static Set s=new HashSet();static void main(String[]a){o(Arrays.toString(a));while(s.size()<n(a.length)){p(a);o(Arrays.toString(a));}}static<T>void o(T z){System.out.println(z);s.add(z);}static int n(int x){return x==1?1:x*n(x-1);}static void p(String[]a){Random r=new Random();int l=a.length,j=r.nextInt(l),i=r.nextInt(l);String t=a[j];a[j]=a[i];a[i]=t;System.out.println("("+a[j]+","+t+")");}}

Brute force approach. It keeps making random swaps until all the possible permutations have took place. It uses a Set of the string representation of the array in order to check how many different states have been generated. For n different integers there are n! = 1*2*3*..*n distinct permutations.

Update

Followed Kevin Cruijssen's suggestions to golf it a bit more.

Ungolfed:

import java.util.*;

interface P {

    static Set<String> s = new HashSet<>();

    static void main(String[] a) {
        // prints the original input
        o(Arrays.toString(a));
        while (s.size() < n(a.length)) {
            p(a);
            // prints the array after the swap
            o(Arrays.toString(a));
        }
    }

    static void o(String z) {
        System.out.println(z);
        // adds the string representation of the array to the HashSet
        s.add(z);
    }

    // method that calculates n!
    static int n(int x) {
        if (x == 1) {
            return 1;
        }
        return x * n(x - 1);
    }

    // makes a random swap and prints what the swap is
    static void p(String[] a) {
        Random r = new Random();
        int l = a.length, j = r.nextInt(l), i = r.nextInt(l);
        String t = a[j];
        a[j] = a[i];
        a[i] = t;
        System.out.println("(" + a[j] + "," + t + ")");
    }
}

Usage:

$ javac P.java
$ java P 1 2 3
[1, 2, 3]
(2,1)
[2, 1, 3]
(1,1)
[2, 1, 3]
(2,2)
[2, 1, 3]
(3,1)
[2, 3, 1]
(3,1)
[2, 1, 3]
(1,2)
[1, 2, 3]
(1,1)
[1, 2, 3]
(3,2)
[1, 3, 2]
(2,3)
[1, 2, 3]
(3,1)
[3, 2, 1]
(3,1)
[1, 2, 3]
(3,3)
[1, 2, 3]
(1,2)
[2, 1, 3]
(1,3)
[2, 3, 1]
(1,2)
[1, 3, 2]
(3,1)
[3, 1, 2]

As you can see there are many more swaps than the necessary minimum. But it seems to work :-D

As a bonus, it works with strings too, i.e.

$ java P 'one' 'two'
[one, two]
(two,one)
[two, one]


Find the result of some assignment statements

APL (Dyalog Unicode), 22 bytes

{n⊣⍵{0::0⋄⍵⍎⍺}¨n←⎕NS⍬}

Try it online!
Takes a list of statements in the form of a←b←3, and returns a namespace which is essentially a hashmap of variable names to values. You can't print all the contents of it directly, but you can inspect individual variables like ns.somevar or list all names using ns.⎕NL ¯2.
Oh, and APL doesn't have any alphanumeric-only keywords!
{n⊣⍵{0::0⋄⍵⍎⍺}¨n←⎕NS⍬}  ⍝ ⍵: list of statements
               n←⎕NS⍬   ⍝ Create an empty namespace
   ⍵{        }¨         ⍝ For each statement...
          ⍵⍎⍺           ⍝ Try executing the statement inside the namespace
     0::0⋄              ⍝ ignoring any errors (undefined name)
 n⊣                     ⍝ Return the populated namespace


Not possible in Ruby!

I wanted to write a regular expression in Ruby that matches valid regular expressions in Ruby, but I must conclude that writing one is not possible.

At first, Ruby seems like a good choice. If I want to check for matching parentheses, I can write a recursive expression like (?<mparen>([^()]|\(\g<mparen>\))*) where mparen matches zero or more things that are either not parentheses, or are a set of parentheses with mparen inside.

So I listed things that are valid and not valid in Ruby regular expressions. Then I found things that I cannot check with regular expressions.

Empty ranges of characters

In Ruby, [a-b] is a valid, but [b-a] is not valid, because a comes before b. This rule is common to several flavors of regular expressions:

$ ruby21 -e '/[b-a]/'
-e:1: empty range in char class: /[b-a]/
$ perl -e 'qr/[b-a]/'
Invalid [] range "b-a" in regex; marked by <-- HERE in m/[b-a <-- HERE ]/ at -e line 1.
$ sed '/[b-a]/!d'
sed: 1: "/[b-a]/!d": RE error: invalid character range

So how do I write a regular expression that matches a-b but not b-a, and works with any range? I can't.

I would like to write (?<begin>.)-[\k<begin>-z] using a backreference to the first character. This would become a-[a-z] or b-[b-z] or so on. (Later I would change z to the highest character, but for now I test lowercase letters.) This fails because I can't use backreferences in ranges! [\k<begin>-z] is the same as [<>-z], as the range >-z includes the letters begkin.

I can write in 202 characters:

a-[a-z]|b-[b-z]|c-[c-z]|d-[d-z]|e-[e-z]|f-[f-z]|g-[g-z]|h-[h-z]|i-[i-z]|j-[j-z]|k-[k-z]|l-[l-z]|m-[m-z]|n-[n-z]|o-[o-z]|p-[p-z]|q-[q-z]|r-[r-z]|s-[s-z]|t-[t-z]|u-[u-z]|v-[v-z]|w-[w-z]|x-[x-z]|y-[yz]|z-z

This covers 26 lowercase letters, but only in their literal forms. Octal and hex escapes are also part of the regular expression syntax. Now a is also \141 and \x61, and z is also \172 and \x7a. My regular expression would need to match \141-\172 and \x61-\x7a, and also a-\172 and \x61-z and so on.

(a|\\141|\\x61)-([a-z]|\\1(4[2-7]|[5-7][0-7])|\\x(4[1-9a-fA-F]|[5-7]\h))

I would not try to extend this to the 1112064 codepoints of Unicode.

Missing capture groups

A regular expression is not valid if it has a backreference to an undefined capture group. For example, (?<a>)\k<b> is not valid because it has no capture group b. So, my regular expression for valid regular expressions would need to check \k<b> against the set of valid names. I can't think of a way to do this in one regular expression.

The answer is not (?<=\(\?<b>.*)\\k<b>. This would use the lookbehind feature to match \k<b> if there was a (?<b> earlier in the string. It fails because variable quantifiers like * are not valid in lookbehind expressions.

Another problem happens with subexpression calls. It is valid for two capture groups to share the same name, but it is not valid for a subexpression call to use a multiplex name. So (?<a>)(?<a>) is valid but (?<a>)(?<a>)\g<a> is not.

Encoding troubles

A valid regular expression must also be valid in its character encoding. If the encoding is UTF-8, then \xc4\x80 is valid but \x80\x80 is not. My regular expression for regular expressions would also need to validate UTF-8. It is valid to mix octal and hex escapes, so \xc4\200 and \304\x80 are valid too.

Ruby has other encodings. My regular expression would also need to validate EUC-JP, Windows-31J, GB18030, and every other ASCII-compatible encoding known to Ruby. That's not possible! My regular expression can't know which encoding to validate.

Is \200 a valid regular expression? Regexp.new '\200'.encode('binary') is valid, but Regexp.new '\200'.encode('utf-8') is not valid. My regular expression can't see the encoding tag. It can only see the four ASCII characters in \200, so it can't decide whether \200 is valid.

I might fix this if I decree that my regular expression for regular expressions only works with one encoding. I might pick 'us-ascii', which has only 128 characters. This does not fix my problem with capture groups.


Create an n to the d tic tac toe win-checker

Not an answer - Java

I was curious to see how many different ways there were to win for a given n,d so I wrote this code to list them all.

import java.util.*;

public class MultiDTTT {
    static Set<Win> wins = new HashSet<Win>();
    static final int d = 3;
    static final int n = 3;
    static final char maxChar = (char)(n-1) + '0';

    public static void main(String[] args) throws Exception {
        String pad = "";
        for(int i=0; i<d; i++) pad = pad + "0";
        for(int i=0; i<Math.pow(n,d); i++) {
            String s = Integer.toString(i,n);
            s = pad.substring(s.length()) + s;
            buildWin(s,"",0);
        }
        System.out.println(wins.size());
        for(Win w : wins) System.out.println(w.toString());
    }

    static void buildWin(String s, String p,int i) {
        if(i<d) {
            if(s.charAt(i) == '0') {
                buildWin(s,p+"u",i+1);
                buildWin(s,p+"s",i+1);
            }
            else if(s.charAt(i) == maxChar) {
                buildWin(s,p+"d",i+1);
                buildWin(s,p+"s",i+1);
            }
            else {
                buildWin(s,p+"s",i+1);
            }
        }
        else {
            if(p.contains("u") || p.contains("d")) wins.add(new Win(s,p));
        }
    }

    static class Win {
        String start;
        String pattern;
        Set<String> list = new HashSet<String>();

        Win(String s, String p) {
            start = s;
            pattern = p;
            char[] sc = s.toCharArray();
            for(int i=0; i<n; i++) {
                list.add(new String(sc));
                for(int j=0; j<d; j++) {
                    switch (p.charAt(j)) {
                        case 'u':
                            sc[j]++;
                            break;
                        case 'd':
                            sc[j]--;
                            break;
                        case 's':
                            break;
                    }
                }
            }
        }

        public String toString() {
            String s = ""; //start + ", " + pattern + "\n    ";
            for(String ss : list) s = s + ss + " ";
            return s;
        }

        public boolean equals(Object x) {
            return (x instanceof Win) && this.list.equals(((Win)x).list);
        }
        public int hashCode(){
            return list.hashCode();
        }
    }
}

I hand-tested it on n,d = 2..3,2..3 and it appears to work… after that the number of possible ways to win grows quickly as shown below:

n       1       2       3       4       5       6
d
1       1       1       1       1       1       1
2       1       6       8       10      12      14
3       1       28      49      76      109     148
4       1       120     272     520     888     1400
5       1       496     1441    3376    6841    12496
6       1       2016    7448    21280   51012   107744

Having generated all wining sets, I could extend the program to check the given input against winning sets but, of course, that method would never win the golf.  So I was content to stop here - except it looked like I could find a closed-form solution for the number of ways to win as a function of n and d… It is Number of ways to win = 0.5( (n+2)^d - n^d).


Incrementing Numbers, Over Multiple Sessions

bash script, 39,37,21 18
wc -l<$0;echo>>$0

Short and sweet, my first submission in code golf :)


The shortest game of halma is 49 moves

49 move solution

Proof there is no 48-move solution

Code used for this solution

The code now supports pass

Notice that the 47 move solution in the paper is for the army transfer problem, not for the shortest game of halma

I'll hopefully get to doing a proper writeup this weekend


Japt, 55 51 bytes

`
SÆ
NÆ° `·gV +`
E†t
Wƒt`·gU ª`T•t goƒ Í2€e, Ðéy!

Explanation

                      // Implicit: U, V = inputs
`\nSÆ \nNÆ° `       // Take the string "\nSouth \nNorth ".
·                     // Split it at newlines, giving ["", "South ", "North "].
gV                    // Get the item at index V. -1 corresponds to the last item.
+                     // Concatenate this with
`\nE†t\nWƒt`·gU       // the item at index U in ["", "East", "West"].
ª`T•t goƒ Í2€e, Ðéy!  // If the result is empty, instead take "That goes nowhere, silly!".
                      // Implicit: output result of last expression

Try it online!


Python 3.8, 84 83 82 bytes
-2 bytes thanks to dingledooper!

import random as R
print(*[(R:=c([*{*"FUR"}-{R}]))+c(" '2")for c in[R.choice]*16])

Try it online!


V, 14 bytes

òYp$xhòjòÄ$xhh

Try it online!

Explanation:

ò     ò     "Recursively:
 Yp         "  Yank the current line and paste it
   $        "  Move to the end of the current line
    x       "  Delete one character
     h      "  Move One character to the right.
            "  Because of the way loops work in V, this will throw an error if there
            "  Is only one character on the current line.

Now, the buffer looks like this:

0123456789
012345678
01234567
0123456
012345
01234
0123
012
01
0

We just need to do the same thing in reverse for the next line:

j           "Move down one line
 ò     ò    "Recursively (The second ò is implicit)
  Ä         "  Duplicate this line up
   $        "  Move to the end of the current line
    x       "  Delete one character
     hh     "  Move two characters to the right.
            "  Because of the way loops work in V, this will throw an error if there
            "  Is only two characters on the current line.

More interesting alternate solution:

òÄ$xhòç^/:m0
ddGp@qd


JavaScript (ES6),  75 73  71 bytes
Saved 1 byte thanks to @Shaggy
Saved 2 bytes thanks to @Neil

s=>/1|7|(2[^07]|3[578]|42|599?|50|6[789]|8[0578]|9[679]|.)./.exec(s)[0]

Try it online!


R, 301 287 277 274 222 217 195 186 178 174 bytes

Nothing particularly creative, including the zero buffering of the peripheral elements of the entry matrix, an earlier version later improved by Robin:

function(x){w=which.max
if(any(s<-!x^.5%%1)){
y=cbind(NA,rbind(NA,x,NA),NA)
z=y[i]=y[i<-w(y*y%in%x[s])]^.5
m=i+c(r<--c(1,nrow(y)),-r)
y[j]=y[j<-m[w(-y[m])]]*z
x=p(y[r,r])}
x}

Try it on-line

Using a sequence of numbers as its entry, and hence removing the call to a function, Nick Kennedy earlier managed a 186 bytes version of the algorithm as follows (with -10 bytes by Robin):

w=which.max;`~`=cbind;x=scan();while(any(s<-!x^.5%%1)){y=NA~t(NA~matrix(x,n<-length(x)^.5)~NA)~NA;i=w(y*y%in%x[s]);=i+c(r<--c(1,n+2),-r);y[j]=y[j<-m[w(-y[m])]]*(y[i]=y[i]^.5);x=y[r,r]};x

avoiding the definition of a (recursive) function, plus other nice gains.

Try it on-line


CJam (58 56 bytes)

2q~:Xm*{7Yb#W=}:F,Xm*{ee{~0a@*\+}%zS*F},_Wf%:z&Mf*1fb:e>

This is incredibly slow and uses a lot of memory, but that's code-golf for you.

Dissection

2q~:Xm*        e# Read input into X and find Cartesian product {0,1}^X
{7Yb#W=}:F,    e# Filter with a predicate F which rejects arrays with a 111
Xm*            e# Take the Cartesian product possible_rows^X to get possible grids
{              e# Filter out grids with an anti-diagonal 111 by...
  ee{~0a@*\+}% e#   prepending [0]*i to the ith row
  zS*F         e#   transposing, joining on a non-1, and applying F
},
_Wf%:z         e# Copy the filtered arrays and map a 90 degree rotation
&              e# Intersect. The rotation maps horizontal to vertical and
               e# anti-diagonal to diagonal, so this gets down to valid grids
Mf*            e# Flatten each grid
1fb            e# Count its 1s
:e>            e# Select the maximum

The number of valid rows is a tribonacci number and is \$\Theta(a^X)\$ where \$a\$ is the tribonacci constant, \$1.83928675\ldots\$. The number of grids generated in the Cartesian product is \$\Theta(a^{X^2})\$; the second filter will reduce the number somewhat, but the intersection is still probably \$\Theta(a^{X^4})\$.

An "efficient" approach ("merely" \$O(X a^{3X})\$) uses dynamic programming. Ungolfed in Java:

public class A181018 {
    public static void main(String[] args) {
        for (int i = 1; i < 14; i++) {
            System.out.format("%d:\t%d\n", i, calc(i));
        }
    }

    private static int calc(int n) {
        if (n < 0) throw new IllegalArgumentException("n");
        if (n < 3) return n * n;

        // Dynamic programming approach: given two rows, we can enumerate the possible third row.
        // sc[i + rows.length * j] is the greatest score achievable with a board ending in rows[i], rows[j].
        int[] rows = buildRows(n);
        byte[] sc = new byte[rows.length * rows.length];
        for (int j = 0, k = 0; j < rows.length; j++) {
            int qsc = Integer.bitCount(rows[j]);
            for (int i = 0; i < rows.length; i++) sc[k++] = (byte)(qsc + Integer.bitCount(rows[i]));
        }

        int max = 0;
        for (int h = 2; h < n; h++) {
            byte[] nsc = new byte[rows.length * rows.length];
            for (int i = 0; i < rows.length; i++) {
                int p = rows[i];
                for (int j = 0; j < rows.length; j++) {
                    int q = rows[j];
                    // The rows which follow p,q cannot intersect with a certain mask.
                    int mask = (p & q) | ((p << 2) & (q << 1)) | ((p >> 2) & (q >> 1));
                    for (int k = 0; k < rows.length; k++) {
                        int r = rows[k];
                        if ((r & mask) != 0) continue;

                        int pqrsc = (sc[i + rows.length * j] & 0xff) + Integer.bitCount(r);
                        int off = j + rows.length * k;
                        if (pqrsc > nsc[off]) nsc[off] = (byte)pqrsc;
                        if (pqrsc > max) max = pqrsc;
                    }
                }
            }

            sc = nsc;
        }

        return max;
    }

    private static int[] buildRows(int n) {
        // Array length is a tribonacci number.
        int c = 1;
        for (int a = 0, b = 1, i = 0; i < n; i++) c = a + (a = b) + (b = c);

        int[] rows = new int[c];
        int i = 0, j = 1, val;
        while ((val = rows[i]) < (1 << (n - 1))) {
            if (val > 0) rows[j++] = val * 2;
            if ((val & 3) != 3) rows[j++] = val * 2 + 1;
            i++;
        }

        return rows;
    }
}


Javascript (ES6) + jQuery, 247 bytes

s=>c=>$.getJSON('https://tio.run/static/645a9fe4c61fc9b426252b2299b11744-languages.json',data=>{for(l of Object.values(data))s=s.replace(eval(`/([^a-zA-Z]|^)${l.name.replace(/[\\/+.|()]/g,"\\$&")}(?![a-zA-Z])/g`),`$1[${l.name}](${l.link})`);c(s)})

Explanation (less golfed)

s=>c=>
// Load TIO languages using jQuery
$.getJSON('https://tio.run/static/645a9fe4c61fc9b426252b2299b11744-languages.json',data=>{
  // For every language
  for(l of Object.values(data)) {
    // Construct a regex that matches the language name
    var regex = eval(`/([^a-zA-Z]|^)${l.name.replace(/[\\/+.|()]/g,"\\$&")}(?![a-zA-Z])/g`
    // Replace all occurences of the language name with the language name and link
    s=s.replace(regex),`$1[${l.name}](${l.link})`)
  }
  // Return using callback
  c(s);
});

f=
s=>c=>$.getJSON('https://tio.run/static/645a9fe4c61fc9b426252b2299b11744-languages.json',data=>{for(l of Object.values(data))s=s.replace(eval(`/([^a-zA-Z]|^)${l.name.replace(/[\\/+.|()]/g,"\\$&")}(?![a-zA-Z])/g`),`$1[${l.name}](${l.link})`);c(s)})

f("47")(console.log);
f("///")(console.log);
f("////")(console.log);
f("//////")(console.log);
f("Uṅıċȯḋė")(console.log);
f("\///")(console.log);
f("S.I.L.O.S.I.L.O.S")(console.log);
f("Del|m|t")(console.log);
f("Del|m|tcl")(console.log);
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>


Brainf*** code golf challenge - write a Brainf*** program that searches for the first non-zero cell

11 24 Points
Edit: Now, we do not change the value that is there and do not output it. This now behaves as expected for 255 as well.
+[-[[-<<+>>]<<+>>-<]>+]-<<[->>+<<]>>

This program searches for the first non-zero byte and exits. We expect the first value pointed at to be 0, and we require that the pointer be at least at cell 1 to begin with ("The program should start somewhere in fairly low memory").
Here's a little test, no funky interpreter required:
[ Search for the first non-zero cell            ]
[ http://codegolf.stackexchange.com/q/54432/31054   ]

[We require moving one cell to the right from the left end ] >

[Testing code: ]
>>>>>>>>> [... any number of > ...] >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
[ASCII code '0'] ++++++[-<++++++++>]
<<<<<<<<< [... the same number of < ...] <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

[Find it and stop:  ]
+[-[[-<<+>>]<<+>>-<]>+]-<<[->>+<<]>>

>[Output, for checking: ]<
.

Example run:
~ Me$ bf f.bf
0


Pyth, 26 20
Lnb_bWP`+QZ=Z-g0ZZ)Z

Updated to meet the new rules.
The program runs in an infinite loop which tests every possible increment, in the order 0, -1, 1, -2, -2 ...
Explanation:
Q=eval(input())     implicit
Z=0                 implicit
Lnb_b               def P(b): return b != rev(b)
WP`+QZ              while P(repr(Q+Z)):
=Z-g0ZZ             Z=(0>=Z)-Z
)                   <end while>
Z                   print(Z)

Example run:
python3 pyth.py programs/palin.pyth <<< 965376457643450
-2969881

This took 23 seconds.

Bonus solution, same character count:
Wn`+QZ_`+QZ=Z-g0ZZ)Z


What characters are more common in my MD2 hash?

Mathematica, 43 bytes

Tr@Sign[15-2#~Hash~"MD2"~IntegerDigits~16]&

Outputs the number of digits in 01234567 minus the number of digits in 89abcdef.


Pyth, 105 103 100 92 86 bytes

V.pQK0FktlNJ.a[@Nk@Nhk)FdlNI&!qdk&!qdhkq+.a[@Nk@Nd).a[@Nd@Nhk)J=K.n5B)=K+KJ)IgKZ=ZK))Z

              Z = 0 - value of longest path
              Q = eval(input())

V.pQ         for N in permutations(Q):
  K0           K = 0 - value of current path
  FktlN        for k in len(N) - 1:
    J.a          set J = distance of
    [@Nk                 Q[k] and Q[k+1]
    @Nhk)
    FdlN         for d in len(N):
I&                 if d != k && d != (k + 1)
!qdk
&!qdhk
q+                and if sum of
.a                   distance Q[k] and Q[d]
 [@Nk
 @Nd)
.a                   distance Q[d] and Q[k+1]
 [@Nd
 @Nhk)
J                    are equal to J then
  =K.n5              set K to -Infinity
  B                  and break loop
                     ( it means that we passed over point )
  )                   end of two if statements
=K+KJ                  K+=J add distance to our length
)                      end of for
IgKZ                   if K >= Z - if we found same or better path
  =ZK                  Z = K       set it to out max variable
))                     end of two for statements
Z                      output value of longest path

Try it here!


Perl, 49 bytes

Added +3 for -an0

Input on STDIN or 1 or more filenames as arguments.
Run as perl -an0 wc.pl

wc.pl:

/\z/g;pos=~//;printf"%@+d %@+d $`
",y/
//,~~@F

Explanation:

-n0      slurps the whole input into $_ and says we will do our own printing
-a       tells perl to split the input on whitespace into array @F
/\z/g    Matches the absolute end of the input. g modifier so the position
         is remembered in pos which will now contain the input length
pos=~//  An empy regex repeats the last succesful match, so /\z/ again.
         After that $` will contain the the number of input characters and
         the array @+ will contain the length of this number
printf   All preparation is complete, we can go print the result
"%@+d"   will become e.g. %6d if the number of characters is a number of
         length 6, so lines and words will get printed right aligned
         in a field of length 6.
$`       $` we can directly interpolate since it won't contain a %
y/\n//   Count the number of newlines in $_
~~@F     The array of words @F in scalar context gives the number of words


Python 2, 77 72 71 62 60 bytes

lambda n:reduce(lambda x,c:eval(c.join(`x`)),'*+'*n,-n*~n/2)

Thanks to @xnor for golfing off 2 bytes!

Try it online!


Maximum number of PEP8 violations in a single line

241

if you want the most error, just go crazy with semicolon

$ cat test.py
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

$ cat test.py | wc -m
120

$ pep8 test.py | wc -l
241

most of the error are:

test.py:1:119: E231 missing whitespace after ';'
test.py:1:119: E702 multiple statements on one line (semicolon)

with those error at the end:

test.py:1:120: E703 statement ends with a semicolon
test.py:1:121: W292 no newline at end of file


Python 2, 62 bytes

def f(s):b,a=[eval(s)/2.for j in-1,1];print'%d+j*%d'%(a+b,a-b)

We simply evaluate the expression s with  j=1 and j=-1, and output half their sum and half their difference as the coefficients of 1 and j.
This works because both j=1 and j=-1 satisfy the defining equation defining equation j*j==1. So, the original and simplified expressions must be equal for both these values. The simplified expression is linear, so this gives two linear equations in two unknowns:
x + 1*y  = s(1)  = 2*a
x - 1*y  = s(-1) = 2*b

which is solved by x=a+b, y=a-b.


Sorting a list of strings without using any built-in sort method

Ruby 76 54 51 chars

x=gets.scan /\w+/;$><<x.dup.map{x.delete(x.min)}*?,


Pyth, 33 bytes

M?+&<HGgtGH&+-499GHgGtHH1g749 250

Try it online: Pyth Compiler/Executor. Takes about 3 seconds on my laptop. The online compiler is a bit slower, but also computes the answer in about 15 seconds.

The answer is:

160547283350099323317963999889002394629262478407796913030854915361460989263675794524349914992326520887556329626280682363011590724268659750627030457440692447081328860242720905181098211539560301455338502543318855115593179999323115473879753632000

Explanation:

First some pseudo-code of the recursive function. This is quite easy to write.

function g(p, n):
   if (p > 0 and n > 0):
      count = 0
      if (occupied_places_in_barn < 499):
         count += g(p-1, n)
      if (occupied_places_in_barn > 0):
         count += g(p, n-1)
      return count
   else:
      return 1 # only one way possible

And the Pyth translation:

M                                  def g(G,H): return _
    <HG                               H < G
   &   gtGH                                 and g(G-1,H)
            +-499GH                   499-G+H
           &       gGtH                       and g(G,H-1)
  +                                   return sum of these two numbers
 ?                     H1             if H else 1
                         g749 250  call g(749,250) and print

Why is this recursive code so fast? Doesn't the function g iterate over all 1.6*10^199 possibilities?

No it doesn't. The key here is dynamic programming. We store known results in a cache and lookup the results, when we call the function with the same parameters again. One really cool feature of Python is the @lru_cache decorator, which does all the work for you. No need to manually generate such a cache and handle stuff like lookup, storing results, ... And in Pyth it's even simpler, since each function automatically uses such a cache. So in total the function g gets executed only 125499 times. Way less than 1.6*10^199 times.


CJam, 43 41 40 bytes

{6a4*:mr$0Zt:+}6*]$2m<"FRXWCDM"r#4e<3e\p

Thanks to @Sp3000 for golfing off 1 byte.

Try it online in the CJam interpreter.

How it works

{             }6*                       e# Repeat 6 times:
 6a4*                                   e#   Push [6 6 6 6].
     :mr                                e#   Replace each six with a pseudo-randomly
                                        e#   generated integer in [0 ... 5].
        $                               e#   Sort the results.
         0Zt                            e#   Replace the lowest result by 3.
            :+                          e#   Add all four integers
                ]                       e# Wrap the 6 generated integers in an array.
                 $                      e# Sort.
                  2m<                   e# Rotate 2 units to the left to assign the
                                        e# second highest result to Constitution.
                     "FRXWCDM"          e# Push that string.
                              r#        e# Find the index of the input.
                                        e# The string doesn't contain B, P or S, so
                                        e# those push -1.
                                4e<     e# Truncate the index at 4. This way, C, D
                                        e# M all push 4.
                                   3e\  e# Swap the integer at that index with the
                                        e# one at index 3, i.e., the highest one.
                                      p e# Print.


Given a string find the substring which appears most often

Perl, 99 (+1) bytes

$_=$;{(sort%;)[m{(.+).*\1(?{$;{$;x$+=~y///c.1x@{[/$+/g]}.2x$+[1]}=$+})^}]}
||"No substrings repeat."

Requires a -p command line switch.

For each repeated substring a hash entry is created, such that the largest substring, repeated the most times, with the earliest position is guaranteed to be the smallest key in the hash. The hash is then sorted, and the corresponding value for the smallest key is output.

Sample Usage:

$ echo 123456 | perl -p repeated-substring.pl
No substrings repeat.

$ echo 12121 | perl -p repeated-substring.pl
12

$ echo 99999999 | perl -p repeated-substring.pl
9999

$ echo 321321788788788 | perl -p repeated-substring.pl
788

$ echo 12012112299999999 | perl -p repeated-substring.pl
9999

$ echo 56698853211564788954126162561664412355899990001212345 | perl -p repeated-substring.pl
412


PHP, 229 174

<?php $s=" |.. w\$km<]_d\x7F}";for($r=3;$r--;print'
')foreach(str_split(date('H:i'))as$c)echo$c>'9'?$s[$r+2]:$s[($d=ord($s[$c+5])>>$r*3)/2&1].($d&1?@__:'  ').$s[$d/4&1],'  ';

$s is a lookup table that encodes several things. The first two characters are the vertical segments, when off or on. The next three characters are the characters of the colon on each of the three rows. The character codes of the remaining characters encode in binary the state of the segments of each digit.

Old version, 229 chars:

<?php foreach([strtr(decbin(735),['    ',' __ ']).' ','|  |   | __| __||__||__ |__    ||__||__|.','|__|   ||__  __|   | __||__|   ||__| __|.']as$r){foreach(str_split(date('H:i'))as$c)echo substr($r,ord($c)-48<<2,4).'  ';echo'
';}

Useful fact: the ASCII code of : is one greater than the ASCII code of 9, so 0123456789: are contiguous.


Excel, 48 bytes

Hooray! Finally something Excel is actually good at.

=COUNT(VALUE(ROW(1:12)&"/"&A1/ROW(1:12)&"/"&A1))

Takes input from A1 in the form of an integer 1-99 representing the year, and outputs to wherever you enter this formula. It's an array formula, so use Ctrl-Shift-Enter instead of Enter to enter it.

This takes advantage of the fact that COUNT ignores errors, so any errors that are caused by either the month not dividing the year (leading Excel to parse something like 2/12.5/25 or by the date not being valid, like 2/29/58, are just silently ignored.


Python, no string manipulation

def f(n):
    n += 1
    p = 1
    m = n
    while m:
        if m % 1000 == 666:
            n += p - n % p
        p *= 10
        m /= 10
    return n

Works by finding powers of 10, p, where 666 appears, and adding p - n % p to n which replaces 666xxxxx with 66700000.


Python
# This "program" does nothing and assumes "valid code" means it doesn't throw an error.

You might want to tighten up the rules a bit.


Shortest representation of an Underload number

Python 2.7 - 87 84 92

u=lambda n:n>1and min([u(i)+u(n/i)for i in range(2,n)if n%i<1]+[':'+u(n-1)+'*'],key=len)or''

Explanation:
This is a pretty straightforward solution. It recursively tests all possible representations of n as either the product of two numbers or as :(n-1)*, and then finds the minimum length solution. range(2,n) is necessary so that the recursion has bounded depth, and n<2 gives the base case.

Notes:
i and n/i are the two factors of n. The ... and ... or ... replacement for ... if ... else ... doesn't work because '' evaluates to false. min of strings gives one of the shortest strings. Python 2.7 saves 1 character by using / instead of //.

Edit: Moved the base case to the back of the expression, allowing me to use ... and ... or ... and shave a couple spaces.

Test cases:

u(1)
''
u(5)
'::*:**'
u(49)
'::*:*:*:*::***'


First of all, this is totally cheaty, and not complete to the specs.

requires the --disable-web-security flag on chrome, +22

Javascript 509 + 22 = 531

x=new XMLHttpRequest;y=Object.keys(x);b=alert;q="querySelectorAll";s="send";x[y[3]]="document";x.open("GET","http://www.wolframalpha.com/input/?i="+escape(prompt()));x[y[10]]=function(c){4===x.readyState&&(w=[].filter.call(x.response[q](".pod h2"),function(a){return"ame:"==a.innerText.slice(-4)})[0].parentElement,(k=w[q]("a")[0])&&"Words only"==k.innerText?(x.open("GET",k.href),x.send()):alert(JSON.parse([].pop.call(x[y[2]][q]("script")).innerHTML.match(/d_0.00\.push\((.+?)\)/)[1]).stringified))};x[s]()

The first off the spec is as well the example output
The input two plus two minus five times five divided by negative zero point five outputs

Any other case should get handled fine (now), this is yet pretty ungolfed as is, I just wanted it to get fixed.

input: two plus two
output: four

input: twenty-one point five minus one point five
output: twenty

input: one minus two
output: negative one

input: five times five
output: twenty-five

input: twenty-five divided by five
output: five

input: two plus two minus five times five divided by negative zero point five
output: fifty-four

input: one million times one thousand
output: one billion

input: one million times one thousand plus one
output: one billion, one

input: two million plus one million:
output: three million

input: one million plus one million plus one million
output: three million

Oh, and if you actually going to test it, it may take a few seconds, as it loads the complete Wolfram Alpha page up to two times.

Well, there might be a lot to enhance though.


Monday Mini-Golf #6: Meeesesessess upp teeexexextext

Retina, 43 bytes

.(?<=[^_\W]([^_\W]+))(?<=(\1)(?<=\D))?
$1$2

Run the code from a single file with the -s flag. Since this is just a single regex substitution, you can test it here (click the Context tab to see the results).

Explanation

This matches any digit and letter which is not the first in a run. While . can match any non-linefeed character, the lookbehinds ensure the other conditions:

(?<=[^_\W]([^_\W]+))

This matches backwards from the position after the .. First it matches one or more alphanumeric characters and captures them into group 1 with ([^_\W]+). This immediately ensures that the . corresponds to an alphanumeric character itself. Then the additional [^_\W] makes sure that there is one more alphanumeric character in the current run, which we don't include the match. Now group 1 is what we want to replace the match with if it is a digit - if it is a letter we want to replace it with twice this string. That's where the second lookbehind comes into play:

(?<=(\1)(?<=\D))?

This one is optional, so if it fails it won't affect the match at all. It first ensures that the . was not a digit via (?<=\D) - so this lookbehind is only relevant when we're matching letters. In that case, we match group \1 once more (this always matches, because we've captured the group from the same position), but capture it into group 2.

Hence, we simply replace the regex with the contents of both groups ($1$2). If the match was a digit, $2 will still be empty and we write back the prefix only once. If it was a letter, $2 is the same as $1 and we write it back twice.


CJam, 49 47

0q')/{'(/):U;,+:TW>{T:W];}*TW={U]',*}*T(}/;W':@

0                 " Push 0 ";
q                 " Read the whole input ";
')/               " Split the input by ')' ";
{                 " For each item ";
  '(/             " Split by '(' ";
  )               " Extract the last item of the array ";
  :U;             " Assign the result to U, and discard it ";
  ,               " Get the array length ";
  +               " Add the top two items of the stack, which are the array length and the number initialized to 0 ";
  :T              " Assign the result to T ";
  W>{             " If T>W, while W is always initialized to -1 ";
    T:W];         " Set T to W, and empty the stack ";
  }*
  TW={            " If T==W ";
    U]',*         " Push U and add a ',' between everything in the stack, if there were more than one ";
  }*
  T(              " Push T and decrease by one ";
}/
;                 " Discard the top item, which should be now -1 ";
W                 " Push W ";
':                " Push ':' ";
@                 " Rotate the 3rd item to the top ";


Pure HTML and CSS, 355 characters

0-0

You may need an up-to-date or beta browser for the CSS animation properties.

Here is a fiddle, with -webkit- vendor prefixes added so that it works in latest Chrome.

The ball just bounces back and forth. The AIs are extremely smart and know not to move.

The 0-0 at the bottom is the score, and you can resize the window.


Perl 6, 29 bytes

{bag(.grep(?*)X-1)⊆.squish}

Try it online!

Very nice challenge for Perl 6. Uses the subset operator on Bags (integer-weighted sets). Explanation:

{
    bag(           # Create bag of
        .grep(?*)  # non-zero elements,
        X- 1       # decremented by one.
    )
    ⊆              # Subset test.
    .squish        # "squish" removes repeated elements in each run.
                   # The result is implicitly converted to a bag
                   # counting the number of runs.
}


I found a semi-edge case where a multiple comparison can be shortened. This is useful when you need to test two or more variables for equality, and only return true if all tests are true.

Instead of this:

$a-eq$b-and$c-eq$d

You might be able to do this:

"$a$c"-eq"$b$d"

It's worked for me in a Pisano Period script, where I changed:

$a-eq1-and$b-eq0

To:

"$a$b"-eq10

Another example:

$a-eq'apple'-and$b-eq'orange'

Can be cut down to:

"$a$b"-eq'appleorange'


Determine If a Challenge is Worth Answering

05AB1E, 167 160 159 158 156 154 143 bytes

Damn, almost as long as a normal language...

Crap... longer currently beating the the Ruby answer by 1 byte.

Now longer than the Ruby answer, argh!.

I probably should go to bed right now.

Thanks to @wnnmaw for saving 1 byte and thanks to @R. Kap for saving another 2 bytes!

Code:

’£Ø ˆå§¾.‡¢ as g;#.¾¿„–(g.ˆåƒÛ('·Ç://ÐÏg.´¢/q/'+•œ_#()).‚Ø())’.e©’„à="Ž»"’DU¢®…îŒ€ƒŠ‡¡`99£þs\®X¡¦vy’„à="‚¬-„¹"’¡¦'>¡¦¦¬l’±¸’¢s\}rUV)O2‹X5›Y3›)P

Or with more readability:

’£Ø ˆå§¾.‡¢ as g;#.¾¿„–(g.ˆåƒÛ('·Ç://ÐÏg.´¢/q/'+•œ_#()).‚Ø())’
 .e©
’„à="Ž»"’
 DU¢®
“îŒ€ƒŠ‡“
 ¡`99£þs\®X¡¦
v
 y’„à="‚¬-„¹"’¡¦'>¡¦¦¬l’±¸’¢s\}rUV)O2‹X5›Y3›)P

Explanation:

First of all, a lot of text is being compressed here, which translates to good old Python. The uncompressed version is:

"import urllib.request as g
 f=g.urlopen('http://ppcg.lol/q/'+pop_#())
 #.append(f.read())"
.e©“class="answer"“¢®"useful and clear"¡`99£þs\®“class="answer"“¡¦vy“class="post-text"“¡¦'>¡¦¦¬l"python"¢s\}rUV)O2‹X5›Y3›)P

This part:

import urllib.request as g
stack.append(g.urlopen('http://ppcg.lol/q/'+pop_stack()).read())`

actually pops a stack value, copies it into the url and fetches all HTML data. The HTML data is pushed on top of the stack using #.append(f.read()).

We count the number of answers, by count the number of occurences of class="answer".

To count the number of votes, we just split the data at "useful and clear" and keep only the digit values of [0:99] using ®"useful and clear"¡`99£þ. This is the number of upvotes.

Eventually, we need to check every answer if the text "Python" exists before the closing header text. To get all answers, we just split the data on class="post-text" and split each of them again on <. We remove the first two elements to get the part in which the language is displayed and check if the lowercase version is in this string.

So, now our stack looks like this for id = 79273:

`[6, '14', 0, 0, 0, 1, 0, 0]`
  │    │   └───────┬──────┘
  │    │           │
  │    │   is python answer?
  │    │
  │    └── number of upvotes
  │
  └─── number of answers

This can also be seen with the -debug flag on in the interpreter.

So, it's just a matter of processing the data:

rUV)O2‹X5›Y3›)P

r                # Reverse the stack
 U               # Pop the number of answers value and store into X
  V              # Pop the number of upvotes value and store into Y
   )O            # Wrap everything together and sum it all up
     2‹          # Check if smaller than 2
       X5›       # Push X and check if greater than 5
          Y3›    # Push Y and check if greater than 3
             )P  # Wrap everything into an array and take the product.
                   This results into 1 if and only if all values are 1 (and not 0).

Uses CP-1252 encoding. You can download the interpreter here.


Javascript (ES6), 101 99 bytes

f=
s=>-~'ONE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE'.split` `.findIndex(x=>s.match([...x].join`.*`))
<!-- snippet demo: -->
<input list=l oninput=console.log(f(this.value))>
<datalist id=l><option value=BOUNCE>
<option value=ENCODE>
<option value=EIGHT>
<option value=BLACKJACK>
<option value=FABULOUS>
<option value=EXERCISE>
<option value=DRIFTWOOD>
<option value=SERVICEMAN>
<option value=INSIGNIFICANCE>
<option value=THROWDOWN>
<option value=ZERO>
<option value=OZNERO>


r=str.replace;print r('abc','b','c')

The magic is real.

Shortening str.replace()


Tic Tac Toe: print all possible positions without duplicates

Jelly, 192 179 168 bytes
5ĿḢṠµFf0L¬ị⁾-/µ5ĿḢṠµ?
U,µṚ,µ€µ“æɗþƑ’DịFs3,µ€€Fs9s3$€Ṣ
FSµ×’¬
ÑPµA_µọ9n1
,UŒDḢ$€;;ZS€f3,-3
Ç,SS€µṪµṪCµSṠ‘µ?÷Ḣ
Ça3Ŀa4Ŀ
3ṗ9_2s3$€ÇÐf2Ŀ€QḢ€µ;ÑFµ€µ3Ḷ’,“O¤X”yµ€Fs10µs3Gµ€j⁾¶¶

Try it online! (Takes about 30 seconds, so be patient).
How it Works
High level overview:
In intermediate steps, this stores X as 1, unplaced as 0, and O as -1.
The program generates all 3^9 possibilities, then keeps only the valid positions based on meeting the three criteria:

There is 1 or 0 more X than O.
Not both X and O have won.
If X has won, there is 1 more X than O. If O has won, there are an equal number of Os and Xs.

Then, the program replaces each game state with all of its rotations and reflections to get a list of all equivalence classes. This is the operation which takes most of the time.
The first game state is taken from each of the equivalence classes, then who won is calculated.
Where this happens
The lines are numbered for readability
1: 5ĿḢṠµFf0L¬ị⁾-/µ5ĿḢṠµ?          ••calculates who wins (output as -1 or 1) or draw ("-") or in game ("/")
                 µ5ĿḢṠµ?          - if(someone won based on line 5):
   5ĿḢṠ                             - return 1 if X won and -1 if O won
       µ                          - else:
        Ff0L¬ị⁾-/                   - return "/" if the game is in progress and "-" if the game is at a tied end-state
2: U,µṚ,µ€µ“æɗþƑ’DịFs3,µ€€Fs9s3$€Ṣ••outputs the equivalence class to a game state
   U,                             - list of game state [reflected horizontally, unaltered]
     µṚ,µ€                        - for each, replace with the list [reflected vertically,unaltered]
          µ“æɗþƑ’DịFs3,µ€€        - for each, replace with the list [rotated 90 degrees counter-clockwise,unaltered]
                          Fs9s3$€ - reformat into list of game states
                                 Ṣ- Sort
3: FSµ×’¬                         ••outputs truthy iff there is the right number of `X`s to `O`s (condition 1)
   FS                             - d = number of `X`s minus number of `O`s
     µ×’                          - d*(d-1): falsey iff d is 0 or 1
        ¬                         - logical not, to return truthy iff d is 0 or 1
4: ÑPµA_µọ9n1                     ••outputs truthy iff there is the right number of winners (condition 2)
   Ñ                              - the winners. [-3,3] is what we want to return falsy on
    PµA_µ                         - 18 on [-3,3] and 0 otherwise
         ọ9n1                     - not divisible by 9 exactly once: 0 on [-3,3] and 1 otherwise
5: ,UŒDḢ$€;;ZS€f3,-3              ••outputs the number of times each player won.
   ,UŒDḢ$€;;Z                     - the diagonals, rows, and columns of a board
             S€                   - sum of each. Returns -3 or 3 iff the line is only 1s or -1s
               f3,-3              - filter out, keeping only 3s and -3s
6: Ç,SS€µṪµṪCµSṠ‘µ?÷Ḣ             ••return truthy iff the winner corresponds to the respective numbers of X and O (condition 3)
   Ç,SS€                          - list of winners and how many more Xs than Os there are
             µSṠ‘µ?               - if O won, then
        µṪ                          - how many more Xs than Os there are
                                  - else:
          µṪC                       - the complement of how many more Xs than Os there are
                   ÷Ḣ             - deal with no one winning
7: Ça3Ŀa4Ŀ                        ••return truthy iff the game state meets all three conditions
   Ç 3Ŀ 4Ŀ                        - the three conditions: on line 3,4, and 6
    a  a                          - joined by logical ANDs
8: 3ṗ9_2s3$€ÇÐf2Ŀ€QḢ€µ;ÑFµ€µ3Ḷ’,“O¤X”yµ€Fs10µs3Gµ€j⁾¶¶ ••do everything
   3ṗ9_2                        - all possible game states, with -1 for O and 1 for X
        s3$€                    - turn into two-dimensional game boards
            ÇÐf                 - filter based on line 6: if the board meets all three ocnditions
               2Ŀ€Q             - generate the equivalence classes for each and remove repeats based on line 1
                   Ḣ€           - get the first board from each class
                     µ;ÑFµ€     - append the winner to each board based on line 1
   µ3Ḷ’,“O¤X”yµ€                   - map each -1, 0, and 1 to the proper `O`,  `¤`, and `X`.
                Fs10µs3Gµ€         - format each board- winner combos
                          j⁾¶¶     - join the combos by double-newlines


Create a grid as close to a square as possible

CJam, 16 (31 - 10 - 5)

This takes two integers are input, first one being 0 or 1 for direction and second one being the number of O or X in the grid.

It prints an alternate O and X.

:X"OX"*X<\Xmqi){(_X\%}g_X\/?/N*

This is just the function body, to try it out add l~ in front of the code like:

l~:X"OX"*X<\Xmqi){(_X\%}g_X\/?/N*

and give input like

0 10

to get output like

OXOXO
XOXOX

or input like

1 10

for

OX
OX
OX
OX
OX

Try it online here

How it works:

l~                                 "Put the two input integers to stack";
  :X                               "Assign the number of cells to X";
    "OX"*                          "Take string "OX" and repeat it X times";
         X<                        "Slice it to take only first X characters";
           \                       "Swap top two stack elements, now string is at bottom";
            Xmqi)                  "Take square root of X, ceil it and put on stack";
                 {(_X\%}g          "Keep decrementing until it is perfectly divisible by X";
                         _X\/      "Copy it, divide X by that and put it on stack";
                             ?     "Based on first input integer, take either of numbers";
                              /    "Divide the XOXO string that many times";
                               N*  "Join the string parts with a new line";

Example run:

l~ed:X"OX"*edX<ed\edXmqi)ed{(_X\%}ged_edXed\ed/ed?ed/edN*ed

#INPUT:
1 10

#OUTPUT:
Stack: [1 10]

Stack: [1 "OXOXOXOXOXOXOXOXOXOX"]

Stack: [1 "OXOXOXOXOX"]

Stack: ["OXOXOXOXOX" 1]

Stack: ["OXOXOXOXOX" 1 4]

Stack: ["OXOXOXOXOX" 1 2]

Stack: ["OXOXOXOXOX" 1 2 2]

Stack: ["OXOXOXOXOX" 1 2 2 10]

Stack: ["OXOXOXOXOX" 1 2 10 2]

Stack: ["OXOXOXOXOX" 1 2 5]

Stack: ["OXOXOXOXOX" 2]

Stack: [["OX" "OX" "OX" "OX" "OX"]]

Stack: ["OX
OX
OX
OX
OX"]

OX
OX
OX
OX
OX


///, 7 lines, 22 bytes

/
//Hello
,
 Wor
l
d
!

A rare chance for /// to be competitive (well as long as no one starts with Unary and Lenguage...).

The code first encounters a /, and parses the

/
//

as a substitution instruction which removes all newlines from the remainder of the program. Afterwards, the program merely reads

Hello, World!

which is printed verbatim as it doesn't contain any further slashes.


Model a probability table using 15-bit fixed probabilities

Python, score 8.682671033510566e-07, O(n * log(n))
#!/usr/bin/env python
from __future__ import division
from ast import literal_eval
from fractions import Fraction
from operator import itemgetter
from sys import argv
import fileinput

def model(hist):
    TOTAL_FINAL = 0x7fff
    TOTAL_INIT = sum(hist)
    SCALE = Fraction(TOTAL_FINAL, TOTAL_INIT)
    hist_probs = [Fraction(x, TOTAL_INIT) for x in hist]
    res = [max(int(x*SCALE),1) if x > 0 else 0 for x in hist]

    adjust = TOTAL_FINAL - sum(res)
    res_probs = [Fraction(x,TOTAL_FINAL) for x in res]
    diffs = [(x-y)**2 for x,y in zip(hist_probs, res_probs)]
    d2 = [(x-y) for x,y in zip(hist_probs, res_probs)]
    if adjust > 0:
        idx, vals = zip(*list(filter(lambda x:x[1]>0, sorted(((i,x) for (i,x) in enumerate(d2) if hist[i]), key=itemgetter(1), reverse=True))))
        i = 0
        while i < adjust:
            res[idx[i%len(idx)]] += 1
            i += 1
    else:
        idx, vals = zip(*list(filter(lambda x:x[1]<0,sorted(((i,x) for (i,x) in enumerate(d2) if hist[i]), key=itemgetter(1)))))
        i = 0
        while i < adjust:
            res[idx[i%len(idx)]] -= 1
            i += 1

    return res

if __name__ == '__main__':
    for line in fileinput.input():
        print(model(literal_eval(line)))

This takes input as a file (or sequence of files) with one Python-list-format histogram per line, with the filename(s) provided on the command line (like python prog.py hist.txt).
The general strategy here is to make a (decent) initial guess at the best probability representation, by doing integer scaling of the input histogram to 15 bits. This almost always gets the resultant list just shy of 32767 total. To adjust the probabilities, the items with the largest squared differences from the input histogram get incremented. If the result is too high initially, the largest value in the array is decreased by the excess, instead.
Time Complexity
O(n * log(n)), based on the sorting, which is the most time-consuming operation for each histogram.


Rail, 24 bytes

$'main'    #
 -[world]o/

I think this works. And it's both short and readable (as far as Rail goes).

If the removed substring includes any part of $'main' we get Internal Error: Crash: No 'main' function found.
If the removed substring includes the #, there is no way for the program to exit cleanly, so it will always terminate with Crash: No valid move. I believe that it's not possible to delete a substring such that the track forms a valid (infinite) loop.
If the removed substring is in front of the #, it will be disconnected from the end of the track, so the train will crash (with the same error as above).
If the removed substring is after the #, it will also disconnect the # from the end of the track (and potentially even the beginning of the track from the entry point $). So again the same error.

As for the actual program: every Rail program needs to have a $'main' (or a longer variant, but we're golfing here) as an entry point into the function and the train starts on the $ going South-East. Everything on that first line can be part of the track though, so removing the 'main' the track is:

$          #
 -[world]o/

The - and / are simply pieces of rail which we need to let the train take those 45° turns.

[world] pushes the string world and o prints it. # marks the end of the track - the only way to safely terminate a Rail program.

Interestingly, this solution is only possible because Rail allows the tracks to go through the main line - if that wasn't possible # would be after the first newline and the code could always be shortened to

$'main'
 #

which is a valid program that doesn't do anything. (Non-space characters between ' and # wouldn't affect that.)

Also quite interesting: if I had just golfed the task printing world it wouldn't have been much shorter or simpler:

$'main'
 -[world]o#


Octave, 36 34 bytes

@(x)(y=lambertw(-1:0,x))(~imag(y))

Try it online!

I solved this in 10 different ways without the builtin, but I couldn't get the solution for both the -1 branch and the 0-branch. I wasn't able to solve this without resorting to the builtin lambertw function. Even though it uses a builtin, it's far from straightforward.

lambertw will only give out one value by default, namely the W0(x), unless otherwise specified. The problem arises when we specifies that we want two values, both W0(x) and W-1(x). If this is the case, and x>=0, it will return one real and one complex result.

We therefore have to specify that we only want the results where the imaginary part of the result is zero.

Breakdown:

@(x)                              % Anonymous function that takes x as input
    (y=lambertw(-1:0,x))          % The lambertw function, with both the -1 and 0 branches
                        (~imag(y))  % Index, where the elements with imag(y)=0 is true


JavaScript (ES6), 41 bytes
Returns false for valid or true for invalid.

a=>a.some(p=(x,i)=>--p>0?x:a[i+x-1]^=p=x)

Try it online!
Commented
a =>            // a[] = input
a.some(p =      // start with p NaN'ish
  (x, i) =>     // for each value x at position i in a[]:
  --p > 0 ?     //   decrement p; if it's positive:
    x           //     make sure that we have x = 0
                //     (because we're currently over a connection 'line')
  :             //   else:
    a[          //     XOR the entry at ...
      i + x - 1 //     ... i + x - 1 ...
    ]           //
    ^= p = x    //     ... with x; and set p = x
                //     this must give 0 if the puzzle is valid
)               // end of some()

The trickiest case is when a \$0\$ is reached at position \$i\$ and we're currently outside a connection (i.e. \$p\le0\$), which causes the entry at \$i-1\$ to be XOR'ed with \$0\$. If the puzzle is valid, this will always result in \$0\$ as expected because:

if \$i=0\$, we do undefined ^ 0
if \$i>0\$, the entry at \$i-1\$ either was already set to \$0\$ or was cleared by the previous XOR