Golfing A Weasel Program Richard Dawkins in his book The Blind Watchmaker, describes a Weasel program. The algorithm can be described as follows:

Start with a random string of 28 characters. Valid characters are all upppercase letters, and space.

Make 100 copies of that string, with a 5% chance per character of that character being replaced with a random character.

Compare each new string with the target "METHINKS IT IS LIKE A WEASEL", and give each a score according to the number of letters in the string which are correct and in the correct position.

If any of the new strings has a perfect score (28), halt.

Choose the highest-scoring string from step 3. How you work out a tie is up to you, but only one string may be chosen. Take the chosen string and go to step 2.

The winner will be the shortest code snippet to get to the correct answer while printing the highest-scoring string of each generation in the following format:

If people could help by checking other peoples answers would be very helpful!

APL (143)

0{⍵≢T←'METHINKS IT IS LIKE A WEASEL':c∇⍨1+⍺⊣⎕←(⍕⍺),':'c'-- score:',s⊣c←⊃c/⍨G=s←⌈/G←{+/⍵=T}¨c←{⍵{⍵:⍺⋄C[?27]}¨9≠?28/20}¨100⍴⊂⍵}⊃∘(C←27↑⎕A)¨?28/27

Explanation:

0{...}⊃∘(C←27↑⎕A)¨?28/27: set C to the first 27 capital letters. There are only 26, so the 27th element will be a space. Select 28 random items from C. This will be the first ⍵. The first ⍺ (generation) will be 0.
⍵≢T←'METHINKS IT IS LIKE A WEASEL: set T to the string 'METHINKS IT IS LIKE A WEASEL'. As long as ⍵ is not equal to T:

{...}¨100⍴⊂⍵: Make 100 copies of ⍵. For each of these...

9≠?28/20: select 28 random numbers from 1 to 20. Make a bitmask where each 1 means that the random number was not equal to 9. (This means 5% chance of a 0).
⍵{⍵:⍺⋄C[?27]}¨: for each letter in ⍵, if the corresponding bit was 1, keep that letter, otherwise replace it with a randomly chosen element from C.

c←: store the 100 mutated strings in c.
G←{+/⍵=T}¨c: for each element in c, calculate the score (amount of characters that match T) and store the scores in G.
s←⌈/G: find the maximum score and store that in s.
c←⊃c/⍨G=s: select the first item from c whose score is equal to s (the maximum), and store it in c again.
⎕←(⍕⍺),':'c'-- score:',s: print the generation in the given format (⍺ is current generation, c is current best string, s is score)
c∇⍨1+⍺: Increment the generation and run the mutation again using the current best string (c) as input.


Where does the pivot belong? You will be given a positive integer as input.
The integer is the board of a seesaw.
Th integer will not have leading zeroes. You may take this input however you like.
Your task is to output the location of the pivot point of this seesaw, such that the board would balance.
A board balances if the moments on each side are equal in magnitude. A moment is calculated by multiplying the force by the distance from the pivot point. In this case, the force is equal to the digit.
For the integer 100 with a pivot point below the first 0, the moment on the left is 1x1=1. The moment on the right is 0x1=0. If the pivot point was below the second 0, the moment on the left would be 2x1=2 (because the 1 is now 2 away from the pivot).
For example, for the integer 31532 the pivot goes underneath the number 5. This is because the moments on the left are 3x2 + 1x1 = 7 and on the right the moments are 3x1 + 2x2 = 7.
The output for this integer is 3 because the pivot goes underneath the 3rd digit.
If the integer cannot be balanced, your code does not have to do anything - it can hang, error, output nothing - whatever you want.
Note that a pivot cannot go between two numbers. The pivot location must be an integer.
Test cases:
31532 -> 3
101 -> 2
231592 -> 4
8900311672 -> 5

Standard loopholes apply, this is code golf so shortest answer wins.

Haskell, 64 62 59 57 45 35 31 bytes

d l=sum(zipWith(*)[1..]l)/sum l

Try it online!


Winnable Solitaire Mancala Boards Mancala is the name of a family of board games that usually involve a series of cups filled with beads that the players manipulate. This challenge will use a specific rule set for a solitaire variant of the game.

The board consists of a "basket" at one end, followed by an infinite number of cups, numbered starting from 1. Some of the cups will have some number of beads in them. If the nth cup has exactly n beads in it, you may "sow" the beads from it. Sowing means to take all n beads out of the cup, then deposit them one at a time in each cup towards the basket. The last bead will go into the basket. The player wins when all of the beads on the board are in the basket.

Clearly, there are many boards which are not winnable, such as if there is exactly one bead in the second cup. There are no legal plays because all the cups with 0 beads cannot be sown, and the second cup does not have enough beads to be sown. This is obviously no fun, so your task will be to create winnable boards.

Task

Given a positive integer representing a number of beads output a list of non-negative integers representing the number of beads that should be put in each cup to make a winnable board as described above. This list should not contain any trailing zeroes.

For any given number of beads, there is always exactly one winnable board configuration.

Demonstration

This is a demonstration of how to play the winnable board for and input of 4. The winnable board is [0, 1, 3]. We start with the only available move, sowing the beads from the third cup to get [1, 2, 0]. Now we actually have a choice, but the only correct one is sowing the first cup, getting: [0, 2, 0]. Then we sow the second cup yielding [1, 0, 0] and finally we sow the first cup again to get all empty cups.

Test cases:

1 => [1]
2 => [0, 2]
3 => [1, 2]
4 => [0, 1, 3]
5 => [1, 1, 3]
6 => [0, 0, 2, 4]
7 => [1, 0, 2, 4]
8 => [0, 2, 2, 4]
9 => [1, 2, 2, 4]
10 => [0, 1, 1, 3, 5]
11 => [1, 1, 1, 3, 5]
12 => [0, 0, 0, 2, 4, 6]
13 => [1, 0, 0, 2, 4, 6]
14 => [0, 2, 0, 2, 4, 6]
15 => [1, 2, 0, 2, 4, 6]
16 => [0, 1, 3, 2, 4, 6]
17 => [1, 1, 3, 2, 4, 6]
18 => [0, 0, 2, 1, 3, 5, 7]
19 => [1, 0, 2, 1, 3, 5, 7]
20 => [0, 2, 2, 1, 3, 5, 7]

Big thanks to PeterTaylor for coming up with a program to generate test cases!

Python, 42 41 bytes

m=lambda n,i=2:n*[1]and[n%i]+m(n-n%i,i+1)


Find the last Sunday in every month of a given year F# solutions known inside 140 chars, and this is a Rosetta Code problem.

Required result on stdout or in a string variable for input year 2014:

2014-01-26 2014-02-23 2014-03-30 2014-04-27 2014-05-25 2014-06-29 2014-07-27 2014-08-31 2014-09-28 2014-10-26 2014-11-30 2014-12-28

As it was requested, for 1900:

1900-01-28 1900-02-25 1900-03-25 1900-04-29 1900-05-27 1900-06-24 1900-07-29 1900-08-26 1900-09-30 1900-10-28 1900-11-25 1900-12-30

And 2000:

2000-01-30 2000-02-27 2000-03-26 2000-04-30 2000-05-28 2000-06-25 2000-07-30 2000-08-27 2000-09-24 2000-10-29 2000-11-26 2000-12-31

Posed because dates seem to bring out awkwardness in most languages. More than permitting date libraries, I hope to see them! But if external to the base language, declare in the name of the post (e.g. C# + Jon Skeet's NodaTime).

Clarifications:

Year range 1900 to 3015
Gregorian calendar
If it otherwise matters, whatever is conventional for UK/London.
A program taking a commandline switch or stdin is fine, producing the result to stdout
A function taking a value for the year and returning a string is also fine.

Standard loopholes excluded. Looking forward to the APL, J, K solutions, and seeing some new date libraries.

Ruby, 91+6=97

#!ruby -prdate
$_=(Date.new(y=$_.to_i)...Date.new(y+1)).select(&:sunday?).chunk(&:mon).map{|k,v|v[-1]}*' '

Works out pretty well. select(&:sunday?) is pretty, and surprisingly, *' ' does all of the formatting by itself.


CJam, 16 15 13 12 bytes

q2*A~<$e`3=(

Test it here.

Explanation

The basic idea is to manipulate the string such that we can make CJam's built-in run-length encoding work for us.

Let's go through an example (the one from the question). The input string is

 _________
|         |
|  H   H  |
|  H H H  |
---H---H---

We repeat that twice:

 _________
|         |
|  H   H  |
|  H H H  |
---H---H---
 _________
|         |
|  H   H  |
|  H H H  |
---H---H---

And remove the last line:

 _________
|         |
|  H   H  |
|  H H H  |
---H---H---
 _________
|         |
|  H   H  |
|  H H H  |

Then we sort this string. It'll now have a bunch of newlines at the start, and then this (shortened by a few spaces to avoid a horizontal scrollbar):

                                    ---------HHHHHHHHHHHH__________________||||||||||||

While the suit character will vary, it'll always be an upper case letter, found in the fourth run of the sorted string (accounting for the newline). When we run-length encode this we get

[8 '\n] [46 ' ] [9 '-] [12 'H] [18 '_] [12 '|]]

So all we need to do is pick out the fourth  element and reverse it.

Here is a breakdown of the actual code:

q              e# Read the input.
 2*            e# Repeat twice.
   A~<         e# Remove the last 11 characters, i.e. the last line.
      $        e# Flatten into a single string and sort its characters.
       e`      e# Run-length encode: turns the sorted string into 5 pairs of numbers
               e# and characters.
         3=    e# Select the one corresponding to the suit.
           (   e# Pull off the number so that its printed after the suit.


Find how many pair elements sums up to N Based on a recent question in StackOverflow

Write a program/function that takes in one ARRAY/list and returns the number of pair-values which sums up to a given TOTAL.

Explaining

TOTAL=4, ARRAY=[1,3,7,1,-3] => RESULT=2

The result was 2 because 1 + 3 and 7 + -3 are valid pairs which sums up to TOTAL=4.

When one pair is formed, you should not count any of its values again
Also, you are not allowed to add any value that is not present in the ARRAY.

This is code-golf, shortest in bytes wins

All values will be between your language's int min-max.

Another cases

9, [1,2,3,5,4,6,7,-10] => 3          // [2,7]  [3,6]  [5,4]
0, [] => 0                           //
0, [1,-2,0,-1,2] => 2                // [1,-1]  [-2,2]
5, [5,5,5,0,-1,1,-5] => 1            // [5,0]
3, [7,-7,8,3,9,1,-1,5] => 0          //
2, [1,1] => 1                        // [1,1]
2, [1,1,1,1,1] => 2                  // [1,1]  [1,1]
4, [1,3,3,3] => 1                    // [1,3]

Pyth, 9 bytes

/sM{.cSE2

Test suite

Takes the number and array newline separated.

Explanation:

/sM{.cSE2
/sM{.cSE2Q    Implicit variable introduction.
              Implicit: Q = eval(input())
       E      Take the array as input.
      S       Sort the input.
    .c  2     Form all ordered pairs.
   {          Deduplicate.
 sM           Map each to its sum.
/        Q    Count the number of occurrences of Q in the resulting list.


Create a multi-level 5x5x5 Labyrinth with only one solution The aim of this challenge is to create the shortest code (in characters) that successfully do the following:

Specifications:

Must create a 5x5x5 labyrinth with exactly 1 possible solution (no more, no less)
The labyrinth must be created randomly It must be able to generate every existing solution if left running for years
The start and finish must be placed in *opposite corners
The map output must in one of the following formats:

Option output format 1 strings, printed or alerted:

xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx/
xxxxx,xxxxx,xxxxx,xxxxx,xxxxx

Option output format 2 arrays:

[[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx],
[xxxxx,xxxxx,xxxxx,xxxxx,xxxxx]]

Output Notes:

Use 0 for empty and 1 for squares
Break lines are NOT necessary
You decide what index is what, but just make sure to explain it well

*Here is an example of what I mean by opposite corners:

Clarifications:

Can NOT move in diagonal
Can NOT pass twice on the same path
Having inaccessible areas is allowed
You can go up/down more than one level in a row

Tips:

Don't see them as walls, instead see them as a 5x5x5 stack of squares that some of them are missing and you can go through the missing ones

C++ C, about 1000 670 643 395 297 248 chars

Sample output:

00111,10011,10111,00110,11000,
11001,01010,00100,11011,10101,
10111,10101,10001,01010,00101,
11001,11110,11100,11110,10101,
11100,10010,11001,10101,00000,

How it works: The program uses Brownian Motion to generate solutions. The start point is set. Then, a random point is selected and repeatedly moved randomly until it touches one and only one point on the start branch. The point is then set, and if it also touches the end point, the program exits and the matrix displayed. Since no point can join two branches, there is only one path through the labyrinth. The program uses the rand function, and a command line integer argument as the seed, so with a sufficient rand function it should be possible to eventually generate all valid labyrinths (this algorithm will not create unconnected areas however, so it won't generate all possible labyrinths).

Brownian motion was dropped since it turned out to be unneeded and it's removal simplifies the code significantly. I do think it made nicer labyrinths though. Likewise, the seed argument was dropped, since requiring a stateless random number generator makes more sense to me than a 128-bit seed.

It is possible for the program to get stuck in an infinite loop, since it is possible for situations where any point added to the branches would create multiple paths. This is fixable, but I think that it is rare enough to not be a concern for code golf.

#define M m[*p+1][p[1]][p[2]]
#define F(a,b)for(p[a]=5;p[a]--;putchar(b))
#define f for(i=3;i--;p[i]
p[]={4,4,4},h[3],m[7][6][6]={1};
main(i){
    for(M=2;h[1]^1||(M=1)^h[2];){
        f=rand()%5)
            h[i]=0;
        f++)
            p[i]++,
            h[M]++,
            p[i]-=2,
            h[M]++;
    }
    F(0,10)
        F(1,44)
            F(2,48+!M);
}

I've added newlines and indentation to the displayed code for readability.


Partition into increasing subsequences Specification

This challenge is simple to state: your input is a non-empty array of nonnegative integers, and your task is to partition it into as few increasing subsequences as possible.
More formally, if the input array is A, then the output is an array of arrays B such that:

Each arrays in B form a partition of A into disjoint (not necessarily contiguous) subsequences. Inductively, this means that either B is the singleton array containing A, or the first element of B is a subsequence of A and the rest form a partition of A with that subsequence removed.
Every array in B is (not necessarily strictly) increasing.
The number of arrays in B is minimal.

Both the input and output can be taken in the native array format of your language.
Note that there may be several correct outputs.

Example

Consider the input array A = [1,2,1,2,5,4,7,1].
One possible output is B = [[1],[1,2,4,7],[1,2,5]].
The partition condition is evident from this diagram:

A    1 2 1 2 5 4 7 1
B[0]               1
B[1] 1 2       4 7
B[2]     1 2 5

Also, each array in B is increasing.
Finally, A can't be split into two increasing subsequences, so the length of B is also minimal.
Thus it's a valid output.

Rules and scoring

You can write a function or a full program.
The lowest byte count wins, and standard loopholes are disallowed.
There is no time bound, but you should evauate your solution on all test cases before submitting it.

Test cases

Only one possible output is shown, but there may be several valid options.
In particular, the order of the arrays in the result doesn't matter (but each individual array should be in increasing order).

[0] -> [[0]]
[3,5,8] -> [[3,5,8]]
[2,2,2,2] -> [[2,2,2,2]]
[1154,1012,976,845] -> [[845],[976],[1012],[1154]]
[6,32,1,2,34,8] -> [[1,2,8],[6,32,34]]
[1,12,1,12,1,13] -> [[1,1,1,13],[12,12]]
[6,4,6,13,18,0,3] -> [[0,3],[4,6,13,18],[6]]
[1,2,3,2,3,4,7,1] -> [[1,1],[2,2,3,4,7],[3]]
[0,9,2,7,4,5,6,3,8] -> [[0,2,3,8],[4,5,6],[7],[9]]
[7,1,17,15,17,2,15,1,6] -> [[1,1,6],[2,15],[7,15,17],[17]]
[4,12,2,10,15,2,2,19,16,12] -> [[2,2,2,12],[4,10,15,16],[12,19]]
[10,13,9,2,11,1,10,17,19,1] -> [[1,1],[2,10,17,19],[9,11],[10,13]]
[3,7,3,8,14,16,19,15,16,2] -> [[2],[3,3,8,14,15,16],[7,16,19]]
[15,5,13,13,15,9,4,2,2,17] -> [[2,2,17],[4],[5,9],[13,13,15],[15]]

Haskell, 54 bytes

n#[]=[[n]]
n#(l:c)|[n]<=l=(n:l):c|1<2=l:n#c
foldr(#)[]

Usage example: foldr(#)[] [4,12,2,10,15,2,2,19,16,12]-> [[2,2,2,12],[4,10,15,16],[12,19]]

How it works: go through the input list starting at the right end. Build the output list (of lists) by prepending the current element n to first sublist l where n is less or equal to the head of l. If there's none, make a new singleton list of n at the end of the output list.


Convert to and from Base 94 The challenge

Make 2 programs which convert decimal to and from base 94, or a bidirectional program.

Base 94?

Base 94 is like any other base, but instead of 0 to 9 and letters, it uses ASCII characters 33 to 126. Not 127 because chr(127) is DEL. Not 32 because that's a space.

Examples

0 - ! or empty string
1 - "
93 - ~
94 - "!
2020 - 6O
14233221 - 2-n8

Scoring

For two programs, the score will be the sum of the byte count of both of the programs.

The bidirectional program is simply just the byte count. Consider it like a -50% to the score.

Haskell, 42 + 31 = 73 bytes

To base 94: 42 bytes

(l!!)
l="":tail[s++[c]|s<-l,c<-['!'..'~']]

Try it online!

Instead of using modular arithmetic, we generate the list l of all strings in the desired order and index into it.

The recursive definition of l is similar to this one for generating all strings, but modified to output strings in the desired order by appending the new character, and with a tail to prevent the analogue of leading zeroes.

From base 94: 31 bytes

foldl(\n->(94*n-33+).fromEnum)0

Try it online!

Iterates over the characters c of the string, updating the current value n to 94*n-33+fromEnum c.


Generate 100 Java Tuple classes Write a script that writes to standard output, or your language's equivalent, 100 lines of (valid) Java code that begins with:

class Tuple1 {public Object _0;}
class Tuple2 {public Object _0,_1;}
class Tuple3 {public Object _0,_1,_2;}
class Tuple4 {public Object _0,_1,_2,_3;}
class Tuple5 {public Object _0,_1,_2,_3,_4;}
class Tuple6 {public Object _0,_1,_2,_3,_4,_5;}
class Tuple7 {public Object _0,_1,_2,_3,_4,_5,_6;}
class Tuple8 {public Object _0,_1,_2,_3,_4,_5,_6,_7;}
class Tuple9 {public Object _0,_1,_2,_3,_4,_5,_6,_7,_8;}
class Tuple10 {public Object _0,_1,_2,_3,_4,_5,_6,_7,_8,_9;}
class Tuple11 {public Object _0,_1,_2,_3,_4,_5,_6,_7,_8,_9,_10;}
class Tuple12 {public Object _0,_1,_2,_3,_4,_5,_6,_7,_8,_9,_10,_11;}

The last line should begin with class Tuple100.

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

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

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

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


Depalindromize this string! Given a palindrome generated according to this challenge, depalindromize it.

Test cases

abcdedcba -> abcde
johncenanecnhoj -> johncena
ppapapp -> ppap
codegolflogedoc -> codegolf

As this is about depalindromizing, your code cannot be a palindrome.

Remember, this is code-golf, so the code with the fewest bytes wins.

Julia, 21 15 bytes
x->x[1:end/2+1]

Try it online! (extra code is for printing output)


Modified Boggle-able Code and Output: CnR Edition (Robbers) This is the Robbers' thread. Cops' thread is here.

Background

Boggle is a board game where the players have to find English words on a 4-by-4 board of random alphabets. Words can be constructed by selecting sequentially adjacent cells on the board. ("adjacent" means horizontally, vertically or diagonally adjacent.) Also, same cell can't be used more than once in a word.

The following is an example board:

I L A W
B N G E
I U A O
A S R L

On this board, BINGO, ORANGE and WEARS are valid words, but SURGE and RUSSIA are not:

SURGE : There's no adjacent pair on the board having RG.
RUSSIA : S cannot be used twice.

Modified Boggle is a modified version of Boggle, with the following rules:

The board size is m-by-n, where m and n can be any positive integer.
Each cell can contain any one byte between 0 and 255 inclusive.
A cell can be used more than once, but not twice in a row.

Using the example board above, in addition to BINGO, ORANGE and WEARS, LANGUAGE becomes a valid string (since G is used twice, but not twice in a row) but RUSSIA is still not (due to SS pair).

Here is another example using a code fragment. The string from itertools import*\n can be found on the following board, but not from itertoosl import* or from itertools import *:

f   i   ' ' s
r   t   m   l
e   o   o   p
\n  *   t   r

Note that you need two o's in order to match the oo sequence.

Robber's challenge

Pick a cop's submission which isn't yet cracked or marked safe. In the given language, find a full program that fits in the code board which outputs some string that fits in the output board. The program's length should be equal or less than given, and the output's should be equal or greater.

Scoring for robbers

Each successful crack counts as a score of 1. The user with the greatest score wins.

Robber example & formatting

# Japt, code 8 bytes, output 21 bytes, [Bubbler](link-to-cops-post)

    `líÏ`íÏl

    [Try it online!](link-to-tio)

    The output is `112624120720504040320`.

Modified Boggle verification script

All of the scripts below have an example input with it.

Script for character string(code/output) & boggle. This does not support multi-line string. The input format is

a single line of string (either code or output), followed by
the raw boggle board.

Script for character string with byte-value boggle. Use this if the target string is printable but has one or more newlines in it. The input format is

the number of lines for the string,
raw string (possibly multi-line), then
the boggle board as byte values.

Script for byte-value string & boggle. Use this if the target string contains one or more unprintable characters. The input format is

a single line of string (either code or output) as byte values, followed by
the boggle board as byte values.


Count trailing truths Inspired by, and in memory of, my dear friend and colleague,

Dan Baronet, 1956 – 2016. R.I.P.
He found the shortest possible APL solution to this task:
Task
Given a Boolean list, count the number of trailing truth values.
Example cases
{} → 0
{0} → 0
{1} → 1
{0, 1, 1, 0, 0} → 0
{1, 1, 1, 0, 1} → 1
{1, 1, 0, 1, 1} → 2
{0, 0, 1, 1, 1} → 3
{1, 1, 1, 1, 1, 1} → 6

Dyalog APL, 6 2 bytes

⊥⍨

Test it on TryAPL.

How it works

⊥ (uptack, dyadic: decode) performs base conversion. If the left operand is a vector, it performs mixed base conversion, which is perfect for this task.

For a base vector b = bn, ⋯, b0 and a digit vector a = an, ⋯, a0, b ⊥ a converts a to the mixed base b, i.e., it computes b0⋯bn-1an + ⋯ + b0b1a2 + b0a1 + a0.

Now, ⍨ (tilde dieresis, commute) modifies the operator to the left as follows. In a monadic context, it calls the operator with equal left and right arguments.

For example, ⊥⍨ a is defined as a ⊥ a, which computes a0⋯an + ⋯ + a0a1a2 + a0a1 + a0, the sum of all cumulative products from the right to the left.

For k trailing ones, the k rightmost products are 1 and all others are 0, so their sum is equal to k.


Minecraft castle fractal Inpsired by a youtube video from a fellow PPCG user...

You challenge is to use ASCII-art draw a Minecraft castle wall of Andesite and Diorite. The shape of the wall is the Cantor Set. For reference, the Cantor Set is made by repeating the following N times:

Triple the current step
Replace the middle one with blank space
Add a full line below it

This creates the following for the first four steps:

*

* *
***

* *   * *
***   ***
*********

* *   * *         * *   * *
***   ***         ***   ***
*********         *********
***************************

However, your challenge is not quite that simple. You see, after the cantor set gets really big, it becomes boring to look at the same character repeated over and over and over. So we're going to change that by overlaying an alternating series of asterisks * and pound signs #. You should alternate on every three characters horizontally, and on every row vertically. (Of course leaving the spaces the same) For example, the second example will become:

* *
###

and the third example will become:

* *   * *
###   ###
***###***

For completeness, here are examples four and five:

#4
* *   * *         * *   * *
###   ###         ###   ###
***###***         ***###***
###***###***###***###***###

#5
* *   * *         * *   * *                           * *   * *         * *   * *
###   ###         ###   ###                           ###   ###         ###   ###
***###***         ***###***                           ***###***         ***###***
###***###***###***###***###                           ###***###***###***###***###
***###***###***###***###***###***###***###***###***###***###***###***###***###***

And one mega example, the 6th iteration:

* *   * *         * *   * *                           * *   * *         * *   * *                                                                                * *   * *         * *   * *                           * *   * *         * *   * *
###   ###         ###   ###                           ###   ###         ###   ###                                                                                ###   ###         ###   ###                           ###   ###         ###   ###
***###***         ***###***                           ***###***         ***###***                                                                                ***###***         ***###***                           ***###***         ***###***
###***###***###***###***###                           ###***###***###***###***###                                                                                ###***###***###***###***###                           ###***###***###***###***###
***###***###***###***###***###***###***###***###***###***###***###***###***###***                                                                                ***###***###***###***###***###***###***###***###***###***###***###***###***###***
###***###***###***###***###***###***###***###***###***###***###***###***###***###***###***###***###***###***###***###***###***###***###***###***###***###***###***###***###***###***###***###***###***###***###***###***###***###***###***###***###

The challenge

You must write a full program or function that accepts a positive integer for input, and outputs the N'th generation of this minecraft castle fractal. You can take Input and output by any reasonable method, and you do not have to worry about invalid inputs (such as numbers less than 1, floating point numbers, non-numbers, etc.).

The shortest answer, measured in bytes wins!

Jelly, 43 36 35 bytes

ḶṚ3*µ5B¤xÐ€ṁ€Ṁ×\Ṛ©1,‘xS$¤ṁ×®ị“*# ”Y

Just a start, I'm sure this could be shorter.

Try it online!

*For n > 5, your browser might wrap the output but if you copy-paste it into a non-wrapping editor, you will see the proper output.

Explanation

ḶṚ3*µ5B¤xÐ€ṁ€Ṁ×\Ṛ©1,‘xS$¤ṁ×®ị“*# ”Y  Input: integer n
Ḷ                                    Create the range [0, n)
 Ṛ                                   Reverse it
  3*                                 Raise 3 to the power of each
    µ                                Begin a new monadic chain on the powers of 3
     5B¤                             Nilad. Get the binary digits of 5 = [1, 0, 1]
        xÐ€                          Duplicate each of [1, 0, 1] to a power of 3 times
             Ṁ                       Get the maximum of the powers of 3
           ṁ€                        Reshape each to a length of that value
              ×\                     Cumulative products
                Ṛ©                   Reverse and save the result
                  1,‘xS$¤            Niladic chain.
                  1                    Start with 1
                    ‘                  Increment it
                   ,                   Pair them to get [1, 2]
                       $               Operate on [1, 2]
                      S                  Sum it to get 3
                     x                   Repeat each 3 times to get [1, 1, 1, 2, 2, 2]
                         ṁ           Reshape that to the saved table
                          ×®         Multiply elementwise with the saved table
                            ị“*# ”   Use each to as an index to select from "*# "
                                  Y  Join using newlines
                                     Return and print implicitly


Fastest Longest Common Subsequence Finder Your task is to solve the Longest Common Subsequence problem for n strings of length 1000.
A valid solution to the LCS problem for two or more strings S1, … Sn is any string T of maximal length such that the characters of T appear in all Si, in the same order as in T.
Note that T does not have to be a substring of Si.
We've already solved this problem in the shortest amount of code. This time, size doesn't matter.
Example
The strings axbycz and  xaybzc have 8 common subsequences of length 3:
abc abz ayc ayz xbc xbz xyc xyz

Any of these would be a valid solution for the LCS problem.
Details
Write a full program that solves the LCS problem, as explained above, abiding the following rules:

The input will consist of two or more strings of length 1000, consisting of ASCII characters with code points between 0x30 and 0x3F.

You have to read the input from STDIN.
You have two choices for the input format:

Each string (including the last) is followed by a linefeed.

The strings are chained together with no separator and no trailing linefeed.

The number of strings will be passed as a command-line parameter to your program.

You have to write the output, i.e., any one of the valid solutions to the LCS, to STDOUT, followed by one linefeed.

Your language of choice has to have a free (as in beer) compiler/interpreter for my operating system (Fedora 21).

If you require any compiler flags or a  specific interpreter, please mention it in your post.

Scoring
I will run your code with 2, 3, etc. strings until it takes longer than 120 seconds to print a valid solution. This means that you have 120 seconds for each value of n.
The highest amount of strings for which your code finished in time is your score.
In the event of a tied score of n, the submission that solved the problem for n strings in the shortest time will be declared the winner.
All submissions will be timed on my machine (Intel Core i7-3770, 16 GiB RAM, no swap).
The n strings of the (n-1)th test will be generated by calling rand n (and stripping the linefeeds, if requested), where rand is defined as follows:
rand()
{
    head -c$[500*$1] /dev/zero |
    openssl enc -aes-128-ctr -K 0 -iv $1 |
    xxd -c500 -ps |
    tr 'a-f' ':-?'
}

The key is 0 in the above code, but I reserve the right to change it to an undisclosed value if I suspect anybody of (partially) hardcoding the output.

C, n = 3 in ~7 seconds

Algorithm

The algorithm is a direct generalization of the standard dynamic programming solution to n sequences. For 2 strings A and B, the standard recurrence looks like this:

L(p, q) = 1 + L(p - 1, q - 1)           if A[p] == B[q]
        = max(L(p - 1, q), L(p, q - 1)) otherwise

For 3 strings A, B, C I use:

L(p, q, r) = 1 + L(p - 1, q - 1, r - 1)                          if A[p] == B[q] == C[r]
           = max(L(p - 1, q, r), L(p, q - 1, r), L(p, q, r - 1)) otherwise

The code implements this logic for arbitrary values of n.

Efficiency

The complexity of my code is O(s ^ n), with s the length of the strings. Based on what I found, it looks like the problem is NP-complete. So while the posted algorithm is very inefficient for larger values of n, it might actually not be possible to do massively better. The only thing I saw are some approaches that improve efficiency for small alphabets. Since the alphabet is moderately small here (16), that could lead to an improvement. I still predict that nobody will find a legitimate solution that goes higher than n = 4 in 2 minutes, and n = 4 looks ambitious already.

I reduced the memory usage in the initial implementation, so that it could handle n = 4 given enough time. But it only produced the length of the sequence, not the sequence itself. Check the revision history of this post for seeing that code.

Code

Since loops over n-dimensional matrices require more logic than fixed loops, I'm using a fixed loop for the lowest dimension, and only use the generic looping logic for the remaining dimensions.

#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

#define N_MAX 4

int main(int argc, char* argv[]) {
    int nSeq = argc - 1;
    if (nSeq > N_MAX) {
        nSeq = N_MAX;
    }

    char** seqA = argv + 1;

    uint64_t totLen = 1;
    uint64_t lenA[N_MAX] = {0};
    uint64_t offsA[N_MAX] = {1};
    uint64_t offsSum = 0;
    uint64_t posA[N_MAX] = {0};

    for (int iSeq = 0; iSeq < nSeq; ++iSeq) {
        lenA[iSeq] = strlen(seqA[iSeq]);
        totLen *= lenA[iSeq] + 1;

        if (iSeq + 1 < nSeq) {
            offsA[iSeq + 1] = totLen;
        }

        offsSum += offsA[iSeq];
    }

    uint16_t* mat = calloc(totLen, 2);
    uint64_t idx = offsSum;

    for (;;) {
        for (uint64_t pos0 = 0; pos0 < lenA[0]; ++pos0) {
            char firstCh = seqA[0][pos0];
            int isSame = 1;
            uint16_t maxVal = mat[idx - 1];

            for (int iSeq = 1; iSeq < nSeq; ++iSeq) {
                char ch = seqA[iSeq][posA[iSeq]];
                isSame &= (ch == firstCh);

                uint16_t val = mat[idx - offsA[iSeq]];
                if (val > maxVal) {
                    maxVal = val;
                }
            }

            if (isSame) {
                mat[idx] = mat[idx - offsSum] + 1;
            } else {
                mat[idx] = maxVal;
            }

            ++idx;
        }

        idx -= lenA[0];

        int iSeq = 1;
        while (iSeq < nSeq && posA[iSeq] == lenA[iSeq] - 1) {
            posA[iSeq] = 0;
            idx -= (lenA[iSeq] - 1) * offsA[iSeq];
            ++iSeq;
        }
        if (iSeq == nSeq) {
            break;
        }

        ++posA[iSeq];
        idx += offsA[iSeq];
    }

    int score = mat[totLen - 1];

    char* resStr = malloc(score + 1);
    resStr[score] = '\0';

    for (int iSeq = 0; iSeq < nSeq; ++iSeq) {
        posA[iSeq] = lenA[iSeq] - 1;
    }

    idx = totLen - 1;
    int resIdx = score - 1;

    while (resIdx >= 0) {
        char firstCh = seqA[0][posA[0]];
        int isSame = 1;
        uint16_t maxVal = mat[idx - 1];
        int maxIdx = 0;

        for (int iSeq = 1; iSeq < nSeq; ++iSeq) {
            char ch = seqA[iSeq][posA[iSeq]];
            isSame &= (ch == firstCh);

            uint16_t val = mat[idx - offsA[iSeq]];
            if (val > maxVal) {
                maxVal = val;
                maxIdx = iSeq;
            }
        }

        if (isSame) {
            resStr[resIdx--] = firstCh;
            for (int iSeq = 0; iSeq < nSeq; ++iSeq) {
                --posA[iSeq];
            }
            idx -= offsSum;
        } else {
            --posA[maxIdx];
            idx -= offsA[maxIdx];
        }
    }

    free(mat);

    printf("score: %d\n", score);
    printf("%s\n", resStr);

    return 0;
}

Instructions for Running

To run:

Save the code in a file, e.g. lcs.c.
Compile with high optimization options. I used:

clang -O3 lcs.c

On Linux, I would try:

gcc -Ofast lcs.c

Run with 2 to 4 sequences given as command line arguments:

./a.out axbycz xaybzc

Single quote the command line arguments if necessary, since the alphabet used for the examples contains shell special characters.

Results

test2.sh and test3.sh are the test sequences from Dennis. I don't know the correct results, but the output looks at least plausible.

$ ./a.out axbycz xaybzc
score: 3
abc

$ time ./test2.sh
score: 391
16638018802020>3??3232270178;47240;24331395?<=;99=?;178675;866002==23?87?>978891>=9<6<9381992>>7030829?255>6804:=3>:;60<9384=081;0:?66=51?0;5090724<85?>>:2>7>3175?::<9199;5=0:494<5<:7100?=95<91>1887>33>67710==;48<<327::>?78>77<6:2:02:<7=5?:;>97<993;57=<<=:2=9:8=118563808=962473<::8<816<464<1==925<:5:22?>3;65=>=;27?7:5>==3=4>>5>:107:20575347>=48;<7971<<245<??219=3991=<96<??735698;62?<98928

real  0m0.012s
user  0m0.008s
sys   0m0.003s

$ time ./test3.sh
score: 269
662:2=2::=6;738395=7:=179=96662649<<;?82?=668;2?603<74:6;2=04=>6;=6>=121>1>;3=22=3=3;=3344>0;5=7>>7:75238;559133;;392<69=<778>3?593?=>9799<1>79827??6145?7<>?389?8<;;133=505>2703>02?323>;693995:=0;;;064>62<0=<97536342603>;?92034<?7:=;2?054310176?=98;5437=;13898748==<<?4

real  0m7.218s
user  0m6.701s
sys   0m0.513s


UTF-8 Reduce Ascii art This challenge is a cut'n paste from Enlarge ASCII art, but reversed, using PetSCII based half-block chars:
string=" ▝▘▀▗▐▚▜▖▞▌▛▄▟▙█"

There, PetSCII is emulated by using UTF-8 characters, you may found between U+2580 UPPER HALF BLOCK and U+259F QUADRANT UPPER RIGHT AND LOWER LEFT AND LOWER RIGHT.
So the goal is to reduce by 1/2 submited ascii-art.
You have to group 2 char from 2 lines to obtain one 2x2 pattern for one character:
|XX|         |X |         |X |         |  |
|XX| -> '█'  |XX| -> '▙'  | X| -> '▚'  | X| -> '▗'  and so on...

Some samples: From
 OOOOOO  OOOOOO  OOOOOO  OOOOOOO      OOOOOO   OOOOOO  OO      OOOOOOO
OO      OO    OO OO   OO OO          OO       OO    OO OO      OO
OO      OO    OO OO   OO OOOOO       OO   OOO OO    OO OO      OOOOO
OO      OO    OO OO   OO OO          OO    OO OO    OO OO      OO
 OOOOOO  OOOOOO  OOOOOO  OOOOOOO      OOOOOO   OOOOOO  OOOOOOO OO

you have to render:
▟▀▀▘▟▀▀▙▐▛▀▙▐▛▀▀  ▗▛▀▀ ▟▀▀▙▐▌  ▐▛▀▀
█   █  █▐▌ █▐▛▀   ▐▌ ▜▌█  █▐▌  ▐▛▀
▝▀▀▘▝▀▀▘▝▀▀▘▝▀▀▀   ▀▀▀ ▝▀▀▘▝▀▀▀▝▘

And from:
  OOOOOO  OOOOOO  OOOOOO  OOOOOOO      OOOOOO   OOOOOO  OO      OOOOOOO
 OO      OO    OO OO   OO OO          OO       OO    OO OO      OO
 OO      OO    OO OO   OO OOOOO       OO   OOO OO    OO OO      OOOOO
 OO      OO    OO OO   OO OO          OO    OO OO    OO OO      OO
  OOOOOO  OOOOOO  OOOOOO  OOOOOOO      OOOOOO   OOOOOO  OOOOOOO OO

Where 1st column hold spaces you may render:
▗▛▀▀▗▛▀▜▖█▀▜▖█▀▀▘  ▟▀▀▘▗▛▀▜▖█   █▀▀▘
▐▌  ▐▌ ▐▌█ ▐▌█▀▘   █ ▝█▐▌ ▐▌█   █▀▘
 ▀▀▀ ▀▀▀ ▀▀▀ ▀▀▀▘  ▝▀▀▘ ▀▀▀ ▀▀▀▘▀

Piping:
wget -O - https://codegolf.stackexchange.com/q/19123/9424 |
    sed -ne '/
/,/<\/code><\/pre>/{//{/\//q};s/
//;p}'
   ('l2v2l6v2'+  'e1l1v3l2'+
 'v3e1v7e1v7e1v7e1l2v6e1l4v5'+
'e1l6v4e1l8v3e1l7l3v2e1l9l3v1')
 .replace(/[lve]\d/g,function
   (c){return Array(-~c[1]).
      join({l:' ',v:'Love'
         ,e:'\n'}[c[0
             ]])})

must give:
▗▟█████▙▟█████▄
▜█████████████▛▘
 ▝▀███▙▛█████▀
    ▝▀▜██▀▘

Other samples on my terminal:

With standard rules:

Input ASCII from STDIN or file, without special chars, tabulations or UTF-8.
Each submited chars have to be represented, only whitespaces have to stay empty.
This is code-golf too, so the lowest score win. Score is computed as:

+1 by chars, to be counted in chars, not in bytes!! Ie: s=' ▝▘▀▗▐▚▜▖▞▌▛▄▟▙█' count for 20 chars, not 52 !!
-10 for explanation;
+20 for use of external font tool or library.

GolfScript (90 chars)

n/.,1&[""]*+.{,}%$-1=.1&+{1$,-´' '*+}+%2/{zip 2/{~+0\{32=!1$++}/" ▗▝▐▖▄▞▟▘▚▀▜▌▙▛█"3/=}%n}%

A lot of this goes to handling ragged arrays. Nasty test case:

xx
xxx
xxx
xx
x

contains a 3 different 2x2 grids with only one of the 4 cells containing any character at all.

To make things worse, the zip transposition to chop the columns into pairs gives the same output for ["xx" "xxx"]zip and ["xxx" "xx"]zip. I therefore begin by padding out to ensure that all lines are the same even length, and that there are an even number of lines.

Note that this program assumes that the interpreter will treat " ▗▖▄▝▐▞▟▘▚▌▙▀▜▛█" as a string of length 48, even though as per instructions in the question I'm counting it as 16 chars plus delimiters.

I've tested this to the best of my ability, but I can't find a monospace font which actually renders those characters correctly.


Print the n-th digit of pi Task

Given an input n, calculate the n-th decimal digit of pi

Rules

Answer can be a full program or a function.
Input must be taken from stdin or from function arguments.
Output must be either sent to stdout, the return value of a function, or written to a file.
all n values between 0 and 20000 must be supported (can be between 1 and 20001 for 1-indexed languages).
Built-ins to calculate pi cannot be used. This includes pi constants (e.g. math.pi in Python) and built-in functions that return either the value of pi, or the n-th digit of pi. This means that an algorithm which calculates pi, or the n-th digit of pi must be implemented in your answer.
Digits must be calculated at runtime.

First digit (0-th or 1-th, depending on the language) is 3.

This is code-golf, so shortest code in bytes wins.

EDIT:

This is not a duplicate of 'Find the n-th decimal of pi', since that challenge allowed built-ins. This one is focused around actually implementing an algorithm to find the digits, rather than relying on built-ins.

Python 2, 182 65 bytes

a=p=2*10**20004
i=3
while a:a=i/2*a/i;p+=a;i+=2
print`p`[input()]

repl.it

Uses the Leibniz formula to calculate 20000 correct digits (plus a handful to allow the algorithm to maintain accuracy) then prints the requested digit.

Previous (182):
"The Spigot Algorithm For Pi" of Stanley Rabinowitz and Stan Wagon has the added bonus that it will work for any n when implemented as a generator

p=lambda n,r=3,a=0,b=1,c=1,d=1,e=3,f=3,i=0:i>n and r or p(n,e,*[((2*b+a)*f,b*d,c*f,d+1,(b*(7*d)+2+(a*f))/(c*f),f+2,i),(10*(a-e*c),10*b,c,d,((10*(3*b+a))/c)-10*e,f,i+1)][4*b+a-c<e*c])

repl.it Reaches Python's default recursion limit for the 117th digit.

Here is a non-recursive version for 198 bytes:

def p(n):
 a=i=0;b=c=d=1;e=f=3
 while i<=n:
     r=e
     if 4*b+a-c<e*c:g=10*(a-e*c);e=((10*(3*b+a))/c)-10*e;b*=10;i+=1
     else:g=(2*b+a)*f;h=(b*(7*d)+2+(a*f))/(c*f);b*=d;c*=f;f+=2;d+=1;e=h
     a=g
 print r

repl.it

(first indent space, second indent tab), the digits could, of course, be generated by yielding e at the start of the if clause instead of tracking the last digit with r.


Draw the flag of Tennessee The flag of Tennessee is specified by chapter 498 of the Public Acts of 1905.

An oblong flag or banner in length one and two thirds times its width, the large or principal field of same to be of color red, but said flag or banner ending at its free or outer end in a perpendicular bar of blue, of uniform width, running from side to side; that is to say, from top to bottom of said flag or banner, and separated from the red field by a narrow margin or stripe of white of uniform width; the width of the white stripe to be one-fifth that of the blue bar; and the total width of the bar and stripe together to be equal to one-eighth of the width of the flag.
In the center of the red field shall be a smaller circular field of blue, separated from the surrounding red field by a circular margin or stripe of white of uniform width and of the same width as the straight margin or stripe first mentioned. The breadth or diameter of the circular blue field, exclusive of the white margin, shall be equal to one-half of the width of the flag. Inside the circular blue field shall be three five-pointed stars of white distributed at equal intervals around a point in the center of the blue field and shall be of such size and arrangement that one point of each star shall approach as closely as practicable without actually touching one point of each of the other two around the center point of the field; and the two outer points of each star shall approach as nearly as practicable without actually touching the periphery of the blue field. The arrangement of the three stars shall be such that the centers of no two stars shall be in a line parallel to either the side or end of the flag, but intermediate between same; and the highest star shall be the one nearest the upper confined corner of the flag.

Here is the flag, with annotations for its ratios:

Your task is to draw this flag in a way that complies with the statute. However, because the statute is ambiguous, you have some wiggle room with what you output. Specifically:

You may use any colors reasonably recognizable as "red", "white", and "blue". (The sample image uses #cc0000, #002d65, and #ffffff.)
The "stars" may have any exterior or interior angles. But all the interior angles must be equal, all the exterior angles must be equal, all edges must be the same length, it must have ten edges and ten vertices, and it must be reasonably recognizable as a five-pointed star.
The stars must be as large as "practicable" so that their points do not touch each other in the center or the white band around the edge of the circle. Between the two points of each star closest to the edge and the edge, and between the points approaching the center of any two stars, there must be at least 1 pixel of space but not more than 1/48 of the length of the flag.
The centers of the three stars may form any equilateral triangle, so long as no side of the triangle is parallel to an edge of the flag, and the vertex closest to the top of the flag is closer to the top left corner than the top right corner.

Shortest code wins.

PostScript, 346 315 bytes

Code (compressed version):

5 5 scale<</C {setrgbcolor}/R{1 0 0 C}/B{0 0 1 C}/W{1 setgray}/o{closepath fill}/c{0 360 arc o}/f{rectfill}/t{translate}/p{currentpoint}/s{gsave p t 4{0 -11 lineto p t -144 rotate}repeat o grestore}>>begin R 0 0 74 48 f B 75 0 5 48 f W 37 24 13 c B 37 24 12 c W 37 24 t 3{-.1 -.5 moveto s 120 rotate}repeat showpage

Code (uncompressed version):

5 5 scale                 % over-all scale

% define some short-named procedures for later use
<<
  /C {setrgbcolor}
  /R {1 0 0 C}            % set red color
  /B {0 0 1 C}            % set blue color
  /W {1 setgray}          % set white color
  /o {closepath fill}
  /c {0 360 arc o}        % draw circle
  /f {rectfill}
  /t {translate}
  /p {currentpoint}
  /s {                    % draw 5-pointed star
    gsave
    p t
    4 {
      0 -11 lineto          % one line of star
      p t
      -144 rotate           % rotate by 144°
    } repeat
    o                       % fill the star
    grestore
  }
>> begin

R 0 0 74 48 f             % draw big red rectangle
B 75 0 5 48 f             % draw blue rectangle
W 37 24 13 c              % draw white circle
B 37 24 12 c              % draw blue circle
W
37 24 t                   % translate to center of circle
3 {
  -.1 -.5 moveto          % move a little off the center
  s                       % draw white star
  120 rotate              % rotate by 120°
} repeat
showpage

Result:


Make a transparent 448*448 image This is a simple challenge.

The task is to write code that outputs a 448*448 square image with 100% transparency.  The output should follow the standard image rules.

Imagemagick in some shell, 35

convert -size 448x448 xc:none a.png

Is this allowed?


Count number of hefty decimals between 2 numbers Let's say we have a non-negative integer that is "hefty" (that is, "heavy") if its average digit value is greater than 7.

The number 6959 is "hefty" because:

(6 + 9 + 5 + 9) / 4 = 7.5

The number 1234 is not, because:

(1 + 2 + 3 + 4) / 4 = 2.5

Write a function, in any language,

HeftyDecimalCount(a, b)

which, when provided two positive integers a and b returns an integer indicating how many "hefty" integers are within the interval [a..b], inclusive.

For example, given a=9480 and b=9489:

9480   (9+4+8+0)/4 21/4 = 5.25
9481   (9+4+8+1)/4 22/4 = 5.5
9482   (9+4+8+2)/4 23/4 = 5.75
9483   (9+4+8+3)/4 24/4 = 6
9484   (9+4+8+4)/4 25/4 = 6.25
9485   (9+4+8+5)/4 26/4 = 6.5
9486   (9+4+8+6)/4 27/4 = 6.75
9487   (9+4+8+7)/4 28/4 = 7
9488   (9+4+8+8)/4 29/4 = 7.25   hefty
9489   (9+4+8+9)/4 30/4 = 7.5    hefty

Two of the numbers in this range are "hefty" and so the function should return 2.

Some guidelines:

assume that neither a or b exceeds 200,000,000.
an n-squared solution will work, but will be slow -- what's the fastest we can solve this?

The problem can be solved in O(polylog(b)).

We define f(d, n) to be the number of integers of up to d decimal digits with digit sum less than or equal to n.  It can be seen that this function is given by the formula

  Let's derive this function, starting with something simpler.

  The function h counts the number of ways to choose d - 1 elements from a multi-set containing n + 1 different elements.  It's also the number of ways to partition n into d bins, which can be easily seen by building d - 1 fences around n ones and summing up each separated section .  Example for n = 2, d = 3':

3-choose-2     fences        number
-----------------------------------
11             ||11          002
12             |1|1          011
13             |11|          020
22             1||1          101
23             1|1|          110
33             11||          200

  So, h counts all numbers having a digit-sum of n and d digits.  Except it only works for n less than 10, since digits are limited to 0 - 9 .  In order to fix this for values 10 - 19, we need to subtract the number of partitions having one bin with a number greater than 9, which I'll call  overflown bins from now on.

  This term can be computed by reusing h in the following way.  We count the number of ways to partition n - 10, and then choose one of the bins to put the 10 into, which results in the number of partitions having one overflown bin.  The result is the following preliminary function.

  We continue this way for n less or equal 29, by counting all the ways of partitioning n - 20, then choosing 2 bins where we put the 10's into, thereby counting the number of partitions containing 2 overflown bins.

  But at this point we have to be careful, because we already counted the partitions having 2 overflown bins in the previous term. Not only that, but actually we counted them twice.  Let's use an example and look at the partition (10,0,11) with sum 21.  In the previous term, we subtracted 10, computed all partitions of the remaining 11 and put the 10 into one of the 3 bins.  But this particular partition can be reached in one of two ways:

(10, 0, 1) => (10, 0, 11)
(0, 0, 11) => (10, 0, 11)

  Since we also counted these partitions once in the first term, the total count of partitions with 2 overflown bins amounts to 1 - 2 = -1, so we need to count them once more by adding the next term.

  Thinking about this a bit more, we soon discover that the number of times a partition with a specific number of overflown bins is counted in a specific term can be expressed by the following table (column i represents term i, row j partitions with j overflown bins).

1 0 0 0 0 0 . .
1 1 0 0 0 0 . .
1 2 1 0 0 0 . .
1 4 6 4 1 0 . .
. . . . . .
. . . . . .

  Yes, it's Pascals triangle.  The only count we are interested in is the one in the first row/column, i.e. the number of partitions with zero overflown bins. And since the alternating sum of every row but the first equals 0 (e.g. 1 - 4 + 6 - 4 + 1 = 0), that's how we get rid of them and arrive at the penultimate formula.

  This function counts all numbers with d digits having a digit-sum of n.

  Now, what about the numbers with digit-sum less than n ?  We can use a standard recurrence for binomials plus an inductive argument, to show that

  counts the number of partitions with digit-sum at most n.  And from this f can be derived using the same arguments as for g.

Using this formula, we can for example find the number of heavy numbers in the interval from 8000 to 8999 as 1000 - f(3, 20), beacuse there are thousand numbers in this interval, and we have to subtract the number of numbers with digit sum less than or equal to 28 while taking in to acount that the first digit already contributes 8 to the digit sum.

As a more complex example let's look at the number of heavy numbers in the interval 1234..5678.  We can first go from 1234 to 1240 in steps of 1.  Then we go from 1240 to 1300 in steps of 10.  The above formula gives us the number of heavy numbers in each such interval:

1240..1249:  10 - f(1, 28 - (1+2+4))
1250..1259:  10 - f(1, 28 - (1+2+5))
1260..1269:  10 - f(1, 28 - (1+2+6))
1270..1279:  10 - f(1, 28 - (1+2+7))
1280..1289:  10 - f(1, 28 - (1+2+8))
1290..1299:  10 - f(1, 28 - (1+2+9))

Now we go from 1300 to 2000 in steps of 100:

1300..1399:  100 - f(2, 28 - (1+3))
1400..1499:  100 - f(2, 28 - (1+4))
1500..1599:  100 - f(2, 28 - (1+5))
1600..1699:  100 - f(2, 28 - (1+6))
1700..1799:  100 - f(2, 28 - (1+7))
1800..1899:  100 - f(2, 28 - (1+8))
1900..1999:  100 - f(2, 28 - (1+9))

From 2000 to 5000 in steps of 1000:

2000..2999:  1000 - f(3, 28 - 2)
3000..3999:  1000 - f(3, 28 - 3)
4000..4999:  1000 - f(3, 28 - 4)

Now we have to reduce the step size again, going from 5000 to 5600 in steps of 100, from 5600 to 5670 in steps of 10 and finally from 5670 to 5678 in steps of 1.

An example Python implementation (which received slight optimisations and testing meanwhile):

def binomial(n, k):
    if k < 0 or k > n:
        return 0
    result = 1
    for i in range(k):
        result *= n - i
        result //= i + 1
    return result

binomial_lut = [
    [1],
    [1, -1],
    [1, -2, 1],
    [1, -3, 3, -1],
    [1, -4, 6, -4, 1],
    [1, -5, 10, -10, 5, -1],
    [1, -6, 15, -20, 15, -6, 1],
    [1, -7, 21, -35, 35, -21, 7, -1],
    [1, -8, 28, -56, 70, -56, 28, -8, 1],
    [1, -9, 36, -84, 126, -126, 84, -36, 9, -1]]

def f(d, n):
    return sum(binomial_lut[d][i] * binomial(n + d - 10*i, d)
               for i in range(d + 1))

def digits(i):
    d = map(int, str(i))
    d.reverse()
    return d

def heavy(a, b):
    b += 1
    a_digits = digits(a)
    b_digits = digits(b)
    a_digits = a_digits + [0] * (len(b_digits) - len(a_digits))
    max_digits = next(i for i in range(len(a_digits) - 1, -1, -1)
                      if a_digits[i] != b_digits[i])
    a_digits = digits(a)
    count = 0
    digit = 0
    while digit < max_digits:
        while a_digits[digit] == 0:
            digit += 1
        inc = 10 ** digit
        for i in range(10 - a_digits[digit]):
            if a + inc > b:
                break
            count += inc - f(digit, 7 * len(a_digits) - sum(a_digits))
            a += inc
            a_digits = digits(a)
    while a < b:
        while digit and a_digits[digit] == b_digits[digit]:
            digit -= 1
        inc = 10 ** digit
        for i in range(b_digits[digit] - a_digits[digit]):
            count += inc - f(digit, 7 * len(a_digits) - sum(a_digits))
            a += inc
            a_digits = digits(a)
    return count

Edit: Replaced the code by an optimised version (that looks even uglier than the original code).  Also fixed a few corner cases while I was at it.  heavy(1234, 100000000) takes about a millisecond on my machine.


Convert an Excel date code to a "date" Given a non-negative integer Excel-style date code, return the corresponding "date" in any reasonable form that clearly shows year, month, and "day".

Trivial, you may think. Did you notice the "scare quotes"? I used those because Excel has some quirks. Excel counts days with number 1 for January 1st, 1900, but as if 1900 had a January 0th and a February 29th, so be very careful to try all test cases:

 Input → Output (example format)
     0 → 1900-01-00    Note: NOT 1899-12-31
     1 → 1900-01-01
     2 → 1900-01-02
    59 → 1900-02-28
    60 → 1900-02-29    Note: NOT 1900-03-01
    61 → 1900-03-01
   100 → 1900-04-09
  1000 → 1902-09-26
 10000 → 1927-05-18
100000 → 2173-10-14

Excel, 3(+7?)

=A1

with format

yyy/m/d

Pure port


Algebra, graph theory, Möbius inversion, research, and Java

The symmetry group of the hexagon is the dihedral group of order 12, and is generated by a 60 degree rotation and a mirror flip across a diameter. It has 16 subgroups, but some of them are in non-trivial conjugacy groups (the ones which only have reflections have 3 choices of axis), so there are 10 fundamentally different symmetries which a tiling of the hexagon can have:

The number of diamond tilings of a subset of a triangular lattice can be calculated as a determinant, so my initial approach was to set up one determinant for each of the symmetries of the hexagon, to calculate the number of tilings which have at least those symmetries; and then use Möbius inversion in the incidence algebra of their poset (basically a generalisation of the inclusion-exclusion principle) to work out the number of tilings whose symmetry group is exactly each of the 10 cases. However, some of the symmetries have nasty edge conditions, so I was forced to sum over exponentially many determinants. Fortunately, the values obtained for n < 10 gave me enough data to be able to identify relevant sequences in OEIS and piece together a closed form (for some value of "closed" which allows finite products). There's a bit of discussion of the sequences, and references to proofs, in the formal writeup which I prepared to justify the OEIS sequence updates.

Once the double-counting is taken care of, it turns out that four of the ten values cancel out neatly, so we only have to calculate the remaining six and then do a weighted sum.

This code takes under 30 seconds for N=1000 on my machine.

import java.math.BigInteger;

public class OptimisedCounter {
    private static int[] minp = new int[2];

    public static void main(String[] args) {
        if (args.length > 0) {
            for (String arg : args) System.out.println(count(Integer.parseInt(arg)));
        }
        else {
            for (int n = 0; n < 16; n++) {
                System.out.format("%d\t%s\n", n, count(n));
            }
        }
    }

    private static BigInteger count(int n) {
        if (n == 0) return BigInteger.ONE;

        if (minp.length < 3*n) {
            int[] wider = new int[3*n];
            System.arraycopy(minp, 0, wider, 0, minp.length);
            for (int x = minp.length; x < wider.length; x++) {
                // Find the smallest prime which divides x
                for (wider[x] = 2; x % wider[x] != 0; wider[x]++) { /* Do nothing */ }
            }
            minp = wider;
        }

        BigInteger E = countE(n), R2 = countR2(n), F = countF(n), R3 = countR3(n), R = countR(n), FR = countFR(n);
        BigInteger sum = E.add(R3);
        sum = sum.add(R2.add(R).multiply(BigInteger.valueOf(2)));
        sum = sum.add(F.add(FR).multiply(BigInteger.valueOf(3)));
        return sum.divide(BigInteger.valueOf(12));
    }

    private static BigInteger countE(int n) {
        int[] w = new int[3*n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= i + n; j++) w[j]--;
            for (int j = i + n + 1; j <= i + 2*n; j++) w[j]++;
        }
        return powerProd(w);
    }

    private static BigInteger countR2(int n) {
        int[] w = new int[3*n];
        for (int i = 0; i < n; i++) {
            w[3*i+2]++;
            for (int j = 3*i + 1; j <= 2*i + n + 1; j++) w[j]--;
            for (int j = 2*i + n + 1; j <= i + n + n; j++) w[j]++;
        }
        return powerProd(w);
    }

    private static BigInteger countF(int n) {
        int[] w = new int[3*n];
        for (int i = 0; i < n; i++) {
            for (int j = 2*i + 1; j <= 2*i + n; j++) w[j]--;
            for (int j = i + n + 1; j <= i + 2*n; j++) w[j]++;
        }
        return powerProd(w);
    }

    private static BigInteger countR3(int n) {
        if ((n & 1) == 1) return BigInteger.ZERO;
        return countE(n / 2).pow(2);
    }

    private static BigInteger countR(int n) {
        if ((n & 1) == 1) return BigInteger.ZERO;
        int m = n / 2;
        int[] w = new int[3*m-1];
        for (int i = 0; i < m; i++) {
            for (int j = 1; j <= 3*i+1; j++) w[j] += 2;
            for (int j = 1; j <= i + m; j++) w[j] -= 2;
        }
        return powerProd(w);
    }

    private static BigInteger countFR(int n) {
        if ((n & 1) == 1) return BigInteger.ZERO;
        int m = n / 2;
        int[] w = new int[3*n-2];
        for (int j = 1; j <= m; j++) w[j]--;
        for (int j = 2*m; j <= 3*m-1; j++) w[j]++;
        for (int i = 0; i <= 2*m-3; i++) {
            for (int j = i + 2*m + 1; j <= i + 4*m; j++) w[j]++;
            for (int j = 2*i + 3; j <= 2*i + 2*m + 2; j++) w[j]--;
        }
        return powerProd(w);
    }

    private static BigInteger powerProd(int[] w) {
        BigInteger result = BigInteger.ONE;
        for (int x = w.length - 1; x > 1; x--) {
            if (w[x] == 0) continue;

            int p = minp[x];
            if (p == x) result = result.multiply(BigInteger.valueOf(p).pow(w[p]));
            else {
                // Redistribute it. This should ensure we avoid negatives.
                w[p] += w[x];
                w[x / p] += w[x];
            }
        }

        return result;
    }
}


Egg, sausage, bacon and spam (lovely spam!) You are given four integers: \$e,s,b\in\{0,1\}\$ and \$S\in \{0,1,2,4\}\$, where \$e,s,b,S\$ stand for egg, sausage, bacon and spam respectively.

Your task is to figure out whether the corresponding ingredients match a valid entry in the following menu:

 [e]gg | [s]ausage | [b]acon | [S]pam
-------+-----------+---------+--------
   1   |     0     |    1    |   0
   1   |     1     |    1    |   0
   1   |     0     |    0    |   1
   1   |     0     |    1    |   1
   1   |     1     |    1    |   1
   0   |     1     |    1    |   2
   1   |     0     |    1    |   4
   1   |     0     |    0    |   4
   1   |     1     |    0    |   2

This is a subset of the menu described in the famous Monty Python's sketch, where dishes based on other ingredients are omitted.

Rules

You can take \$(e,s,b,S)\$ in any order and any convenient format as long as they are clearly separated into 4 distinct values as described above (e.g. claiming that your code takes a single bitmask with all values packed in there is not allowed).

Examples: [1,0,1,4], "1014", or 4 distinct arguments
Each value is guaranteed to be valid (i.e. you don't have to support \$e=2\$ or \$S=3\$).
You may return (or print) either:

a truthy value for matching and a falsy value for not-matching
a falsy value for matching and a truthy value for not-matching
2 distinct, consistent values of your choice (please specify them in your answer)

This is code-golf

Test cases (all of them)

Format: [e, s, b, S] --> matching

[ 0, 0, 0, 0 ] --> false
[ 0, 0, 0, 1 ] --> false
[ 0, 0, 0, 2 ] --> false
[ 0, 0, 0, 4 ] --> false
[ 0, 0, 1, 0 ] --> false
[ 0, 0, 1, 1 ] --> false
[ 0, 0, 1, 2 ] --> false
[ 0, 0, 1, 4 ] --> false
[ 0, 1, 0, 0 ] --> false
[ 0, 1, 0, 1 ] --> false
[ 0, 1, 0, 2 ] --> false
[ 0, 1, 0, 4 ] --> false
[ 0, 1, 1, 0 ] --> false
[ 0, 1, 1, 1 ] --> false
[ 0, 1, 1, 2 ] --> true
[ 0, 1, 1, 4 ] --> false
[ 1, 0, 0, 0 ] --> false
[ 1, 0, 0, 1 ] --> true
[ 1, 0, 0, 2 ] --> false
[ 1, 0, 0, 4 ] --> true
[ 1, 0, 1, 0 ] --> true
[ 1, 0, 1, 1 ] --> true
[ 1, 0, 1, 2 ] --> false
[ 1, 0, 1, 4 ] --> true
[ 1, 1, 0, 0 ] --> false
[ 1, 1, 0, 1 ] --> false
[ 1, 1, 0, 2 ] --> true
[ 1, 1, 0, 4 ] --> false
[ 1, 1, 1, 0 ] --> true
[ 1, 1, 1, 1 ] --> true
[ 1, 1, 1, 2 ] --> false
[ 1, 1, 1, 4 ] --> false

Spam spam spam spam. Lovely spam! Wonderful spam!

Python, 32 bytes

"001111020114001410120110".count

Try it online!

Takes input in 'sbeS' order as a single string, like '1102'. Simply checks whether the string appears as a substring of the hardcoded string, using the object method to avoid needing to write out a costly lambda to define a function.

The desired strings are squished together as much as possible via overlapping. For example, the part "001111020114 checks for 0011, 0111, 1111, 1110, and 1102. The fact that 2 and 4 can only appear as the counts of spam, which is listed last, lets us append strings directly to their right without false positives. I played with the order of the inputs to try to overlap more, but there might be a better outcome.

I suspect this approach can be beaten with a modulo chain or similar using number inputs.


March Madness - When Will Two Seeds Meet? Each March in the United States, the NCAA holds a 68-team tournament for both men's and women's college basketball. Here's what the bracket looks like:

There are four regions, each with 16 teams seeded from 1-16.

Each region is seeded the same way, and across the four regions, the same matchups occur between seeds. For example, in the first round, #1 plays #16 and #8 plays #9, then the winners of those games play in the second round. So, possible options for the second round matchup are #1 vs #8, #1 vs #9, #16 vs #8, and #16 vs #9.

Teams with the same seed can only meet in two ways: the first is in the semifinals (round 5), where the champion of each of the four regions plays another regional champion.

The second has to do with a wrinkle in the tournament. There are also 4 "play-in" games, where two teams with the same seed play each other to enter the "true" game in the round of 64 teams. As you can see in the bracket, this only happens for seeds 11 and 16, so those seeds can play another team in the same seed in the play-in games (round 0).

The Challenge

Given two seeds from 1 to 16, inclusive, in any standard format, output the number of the earliest round a matchup between two teams with those integers as seeds could occur in the NCAA basketball tournament.

Test Cases

Input  Output
1,16   1
1,8    2
1,9    2
9,16   2
3,11   2
3,14   1
1,2    4
5,5    5
11,11  0
16,16  0
15,16  4
3,4    4
6,7    3
6,10   3
6,11   1
10,11  3
1,6    4
1,11   4
4,5    2
4,6    4
4,7    4
4,8    3
4,9    3
5,8    3
5,9    3
2,7    2

This is code-golf, so the submission with the fewest bytes wins.

Mathematica, 79 bytes

o={r=1,1}
Which[#==11o||#==16o,0,Tr@#==(c=32/2^r+1),r,0<r++,#0[Min[#,c-#]&/@#]]&

The second line defines a pure function taking a pair of numbers as input and returning the appropriate nonnegative integer. Inside the Which (which is an "if-then-else" construct): #==11o||#==16o,0, deals with the play-in special cases; Tr@#==(c=32/2^r+1),r, checks whether the sum of the two team seeds is equal to the magic number that means they could be matched up in round r; and 0<r++,#0[Min[#,c-#]&/@#] is the "else" clause (since 0<r++ will always be true here) which recursively calls the function on Min[#,c-#]&/@#, which replaces any lower seed with the seed of the higher-ranked team it would have beaten to get to the next round.


Snow Blow My Driveway! There has recently been a big snow, and my driveway needs snow-blowing. If the snow-blower goes over some area that it has already snow-blowed, then that area will have snow blown onto it and need to be blown again. And of course, the snow-blower cannot start in the middle of the driveway, it needs to start from my garage, where it is stored.

More formally:

Your program takes a standard form of input as a string or multidimensional array that looks like the following:

XXXXOOOOXXXX
X          X
X          X
XXXXXXXXXXXX

X represents an area that cannot be snow-blowed, O represents an area where the snow-blower can be deployed, and empty spaces represent areas where there is snow. You can chose different values if you wish.

Your program must output something like the following:

XXXX*%OOXXXX
Xv<<<^<<<<<X
X>>>>>>>>>^X
XXXXXXXXXXXX

The snow-blower starts at the *. The * always points to the nearest non-garage space. The <,>,v, and ^ all represent pointers of where the next direction is. They point the snow-blower where to go. Once a pointer points to the %, the blower has re-arrived into the garage, and the whole driveway should be clear.

The snow blower must go over the whole driveway. The snowblower's path can never overlap itself. Impossible input must not be given.

Because I don't want to be outside any longer than I need to be, and not need to spend a lot of time typing, the program should be as short as possible. Shortest code wins!

Test Cases:

These test cases may have multiple correct answers. I have provided possible solutions below each test case.

Test case 1:
The one given in the example.

Test case 2:

XOOOOOX
X     X
X     X
X     XXXXXXXX
X            X
X            X
XXXXXXXXXXXXXX

X*OOO%X
Xv>>>^X
Xv^<<<X
Xv>>>^XXXXXXXX
Xv^<<<<<<<<<<X
X>>>>>>>>>>>^X
XXXXXXXXXXXXXX

Test case 3:

XOOOOX
X    X
X    X
X  XXX
X    X
X    X
XXXXXX

XOO%*X
X>>^vX
X^v<<X
X^vXXX
X^>>vX
X^<<<X
XXXXXX

Test case 4:

XXXXXXXXXXXXX
O           X
O    X      X
O    X      X
O           X
XXXXXXXXXXXXX

XXXXXXXXXXXXX
*>>>>>>>>>>vX
Ov<v<Xv<<<<<X
Ov^v^X>>>>>vX
%<^<^<<<<<<<X
XXXXXXXXXXXXX

JavaScript (ES6), 346 310 299 298 297 296 283 bytes

f=(a,y=0,x=0)=>(a[y][x]?a[y][x]=='O'&&(a[y][x]='*',(g=w=>(w=a[y])&&w[x]&&(w[x]<'!'?g(w[x]='v',y++)||g(w[x++]='>',y--)||g(w[--x]='^',y--)||g(w[x--]='<',y++)||+(w[++x]=' '):w[x]=='O'&&!/ /.test(a)?w[x]='%':0))(y++)||g(y-=2)||g(y++,x++)||g(x-=2)||+(a[y][++x]='O'))||f(a,y,x+1):f(a,y+1))
<textarea id="tests">XXXXOOOOXXXX&#10;X          X&#10;X          X&#10;XXXXXXXXXXXX&#10;&#10;XOOOOOX&#10;X     X&#10;X     X&#10;X     XXXXXXXX&#10;X            X&#10;X            X&#10;XXXXXXXXXXXXXX&#10;&#10;XOOOOX&#10;X    X&#10;X    X&#10;X  XXX&#10;X    X&#10;X    X&#10;XXXXXX&#10;&#10;XXXXXXXXXXXXX&#10;O           X&#10;O    X      X&#10;O    X      X&#10;O           X&#10;XXXXXXXXXXXXX</textarea><br><button onclick="for(test of document.getElementById('tests').value.split('\n\n')){console.log(test);arr=test.split('\n').map(line=>line.split(''));f(arr);console.log(arr.map(line=>line.join('')).join('\n'))}">Run</button>

Quite hacky in some places, but I wanted to get the code out there. Input as a 2D character array, output by modifying said array.
Ungolfed version
This is the same exact algorithm, save for some truthy/falsy magic with +' ' being NaN being falsy (and some more), some golf variables and using ifs instead of ?:, || and &&.
f = (a, y = 0, x = 0) => {         // main function
  if (!a[y][x])                    // check for end of line
    return f(a, y + 1);            // end of line, recursively check next
  if (a[y][x] == 'O') {            // check for valid start position
    a[y][x] = '*';                 // set the start position
    function g() {                 // pathfinder function
      if (!a[y] || !a[y][x])       // check for out of bounds
        return 0;
      if (a[y][x] == ' ') {        // check for snow
        a[y][x] = 'v';             // set current cell to 'down'
        y++;                       // move position down
        if (g()) return 1;         // see if a valid route is found from there
        y--;                       // if not, reset position and try again
        a[y][x] = '>';             // repeat for other directions
        x++;
        if (g()) return 1;
        x--;
        a[y][x] = '^';
        y--;
        if (g()) return 1;
        y++;
        a[y][x] = '<';
        x++;
        if (g()) return 1;
        x++;
        a[y][x] = ' ';             // no route found, reset cell to snow
        return 0;
      }
      if (a[y][x] == 'O'           // check for valid exit
          && !/ /.test(a)) {       // and that no snow is left
        a[y][x] = '%';             // set the exit
        return 1;
      }
    }
    y++;                           // move a cell down from the start position
    if (g()) return 1;             // see if a valid route starts there
    y -= 2;                        // repeat for other directions
    if (g()) return 1;
    y++; x++;
    if (g()) return 1;
    x -= 2;
    if (g()) return 1;
    x++;
    a[y][x] = 'O';                 // no route found, continue on
  }
  return f(a, y, x + 1);           // check the next cell
}


Cover a Region with Rectangles Input

Your input in this challenge is a list of integer pairs. They represent the southwest corners of unit squares on the plane, and the list represents their union as a subset of the plane. For example, the list

[(0,0),(1,0),(0,1),(1,1),(2,1),(1,2),(2,2)]

represents the red-colored set in this picture:

Output

Yor output is a list of integer quadruples, representing rectangular subsets of the plane. More explicitly, a quadruple (x,y,w,h) reperents a rectangle of width w > 0 and height h > 0 whose southwest corner is at (x,y). The rectangles must form an exact covering of the input region, in the sense that each of the unit squares is a subset of some rectangle, each rectangle is a subset of the region, and two rectangles may overlap only at their borders. To forbid trivial solutions, the covering must not contain two rectangles that could be merged into a larger rectangle.

For example, the list

[(0,0,2,1),(0,1,3,1),(1,2,2,1)]

represents the legal covering

of the above region, whereas the covering given by

[(0,0,2,2),(2,1,1,1),(1,2,1,1),(2,2,1,1)]

is illegal, since the neighboring 1-by-1 squares could be merged:

Rules

You can give a full program or a function. The precise formatting of the input and output is not important, within reason. The shortest byte count wins, and standard loopholes are disallowed. You are encouraged to provide an explanation of your algorithm, and some example outputs.

Test Cases

A U-shaped region:

[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(1,0),(1,1),(1,2),(1,3),(1,4),(1,5),(2,0),(2,1),(3,0),(3,1),(4,0),(4,1),(4,2),(4,3),(4,4),(4,5),(5,0),(5,1),(5,2),(5,3),(5,4),(5,5)]

A large triangle:

[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(0,9),(1,0),(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(2,0),(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(3,0),(3,1),(3,2),(3,3),(3,4),(3,5),(3,6),(4,0),(4,1),(4,2),(4,3),(4,4),(4,5),(5,0),(5,1),(5,2),(5,3),(5,4),(6,0),(6,1),(6,2),(6,3),(7,0),(7,1),(7,2),(8,0),(8,1),(9,0)]

A square with holes:

[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(1,0),(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(2,0),(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),(3,0),(3,1),(3,2),(3,4),(3,5),(3,6),(3,7),(3,8),(3,9),(4,0),(4,1),(4,2),(4,3),(4,4),(4,5),(4,6),(4,7),(4,8),(4,9),(5,0),(5,1),(5,2),(5,3),(5,4),(5,5),(5,7),(5,8),(5,9),(6,1),(6,2),(6,3),(6,5),(6,6),(6,7),(6,8),(6,9),(7,0),(7,1),(7,2),(7,3),(7,4),(7,5),(7,6),(7,7),(7,8),(7,9),(8,0),(8,1),(8,2),(8,3),(8,4),(8,5),(8,6),(8,7),(8,8),(8,9),(9,0),(9,1),(9,2),(9,3),(9,4),(9,5),(9,6),(9,7),(9,8),(9,9)]

Disconnected regions:

[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(1,0),(1,1),(1,2),(1,3),(1,4),(1,6),(1,7),(1,8),(1,9),(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),(4,0),(4,1),(4,2),(4,4),(4,5),(4,6),(4,7),(4,8),(4,9),(5,0),(5,1),(5,2),(5,3),(5,4),(5,5),(5,6),(5,7),(5,8),(5,9),(6,0),(6,1),(6,2),(6,4),(6,5),(6,6),(6,7),(6,8),(6,9),(8,0),(8,1),(8,2),(8,3),(8,4),(8,5),(8,6),(8,7),(8,8),(8,9),(9,0),(9,1),(9,2),(9,3),(9,7),(9,8),(9,9),(10,0),(10,1),(10,2),(10,3),(10,4),(10,5),(10,6),(10,7),(10,8),(10,9)]

Verifier

Use this Python 2 program to verify your solution. It takes from STDIN a list of tuples (the input) and a list of quadruples (your output), separated by a comma.

I also wrote this Python 2 program to generate the pictures, and you can use it too. It takes from STDIN a list of either tuples or quadruples, and produces a file named out.png. It requires the PIL library. You can change the size of the grid cells and the width of the gird lines too, if you want.

Python - 272 261 258 251 224

I think I can golf this more. I'm pretty sure this works, but I haven't finished testing it on all of the test cases yet. I finished testing it. It works for all of the test cases.

a=sorted(input())
b=[]
r=range
for i in a:
 c=set(a)-set(b);w=h=1;x,y=i
 if i in b:continue
 while not{(x,y+h)}-c:h+=1
 while all((x+w,y+j)in c for j in r(h)):w+=1
 for j in r(w):
  for k in r(h):b+=(j+x,k+y),
 print x,y,w,h

I'm working on adding images of the results.
Edit: Here are the results from the example and the test cases:

I'm trying to write this in Perl, but I can't figure out how to get multidimensional arrays from stdin without a huge number of characters. Does anyone have any suggestions?


Symme-Try This Triangle Trial A string whose length is a positive triangular number (1, 3, 6, 10, 15...) can be arranged into an "equilateral text triangle" by adding some spaces and newlines (and keeping it in the same reading order).

For example, the length 10 string ABCDEFGHIJ becomes:

   A
  B C
 D E F
G H I J

Write a program or function that takes in such a string, except it will only contains the characters 0 and 1. (You may assume the input is valid.)

For the resulting "equilateral text triangle", output (print or return) one of four numbers that denotes the type of symmetry exhibited:

Output 2 if the triangle has bilateral symmetry. i.e. it has a line of symmetry from any one corner to the opposite side's midpoint.

Examples:

 0
1 1

 1
0 1

  0
 0 1
0 1 0

   1
  1 1
 1 0 1
0 1 1 1

Output 3 if the triangle has rotational symmetry. i.e. it could be rotated 120° with no visual change.

Examples:

   0
  1 0
 0 1 1
0 1 0 0

   0
  0 1
 1 0 0
0 0 1 0

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

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

Output 6 if the triangle has both bilateral and rotational symmetry. i.e. it matches the conditions for outputting both 2 and 3.

Examples:

0

1

 0
0 0

  1
 0 0
1 0 1

   0
  0 0
 0 1 0
0 0 0 0

Output 1 if the triangle has neither bilateral nor rotational symmetry.

Examples:

  1
 1 0
0 0 0

  0
 0 1
1 0 1

   1
  1 0
 1 1 1
1 1 1 1

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

The shortest code in bytes wins. Tiebreaker is earlier answer.

Aside from an optional trailing newline, the input string may not have space/newline padding or structure - it should be plain 0's and 1's.

If desired you may use any two distinct printable ASCII characters in place of 0 and 1.

Test Cases

Taken direct from examples.

011 -> 2
101 -> 2
001010 -> 2
1111010111 -> 2
0100110100 -> 3
0011000010 -> 3
101111111010111 -> 3
101001100010000100111 -> 3
0 -> 6
1 -> 6
000 -> 6
100101 -> 6
0000100000 -> 6
110000 -> 1
001101 -> 1
1101111111 -> 1
111111000111111 -> 1

"Rotating" any input by 120° will of course result in the same output.

CJam, 37 29 28 27 bytes

Thanks to Sp3000 for saving 3 bytes.

q{T):T/(\s}h]{z_Wf%_}3*])e=

Test suite.

This reuses some triangle rotation tricks from this challenge.

This also works for the same byte count:

q{T):T/(\s}h]3{;z_Wf%_}%)e=

Explanation

First, a quick recap from the triangle post I linked to above. We represent a triangle as a 2D (ragged) list, e.g.

[[0 1 1]
 [0 0]
 [0]]

The symmetry group of the triangle has 6 elements. There are cycles of length 3 by rotating the triangle and cycles of 2 by mirroring it along some axis. Conveniently, the rotations correspond to perform to two different reflections. We will use the following reflections to do this:

Transpose the list means reflecting it along the main diagonal, so we'd get:

[[0 0 0]
 [1 0]
 [1]]

Reversing each row represents a reflection which swaps the top two corners. Applying this to the result of the transposition we get:

[[0 0 0]
 [0 1]
 [1]]

Using these two transformations, and keeping the intermediate result, we can generate all six symmetries of the input.

A further point of note is the behaviour of transposition on a list like this:

[[0]
 [1 0]
 [1 0 0]
 []]

Because that's what we'll end up with after splitting up the input. Conveniently, after transposing, CJam flushes all lines to the left, which means this actually gets rid of the extraneous [] and brings it into a form that's useful for the above two transformations (all without changing the actual layout of the triangle beyond reflectional symmetry):

[[0 1 1]
 [0 0]
 [0]]

With that out of the way, here's the code:

q       e# Read input.
{       e# While the input string isn't empty yet...
  T):T  e#   Increment T (initially 0) and store it back in T.
  /     e#   Split input into chunks of that size.
  (     e#   Pull off the first chunk.
  \s    e#   Swap with remaining chunks and join them back together
        e#   into a single string.
}h
]       e# The stack now has chunks of increasing length and an empty string
        e# as I mentioned above. Wrap all of that in an array.
{       e# Execute this block 3 times...
  z_    e#   Transpose and duplicate. Remember that on the first iteration
        e#   this gets us a triangle of the desired form and on subsequent
        e#   iterations it adds one additional symmetry to the stack.
  Wf%_  e#   Reverse each row and duplicate.
}3*
        e# The stack now has all 6 symmetries as well as a copy of the
        e# last symmetry.
]       e# Wrap all of them in a list.
)       e# Pull off the copy of the last symmetry.
e=      e# Count how often it appears in the list of symmetries.


Intersection of circles – How can I reduce this golf code to 127 bytes? I started a CodeWars kata in Python, just two days ago, related to code golf.

Task: Given two congruent circles a and b of radius r, return the area of their intersection rounded down to the nearest integer, in less than 128 chars.

Has to be a one-liner.
Version: Python 3.6
External libraries: You may import NumPy as an external library.
Function name: circleIntersection
Input example: circleIntersection([0,0],[0,10], 10)

This is the closest I could come (129):

from math import*;circleIntersection=lambda a,b,r:r*r*(lambda h:h<1and acos(h)-h*(1-h*h)**.5)(hypot(b[0]-a[0],b[1]-a[1])/r/2)//.5

Use Python 2's arg unpacking: 124 bytes

from math import*;circleIntersection=lambda(v,w),(x,y),r:r*r*(lambda h:h<1and acos(h)-h*(1-h*h)**.5)(hypot(v-x,w-y)/r/2)//.5

Try it online!

Python 2 has parameter unpacking, allowing the input point arguments to be taken directly as pairs (v,w) and (x,y), where the input lists like [0,0] and [0,10] will be unpacked into the respective variables. This feature was removed in Python 3 -- a pity, in my opinion, since the old syntax seems more readable. But, the site has a Python 2 option, and nothing in your solution relies on Python 3.


Build a top-front-side puzzle solver A top-front-side puzzle is a puzzle where you are required to construct a 3-D shape of (usually cubic) blocks given three orthogonal views: a top view, a front view, and a side view.

For example, given a top, front, and side view as follows:

Top:        Front:      Side:
. . . .     . . . .     . . . .
. x x .     . x x .     . x x .
. x x .     . x x .     . x x .
. . . .     . . . .     . . . .

In this problem, the side view is taken from the right.

A 2x2x2 cube (with volume 8) would satisfy this solution, but it's doable in volume 4, if we have the following layer structure:

. . . .     . . . .
. x . .     . . x .
. . x .     . x . .
. . . .     . . . .

There are also some unsolvable arrangements. Take, for example:

Top:        Front:      Side:
. . . .     . . . .     . . . .
. . . .     . . x .     . . . .
. x . .     . . . .     . x . .
. . . .     . . . .     . . . .

If the top view says the block is second from the left, there's no way that can match the front view that says the block must be third from the left. So this arrangement is impossible.

Your task is to build a program that, given an arbitrary 4x4 top-front-side puzzle, attempts to solve it in the fewest number of cubes, or declares it unsolvable.

Your program will take as input a series of 48 bits, representing the top, front, and side views. They may be in any format you want (a 6-byte string, a string of 0's and 1's, a 12-digit hex number, etc.), but the order of the bits must map as such:

Top: 0x00   Front: 0x10 Side: 0x20
0 1 2 3     0 1 2 3     0 1 2 3
4 5 6 7     4 5 6 7     4 5 6 7
8 9 a b     8 9 a b     8 9 a b
c d e f     c d e f     c d e f

In other words, the bits go in a left-to-right, top-to-bottom order, in the top, then front, then side view.

Your program will then output either a series of 64 bits indicating the cubes in the 4x4x4 grid that are filled in, or indicate that the grid is unsolvable.

Your program will be scored by running a battery of 1,000,000 test cases.

The test data will be generated by taking the MD5 hashes of the integers "000000" through "999999" as strings, extracting the first 48 bits (12 hexits) of each of these hashes, and using them as input for the top-front-side puzzle. As an example, here are some of the test inputs and the puzzles they generate:

Puzzle seed: 000000   hash: 670b14728ad9
Top:        Front:      Side:
. x x .     . . . x     x . . .
x x x x     . x . x     x . x .
. . . .     . x x x     x x . x
x . x x     . . x .     x . . x

Puzzle seed: 000001   hash: 04fc711301f3
Top:        Front:      Side:
. . . .     . x x x     . . . .
. x . .     . . . x     . . . x
x x x x     . . . x     x x x x
x x . .     . . x x     . . x x

Puzzle seed: 000157   hash: fe88e8f9b499
Top:        Front:      Side:
x x x x     x x x .     x . x x
x x x .     x . . .     . x . .
x . . .     x x x x     x . . x
x . . .     x . . x     x . . x

The first two are unsolvable, while the last one has a solution with the following layers, front to back:

x . . .   . . . .   x x x .   x x x .
. . . .   x . . .   . . . .   . . . .
x . . .   . . . .   . . . .   x x x x
x . . .   . . . .   . . . .   x . . x

There are a total of 16 blocks here, but it can probably be done in less.

Your program's score will be determined by the following criteria, in descending order of priority:

The highest number of solved cases.
The lowest number of blocks required to solve those cases.
The shortest code in bytes.

You must submit and calculate the score by yourself, which requires your program to be able to run through all 1,000,000 test cases.

Python: 5360 test-cases solved using 69519 blocks, 594 bytes

This should be the optimal values.

Approach:

First I'll test if the test-case is actual solvable. I do this by initializing a list of length 64 by ones and set all positions to zero, if there the corresponding pixel of the three views is zero.
Then I simple view at the puzzle from all 3 directions, and look if the views are the same as the input views. If there're equal, the puzzle is solvable (we already found the worst solution), otherwise it's unsolvable.

Then I do a branch-and-bound approach for finding the optimal solution.

Branching: I have a recursive function. The recursion depth tells how many values are fixed already. In each call of the function I call itself twice, if the value at the current index is 1 (this value can be 0 or 1 in the optimal solution), or once, if the value is 0 (it has to be zero in the optimal solution).

Bounding: I use two different strategies here.

I calculate the views from the 3 sides in each function call and look If they still match the input values. If they don't match, I don't call the function recursively.
I keep the best solution in memory. It there already more fixed ones in the current branch than in the best solution, I can already close that branch. Additionally I can estimate a lower bound for the number of activated blocks, which are not fixed. And the condition becomes #number of activated fixed blocks + #lower bound of activated blocks (under the not fixed blocks) < #number of activated blocks in the best solution.

Here's the Python code. It defines a function f which expects 3 lists containing 1s and 0s and returns either 0 (not solvable) or a list of 1s and 0s representing the optimal solution.

S=sum;r=range
def f(t,f,s):
 for i in r(4):s[4*i:4*i+4]=s[4*i:4*i+4][::-1]
 c=[min(t[i%16],f[(i//16)*4+i%4],s[i//4])for i in r(64)]
 m=lambda:([int(S(c[i::16])>0)for i in r(16)],[int(S(c[i+j:i+j+16:4])>0)for i in r(0,64,16)for j in r(4)],[int(S(c[i+j:i+j+4])>0)for i in r(0,64,16)for j in r(0,16,4)])==(t,f,s)
 Z=[65,0];p=[]
 def g(k):
  if k>63and S(c)<Z[0]:Z[:]=[S(c),c[:]]
  if k>63or S(c[:k])+p[k]>=Z[0]:return
  if c[k]:c[k]=0;m()and g(k+1);c[k]=1
  m()and g(k+1)
 for i in r(64):h,R=(i//16)*4+4,(i//4)%4;p+=[max(S(f[h:]),S(s[h:]))+max((R<1)*S(f[h+i%4-3:h]),S(s[h+R-3:h]))]
 g(0);return Z[1]

The code length is 596 bytes/chars. And here's the test framework:

from hashlib import md5
from time import time

N = 1000000
start=time();count=blocks=0
for n in range(N):
 bits = list(map(int,"{:048b}".format(int(md5("{:06}".format(n).encode("utf-8")).hexdigest()[:12], 16))))
 result = f(bits[:16], bits[16:32], bits[32:])
 if result:
  count += 1
  blocks += sum(result)
  print("Seed: {:06}, blocks: {}, cube: {}".format(n, sum(result), result))
print()
print("{} out of {} puzzles are solvable using {} blocks.".format(count, N, blocks))
print("Total time: {:.2f} seconds".format(time()-start))

You can find an ungolfed version of the program here. It's also a little bit faster.

Results:

5360 out of 1000000 puzzles are solvable. In total we need 69519 blocks. The number of blocks varies from 6 blocks to 18 blocks. The hardest puzzle took about 1 second to solve. It's the puzzle with the seed "347177", which looks like

Top:      Front:    Side:
x x . .   x x x x   x . x .
x x x x   x x x x   x x x x
x x x x   x x x x   x x x x
x x . x   x x x x   x . x x

and has an optimal solution with 18 cubes. The following is a few from top for each of the layers:

Top 1:    Top 2:    Top 3:    Top 4:
. . . .   . x . .   . x . .   x . . .
. . x x   . . x .   x . . .   . x x .
. . . .   . . . x   x x x .   . . . .
x x . .   x . . .   . . . x   . . . x

The total running time for all test-cases was about 90 seconds. I used PyPy to execute the my program. CPython (the default Python interpreter) is a bit slower, but also solves all puzzles in only 7 minutes.

You can find the complete output here: The output is self-explanatory. E.g. the output for the puzzle above is:

Seed: 347177, blocks: 18, cube: [0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1]


Bidirectional Quine Chain PPCG hasn't had enough of quines already...

Challenge:

Your task is to create a program "A0". When this program is run with no input, it outputs nothing. When this program is run with input, it outputs "A1". When "A1" is run with no input, it outputs "A0". When "A1" is run with input, it outputs "A2". Pretty much, "A(k)" will output "A(k-1)" when run with no input, and will output "A(k+1)" when run with input.

Details

I believe this challenge is simple enough; there are no other rules really. Every program must contain at least 1 byte, by the way. You may assume that the input will consist of only ASCII characters, and you may ignore whitespace if you want, but you may not specify a specific input. Output may be to either STDOUT or STDERR, but all of your programs must output to the same one. The other one may also contain text (so you may output to STDOUT and then exit with an error). Thanks to @Dennis for pointing that out.

All programs must be in the same language, and each program must be unique from the rest of them.

The score is equal to the length of program "A0". As this is a code-golf challenge, the lowest score wins!

Python 2, 93 bytes
There is a trailing linefeed.

p=1+2*bool(input())-1;s='print"p=%r+2*bool(input())-1;s=%r*(p>0);exec s"%(p,s)'*(p>0);exec s

Try it with input | Try it without input
This is modified from my answer on a similar question.
If there is input, then it will increment p. So the resulting program will be p=2+..., p=3+..., etc.


Remove specified non-numeric rows In case there's any doubt: Nan = Non-numeric datatype for the purposes of this challenge.

Write a program or function that takes a matrix / array as input, as well as a list of column indices.

The challenge is to remove the rows where all elements in the specified columns are Nan. It doesn't matter if other elements in the row are numeric or not. The following examples will hopefully make this more clear (it's one-indexed):

Input array:
    16   NaN     3    13
     5    11   NaN     8
   NaN     7   NaN    12
     4    14   -15     1

Input column index: [1 3]

Output array:
16   NaN     3    13
 5    11   NaN     8
 4    14   -15     1

----

Input array:
    16   NaN     3    13
     5    11   NaN     8
   NaN     7   NaN    12
     4    14   -15     1

Input column index: 3

Output array =
    16   NaN     3    13
     4    14   -15     1

----

Input array:
   NaN   NaN   NaN   NaN
   NaN   NaN   NaN   NaN
   NaN   NaN   NaN   NaN
   NaN   NaN   NaN   NaN

Input column index: 1 2 4

Output array:
 []

Rules and clarifications:

The matrix will always be non-empty
The numeric values will be finite, but not necessarily integers or positive values
The column index vector can be empty (in which case no rows will be removed)
The column index will never have values exceeding the matrix dimensions
You can assume there won't be duplicates in the column index list
You can choose if you want to use zero- or one-indexed values (please specify)
You can take the input on any convenient format

Array as list of lists is OK. The column indices can be separate arguments

ans = and similar is accepted in output
You are free to choose what type of non-numeric datatype you want to use

It should be impossible to perform arithmetic operations with this datatype, or convert it to a finite number using functions such as float(x).

This is code golf, so shortest code in bytes win.

JavaScript (ES6), 48 46 bytes

(a,l)=>a.filter(r=>l.some(c=>r[a=0,c]<1/0)||a)

Explanation

Expects an array of rows as arrays, and an array of 0-indexed numbers for the columns to check. Returns an array of arrays.

Straight-forward filter and some. Checks for NaN by using n < Infinity (true for finite numbers, false for NaNs).

var solution =

(a,l)=>
  a.filter(r=>     // for each row r
    l.some(c=>     // for each column to check c
      r[a=0,       // set a to false so we know the some was executed
        c]<1/0     // if any are not NaN, do not remove the row
    )
    ||a            // default to a because if l is of length 0, some returns false but
  )                //     we must return true
<textarea id="matrix" rows="5" cols="40">16 NaN 3 13
5 11 NaN 8
NaN 7 NaN 12
4 14 -15 1</textarea>

<input type="text" id="columns" value="0 2" />
<button onclick="result.textContent=solution(matrix.value.split('\n').map(l=>l.split(' ').map(n=>+n)),(columns.value.match(/\d+/g)||[]).map(n=>+n)).join('\n')">Go</button>


Generate a (completely deterministic) pseudorandom bit stream Inspired by Random with your hands tied:

The Goal

The goal of this challenge is to write a program that generates a pseudorandom bit stream, which is a string of 1s and 0s that appears to be purely random, but is actually generated in a deterministic way. Your program should output a string of 1 and 0s (with optional whitespace) and should pass the following requirements:

Given unlimited time and memory, your program must continue to output a string of 1s and 0s forever
Your program must output more than 1000 random bits in about one minute, on a reasonable machine. If this requirement is impossible, then I will lessen it.
The string of bits can repeat, but the length of the repeating section must be more than 1000 bits.
The string of bits must pass as many of the randomness tests (described below) as possible.
The program must not take any input from any external sources or use any built-in rand()-like function.
Because of the above requirement, the program must output the same exact string of bits each time that it is run.

Randomness Test #1

The string of pseudorandom bits must not include any obvious pattern upon visual inspection.

Randomness Test #2 (subject to change based on comments)

The string of bits must contain an equal distribution of 1s and 0s. To test this (and other things too), the stream of bits is broken into segments that are 3 bits long, such as 101|111|001.

Out of all of these segments, 1/8 of them should have three 1s and no 0s, 3/8 of them should have two 1s and one 0, 3/8 of them should have one 1 and two 0s, and 1/8 of them should have no 1s and three 0s.

Randomness Test #3

A "run" is defined as a consecutive series of bits that all have the same value. The string 1001001110 has three runs of size 1 (1..1.....0), two runs of size 2 (.00.00....) and one run of size 3 (......111.).  Notice that runs do not overlap.

Out of a string of 1000 random bits, there should be about 250 runs of size 1, 125 runs of size 2, 62 runs of size 3, etc. In general, for run size R, there should be about 1000/(2**(R+1)) runs of that size.

Randomness Test #4

The first 840 bits are split into two halves of 420 bits each. Each bit on the first half is compared to the corresponding bit on the second half. The two bits should match about fifty percent of the time.

Here is the source code of a Perl program that performs tests 2 through 4. As of now, it requires that the string of bits not contain any whitespace.

Objective Winning Criterion Time!

The winner is the program that passes all of the 6 requirements and all of the randomness tests to the degree that it is indistinguishable from randomness. If multiple programs accomplish this, then the one that takes the longest amount of time to repeat will win. If multiple programs accomplish this, then I might have to find more randomness tests to act as tie-breakers.