Word fractal plotter Iterated Function Systems

An Iterated Function System (IFS) is a method of constructing self-similar fractals. Each fractal is defined recursively as the union of several copies of itself, with each copy obtained by applying a transformation function to the whole. The functions are usually affine transformations of the form x↦Mx+b: i.e. a linear transformation such as a rotation, scaling or reflection, followed by a translation. Given a set of transformations, the fractal can then be obtained iteratively as follows: begin with a point (for example the origin) and repeatedly apply a randomly-selected transformation from the set. The sequence of points generated, which converges to the fixed point of the IFS, is then plotted.

The most famous example of an IFS is the Barnsley Fern. This is produced from four affine transformations, shown in the diagram below (taken from Wikipedia).

The affine transformations used in this questions involve only uniform scaling, rotation by a multiple of 90°, and translation. They can be implemented as follows, where n is the scale factor, θ is the rotation angle in radians and b is the translation in 'plot units' (e.g. pixels):

Seven-segment displays

A seven-segment display (SSD) is a cheap and simple electronic display device often used in clocks, meters and calculators to display decimal numerals. Though it wasn't designed to display letters, it is sometimes used to do so. The resulting alphabet is often ambiguous and sometimes unintuitive, but is sufficient for certain status messages (e.g. "nO dISC" or "gOOdbYE"). Below is one way to represent the 26 letters and 10 numerals on a seven-segment display.

Task

The aim of this challenge is to produce word fractals using IFSs and the SSD alphabet above.

The input is a string of multiple alphanumeric characters. The string may contain both upper and lower case letters, though the SSD alphabet is case insensitive. The program need not support punctuation or whitespace characters.
The output should be an IFS plot representing the string as rendered in the SSD alphabet above. Each lit segment in each character should correspond to an additional affine transformation mapping the bounding box of the rendered word to that of the segment. Horizontal segments should remain facing upwards, while vertical segments should face 'outwards' (i.e. left-side up on the left, right-side up on the right). The precise alignment/overlap of segments is left up to the solver, as long as the output is legible. For an example output showing one possible alignment, see below.
There should be a constant non-empty gap between the letters, to make the output legible.
The plot should contain enough points to be legible.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument. The output should be drawn either to screen or to a file in any standard graphic format. As part of the answer you should include a screenshot of your output for the word "COdEgOLF". Standard code golf restrictions apply.

Example

Scoring

Shortest code (in bytes) wins. Standard rules apply.

Miscellania

For a good mathematical introduction to IFSs (including fractal compression) see these PDF lecture notes.

For a similar challenge concerning self-similar text see Words within words within words within words . . ..

Python (518)

from pylab import*
D=dict(zip('ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789',[map(int,bin(7145037215283832782017591362181079009730769141301710950254702714880607436795)[2+n*7:9+n*7])for n in range(36)]))
def T(A,C):y,x=A.shape;M=zeros((2*x-1,x+y));p=A[::-1].T;q=A.T[::-1];M[:y,:x]=C[0]*A;M[:x,:y]=C[1]*p;M[:x,-2*y:-y]=C[2]*q;M[x-1:x-1+y,:x]=C[3]*A;M[x-1:,:y]=C[4]*p;M[x-1:,-2*y:-y]=C[5]*q;M[2*x-1-y:2*x-1,:x]=C[6]*A;return M
def R(S,N):
 V=ones((1,3))
 for i in range(N):V=concatenate([T(V,D[C])for C in S],1)
 ion();imshow(V)

Call as R('CODEGOLF', 3)
first i make a dictionary that maps letters to their 7-bit SSD-representaion, where each bit stands for one bar, the .-corners are simply overwritten by the most recent bar
.000.
1   2
1   2
1   2
.333.
4   5
4   5
4   5
.666.

The function T(BaseArray, BooleanArray) makes a big empty array for one letter and puts rotated copies of BaseArray along the bars as indicated by BooleanArray. Finally R(String, N_levels) connects all the letters form the input and uses the result as BaseArray for the next iteration.
While technically correct, the result is quite ugly because of interpolation and the default colourmap

Unglofed
from pylab import*
D=dict(zip('ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789',
           [map(int,bin(7145037215283832782017591362181079009730769141301710950254702714880607436795)[2+n*7:9+n*7])for n in range(36)]))

def T(A,C):
    y,x = A.shape
    M = zeros((2*x-1,x+y))
    if C[0]: M[:y,           :x] = A
    if C[1]: M[:x,           :y] = A[::-1].T
    if C[2]: M[:x,      -2*y:-y] = A.T[::-1]
    if C[3]: M[x-y+y/2:x+y/2,:x] = A # middle bar shifted upwards by half thickness
    if C[4]: M[x-1:,         :y] = A[::-1].T
    if C[5]: M[x-1:,    -2*y:-y] = A.T[::-1]
    if C[6]: M[2*x-1-y:2*x-1,:x] = A
    return M

def R(S,N):
    V = ones((1,3))
    for i in range(N):
        V = concatenate([T(V, D[C]) for C in S], 1)
    imsave('%s_%s.png'%(S,N), V ,cmap='gray')

The initial seed V kinda controls the font on the deepest level. [1 1 1] make the smallest possible 3x5 letters

With V = ones((1,11)) you get long and thin letters

And with
V=array([[0,1,1,1,1,1,1,1,1,0],
         [1,0,0,0,0,0,0,0,0,1],
         [0,1,1,1,1,1,1,1,1,0]])

you can make hollow letters


Shorten the Java Package Briefing

Given a Fully Qualified Java Class/ Package name, you must shorten it as such:

Each part of the dot separated package will be shortened to it's first letter, apart from the last section and the class (if it exists).

package names will be all lower case, and the class (if it exists) will start with a capital letter and be UpperCamelCase. packages come in the form of:

foo.bar.foo

and

foo.bar.foo.Class

Examples

(No Class)
Input com.stackoverflow.main
Output c.s.main

(Class)
Input com.google.parser.Gson
Output c.g.parser.Gson

(Class)
Input com.google.longer.package.TestClass
Output c.g.l.package.TestClass

Rules

Shortest code in bytes wins
Standard loopholes apply

Retina, 17 bytes

\B\w+(\.[a-z])
$1

Try it online!

Explanation

\B         # Start from a position that isn't a word boundary. This ensures that
           # the first letter of the package name is skipped.
\w+        # Match one or more word characters. This is the remainder of the
           # package name which we want to remove.
(          # Capture the next part in group 1, because we want to keep it...
  \.[a-z]  #   Match a period and a lower-case letter. This ensures that we
           #   don't match the package that precedes the class, or the package or
           #   class at the end of the input.
)

This is replaced with $1, which is the period and lower case letter which shouldn't be removed.


Alphabetize Integers Alphabetize Integers

For a given set of numbers, put them in alphabetical order when they are spelled out (i.e. 1: one, 2: two, 90: ninety, 19: nineteen). Your code should work for the range [-999999, 999999]. Output must have a delimiter between numbers. A space will work, as will a space and a comma as shown in the examples below. Input can be an array of integers, a string of delimited numbers, or however you see fit. All integers are assumed to be unique.

Numbers are not hyphenated for the purposes of this challenge and spaces are alphabetized before any other characters. Negative numbers are assumed to be expressed by using the word minus. For example, four would precede four thousand and the number -40 would be sorted using the string minus forty. Assume all numbers will be solely comprised of number words and no conjunctions (e.g. use two thousand forty two instead of two thousand and forty two).

Test Cases

Single Digit Integers:

Input:

1, 2, 3, 4, 5

Output:

5, 4, 1, 3, 2

Multiple Digit Integers:

Input:

-1002, 5, 435012, 4, 23, 81, 82

Output:

81, 82, 5, 4, 435012, -1002, 23

Spaces between words, no hyphens, commas or "and":

Input:

6, 16, 60, 64, 600, 6000, 60000, 60004, 60008, 60204, 60804

Output:

6, 600, 6000, 16, 60, 64, 60000, 60008, 60804, 60004, 60204

Remember, this is code-golf, so the code with the fewest bytes wins. No loopholes allowed!

Inform 7, 214 201 118 bytes
Inform 7 is an absolutely terrible language for golfing, so I wanted to give it a chance here.
Indentation should use tab (\t) characters, but HTML doesn't like those. Conversely, Inform doesn't like spaces for indentation, so you'll have to replace the spaces with tabs if you copy-paste the code from here to test it. Or just copy-paste from the Markdown source instead.
Golfed:

To X:
    repeat through Table 1:
        now Q entry is "[R entry in words]";
    sort Table 1 in Q order;
    say "[R in Table 1]".

Input should be an Inform table, like so (with \t between the columns):

Table 1
R (number)  Q (text)
-1002
5
435012
4
23
81
82

Output:

81, 82, 5, 4, 435012, -1002, 23

This function runs through the table once, adding a textual representation of each number in a new column. Then it sorts the table rows according to the text column; in Inform, strings are sorted lexicographically. Finally, it prints out the original column in the new order. Conveniently, Inform 7's "crude but sometimes useful" format for printing out table columns turns out to be comma separated, exactly as requested.
Ungolfed, with boilerplate showing how to call the function:

To print the numbers in alphabetical order:
    repeat through the Table of Sortable Numbers:
        now the name entry is "[the index entry in words]";
    sort the Table of Sortable Numbers in name order;
    say "[the index column in the Table of Sortable Numbers]".

Table of Sortable Numbers
index (number)  name (text)
-1002
5
435012
4
23
81
82

There is a room.
When play begins: print the numbers in alphabetical order.


Rise, sequence, rise We have a strictly increasing sequence of non-negative integers, like:

12 11 10

Wait! This sequence isn't strictly increasing, is it? Well, the numbers are written in different bases. The least possible base is 2, the biggest is 10.

The task is to guess bases each number is written, so that:

the sequence is strictly increasing,
the sum of the bases is maximised.

For instance, the solution for the sample will be:

6 8 10

because under those bases the sequence becomes 8 9 10 decimal - a strictly increasing sequence, and we are not capable of finding bases for which the sequence remains strictly increasing and whose sum is bigger than 6+8+10 .

Due to the second limitation a solution 3 5 7 is not satisfactory: in spite of fact that the sequence becomes 5 6 7 under those bases - we need to maximise the bases sum, and 3+5+7 < 6+8+10.

If under no bases 2<=b<=10 is it possible for the series to be strictly increasing, for instance:

102 10000 10

single

0

should be output.

The input sequence can be passed in the way it's most convenient for your solution (standard input / command line parameters / function arguments...).

Pyth, 31 30 29 bytes

e+0f.x!sgM.:iVczdT2ZosN^STlcz

1 byte thanks to @Jakube.

Demonstration. Test Harness.

Input is given on STDIN, space separated. If newline separated input is allowed, I can shorten the program by 2 bytes.

Explanation:

e+0f.x!sgM.:iVczdT2ZosN^STlcz
                                  Implicit: z = input(), T = 10, Z = 0, d = ' '
                        ST        [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
                          lcz     len(z.split())
                       ^          All combinations w/replacement of that length.
                    osN           Order by increasing sum.
   f                              Filter on
              czd                 z.split(' ')
            iV   T                Vectorize the "Convert to base" operation over
                                  the integers as strings and the base sequence.
          .:      2               Take length 2 subsequences.
        gM                        Map the >= operation over them.
      !s                          Sum and logically negate.
    .x             Z              If that throws an error, returns 0 (e.g. reject)
 +0                               Prepend a 0, in case no sequences are found.
e                                 Take the end of the list.

Including 1 in the list of possible bases is safe because i, which uses Python's int builtin, doesn't allow 1 as a base, and therefore always throws an error, which is caught and filtered out.


Evaluating the score based from a chess FEN string Challenge

Forsyth–Edwards Notation (FEN) is a standard notation for describing a particular board position of a chess game. Your challenge is to evaluate the score using the FEN string. This is an example of a FEN string:

5k2/ppp5/4P3/3R3p/6P1/1K2Nr2/PP3P2/8

Using this string, you can calculate the material score for each color with the following score table:

  p / P = Pawn = 1 point
  n / N = Knight = 3 points
  b / B = Bishop = 3 points
  r / R = Rook = 5 points
  q / Q = Queen = 9 points
  k / K = King, these don't have any points because every legal position contains a king for each side

White pieces are designated using upper-case letters ("PNBRQK") while black pieces use lowercase ("pnbrqk"). Empty squares are noted using digits 1 through 8 (the number of empty squares), and "/" separates ranks.

From the example FEN string, we can calculate the material scores for each side:

For black:

  5k2/ppp5/4P3/3R3p/6P1/1K2Nr2/PP3P2/8

  All the black pieces left: p + p + p + p + r, this is a total of 9

For white:

  5k2/ppp5/4P3/3R3p/6P1/1K2Nr2/PP3P2/8

  All the white pieces left: P + R + P + N + P + P + P, this is a total of 13

The final score is determined with the following formula: White score - Black score = Final score, so for the example the final score would be: 13 - 9 = 4

Example :

Input:

5k2/ppp5/4P3/3R3p/6P1/1K2Nr2/PP3P2/8

Output:

4

All code-golf rules apply here, the solution with the least amount of bytes wins.

How to post

# Language Name, N bytes

 [code]

 [explaination, etc.]

><>, 64 57 56 53 bytes

"QRBNP"013359v
$0p4}:{:v?=1l<p4+' '{-
g4v?(0:i<+
n~<;

(-7 bytes with some inspiration from @El'endiaStarman's answer, -3 bytes thanks to @randomra)

Explanation

The program uses the codebox as a lookup table. Out-of-range puts/gets don't work with the online interpreter, so this only works with the official Python interpreter.

The first line pushes the pieces, followed by the piece values. It also pushes an initial 0 to kick off the total for the third line.

The second line then puts the appropriate positive or negative value at the corresponding piece cell, e.g. -1 is placed at ('p', 4) and 1 is placed ('P', 4). The length of the stack is checked to make sure the loop runs 5 times.

After the loop is over, the stack consists of our single zero from the first line. For each char we perform a lookup at the corresponding cell in the table and add it to our total. By default, uninitialised cell values are 0, which is perfect for our purposes.

The last line merely prints the result.


Short drawing programme You just invited a liberal arts major to your house and you're telling him/her

  "You know, I am a great programmer and I can do x and y and z..."

S/he quickly gets bored and asks you:

  "If you really are a great programmer, can you make a programme to let me draw, I just need to draw lines on the screen by using the
  mouse, and selecting different colours in any manner".

Your code may import standard libraries. Your code may require the colours to be selected via the keyboard.

This is code-golf; shortest code wins.

Bullet points

The lines are drawn by moving the mouse around while pressing the left button.
Bresenham's Line Algorithm is not necessary any built-in algorithm will do the trick
If the user can change the line thickness in any way you get a * 0.8 bonus but it is not obligatory.
I guess it should be nicer to implement the line-drawing ourselves, but if you want you can import a library for that just say it in the code description.
The minimum is 5 different colours (red,green,blue,white,black). If you make them change randomly you get a penalty of *1.2. You may change them in any way you may want (both buttons and key presses are OK).
Drawing them pressing the mouse between to points or freehand would be best (i.e. as you do in paint) and gives you a bonus of *0.7 , but any other method is okay: (example) click two points and draw a line between those points?
The drawing canvas has to be 600x400
Changing the colour should change the colour only of the lines that will be drawn in the future.
Implementing a "Clear All " command is not obligatory but if you implement that you get *0.9 bonus.

Processing - 93 · 0.9 = 83.7

With next to no overhead for drawing, but a very verbose syntax, in Processing the best score is probably reached without any nice features and only one bonus:

void setup(){
size(600,400);
}
void draw(){
if(mousePressed)line(mouseX,mouseY,pmouseX,pmouseY);
}

Score: 93 · 0.9 = 83.7 (Newlines are for readability only and are not counted in the score.)

However, it's much more fun with all the bonuses in place:

void setup(){
size(600,400);
}
int i,x,y;
void draw(){
stroke(7*i%256,5*i%256,i%256);
strokeWeight(i%9);
if(keyPressed)i++;
if(!mousePressed){x=mouseX;y=mouseY;if(x<0)background(0);}
}
void mouseReleased(){
line(x,y,mouseX,mouseY);
}

Score: 221 · 0.8 · 0.7 · 0.9 = 111.4

It's used like this:

Click and drag the mouse to draw a straight line.
While clicked, drag the mouse off the left side of the window and release the mouse button to clear the screen.
Holding down any key will cycle through the red, green and blue values of the drawing colour and through different stroke thicknesses. Since the cycling periods are different, practically all combinations can be reached (with a bit of trying).

Edit:

Since freehand drawing gives the 0.7 bonus as well, here is yet another solution:

void setup(){
size(600,400);
}
int i;
void draw(){
stroke(7*i%256,5*i%256,i%256);
strokeWeight(i%9);
if(keyPressed)i++;
if(key>9)background(0);
if(mousePressed)line(mouseX,mouseY,pmouseX,pmouseY);
}

Score: 188 · 0.8 · 0.7 · 0.9 = 94.8

It's used like this:

Click and drag to draw freehand lines.
Hold the tab key to change the colour and stroke thickness. This can also be done while drawing (see picture).
Hit any key but tab and then tab to clear the screen.


Write the fastest Fibonacci This is yet another challenge about the Fibonacci numbers.

The goal is to compute the 20'000'000th Fibonacii number as fast as possible. The decimal output is about 4 MiB large; it starts with:

  28543982899108793710435526490684533031144309848579

The MD5 sum of the output is

  fa831ff5dd57a830792d8ded4c24c2cb

You have to submit a program that calculates the number while running and puts the result to stdout. The fastest program, as measured on my own machine, wins.

Here are some additional rules:

You have to submit the source code and a binary runnable on an x64 Linux
The source code must be shorter than 1 MiB, in case of assembly it is also acceptable if only the binary is that small.
You must not include the number to be computed in your binary, even in a disguised fashion. The number has to be calculated at runtime.
My computer has two cores; you are allowed to use parallelism

I took a small implementation from the Internet which runs in about 4.5 seconds. It should not be very difficult to beat this, assuming that you have a good algorithm.

Sage

Hmm, you seem to assume that the fastest is going to be a compiled program.  No binary for you!

print fibonacci(2000000)

On my machine, it takes 0.10 cpu seconds, 0.15 wall seconds.

edit: timed on the console, instead of the notebook


Find the syncopation Given an input of a string consisting entirely of qs representing quarter
notes and es representing eighth notes, output the indices of the quarter
notes that are syncopated.

Syncopation is complex, but for
the purposes of this challenge, our definition of "syncopated" will be very
simple: a quarter note that starts on the "off-beat"—that is, the beats counted
as "and" in n/4 time.

This may alternatively be defined as any quarter note that is preceded by an
odd number of eighth notes. For example, the notes marked with * below are considered syncopated, and their indices are also shown:

eqqeqqeqqe
 **    **
 12    78
Output: 1 2 7 8

The input will always consist of a whole number of measures in 4/4 time (a
quarter note is a quarter of a measure, and an eighth note is an eighth of a
measure). (The input will also never be empty.) Output can either be a single string with elements separated by any delimiter that does not contain numbers or an array/list/etc. The output may be 1-based (i.e. the first index is 1 instead of 0) if you wish, and it may also be in any numeric base (unary, decimal, etc.).

Since this is code-golf, the shortest code in bytes wins.

Test cases:

In                        Out
-----------------------------------------------
eqqqe                     1 2 3
qeqeq                     2
qqqeqqeeeeqeqeqeqqeqqeqq  4 5 10 14 19 20
eeeeeqeeqeeqqqqeqeqeeqe   5 8 11 12 13 14 18 21
qqqq                      <none>
eeeeeeee                  <none>

Jelly, 12 9 bytes

=“e”µ<^\O

As a program, the above code requires quotes around the input. Since that is not allowed, this is a function submission. The output is 1-based. Try it online!

How it works

=“e”µ<^\O    Monadic link. Argument: s (string)

=“e”         Check each character for equality with 'e'. Yields a Boolean array.
    µ        Start a new, monadic chain.
      ^\     Compute the array of partial reductions by XOR, i. e., the parities
             of all prefixes of the Boolean array.
     <       Check if the Booleans are strictly smaller than the parities.
             A truthy outcome indicates an off-beat quarter note.
        O    Yield all indices of 1's.

Update

The above code doesn't work anymore in the latest version of Jelly, since we need a character e, but “e” yields a string. Fixing that saves a byte, for a total of 8 bytes.

=”eµ<^\O

This works as a full program. Try it online!


The Smart Person's Mirage Once upon a time, I was reading this question/answer on Quora

Are there really programmers with computer science degrees who cannot pass the FizzBuzz test

This code is given as the obvious answer

for i in range(1, 100):
    if i % 3 == 0 and i % 5 == 0:
        print "FizzBuzz"
    elif i % 3 == 0:
        print "Fizz"
    elif i % 5 == 0:
        print "Buzz"
    else:
        print i

Of course FizzBuzz has been golfed to death, but that is not what this question is about. You see, in the comments, someone mentions that this obvious answer is great since it's easy to add extra conditions such as print "Jazz" for multiples of 4. (I don't agree. Extending this scheme requires O(2**n) lines of code.)

Your challenge is to write the most beautiful version of FizzJazzBuzz as judged by your peers.

Some things for voters to consider:

DRY
Efficiency of division/modulus operations

Many of the answers on Quora were using Python, but there is no such language restriction here.

I'll accept the answer with the most votes one month from now

Sample output:

1
2
Fizz
Jazz
Buzz
Fizz
7
Jazz
Fizz
Buzz
11
FizzJazz
13
14
FizzBuzz
Jazz
17
Fizz
19
JazzBuzz
Fizz
22
23
FizzJazz
Buzz
26
Fizz
Jazz
29
FizzBuzz
31
Jazz
Fizz
34
Buzz
FizzJazz
37
38
Fizz
JazzBuzz
41
Fizz
43
Jazz
FizzBuzz
46
47
FizzJazz
49
Buzz
Fizz
Jazz
53
Fizz
Buzz
Jazz
Fizz
58
59
FizzJazzBuzz
61
62
Fizz
Jazz
Buzz
Fizz
67
Jazz
Fizz
Buzz
71
FizzJazz
73
74
FizzBuzz
Jazz
77
Fizz
79
JazzBuzz
Fizz
82
83
FizzJazz
Buzz
86
Fizz
Jazz
89
FizzBuzz
91
Jazz
Fizz
94
Buzz
FizzJazz
97
98
Fizz
JazzBuzz

The most beautiful version, you say? Then, let's try this one in...

Shakespeare Programming Language

The Marvelously Insane FizzBuzzJazz Program.

Lady Capulet, an old bossy woman that loves to count.
The Archbishop of Canterbury, an old fart who adores to spit out letters.

          Act I: The only one of them.

          Scene I: The Archbishop of Canterbury is a bastard.

[Enter The Archbishop of Canterbury and Lady Capulet]

The Archbishop of Canterbury:
 You are nothing!

          Scene II: Count, Lady Capulet, count.

The Archbishop of Canterbury:
 You are as beautiful as the sum of yourself and a cat!

Lady Capulet:
 Am I worse than the square of the product of the sum of a warm gentle flower and a rose
 and my pretty angel?

The Archbishop of Canterbury:
 If not, let us proceed to Scene VIII.

          Scene III: Fizzing to no end!

The Archbishop of Canterbury:
 Is the remainder of the quotient between yourself and the sum of a happy cow and a
 chihuahua as good as nothing?

Lady Capulet:
 If not, let us proceed to Scene IV. Thou art as handsome as the sum of the sum of
 the sweetest reddest prettiest warm gentle peaceful fair rose and a happy proud kindgom
 and a big roman. Speak thy mind!

 Thou art as fair as the sum of thyself and a honest delicious cute blossoming peaceful
 hamster. Thou art as cunning as the sum of the sum of an embroidered King and a horse
 and thyself. Speak thy mind!

 Thou art as amazing as the sum of the sum of a good happy proud rich hero and a hair and
 thyself! Speak thy mind.

 Speak your mind!

          Scene IV: Milady, there is jazz in thy robe.

The Archbishop of Canterbury:
 Is the remainder of the quotient between yourself and a proud noble kingdom as good as
 nothing?

Lady Capulet:
 If not, let us proceed to Scene V. You are as charming as the sum of the sum of a noble
 cunning gentle embroidered brave mighty King and a big warm chihuahua and an amazing
 pony! Speak your mind!

 You are as prompt as the sum of yourself and a big black sweet animal. You are as noble
 as the sum of the sum of a gentle trustworthy lantern and yourself and a hog. Speak your
 mind!

 You are as bold as the sum of the sum of yourself and a good delicious healthy sweet
 horse and my smooth cute embroidered purse. You are as peaceful as the sum of a flower
 and yourself. Speak your mind.

 Speak your mind!

          Scene V: Buzz me up, Scotty!

The Archbishop of Canterbury:
 Is the remainder of the quotient between yourself and the sum of a gentle happy cow and a
 chihuahua as good as nothing?

Lady Capulet:
 If not, let us proceed to Scene VI. Thou art as handsome as the sum of the sweetest
 reddest prettiest warm gentle peaceful fair rose and a small town. Speak your mind!

 You are as prompt as the sum of yourself and a big healthy peaceful fair rich kingdom.
 You are as loving as the sum of the sum of an embroidered King and a horse and thyself.
 You are as amazing as the sum of yourself and a cute fine smooth sweet hamster. Speak
 your mind!

 You are as prompt as the sum of the sum of yourself and an amazing cunning Lord and a
 hair. Speak your mind.

 Speak your mind!

The Archbishop of Canterbury:
 Let us proceed to Scene VII.

          Scene VI: Output or die!

The Archbishop of Canterbury:
 Open your heart!

          Scene VII: Oh, to jump the line.

Lady Capulet:
 You are as handsome as the sum of a proud noble rich kingdom and a rural town. Speak your
 mind! You are as gentle as the sum of the sum of yourself and a green mistletoe and my
 father. Speak your mind!

The Archbishop of Canterbury:
 We must return to Scene II.

          Scene VIII: Goodbye, cruel world!

[Exeunt]

So, after my struggle with SPL here, I felt like I had to do at least one submission with it on any challenge. And this is it.

So, what's all this then?

So, first, we declare the variables we're going to use throughout the program, which must come from Shakespeare plays. Fed up of Romeo, Juliet, Ophelia and Othello, I went up with The Archbishop of Canterbury and Lady Capulet. Their descriptions, as well as the Acts'/Scenes' titles, are disgarded by the parser, so you can put there pretty much anything you like.

So, let's make some king of translation to something a little less gibberishy.

Act I, Scene I

Begin
Lady Capulet = 0;

Act I is pretty straightforward: we initialize our variable with 0.

Act I, Scene II

Lady Capulet += 1;
if(Lady Capulet < Math.pow((2*2*1+1)*(2*1),2))
continue;
else
goto Scene VIII;

We increment Lady Capulet's value and compare it with 100 (yes, that whole sentence serves solely to get the number 100); if it's not smaller, we jump to Scene VIII (the end); otherwise, we continue on to the next Scene.

Act I, Scene III

if(Lady Capulet % (2+1) == 0)
continue;
else
goto Scene IV;
The Archbishop of Canterbury = 2*2*2*2*2*2*1;
System.out.print((char)The Archbishop of Canterbury);
The Archbishop of Canterbury += 2*2*2*2*2*1;
The Archbishop of Canterbury += 2*1+1;
System.out.print((char)The Archbishop of Canterbury);
The Archbishop of Canterbury += 2*2*2*2*1+1;
System.out.print((char)The Archbishop of Canterbury);
System.out.print((char)The Archbishop of Canterbury);

First, we see if the modulus of the division by 3 is 0; if it's not, we jump to Scene IV; if it is, we begin doing arithmetic operations and storing them on the Archieperson, outputting them in character form once we find the one we're looking for. Yes, in the end, the idea is to get Fizz.

Act I, Scene IV

if(Lady Capulet % (2*2) == 0)
continue;
else
goto Scene V;
The Archbishop of Canterbury = 2*2*2*2*2*2*1+2*2*1+2*1;
System.out.print((char)The Archbishop of Canterbury);
The Archbishop of Canterbury += 2*2*2*1;
The Archbishop of Canterbury += 2*2*1+(-1);
System.out.print((char)The Archbishop of Canterbury);
The Archbishop of Canterbury += 2*2*2*2*1+2*2*2*1;
The Archbishop of Canterbury += 1;
System.out.print((char)The Archbishop of Canterbury);
System.out.print((char)The Archbishop of Canterbury);

First checks if the modulus of the division by 4 is 0, then continues as the same scene as before, for Jazz.

Act I, Scene V

if(Lady Capulet % (2*2+1) == 0)
continue;
else
goto Scene VI;
The Archbishop of Canterbury = 2*2*2*2*2*2*1+2*1;
System.out.print((char)The Archbishop of Canterbury);
The Archbishop of Canterbury += 2*2*2*2*2*1;
The Archbishop of Canterbury += 2*1+1;
The Archbishop of Canterbury += 2*2*2*2*1;
System.out.print((char)The Archbishop of Canterbury);
The Archbishop of Canterbury += 2*2+1;
System.out.print((char)The Archbishop of Canterbury);
System.out.print((char)The Archbishop of Canterbury);
goto Scene VII;

Functions like the previous two, checking if the modulus of the division by 5 returns 0, then attempts to write Buzz; the only difference is that, in the end, we skip a Scene.

Act I, Scene VI

System.out.print(Lady Capulet);

To reach this Scene, the number assumed by Lady Capulet must not have been neither Fizz nor Jazz nor Buzz; so, we output it in numeric form.

Act I, Scene VII

The Archbishop of Canterbury = 2*2*2*1+2*1;
System.out.print((char)The Archbishop of Canterbury);
The Archbishop of Canterbury += 2*1+1;
System.out.print((char)The Archbishop of Canterbury);
goto Scene II;

So, this is the only way I found to jump to the next line: output, first, a CR, then a LF; then, we return to Scene II, to that we can continue with the program.

Act I, Scene VIII

End.

Straightforward enough.

I'm still trying to see if I could show this running online, but I can't find an online compiler - the one I know doesn't seem to combine well with any program except the one already loaded, or maybe there's some kind of problem with the interface between the keyboard and the chair...

Update 1:

After mathmandan's comment, I edited the order of Jazz's and Buzz's scenes. It had to be done.


How lit is this room?  pt. 1 Related to this question.

A room is defined to be a (not necessarily convex) non-intersecting polygon, expressed as an ordered list of 2-dimensional coordinates. A sufficiently bright lightbulb is placed at a specific point inside the room, and emits light in every direction. Your task is to find the total illuminated area of the room. You may take in input in any reasonable format. The points on the polygon/room as well as the coordinates of the light source are rational numbers. They can be taken in clockwise or counterclockwise, either format is fine. The test case in the problem is given counterclockwise.

The following picture shows two example rooms, where the purplish dot represents the light source, and the shaded region represents the illuminated area.

Test case:

(1/2, 18)
(1,3)
(5,1/2)
(7,5)
(12,7)
(16,3)
(15,11)
(8,19)
(3,7)
Light source located at (5,8)
Answer: 815523/6710 ≈ 121.538

Here is a graphical depiction of the solution to that test case. The two points that define the solution that are not on the original polygon are (55/61, 363/61) and (856/55, 357/55).

This formula may be helpful in calculating the area.

Since this is code-golf, the shortest code in bytes wins.

Python 3, 388 398 408 409 415 417 493 bytes

To make it more accurate, increase n

from random import*
u=uniform
c=lambda A,B,C:(C[1]-A[1])*(B[0]-A[0])>(B[1]-A[1])*(C[0]-A[0])
I=lambda A,B,C,D:c(A,C,D)!=c(B,C,D)and c(A,B,C)!=c(A,B,D)
def a(l,v,n=9**6,s=0):
 g=lambda i:(min(x[i]for x in v),max(x[i]for x in v))
 for _ in'x'*n:
  h=((u(*g(0)),u(*g(1))),l);s+=any([I(*f,*h)for f in list(zip(v,v[1:]+[v[0]]))])^1
 return(abs(g(0)[0]-g(0)[1])*abs(g(1)[0]-g(1)[1]))*float(s/n)

Basic Monte-Carlo approach.  Steps listed below.

Find x and y ranges that the shape occupies.
Create a list of edges created by the vertices
Iterate a large number of times (the more the better)
Create a random point (j,k) inside the x,y range.
Check if any of the edges intercept with the line-segment created by the light and the random point. If any of the edges intercept, increment the variable s
Divide s by the total numbers, then multiply by the total range area.

Ungolfed version:

import random

def ccw(A,B,C):
    return (C[1]-A[1])*(B[0]-A[0]) > (B[1]-A[1])*(C[0]-A[0])

def intersect(A,B,C,D):
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)

def lit_area(light, vertices):
    # points: list of points
    # i     : x => i=0
    #       : y => i=1
    get_range = lambda i: (min(x[i] for x in vertices), max(x[i] for x in vertices))
    xr = abs(get_range(0)[0] - get_range(0)[1])
    yr = abs(get_range(1)[0] - get_range(1)[1])

    edges = list(zip(vertices, vertices[1:] + [vertices[0]]))

    num_sims = 1000000

    num_successes = 0
    for _ in range(num_sims):
        guess_x = random.uniform(*get_range(0))
        guess_y = random.uniform(*get_range(1))

        light_guess_line = ((guess_x, guess_y), light)

        if not any([intersect(*e, *light_guess_line) for e in edges]):
            num_successes += 1
    return float(num_successes / num_sims) * (xr * yr)

if __name__ == "__main__":
    points = [
    (1/2, 18),
    (1,3),
    (5,1/2),
    (7,5),
    (12,7),
    (16,3),
    (15,11),
    (8,19),
    (3,7)
    ]
    light_source = (5,8)
    print("Area lit by light: %f"% lit_area(light_source, points))

Try it online!

Credit for line intersection algorithm

Also, credit to all the helpful commenters on how to golf this even further.


Tips for golfing in SOGL Do you have any code-golf tips for writing in SOGL, a golfing language created by  dzaima?

Your tips should be at least somewhat specific to SOGL.

Please post one tip per answer.

Use the compression creator

Here is a new, buggy but mostly working online JavaScript compression creator. There, in each line enter a part of the string on each line which closest matches one of:

custom dictionary string - this will find the different characters used in the part, store them and store a number in the base of the amount of characters. This is effective for strings like niooaaoasoioaiaaaoiineeaei where there aren't a lot of different characters. It also works well for just a single character repeated. This has a limit of 98+(different characters used), and the compressor (currently) doesn't auto-split those.
boxstrings - strings with only the characters /\|_- and \n. Practically the same as custom dictionary strings, but more efficient. Note that this is chooses whether to use / and \ with the same bit, so then custom strings will be used. This has a limit the same as custom dictionary strings.
english - this has two word dictionaries, one of length 256 and another of ±65500. This only contains lowercase words and automatically adds spaces between words. To get something like spaceface do two parts of space and face. Each english part has a max of 4 words. If a 4-word part is followed by more english, it adds a space between. Trough the compressor will automatically split the input for you.
Note: the dictionary contains only lowercase versions of strings (except I, I've, and a couple others), so you must correctly case if after usage (using the characters ⁽ - uppercase 1st letter, ⁾ - sentence-case, ū - every words 1st letter).
ascii - Plain ascii - each part is 1-18 long (trough 1 and 2 are done differently) and auto-splits for you. Approx. 87% compression ratio.

Other stuff:

It's always useful to try different combinations and see which is smaller. At the end, it gives you the original and ending byte count and compression ratio. This might be automated sometime in the future.
For example, -_-_\_/_-       is shorter than
-_-_\_/_- and
       as different parts

An example input would be

row
,
row
,
row your boat
,¶"

, which outputs "π¾⌡īk#S)G⁶⁷λ7&[¶⁶āΡn‘, after which I can put uppercase 1st letter and remove the starting quote and get π¾⌡īk#S)G⁶⁷λ7&[¶⁶āΡn‘⁽ for Row, row, row your boat,\n"


Minimal sparse rulers A standard ruler of length n has distance marks at positions 0, 1, ..., n (in whichever units). A sparse ruler has a subset of those marks. A ruler can measure the distance k if it has marks at positions p and q with p−q=k.

The challenge

Given a positive integer n, output the minimum number of marks required in a sparse ruler of length n so that it can measure all distances 1, 2, ..., n.

This is OEIS A046693.

As an example, for input 6 the output is 4. Namely, a ruler with marks at 0, 1, 4, 6 works, as 1−0=1, 6−4=2, 4−1=3, 4−0=4, 6−1=5, and 6−0=6.

Additional rules

The algorithm should be valid for arbitrarily large n. However, it is acceptable if the program is limited by memory, time or data type restrictions.
Input/output can be taken/produced by any reasonable means.
Programs or functions are allowed, in any programming language. Standard loopholes are forbidden.
Shortest code in bytes wins.

Test cases

1   ->   2
2   ->   3
3   ->   3
4   ->   4
5   ->   4
6   ->   4
7   ->   5
8   ->   5
9   ->   5
10  ->   6
11  ->   6
12  ->   6
13  ->   6
14  ->   7
15  ->   7
16  ->   7
17  ->   7
18  ->   8
19  ->   8
20  ->   8
21  ->   8
22  ->   8
23  ->   8
24  ->   9
25  ->   9
26  ->   9
27  ->   9
28  ->   9
29  ->   9
30  ->  10
31  ->  10
32  ->  10

Wolfram Language (Mathematica), 65 bytes

Tr[1^#]&@@Cases[Subsets[n=0~Range~#],k_/;Union@@Abs[k-#&/@k]==n]&

Try it online!


Prime Factor Encoding How the encoding works

Given a list of bits:

Hold a prime (starting with 2)
Have a list
For each bit in the input

If it's the same as the previous bit, add the prime you're holding to the list
If it's different, hold the next prime and add that to the list

Return the product of all the numbers in your list
For the first bit, assume the previous bit was 0

  Note: these steps are for illustration purposes only, you are not required to follow them.

Examples

Input: 001
hold 2

0:         add 2 to the list
0:         add 2 to the list
1: hold 3, add 3 to the list

list: 2,2,3
Output: 12

Input: 1101
hold 2

1: hold 3, add 3 to the list
1:         add 3 to the list
0: hold 5, add 5 to the list
1: hold 7, add 7 to the list

list: 3,3,5,7
Output: 315

Some more examples:

000000000 -> 512
111111111 -> 19683
010101010 -> 223092870
101010101 -> 3234846615
011101101 -> 1891890
000101101010010000 -> 3847834029582062520

Challenge

Write an encoder and a decoder for this encoding method.

(The decoder reverses the process of the encoder).

Input / Output

The encoder can take input in any reasonable format
The encoder must output either an integer or a string
The decoder must take input in the same format that the encoder outputs
The decoder must output the same format that the encoder takes as input

In other words decoder( encoder( input ) ) === input

Notes

The decoder may assume that its input is decodable
Your answer only has to deal with integers that your language can natively support without using (long, bigInt, etc.), be reasonable, if you language only supports ints up to 1, maybe reconsider posting an answer

Scoring

Your score is the sum of the lengths in bytes of the encoder and decoder.

If you need to import a module, the import can be counted only once provided that your encoder and decoder can coexist in the same file and be reused (like functions).

Default loopholes are forbidden.

This is code-golf so the shortest score for every language wins.

05AB1E, 13 bytes

Encoder, 8 bytes

0ì¥ĀηOØP

Try it online!

Explanation

0ì          # prepend 0 to input
  ¥         # calculate deltas
   Ā        # truthify each
    η       # calculate prefixes
     O      # sum each
      Ø     # get the prime at that index
       P    # product

Decoder, 5 bytes

Ò.ØÉJ

Try it online!

Explanation

Ò       # get prime factors of input
 .Ø     # get their indices among the primes
   É    # check for oddness
    J   # join


Implement Sleep Sort Sleep Sort is an integer sorting algorithm I found on the Internet. It opens an output stream, and for each input numbers in parallel, delay for the number seconds and output that number. Because of the delays, the highest number will be outputted last. I estimate it has O(n + m), where n is the number of elements and m is the highest number.

Here is the original code in Bash

#!/bin/bash
function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

Here is the pseudocode

sleepsort(xs)
 output = []
 fork
   for parallel x in xs:
     sleep for x seconds
     append x to output
 wait until length(output) == length(xs)
 return output

Your task is to implement Sleep Sort as a function in the programming language of your choice. You can neglect any concurrency factors such as race conditions and never lock any shared resources. The shortest code wins. The function definition counts toward the code length.

The input list is limited to non-negative integers only, and the length of the input list is expected to reasonably long (test at least 10 numbers) so race conditions never happen.
and assuming race conditions never happen.

C, 127 characters, a rather obvious solution:

main(int c,char**v){
#pragma omp parallel for num_threads(c)
for(int i=1;i<c;++i){int x=atoi(v[i]);sleep(x);printf("%d ",x);}}

(Compiled with gcc -std=c99 -fopenmp sort.c and ignoring all warnings.)


Syntax Highlighting for Greater Golf! Golfers.

Together, we have banded together to produce code that is concise, is functionally beautiful and is uglier then the Phantom of the Opera from the original novel.

The time has come for us to bring beauty back to the world of programming. With color. In a way that is concise, functionally beautiful is uglier then the Phantom of the Opera from the original novel.

We're gonna be coding a colorful syntax highlighter. In the shortest amount of code possible.

You will receive via an input file or Stdin a valid C file. The C file will use the line convention of your choice, and will only contain ASCII characters 32-126. You have to turn it into a HTML file that displays correctly at least in Chrome, that shows the source code  with syntax highlighting. The output may be in a file or to Stdout.

You must highlight:

All strings and characters (including the quote characters) in Green (#00FF00). The strings may contain escaped characters.
All C reserved words in Blue (#0000FF).
All comments in Yellow (#FFFF00).
All C preprocessor directives in Pink (#FF00FF).

The output when displayed in Chrome must:

Be in a fixed-width font
Display new lines wherever they appeared in the original source
Accurately reproduce whitespace. A tab character should be taken as being 4 spaces.

Bonuses

x 0.9 if you include line numbers. Line numbers must be able to reach at least 99999. All source must still be aligned - so, source code with smaller line numbers should still start at the same position as source code with higher line numbers
x 0.8 if background of each line is alternated between light gray (#C0C0C0) and white (#FFFFFF)
x 0.9 if your source code is written in C, and can correctly format itself.

Scoring

This is code golf. Your score is the amount of bytes of your source code multiplied by any bonuses. The winner is the golfer with the lowest score.

Perl 769 chars * 0.9 * 0.8 = 554

Probably still some improvements to be made on some of the regexes, but it's slowly getting there!

$_=join"",<>;$s="<tt class";$c="</tt>";$d=counter;$e=color;s/\t/    /g;s!<!&lt;!g;s!>!&gt;!g;s!^#.+(?=$|
)!$s=d>$&$c!gm;s!//.+!$s=c>$&$c!g;s|(['"]).*?(?<!\\)(\\\\)*\1|($h=$&)=~s!/!&#47;!g;"$s=s>$h$c"|smeg;s!/\*.*?\*/!$s=c>$&$c!smg;s!\b(_Packed|(au|go)to|break|c(ase|har|onst|ontinue)|d(efault|o|ouble)|e(lse|num|xtern)|f(loat|or)|if|int|long|re(gister|turn)|short|(un)?signed|s(izeof|tatic|truct|witch)|typedef|union|vo(id|latile)|while)\b!$s=r>$&$c!g;s!=(\w)>.+?$c!join"$c
$s=$1>",split$/,$&!smeg;s!
!
!g;print"

$_"

Slightly less obfuscated version with comments:

$_=join"",<>; # slurp file
$s="<tt class"; # used later - use <tt/> instead of , fewer chars!
$c="</tt>";
$d=counter;
$e=color;
s/\t/    /g; # convert tabs to spaces
s!<!&lt;!g; # htmlentity < and >
s!>!&gt;!g;
s!^#.+(?=$|\n)!$s=d>$&$c!gm; # directives
s!//.+!$s=c>$&$c!g; # inline comments
s|(['"]).*?(?<!\\)(\\\\)*\1|($h=$&)=~s!/!&#47;!g;"$s=s>$h$c"|smeg; # strings, might have 0 length - thanks @Einacio; work-around string that contain /* by converting them to HTML entities
s!/\*.*?\*/!$s=c>$&$c!smg; # multi-line comments
s!\b(_Packed|(au|go)to|break|c(ase|har|onst|ontinue)|d(efault|o|ouble)|e(lse|num|xtern)|f(loat|or)|if|int|long|re(gister|turn)|short|(un)?signed|s(izeof|tatic|truct|witch)|typedef|union|vo(id|latile)|while)\b!$s=r>$&$c!g; # reserved words, don't optimise this too much! - thanks @bwoebi
s!=(\w)>.+?$c!join"$c
$s=$1>",split$/,$&!smeg; # any multi-line string/comment, ensure s are repeated
s!\n!
!g; # strip newlines, replace with
, don't need 	 _or_
 - thanks @xfix!
print"

$_"

Now successfully highlights @xfix's entry.

Borrowed the idea to drop
 from @xfix's entry, thank you!

Example of output for @xfix's solution.


Normal and visual string reversion Write some code that acts as a cat program. That is, to input a string and output it as is. But the normal reversion of your code must output the normal reversion of the input string. And the visual reversion of your code must output the visual reversion of the input string.
The normal reversion is the reversed character sequence of a string. The visual reversion is the normal reversion with the characters ()[]{}<> replaced by )(][}{>< respectively.
You could use any codepage that has the characters ()[]{}<> and is published before this challenge to define characters. You must use the same codepage for all your code. Your original code must be valid in this codepage, and applying either of your reversed code to that should yield itself.
This is code-golf, shortest code in bytes wins.
Example
For the string AB(XY), its normal and visual reversions are )YX(BA and (YX)BA respectively.
If your code (in a hypothetical language) is AB(XY), then the code )YX(BA and (YX)BA should output the normal and visual reversions of the input string respectively. And AB(XY) should act as a cat program.

05AB1E, 16 bytes
Uses the fact that 05AB1E has a constant predefined to "()<>[]{}" and isn't affected the visually reversion.
Code:
,q‡"}{][><)("užR

Explanation:
,                 # Pop and print the input.
 q                # Quit.
  ‡"}{][><)("užR  # This part is ignored.

Try it online!

Reversed:
Ržu"()<>[]{}"‡q,

Explanation:
R                 # Reverse the input.
 žu               # Short for "()<>[]{}".
   "()<>[]{}"     # Push this string.
             ‡    # Transliterate (no-op, since everything is transliterated to itself).
              q   # Quit and implicitly print.
               ,  # This part is ignored.

Try it online!

Visually reversed:
Ržu")(><][}{"‡q,

Explanation:
R                 # Reverse the input.
 žu               # Short for "()<>[]{}".
   ")(><][}{"     # Push this string.
             ‡    # Transliterate (giving the visually reversed string).
              q   # Quit and implicitly print.
               ,  # This part is ignored.

Try it online!
Uses CP-1252 encoding.


Find the largest prime under a number... but only for the test cases The Code

Your program should take an input of n > 2 and output the largest prime less than or equal to n. You can choose how the number is input (standard input, read from a file, etc). For example:

Input  Output
3      3
9      7
28     23
486    479

Simple enough. And if a program passes all of the test cases it's gonna work fine, right?

The Underhanded

Too bad your program will only pass the test cases. It should work properly for 3, 9, 28, and 486 and no other numbers. Since this is an underhanded challenge, this shouldn't be obvious to a person glancing over the code.

Bonus points if the program still outputs something and if the output isn't obviously composite (getting 555 for 556 would be a little suspicious). This is a popularity contest, so the most popular answer wins. Which means the bonus points are completely meaningless. Oh well!

C
Results will be correct for the test cases, all others will be wrong for one or more reasons. The key is using the specifier %g which will round enough for the test cases but show the others as real numbers. Above inputs of 614, the results are all less than zero. Assuming inputs are in the integer domain!
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
    // Convert input
    double x = atof(argv[1]);

    // Cubic prime determination function
    double y = -1.386269645E-5 * x * x * x + 7.572051723E-3 * x * x + 5.774239804E-1 * x + 1.199953896;

    // Print output, use %g because it guarantees the shortest output
    printf("First prime less than or equal to %g is %g - happy day.\n", x, y);

    // Done!
    return 0;
}

Sample output:
$ ./fake 2
First prime less than or equal to 2 is 2.38498 - happy day.
$ ./fake 3
First prime less than or equal to 3 is 3 - happy day.
$ ./fake 4
First prime less than or equal to 4 is 3.62992 - happy day.
$ ./fake 5
First prime less than or equal to 5 is 4.27464 - happy day.
$ ./fake 6
First prime less than or equal to 6 is 4.9341 - happy day.
$ ./fake 7
First prime less than or equal to 7 is 5.6082 - happy day.
$ ./fake 8
First prime less than or equal to 8 is 6.29686 - happy day.
$ ./fake 9
First prime less than or equal to 9 is 7 - happy day.
$ ./fake 28
First prime less than or equal to 28 is 23 - happy day.
$ ./fake 486
First prime less than or equal to 486 is 479 - happy day.


Symbolic matrix multiplication There are lots of different ways to explain matrix multiplication. I'll stick with a single figure since I believe most people here are familiar with it (and the figure is very descriptive). If you want more detailed information, I suggest you visit the Wikipedia-article, or the explanation on WolframMathWorld.
Simple explanation:
Suppose you have two matrices, A and B, where A is 3-by-2, and B is 2-by-3. If you perform matrix multiplication on these to matrices, either AB, or BA you'll get the results below:

Challenge:
Implement symbolic matrix multiplication in you language. You shall take two matrices as input, where each element in the matrices are represented by an non-whitespace ASCII-character (code points 33-126). You must output the product of these matrices.
Rules regarding output:
A product of two entries shall not have any symbols in between. It's ab, not a*b, a·b, times(a,b) or something similar. It's aa, not a^2.
The sum of terms should have a space (ASCII code point 32) in between. It's a b, not a+b, plus(a,b) or something similar.
The rationale for those two rules is: All non white space characters are allowed as symbols in the matrices, thus using them as mathematical symbols would be messy. So, what you could normally write as a*b+c*d will be ab cd.
You may choose the order of the terms. ab cd, dc ab and cd ba are mathematically speaking the same, so you can choose the order here too. The order need not be consistent as long as it's mathematically correct.
Rules regarding matrix formatting:
A matrix can be entered in whatever format you like, except a single string with no delimiters between rows (this is because the output would be completely messed up). Both matrices must be inputted on the same format. All the examples below are valid ways of entering and outputting a matrix.
"ab;cd"     <- This will look awful, but it's still accepted.

"a,b\nc,d"

[[a,b],[c,d]]

[a, b]
[c, d]

I'm aware that this allows a lot of formats that will look messy, but the challenge is about multiplying matrices, not formatting the output.
General rules:

You may assume valid input. Matrix multiplication will always be possible with the given dimensions.
There will only be two matrices.
You may assume that the matrices are non-empty
Built-in functions are accepted (but probably a bit cumbersome due to the formatting requirements).
You may of course use escape characters in the input if necessary (\' instead of ').
Any standard input and output method is OK.

Test cases:
The two input matrices are shown with an empty line in between. The output is shown after Output:. When there are two output matrices then it's just to show other outputs that would be accepted.
Test case #1
Inputs:
[a]

[b]

Output:
[ab]
[ba]      <- Also OK

Test case #2
Inputs:
[a, b]
[1, 4]
[y, {]

[%, 4, 1]
[a, b, c]

Output:
[a% ba, a4 bb, a1 bc]
[1% 4a, 14 4b, 11 4c]
[y% {a, y4 {b, y1 {c]

Test case #3:
Inputs:
[1, 2, 3, 4]
[5, 6, 7, 8]
[9, 1, 2, 3]
[4, 5, 6, 7]

[a]
[b]
[c]
[d]

Output:
[1a 2b 3c 4d]
[5a 6b 7c 8d]
[9a 1b 2c 3d]
[4a 5b 6c 7d]

[d4 c3 b2 a1]      <-- Also OK
[d8 c7 b6 a5]
[1b 9a c2 3d]
[a4 b5 d7 6c]

If your response to the rules about requiring ab cd instead of a*b+c*d is: you should avoid cumbersome input/output formats, then I'd like note that the input and output formats are very flexible. The fact that you can't use * and + for products and sums might make it harder to use a simple built-in, but I don't consider that negative thing.

Haskell, 62 61 bytes

e=[]:e
a!b=[unwords.zipWith(++)r<$>foldr(zipWith(:))e b|r<-a]

Try it online! Example usage:
Prelude> [["a","b"],["c","e"]] ! [["f","g"],["h","i"]]
[["af bh","ag bi"],["cf eh","cg ei"]]

I found a way to get a transpose function in one byte shorter than using the import:
import Data.List;transpose
e=[]:e;foldr(zipWith(:))e

Old version with import: (62 bytes)
import Data.List
a!b=[unwords.zipWith(++)r<$>transpose b|r<-a]

Try it online!
This is quite similar to my answer to non-symbolic matrix multiplication: a!b=[sum.zipWith(*)r<$>transpose b|r<-a], substituting the multiplication (*) with string concatenation (++) and sum with unwords which concatenates a list of strings with a space in between. The import is needed for the transpose function, so all in all the transposition of the second matrix uses up half of the bytes ...

Old version without import: (64 bytes)
a![]=[];a!b=(unwords.zipWith(++)[h|h:_<-b]<$>a):a![s:t|_:s:t<-b]

Try it online!
With the import and transpose function taking up so much bytes, I tried solving the task without import. So far this approach turned out being two bytes longer, but it might be more golfable. Edit: The other approach at the top now beats the import!
The list comprehension [s:t|_:s:t<-b] gets the non-empty tails of the lists in b, using just [t|_:t<-b] to get the tails would be 4 bytes shorter (even beating the import version) but append an empty row like ["","",""] to the matrix which I suppose is not allowed.


From Programming Puzzles to Code Golf Your task is to write a program that outputs the exact string Programming Puzzles (trailing newline optional), but when all spaces, tabs, and newlines are removed it outputs Code Golf (trailing newline optional.)

Your byte count is the count of the first program, with spaces still there.

Notes

The spaces in Code Golf and Programming Puzzles will be removed as part of the removal, so plan accordingly.
In encodings where 0x09, 0x0A and 0x20 aren't tabs, newlines or spaces respectively, those chars will be removed.
If your code is

42  $@ rw$
@42

then that must output Programming Puzzles. Also, in the same language,

42$@rw$@42

must output Code Golf.

This is code-golf, so the shortest code in bytes wins! Good luck!

Python 2, 50 bytes

print["Code\40Golf","Programming Puzzles"][" ">""]

Try it online!

With all spaces removed:

print["Code\40Golf","ProgrammingPuzzles"]["">""]

Try that online!

Thanks to Stephen S for 3 bytes, and Erik the Outgolfer for 1


Generate all square sub-matrices of a given size You will be given a square matrix of integers M and another positive integer n, strictly smaller than the size of M. Your task is to generate all square sub-matrices of M of size n.

For the purposes of this challenge, a square sub-matrix is a group of adjacent rows and columns contained in M.

Input / Output Formats

You are free to choose any other reasonable formats, these are just some examples.

Input

A matrix in the native matrix type (if your language has one)
A 2D array (an array of 1D arrays, each corresponding to one row / one column)
A 1D array (since the matrix is always square)
A string (you chose the spacing, but please do not abuse this in any way), etc.

Output

A matrix of matrices.
A 4D array, where each element (3D list) represents the sub-matrices on a row/column.
A 3D array, where each element (2D list) represents a sub-matrix.
A string representation of the resulting sub-matrices, etc.

Specs

You may choose to take the size of M as input too. It is guaranteed to be at least 2.
The orientation of the output is arbitrary: you may choose to output the sub-matrices as lists of columns or lists of rows, but your choice must be consistent.
You can compete in any programming language and can take input and provide output through any standard method, while taking note that these loopholes are forbidden by default.
This is code-golf, so the shortest submission (in bytes) for every language wins.

Example

Given n = 3 and M:

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15 16

The possible 3x3 submatrices are:

+-------+        +--------+     1  2  3  4         1  2  3  4
|1  2  3| 4     1| 2  3 4 |     +--------+         +--------+
|5  6  7| 8     5| 6  7 8 |     |5   6  7|8       5| 6  7  8|
|9 10 11|12     9|10 11 12|     |9  10 11|12      9|10 11 12|
+-------+        +--------+     |13 14 15|16     13|14 15 16|
13 14 15 16     13 14 15 16     +--------+         +--------+

So the result would be:

[[[1, 2, 3], [5, 6, 7], [9, 10, 11]], [[2, 3, 4], [6, 7, 8], [10, 11, 12]], [[5, 6, 7], [9, 10, 11], [13, 14, 15]], [[6, 7, 8], [10, 11, 12], [14, 15, 16]]]

As noted above, an output of:

[[[1, 5, 9], [2, 6, 10], [3, 7, 11]], [[2, 6, 10], [3, 7, 11], [4, 8, 12]], [[5, 9, 13], [6, 10, 14], [7, 11, 15]], [[6, 10, 14], [7, 11, 15], [8, 12, 16]]]

would also be acceptable, if you choose to return the sub-matrices as lists of rows instead.

Test cases

The inputs M, n:

[[1,2,3],[5,6,7],[9,10,11]], 1
[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], 3
[[100,-3,4,6],[12,11,14,8],[0,0,9,3],[34,289,-18,3]], 2
[[100,-3,4,6],[12,11,14,8],[9,10,11,12],[13,14,15,16]], 3

And the corresponding outputs (sub-matrices given as lists of rows):

[[[1]],[[2]],[[3]],[[5]],[[6]],[[7]],[[9]],[[10]],[[11]]]
[[[1,2,3],[5,6,7],[9,10,11]],[[2,3,4],[6,7,8],[10,11,12]],[[5,6,7],[9,10,11],[13,14,15]],[[6,7,8],[10,11,12],[14,15,16]]]
[[[100,-3],[12,11]],[[-3,4],[11,14]],[[4,6],[14,8]],[[12,11],[0,0]],[[11,14],[0,9]],[[14,8],[9,3]],[[0,0],[34,289]],[[0,9],[289,-18]],[[9,3],[-18,3]]]
[[[100,-3,4],[12,11,14],[9,10,11]],[[-3,4,6],[11,14,8],[10,11,12]],[[12,11,14],[9,10,11],[13,14,15]],[[11,14,8],[10,11,12],[14,15,16]]]

Or, as lists of columns:

[[[1]],[[2]],[[3]],[[5]],[[6]],[[7]],[[9]],[[10]],[[11]]]
[[[1,5,9],[2,6,10],[3,7,11]],[[2,6,10],[3,7,11],[4,8,12]],[[5,9,13],[6,10,14],[7,11,15]],[[6,10,14],[7,11,15],[8,12,16]]]
[[[100,12],[-3,11]],[[-3,11],[4,14]],[[4,14],[6,8]],[[12,0],[11,0]],[[11,0],[14,9]],[[14,9],[8,3]],[[0,34],[0,289]],[[0,289],[9,-18]],[[9,-18],[3,3]]]
[[[100,12,9],[-3,11,10],[4,14,11]],[[-3,11,10],[4,14,11],[6,8,12]],[[12,9,13],[11,10,14],[14,11,15]],[[11,10,14],[14,11,15],[8,12,16]]]]

05AB1E, 8 bytes

2FεŒsù}ø

Try it online!

Explanation

2F            # 2 times do:
  ε    }      # apply to each element in the input matrix (initially rows)
   Œsù        # get a list of sublists of size input_2
        ø     # transpose (handling columns on the second pass of the loop)


Sample the Pareto Distribution The Pareto Distribution is a probability distribution that comes up a lot in nature. It has lots of special properties, such as an infinite mean. In this challenge, you will output a number sampled from this distribution.

The Pareto Distribution is defined to be greater than or equal to x with probability 1/x, for all x greater than or equal to 1.

Therefore, a number sampled from this distribution is greater than or equal to 1 with probability 1, greater than or equal to 2 with probability exactly 1/2, greater than or equal to 3 with probability exactly 1/3, greater than or equal to 11.4 with probability exactly 1/11.4, and so on.

Since you will sample this distribution, your program or function will take no input, and output a random number, with the above probabilities. However, if your program doesn't perfectly match the above probabilities due to floating-point impression, that's OK. See the bottom of the challenge for more details.

(This is called the Pareto Distribution with alpha 1 and lower bound 1, to be exact)

Here's 10 example draws from this distribution:

1.1540029602790338
52.86156818209856
3.003306506971116
1.4875532217142287
1.3604286212876546
57.5263129600285
1.3139866916055676
20.25125817471419
2.8105749663695208
1.1528212409680156

Notice how 5 of them are below 2, and 5 are above 2. Since this is the average result, it could have been higher or lower, of course.

Your answer only needs to be correct up to the limits of your floating point type, real number type, or whatever else you use, but you must be able to represent numbers at at least 3 decimal digits of precision, and represent numbers up to 1,000,000. If you're not sure whether something is OK, feel free to ask.

This is code golf.

Details about imprecision:

For each range [a, b], where 1 <= a < b, the ideal probability that the sample would fall in that range is 1/a - 1/b. The probability that your program produces a number in that range must be with 0.001 of 1/a - 1/b.  If X is the output of your program, it is required that |P(a <= X <= b) - (1/a - 1/b)| < 0.001.
Note that by applying the above rule with a=1 and b sufficiently large, it is the case that your program must output a number greater than or equal to 1 with at least probability 0.999. The rest of the time it may crash, output Infinity, or do whatever else.

I'm fairly certain that the existing submissions of the form 1/1-x or 1/x, where x is a random float in [0, 1) or (0, 1) or [0, 1], all satisfy this requirement.

MATL, 3 bytes
1r/

Try it online! Or estimate the resulting probabilities by running it 10000 times.
Explanation
1    % Push 1
r    % Push random number uniformly distributed on the open interval (0,1)
/    % Divide. Implicitly display


Calculate the MU-numbers The first two MU-numbers are 2 and 3.  Every other MU-number is the smallest number not yet appeared that can be expressed as the product of two earlier distinct MU-numbers in exactly one way.

Here are the first 10

2, 3, 6, 12, 18, 24, 48, 54, 96, 162

Task

Given a positive number calculate and output the nth MU-number.

This is a code-golf competition so you should aim to make your source code as small as possible.

OEIS A007335

Pyth, 22 21 bytes
@u+Gfq2l@GcLTGheGQhB2

Try it online. Test suite.
0-indexed.
Explanation
@u+Gfq2l@GcLTGheGQhB2Q    Implicitly append Q and read+eval input to it.
                  hB2     Take the list [2, 2 + 1].
 u               Q        Put the list in G and apply this Q times:
               eG           Get last number in G.
              h             Add one.
    f                       Starting from that, find the first T such that:
          cLTG                Divide T by each of the numbers in G.
        @G                    Find the quotients that are also in G.
       l                      Get the number of such quotients.
     q2                       Check that it equals 2.
  +G                        Append that T to G.
@                    Q    Get the Q'th number in G.


Constructible n-gons A constructible \$n\$-gon is a regular polygon with n sides that you can construct with only a compass and an unmarked ruler.
As stated by Gauss, the only \$n\$ for which a \$n\$-gon is constructible is a product of any number of distinct Fermat primes and a power of \$2\$ (ie. \$n = 2^k \times p_1 \times p_2 \times ...\$ with \$k\$ being an integer and every \$p_i\$ some distinct Fermat prime).
A Fermat prime is a prime which can be expressed as \$2^{2^n}+1\$ with \$n\$ a positive integer. The only known Fermat primes are for \$n = 0, 1, 2, 3 \text{ and } 4\$
The challenge
Given an integer \$n>2\$, say if the \$n\$-gon is constructible or not.
Specification
Your program or function should take an integer or a string representing said integer (either in unary, binary, decimal or any other base) and return or print a truthy or falsy value.
This is code-golf, so shortest answer wins, standard loopholes apply.
Relevant OEIS
Examples
3 -> True
9 -> False
17 -> True
1024 -> True
65537 -> True
67109888 -> True
67109889 -> False

Jelly, 7 5 bytes

Thanks to Sp3000 for saving 2 bytes.

ÆṪBSỊ

Uses the following classification:

  These are also the numbers for which phi(n) is a power of 2.

Where phi is Euler's totient function.

ÆṪ        # Compute φ(n).
  B       # Convert to binary.
   S      # Sum bits.
    Ị     # Check whether it's less than or equal to 1. This can only be the
          # case if the binary representation was of the form [1 0 0 ... 0], i.e.
          e# a power of 2.

Try it online!

Alternatively (credits to xnor):

ÆṪ’BP
ÆṪ        # Compute φ(n).
  ’       # Decrement.
   B      # Convert to binary.
    P     # Product. This is 1 iff all bits in the binary representation are
          # 1, which means that φ(n) is a power of 2.

A direct port of my Mathematica answer is two bytes longer:

ÆṪ        # Compute φ(n).
  µ       # Start a new monadic chain, to apply to φ(n).
   ÆṪ     # Compute φ(φ(n)).
      H   # Compute φ(n)/2.
     =    # Check for equality.


Nonogram line brute-force solving Background

Nonogram, also known as Picross or Griddlers, is a puzzle where the objective is to determine if each cell on the 2D grid should be colored or left blank, using the numbers of consecutive colored cells on each line.

The following is an example Nonogram puzzle with solution.

The problem is, some commercial Nonogram games/mobile apps have puzzles which are not solvable by hand (e.g. have multiple solutions, or require deep backtracking). However, they also offer some lives to the player, where one life is lost when you try to color a cell whose correct answer is blank. So now it's time to brute-force those nasty "puzzles"!

In order to simplify the task, imagine just one line with its clue and nothing else:

3 7 | _ _ _ _ _  _ _ _ _ _  _ _ _ _ _

The [3,7] are the clues, and the line length is 15 cells. Since it has multiple possible solutions, we need to risk some lives in order to fully solve this line (i.e. determine all colored cells).

Challenge

Given a line with clues (a list of positive integers) and the line length, find the maximum number of lives you will lose, assuming that you brute-force the line with optimal strategy.

Note that you always guess colored cells. In actual games, guessing empty cells (either right or wrong) have no effect on your lives, so you can't "solve" the puzzle that way.

Also, you can assume the input always represents a valid Nonogram line, so you don't need to worry about something like [6], 5.

Explanation

Let's look at some simpler examples first.

[1,2], 5

There are exactly three possibilities for this line (O is a colored cell, . is an empty one):

O . O O .
O . . O O
. O . O O

If we try coloring cell 0 (0-based index from left), one of the following happens:

The cell is correctly colored. Now we have two possibilities, and we can choose between cell 2 and cell 4 in order to fully solve the line. Either case, we will lose one life in the worst case.
The cell is empty, and we lose a life. In this case, we have already identified the unique solution to this line, so we're done with 1 life lost.

Therefore, the answer for [1,2], 5 is 1.

[5], 10

Binary search? Nope.

The most obvious first choice is 4 or 5, which will reveal one possibility if it's blank (at a cost of 1 life). Let's say we chose 4 first. If cell 4 is indeed colored, we extend it to the left, i.e. try 3, 2, 1 and 0 until a life is lost (or cell 0 is colored, then we end up spending no lives at all). Whenever a life is lost, we can uniquely determine the solution, e.g. if we see something like this:

_ _ X O O _ _ _ _ _

then we already know the answer is this:

. . . O O O O O . .

Therefore, the answer for [5], 10 is also 1.

[3,7], 15

Start with cell 11, which, if empty, will reveal the following solution right away.

O O O . O O O O O O O X . . .

Then try 12, which, if empty, gives two possibilities which can be solved at the cost of 1 extra life.

O O O . . O O O O O O O X . .
. O O O . O O O O O O O X . .

Now try 2. If empty, it leads to three possibilities which can be solved similarly to the [1,2], 5 example.

. . X O O O . O O O O O O O .
. . X O O O . . O O O O O O O
. . X . O O O . O O O O O O O

If you keep minimizing the risk in this manner, you can reach any solution with max. 2 lives spent.

Test Cases

[1,2] 5 => 1
[2] 5 => 2
[1] 5 => 4
[] 5 => 0
[5] 10 => 1
[2,1,5] 10 => 0
[2,4] 10 => 2
[6] 15 => 2
[5] 15 => 2
[4] 15 => 3
[3,7] 15 => 2
[3,4] 15 => 3
[2,2,4] 15 => 4
[1,1,1,1,1,1,1] 15 => 2

[2,1,1,3,1] 15 => 3
[1,1,1,2,1] 15 => 5

For the last two cases, the optimal strategy is not going through the minimum blanks, but simply going from left to right (or right to left). Thanks to @crashoz for pointing it out.

Rules

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

Bounty

If someone comes up with a polynomial-time algorithm (with the proof of correctness), I will award +100 bounty to such a solution.

Ruby, 85 bytes

f=->l,n,s=n-l.sum-l.size+1{*a,b=l;b&&s>0?(a[0]?1+f[a,n-b-2,s-1]:(n.to_f/b).ceil-1):0}

Try it online!

Explanation

The first step is to establish a recursive divide and conquer strategy to solve subproblems.
I will use the variables \$l=[l_1,l_2,...,l_x]\$ for the list of clues, \$x\$ for the number of clues and \$n\$ for the number of cells.

Try to fit the last clue \$l_x\$:
We test the cell at \$n-l_x\$
(1) If it's empty: then all of the clues are before \$n-l_x\$.
So we lose a life and we call recursively \$1+f(l,n-l_x)\$
(2) If it's colored:
We are not sure how to place the last clue, so we test every cells to the right until finding an empty one
The worst case is finding the empty cell at the last index, we lose a life, but we have placed the last clue
so we can call recursively \$1+f(\tilde{l},n-l_x-2)\$ where \$\tilde{l}\$ is \$l\$ without the last clue.

So we can get the number of lives with this function
$$
f(l,n)=\begin{cases}
  0, & \text{if } \sum_1^xl_i+x-1 \geq n\\
  \lceil \frac{n}{l_x} \rceil - 1 & \text{if } x= 1\\
  1+\max\begin{cases}
f(l,n-l_x)\\
f(\tilde{l},n-l_x-2)
  \end{cases}, & \text{otherwise}
\end{cases}
$$

Here is an example _ are unknown, X is a known space, O is a known colored cell and L is life lost

[2,2,4] 15                  _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
(1) -> [2,2,4] 11           _ _ _ _ _ _ _ _ _ _ _ L X X X
    (1) -> [2,2,4] 7        _ _ _ _ _ _ _ L X X X L X X X
        0                   X X X L X X X L X X X L X X X
    (2) -> [2,2] 5          _ _ _ _ _ X O O O O L L X X X
        0                   O O X O O X O O O O L L X X X
(2) -> [2,2] 9              _ _ _ _ _ _ _ _ _ X O O O O L
    (1) -> [2,2] 7          _ _ _ _ _ _ _ L X X O O O O L
        (1) -> [2,2] 5      _ _ _ _ _ L X L X X O O O O L
            0               O O X O O L X L X X O O O O L
        (2) -> [2] 3        _ _ _ X O O L L X X O O O O L
            1               O O L X O O L L X X O O O O L
    (2) -> [2] 5            _ _ _ _ _ X O O L X O O O O L
        2                   O O L L X X O O L X O O O O L

It makes a binary tree, to get the number of lives lost, we just need to count the maximum height of the tree.
However this makes it \$\mathcal{O}(2^n)\$ because we evaluate all of the branches. We can do better.

Let's define a cost function \$h\$ that will help us "choose" the right branch at each step.

$$
h(l,n)=n - \sum_1^xl_i-x+1
$$

\$h\$ counts the number of superfuous spaces we have if we pack all the clues with one space in between.
So it is essentially an indicator of how much lives we are going to need to solve the instance, the higher it is,
the more lives are necessary. The idea is to apply this indicator on our recursive formula.

By definition of \$h\$ we have,
$$
\begin{align}
h(l,n-l_x) &= n - l_x - \sum_1^xl_i-x+1\\
& =(n - \sum_1^xl_i-x+1) - l_x\\
& = h(l,n) - l_x
\end{align}
$$

And,
$$
\begin{align}
h(\tilde{l},n-l_x-2) &= n - l_x - 2 - \sum_1^{x-1}l_i-(x-1)+1\\
& =(n - \sum_1^xl_i-x+1) - 1\\
& = h(l,n) - 1
\end{align}
$$

Then,
$$
h(l,n)=\begin{cases}
  \leq 0, & \text{if } \sum_1^xl_i+x-1 \geq n\\
  n - l_x, & \text{if } x=1\\
  \max\begin{cases}
h(l,n-l_x)+l_x\\
h(\tilde{l},n-l_x-2)+1
  \end{cases}, & \text{otherwise}
\end{cases}
$$

We want to maximize \$h\$ at each step to get the worst case so let's check the difference between the two expressions in the recurrence

$$
[h(l,n-l_x)+l_x] - [h(\tilde{l},n-l_x-2)+1]\\
\begin{align}
 &= n-l_x-n - \sum_1^xl_i-x+1 + l_x - [n-l_x-2 -\sum_1^{x-1}l_i-(x-1)+1+1]\\
 &=-2
\end{align}
$$

$$
\begin{align}
  [h(l,n-l_x)+l_x] - [h(\tilde{l},n-l_x-2)+1] &=-2\\
  [h(l,n-l_x)+l_x] - [h(\tilde{l},n-l_x-2)+1] &< 0\\
  [h(l,n-l_x)+l_x] &< [h(\tilde{l},n-l_x-2)+1]
\end{align}
$$
So the 2nd expression is always the max, we can remove the first one

$$
h(l,n)=\begin{cases}
  \leq 0, & \text{if } \sum_1^xl_i+x-1 \geq n\\
  n - l_x, & \text{if } x=1\\
  h(\tilde{l},n-l_x-2)+1 & \text{otherwise}
\end{cases}
$$

Finally this recursive definition of \$h\$ shows us that option (2) in function \$f\$ is always the worst case (giving the maximum number of possibilities i.e. maximizing \$h\$)

$$
f(l,n)=\begin{cases}
  0, & \text{if } \sum_1^xl_i+x-1 \geq n\\
  \lceil \frac{n}{l_x} \rceil - 1 & \text{if } x= 1\\
  1+ f(\tilde{l},n-l_x-2), & \text{otherwise}
\end{cases}
$$

Every step we decrease \$n\$ by at least 3 and there is now a single recursive call, complexity is \$\mathcal{O}(n)\$


Create a kind of quine, such that the program prints one character of itself, then two, then three and so on Create quine variant such that the program prints its first character, then the first two, then three and so on until the whole program is printed.
Example
Suppose your code is @@@@@2 in some language. Then the output should be
@
@@
@@@
@@@@
@@@@@
@@@@@2

in that order, each line separated by a newline.
The winner is the shortest quine like this.

Jelly, 10 bytes

“;⁾vṾÄY”vṾ

Try it online!

How it works

“;⁾vṾÄY”vṾ  Main link. No arguments.

“;⁾vṾÄY”    Set the return value to the string ';⁾vṾÄY'.
         Ṿ  Uneval; yield a string representation of the string, i.e., '“;⁾vṾÄY”'.
        v   Dyadic eval; execute the string to the left, passing the string to the
            right as argument.
  ⁾vṾ         Literal; yield 'vṾ'.
 ;            Concatenate the argument ('“;⁾vṾÄY”') and 'vṾ', yielding '“;⁾vṾÄY”vṾ'.
     Ä        Accumulate; take the cumulative sum.
              Since string addition is concatenation in Python (and Jelly doesn't do
              type checks), this yields all prefixes of the string.
      Y       Join the prefixes, separated by linefeeds.


Solve a Matchstick puzzle On puzzling SE there are what are called "matchstick problems" in which math is written in match sticks and you are allowed to move a certain number of them to get a certain property.

In this question we will be considering only integers represented in a 7-segment display format.  Here are all 10 digits in that format:

 __          __   __          __    __    __    __    __
|  |     |   __|  __|  |__|  |__   |__      |  |__|  |__|
|__|     |  |__   __|     |   __|  |__|     |  |__|   __|

Each segment of the display is one "match-stick" which can be moved independently of the rest of the number.  Matchsticks are indivisible and indestructible, the cannot be broken or removed by any means.

A common puzzle is to take a number given in base 10 and try to make the largest number possible in a given number of moves.  A move is considered to be one movement of a matchstick from any occupied slot to any other unoccupied slot.  You are perfectly permitted to make new digits on either side of the number, for example 0 can be made into 77 give 3 moves

 __      __  __      __   __      __   __
|  |    |  |        |  |    |       |    |
|__| ,   __|     ,     |      ,     |    |

However you may not make one slot into 2 or make new slots between existing ones, for example turning a 4 into an 11 in the middle of a number or inserting new digits in between existing ones.  Each move need not make a proper number but the final result should be a proper number in the base 10 seven segment display.  You need not use every move if you do not wish to.  Unlike on puzzling this is a [tag:close ended question] you may not use any operators (multiplication, exponentiation, etc.) or mathematical constants (Pi, Graham's number, etc.) in your answers.

Task

Write a program or function that takes a number and a number of moves as input and returns the largest number that can be made with that many moves on the original number.

This is a code-golf question so answers will be scored in bytes, with less bytes being better.

Test Cases

n, moves -> max
0, 1     -> 9
0, 3     -> 77
0, 4     -> 111
8, 3     -> 74
220, 1   -> 320
220, 2   -> 520
220, 3   -> 7227
220, 4   -> 22111
220, 5   -> 32111
747, 1   -> 747
747, 2   -> 7171
747, 3   -> 7711

Related

JavaScript (ES6), 297 286 279 267 bytes

Takes input in currying syntax (s)(k), where s is an array of digit characters and k is the number of moves (integer).

s=>k=>(B=(n,b=0)=>n?B(n^n&-n,b+1):b,b=[...p='u"[k,iy#}m'].map(c=>c.charCodeAt()+2),r=[],g=(n,d='')=>n?n>0&&b.map((v,i)=>g(n-B(v),d+i)):r.push(d))(s.reduce((s,c)=>s+B(b[c]),M=0))&&b.map((_,j)=>r.map(n=>M=[...n+p].reduce((t,d,i)=>t+B(b[d]^b[s[i-j]]),0)>k*2|+n<M?M:n))|M

Test cases

let f=

s=>k=>(B=(n,b=0)=>n?B(n^n&-n,b+1):b,b=[...p='u"[k,iy#}m'].map(c=>c.charCodeAt()+2),r=[],g=(n,d='')=>n?n>0&&b.map((v,i)=>g(n-B(v),d+i)):r.push(d))(s.reduce((s,c)=>s+B(b[c]),M=0))&&b.map((_,j)=>r.map(n=>M=[...n+p].reduce((t,d,i)=>t+B(b[d]^b[s[i-j]]),0)>k*2|+n<M?M:n))|M

console.log("0   / 1 -> " + f([..."0"  ])(1)) // -> 9
console.log("0   / 3 -> " + f([..."0"  ])(3)) // -> 77
console.log("0   / 4 -> " + f([..."0"  ])(4)) // -> 111
console.log("8   / 3 -> " + f([..."8"  ])(3)) // -> 74
console.log("220 / 1 -> " + f([..."220"])(1)) // -> 320
console.log("220 / 2 -> " + f([..."220"])(2)) // -> 520
console.log("220 / 3 -> " + f([..."220"])(3)) // -> 7227
console.log("220 / 4 -> " + f([..."220"])(4)) // -> 22111
console.log("220 / 5 -> " + f([..."220"])(5)) // -> 32111
console.log("747 / 1 -> " + f([..."747"])(1)) // -> 747
console.log("747 / 2 -> " + f([..."747"])(2)) // -> 7171
console.log("747 / 3 -> " + f([..."747"])(3)) // -> 7711

How?

Shape data and helper function

The array b describes the shapes of the digits as 7-bit integers, where each bit is a segment:

For instance, the shape of "7" is 0b0100101 = 37.
The helper function B() returns the number of 1's in the binary representation of a given number:

B = (n, b = 0) => n ? B(n ^ n & -n, b + 1) : b

Step #1

We first count the number of matchsticks used in the input number:

s.reduce((s, c) => s + B(b[c]), 0)

Step #2

We pass this value to the recursive function g(), which populates a list r with all numbers that can be built with exactly this number of matchsticks:

g = (n, d = '') =>
  n ?
    n > 0 &&
    b.map((v, i) => g(n - B(v), d + i))
  :
    r.push(d)

For instance, g(5) will load [ '17', '2', '3', '5', '71' ] into r.

Step #3

We now have to select the highest number M in r which can actually be obtained from the input number, within the allowed number of moves k.

Because each number n in r uses exactly as many matchsticks as the input number s, the number of moves required to transform s into n equals half the number of segment differences between each of their digits.

The number of segment differences between two digits x and y is given by the number of 1's in the binary representation of b[x] XOR b[y].

Finally, it's important to note that we need to try several possible digit alignments, because the first digit of s is not necessarily mapped to the first digit of n. The shift between the digits is given by the variable j in the code.


Minimum cost block diagonalisation Consider binary block diagonal matrices which have square blocks of 1s on the main diagonal, and are 0 everywhere else. Let's call such matrices "valid" matrices.

For example, here are some valid 4x4 matrices:

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

Note that an alternative way of describing such matrices is that there is a chain of square 1 blocks from the top-left to the bottom-right, touching corner to corner, and everywhere else is 0.

For contrast, here are some invalid 4x4 matrices:

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

You will be given an n by n binary matrix as input – what is the minimum number of 0 bits you'll need to set to 1 in order to get a valid matrix?

You may write a function or program taking in any convenient string, list or matrix format representing an n by n matrix of 0s and 1s (as long as it isn't preprocessed). Rows must be clearly separated in some way, so formats like a 1D array of bits are not allowed.

This is code-golf, so the goal is to minimise the number of bytes in your program.

Examples

For example, if the input is

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

then the answer is 5, since you can set five 0 bits to 1 to get:

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

and this is the minimum number required. However, if the input was

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

then the answer is 24, since the only valid 5x5 matrix where the top-right is 1 is the matrix of all 1s.

Test cases

Tests are represented here as a 2D array of integers.

[[0]] -> 1
[[1]] -> 0
[[0,1],[0,0]] -> 3
[[1,0],[0,0]] -> 1
[[0,0,0],[0,1,0],[0,0,0]] -> 2
[[0,1,0],[0,0,0],[0,1,0]] -> 7
[[0,1,0],[1,0,0],[0,0,1]] -> 2
[[1,1,1],[1,1,1],[1,1,1]] -> 0
[[0,0,0,0],[0,0,1,0],[0,1,0,0],[0,0,0,0]] -> 4
[[0,0,1,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]] -> 8
[[0,0,1,0],[0,0,0,0],[0,0,0,0],[0,0,1,0]] -> 14
[[0,0,1,0],[0,0,0,0],[0,0,0,0],[0,1,0,0]] -> 14
[[0,0,0,0,0],[0,0,0,0,0],[0,1,0,0,0],[0,0,0,0,1],[0,0,0,0,0]] -> 7
[[0,0,0,0,0],[0,0,0,0,0],[1,0,0,0,0],[0,0,0,0,1],[0,0,0,0,0]] -> 11
[[0,0,0,0,0],[0,0,1,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,1]] -> 5
[[0,0,0,0,1],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]] -> 24
[[0,0,0,1,0],[0,0,0,0,1],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]] -> 23
[[0,1,0,0,0],[1,0,0,0,0],[0,0,1,0,0],[0,0,0,0,1],[0,0,0,1,0]] -> 4
[[0,1,1,1,0],[0,1,1,0,1],[0,1,1,1,0],[0,1,0,0,1],[0,0,0,0,0]] -> 14

Notes

Related challenge: Print a Block-Diagonal Matrix
Inspiration: Freedom Factory, Google Code Jam 2016 Problem 2D

MATL, 46 43 bytes

nX^tQt:qZ^!tsb=Z)"@!"@1$l]@n$YdG-Q?6MG>zvX<

Input is a 2D array with semicolon as row separator. For example, the input for the last test case is

[0,1,1,1,0;0,1,1,0,1;0,1,1,1,0;0,1,0,0,1;0,0,0,0,0]

Try it online! Or verify all test cases (code slightly modified to take all inputs; the results appear after a few seconds)

Explanation

Let the input be an N×N matrix. The code first computes all (N+1)-tuples of block sizes that produce the appropriate matrix size. For example, for N=4 the tuples are 0 0 0 0 4, 0 0 0 1 3, ..., 4 0 0 0 0. For each tuple it builds the block-diagonal matrix with those block sizes. It then checks if the matrix covers all the 1 entries in the input, and if so takes note of the number of 1 entries that were not present in the input. The final result is the minimum of all the obtained numbers.

nX^      % Implicit input  an N×N matrix. Get N
t        % Duplicate N
Qt:q     % Vector [0 1 ... N]
Z^       % Cartesian power. Gives 2D array
!ts      % Transpose, duplicate, sum of each column
b=       % Logical vector that equals true if the sum is N
Z)       % Filter columns according to that. Only keep columns that sum to N. Each
         % column is the size of one block
"        % For each column
  @      %   Push that column
  "      %   For each entry of that column
    @    %     Push that entry
    1$l  %     Square matrix with that size, filled with 1
  ]      %   End
  @n     %   Column size. This is the number of blocks in the block-diagonal matrix
  $Yd    %   Build block-diagonal matrix from those blocks
  G-Q    %   Subtract input matrix element-wise, and add 1
  ?      %   If all entries are nonzero (this means each that entry that is 1 in the
         %   block-diagonal matrix is also 1 in the input matrix)
    6M   %   Push block-diagonal matrix again
    G>   %   For each entry, gives 1 if it exceeds the corresponding entry of the
         %   input, that is, if the block-diagonal matrix is 1 and the input is 0
    z    %   Number of 1 entries
    v    %   Concatenate vertically with previous values
    X<   %   Take minimum so far
         %   Implicit end
         % Implicit end
         % Implicit display


Connecting the Dots: Counting n²-gons in the n×n Grid The recent volume of MAA's Mathematics Magazine had an article "Connecting the Dots: Maximal Polygons on a Square Grid" by Sam Chow, Ayla Gafni, and Paul Gafni about making (very convex) \$n^2\$-gons where each vertex is a different point of the \$n \times n\$ grid.

One is not allowed to have two consecutive segments be collinear, since that would merge two sides of the polygon.

For example, the following images are from Figures 2 and 10 in the Chow, Gafni, Gafni paper, which show a \$49\$-gon on the \$7 \times 7\$ grid of dots and a \$100\$-gon on the \$10 \times 10\$ grid of dots:

In the paper, the authors show that it is possible to form these \$n^2\$-gons for all integers \$n \geq 2\$ except for \$n=3\$ and \$n=5\$.
Challenge
This fastest-code challenge will have you count the number of "essentially different" \$n^2\$-gons on the \$n \times n\$ grid, where two polygons are considered the same if you can reflect or rotate one to match the other.
To score this, I will run the code on my machine—a 2017 MacBook with an Intel chip and 8GB of RAM—for five minutes with increasing sizes of \$n\$. Your score will be the maximum value of \$n\$ that your program can produce, and ties will be broken by the amount of time it took to get to that value.
Small test cases
(From the Chow, Gafni, Gafni paper.)

When \$n = 2\$ there is only one \$4\$-gon, the square.
When \$n = 3\$ there are no \$9\$-gons.
When \$n = 4\$ there is only one \$16\$-gon:

When \$n = 5\$ there are no \$25\$-gons.

Python 3 + Z3, N=5
Not 100% sure if this is correct. Basically a standard SAT/SMT coding of the Hamiltonian cycle problem, with additional clauses to block intersecting diagonals and collinear segments. Each time a solution is found all of its distinct rotations/flips are blocked. I've run it up to N=6 (2120 solutions found), which took 30 minutes.
Edit: I just realized that this only allows edges between adjacent grid points, but this restriction wasn't intended by the challenge. Oh well, I'll leave it up for now.

import collections
import heapq
import itertools
import math
import random
import time
import sys
import z3

show_paths = len(sys.argv) >= 2 and 'show' in sys.argv[1]

if show_paths:
    import numpy as np
    import pylab as plt
    from matplotlib import collections  as mc

    def show_path(path):
        lines = list(zip(path, path[1:] + path[:1]))
        c = np.array([(1, 0, 0, 1), (0, 1, 0, 1), (0, 0, 1, 1)])
        lc = mc.LineCollection(lines, colors=c, linewidths=2)
        fig, ax = plt.subplots()
        ax.add_collection(lc)
        ax.autoscale()
        ax.margins(0.1)
        plt.show()

def compute_min_distances(C, distance_matrix, starting_points, banned):
    min_distances = collections.defaultdict(lambda: float('inf'))
    open_set = []
    for i in starting_points:
        state = (i, C[i])
        min_distances[state] = 1
        open_set.append((1, state))
    while open_set:
        d, state = open_set.pop()
        if d > min_distances[state]:
            continue
        i, delta = state
        x0, y0 = c0 = C[i]
        for j, _ in distance_matrix[i]:
            if j in banned:
                continue
            x1, y1 = c1 = C[j]
            delta1 = (x1 - x0, y1 - y0)
            if delta in (delta1, (x0 - x1, y0 - y1)):
                continue
            state = (j, delta1)
            if d + 1 < min_distances[state]:
                min_distances[state] = d + 1
                heapq.heappush(open_set, (d + 1, state))
    distance_array = [float('inf') for _ in distance_matrix]
    distance_array[0] = 0
    for (i, _), d in min_distances.items():
        distance_array[i] = min(distance_array[i], d)
    return distance_array

def point_orientations(p, n):
    for (x, y) in (p, p[::-1]):
        for x1 in (x, n - 1 - x):
            for y1 in (y, n - 1 - y):
                yield (x1, y1)

def path_orientations(path, n):
    orientations = list(zip(*map(lambda p: point_orientations(p, n), path)))
    for o in orientations:
        i = o.index((0, 0))
        if o[i - 1] == (0, 1):
            o = o[::-1]
            i = (len(o) - 1) - i
        if o[(i + 1) % len(o)] != (0, 1):
            continue
        yield o[i:] + o[:i]

start_time = time.time()
for N in itertools.count(2):
    print("starting n = %d..." % N)
    solver = z3.Solver()
    C = [(x, y) for x in range(N) for y in range(N)]
    C_inv = {c : i for i, c in enumerate(C)}
    bit_width = math.ceil(math.log(N * N + 1, 2))
    P = [z3.BitVec('P_%d' % i, bit_width) for i in range(N * N)]
    V = [z3.BitVec('V_%d' % i, bit_width) for i in range(N * N)]
    for v in V:
        solver.add(z3.ULT(v, N * N))
    A = [[] for _ in range(N * N)]
    for i, (x, y) in enumerate(C):
        for dx, dy in itertools.product(range(-1, 2), repeat=2):
            if not (dx or dy):
                continue
            try:
                A[i].append(C_inv[(x + dx, y + dy)])
            except KeyError:
                pass
    H = [[(j, z3.Bool('H_%d_%d' % (i, j))) for j in A[i]] for i in range(N * N)]
    start = C_inv[(0, 1)]
    min_distances = compute_min_distances(C, H, [start], {0})
    end0, end1 = C_inv[(1, 0)], C_inv[(1, 1)]
    min_distances_rev = compute_min_distances(C, H, [end0, end1], {0, start})
    for i, (d0, d1) in enumerate(zip(min_distances, min_distances_rev)):
        if i not in (0, start):
            solver.add(z3.UGE(P[i], d0))
            solver.add(z3.ULE(P[i], N * N - d1))
    H_t = [[] for _ in range(N * N)]
    for i, row in enumerate(H):
        x0, y0 = C[i]
        for j, v in row:
            H_t[j].append(v)
            if i == 0:
                e = P[j] == 1
            elif j == 0:
                e = P[i] == (N * N - 1)
            else:
                e = P[j] == (P[i] + 1)
            clauses = [V[i] == j, e]
            x1, y1 = C[j]
            dy = y1 - y0
            dx = x1 - x0
            blocked = []
            if dy and dx:
                x_m = min(x0, x1)
                y_m = min(y0, y1)
                if dy == dx:
                    blocked.append(((x_m + 1, y_m), (x_m, y_m + 1)))
                else:
                    blocked.append(((x_m, y_m), (x_m + 1, y_m + 1)))
                blocked.append(blocked[-1][::-1])
            x2 = x1 + dx
            y2 = y1 + dy
            if all(0 <= c < N for c in (x2, y2)):
                blocked.append(((x1, y1), (x2, y2)))
            for (c0, c1) in blocked:
                k = C_inv[c0]
                l = C_inv[c1]
                clauses.append(z3.Not(next(w for m, w in H[k] if m == l)))
            solver.add(z3.Implies(v, z3.And(*clauses)))
    solver.add(P[0] == 0)
    solver.add(P[start] == 1)
    for row in H_t:
        solver.add(z3.PbEq([(v, 1) for v in row], 1))
    solutions = set()
    old_len = 0
    while solver.check() == z3.sat:
        model = solver.model()
        successors = [int(str(model.eval(v))) for v in V]
        path = [0]
        while len(path) < N * N:
            path.append(successors[path[-1]])
        path = tuple(C[i] for i in path)

        if show_paths:
            show_path(path)

        orientations = set(path_orientations(path, N))
        assert not any(reoriented in solutions for reoriented in orientations)
        solutions.add(path)
        for reoriented in orientations:
            successor = {}
            for p0, p1 in zip(reoriented, reoriented[1:] + reoriented[:1]):
                successor[C_inv[p0]] = C_inv[p1]
            solver.add(z3.Not(z3.And(*[v == successor[i] for i, v in enumerate(V)])))
        s = "%d solutions found so far... (%.1f seconds elapsed)" % (len(solutions), time.time() - start_time)
        sys.stdout.write(s + max(0, old_len - len(s)) * ' ' + '\r')
        sys.stdout.flush()
        old_len = len(s)
    sys.stdout.write(' ' * old_len + '\r')
    sys.stdout.flush()
    end_time = time.time()
    print("%d solution%s found for n = %d in %.2g seconds" % (len(solutions), 's' * (len(solutions) != 1), N, end_time - start_time))
    start_time = end_time