Sharing pizza fairly The difficulty with sharing pizza with friends is that it is hard to make sure that everyone gets the same amount of pepperoni on their slice. So, your task is to decide how to fairly slice a pizza so that everyone is happy.

Directions

Write a program that, given a list of the positions of pepperonis on a circular pizza and the number of slices to be made, outputs a list of the angles that the pizza should be cut at so that each slice has the same amount of pepperoni on it.

The pizza has only one topping: pepperoni.
Your friends don't care about the size of their slice, just that they are not cheated out of any pepperoni.
The pizza is a circle centered on the origin (0, 0) and with a radius of 1.
The pepperonis are circles that are centered wherever the input says they are centered and have a radius of 0.1
Take input as an integer that represents the number of slices to be made and a list of ordered-pairs that represent the positions of the pepperonis on a cartesian coordinate system. (In any reasonable format)
Output should be a list of angles given in radians that represents the positions of the "cuts" to the pizza (in the range 0 <= a < 2pi). (In any reasonable format) (Precision should be to at least +/- 1e-5.)
You can have partial pieces of a pepperoni on a slice (eg. If a pizza has one pepperoni on it and it needs to be shared by 10 people, cut the pizza ten times, all cuts slicing through the pepperoni. But make sure it's fair!)
A cut can (may have to) slice through multiple pepperonis.
Pepperonis may overlap.

Examples

Input:

8 people, pepperonis: (0.4, 0.2), (-0.3, 0.1), (-0.022, -0.5), (0.3, -0.32)

Possible valid output:

slices at:
0, 0.46365, 0.68916, 2.81984, 3.14159, 4.66842, 4.86957, 5.46554

Here is a visualisation of this example (everyone gets half a pepperoni):

More examples:

Input: 9 people, 1 pepperoni at: (0.03, 0.01)
Output: 0, 0.4065, 0.8222, 1.29988, 1.94749, 3.03869, 4.42503, 5.28428, 5.83985

Input: 5, (0.4, 0.3), (0.45, 0.43), (-0.5, -0.04)
Output: 0, 0.64751, 0.73928, 0.84206, 3.18997

Scoring

This is code-golf, so least number of bytes wins.

Mathematica, 221 bytes

f=(A=Pi.01Length@#2/#;l=m/.Solve[Norm[{a,b}-m{Cos@t,Sin@t}]==.1,m];k=(l/.{a->#,b->#2})&@@@#2;d=1.*^-5;For[Print[h=B=0];n=1,n<#,h+=d,(B+=If[Im@#<0,0,d(Max[#2,0]^2-Max[#,0]^2)/2])&@@@(k/.{t->h});If[B>A,n+=1;Print@h;B-=A]])&

Ungolfed:

f = (
   A = Pi .01 Length@#2/#;
   l = m /. Solve[Norm[{a, b} - m {Cos@t, Sin@t}] == .1, m];
   k = (l /. {a -> #, b -> #2}) & @@@ #2;
   d = 1.*^-5;
   For[Print[h = B = 0]; n = 1, n < #, h += d,
    (
      B += If[Im@# < 0, 0, d (Max[#2, 0]^2 - Max[#, 0]^2)/2]
    ) & @@@ (k /. {t -> h});
    If[B > A, n += 1; Print@h; B -= A]
   ]
) &

This defines a function which takes as parameters the number of slices and a list of pairs for the peperoni coordinates, like

f[8, {{0.4, 0.2}, {-0.3, 0.1}, {-0.022, -0.5}, {0.3, -0.32}}]

It will print the slices to the console as it traverses the pizza.

On most pizzas, this is fairly slow, because (to achieve the required precision) I'm integrating the peperoni area from 0 to 2π in steps of 1e-5. To get a slightly less precise result in a reasonable amount of time, you can change the 1.*^-5 at the end to 1.*^-3.

How it works

The idea is to sweep out the slices of pizza while integrating over the area of the peperoni pieces covered. Whenever that area hits the required amount of peperoni per person, we report the current angle and reset the area counter.

To obtain the peperoni area swept out, we intersect the line with the peperoni to give use the two distances from the origin, where the line intersects with the peperoni. Since a line extends to infinity in both directions, we need to clamp these distances to non-negative values. This solves two problems:

Counting intersections with each peperoni twice, once positive and once negative (which would actually yield to an overall area of 0).
Counting only wedges of peperoni pieces which include in the origin.

I'll include some diagrams later.


Palindromic Prime Factors Palindromic prime problems are pretty common, but that's not what this question is about. In this challenge, the number doesn't have to be a palindrome, its prime factors do.
Task
Your code has to take a single positive integer as input. Then check if any of the permutations of the prime factors of that integer are palindromic when concatenated. If so, output one of them (the list of factors, not the concatenated string). Else, you have to output -1.
This is code-golf, so shortest code in bytes wins!
Test Cases
11 -> [11]
4 -> [2, 2]
39 -> [3, 13]
6 -> -1
1207 -> [17, 71]
393 -> -1
2352 -> [2, 2, 7, 3, 7, 2, 2]

05AB1E, 7 bytes

Òœ.ΔJÂQ

Try it online!

Explanation:

Ò            # prime factorization of the input
 œ           # permutations
  .Δ         # find the first one such that
    J        # concatenated
     ÂQ      # is a palindrome

(.Δ conveniently defaults to -1, so no extra work needed)


Exact change in fewest bills and coins Overview

In the US, the common denominations are the penny ($0.01), the nickel ($0.05), the dime ($0.10), the quarter ($0.25), one dollar, two dollars (less common but lets pretend it's common), five dollars, ten dollars, twenty dollars, fifty dollars, and one hundred dollars. ($1 to $100 respectively).

Your goal is to take an arbitrary money value and output a list of the fewest bills and coins that add up to that amount.

Rules

The output must be minimal. You cannot output "4175 pennies" for $41.75.
The inputs and outputs can be any format or type, as long as you can explain what it means.
Values must be kept the same. For instance, your program cannot accept "6523" for $65.23. It must accept the decimal value "65.23"

Examples

If the input is $185.24, the output should be something like
$100 + $50 + $20 + $10 + $5 + $0.10 + $0.10 + $0.01 + $0.01 + $0.01 + $0.01

For the input $44.75, another acceptable output would be
[0, 0, 2, 0, 0, 2, 0, 3, 0, 0, 0]
Meaning 2 $20s, 2 $2s, 3 quarters, and 0 of the other denominations.

Bonus

Accept another argument for the list of denominations so your program will work in other countries.

For example, if it's given this list of denominations.
[15, 7, 2.5, 1, 0.88, 0.2, 0.01]
and the money value "37.6", it should return something like
15 + 15 + 7 + 0.2 + 0.2 + 0.2


Shorter than a Split Second! Challenge
You task for this question is to split an input array of integers on the second occurrence of every integer in that array.
Not clear enough ? Here is an example to help
Input array:
[2 1 1 2 3 2 2 4 5 6 7 3 7 0 5]

Output:
[[2 1] [] [3 2 2 4 5 6 7] [] [0] []]

Explanation:
Here is the array with just the second element highlighted in bold:
[2 1 1 2 3 2 2 4 5 6 7 3 7 0 5]
Now we put the splitting array blocks around these bold second occurrences:
[2 1] 1 [] 2 [3 2 2 4 5 6 7] 3 [] 7 [0] 5 []
and wrap these splitted arrays in an array to get the final
[[2 1] [] [3 2 2 4 5 6 7] [] [0] []]

Note that when adjacent second occurrences occur, there will be empty arrays.
Rules
As usual, you have to write a full program or a function taking the input array via STDIN, ARGV or function argument.
Input
The input consists on any convenient array (or array-like) format of integers.
For instance, any of the following would be acceptable:
2 1 1 1 4 5 6
[2 1 1 1 4 5 6]
[2, 1, 1, 1, 4, 5, 6]

Output
When outputting to STDOUT, your array can also be printed in any convenient (nested) array format, e.g. one of
[[2 1] [1 4 5 6]]
[[2, 1], [1, 4, 5, 6]]
{{2, 1}, {1, 4, 5, 6}}

(This will usually be the native string representation of arrays in your language.)
Also note that trailing empty arrays should be printed as the part of the array.
Scoring
This is code-golf so shortest code in bytes win!

APL (Dyalog 14) (31)

{1↓¨(1,(⍳⍴⍵)∊2⍳⍨¨↓+\∘.=⍨⍵)⊂0,⍵}

This is a function that takes an array and returns a nested array.

Test:

      +V← {1↓¨(1,(⍳⍴⍵)∊2⍳⍨¨↓+\∘.=⍨⍵)⊂0,⍵} 2 1 1 2 3 2 2 4 5 6 7 3 7 0 5
┌───┬┬─────────────┬┬─┬┐
│2 1││3 2 2 4 5 6 7││0││
└───┴┴─────────────┴┴─┴┘
      ⍝ this return value is a real nested array:
      ⎕←'Length: ',⍴V ⋄ (⍳⍴V){⎕←'Array #',⍺,': (', ⍵, ')'}¨V
Length:  6
Array # 1 : ( 2 1 )
Array # 2 : ()
Array # 3 : ( 3 2 2 4 5 6 7 )
Array # 4 : ()
Array # 5 : ( 0 )
Array # 6 : ()

Explanation:

0,⍵: Add a 0 to the front of ⍵, for easier processing. (It does not count as an occurrence.)
(...)⊂: Split the array according to the given bitmask. A new group starts at each 1 in the bitmask.

+\∘.=⍨⍵: for each value in (the original) ⍵, find all occurrences in ⍵. Then make a running sum for each value, giving a square matrix showing for each position in ⍵ how many of each value have already occurred.
↓: Split the matrix by its rows, giving for each value an array showing the amount of times it has occurred by each position.
2⍳⍨¨: In each of these arrays, find the index of the first 2.
(⍳⍴⍵)∊: For each possible index into ⍵, see if it is contained in the list of indices of second occurrences. (These start each group, except the first one.)
1,: Add an 1 to the front, marking the start of the first group.

1↓¨: Remove the first element from each group. (These are the added 0, and the second occurrence of each value.)


Is the brick structure stable? Let's represent a standard masonry brick as [__] (and ignore the fact that the top is open). When these bricks are stacked every other layer is offset by half a brick, as is usual in brick construction:

  [__][__][__][__]
[__][__][__][__]
  [__][__][__][__]
[__][__][__][__]

Thus each brick has at most six neighbors and it's impossible for two bricks to directly line up vertically.

The key point is that arrangements of these bricks are not mortared, but merely held together by gravity. So it is important that each brick in the structure is stable, otherwise the entire structure is unstable.

There are three ways an individual brick may be stable:

Any brick on the ground (the lowest line of bricks) is stable.
Any brick that has two bricks directly below it is stable:

  [__]   <- this brick is stable
[__][__] <- because these bricks hold it up

Any brick that has a brick both above and below it on the same side is stable:

  [__]  [__]
[__]      [__] <- these middle bricks are stable
  [__]  [__]      because the upper and lower bricks clamp them in

[__]          [__]
  [__]      [__]   <- these middle bricks are NOT stable
    [__]  [__]

From these rules we can see, for example, the arrangement

  [__][__][__][__]
[__][__][__][__]
  [__][__][__][__]
[__][__][__][__]

is unstable because the top right brick is unstable, which is all it takes.

A brick structure is only stable if all of its bricks are stable.

Challenge

Your task is to write a function that takes in a brick structure string and returns a truthy value if the structure is stable, and a falsy value if unstable. (truthy/falsy definition)

The input string may be arbitrarily large but it will always be a rectangular grid of characters, with spaces filling areas void of bricks. The character grid width will be divisible by 4 but the height may be odd or even.

The brick grid always extends above and to the right of the lower left brick position:

         .
         .
         .
  BRK?BRK?BRK?BRK?
BRK?BRK?BRK?BRK?BRK?
  BRK?BRK?BRK?BRK?
BRK?BRK?BRK?BRK?BRK? . . .
  BRK?BRK?BRK?BRK?
BRK?BRK?BRK?BRK?BRK?

Depending on the structure, each BRK? either represents a brick ([__]) or empty space (4 spaces).

Notice that the half-brick cavities are filled with spaces to ensure that the character grid is rectangular.

Scoring

The shortest code in bytes wins.

Notes

If desired you may use . instead of space as the empty space character.
The empty string is considered stable.
If your language doesn't have functions you may use a named string variable as input and assign the result to another variable.
If your language doesn't have strings you may do whatever seems appropriate for input.

Test Cases

Various test cases, separated by empty lines. For clarity . is used instead of space for empty spaces.

Stable:

[__]

..[__]..
[__][__]

........[__]........
......[__][__]......
........[__]........

..[__][__]..
[__][__][__]
..[__][__]..
[__]....[__]

............[__]..
..[__][__][__][__]
[__][__][__][__]..
..[__][__][__][__]
[__][__][__][__]..

..[__]........[__]..
[__][__][__][__][__]
..[__][__][__][__]..
....[__][__][__]....
......[__][__]......
........[__]........

Unstable:

..[__]..
........

..[__]..
[__]....

..[__]..
....[__]

..[__][__]..
[__]....[__]
..[__][__]..
[__]....[__]

..[__][__][__][__]
[__][__][__][__]..
..[__][__][__][__]
[__][__][__][__]..

[__][__][__][__][__]
..[__][__][__][__]..
....[__][__][__]....
......[__][__]......
........[__]........

80386 machine code, 98

The code:

60 8b f1 8b f9 b0 0a f2 ae 8b ef 2b ee b0 00 f2
ae 2b fe 83 ef 02 2b fd 72 41 03 f7 2b f5 33 c9
8a 7c 6e fc 8a 1c 6e b1 02 33 d2 8b c7 f7 f5 83
fa 02 75 03 b7 00 41 8a 66 fc 8a 06 3b fd 7d 02
33 c0 23 c3 0a c4 22 df 0b c3 f6 44 2e fe 01 74
04 d1 e8 73 06 2b f1 2b f9 73 c5 61 d1 d0 83 e0
01 c3

The code scans the ASCII art from the end to the beginning, jumping 2 characters at a time. This does twice the needed checks (it would be enough to jump 4 characters), but simplifies the logic.

Checking starts at the next-to-last row of characters (no need to check the last line). At each line, it starts 3 characters from the right (no need to check too far to the right). For each character, it checks 4 surrounding characters:

A...B
..X..
C...D

There is a bunch of logical conditions to check:

If A and C are brick characters, X is supported
If B and D are brick characters, X is supported
If C and D are brick characters, X is supported
If X is a brick character, it has to be supported; otherwise the structure is unstable

It's a lucky coincidence that all brick characters [_] have their LSB set; all other characters .\n have it clear. In addition, the 80386 instruction set has these handy "high" and "low" registers (ah, al, etc), which help parallelize the checks a bit. So all the checking amounts to some obscure bit fiddling.

I started from the following C code:

int check(const char* ptr)
{
    int width, result = 0, pos;

    width = strchr(ptr, '\n') - ptr + 1;
    pos = strlen(ptr) - 1 - width; // pos points to the B character
    ptr += pos - width;

    while (pos >= 0)
    {
        int a = ptr[-4];
        int c = ptr[-4 + 2 * width];
        int b = ptr[0];
        int d = ptr[0 + 2 * width];
        int ab = a << 8 | b;
        int cd = c << 8 | d;
        if (pos < width)
            ab = 0; // A and B don't exist; set them to 0
        int jump = 2; // distance to next brick
        if (pos % width == 2) // leftmost brick?
        {
            cd &= 0xff; // C doesn't exist; set it to 0
            ++jump;
        }
        int support_v = ab & cd;
        support_v = support_v | support_v >> 8; // data in LSB
        int support_h = cd & cd >> 8; // data in LSB
        int support = (support_v | support_h) & 1;
        if (!support & ptr[-2 + width])
            goto UNSTABLE;
        ptr -= jump;
        pos -= jump;
    }
    return 1;
UNSTABLE:
    return 0;
}

I translated the code to assembly language (it's mostly one-to-one), including a golfed implementation of strchr and strlen. The following source code is translated by MS Visual Studio to the machine code at the top of my post.

__declspec(naked) int __fastcall check(const char* ptr) // MS Visual Studio syntax
{
    _asm
    {
        pushad;

        // ecx = ptr
        mov esi, ecx; // esi = ptr
        mov edi, ecx
        mov al, 10;
        repne scasb;
        mov ebp, edi;
        sub ebp, esi; // ebp = width

        mov al, 0;
        repne scasb;
        sub edi, esi;
        sub edi, 2;
        sub edi, ebp; // edi = pos
        jc DONE;

        add esi, edi;
        sub esi, ebp;

        xor ecx, ecx; // ecx = jump

    LOOP1:
        mov bh, [esi - 4 + 2 * ebp]; // bh = C
        mov bl, [esi + 2 * ebp]; // bl = D
        // bx = CD
        mov cl, 2;
        xor edx, edx
        mov eax, edi
        div ebp;
        cmp edx, 2;
        jne LABEL2;
        mov bh, 0
        inc ecx;
    LABEL2:

        mov ah, [esi - 4]; // ah = A
        mov al, [esi]; // al = B
        // ax = AB
        cmp edi, ebp;
        jge LABEL3;
        xor eax, eax;
    LABEL3:

        and eax, ebx; // ax = support_v
        or al, ah; // al = support_v
        and bl, bh; // bl = support_h
        or eax, ebx; // eax = support
        test byte ptr[esi - 2 + ebp], 1;
        jz LABEL4; // not a brick character - nothing to check
        shr eax, 1; // shift the LSB into the carry flag
        jnc DONE;
    LABEL4:
        sub esi, ecx;
        sub edi, ecx;
        jnc LOOP1;

    DONE:
        // here, the result is in the carry flag; copy it to eax
        popad;
        rcl eax, 1;
        and eax, 1;
        ret;
    }
}


FOIL Python's strong typing! Your task is to write some code in Python 2 or 3 such that this expression:

(a+b)(c+d) == a*c + b*c + a*d + b*d

will evaluate to True without raising any exceptions.

To clarify, I will copy your code into a file, then from the file import *. Then I will type the expression into the console and verify that it is True.

This is code-golf, so the answer with the shortest length (in bytes) wins.

54 52 50 49 48 45 39 bytes
Removed 4 bytes thanks to Dennis.
The latest version is inspired by the "some reason" in xnor's answer.
class t(int):__add__=type
a=b=t()
c=d=0


2017 is Almost Here! Challenge

The challenge is simple:

Taking no inputs and output the following message:

 _     __    __
  |   |  | |   |
  |_  |__| |   |

A number of times equal to the number of hours before or after midnight UTC on 31st Dec  2016.

Examples

For example if it is 19:01 UTC dec 31st you should output:

 _     __    __
  |   |  | |   |
  |_  |__| |   |
 _     __    __
  |   |  | |   |
  |_  |__| |   |
 _     __    __
  |   |  | |   |
  |_  |__| |   |
 _     __    __
  |   |  | |   |
  |_  |__| |   |
 _     __    __
  |   |  | |   |
  |_  |__| |   |

if it is 23:24 UTC dec 31st you should output:

 _     __    __
  |   |  | |   |
  |_  |__| |   |

and if it is 1:42 UTC jan 1st you should output:

 _     __    __
  |   |  | |   |
  |_  |__| |   |
 _     __    __
  |   |  | |   |
  |_  |__| |   |

Clarification: if it is 10-11pm dec 31st you should output two, 11-12pm dec 31st output one, 00-01am jan 1st output one, 01-02am jan 1st output two etc...

Rules

No Inputs
Trailing lines or spaces are ok.
Your program should work any time or day I run it (albeit with a large output). For example on jan 2nd at 00:15am your code should output 25 times.

(This is my first Code Golf question so if I have left any thing important out please let me know.)

This is Code Golf so Shortest bits win

JavaScript (ES6), 107
As an anonymous method with no parameters
Note 1483228800000 is Date.UTC(2017,0)
_=>` _     __    __
  |   |  | |   |
  |_  |__| |   |
`.repeat((Math.abs(new Date-14832288e5)+36e5-1)/36e5)

Test This keeps updating every 1 minute, but you'll need a lot of patience to see the output change.

F=_=>`_     __    __
 |   |  | |   |
 |_  |__| |   |
`.repeat((Math.abs(new Date-14832288e5)+36e5-1)/36e5)

update=_=>O.textContent=F()

setInterval(update,60000)

update()


Calculate the Numpad Taxicab Credit goes where credit is due

Given two digits, x, and y, calculate the shortest number of horizontal or vertical jumps to get from x to y on a standard numpad, e.g.
789
456
123
00

You can safely assume that all inputs will be 0-9, and you do not have to handle invalid inputs. The input may be the same number twice, which has a distance of 0.
IO can be in any reasonable format, and standard loopholes are forbidden. Shortest answer in bytes wins!
Sample IO:
1, 4: 1
1, 8: 3
3, 7: 4
8, 2: 2
6, 1: 3
0, 9: 4
4, 4: 0
0, 4: 2

Jelly, 11 bytes

o-1.’d3ạ/ḞS

Try it online! or verify all test cases.

How it works

o-1.’d3ạ/ḞS  Main link. Argument: [a, b] (list of integers)

 -1.         Yield -1.5.
o            Take the logical OR of a and b with -1.5.
             This maps 0 to -1.5, and all other integers to themselves.
    ’        Decrement the results.
     d3      Divmod; compute quotient and remainder of each result divided by 3.
       ạ/    Reduce by absolute difference across columns.
         Ḟ   Floor; round all differences down to the nearest integer.
          S  Sum; add the rounded absolute differences.


Computer Generated Olympic Theme Song Try to regenerate the olympic theme song, "Bugler's Dream" using the programming language of your choice. The language/platform used must be able to emit the physical sound. Only playing the main melody (trumpets) is required, but doing more would be great.

You must generate all the tones yourself - you cannot play back a midi/wav or any other sound file.

Here are the sound files for reference:

http://www.jonfullmer.com/music-of-the-month/buglers_dream/buglers_dream.mp4
http://www.armory.com/~keeper/1/bugdream.mid

Good luck!


Code Golf - Word Clock Write a program which takes the current time of the system clock, rounds to the nearest minute (you may choose how to round halves) and displays it formatted as the following:

A quarter past one in the morning.
A quarter to two in the afternoon.
Two o'clock in the afternoon.
Twenty-five minutes to three in the morning.
Twenty-seven minutes to seven in the evening.
One minute past twelve in the afternoon.
Twelve o'clock noon.
Twelve o'clock midnight.

Rules:

12:01am to 11:59am is deemed as morning.
12:01pm to 5:59pm is deemed as afternoon.
6:00pm to 11:59pm is deemed as evening.
15 minutes past the hour must be expressed as A quarter past the hour
30 minutes past the hour must be expressed as Half past the hour
45 minutes past the hour must be expressed as A quarter to the upcoming hour
On-the-hour times must be expressed as the hour o'clock, with the addition of noon and midnight being expressed with the addition of noon or midnight respectively.
Other times in hh:01 to hh:29 must be expressed as (number of minutes) past the hour.
Other times in hh:31 to hh:59 must be expressed as (number of minutes) to the upcoming hour.
Twenty-one to twenty-nine must be hyphenated.
The first letter of the output must be capitalised. The other letters must be lower-case.

It would be useful to provide a testing version of your code so that it can be tested without manipulating the system clock.

Mathematica 450
Date[] calls for the current date and time. [[{4,5}]] returns the hour and minutes
f[]:=f[Date[][[{4,5}]]];
f[{h_,m_}]:=Module[{p,w,s},
p@h1_:=Which[0<h<12," in the morning.",12<h<18," in the afternoon.",18<h<24, " in the evening."];
s[t_]:=WolframAlpha["spell "<>ToString@t,{{"Result",1},"Plaintext"}];
w=s[h~Mod~12]<>p@h;
Which[
m==0, Switch[h,12, "noon", 0|24,"midnight",_,s[h~Mod~12]<>p@h],
m==15,"a quarter past "<>w,
m==30,"half past "<>w,
m==45,"a quarter to "<>s[h~Mod~12+1]<>p@h,
m<30,s@m<>" minutes after "<>w,
m>29,s[60-m]<>" minutes before "<>s[h~Mod~12+1]<>p@h]]

Current Time
f[]

"ten minutes past three in the afternoon."

Specific times
f[{4, 45}]
f[{10, 30}]
f[{11, 0}]
f[{12, 0}]
f[{13, 15}]
f[{15, 0}]
f[{22, 17}]
f[{24, 0}]

"a quarter to five in the morning."
"half past ten in the morning."
"eleven in the morning."
"noon"
"a quarter past one in the afternoon."
"three in the afternoon."
"seventeen minutes past ten in the evening."
"midnight"


Can I make that shape with blocks, slabs, and stairs? Consider a rectangular two-dimensional grid where each cell can either be empty (.) or full (0).

e.g.

..00....
0000....
.00000..
000...00
..000000
000.00..

The grid is considered infinite, all cells outside the depicted region are empty.

The goal is to cover the filled spaces and leave the empty spaces open using a set of 7 distinctly shaped bricks that each take up 4 cells (2×2) of the grid.

These are the 7 bricks:

Blocks - 1 variant

11
11

Slabs - 2 variants

..
22

33
..
Stairs - 4 variants

.4
44

5.
55

66
.6

77
7.

These bricks must always align to a grid whose cells are twice as wide and tall as the cells of the input grid. Each brick can only occupy one cell of this larger grid but the smaller grid can be translated (shifted up, down, left, right) beneath the larger grid to give more options for finding a cover. Neither of the grids nor individual bricks may be rotated.

So one way to cover (a.k.a. solve) the example above is like this:

..11....
2211....
.47733..
447...22
..771133
227.11..

(Identical neighboring bricks can still cause ambiguity but carefully identifying the larger grid resolves that.)

An invalid solution for

000000
000000

is

566774
556744

because the bricks do not all align to the larger grid nor only occupy one cell of it.

A valid solution here is 3 blocks in a row:

111111
111111

And another valid solution involves 6 slabs:

......
222222
333333
......

So note that some input grids have multiple solutions.

An invalid solution for

00.00
00...

is

11.33
11...

because the bricks don't align to the larger grid. The slab would need to move left or right by one, but then of course the cover would be incomplete. This input grid has no solution.

Challenge

Write a program that takes in (via stdin/command line) a rectangular block of text of .'s and 0's that represents a grid to be covered.

If there is a valid covering solution, print (via stdout) any one solution in the same manner as above, replacing all 0's with the appropriate 1 through 7 bricks.

If there is no solution, your program should not output anything, just quietly end normally.

Notes

The input and output do not need to have the same rectangular dimensions. Your output can have extraneous rows and/or columns of all .'s (as long as they don't invalidate the solution).
It's also alright to trim rows and column's of all .'s if it won't affect the filled spaces. e.g.

222222
333333

is a valid solution to

000000
000000

Conversely, the two empty columns in 00..00 could not be removed since that would disarrange the filled spaces.
You may optionally assume the input has a single trailing newline. A single trailing newline in the output is fine as well, even in the case of no solution.
Grids that are completely empty (all .'s) and the trivial 0×0 grid are not input cases you need to worry about. But the 1×1 0 grid is, as are all other grids that contain at least one 0. (You may not assume the width or height of the input grid is even!)
Instead of a program you may write a function that takes the input as a string argument and prints the output normally or returns it as a string. Any falsy value can be returned if there is no solution.
You may use any 9 distinct printable ASCII characters in place of . 0 1 2 3 4 5 6 7. Just be sure to say what your substitutions were! Newlines must remain as is.

Scoring

The shortest code in bytes wins. Tiebreaker is highest voted post.

This challenge was inspired by blocks, slabs, and stairs in Minecraft, which follow the same rules described here. If you enjoy PPCG and Minecraft, you may want to check out the PPCG Minecraft Server.

Python - 525 491 478 430 bytes

r=range
def t(s):
 m=s.find("\n")+1
 for q in r(4):
  try:
   for i in r(-q%2,m-1,2):
    for j in r(-q/2,len(s)/m,2):
     k,g=j*m+i,""
     b=[k,k+1,k+m,k+m+1]
     for z in b:g+=a(s,z)
     for z in b:
      if a(s,z)!="d":s=s[:z]+`dict(dddd=0,zzdd=3,ddzz=2,zzzd=7,zzdz=6,zdzz=5,dzzz=4,zzzz=1)[g]`+s[z+1:]
   return s
  except:d
def a(v,i):
 try:
  if v[i]!="\n":return v[i]
  return "d"
 except:return "d"

Explanation: This is my first code golf, so it might not be optimal, but here's how it works. The function t(s) gives the result for the string passed in. First, it finds the number of columns, then goes through the four possible distinct translations by 1 (none, left, up, up-left) and tries to solve it for each one. It looks at each 2x2 block and maps it to a valid block number, given by a dictionary, and changes the zeros to the number.

If it finds one not in the dictionary, it abandons that specific offset and starts over with the next one. If it goes through all 4 offsets without finding a valid solution, it ends without outputting anything. a(v, i) allows for the default value outside the string, and ignores newline characters. Although it may end up with partial solutions through the duration of the run, it will always override them with the final correct one if it exists.

Edit: A different mapping of characters is used: . -> d, 0 -> z, all other numbers go to themselves. This applies to both input and output.


Building a long chain of words This challenge is to find the longest chain of English words where the first 3
characters of the next word match the last 3 characters of the last word. You will use
an common dictionary available in Linux distributions which can be downloaded
here:

https://www.dropbox.com/s/8tyzf94ps37tzp7/words?dl=0

which has 99171 English words. If your local Linux /usr/share/dict/words is the same file (has md5sum  == cbbcded3dc3b61ad50c4e36f79c37084), you can use that.

Words may only be used once in an answer.

EDIT: Letters must match exactly including upper/lower case, apostrophes, and accents.

An example of a valid answer is:
idea deadpan panoramic micra craftsman mantra traffic fiche
which would score 8.

The answer with the longest valid chain of words will be the winner. In the
event of a tie, the earliest answer will win. Your answer should list the chain
of words you have found and (of course) the program you wrote to do it.

Java, heuristic favouring the vertex which induces the largest graph: 1825 1855 1873

The code below runs in under 10 minutes and finds the following path:

[wad, wadis, dis, dismay, may, mayfly, flywheels, elsewhere, erecting, ingratiate, ateliers, ersatzes, zest, esthetic, tickled, ledger, germicide, idealizes, zestful, fulling, ingrains, institute, uterine, ineptness, essaying, ingeniously, slyness, essences, cessations, onshore, ores, resoundingly, glycerine, inertness, essay, say, saying, ingenuous, ousted, tediously, sly, slyest, estrogen, genuflecting, ingestion, ionizer, zeros, roses, sesames, mes, meshed, hedonist, isthmuses, sesame, amending, ingredient, entrapment, enthuses, session, ionosphere, erectness, essayist, isthmus, mustaches, hesitatingly, glycogen, generation, ions, onset, settable, blew, lewder, deriding, ingratiates, testicles, lessen, sensitization, ionization, ionizing, ingratiating, ingenious, ouster, terrorizing, ingest, estranges, gesticulating, ingrates, testis, tissue, sue, suede, edelweiss, issuing, ingraining, ingrown, owner, nerdiest, estimation, ionospheres, rescue, cue, cueing, ingesting, ingot, got, gotten, tensor, sorrowing, ingratiated, tedious, ousting, ingratiatingly, glycerin, ringside, identifiable, bleariest, ester, terminological, calibrator, torrent, entraps, apse, pseudonym, nymphomania, niacin, cinema, emailed, led, ledges, gesticulates, testicle, clement, entail, ail, ailment, enter, terrains, inspires, restaurateur, euros, rosiest, estimates, tester, termite, iterator, torture, urethras, raspiest, estimator, tore, oregano, anointment, enthuse, useful, fulfil, filmstrip, riposte, stereotyped, pedicure, urea, readmits, itself, elf, elfin, finagles, lesbians, answerable, bleat, eatery, erythrocytes, testosterone, one, ones, nest, esteemed, medicine, inextricable, blessed, sediment, entry, try, tryout, outsources, cesarians, answered, redressed, seducer, cervical, calumniates, test, establishment, entombment, enthusiastic, tickles, lessens, ensemble, blemishes, hesitant, antic, tick, ickiest, estimable, blemished, hedgehog, hogan, gantlet, letdown, own, ownership, hippest, estates, testates, testiest, establishes, hes, hesitates, testable, bleakest, esthetes, testament, entice, iceberg, erg, ergonomic, microscope, operatives, vestibules, lesser, serenade, adenoidal, dales, lest, estrangement, entrap, raptures, resourceful, fulsome, omen, menswear, earthliest, established, hedges, gestates, testy, styes, yeshivot, voter, terrible, blender, derides, descent, enticed, cedillas, lass, assailable, bleacher, hermit, mite, item, temperas, rash, ashtray, rayon, yonder, dermis, mismanage, agendas, dash, ashy, shy, shyster, terrapins, insatiable, bleeder, derives, vestment, entangle, glen, lengthens, ensconced, ceded, deduced, cedars, arsenic, nice, ice, iced, cedar, daredevil, villa, llamas, masseuse, use, useable, bleach, achievable, bleached, hedonistic, tic, ticker, kerchieves, vessel, sell, ell, elliptic, ticket, kettles, lessee, seeps, epsilon, longboat, oath, atherosclerosis, sisterhood, oodles, lesson, sonatas, tassel, selvage, age, agent, entranced, cedes, descender, deranges, gestures, restraint, interment, enthused, seduced, cedilla, llama, amalgam, gamut, mutable, blend, endear, earthy, thymus, mussel, seltzer, zero, erodes, despot, potful, fulfillment, enthrall, allot, lotus, tussle, sledgehammered, redolent, entrapped, pedestal, talk, alkalis, listen, tended, deductible, bleeped, pedigree, reentered, redistribute, uterus, rustproofed, fed, fedora, oranges, gesundheit, either, herdsman, manes, nestles, lessor, sorrowful, fullback, acknowledges, gestured, redoubtable, blended, deduces, cesareans, answer, werewolves, vesper, perseveres, restructures, reside, ideogram, rammed, meddlesome, omens, ensign, ignores, restrains, insolent, entanglement, entrenchment, enticement, entomological, calligraphy, physical, calico, iconoclast, astringent, entertainment, entrant, antennas, nasty, stymie, miens, enslave, averred, redefine, inexorable, blenched, hedgerow, rowboat, oat, oaten, tend, endears, arson, songwriter, terminable, blent, entreaty, atypical, calypso, psoriasis, sister, term, ermine, ineligible, bleaker, kerosene, enema, emancipator, tormentor, torrider, derailment, entertains, instil, tildes, destine, inelegant, anthropomorphic, hiccup, cupolas, lastingly, glycerol, rollback, acknowledgment, entombed, bedridden, denser, servicewomen, menopause, used, sedatives, vesicle, clearinghouse, user, servant, antipodes, descry, crystalline, inexpedient, enthusiast, astonishment, entirety, etymological, calendared, redbreast, astronomer, merinos, nosedove, overpay, pay, paymaster, termagant, antiaircraft, aftercare, ares, resentful, fulcrum, rumpus, pushcart, artiste, stethoscopes, pesetas, taste, steadfast, astride, ides, destitute, utensil, silvan, vanguard, ardent, entryway, waysides, despair, airdrop, ropes, pestered, redder, derangement, entered, redeemed, medullas, lasagnas, nasal, salsas, sashay, hay, haymow, mow, mowed, wedder, derringer, germane, anemic, microfilmed, media, diatom, tomboys, oyster, terminator, toreador, dorsal, salespeople, pleased, sedater, terabit, bitten, tentacle, clergyman, manifesto, stomach, achoo, hoopla, plaza, azalea, leaven, vendor, dormant, antiparticle, cleared, redraft, afterword, ordains, insufficient, entitlement, entomb, ombudsmen, men, mental, tallyhos, hospice, icecap, cape, aperitif, tiffed, fedoras, rasped, pediatric, rickshaw, hawker, keratin, tinctures, reset, setback, acknowledgement, enthronement, entwine, inexact, actor, torpedos, dosed, sedan, dancer, cerebrum, rumple, plea, leach, ache, cheaper, per, periscopes, pestilent, entreat, eater, terser, serape, ape, apes, pesky, skycap, capped, pederast, astuter, terrace, acetaminophen, henchmen, menopausal, saltcellar, lard, ardor, dormice, icebound, underbrush, ushered, redrew, rewound, underclass, assassin, sinew, newscast, astrologer, gerund, undertaken, ken, kens, ensnared, redcap, cappuccinos, nostrum, rum, rumored, redraw, rawhide, identical, calcine, inertia, tiara, arabesque, queerer, reruns, unsold, oldie, diesel, selectmen, mentored, redden, dental, talon, longhand, and, androgen, genome, omelet, lethal, hallucinogenic, nickname, amen, menhaden, denudes, despaired, redevelop, lope, operas, rasp, aspired, redskin, kindergartens, ensnares, resultant, anthropological, callus, lustful, fulcra, crammed, mediocre, crepes, pesticide, ideas, eastbound, under, derrières, respired, rediscovered, redundant, antihero, erode, ode, odes, described, bedevil, villager, gerrymander, deride, ideograph, aphid, hid, hides, describes, besides, despoil, oilskin, kingdom, dominant, ant, antipasti, stiffens, ensured, redeemer, merchant, antiwar, warped, pederasty, stylus, lush, usher, her, hereafter, terrapin, pinnacle, clerical, caliber, bereave, avenger, geriatric, rickshas, haste, stereoscopes, pester, termini, initiator, tortures, restorer, reran, ransomed, medulla, llanos, nostril, rill, illogical, calif, lifer, fervor, vortex, textures, resister, termed, medieval, valor, lord, ordered, rediscover, verbatim, times, mesdames, mescal, caliper, periscope, opera, erasures, restart, artichokes, kestrel, reliant, antebellum, lumbago, agog, goggle, gleeful, fulfill, illustrator, tor, torque, questionnaires, resumed, mediator, tort, orthodoxy, oxymora, oratorio, riot, iotas, taster, terrific, fiche, checkpoint, interloper, perfumes, mesas, sassafras, rasher, heraldry, drywall, all, allergens, ensnare, area, rearm, armchair, airman, manufactures, resurface, acerbic, bicycle, cleverer, rerun, runt, untidy, idyllic, lichens, ensures, resend, endemic, microchip, hippopotamus, muscatel, telecast, astronaut, autopilot, lot, loth, other, heros, rosin, single, gleamed, mediaeval, valet, lettered, redound, underside, ideological, calliper, perihelia, liaison, sonic, nicknames, messenger, germicides, descendant, antigen, genital, tall, allergen, gentleman, mangos, gossipped, pedicures, resistant, antlered, redeveloped, pedagogical, calligrapher, heroins, inside, idea, deafen, fen, fencer, cerebra, bravuras, rascal, calculus, lusher, herbivores, resins, instill, illicit, citric, ricochet, heterodoxy, oxygen, generic, rice, icebox, box, boxcar, cartography, physique, quell, ellipsis, sis, sisal, sallow, lowbrow, rowel, well, elliptical, calf, alfresco, scow, cow, cowboy, boy, boyfriend, end, endeared, red, redesign, ignoramus, musket, kettledrum, rump, umped, pedlar, larvas, vassal, salmonellas, last, astronomical, calfskin, kingfisher, hereupon, ponchos, hospital, talisman, mantel, telethon, honcho, chomped, pedant, antitoxins, instant, antipastos, tossup, superintend, endangered, redskins, instigator, torpor, portico, icon, conquistador, dormer, merganser, seraphic, hiccuped, pedagogue, guerrillas, laser, sera, eraser, seraph, aphasic, sickbed, bed, bedsores, resign, ignorant, anthropocentric, richer, herdsmen, menu, enures, resuscitator, tornado, ado, adobe, obeisant, anthill, illegal, gallon, longshoremen, menace, ace, acetylene, enemas, mas, mascot, cot, cotton, tonsures, restores, result, ultraviolet, letterbox, boxer, xerography, physiological, calmer, merchantmen, mentor, torus, russet, settee, teenager, gerbil, billfold, old, olden, denatures, resubmit, mitten, ten, tenon, nonchalant, antique, queasy, asymmetric, ricksha, shanghai, haircut, cutups, upsides, descriptor, torpid, pidgin, gins, instep, tepee, peeper, perturb, urbane, anemia, miasmas, mascaras, raspy, spy, spyglass, assures, resonator, tortilla, llano, anon, nontechnical, calabash, ashram, rampart, arthropod, podia, diagram, ramp, amp, amphitheatres, resistor, tortillas, lasagna, gnat, natal, talc, alcoholic, licensee, seemed, medical, calm, almanac, nacho, choreography, phylum, lumbar, barman, mannequins, insures, respires, resound, underarm, armatures, resides, desideratum, tumult, ultrasound, underdog, dogcatcher, herald, alderwoman, mandarins, insecticides, desires, respirator, torrid, rid, rides, descant, anticlimax, maximum, mum, mummer, meringue, guesser, sermon, monogram, ramrod, rodeo, deodorant, antelopes, peso, esophagus, gusset, setups, upshot, hotel, telescope, open, penicillin, lingos, gossip, sip, siphon, honor, normal, maltreat, eaten, tenet, nether, herpes, pesticides, descend, endow, downfall, alleyway, way, waylay, layman, manicures, reshuffle, flea, lea, leash, ashen, henchman, mandolin, linchpins, inscribes, bestow, townspeople, plectrum, rumbas, baste, sternum, numb, umbilici, icicle, cleaver, vertebra, brains, insouciant, antidepressant, anthem, hemoglobin, binocular, largos, gossamer, mermaid, aid, aides, desperado, adopt, opt, optima, imam, mambos, bosun, sun, sunspot, potpourris, risky, sky, skyscraper, perturbed, bedraggle, glee, lee, leech, echo, choreographer, heraldic, dictum, tumid, midday, day, daybed, bedsides, desktop, topknot, notepaper, periodical, calendar, dare, areas, easel, selfsame, amebas, basins, ins, insulin, linnet, nettlesome, omegas, gasp, aspartame, amend, endures, researcher, herbal, balsas, sass, assault, ultimatum, tumor, mortgagor, gores, resort, orthopaedic, dictatorship, hipper, person, sonar, narc, arc, archduke, ukelele, elegant, anther, hereabout, outfox, fox, foxtrot, rotogravures, restaurant, antechamber, beret, retriever, verbena, enamor, morsel, sellout, outmaneuver, vertical, call, allergenic, niche, chessman, mandolins, insipid, pidgins, install, allures, rescind, indignant, antithetical, calicos, cosmonaut, auto, utopia, piano, another, heretical, calk, alkali, alibi, ibis, bistro, troupe, upend, endorser, serviceman, mandarin, rind, inductee, teepee, pee, peekaboo, bootstrap, rape, apertures, resin, singular, larval, valiant, antiperspirant, antipasto, stop, topical, calisthenic, nicer, cervix, vixen, xenophobic, bicep, cephalic, licit, citizenship, hippopotami, amigos, gospel, pellet, letups, upstart, artificer, cerebellum, lumberman, manic, nicknamed, medic, dickie, kielbasas, sash, ash, ashcan, cannon, nonskid, kid, kidnaper, perjures, resolver, vernacular, larkspur, puree, reefer, ferret, retains, insofar, far, fart, artisan, sandbag, bagel, gelatin, tinsel, selectman, manacle, clever, versus, sustains, inscribed, bedpan, pandemic, microprocessor, sorbet, bet, betcha, char, harem, remodel, deli, elicit, citadel, deliver, verandas, dashikis, kisser, servicemen, menthol, holiday, daydreamer, merchantman, manikins, insane, anew, newsprint, interwove, overreach, achieve, even, venom, nomad, mad, madrigal, gala, alarm, armpit, pitchman, manor, northbound, underbid, bidet, detox, toxemia, miasma, smarten, tenderloins, insult, ultra, travel, velvet, veteran, random, domino, inopportune, uneconomic, microbes, bestir, tiro, ironware, arena, enamel, melodramas, mastodon, don, donut, nut, nutmeg, meg, megalopolis, lissom, sombre, breathe, therefrom, romper, performer, merman, mangrove, overshadow, downcast, astir, tiros, rostra, trachea, heaven, ventricle, clergywoman, maneuver, verbal, ballad, ladyship, hippie, pie, piebald, alderman, manatee, teethe, thereupon, poncho, choicer, ceramic, microscopic, picayune, uneaten, tendon, donor, northeast, astound, underpass, assessor, sorghum, hum, human, mantra, trainee, needlepoint, interplay, laywoman, mannikin, kinsman, mantillas, lassie, sieve, ever, verdigris, risen, sensor, sorrel, relabel, belabor, borsch, schlep, leprechauns, unsnap, nap, napkin, kin, kingpin, pinkeye, eyeglass, assemblyman, manikin, kingship, hip, hippos, postpartum, tumbrel, relic, lichee, heehaw, haw, hawser, servicewoman, many, anyhow, howsoever, vertex, text, extra, trap, rap, rapper, periwig, wigwag, wag, wagon, gonorrhea, heave, aver, vermin, minesweeper, perplex, lexicon, congas, gastronomic, microfiche, cheapen, pentathlon, longhair, air, aircraft, aft, aftertaste, stem, tempos, postwar, war, wart, article, clear, earshot, hotshot, hotbed, bedlam, lam, lambkin, kindergarten, tenser, serum, rumor, mortar, tarmac, macabre, breech, echos, hostel, telescopic, pickerel, relay, laypeople, pleas, east, astronomic, micra, crackpot, pot, potato, atom, tombed, bedbug, bugaboo, bootleg, leg, legato, atop, topple, plethora, orangutang, angora, orangutan, tan, tandem, democrat, rat, rattan, tang, angry, gryphon, honeybee, bee, beeswax, waxen, xenon, nonplus, lustre, trellis, lisle, sleepwear, earwig, wig, wigwam, wampum, pummel, melanomas, massacre, cretin, tin, tint, interviewee, wee, weeper, persimmon, monsignori, origin, gingham, ham, hamper, pericardia, diarrhea, heartthrob, rob, robes, besom, sombreros, rosebud, bud, budgerigar, garret, retrodden, denim, nimbus, bus, bushel, helmet, metaphor, horsefly, flypaper, peritonea, near, ear, earlobes, bestowal, wall, allay, layout, outlast, astrakhan, handicapper, perusal, saltpetre, tremor, moribund, undercut, cut, cutoff, off, offal, falcon, con, consul, sultan, tannin, ninepin, pinball, allegro, grommet, metro, trot, rot, rotten, tenpin, pineapple, plectra, transit, sitar, tar, taro, arousal, salmon, moneybag, bagpipe, ipecac, cache, checkout, outrun, runaround, undersea, sea, sear, earache, cherub, rub, rubicund, underpin, pin, pint, intagli, glib, lib, libel, bellyache, cherubim, bimbos, bosuns, unsound, undertow, tow, towel, wellington, ton, tonsil, silicon, concoct, octet, tetrahedra, drachmae, maestri, tripos, possum, sum, sumac, macro, crocus, custom, tom, tomcat, catsup, sup, superstar, tarpaulin, linchpin, pinpoint, intercom, comet, met, metacarpus, pussycat, catastrophe, phenomenon, nonverbal, ballpoint, interurban, bani, animal, malt, altar, tartar, tarot, rotund, undergrad, radio, diocesan, sandbar, bar, barren, renewal, walkout, outstrip, ripen, pen, pencil, cilantro, trout, outran, rancor, corncob, cob, cobra, bra, brag, rag, ragas, gas, gasohol, holdout, output, put, putsch, schwas, was, waste, stereo, reoccur, cur, curb, urban, ban, bantam, tam, tamp, ampul, pullout, outwit, wit, withal, halo, alohas, hasp, asparagus, gusto, stove, overlap, lapel, pelvis, visit, sit, sitcom, compendia, diadem, demigod, god, goddam, dam, dampen, pennon, non, noncom, compel, pelican, cancan, can, cancel, celesta, starlit, lit, litmus, muscat, cat, catnap, naphtha, than, handcar, carpel, pellagra, grammar, mar, mariachi, chichi, chi, chimp, imp, impel, pelvic, vicar, car, caribou, bourgeoisie, siesta, stab, tab, tabu, abut, but, butterfat, fat, fathom, homespun, pun, puns, unsheathe, the, theorem, remove, overtax, tax, taxicab, cab, cabal, balsam, sambas, basal, salamis, missal, salt, altho, tho, thou, housebound, underground, underclassman, man, mannikins, insectivores, resonant, antelope, operator, torn, ornamental, tallow, low, lowered, reddens, enshrine, inefficient, entertainer, nerves, vestiges, gesturing, ingested, tediousness, essentials]

Core ideas

In Approximating longest directed paths and cycles, Bjorklund, Husfeldt, and Khanna, Lecture Notes in Computer Science (2004), 222-233, the authors propose that in sparse expander graphs a long path can be found by a greedy search which selects at each step the neighbour of the current tail of the path which spans the largest subgraph in G', where G' is the original graph with the vertices in the current path deleted. I'm not sure of a good way to test whether a graph is an expander graph, but we're certainly dealing with a sparse graph, and since its core is about 20000 vertices and it has a diameter of only 15 it must have good expansion properties. So I adopt this greedy heuristic.

Given a graph G(V, E), we can find how many vertices are reachable from each vertex using Floyd-Warshall in Theta(V^3) time, or using Johnson's algorithm in Theta(V^2 lg V + VE) time. However, I know that we're dealing with a graph which has a very large strongly connected component (SCC), so I take a different approach. If we identify SCCs using Tarjan's algorithm then we also get a topological sort for the compressed graph G_c(V_c, E_c), which will be much smaller, in O(E) time. Since G_c is a DAG, we can compute reachability in G_c in O(V_c^2 + E_c) time. (I have subsequently discovered that this is hinted at in exercise 26-2.8 of CLR).

Since the dominant factor in the running time is E, I optimise it by inserting dummy nodes for the prefixes/suffixes. So rather than 151 * 64 = 9664 edges from words ending -res to words starting res- I have 151 edges from words ending -res to #res# and 64 edges from #res# to words starting res-.

And finally, since each search takes about 4 minutes on my old PC, I try to combine the results with previous long paths. This is much faster, and turned up my current best solution.

Code

org/cheddarmonk/math/graph/Graph.java:

package org.cheddarmonk.math.graph;

import java.util.Set;

public interface Graph<V> {
    public Set<V> getAdjacent(V node);
    public double getWeight(V from, V to);
}

org/cheddarmonk/math/graph/MutableGraph.java:

package org.cheddarmonk.math.graph;

import java.util.*;

public class MutableGraph<V> implements Graph<V> {
    private Map<V, Map<V, Double>> edgesBySource = new HashMap<V, Map<V, Double>>();

    public void addEdge(V from, V to, double weight) {
        if (!edgesBySource.containsKey(to)) edgesBySource.put(to, new HashMap<V, Double>());
        Map<V, Double> e = edgesBySource.get(from);
        if (e == null) edgesBySource.put(from, e = new HashMap<V, Double>());
        if (e.containsKey(to)) throw new IllegalArgumentException("There is already an edge between the vertices");
        e.put(to, weight);
    }

    @Override
    public Set<V> getAdjacent(V node) {
        Map<V, Double> e = edgesBySource.get(node);
        if (e == null) throw new IllegalArgumentException("node doesn't appear to be in the graph");
        return Collections.unmodifiableSet(e.keySet());
    }

    @Override
    public double getWeight(V from, V to) {
        Map<V, Double> e = edgesBySource.get(from);
        if (e == null) throw new IllegalArgumentException("from doesn't appear to be in the graph");
        if (!edgesBySource.containsKey(to)) throw new IllegalArgumentException("to doesn't appear to be in the graph");

        Double c = e.get(to);
        return c == null ? 0 : c.doubleValue();
    }
}

org/cheddarmonk/math/graph/StronglyConnectedComponents.java:

package org.cheddarmonk.math.graph;

import java.util.*;

/**
* A helper class for finding the strongly connected components of a graph using Tarjan's algorithm.
* http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
*/
public class StronglyConnectedComponents<V> {
    private final Graph<V> g;
    private List<Set<V>> topologicallySortedSccs = new ArrayList<Set<V>>();

    private final LinkedList<V> S = new LinkedList<V>();
    private final Set<V> S2 = new HashSet<V>();
    private final Map<V, Integer> index = new HashMap<V, Integer>();
    private final Map<V, Integer> lowlink = new HashMap<V, Integer>();

    private StronglyConnectedComponents(Graph<V> g) {
        this.g = g;
    }

    private void strongConnect(V v) {
        int idx = index.size();
        index.put(v, idx);
        lowlink.put(v, idx);

        S.push(v);
        S2.add(v);

        for (V w : g.getAdjacent(v)) {
            if (!index.containsKey(w)) {
                strongConnect(w);
                if (lowlink.get(w) < lowlink.get(v)) {
                    lowlink.put(v, lowlink.get(w));
                }
            }
            else if (S2.contains(w)) {
                if (index.get(w) < lowlink.get(v)) {
                    lowlink.put(v, index.get(w));
                }
            }
        }

        if (lowlink.get(v).equals(index.get(v))) {
            Set<V> scc = new HashSet<V>();
            V w;
            do {
                w = S.pop();
                S2.remove(w);
                scc.add(w);
            } while (!w.equals(v));

            topologicallySortedSccs.add(scc);
        }
    }

    public static <V> List<Set<V>> analyse(Graph<V> g, Set<V> sources) {
        if (g == null) throw new IllegalArgumentException("g");

        StronglyConnectedComponents<V> scc = new StronglyConnectedComponents<V>(g);
        for (V v : sources) {
            if (!scc.index.containsKey(v)) {
                scc.strongConnect(v);
            }
        }

        return scc.topologicallySortedSccs;
    }
}

org/cheddarmonk/ppcg/PPCG.java:

package org.cheddarmonk.ppcg;

import java.io.*;
import java.util.*;
import org.cheddarmonk.math.graph.*;

public class PPCG44922 {
    private static final String path = "/usr/share/dict/words";
    private static Set<String> allWords;
    private static Graph<String> fullGraph;

    public static void main(String[] args) {
        loadGraph();

        Random rnd = new Random();
        rnd.setSeed(8104951619088972997L);
        List<String> a = search(rnd);
        rnd.setSeed(-265860022884114241L);
        List<String> b = search(rnd);
        List<String> chain = spliceChains(a, b);
        System.out.println(chain.size());
        System.out.println(chain);
    }

    private static List<String> search(Random rnd) {
        List<String> chain = new ArrayList<String>();
        chain.add(selectOptimalReachabilityCount(fullGraph, allWords, rnd));
        while (true) {
            String tail = chain.get(chain.size() - 1);
            FilteredGraph g = new FilteredGraph(chain);

            // We know that tail only has one successor, so skip ahead.
            Set<String> candidates = new HashSet<String>(fullGraph.getAdjacent(suffix(tail)));
            candidates.removeAll(chain);
            if (candidates.isEmpty()) break;

            chain.add(selectOptimalReachabilityCount(g, candidates, rnd));
        }

        Iterator<String> it = chain.iterator();
        while (it.hasNext()) {
            if (it.next().charAt(0) == '#') it.remove();
        }
        return chain;
    }

    private static List<String> spliceChains(List<String> a, List<String> b) {
        Set<String> intersect = new HashSet<String>(b);
        intersect.retainAll(a);
        if (intersect.isEmpty()) return null;

        // Splice the longest bits. To avoid cycles, we look for intersection points which have the same set of reached intersection points.
        // Thus to get from one to the next we can take either route without violating the unique occurrence of each element in the spliced chain.
        Set<String> left = new HashSet<String>();
        Set<String> right = new HashSet<String>();
        List<String> newChain = new ArrayList<String>();

        // NB We assume that either a(0) and b(0) are the same or neither is in intersect.
        // This is a safe assumption in practice because they're both "wad".
        int idxA = 0, idxB = 0, nextA = 0, nextB = 0;
        while (idxA < a.size()) {
            nextA++;
            while (nextA < a.size() && !intersect.contains(a.get(nextA))) nextA++;
            String tailA = nextA < a.size() ? a.get(nextA) : "";
            left.add(tailA);

            nextB++;
            while (nextB < b.size() && !intersect.contains(b.get(nextB))) nextB++;
            String tailB = nextB < b.size() ? b.get(nextB) : "";
            right.add(tailB);

            if (left.equals(right) && tailA.equals(tailB)) {
                // We take the longer of idxA to nextA-1 or idxB to nextB - 1.
                if (nextA - idxA > nextB - idxB) newChain.addAll(a.subList(idxA, nextA));
                else newChain.addAll(b.subList(idxB, nextB));

                idxA = nextA;
                idxB = nextB;
            }
        }

        if (new HashSet<String>(newChain).size() == newChain.size()) return newChain;
        throw new IllegalStateException();
    }

    private static void loadGraph() {
        Set<String> words = new HashSet<String>();
        Set<String> prefixes = new HashSet<String>();
        Set<String> suffixes = new HashSet<String>();
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(path), "UTF-8"));
            String line;
            while ((line = br.readLine()) != null) {
                if (line.length() >= 3) {
                    words.add(line);
                    prefixes.add(prefix(line));
                    suffixes.add(suffix(line));
                }
            }
            br.close();
        }
        catch (IOException ioe) {
            throw new RuntimeException(ioe);
        }

        // Filter down to a core with decent reachability.
        prefixes.retainAll(suffixes);
        MutableGraph<String> g = new MutableGraph<String>();
        Iterator<String> it = words.iterator();
        while (it.hasNext()) {
            String line = it.next();
            if (prefixes.contains(prefix(line)) && prefixes.contains(suffix(line))) {
                // In the interests of keeping the number of edges down, I insert fake vertices.
                g.addEdge(prefix(line), line, 1);
                g.addEdge(line, suffix(line), 1);
            }
            else it.remove();
        }

        fullGraph = g;
        allWords = Collections.unmodifiableSet(words);
    }

    private static String prefix(String word) {
        return "#" + word.substring(0, 3) + "#";
    }

    private static String suffix(String word) {
        return "#" + word.substring(word.length() - 3, word.length()) + "#";
    }

    private static <V> Map<V, Integer> reachabilityCount(Graph<V> g, Set<V> sources) {
        List<Set<V>> sccs = StronglyConnectedComponents.analyse(g, sources);
        int n = sccs.size();

        // Within a strongly connected component, each vertex can reach each other vertex.
        // Then we need to also take into account the other SCCs which they can reach.
        // We can exploit the fact that we already have a topological sort of the DAG of SCCs to do this efficiently.
        Map<V, Integer> index = new HashMap<V, Integer>();
        for (int i = 0; i < n; i++) {
            for (V v : sccs.get(i)) index.put(v, i);
        }

        BitSet[] reachableSccs = new BitSet[n];
        Map<V, Integer> reachabilityCounts = new HashMap<V, Integer>();
        for (int i = 0; i < n; i++) {
            Set<V> scc = sccs.get(i);
            reachableSccs[i] = new BitSet(n);
            reachableSccs[i].set(i);
            for (V v : scc) {
                for (V w : g.getAdjacent(v)) {
                    int j = index.get(w);
                    if (j < i) reachableSccs[i].or(reachableSccs[j]);
                }
            }

            int count = 0;
            for (int j = reachableSccs[i].nextSetBit(0); j >= 0; j = reachableSccs[i].nextSetBit(j+1)) {
                count += sccs.get(j).size();
            }
            for (V v : scc) {
                reachabilityCounts.put(v, count);
            }
        }

        return reachabilityCounts;
    }

    private static <V extends Comparable<? super V>> V selectOptimalReachabilityCount(Graph<V> g, Set<V> candidates, Random rnd) {
        Map<V, Integer> r = reachabilityCount(g, candidates);

        int max = 0;
        List<V> attaining = new ArrayList<V>();
        for (V candidate : candidates) {
            int score = r.get(candidate);
            if (score > max) {
                max = score;
                attaining.clear();
            }
            if (score == max) attaining.add(candidate);
        }

        return selectRandom(attaining, rnd);
    }

    private static <T extends Comparable<? super T>> T selectRandom(Collection<T> elts, Random rnd) {
        List<T> deterministic = new ArrayList<T>(elts);
        Collections.sort(deterministic);
        Collections.shuffle(deterministic, rnd);
        return deterministic.get(0);
    }

    private static class FilteredGraph implements Graph<String> {
        private final Set<String> filteredVertices;

        public FilteredGraph(Collection<String> filteredVertices) {
            this.filteredVertices = new HashSet<String>(filteredVertices);
        }

        @Override
        public Set<String> getAdjacent(String node) {
            if (filteredVertices.contains(node)) return Collections.emptySet();

            Set<String> adj = new HashSet<String>(fullGraph.getAdjacent(node));
            adj.removeAll(filteredVertices);
            return adj;
        }

        @Override
        public double getWeight(String from, String to) {
            throw new RuntimeException("Not used");
        }
    }
}


Jelly, 8 bytes

Z¬Þ€UZṚḌ

Try it online!

How it works

Z¬Þ€UZṚḌ  Main link. Argument: M (2D array / matrix)

Z         Zip; transpose M by reading columns as rows.
 ¬Þ€      Sort each row of the transpose by logical NOT, pushing 0's to the end.
    U     Upend; reverse all sorted rows of the transpose.
     Z    Zip again, restoring rows from columns. Overhangs rise to the top.
      Ṛ   Reverse the order of the rows.
       Ḍ  Decimal; convert the rows from base 10 to integer.


"Early bird" squares Definition

If you take the sequence of positive integer squares, and concatenate them into a string of digits (i.e. 149162536496481100...), an "early bird" square is one that can be found in this string ahead of its natural position.

For example, 72 (the number 49), can be found at an offset of 2 in the string, although the natural position is at offset 10. Thus 7 is the first "early bird" square.

Note that for it to be considered an "early bird" square, all the digits in the square must occur before the start of the natural position. A match that partially overlaps the natural position does not count.

a(n) is the nth positive integer k such that k2 is an "early bird" square.

Task

Given a positive integer n, output a(n).

You can use 1-based or 0-based indexing, but if you use 0-based indexing, please say so in your answer.

You solution should be able to handle at least as high as a(53) (or if you're using 0-based indexing, a(52)).

Testcases

n     a(n)
1     7
2     8
3     21
4     25
5     46
6     97
7     129
8     161
9     196
10    221
...
13    277
...
50    30015
51    35000
52    39250
53    46111

References

OEIS A181585

JavaScript (ES6), 51 49 45 bytes

1-indexed.

f=(n,s=k='')=>n?f(n-!!s.match(++k*k),s+k*k):k

Demo

f=(n,s=k='')=>n?f(n-!!s.match(++k*k),s+k*k):k

for(n = 1; n <= 20; n++) {
  console.log('a(' + n + ') = ' + f(n))
}

Formatted and commented

f = (                         // f = recursive function taking:
  n,                          //   n = input
  s = k = ''                  //   s = string of concatenated squares, k = counter
) =>                          //
  n ?                         // if we haven't reached the n-th term yet:
    f(                        //   do a recursive call with:
      n - !!s.match(++k * k), //     n decremented if k² is an early bird square
      s + k * k               //     s updated
    )                         //   end of recursive call
  :                           // else:
    k                         //   return k

Non-recursive version, 53 bytes

This one does not depend on your engine stack size.

n=>{for(k=s='';n-=!!(s+=k*k).match(++k*k););return k}

Try it online!


Find minimum difference between numbers in array STDIN: Array of integers

STDOUT: Smallest difference (the difference between the closest two numbers in the array).

Rules: Given an array of positive integers find the difference between the closest two numbers in the array. Performance should be taken into consideration.

Example:

STDIN: [55, 99, 6, 29, 1, 523, 3]

STDOUT: 2 (e.g. 3-1)

Scoring: Although somewhat informal, the shortest, most efficient (performance wise) will win. Creativity will also be taken into consideration.

The R language

23 characters,  O(n log n)

min(diff(sort(scan())))

Example:

> min(diff(sort(scan())))
1: 55 99 6
4: 29 1 523 3
8:
Read 7 items
[1] 2

...The [1] 2 shows the result 2. (the [1] is to keep track of where in the result vector your are since in R all values are vectors - in this case of length 1)


How to write a C program for multiplication without using the * and + operators? Is it possible to write a C program that multiplies two numbers without using the multiplication and addition operators?

I found this on Stack Overflow. Please help this poor programmer with his problem. And please don't give answers like c = a/(1/((float)b)), which is exactly the same as c = a*b. (And is already given as an answer.)

The answer with the most upvotes on January 19th 2014 wins.

Note: This is a code-trolling question. Please do not take the question and/or answers seriously. More information is in code-trolling.

Always use recursion

Recusion is the right way!

int inc(int x) {
    return x&1?inc(x>>1)<<1:x|1;
}

int dec(int x) {
    return x&1?x^1:dec(x>>1)<<1|1;
}

int add(int x, int y) {
    return x?add(dec(x),inc(y)):y;
}

int mul(int x, int y) {
    return x?x^1?add(y,mul(dec(x),y)):y:0;
}

int main() {
    int a, b;
    scanf("%i\n%i", &a, &b);
    printf("%i", mul(a,b));
}


Program that outputs a program that outputs a program ... that outputs "Hello!" Challenge

Write the shortest program P such that

P takes any positive integer n as input, and outputs a program string P1
executing P1 (with no input) outputs a program string P2,
executing P2 (with no input) outputs a program string P3,
...
executing Pn (with no input) outputs exactly "Hello!" (without the quotes).

Schematically:

                P(n) → P1 → P2 → ... → Pn → Hello!

Criteria

I/O is via stdin/stdout.
Program length is measured in bytes.
Programs consist only of ASCII printable characters.
There must be no duplicates among the programs P, P1,...,Pn.

EDIT: Programs P, P1,...,Pn are meant to be source code, and "executing the program" refers to whatever processing produces the output (i.e., interpretation, compilation & execution, etc.).

Golfscript 39 14

~'Hello!'{`}@*

Example:

Assuming that n=4 and our program is P, these are the steps:

Run P with parameter 4. The output is "\"\\\"\\\\\\\"Hello!\\\\\\\"\\\"\"" (P1)
Running P1 outputs "\"\\\"Hello!\\\"\"" (P2)
Running P2 outputs "\"Hello!\"" (P3)
Running P3 outputs "Hello!"(P4)
Running P4 outputs Hello!. If you don't trust me, follow this link ☺.


Print the N-bonacci sequence This isn't very widely known, but what we call the Fibonacci sequence, AKA
1, 1, 2, 3, 5, 8, 13, 21, 34...

is actually called the Duonacci sequence. This is because to get the next number, you sum the previous 2 numbers. There is also the Tribonacci sequence,
1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201...

because the next number is the sum of the previous 3 numbers. And the Quadronacci sequence
1, 1, 1, 1, 4, 7, 13, 25, 49, 94, 181, 349, 673...

And everybody's favorite, the Pentanacci sequence:
1, 1, 1, 1, 1, 5, 9, 17, 33, 65, 129...

And the Hexanacci sequence, the Septanacci sequence, the Octonacci sequence, and so on and so forth up to the N-Bonacci sequence.
The N-bonacci sequence will always start with N 1s in a row.
The Challenge
You must write a function or program that takes two numbers N and X, and prints out the first X N-Bonacci numbers. N will be a whole number larger than 0, and you can safely assume no N-Bonacci numbers will exceed the default number type in your language.  The output can be in any human readable format, and you can take input in any reasonable manner. (Command line arguments, function arguments, STDIN, etc.)
As usual, this is Code-golf, so standard loopholes apply and the shortest answer in bytes wins!
Sample IO
#n,  x,     output
 3,  8  --> 1, 1, 1, 3, 5, 9, 17, 31
 7,  13 --> 1, 1, 1, 1, 1, 1, 1, 7, 13, 25, 49, 97, 193
 1,  20 --> 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
 30, 4  --> 1, 1, 1, 1       //Since the first 30 are all 1's
 5,  11 --> 1, 1, 1, 1, 1, 5, 9, 17, 33, 65, 129

Boolfuck, 6 bytes

,,[;+]

  You can safely assume no N-Bonacci numbers will exceed the default number type in your language.

The default number type in Boolfuck is a bit. Assuming this also extends to the input numbers N and X, and given that N>0, there are only two possible inputs - 10 (which outputs nothing) and 11 (which outputs 1).

, reads a bit into the current memory location. N is ignored as it must be 1. If X is 0, the loop body (surrounded by []) is skipped. If X is 1, it is output and then flipped to 0 so the loop does not repeat.


Together Everyone Achieves More (related: one, two, three)

An acrostic is a style of poem/writing where the beginning character of each line, when read vertically, also produces a word or message. For example,

Together
Everyone
Achieves
More

also spells out the word TEAM when the first column is read vertically.

Acrostics are a subset of mesostics, where the vertical word can be anywhere in the horizontal words. For example, the TEAM one above could also be written as a mesostic as follows

   togeTher
everyonE
       Achieves
       More

along with several other variations.

The challenge here will be to produce an acrostic or mesostic from a given list of input words.

Input

A list of words in any any suitable format.
The list will only contain words made from lowercase [a-z].
The list is guaranteed to form an acrostic or a mesostic (no need to handle bogus input).
One of the words in the input will form the vertical word, while the rest make the horizontal words - part of the challenge here is to find the appropriate vertical word, so it cannot be taken separately.

Output

The ASCII-art acrostic or mesostic formed from the input words, written to STDOUT or returned, in any reasonable format.
The corresponding vertical word must be capitalized (as in the examples).
Leading spaces to get the vertical word to line up appropriately are required. Trailing spaces, and leading/trailing newlines are optional. Extra leading spaces are fine as well, so long as the words align correctly.
If both an acrostic and mesostic are possible, output only the acrostic.
If more than one acrostic/mesostic is possible, your code can output any or all of them.

Rules

Either a full program or a function are acceptable.
Standard loopholes are forbidden.
This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.

Examples

['together', 'team', 'everyone', 'achieves', 'more']
Together
Everyone
Achieves
More

['aaa', 'aaa', 'aaa', 'aaa']
Aaa
Aaa
Aaa
# One output, or multiple (of the same) output is allowed

['aaa', 'aaa', 'aab', 'baa']
Aaa
Aaa
Baa
# This is the only allowed output, since others would be mesostic, which are lower priority

['live', 'every', 'love', 'very', 'ohio']
Live
Ohio
Very
Every
# Note that 'live' couldn't be the vertical word since then it would be a mesostic, which is lower priority output

['cow', 'of', 'fox']
cOw
 Fox
# A shorter mesostic test case

['late', 'ballroom', 'anvil', 'to', 'head']
anviL
   bAllroom
    To
   hEad

Brachylog, 145 bytes

p~c[A:B:C],Bl1,A:CcP@pz:cahgB,P:1a~@nw|lL,?:laot:" "rjg:Ljb:sa:?z:cap~c[A:B:C],Bl1,A:Cc@pz:caZ:LmgB,Zl-yM,Z:M:Lz:2az:ca~@nw
bB,?h@u:Bc
b#=,?h@u|h

Try it online!

(Takes half a minute, so be patient.)


Solve a 2x2 Eigensystem For those with a little linear algebra background, the challenge is as simple as this: determine the eigenvalues and eigenvectors of a given complex 2x2 matrix. You may skip ahead to The Challenge for I/O details, etc. For those who need a little refresher on eigensystems, read on.
Background
The characteristic equation of a matrix \$A\$ is defined by
$$\det| A - λI | = 0$$
where \$λ\$ is a complex (scalar) parameter, \$I\$ is the identity matrix and \$\det|...|\$ is the determinant. The left-hand side evaluates to a polynomial in \$λ\$, the characteristic polynomial, which is quadratic in the case of 2x2 matrices. The solutions of this characteristic equation are the eigenvalues of \$A\$, which we will denote as \$λ_1\$ and \$λ_2\$.
Now the eigenvectors \$v_i\$ of \$A\$ satisfy
$$Av_i = λ_iv_i$$
For each \$λ_i\$, this gives you a system of two equations in two unknowns (the components of \$v_i\$), which can be solved quite easily. You will notice that the system is actually underspecified, and the magnitude of the eigenvectors are not determined by the equations. We will usually want the eigenvectors to be normalised, that is \$\sqrt{|x|^2 + |y|^2} = 1\$, where \$x\$ and \$y\$ are the vector components, \$|x|^2\$ is \$x\$ multiplied by its complex conjugate.
Note that the eigenvalues may be degenerate, i.e. \$λ_1 = λ_2\$. In this case, you may or may not be able to satisfy the single system of equations with two linearly independent eigenvectors.
The Challenge
Given a 2x2 matrix with complex elements, determine its two (possibly identical) eigenvalues and a normalised eigenvector for each eigenvalue. The resulting numbers must be accurate to at least 3 (decimal) significant digits. You may assume that the real and imaginary parts of any matrix element is in the range \$[-1,1]\$.
You may write a function or a program, taking input via STDIN, command-line argument, prompt or function argument. You may output the result to STDOUT, a dialog box or as the function return value.
You may use any convenient (but unambiguous) string or list format for input and output. You can also choose between pairs of floats or complex types to represent the individual numbers.
You must not use built-in functions for solving eigensystems (like Mathematica's Eigenvectors or Eigensystem) or equation solvers.
This is code golf, so the shortest answer (in bytes) wins.
Examples
Each example is three lines: the input, the eigenvalues and the corresponding eigenvectors in the same order. Note that the eigenvectors are only determined up to their phase, and that in the case of degenerate eigenvalues, the eigenvectors may actually be arbitrary (as in the first example).
[[1.0, 0.0], [0.0, 1.0]]
[1.0, 1.0]
[[1.0, 0.0], [0.0, 1.0]]

[[0.0, 0.4], [-0.1, -0.4]]
[-0.2, -0.2]
[[0.894427, -0.447214], [0.894427, -0.447214]]

[[0.3, 0.1], [0.4, -0.9]]
[-0.932456, 0.332456]
[[-0.0808731, 0.996724], [0.951158, 0.308703]]

[[0.5, -1.0], [0.8, -0.5]]
[0.74162i, - 0.74162i]
[[0.745356, 0.372678 - 0.552771i], [0.745356, 0.372678 + 0.552771i]]

[[-0.0539222 + 0.654836i, -0.016102 + 0.221334i], [0.739514 - 0.17735i, -0.0849216 + 0.77977i]]
[0.238781 + 0.984333i, -0.377625 + 0.450273i]
[[0.313668 + 0.322289i, 0.893164], [-0.236405 - 0.442194i, 0.865204]]

[[-0.703107 - 0.331792i, 0.286719 - 0.587305i], [-0.418476 + 0.396347i, -0.885934 + 0.50534i]]
[-1.13654 - 0.32678i, -0.4525 + 0.500329i]
[[0.833367, -0.248208 - 0.493855i], [-0.441133 - 0.408236i, 0.799215]]

[[-0.156312 + 0.788441i, 0.045056 - 0.579167i], [0.130741 - 0.97017i, 0.049183 - 0.590768i]]
[-0.181759 + 1.11738i, 0.0746298 - 0.919707i]
[[0.86955, -0.493846 + 0.000213145i], [0.318856 - 0.0181135i, 0.94763]]

Python 2, 198 bytes
a,b,c,d=input()
H=(a+d)/2
D=(H*H-a*d+b*c)**.5
X,Y=H+D,H-D
p,q,r,s=[[1,0,0,1],[b,X-a,b,Y-a],[X-d,c,Y-d,c]][2*(c!=0)or(b!=0)]
A=abs
V=A(A(p)+A(q)*1j)
W=A(A(r)+A(s)*1j)
print[X,Y],[[p/V,q/V],[r/W,s/W]]

Input is a flat list of 4 complex numbers via STDIN, e.g.
[0.0+0j, 0.4+0j, -0.1+0j, -0.4+0j]

Note that Python uses j instead of i for complex numbers.
Output is two lists, the first containing the eigenvalues and the second containing the eigenvectors, e.g.
[(-0.2+0j), (-0.2+0j)]
[[(0.8944271909999159+0j), (-0.4472135954999579+0j)], [(0.8944271909999159+0j), (-0.4472135954999579+0j)]]

(newline inserted for clarity)


Bi-directional translator Bi-directional translator
The challenge is to create a translator that can translate a [a-zA-Z ] string into another string according to the mappings below. The translator should also be able to translate translated text back into its normal form (hence bi-directional). Case doesn't have to be maintained and can be either lower/uppercase (or both lower and upper-cased) in the output, however your program should be able to handle either lower/uppercase strings.
Here is the specification of the mappings for this challenge:
-------------------
|Letter | Mapping |
-------------------
|   S   |    9    |
|   F   |    1    |
|   H   |    5    |
|   X   |    =    |
|   Z   |   {N}   |
|   M   |   --*   |
|   N   |   :)    |
|   G   |    ]    |
|   T   |    [    |
-------------------

Here are some example in/outputs:
(The " or ... or ..." obviously shouldn't be in your actual output, its just to demonstrate the possible outputs)
> ABS
< AB9 or ab9 or Ab9 or aB9

> foo
< 1oo or 1OO or ...

> FIZZ BUZZ
> 1i{N}{N} bu{N}{N} or 1I{N}{N} BU{N}{N} or ...

> {n}[:)
< ztn or ZTN or ...

> bar
< bar or BAR or ...

The inputs will always be in [a-zA-Z ] or a "translated" string containing the mapped symbol, other symbols or characters outside wouldn't be inputted.

JavaScript (ES6),  118 113  109 bytes

s=>s.toUpperCase(A=[':)',...'NF1G]H5S9T[X=Z','{N}','M','--*']).replace(/[{-]..|:?./g,c=>A[A.indexOf(c)^1]||c)

Try it online!
How?
Because the input is guaranteed to contain exclusively [a-zA-Z] and/or the special patterns, we can use the following minimal regular expression to match them all:
/[{-]..|:?./g
 [{-]..        // either "{" or "-" followed by 2 other characters
               // -> to match "{N}" or "--*"
        :?.    // or any character, preceded by an optional ":"
               // -> to match ":)" or any single character

Working on the uppercase version of the input, we look for the position of each matched pattern in the lookup array A[] and replace it with its counterpart, or leave it unchanged if it is not found (which may only happen for ABCDEIJKLOPQRUVWY).


Find the program that prints this integer sequence (Robbers' thread) This is the robbers' thread. The cops' thread goes here.

In the cops thread, the task was to write a program/function that takes a positive (or non-negative) integer and outputs/returns another number (not necessarily integer). The robbers task is to unscramble the code the cops used to produce this output.

The cracked code doesn't have to be identical, as long as it has the same length and any revealed characters are in the correct positions. The language must also be the same (version numbers can be different). The output must of course be identical.

No-ops can be used in robber's solution.

The winner of the robbers thread will be the user who has cracked the
most submissions by May 7th 2016. If there's a tie, the user who has cracked submissions with the longest combined code will win.

The submission should be formatted like this:

Language, nn characters (including link to answer), Cop's username

Code:

function a(n)
    if n<2 then
        return n
    else
        return a(n-1) + a(n-2)
    end
end

Output

a(0) returns 0
a(3) returns 2

Optional explanation and comments.

MATL, 5 bytes, Luis Mendo
H5-*|

This code calculates abs((2-5)*input) which is just a(n)=3*n for positive numbers, which is http://oeis.org/A008585


Print multiplication tables by input In this challenge you've to print multiplication tables by input, Here are some examples:

Input: 2

Output:
0 2  4 6 8  10  12  14  16  18  20

Input: 20

Output: 20 40 60 80 100 120 140 160 180 200

Rules

The shortest code in bytes wins.
This challenge is a code-golf, It follows code-golf general rules (code-golf)
If, just if, your code can't print number, you can use letters, Here is an example:

Input: B

Output: B D F H J L N P R T
You can choose to start from 0 or your number (like 20). You can choose if put spaces or don't. The challenge is free, just take an input and print multiplication tables.
Your output must list the first 10 members of the times table for the given number. You may leave out 0*n.

MATL, 4 bytes

10:*

Breakdown:

        % Implicit input
10:     % Create a list from 1 2 ... 10
   *    % Multiply list by input
        % Implicit output

Try it online


Histogram generation Write the shortest program that generates a histogram (a graphical representation of the distribution of data).

Rules:

Must generate a histogram based on the character length of the words (punctuation included)
input into the program. (If a word is 4 letters long, the bar representing the number 4 increases by 1)
Must display bar labels that correlate with the character length the bars represent.
All characters must be accepted.
If the bars must be scaled, there needs to be some way that is shown in the histogram.

Examples:

$ ./histogram This is a hole in one!
1 |#
2 |##
3 |
4 |###

$./histogram Extensive word length should not be very problematic.
1 |
2 |#
3 |#
4 |##
5 |
6 |##
7 |
8 |
9 |#
10|
11|
12|#

./histogram Very long strings of words should be just as easy to generate a histogram just as short strings of words are easy to generate a histogram for.
1 |##
2 |#######
3 |#
4 |#######
5 |###
6 |#
7 |##
8 |##
9 |##

Python - 83 characters
Seems that we can take input from anywhere, so this takes input during execution, rather than from the command line, and uses Ejrb's suggestion to shorten it by 8.
s=map(len,raw_input().split())
c=0;exec'c+=1;print"%3d|"%c+"#"*s.count(c);'*max(s)

Python - 91 characters
This will fall over with quotes.
import sys;s=map(len,sys.argv[1:])
for i in range(1,max(s)+1):print"%3d|"%i+'#'*s.count(i)

Input:
> python hist.py Please write a specification rather than giving a single example which, solely by virtue of being a single example, cannot express the range of acceptable output styles, and which doesnt guarantee to cover all corner cases. Its good to have a few test cases, but its even more important to have a good spec.

Output:
  1|#####
  2|######
  3|#####
  4|##########
  5|######
  6|#############
  7|####
  8|#
  9|##
 10|#
 11|
 12|
 13|#


Remove loops from a walk I've been playing around with a robot on the coordinate plane. This robot is able to tell me if it goes left, right, up, or down by reporting back a string consisting of the letters L, R, U, and D, such as DLURRDLURDLLLRRLRLDURRU. Each character represents a movement of one unit. However, it seems that the robot is going in loops on the plane, returning to coordinates that it has already visited. I don't want the robot to do that. I'd like the robot to tell me about the path it takes without any loops included - these loops should be removed from left to right in the string. Every step in the string it reports should represent movement to a cell that it has not yet visited before. If the robot ends where it starts, then it should report back an empty string.

Test cases

ULRURU -> UURU
URDLDRU -> DRU
LLLLRRRL -> LL
LLLULRRRL -> LLLUR
UURDDRULDL -> {empty string}
DLURRDLURDLLLRRLRLDURRU -> R
URULLLDLUULDDLDRDDLLLLLDLLUUULLURU -> URULLLDLUULDDLDRDDLLLLLDLLUUULLURU

This is a standard code golf challenge, where the shortest answer wins. Standard rules apply.

Jelly, 20 bytes

O2ȷ:ı*S
ẆÇÐḟḢ⁸œṣFµÐL

Try it online! Or see the test-suite.

How?

O2ȷ:ı*S - Link 1, distance travelled: list of UDLR characters
O       - ordinals -> U:85 D:68 L:76 R:82
 2ȷ     - 2000
   :    - integer division -> U:23 D:29 L:26 R:24 (Note mod 4 these are 3 1 2 0)
    ı   - square root of -1  - i.e. (0+1j)
     *  - exponentiate -> U:(0-1j) D:(0+1j) L:(-1+0j) R:(1+0j)
      S - sum - 0 iff the path is a loop

ẆÇÐḟḢ⁸œṣFµÐL - Main Link: list of UDLR characters
         µÐL - loop until no change occurs:
Ẇ            -   all sublists
  Ðḟ         -   filter discard those which are truthy (non-zero) under:
 Ç           -     call last Link (1) as a monad
    Ḣ        -   head - X = first, shortest loop (if none this yields 0)
     ⁸       -   chain's left argument
      œṣ     -   split at sublists equal to X
        F    -   flatten


Calculate the first n perfect numbers Write a program that calculates the first n perfect numbers. A perfect number is one where the sum of the factors is the original number. For example, 6 is a perfect number because 1+2+3=6. No non standard libraries.The standard loopholes are forbidden.

Pyth - 27 25 bytes
Extremely super slow brute force approach.
K2W<ZQ~K1IqKsf!%KTr1KK~Z1

Trial division to factor, then while loop till length of perfect numbers is enough.
Try it here online.


Can Mario go to the end of this map Create a program that determines, given an input of the path, whether Mario can reach the end, denoted by E, from the start, denoted by S.

A path will look something like this:

S = E
=====

In a path, the various symbols and what they represent are:

=: wall/floor/ceiling. Mario cannot walk through wall , and cannot fall past a floor, or jump past a ceiling (he would hit his head)
  (space): air. Mario can walk through this, and jump through it, and fall through it
S: air, except showing where Mario starts. This will always appear in the left-most column of the input, at ground level.
E: air, except showing where Mario wants to get. This will always appear in the right-most column of the input, at ground level.

The input will have spaces at every place where Mario could walk.

Mario can only move forward; in this example Mario cannot get to the goal

S
===

 ===
   E
====

nor can he in this one

    E
   ==
==
  #==
==
   ==
==
S  ==
======

However, he can reach the space denoted by # (which will not appear in input), because he can jump up to four cells high; Mario is superhuman. As another example of his superhumanity:

S
=
=
=
=
=
= #
= =
=
=
=
=     E
=======

Mario can get to the E by falling the great distance, surviving, and walking calmly to E. Note that he cannot reach the #, because Mario falls straight down.

Mario can jump really high, but not very far forward by comparison.

S   E
== ==
 = =

Mario may attempt to jump the gap, but he will fail, and fall straight in. he cannot reach the end.

Mario can reach the goal in all of these examples:

 E
 =
 =
 =
S=
==

 =
 =   E
S=   =
==   =
 =   =
 =====

S
=

=  E
====

This is code golf, so fewest bytes wins!

Slip, 38 27 25 bytes

S>(`=<<`P{1,5}>`P>`P*)+#E

Requires input to be padded to a rectangle such that there are spaces in every cell Mario needs to traverse (potentially with a leading line full of spaces). Prints either a string representing the valid path (which includes S, E and all the = walked on except the last) or nothing if no path exists.

Test it here.

Explanation

Slip was Sp3000's entry to our 2D pattern matching language design challenge. It's a bit like a 2D-extension of regex where you can give instructions to the engine's cursor when it's allowed or required to make left or right turns. It also has a convenient feature where you can prevent the cursor from advancing, allowing you to match a single position twice in a row (with different patterns).

Slip doesn't have something comparable to lookarounds in regex, but since you can move over any position multiple times, one can just test the condition and then return. We use this to ensure that we only jump when on the ground by moving into the ground tile after each step.

S           Match the starting position S.
>           Turn right, so that the cursor points south.
(           One or more times... each repetition of this group represents
            one step to the right.
  `=          Match a = to ensure we've ended up on ground level before.
  <<          Turn left twice, so that the cursor points north.
  `P{1,5}     Match 1 to 5 non-punctuation characters (in our case, either space,
              S or E, i.e. a non-ground character). This is the jump.
  >           Turn right, so that the cursor points east.
  `P          Match another non-ground character. This is the step to the right.
  >           Turn right, so that the cursor points south.
  `P*         Match zero or more non-ground characters. This is the fall.
)+
#           Do not advance the cursor before the next match.
E           Match E, ensuring that the previous path ended on the exit.


Illuminate a Mirrored Room Goal

In this competition, you are given a random room with one candle inside. The goal is to write the shortest program (this is golf) that determines what parts of the room are illuminated by the candle, by replacing the dark spots with @'s. The program should take a room from STDIN, with the output printed to STDOUT.

Example Input/Room

+------+
|  C   |
|      +--+
|  \      |
+---------+

The candle is represented with a C, and the walls/mirrors are represented with |,-,/, or \. The walls themselves are mirrors. The corners of the room are represented with a +.

Rooms will never have diagonal walls, and light will never be able to escape out of the room.

Also, the first character on a line is always going to be part of the wall off the room. The absolute last character on each line is going to be the opposite wall of the room. No characters between these two are going to be outside of the room.

Light and Reflection

The candle emits eight (laser-like) beams of light in eight basic directions: N, S, E, W, NE, SE, SW, and NW. These rays of light bounce off of the mirrors as described below:

Old Direction of Travel | Mirror | New Direction
N S E W NE SE SW NW       /        E W N S -- -- -- --
N S E W NE SE SW NW       \        W E S N -- -- -- --
N S E W NE SE SW NW       |        - - - - NW SW NE SW
N S E W NE SE SW NW       -        - - - - SE NE SW NE

A - represents the light being absorbed. Light is always absorbed by C's or +'s.  It is important to note that the lights reflects off of a mirror only when it is occupying the same space as the mirror. These rules are much easier to understand when you draw the reflection out on paper.

Example Output

As output, the program should print an image of the illuminated room, with dark spots written as an @, light spots left blank, and mirrors unaffected. For the above example, the output would be:

+------+
|  C   |
|@   @ +--+
| @\      |
+---------+

This means that, if you drew out the beams of light, they will never reach the spaces marked with @.

More examples

Input:
+-----+
|     |
|     |
|  C  |
|     |
|     |
+-----+
Output:
+-----+
| @ @ |
|@   @|
|  C  |
|@   @|
| @ @ |
+-----+

Input:
+-----+
|  \  |
|/ C \+-+
|       |
|  \ - ++
+------+
Output:
+-----+
|  \ @|
|/ C \+-+
|      @|
| @\ -@++
+------+

Python, 292 chars

import sys
R=''
for x in sys.stdin:R+='%-97s\n'%x[:-1].replace(' ','@')
M={'/':'-98/d','\\':'98/d'}
for d in(-98,-1,1,98,99,97,-97,-99):
 if d>98:M={'|':'d^2','-':'-d^2'}
 p=R.find('C')
 while 1:
  p+=d
  if R[p]in' @':R=R[:p]+' '+R[p+1:]
  elif R[p]in M:d=eval(M[R[p]])
  else:break
print R,

Reads in the room, makes it rectangular, then walks out from the candle in all directions.  M contains the active mirror characters and their effect (/\ for the cardinal directions, |- for the others)

Can handle rooms up to 97 characters wide.


Calculating dehydration synthesis results Disclaimer: This challenge is extremely scientifically inaccurate.
;)

Given an input of a list of molecules, output what the result would be if they
were to all combine via dehydration synthesis, if possible.

For the purposes of this challenge, although this description is inaccurate, a
dehydration reaction
between two molecules is performed as follows:

Remove OH (one oxygen and one hydrogen atom) from either of the two
molecules.
Remove H (a single hydrogen atom) from the other one.
Combine the two molecules into one.

For instance, combining two
C6H12O6 molecules via dehydration
synthesis would result in
C12H22O11. Note that there are
two less Hs and one less O in the product than in the reactants. (These
missing parts would form H2O, hence "dehydration," but
that's irrelevant to this challenge.)

An example of molecules that cannot be combined via dehydration synthesis is
C6H12O6 +
CO2. The required amount of hydrogen and oxygen is
present, but neither OH nor H can be taken from the
CO2.

The format of the input for each molecule is a list of atoms concatenated. An
atom is always a single capital letter, possibly followed by a single lowercase
letter (you don't have to handle atoms like Uuo). Atoms may also have
integers ≥ 2 after them, representing how many of them there are; if this
number is not present, it is assumed to be 1. Atoms will never be repeated
within the same molecule.

Input may be provided as either an array/list/etc. of strings, or a single
string separated by any non-alphanumeric character. Output must be a single
string, but the output for "invalid input" (i.e. a list of molecules that
cannot be combined via dehydration synthesis) may be any string containing at
least one non-alphanumeric character (to distinguish from valid output). The
order of the atoms in the output does not matter.

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

Test cases (invalid output is represented here by an asterisk *):

In                                                Out
------------------------------------------------------------------
C6H12O6 C6H12O6 C6H12O6 C6H12O6 C6H12O6 C6H12O6 | C36H62O31
CHO5 CH2 CH2 CH2 CH2 CH2                        | C6H
CHO4 CH2 CH2 CH2 CH2 CH2                        | *
H H H CH3O3                                     | C
H H H CH4O2                                     | *
C6H12O6 ABCDELMNOP C6H12O6                      | *
HO HO HO H3                                     | <empty string>
HgO4 C6H12O6                                    | *
HgHO4 C6H12O6                                   | HgH11O9C6
PdZnXeRaHO KrArKRbFH                            | PdZnXeRaKrArKRbF

Python (337 336 chars)
import re
i=input().split()
a,d,o,e=[],{},"",len(i)-1
for b in i:a.append(dict(re.findall(r"([A-Z][a-z]*)(\d*)",b)))
a=[{b:int(c[b])if c[b]else 1for b in c}for c in a]
for b in a:
 for c in b:d[c]=c in d and d[c]+b[c]or b[c]
 if"H"not in b:d["-"]=0
d["H"]-=2*e;d["O"]-=e
for b in d:o+=b+(str(d[b])if d[b]-1else"")if d[b]else""
print(o)

Here is an example of how to use this program:
sh3.14$ python dehydrate.py <-Run the program
C6H12O6 HgHO4               <-Input
O9H11C6Hg                   <-Output

Try it!


Monday Mini-Golf #7: Simplify ingredient measurements Monday Mini-Golf: A series of short code-golf challenges, posted (hopefully!) every Monday.
Sorry it's late; I realized 90% of the way through writing out a different idea that it was a duplicate.

My family is rather large, so we eat a lot of food. We usually need to double, triple, or even quadruple recipes to make enough food! But as multiplying the measurements can be a pain, it'd be nice to have a program to do this for us.

Challenge

Your challenge is to create a program or function that takes in a measurement as a number N and a letter L, and returns the same measurement, simplified as much as possible. Here's the required measurement units (all are American, like my family), and their corresponding letters:

1 cup (c) = 16 tablespoons (T) = 48 teaspoons (t)
1 pound (l) = 16 ounces (o)
1 gallon (g) = 4 quarts (q) = 8 pints (p) = 128 fluid ounces (f)

"simplified as much as possible" means:

Using the largest measurement unit possible. Each unit can have a remainder of 1/4, 1/3, 1/2, 2/3, or 3/4.
Turning the result into a mixed number, if necessary.

For example, 4 o is four ounces, which becomes 1/4 l, a quarter pound. 8 t, 8 teaspoons, becomes 2 2/3 T.

Details

The input may be taken in any reasonable format; same with output. (1 t, 1,"t", 1\nt, etc.)
Make sure any fractional part is dealt with properly. (11/4 in place of 1 1/4 is not allowed.)
The number will always be a mixed number, and will always have a denominator of 2, 3, or 4 (or none). (no 1 1/8 T, no 1.5 T, etc.)
As a result of the above, no downward conversions (e.g. cups to tablespoons) are ever needed.
The letter will always be one of the letters listed above (Tcfglopqt).

Test-cases

Here's an large list, hopefully covering all types of cases:

Input   | Output
--------+--------
1/2 t   | 1/2 t
3/4 t   | 1/4 T
1 t     | 1/3 T
1 1/2 t | 1/2 T
2 t     | 2/3 T
2 1/4 t | 3/4 T
2 1/2 t | 2 1/2 t
3 t     | 1 T
10 t    | 3 1/3 T
16 t    | 1/3 c
5 1/3 T | 1/3 c
8 T     | 1/2 c
16 T    | 1 c
36 T    | 2 1/4 c
1/4 c   | 1/4 c
1024 c  | 1024 c
1 o     | 1 o
4 o     | 1/4 l
5 1/3 o | 1/3 l
5 2/3 o | 5 2/3 o
8 o     | 1/2 l
28 o    | 1 3/4 l
28 l    | 28 l
2 f     | 2 f
4 f     | 1/4 p
8 f     | 1/4 q
16 f    | 1/2 q
32 f    | 1/4 g
64 f    | 1/2 g
128 f   | 1 g
2/3 p   | 1/3 q
1 1/3 p | 2/3 q
2 p     | 1/4 g
1 q     | 1/4 g

Scoring

Our kitchen is very small, so the code should be as short as possible, so as not to make the kitchen more cramped. Shortest valid code in bytes wins; tiebreaker goes to submission that reached its final byte count first. The winner will be chosen next Monday, Nov 9. Good luck!

Please note that this challenge is similar to, but not a duplicate of, World Big Dosa.

Mathematica, 349 334 330 322 bytes

This answer section felt a little lonely. So uh, here's my attempt. Input should be given as in the test cases.

n=ToExpression@StringSplit@InputString[];i=#~Mod~1&;b=#&@@n;If[Length@n==3,{x,y,z}=n,{x,y,z}=If[IntegerQ@b,{b,0,Last@n},{0,b,Last@n}]];v={0,1/4,1/3,1/2,2/3,3/4};s=<|T->16,t->3,o->16,q->4,p->2,f->16|>;r=<|T->c,t->T,o->l,f->p,p->q,q->g|>;If[v~MemberQ~i[a=(x+y)/s@z],{x,y,z}={Floor@a,i@a,r@z}]~Do~3;Print@Row[{x,y,z}/. 0->""]

Explanation

First get the user input, split that input on whitespace, and assign that to n. i=#~Mod~1& creates a function that gets the fractional part of a number, by taking it mod 1. b=#&@@n will simply get the first item in n; that would be everything up to the first space.

If n is 3 elements long, that means we have an integer, a fraction, and a unit. {x,y,z}=n will assign x, y and z to be the three parts of n.
The other case is that n is not 3 elements long; that means it’ll be 2 elements long instead. To stay consistent with above, we want x to be the integer part, y to be the fraction, and z the unit. So in this case, we need to check:

If b (the first element of n) is an integer, then x=b, y=0 and z=Last@n (the last element of n).
If b isn’t an integer, that means we only have a fraction with no integer. So we want to swap x and y from above; instead, x=0, y=b, and z is the same as above.

Now we need to set up some lists:

v = {0, 1/4, 1/3, 1/2, 2/3, 3/4} is the list of acceptable fractions, as stated in the question.

s = <|T -> 16, t -> 3, o -> 16, q -> 4, p -> 2, f -> 16|> is an association (key-value pair, like a dictionary in Python) that represents the amount needed of a given unit to go “up” to one of the next largest unit. For example, o -> 16 is because 16 ounces are required before we go up to 1 pound.

r = <|T -> c, t -> T, o -> l, f -> p, p -> q, q -> g|> is the association that actually represents what the next unit up is. For example, T -> c means one unit larger than Tablespoons is cups.

If[v~MemberQ~i[a = (x + y)/s@z], {x, y, z} = {Floor@a, i@a, r@z}]~Do~3

Now, the maximum number of times we need to go up a unit is 3; that would be fluid ounces (f) -> pints (p) -> quarts (q) -> gallon (g). So, now we do the following 3 times:

Add x and y, (the integer and fractional parts)
From the s association above, get element z; that is, access the current unit, and get the corresponding value in that association.
Divide (x+y) by that value we got above, assign it to a, then get its fractional part.
If that part is in the list v, then we can go up one unit; set x to a rounded down (integer part), set y to the fractional part of a, then access the association r with the current unit z to get the next unit up, and set that to z.
If it’s not part of v instead, we don’t do anything, since it can’t be simplified.

Once that’s done 3 times, we print out the result:

Print@Row[{x,y,z}/. 0->””]

This simply prints out {x,y,z} in a row, but replaces any zeroes (if there’s no integer, or no fraction), with an empty string, so those don’t print out.