Complement of a Regex For the purposes of this challenge, we define a postfix regex dialect with alphabet {1, 0} and the following operations:

1 and 0 match themselves literally.
_ matches the empty string.
! always fails (i.e. it does not match anything).
ab; matches a, followed by b.
ab| matches both a and b.
a+ matches one or more instances of a.

The regex should always start matching from the start of the string, and stop matching at the end of a string (in other word, it is implicitly wrapped in ^$).

As an example, the following regex matches any string with an even number of 1s:

0+_|10+_|;10+_|;;+_|;

This is equivalent to the regex 0*(10*10*)*.

The following regex matches any nonempty string of ASCII letters, expressed in binary:

110|010|10|10|10|;;;;1010|10|10|;;;10010|;10;|;;|;|;;+

This is equivalent to the regex (1.(0....|1(0...|10(0.|10))))* (where . matches any character.

You can test regexes with this program.

The Challenge

Given a regex in the format described above, return a regex in this format that matches precisely those strings that are not matched by the input.

One potential method to do this would be to convert the regex into a nondeterministic finite automaton, then convert that into a deterministic finite automaton, flip which states are designated as accept states, and then convert it back to a regex.

Test Cases

format:
input   => potential output
           equivalent infix regex

0       => _101|+_|;|
           |1.*
1       => _001|+_|;|
           |0.*
_       => 01|+
           .+
!       => 01|+_|
           .*
01|+    => _

01|+_|  => !
           [] (empty character class)
1001;;; => _01|01|01|;01|01|01|;;001|01|01|01|+_|;;;;01|101|01|01|+_|;;;;01|01|101|01|+_|;;;;01|01|01|001|+_|;;;;|||||||
           |.|..|...|0....*|.1...*|..1..*|...0.*

Dyalog APL, 166 bytes
{l←!!5*≢⍵⋄z←⊂''⋄n←,∘.,⍨⋄k←{⊃,/n\l/⊂⍵}⋄f←{⊃⊃{⍺∊';|':(2↓⍵),⍨⍺{';'=⍺:n/⍵⋄,/⍵}2↑⍵⋄⍺='_':⍵,⍨⊂z⋄'+'=⍺:⊂∘k∘⊃@1,⍵⋄⍺,⍵}/⌽1,⍵}⋄w←f⍵⋄⊃q/⍨{0=≢((z,k'01')~w∪f⍵)∪w∩f⍵}¨q←k'10!_|;+'}

The solution is a function that works by brute-forcing. It cannot be run in reasonable time nor with reasonable memory on any of the inputs, so no TIO link is provided; this is due to looping over every possible regex over the factorial of the factorial of 5 to the power of the input length. Note that the numbers involved go out of Dyalog's maximum number size for an input regex of length greater than 1. To test this, take a look at the function f, which returns a value that includes all matches less than the calculated upper bound l, and test it on the complementarity check {0=≢ ... ⍵∩f⍵}. Using smaller values of l can make the function provide wrong results, so note that before reducing its value.

There is an upper bound for the minimum length of the complementary regex as a function of the length of the input regex, and an upper bound for the length of the longest string the two regexes need to be tested against to determine their complementarity. These parameters are used to brute force the complementary regex, by comparing the strings accepted by the input regex and the regex being tested for complementarity.
We start by comparing the length of a regular expression to the number of states of its respective DFA.
The non-deterministic finite automaton (NFA) for the regex 1 is the following (using (Sn) to denote accepting states)
   1
Si-->(Sf)

The regex _ representing an \$\epsilon\$-transition can be represented by an NFA that has less than 2 states, as can the regex ! representing non-acceptance.
 _

(Si)

 !

Si

Thus, a regex with only characters from 01_! with length n will have an NFA with max size n+1.
The regex ab;, where a and b are sub-regexes, denotes the concatenation of a and b and can be described as the following. (Si# denotes an initial state and (S##) denotes a final state.)
  Si1-->...-->(Sf1)   Si2-->...-->(Sf2)    ;

                     ε
NFA= Si1-->...-->Sf1-->Si2-->...-->(Sf2)

The regex a+ denotes one or more occurrences of a.
  Si1-->...-->(Sf1)   +

            ε
      +------------+
      v            |
NFA= Si1-->...-->(Sf1)

This produces an NFA with the same size as that of a. Again, a regex with only characters from 01_!; with length n will have an NFA with max size n+1.
The regex ab| denotes an alternative of either a or b.
  Si1-->...-->(Sf1)   |   Si2-->...-->(Sf2)

      Si1-->...-->(Sf1)
NFA=
      Si2-->...-->(Sf2)

Both Si1 and Si2 are starting states in the above NFA. This does not fit the traditional definition of an NFA, where an NFA has only 1 starting state, but the size of the resulting deterministic finite automaton (DFA) does not increase. If needed, the NFA for + can be changed so that there is an ε-transition from the final state to the second state, and the NFAs for _ and ! changed to have 2 states each, so that a traditional NFA can be constructed for alternation with ε-transitions between Si1 and Si2.
An NFA resulting from alternation will be as large as the sum of the two sub-regexes that make it up. A regex of length n will have an NFA with a maximum size of n+1.
By the powerset construction, an NFA with size \$n\$ will result in a DFA with size \$2^n\$. So a regex of length \$n\$ will have a minimal DFA upper-bounded by \$2^{n+1}\$. A DFA can be inverted by simply switching the final and non-final states, so its complement will have the same number of states as itself.
With this information, we need an upper limit on the size of the complementary regex as a function of the length of the number of states of the DFA. To do this, I use an algorithm to convert a DFA to a regex; the idea is to represent every possible path from Si to any other state, as well as accounting for loops by tracking every loop that starts and ends at Si, in a recursive manner. For every state that can be reached in 1 step from Si, the process is repeated and a path is constructed from this new state to every other state except the states that have already been encountered, i.e. Si in the first iteration, since loops back to Si would already be covered by tracking loops. An example of the construction can make this clearer.
0<c0>;1<c1>;|+_|
0<r0>;1<r1>;<a>||
;

This is a regex that represents a DFA that I will call the "base form". The base form for a state is a regex that traverses paths from that state to every state in the DFA except for, as we will see, states that have been explicitly excluded for a particular iteration. The accept/reject status of each path is denoted by <a>, being _ for accept or ! for reject. The second line of the regex accounts for this "breadth-first" filling, by transitioning to states that are 1 step way, and recursing the base form (as represented by <r0> and <r1>) on those states. Each time we recurse, we exclude the original "parent" state from the graph traversal to prevent the algorithm from infinitely looping. Loops in the regex are tracked in the first line, where, also, every possible path is traversed, halting when reaching the parent state, but these sub-regexes, as denoted by <c0> and <c1>, consider only the parent state to be the accepting state.
At each level of recursion, the number of excluded states increases by 1, until every possible state is covered at which point the algorithm ends.
The base form, without the recursive parts, is of length 16. Each iteration spawn 4 new sub-regexes, and there are as many iterations as states in the DFA.
If a DFA has n states, an upper bound for the regex length is \$16 + 16×4 + 16×4×4 + ... + 16×4^{n-1}\$. This is a geometric series and can also be written as
$$\frac{16}{3}\left(4^n-1\right)$$
Now given a regex with length s, the length of its complement is bounded by
$$h=\frac{16}{3}\left(4^{2^{n+1}}-1\right)$$
(I felt that this upper bound could be improved to a mere exponential instead of a double exponential, potentially saving some bytes, but I was proven wrong by this answer.)
We can check if two regexes are equivalent by brute force, but to do that we need to know the upper limit of the input length to test. If the DFAs of the two regexes are a and b, we can construct another DFA c whose states are the Cartesian product of the states of a and b, so each state of DFA c can be labeled as a 2-tuple (a_j,b_k) where a_j and b_k are states of DFA a and b respectively. The transition of DFA c's state (a_j,b_k) under input letter l is the tuple of the transition of each state a_j and b_k in DFAs a and b respectively under letter l. The final states of DFA c are all the states (a_j,b_k) where either both a_j and b_k are final states or they are both non-final states. DFA c accepts a word if both DFAs a and b accept this word, i.e. DFAs a and b do not yield complementary results on this word. DFAs a and b are complementary iff DFA c does not accept any word. By the pumping lemma, to check for this, we only need to check of input word sizes up to the number of states of DFA c, minus 1.
The size of the DFA of the complementary regex is 2^(h+1) and that of the input regex is 2^(n+1). Thus we only need to check for input lengths up to 2^(h+1)×2^(n+1)-1.
$$2^{\frac{16}{3}\left(4^{2^{n+1}}-1\right)+1+n+1}-1$$
We need to find a golfy way to write a function that is always greater than the triple exponential above for n≥1. Factorials grow faster than exponentials and are 1 byte shorter and so can be useful. However, the factorial of 1 is still 1, so we cannot simply chain 3 factorials together. The first function can instead be an exponential b*n, APL for b to the power of n, after which two factorials can be added in place of the remaining double exponential, yielding !!b*n. \$b=3\$ is too small for the base case of n=1, \$b=4\$ is slightly smaller, but \$b=5\$ goes above the function.
$$l=(5^{≢\omega}!)!$$
This gives the first statement of the APL code, l←!!5*≢⍵ assign to the variable l the factorial ! of the factorial ! of 5 to the power of * the length ≢ of ⍵ the right argument.
The submission
{l←!!5*≢⍵⋄z←⊂''⋄n←,∘.,⍨⋄k←{⊃,/n\l/⊂⍵}⋄f←{⊃⊃{⍺∊';|':(2↓⍵),⍨⍺{';'=⍺:n/⍵⋄,/⍵}2↑⍵⋄⍺='_':⍵,⍨⊂z⋄'+'=⍺:⊂∘k∘⊃@1,⍵⋄⍺,⍵}/⌽1,⍵}⋄w←f⍵⋄⊃q/⍨{0=≢((z,k'01')~w∪f⍵)∪w∩f⍵}¨q←k'10!_|;+'}

The regex is parsed and its matches returned by the function f. It works on the reversed regex, and 'fold'ing ('reducing' in APL-speak) over it. It returns all matches of a regex, with the special case of the regex a+ only returning up to the first l repetitions of sub-regex a, thus keeping the list of matches finite. By having this behaviour of +, all input matches up to a length of l are included in the result of f, i.e. nothing less than what is needed to test for complementarity. APL reduces from right to left, due to order of operations being from right to left. Each intermediate results of the reduce is formed by the matches of each sub-regex encountered thus far. For the initial case, a 1 is prepended to the regex before reversing it, after which the reduce operation is applied.
f←{⊃⊃{⍺∊';|':(2↓⍵),⍨⍺{';'=⍺:n/⍵⋄,/⍵}2↑⍵⋄⍺='_':⍵,⍨⊂z⋄'+'=⍺:⊂∘k∘⊃@1,⍵⋄⍺,⍵}/⌽1,⍵}

The right argument ⍵ contains the matches of each sub-regex encountered so far. The left argument ⍺ is the next character of the regex that is being processed. Each case of the regex character is checked using = equality or ∊ belongs-to when multiple cases can be joined into 1.
Of particular note, ! in the regex is treated the same as 0 or 1, resulting in a match of the character !. Due to how the regexes are checked for complementarity, this works fine. Its exact mechanism is ⍺,⍵, concatenate ⍺, a single character being either of 0, 1, or !, with ⍵.
_ matches the empty string, z in the APL code refers to z←⊂'' present earlier in the entire submission; ⍵,⍨⊂z the enclosed empty string, i.e. signifying that only the empty string is being matched, is prepended to ⍵.
The mechanism of + is dependent on the function k←{⊃,/n\l/⊂⍵}, which given a list of strings ⍵, performs the Cartesian concatenation (Cartesian product, but using concatenation instead of set union) of l copies of ⍵, where the Cartesian concatenation is defined earlier as n←,∘.,⍨. This is achieved using the @ operator, applying the function ⊂∘k∘⊃ on the list of matches at index 1, the ⊂ enclose and ⊃ pick functions are required due to the behaviour of @.
Concatenation and alternation are considered together. On 2↑⍵ the list of the first two elements of ⍵, n/ (reduce by n Cartesian concatenation) is applied in the case of concatenation, and ,/ (reduce by concatenation). The remaining ⍵ is concatenated at the end of this result.
After the execution of the reduce operation, its first set of matches is retrieved using ⊃.
The regex does not give errors even on incorrect regexes. The handling of + uses the @ operator which expects the argument to be indexable. When + is by itself, ⍵ is the scalar 1, so @ on 1 would not work, but the , applied on ⍵ converts it into a list, preventing an error. + then takes the Cartesian concatenation of 1 with l copies of itself.
; and | with too few arguments are implicitly handled by the functionality of the ↑ take function and the ↓ function. 2↑ takes the first 2 elements of the right argument, but if the right argument is shorter, the result is padded with sufficient prototype values, for example the prototype of a strictly numeric array is 0, while that of a character array is the space character ' '.
However, even with this treating of anomalous regexes, these regexes will not be returned by the entire complementary regex function as a complementary regex. This is due to the fact that they cannot be shorter than the respective shortest valid postfix regex, and even if these incorrect regexes are of the same length as the shortest valid regex, they are ordered lexicographically later than a valid regex, with the order being specified later while performing the complementarity check by 10!_|;+, and only the first (again, ordered lexicographically) complementary regex is picked as a result to the function submission.
Complementarity check
The checking for complementarity is done by the following part. q←k'10!_|;+' generates all possible regexes up to a length of l (k computes this function as mentioned earlier) and assigns this to q. The ordering specified by this part is what prevents incorrect regexes from being returned by the function.
For each of these strings ¨, the following function is computed, (⍵ denotes the right argument, in this case, each string for which the following function is applied on)
{0=≢((z,k'01')~w∪f⍵)∪w∩f⍵}

w is assigned earlier to the matches of the input regex. w∩f⍵ computes the intersection of w, the matches of the input, with f⍵, the matches of ⍵. For complementary regexes, this should be the empty set.
w∪f⍵ computes the union of w and f⍵. ~ performs set complement. z is ⊂'', the enclosed empty string. k'01' computes all binary strings with length up ≤ l, so z,k'01' is a list containing all these binary strings, along with the empty string.
The result of (z,k'01')~w∪f⍵ is all the binary strings that are not present in w∪f⍵, so it contains the strings that are matches by neither the input regex nor ⍵. For complementary regexes this should be the empty set.
((z,k'01')~w∪f⍵)∪w∩f⍵ is the union of the two sets above. This should be empty if the regexes are complementary. Its emptiness is checked by counting the number of elements contained within it using ≢, and comparing this result with 0. (Using ⍬ doesn't work because in Dyalog APL, empty lists can have different prototype lists.)
This function explained above returns 1 is the regexes are complementary, and 0 if they are not. The first truthy regex is picked by ⊃q/⍨, being returned by the function.
Alternative approaches
Initially, I thought that using the approach recommended in the challenge of doing the conversion regex → NFA → DFA → regex would yield a short solution in APL because of APL's strength with matrices (by storing the NFA/DFA as a 3-dimensional array, with each of its 2-dimensional arrays being adjacency matrices for transitions involving each input character and ε-transitions). I got to implement a part of this for the regex matching challenge that popped up recently, but I got a solution much longer than what I had expected at over 250 bytes. It's the handling of individual matrix entries that made the program long, for example, I had to include specific transitions between specific states, like an ε-transition from state 1 to states 2 and 3 for alternation. However the handling of the entire array or its component matrices was short, as was needed to execute the NFA on the input string. And besides, all that the >250 byte program did was only to determine if 1 string matches the input regex. Maybe storing the NFA in a "sparse" format with list of lists of numbers representing states might end up being shorter that the matrix-oriented approach.
I tried another approach to that regex matching challenge by listing all the matches of the input regex, with + repetitions bounded by the input length, and checking if the input string belongs to this list, which yielded a >140-byter, almost half the length of my previous approach. This approach ended up being adapted into function f of my submission to this challenge. Unlike the approach mentioned in the previous paragraph, this approach generates the list of all input matches, so I do not have to separately run the regex matching function on each of the possible inputs to see which ones it matches, thus saving a great deal of bytes.
Moreover, I had also tried ⎕r, Dyalog APL's PCRE replace function, for this challenge but that resulted in a postfix → PCRE converter at >110 bytes. Besides, similarly to the approach where I stored the NFA in an array, implementing the matching as well as finding all of the matches of this regex on all (bounded) input strings added too many bytes.
It was when I stumbled upon ankh-morpork's Prolog submission to the regex decomposition challenge and by the power of Prolog DCGs that I started working on this regex complement challenge in Prolog. However my Prolog skills was not good enough to make it work, and seeing how my approach ended up becoming un-Prolog-y and more APL-y I switched to APL and started this solution with the knowledge I had gathered from attempting the regex matching challenge. This brute-force approach proved to be significantly short than any other approach I could think of, so I went ahead with this. I left the calculation of the upper bound to the very end, i.e. the l← bit, and golfed the rest of my program from an initial size of >210 bytes.
The complementary check might be further golfable, perhaps there's a nice way to get rid of the parentheses, or an alternative logic. In function f, under the case when ⍺∊';|', I feel the 2↑⍵ and 2↓⍵ surrounding the code has a shorter alternative; I tried @1 2⊢⍵, but this results in an error for invalid regexes requiring me to use an error guard.


What is a short code for generating this matrix in R? I can see that it is 101 'moving to the right' but I cannot think of a short way to generate it in R language.

\$\begin{bmatrix}
0 & 1 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 & 0 & 1 \\
0 & 0 & 0 & 0 & 1 & 0 \\
\end{bmatrix}\$

R, 24 23 22 20 bytes

diag(0,6)+c(!-1:4,1)

Try it online!

Just use R's recycling! This does give a warning, but otherwise is fine.

Thanks to Robin Ryder for the 2 byte golf.


Tips for golfing in Burlesque This serves as a catalog for tips related to golfing in Burlesque.
Burlesque is a lazy, esoteric programming language. It's mostly used on anarchy golf while popularity on Codegolf is not as high. However, this catalog is intended to be used by people golfing on anarchy golf as well.

Please only mention tricks and not obvious shortcuts. An obvious shortcut is for example using r\ instead of r@\[ because the built-in r\ is defined to be r@\[ and is stated as such in the documentation and is thus just an obvious shortcut.

Using ".. .."wd instead of {".."".."}

If you need a Block of Strings such as {"abc" "def"} it is shorter to use the words built-in: "abc def"wd.

Using ra to parse fail-safe

ps will fail if the input is not properly formated or might produce unwanted results. In such cases, using ra is better.

blsq ) "5,"ra
5
blsq ) "5,"ps
{5 ,}
blsq ) "5a"ps
{ERROR: (line 1, column 3):
unexpected end of input}
blsq ) "5a"ra
5

Using , to drop stdin

, is defined as a pop instruction if and only if there is exactly one element on the stack. It's used to pop STDIN from the stack when it's not needed but there (such as for example is the case on anarchy golf).

Abusing the way mo is defined

mo is defined as 1R@\/?* and is used to generate a Block containing multiples of N:

blsq ) 3mo9.+
{3 6 9 12 15 18 21 24 27}

Yet due to side effects of ?* you can do some nasty things with it if you don't provide a number:

blsq ) "1"mo9.+
{"11" "21" "31" "41" "51" "61" "71" "81" "91"}

blsq ) {1 2 3 4}mo9.+
{1 4 9 16}


Tips for golfing in dc What general tips do you have for golfing in dc?

dc is a calculator utility for UNIX/Linux that predates the C language. I am interested in how to make my dc programs (calculations?) shorter. I'm looking for ideas that can be applied to general code-golf that are at least a little bit specific to dc (eg. removing comments is not a helpful answer)

Please post one tip per answer.

If-then-else statements

Suppose we want to check the condition a==b (let a and b be stored in their respectively-named registers).

edit:

[         # Everything is wrapped in one big macro
  [         # An inner macro for our *then* part
              # <-- Stuff to execute if a==b here
  2Q          # Then quit the inner and outer macro
]sE       # `E' is for Execution register ;)
la lb =E  # if a==b, execute E
          # if E is executed, it will quit the whole macro, so the rest is never reached:
          # <-- Stuff to execute if a!=b here
]x        # End macro; Execute

Let (foo) be a placeholder, for the purpose of condensing:

[[(then)2Q]sE(condition)E(else)]x

Pretty sure this is the most compact if statement possible (also featured here).


Twinkle Twinkle Little Star Write a program to play the popular English nursery rhyme.

(This file is licensed under the Creative Commons Attribution-Share Alike 3.0 Unported license. Attribution: Helix84 at the English language Wikipedia; Blahedo at the English language Wikipedia.)

Some Wikipedia articles that may be useful:

Twinkle Twinkle Little Star (has an audio clip of what your program's output should sound like)
Modern musical symbols (to learn about the music notation used above)
Note#Note frequency (hertz) (the formula for calculating the frequency of each note)

Some guidelines for your submission:

Your program must use the computer's sound card. If your programming language doesn't have convenient access to audio hardware, your program must create an output file in some standard format such as WAV or MIDI.
Your program must actually generate its output. For example, embedding the Ogg Vorbis file from Wikipedia would not be allowed.
The audio quality must be acceptable. At the very least, the song should be easily recognizable. Preferably, it should sound good as well.
The focus should be on code size, sound quality, or both (explain which one you decided on). Elegant solutions would also be great. Have fun!
This is a code-golf, so shortest code wins

QBasic (56)

A$="CCGGAAG2FFEEDDC2"
B$="GGFFEED2"
PLAY "L4"+A$+B$+B$+A$

Focus is on reminiscence :)

(Don't have a QBasic to test this though)


I reverse the source code, you negate the output! Your task, if you wish to accept it, is to write a program that outputs a non-zero number(can be integer or float). The tricky part is that if I reverse your source code, the output must be the original integer negated.

Rules

You must build a full program. That is, your output has to be printed to STDOUT.
Both the numbers must be in base 10 (outputting them in any other base or with scientific notation is forbidden).
Outputting the numbers with trailing / leading spaces is allowed.
This is code-golf, so the shortest (original) code in each language wins!
Default Loopholes apply.

Example

Let's say your source code is ABC and its corresponding output is 4. If I write CBA instead and run it, the output must be -4.

05AB1E, 2 bytes

(1

Try it online!

!enilno ti yrT

(       # negate nothing
 1      # push 1 (and implictly output it)

1       # push 1
 (      # negate it (and implictly output it)


Grid crossing sequence If you take a sheet of graph paper and draw a sloped line that goes m units right and n units up, you cross n-1 horizontal and m-1 vertical gridlines in some sequence. Write code to output that sequence.

For example, m=5 and n=3 gives:

Possibly related: Generating Euclidian rhythms, Fibonacci tilings, FizzBuzz

Input: Two positive integers m,n that are relatively prime

Output: Return or print the crossings as a sequence of two distinct tokens. For example, it could be a string of H and V, a list of True and False, or 0's and 1's printed on separate lines. There can be a separator between tokens as long as it's always the same, and not, say, a variable number of spaces.

Test cases:

The first test case gives empty output or no output.

1 1
1 2 H
2 1 V
1 3 HH
3 2 VHV
3 5 HVHHVH
5 3 VHVVHV
10 3 VVVHVVVHVVV
4 11 HHVHHHVHHHVHH
19 17 VHVHVHVHVHVHVHVHVVHVHVHVHVHVHVHVHV
39 100 HHVHHHVHHVHHHVHHVHHHVHHVHHHVHHHVHHVHHHVHHVHHHVHHVHHHVHHHVHHVHHHVHHVHHHVHHVHHHVHHVHHHVHHHVHHVHHHVHHVHHHVHHVHHHVHHHVHHVHHHVHHVHHHVHHVHHHVHH

In the format (m,n,output_as_list_of_0s_and_1s):

(1, 1, [])
(1, 2, [0])
(2, 1, [1])
(1, 3, [0, 0])
(3, 2, [1, 0, 1])
(3, 5, [0, 1, 0, 0, 1, 0])
(5, 3, [1, 0, 1, 1, 0, 1])
(10, 3, [1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1])
(4, 11, [0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0])
(19, 17, [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1])
(39, 100, [0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0])

Ruby, 92; Ostrich 0.7.0, 38

f=->m,n{((1..m-1).map{|x|[x,1]}+(1..n-1).map{|x|[1.0*x*m/n,0]}).sort_by(&:first).map &:last}

:n;:m1-,{)o2W}%n1-,{)m n/*0pW}%+_H$_T%

Output for both of them uses 1's and 0's (ex. 101101).

Here's an explanation of the Ostrich one:

:n;:m    store n and m as variables, keep m on the stack
1-,      from ex. 5, generate [0 1 2 3]
{...}%   map...
  )        increment, now 5 -> [1 2 3 4]
  o        push 1 (the digit 1 is special-cased as `o')
  2W       wrap the top two stack elements into an array
           we now have [[1 1] [2 1] [3 1] [4 1]]
n1-,     doing the same thing with n
{...}%   map...
  )        increment, now 3 -> [1 2]
  m n/*    multiply by slope to get the x-value for a certain y-value
  0        push 0
  pW       wrap the top two stack elements (2 is special-cased as `p')
+        concatenate the two arrays
_H$      sort-by first element (head)
_T%      map to last element (tail)

And an explanation of how the whole thing works, using the Ruby code as a guide:

f = ->m,n {
    # general outline:
    # 1. collect a list of the x-coordinates of all the crossings
    # 2. sort this list by x-coordinate
    # 3. transform each coordinate into a 1 or 0 (V or H)
    # observation: there are (m-1) vertical crossings, and (n-1) horizontal
    #   crossings. the vertical ones lie on integer x-values, and the
    #   horizontal on integer y-values
    # collect array (1)
    (
        # horizontal
        (1..m-1).map{|x| [x, 1] } +
        # vertical
        (1..n-1).map{|x| [1.0 * x * m/n, 0] }  # multiply by slope to turn
                                               # y-value into x-value
    )
    .sort_by(&:first)  # sort by x-coordinate (2)
    .map &:last        # transform into 1's and 0's (3)
}


Fermat's factorization helper We'd like to factorize a semiprime \$N\$. The goal of this challenge is to find two small integers \$u\$ and \$v\$ such that \$uvN\$ can be trivially factorized with Fermat's method, thus allowing to easily deduct the factors of \$N\$.

The task

Given a semiprime \$N\$ and a positive integer \$k\$, we define \$x\$ and \$y\$ as:

$$x=\lceil\sqrt{kN}\rceil$$
$$y=x^2-kN$$

Step #1 - Find \$k\$

You first need to find the smallest possible value of \$k\$ such that \$y\$ is a square number (aka perfect square).

This allows to factorize \$kN\$ with a single iteration of Fermat's factorization method. More concretely, this immediately leads to:

$$kN=(x+\sqrt{y})\times(x-\sqrt{y})$$

(Update: this sequence is now published as A316780)

Step #2 - Factorize \$k\$

You then have to find the two positive integers \$u\$ and \$v\$ such that:

$$uv=k$$
$$cu=x+\sqrt{y}$$
$$dv=x-\sqrt{y}$$

where \$c\$ and \$d\$ are the prime factors of \$N\$.

Summary

Your task is to write a program or function that takes \$N\$ as input and prints or outputs \$u\$ and \$v\$ in any order and any reasonable format.

Example

Let's consider \$N = 199163\$

Step #1

The smallest possible value of \$k\$ is \$40\$, which gives:

$$x = \lceil(\sqrt{40 \times 199163})\rceil = 2823$$
$$y = 2823^2 - 40 \times 199163 = 7969329 - 7966520 = 2809 = 53^2$$
$$kN = (2823 + 53) \times (2823 - 53)$$
$$kN = 2876 \times 2770$$

Step #2

The correct factorization of \$k\$ is \$k = 4 \times 10\$, because:

$$kN = 2876 \times 2770$$
$$kN = (719 \times 4) \times (277 \times 10)$$
$$N = 719 \times 277$$

So, the correct answer would be either \$[ 4, 10 ]\$ or \$[ 10, 4 ]\$.

Rules

It is not required to strictly apply the two steps described above. You're free to use any other method, as long as it finds the correct values of \$u\$ and \$v\$.
You must support all values of \$uvN\$ up to the native maximum size of an unsigned integer in your language.
The input is guaranteed to be a semiprime.
This is code-golf, so the shortest answer in bytes wins.
Standard loopholes are forbidden.

Test cases

N          | k    | Output
-----------+------+------------
143        | 1    | [   1,  1 ]
2519       | 19   | [   1, 19 ]
199163     | 40   | [   4, 10 ]
660713     | 1    | [   1,  1 ]
4690243    | 45   | [   9,  5 ]
11755703   | 80   | [  40,  2 ]
35021027   | 287  | [   7, 41 ]
75450611   | 429  | [ 143,  3 ]
806373439  | 176  | [   8, 22 ]
1355814601 | 561  | [  17, 33 ]
3626291857 | 77   | [   7, 11 ]
6149223463 | 255  | [  17, 15 ]
6330897721 | 3256 | [  74, 44 ]

Example implementation

In the snippet below, the \$f\$ function is an ungolfed implementation which takes \$N\$ as input and returns \$u\$ and \$v\$.

For illustrative purposes only, the snippet also includes the \$g\$ function which takes \$N\$, \$u\$ and \$v\$ as input and computes the factors of \$N\$ in \$O(1)\$.

f = N => {
  for(k = 1;; k++) {
    x = Math.ceil(Math.sqrt(k * N));
    y = x * x - k * N;
    ySqrt = Math.round(Math.sqrt(y));

    if(ySqrt * ySqrt == y) {
      p = x + ySqrt;

      for(u = 1;; u++) {
        if(!(p % u) && !(N % (p / u))) {
          v = k / u;
          return [ u, v ];
        }
      }
    }
  }
}

g = (N, u, v) => {
  x = Math.ceil(Math.sqrt(u * v * N));
  y = x * x - u * v * N;
  ySqrt = Math.round(Math.sqrt(y));
  p = x + ySqrt;
  q = x - ySqrt;
  return [ p / u, q / v ];
}

[
  143, 2519, 199163, 660713, 4690243, 11755703,
  35021027, 75450611, 806373439, 1355814601,
  3626291857, 6149223463, 6330897721
]
.map(N => {
  [u, v] = f(N);
  [c, d] = g(N, u, v);
  console.log(
    'N = ' + N + ', ' +
    'u = ' + u + ', ' +
    'v = ' + v + ', ' +
    'N = ' + c + ' * ' + d
  );
});

Mathematica, 81 79 bytes

Thanks to Martin Ender for saving 2 bytes!

(c=Ceiling;For[j=0;z=E,c@z>z,p=(x=c@Sqrt[j+=#])+{z=Sqrt[x^2-j],-z}];p/#~GCD~p)&

Pure function taking a semiprime as input and returning an ordered pair of positive integers. The For loop implements the exact procedure described in the question (using # for the input in place of n), with x as defined there, although we store j = k*n instead of k itself and z=Sqrt[y] instead of y itself. We also compute p={x+z,x-z} inside the For loop, which ends up saving one byte (on like the seventh try). Then the two desired factors are (x+z)/GCD[#,x+z] and (x-z)/GCD[#,x-z], which the concise expression p/#~GCD~p computes directly as an ordered pair.

Curiosities: we want to loop until z is an integer; but since we're going to use Ceiling already in the code, it saves two bytes over !IntegerQ@z to define c=Ceiling (which costs four bytes, as Mathematica golfers know) and then test whether c@z>z. We have to initialize z to something, and that something had better not be an integer so that the loop can start; fortunately, E is a concise choice.


Sort a concatenated sequence Consider a sequence based on recurrence relations, f(n) = f(n-1)+f(n-2), starting with f(1) = x1, f(2) = x2. For x1 = 2, x2 = 1, the sequence begins like this:

2  1  3  4  7  11  18  29  47  76  123  199  322  521  843

Concatenating this into a string will give:

213471118294776123199322521843

Now, divide this list into the smallest possible numbers that gives y(n) > y(n-1). Start with the first number, then the second etc. The first output number should always be a single digit. Pad the last number with the required number of zeros.

2 13 47 111 829 4776 12319 93225 218430

You will get two numbers, (x1, x2) as input, on any convenient format, and the challenge is to output the sorted list.

Rules:

Function and programs are OK
The initial sequence shall have exactly 15 numbers (The last number is f(15)).
x1 and x2 are non-negative (zero is possible).
The output can be on any convenient format
The output vector y must be created so that y2 > y1.

First the smallest possible y1, then the smallest possible y2, then y3 and so on.

If x1 = x2 = 0 then output 15 zeros (on the same format as other output, i.e. not 000000000000000).

Examples:

Input: 1 1
Output: 1  12  35  81  321  345  589  1442  3337 7610

Input: 3 2
Output: 3  25  71  219  315  0811 3121  23435 55898 145300
                             |
                             Optional leading zero
Input: 0 0
Output: 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0

The shortest code in bytes wins. Please include a link to an online interpreter if possible.


Display random colored pixels I've always liked screens full of randomly colored pixels. They're interesting to look at and the programs that draw them are fun to watch.

The challenge

Fill your screen, or a graphical window, with colored pixels.

The rules

Your program must have an even chance of picking all colors (i.e in the range #000000 to #FFFFFF), or all colors that can be displayed on your system.
Your program must continue to display random pixels until manually stopped (it cannot terminate on its own).
Pixels can be any size, as long as your output has at least 40x40 "pixels".
Your program must run at such a speed that it can replace every pixel on the screen/window at least once after running for three minutes.
Your program must choose truly random colors and points to replace, i.e. random with all points/colors equally likely. It cannot just look random. It must use a pRNG or better, and the output cannot be the same every time.
Your program must have an equal chance of picking all colors each iteration.
Your program must replace only one pixel at once.
Your program cannot use the internet nor your filesystem (/dev/random and /dev/urandom excepted).

Example

Your output could look like this if stopped at a random time:

The winner

The shortest answer in each language wins. Have fun!

Minecraft 1.12 Redstone Command Blocks, 4,355 2,872 bytes

(Size determined by saved structure block file size.)
Here is a full YouTube overview, but I'll try to outline the code below.
Setup Routine:

This sets up the 40x40 grid of Minecraft armor stands. Armor stands are necessary because Minecraft has no way to substitute variables into world coordinates. So the workaround is to refer to the location of these armor stand entities.
(impulse) summon armor_stand 2 ~ 1 {CustomName:"A"} /create named armor stand
(chain) fill -2 ~ -2 43 ~ 43 stone                  /create big stone square
(chain) fill -1 ~ -1 42 ~ 42 air                    /leave just a ring of stone
(chain) setblock -4 ~ -12 redstone_block            /kicks off next sequence

This named armor stand is basically our "cursor" to place all the armor stands that we will need. The redstone block in the last step "powers" nearby blocks (including our command blocks), so kicks off the next loop:
(repeat) execute @e[name=A] ~ ~ ~ summon armor_stand ~-1 ~ ~   /create new armor stand
(chain) tp @e[name=A] ~1 ~ ~                                   /move "cursor" one block
(chain) execute @e[name=A] ~ ~ ~ testforblock ~1 ~ ~ stone     /if at end of row,
(conditional) tp @e[name=A] ~-40 ~ ~1                          /go to start of next row
(chain) execute @e[name=A] ~ ~ ~ testforblock ~ ~ ~2 stone     /If at last row
(conditional) setblock ~6 ~ ~ air                              /stop looping
(conditional) kill @e[name=A]                                  /kill cursor

At this point our grid is complete:

Random Color Selector

The purple repeaters in the center of this picture choose a random color via the following command:
(repeat) execute @r[type=armor_stand,r=9] ~ ~ ~ setblock ~ ~-2 ~ redstone_block

That "@r[]" is the magic sauce, it selects a random entity in the world that matches the given conditions. In this case, it finds an armor stand inside a radius of 9 blocks, and we've set up 16 armor stands, one for each wool color. Under the selected color, it places a redstone block (which powers the two command blocks on either side).
Random Pixel Selector
Placing the redstone block under the selected wool color triggers two more command blocks:
(impulse) execute @r[type=armor_stand] ~ ~ ~ setblock ~ ~3 ~ wool X
(impulse) setblock ~ ~ ~1 air

This first line uses our same magic @r command to choose any armor stand on the entire map (no radius restriction, so that includes the 40x40 grid), and places a wool of the selected color above its head. The X determines the color, and ranges from 0 to 15. The second command removes the redstone block so it is ready to go again.
I have 5 purple repeater blocks, and redstone works in "ticks" 20 times a second, so I'm placing 100 pixels per second (minus some color overlaps). I've timed it, and I usually get the entire grid covered in about 3 minutes.
This was fun, I'll try to look for other challenges that might also work in Minecraft. Huge thanks to lorgon111 for his YouTube Command Block tutorial series.
EDIT: Made some serious reductions in the size of the saved structure, now at 2,872 saved bytes:

Scooted things in a bit (in all 3 dimensions) so I could reduce the overall size of the saved area.
Changed the different colored wools to stone, they were just decorative anyway.
Removed the glowstone lamp.
Changed all air blocks to void blocks (the red squares).

Tested by pulling the saved structure into a new world, everything still works as designed.
EDIT 2: Read-only Dropbox link to the NBT structure file
Walk through is in my YouTube video, but here are the steps:

In Minecraft 1.12, create a new creative superflat world using the "Redstone Ready" preset. Make it peaceful mode.
Once the world exists, copy the NBT file into a new \structures folder you create under the current world save.
Back in the game, do /give @p structure_block, and /tp @p -12, 56, -22 to jump to the right spot to get started.
Dig a hole and place the structure block at -12, 55, -22.
Right-click the structure block, click the mode button to switch it to "Load".
Type in "random_pixels", turn "include entities" ON, and click "Load"
If it finds the structure file, it will preview the outline. Right-click again and click "load" to bring the structure into the world.
Press the button to run the setup routine.
When it completes, flip the switch to run the wool randomization.


No trailing but(t)s please! This challenge was inspired by Yeah But No But Yeah.

maxb´s colleague recently sent him the following piece of JavaScript as a joke:

let butScript = (nrOfButs) => {
    for(var i = 0; i < nrOfButs; i++){
        if(i % 3 == 0){
            console.log("Yeah")
        }
        if(i % 2 == 0){
            console.log("But")
        }
        if(i % 3 == 1){
            console.log("No")
        }
    }
}

Since the code is not only overly long but also incorrect, I´ll suggest to maxb´s boss to fire that guy and hire one of you folks instead.

I can´t guarantee anything; but I reckon there´ll be a decent wage, health insurance and possibly a company car in it. All You have to do is
A) correct the code, so the Number of Buts printed is the same as asked in the parameter
B) correct the grammar. (see below)
C) make it as short as possible.

He might as well block my calls after that because he doesn´t like pennypickers; but who knows.

Input

a non-negative integer, in any convenient way

Output

Yeah and No, mostly separated by Buts. The code above and the examples below should clarify the pattern.
Output should never end in a But.
And a sentence should always end with a stop (.) or exclamation mark; i.e. put one after every No that is directly followed by a Yeah (without a But) and one at the end of the output.
A single trailing "Yeah." may be printed (if you want to think positive), but that´s not a must.

You may print the output or return a list of strings.
Trailing blanks are acceptable, as well as a single leading or trailing newline.

examples (input => possible output)

input 0:

Yeah.

input 1:

Yeah
But
No.

input 2:

Yeah
But
No
But
Yeah.

input 3:

Yeah
But
No
But
Yeah
But
No.
Yeah!       <optional>

...

input 5:

Yeah
But
No
But
Yeah
But
No.
Yeah
But
No
But
Yeah.

JavaScript (Node.js), 80 bytes

a=>{s='';for(i=0;i<a+1;i++)s+=(i%2==0?'yeah':'no')+(i<a?'\nbut\n':'.');return s}

Try it online!


Recursive 2x2 determinant The determinant of a 2 by 2 matrix

a b
c d

is given by ad - bc.

Given a matrix of digits with dimensions 2n by 2n, n ≥ 1, output the result obtained by recursively computing the determinant of each 2 by 2 sub-block until we reach a single number.

For example, given the input

3 1 4 1
5 9 2 6
5 3 5 8
9 7 9 3

After one step, we obtain:

(3*9 - 1*5)    (4*6 - 1*2)    =    22  22
(5*7 - 3*9)    (5*3 - 8*9)         8  -57

And iterating once more, we get:

(22*-57 - 22*8) = -1430

Hence, the output should be -1430.

Rules

The elements of the matrix will always be single digit integers, i.e. 0 to 9.
You may take input in any convenient list or string format, as long as no preprocessing of data is done. Since the matrix is always square, you may take input as a single 1D list instead of a 2D list if you wish.
Input can be via function input, STDIN, command-line argument or closest alternative.
Output should be a single integer to function output, STDOUT or closest alternative. You may not output the single integer in a list or matrix.
You may use builtin determinant and matrix manipulation methods if your language happens to support them.
Your algorithm must work in theory for any valid input.
Standard code-golf rules apply.

Test cases

The following test cases are given as Python-style lists:

[[1,0],[0,1]] -> 1
[[1,9],[8,4]] -> -68
[[0,1,2,3],[4,5,6,7],[8,9,0,1],[2,3,4,5]] -> 40
[[3,1,4,1],[5,9,2,6],[5,3,5,8],[9,7,9,3]] -> -1430
[[9,0,0,9],[0,9,9,0],[9,0,9,0],[0,9,0,9]] -> 13122
[[1,0,0,0,0,0,0,0],[2,1,0,0,0,0,0,0],[3,2,1,0,0,0,0,0],[4,3,2,1,0,0,0,0],[5,4,3,2,1,0,0,0],[6,5,4,3,2,1,0,0],[7,6,5,4,3,2,1,0],[8,7,6,5,4,3,2,1]] -> 1
[[7,1,0,5,8,0,1,5],[9,9,6,6,1,2,4,8],[4,8,7,3,8,7,4,7],[4,6,1,9,7,0,1,7],[7,6,7,1,9,4,1,6],[8,0,0,8,5,5,9,9],[4,6,4,8,9,4,8,6],[9,0,8,7,6,2,1,5]] -> 2937504
[[1,2,3,4,5,6,7,8],[2,3,4,5,6,7,8,1],[3,4,5,6,7,8,1,2],[4,5,6,7,8,1,2,3],[5,6,7,8,1,2,3,4],[6,7,8,1,2,3,4,5],[7,8,1,2,3,4,5,6],[8,1,2,3,4,5,6,7]] -> -10549504
[[1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0],[0,1,1,1,1,0,0,1,0,1,1,1,1,1,1,0],[1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,0],[0,1,1,1,1,0,0,0,0,1,1,1,1,1,0,1],[1,0,1,0,1,1,1,0,0,1,1,1,1,0,1,0],[0,0,1,1,1,0,1,1,1,1,1,1,1,0,0,0],[1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1],[1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1],[1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1],[0,1,1,1,1,1,1,1,1,0,0,1,0,1,0,1],[1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[1,1,0,1,1,0,1,1,1,1,1,0,0,1,1,0],[1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[1,0,1,0,0,1,0,1,0,1,1,1,1,1,0,1],[1,1,1,1,1,1,1,1,1,0,0,1,1,1,0,1]] -> -8

(Thanks to @MartinBüttner for help with this challenge)

J, 21 25 bytes

0{0{(_2(_2-/ .*\|:)\])^:_

Usage:

   ]input=.(3,1,4,1),(5,9,2,6),(5,3,5,8),:(9,7,9,3)
3 1 4 1
5 9 2 6
5 3 5 8
9 7 9 3
   (0{0{(_2(_2-/ .*\|:)\])^:_) input
_1430

At every step we cut up the matrix to 2-by-2's and compute each ones determinant resulting in the next step's input matrix. We repeat this process until the result doesn't change (the final element is the determinant itself). We convert the final result to a scalar with 0{0{.

Try it online here.


Output the first position in your program for each input character Challenge

Write a non-empty program/function p that, given a non-empty input string s, outputs the position of the first occurrence of each character of s in the source code of p.

For example, if your program is

main() { cout << magic << cin }
^0   ^5   ^10  ^15  ^20  ^25

and it receives an input abcd{, the output should be

[1, x, 9, x, 7] (0-based)        [2, x, 10, x, 8] (1-based)

Here, x represents any output that is not a valid output for a character position (e.g., a negative number, 0 if you use 1-based indexing, NaN, Inf, the string potato, a number greater than your program's length, etc).

Restrictions

Reading the source code is not allowed (like in a proper quine). The use of comments is allowed, but does count towards your score.

Input and output can be done in a reasonable format, but must be unambiguous (only additional delimiters, no rand stream and claiming that the answer is somewhere in there), consistent (e.g., the x from above should always be the same value) and human-readable; for example, a string or a character array. You can assume that the input is a string (or array) of printable ASCII characters; no need to handle the entire Unicode set.

Custom code-page or non-printable ascii in your code?

If your language uses a custom code-page (Jelly, APL, etc), you must take that into account (so a program €æÆ must output [1, x, 2] for an input €%æ). Using only non-ASCII characters to output -1 always (since the input is ASCII-only) is not a valid solution. You may assume that your program natively accepts your custom codepage, i.e., if your program has a method of converting a character A to an integer 65 (ASCII encoding), you may assume that it now converts the 65th character in your codepage to 65.

Inspired on the following challenge: Positional Awareness

Python2, 55 Bytes

a=" )dfi(+m,nprut.';";print map(('a="'+a).find,input())

Starts with a string that contains all the characters used in the code, and then search the indexes


Rock Paper Scissors (Sorta) Quine Create three programs, which we'll call Rock, Paper, and Scissors.

Each program must be unique, and accept input.

If a program gets any input which is not one of the programs Rock, Paper or Scissors, it must print itself.

RPS style, the programs will each print one of the following four outputs:

"win" if the running program beats the program that is being input
"lose" if the running program loses against the program that is being input
"tie" if the input is equal to the source code of the running program
The source code of the running program itself for any other input (including an empty input)

General rules:

The three programs can be in any language. Rock can be in a different language from Paper: same for any other pair.
They are not restricted by size.
They must print through STDOUT or closest equivalent, and must print strings or closest equivalent. They must not print to STDERR.
They need not be full programs. They can be functions, if you wish to get rid of the stuff needed in a program, like C's #includes.

This is a code-golf challenge, where your score is determined by the sum of the programs' sizes. The person with the lowest score wins.
If two people have the same score, the person whose largest program by bytes out of the set Rock, Paper, Scissors is smaller wins.

Python 3, 273, 489, 429  bytes

Rock:

r=['tie', 'lose', 'win'];s="i=input();t=[f'r={r[n:]+r[:n]};s={s!r};exec(s)'for n in[0,1,2]];print(i in t and r[i.find('t')//7]or t[0])";exec(s)

Try it online against itself!
Try it online against Paper!
Try it online against Scissors!
Try it online against rubbish!

Paper:

r=['win', 'tie', 'lose'];s="i=input();t=[f'r={r[n:]+r[:n]};s={s!r};exec(s)'for n in[0,1,2]];print(i in t and r[i.find('t')//7]or t[0])";exec(s)

Try it online against itself!
Try it online against Scissors!
Try it online against Rock!
Try it online against garbage!

Scissors:

r=['lose', 'win', 'tie'];s="i=input();t=[f'r={r[n:]+r[:n]};s={s!r};exec(s)'for n in[0,1,2]];print(i in t and r[i.find('t')//7]or t[0])";exec(s)

Try it online against itself!
Try it online against Rock!
Try it online against Paper!
Try it online against trash!

The same as the previous version, but check that the input exactly matches the source code of one of the programs.

Try it online (together)!

Old (invalid) version

Rock:

s="print(['tie','lose','win','s='+repr(s)+';exec(s)',''][input().find('ti')//7-1])";exec(s)

Paper:

s="print(['win','tie','lose','s='+repr(s)+';exec(s)',''][input().find('ti')//7-1])";exec(s)

Scissors:

s="print(['lose','win','tie','s='+repr(s)+';exec(s)',''][input().find('ti')//7-1])";exec(s)

Try it online!

Three almost identical programs (all with 91 bytes), the only difference is the order of the win/tie/lose, which each program uses the position of the 'tie' to determine the result from it's own ordering.

As pointed out, these programs are invalid, as they will only print out themselves if the input doesn't contain 'ti' (or the 'ti' is in a certain place).


Lyndon word factorization Background
A Lyndon word is a non-empty string which is strictly lexicographically smaller than all its other rotations. It is possible to factor any string uniquely as the concatenation of Lyndon words such that these subwords are lexicographically non-increasing; your challenge is to do this as succinctly as possible.
Details
You should implement a function or program which enumerates the Lyndon word factorization of any printable ASCII string, in order, outputting the resultant substrings as an array or stream of some kind. Characters should be compared by their code points, and all standard input and output methods are allowed. As usual for code-golf, the shortest program in bytes wins.
Test Cases
''           []
'C'          ['C']
'aaaaa'      ['a', 'a', 'a', 'a', 'a']
'K| '        ['K|', ' ']
'abaca'      ['abac', 'a']
'9_-$'       ['9_', '-', '$']
'P&O(;'      ['P', '&O(;']
'xhya{Wd$'   ['x', 'hy', 'a{', 'Wd', '$']
'j`M?LO!!Y'  ['j', '`', 'M', '?LO', '!!Y']
'!9!TZ'      ['!9!TZ']
'vMMe'       ['v', 'MMe']
'b5A9A9<5{0' ['b', '5A9A9<5{', '0']

Pyth, 17 16 bytes

-1 byte thanks to isaacg!

hf!ff>Y>YZUYT+./

Try it online!

Explanation

hf!ff>Y>YZUYT+./
              ./    Take all possible disjoint substring sets of [the input]
             +      plus [the input] itself (for the null string case).
 f                  Filter for only those sets which
  !f        T       for none of the substrings
    f  >YZUY        is there a suffix of the substring
     >Y             lexographically smaller than the substring itself.
h                   Return the first (i.e. the shortest) such set of substrings.


Prime containment numbers (golf edition) This is sequence A054261.

The \$n\$th prime containment number is the lowest number which contains the first \$n\$ prime numbers as substrings. For example, the number \$235\$ is the lowest number which contains the first 3 primes as substrings, making it the 3rd prime containment number.

It is trivial to figure out that the first four prime containment numbers are \$2\$, \$23\$, \$235\$ and \$2357\$, but then it gets more interesting. Since the next prime is 11, the next prime containment number is not \$235711\$, but it is \$112357\$ since it's defined as the smallest number with the property.

However, the real challenge comes when you go beyond 11. The next prime containment number is \$113257\$. Note that in this number, the substrings 11 and  13 are overlapping. The number 3 is also overlapping with the number 13.

It is easy to prove that this sequence is increasing, since the next number needs to fulfill all criteria of the number before it, and have one more substring. However, the sequence is not strictly increasing, as is shown by the results for n=10 and n=11.

Input

A single integer n>0 (I suppose you could also have it 0-indexed, then making n>=0)

Output

Either the nth prime containment number, or a list containing the first n prime containment numbers.

The numbers I have found so far are:

 1 =>             2
 2 =>            23
 3 =>           235
 4 =>          2357
 5 =>        112357
 6 =>        113257
 7 =>       1131725
 8 =>     113171925
 9 =>    1131719235
10 =>  113171923295
11 =>  113171923295
12 => 1131719237295

Note that n = 10 and n = 11 are the same number, since \$113171923295\$ is the lowest number which contains all numbers \$[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]\$, but it also contains \$31\$.

Since this is marked code golf, get golfing! Brute force solutions are allowed, but your code has to work for any input in theory (meaning that you can't just concatenate the first n primes). Happy golfing!

05AB1E, 8 bytes

∞.ΔIÅpåP

Try it online!

Explanation

           # from
∞          # a list of infinite positive integers
 .Δ        # find the first which satisfies the condition:
       P   # all
   IÅp     # of the first <input> prime numbers
      å    # are contained in the number


all occurences of each line from a file in another file for each line in the first file This is a code golf problem: Say you have two files, one file s and one  file h. The problem is that for each line l of s you should produce a list that contains all lines of h that contain l. By "contain" I mean a substring, so, for example the line "foobar12baz" contains either foo, bar, foobar, 12, 1 or baz, etc...

You may use any programming language or any program to accomplish this in the least number of characters possible. Instead of a list you may print an array, or other sequence type structure.

Here is some Haskell I wrote that does it in 103 characters, and assumes you have the following modules imported

Data.List

Control.Monad

Control.Applicative

let f = (<$>) lines . readFile in (\(a,b)-> [[d|d<-b, isInfixOf c d]|c<-a]) <$> liftM2 (,) (f "s") (f "h")

Example files:

"h"

asdf1
asd2asdf
s3adsf

"s"

1
2
3

Output:

[["asdf1"],["asd2asdf"],["s3adsf"]]


Tips for golfing in PARI/GP PARI/GP is a free computer algebra system. It is designed for (algebraic) number theory, not golfing, but that's part of the attraction. Unsurprisingly, it fares best at mathematical tasks; its support for string manipulation is primitive. (Having said that, advice for golfing non-mathematical tasks is also welcome.)

As usual, please post one tip per answer.

These tips should be at least somewhat specific to PARI/GP; advice which applies to 'most' languages belongs at Tips for golfing in <all languages>. Some general tips which don't need to be included:

Compress whitespace. (In GP all whitespace outside of strings is optional.)
Use single-character variables. (There are 50 choices, a-z and A-Z except I and O.)
Use < and > rather than <= and >= when possible.
Chain assignments. (a=b=c or a+=b*=c)

Use operators to replace commands (or longer operators!) when possible.

length(v) → #v (saves 5-7 bytes)

matsize(M)[2] → #M (saves 9-11 bytes)

matsize(M)[1] → #M~ (saves 8-10 bytes)

floor(x) → x\1 (saves 3-5 bytes)

round(x) → x\/1 (saves 2-4 bytes)*

shift(x,n) → x>>n or x<<n (saves 2-6 bytes)

sqr(x) → x^2 (saves 1-3 bytes)

deriv(x) → x' (saves 4-6 bytes)

mattranspose(M) → M~ (saves 11-13 bytes)

factorial(n) → n! (saves 8-10 bytes)

&& → & (saves 1 byte; note that this syntax is deprecated)

|| → | (saves 1 byte; only works in older versions)

* Prior to 2.8.1 (2016) the \/ operator did not work correctly on t_REAL numbers—update if you haven't!


The sum of consecutive odd numbers Although related challenges have been asked, this one is different to warrant its own question.

Challenge

Given a positive integer, return the longest sequence of consecutive positive odd integers whose sum is the given integer. If no such sequence exists, you may report an error in whatever way makes sense for your language, including returning a falsy value or throwing an exception.

Test Cases

  1 -> [1]
  2 -> []
  3 -> [3]
  4 -> [1, 3]
  5 -> [5]
  6 -> []
  9 -> [1, 3, 5] (note that [9] is not a valid answer)
 15 -> [3, 5, 7]
104 -> [23, 25, 27, 29] (note that [51, 53] is not a valid answer)

Scoring

This is code-golf, so the shortest answer in each language wins.

Haskell, 67 65 63 62 58 bytes

Saved 4 bytes thanks to Julian Wolf

f x=[[2*n+1,2*n+3..2*m]|n<-[0..x],m<-[n..x],m^2-n^2==x]!!0

Try it online!

I check if the number can be expressed as he difference of two squares: m^2-n^2. I can then construct the list of consecutive odd numbers: [2n+1,2n+3...2m-1]. Note that because the minimum n is chosen, the longest list will be output


Three polyglots, two period-two quines, and one code-golf challenge Produce a program A such that running it in language A produces Program B, and running program A in language B produces program C.

Program B, when run in language B produces Program A, and running program B in language A produces program C.

Program C, when run in language A or language B, prints "Wrong language!".

Program | Language | Result
--------|----------|----------
A       | A        | Program B
B       | B        | Program A
A       | B        | Program C
B       | A        | Program C
C       | A        | "Wrong language!"
C       | B        | "Wrong language!"

Your answer should use this template:

Language A/Language B, {a bytes} + {b bytes} = {total bytes} bytes

Program A:

a code

Program B:

b code

Program C:

c code

Source:

# Language A/Language B, <a bytes> + <b bytes> = <total bytes> bytes

Program A:

    a code
Program B:

    b code
Program C:

    c code

None of these programs should take input.
Different versions of the same language do count as different languages. (although this is discouraged because it leads to boring solutions)
Languages A and B must be distinct.
You must not read your own source code from a file. Programs may not be empty
Standard loopholes apply.

Hints

C++ and [Python/Bash/other # commented languages] are good combos because you can define macros that one language can ignore

This is code-golf, so the smallest sum of the byte counts Program A and B wins.

JavaScript (ES6) / Python 3, 264 + 258 = 522 bytes

Program A:

a="a=%r;b=%r;c=%r;1//2;print(c);'''\nconsole.log(b,...[a,b,c].map(uneval))//'''";b="a=%s;b=%s;c=%s;1//2;'''\nprint=_=>console.log(c)//'''\nprint(a%(a,b,c))";c="1//2;alert=print\nalert('Wrong language!')";1//2;print(c);'''
console.log(b,...[a,b,c].map(uneval))//'''

Program B:

a="a=%r;b=%r;c=%r;1//2;print(c);'''\nconsole.log(b,...[a,b,c].map(uneval))//'''";b="a=%s;b=%s;c=%s;1//2;'''\nprint=_=>console.log(c)//'''\nprint(a%(a,b,c))";c="1//2;alert=print\nalert('Wrong language!')";1//2;'''
print=_=>console.log(c)//'''
print(a%(a,b,c))

Program C:

1//2;alert=print
alert('Wrong language!')

Probably golfable...

JavaScript explanation

Program A:

// Set a, b, and c to these strings:
a="a=%r;b=%r;c=%r;1//2;print(c);'''\nconsole.log(b,...[a,b,c].map(uneval))//'''";
b="a=%s;b=%s;c=%s;1//2;'''\nprint=_=>console.log(c)//'''\nprint(a%(a,b,c))";
c="1//2;alert=print\nalert('Wrong language!')";

// Ignore this line:
1//2;print(c);'''

// Print the Python program (b), replacing the "%s"s with the raw forms of a, b, and c:
console.log(b,...[a,b,c].map(uneval))//'''

Program B:

// Set a, b, and c to these strings:
a="a=%r;b=%r;c=%r;1//2;print(c);'''\nconsole.log(b,...[a,b,c].map(uneval))//'''";
b="a=%s;b=%s;c=%s;1//2;'''\nprint=_=>console.log(c)//'''\nprint(a%(a,b,c))";
c="1//2;alert=print\nalert('Wrong language!')";

// Ignore this line:
1//2;'''

// Define a function `print` which prints `c` (the "Wrong language!" program):
print=_=>console.log(c)//'''

// Call `print`, ignoring the argument (which is NaN):
print(a%(a,b,c))

Program C:

// Ignore this line:
1//2;alert=print

// Alert "Wrong language!":
alert('Wrong language!')

Python explanation

Program A:

# Set a, b, and c to these strings:
a="a=%r;b=%r;c=%r;1//2;print(c);'''\nconsole.log(b,...[a,b,c].map(uneval))//'''";
b="a=%s;b=%s;c=%s;1//2;'''\nprint=_=>console.log(c)//'''\nprint(a%(a,b,c))";
c="1//2;alert=print\nalert('Wrong language!')";

# Print `c` (the "Wrong language!" program):
1//2;print(c);

# Ignore this part:
'''
console.log(b,...[a,b,c].map(uneval))//'''

Program B:

# Set a, b, and c to these strings:
a="a=%r;b=%r;c=%r;1//2;print(c);'''\nconsole.log(b,...[a,b,c].map(uneval))//'''";
b="a=%s;b=%s;c=%s;1//2;'''\nprint=_=>console.log(c)//'''\nprint(a%(a,b,c))";
c="1//2;alert=print\nalert('Wrong language!')";

# Ignore this part:
1//2;'''
print=_=>console.log(c)//'''

# Print the JS program (a), replacing the "%r"s with the raw forms of a, b, and c:
print(a%(a,b,c))

Program C:

# Set `alert` to the function `print`:
1//2;alert=print

# Call this function on "Wrong language!":
alert('Wrong language!')


The greedy regex (cops) This is the cops' post. The robbers' is here.

You make a program and a regex.

For most inputs, one of the following happens:

the regex doesn't match, and the program returns a falsey value
the regex doesn't match, and the program returns a truthy value
the regex matches, and the program returns a truthy value

But for one (or more) input, the regex matches, but the program returns a falsy value.

You should try to keep this input hidden. Robbers will try to find an input where the regex matches, but the program returns a falsy value.

Post your program and your regex, as well as your language name, byte count of the program, regex flavor, and byte count of the regex.

If a robber finds an input where the regex matches, but the program returns a falsy value, even if it wasn't the intended input your program is considered cracked, and you edit in a link to the robber's crack.

If nobody has cracked your program & regex after a week, then edit in that your submission is safe and is therefore not eligible for cracking. Also edit in the intended input. The shortest (program bytes + regex bytes) non-cracked submission wins.

Example

Let's say your regex is (all of the flavors):

/^[0-9]$/

And your program is (JS):

x=>Boolean(parseInt(x))

Then a valid crack would be 0, because the regex matches 0 but 0 is falsey.

Delimiters don't count in the byte count.

I can't enforce the banning of hash functions with rules, but please don't use SHA/RSA or anything that is unfair to the robbers

Python, cracked
Regex: (?!.)
Program: from operator import not_
This is a little easier than my previous one.


Empty a Swimming Pool . . . With Only a Red Solo Cup You have a swimming pool that is filled to the brim with water. You need to empty it, but you can't think of an efficient method. So you decide to use your red solo cup. You will repeatedly fill the cup all the way and dump it outside the pool.

Challenge

How long will it take to empty the pool?

Input

[shape of pool] [dimensions] [shape of cup] [dimensions] [speed]

shape of pool will be one of these strings: circle, triangle, or rectangle. Note that these actually refer to the 3-dimensional shapes: cylinder, triangular prism, and rectangular prism.
dimensions will be different depending on the shape.

circle: [radius] [height]. Volume = π r2 h
triangle: [base] [height] [length]. Volume = 1/2(bh) * length
rectangle: [width] [length] [height] Volume = lwh

shape of cup and dimensions work the same way. The cup can also be either a circle, triangle, or rectangle.
speed is the amount of time it takes to empty one cup full of water in seconds.

Output

The number of seconds it takes to empty the swimming pool. This can be rounded to the nearest second.

Notes

There will be no units in the input. All distance units are assumed to be the same (a shape won't have a height in inches and a width in feet).
Use 3.14 for pi.
Input will be made up of strings and floating-point numbers.
It will never rain. No water will ever be added.
You have a very steady hand. You will fill the cup exactly to the brim every time, and you will never spill any.
Once you get near the end, it will get hard to scoop up a full cup of water. You do not need to worry about this. You're very strong, so you can tilt the pool onto its side (without using up any more time).
Anytime you make a calculation, it's okay to round to the nearest hundredth. Your final answer will not need to be exact.

Test Cases

Input: triangle 10 12.25 3 circle 5 2.2 5
Output: 10
Even though there is less than 172.7 left on the last scoop, it still takes the whole five seconds to empty it.

Input: triangle 5 87.3 20001 rectangle 5.14 2 105.623 0.2
Output: 804.2

You should round to the nearest hundredth after each calculation.
The final calculation is rounded up from 804.05567 to 804.2. This is because that last little bit of water must be emptied.

Rules

You can write a full program or function.
Input should be taken from stdin or function parameters. Output should be printed through stdout or returned.
The input format can be rearranged, as long as you specify that in the submission. You can also shorten the strings "circle", "triangle", and "rectangle."
Libraries and built-in functions that involve volume or area are not allowed.

Scoring

This is code-golf. Submission with least number of bytes wins.

JavaScript ES6, 100 78 82 81 74 bytes

Thanks to @UndefinedFunction for helping golf off 4 bytes

(a,z,d,f=([a,g,k,p])=>g*k*(a[6]?p/-~!a[8]:3.14*g))=>Math.ceil(f(a)/f(z))*d

Usage:

t(["triangle",10,12.25,3],["circle",5,2.2],5);


The time after some time For this challenge, we are writing the time in the following form: hh:mm:ss
Some examples:

12:34:08
06:05:30
23:59:00

The challenge is to output the time after an amount of hours, minutes and seconds have elapsed, with as starting time 00:00:00. You can compare this with a timer that started at 00:00:00.
Here is an example of inputs (using STDIN) and outputs:
Input: 1h20m5s
Output: 01:20:05

Input: 0h100m0s
Output: 01:40:00

After 24 hours, the timer resets itself:
Input: 25h0m0s
Output: 01:00:00

The form of the input is always the same: XhYmZs, with X hours, Y minutes and Z seconds (assume that X, Y and Z are whole integers less than 100000 and never negative)
This is code-golf, so least amount of bytes wins this challenge

Ruby - 131 115 107 97 84 bytes

I'm still golfing it.

h,m,s=gets.split(/\w/).map &:to_i;$><<"#{(h+m/60+s/3600)%24}:#{(m+s/60)%60}:#{s%60}"

Thanks for @Doorknob for /\w/ inshead of /h|m|s/


Pathological Sorting Pathological Sorting

Your boss has demanded that you develop a sorting algorithm to improve the performance of your company's application. However, having written the application, you know that you're unlikely to be able to make it significantly faster. Not wanting to disappoint your boss, you've decided to develop a new algorithm that works even better than *sort on certain sets of data. Of course, you can't make it obvious that the algorithm only works on some cases, so you want to make it obscure as possible.

The objective of this contest is to write a sorting routine in the language of your choice that performs better on certain sets of data than others, with repeatable results. The more specific the classification that determines speed, the better. The algorithm must do sorting of some kind, so an algorithm that depends on the data already being completely sorted (as in, an algorithm that does nothing), or an algorithm that depends on the data being completely sorted in reverse, are both invalid. The sorting algorithm must correctly sort any set of data.

After presenting your routine, please include an explanation of why it only works on certain sets of data, and include test runs on at least one set of good (fast) data and one set of bad (slow) data. The point here is to be able to prove to your boss that you've stumbled upon a better way to sort, so more test data is better. Of course, you're only going to show your boss the test results from the good data, so the flaw in the required testing data can't be too obvious. If applicable to your language, please show that your algorithm is faster than your language's built-in sorting algorithm.

For example, one might submit an insertion sort algorithm, with the good data being data that is already nearly sorted, and bad data being completely random data, since insertion sort approaches O(n) on nearly-sorted data. However, this isn't very good, since my boss would probably notice that all of the testing data is nearly sorted to begin with.

This is a popularity-contest, so the answer with the most votes after 7 days (May 21) wins.

If no one beats me to it, I'd like to submit a community wiki answer that takes advantage of uniformly distributed data sets.

It's been a pretty long time, but I remember back in Algorithms 101 we were taught some sorting algorithm that used randomization. I wasn't a very good student so I don't really remember how it went or why it worked quickly on average.

Nevertheless, I've decided that this problem calls for a solution that uses randomization, which will hopefully work in my favor on average.

import random

def arrayIsSorted (arr) :
    for i in range(len(arr)-1) :
        if arr[i]>arr[i+1] : return False
    return True

def rSort (arr) :
    random.seed (42)
    counter = 0
    while not arrayIsSorted(arr) :
        random.shuffle (arr)
        counter+=1
    print ("Sorted in %d iterations." % counter)
    return arr

Since true randomization is important, I make sure to seed the RNG with the answer to Life, the Universe and Everything. After a bit of testing it turns out that that was a smart move! Check out how fast these 2 completely arbitrary lists get sorted:

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

Both of these get sorted in only 1 iteration - you couldn't possibly ask for a faster function than that!

Now, admittedly, some other lists produce slightly worse results...

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

These get sorted in 4,176 and 94,523 iterations respectively, which actually takes more than a second... but let's just keep that fact to ourselves so as not to distract anyone from how amazing this algorithm is!

Edit:

I've been asked to prove my algorithm's efficiency on a list of 100 items, so here you go:

rSort ([70, 6, 52, 97, 85, 61, 62, 48, 30, 3, 11, 88, 39, 91, 98, 8, 54, 92, 44, 65, 69, 21, 58, 41, 60, 76, 27, 82, 93, 81, 20, 94, 22, 29, 49, 95, 40, 19, 55, 42, 43, 1, 0, 67, 35, 15, 51, 31, 16, 25, 5, 53, 37, 74, 86, 12, 13, 72, 56, 32, 47, 46, 59, 33, 80, 4, 45, 63, 57, 89, 7, 77, 14, 10, 34, 87, 18, 79, 9, 66, 24, 99, 64, 26, 78, 38, 90, 28, 83, 75, 68, 2, 17, 73, 96, 71, 23, 84, 36, 50])

Even this long and completely arbitrary list gets sorted instantly! Truly I must have stumbled upon the best sorting algorithm in the world!


Binary Stream With Unknown Byte-Width Context:

You are a cryptographer. You have stumbled upon a mysterious group of individuals, who present you with a challenge, which you must solve in order to join their secret society.

Description:

You have been given a binary stream consisting of 3 byte sequences that have a random width (unchanging per-stream). This stream has the following properties:

The first two bytes in a sequence are randomly generated unsigned binary numbers.

The third byte is the sum of the first two bytes.

If the sum overflows, the carry-bit disappears (That is, it does not affect the first 2 bytes).

The bytes are big-endian.

The byte-width will always be between 3 and 16.

Examples of potential streams:

A stream is an infinite series of 3 byte sequences, where the first 2 bytes are randomly generated for each sequence in the series.
Byte-width = 5: 01001 01010 10011 10010 11101 01111 ... is a valid stream (without spaces, of course). 01001 + 01010 = 10011, and 10010 + 11101 = 01111 (after integer overflow).
Byte-width = 10: 1100110011 0101010101 0010001000 ... is a valid stream. 1100110011 + 0101010101 = 0010001000 (after overflow).

The Rules:

Write a program that consumes the binary stream, and outputs (with 100% certainty) the byte-width. This puzzle has two parts, efficiency and code-golf.
Efficiency: Your score in this section is determined by the average number of bits your program must consume to make it's determination (after N>=1000 runs).
Golf: Your score in this section is determined by the number of characters used in your code. This number does not include the scaffolding to generate the stream, includes/imports, or boilerplate. For example, in C/C++: int main(){ ONLY_THIS_COUNTS }.
Your final score is equal to the multiplication of your scores in both sections. The lowest score wins.

Haskell 59.5 * 228 = 13566

import Data.List
import Data.List.Split
import Prelude.Unicode
import System.Random

findBW strm
 | i == 0    = (16, rest)
 | i < 3     = findBW rest
 | otherwise = (i, rest)

 where
 (bw,rest) = splitAt 4 strm
 i = sum $ zipWith ((*).(2^)) [0..] bw

mkStream i strm = first ++ second ++ sum ++ mkStream i rest
 where
 (first,tmp) = splitAt i strm
 (second,rest) = splitAt i tmp
 sum = reverse $ g (reverse first) (reverse second) 0

run 100000 reps _ = print $ (reps*16*3) / 100000
run n reps gen = do
 p validstream
 run (n+1) (reps+rep) gen2

 where
 (gen1,gen2) = System.Random.split gen
 (bytewidth, rndstream) = findBW $ randomRs (0::Int,1) gen1
 validstream = mkStream bytewidth rndstream
 rep = fst $ until(\(_,t)->sum[1|x<-h#t,x]<2)(\(n,s)->(n+1,tail#s))(1,f validstream)

main = do
 gen <- getStdGen
 run 0 0 gen

r=reverse
(#)=map
h=head
g[]_ _=[]
g(a:b)(c:d)e=mod(a+c+e)2:g b d(div(a+c+e)2)
c(m:n:o:p)=(g(r m)(r n)0≡r o):c p
f s=(scanl1(∧).c.(`chunksOf`s))#[3..16]
p=print.(3+).h.elemIndices True .(h#).until(\t->sum[1|x<-h#t,x]<2)(tail#).f

The average bits consumed in a run on 100,000 streams are around 59.3x / 59.4x , so I take 59.5 as the multiplier. For the golf part I count the characters of function p and it's helper functions, i.e. all characters beginning with r=reverse to the end. p is the function that analyses a bit stream and prints the byte-width.  Note: there are some unicode characters, all counting 1.

How it works: split the bit stream in chunks of 3 bits, 4 bits, ... 16 bits and check for validity. Repeat taking 3 of the chunks for every size until there's only one valid set. That means I consume 3*16 = 48 bits per repetition. Most of the time one ore two repetitions are enough.


Greek Conversion Golf Introduction

You must create a function to convert Arabic numerals into Greek numerals. The input will be an integer less than 1000 and more than 0.

Algorithm

Split number into digits (e.g. 123 -> 1, 2, 3)
Take each digit, and change to character found in table below, for letter symbol or letter name, (e.g. 123 -> 1, 2, 3 -> ΡΚΓ or RhoKappaGamma).

Specifications

No built-in number-system conversion
Result must be capitalized as in example.
Input will be in base 10.

Test Cases

123 -> RhoKappaGamma or ΡΚΓ
8 -> Eta or Η
777 -> PsiOmicronZeta or ΨΟΖ
100 -> Rho or Ρ
606 -> ChiDiGamma or ΧϜ

Table

Α = 1 = Alpha = 913 UTF-8
Β = 2 = Beta = 914 UTF-8
Γ = 3 = Gamma = 915 UTF-8
Δ = 4 = Delta = 916 UTF-8
Ε = 5 = Epsilon = 917 UTF-8
Ϝ = 6 = DiGamma = 988 UTF-8
Ζ = 7 = Zeta = 918 UTF-8
Η = 8 = Eta = 919 UTF-8
Θ = 9 = Theta = 920 UTF-8

Ι = 10 = Iota = 921 UTF-8
Κ = 20 = Kappa = 922 UTF-8
Λ = 30 = Lambda = 923 UTF-8
Μ = 40 = Mu = 924 UTF-8
Ν = 50 = Nu = 925 UTF-8
Ξ = 60 = Xi = 926 UTF-8
Ο = 70 = Omicron = 927 UTF-8
Π = 80 = Pi = 928 UTF-8
Ϙ = 90 = Koppa = 984 UTF-8

Ρ = 100 = Rho = 929 UTF-8
Σ = 200 = Sigma = 931 UTF-8
Τ = 300 = Tau = 932 UTF-8
Υ = 400 = Upsilon = 933 UTF-8
Φ = 500 = Phi = 934 UTF-8
Χ = 600 = Chi = 935 UTF-8
Ψ = 700 = Psi = 936 UTF-8
Ω = 800 = Omega = 937 UTF-8
Ϡ = 900 = SamPi = 992 UTF-8

Pyth, 49 48 46 44 bytes

_s.b@+kNsYc3mC+913d-.iU25smXm17hT4Cd"KGO"17_

Try it here.

Still working on shortening the function to generate the alphabet... and yes, the generator is longer than hardcoding the alphabet by 4 characters, but not in bytes.

_s.b@+kNsYc3[...]_
                 _  get input (implicit) and reverse
            [...]   generate "ΑΒΓΔΕϜΖΗΘΙΚΛΜΝΞΟΠϘΡΣΤΥΦΧΨΩϠ" (see below)
          c3        split into 3 equal chunks
  .b                map over each input digit (as Y) and chunk (as N)...
     +kN            prepend empty string to N (to support digits of 0)
    @   sY          get the Yth element of the empty-string-plus-digits array
 s                  concatenate all the digits
_                   reverse again to put digits back in the right order

Here's how the alphabet-generating function works. Let's take all the codepoints and subtract 913 (the smallest value):

0 1 2 3 4 75 5 6 7 8 9 10 11 12 13 14 15 71 16 18 19 20 21 22 23 24 79

Now let's pull out the ones that don't fit the pattern:

0 1 2 3 4    5 6 7 8 9 10 11 12 13 14 15    16 18 19 20 21 22 23 24
          75                             71                         79

Okay, so the strategy is forming: generate the range 0 to 24 (we'll deal with the missing 17 later), and then insert 75, 71, and 79 at the correct locations.

How can we insert the outliers? Pyth has an .interleave function that takes ex. [1,2,3] and [4,5,6] and results in [1,4,2,5,3,6]. We're going to have to add some placeholders, though, since obviously the outliers are far apart. Let's represent the placeholder with X:

0 1 2 3  4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20 21 22 23 24
X X X X 75 X X X X X  X  X  X  X  X 71  X  X  X  X  X  X  X 79

Right, so the bottom outlier array starts with four Xs. Can we group the outliers to each be preceded by four Xs and see what remains?

0 1 2 3  4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20 21 22 23 24
[four X]75 X X X X X  X [  four X  ]71  X  X  X [  four X  ]79

Now we make another key observation: since 79 comes at the very end, there can be any number of Xs preceding it, and any number of Xs following it as well! This is because interleaving [1,2,3] and [4,5,6,7,8,9] results in [1,4,2,5,3,6,7,8,9]—note that the extra elements in the second array end up at the end, and since they're going to be removed anyway, we can safely allow that.

That means we can normalize this such that every outlier is preceding by four Xs and succeeded by 6:

0 1 2 3  4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20 21 22 23 24
[four X]75[   six X   ] [  four X  ]71[     six X      ] [four X]79[six X]

Great! Now we can simply take the array [75, 71, 79], insert four placeholder values before each element and six after, and then interleave it with the range 0..24.

But wait, what happened to 17? Remember, the top line in all of these examples has been missing 17. We can simply remove the 17 after interleaving; but this leaves another delightfully evil possibility open. You guessed it—the placeholder value we've been referring to as X will be 17. This allows us to remove both the extraneous 17 and all the placeholder values in one fell swoop.

Finally! Here's the code used to implement this:

mC+913d-.iU25smXm17hT4Cd"KGO"17
              m         "KGO"    for each char in the string "KGO"...
                      Cd         take its ASCII value ("KGO" -> 75,71,79)
                m17hT            generate an 11-element array filled with 17
               X     4           replace the 5th element with the ASCII value ^^
             s                   concatenate all of these together
        .iU25                    interleave with range(25)
       -                     17  remove all the 17s
m     d                          for each value in the resulting array...
  +913                           add 913 (to get the real character value)
 C                               convert to character


Multiply Pauli Matrices The Pauli matrices are a set of 2x2 matrices which appear very commonly in quantum physics (no, you don't need to know any quantum physics for this challenge). If we include the identity in the set, the four matrices are:

 σ0 =      σ1 =      σ2 =      σ3 =
[1  0]    [0  1]    [0 -i]    [1  0]
[0  1]    [1  0]    [i  0]    [0 -1]

Multiplying two of these will always give another Pauli matrix, although it may be multiplied by one of the complex phases 1, i, -1, -i. For instance, σ1σ3 = -iσ2.

Your task is to multiply a number of Pauli matrices and return the resulting matrix and phase. Input will be given as a non-empty string of digits 0 to 3 representing the matrices σ0 to σ3. The output should be a string containing a single digit for the resulting matrix, optionally preceded by i, - or -i to indicate the phase (- is for -1).

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

You must not use any built-in (or 3rd-party) features related to Pauli matrices.

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

Test Cases

1 => 1
13 => -i2
000 => 0
123 => i0
03022 => 3
02132230 => -i3
1320130100032 => i2
311220321030322113103 => -2
0223202330203313021301011023230323 => -i0
1323130203022111323321112122313213130330103202032222223 => -1

Python 2, 108 89 87 86 bytes

x=y=0
for m in map(int,raw_input()):x+=m*y and(m-y)%3*3/2;y^=m
print"--i"[~x%4::2]+`y`

(Thanks to @grc and @xnor for the help)

Explanation

Let's split up the coefficient and the base matrix. If we focus on the base matrix only, we get this multiplication table (e.g. 13 is -i2, so we put 2):

  0123

0 0123
1 1032
2 2301
3 3210

which just happens to be the same thing as doing bitwise xor.

Now let's focus on the coefficients. If we let 0123 denote 1,i,-1,-i respectively, we get:

  0123

0 0000
1 0031
2 0103
3 0310

For this we first check if either number is 0 by doing m*y, taking care of the left column and top row. Adding in (m-y)%3 then gives:

  0123

0 0000
1 0021
2 0102
3 0210

which is close, except that we have 2 instead of 3. We account for this by performing *3/2.

For indexing, we notice that if we take the string "--i" and select every second character starting from indices 0123 we get "-i","-","i","".


F̲o̲r̲m̲a̲t̲t̲e̲r̲ (*Unicode* **Markdown** __Formatter__) If you cannot see this post, you can use this image

Your task is to create a markdown parser that outputs Unicode. It should support , , , and ̲̲̲̲̲̲̲̲̲.

Every alphabetical character should be converted into Math Sans. This includes the characters before an underline character.

Underlines: Add a ̲ character (code point 818) after each character. Underlines can be combined with anything else.

There should be no way to escape a control character.

The following combinations should be supported:

 (code point 120224 to 120275 Math Sans)

`   ` (120432 to 120483 Math Monospace)

*  * (120328 to 120379 Math Sans Italic)

**  ** (120276 to 120327 Math Sans Bold)

***  *** (120380 to 120431 Math Sans Bold Italic)

__ ̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲ __ (818 Math Sans with Combining Low Line after each character)

__` ̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲ `__ (Math Sans Monospace with Combining Low Line)

Underline should also support Math Sans Italic, Math Sans Bold, and Math Sans Bold Italic

The final output should not contain the characters used to format the text.

Nesting

Some things can be nested. Underlines can nest with any character and can be put in the inside or outside of another control character. Both of these will have an underline

**Underlines __inside the bold__**
__Bold **inside the underline**__

Other things such as bold, monospace, bold italic, and italic can't nest because there are no charactes for it

**This is `not valid` input and will***never be given*

Ambiguous Formatting Characters

Formatting characters that can be ambiguous will never be given. ** is valid because it is bold, but **** will never be given because it is undefined.

At the end of formatting characters, there will always be another character between the next formatting delimiter of the same character. *format***ing** will not be given because there should be a character before the next *format* **ing** delimiter using *s, however *format*__ing__ could be given because they are different characters used in the delimiter.

**Which is bold ***and which is italic?* <-- Invalid, will never be given
**Oh I see** *now.* <-- Valid

Escaping

Nothing can escape. There is no way to use any of the control characters except for a singular underscore

*There is no way to put a * in the text, not even \* backslashes* <-- All of the asterisks will be italic

Even __newlines
don't interrupt__ formatting <-- newlines don't interrupt will all be underlined

Because the singular _underscore is not a formatting character, it_is allowed_ and will not be removed

Example I/O

Example I

*This* is_a **test** of __the ***markdown*** `parser`__ Multi-line `__should
be__ supported`. Nothing `can\` escape.

Example O

 _   ̲̲̲ ̲̲̲̲̲̲̲̲̲ ̲̲̲̲̲̲̲ - ̲̲̲̲̲̲
̲̲̲ .  \ .

This input is not valid and it doesn't matter what your program outputs:

*This **is not valid** input* because it nests italic and bold

*Neither `is this`* because it nests italic and monospace

*This***Is not valid** Either because it can be interpreted different ways

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

Stax, 75 73 74 70 bytes

Ç╜ÿPÜV►♀b7╛i┴?τ\⌂:Té√╖■♠(µ`ómƒÜKx▬∙═τ½εxÅr∩!E#î⌡╕B┴zäÅéë┘S²↔óh₧≡6ÿ╖iô├

Run and debug it online

The basic approach is store the 4 types of formatting in a bit field, and then get the correct character offset from a lookup using the integer value.  Only 8 values are in the lookup.  The high bit denoting underline is handled separately.

Here's a commented ungolfed version.

m                       Map mode: for each line of input,
                            run the rest of the program, then output
"\*\*|__|."|F           Find all regex matches using pattern. This splits the string into
                            individual characters except for ** and __, which stay together.
                            These will be called "atoms" of the input.
{                       begin a block
  VAVa+                 Construct "ABC..XYZabc..xyz"
  "_*``_****__"_I       Get the index of the current atom in "_*`_****__"
  0|MY                  Take the maximum with zero, then store in register y.
                            This gives {*: 1, `: 2, **: 4, __: 8} and 0 for all else.
  x|^X                  Xor with the x register and write back. It stores bitflags for 4 modes.
  "&6mU*9*9 0E*9 !"!@   Index into codepoint lookup table using x.
  c52+|r                Build range of 52 consecutive values starting at codepoint.
  \$                    Build translation string by combination with the alphabetic string.
  |t                    Perform translation on the current atom.
  818+                  Add codepoint 818 to the current atom.
  x8<T                  Remove it again if x<8.  This is iff underline mode is off.
  y!*                   Multiply by the logical not of y.  If the atom is for formatting,
                        this eliminates output for this atom
m                       map over atoms using the enclosed block

Run this one


Take the square root of a string Motivation

In this challenge your task was to multiply two strings, this naturally introduces a way to take the square root of a string.

How does it work?

Given a string (for example pub) the first thing you need to do, is to determine the ASCII code for each character:

"pub" -> [112, 117, 98]

Next you map these codes to the range [0..94] by subtracting 32 of each value:

[112, 117, 98] -> [80, 85, 66]

Now you need to find for each value its root modulo 95 (eg. 40*40 % 95 = 80, you could also pick 55):

[80, 85, 66] -> [40, 35, 16]

And finally you'll map it back to the range [32..126] and convert it back to a string:

[40, 35, 16] -> [72, 67, 48] -> "HC0"

Indeed "HC0" ⊗ "HC0" = "pub" as you can verify with a solution from the other challenge here.

The ones familiar with modular arithmetic probably noticed that the square root modulo 95 does not always exist, for example there's no root for 2. In such a case the square root of a string is not defined and your program/function may crash, loop indefinetly etc.

For your convenience, here's the list of chars that have a square root (the first one is a space):

 !$%&)+03489:>CDGLMQVW]`bjlpqu

Rules

You will write a program/function that takes a string (or list of chars) as an argument and returns any square root if it exists
You may assume that the input always has a square root
The input may consist of an empty string
The input will be in the printable range ([32..126])
The output is either printed to the console or you return a string if the square root exists
In case the square root doesn't exist, the behavior of your program/function is left undefined
If you choose to print the root to the console trailing newlines or whitespaces are fine

Test cases

Note that these are not necessarily the only solutions:

''              -> ''
'pub'           -> 'HC0'
'pull!'         -> 'HC33!'
'M>>M'          -> '>MM>'
'49'            -> '4%'
'64'            -> undefined
'Hello, World!' -> undefined

sh + coreutils, 58 bytes

tr '$%&)+0389:>CDGLMQVW]`bjpqu' 1u.#:BFO%+M/L2Aa,795d0@H=C

Try it online!

The modular square root is typically not unique; we have 2 or 4 choices for each character except .  We don’t need to translate , !, 4, l since each is already a square root of itself.  For the remaining characters, we choose images that don’t need to be escaped for the shell or tr.


Remove single line and multiline comments from string Goal

Using the programming language of your choice, write the shortest program to eliminate comments from a string representing a C program.

Input

The string can be taken as any form of input, but it may also be taken as a variable.

Instructions

Two different kinds of comments are to be removed:

multiline comments, starting with /* and ending with */
single line comments, starting with // and ending with Linux-style line breaks (LF, \n)

Comments within strings are not to be deleted. For the purpose of this challenge, you only need to consider "-delimited strings. In particular, you can ignore the possibility of '-delimited character literals. You may also ignore trigraphs and line continuations (/\<LF>*...).

Examples

Input:

#include <stdio.h>

int main(int argc, char** argv)
{
    // this comment will be removed
    if (argc > 1) {
        printf("Too many arguments.\n");   // this too will be removed
        return 1;
    }
    printf("Please vist http://this.will.not.be.removed.com\n");
    printf("/* This will stay */\n");
    printf("\"/* This will stay too */\"\n");
    printf("//and so will this\\");
    // but not this
    printf("just \"ano//ther\" test.");
    return 0;
}

Output:

#include <stdio.h>

int main(int argc, char** argv)
{

    if (argc > 1) {
        printf("Too many arguments.\n");
        return 1;
    }
    printf("Please vist http://this.will.not.be.removed.com\n");
    printf("/* This will stay */\n");
    printf("\"/* This will stay too */\"\n");
    printf("//and so will this\\");

    printf("just \"ano//ther\" test.");
    return 0;
}

Input:

/*
    this shall disappear
*/
#include <string>
int main(int argc, char** argv)
{
    string foo = ""/*remove that!**/;
    // Remove /* this
    int butNotThis = 42;
    // But do */ remove this
    int bar = 4 /*remove this*/* 3; // but don't remove that 3. */
    return 0;//just a comment
}/*end of the file has been reached.*/

Output:

#include <string>
int main(int argc, char** argv)
{
    string foo = "";

    int butNotThis = 42;

    int bar = 4 * 3;
    return 0;
}

Shell + coreutils + gcc compiler collection, 31 bytes
This answer may seem a bit loopholey, but I didn't see anything specifically banning it in the question.
Rather than using clumsy regular expressions, why not use the tool that was built for the job.  It should have no problem giving correct results:
cpp -fpreprocessed -o- -|sed 1d

Takes input from STDIN and output to STDOUT.  Normally ccp will do all preprocessing (header files, macro expansion, comment removal, etc), but with the -fpreprocessed option, it will skip most of the steps, but it will still remove comments.  In addition, cpp adds a line like # 1 "<stdin>" to the beginning of the output, so the sed is there to delete it.


Code-Challenge:The Nearest Prime Challenge

  In this task you would be given an
  integer N you have to output the
  nearest prime to the integer.

If the number is prime itself output the number.

The input N is given in a single line,the inputs are terminated by EOF.The number of inputs would not exceed 10000 values.

The challenge is to implement the fastest solution so that it can process a maximum of 10000 values as fast as possible.

Input

 299246598
 211571591
 71266182
 645367642
 924278231

Output

 299246587
 211571573
 71266183
 645367673
 924278233

Constraints

N is less than 2^64
Take care of your fingers do not use more than 4096 bytes in your solution.
You can use any language of your choice as long as you are not using it's any inbuilt things for the primes.
Fastest solution,with the most efficient time complexity wins!

ADDED:

This is a easier version of the this same problem (with N < 2^31) so that you may try checking your approach in smaller cases before building it up for this actual problem.

Python

import sys,random

# Miller-Rabin primality test, error rate 2^-200.
def prime(N):
  if N<3:return N==2
  s=0
  d=N-1
  while (d&1)==0:s+=1;d>>=1
  for i in xrange(100):
    a=random.randrange(1,N)
    if pow(a,d,N)!=1 and all(pow(a,d<<r,N)!=N-1 for r in xrange(s)):return 0
  return 1

for N in map(int,sys.stdin):
  d=0
  while 1:
    if prime(N+d):print N+d;break
    if prime(N-d):print N-d;break
    d+=1


Time taken to print numbers Summary

Write a program or function, which doesn't take any input, and outputs all the integer numbers, between -1000 and 1000 in ascending order, to the stdout, one per line, like this:

-1000
-999
-998
-997
...

And after that you need to print the time taken to print these numbers, or the time from the start of the program's execution in milliseconds (if necessary, it can also contain some other things, for example: time taken:xxxms is ok). It can be a float, or an integer (if you print an integer, you need to round down to the nearest).

Example code

using System;
using System.Diagnostics;
class P
{
    static void Main(string[] args)
    {
        Stopwatch st = Stopwatch.StartNew();
        for (int i = -1000; i <= 1000; i++)
        {
            Console.WriteLine(i);
        }
        Console.WriteLine(st.ElapsedMilliseconds);
    }
}

Restrictions

Standard loopholes are not allowed

Other infos

It's code golf, so the shortest submission wins.

Octave, 46 43 36 30 23 bytes
tic;(-1e3:1e3)',toc*1e3

This will print:
ans =

  -1000
   -999
   -998
   -997
   -996
   -995

If you don't like the ans = , then we have to add an additional 6 bytes for disp:
tic;disp((-1e3:1e3)'),toc*1e3

Saved a lot of bytes thanks to a few reminders from rahnema1.
Explanation:
tic;                              % Starts timer
         (-1e3:1e3)'              % A vertical vector -1000 ... 1000
    disp((-1e3:1e3)'),            % Display this vector
                      toc*1e3     % Stop the timer and output the time in milliseconds