Generate a Walsh Matrix A Walsh matrix is a special kind of square matrix with applications in quantum computing (and probably elsewhere, but I only care about quantum computing).

Properties of Walsh matrices

The dimensions are the same power of 2. Therefore, we can refer to these matrices by two's exponent here, calling themW(0), W(1), W(2)...

W(0) is defined as [[1]].

For n>0,  W(n) looks like:

[[W(n-1)  W(n-1)]
 [W(n-1) -W(n-1)]]

So W(1) is:

[[1  1]
 [1 -1]]

And W(2) is:

[[1  1  1  1]
 [1 -1  1 -1]
 [1  1 -1 -1]
 [1 -1 -1  1]]

The pattern continues...

Your task

Write a program or function that takes as input an integer n and prints/returns W(n) in any convenient format. This can be an array of arrays, a flattened array of booleans, a .svg image, you name it, as long as it's correct.

Standard loopholes are forbidden.

A couple things:

For W(0), the 1 need not be wrapped even once. It can be a mere integer.

You are allowed to 1-index results—W(1) would then be [[1]].

Test cases

0 -> [[1]]
1 -> [[1  1]
      [1 -1]]
2 -> [[1  1  1  1]
      [1 -1  1 -1]
      [1  1 -1 -1]
      [1 -1 -1  1]]
3 -> [[1  1  1  1  1  1  1  1]
      [1 -1  1 -1  1 -1  1 -1]
      [1  1 -1 -1  1  1 -1 -1]
      [1 -1 -1  1  1 -1 -1  1]
      [1  1  1  1 -1 -1 -1 -1]
      [1 -1  1 -1 -1  1 -1  1]
      [1  1 -1 -1 -1 -1  1  1]
      [1 -1 -1  1 -1  1  1 -1]]

8 -> Pastebin

This is code-golf, so the shortest solution in each language wins! Happy golfing!

MATL, 4 bytes

W4YL

Try it online!

How it works:

W       % Push 2 raised to (implicit) input
4YL     % (Walsh-)Hadamard matrix of that size. Display (implicit)

Without the built-in: 11 bytes

1i:"th1M_hv

Try it online!

How it works:

For each Walsh matrix W, the next matrix is computed as [W W; W −W], as is described in the challenge. The code does that n times, starting from the 1×1 matrix [1].

1       % Push 1. This is equivalent to the 1×1 matrix [1]
i:"     % Input n. Do the following n times
  t     %   Duplicate
  h     %   Concatenate horizontally
  1M    %   Push the inputs of the latest function call
  _     %   Negate
  h     %   Concatenate horizontally
  v     %   Concatenate vertically
        % End (implicit). Display (implicit)


Mathematics is fact. Programming is not In mathematics an exclamation mark ! often means factorial and it comes after the argument.
In programming an exclamation mark ! often means negation and it comes before the argument.
For this challenge we'll only apply these operations to zero and one.
Factorial
0! = 1
1! = 1

Negation
!0 = 1
!1 = 0

Take a string of zero or more !'s, followed by 0 or 1, followed by zero or more !'s (/!*[01]!*/).
For example, the input may be !!!0!!!! or !!!1 or !0!! or 0! or 1.
The !'s before the 0 or 1 are negations and the !'s after are factorials.
Factorial has higher precedence than negation so factorials are always applied first.
For example, !!!0!!!! truly means !!!(0!!!!), or better yet !(!(!((((0!)!)!)!))).
Output the resultant application of all the factorials and negations. The output will always be 0 or 1.
Test Cases
0 -> 0
1 -> 1
0! -> 1
1! -> 1
!0 -> 1
!1 -> 0
!0! -> 0
!1! -> 0
0!! -> 1
1!! -> 1
!!0 -> 0
!!1 -> 1
!0!! -> 0
!!!1 -> 0
!!!0!!!! -> 0
!!!1!!!! -> 0

The shortest code in bytes wins.

Mathematica, 25 17 bytes

Input[]/.!x_:>1-x

Takes input from a user prompt. Assumes Mathematica's notebook environment for implicit printing. To make it a command-line script, wrap it in Print[...] or to make it an argumentless function (which then takes input from the prompt), append &.

Mathematica has both of the required operators (with the required precedence), so we can just "eval" the input (which is done automatically by Input[]), but the logical negation operator doesn't work on integers (so it will remain unevaluated). If there's a !x left in the result, we replace it with 1-x.

A couple of fun facts about the evaluation:

Mathematica actually also has the double factorial operator !!, which computes n*(n-2)*(n-4)*..., but applied to 0 or 1 it still gives 1, so it doesn't matter that 0!!!!! will actually be parsed as ((0!!)!!)!.
Even though Mathematica leaves !0 and !1 unevaluated, it does know that ! is self-inverse, so it will automatically cancel all pairs of leading !. After the ToExpression we're always left with one of 0, 1, !0, !1.


Build a code minifier Pick a programming language.

In that language, write a function or program that takes as input a string of working code (in the same language).

It should return/output a minified version of the input code.  The output should be functionally equivalent to the input.

Answers should contain both

The code that does the minifying (should be readable/non-golfed)
The resulting output after passing your code (that is, the code that does the minifying) in to itself

The shortest output wins.

Edit: notes explaining the minification methods you used are appreciated.

Edit: obviously, minification methods could vary from language to language, but a good-faith attempt at writing a minifier for this challenge would most likely perform actions such as

Removing unnecessary whitespace
Removing unnecessary newlines
Removing comments
Shortening variable names

Brainfuck

I always had in mind to do this, so here we go:

>>>,
[
[->+>+<<]             copy input

<<<+++++++++++++      fill cell with 13 for subtraction
[->+>+>+<<<]          and duplicate some times

>>>[->---<]           sub 39
>----                 43

[                     plus
-
[                     comma
-
[                     minus
-
[                     dot

<<[->>-<<]>>-         60

[                     less than
--
[                     greater than

<<<[->>>--<<<]>>>     86
---                   91

[                     open square bracket
--
[                     closing square bracket

>[-]                  remove copy

]]]]]]]]

>[.[-]>]              the copy has not been removed; print

<<[-]<<<[-]>[-]>      clean up

,]

Compresses itself to (144 characters):

>>>,[[->+>+<<]<<<+++++++++++++[->+>+>+<<<]>>>[->---<]>----[-[-[-[<<[->>-
<<]>>-[--[<<<[->>>--<<<]>>>---[--[>[-]]]]]]]]]>[.[-]>]<<[-]<<<[-]>[-]>,]

The size of the compressing could probably still reduced a bit. The compression alogorithm itself is near perfect, it's hard to do any more than removing non-+-[]<>,..


Is there a language that supports Turing machines? Is there a programming language that supports single tape Turing machines specified in some format?

I am aware multiple formats for expressing them exist, but is there a standard one using which an acceptable answer can be published on this site?

If it doesn't exist can somebody create one? Golfing Turing machines has academic relevance too.

It should be acceptable to post answers in pure turing machine code. I have seen people do this before.
Examples:
https://codegolf.stackexchange.com/a/200380/95627
Simple cat program
If anyone knows more about this, you can edit.


The "skip-pure" numbers The skip-pure numbers are defined with this rule:

A(0) = 1
A(1) = 1
A(n) = the smallest positive number not in the sequence such that A(x) + A(x-2) for any x never appears

For example, the term A(2) is 2, because 1 has already appeared. The term A(3) is 4, as A(2) + A(0) = 3 and 3 is disallowed by the third line of the rule.

Given a number n, your program should output the nth skip-pure number, using zero-based indexing (such that A(0) is defined).

Output can be in any format (strings, ints, lists, arrays, etc.), but the number itself must be outputted in base 10.

Trailing output (newlines, etc.) is allowed but only if your language has to output it. If you can work around trailing output, solve it with the workaround.

Here are test cases, shown in the format input = output:

0 = 1
1 = 1
2 = 2
3 = 4
4 = 6
5 = 7
6 = 9
7 = 10
8 = 12
9 = 13

I created this sequence myself and am probably the first person to talk about it, so there is no OEIS link.

This is a code-golf, so the shortest program that does all of the above (measured in bytes) wins. Have fun.

JavaScript (ES7),  59  31 bytes
Returns the \$n\$-th term, 0-indexed. This is a closed-form formula.

n=>n*1.5^Math.log2(n)&n%4==2^!n

Try it online!
Formula
The only edge case is \$a(0)=1\$. For \$n\ge1\$:
$$a(n)=\cases{\left\lfloor\dfrac{3n}{2}\right\rfloor-1,&\text{if $\lfloor log_2(n)\rfloor$ is odd and $n\equiv 2\pmod 4$} \\
\left\lfloor\dfrac{3n}{2}\right\rfloor,&\text{otherwise}
}
$$


Solve a separable differential equation A first order separable ordinary differential equation is (arguably) the easiest type of differential equation to solve, and takes the form of

$$N(y)\frac{dy}{dx} = M(x) \\
y(x_0) = y_0$$

For two given functions \$N(y)\$ and \$M(x)\$ and an initial condition \$y(x_0) = y_0\$.

Your task is to take \$N(y)\$, \$M(x)\$, \$x_0\$ and \$y_0\$ and output the solution to that differential equation.

How to solve a separable differential equation

The differential equation

$$N(y)\frac{dy}{dx} = M(x)$$

can be solved through the following method:

$$
\begin{align}
N(y)\frac{dy}{dx} & = M(x) \\
\int{N(y)\frac{dy}{dx}dx} & = \int{M(x)dx} \\
\int{N(y)dy} & = \int{M(x)dx}
\end{align}
$$

Once the integrals have been calculated, we can remove one of the constants of integration, leaving the equation

$$f(y) = g(x) + c$$

where

$$
f(y) = \int{N(y)dy} \\
g(x) = \int{M(x)dx}
$$

After this, \$c\$ can be calculated by applying the initial condition:

$$
c = f(y_0) - g(x_0)
$$

and a final solution for \$f(y)\$ can be given.

Challenge

You are to take in four inputs:

The function \$N(y)\$
The function \$M(x)\$
\$x_0\$
\$y_0\$

Both \$x_0\$ and \$y_0\$ can be any real number, and can be taken as input in many reasonable manner (i.e. a list, tuple, two integers etc.). The functions, in order to avoid having to focus on parsing mathematical input, will be limited to a type of Laurent polynomials - i.e polynomials in the form

$$
p(x) = \alpha \cdot x^n + \beta \cdot x^{n-1} + \dots + \gamma + \delta \cdot x^{-2} + \epsilon \cdot x^{-3} + \dots + \zeta \cdot x^{-m+1} + \eta \cdot x^{-m} \\
\alpha, \beta, \dots, \eta \in \mathbb{R}, \:\: n, m \in \mathbb{N}
$$

Notice that we'll never have \$x^{-1}\$ in the polynomial, and that because of this, the integrals will always be Laurent polynomials of the same form (with \$x^{-1}\$ included after integrating).

With inputs in this format, there are multiple ways you could represent them for input. As with the mapping, any reasonable representation is acceptable, and if you aren't sure, ask. However, here are some that are definitely allowed (for the example \$p(x) = 3x^2 + x + 6 - 2x^{-2} + 7x^{-5}\$):

Nested list: [[3, 2], [1, 1], [6, 0], [-2, -2], [7, -5]]
A pair of lists of coefficients: [3, 1, 6] and [0, -2, 0, 0, 7]
A string representation: "3x^2 + x + 6 - 2x^-2 + 7x^-5"
etc.

Given these four inputs, you are to output the solution to the differential equation they represent.

In order to avoid having to algebraically manipulate your solutions to get into the form \$y(x) = ...\$, you can output two Laurent polynomials, in the same form as the input; one representing \$y\$ and the other \$x\$.

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

Test cases

Both the MathJax and text-based inputs will be included for each example, where the text based will use the nested list input format above. In addition, I will walk through the first example for clarity.

In:
  N = [[1, -2]]
  M = [[6, 1]]
  1 -> 1/25 = 0.04
Out:
  y = [[-1, -1]]
  x = [[3, 2], [28, 0]]

$$
\begin{align}
\frac{1}{y^2}\frac{dy}{dx} & = 6x \\
y(1) & = \frac{1}{25} = 0.04 \\
\\
\int{N(y)dy} & = \int{M(x)dx} \\
\int{\frac{1}{y^2}dy} & = \int{6xdx} \\
-\frac{1}{y} & = 3x^2 + c \\
-25 & = c + 3 \implies c = -28 \\
-\frac{1}{y} & = 3x^2 - 28
\end{align}
$$

In:
  N = [[2, 1], [-4, 0]]
  M = [[3, 2], [4, 1], [-4, 0]]
  1 -> 3
Out:
  y = [[1, 2], [-4, 1]]
  x = [[1, 3], [2, 2], [-4, 1], [-2, 0]]

$$
N(y) = 2y - 4, \:\: M(x) = 3x^2 + 4x - 4 \\
y(1) = 3 \\
\:\\
y^2 - 4y = x^3 + 2x^2 - 4x + c \\
c = -2 \\
y^2 - 4y = x^3 + 2x^2 - 4x - 2 \\
$$

In:
  N = [[1, 0]]
  M = [[3, 2], [2, 0]]
  0 -> 0
Out:
  y = [[1, 1]]
  x = [[1, 3], [2, 1]]

$$
N(y) = 1, \:\: M(x) = 3x^2 + 2 \\
y(0) = 0 \\
\:\\
y = x^3 + 2x + c \\
c = 0 \\
y = x^3 + 2x \\
$$

Python 2, 123 122 bytes

def f(p,P):R=[[[a/-~b,b+1]for a,b in F]for F in P];a,b=map(lambda F,x:sum(a*x**b for a,b in F),R,p);R[1]+=[a-b,0],;print R

Try it online!

Straight-forward implementation. A function that takes arguments in the form (y, x), (N, M), and prints the resulting 2 polynomials to STDOUT.


Back to the chemistry class Introduction

One of the first things I learned in chemistry, was giving the formula for the combustion of alkanes. The most basic example was: 2CH4 + 4O2 > 4H2O + 2CO2. Note that the equation could have been simplified by dividing every coefficient by 2, we would get CH4 + 2O2 > 2H2O + CO2. To make things easier, we are going to ignore this step.

You can see that with the combustion of any alkane, oxygen is used. After the reaction, only CO2 and H2O are made.

The task:

Give a complete program that takes input from STDIN or the nearest possible equivalent, and outputs the total reaction using STDOUT or the nearest possible equivalent.

The input will always be in the form C(n)H(2n+2), with n > 0. These are some example inputs:

CH4
C2H6
C3H8
C4H10
C5H12
C6H14

etc.

A useful tip:

Every alkane has a standard pattern in the combustion reaction:

2C(n)H(2n+2) + (3n+1)O2 > (2n+2)H2O + (2n)CO2

e.g.

C4H10 gives the following equation: 2C(4)H(2*4+2) + (3*4+1)O2 > (2*4+2)H2O + (2*4)CO2. After calculating everything, we get this final equation: 2C4H10 + 13O2 > 10H2O + 8CO2

Examples:

input:  CH4
output: 2CH4 + 4O2 > 4H2O + 2CO2

input:  C3H8
output: 2C3H8 + 10O2 > 8H2O + 6CO2

input:  C4H10
output: 2C4H10 + 13O2 > 10H2O + 8CO2

input:  C12H26
output: 2C12H26 + 37O2 > 26H2O + 24CO2

Rules:

You need to provide a full program.
Your program needs to take input from STDIN, or the nearest equivalent if not possible.
Your program needs to output using STDOUT, or the nearest equivalent if not possible.
Note that I used spaces for the examples to increase readability, these are not necessary. 2CH4 + 4O2 > 4H2O + 2CO2 and 2CH4+4O2>4H2O+2CO2 are both valid outputs. However, if you consistently use spaces for the output, you get a -10% bonus
This is code-golf, so the program with the least amount of bytes wins!

Python 3, 86 * 0.9 = 77.4 bytes

s=input()
N=int(s.split('H')[1])
print("2%s + %dO2 > %dH20 + %dCO2"%(s,N*1.5-2,N,N-2))

Extracts the number of H's rather than the number of C's from the input. This avoid special-casing CH4 and simplifies the output expressions in terms of N=2n+2.

The output has parameters plugged in via string formatting. The first summand is just the input string, and the rest have calculated numbers plugged in. Note that N*1.5-2 (same as N*3/2-2) gives a float, but the string formatting converts it to an int.


Matrix in "slash" order Given two positive numbers N >= 2 and N <= 100 create a matrix which follows the following rules:

First Number starts at position [0,0]
Second Number starts at position [0,1]
Third number goes below First Number (position [1,0])
Following numbers goes in "slash" direction
Range of numbers used is [1, N1 * N2]. So, numbers goes from starting 1 to the result of the multiplication of both inputs.

Input

Two numbers N >= 2 and N <= 100. First number is the amount of rows, Second number the amount of columns.

Output

Matrix. (Can be outputted as a multidimensional array or a string with line breaks)

Example:

Given numbers 3 and 5 output:

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

Given numbers 2 and 2

1   2
3   4

Given Numbers 5 and 5

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

The shortest code in bytes wins.

Jelly, 6 5 bytes

pSÞỤs

Try it online!

How it works

pSÞỤs  Main link. Left argument: n. Right argument: k

p      Take the Cartesian product of [1, ..., n] and [1, ..., k], yielding
       [[1, 1], [1, 2], ..., [n, k-1], [n, k]].
 SÞ    Sort the pairs by their sums.
       Note that index sums are constant on antidiagonals.
   Ụ   Grade up, sorting the indices of the sorted array of pairs by their values.
    s  Split the result into chunks of length k.


Check whether an integer is a power of 2 without using +,- operations Write a program that checks if the integer is a power of 2.

Sample input:

8

Sample output:

Yes

Sample input:

10

Sample output:

No

Rules:

Don't use +,- operations.
Use some sort of input stream to get the number. Input is not supposed to be initially stored in a variable.
The shortest code (in bytes) wins.

You can use any truthy/falsy response (for instance, true/false). You may assume that input number is greater than 0.

APL (7)

Yes, that's 7 bytes. Assume for the moment that I'm using IBM codepage 907 instead of Unicode and then each character is a byte :)

0=1|2⍟⎕

i.e. 0 = mod(log(input(),2),1)


Greater than less than greater than something fishy Given a length N string of less-than and greater-than signs (<, >), insert the integers 0 through N at the start and end and in between each pair of signs such that all the inequalities are satisfied. Output the resulting string. If there are multiple valid outputs, output any one (and just one) of them.
For example
<<><><<

has 7 characters so all the numbers from 0 to 7 inclusive must be inserted. A valid output is
2<3<4>1<5>0<6<7

because all the inequalities taken one at a time
2<3
3<4
4>1
1<5
5>0
0<6
6<7

are true.
If desired, the output may have spaces surrounding the signs, e.g. 2 < 3 < 4 > 1 < 5 > 0 < 6 < 7.
The shortest code in bytes wins.
Test Cases
The first line after an empty line is the input and the next line(s) are each valid output examples.
[empty string]
0

<
0<1

>
1>0

<<
0<1<2

<>
1<2>0

><
1>0<2
2>0<1

>>
2>1>0

<<<
0<1<2<3

><>
1>0<3>2

>><
3>2>0<1
3>1>0<2
2>1>0<3

>>>
3>2>1>0

>>><<<
3>2>1>0<4<5<6
6>3>1>0<2<4<5
4>2>1>0<3<5<6
4>3>1>0<2<5<6

<<><><<
2<3<4>1<5>0<6<7

>><><>>
7>6>0<5>1<4>3>2

<<<<<<<<<<<<<<
0<1<2<3<4<5<6<7<8<9<10<11<12<13<14

>><<<<><>><><<
6>5>4<7<8<9<10>3<11>2>1<12>0<13<14
14>5>4<7<8<9<10>3<11>2>1<12>0<13<6

Retina, 20 bytes

Byte count assumes ISO 8859-1 encoding.

$.'
S`>
%O#`\d+
¶
>

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

Explanation

A simple way to find a valid permutation is to start by inserting the numbers from 0 to N in order, and then to reverse the numbers surrounding each substring of >s. Take <><<>>><< as an example:

0<1>2<3<4>5>6>7<8<9
  ---   -------      these sections are wrong, so we reverse them
0<2>1<3<7>6>5>4<8<9

Both of those tasks are fairly simple in Retina, even though all we can really work with are strings. We can save an additional byte by inserting the numbers from N down to 0 and reversing the sections surrounding < instead, but the principle is the same.

Stage 1: Substitution

$.'

We start by inserting the length of $' (the suffix, i.e. everything after the match) into every possible position in the input. This inserts the numbers from N down to 0.

Stage 2: Split

S`>

We split the input around > into separate lines, so each line is either an individual number or a list of numbers joined with <.

Stage 3: Sort

%O#`\d+

Within each line (%) we sort (O) the numbers (\d#) by their numerical value (#). Since we inserted the number in reverse numerical order, this reverses them.

Stage 4: Substitution

¶
>

We turn the linefeeds into > again to join everything back into a single line. That's it.

As a side note, I've been meaning to add a way to apply % to other delimiters than linefeeds. Had I already done that, this submission would have been 14 bytes, because then the last three stages would have been reduced to a single one:

%'>O#`\d+


Tips for Golfing in Vitsy While there are only a few users of the Vitsy programming language right now, I wish to create a place for tips for golfing in Vitsy.

What general tips do you have for golfing in Vitsy? I'm looking for ideas that can be applied to code golf problems in general that are at least somewhat specific to Vitsy (e.g. "remove NOPs" is not an answer). Please post one tip per answer.

For reference, the online interpreter is here, the esolang page is here, and you can receive answer-per-answer help here.

Do not doubt the power of m

Background: Fm calls the a specified line index in the current Vitsy class. (F is the line index you seek).

The m command (method) has saved me literally hundreds of bytes in the past. Any algorithm that uses repeated steps, or a common character sequence (such as D1M- (floor algorithm)).

This is extremely helpful in repetitive kolmogorov complexity challenges.

Instead of:

WD1M-(something else here)WD1M-(something different)WD1M-l\[NaO]

Use:

1m(something else here)1m(something different)1ml\[NaO]
WD1M-

(floor(prompt))

Also, you can return from method statements with ;, allowing for looping until condition(s) (over the general [  ] syntax, which isn't as powerful):

1mN
<;)

(loops through code until finding non-zero, popping it from the stack and returning to first line)


Mixing characters in a string You have to write a function/program that takes input via the stdin/command-line arguments/function arguments, mixes up characters in a string, and then output the final string via the stdout.

Input will first contain a string (not empty or null), a space, and then an even number of non-negative numbers all separated by spaces. If input is taken via function arguments, the string will be the one of the arguments while the integers, which are seperated by a space, will be the other. You must swap the characters of the string at the indices corresponding to consecutive pairs of numbers.

For instance:

Hello_world! 0 6

must result in

wello_Horld!

Assumptions

You may choose between 0-based and 1-based indexing, and may assume that the given indexes will always be in range.
The string will not be longer than 100 characters and will only contain ASCII characters in range ! to ~ (character codes 0x21 to 0x7E, inclusive). See ASCII table for reference.
The two indices in a pair may be identical (in which case, nothing is swapped in that step).

Scoring

This is code golf, so the shortest submission (in bytes) wins.

Test Cases

Hello_world! 0 6 => wello_Horld!
First 1 2 1 0 0 4 => tFisr
(Second!$$) 8 7 10 1 => ()econd$!$S
~Third~ 0 0 6 6 0 6 6 0 => ~Third~

CJam, 11 bytes
rr{irie\r}h

How it works
This is a slightly different approach, in which I simply run a do-while loop till I have pairs of numbers left in the input.
r                 e# Read the first string
 r                e# Read the first number of the first number pair in the input
  {      }h       e# Do a do-while loop
   i              e# Convert the first number from the pair to integer
    ri            e# Read the second number from the pair and convert to intger
      e\          e# String X Y e\ works by swapping the Xth index with the Yth index in the
                  e# String
        r         e# This is our exit condition of the do-while loop. If we still have
                  e# a number on the input left, that means there are more pairs to swap.
                  e# Otherwise, we exit the loop and the result is printed automatically

Try it online here


Debunking Stroustrup's debunking of the myth “C++ is for large, complicated, programs only” Stroustrup has recently posted a series of posts debunking popular myths about C++. The fifth myth is: “C++ is for large, complicated, programs only”. To debunk it, he wrote a simple C++ program downloading a web page and extracting links from it. Here it is:
#include <string>
#include <set>
#include <iostream>
#include <sstream>
#include <regex>
#include <boost/asio.hpp>

using namespace std;

set<string> get_strings(istream& is, regex pat)
{
    set<string> res;
    smatch m;
    for (string s; getline(is, s);)  // read a line
        if (regex_search(s, m, pat))
            res.insert(m[0]);              // save match in set
    return res;
}

void connect_to_file(iostream& s, const string& server, const string& file)
// open a connection to server and open an attach file to s
// skip headers
{
    if (!s)
        throw runtime_error{ "can't connect\n" };

    // Request to read the file from the server:
    s << "GET " << "http://" + server + "/" + file << " HTTP/1.0\r\n";
    s << "Host: " << server << "\r\n";
    s << "Accept: */*\r\n";
    s << "Connection: close\r\n\r\n";

    // Check that the response is OK:
    string http_version;
    unsigned int status_code;
    s >> http_version >> status_code;

    string status_message;
    getline(s, status_message);
    if (!s || http_version.substr(0, 5) != "HTTP/")
        throw runtime_error{ "Invalid response\n" };

    if (status_code != 200)
        throw runtime_error{ "Response returned with status code" };

    // Discard the response headers, which are terminated by a blank line:
    string header;
    while (getline(s, header) && header != "\r")
        ;
}

int main()
{
    try {
        string server = "www.stroustrup.com";
        boost::asio::ip::tcp::iostream s{ server, "http" };  // make a connection
        connect_to_file(s, server, "C++.html");    // check and open file

        regex pat{ R"((http://)?www([./#\+-]\w*)+)" }; // URL
        for (auto x : get_strings(s, pat))    // look for URLs
            cout << x << '\n';
    }
    catch (std::exception& e) {
        std::cout << "Exception: " << e.what() << "\n";
        return 1;
    }
}

Let's show Stroustrup what small and readable program actually is.

Download http://www.stroustrup.com/C++.html

List all links:
 http://www-h.eng.cam.ac.uk/help/tpl/languages/C++.html
 http://www.accu.org
 http://www.artima.co/cppsource
 http://www.boost.org
 ...

You can use any language, but no third-party libraries are allowed.
Winner
C++ answer won by votes, but it relies on a semi-third-party library (which is disallowed by rules), and, along with another close competitor Bash, relies on a hacked together HTTP client (it won't work with HTTPS, gzip, redirects etc.). So Wolfram is a clear winner. Another solution which comes close in terms of size and readability is PowerShell (with improvement from comments), but it hasn't received much attention. Mainstream languages (Python, C#) came pretty close too.
Comment on subjectivity
The most upvoted answer (C++) at the moment votes were counted was disqualified for not following the rules listed here in the question. There's nothing subjective about it. The second most upvoted question at that moment (Wolfram) was declared winner. The third answer's (Bash) "disqualification" is subjective, but it's irrelevant as the answer didn't win by votes at any point in time. You can consider it a comment if you like. Furthermore, right now the Wolfram answer is the most upvoted answer, the accepted one, and is declared winner, which means there's zero debate or subjectivity.

Wolfram

This feels like complete cheating

Import["http://www.stroustrup.com/C++.html", "Hyperlinks"]

So just add some honest parsing on top

Cases[
 Import["http://www.stroustrup.com/C++.html", "XMLObject"],
 XMLElement["a", {___, "href" -> link_, ___}, ___] :>
  link /; StringMatchQ[link, RegularExpression["((http://)?www([./#\\+-]\\w*)+)"]]
, Infinity]


Binary Tetris in tweets There was recently (a few years back) some buzz on programming websites about an implementation of Tetris in 140 Bytes.
...

It turns out that although it is small, it is a simplified version of Tetris, and not even a complete implementation. Only the core logic function fits in 140 bytes of Javascript. To actually run it, you need another ~840 characters of HTML.

We can do better!
This challenge is to implement a complete version of "Binary Tetris" in as few tweets as possible.

Binary Tetris Rules:

The program must display a playing field containing at least 5 columns and 6 rows of cells.

Any method of display may be used, as long as the blocks and the edges of the field are clearly marked.

There must be at least two types of blocks:  # and ##. Additional block support such as ### or angle blocks shaped like an L will get upvoted by me :P and the most complete game of binary tetris (the most blocks like the original and rotation features) will win my happiness and a possible bounty up 50 rep.
New blocks are added to the field in the top row, and one block cell must occupy the center column.
Blocks descend towards the bottom row at a fixed rate.  Blocks must descend even without user input.
When blocks touch the bottom of the field or a lower block, they stop falling and are fixed in place.  A new block is added.
When all the columns in the row are filled with blocks, the row is emptied, and all the fixed blocks above drop down one row.
The program must respond to keypresses.  There must be 3 unique keys that perform the following functions

shift current block left 1 column
shift current block right 1 column
shift current block down 1 row

Each tweet may only have 140 characters. Using multi-byte characters that can be put in tweets is allowed.
The rules for what can be in a tweet is simple. If you can tweet it you can use it.
Interpreted languages follow the same rules. Each section must follow the specs. As long as no run time errors occur (and the rest is valid following the specs) your answer is valid
Golfing Rules:
Because the original implementation was "tweetable", this challenge requires the same.  Entries must be able to be transmitted as a series of tweets (lines of 140 characters or less).
The first tweet must contain the name of the compiler/interpreter, the name of the program, and any command line arguments

it will be saved as file "P0"

The following N tweets must contain the program as a series of lines.

Each tweet will be stored in a file with the name T<n>, where n is 1..N

Each line will be added to the previous lines and compiled or interpreted.  It must produce a valid object file or program.
The program does not need to be functional until the last line is added.
The program will be run in the following manner (pseudo-bash)

interp,prog,args = split P0 /\s/
touch $prog
for file in ./T* do
  cat $prog file > $prog
  $interp $prog $args
  die("FAIL") if $? #detect error
done

The interpreter must be a commonly available executable program that does not already implement Tetris.

Scoring:
Fewest Tweets, including P0.  Ties broken by largest number of spare characters (140 * num tweets - total character count).

Example Entries

chrome a.htm

Score = 3 (334 spare)

cc a.c ;a.out
main(){/*cool prog here*/}

Score = 2 (241 spare)

tetris

Score = 1 (134 spare)    if it were legal, which it's not

Special thanks

I was allowed to post this by Ashelly's consent here

Python 3, Score of 5 Tweets (242 spare, counting P0)

-19 bytes thanks to Jonathan Allan!

The spare count does not take into account newlines from between tweets.

Tweet 1 (Declaration, 12 bytes)

python3 t.py

Tweet 2 (70 bytes)

import msvcrt as m,os;f=c=s=0;a=34636833;r=range;p=1<<32;t=30
while 1:

Tweet 3 (129 bytes)

 if m.kbhit()and b"\xe0"==m.getch():p=[p>>(not(a|f<<1)&p),p,p<<(not(a<<4|f>>1)&p),p>>5-5*(bool(f&p>>5)or p<t)][ord(m.getch())-77]

Tweet 4 (113 bytes)

 c+=1;print("\n".join("".join(".#"[1&(f|p)>>i*5+j]for j in r(5))for i in r(6))[::-1]);os.system("cls")
 if c%t<1:

Tweet 5 (134 bytes)

  if f&p>>5or p<t:s=~s;f|=p;p=2-s<<26
  else:p>>=5
 for i in r(0,t,5):
  if f|31<<i==f:b=bin(f)[2:].zfill(t);f=int(b[:-i-5]+b[t-i:],2)

Full Program (449 bytes)

import msvcrt as m,os;f=c=s=0;a=34636833;r=range;p=1<<32;t=30
while 1:
 if m.kbhit()and b"\xe0"==m.getch():p=[p>>(not(a|f<<1)&p),p,p<<(not(a<<4|f>>1)&p),p>>5-5*(bool(f&p>>5)or p<t)][ord(m.getch())-77]
 c+=1;print("\n".join("".join(".#"[1&(f|p)>>i*5+j]for j in r(5))for i in r(6))[::-1]);os.system("cls")
 if c%t<1:
  if f&p>>5or p<t:s=~s;f|=p;p=2-s<<26
  else:p>>=5
 for i in r(0,t,5):
  if f|31<<i==f:b=bin(f)[2:].zfill(t);f=int(b[:-i-5]+b[t-i:],2)

Does some evil bit point hacking and stores the field and piece in two integers. I'll try and post an explanation soon.

Note: This only runs on Windows, but it could be switched to Linux through msvcrt → getch and "cls" → "clear". Additionally, character input doesn't work on Python's IDLE, so I'd recommend running it elsewhere.


set intersection of two lists Your goal is to compute the set intersection of two lists of integers. The intersection is defined as the unique un-ordered group of integers found at least once in both input list.

Input

The input may be in any format desired (function parameter, stdio, etc.), and consists of two lists of integers. You many not assume anything about each list other than they may contain any non-negative number of integers (i.e. they are unsorted, possibly may contain duplicates, may have different lengths, and may even be empty). It is assumed that each integer will fit in your language's native signed integer type, may be more than 1 decimal digit long, and are signed.

Example input:

1 4 3 9 8 8 3 7 0
10 1 4 4 8 -1

Output

The output is any list-like of integers representing the set intersection of the two lists to any format desired (return value, stdio, etc.). There is no requirement that the output be sorted, though you are welcome to provide an implementation that happens to always be sorted. The output must form a valid un-ordered set (e.g. it must not contain any duplicate values).

Example test cases (note that the order of the output is not important):

First two lines are the input lists, third line is the output. (empty) denotes the empty list.

(empty)
(empty)
(empty)

1000
(empty)
(empty)

3 1 2 4 3 1 1 1 1 3
3 1 -1 0 8 3 3 1
1 3

1 2 1
3 3 4
(empty)

Scoring

This is code golf; shortest answer in bytes wins.

Standard loop-holes are prohibited. You may use any built-in features not designed for set-like operations.

Prohibited built-in features:

set creation/removing duplicates
set difference/intersection/union
Generalized membership testing (e.g. anything similar to the in keyword in Python, indexOf-like functions, etc). Note that the use of "foreach item in list" constructs are allowed (assuming they don't violate any of the other restrictions), despite the fact that Python re-uses the in keyword to create this construct.
These prohibited built-ins are "viral", i.e. if there's a larger built-in containing any of these sub-features, it is similarly prohibited (e.g. filtering by membership in a list).

Any built-ins not on the above list are allowed (ex. sorting, integer equality testing, list append/remove by index, filtering, etc.).

For example, take the following two example snippets (Python-like code):

# prohibited: filters by testing if each value in tmpList is a member of listA
result = tmpList.filter(listA)

# ok: filtering by a lambda which manually iterates over listA and checks for equality
def my_in_func(val, slist):
    for a in slist:
        if(val == a):
            return True
    return False
result = filter(lambda v: my_in_func(val, listA), tmpList)

You are welcome to implement any of these set-like features yourself and they will count towards your score.

Your solution should complete in a reasonable amount of time (say, less than a minutes on whatever hardware you have for two lists ~length 1000 each).

Haskell, 45 42 bytes

y#(e:s)=[e|any(==e)y,all(/=e)s]++y#s
_#x=x

Try it online!

Edit: -2 bytes thanks to @Ørjan Johansen, -1 byte thanks to @dfeuer.


Parentheses sequences in lexicographical order Challenge Taken from here and also here

An n parentheses sequence consists of n (s and n )s.

A valid parentheses sequence is defined as the following:

  You can find a way to repeat erasing adjacent pair of parentheses "()" until it becomes empty.

  For example, (()) is a valid parentheses, you can erase the pair on the 2nd and 3rd position and it becomes (), then you can make it empty.
  )()( is not a valid parentheses, after you erase the pair on the 2nd and 3rd position, it becomes )( and you cannot erase any more

Task

Given a number n you need to generate all correct parenthesis sequence in lexicographical order

Output can be an array, list or string (in this case a sequence per line)

You can use a different pair of parenthesis such as {}, [], () or any open-close sign

Example

n = 3

((()))
(()())
(())()
()(())
()()()

n = 2

(())
()()

Perl 6, 36 bytes

{grep {try !.EVAL},[X~] <[ ]>xx$_*2}

Try it online!

Finds all lexographically sorted combinations of \$2n\$ []s and filters the ones that EVAL correctly. Note that all valid combinations (even stuff like [][]) evaluate to [] (which is falsey, but we not it (!) to distinguish from try returning Nil)

Explanation:

{                                  }  # Anonymous code block
                        <[ ]>         # Create a list of ("[", "]")
                             xx$_*2   # Duplicate this 2n times
                   [X~]               # Find all possible combinations
 grep {          },                   # Filter from these
            .EVAL                     # The EVAL'd strings
       try !                          # That do not throw an error


All Aboard the ASCII Train All Aboard the ASCII Train!
    o O O   ___     ___     ___     ___     ___     ___     ___     ___     ___
   o       | C |   | O |   | D |   | E |   |   |   | G |   | O |   | L |   | F |
  TS__[O]  |___|   |___|   |___|   |___|   |___|   |___|   |___|   |___|   |___|
 {======|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|
./o--000'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'

You best be prepared to ride the train, because you're about to build the train you'll be riding on. Given a string s, output a fully formed train as depicted above. The first thing output is always the engine that'll be tugging your string along, as depicted alone below:
    o O O
   o
  TS__[O]
 {======|
./o--000'

Following the locomotive are rail-cars containing each character of your precious cargo. To save confusion when unloading, your company has tasked you with labeling the outside of these cars. The cars in question will always look like this:
   ___
  | # |
  |___|
_|"""""|
"`-0-0-'

Where the # is representative of the character that is inside the "cargo" hold. Chaining the engine to each car is also part of your job, as you've been tasked with overseeing the fluidity and success of this entire shipment. So, once you've labeled all the cars and got the engine on the tracks, you must ensure that the train is assembled and ready to roll.
Rules

The only input your program should take is a single string.
The engine must always be output, even if your shipment is empty.
Each car can only hold one character, don't push your luck you may damage the goods.
You need only support the following printable ASCII characters:
_-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
If you end up doing more, that's fine too, but this is the bare minimum.
1-2 trailing spaces are acceptable, as is a single trailing newline.
This is code-golfascii-art, shortest byte-count wins.

JavaScript (ES6), 149 144 bytes

s=>`    o O Oa   ___
   o     a  | $& |
  TS__[O]a  |___|
 {======|a_|"""""|
./o--000'a"\`-0-0-'`.replace(/a(.*)/g,(_,c)=>s.replace(/./g,c))

I don't think the engine itself can be compressed, but perhaps it's possible.

Test snippet

let f =

s=>`    o O Oa   ___
   o     a  | $& |
  TS__[O]a  |___|
 {======|a_|"""""|
./o--000'a"\`-0-0-'`.replace(/a(.*)/g,(_,c)=>s.replace(/./g,c))

O.innerHTML = f("CODE GOLF")
<input value="CODE GOLF" oninput="O.innerHTML=f(this.value.replace(/\n/g,'&lt;br&gt;'))">


Drawing 3d nets - Platonic solids This is a basic version of the rather more difficult Drawing 3d nets - Archimedean solids .

I have a weakness for 3d nets which when cut out and folded allow you to make 3d shapes out of paper or card.  The task is simple, write the shortest program you can that draws nets for the 5 Platonic solids. The output should be an image file in any sensible format of your choosing (png, jpg, etc.).

All five shapes are described at http://en.wikipedia.org/wiki/Platonic_solid . Their nets looks like this (taken from http://www.newscientist.com/gallery/unfolding-the-earth/2 ).

Input: An integer from 1 to 5.  Assume the shapes are numbered in order of the number of sides they have. So, 1 would be a tetrahedron and 5 the icosahedron.

Output: An image file containing the net for that shape. Just the outline including the internal lines is OK. There is no need to fill it in with colors

You can use any programming language you like as well as any library that was not made especially for this competition. Both should be available freely however (in both senses) online.

I will accept the answer with the smallest number of characters in exactly one week's time.

Winner. Only one entrant but it was wonderful. The winner is ... Raufio for what is my favourite piece of code golf ever.

Python, 456 429 381
import turtle as t
L="fl"
R="fr"
d=L*3+R*3
b=(d+R)*3
a=[b,120,L*3+"fflflffflflfrflflfffl"+R*4+"flf",90,b+"ffrfrflffrffrfrfrflflf",120,(R*5+L*5+R+L)*5+"rrfr"+L*5+R*2+L*2+R*4+"f",72,(d+"f")*5+"rfl"+((d+"b")*5)[:-1],120]
l=t.lt
f=t.fd
b=t.bk
r=t.rt
p=input()*2-2
t.setup(.9,.9)
t.goto(-200,150)
t.clear()
for c in a[p]:exec c+"(a[p+1])"
t.getscreen().getcanvas().postscript(file="o")

I implemented a primitive interpreter with l r f b as operators that move the turtle cursor around at the angle of the shapes. At one time, it turns only one angle. I compressed the strings by reusing strings (kind of like psuedo-subroutines), other than that, I didn't check to see if I was using the best path. It outputs to a postscript file.
A little explanation of un-golfed code:
import turtle as t
Left="fl"
Right="fr"
diamond= Left*3 + Right*3
tetrahedron=(d+R)*3 #used to be b

Imports the built-in turtle module and defines the macros that shorten the strings. The turtle module uses commands to move a 'turtle' around the screen (ie forward(100), left(90))
netList=[
   #tetrahedron
   tetrahedron,120,
   #cube
   Left*3+"fflflffflflfrflflfffl"+Right*4+"flf",90,
   #octohedron, builds off the tetrahedron
   tetrahedron+"ffrfrflffrffrfrfrflflf",120,
   #dodecahedron
   (Right*5 + Left*5 + Right + Left)*5
    +"rrfr"+
    Left*5 + Right*2 + Left*2 + Right*4 + "f",72,
   #icosahedron
   (diamond+"f")*5 +"rfl"+((diamond+"b")*5)[:-1],120
]

This list holds the angles and movement sequences. The tetrahedron was saved to reuse with the octohedren.
l=t.left
f=t.forward
b=t.back
r=t.right

This is the part that i like, it makes single character local functions so the calls can be shortened and automated through pre-defined strings.
input=int(raw_input())*2-2
t.setup(.9,.9)
t.goto(-200,150)
t.clear()

This starts by taking the input (between 1 and 5), and converting that to an index that points to the shape string in the netList. These setup turtle to show the whole net. These could be left out if the task was just to draw them, but since we need a picture output they are needed.
for command in netList[input]:
    exec command+"(netList[input+1])"
t.getscreen().getcanvas().postscript(file="o")

The for loop takes the commands in the command sequence string and executes them, so for a string like "fl", this executes "forward(angle);left(angle);" by calling the newly created local functions. the last line outputs a file called 'o' that is in postscript format format using turtle function.
To run:
Copy it into a file and run it from there. When you run it, it will wait for a number input between 1 and 5 (i just changed it so that it asks before setting up turtle). When you input a number, a window pops up and draws the net. if you want it to go faster you can add t.speed(200) before setup.
You can copy-paste it into the interpreter, but when raw_input() is called it consumes the next string you input "t.setup(.9,.9)" instead of a number. So if you do this, copy up until raw_input(), input a number, than copy paste the rest. It is intended to be run as a whole. Or you could copy it into a function and call it.
Here are it's outputs (converted from postscript):
Note: the position of these in the window has changed, but their overall shape is the same.

It's a little brute force for code golf, but I got tired of trying to find a consistent pattern between the shapes.


Take a stand against long lines Recently, someone proposed more stringent limits for Python's default line length:

Clearly, no program should ever use more than 80 characters per line, for a whole host of reasons. First and foremost, for readability and maintainability, it is important to have a solid standard, so we can adjust the width of our text editors appropriately. As a secondary benefit, code can easily be transferred onto media that may have restrictions, and where adding line-breaks can be distracting, like print pages for review in a meeting, or punch cards.
But is 80 characters too high? Some suggest 79, or even as low as 75, to allow for an 80 character wide terminal to fit the code with a few columns devoted to line numbers. Clearly, ultimately, lower is better, as lower limits allow for the code to be used in more situations without reformatting.
Introducing the max6 standard

Your goal is to find and demonstrate the minimum line length required by Your Favorite Language by writing a FizzBuzz variant with the fewest number of characters in any line.
Input
An integer, n, via any desired method.
Output
Print the numbers from 1 to n, (n ≥ 1, n ∈ ℤ)  separated by line breaks, except:

for multiples of 3 print "Apple"
for multiples of 5 print "Pie"
for multiples of both 3 and 5 print "ApplePie"

Scoring
The maximum line length in bytes, not including the line break (Cr, CrLf, Lf, or other system standard break, specify, as desired), and the total code length in bytes as a tiebreaker.
Rules
All line breaks must be meaningful. Line breaks that can be removed and adjacent lines directly concatenated without an impact on the output, must be removed.

><>, 1 byte per line, 243 161 135 bytes

-26 bytes thanks to Jo King!

2D languages FTW! Although writing loops and branches using goto instructions instead of the 2D structure is not fun.

v
l
:
:
3
%
:
&
0
4
7
*
&
?
.
~
~
"
e
l
p
p
A
"
o
o
o
o
o
$
5
%
:
&
0
a
5
*
&
?
.
~
~
"
e
i
P
"
o
o
o
*
0
@
?
n
?
~
l
{
:
}
=
?
;
a
o
1

Try it online!, or watch it at the fish playground!

The fish swims downward along the code, using conditional gotos to skip things depending on what divides the accumulator.

I believe this meets the spec: whatever newlines are removed, the fish always hits the initial v (the only direction-changing instruction present), so the fish always swims downwards in the first column. Thus deleting a newline has the effect of simply removing the next character from the fish's path, and I don't think you can remove any of the characters without changing the output.


Jimmy needs a new pair of shoes! Jimmy has had a busy last week with all these platforms and ropes, and poor Jimmy doesn't even have legs or feet to stand on!

Your job is to take a string containing multiple Jimmys and give them legs and shoes!

Get input in the form of a Jimmy String

Jimmy String => /o\  /o\   /o\

containing only /o\ and

give each Jimmy in the input a pair of feet that look like this:

 /o\
_/ \_

Turn the inputed floating head Jimmy string into Jimmy with feet string, like so:

// Input

       /o\   /o\          /o\

// Output

       /o\   /o\          /o\
      _/ \_ _/ \_        _/ \_

If 2 Jimmys are close together they must move over to make room,
Jimmys will always move towards the right to make room for other Jimmys.

// Input

/o\/o\

// Output

 /o\  /o\
_/ \__/ \_

Other Jimmys that are further away must not be moved unless necessary

// Input

/o\/o\      /o\

// Output

 /o\  /o\   /o\
_/ \__/ \_ _/ \_

// Input

/o\/o\    /o\

// Output

 /o\  /o\  /o\
_/ \__/ \__/ \_

Standard rules and loopholes apply,

This is code-golf, so may the shortest answer win.

Python 2, 131 120 115 114 121 118 bytes

o=1;W=[]
for g in map(len,input().split('/o\\')):W+=[' '*(g-o)];o=max(o-g,0)+2
for q in' /o\ ','_/ \_':print q.join(W)

Try it online!

4 bytes thx to movatica; 10 bytes lost for bug fix.


Find amount of heads and tails from percentages Note: as this question has been marked as a duplicate, I have accepted an answer. However, I will still check this question if users can find a shorter way of doing it, and accept that answer.

Given two numbers (which are multiples of 0.5) representing heads-percentage and tails-percentage from a series of coin-flipping, output the minimum amounts of heads and tails to produce percentages such as those. Input and output can be in any form. However, output must be in a readable format (Good examples are x y, [x y], etc).

Examples:

Input: 25 75 (25% heads, 75% tails) Output: 1 3 (an output of 25 75 is invalid since that is not the minimum amounts of heads and tails to produce those percentages)
Input: 30 70 (30% heads, 70% tails) Output: 3 7
Input: 99.5 0.5 (99.5% heads, 0.5% tails) Output: 199 1

You may assume that there will always be a digit before and after a decimal point in an input (no .5s or 15.s). You may also assume the input adds up to 100%. This is code-golf, shortest code in bytes wins!

Dyalog APL, 3 bytes

,÷∨

This is a dyadic function train that accepts the percentages as left and right arguments:

┌─┼─┐
, ÷ ∨

It is equivalent to the following, train-less function:

{(⍺,⍵)÷⍺∨⍵}

Try it online on TryAPL.

How it works

  ∨  Compute the GCD of both arguments.
,    Concatenate both arguments.
 ÷   Divide the latter by the former.


Make a Snake Parser! Snakes look like this:
      >>>v
@     ^  v
^  >>>^  v
^        v
^<<<<<<<<<

The snake can cross over itself as in this case:
 @
 ^
>^>v
 ^<<

For a crossover to be valid, the characters on either side must be moving the same direction. The case of
 @
>^v
 ^<

can be considered unclear and invalid.
The output is a string of WASD representing going from the head to the tail  (@).
Given a snake that doesn't backtrack and isn't ambiguous, can you write a program that will output the string of moves that the snake takes?
This is code-golf, so shortest answer wins!
Test cases:
(Note: The @ can be replaced with any character not in v^<>)
Input:
>>>>v
    v
  v<<  @
  v    ^
  >>>>>^

Output: ddddssaassdddddww

Input:
@>>v
^  v
^  v
^<<<

Output: dddsssaaawww

Input:
>>>v
   v       @
   v       ^
   >>>>v   ^
       >>>>^

Output: dddsssddddsddddwww

Input:
@<< v
  ^ v
v<^<<
v ^
>>^

Output: ssaaaassddwwwwaa

Input:
@v<v
^v^v
^v^<
^<

Output: ssawwasssawww

Java, 626 539 536 529 bytes

-87 bytes by saving a few in a lot of places. Thanks goes to Mr Public for pointing some out.

-3 bytes because I can't manage to remove all the spaces first try (thanks mbomb007)

+8 bytes to fix for this case:

@v<v
^v^v
^v^<
^<

-15 bytes by front-loading variable declaration

s->{String o="",t;String[]p=s.split("\n");int h=p.length,w=p[0].length(),y=0,x,b=0,a,n,m;char[][]d=new char[h][w];for(;y<h;y++)for(x=0;x<w;x++){d[y][x]=p[y].charAt(x);if(d[y][x]=='@')d[y][x]=' ';}for(;b<h;b++)for(a=0;a<w;a++){t="";x=a;y=b;n=0;m=0;while(!(y<0|y>h|x<0|x>w||d[y][x]==' ')){if(y+m>=0&y+m<h&x+n>=0&x+n<w&&d[y+m][x+n]==d[y-m][x-n])d[y][x]=d[y-m][x-n];n=m=0;switch(d[y][x]){case'^':t+="W";m--;break;case'<':t+="A";n--;break;case'v':t+="S";m++;break;case'>':t+="D";n++;}x+=n;y+=m;}o=t.length()>o.length()?t:o;}return o;}

Readable version:

static Function<String,String> parser = snake -> {
    // declare all variables in one place to minimize declaration overhead
    String output = "", path;
    String[] split = snake.split("\n");
    int h=split.length, w=split[0].length(), y=0, x, startY=0, startX, dx, dy;
    char[][] board = new char[h][w];
    // setup char[][] board
    for (; y<h; y++)
        for (x=0; x<w; x++) {
            board[y][x]=split[y].charAt(x);
            if(board[y][x]=='@')board[y][x]=' ';
        }
    // find the longest possible path
    for (; startY<h; startY++)
        for (startX=0; startX<w; startX++) {
            path = "";
            x=startX; y=startY; dx=0; dy=0;
            while (!(y<0 | y>h | x<0 | x>w || board[y][x] == ' ')) {
                if (y + dy >= 0 & y + dy < h & x + dx >= 0 & x + dx < w
                        && board[y + dy][x + dx] == board[y - dy][x - dx]) {
                    board[y][x] = board[y - dy][x - dx];
                } dx = dy = 0;
                switch(board[y][x]) {
                    case '^':path+="W";dy--;break;
                    case '<':path+="A";dx--;break;
                    case 'v':path+="S";dy++;break;
                    case '>':path+="D";dx++;break;
                }
                x+=dx; y+=dy;
            }
            output = path.length()>output.length()?path:output;
        }
    return output;
};

Takes a String like v  @\n>>>^.
Creates a path starting at each coordinate, then returns the longest one.
The lookahead required for the overlapping paths was the hardest part.


Calculate 500 digits of pi Write a program to calculate the first 500 digits of pi, meeting the rules below:

It must be less than 500 characters in length.
It cannot include "pi", "math.pi" or similar pi constants, nor may it call a library function to calculate pi.
It may not use the digits "3", "1" and "4" consecutively.
It must execute in a reasonable time (under 1 minute) on a modern computer.

The shortest program wins.

Golfscript - 29 chars

6666,-2%{2+.2/@*\/9)499?2*+}*

I will post analysis later


Charlie and the evil hyphen Here's the phonetic alphabet:

Alfa
Bravo
Charlie
Delta
Echo
Foxtrot
Golf
Hotel
India
Juliett
Kilo
Lima
Mike
November
Oscar
Papa
Quebec
Romeo
Sierra
Tango
Uniform
Victor
Whiskey
X-ray
Yankee
Zulu

In the fewest bytes possible:

Input will be these words in a random  order, with the first letters removed.
Your goal is to arrange the words back to their original order using only the letters you now have. In other words: work out how '[A]lfa' comes before '[B]ravo', and so on. Your code must not refer the original list, index keys, etc.
Restore the original first letters of each word.

Rules

The hyphen in X-ray is probably evil, but needs to stay, for I am also evil.
The result can be a string (comma or newline separated, for example), or an array.
The spellings and letter cases are non-negotiable.
No need to show example output in answers.

Jelly, 21 bytes

“ṣȤW¶¬þḷẒ⁶4ẹ’Œ?ịṢØA;"

Input and output are string arrays.

Try it online!

Background

While there are 26! = 403291461126605635584000000 different inputs, we can sort the input so we have to deal only with one permutation of this phonetic alphabet. Sorting lexicographically, we get

-ray
ango
ankee
apa
cho
elta
harlie
hiskey
ictor
ierra
ike
ilo
ima
lfa
ndia
niform
olf
omeo
otel
ovember
oxtrot
ravo
scar
uebec
uliett
ulu

We can simply index into this array to sort it by the removed letters. The (1-based) indices are

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

All that's left to do is to prepend the uppercase letters of the alphabet to the strings in the result.

How it works

“ṣȤW¶¬þḷẒ⁶4ẹ’Œ?ịṢØA;"  Main link. Argument: A (string array)

“ṣȤW¶¬þḷẒ⁶4ẹ’          Replace the characters by their indices in Jelly's code page
                       and convert the result from bijective base 250 to integer.
                       This yields k := 214215675539094608445950965.
             Œ?        Construct the k-th permutation (sorted lexicographically)
                       of [1, ..., n], with minimal n (26 here). This yields
                       [14, 22,  7,  6,  5, 21, 17, 19, 15, 25, 12, 13, 11,
                        20, 23,  4, 24, 18, 10,  2, 16,  9,  8,  1,  3, 26].
                Ṣ      Yield A, sorted.
               ị       For each j in the array to the left, select the j-th string
                       from the array to the right.
                 ØA    Yield "ABCDEFGHIJKLMNOPQRSTUVWXYZ".
                   ;"  Concatenate zipwith; prepend the j-th character from the
                       alphabet to the j-th string of the permuted input.


Find the Needle in the Haystack (Robbers) This is part of a cops-and-robbers challenge. Go here for the cops' part.

The Robbers' Challenge

A cop's answer can be cracked by removing any subset of characters from the Haystack program, so that it outputs Needle instead of Haystack (while still being a valid submission in the same language). You don't have to find the exact same solution as the cop intended, as long as yours is valid by the above constraints.

If you manage this, post an answer with the solution, linking to the cop's answer, and leave a comment on the cop's answer linking back to yours.

The robber who cracks the most cop answers wins. Ties are broken by the sum of sizes of the cracked cop answers (in favour of the robber who cracks longer submissions).

Each cop answer can only be cracked once, and of course, you're not allowed to crack your own answer. If the cop's answer turns out to be invalid before or after being cracked, it is not counted towards the robber's score.

Examples

Here are a couple of simple examples in different languages:

Ruby

Haystack: puts 1>0?"Haystack":"Needle"
Delete:        XXXXXXXXXXXXXXX
Needle:   puts "Needle"

Python 2

Haystack: print "kcatsyaHeldeeN"[-7::-1]
Delete:          XXXXXXXX        XX
Needle:   print "eldeeN"[::-1]

Note that the subset of removed characters doesn't have to be contiguous.

JavaScript, 85 bytes (ES6)

Cracks Arnauld's answer

f=(k=b=x=35)=>x--?f(k*4853461&268435455):k&2?'N'+(k^12408877).toString(b):'Haystack'

"Needle" demo

f=(k=b=x=35)=>x--?f(k*4853461&268435455):k&2?'N'+(k^12408877).toString(b):'Haystack'

console.log(f())

Explanation

The original function was:

f=(k=b=x=35)=>x--?f(k*74837258394056219&268435455):k&2?'N'+(k^124038877).toString(b):'Haystack'

which is more readable as:

f = (k=b=x=35) => {
    if (x--) {
        return f(k*74837258394056219&268435455);
    } else {
        if (k&2) {
            return 'N'+(k^124038877).toString(b);
        } else {
            return 'Haystack';
        }
    }
}

Note that when n=21625674, then n.toString(35) is 'eedle'.

The 35 in the input probably cannot be changed to a subset (because we want a base large enough to contain all the letters 'del', so we need a base that's at least 22). So the numbers to change are 74837258394056219, 268435455, and 124038877. We want to replace them with numbers a, b, c, each formed with a subset of the digits of the original numbers, such that the function g(k) = (k * a & b), starting with k=35 and iterated 35 times, and then XORed with c, gives 21625674.

For this one, after thinking a bit, as the lengths are small (the maximal a has length 17, b and c have length 9), I just used brute-force :-) Wrote a C++ program to generate all possible numbers a, b, c formed as subsets of the original numbers, iterate through all a and b, and check whether the required c was in the set. Runs in about 15 seconds, and the only output is a=4853461, b=268435455, c=12408877 (turns out the number b doesn't need to be changed). I'm not sure whether there's a more clever way of inverting this function.


N numbers closest to zero staying balanced Objective: Given a positive integer n:

If n is odd, output the list of n numbers closest to 0 in increasing order
If n is even, output a Falsey value.

Test cases:

5 -> [-2,-1,0,1,2]
4 -> false (or any Falsey value)
1 -> [0]

Reference implementation

function update(){
  var num = +document.getElementById("yield").value;
  if(num){
    var out = document.getElementById("output");
    if(num % 2 == 1){
      // base is balanced
      var baseArr = [];
      for(var i=0;i<num;i++){
        baseArr.push(i-Math.floor(num/2));
      }
      out.innerHTML = baseArr.join(" ");
    } else {
      out.innerHTML = "false";
    }
  } else {
    out.innerHTML = "enter input";
  }
}

setInterval(update,1);
* {
  font-family: "Constantia", "Consolas", monospace;
}

[type="number"] {
  width: 10px;
  width: 2em;
}

#output {
  font-family: "Consolas", monospace;
}
Input: <input type="number" id="yield" value="3"> is enter input

Pyth, 10 bytes

*-R/Q2Q%Q2

Try it online.

How it works

            (implicit) Store the input in Q.
   /Q2      Calculate Q/2 (integer division).
 -R   Q     Subtract that value (-R) from each element in [0, ..., Q-1] (Q).
*      %Q2  Repeat the resulting array Q%2 times.


False Positives on an Integer Lattice Leaderboard

 User            Language      Score
 =========================================
 Ell             C++11         293,619,555
 feersum         C++11         100,993,667
 Ell             C++11          78,824,732
 Geobits         Java           27,817,255
 Ell             Python         27,797,402
 Peter Taylor    Java                2,468
 <reference>     Julia                 530

Background

When working on a 2-D grid of integer coordinates, you sometimes want to know whether two vectors (with integer components) have the same magnitude. Of course, in Euclidean geometry the magnitude of a vector (x,y) is given by

√(x² + y²)

So a naive implementation might compute this value for both vectors and compare the results. Not only does that incur an unnecessary square root computation, it also causes trouble with floating point inaccuracies, which might yield false positives: vectors whose magnitudes are different, but where the significant digits in the floating point representation are all identical.

For the purposes of this challenge, we define a false positive as a pair of coordinate pairs (a,b) and (c,d) for which:

Their squared magnitude is different when represented as 64-bit unsigned integers.
Their magnitude is identical when represented as 64-bit binary floating point number and computed via a  64-bit square root (as per IEEE 754).

As an example, using 16-bit representations (instead of 64), the smallest1 pair of vectors which yields a false positive is

(25,20) and (32,0)

Their squared squared magnitudes are 1025 and 1024. Taking the square root yields

32.01562118716424 and 32.0

But in 16-bit floats both of these get truncated to 32.0.

Likewise, the smallest2 pair yielding a false positive for 32-bit representations is

(1659,1220) and (1951,659)

1"Smallest" as measured by their 16-bit floating point magnitude.
2"Smallest" as measured by their 32-bit floating point magnitude.

Lastly, here are a handful of valid 64-bit cases:

 (51594363,51594339) and (54792160,48184783)
 (54356775,54353746) and (54620742,54088476)
 (54197313,46971217) and (51758889,49645356)
 (67102042,  956863) and (67108864,       6) *

* The last case is one of several with the smallest possible magnitude for 64-bit false positives.

The Challenge

In less than 10,000 bytes of code, using a single thread, you're to find as many false positives for 64-bit (binary) floating point numbers  in the coordinate range 0 ≤ y ≤ x (that is, only within the first octant of the Euclidian plane) such that x² + y² ≤ 253 within 10 minutes. If two submissions tie for the same number of pairs, the tie breaker is the actual time taken to find the last of those pairs.

Your program must not use more than 4 GB of memory at any time (for practical reasons).

It must be possible to run your program in two modes: one which outputs every pair as it finds it, and one which only outputs the number of found pairs at the end. The first will be used to verify the validity of your pairs (by looking at some sample of outputs) and the second will be used for actually timing your submission. Note that the printing must be the only difference. In particular, the counting program may not hardcode the number of pairs it could find. It must still perform the same loop that would be used to print all the numbers, and only omit the printing itself!

I will test all submissions on my Windows 8 laptop, so please ask in the comments if you want to use some not-too-common language.

Note that pairs must not be counted twice under switching of the first and second coordinate pair.

Note also that I will run your process via a Ruby controller, which will kill your process if it hasn't finished after 10 minutes. Make sure to output the number of pairs found by then. You can either keep track of time yourself and print the result just before the 10 minutes elapse, or you just output the number of pairs found sporadically, and I will take the last such number as your score.

Python, 27,797,402
Just to set the bar a little higher...
from sys import argv
verbose = len(argv) > 1
found = 0
for x in xrange(67108864, 94906266):
    found += 1
    if verbose:
        print "(%d, 0) (%d, 1)" % (x, x)
print found

It's easy to verify that for all 67,108,864 <= x <= 94,906,265 = floor(sqrt(253)) the pairs (x, 0) and (x, 1) are false positives.
Why it works: 67,108,864 = 226. Therfore, all numbers x in the above range are of the form 226 + x' for some 0 <= x' < 226.
For all positive e, (x + e)2 = x2 + 2xe + e2 = x2 + 227e + 2x'e + e2.
If we want to have  (x + e)2 = x2 + 1 we need at least 227e <= 1, that is, e <= 2-27
However, since the mantissa of double-precision floating point numbers is 52-bit wide, the smallest e such that x + e > x is e = 226 - 52 = 2-26.
In other words, the smallest representable number greater than x is x + 2-26 while the result of sqrt(x2 + 1) is at most x + 2-27.
Since the default IEEE-754 rounding mode is round-to-nearest; ties-to-even, it will always round to x and never to x + 2-26 (where the tie-break is really only relevant for x = 67,108,864, if at all. Any larger number will round to x regardless).

C++, 75,000,000+
Recall that 32 + 42 = 52.
What this means is that the point (4, 3) lies on the circle of radius 5 centered around the origin.
Actually, for all integers n, (4n, 3n) lies on such circle of radius 5n.
For large enough n (namely, such that 5n >= 226), we already know a false-positive for all points on this circle: (5n, 1).
Great! That's another 27,797,402 / 5 free false-positive pairs right there!
But why stop here? (3, 4, 5) is not the only such triplet.
This program looks for all positive integer triplets (a, b, c) such that a2 + b2 = c2, and counts false-positives in this fashion.
It gets to 70,000,000 false-positives pretty fast but then slows down considerably as the numbers grow.
Compile with g++ flspos.cpp -oflspos -std=c++11 -msse2 -mfpmath=sse -O3.
To verify the results, add -DVERIFY (this will be notably slower.)
Run with flspos. Any command-line argument for verbose mode.
#include <cstdio>
#include <cmath>
#include <cfloat>

using namespace std;

/* Make sure we actually work with 64-bit precision */
#if defined(VERIFY) && FLT_EVAL_METHOD != 0 && FLT_EVAL_METHOD != 1
#   error "invalid FLT_EVAL_METHOD (did you forget `-msse2 -mfpmath=sse'?)"
#endif

template <typename T> inline long long sqr(T x) { return 1ll * x * x; }
template <typename T>
T gcd(T a, T b) { while (b) { T t = a; a = b; b = t % b; } return a; }

int main(int argc, const char* argv[]) {
    const bool verbose = argc > 1;

    const int min = 1 << 26;
    const int max = sqrt(1ll << 53);

    int found = 0;
    auto add = [=, &found] (int x1, int y1, int x2, int y2) {
#ifdef VERIFY
        auto n1 = sqr(x1) + sqr(y1), n2 = sqr(x2) + sqr(y2);
        if (n1 == n2 || sqrt(n1) != sqrt(n2)) {
            fprintf(stderr, "Wrong false-positive: (%d, %d) (%d, %d)\n",
                    x1, y1, x2, y2);
            return;
        }
#endif
        if (verbose) printf("(%d, %d) (%d, %d)\n", x1, x2, y1, y2);
        ++found;
    };

    for (int x = min; x <= max; ++x) add(x, 0,    x, 1);

    for (int a = 1; a < max; ++a) {
        auto a2b2 = sqr(a) + 1;
        for (int b = 1; b <= a; a2b2 += 2 * b + 1, ++b) {
            int c = sqrt(a2b2);
            if (a2b2 == sqr(c) && gcd(a, b) == 1) {
                int max_c = max / c;
                for (int n = (min + c - 1) / c; n <= max_c; ++n)
                    add(n * a, n * b,    n * c, 1);
            }
        }

        if (a % 512 == 0) printf("%d\n", found), fflush(stdout);
    }

    printf("%d\n", found);
}


Swap contents of two files This is a code-golf question.  You need to take the contents of two separate files (i.txt and o.txt) and swap them.  You can create a third file to help you with the process, but have your program delete it after the file contents are swapped.  Renaming the files is now allowed again.

Programs must work for any file content.

Shortest code wins, all eligible submissions will be up-voted.


Create a FizzBuzz compiler Welcome to the world of compiler golf. Your task is to write a program that generates another program to play a variant of FizzBuzz on spec.

Your compiler

Write a compiler that generates variants of the FizzBuzz program to spec. The spec of this variant is expressed in the form of an array of integer/string pairs.

The input may be in any form that is convenient to your language. (My examples use n:xxxx, but this is just for illustrative purposes.)
Each integer input may only be used once per invocation of your compiler.
The integer of each pair will have a value of at least one.
The string of each pair will be made of only exactly four ASCII letters.
The output must be a single complete program that conforms to the rules below.
The output may be in any convenient form, as long as it is a textual program. (So no returning lambda expressions.)

Behavior is undefined for inputs not conforming to the above rules.

Your generated FizzBuzz program

The program generated by your compiler will take a single integer, n, as input. It will output a sequence of numbers starting from one up to and including n, replacing numbers with FizzBuzz strings when required.

The generated program must be in the same language as the compiler.
The input n may be in any form convenient to your language.
n will have a value of at least one.
A number that is a multiple of at least one of the integers input to the compiler must be replaced by all of the strings paired with those integers joined together.
A number that is not to be replaced by a FizzBuzz string must be output in decimal ASCII.

For example;

> GenFizzBuzz 3:Fizz 5:Buzz
> a.out 5
1
2
Fizz
4
Buzz

Scoring

Your entry will be scored by the length of the programs your compiler generates added to the length of your compiler. Run your compiler many times with each the following parameters and add the lengths of the generated programs together with the length of the compiler to find your score.

Just Count. (No inputs - The generated program will count 1 to n without replacements.)
Just Golf. (1:Golf - The generated program will output "Golf" n times.)
Classic FizzBuzz. (3:Fizz, 5:Buzz)

(Note that your compiler is required to generate code for any valid input, not just these listed.)

Python 3 - 168 162 + 230 = 392
Oh, Python, you try so hard, but multiplying the import sys;sys.argv stuff by 4 really hurts!
import sys;a=eval(sys.argv[1])
print("import sys\nfor i in range(1,int(sys.argv[1])+1):print("+"+".join('"%s"*(i%%%d==0)'%t for t in a)+(a and"or str(i))"or"i)"))

Output programs:
import sys
for i in range(1,int(sys.argv[1])+1):print(i)
import sys
for i in range(1,int(sys.argv[1])+1):print("Golf"*(i%1==0)or str(i))
import sys
for i in range(1,int(sys.argv[1])+1):print("Fizz"*(i%3==0)+"Buzz"*(i%5==0)or str(i))

Expected input for the main program is an eval-able sequence of Python tuples or '()' for no input. (You did say "convenient".) Example input: '()', '("Golf",1),', '("Fizz",3),("Buzz",5)' Note quoting for shell and trailing comma for one input.

Fixed 1am mistake by changing from dict (undefined ordering!) to tuples.

Expected input for the other programs is just the number


Balanced Ternary Converter Credits for the challenge idea go to @AndrewPiliser. His original proposal in the sandbox was abandoned and since he has not been active here for several months, I have taken over the challenge.

Balanced ternary is a non-standard numeral system. It is like ternary in that the digits increase in value by a factor of 3 as you go further to the left - so 100 is 9 and 1001 is 28.

However, instead of having values of 0, 1 and 2, the digits have values of -1, 0, and 1. (You can still use this to express any integer.)

For this challenge, the digit meaning +1 will be written as +, -1 will be written as -, and 0 is just 0. Balanced ternary does not use the - symbol in front of numbers to negate them like other numeral systems do - see examples.

Your task is to write a complete program which takes a 32-bit decimal signed integer as input and converts it to balanced ternary. No built-in base conversion functions of any sort are allowed (Mathematica probably has one...). Input can be on standard input, command-line arguments, etc.

Leading zeroes may be present in input but not in output, unless the input is 0, in which case the output should also be 0.

Examples

These are conversions from balanced ternary to decimal; you will have to convert the other way.

+0- = 1*3^2 + 0*3^1 + -1*3^0 = 9 + 0 + -1 = 8
+-0+ = 1*3^3 + -1*3^2 + 0*3^1 + 1*3^0 = 27 + -9 + 0 + 1 = 19
-+++ = -1*3^3 + 1*3^2 + 1*3^1 + 1*3^0 = -27 + 9 + 3 + 1 = -14

Python 2: 58 chars

n=input()
s=""
while n:s="0+-"[n%3]+s;n=-~n/3
print s or 0

Generates the balanced ternary digit-by-digit from the end. The last digit is given by the residue n%3 being -1,0, or +1. We then remove the last digit and divide by 3 using Python's floor-divide n=(n+1)/3. Then, we proceed recursively with the new last digit until the number is 0.

A special case is needed for the input 0 to give 0 rather than the empty string.

The specs don't allow this, but if one could write a function instead of a program and output the empty string for 0, a 40 char solution would be possible.

g=lambda n:n and g(-~n/3)+"0+-"[n%3]or""


Necklace stones puzzle Given a necklace with color stones (yellow, white, brown, etc.) of at least two different colors, we describe that necklace using letters that correspond to each color, choosing an arbitrary starting point.

We try to answer these questions:

How many distinct colors does the necklace have?
What's the length of the longest segment of contiguous stones of the same color?
If necklace can be cut at any position, removing all contiguous stones of the same color immediately to the left and to the right of the cutting point, what's the biggest amount of stones which could be taken?

Note that the necklace is considered cyclical. Therefore, letters at the start and end of the given input string can form a single sequence (see second test case below).

Test cases

aaaab -> 2 4 5
aabaa -> 2 4 5
uamaaauumaummuauamumummmmua -> 3 4 5

What's the shortest code to achieve this? Any language is welcome.

CJam, 28 bytes

r__&,a\2*e`0f=_2ew::+]::e>S*

Try it online.

How it works

r    e# Read a whitespace-separated token from STDIN.
__   e# Push two copies.
&    e# Intersect two of the copies (removes duplicates).
,a   e# Calculate the length and wrap it in an array.
\    e# Swap the array with the input string.
2*   e# Repeat the input string two times.
e`   e# Perform run-length encoding.
0f=  e# Keep only the repetitions.
_2ew e# Copy and push the overlapping slices of length two.
::+  e# Add the integers in the resulting slices.
]    e# Wrap the entire stack in an array.
::e> e# Compute the maximum of each of the three arrays.
S*   e# Join, separating by spaces.


Reverse Regular expressions The idea here is to write a little segment that will spit out regular expression patterns when given a string that matches them.

As you might have guessed, this will be a popularity contest, and I'll accept whichever answer has the most upvotes by March 7th

pseudocode Example:

print(reverseRegex('dog'));
//prints /[a-z]{3}/, /dog/, and a bunch other stuff

EDIT: The regular expressions spat out should not exceed 3 times the input string's length

Ruby

def esc chr
  '\\[]'.index(chr) ? "\\#{chr}" : chr
end

def reverse_regex str
  ords = str.chars.to_a.uniq.map(&:ord).sort
  prev = ords.first
  ranges = ords.slice_before{|x|
    prev, prev2 = x, prev
    prev2 + 1 != x
  }.map{|x| x[0]..x[-1]}

  reversed = "[#{ranges.map{|c|esc(c.min.chr) + (c.min == c.max ? '' : (c.min + 1 == c.max ? '' : '-') + esc(c.max.chr))}*''}]{#{str.size}}"
  reversed.size > str.size * 3 ? /#{Regexp.escape str}/ : /#{reversed}/
end

Sample outputs:

reverse_regex 'dogs are delicious'
  => /[ ac-egilorsu]{18}/
reverse_regex 'a'
  => /a/
reverse_regex ''
  => //
reverse_regex 'This is a test: []{}.*potato'
  => /[ *.:T\[\]aehiopst{}]{28}/

Now with ranges!

These regexen match the entire string (if you added ^...$ it would still match, but I'm too lazy to do that and add the required length check). Also, I'm assuming the /s don't count for length. (If they did, it would be impossible for input of empty string.)


Make me a scrolling marquee Introduction

Remember the roaring 80's? I mean, you know, like 30 years ago? No cell phones, no internet, no ATM's, fluorescent clothing (what was that?!) and scrolling marqee's! No, no, no! Not the online ones, but real ones, With LED lights.

Since I'm in a nostalgic mood, I'd like you to create a scrolling marquee.

Challenge

Create a program where you can enter a one line string. You program needs to create a 80 character wide scrolling marquee, repeating the text if necessary.

Rules

The user must be able to enter a string to your program as input. The string can be a command line parameter or a string entered while running the program.
Your program must continuously print a string of exactly 80 (visible) characters.
The string must be updated every 0.1 second (more or less; I won't be timing it), shifting the characters every iteration one position to the left.
The string "rotates". At the end of the user supplied string, another instance of the string must appear.
You program must print it's output on one line, without linefeeds (use a '\r' instead of a '\n')
Your program must run ad infinitum, until an user interrupt.
This is a codegolf, so shortest code in bytes wins.
There is a 10% bonus (rounded up to the next integer) for printing in red on a black background.
Standard loopholes apply.

Reference implementation in Python 2.7

This program isn't golfed, but it provides a reference implementation (and thus an upper limit to the size).

import time,sys
s=raw_input()*99
while 1:
    for i in range(80):
        print s[i:i+80]+'\r',
        sys.stdout.flush()
        time.sleep(0.1)

PowerShell, 118 113 112 108 102 101 99  96 - 10% = 86

Code

$s=(Read-Host)*180;for(){Write-Host($s.substring(($i=++$i%80),80)+"`r")-N -F R -B 0;sleep -m 99}

With the caveat that it now begins the first loop with the second character; The rules don't say it has to start from the front of the string, and the first one is included overall, so that's fine by me. I will get it to 100 chars somehow - edit: thanks @ConnorLSW for the edits to get it below 100.

Instructions

Run PowerShell (normal console, it doesn't work in PowerShell ISE)
Paste the single line version into PoSH, press enter
Type a message, press enter
Ctrl-C to break

Output

Notes

A more readable version with the variable names and parameters filled out a bit:

$test = (Read-Host) * 180
for () {
    Write-Host ($text.substring(($i=++$i%80), 80)+"`r") -NoNewLine -ForegroundColor Red -BackgroundColor Black
    sleep -Miliseconds 99
}

The parameters only need to be long enough to be unique, so -F R is unique enough to set a Red ForegroundColor, for example.
'Black' has to be 'Bla' to be unique compared to 'Blue', but -B 0 sets it to color Enum value 0 which is interpreted as Black.

Alternative, more 'correct' marquee:

The reference code doesn't handle strings longer than 80 characters nicely, skipping anything in the message past ~160 characters, and it glitch-resets every 99*len(string) characters. e.g. if the sign width was 5 characters long, it does this:

   here is my long test input
 0 |here |
 1  |ere i|          ^^^^ never shown
 2   |re is|
 3    |e is |
 4     | is m|
 0 |here |
 1  |ere i|
    ...

This version indexes modulo the text length instead of the sign width, so it runs through the whole string. 106 - 10% = 95 chars.

$l=($s=Read-Host).Length;for(){Write-Host(($s*160).substring(($i=++$i%$l),80)+"`r")-N -F R -B 0;sleep -m 99}

Alternative: sign which cycles like the .gif in the question, 118-10%=106

Because it looks better.

$s=' '*80+(read-host)+' '*80;for(){write-host($s.Substring(($i=++$i%($s.length-80)),80)+"`r")-N -F R -B 0;sleep -m 99}


Compare the averages of my lists Getting the average of a list  (e.g [2,6,7])

Get the length of the list: [2,6,7] -> 3
Sum the numbers in the list: 2 + 6 + 7 = 15.
Divide the sum by their count: 15 / 3 = 5.

You should compare the averages of two lists of positive integers N and M, by returning a value if N has a higher average, another value if M has a higher average, and another one in case of a tie.

I/O rules
All the standard Input and Output methods are allowed.
Input
You may take input as two separate lists, a nested list, or anything else you consider suitable for the task. Please specify the format.
Output
The values provided have to be distinct and must consist of at least one non-whitespace character. Also, they must be consistent between runs (a single value for N, a single value for M, a single value for Tie). Please specify those in your answer. The values can be non-empty Strings, Bool values, Integers, or anything you consider suitable.

Specs

The lists will not necessarily have equal length.

You are guaranteed that the lists are non-empty.

Test Cases
I chose the values N wins, M wins and Tie, which are pretty much self-evident.

N, M                     ->   Output     (Averages)

[7], [6]                 -> N wins  (N has 7, M has 6 )
[4,5], [4,4]             -> N wins  (N has 4.5, M has 4)
[2,3,4], [4,5,6]         -> M wins  (N has 3, M has 5)
[4,1,3], [7,3,2,1,1,2]   -> Tie     (both have 2.666...)
[100,390,1], [89,82,89]  -> N wins  (N has 163.666..., M has 86.666...)
[92,892], [892,92]       -> Tie     (lists are basically identical)
[10,182], [12,78,203,91] -> Tie     (both have 96)

Default Loopholes apply. Explanations are encouraged! This is code-golf, so the shortest code in bytes wins!

Mathematica, 15 bytes

Order@@Mean/@#&

Try it online!

Function which expects a list of two lists. Mean/@# takes the arithmetic mean of each list in the input, then those means are passed into Order, which returns -1 if the first list wins, 0 if there is a tie, and 1 if the second list wins.


Turn nouns into plurals Your task is to take as input an English noun and output its plural. To win the challenge you must trade off code length against accuracy.

Entries will be scored according to this comma-separated list of 95642 English nouns and their plurals. Your score is the length of your code in bytes, plus the number of nouns in this file that it does not correctly pluralise. If you manage to correctly pluralise every single line in the file then you may apply a 50% bonus. (I don't expect anyone to claim this, but you never know.) The lowest score wins.

Every line in the file consists of a word composed of letters [a-z], followed by ,, followed by the plural, which is also composed of letters [a-z].

Please note that the data in the file is pretty terrible. It was scraped from Wiktionary using someone else's script. There are duplicates, there are things that are not real words, and there are entries that are clearly completely wrong. But none of this matters from the point of view of the challenge. The goal is to produce a program that will correctly reproduce the plurals as written in this file; their correspondence or otherwise to correct English plurals is irrelevant. Also please note that, like any dictionary, the provided file contains its fair share of offensive terms.

Input and output may be performed in any way you find convenient. (Function parameters, command-line input, etc.)

To evaluate your score you will probably need to write some testbed code that iterates over the provided file. Please include this in your answer. This code need not be in the same language as your pluralising program, and should not be golfed. (It should be readable, so we can verify that it works.)

A useful tip: while developing your code, you will probably find it helpful to modify your testbed code so that it prints out every line for which your function fails. That way you can easily see which additional cases you need to consider.

Illustrative examples

the Python code

def p(a):
 return a+'s'

is 24 bytes. However, if we run it through the following evaluation function

def testPlural(func):
    badLines = 0
    with open("simpleNouns.csv") as file:
        for line in file:
            noun, plural = line.rstrip().split(',')
            if plural != func(noun):
                badLines += 1
    return badLines

then we can see that it fails in 11246 cases, giving a score of 24 + 11246 = 11270.

However, if we update the function to

import re
def p(a):
 a+='s'
 return re.sub('ys$','ies',a)

then its length has increased to 58 bytes, but it now fails in only 7380 cases, giving a score of 58 + 7380 = 7438.

I'll start us out with something simple.

Javascript 232+2730=2962

w=prompt();r="ay,ays;ey,eys;oy,oys;y,ies;us,i;um,a;is,es;x,xes;man,men;s,ses;sh,shes;ch,ches;z,zes".split(";");for(i=0;i<r.length;i++){b=r[i].split(",");if(w.slice(-b[0].length)==b[0])return w.slice(0,-b[0].length)+b[1];}alert(w+"s")

Uses a small list of replacement rules. Fails 2730 test cases out of 95642.


Write the longest period iterating quine bounded by 500 bytes Your job is to create the longest period iterating quine, where the length of each program in the sequence is bounded by 500 bytes.

That is, if you repeat the following steps:

Start with your initial program
Run the current program
Go back to step 2

You will eventually get back to your original program. The number of programs in the cycle is your score, which you are trying to maximize.

None of the programs may raise any errors. Each program must be run the same way as well (e.g. no different versions, implementations, compiler options, platforms, etc...) (EDIT: Yes, any external state such as that of a pseudo random number generator was included in the last statement. The external state must be "reset" after each run. If you use true random numbers, worst case is assumed.)

What separates this challenge from The longest period iterating quine (other than 100 v.s. 500) is that every program in the cycle must also be 500 bytes or less. This means that the longest possible cycle is (256^501 - 1)/255 or less. That of course is a big number, but not that big in terms of how much code it takes to calculate. So the challenge is about using as many of the (256^501 - 1)/255 possibilities as you can, not a busy beaver challenge.

The programs are not permitted to access its own source code. However an empty program is permitted if you want (as long as you follow the other rules).

Since checking the programs manually would be hard, you may figure out the score using theoretical methods. You must include an explanation of the score and correctness with your program. If you can not figure out the score, you may instead use a lower bound of the number of programs in the cycle as a defacto score. You are allowed to update this as you find better lower bounds, or if you find the exact actual score.

This is code-challenge, so highest score wins!

EDIT: It is recommended that you write what your score is in scientific notation, so that answers are more easily comparable. It is perfectly fine to have other forms of the score as well, especially if they are connected to your program more clearly. Also, readers are encouraged to edit previous answers to comply with this.

Perl 6, \$126^{398} \approx 8.86 \times 10^{835}\$ iterations

$!=Q~~;<say "\$!=Q~{chrs(my@a=[R,] polymod :126[$!.ords]+1: 126 xx*)x?(@a-399)}~;<$_>~~.EVAL">~~.EVAL

Try it online!

This iterates through all the possible combinations of the first 126 bytes of length 398 and under (excluding strings with leading NUL bytes). If you want to see that it actually returns to the first iteration, you can reduce the length to 1 by changing the limit like so.

Explanation:

Each iteration increments the string, stored in base 126 form, and then converts it back to base 126. It does this until it reaches a string with length 399, and then resets the string back to empty again. If you're having trouble conceptualising the number, imagine it with ten bytes instead. Starting from 0, increment up to 4 digits, 1000 and reset. This is \$10^{4-1}\$ iterations (including 0 or empty string in my program's case).

$!=Q~~;         # Start with an empty string
< ... >~~.EVAL  # Set a string to $_ and EVAL it
  say "\$!=Q~{...}~;<$_>~~.EVAL"   # Print the program with the string replaced by
                       :126[$!.ords]   # The string converted from base 126
                                    +1 # Incremented
          [R,] polymod                : 126 xx*  # Back to base 126
chrs(                                )  # Back to a string
     my@a=                            x?(@a-399)  # Only if it isn't 399 characters


Find the longest path, avoiding obstacles in a 2D plane The Scenario

You are given a matrix of size m x n (width x height) with m*n spots where there are a few obstacles. Spots with obstacles are marked as 1, and those without are marked as 0. You can move vertically or horizontally, but can visit each spot only once. The goal is to cover as much area/spots as possible, avoiding obstacles.

Input

A 2D Matrix consisting of 0s and 1s and the coordinates of starting point.

Example Matrix1:

0(0,0) 1(0,1) 0(0,2)
0(1,0) 0(1,1) 0(1,2)
1(2,0) 0(2,1) 0(2,2)

Example Matrix2:

0(0,0) 0(0,1) 1(0,2) 0(0,3) 0(0,4)
0(1,0) 1(1,1) 0(1,2) 0(1,3) 0(1,4)
0(2,0) 0(2,1) 0(2,2) 1(2,3) 0(2,4)
0(3,0) 1(3,1) 0(3,2) 0(3,3) 0(3,4)
0(4,0) 0(4,1) 1(4,2) 0(4,3) 0(4,4)

The coordinates shown above, next to matrix elements is for explanation only. They are nothing but array indices. Actual input would just be the matrix. for example1 the input is just,

0 1 0
0 0 0
1 0 0

Input for example2,

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

Starting Point (0,0).

Output

Output should be a line containing comma separated moves. A move is a space separated direction (n,s,e,w) and number of units of movement in the direction (range 1-1000).

Example output for the matrix in example1 would be,

s 1,e 1,s 1,e 1,n 2

(0,0) --> (1,0) --> (1,1) --> (2,1) --> (2,2) --> (1,2) --> (0,2)

and for the matrix in example2 would be,

s 2,e 2,n 1,e 1,n 1,e 1,s 4,w 1,n 1,w 1

(0,0) --> (1,0) --> (2,0) --> (2,1) --> (2,2) --> (1,2) --> (1,3) --> (0,3) --> (0,4) --> (1,4) --> (2,4) --> (3,4) --> (4,4) --> (4,3) --> (3,3) --> (3,2)

which is the longest path, visiting each coordinate only once and avoiding those coordinates with obstacles.

Objective Winning Criteria

Should compute the distance efficiently(efficient: performance wise, fast program basically) for huge matrices (Of order say, 500x500). One which computes the fastest wins (All submissions run on my machine, for fairness). No restrictions on number of bytes!

Here is a 20x20 matrix which can be used to get some idea of the performace, for tuning purposes.

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

Python 3, 2619 bytes (90 LOC), ~6 seconds (20x20)

#!/usr/bin/env python

import networkx as nx

class input(object):
    def __init__(self,world_string):
        rows=world_string.split("\n")
        column_count=len(rows[0])
        blocked_cells=[]
        x=0
        y=-1
        for row in rows:
            if len(row)>column_count:
                column_count=len(row)
            y+=1
            for column in row:
                if column=='1':
                    blocked_cells.append((y,x))
                x+=1
            x=0
        self.matrix=world(len(rows),column_count)
        self.block_graph(blocked_cells)
        self.matrix.add_sink()

    def block_graph(self,block_list):
        for cell in block_list:
            self.matrix.block_cell(cell)

class world(object):
    SINK="END"

    def __init__(self, rows=3, columns=3):
        self.graph=nx.grid_2d_graph(rows, columns)
        for e in self.graph.edges():
            self.graph[e[0]][e[1]]["weight"]=-1.0

    def block_cell(self,node):
        neighbours=list(self.graph[node].keys())
        for linked_node in neighbours:
            self.graph.remove_edge(node,linked_node)

    def add_sink(self):
        matrix=self.graph.nodes()[:]
        self.graph.add_node(world.SINK)
        for source_cell in matrix:
            self.graph.add_edge(source_cell, world.SINK, weight=1.0)

class algorithm(object):
    SOURCE=(0,0)
    def find_path(graph):
        def _heuristic(current, target):
            if current==target:return 0.0
            cost=nx.astar_path(graph, algorithm.SOURCE,current,lambda x,y:1)
            return -1 * len(cost)
        path=nx.astar_path(graph, algorithm.SOURCE, world.SINK, _heuristic)
        return path[:-1]

class output(object):
    directions={
        ( 1,  0)  : "n",
        (-1,  0)  : "s",
        ( 0,  1)  : "w",
        ( 0, -1)  : "e"
    }

    def edge_to_direction(source_node, dest_node):
        row_delta=source_node[0]-dest_node[0]
        column_delta=source_node[1]-dest_node[1]
        return output.directions[(row_delta, column_delta)]

    def path_to_directions(path):
        result=""
        for step in range(len(path)-1):
            result+=output.edge_to_direction(path[step],path[step+1])
        return result

    def simplify_directions(directions):
        directions+="\0"
        count=0
        result=""
        last=""
        for d in directions:
            if d!=last or d is "\0":
                result+="{} {},".format(last, count)
                count=0
                last=""
            if count==0:
                last=d
                count=1
                continue
            if d==last:
                count+=1
        return result[3:-1]

if __name__=='__main__':
    contents="010\n000\n100"    #read from file?

    data=input(contents).matrix.graph
    result_path=algorithm.find_path(data)
    directions=output.path_to_directions(result_path)
    directions=output.simplify_directions(directions)
    print(directions+"\n")
    print(str(result_path)[1:-1].replace('), (',') --> (').replace(', ',','))

Performance

I ran this solution (on my old Core i3 laptop) on the 20x20 'performance' example input and it ran in around ~6 seconds (of course, YMMV).  I am SURE there are ways to do this faster, probably by orders of magnitude.  However, I didn't feel like re-writing my own A* algorithm in assembly and renting some time slices on a super computer!

About this Code

The Idea

The idea for this approach comes from my answer over here in Code Review.  You can also read a little bit more about it and the end of my answer here.

Dependencies

As you may have notice by the (rather prominent) line import networkx as nx - this code relies upon the Python NetworkX module to function.  So do >pip install networkx if you get import errors when running.

Breakdown of Solution Elements by Lines of Code

I also thought it would be interesting (and it was), after Don Muesli's comment (particularly the part "a significant part of the efffort[sic] is formatting the output"), to examine how much of the code is for various things.

      Breakdown:

39 lines (or 43.33%) of the lines of code in the program are concerned with parsing the input and constructing/weighting the graph data structure.
37 lines (approx. 41%) directly relate solely to displaying and formatting the desired output!
5 lines (5.5%) are 'other' stuff, which relates to running the program (shebang line, imports, the if __name__=="__main__"..., etc).
And 9 (yes.. nine) lines of code (or just 10%) actually relates to the algorithm usage.

      Obligatory Pie Chart:

About the Approach

As I mentioned above, most of the idea for this approach comes from my answer over on Code Review regarding this problem.

The process itself is relatively straightforward:

Transform the given matrix into an undirected graph data structure
Annotate (i.e. add weights) the edges of that graph
Add a "sink" node - to be used as a search target
Add (weighted) edges between all nodes and the sink node
Use a Graph Search Algorithm (in this case A*)

So, taking the 3x3 matrix from the question for example.  The transformation into a graph would yield something like the following:

(Note: the 'blocked' nodes do not have any edges)

Step 2; imagine each green line in the above picture has a weight of -1.

Next, for step 3 and 4 together (I didn't want to have to make another picture), take a look at the following graph:

And again imagine the edges are weighted, only red lines are weighted +1.

We can then apply the A-star algorithm from the NetworkX library to this graph, using the custom heuristic function.
This makes the search algorithm score paths in an inverse manner (longest path rather than shortest).  And the longest path will be the one that visits the most cells of the problem matrix!