I need a program where the user inputs an array of doubles and the program outputs the array sorted

Here it is in java. It is utter cheating, unacceptable and unfixable because it creates a MySQL database, insert the number there, do a select with an ORDER BY clause and outputs the numbers given by MySQL. In fact, it is MySQL who is doing the sorting, not the program.

package sorter;

import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.PreparedStatement;
import java.sql.ResultSet;
import java.util.ArrayList;
import java.util.List;
import javax.swing.JOptionPane;

public class SortingAlgorithm {

    private static final String CREATE_DB = "CREATE DATABASE sorting";
    private static final String DROP_DB = "DROP DATABASE sorting";
    private static final String CREATE_TABLE = "CREATE TABLE sorting.sorting ( num double not null )";

    public static void main(String[] args) throws Exception {
        Class.forName("com.mysql.jdbc.Driver");
        List<Double> doubles = new ArrayList<>(50);
        String typed;
        do {
            typed = JOptionPane.showInputDialog(null, "Type a double:");
            if (typed != null) doubles.add(Double.parseDouble(typed));
        } while (typed != null);

        List<Double> sorted = new ArrayList<>(50);

        try (Connection con = DriverManager.getConnection("jdbc:mysql://localhost:3306", "root", "root")) {
            try (PreparedStatement ps = con.prepareStatement(CREATE_DB)) {
                ps.executeUpdate();
            }
            try (PreparedStatement ps = con.prepareStatement(CREATE_TABLE)) {
                ps.executeUpdate();
            }

            for (Double d : doubles) {
                try (PreparedStatement ps = con.prepareStatement("INSERT INTO sorting.sorting (num) VALUES (" + d + ")")) {
                    ps.executeUpdate();
                }
            }

            try (
                    PreparedStatement ps = con.prepareStatement("SELECT * FROM sorting.sorting ORDER BY num");
                    ResultSet rs = ps.executeQuery())
            {
                while (rs.next()) {
                    sorted.add(rs.getDouble("num"));
                }
            }
            try (PreparedStatement ps = con.prepareStatement(DROP_DB)) {
                ps.executeUpdate();
            }
        }

        JOptionPane.showMessageDialog(null, "The array sorted is: " + sorted);
    }
}


Perl, 43 bytes
42 bytes of code + -n flags.
chop$@,say$@while!s/^$@//;s/./say$@.=$&/ge

To run it:
perl -nE 'chop$@,say$@while!s/^$@//;s/./say$@.=$&/ge' <<< "abc
abd
aefg
h"


Linear dependences over the field with two elements


JavaScript (ES6),  134 124  121 bytes
Expects a float and returns an array of 2 strings.
n=>([x,y]=(+(g=n=>s=n.toString(16))(n).replace(r=/[1-f]/g,1)).toExponential().split`e`,[x.replace(r,_=>r.exec(s)),g(+y)])

Try it online!
How?
We first convert the input to hexadecimal and save the result in the variable s.
For instance, 7.257672195146994e93 is turned into:
"deadbeef0000000000000000000000000000000000000000000000000000000000000000000000"

We replace all non-zero hexadecimal digits with 1's:
"111111110000000000000000000000000000000000000000000000000000000000000000000000"

We coerce this back to an integer and invoke the .toExponential() method:
"1.1111111e+77"

We split this string into x = "1.1111111" and y = "+77".
We replace all 1's in x with the non-zero hexadecimal digits of s in order of appearance:
"d.eadbeef"

Finally, we convert y to hexadecimal:
"4d"

Below is another example with 6e-19:
"0.000000000000000b116b7de48f008"
"0.00000000000000011111111111001"
"1.1111111111001e-16"
[ "1.1111111111001", "-16" ]
[ "b.116b7de48f008", "-10" ]

Commented
n => (                       // n = input
  [x, y] =                   // x = mantissa, y = exponent
    (                        //
      +(                     // coerce to integer:
        g = n =>             //   g is a helper function converting its input ...
          s = n.toString(16) //     ... to a hexadecimal string saved in s
      )(n)                   //   invoke g with n
      .replace(              //   replace:
        r = /[1-f]/g,        //     r = regular expression to match the non-zero
                             //         hexa digits
        1                    //     replace all of them with 1's
      )                      //   end of replace()
    )                        //
    .toExponential()         // convert to exponential notation
    .split`e`,               // split into [ x, y ] = [ mantissa, exponent ]
  [                          // output array:
    x.replace(               //   replace in x:
      r,                     //     use r a 2nd time to match the 1's
      _ => r.exec(s)         //     use r a 3rd time to get the next hexa digit
                             //     from s, this time taking advantage of the
                             //     stateful nature of RegExp
    ),                       //   end of replace()
    g(+y)                    //   convert y to hexadecimal
  ]                          // end of output array
)                            //


Pyth, 12 bytes

V+Gt_GXGNrN1

Demonstration.

In Pyth, G is the lowercase alphabet. +Gt_G is abcdefghijklmnopqrstuvwxyzyxwvutsrqponmlkjihgfedcba, the character that needs to be uppercased in each row.

V sets up a for loop over this string, with N as the loop variable.

In the body, XGNrN1 is a string translation function. X translates G, the alphabet, replacing N with rN1, the uppercase version of N. r ... 1 is the uppercase function. This gives the desired output.


Charcoal, 10 bytes

ＵＴＦθ«ι≡ι⸿↑

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

ＵＴ

Disable right padding.

Ｆθ«

Loop over the input.

ι

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

≡ι⸿

... check for an \r...

↑

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


Charcoal, 25 22 21 bytes

≔÷Ｌθ⁴λ↙…θλ→✂θλ±λ↖✂θ±λ

Try it online! Link is to verbose version of code. Simply slices the string into three parts and prints them in the appropriate directions. Edit: Saved 3 bytes by using integer division and slicing. Saved a further byte by using CycleChop instead of Slice for the head of the string. Edit: Charcoal now supports drawing arbitrary text along the edge of a polygon, simplifying the code to 12 bytes:

ＧＨ↙→→↖⊕÷Ｌθ⁴θ

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


Python 3, 100 99 99 97 bytes

-1 byte thanks to ovs
-1 byte thanks to Jonathan Allan
-1 byte thanks to Dennis

for i in b'!-3?':print('Steve Ballmer still does not know what he did wrong with mobile'[:i]+'.')

Try it online!


Compute the polyomino capacity of a rectangle

Python 2, 53 bytes
lambda p,q,n:p/n*q+q/n*(p%n)-min(0,n-p%n-q%n)*(p>n<q)

Adapts the formula given in this paper, which is:
def f(p,q,n):a=p%n;b=q%n;return(p*q-[a*b,(n-a)*(n-b)][a+b>=n and p>=n and q>=n])/n


Is it an arithmetico-geometric sequence?

Wolfram Language (Mathematica), 55 bytes

{}!=Solve[i=Range@Tr[1^#];(a+i*d)r^i==#,{r,a,d},Reals]&

Try it online!

Solve return all solution forms. The result is compared with {} to check if there is any solution.


Pyth - 22 bytes
Hope to golf a lot more, pretty straightforward.
sfq3l`TmCid16csjRQCMz2

Try it online here.


Python 2, 83 bytes

lambda s:re.findall('.*?'.join(s),'qwertyuioplkmnjhbvgfcxdsza'*len(s))[0]
import re

Try it online!

Walks the entire keyboard until the word is written.


Concatenations of powers and their squares

APL (Dyalog Unicode), 21 bytes (SBCS)

Anonymous infix lambda, taking \$r\$ as left argument and \$n\$ as right argument. Requires ⎕IO←0 (zero-based indexing).
{⍵∊(⊢⍎⍤,⍥⍕¨×⍨)⍺*⍳⌊⍟⍵}

Try it online! (Dyalog Extended as polyfill for version 18.0)
{…} "dfn", ⍺ is \$r\$ and ⍵ is \$n\$:
 ⍟⍵ natural log of \$n\$ (to avoid overflow)
 ⌊ round that down
 ⍳ ɩntegers zero through one less than that
 ⍺* raise \$r\$ to those powers
 (…) apply the following monadic function to that:
  ×⍨ multiply those with themselves (i.e. square them)
  ⊢…¨ for each unmodified argument and its corresponding square:
   ⍥⍕… stringify the argument and its square before
    ⍤, concatenating them, and then
     ⍎ evaluating the result
 ⍵∊ is the original argument a member of that?


Python, 153 characters

s=raw_input()
R=range(8)
C=[s[i::9].count('*')for i in R]
print"%d|%d|%.1f|%d"%(min(C),max(C),sum(C)/8.,max(8-s[i::9].find('*')-C[i]for i in R if C[i]))


Common Lisp, 737

self-answer

(lambda(n &aux(d 1))#2=(catch'$(let((s(* n n))(c d))(labels((R(w % @ b ! &aux r h v a)(loop for u from % below s do(setf h(mod u n)v(floor u n)a #4=(aref b u))(when(< 0(logand a w)4)(and(= 6 w)!(throw'! t))(let((b(copy-seq b))(o 5))(loop for(K D)on'(-1 -2 -1 2 1 -2 1 2)for y =(+ K v)for x =(+(or D -1)h)for u =(and(< -1 y n)(< -1 x n)(+(* y n)x))if u do #1=(if(< #4#4)(setf #4#(logand #4#o(if(= w o)3 0)))))(#8=dotimes(y N)(#8#(x N)(let((u(+(* y n)x))(o 6))(if(or(= x h)(= y v)(=(abs(- h x))(abs(- v y))))#1#))))(setf #4#w r(or(cond((= w 5)(R 6 @ U b !))((R 5 @ U b())t)((catch'!(R 5 0 0 b t))t)(t(and(=(decf c)0)(incf d)(or(format t"~%(lambda(&aux(n ~A)(d ~A))~%~S)"n d'#2#)(throw'$ B)))t))r)))))r))(R 5 0 0(fill(make-array s)3)())))))

Example

Paste the above in the REPL, which returns a function object:

#<FUNCTION (LAMBDA (N &AUX (D 1))) {1006D1010B}>

Call it (the star is bound to the last returned value):

QN> (funcall * 4)

This prints the following to the standard output:

(lambda(&aux(n 4)(d 2))
#1=(CATCH '$
 (LET ((S (* N N)) (C D))
   (LABELS ((R (W % @ B ! &AUX R H V A)
              (LOOP FOR U FROM % BELOW S
                    DO (SETF H (MOD U N)
                             V (FLOOR U N)
                             A #2=(AREF B U)) (WHEN (< 0 (LOGAND A W) 4)
                                                (AND (= 6 W) !
                                                     (THROW '! T))
                                                (LET ((B (COPY-SEQ B))
                                                      (O 5))
                                                  (LOOP FOR (K D) ON '(-1
                                                                       -2
                                                                       -1 2
                                                                       1 -2
                                                                       1 2)
                                                        FOR Y = (+ K V)
                                                        FOR X = (+
                                                                 (OR D -1)
                                                                 H)
                                                        FOR U = (AND
                                                                 (< -1 Y N)
                                                                 (< -1 X N)
                                                                 (+ (* Y N)
                                                                    X))
                                                        IF U
                                                        DO #3=(IF (< #2# 4)
                                                                  (SETF #2#
                                                                          (LOGAND
                                                                           #2#
                                                                           O
                                                                           (IF (=
                                                                                W
                                                                                O)
                                                                               3
                                                                               0)))))
                                                  (DOTIMES (Y N)
                                                    (DOTIMES (X N)
                                                      (LET ((U
                                                             (+ (* Y N) X))
                                                            (O 6))
                                                        (IF (OR (= X H)
                                                                (= Y V)
                                                                (=
                                                                 (ABS
                                                                  (- H X))
                                                                 (ABS
                                                                  (- V
                                                                     Y))))
                                                            #3#))))
                                                  (SETF #2# W
                                                        R
                                                          (OR
                                                           (COND
                                                            ((= W 5)
                                                             (R 6 @ U B !))
                                                            ((R 5 @ U B
                                                                NIL)
                                                             T)
                                                            ((CATCH '!
                                                               (R 5 0 0 B
                                                                  T))
                                                             T)
                                                            (T
                                                             (AND
                                                              (= (DECF C)
                                                                 0)
                                                              (INCF D)
                                                              (OR
                                                               (FORMAT T
                                                                       "~%(lambda(&aux(n ~A)(d ~A))~%~S)"
                                                                       N D
                                                                       '#1#)
                                                               (THROW '$
                                                                 B)))
                                                             T))
                                                           R)))))
              R))
     (R 5 0 0 (FILL (MAKE-ARRAY S) 3) NIL)))))

Also, the value returned by this function is:

#(5 0 0 0 0 0 0 6 0 0 0 2 0 2 0 0)

... which is an array literal. Number 5 represents queens, 6 is for knights and anything else stands for an empty cell, except there are more informations stored internally. If we copy-paste the returned function to the repl, we obtain a new function.

#<FUNCTION (LAMBDA (&AUX (N 4) (D 2))) {100819148B}>

And we can call it to, without arguments:

QN> (funcall * )

This call returns a new solution #(5 0 0 0 0 0 0 2 0 0 0 6 0 0 2 0) and the source of another function (not shown here). In case the original function or the last generated one does not find a solution, nothing is printed and nothing is returned.

Internal values

|----------+--------+---------+--------+-----------------|
|          | Binary | Decimal | Symbol | Meaning         |
|----------+--------+---------+--------+-----------------|
| Empty    |    000 |       0 | -      | safe for none   |
|          |    001 |       1 | q      | safe for queen  |
|          |    010 |       2 | n      | safe for knight |
|          |    011 |       3 | #      | safe for both   |
|----------+--------+---------+--------+-----------------|
| Occupied |    101 |       5 | Q      | a queen         |
|          |    110 |       6 | K      | a knight        |
|----------+--------+---------+--------+-----------------|

I used to generate too few solutions. Now, I propagate what cell is safe for a queen and for a knight, independently. For example, here is an output for n=5 with pretty-printing:

Q - - - -
- - - n N
- q - n n
- # n - n
- n # # -

When we placed the queen Q, positions that are a knight-move away from this queen are still safe for queens and denoted q. Likewise, knights that are reachable only by queens are safe for other knights.
Values are bitwise and-ed to represent the possible moves and some cells are reachable by no kind of piece.

More precisely, here is the sequence of boards leading to the following solution (from left to right), where free cells are gradually constrained with different values:

# # # # # #     q - - - q #     - - - - - #     - - - - - #     - - - - - n
# # # # # #     - - Q - - -     - - Q - - -     - - Q - - -     - - Q - - -
# # # # # #     q - - - q #     q - - - - -     Q - - - - -     Q - - - - -
# # # # # #     - q - q - #     - q - - - n     - - - - - n     - - - - - n
# # # # # #     # # - # # -     n n - n N -     - - - n N -     - - - - N -
# # # # # #     # # - # # #     # # - n n n     - # - - n n     - n - - n N

Non-quine approach

Ungolfed, commented version

(defun queens-and-knights
    (n    ; size of problem
     fn   ; function called for each solution

     ;; AUX parameters are like LET* bindings but shorter.
     &aux
       ;; total number of cells in a board
       (s (* n n)))

  (labels
      ;; Define recursive function R
      ((R (w      ; what piece to place: 5=queen, 6=knight
           %      ; min position for piece of type W
           @      ; min position for the other kind of piece
           b      ; current board
           !      ; T iff we are in "check" mode (see below)
           &aux
           r      ; result of this function: will be "true" iff we can
                  ; place at least one piece of type W on the board b
           h      ; current horizontal position
           v      ; current vertical position
           a      ; current piece at position (h,v)
           )

         (loop
            ;; only consider position U starting from position %,
            ;; because any other position below % was already visited
            ;; at a higher level of recursion (e.g. the second queen
            ;; we place is being placed in a recursive call, and we
            ;; don't visit position before the first queen).
            for u from % below s

            do
              (setf h (mod u n)         ; Intialize H, V and A
                    v (floor u n)       ;
                    a (aref b u))       ;

            ;; Apply an AND mask to current value A in the board
            ;; with the type of chess piece W. In order to consider
            ;; position U as "safe", the result of the bitwise AND
            ;; must be below 4 (empty cell) and non-null.
              (when (< 0 (logand a w) 4)

                ;; WE FOUND A SAFE PLACE TO PUT PIECE W

                (when (and ! (= 6 w))
                  ;; In "check" mode, when we place a knight, we knwo
                  ;; that the check is successful. In other words, it
                  ;; is possible to place an additional queen and
                  ;; knight in some board up the call stack. Instead
                  ;; of updating the board we can directly exit from
                  ;; here (that gave a major speed improvement since
                  ;; we do this a lot). Here we do a non-local exit to
                  ;; the catch named "!".
                  (throw '! t))

                ;; We make a copy of current board b and bind it to the
                ;; same symbol b. This allocates a lot of memory
                ;; compared to the previous approach where I used a
                ;; single board and an "undo" list, but it is shorter
                ;; both in code size and in runtime.
                (let ((b (copy-seq b)))

                  ;; Propagate knights' constraints
                  (loop
                     ;; O is the other kind of piece, i.e. queen here
                     ;; because be propagate knights. This is used as
                     ;; a mask to remove knights pieces as possible
                     ;; choices.
                     with o = 5

                     ;; The list below is arranged so that two
                     ;; consecutive numbers form a knight-move. The ON
                     ;; iteration keyword descend sublist by sublist,
                     ;; i.e. (-1 -2), (-2 -1), (-1 2), ..., (2 NIL). We
                     ;; destructure each list being iterated as (K D),
                     ;; and when D is NIL, we use value -1.
                     for (K D) on '(-1 -2 -1 2 1 -2 1 2)

                     ;; Compute position X, Y and index U in board,
                     ;; while checking that the position is inside the
                     ;; board.
                     for y = (+ K v)
                     for x = (+ (or D -1) h)
                     for u = (and (< -1 y n)
                                  (< -1 x n)
                                  (+(* y n)x))

                     ;; if U is a valid position...
                     if u
                     do
                     ;; The reader variable #1# is affected to the
                     ;; following expression and reused below for
                     ;; queens. That's why the expression is not
                     ;; specific to knights. The trick here is to
                     ;; use the symbols with different lexical
                     ;; bindings.
                       #1=(when (< (aref b u) 4) ; empty?
                            (setf (aref b u)

                                  (logand
                                   ;; Bitwise AND of current value ...
                                   (aref b u)

                                   ;; ... with o: position U is not a
                                   ;; safe place for W (inverse of O)
                                   ;; anymore, because if we put a W
                                   ;; there, it would attack our
                                   ;; current cell (H,V).
                                   o

                                   ;; ... and with zero (unsafe for
                                   ;; all) if our piece W is also a
                                   ;; knight (resp. queen). Indeed, we
                                   ;; cannot put anything at position
                                   ;; U because we are attacking it.
                                   (if (= w o) 3 0)))))

                  ;; Propagate queens' constraints
                  (dotimes (y N)
                    (dotimes (x N)
                      (let ((u(+(* y n)x))(o 6))
                        (if (or (= x h)
                                (= y v)
                                (= (abs(- h x)) (abs(- v y))))

                            ;; Same code as above #1=(if ...)
                            #1#))))

                  (setf
                   ;; Place piece
                   (aref b u) w

                   ;; Set result value
                   r (or (cond
                           ;; Queen? Try to place a Knight and maybe
                           ;; other queens. The result is true only if
                           ;; the recursive call is.
                           ((= w 5) (R 6 @ U b !))

                           ;; Not a queen, so all below concern
                           ;; knights: we always return T because
                           ;; we found a safe position.
                           ;; But we still need to know if
                           ;; board B is an actual solution and
                           ;; call FN if it is.
                           ;; ------------------------------------

                           ;; Can be place a queen too? then current
                           ;; board is not a solution.
                           ((R 5 @ U b()) t)

                           ;; Try to place a queen and a knight
                           ;; without constraining the min positions
                           ;; (% and @); this is the "check" mode that
                           ;; is represented by the last argument to
                           ;; R, set to T here. If it throws true,
                           ;; then board B is a duplicate of a
                           ;; previous one, except that it is missing
                           ;; pieces due to constraints % and @. The
                           ;; "check" mode is a fix to a bug where we
                           ;; reported as solutions boards where there
                           ;; was still room for other pieces.
                           ((catch'!(R 5 0 0 b t)) t)

                           ;; Default case: we could not add one more
                           ;; layer of pieces, and so current board B
                           ;; is a solution. Call function FN.
                           (t (funcall fn b) t))

                         ;; R keeps being true if it already was for
                         ;; another position.
                         r)))))

         ;; Return result R
         r))

    ;; Start search with a queen and an empty board.
    (R 5 0 0 (fill (make-array s) 3)  nil)))

Duplicates and bugs

My very first solution outputted duplicate solutions. In order to solve it, I introduced two counters for queens and knights. The counter for queens (resp. knights) keep track of the first position in the board where a queen (resp. knight) exists: I add a queen (resp. a knight) only at positions that follow that minimal position.

That methods prevents me from revisiting solutions that were already found in previous iterations, because I iterate with an increasing queen (resp. knight) position.

However, Sleafar noticed that there were solutions for which there could be room for queens and knights, which is against the rules. For a while I though I had to revert to a normal search and store all the known solutions to prevent duplicates, which felt too costly (both in terms of bytes and memory usage).

Instead, here is what I do now: when a potential solution board is found, I try to add exactly one queen and one knight, without taking into account the counters (i.e. for all cells on the board). If this is possible, then current board is a duplicate of a previous one, and I reject the solution.

Tests

|---+---------+------------+--------------|
| N |  boards |    seconds |        bytes |
|---+---------+------------+--------------|
| 3 |       0 |          0 |        32768 |
| 4 |      40 |          0 |       360416 |
| 5 |     172 |          0 |      3440016 |
| 6 |    2836 |   0.085907 |     61251584 |
| 7 |   23876 |   1.265178 |    869666288 |
| 8 |  383586 |  24.991300 |  17235142848 |
| 9 | 6064506 | 524.982987 | 359952648832 |
|---+---------+------------+--------------|

Quine-ification

I had different ideas to make successive quines.
The easiest one is probably to generate all solutions first as a list of strings and write sequential quines which pop from that list at each generation. However this did not seem to be shorter than current approach.
Alternatively, I tried to rewrite the recursive code with a custom stack and dump all the state variables each time I find a solution; the goal is that the next step can be processed as a continuation of current step.
 Maybe this would be better suited for a stack based language.
The current one is quite simple and rely on Common Lisp reader variables, which are always fun to use.


Jelly, 3 bytes

ŻVƝ

A monadic link accepting an integer which yields a list of integers

Try it online!

How?

ŻVƝ - Link: integer       e.g. 59
Ż   - zero-range               [0,1,2,3,4,5,6, ... ,58,59]
  Ɲ - apply to each pair: i.e: [0,1] or [5,6]  or  [58,59]
 V  -   evaluate* jelly code   1     or 56     or  5859
    -                       -> [1,12,23,45,56, ... 5859]

* When given a list V actually joins the Python string values and evaluates that
  ...so e.g.: [58,59] -> ['58','59'] -> '5859' -> 5859


Python, Score: 24 16
This solution, like Falko's one, is based on measuring the "foreground" area and dividing it by the average grain area.
In fact, what this program tries to detect is the background, not so much as the foreground.
Using the fact that rice grains never touch the image boundary, the program starts by flood-filling white at the top-left corner.
The flood-fill algorithm paints adjacent pixels if the difference between theirs and the current pixel's brightness is within a certain threshold, thus adjusting to gradual change in the background color.
At the end of this stage, the image might look something like this:

As you can see, it does a pretty good job at detecting the background, but it leaves out any areas that are "trapped" between the grains.
We handle these areas by estimating the background brightness at each pixel and painting all equal-or-brighter pixels.
This estimation works like so:
during the flood-fill stage, we calculate the average background brightness for each row and each column.
The estimated background brightness at each pixel is the average of the row and column brightness at that pixel.
This produces something like this:

EDIT:
Finally, the area of each continuous foreground (i.e. non-white) region is divided by the average, precalculated, grain area, giving us an estimate of the grain count in the said region. The sum of these quantities is the result.
Initially, we did the same thing for the entire foreground area as a whole, but this approach is, literally, more fine-grained.

from sys import argv; from PIL import Image

# Init
I = Image.open(argv[1]); W, H = I.size; A = W * H
D = [sum(c) for c in I.getdata()]
Bh = [0] * H; Ch = [0] * H
Bv = [0] * W; Cv = [0] * W

# Flood-fill
Background = 3 * 255 + 1; S = [0]
while S:
    i = S.pop(); c = D[i]
    if c != Background:
        D[i] = Background
        Bh[i / W] += c; Ch[i / W] += 1
        Bv[i % W] += c; Cv[i % W] += 1
        S += [(i + o) % A for o in [1, -1, W, -W] if abs(D[(i + o) % A] - c) < 10]

# Eliminate "trapped" areas
for i in xrange(H): Bh[i] /= float(max(Ch[i], 1))
for i in xrange(W): Bv[i] /= float(max(Cv[i], 1))
for i in xrange(A):
    a = (Bh[i / W] + Bv[i % W]) / 2
    if D[i] >= a: D[i] = Background

# Estimate grain count
Foreground = -1; avg_grain_area = 3038.38; grain_count = 0
for i in xrange(A):
    if Foreground < D[i] < Background:
        S = [i]; area = 0
        while S:
            j = S.pop() % A
            if Foreground < D[j] < Background:
                D[j] = Foreground; area += 1
                S += [j - 1, j + 1, j - W, j + W]
        grain_count += int(round(area / avg_grain_area))

# Output
print grain_count

Takes the input filename through the comand line.
Results
      Actual  Estimate  Abs. Error
A         3         3           0
B         5         5           0
C        12        12           0
D        25        25           0
E        50        48           2
F        83        83           0
G       120       116           4
H       150       145           5
I       151       156           5
J       200       200           0
                        ----------
                Total:         16


Python 3 / 84 chars / 7 correct outputs / score 8.3333

edit As per clarifications, removed .upper() and considering all 7 ouputs correct.

a=sorted
for b in input().split():print([c for c in open('x')if a(b)==a(c[:-1])][0])

Output:

BUBBLE
FLOWER
CAKE
WATER
CORK
MILK
PEACE


Piet, 280 273 codels

Edit: I have golfed this down some more, and I think I can golf it down even further, but that is still to come. For now, I'm just glad it works, and that I had room to sign it in the bottom left-hand corner. Two ideas I have to save more codels are a) to change the end instructions be pop, push 1, add, out num (pop n, output r+1) and b) to duplicate again at the bottom left corner to save codels in stack manipulation later on in the loop.

The picture above is my code at 8 pixels per codel. In general, it's the same algorithm as my Python answer, but with the inputs in the order of k, q, n. In practice, there is a also a great deal of stack manipulation. You can try it here by opening the image there and running the code with it.

Explanation

This is a step-by-step ungolfing of the solution.

in num    get k
dup       Stack: k k
push 1
subtract  Stack: k k-1
in num    get q
dup       Stack: k k-1 q q
dup       Stack: k k-1 q q q
push 4
push 2
roll      Stack: k q q k-1 q
mod       Stack: k q q r
in num    get n
# note: the loop will return to the following codel
dup       Stack: k q q r n n
push 4
push 3
roll      Stack: k q r n n q
greater   1 or 0
pointer   Here the loop begins. If q>n, the pointer moves clockwise.
          Else, it points straight ahead

LOOP:     Stack: k i r n (i=q at the start of the loop)
push 4
push 2
roll      Stack: r n k i
push 1
add       Stack: r n k i=i+1
push 2
push 1
roll      Stack: r n i k
dup       Stack: r n i k k
push 5
push 4
roll      Stack: n i k k r
add       Stack: n i k m=r+k
push 3
push 2
roll      Stack: n k m i
dup       Stack: n k m i i
push 3
# here it turns the corner
push 1
roll      Stack: n k i m i
mod       Stack: n k i r=m%i
push 4
# here it turns the corner and avoids the black codels
push 1
roll      Stack: r n k i
dup       Stack: r n k i i
push 5
push 3
roll      Stack: k i i r n
dup       Stack: k i i r n n
# and we meet up with the dark green codel once more
push 4
push 3
roll      Stack: k i r n n i
greater   Stack: k i r n (0 or 1)
pointer   if else again

# else    Stack: k i r n
push 2
push 1
roll      Stack: k i n r
# and turn the corner
push 1
add       Stack: k i n r+1
out num   print r+1
# turn the corner into the end pattern (the shape with the black edges)
END


Javascript + jQuery (997)

Tested on Chrome 32, Firefox 27, IE9

Open Console (F12) from this page and copy/paste the following code.

scroll(0,0);h=1/30;p=[];r=320;n=0;w=80;f=2.5;o=80;t=setInterval;$('#question').children().hide().end().append('

').append('

').click(function(){v=100});$('#s').css({position:'relative',margin:'auto',border:'2px solid',width:200,height:r}).append('');$('').appendTo('head');function u(){$('#m').text('score '+m+' (max '+n+')')}function i(){x=r/2;v=0;m=0;p.length=0;u()}i();t("v-=h*100;x+=h*v;if(x<0||x>r)i();$('.p').remove();for(j=0;j
200){p.shift();j--;m++;if(m>n)n=m;u();}else if((p[j].r>165&&p[j].r<185)&&(x
p[j].h+o))i();else{$('

').appendTo('#s').css({bottom:0,right:p[j].r,height:p[j].h});$('

').appendTo('#s').css({bottom:p[j].h+o,right:p[j].r,height:320-p[j].h-o})}}$('#b').css({position:'absolute',left:0,bottom:x-25})",h*1e3);t("p.push({h:Math.random()*(r-o),r:0})",f*1e3)

  The game replace the question block of this page.
  You have to click on the game frame to make the bird fly.

Ungolfed and commented version :

$('#question').children().hide();
$('#question').append('

');
$('#question').append('

');
$('#scene').css({position:'relative',margin:'auto',border:'2px solid black',width:'200',height:'320'});
$('#scene').append('');
$('#bird').css({display:'block',position:'absolute',left:0,'pointer-events':'none',margin:'0 auto'});
$(window).scrollTop(0);

//CONFIGURATION
var dt=1/30,      //delta timestep (typically 30Hz)
    pipevel=80,   //pipe velocity (in pixels per second)
    pipefreq=2.5, //pipe spawn frequency (in second)
    holesize=80,  //hole size (in pixels)
    gravity=-100, //gravity (in pixels per square second)
    punchvel=100; //velocity punch when clicked (in pixels per second)

var x, y, pipes=[], roof=$('#scene').height(), score, maxscore=0;

function updateScore() {
  $('#score').text('Score : '+score+' (max : '+maxscore+')');
}

function init() {
  x=roof/2; //position
  v=0; //velocity
  score=0;
  pipes.length=0;

  updateScore();
}

function step() {
  //euler integration
  v+=dt*gravity;
  x+=dt*v;

  if (x<0 || x>roof)  init();

  //pipes
  $('.pipe').remove();
  for (i=0; i<pipes.length; i++) {
    pipes[i].rightpos += dt*pipevel;
    if (pipes[i].rightpos > 200) {
      pipes.shift();
      i--;
      score++;
      if (score>maxscore) maxscore=score;
      updateScore();
    } else if ((pipes[i].rightpos > 165 && pipes[i].rightpos < 185) && (x < pipes[i].holepos || x > pipes[i].holepos+holesize)) {
      //collision
      init();
    } else {
      $('#scene').append('

');
      $('#scene').append('

');
    }
  }

  $('#bird').css({bottom:Math.floor(x)-25});

  setTimeout(step, dt*1000);
}

$('#question').click(function() {
  v=punchvel;
});

function addPipe() {
  pipes.push({holepos:Math.random()*(roof-holesize),rightpos:0});
  setTimeout(addPipe, pipefreq*1000);
}

init();
setTimeout(step, dt*1000);
setTimeout(addPipe, pipefreq*1000);

You can easily modify the configuration (gravity, pipe velocity...), have a look at commented version.


APL (Dyalog Unicode) version 16.0, 8384 programs

⍝ empty program
 ⍝ single space
	⍝ single tab
0
1
2
3
4
5
6
7
8
9
+
-
×
÷
⌈
⌊
*
⍟
|
!
○
~
∨
∧
⍱
⍲
<
≤
=
≥
>
≠
≡
≢
⍴
,
⍪
⍳
↑
↓
?
⍒
⍋
⍉
⌽
⊖
∊
⊥
⊤
⍎
⍕
⌹
⊂
⊃
∪
∩
⍷
⌷
→
⎕
1 2 3           ⍝ input for above program
⍞
Hello, World!   ⍝ input for above program
/
⌿
\
⍀
¨
&
⍨
⌶
#
⊆
⊣
⊢
⌸
⍸
⍝
⋄
L:
⍬
{}
⍝ just a newline
⍝ this line belong with the previous one

Try it online! (except for two which cannot run on TIO's version 15.0)
Explanations:
Most of the programs just print their content. Exceptions are:

The four whitespace ones do nothing.
→ terminates
⎕ asks for evaluated input
⍞ asks for character input
⍝ is a comment
⋄ is a statement separator (i.e. two statements that each do nothing)
⍬ prints an empty numeric list (i.e. just a newline)


Ruby, 127

Runs in about 6.5 seconds. Uses a couple of cool tricks. ARGF ($< or stdin, really) is enumerable! If an array is passed as a block argument, it can be "exploded" and assigned to a parameter using {|w,| ... }. Notice the comma.

I found an even shorter solution which uses Array#& (set intersection) to do the lookup of words, but that runs extremely slow, unfortunately.

Thanks to w0lf for shaving off a few characters

D={}
$<.map{|l|D[l.strip!]=l}
puts D.map{|w,|c=[w]
w.chars.all?{w=c[0]
r=D[w.chop]||D[w[1..-1]]
r ?c=[r]+c :p}
c}.max_by &:size

Output

r
ra
rah
rahm
brahm
brahma
brahman
brahmani
brahmanis
brahmanism
brahmanisms

Readable version

D = {}
$<.lines { |l| D[l.strip] = l.strip }

chains = D.map do |word, _|
  chain = [word]

  word.chars.all? do
    word   = c.first
    result = D[w.chop] || D[w[1..-1]]

    result ? chain.unshift(result) : nil
  end
end

puts chains.max_by(&:size)


Actually, 2 bytes

10

Try it online!

This prints

0
1

while the (only) other permutation

01

prints

1
0

How it works

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

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

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


CJam, 18 bytes

UXri{_@+}*;26b'af+

Try it online in the CJam interpreter.

How it works

UX    e# Push 0 and 1.
ri{   e# Read an integer and execute the loop that many times.
  _   e#   Push a copy the topmost integer.
  @   e#   Rotate the bottom-most integer on top of the stack.
  +   e#   Pop the two topmost integers and push their sum.
}*    e#
;     e# Discard the topmost integer from the stack.
26b   e# Convert the remaining integer to base 26.
'af+  e# Add the character 'a' to each base-26 digit.


Python 2, 177 168 162 bytes

import re,itertools as q
f=lambda n:sum(None!=re.match("^M*(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})$",(''.join(m)))for m in q.product('MDCLXVI',repeat=n))

Try it online!

I'm pretty new, help me golf this! This checks for actual roman numerals, the regex needs to be adjusted to account for the odd cases such as IVI

-9 bytes thanks to @Dead Possum!

-6 bytes thanks to @ovs


Jelly, 21 bytes, cracks Jonathan Allan's answer
“¡ẉḟUHġ[4A»ŒVw⁾SuNXṛ⁸

Try it online!
Takes the return value of time.ctime(), finds Su in it, and negates the value. On a Sunday, this passes -1 to X (random number function), causing an error. Otherwise it passes 0 to X, not erroring. then final return value is forced to be the empty string ⁸, so it will print nothing.


JavaScript (ES7), 172 bytes
x=>[for(i of"V(SO?)?0V(O?S)?0(SVO?|V)0(O?VS|V)0(SO?)?V0(O?S)?V".split(0))if((y=x.match(RegExp(i,"g"))).join``==x)i.match(/\w/g).slice(0,3).join``+":"+y.join`.`+"."].join`
`

Could probably be golfed further. Suggestions welcome!


Ruby, 100% (74 characters)

Input on STDIN, output on STDOUT.

Vj=s=gets;puts(s.tr'!-~','P-~!-O');Vj;'lDl86EDjAFEDWD]ECVP\OV[V!\OP\~VXj;'

The second line is the first line ROT-47'd. Therefore, when ROT-47ing the whole program, it becomes:

';lDl86EDjAFEDWD]ECVP\OV[V!\OP\~VXj';jV=s=gets;puts(s.tr'!-~','P-~!-O');jV

My strategy here is based upon the fact that:

V is ' when ROT-47'd
j is ; when ROT-47'd
Therefore, Vj=...Vj; turns into ';l...';, which is essentially a no-op

Now you can create any arbitrary code that does anything normally and no-ops when ROT-47'd. This is because Vj=...Vj; can support running any code as you could do Vj=0;{INSERT ANY CODE};Vj;, and that will become '...'; when ROT-47'd. You just have to be careful not to use V in that code, since that will break it.

Similar logic can be used in reverse to produce the second half (jV instead of Vj)


Determine if a move exists in a Bejeweled/match 3 game

Original Solution: JavaScript - 261 255 228 227 179 153 Characters
/(\d)(\1(\d|.{6}|.{9})|(\d|.{6}|.{9})\1|.{7}\1(.|.{9})|(.|.{9})\1.{7}|(.{7,9}|.{17})\1.{8}|.{8}\1(.{7,9}|.{17}))\1/.test(s.replace(/\n/g,'A'))?'yes':'no'

Assuming that the string to test is in the variable s (to make it a function f then add f=s=> to the beginning of the code or, otherwise, to take input from a prompt then replace s with prompt()).
Outputs is to the console.
3rd Solution: JavaScript (ECMAScript 6) - 178 Characters
p=x=>parseInt(x,36);for(t="2313ab1b8a2a78188h9haj9j8iaiir9r",i=v=0;s[i];i++)for(j=0;t[j];v|=s[i]==s[i+a]&s[i]==s[i+b]&i%9<8&(b>3|(i+b-a)%9<8))a=p(t[j++]),b=p(t[j++]);v?'yes':'no'

I took the 2nd solution, below, (which uses regular expressions to check for characters in certain configurations) and reworked it to just check the string for identical characters in the same configurations without using regular expressions.
The Base-36 string "2313ab1b8a2a78188h9haj9j8iaiir9r" gives pairs of offsets to check - i.e. the pair 23 results in the check if ith character is identical to the (i+2)th character and the (i+3)th character (the equivalent of the regular expression (.).\1\1 - with some additional checks to ensure that the non-identical character is not a newline).
2nd Solution: JavaScript (ECMAScript 6) - 204 Characters
p=x=>parseInt(x,18);g=a=>a?a>1?"(.|\\n){"+a+"}":".":"";f=(x,a,b)=>RegExp("(.)"+g(a)+"\\1"+g(b)+"\\1").test(x);for(t="10907160789879h8",i=v=0;t[i];v|=f(s,x,y)||f(s,y,x))x=p(t[i++]),y=p(t[i++]);v?'yes':'no'

Builds multiple regular expressions (see below for more details) using pairs of values taken from the  Base-18 string 10907160789879h8 and takes the OR of all the tests. To reduce it further you can note that the regular expressions come in pairs where one is the "reverse" of the other (ignoring the Regular Expressions for 3-in-a-row horizontally and vertically as the OP states they will never be present - if you want to add those tests back in the append 0088 to the Base-18 string).
Explanation
Start with 16 regular expressions covering all the possible configurations of valid moves:
REs=[
    /(\d)\1\1/,                 // 3-in-a-row horizontally
    /(\d).\1\1/,                // 3-in-a-row horizontally after left-most shifts right
    /(\d)\1.\1/,                // 3-in-a-row horizontally after right-most shifts left
    /(\d)(?:.|\n){9}\1\1/,  // 3-in-a-row horizontally after left-most shifts down
    /(\d)(?:.|\n){7}\1.\1/, // 3-in-a-row horizontally after middle shifts down
    /(\d)(?:.|\n){6}\1\1/,  // 3-in-a-row horizontally after right-most shifts down
    /(\d)\1(?:.|\n){6}\1/,  // 3-in-a-row horizontally after left-most shifts up
    /(\d).\1(?:.|\n){7}\1/, // 3-in-a-row horizontally after middle shifts up
    /(\d)\1(?:.|\n){9}\1/,  // 3-in-a-row horizontally after right-most shifts up
    /(\d)(?:.|\n){7,9}\1(?:.|\n){8}\1/, // 3-in-a-row vertically (with optional top shifting left or right)
    /(\d)(?:.|\n){7}\1(?:.|\n){9}\1/,   // 3-in-a-row vertically after middle shifts right
    /(\d)(?:.|\n){9}\1(?:.|\n){7}\1/,   // 3-in-a-row vertically after middle shifts left
    /(\d)(?:.|\n){8}\1(?:.|\n){7}\1/,   // 3-in-a-row vertically after bottom shifts right
    /(\d)(?:.|\n){8}\1(?:.|\n){9}\1/,   // 3-in-a-row vertically after bottom shifts left
    /(\d)(?:.|\n){17}\1(?:.|\n){8}\1/,  // 3-in-a-row vertically after top shifts down
    /(\d)(?:.|\n){8}\1(?:.|\n){17}\1/,  // 3-in-a-row vertically after bottom shifts up
];

(Note: the regexs for 3-in-a-row horizontally (0th) and vertically (part of the 9th) are irrelevant as the OP states that inputs matching these will never be present.)
Testing each of those against the input will determine if a valid move of that configuration can be found.
However, the regular expressions can be combined to give these 6:
/(\d)(?:.|(?:.|\n){9}|(?:.|\n){6})?\1\1/            // Tests 0,1,3,5
/(\d)\1(?:.|(?:.|\n){9}|(?:.|\n){6})?\1/            // Tests 0,2,6,8
/(\d)(?:.|\n){7}\1(?:.|(?:.|\n){9})\1/              // Tests 4,10
/(\d)(?:.|(?:.|\n){9})\1(?:.|\n){7}\1/              // Tests 7,11
/(\d)(?:(?:.|\n){7,9}|(?:.|\n){17})\1(?:.|\n){8}\1/ // Tests 9,14
/(\d)(?:.|\n){8}\1(?:(?:.|\n){7,9}|(?:.|\n){17})\1/ // Tests 9a,12,13,15

These can then be combined into a single regular expression:
/(\d)(?:.|(?:.|\n){9}|(?:.|\n){6})?\1\1|(\d)\2(?:.|(?:.|\n){9}|(?:.|\n){6})?\2|(\d)(?:.|\n){7}\3(?:.|(?:.|\n){9})\3|(\d)(?:.|(?:.|\n){9})\4(?:.|\n){7}\4|(\d)(?:(?:.|\n){7,9}|(?:.|\n){17})\5(?:.|\n){8}\5|(\d)(?:.|\n){8}\6(?:(?:.|\n){7,9}|(?:.|\n){17})\6/

Which just needs to be tested against the input.
Test Cases
Some test cases which other people might find useful (doesn't comply with the input format of using only digits 1-7 but that's easily corrected and is only an 8x4 grid - since that is the minimum required for a test of all the valid inputs).
In the format of a map from input string to which of the 16 regular expressions above it matches.
Tests={
    "12345678\n34567812\n56781234\n78123456": -1, // No Match
    "12345678\n34969912\n56781234\n78123456": 1,    // 3-in-a-row horizontally after left-most shifts right
    "12345678\n34567812\n59989234\n78123456": 2,    // 3-in-a-row horizontally after right-most shifts left
    "12345978\n34567899\n56781234\n78123456": 3,    // 3-in-a-row horizontally after left-most shifts down
    "12345978\n34569892\n56781234\n78123456": 4,    // 3-in-a-row horizontally after middle shifts down
    "12345678\n34967812\n99781234\n78123456": 5,    // 3-in-a-row horizontally after right-most shifts down
    "12399678\n34967812\n56781234\n78123456": 6,    // 3-in-a-row horizontally after left-most shifts up
    "12345678\n34597912\n56789234\n78123456": 7,    // 3-in-a-row horizontally after middle shifts up
    "12345998\n34567819\n56781234\n78123456": 8,    // 3-in-a-row horizontally after right-most shifts up
    "12945678\n34597812\n56791234\n78123456": 9,    // 3-in-a-row vertically after top shifts right
    "12349678\n34597812\n56791234\n78123456": 9,    // 3-in-a-row vertically after top shifts left
    "12345978\n34569812\n56781934\n78123456": 10,   // 3-in-a-row vertically after middle shifts right
    "92345678\n39567812\n96781234\n78123456": 11,   // 3-in-a-row vertically after middle shifts left
    "12945678\n34967812\n59781234\n78123456": 12,   // 3-in-a-row vertically after bottom shifts right
    "12349678\n34569812\n56781934\n78123456": 13,   // 3-in-a-row vertically after bottom shifts left
    "12395678\n34567812\n56791234\n78193456": 14,   // 3-in-a-row vertically after top shifts down
    "12345698\n34567892\n56781234\n78123496": 15,   // 3-in-a-row vertically after bottom shifts up
    "12345678\n34567899\n96781234\n78123456": -1,   // No match - Matches (.)\1.\1 but not 3 in a row
    "12345679\n99567812\n56781234\n78123456": -1,   // No match - Matches (.).\1\1 but not 3 in a row
};

Edit 1
Replace \ds with . - saves 6 characters.
Edit 2
Replace (?:.|\n) with [\s\S] and removed extra non-capturing groups and updated back references (as suggested by m-buettner) and added in yes/no output.
Edit 3

Added ECMAScript 6 solution to build the individual Regular Expressions from a Base-18 string.
Removed the tests for 3-in-a-row horizontally (as suggested by m-buettner).

Edit 4
Added another (shorter) solution and two more non-matching tests cases.
Edit 5

Shortened original solution by replacing newlines with a non-numeric character (as suggested by VadimR).

Edit 6

Shortened original solution by combining bits of the regular expression (as suggested by VadimR).


Python 2, 0 (350 344 314 309 301 298 291 bytes)

def f(tt):11
def f(tt):
 tt=tt.split('\n')
 r =0#.split('\n')
#r  0#
#for
 for  ii,ll in enumerate(tt):
  for jj,cc in enumerate(ll):
##for+=1-(
    r+=1-(cc in ll[(jj or 2)-1:jj+2:2]    +''.join(ll[jj:
 jj+1]for ll in tt[(ii or 2)-1:ii+2:2]))##+''.join(ll[jj:
#  +1]for
#print r
 print r

Try it online!

-7 bytes, thanks to Jo King


Putting my two cents in on array programming languages, J and APL in particular.

K/Kona, Q, and Nial fall in this category too, but they generally have the same benefits and criticisms. Use discretion. I will use J examples below, mostly because these are ASCII and thus easy to type--remember than APL characters count as single bytes, so don't let that be your problem with the language as choice for golfing.

Math problems
Solving number puzzles
Performing numerical methods
Tricky 2D array problems

These two are very good math and data-manipulation languages, because they toss arrays around a high level, and a lot of looping is done implicitly, by saying, e.g. add ten to each of 3, 4, and 5 (10 + 3 4 5) or sum each row of an array (+/"1 arr--the looping is in the "1).

Problem dealing with prime numbers

With prime number problems in particular, J has fast and short builtin primitives, as do some dialects of APL. (Edit: I'm thinking of Nars2000, which is part dialect and part completely different implementation. APL has no builtin for primes.) N-th prime (p:), no. of primes up to (_1&p:), factoring (q:), GCD and LCM (+. and *.), and so on, there's a lot there. However, in practice, the question will often specify that you have to cook your own prime implementations, so these don't see too much use. There are still neat and fancy ways of getting the prime stuff you need, it just becomes a little less cut-and-paste.

String processing
Array processing

Array and string processing is a bit of a mixed bag: if it's something that APL/J is good at or has a primitive or common idiom for, it's nearly trivial; if it's something that's very sequential and not very parallelizable, you're going to have a bad time. Anything in between is up in the air, though usually they will respond favourably.

Problems that require I/O solution, either console or file
Problems that requires you to write your solution as a function definition

IO is weird. APL has a single-character input expression, but with J you have to spend at least 8 to read in a number: ".1!:1]1. Output is a little less verbose, but you're still looking at 6 or 7 characters wasted, in practice. J in particular really likes it a lot if you can take in the input as arguments to a function, instead of having to muck around with IO itself.

In practice, with J and APL, usually the solution is written as a function that you invoke at the console. With APL, you can basically just put in variable names for your arguments and wrap the expression you were working with in curly braces and call it a day.

But with J, there's a bit of an overhead for defining functions explicitly--3 :'...', and you have to escape any strings inside--so what is usually done is something called tacit programming: you program at the function level, combining primitives in a manner not unlike that of Haskell. This can be both a blessing and a curse, because you don't have to spend as many characters referring to your arguments, but it's easy to drown in parentheses and end up losing tens of characters trying to hack your otherwise short and clever solution into something that works.

Problems that require parsing
Computational geometry

I don't have experience with golfing these particular problems, but I will say this: in the end, array programming languages are very good at piping and transforming lots of data in the same way. If you can turn the problem into an exercise in number shuffling, you can make it an APL/J problem, no sweat.

That said, not everything is an APL/J problem. Unlike Golfscript, APL and J just happened to be good for golfing, alongside their other benefits ;)


Finding Collatz-like rules with many loops

GolfScript, arbitrary score

~:l 2:m.@?):d\1 l,{m\)?d-*}/abs.{1 m 3$)?-*m@)?d-m(*/}+l,/]' '*

This takes an integer on stdin and outputs a sequence with that many loops, in the input format of the Python tester. The online demo runs it for l = 4 and produces output 17 2 1755 117 405 1365 26325; this fork of the tester verifies it.

Explanation

In order to keep it simple, I restricted the analysis to primitive loops: ones with only one division.

(x -> mx + i)^n = (x -> m^n x + (m^n - 1)/(m-1) i)

so this means that I'm looking for solutions to

m^n x + (m^n - 1)/(m - 1)i = dx

or

(m^n - d) x + (m^n - 1)/(m - 1)i = 0

When n > 0, m > 1, m^n - d != 0 this has exactly one solution for x. m - 1 > 0 and m^n - 1 > 0, so in order for the solution to be positive we require m^n - d < 0, and in order for the solution to be an integer we require d - m^n to be a factor of (m^n - 1)/(m - 1)i.

The rest may already be obvious. We pick the desired score, l. We're going to find primitive loops of length 1 to l, so we want d - m^l > 0. To get a smallish output we pick m = 2, d = 2^l + 1. Then to get an easy guarantee of the divisibility constraints we pick i to be the absolute value of (m - d)(m^2 - d)...(m^l - d).


Random ASCII Art of the Day #5: Diamond Tilings

CJam, 105 bytes

ri:A" __"e*A,2f*:B,[W1]{J+B:):B,{N1$S*"\/"J%A2*4$-:D*
0{;B{_1&!2mr+J*m1e>D(2*e<}%__:)&}g:B{'_t}/+@J+}*}fJ;

Newline added to avoid scrolling. Try it online

Explanation:

This solution starts each line as a zigzag, then places N underscores on it, based on their position on the previous line and a couple of rules. I got this from a series of observations while looking at the output as a plain 2D matrix of characters:

each line has exactly N underscores
the underscores can be replaced with / or \ to make a perfectly repeating zigzag pattern (/\ in the top half, \/ in the bottom half)
underscores can not touch the sides, and can't be adjacent to another underscore
when going to the next line, the position of each underscore changes by -1, 0 or 1
more than that, /_/ can only change by -1 or 0, and \_\ can only change by 0 or 1
for the initial underscore positions we can either use a "_ " pattern or a " _" pattern, both are fine
the above rules are sufficient to obtain all the tilings

So I decided to implement it by keeping the previous underscore positions, modifying them with a random factor (2 choices for each underscore) and repeating until the rules are satisfied. In the process of optimizing, I switched to underscore positions relative to the left side of the hexagon (not including spaces).

ri:A" __"e*       read the input (A) and generate the top line
A,2f*:B           make an array [0 2 4 ... 2A-2] and store in B
                  these are the initial positions for the underscores
,                 B's length = A, used as the initial number of leading spaces
                  let's call it C
[W1]{…}fJ         for J in [-1 1] (top half, bottom half)
  J+              add J to C
  B:):B           increment the underscore positions (adjustment before each half)
  ,{…}*           repeat A times
    N1$S*         add a newline and C spaces
    "\/"J%        take "\/" and reverse it if J=-1 (zigzag pattern)
    A2*4$-:D*     calculate D=A*2-C and repeat the pattern
    0             dummy value (for the next loop)
    {…}g          do-while
      ;B          pop last value and push B
      {…}%        apply block to each item (say x)
        _1&!      duplicate x and calculate !(x&1) (for /_/ vs \_\)
        2mr+      randomly add 0 or 1
        J*m       multiply by J and subtract from x
        1e>       limit the minimum value to 1
        D(2*e<    and the maximum value to 2*(D-1)
      __:)&       check if the modified array has any adjacent values
    :B            store the new positions in B
    {'_t}/        place underscores over the zigzag pattern
    +@J+          bring C to the top and add J to it
;                 pop C

Old "3D" version, 189 bytes:

ri:A" __"e*aA4*S*aA2**+[0-2XXW1]:C;"/\_\\\/_/":D;A3m*{{C2/.f*:.+~
A(2*+:V;A+:U;2{UI+1$1$=4{_V+D4/I=@=t}/t}fI}:F~}/[0Y1WWW]:C;
"/_/\\\_\/":D;AaA*:B;A{A[_{_BI=e<)mr}fI]:B;{BQ={[PQR]F}fR}fQ}fPN*

Try it online


Tips for golfing with numpy, scipy, or pylab

Make use of Numpy's broadcasting

Broadcasting means replicating a multidimensional array along some of its singleton dimensions to match the size of another array. This happens automatically for Numpy arrays when arithmetic operators are applied to them.

For example, to generate a 10×10 multiplication table you can use

import numpy
t=numpy.arange(1,11)
print(t*t[:,None]) # Or replace t[:,None] by [*zip(t)]

Try it online!

Here t is created as the Numpy array [1, 2, ..., 10]. This has shape (10,), which is equivalent to (1,10). The other operand array, t[:,None], has size (10,1). Multiplying the two arrays implicitly replicates them, so they behave as if they both had shape (10,10). The result, which also has shape (10,10), contains the products for all pairs of entries in the original arrays.


CJam, 67 bytes

Definitely still room for improvement, but I'll post what I have so far.

Try it online

0r:T,,ri>{T,L(-,_m*{~:XT>L<T@LX+e>,{0t}/X>\#_W>\2$?{\1$_!+%}h;}/}fL


J, 88 86 bytes
Expects a matrix with 0 for ., 1 for A and 2 for T.
(2>1#.1=,);.3~&2 2*/@,&,1&=((1 e.[:*/"{2>[:+/"1|@-"2)i.@!@#A.]) ::0&($ #:i.@$#~&,])2&=

Try it online!
How it works
1&= (…) 2&=

Tents on the left side, trees on the right side.
(…)&($#:i.@$#~&,])

Convert both arguments to 2D coordinates.
(…) ::0

If the following function throws an error, return 0. This happens only in the single A case. :-(
i.@!@#A.]

List all permutations of the trees.
|@-"2

Get the difference between the tents from every permutation.
[:*/2>[:+/"1

Check that each difference's sum is 1.
1 e.

Does any permutation fulfill this?
(2>1#.1=,);.3~&2 2

Get all 2x2 matrices of the original, and check if there is at most one tent in there.
*/@,@,

Combine both results, flatten the lists, and check if there are only 1's.


Jelly, 62 bytes

TṀị
“¢<<ð¢‘×\×€0¦7,31,365F⁸:µç“ɲþḣ⁹ḢṡṾDU¤µQƝṁ⁼ẹ»Ḳ¤ṭÇK;⁸Ç>1¤¡”s

A full program printing the result.
(As a monadic link it returns a list of an integer followed by characters)

Try it online!

How?

TṀị - Link 1: list of integers, K; list, V  e.g. [86401,1440,24,1,0,0,0], ["second","minute","hour","day","week","month","year"]
T   - truthy indexes of K                        [1,2,3,4]
 Ṁ  - maximum                                    4
  ị - index into V                               "day"

“¢<<ð¢‘×\×€0¦7,31,365F⁸:µç“...»Ḳ¤ṭÇK;⁸Ç>1¤¡”s - Main link: integer, N  e.g. 3599
“¢<<ð¢‘                                       - list of code-page indices = [1,60,60,24,1]
        \                                     - cumulative reduce with:
       ×                                      -  multiplication = [1,60,3600,86400,86400]
             7,31,365                         - list of integers = [7,31,365]
            ¦                                 - sparse application...
           0                                  - ...to index: 0 (rightmost)
         ×€                                   - ...of: multiplication for €ach = [1,60,3600,86400,[604800,2678400,31536000]]
                     F                        - flatten = [1,60,3600,86400,604800,2678400,31536000]
                      ⁸                       - chain's left argument, N    3599
                       :                      - integer divide         [3599,59,0,0,0,0,0]
                        µ                     - start a new monadic chain, call that X
                                ¤             - nilad followed by links as a nilad:
                          “...»               -   compression of "second minute hour day week month year"
                               Ḳ              -   split at spaces = ["second","minute","hour","day","week","month","year"]
                         ç                    - call the last link (1) as a dyad - i.e. f(X,["second","minute","hour","day","week","month","year"])
                                              -                             "minute"
                                  Ç           - call the last link (1) as a monad - i.e. f(X,X)
                                              -                             59
                                 ṭ            - tack                        [59,['m','i','n','u','t','e']]
                                   K          - join with spaces            [59,' ','m','i','n','u','t','e']
                                           ”s - literal character '
                                          ¡   - repeat...
                                         ¤    - ...number of times: nilad followed by link(s) as a nilad:
                                     ⁸        -   chain's left argument, X  [3599,59,0,0,0,0,0]
                                      Ç       -   call the last link (1) as a monad - i.e. f(X,X)
                                              -                             59
                                       >1     -   greater than 1?           1
                                    ;         - concatenate                 [59,' ','m','i','n','u','t','e','s']
                                              - implicit print - smashes to print  "59 minutes"


J, 28 17 25 27

J doesn't really have functions, but here's a monadic verb that takes a vector of points from the complex plane:

4 8 4-:#/.~&(/:~&:|&,&(-/~))

Method is a mix of Michael Spencer (work solely on inter-vertex lengths; but he's currently failing my rhombus2) and Eelvex's (check the sets' sizes) works.  Reading right to left:

-/~ compute all point differences
, flatten
| extract magnitude
/:~ sort up
#/.~ nub and count
4 8 4 -: must have exactly 4 equidistant (at 0), 8 a bit bigger (length 1, sides), 4 bigger yet (length sqrt 2, diagonals)

Demonstration:

   NB. give the verb a name for easier use
   f =: 4 8 4-:#/.~&(/:~&:|&,&(-/~))

   NB. standard square
   f 0 0j1 1j1 1
1

   NB. non-axis-aligned square
   f 0 2j1 3j_1 1j_2
1

   NB. different order
   f 0 1j1 0j1 1
1

   NB. rectangle
   f 0 0j2 3j2 3
0

   NB. rhombus 1
   f 0 3j4 8j4 5
0

   NB. rhombus 2
   f 0 1ad_60 1ad0 1ad60
0

For memory's sake, my previous method (required ordered vertices, but could detect regular polygons of any order):

*./&(={.)&(%1&|.)&(-1&|.)

See history for explanation and demo.  The current method could probably be expanded to other polygons, that 4 8 4 does look a lot like a binomial distribution.


Center of Mass from a list of coordinates and their masses

MATL, 6 5 bytes

ys/Y*

Input format is a row vector with the masses, then a two-column matrix with the coordinates (in which spaces or commas are optional).

First example:

[2, 6, 2, 10]
[0,2; 3,4; 0,1; 1,1]

Second example:

[2, 4, 1]
[3,1; 0,0; 1,4]

Try it online!

Explanation

Let m denote the vector of masses (first input) and c the matrix of coordinates (second input).

y     % implicitly take two inputs. Duplicate the first.
      % (Stack contains, bottom to top: m, c, m)
s     % sum of m.
      % (Stack: m, c, sum-of-m)
/     % divide.
      % (Stack: m, c-divided-by-sum-of-m)
Y*    % matrix multiplication.
      % (Stack: final result)
      % implicitly display


Perl, 37 bytes

35 bytes of code + 2 bytes for -lp flags.

splice@F,1+<>%(@F||1),0,$_}{$_="@F"

Try it online!

The implementation is quite straight forward, splice inserts in array @F at index 1+<>%(@F||1) (note that @F||1 handles the case of the array being empty).

Just a few words about the (seemingly) unmatched braces }{ (because I had a comment about it, and I think it's quite weird for people who don't know Perl), and it's a quite common trick in Perl golfings:
-p flag surrounds the code with (roughly) while(<>){ CODE } continue { print }, (the continue is executed after each iteration). So with those unmatched }{, I change my code to while(<>) { CODE}{ } continue { print }. So it creates an empty block right after my code (but that's not a problem), and the continue is executed only once, after the while (ie. when the all the input has been read).


Pip, 26 12 bytes
T0{LbPaLcPx}

-14 bytes after taking ratio as two arguments.
Explanation:
T0           Till 0 (infinite loop)
  {Lb        Loop b(second argument) number of times
     Pa      Print a(first argument) with newline
       Lc    Loop c(third argument) number of times
         Px} Print x(empty string) with newline

Try it online!


bash (13)

sudo rm -rf /

The faster the hard drive the better the sound. Don't work with SSDs.
(Don't try this at home, sudo rm -rf / erases everything on your hard drive)


Mini-Flak, 6851113 cycles

The program (literally)

I know most people aren't likely expecting a Mini-Flak quine to be using unprintable characters and even multi-byte characters (making the encoding relevant). However, this quine does, and the unprintables, combined with the size of the quine (93919 characters encoded as 102646 bytes of UTF-8), make it fairly difficult to place the program into this post.

However, the program is very repetitive, and as such, compresses really well. So that the entire program is available literally from Stack Exchange, there's an xxd reversible hexdump of a gzip-compressed version of the full quine hidden behind the collapsible below:

00000000: 1f8b 0808 bea3 045c 0203 7175 696e 652e  .......\..quine.
00000010: 6d69 6e69 666c 616b 00ed d9db 6a13 4118  miniflak....j.A.
00000020: 0060 2f8b f808 0d64 a1c1 1dc8 4202 c973  .`/....d....B..s
00000030: 4829 4524 0409 22e2 5529 a194 1242 1129  H)E$..".U)...B.)
00000040: d2d7 ca93 f9cf 4c4c d45b 9536 e6db 6967  ......LL.[.6..ig
00000050: 770e 3bc9 ffed eca9 edb7 b1a4 9ad2 6a1d  w.;...........j.
00000060: bfab 75db c6c6 6c5f 3d4f a5a6 8da6 dcd8  ..u...l_=O......
00000070: 465b d4a5 5a28 4bd9 719d 727b aa79 f9c9  F[..Z(K.q.r{.y..
00000080: 43b6 b9d7 8b17 cd45 7f79 d3f4 fb65 7519  C......E.y...eu.
00000090: 59ac 9a65 bfdf 8f86 e6b2 69a2 bc5c 4675  Y..e......i..\Fu
000000a0: d4e4 bcd9 5637 17b9 7099 9b73 7dd3 fcb2  ....V7..p..s}...
000000b0: 4773 b9bc e9bd b9ba 3eed 9df7 aeaf 229d  Gs......>.....".
000000c0: e6ed 5eae 3aef 9d46 21b2 5e4d bd28 942e  ..^.:..F!.^M.(..
000000d0: 6917 d71f a6bf 348c 819f 6260 dfd9 77fe  i.....4...b`..w.
000000e0: df86 3e84 74e4 e19b b70e 9af0 111c fa0d  ..>.t...........
000000f0: d29c 75ab 21e3 71d7 77f6 9d8f f902 6db2  ..u.!.q.w.....m.
00000100: b8e1 0adf e9e0 9009 1f81 f011 18d8 1b33  ...............3
00000110: 72af 762e aac2 4760 6003 1bd8 698c c043  r.v...G``...i..C
00000120: 8879 6bde 9245 207c 04ae 5ce6 2d02 e1bb  .yk..E |..\.-...
00000130: 7291 4540 57f8 fe0d 6546 f89b a70b 8da9  r.E@W...eF......
00000140: f5e7 03ff 8b8f 3ad6 a367 d60b f980 679d  ......:..g....g.
00000150: d3d6 1c16 f2ff a767 e608 57c8 c27d c697  .......g..W..}..
00000160: 4207 c140 9e47 9d57 2e50 6e8e c215 b270  B..@.G.W.Pn....p
00000170: bdf6 9926 9e47 9d05 ce02 0ff0 5ea7 109a  ...&.G......^...
00000180: 8ba6 b5db 880b 970b 9749 2864 47d8 1b92  .........I(dG...
00000190: 39e7 9aec 8f0e 9e93 117a 6773 b710 ae53  9........zgs...S
000001a0: cd01 17ee b30e d9c1 15e6 6186 7a5c dc26  ..........a.z\.&
000001b0: 9750 1d51 610a d594 10ea f3be 4b7a 2c37  .P.Qa.......Kz,7
000001c0: 2f85 7a14 8fc4 a696 304d 4bdf c143 8db3  /.z.....0MK..C..
000001d0: d785 8a96 3085 2acc 274a a358 c635 8d37  ....0.*.'J.X.5.7
000001e0: 5f37 0f25 8ff5 6854 4a1f f6ad 1fc7 dbba  _7.%..hTJ.......
000001f0: 51ed 517b 8da2 4b34 8d77 e5b2 ec46 7a18  Q.Q{..K4.w...Fz.
00000200: ffe8 3ade 6fed b2f2 99a3 bae3 c949 9ab5  ..:.o........I..
00000210: ab75 d897 d53c b258 a555 1b07 63d6 a679  .u...<.X.U..c..y
00000220: 4a51 5ead a23a 6a72 9eb6 d569 960b f3dc  JQ^..:jr...i....
00000230: 9ceb 53fa 658f 345f ad07 6f6f efce 06ef  ..S.e.4_..oo....
00000240: 0677 b791 cef2 f620 57bd 1b9c 4521 b241  .w..... W...E!.A
00000250: 4d83 2894 2eaf a140 8102 050a 1428 50a0  M.(....@.....(P.
00000260: 4081 0205 0a14 2850 a040 8102 050a 1428  @.....(P.@.....(
00000270: 50a0 4081 0205 0a14 2850 a040 8102 050a  P.@.....(P.@....
00000280: 1428 50a0 4081 0205 0a14 2850 a040 8102  .(P.@.....(P.@..
00000290: 050a 1428 50a0 4081 0205 0a14 2850 a040  ...(P.@.....(P.@
000002a0: 8102 050a 1428 50a0 4081 0205 0a14 2850  .....(P.@.....(P
000002b0: a040 8102 050a 1428 50a0 4081 0205 0a14  .@.....(P.@.....
000002c0: 2850 a040 8102 050a 1428 50a0 4081 0205  (P.@.....(P.@...
000002d0: 0a14 2850 a040 8102 050a 1428 50a0 4081  ..(P.@.....(P.@.
000002e0: 0205 0a14 2850 a040 8102 050a 1428 50a0  ....(P.@.....(P.
000002f0: 4081 0205 0a14 2850 a040 8102 050a 1428  @.....(P.@.....(
00000300: 50a0 4081 0205 0a14 2850 a040 8102 050a  P.@.....(P.@....
00000310: 1428 50a0 4081 0205 0a14 2850 a040 8102  .(P.@.....(P.@..
00000320: 050a 1428 50a0 4081 0205 0a14 2850 a040  ...(P.@.....(P.@
00000330: 8102 050a 1428 50a0 4081 0205 0a14 2850  .....(P.@.....(P
00000340: a040 8102 050a 1428 50a0 4081 0205 0a14  .@.....(P.@.....
00000350: 2850 a040 8102 050a 1428 50a0 4081 0205  (P.@.....(P.@...
00000360: 0a14 2850 a040 8102 050a 1428 50a0 4081  ..(P.@.....(P.@.
00000370: 0205 0a14 2850 a01c 14ca 7012 cbb4 a6e9  ....(P....p.....
00000380: e6db e6b1 e4b1 9e4c 4ae9 d3be f5f3 745b  .......LJ.....t[
00000390: 37a9 3d6a af49 7489 a6e9 ae5c 96dd 488f  7.=j.It....\..H.
000003a0: d31f 5da7 fbad 5d56 3e73 5277 7cf5 aa7b  ..]...]V>sRw|..{
000003b0: 3fbc df7c e986 c3ba 5ee4 3c6f 74f7 c3e1  ?..|....^.<ot...
000003c0: 301a bb45 d795 9afb fbdc 1495 65d5 6d9b  0..E........e.m.
000003d0: baf7 a5b4 a87d 4a5b d7fd b667 b788 ec27  .....}J[...g...'
000003e0: c5d8 28bc b96a 9eda 7a50 524d 290a a5cb  ..(..j..zPRM)...
000003f0: cbef 38cb c3ad f690 0100                 ..8.......

(Yes, it's so repetitive that you can even see the repeats after it's been compressed).

The question says "I would also highly recommend not running your program in TIO. Not only is TIO slower than the desktop interpreter, but it will also timeout in about a minute. It would be extremely impressive if someone managed to score low enough to run their program before TIO timed out." I can do that! It takes about 20 seconds to run on TIO, using the Ruby interpreter: Try it online!

The program (readably)

Now I've given a version of the program that computers can read, let's try a version that humans can read. I've converted the bytes that make up the quine into codepage 437 (if they have the high bit set) or Unicode control pictures (if they're ASCII control codes), added whitespace (any pre-existing whitespace was converted to control pictures), run-length-encoded using the syntax «string×length», and some data-heavy bits elided:

␠
(((()()()()){}))
{{}
    (({})[(()()()())])
    (({})(
        {{}{}((()[()]))}{}
        (((((((({})){}){}{})){}{}){}){}())
        {
            ({}(
                (␀␀!S␠su! … many more comment characters … oq␝qoqoq)
                («()×35» («()×44» («()×44» («()×44» («()×44» («()×45»
                … much more data encoded the same way …
                («()×117»(«()×115»(«()×117»
                «000010101011┬â┬ … many more comment characters … ┬â0┬â┬à00␈␈
                )[({})(
                    ([({})]({}{}))
                    {
                        ((()[()]))
                    }{}
                    {
                        {
                            ({}(((({}())[()])))[{}()])
                        }{}
                        (({}))
                        ((()[()]))
                    }{}
                )]{}
                %Wwy$%Y%ywywy$wy$%%%WwyY%$$wy%$$%$%$%$%%wy%ywywy'×almost 241»
                ,444454545455┬ç┬ … many more comment characters … -a--┬ü␡┬ü-a␡┬ü
            )[{}()])
        }{}
        {}({}())
    )[{}])
    (({})(()()()()){})
}{}{}␊

(The "almost 241" is because the 241st copy is missing the trailing ', but is otherwise identical to the other 240.)

Explanation

About the comments

The first thing to explain is, what's up with the unprintable characters and other junk that isn't Mini-Flak commands? You may think that adding comments to the quine just makes things harder, but this is a speed competition (not a size competition), meaning that comments don't hurt the speed of the program. Meanwhile, Brain-Flak, and thus Mini-Flak, just dump the contents of the stack to standard output; if you had to ensure that the stack contained only the characters that made up the commands of your program, you'd have to spend cycles cleaning the stack. As it is, Brain-Flak ignores most characters, so as long as we ensure that junk stack elements aren't valid Brain-Flak commands (making this a Brain-Flak/Mini-Flak polyglot), and aren't negative or outside the Unicode range, we can just leave them on the stack, allow them to be output, and put the same character in our program at the same place to retain the quine property.

There's one particularly important way we can take advantage of this. The quine works by using a long data string, and basically all the output from the quine is produced by formatting the data string in various ways. There's only one data string, despite the fact that the program has multiple pieces; so we need to be able to use the same data string to print different parts of the program. The "junk data doesn't matter" trick lets us do this in a very simple way; we store the characters that make up the program in the data string by adding or subtracting a value to or from their ASCII code. Specifically, the characters making up the start of the program are stored as their ASCII code + 4, the characters making up the section that's repeated almost 241 times as their ASCII code − 4, and the characters making up the end of the program are stored as their ASCII code − 8. We can then print any of these three parts of the program via printing every character of the data string with an offset; if, for example, we print it with 4 added to every character code, we get one repeat of the repeated section, with some comments before and after. (Those comments are simply the other sections of the program, with character codes shifted so that they don't form any valid Brain-Flak commands, because the wrong offset was added. We have to dodge Brain-Flak commands, not just Mini-Flak commands, to avoid violating the restricted-source part of the question; the choice of offsets was designed to ensure this.)

Because of this comment trick, we actually only need to be able to output the data string formatted in two different ways: a) encoded the same way as in the source, b) as character codes with a specified offset added to every code. That's a huge simplification that makes the added length totally worth it.

Program structure

This program consists of four parts: the intro, the data string, the data string formatter, and the outro. The intro and outro are basically responsible for running the data string and its formatter in a loop, specifying the appropriate format each time (i.e. whether to encode or offset, and what offset to use). The data string is just data, and is the only part of the quine for which the characters that make it up are not specified literally in the data string (doing that would obviously be impossible, as it would have to be longer than itself); it's thus written in a way that's particularly easy to regenerate from itself. The data string formatter is made of 241 almost identical parts, each of which formats a specific datum out of the 241 in the data string.

Each part of the program can be produced via the data string and its formatter as follows:

To produce the outro, format the data string with offset +8
To produce the data string formatter, format the data string with offset +4, 241 times
To produce the data string, format the data string via encoding it into the source format
To produce the intro, format the data string with offset -4

So all we have to do is to look at how these parts of the program work.

The data string

(«()×35» («()×44» («()×44» («()×44» («()×44» («()×45» …

We need a simple encoding for the data string as we have to be able to reverse the encoding in Mini-Flak code. You can't get much simpler than this!

The key idea behind this quine (apart from the comment trick) is to note that there's basically only one place we can store large amounts of data: the "sums of command return values" within the various nesting levels of the program source. (This is commonly known as the third stack, although Mini-Flak doesn't have a second stack, so "working stack" is likely a better name in the Mini-Flak context.) The other possibilities for storing data would be the main/first stack (which doesn't work because that's where our output has to go, and we can't move the output past the storage in a remotely efficient way), and encoded into a bignum in a single stack element (which is unsuitable for this problem because it takes exponential time to extract data from it); when you eliminate those, the working stack is the only remaining location.

In order to "store" data on this stack, we use unbalanced commands (in this case, the first half of a (…) command), which will be balanced within the data string formatter later on. Each time we close one of these commands within the formatter, it'll push the sum of a datum taken from the data string, and the return values of all the commands at that nesting level within the formatter; we can ensure that the latter add to zero, so the formatter simply sees single values taken from the data string.

The format is very simple: (, followed by n copies of (), where n is the number we want to store. (Note that this means we can only store non-negative numbers, and the last element of the data string needs to be positive.)

One slightly unintuitive point about the data string is which order it's in. The "start" of the data string is the end nearer the start of the program, i.e. the outermost nesting level; this part gets formatted last (as the formatter runs from innermost to outermost nesting levels). However, despite being formatted last, it gets printed first, because values pushed onto the stack first are printed last by the Mini-Flak interpreter. The same principle applies to the program as a whole; we need to format the outro first, then the data string formatter, then the data string, then the intro, i.e. the reverse of the order in which they are stored in the program.

The data string formatter

)[({})(
    ([({})]({}{}))
    {
        ((()[()]))
    }{}
    {
        {
            ({}(((({}())[()])))[{}()])
        }{}
        (({}))
        ((()[()]))
    }{}
)]{}

The data string formatter is made out of 241 sections which each have identical code (one section has a marginally different comment), each of which formats one specific character of the data string. (We couldn't use a loop here: we need an unbalanced ) to read the data string via matching its unbalanced (, and we can't put one of those inside a {…} loop, the only form of loop that exists. So instead, we "unroll" the formatter, and simply get the intro/outro to output the data string with the formatter's offset 241 times.)

)[({})( … )]{}

The outermost part of a formatter element reads one element of the data string; the simplicity of the data string's encoding leads to a little complexity in reading it. We start by closing the unmatched (…) in the data string, then negate ([…]) two values: the datum we just read from the data string (({})) and the return value of the rest of the program. We copy the return value of the rest of the formatter element with (…) and add the copy to the negated version with {}. The end result is that the return value of the data string element and formatter element together is the datum minus the datum minus the return value plus the return value, or 0; this is necessary to make the next data string element out produce the correct value.

([({})]({}{}))

The formatter uses the top stack element to know which mode it's in (0 = format in data string formatting, any other value = the offset to output with). However, just having read the data string, the datum is on top of the format on the stack, and we want them the other way round. This code is a shorter variant of the Brain-Flak swap code, taking a above b to b above a + b; not only is it shorter, it's also (in this specific case) more useful, because the side effect of adding b to a is not problematic when b is 0, and when b is not 0, it does the offset calculation for us.

{
    ((()[()]))
}{}
{
    …
    ((()[()]))
}{}

Brain-Flak only has one control flow structure, so if we want anything other than a while loop, it'll take a bit of work. This is a "negate" structure; if there's a 0 on top of the stack, it removes it, otherwise it places a 0 on top of the stack. (It works pretty simply: as long as there isn't a 0 on top of the stack, push 1 − 1 to the stack twice; when you're done, pop the top stack element.)

It's possible to place code inside a negate structure, as seen here. The code will only run if the top of the stack was nonzero; so if we have two negate structures, assuming the top two stack elements aren't both zero, they'll cancel each other out, but any code inside the first structure will run only if the top stack element was nonzero, and the code inside the second structure will run only if the top stack element was zero. In other words, this is the equivalent of an if-then-else statement.

In the "then" clause, which runs if the format is nonzero, we actually have nothing to do; what we want is to push the data+offset to the main stack (so that it can be output at the end of the program), but it's there already. So we only have to deal with the case of encoding the data string element in source form.

{
    ({}(((({}())[()])))[{}()])
}{}
(({}))

Here's how we do that. The {({}( … )[{}()])}{} structure should be familiar as a loop with a specific number of iterations (which works by moving the loop counter to the working stack and holding it there; it'll be safe from any other code, because access to the working stack is tied to the nesting level of the program). The body of the loop is ((({}())[()])), which makes three copies of the top stack element and adds 1 to the lowest. In other words, it transforms a 40 on top of the stack into 40 above 40 above 41, or viewed as ASCII, ( into ((); running this repeatedly will make ( into (() into (()() into (()()() and so on, and thus is a simple way to generate our data string (assuming that there's a ( on top of the stack already).

Once we're done with the loop, (({})) duplicates the top of the stack (so that it now starts ((()… rather than (()…. The leading ( will be used by the next copy of the data string formatter to format the next character (it'll expand it into (()(()… then (()()(()…, and so on, so this generates the separating ( in the data string).

%Wwy$%Y%ywywy$wy$%%%WwyY%$$wy%$$%$%$%$%%wy%ywywy'

There's one last bit of interest in the data string formatter. OK, so mostly this is just the outro shifted 4 codepoints downwards; however, that apostrophe at the end may look out of place. ' (codepoint 39) would shift into + (codepoint 43), which isn't a Brain-Flak command, so you may have guessed that it's there for some other purpose.

The reason this is here is because the data string formatter expects there to be a ( on the stack already (it doesn't contain a literal 40 anywhere). The ' is actually at the start of the block that's repeated to make up the data string formatter, not the end, so after the characters of the data string formatter have been pushed onto the stack (and the code is about to move onto printing the data string itself), the outro adjusts the 39 on top of the stack into a 40, ready for the formatter (the running formatter itself this time, not its representation in the source) to make use of it. That's why we have "almost 241" copies of the formatter; the first copy is missing its first character. And that character, the apostrophe, is one of only three characters in the data string that don't correspond to Mini-Flak code somewhere in the program; it's there purely as a method of providing a constant.

The intro and outro

(((()()()()){}))
{{}
    (({})[(()()()())])
    (({})(
        {{}{}((()[()]))}{}
        (((((((({})){}){}{})){}{}){}){}())
        {
            ({}(
                (␀␀!S␠su! … many more comment characters … oq␝qoqoq)
                …
            )[{}()])
        }{}
        {}({}())
    )[{}])
    (({})(()()()()){})
}{}{}␊

The intro and outro are conceptually the same part of the program; the only reason we draw a distinction is that the outro needs to be output before the data string and its formatter are (so that it prints after them), whereas the intro needs to be output after them (printing before them).

(((()()()()){}))

We start by placing two copies of 8 on the stack. This is the offset for the first iteration. The second copy is because the main loop expects there to be a junk element on top of the stack above the offset, left behind from the test that decides whether to exist the main loop, and so we need to put a junk element there so that it doesn't throw away the element we actually want; a copy is the tersest (thus fastest to output) way to do that.

There are other representations of the number 8 that are no longer than this one. However, when going for fastest code, this is definitely the best option. For one thing, using ()()()() is faster than, say, (()()){}, because despite both being 8 characters long, the former is a cycle faster, because (…) is counted as 2 cycles, but () only as one. Saving one cycle is negligible compared to a much bigger consideration for a quine, though: ( and ) have much lower codepoints than { and }, so generating the data fragment for them will be much faster (and the data fragment will take up less space in the code, too).

{{} … }{}{}

The main loop. This doesn't count iterations (it's a while loop, not a for loop, and uses a test to break out). Once it exits, we discard the top two stack elements; the top element is a harmless 0, but the element below will be the "format to use on the next iteration", which (being a negative offset) is a negative number, and if there are any negative numbers on the stack when the Mini-Flak program exits, the interpreter crashes trying to output them.

Because this loop uses an explicit test to break out, the result of that test will be left on the stack, so we discard it as the first thing we do (its value isn't useful).

(({})[(()()()())])

This code pushes 4 and f − 4 above a stack element f, whilst leaving that element in place. We're calculating the format for the next iteration in advance (while we have the constant 4 handy), and simultaneously getting the stack into the correct order for the next few parts of the program: we'll be using f as the format for this iteration, and the 4 is needed before that.

(({})( … )[{}])

This saves a copy of f − 4 on the working stack, so that we can use it for the next iteration. (The value of f will still be present at that point, but it'll be in an awkward place on the stack, and even if we could manoeuvre it to the correct place, we'd have to spend cycles subtracting 4 from it, and cycles printing the code to do that subtraction. Far easier simply to store it now.)

{{}{}((()[()]))}{}

A test to see if the offset is 4 (i.e. f − 4 is 0). If it is, we're printing the data string formatter, so we need to run the data string and its formatter 241 times rather than just once at this offset. The code is fairly simple: if f − 4 is nonzero, replace the f − 4 and the 4 itself with a pair of zeros; then in either case, pop the top stack element. We now have a number above f on the stack, either 4 (if we want to print this iteration 241 times) or 0 (if we want to print it only once).

(
    ((((((({})){}){}{})){}{}){}){}
    ()
)

This is an interesting sort of Brain-Flak/Mini-Flak constant; the long line here represents the number 60. You may be confused at the lack of (), which are normally all over the place in Brain-Flak constants; this isn't a regular number, but a Church numeral, which interprets numbers as a duplication operation. For example, the Church numeral for 60, seen here, makes 60 copies of its input and combines them all together into a single value; in Brain-Flak, the only things we can combine are regular numbers, by addition, so we end up adding 60 copies of the top of the stack and thus multiplying the top of the stack by 60.

As a side note, you can use an Underload numeral finder, which generates Church numerals in Underload syntax, to find the appropriate number in Mini-Flak too. Underload numerals (other than zero) use the operations "duplicate top stack element" : and "combine top two stack elements" *; both those operations exist in Brain-Flak, so you just translate : to ), * to {}, prepend a {}, and add enough ( at the start to balance (this is using a weird mix of the main stack and working stack, but it works).

This particular code fragment uses the church numeral 60 (effectively a "multiply by 60" snippet), together with an increment, to generate the expression 60x + 1. So if we had a 4 from the previous step, this gives us a value of 241, or if we had a 0, we just get a value of 1, i.e. this correctly calculates the number of iterations we need.

The choice of 241 is not coincidental; it was a value chosen to be a) approximately the length at which the program would end up anyway and b) 1 more than 4 times a round number. Round numbers, 60 in this case, tend to have shorter representations as Church numerals because you have more flexibility in factors to copy. The program contains padding later on to bring the length up to 241 exactly.

{
    ({}(
        …
    )[{}()])
}{}

This is a for loop, like the one seen earlier, which simply runs the code inside it a number of times equal to the top of the main stack (which it consumes; the loop counter itself is stored on the working stack, but visibility of that is tied to the program's nesting level and thus it's impossible for anything but the for loop itself to interact with it). This actually runs the data string and its formatter 1 or 241 times, and as we've now popped all the values we were using for our control flow calculation from the main stack, we have the format to use on top of it, ready for the formatter to use.

(␀␀!S␠su! … many more comment characters … oq␝qoqoq)

The comment here isn't entirely without interest. For one thing, there are a couple of Brain-Flak commands; the ) at the end is naturally generated as a side effect of the way the transitions between the various segments of the program work, so the ( at the start was manually added to balance it (and despite the length of the comment inside, putting a comment inside a () command is still a () command, so all it does is add 1 to the return value of the data string and its formatter, something that the for loop entirely ignores).

More notably, those NUL characters at the start of the comment clearly aren't offsets from anything (even the difference between +8 and -4 isn't enough to turn a ( into a NUL). Those are pure padding to bring the 239-element data string up to 241 elements (which easily pay for themselves: it would take much more than two bytes to generate 1 vs. 239 rather than 1 vs. 241 when calculating the number of iterations required). NUL was used as the padding character because it has the lowest possible codepoint (making the source code for the data string shorter and thus faster to output).

{}({}())

Drop the top stack element (the format we're using), add 1 to the next (the last character to be output, i.e. the first character to be printed, of the program section we just formatted). We don't need the old format any more (the new format is hiding on the working stack); and the increment is harmless in most cases, and changes the ' at one end of the source representation of the data string formatter into a ( (which is required on the stack for next time we run the formatter, to format the data string itself). We need a transformation like that in the outro or intro, because forcing each data string formatter element to start with ( would make it somewhat more complex (as we'd need to close the ( and then undo its effect later), and we'd somehow need to generate an extra ( somewhere because we only have almost 241 copies of the formatter, not all 241 (so it's best that a harmless character like ' is the one that's missing).

(({})(()()()()){})

Finally, the loop exit test. The current top of the main stack is the format we need for the next iteration (which just came back off the working stack). This copies it and adds 8 to the copy; the resulting value will be discarded next time round the loop. However, if we just printed the intro, the offset was -4 so the offset for the "next iteration" will be -8; -8 + 8 is 0, so the loop will exit rather than continuing onto the iteration afterwards.


APL, 13 17

(21 byte in UTF-8)

B[{↑⍋|⍵-B}¨A]

If you want true lambda (A as left argument and B as right):

{⍵[⍺{↑⍋|⍺-⍵}¨⊂⍵]}

How it works:

{...}¨A invokes lambda function {...} with every A value (instead of invoking with A as array), gathering results to array of same shape

|⍵-B computes absolute values of difference between argument ⍵ and all in B (- is subtraction, | is abs).

↑⍋ takes index of least element (⍋ sorts array returning indices, ↑ get first element)

B[...] is just fetching element(s) by index(es).

The solution is quite strightforward, altough it uses
wonderful feature of APL's sorting function returning permutation vector (sorted element's indices in original array) rather than sorted array itself.


Can the number reach 1 by repeatedly subtracting the largest prime less than it?

Retina, 31 bytes

.+
$*
+`1(?!(11+)\1+$)11+
1
^1$

Prints 0 (falsy) or 1 (truthy).

Try it online! (The first line enables a linefeed-separated test suite.)

Explanation

.+
$*

Convert input to unary by turning input N into N copies of 1.

+`1(?!(11+)\1+$)11+
1

Repeatedly remove the largest prime less than the input. This is based on the standard primality test with regex.

^1$

Check whether the result is a single 1.


Rust, 109 106 bytes

fn t(n:i8)->Result<Box::<Iterator::<Item=i8>>,i8>{if n==0{Err(0)}else{Ok(Box::new(std::iter::repeat(1)))}}

Try it online!
Returns a result whose ok variant is a dynamically typed iterator that always yields one wrapped in a smart pointer so the compiler can know its size. The error variant is simply zero. The code does emit a deprecation warning, so it may randomly stop working at some point in the future. Rust's type inference is too good for me to get a pristine closure, and as verbose as this solution is it is still shorting than fully listing the returned iterator's type and much shorter than using the main function and reading from stdin.
-3 bytes because there is a method to create an endlessly repeating iterator


05AB1E, 11 bytes
-1 byte thanks to @KevinCruijssen
gžQ×æêéI¡н

Try it online!
TIO link is for "abcd" instead of printable ascii since powerset of len(input) printable ascii takes a while to compute...

Explanation
gžQ×                 - repeat printable ascii length of the input times
    æ                - get the powerset of this string
     êé              - sort and uniquify lexicographically then sort by length
       I¡            - split on the input
         н           - and take the elements that are before it
                     - output these implicitly


Embedded Decoder

A Postscript program has a unique(?) ability to read it's own program text as data. This is normally used by the image operator which receives a data-acquisition-procedure as input, and this procedure often uses currentfile followed by readline, readstring, or readhexstring. But seen another way, image is just another looping operator, so any loop can read-ahead. An example is the line-printer emulator from the Green Book.

Using the token operator invokes the scanner on a file or string, pulling off a number or space- (or otherwise-: see other answer) -delimited name.

A simple PS interpreter in PS:

{currentfile token not {exit} if dup type /arraytype ne {exec} if }loop

Binary Operator String Decoder

Since I can't seem to get raw binary tokens to work for me (see other answer), I've made use of the "embedded decoding" idea to exploit the binary token mechanism to pack code into 8-bit strings, and then manipulate and parse the commands from the string on the fly.

/.{
    <920>  % two-byte binary-encoded name template with 0x92 prefix
    dup 1 4 3 roll put  % insert number into string
    cvx exec  % and execute it
}def
/${
    //.   %the /. procedure body defined above
    73 .  %"forall" (by code number)
}def

The . procedure takes a number from the stack and inserts it as the second byte in a two-byte string, the first byte being the prefix-byte for a binary token, specifying an executable system name. We save a byte in the hexstring by using a rule of the scanner that an odd number of nibbles in the hexstring is padded with an extra 0 nibble, so 3 hex nibbles produces a 2-byte string. The string is then marked executable and called with exec which invokes the scanner, produces the desired executable system name, and then loads the name and executes the operator. The $ does this on each byte of a string on the stack, using the . procedure twice, once as the loop body, and then to execute the looping operator forall by number.

More compactly, these procedures look like this:

 /.{<920>dup 1 4 3 roll put cvx exec}def/${//. 73 .}def
%123457890123456789012345678901234567890123456789012345
%        1         2         3         4         5

So, 55 chars buys binary token strings. Or, for 6 (maybe 7, if you terminate it with a space) chars, you can load the G library with (G)run which defines . and $ as above (+ a few others to extend the range of ascii-reachable codes).

Further illustrated in my crossword puzzle answer.