Solve 2-SAT (boolean satisfiability) The general SAT (boolean satisfiability) problem is NP-complete.  But 2-SAT, where each clause has only 2 variables, is in P.  Write a solver for 2-SAT.

Input:

A 2-SAT instance, encoded in CNF as follows.  The first line contains V, the number of boolean variables and N, the number of clauses.  Then N lines follow, each with 2 nonzero integers representing the literals of a clause.  Positive integers represent the given boolean variable and negative integers represent the variable's negation.

Example 1

input

4 5
1 2
2 3
3 4
-1 -3
-2 -4

which encodes the formula (x1 or x2) and (x2 or x3) and (x3 or x4) and (not x1 or not x3) and (not x2 or not x4).

The only setting of the 4 variables that makes the whole formula true is x1=false, x2=true, x3=true, x4=false, so your program should output the single line

output

0 1 1 0

representing the truth values of the V variables (in order from x1 to xV).  If there are multiple solutions, you may output any nonempty subset of them, one per line.  If there is no solution, you must output UNSOLVABLE.

Example 2

input

2 4
1 2
-1 2
-2 1
-1 -2

output

UNSOLVABLE

Example 3

input

2 4
1 2
-1 2
2 -1
-1 -2

output

0 1

Example 4

input

8 12
1 4
-2 5
3 7
2 -5
-8 -2
3 -1
4 -3
5 -4
-3 -7
6 7
1 7
-7 -1

output

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

(or any nonempty subset of those 3 lines)

Your program must handle all N,V < 100 in a reasonable time.  Try this example to make sure your program can handle a big instance.  Smallest program wins.

Haskell, 278 characters

(∈)=elem
r v[][]=[(>>=(++" ").show.fromEnum.(∈v))]
r v[]c@(a:b:_)=r(a:v)c[]++r(-a:v)c[]++[const"UNSOLVABLE"]
r v(a:b:c)d|a∈v||b∈v=r v c d|(-a)∈v=i b|(-b)∈v=i a|1<3=r v c(a:b:d)where i w|(-w)∈v=[]|1<3=r(w:v)(c++d)[]
t(n:_:c)=(r[][]c!!0)[1..n]++"\n"
main=interact$t.map read.words

Not brute force. Runs in polynomial time. Solves the hard problem (60 variables, 99 clauses) quickly:

> time (runhaskell 1933-2Sat.hs < 1933-hard2sat.txt)
1 1 1 0 0 0 0 0 0 1 1 0 0 1 0 1 1 1 0 1 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 1 1 1 1 0

real 0m0.593s
user 0m0.502s
sys  0m0.074s

And actually, most of that time is spent compiling the code!

Full source file, with test cases and quick-check tests available.

Ungolf'd:

-- | A variable or its negation
-- Note that applying unary negation (-) to a term inverts it.
type Term = Int

-- | A set of terms taken to be true.
-- Should only contain  a variable or its negation, never both.
type TruthAssignment = [Term]

-- | Special value indicating that no consistent truth assignment is possible.
unsolvable :: TruthAssignment
unsolvable = [0]

-- | Clauses are a list of terms, taken in pairs.
-- Each pair is a disjunction (or), the list as a whole the conjuction (and)
-- of the pairs.
type Clauses = [Term]

-- | Test to see if a term is in an assignment
(∈) :: Term -> TruthAssignment -> Bool
a∈v = a `elem` v;

-- | Satisfy a set of clauses, from a starting assignment.
-- Returns a non-exhaustive list of possible assignments, followed by
-- unsolvable. If unsolvable is first, there is no possible assignment.
satisfy :: TruthAssignment -> Clauses -> [TruthAssignment]
satisfy v c@(a:b:_) = reduce (a:v) c ++ reduce (-a:v) c ++ [unsolvable]
  -- pick a term from the first clause, either it or its negation must be true;
  -- if neither produces a viable result, then the clauses are unsolvable
satisfy v [] = [v]
  -- if there are no clauses, then the starting assignment is a solution!

-- | Reduce a set of clauses, given a starting assignment, then solve that
reduce :: TruthAssignment -> Clauses -> [TruthAssignment]
reduce v c = reduce' v c []
  where
    reduce' v (a:b:c) d
        | a∈v || b∈v = reduce' v c d
            -- if the clause is already satisfied, then just drop it
        | (-a)∈v = imply b
        | (-b)∈v = imply a
            -- if either term is not true, the other term must be true
        | otherwise = reduce' v c (a:b:d)
            -- this clause is still undetermined, save it for later
        where
          imply w
            | (-w)∈v = []  -- if w is also false, there is no possible solution
            | otherwise = reduce (w:v) (c++d)
                -- otherwise, set w true, and reduce again
    reduce' v [] d = satisfy v d
        -- once all caluses have been reduced, satisfy the remaining

-- | Format a solution. Terms not assigned are choosen to be false
format :: Int -> TruthAssignment -> String
format n v
    | v == unsolvable = "UNSOLVABLE"
    | otherwise = unwords . map (bit.(∈v)) $ [1..n]
  where
    bit False = "0"
    bit True = "1"

main = interact $ run . map read . words
  where
    run (n:_:c) = (format n $ head $ satisfy [] c) ++ "\n"
        -- first number of input is number of variables
        -- second number of input is number of claues, ignored
        -- remaining numbers are the clauses, taken two at a time

In the golf'd version, satisfy and format have been rolled into reduce, though in order to avoid passing n, reduce returns a function from a list of variables ([1..n]) to the string result.

Edit: (330 -> 323) made s an operator, better handling of the newline
Edit: (323 -> 313) first element from a lazy list of results is smaller than a custom short-circuit operator; renamed main solver function 'cause I like using ∮ as an operator!
Edit: (313 -> 296) keep clauses as a single list, not a list of lists; process it two elements at a time
Edit: (296 -> 291) merged the two mutually recursive functions; it was cheaper to inline ★ so test now renamed ∈
Edit: (291 -> 278) inlined output formatting into results generation


Print cos(2π/17) exactly One way to construct a regular heptadecagon starts with drawing a horizontal line of length 1 from the center to a vertex. Then the distance along that line from the center to the second vertex is cos(2π/17). All other vertices are easy to get.

The goal of this challenge is to print (or produce in any other conventional way) an ASCII math expression involving the operations +, -, *, /, sqrt() and the natural numbers, which gives cos(2π/17) when evaluated. The power operator is not allowed: e.g. sqrt(17) cannot be written as 17^(1/2).

For example (formula taken from Wikipedia):

1/16*(
    -1+
    sqrt(17)+
    sqrt(34-2*sqrt(17))+
    2*sqrt(
        17+
        3*sqrt(17)-
        sqrt(34-2*sqrt(17))-
        2*sqrt(34+2*sqrt(17))
    )
)

Whitespace doesn't matter. The length and complexity of the expression doesn't matter, as long as it's syntactically correct (as defined above) and numerically equivalent to cos(2π/17).

Built-in functions are allowed.

CJam (60 bytes)

1-4{"(- +sqrt( * -4*
))/2"S/@a*N/\a*}:F~'-\+WF'-\+W-4FWFF'/2

Online demo

Output (with added newlines to avoid wrapping):

(--(--(-1+sqrt(1*1-4*-4))/2+sqrt(-(-1+sqrt(1*1-4*-4))/2*-(-1+sqrt(1*1-4*-4))/2-4*-1)
)/2+sqrt(-(--(-1+sqrt(1*1-4*-4))/2+sqrt(-(-1+sqrt(1*1-4*-4))/2*-(-1+sqrt(1*1-4*-4))/
2-4*-1))/2*-(--(-1+sqrt(1*1-4*-4))/2+sqrt(-(-1+sqrt(1*1-4*-4))/2*-(-1+sqrt(1*1-4*-4)
)/2-4*-1))/2-4*(-(--1+sqrt(-1*-1-4*-4))/2+sqrt((--1+sqrt(-1*-1-4*-4))/2*(--1+sqrt(-1
*-1-4*-4))/2-4*-1))/2))/2/2

I suspect this is the kind of answer OP was secretly hoping for. Rather than apply general-purpose compression to a string, it uses the field structure which Gauss first exploited to present this value in surds, in his Disquisitiones Arithmeticae.

I worked from this presentation (pages 18 and 19) but adapted it slightly in order to only ever require the positive root of a quadratic. Unrolled and in pseudo-code, the expression breaks down as

# Positive root of x^2 + bx + c = 0
F(b, c) = (-b + sqrt(b*b - 4*c))/2
# (8,1)
p = F(1, -4)
# (4,1)
q = F(-p, -1)
# -(8,3)
r = F(-1, -4)
# (4,3)
s = F(r, -1)
# Result
F(-q, s)/2


Generate a golfed program to evaluate an arithmetic expression Your task is to write a program that will take input like this:

a + b * c + a / 2

and will generate the source code for a program that takes user input and then evaluates the expression.

The expression can contain the operators +,-,*,/; single-letter lowercase variables; and integers between 0 and 32000.  Standard arithmetic precedence must be correctly followed. The expression is limited to 26 unique variables a to z.  However, a single variable can appear more than once.

You can assume that the input expression is valid (follows these rules).

The generated program must prompt for user input in this form, prompting only once for each variable:

a =

User input from 0 to 32000 should be handled correctly. It will then print the expression and the correct result.  You can use either integer or floating point arithmetic.  The calculations should be performed with at least 32 bit precision. Beyond that, you don't have to worry about overflow or divide by zero.

Example of a non-golfed generated Perl program for the above expression:

print "a = ";
my $a = <>;
print "b = ";
my $b = <>;
print "c = ";
my $c = <>;
print "a + b * c + a / 2 = " . ($a + $b * $c + $a / 2);

Example input and output of program generated for above expression:

a = 1
b = 2
c = 3
a + b * c + a / 2 = 7.5

The score is calculated as length of the program + length of the generated program for this expression:

1 + a * 4 * b + 2 / d * e - a - 3 + g / h * 32000

Lowest score wins.

Update: Just to highlight a couple of requirements of the problem, as stated above:

The output of the program must be source code for another program that evaluates the expression.
The program must print the original expression. Perhaps there is some ambiguity in this (one could argue that a+b is the same expression as a + b), but for clarity let's say that it must be the original expression with white space intact.  All valid answers so far have done it that way.

Lua, 202 + 166 = 368

File "generate_code.lua"

F=...
C='function G(v)io.write(v.." = ")_G[v]=io.read"*n"end 'V={}for v in F:gmatch'%l'do V[v]=0 end
for v in pairs(V)do C=C..'G"'..v..'"'end
print(C..'F="'..F..'"print(F.." = "..load("return "..F)())')

Usage:

$ lua generate_code.lua "1 + a * 4 * b + 2 / d * e - a - 3 + g / h * 32000"

Code generated (order of variables is not specified):

function G(v)io.write(v.." = ")_G[v]=io.read"*n"end G"g"G"e"G"d"G"b"G"a"G"h"F="1 + a * 4 * b + 2 / d * e - a - 3 + g / h * 32000"print(F.." = "..load("return "..F)())

Generated code in action:

g = 4
e = 3
d = 2
b = 1
a = 6.5
h = 4.3
1 + a * 4 * b + 2 / d * e - a - 3 + g / h * 32000 = 29787.941860465


Operator that combines sum, product and difference between two numbers Challenge:

There's a silly puzzle circulating on social networks that reads:

8 + 2 = 16106
5 + 4 = 2091
9 + 6 = ?

Implement a function or operator that, when given two positive integer numbers x and y such that x > y > 0, yields the correct answer as an integer, where the answer's digits are the digits of x * y followed by the digits of x + y followed by the digits of x - y. Very simple.

Rules:

Standard loopholes are disallowed.
This is code-golf so shortest code in bytes wins.
Input data validation is not required. This program may crash or return garbage when given invalid input.
You're allowed to use numeric functions and operators (including integer and floating point, math library functions, and other functions that accept and return numbers).
You're allowed to use a function that returns the number of digits of a number, if applicable.
You're not allowed to use strings or any kind of concatenation anywhere in your code.
The result may be returned or pushed to the stack, whichever applies in the language. The result must be an integer number, not a string.

Sample code:

Dyalog APL:

The following code creates a dyadic operator named X.

  X←{(⍺-⍵)+((⍺+⍵)×10*1+⌊10⍟⍺-⍵)+⍺×⍵×10*(2+⌊10⍟⍺+⍵)+⌊10⍟⍺-⍵}

Explanation:

In APL, you evaluate from right to left.
⍺ and ⍵ are the left and right operand, respectively
⌊10⍟⍺-⍵ reads: floor of log10(⍺-⍵). First performs substraction then logarithm then floor. From right to left. log10 is done in order to count the digits of ⍺-⍵ (you must sum 1 afterwards).
⍺×⍵×10*(...) reads: 10 to the (...)th power, multiplied by ⍵, multiplied by ⍺
Hence, ⍺×⍵×10*(2+⌊10⍟⍺+⍵)+⌊10⍟⍺-⍵ is the product, shifted to the left by the sum of the number of digits of the sum and the difference. Multiplying by a power of 10 will shift an integer to the left.
((⍺+⍵)×10*1+⌊10⍟⍺-⍵) is the sum, shifted to the left by the number of digits of the difference.
(⍺-⍵) is the difference. No shifting is necessary here.
X←{...} is how you define an operator in APL.

Examples:

      8 X 2
16106
      5 X 4
2091
      9 X 6
54153

GNU dc:

The following code creates a macro named a:

[sysx10lxly-dseZdsclxly+dsd+Z1+^lxly**10lc^ld*+le+]sa

Explanation:

sx and sy pop an element from the stack and save it on the registers x and y, respectively.
lx and ly load an element from registers x and y respectively and push it to the stack.
d duplicates the last element in the stack.
^ computes the power of two numbers.
Z pops a number and returns its number of digits. This is done because dc has no logarithm function.
[...]sa stores a macro in register a. la loads it. x executes the macro at the top of the stack.

Examples:

8 2 laxn
16106
5 4 laxn
2091
9 6 laxn
54153

JavaScript (ES7), 63 61 59 bytes

Saved 4 bytes thanks to Neil.

(a,b)=>[a*b,a+b,a-b].reduce((p,c)=>p*10**-~Math.log10(c)+c)

<input id=a type=number oninput="c.innerText=((a,b)=>[a*b,a+b,a-b].reduce((p,c)=>p*10**-~Math.log10(c)+c))(+a.value,+b.value)">
<input id=b type=number oninput="c.innerText=((a,b)=>[a*b,a+b,a-b].reduce((p,c)=>p*10**-!Math.log10(c)+c))(+a.value,+b.value)">
<p id=c>


Is there a way of shortening fat-arrow functions? From what I've seen throughout my time here on PPCG, most JavaScript entries involving fat arrow functions tend to be one of two camps:

The simple ones that are capable of running as a single statement and returning an answer, straight off the bat, like x=(a,b)=>a*a+b
The more complex ones that usually have curly braces because of the use of loops, and as a result require the use of a return statement.. like p=b=>{m=b;for(a=1;~-m;)--m,a*=m*m;return a%b}

Taking the above example from category 2 with the curly braces concept as proof-of-concept... Would there be a way to re-golf this code (or similar) like this so as to eliminate the curly braces as well as the return? I'm only asking this as this could potentially (not saying this will happen all the time) eliminate 8 bytes from a JS golfer's code. Are there any techniques that one could use in this instance? I've tried recursion, but the m=b statement has proven to be a bit of a bugbear, as I can't seem to shake it.

For the above code, how would one golf that further so as to eliminate the return statement, regardless of whether it golfs shorter or not?

Use Recursion

I've found that recursion is (almost) always shorter than eval+for. The general way to convert from for to eval is:

for(a=n;b;c);d
(f=a=>b?f(c):d)(n)

So let's see your example:

b=>{m=b;for(a=1;~-m;)--m,a*=m*m;return a%b}

We can first simplify it to:

for(m=b,a=1;~-m;--m,a*=m*m)a%b;

What did we do here? Well we simply moved everything inside the for statement, this helps us reduce the amount of semicolons which is not directly better but almost always leads to some golf.

Let's put this in eval and compare it to the recursion version:

b=>{m=b;for(a=1;~-m;)--m,a*=m*m;return a%b}
b=>eval('for(m=b,a=1;~-m;--m,a*=m*m)a%b')
b=>(f=a=>~-m?(--m,f(a*=m*m)):a%b)(1,m=b)

The first part of the for loop (a=n), we can start that off by passing those variables in as arguments. The condition is simply: b?(c,f(a)):d where d is the return value. Usually c just modifies a so it can be merged into it. So we can golf it even more using what I've mentioned:

b=>(f=a=>~-m?(--m,f(a*=m*m)):a%b)(1,m=b)
b=>(f=a=>~-m?f(a*=--m*m):a%b)(1,m=b) // --m moved into a*=
b=>(f=a=>--m?f(a*=m*m):a%b)(1,m=b) // --m moved to condition

That said, as noted by @Niel is simplifying your algorithm. An algorithm golfy in one language may not be golfy in another so make sure to try different algoriths and compare them.


I uppercase the source code, you reverse the input! It's one of these again :D
Your task, if you wish to accept it, is to write a program/function (without any uppercase letters) that outputs/returns its string input/argument. The tricky part is that if I convert your source code to uppercase, the output must be reversed.
For simplicity, you can assume that the input is always a single line string containing only ASCII letters (a-z), digits (0-9), and spaces.
You do not need to handle empty input.
Example
Let's say your source code is abc and its input is hello. If I write ABC instead and run it, the output must be olleh.

05AB1E, 1 byte
r

Try it online lowercase or uppercase!
Finally a question which I (a dumb brain) can answer! Thanks for this easy, yet fun challenge! (I do feel great, even though it requires little effort to make an answer in 05AB1E.)
Wait, how?
r # reverses the stack. (Which literally does not do anything since only the
  # implicit input is in the stack)
R # actually reverses the top string of the stack (Which is the implicit input).
  # at the end, the input is automatically printed.


Prepare data for JS renderer It's asked to write a script to generate a source data to feed a JavaScript renderer.
JS Renderer documentation
The JS renderer is this script:

function o(x){
  r=x.split(' ');
  (d=document).write('<style>i{position:absolute;width:10;height:10;background:#000}</style>');
  for(i=0;i<r.length;++i){c=r[i].split(',');d.write('<i style=top:'+(e=eval)(c[0])+';left:'+e(c[1])+'></i>')
  }
}

It takes as input a list of X/Y coordinates separated by spaces and commas and prints on DOM the points as 10×10 pixel squares.
For example, if you call the script with:
o('0,0 10,0 20,0 30,0 40,0 20,10 20,20 0,30 10,30 20,30 30,30 40,30 0,50 10,50 20,50 30,50 40,50');

It will print:

Notice that the values can be expressed as calculations, so it will accept:
o('10*2,50/5');

Your task
Write a script that, given as input a string of characters ([A-Z0-9 ]; uppercase letters, numbers, spaces) prints on stdout the coordinates to feed the JS renderer.
Rules

The "line-height" of the characters should be of at least 50px
Your script doesn't need to run the JS parser
The expected output format is: x,y x,y x,y x,y
The shortest code wins

Bonus: if you could reduce the length of the JS renderer without changing the behavior would be great :)


Iterated Divisor Twist Definitions

Let m and n be positive integers. We say that m is a divisor twist of n if there exists integers 1 < a ≤ b such that n = a*b and m = (a - 1)*(b + 1) + 1. If m can be obtained from n by applying zero or more divisor twists to it, then m is a descendant of n. Note that every number is its own descendant.

For example, consider n = 16. We can choose a = 2 and b = 8, since 2*8 = 16. Then

(a - 1)*(b + 1) + 1 = 1*9 + 1 = 10

which shows that 10 is a divisor twist of 16. With a = 2 and b = 5, we then see that 7 is a divisor twist of 10. Thus 7 is a descendant of 16.

The task

Given a positive integer n, compute the descendants of n, listed in increasing order, without duplicates.

Rules

You are not allowed to use built-in operations that compute the divisors of a number.

Both full programs and functions are accepted, and returning a collection datatype (like a set of some kind) is allowed, as long as it is sorted and duplicate-free. The lowest byte count wins, and standard loopholes are disallowed.

Test Cases

1 ->  [1]
2 ->  [2] (any prime number returns just itself)
4 ->  [4]
16 -> [7, 10, 16]
28 -> [7, 10, 16, 25, 28]
51 -> [37, 51]
60 -> [7, 10, 11, 13, 15, 16, 17, 18, 23, 25, 28, 29, 30, 32, 43, 46, 49, 53, 55, 56, 60]

Python 2, 109 98 85 82 bytes
f=lambda n:sorted(set(sum(map(f,{n-x+n/x for x in range(2,n)if(n<x*x)>n%x}),[n])))

Since (a-1)*(b+1)+1 == a*b-(b-a) and b >= a, descendants are always less than or equal to the original number. So we can just start with the initial number and keep generating strictly smaller descendants until there are none left.
The condition (n<x*x)>n%x checks two things in one - that n<x*x and n%x == 0.
(Thanks to @xnor for taking 3 bytes off the base case)
Pyth, 32 bytes
LS{s+]]bmydm+-bk/bkf><b*TT%bTr2b

Direct translation of the above, except for the fact that Pyth seems to choke when trying to sum (s) on an empty list.
This defines a function y which can be called by appending y<number> at the end, like so (try it online):
LS{s+]]bmydm+-bk/bkf><b*TT%bTr2by60

CJam, 47 45 bytes
{{:X_,2>{__*X>X@%>},{_X\/\-X+}%{F}%~}:F~]_&$}

Also using the same method, with a few modifications. I wanted to try CJam for comparison, but unfortunately I'm much worse at CJam than I am at Pyth/Python, so there's probably a lot of room for improvement.
The above is a block (basically CJam's version of unnamed functions) that takes in an int and returns a list. You can test it like so (try it online):
{{:X_,2>{__*X>X@%>},{_X\/\-X+}%{F}%~}:F~]_&$}:G; 60 Gp


Program template for printing *any* string Write a program with the following properties:

When run as-is, the program produces no output (i.e. 0 bytes of output).
There is a location within the program (of your choice: it could be at the start, end, or somewhere in the middle) with the following property: modifying the program via placing any string there will cause the resulting program to print that string when executed.

This must work regardless of whether the string contains quotes, backslashes, comment marks, delimiters, NUL bytes, etc.; no matter what you place there, the string is still interpreted as a string and printed entirely verbatim. You can, however, fail to handle very very long strings if they would cause the compiler to run out of memory, or the like (to be precise, you should at least be able to handle strings up to 1000 bytes long or three times the length of your program, whichever is longer).

An example of an invalid solution would be

print("");
#      ^ text goes here

in Python, Perl, Ruby, etc.; although it works for many strings, it will not work for a string containing a double quote, or a string containing the substring \n (which would be interpreted as a newline).

Note that this problem is probably impossible in most languages; the challenge is at least partially about finding a language where it works. Your chosen language must be a programming language under this site's definition, e.g. no submitting a solution in Text.

As this is a code-golf, the shortest program template wins. However, do not be discouraged from submitting solutions even if they can't beat the current winner! You can still compete for second, third, etc. place, or simply to find as many answers where it works as possible. You should, however, ensure that your program meets the entire specification before submitting it; approximate solutions would miss the point of the problem.

Excel, 1 byte

'

Ungolfed version

'        <-- print the following text,
             and exit the current formula


Fastest Home Prime Generator What is a home prime?

For an example, take HP(4). First, find the prime factors. The prime factors of 4 (in numerical order from least to greatest, always) are 2, 2. Take those factors as a literal number. 2, 2 becomes 22. This process of factoring continues until you reach a prime number.

number    prime factors
4         2, 2
22        2, 11
211       211 is prime

Once you reach a prime number, the sequence ends. HP(4)=211. Here's a longer example, with 14:

number    prime factors
14        2, 7
27        3, 3, 3
333       3, 3, 37
3337      47, 71
4771      13, 367
13367     13367 is prime

Your challenge is to create a program that will calculate HP(x) given x, and do it as quickly as possible. You may use whatever resources you want, other than a list of known home primes.

Take note, these numbers become very large very fast. At x=8, HP(x) jumps all the way to 3331113965338635107. HP(49) has yet to be found.

Program speed will be tested on a Raspberry Pi 2, averaging the following inputs:

16
20
64
65
80

If you have a Raspberry Pi 2, time the program yourself, then average the times.

Mathematica, HP(80) in ~0.88s

NestWhile[
  FromDigits[
    Flatten[IntegerDigits /@
      ConstantArray @@@ FactorInteger[#]]] &, #, CompositeQ] &

Anonymous function. Takes a number as input and returns a number as output.


400th Question Celebration/Challenge I just looked and saw that there are 399 questions on this wondrous "Programming Puzzles & Code Golf" site!!!  That means that...THIS IS THE 400th question!!!  To celebrate this momentous occasion, here are your goals:

Write a piece of code that is EXACTLY 400 bits.

That's right...BITS!!!
For the risk of redundancy and the sake of clarity, that's 50 bytes!!!

Because this occasion is so extraordinarily meaningful, each bit and therefore each byte must also be meaningful!

In other words:  You can't just name a variable aaaaa because you needed 32 extra bits to get to 400.  However, you can rename it to party as long as that is a meaningful name for that variable.

Your program must do something appropriate (not necessarily output something appropriate) to celebrate this grand occasion!

For example:  You could choose to make a program that outputs 400. However, I must needs state that although submitting code that does only that would meet this requirement, it would also be like celebrating your birthday party at home by yourself sick in bed.  At least you celebrated, but hey: You can do better!!!

The most creative code wins!!!  In this case, creativity will be measured by votes.
This contest will last until 400 users have viewed this question.  If there is a tie when the 400th user views this question, the contest will go into sudden-death overtime until there is a clear winner

Oh, and lest I forget...HAPPY 400th QUESTION!!!

Python, FOUR HUNDRED bits
i=0
while 1:print" "*(i%8>3 and-i%4 or i%4),0;i+=1
At first I wanted to make a sine scroller, but there was no place for the import. Now you get a bugged triangle wave. ~~~party~~~


Evaluate the B-spline basis B-splines are defined using a set of "knots", "control points", and degree. For the purposes of this challenge, the control points are not needed.

The knots are simply a list of strictly increasing real values (note that real B-splines may have repeated knots, for the purposes of this challenge assume knots are all unique). The degree is a non-negative integer.

The set of polynomial basis functions are recursively defined as (image credit):

where i is the i-th basis function, and p is the degree of the basis function. u is the curve parameterization, and u_j is the j'th knot.

The goal of this challenge is to evaluate all the basis functions for a curve of degree m at location u.

Input

Your program/function should take as input 3 parameters:

A real value for the location u
A non-negative integer for the curve degree m
A list of strictly increasing real values for the knots vector u_j

You may take these parameters in any order desired and may mutate the inputs as long as no additional information is added (for example, you may take the knots vector to be a combination of a real pointer and integer length).

The input may come from any source desired (stdio, function parameter, etc.).

You may assume the input describes a valid B-spline and that u is in the range of the knots vector.

Output

Your program/function should output a list of real numbers describing what the basis functions evaluate to. That is, you should output  for all 0 <= i <= n-1-m, where n is the number of knots (For 1-based indexing, then 1 <= i <= n - m). The output must be accurate to within 1% or 1000 ULP of the true value, whichever is greater. The output may be to any sink desired (stdout, return value, etc.)

Examples

All examples are formatted as such:

u
m
u_0 u_1 u_2 ...
N_{0,m}(u) N_{1,m}(u) N_{2,m}(u) ...

case 1:

.5
0
0 0.5 1
0 1

case 2:

.5
1
-1 0 1 2
0.5 0.5

case 3:

 0.9
 1
 -1 0 1 2 3
 0.1 0.9 0

case 4:

 1.1
 1
 -1 0 1 2 3
 0 0.9 0.1

case 7:

 3
 3
 -1 0 1 2 3 8 10 12 15 20
 0 0.5952381 0.38392857 0.02083333 0 0

Hints

Notice that N_{p} depends only on N_{p-1}. That means rather than recursing from the top-down, you could start at the base case and work up. While this is faster execution-wise, I'm not sure if this will necessarily produce the shortest code.

Here's a reference implementation using Python3+NumPy for the bottom-up approach:

from numpy import *

def basis(knots, m, u):
    # base case
    Ns = 1.*logical_and(knots[:-1] <= u, u < knots[1:])
    # work backwards, starting at the base case up to p=m
    for p in range(1,m+1):
        Ns = (u - knots[:-1-p]) * Ns[:-1] / (knots[p:-1] - knots[:-p-1]) \
             + (knots[p+1:] - u) * Ns[1:] / (knots[p+1:]- knots[1:-p])
    return Ns

Scoring

This is code golf; shortest answer in bytes wins. Standard loopholes are prohibited. You are welcome to use any built-ins desired.

Pyth - 83 82 bytes
Jesus, this is long, probably a few redundancies, but the formulas are long. This is a recursive solution that just implements the formulas given. The reference solution seems to be doing something else, but I don't know what. Maybe if I knew more about what all of this does...
KEM?H+.x*c-KJ@QG-@Q+GHJgGtHZ.x*c-=T@Qh+GHK-T@QhGghGtHZ&|>K@QGqK@QG<K@QhGgRvzt-lQvz

Test Suite.


What a wonderful world The challenge is programming a program that prints following lyrics of Louis Armstrong's What A Wonderful World with as few characters as possible. The key is obviously kind of a 'compression'. I encourage to use and enhance ideas of previous answers, but please declare if you do so!

Rules:
No information can be stored externally, everything must be contained in the code itself.
Only ASCII characters allwed in the code.
The text must be reproduced exactly.
Output to console or text file.

I see trees of green, red roses, too,
I see them bloom, for me and you
And I think to myself
What a wonderful world.

I see skies of blue, and clouds of white,
The bright blessed day, the dark sacred night
And I think to myself
What a wonderful world.

The colors of the rainbow, so pretty in the sky,
Are also on the faces of people going by.
I see friends shaking hands, sayin', "How do you do?"
They're really sayin', "I love you."

I hear babies cryin'. I watch them grow.
They'll learn much more than I'll ever know
And I think to myself
What a wonderful world

Yes, I think to myself
What a wonderful world

PS: Why I think this is different to other encoded songs: Longer text; ASCII-only; a lot of repeating text/similar text.

EDIT: FEWEST of course. Ending will be 22th of June!

Cobra - 585

Still many improvements to be made

class P
    def main
        i='I see '
        f='s of '
        w=' I think to myself\nWhat a wonderful world'
        a='\nAnd[w]'
        t=' the '
        s=' sayin\', "'
        print "[i]trees of green, red roses, too,\n[i]them bloom, for me and you[a].\n\n[i]skie[f]blue, and cloud[f]white,\nThe bright blessed day,[t]dark sacred night[a].\n\nThe colors of[t]rainbow, so pretty in[t]sky,\n are also on[t]face[f]people going by.\n[i]friends shaking hands,[s]How do you do?\"\nThey're really[s]I love you.\"\n\nI hear babies cryin'. I watch them grow.\nThey'll learn much more than I'll ever know\nAnd[w]\n\nYes,[w]"


Predictable unpredictability Ever programmer knows, that programs need to be predictable. Any code that is not predictable will do something undefined and therefore most likely crash or worse. But when I tried to figure out what Java's lazySet() method does, I came up with the idea

Is it possible to write a program that is unpredictable, yet works fine and does something useful/interesting?

So that will be your task. Do not avoid chaos, but utilize it. Whether you use the actual lazySet, thread timing, random or uninitialized variables is up to you. The following rules apply:

The code-path must be unpredictable. That is: if I would debug it, the program would take a "random" path each time.
The program must do something useful/interesting and handle all possible (unpredictable) states somehow. No crashes! (Core dumps are neither useful nor interesting!)
You are not allowed to check something in a loop till it has the desired value. You must work with whatever is stored in there and do something with it.
You can use any language, except those specifically optimized for this contest.

This is a creative question so the one with the most votes wins. Please note that programs doing common stuff like gambling, printing random numbers or generating RPG loot are too well-known to be considered interesting. Please surprise us.

Bonus points should be given for:

The creativity of the choice/design of unpredictability (Math.random isn't that creative).
The creativity in management of unpredictability.
Everything genius. ;)

Ruby

This works only on Windows.

if aTerribleErrorOccurredAndWeNeedToKillTheScriptNow
    c = ($$ % 94 + 33).chr
    puts "#{c * 50}\n#{c + "KILLING SCRIPT".center(48) + c}\n#{c * 50}"
    `taskkill /PID #{$$} /F`
end

The process ID, $$, is unpredictable. However, this will always kill the currently running script, while printing an error message bordered by an unpredictable character like this:

##################################################
#                 KILLING SCRIPT                 #
##################################################

Of course, exit or quit do the same thing, but this one kills Ruby forcefully with the OS! And it also bypasses at_exit handlers.


English numeral calculator Challenge

Write a calculator that takes input in a verbal form (as one might speak an equation) and also outputs in a verbal form (as one might speak a number).

Rules

The calculator should be able to:

add, subtract, multiply and divide
handle operands between negative one million and one million
handle outputs between negative one billion and one billion
handle decimal points in its input and place them correctly in its output
handle decimal output to the hundredths place, rounding where needed

All operations yielding fractional results should round to the nearest hundredths place (identically to the output formatting).

Report with output "E" (for error) when input would cause the program to fail due to being incorrectly formatted or dividing by 0; basically, the program shouldn't crash on bad input, because that would be a lousy calculator.

The calculator is allowed, but not required to report errors when operands or output escape their bounds.  This is meant to simplify the problem, but if you disagree with me, feel free to make a calculator capable of correctly handling greater operands and outputs without reporting errors.

Output "E" in the event that an operand for an operation exceeds the bounds defined for operands.

Output "E" in the event that the output exceeds the bounds described for outputs

How the program handles case-sensitivity and whitespace are left up to the golfer, as is the choice of British or American English.1

Programs that bypass the implementation of the calculator by using a language or library that has already implemented the functionality described above will be ineligible for victory.

Winner

The program with the lowest number of characters wins.

Examples

Input: two plus two
Output: four

Input: twenty-one point five minus one point five
Output: twenty

Input: one minus two
Output: negative one

Input: five times five
Output: twenty-five

Input: twenty-five divided by five
Output: five

Input: two plus two minus five times five divided by negative zero point five
Output: ten

Input one million times one thousand
Output: one billion

Input: one million times one thousand plus one
Output: E

Input: two million plus one million
Output: E

Input: one million plus one million plus one million
Output: E

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

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

Javascript 509 + 22 = 531

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

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

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

input: two plus two
output: four

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

input: one minus two
output: negative one

input: five times five
output: twenty-five

input: twenty-five divided by five
output: five

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

input: one million times one thousand
output: one billion

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

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

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

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

Well, there might be a lot to enhance though.


Repetend length in 1/n This problem is based on non-terminating, repeating decimal points.
Let \$n\$ be any positive integer \$(n > 1 \text{ and } n < 10000)\$, say \$7\$. Then, \$1/n = 1/7 = 0.142857142857142857...\$
We see a pattern like, 0. 142857 142857 142857 ...
In this, the 142857 part is always repeating, which has length of \$6\$. Or, if \$n = 11\$, then \$1/n = 1/11 = 0.0909090909090909...\$
Here the length of the pattern is 2. So, here goes the problem!
Task
Given a positive integer \$n\$, \$(n > 1 \text{ and } n < 10000)\$, find the length of pattern in \$1/n\$, if it's repeating. Otherwise, return any non-positive integer (e.g., cases: \$1/5, 1/94, 1/22\$).
Note that, the pattern should start just after the decimal point. Hint: \$1/22 = 0.04545454545454545454545\$.
Sample I/O

5 -> -1
13 -> 6
21 -> 6
27 -> 3
33 -> 2
37 -> 3
94 -> -1
22 -> -1
69 -> 22
197 -> 98
65 -> -1
\$1/9979\$
\$1/9967\$

This is a code-golf, so the fewest bytes will win!

Jelly, 6 bytes
R⁵*%i1

Try it online!
Basically compute 10**[1..n] % n and get the 1-based index of 1.


When was the last time the date was divisible by n? A date can be represented by an unsigned integer as such: YYYYMMDD. What you need to do, is write the shortest program or function that figures out the most recent date whose number was divisible by a given number n (including today's date) and then returns that date in the format showed above. If there has never been a date (between 00000101 and today inclusive) divisible by the given integer, you should return -1.

Examples

Current Date     Input     Output

30 July, 2014      4       20140728
30 July, 2014      7       20140729
28 July, 2014      4       20140728
28 July, 2014      7       20140722
28 July,    5    90000     -1

Input

You can read from STDIN or take a function argument or even expect the input to be stored in a variable. The input will be an unsigned integer.

Output

Write to STDOUT or return (or save in a variable) the integer representing the date in the format YYYYMMDD.

Restrictions

You may use any standard library your language offers. Standard loopholes apply.

Winning conditions

This is a code-golf, so smallest program (in bytes) wins. In case of a tie, the answer with the most votes wins.

Mathematica, 93 60 bytes

For[i=0,(r=DatePlus@i--~FromDigits~100)>0&&!n∣r,];r~Max~-1

Expects the input to be stored in n.

Note that the vertical line ∣ is the unicode character for "divides", which I've counted as 3 bytes (UTF-8).

Edit: Found a neat trick to avoid the bloated DateString and format specification :).

Edit: Totally forgot about the -1 requirement. Fixed now.

Here is an explanation

For[i=0,            i--                        ,];         (* i is the number of days AFTER
                                                              today. Hence, we decrement
                                                              it. *)
For[i=0,   DatePlus@i--                        ,];         (* If no reference date is
                                                              provided, DatePlus will add
                                                              the given number of days to
                                                              today's date. The result is a
                                                              list of 3 integers, luckily
                                                              in order {year,month,day} *)
For[i=0,   DatePlus@i--~FromDigits~100         ,];         (* Interpret these as the digits
                                                              of a base 100 number. The
                                                              beauty is that FromDigits
                                                              doesn't care about digits
                                                              greater than the base and
                                                              just carries them over. *)
For[i=0,(r=DatePlus@i--~FromDigits~100)        ,];         (* Store the number in r. *)
For[i=0,(r=DatePlus@i--~FromDigits~100)>0      ,];         (* Make sure it's positive. *)
For[i=0,(r=DatePlus@i--~FromDigits~100)>0&&!n|r,];         (* And keep going while n does
                                                              not divide r. *)
For[i=0,(r=DatePlus@i--~FromDigits~100)>0&&!n|r,];r~Max~-1 (* Clamp result to -1. *)

Note that I've used | instead of ∣ in the explanation, because the Unicode one messes with monospacing.


Repdigit Base Finding A repdigit is a natural number that can be written solely by repeating the same digit. For example, 777 is a repdigit, since it's solely composed of the digit 7 repeated three times.
This isn't limited to simply decimal (base 10) numbers, however:

Every Mersenne number (of the form Mn = 2n-1) is a repdigit when written in binary (base 2).
Every number is trivially a repdigit when written in unary (base 1).
Every number n can also trivially be written as the repdigit 11 in base n-1 (for example, 17 when written in hexadecimal (base 16) is 11, and 3 when written in binary (base 2) is also 11).

The challenge here is to find other bases where the input number may be a repdigit.
Input
A positive integer x > 3, in any convenient format.
Output
A positive integer b with (x-1) > b > 1 where the representation of x in base b is a repdigit.

If no such b exists, output 0 or some falsey value.
If multiple such b exist, you can output any or all of them.

Rules

The (x-1) > b > 1 restriction is to prevent the trivial conversions to unary or the "subtract one" base. The output number can be written in unary or any convenient base, but the base itself must not be one of the trivial conversions.
Input/output can be via any suitable method.
Standard loophole restrictions apply.

Examples
In --> Out
11 --> 0            (or other falsey value)
23 --> 0            (or other falsey value)
55 --> 10           (since 55 is 55 in base 10)
90 --> 14           (since 90 is 66 in base 14 ... 17, 29, 44 also allowed)
91 --> 9            (since 91 is 111 in base 9 ... 12 also allowed)

Jelly, 11 9 bytes

bRI¬P€TḊṖ

Returns a list of bases, which is empty (falsy) if there is none. Try it online!

How it works

bRI¬P€TḊṖ  Main link. Argument: x (number)

 R         Range; yield [1, ..., x].
b          Base; convert x to base n, for each n in the range.
  I        Compute the increment (differences of successive values) of each array
           of base-n digits. This yields only 0's for a repdigit.
   ¬       Apply logical NOT to each increment.
    P€     Compute the product of all lists of increments.
      T    Get the indices of all truthy products.
       Ḋ   Discard the first index (1).
        Ṗ  Discard the last index (x - 1).


Add a egaugnaL to a polyglot This is an answer-chaining question, which means that all answers are affected by those before them.
The task
The n-th answer to this question must run in all languages that are present in answers before it. They need not run in order, but must print the name of the language currently running, reversed.
Additional rules

A language cannot be used twice.
Your program must run without errors. Using errors to log the language name is not permitted, but you are allowed to use errors to determine language.
Each answer must be no more than 30% or 40 bytes (whichever is larger) longer than the previous answer. If the percentage is not an integer, it is rounded down.
Your added language must be a free implementation language.
Any interpreter for a language is allowed.
If you can link to reproducible results, please do so.
The name of the language being reversed is Case-insensitive, so '3nohtyp' is valid for Python 3.0
You may not put 2 answers in a row.
If your language does not support strings, print the letters as numbers, following this pattern: "A" = 0, "B" = 1, "C" = 2...
In the case of a language not supporting strings and having non-letter characters in its name, print -1 instead of the non-letter character. Please show verification that the language does not support strings.

Victory condition
If this question goes for 20 days without an answer, the second to last answer wins.
Answer format

4. CoffeeScript, 20 bytes
(program goes here)

This program prints nohtyp in Python 3, and tpircsavaj in JavaScript.
(If you wish to explain how you did it, do so here)

3. ><>, 106 bytes
void main(){import std.stdio;"D".write;}
/*                        ;ooo"><>"
1j U8=XPC#18M<<}9F ,+;q,+;
*/

Try it online!
This program prints D in D, emmoS in Somme, and ><> in ><>.
Next answer cannot exceed 146 bytes (106 + 40).
Explanation
;ooo"><>" prints "><>" in ><> (which is a palindrome), then exits.


Output the Euler Numbers Given a non-negative integer \$n ,\$ output the \$n^{\text{th}}\$ Euler number (OEIS A122045).
All odd-indexed Euler numbers are \$0 .\$ The even-indexed Euler numbers can be computed with the following formula (\$i \equiv \sqrt{-1}\$ refers to the imaginary unit):
$$
E_{2n}
= i
\sum_{k=1}^{2n+1}{
  \sum_{j=0}^{k}{
    \left(\begin{array}{c}k \\ j \end{array}\right)
    \frac{{\left(-1\right)}^{j} {\left(k-2j\right)}^{2n+1}}{2^k i^k k}
  }
}
\,.
$$
Rules

\$n\$ will be a non-negative integer such that the \$n^{\text{th}}\$ Euler number is within the representable range of integers for your language.

Test Cases
0 -> 1
1 -> 0
2 -> -1
3 -> 0
6 -> -61
10 -> -50521
20 -> 370371188237525


Win a KQ vs K endgame Win a K vs KQ endgame
Summary
The goal of this challenge is to create a program or function which will win a Chess game with a King and Queen against a lone King. The user will specify three squares, representing the locations of the computer's King, the computer's Queen, and the user's King. The computer will then a output a move which will eventually lead to checkmate.
Input/Output
The program or function will first take as input three squares, representing the locations of the computer's King, the computer's Queen, and the user's King (not necessarily in that order). It can be assumed that the input is a legal position.
Parsing input is not the point of this challenge, so all reasonable forms of input/output are allowed, including but not limited to

Strings with algebraic chess notation such as "Ke4" or "Qf6"

Triples representing pieces and coordinates such as ('K', 0, 2)

After three squares are taken as input, the computer outputs a single legal move. Behaviour on invalid input is undefined.
Requirements
This procedure must terminate using your program or function:

User sets up a legal KQ vs K position on a physical chessboard.

User inputs the board position. The computer outputs a legal move. If the move is a checkmate, STOP. If the move is a stalemate or allows the computer's queen to be captured, your solution is invalid.

User makes the computer's move on the physical board.

User makes a legal move for the lone king on the physical board.

User goes to step 2 and repeats.

In other words, the computer must eventually win by checkmate, through repeatedly using your program or function.
Furthermore, from any legal starting position the checkmate must occur in 50 or fewer moves by the computer, i.e. the above procedure will be repeated no more than 50 times. An explanation as to why your solution will always win in 50 moves or fewer is appreciated.
(Of course, a physical chessboard is in no way necessary to test the code; I only mentioned it to help visualize the procedure. The chessboard could just as well be visualized in the user's head.)
Possible test cases
The squares are given in the order: computer's Queen, computer's King, user's King

c2, h8, a1 (must avoid stalemate)
a1, a2, a8
a8, a1, e5

Rules

The checkmate must occur in 50 or fewer moves by the computer, but it does not need to be as fast as possible.
Chess libraries are not permitted.
Shortest program in each language (in bytes) wins.

Python 3, 1054 bytes

def d(kx,ky,x,y):return abs(x-kx)<2>abs(y-ky)
def l(qx,qy,kx,ky,x,y):
 if x==qx:return x!=kx or ky<min(y,qy)or max(y,qy)<ky
 o=kx<min(x,qx)or max(x,qx)<kx
 if y==qy:return o or y!=ky
 if x-y==qx-qy:return o or x-y!=kx-ky
 return x+y==qx+qy and(o or x+y!=kx+ky)
def f(c,x,y):c[x][y]=1;[f(c,u,v)for v in range(max(y-1,0),min(y+2,8))for u in range(max(x-1,0),min(x+2,8))if c[u][v]<1]
def s(qx,qy,kx,ky,hx,hy):c=[[d(kx,ky,u,v)or l(qx,qy,kx,ky,u,v)for v in range(8)]for u in range(8)];t=sum(map(sum,c));f(c,hx,hy);t=sum(map(sum,c))-t;return t if t-1else 64
def m(qx,qy,kx,ky,hx,hy):a=[[s(x,y,kx,ky,hx,hy)if(x+y-7and x-y)and d(hx,hy,x,y)<=d(kx,ky,x,y)and l(qx,qy,kx,ky,x,y)and l(qx,qy,hx,hy,x,y)else 64for y in range(8)]for x in range(8)];b=list(map(min,a));c=min(b);e=b.index(c);return(0,e,a[e].index(c))if c<a[qx][qy]else min(((x-hx)**2*2+(y-hy)**2*2+(x-3)*(x-4)+(y-3)*(y-4),x,y)for x in range(max(kx-1,0),min(kx+2,8))for y in range(max(ky-1,0),min(ky+2,8))if(x!=kx or y!=ky)and(x!=qx or y!=qy)>d(hx,hy,x,y)and(x-7and x or y-7and y)and s(qx,qy,x,y,hx,hy)<64)

Try it online! Link includes footer which starts from the given position (input as a string of three squares in the order computer Queen, computer King, human King, without separators) and plays random moves on the human's behalf until the computer checkmates it. I've never seen it take anywhere near 50 moves but I don't know how to prove that it won't. Not completely golfed for the sake of my sanity. Explanation:
def d(kx,ky,x,y):return abs(x-kx)<2>abs(y-ky)

Determines whether a square is under attack from a King, e.g. to prevent the Queen from giving itself away.
def l(qx,qy,kx,ky,x,y):
 if x==qx:return x!=kx or ky<min(y,qy)or max(y,qy)<ky
 o=kx<min(x,qx)or max(x,qx)<kx
 if y==qy:return o or y!=ky
 if x-y==qx-qy:return o or x-y!=kx-ky
 return x+y==qx+qy and(o or x+y!=kx+ky)

Determines whether the Queen is threatening the square that the human's King might want to move to.
def f(c,x,y):c[x][y]=1;[f(c,u,v)for v in range(max(y-1,0),min(y+2,8))for u in range(max(x-1,0),min(x+2,8))if c[u][v]<1]

Helper recursive function to flood fill the squares that the human's King can reach.
def s(qx,qy,kx,ky,hx,hy):c=[[d(kx,ky,u,v)or l(qx,qy,kx,ky,u,v)for v in range(8)]for u in range(8)];t=sum(map(sum,c));f(c,hx,hy);t=sum(map(sum,c))-t;return t if t-1else 64

Calculate the scope of the human's King. However, it returns 64 on stalemate, indicating that this is a bad move for the Queen to make.
def m(qx,qy,kx,ky,hx,hy):a=[[s(x,y,kx,ky,hx,hy)if(x+y-7and x-y)and d(hx,hy,x,y)<=d(kx,ky,x,y)and l(qx,qy,kx,ky,x,y)and l(qx,qy,hx,hy,x,y)else 64for y in range(8)]for x in range(8)];b=list(map(min,a));c=min(b);e=b.index(c);return(0,e,a[e].index(c))if c<a[qx][qy]else min(((x-hx)**2*2+(y-hy)**2*2+(x-3)*(x-4)+(y-3)*(y-4),x,y)for x in range(max(kx-1,0),min(kx+2,8))for y in range(max(ky-1,0),min(ky+2,8))if(x!=kx or y!=ky)and(x!=qx or y!=qy)>d(hx,hy,x,y)and(x-7and x or y-7and y)and s(qx,qy,x,y,hx,hy)<64)

The meat of the program, this actually computes the computer's move. The return value is a tuple of (Piece to move, desired X, desired Y) where the flag is 0 to move the Queen and all parameters and X and Y are 0-indexed. It first checks all of the Queen's available moves (except those that give it away or those to squares on the main diagonals, as the symmetry confuses it) to see whether it can reduce the scope of the human's King. If not, it tries to move its own King nearer the human's King, or failing that, nearer the middle of the board.


Generate antsy permutations Introduction

I defined the class of antsy permutations in an earlier challenge.
As a reminder, a permutation p of the numbers from 0 to r-1 is antsy, if for every entry p[i] except the first, there is some earlier entry p[i-k] such that p[i] == p[i-k] ± 1.
As a fun fact, I also stated that for r ≥ 1, there are exactly 2r-1 antsy permutations of length r.
This means that there is a one-to-one correspondence between the antsy permutations of length r and the binary vectors of length r-1.
In this challenge, your task is to implement such a correspondence.

The task

Your task is to write a program or function that takes in a binary vector of length 1 ≤ n ≤ 99, and outputs an antsy permutation of length n + 1.
The permutation can be either 0-based of 1-based (but this must be consistent), and the input and output can be in any reasonable format.
Furthermore, different inputs must always give different outputs; other than that, you are free to return whichever antsy permutation you want.

The lowest byte count wins.

Example

The (0-based) antsy permutations of length 4 are

0 1 2 3
1 0 2 3
1 2 0 3
1 2 3 0
2 1 0 3
2 1 3 0
2 3 1 0
3 2 1 0

and your program should return one of them for each of the eight bit vectors of length 3:

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

Jelly, 12 11 10 bytes

ḟẋLṭ+
0;ç/

Try it online! or generate all permutations of length 4.

How it works

0;ç/   Main link. Argument: B (bit array)

0;     Prepend a 0 to B.
  ç/   Reduce [0] + B by the helper link.

ḟẋLṭ+  Helper link. Left argument: A (array or 0). Right argument: b (bit)

 ẋ     Repeat A b times, yielding A or [].
ḟ      Filter false; remove the elements of A or [] from A.
  L    Get the length of the resulting array.
       This yield len(A) if b = 0 and 0 if b = 1.
    +  Add b to all elements of A.
   ṭ   Tack; append the result to the left to the result to the right.


Tips for golfing in Julia What general tips do you have for golfing in Julia? I'm looking for ideas that can be applied to code golf problems in general that are at least somewhat specific to Julia (e.g. "remove comments" is not an answer).

NOTE: The below are correct as of Julia 1.4.1
A few tricks to save a few characters

Overload operators with frequently used binary functions. For example, if you need to do a lot of integer divisions, and no need for inverse division, use \ =div, and you can then type a\b instead of div(a,b). Note the space - this is necessary to avoid it parsing as a "=" operator. Also note that, if overloaded at REPL prompt level, use (\)=Base.(\) or \ =Base. \ to reset it. NOTE: some functions have existing UTF-8 operators pre-defined, such as ÷ for div, as noted by Alex A.
Use ^ with strings for conditional output. That is, rather than a>0?"Hi":"", use "Hi"^(a>0) to save one byte, or for boolean a, use "Hi"^a to save three bytes.
(sometimes) Store small fixed-size vectors as separate variables. For instance, rather than a=split("Hi there"," "), you may be able to avoid a[1] and a[2] by using a,b=split("Hi there"," "), which can be referenced as a and b, saving three bytes for each use, at the cost of just two extra characters at assignment. Obviously, do not do this if you can work with vector operations.
Don't use isempty for Arrays, Tuples, or Strings - instead, use ==[] for arrays and ==() for tuples; similarly, for the negative, use !=[] and !=(). For strings, use =="" for empty, but use >"" for not-empty, as "" is lexicographically before any other string and it saves one byte.
Use the right short-circuit boolean operator in place of "if". It might be a bit less Julia-specific, but it is worth bearing in mind. x<=1&&"Hi" can be written as x>1||"Hi", saving a character (so long as the return of the boolean isn't important).
Don't use contains to check presence of character in string - if you're restricted to the basic ASCII, use in('^',s) rather than contains(s,"^"). If you can use other characters, you can save a bit more with '^'∈s, but note that ∈ is 3 bytes in UTF-8.
Looking for minimum/maximum values in an array? Don't use minimum or maximum - rather than using minimum(x) or maximum(x), use min(x...) or max(x...), to shave one character off your code. Alternatively, if you know all elements of x will be non-negative, use minabs(x) or maxabs(x)
Where possible and permitted by the challenge, use an actual newline instead of \n - note that this will make your code harder to read, and may mean that you need to provide an "ungolfed" version to make it possible for people to actually understand it.
Put options after the regex string - if you want to have a regex string in multiline mode, for example, don't type r"(?m)match^ this", type r"match^ this"m, saving three characters.
Where possible, use array concatenation instead of push!, unshift!, append!, or prepend! - for normal arrays, this can be done easily. For arrays of type Any with array elements, you will need the type Any, as in Any[[1,2]]. At one stage, curly braces could be used as an alternate notation ({[1,2]}), but this has been discontinued.
Don't use collect to convert a string into a char array - instead of collect(A), use [A...], which will do the same thing and save 4 bytes.
Need a number converted to a string? Use "$(s[i])" or dec(s[i]) for expressions or multi-character variables, and "$i" for single-character variables.
Use union or ∪ instead of unique - union(s) will do the same thing as unique(s), and save a byte in the process. If you can use non-ASCII characters, then ∪(s) will do the same thing, and ∪ only costs 3 bytes instead of the 5 bytes in union. In some circumstances, for single-character variables, you can save another byte using s∪s (thanks, MarcMush, for s∪s).
Use array indexing to get the size of an array or string - when you use end within array indexing, it automatically gets converted to the length of the array/string. This can be handy when you want to collect the length while doing certain operations. For example, if you need the length of A and the middle value, you might write A[(k=end)÷2]. This can also work in multiple dimensions, and for index iterators - A[(k=1:end;)] will give you an iterator for k=1:length(A), which can be handy when you also want to use A. Note that the assignment must occur in brackets, with a semicolon (such as (k=end;)) if no operation is done outside the brackets. (thanks to MarcMush for identifying a workaround for keywords in array indexing)

Outdated tricks that worked at some point, but no longer do:

 Access first element of Array with [] - for arrays, the expression A[] is equivalent to A[1]. Note that this does not work for Strings if you wish to get the first character, or for Tuples. - A[] no longer works.

 Reverse 1-D arrays using flipud - reverse(x) is one byte longer than flipud(x) and will perform the same operation, so the latter is better. - flipud is no longer in Base.

 Use ?: instead of && or || for conditional assignment - that is, if you want to perform an assignment only on some condition, you can save one byte by writing cond?A=B:1 rather than cond&&(A=B), or cond?1:A=B rather than cond||(A=B). Note that the 1, here, is a dummy value. - the ?: notation now requires spaces around ? and :.


Validate 2Col syntax! As a couple of people may have noticed lately, I've largely abandoned development of Braingolf because it's boring and uninspired, and moved on to 2Col which is a little more interesting, and not designed to be a golfing language.

The defining feature of 2Col is that every line of code must be exactly 2 characters long, excluding the newline. This means that the length of a 2Col program can always be calculated as 3n-1 where n is the number of lines in the program.

So here's my challenge: Given 2Col code as a string, output truthy if it is valid 2Col code (Every line is exactly 2 characters and it conforms with the 3n-1 formula), and falsey otherwise.

Input

Input should be taken as a single string, or an array of characters.

Output

A truthy value if the input string is valid layout, and a falsey value otherwise.

Your code should be consistent in which truthy/falsey values it uses

Testcases

======
F!
$^
----
truthy
======

======
*8
+1
Sq
----
truthy
======

======
nop
xt
----
falsey
======

======
+1
+1
#^

----
falsey
======

======
<empty string>
----
falsey
======

======
ye
----
truthy
======

======
no<space>
----
falsey
======

======
test
----
falsey
======

======
puzzle
----
falsey
======

Scoring

This is code-golf so fewest bytes wins!

Brachylog (2), 4 bytes

ṇl₂ᵐ

Try it online!

Full program (because this is a decision-problem; Brachylog full programs output false. if there was an assertion failure, true. without one).

Explanation

ṇl₂ᵐ
ṇ     Split input into lines
   ᵐ  For each line:
 l₂     Assert that that line has length 2

Subscripts on l are one of Brachylog's newest features (although still older than the challenge), and this is a good challenge to use them on.


Fibonacci’s sexagesimals Leonardo da Pisano a.k.a Fibonacci was instrumental in bringing the Hindu-Arabic numeral system into Europe. Before that, mathematicians there worked in base sixty with Roman numerals.

For example, the square root of two might be approximated as: one and twenty-four parts of sixty and fifty-one parts of three-thousand-six-hundred, and written as: i xxiv li, with the scaling determined by context. At the time, “nothingness” was known (i.e. zero), but had no standard representation in this number system.

Had Fibonacci ignored these new-fangled decimal digits he encountered during his travels, he surely would have addressed the deficiencies in the current system. This improved system we'll call Fibonacci’s sexagesimals.

Your task is to write a program, function or code snippet which takes a floating point number in ASCII or binary format and outputs in base sixty Roman numerals. The input can be file, console, command line or function argument and output can be file or console, whichever is easiest.

The output can be upper or lower case, and must include these improvements:

use n or N to indicate null meaning a place has no value, i.e. “zero” (a problem with the system)
use e or E to indicate et corresponding to the sexagesimal point (another problem with the system)
use a middle dot · or an asterisk * to separate groups of Roman numerals (yet another problem with the system)

Assume the input will be floating point with mantissa not greater than lix·lix·lix·lix·lix. Fractions less than n·e·n·n·n·n·i can be ignored. So, provided the input has these restrictions, at most ten groups of Roman numerals with one e can be outputted.

Numbers less than i must have a leading n·e to ensure the context is clear.

Some examples: input → output

0 → n
1 → i
60 → i·n
0.1 → n·e·vi
3600 → i·n·n
10.5 → x·e·xxx
16777215 → i·xvii·xl·xx·xv
3.1415926536 → iii·e·viii·xxix·xliv·n·xlvii

The output must avoid unnecessary leading n· in the mantissa part, isolated e, or trailing ·n in the fractional part of the output. So for example, n·n·n·n·i, i·e, and i·e·n·n·n·n·n are incorrect outputs for an input of 1.

Differences of plus or minus n·e·n·n·n·n·i in the output are within tolerances and acceptable.

The input is any legal floating point in the language of your choice, so can include positive or negative exponents as long as the input doesn't fall outside the range specified above.

And finally, Roman numeral built-ins are allowed!

C – 584 bytes
Non-competing (obviously), but to serve as inspiration:
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
char*f(int z){static char r[8];char*l[]={"","I","II","III","IV","V","VI","VII","VIII","IX"},*h[]={"","X","XX","XXX","XL","L"};if(!z)return"N";sprintf(r,"%s%s",h[z/10],l[z%10]);return r;}int main(int c,char**v){char*s="";int i,j,z[10],k=60;long x;double d,y;y=modf(atof(v[1]),&d);x=d;for(i=4;i>=0;i--){z[i]=x%k;x/=k;}for(i=5;i<=9;i++){z[i]=(y*=k);y-=z[i];}for(i=0;!z[i]&&i<4;i++);for(;i<5;i++){printf("%s%s",s,f(z[i]));s="*";}for(j=9;!z[j]&&j>=i;j--);if(i<=j)printf("*E");for(;i<=j;i++)printf("*%s",f(z[i]));printf("\n");return 0;}

Save as fs.c, build with gcc -o fs fs.c -lm, and run as ./fs <arg>.
Test cases:
$ ./fs 0
N
$ ./fs 1
I
$ ./fs 60
I*N
$ ./fs 0.1
N*E*VI
$ ./fs 3600
I*N*N
$ ./fs 10.5
X*E*XXX
$ ./fs 16777215
I*XVII*XL*XX*XV
$ ./fs 3.1415926536
III*E*VIII*XXIX*XLIV*N*XLVII

Largest mantissa and fraction:
$ ./fs 777599999
LIX*LIX*LIX*LIX*LIX
$ ./fs 0.999999998713992
N*E*LIX*LIX*LIX*LIX*LIX

I'm using double as the working type, so the largest mantissa and fraction combined exceeds the native accuracy of that type. If I used long double instead it could handle it.


Underhanded launcher Your goal is to write a super-secret program which launches another (independent) program. You don't have to provide the payload in your answer, it can be any program name your program will launch.

However, the challenge is to keep this behavior a secret. Upon casual inspection of the code, it should be impossible or very hard to notice that your program actually executes a foreign program. Bonus if this "hidden feature", once discovered, can reasonably be explained away as an unintentional bug. This is why the code has to be as clear as possible, and everything should have an alibi for being there, otherwise someone inspecting your code might become suspicious.

Remember, this is not a code-golf, but an underhanded contest.

Your code has to be clear and readable.
The causes of the change have to be hidden. Even if discovered, they should look more like bugs than malice.

You should provide an explanation, best in spoiler.

   like this

The winner will be selected as the highest voted answer not sooner than 10 days after the first valid answer. Yes, I know it's subjective, but this is the only criteria adequate for underhanded contests.

Voters should value the standard "underhanded" qualities, like how clear the code is and how well hidden the reason is.

I made this competition for compiled languages, but you can also use interpreted languages if you find two different notable interpreters for it.

Tcl

Simple.

proc main {} {
    set fd [open filenames.txt]
    while {[gets $fd line] ne ""} {
        set other [open $line w]
        puts $other [clock format [clock seconds]]
    }
}
main

   Ilmari Karonen is right:
 If you supply a filename with a | as first character, it will treat the rest as command. IIRC for Perl it has to be at the end.


Lorem Ipsum Generator Lorem Ipsum is placeholder text used when preparing layout without wanted to have content already filled.

One of its key features over using some arbitrary text is that it is nonsense.
It isn't even valid latin (though it is close).
This prevents anyone being shown the layout from becoming distracted reading the text.

The other key feature is that it looks like real language.
The words are the right length, and the characters occur with the right distributions.

A problem is that the Lorem Ipsum is not necessarily good gobbldy-gook for all languages, or even for all subject matter.
We expect that the distribution of letters would be different in a novel, than in a scientific article.

Your task thus is to create a tool that when given an example of text, generate a lorum ipsum style gobbldy-gook that is a suitable imitation of the characteristics of that text.

The Task

Given an input in UTF8 text input-text, and a number x.
Output x characters of gobbldy-gook following the style of that text.

It may be assumed that words are separated using the space character in the input text.

You may take the input in any reasonable form (though it must be able to accept UTF-8). Eg reading from STDIN, reading from file, as a string passed to the function etc.
Similar for output.

Critria

Must not be real correct text in the language of input-text

In particular must contain no words with more than 3 characters from input-text.
This can be trivially avoided by using a hashset to ban all words from input-text from occurring in the output

Must look like it could have been real text from the language of input-text.

That is to say it must have the correct letter and word length distributions that is convincing to the eye of the reader.

It is up to the implementation if they take this to mean unigram, bigram, trigram or other statistics for the distributions.
The goal is for it to look right

Judging Texts

For purposes of judging please provide 256 characters of output based on each of the following public domain texts:

De Finibus, Book 1, sections 32–3, by Cicero.txt
Pride and Prejudice, By Jane Austen
Die Verwandlung, by Franz Kafka
The Magna Carta

gist with all files

Those that these are all UTF-8 encoded, and in particular Die Verwandlung, being in German uses many characters outside [a-zA-Z]

Python 3

import string
import random

with open('lorem.txt') as f:
    text = f.read()
number = eval(input("Input number: "))

dictionary = ''.join(ch for ch in text if ch not in set(string.punctuation)).split(" ")

chars = []

for word in dictionary:
    for char in word:
        chars.append(char)

chars = list(set(chars))

occurences = {}

for char in chars:
    occurences[char] = []

for word in dictionary:
   for idx, char in enumerate(word):
        try:
            occurences[char].append(word[idx+1])
        except IndexError:
            pass

lengths = [len(x) for x in dictionary]

result = ""

for _ in range(number):
    length = random.choice(lengths)
    word = random.choice(chars)
    for _ in range(length):
        try:
            word += random.choice(occurences[word[-1]])
        except IndexError:
            break
    result += word + " "

print(result)

Takes text input through a file named lorem.txt and number of words through STDIN.

Samples:

De Finibus:

  bolute moresu xisi libospssev lolu ute tamqump Sercolimo mnci iaerue unt xptemp ptur xiui mumnsc ner citerum hiositius fun Set llu hibol etet mpesi amitap voserata mol iumol ospe pte ell asequmut

Die Verwandlung:

  Frehwauchmi «
      vo ineic venzundenwasender geitende «
      darenenserttem Semint estt Scklode
      Zur
      g ZenÂ»e Orer urd cher
      s
      Bet
      kun renaunn

Pride and Prejudice:

  paime k
      hothenoc 5
      “ 230
      erth ZZWedomincab Mrevoueim Vifedrctogei Come Kidi yol qul
      “Thant Kie Rag 41
      mf vate 12
      Eled 8
      Dathed 1
      mb Bed
      “Y merie xto zasorl h’sh ghasst Wha quce skeniat zan dishond
       othing
      hare hing din

And finally, the Magna Carta:

  wincand zisend
      s
       Pes CEFured indons fequ dindshay ranen Gofun
       OURore ibec 6248 Rofonestheasaven
      sul nthal
      232 rend
      matyont r
       uiconlicend
       ucriof 7 ashesevenye Gerd
       BEndrouse IIns jurig 20000 UREndit mandira 0000000000s
      a
      wic 47 Enccet

It's not my best work.

All I'm doing here is some simple Markov chain recreation of the original text, with word lengths taken from a list of all lengths in the given text.

I sort of hoped for better results, but oh well.


9 Deaths of the Ninja Inspired by this conversation in chat.
Your goal in this challenge is to emulate a ninja and count how many deaths he has left.
Specs
You ninja starts out with 9 deaths left. He also gets an integral starting health as an input.
Then, he takes as input a list of events in his life that alter his health. These can be negative, positive, or zero integers.
At any point, if his health reaches at or below zero, he loses a life and his health goes back to the starting health.
Your program should report the number of deaths he has left. If he has zero or less left, you should output dead instead.
This is code-golf, so shortest code in bytes wins!
Test Cases
3, [] -> 9
100, [-20, 5, -50, 15, -30, -30, 10] -> 8
10, [-10, -10, -10, -10] -> 5
10, [-10, -10, -10, -10, -10, -10, -10, -10, -10] -> dead
0, [] -> dead
0, [1] -> dead
100, [10, -100] -> 9

Jelly, 30 28 26 bytes

»0o⁴+
;@ñ\<1S_9«0N“dead”×?

Try it online!

How it works

;@ñ\<1S_9«0N“dead”×?  Main link. Input: e (events), h (initial health)

;@                    Prepend h to e.
  ñ\                  Reduce the resulting array by the next, dyadic link.
                      This returns the array of intermediate results.
    <1                Check each intermediate value for non-positivity.
      S               Sum. This calculates the number of event deaths.
       _9             Subtract 9 from the result.
         «0           Take the minimum of the result and 0. This yields 0 if no
                      lives are left, the negated amount of lives otherwise.
                   ?  Conditional:
                  ×     If the product of the minimum and h is non-zero:
           N              Return the negated minimum.
            “dead”      Else, return "dead".

»0o⁴+                 Dyadic helper link. Arguments: x, y

»0                    Take the maximum of x and 0.
                      This yields x if x > 0 and 0 otherwise.
  o⁴                  Take the logical OR of the result and the second input (h).
    +                 Take the sum of the result and y.


De-interleave log lines You've inherited a server that runs several apps which all output to the same log.
Your task is to de-interleave the lines of the log file by source. Fortunately, each line begins with a tag that indicates which app it is from.
Logs
Each line will look something like this:
[app_name] Something horrible happened!

App tags are always between square brackets and will contain only alphanumeric characters and underscores.
All lines will have an app tag at the beginning. There will not be preceding whitespace or any other characters.
There will always be at least one space after the app tag
App tags are nonempty
There may be other square brackets later on any given line.
There may or may not be a message after the tag
The log may be empty
There is no limit to how many unique app tags will be present in the file.

Example
An entire log might look like this:
[weather] Current temp: 83F
[barkeep] Fish enters bar
[barkeep] Fish orders beer
[stockmarket] PI +3.14
[barkeep] Fish leaves bar
[weather] 40% chance of rain detected

Which should output three different logs:
[weather] Current temp: 83F
[weather] 40% chance of rain detected

[barkeep] Fish enters bar
[barkeep] Fish orders beer
[barkeep] Fish leaves bar

[stockmarket] PI +3.14

You are not given the names of the app tags ahead of time. You must determine them only by analyzing the log file.
Rules and Scoring

This is code-golf, so shortest code wins.
Standard rules and loopholes apply
Use any convenient IO format, provided that each input line is represented as a string, not a pre-parsed tag + message. Non-exhaustive list of allowed outputs:

Several files named after each tag
Several lists of strings
One concatenated list of strings containing lines grouped by tag with or without a separator (the separator must not begin with a tag)
Same as above, but to stdout or a file.

The order in which separated logs are output is irrelevant, however the log lines within each group must preserve the order they were found in the original file

Bash, 4 11 bytes
Added 7 bytes to fix a bug kindly pointed out by Shaggy.

sort -sk1,1

Try it online!
Performs a stable sort (the s command line argument) based on the first field (k1,1) separated by whitespace.


Transferring the DNA of bacteria from generations Introduction

Scientists have recently found a new type of bacteria that replicates in odd ways. To reproduce, two bacteria each split into 3 (for a total of 6) and pairs combine (resulting in 3 bacteria, two parents, one child). However, the bacteria can only split if it has a partner. For example, 2 bacteria split and combine into 3, 3 into 4, 4 into 6, etc. Additionally, when a bacteria splits, only one of the daughter cells combines with the other parent cell's daughter cells, and vice versa. In other words, if bacteria A and B split, the daughter cells will combine to be AA, AB, and BB.

The Challenge

Your challenge is to make a program that accepts or generates 4 bacteria's DNA, each with a strand in a 10-bit Quaternary format. An example DNA strand could be 0123302012. When two daughter bacteria combine, the DNA is merged in a punnet-square style (the DNA can be merged in every pair or only the AB pair, your choice). Meaning that 0 is the recessive trait, 1 is the mixed trait, and 2 is the dominant trait. However, when there is a 3, it is a mutated trait (more on this later). Starting with the 4 bacteria, have your program run 20 trials (4 splitting into 6 would be the first trial). Once it is done, have the program output through STDOUT (or equivalent) each cell's DNA on a seperate line, but only from the cells generated from the 20th trial.

Key Features

Each trial must calculate the new number of cells and each new cell's DNA (see below).
The program must output each 20th-trial cell's DNA (The 4046 new bacteria) each on a seperate line in STDOUT (or equivalent).
The bacteria must each replicate in the method stated above. (A and B split into AA, AB, and BB).

How the DNA is Passed on

The DNA is passed from the parents to child in a punnet-square style where:

0 is a recessive trait (rr).
1 is a mixed trait (Rr).
2 is a dominant trait (RR).

If one of the traits is a 3 (a mutation), the ending trait is decided randomly, but if both are 3,the ending trait is a 3. Parents can be decided randomly or in order (A & B, C & D, etc).

Example:

    |   DNA A    |   DNA B    | DNA C (Child) |
    | 0123311200 | 1203123213 |  0113012203   |

Scoring

This is code golf, so shortest character count wins! For legibility, please include a version that separates the code onto multiple lines, if possible. If the challenge is not explained well or you have suggestions, post a comment!

Here is an example program (in java) that successfully completes the challenge: Ideone Link.

Haskell -- 349

import Control.Monad
import System.Random
import Data.List
a=[0,1,2,3,3,1,1,2,0,0]
b=[a,a,a,a]
f 3 _=randomRIO(0,3)
f _ 3=randomRIO(0,3)
f x y=return$div(x+y)2
z::[Integer]->[Integer]->IO[Integer]
z x y=zipWithM f x y
c=filter(\x->length x==2).subsequences
r=sequence.map(\x->z(x!!0)(x!!1)).c
y=foldr(<=<)return.replicate 20
main=y r b>>=mapM_ print

Try it online with nicer looking source code: http://ideone.com/9FUMLd

The online example does only till 2 instead of 20 because of ideone's time limit.


Smallest unused number sharing a factor This is a pretty run of the mill question.  I will define a sequence and you golf some code to output a entry given a index.

The first item in the sequence is 2.
The nth item in the sequence is the smallest positive integer other than n and 1 sharing at least one factor with n (other than 1) that has not already appeared in the list.

Test cases

Here are the first 25 items in the sequence:

1  2
2  4
3  6
4  8
5  10
6  3
7  14
8  12
9  15
10 5
11 22
12 9
13 26
14 7
15 18
16 20
17 34
18 16
19 38
20 24
21 27
22 11
23 46
24 21
25 30

Related (offset by one) OEIS

Jelly, 19 bytes

R»2ɓ²Rg⁸>1Tḟ⁸ḟḢṭµ/Ṫ

Try it online!


Fraction to exact decimal Write a program or function that given two integers a, b outputs a string containing a decimal number representing the fraction a/b exactly.

If a/b is integer, simply output the value, without a decimal dot or leading zeroes:

123562375921304812375087183597 / 2777 -> 44494913907563850333124661
81 / 3 -> 27
-6 / 2 -> -3

If a/b is not integer but has a finite representation in base 10, output the value without leading or trailing zeroes (except a single zero before the dot):

1 / 2 -> 0.5
3289323463 / -250000000 -> -13.157293852

Finally, if and only if (so no 0.999...) a/b is not integer and does not have a finite representation, output the finite part followed by the repeating part in parenthesis. The repeating part must be as small as possible, and start as early as possible.

-1 / 3 -> -0.(3)
235 / 14 -> 16.7(857142)
123 / 321 -> 0.(38317757009345794392523364485981308411214953271028037)
355 / 113 -> 3.(1415929203539823008849557522123893805309734513274336283185840707964601769911504424778761061946902654867256637168)

Your program must work for all above examples in under 10 seconds on a modern desktop PC. Smallest program in bytes wins.

Python 2, 174 bytes

x,y=input()
a=abs(x)
b=abs(y)
r=a%b*10
L=[]
M=''
while~-(r in L):L+=r,;M+=str(r/b);r=r%b*10
i=L.index(r)
t=M[:i]+"(%s)"%M[i:]*(M[i:]>'0')
print"-%d."[x*y>=0:(t>'')+3]%(a/b)+t

I'm not quite convinced about the validity of this answer, but it's worked for the test cases above and other test cases I've thrown at it. It looks like a right mess though, so I'm sure there's plenty of room for golfing.

The initial setup takes absolute values of both arguments to ensure that we're dealing with nonnegative numbers (saving the sign calculation for later), and delegates the quotient part of the result to Python's arbitrary precision arithmetic. The fractional part is done with the grade-school division algorithm until we get a repeat in the remainder. We then look up when we last saw this repeat in order to get the period, and construct the string accordingly.

Note that the algorithm's actually quite slow due to the O(n) in operation, but it's fast enough for the examples.


Reducing a Python Script Does anyone have any suggestions as to how I could shorten this program?

_=map(ord,raw_input());_=[10if y==88else 0if y==45else 58-_[x-1]if y==47else y-48for x,y in enumerate(_)];t=0;exec('t+=sum(_[:2+(_[0]+_[1]>=10)]);_=_[2-(_[0]==10):];'*10);print t

Run it online

I'd like to write a bowling calculator. I'm fairly proficient in python so I chose that language.

The trick is that the input string is made up of frames not split by white-space and the spares, strikes, and misses are marked by /, X, and - respectively. (note that there are no 0 in the code, - is used instead)

Here is an example line X7/9-X-88/-6XXX81, this line would have a score of 167.

As you can see, most of my characters are spent on mapping these special characters to their actual bowl scores. I do this by taking their ord values and then replacing the X and - with 10 and 0 respectively. I then find the / rolls and set their value as ten minus the previous roll.

After this, I calculate the final game score by looping over 10 frames (the size of a line of bowling), chunking the line array based on if the  frame was a strike spare or normal roll, and then reducing the array going forward.

I feel like this is the best way to perform this challenge as a golf challenge, but I'm not sure if I'm reducing it enough.

1.

The portion 2+(_[0]+_[1]>=10) could be rewritten as 2+(_[0]+_[1]>9) to save two bytes. In a similar vein 2-(_[0]==10) can be rewritten as 2-(_[0]>9), since 10 is the only possible value greater than 9.

a=map(ord,raw_input());a=[10if y==88else 0if y==45else 58-a[x-1]if y==47else y-48for x,y in enumerate(a)]
t=0;exec('t+=sum(a[:2+(a[0]+a[1]>9)]);a=a[2-(a[0]>9):];'*10);print t

Try it online!

(I also renamed _ to a, because even though it's code-golf we don't have to make it unreadable)

2.

You can also use a dictionary instead of conditionals to saves some bytes.

a=raw_input();a=[{y:ord(y)-48,'X':10,'-':0,'/':58-ord(a[x-1])}[y]for x,y in enumerate(a)]
t=0;exec('t+=sum(a[:2+(a[0]+a[1]>9)]);a=a[2-(a[0]>9):];'*10);print t

Try it online!

3.

Don't enumerate.  enumerate tends to be too long for it's own good.  Here you want to get the last character, which can better be acheived with a zip.

a=raw_input();a=[{y:ord(y)-48,'X':10,'-':0,'/':58-ord(x)}[y]for x,y in zip('-'+a,a)]
t=0;exec('t+=sum(a[:2+(a[0]+a[1]>9)]);a=a[2-(a[0]>9):];'*10);print t

Try it online!

If you combine this with @user202729's two tips you get 149 bytes.

a=raw_input();a=[[10,0,58-ord(x),ord(y)-48]['X-/'.find(y)]for x,y in zip('-'+a,a)]
t=0;exec't+=sum(a[:2+(a[0]+a[1]>9)]);a=a[2-(a[0]>9):];'*10;print t

Try it online!

Here's another version that is also 149 bytes:

a=raw_input();a=[['-123456789X'.find(y),58-ord(x)][y=='/']for x,y in zip('-'+a,a)]
t=0;exec't+=sum(a[:2+(a[0]+a[1]>9)]);a=a[2-(a[0]>9):];'*10;print t

Try it online!


Determine if an integer is divisible by 3 Your goal is to determine if a number is divisible by 3 without using conditionals.
The input will be an unsigned 8 bit number from 0 to 255. Creativity encouraged!

You are ONLY allowed to use

Equality/Inequality (==, !=, >, <, >=, <=)
Arithmetic (+, -, x)
Logical Operators (! not, && and, ||  or)
Bitwise Operators (~ not, & and, | or, ^ xor, <<, >>, >>> arithmetic and logical left and right shifts)
Constants (it would be better if you kept these small)
Variable assignment

Output 0 if false, 1 if true.

Standard atomic code-golf rules apply. If you have any questions please leave them in the comments. Example methods here. A token is any of the above excluding constants and variables.

C - 2 tokens

int div3(int x) {
    return x * 0xAAAAAAAB <= x;
}

Seems to work up to 231-1.

Credits to zalgo("nhahtdh") for the multiplicative inverse idea.


How can I make this program smaller? I am trying my hand at writing super small programs. I wrote a simple "tree" display program for showing a graphical representation of a folder hierarchy. I have made it small in all the ways I can think of. I was just wondering if you guys had more creative ways to "minify" it further. Here is the small version as well as a human-readable version.

import os,os.path as p
def w(c,d,s):
    a=os.listdir(c);s=s+'|';i=0
    for f in a:
        print s+'--'+f;j=p.join(c,f);
        if p.isdir(j):w(j,d+1,s[:-i==len(a)-1]+'  '*(d+1));i=i+1
def t(c):print c;w(c,0,'')
t(p.curdir)

That's a total of 236 bytes

import os

def treeWrap(curdir,depth,pipeStr):
    files = os.listdir(curdir)
    pipeStr = pipeStr + '|'
    for f in files:
        print pipeStr + '--' + f
        if os.path.isdir(os.path.join(curdir,f)):
            dir = os.path.join(curdir,f)
            if files.index(f) == (len(files)-1):
                treeWrap(dir,depth+1,pipeStr[:-1] + '  '*(depth+1))
            else:
                treeWrap(dir,depth+1,pipeStr + '  '*(depth+1))

def tree(curdir):
    print curdir
    treeWrap(curdir,0,'')

tree(os.path.curdir)

Oh, in addition, does anyone know how I can use the unicode ├,└,─ in this program? Whenever I use them they appear as garbage in the console and the idle interpreter.

There is a bug with your minified version: s[:-0] gives you the empty string, not the complete string as you anticipate with s[:-i==len(a)-1]. To rectify this, you will need to either ignore preceding bars or calculate the a little more thoroughly. The shorter version would be to ignore preceding bars and not worry about passing spacing to further recursions. Since it permits the removal of several variables, I worked your code to do this

Your tree function is only called once, I removed it.

s=s+'|' and i=i+1 can be collapsed into s+='|' and i+=1

os.path as p can become p=os.path (Thanks James)

p.join(c,f) can become c+'/'+f (Thanks beary605)

New version:

import os,p=os.path
def w(c,d):
    for f in os.listdir(c):
        print '  '*(d+1)+'|--'+f;j=c+'/'+f
        if p.isdir(j): w(j,d+1)
z=p.curdir;print z;w(p.curdir,0)

If you really wanted to go crazy, you can make put this all on one line and get it down to 143 bytes (on linux)

import os,p=os.path
def w(c,d):
 for f in os.listdir(c):print'  '*(d+1)+'|--'+f;j=c+'/'+f;w(j,d+1)if p.isdir(j)else 0
z=p.curdir;print z;w(z,0)


Expanding Expressions Given an expression of one-letter variables ([a-z]), operators (*, +, &) and parenthesis, expand it using the following axioms:

a * b != b * a
a * b * c = (a * b) * c = a * (b * c)
a + b = b + a
a + b + c = (a + b) + c = a + (b + c)
a * (b + c) = a * b + a * c
a & b = b & a
a & (b + c) = a & b + a & c

   | Comm | Assoc | Dist
 * | NO   | YES   |
 + | YES  | YES   | *
 & | YES  | YES   | + *

The user will input an expression, the syntax of the input expression is called "input form". It has the following grammar:

inputform ::= expr
var ::= [a-z] // one lowercase alphabet
expr ::= add
       | add & expr
add ::= mult
      | mult + add
mult ::= prim
       | prim * mult
       | prim mult
prim ::= var
       | ( expr )

Before
That means, the order of operations is * + &, a + b * c & d + e = (a + (b * c)) & (d + e)
Furthermore, the operator * can be omitted:
    a b (c + d) = ab(c + d) = a * b * (c + d)

Whitespace is stripped out before parsing.

Examples:

(a + b) * (c + d)
= (a + b)(c + d)
= (a + b)c + (a + b)d
= ac + bc + ad + bd
(a & b)(c & d)
= ac & ad & bc & bd
(a & b) + (c & d)
= a + c & a + d & b + c & b + d
((a & b) + c)(d + e)
= ((a & b) + c)d + ((a & b) + c)e (I'm choosing the reduction order that is shortest, but you don't need to)
= ((a & b)d + cd) + ((a & b)e + ce)
= ((ad & bd) + cd) + ((ae & be) + ce)
= (ad + cd & bd + cd) + (ae + ce & be + ce)
= ad + cd + ae + ce & ad + cd + be + ce & bd + cd + ae + ce & bd + cd + be + ce

Due to commutativity, order of some terms do not matter.

Your program will read an expression in input form, and expand the expression fully, and output the expanded expression in input form, with one space separating operators, and no spaces for multiplication. (a + bc instead of a+b * c or a + b * c or a + b c)

The fully expanded form can be written without any parens, for example, a + b & a + c is fully expanded, because it has no parens, and a(b + c) is not.

Here is an example interactive session (notice the whitespaces in input)

$ expand
> a(b + (c&d))
ab + ac & ab + ad
> x y * (wz)
xywz
> x-y+1
Syntax error
> c(a +b
Syntax error

Ruby, 698 648
O=[A='&',B='+',C='*']
M='Syntax error'
def u(x)c=x.shift;(c.nil?)?S[0]=~/[a-z]/?(S.shift):S[0]=='('?(S.shift;o=u(O*1);S[0]==')'?(S.shift;o):abort(M)):abort(M):(o=[c];loop{o<<u(x*1);break if S[0]!=c;S.shift};o)end
def d(e,a,b)a!=e[0]?e:(i=e.index{|x|x[0]==b};(i.nil?)?e:y([b]+e[i][1..-1].map{|k|z=e*1;z[i]=k;z}))end
def y(e)e.map!{|x|(x.is_a?Array)?(y(x)):(x)};o=[e[0]];e[1..-1].map{|x|x[0]==o[0]?(o+=x[1..-1]):(o<<x)};d(d(d(o.size==2?o[1]:o,C,B),C,A),B,A)end
def j(e)(e.is_a?Array)?(e.map!{|x|j(x)};o=e.shift;e*(o=='*'?'':" #{o} ")):e;end
S=gets.gsub(/ /,'').gsub(/([a-z)])(?=[a-z(])/,'\1*\2').split(//)
k=u(O*1)
puts S!=["\n"]?(M):(j y k)

This solution consists of a basic recursive descent parser (method u) which builds an syntax tree which is then flattened (y) and transformed (d) according to the distribution axioms. The output (j) simply joins the operands again.
Unfortunately I broke the functionality when I later tried to reduce the code by restructuring. Nevertheless I think there is still some chance for golfing.


Lists and arrays, part by part In this challenge, you'll get four different but somewhat related tasks that must be solved in a specific manner. First, I'll explain the tasks, then follows an explanation of how you must solve it.

Your code should for all four tasks take two positive integers as input: n,m, where n<m. All tasks must be solved in the same language. The orientation of matrices are optional (n-by-m may be interpreted as "n rows, m columns", or "n columns, m rows").

Task 1:

Create (and output/print) a vector / list consisting of the elements: n, n+1 ... m-1, m. So, for n=4, m=9, you should output: 4,5,6,7,8,9.

Task 2:

Create (and output/print) a matrix / array / list of lists (or equivalent) looking like this:

n,   n+1, ... m-1, m
n+1, n+2, ... m-1, m+1
...
n+m, n+m+1, ... 2*m-1, 2*m

For n=4, m=9 you should output:

4, 5, 6, 7, 8, 9
5, 6, 7, 8, 9, 10
...
13, 14, 15, 16, 17, 18

Task 3:

Create (and output/print) an n-by-m multiplication table (on any suitable format). Example for n=4, m=9:

1   2   3  4
2   4   6  8
3   6   9  12
4   8  12  16
5  10  15  20
6  12  18  24
7  14  21  28
8  16  24  32
9  18  27  36

Task 4:

Output / print a vector / list consisting of the elements in the multiplication table from task 3, sorted in ascending order, keeping duplicate values. For n=4, m=9, you should output: 1, 2, 2, 3, 3, 4, 4, 4, 5, 6, 6, 6, 7, 8, 8, 8, 9, 9, 10, 12, 12, 12, 14, 15, 16, 16, 18, 18, 20, 21, 24, 24, 27, 28, 32, 36.

The challenge:

Now, all the tasks above are quite trivial. The real challenge here is that the code for task 2 must start with the code for task 1, the code for task 3 must start with the code for task 2 and the code for task 4 must start with the code for task 3.

To make it more clear:

Suppose the code for Task 1 is (works in Octave):

@(n,m)(n:m)

Then your code for Task 2 could be (works in Octave):

@(n,m)(n:m)+(0:m)'

The code for task Task 3 must be (doesn't work in Octave):

@(n,m)(n:m)+(0:m)'"Code_for_task_3"

And finally, the code for Task 4 must be (doesn't work in Octave):

@(n,m)(n:m)+(0:m)'"Code_for_task_3""Code_for_task_4"

This is code-golf, so the submission with the shortest code for task 4 in each language wins. As always: Explanations are highly encouraged.

Jelly, 12 bytes

Task 1

r

Try it online!

Task 2

r+þ0r$}

Try it online!

Task 3

r+þ0r$}
×þ

Try it online!

Task 4

r+þ0r$}
×þFṢ

Try it online!

How it works

Task 1

r is the dyadic range atom and does exactly what the task asks for.

Task 2

A dyadic chain that begins with three dyadic links is a fork; the outmost links get evaluated first, then the middle link is called with the results to both sides as arguments.

r behaves as before, yielding [n, …, m].
0r$} is a quicklink (or quickquicklink, if you will).

The quick $ (monadich chain) consumes the links 0 (yield 0) and r (dyadic range) and turns them into a monadic chain. When called with argument k, this will yield [0, …, k].

The quick } (right argument) takes the quicklink created by $ and turns it into a dyadic link that calls 0r$ with 0r$}'s right argument.

0r$} will be called with left argument n and right argument m, so 0r$ is alled with argument m and yields [0, …, m].
+þ is another quicklink. þ (table) will call + (addition) for every element in its left argument and any element in its right argument, grouping the results for each right argument into a single row.

+þ will be called with left argument [n, …, m] and right argument [0, …, m], yielding the desired table.

Task 3

Every line in a Jelly program defines a different link. The last one is the main link and, like C's main function, is the only link that is executed by default. The remaining links can be called from the main link, but we won't do this here.

As before, þ (table) will call × (addition) for every element in its left argument and any element in its right argument, grouping the results for each right argument into a single row.

Since both arguments to ×þ are integers, þ casts them to ranges, transforming the arguments n and m into [1, …, n] and [1, …, m].

Task 4

×þ works as before. The following links are monadic, making them atops, i.e., they are applied on top of the previous ones.

After executing ×þ, F flattens the resulting 2D array, and Ṣ sorts the resulting 1D array.


Compute the Wilson score interval The Wilson score interval is a confidence interval of the probability of success, based on the proportion of successes in a set of Bernoulli trials (a Bernoulli trial is a trial in which exactly two outcomes are possible: success or failure). The interval is given by the following formula:

The two values given by the formula are the upper and lower bounds of the interval. nS and nF are the number of successes and failures, respectively, and n is the total number of trials (equivalent to nS + nF). z is a parameter dependent on the level of confidence desired. For the purposes of this challenge, z = 1.96 will be used (corresponding to a 95% confidence interval)1.
Given non-negative integers nS and nF, output the bounds of the Wilson score interval.
Rules

The outputs must be as accurate as possible to the true values, within the limits of your language's floating-point implementation, ignoring any potential issues due to floating-point arithmetic inaccuracies. If your language is capable of arbitrary-precision arithmetic, it must be at least as precise as IEEE 754 double-precision arithmetic.
The inputs will be within the representable range for your language's native integer type, and the outputs will be within the representable range for your language's native floating-point type.
n will always be positive.
The order of the outputs does not matter.

Test Cases
Format: n_s, n_f => lower, upper
0, 1 => 0.0, 0.7934567085261071
1, 0 => 0.20654329147389294, 1.0
1, 1 => 0.09452865480086611, 0.905471345199134
1, 10 => 0.016231752262825982, 0.3773646254862038
10, 1 => 0.6226353745137962, 0.9837682477371741
10, 90 => 0.05522854161313612, 0.1743673043676654
90, 10 => 0.8256326956323345, 0.9447714583868639
25, 75 => 0.17545094003724265, 0.3430464637007583
75, 25 => 0.6569535362992417, 0.8245490599627573
50, 50 => 0.40382982859014716, 0.5961701714098528
0, 100 => 0.0, 0.03699480747600191
100, 0 => 0.9630051925239981, 1.0

The z value is the 1-α/2th quantile of the standard normal distribution, where α is the significance level. If you want a 95% confidence interval, your significance level is α=0.05, and the z value is 1.96.

Mathematica, 48 bytes (UTF-8 encoding)

({-1,1}√((s=1.4^4)##/+##+s^2/4)+#+s/2)/(s+##)&

Unnamed function taking two arguments in the order n_s, n_f and returning an ordered pair of real numbers. The three-byte symbol √, representing the square-root function, is U-221A.

Uses the fact that preceding ## by a number results in the product of the two arguments, while +## results in their sum. Also uses the fact that products and sums automatically thread over lists, so that {-1,1}√(...) implements the ± in the formula. Defining the constant s = z^2 instead of z itself also saved a couple of bytes. (Mostly I'm just proud of saving a byte by noticing that 1.4^4 is exactly 1.96^2!)