Cheating a multiple choice test, part 2 This is sequel to this challenge by Adnan. If you like this challenge, chances are you'll like the other one too. Check it out!

A multiple choice test with 8 questions each with 4 choices might have the answers: BCADBADA. Converted to four different arrays, with true and false if the current letter is the answer, it will look like this

Q#: 1  2  3  4  5  6  7  8
    B  C  A  D  B  A  D  A
A: [0, 0, 1, 0, 0, 1, 0, 1]
B: [1, 0, 0, 0, 1, 0, 0, 0]
C: [0, 1, 0, 0, 0, 0, 0, 0]
D: [0, 0, 0, 1, 0, 0, 1, 0]

This can be compressed using a bit of logic. Each of the choices A, B, C and D can be represented
by two true/false values shown below:

A: 1 0
B: 0 1
C: 0 0
D: 1 1

Using this logic, we can compress the four vectors above to just two:

 1  2  3  4  5  6  7  8
 B  C  A  D  B  A  D  A
[0, 0, 1, 1, 0, 1, 1, 1]
[1, 0, 0, 1, 1, 0, 1, 0]

That is, the solution to your test is simply: 00110111, 10011010. By concatenating these, we get the binary number
0011011110011010, or 14234 in decimal. Use this decimal value to cheat on your test!

Challenge

Take a number N in the (inclusive) range [0, 65535], and output a string with the answer to the multiple choice test.

Test cases:

14234
BCADBADA

38513
ABBDCAAB

0
CCCCCCCC

120
CBBBBCCC

65535
DDDDDDDD

39253
ABCDABCD

The output may be in upper or lower case letters, but you can not use other symbols.

05AB1E, 19 18 16 bytes
Code:
žH+b¦2äøC’c‰±’sè

Uses the CP-1252 encoding. Try it online!
Explanation:
First, we add 65536 to the number (žH is a constant defined to 65536), which is also 10000000000000000 in binary. This is to pad the number with zeroes. Let's take the number 14234 as an example. 14234 + 65536 is equal to 79770. Which in binary is:
10011011110011010

We remove the first character, resulting in:
0011011110011010

We split the string into two pieces using 2ä:
00110111, 10011010

After that, we zip the array with ø:
01, 00, 10, 11, 01, 10, 11, 10

Converting them back into decimal (using C) results in:
1, 0, 2, 3, 1, 2, 3, 2

Now, we only need to index it with the string cbad. The compressed version for this string is ’c‰±’, which can also be tested here. Finally, we get the characters at the index of the above array. For the above example, this results in:
1, 0, 2, 3, 1, 2, 3, 2
b  c  a  d  b  a  d  a


Animating the Separation of Fluids by Density Let the characters 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ represent the particles of 36 immiscible fluids, each more dense than the last. So the 0 fluid is the least dense and floats on all the others, while Z is the densest and always sinks.
Let # represent a solid particle that cannot move at all..
Consider a rectangular grid of some of these 37 characters, with anything out of bounds treated as #. Gravity will want to stabilize them with the least dense fluids on top and the most dense on the bottom.
Our procedure for stabilization is:

Choose a random grid cell c that is not a # and has a density greater than that of at least one of the 3 neighboring cells on the layer below it (southwest, south, and southeast) that is not a #.
Stop procedure if no such choice exists.
Let d be a cell randomly sampled from these valid neighboring cells with the least densities.
Swap the values at c and d.
Repeat procedure until it has stopped.

Example
Running the procedure on
A01
#10
020

might start out step 1 by selecting the A. There is only one cell below it with smaller density so the next grid would be
101
#A0
020

The procedure might continue on as
101 100 000 000
#00 #01 #11 #01
A20 A20 A20 A21

The last arrangement being stable.
Challenge
Write a program that takes in a rectangular string of the 37 characters via stdin, command line, or function call. Initially, the given grid should be printed to stdout, but each time Enter is hit, one swap (step 3) should be done and the grid reprinted, separated from the last grid by an empty line. When the grid with no more possible swaps is printed (the end of the procedure) the program immediately ends.

Grid dimensions will be 1×1 at minimum, and have no maximum size (as limited by Int.Max or computer memory). The grid is not always square.
You can assume valid input. The grid will always be perfectly rectangular, containing only uppercase alphanumeric characters and #.
You may use a key besides Enter if it is more convenient.
Your program must follow [something equivalent to] the stabilization procedure, including using [pseudo]randomness for steps 1 and 2.
In the input (but not the output) underscores (_) may be used instead of newlines.

Scoring
This is code-golf, so the shortest code in bytes wins. There are bonuses however.
Bonus 1 - Horizontal periodic boundary conditions: (minus 30 bytes)
Instead of treating the left and right out of bounds areas as #, connect them with PBC. There should be an option in your code where changing something like 0 to 1 or False to True enables or disables the PBC.
Bonus 2 - Graphics instead of text: (minus 100 bytes)
Instead of using blocks of text, use images (of any common truecolor format). Represent 0...Z with 36 distinct but related colors, e.g. a gradient from white to dark blue, and # with some other distinct color like dark red.
The program behaves the same way except now an image is either saved to a file (it may be the same file each time) or displayed to the screen for each grid swap in place of any textual output. The input may still be textual or some valid image, your choice.
Whether you do this bonus or not, giving output examples is highly encouraged.

Python, 300 298 chars

import random
C=random.choice
R=raw_input
G=list(R().replace('_','\n'))
S=w=G.index('\n')
while S:
 print''.join(G);S=[];R()
 for i,c in enumerate(G):
    B=[(d,j)for j,d in enumerate(G[i+w:i+w+3])if'/'<d<c]
    if B:S+=[(i,[i+w+j for d,j in B if d==min(B)[0]])]
 if S:i,B=C(S);j=C(B);G[i],G[j]=G[j],G[i]

Run it like cat inputfile - | fluid.py.  The input file should be a single line using _ as a line separator.


Recursive Collatz Conjecture The Collatz conjecture postulates that if you take any positive integer, then repeat the following algorithm enough times:
if number is odd, then multiply by three and add one
if number is even, then divide by two

you'll eventually end up at 1. It seems to always work, but it's never been proven that it always does.
You've already golfed calculating how long it takes to get to 1, so I thought I'd switch things up a bit.
Starting with a given positive integer, calculate how long it takes to get to 1 (its "stopping time"). Then find that number's stopping time.
Repeat until you get to 1, or until you get to the entirely arbitrary limit of 100 iterations. In the former case, print how many iterations it took. In the latter case, print "Fail" or some other consistent output of your choice, as long as it's not an integer 1≤n≤100. You may not output an empty string for this option. Outputting an integer outside of the range [1, 100], however, is allowed.
Examples:
Input: 2
2->1
Output: 1

Input: 5
5->5->5->5->5->...
Output: Fail

Input: 10
10->6->8->3->7->16->4->2->1
Output: 8

Input: 100
100->25->23->15->17->12->9->19->20->7->16->4->2->1
Output: 13

Input: 10^100
10^100->684->126->108->113->12->9->19->20->7->16->4->2->1
Output: 13

Input: 12345678901234567890
12345678901234567890->286->104->12->9->19->20->7->16->4->2->1
Output: 11

Input: 1
--Depending on your code, one of two things may happen. Both are valid for the purposes of this question.
1
Output: 0
--Or:
1->3->7->16->4->2->1
Output: 6

As I calculated 10^100 and 12345678901234567890 using a language that only supports reals for that size, if your language is more accurate you may get different results for those.
Scoring
As this is code-golf, the answer with the shortest amount of bytes wins.

Python 2, 70 bytes

f=lambda n,k=0,j=0:n-1and-~f(k*[n/2,n*3+1][n%2]or f(j/99or n,1),k,j+1)

Returns 199 for one hundred or more iterations.

Try it online!


Novel Prime Factors of Repunits The Background

Folks were talking prime factorization in chat and we found ourselves talking about repunits. Repunits are a subset of the numbers known as repdigits, which are numbers consisting of only repeating digits, like 222 or 4444444444444444, but repunits consist only of 1.

The first couple repunits are therefore 1, 11, 111, etc. These are referred to by Rn, so R1=1, R2=11, etc., and are generated by the formula R(n) = (10^n - 1)/9, with n > 0.

Prime factorization of these repunit numbers follows sequence A102380 in the OEIS. For example:

  R1 = 1
  R2 = 11
  R3 = 111 = 3 * 37
  R4 = 1111 = 11 * 101
  R5 = 11111 = 41 * 271
  R6 = 111111 = 3 * 7 * 11 * 13 * 37
  R7 = 1111111 = 239 * 4649
  ...

The Challenge

Write a program or function which, when given an input integer n with n >= 2 via STDIN or equivalent, outputs or returns the novel prime factors for Rn, in any convenient format. "Novel prime factors" here means all x where x is a prime factor of Rn, but x is not a prime factor for any previous Rk, with 1 <= k < n (i.e., if we write the prime factors for all R in sequence, we've not seen x before).

The Examples

Input: 6
Output: 7, 13
(because 3, 11, and 37 are factors of a smaller R_k)

Input: 19
Output: 1111111111111111111
(because R_19 is prime, so no other factors)

Input: 24
Output: 99990001
(because 3, 7, 11, 13, 37, 73, 101, 137, 9901 are factors of a smaller R_k)

Input: 29
Output: 3191, 16763, 43037, 62003, 77843839397
(because no factors of R_29 are also factors of a smaller R_k)

The Extras:

Your code can do anything or nothing if n < 2.
You can assume a "reasonable" upper limit for n for testing and execution purposes -- your code will not be expected to output for n = 10000000, for example, but your algorithm should work for such a case if given unlimited computing power and time.
Here is a site dedicated to the factorizations of repunits for reference.
I've not gone through the math, but I propose a hypothesis that every n has a distinct result for this algorithm -- that is, no n exists such that Rn has no novel factors. I'll offer a 250-point bounty if someone proves or disproves that in their answer. Thomas Kwa proposed an elegant proof, and I awarded the bounty.

Proof that every repunit has a novel prime factor
Using Zsigmondy's Theorem, the proof is simple. From Wikipedia:

In number theory, Zsigmondy's theorem, named after Karl Zsigmondy,
states that if a > b > 0 are coprime integers, then for any integer n
≥ 1, there is a prime number p (called a primitive prime divisor) that
divides an − bn and does not divide ak − bk for any positive integer k
< n, with the following exceptions: [things that don't apply here].

Consider the repunits times 9: that is, 10n-1. By Zsigmondy's Theorem with a=10, b=1, there is some prime p | 10n-1 that does not divide any 10k-1, k < n.

Since p is prime and 10n-1 = 9 · Rn, it must divide either 9 or Rn.

p cannot divide 9, since 9 = 101-1.

Therefore p divides Rn.

p cannot divide any Rk, since it doesn't divide 10k-1 = 9 · Rk.

Therefore the p from Zsigmondy's Theorem is a novel prime factor of any Rn, n ≥ 2. ∎

An example of a repeated novel prime factor
The prime 487 is a repeated prime factor of R486:
By the Fermat-Euler theorem, 10487-1 ≡ 1 (mod 487). The order of 10 mod 487, that is, the smallest power of 10 that is 1 mod 487, therefore must be a divisor of 486. In fact, the order is equal to 486. It also happens that not only is 10486 ≡ 1 (mod 487), it's also 1 (mod 4872).
See here that the order of 10 mod 487 is 486; that is, that no smaller 10k-1 is divisible by 487. Obviously, 487 doesn't divide 9, so it must divide R486.


Polyglot Anagrams Robbers' Thread This is the robbers' thread of this challenge
The cops will choose an OEIS sequence and write two full programs in two different languages that produces that nth item in the sequence when given an n via STDIN.  The two programs must be anagrams of each other, meaning each can be rearranged from the other's letters.
They will present the OEIS number, the source code for and the name of one language it is in.
You must find an anagram of the original cop's submission that runs in a language other than the one used by the cop.  To crack an answer you must only find any language and program which produces the sequence and is an anagram of the original, not necessarily the answer the cop was thinking about.
You may output by character code or include STDERR in your solution, but only if the cop has indicated their hidden solution does so.  Decimal output to STDOUT is always a valid crack.
Thus cops are incentivized to make it as hard as possible to find any language that does the task using their list of symbols.
Scoring
The person with the most cracks will be the winner of this section.  Only the first crack for each solution will count towards one's score.
Leader Board
Big thanks to every one that took place in this challenge.
Here is the leader board as it stands
Place  User             Score
-----------------------------
1      Adnan            3
1      Kritixi Lithos   3
1      Emigna           3
1      milk             3
5      Steven H.        2
5      Wheat Wizard     2
5      jimmy23013       2
8      ETH Productions  1
8      Dennis           1
8      alleks           1
8      Martin Ender     1
8      Oliver           1
8      Conor O'Brien    1

05AB1E, 38 bytes, Loovjo, A000290

nXtdief e():return X*X
pr e(input())##

Try it online!

Very likely not the intended solution, but it works.

Explanation

n      # square input
 X     # push 1
  t    # push sqrt(1)
   d   # push is_number(1.0)
    i  # if true do the rest of the code (1.0 is not a number so it will never execute)


Weirdest way to produce a stack overflow As a programmer you certainly know the error of a stack overflow due to an obvious recursion.
But there are certainly many weird and unusual ways to get your favourite language to spit that error out.

Objectives:

Must cause a stack overflow which is clearly visible on the error output.
Not allowed to use an obvious recursion.

Examples of invalid programs:

// Invalid, direct obvious recursion.
methodA(){ methodA(); }

// Invalid, indirect, but obvious recursion.
methodA(){ methodB(); }
methodB(){ methodA(); }

The most creative ways are the best as this a popularity-contest. I.e, avoid boring obvious answers like this:

throw new StackOverflowError(); // Valid, but very boring and downvote-deserving.

Even though I accepted an answer now, adding more answers is still okay :)

Python

import sys
sys.setrecursionlimit(1)

This will cause the interpreter to fail immediately:

$ cat test.py
import sys
sys.setrecursionlimit(1)
$ python test.py
Exception RuntimeError: 'maximum recursion depth exceeded' in <function _remove at 0x10e947b18> ignored
Exception RuntimeError: 'maximum recursion depth exceeded' in <function _remove at 0x10e8f6050> ignored
$

Instead of using recursion, it just shrinks the stack so it will overflow immediately.


Animation of Code Golf When I see code-golf entries that knock a few characters off, whittling down the code, I go look at the edit history for a side-by-side diff.  See and learn :)

This challenge is to make a program that produces the prettiest animated diffs.

The input will be any ordered series of text versions.
The program may be written in any programming language.
It is allowed that the program limit itself to input data in some specific programming languages.
The program should not be tuned to the specific input data; the program should be generic and work for any ordered series of text versions.
For each version in the input there must be a corresponding time in the output animation where the full text of the version is displayed.  You must animate the diff between version stages, and all version stages must be present and in order in the output.  On these key frames, the version size must be shown and the viewer should understand this is a complete version they are seeing at that point.
The program may not use any third party code to compute the diffs.
Syntax highlighting output is optional.  If the program colours syntax, it may not use any third party code to do so.
The output will be an animated GIF.
The program may use a third party library to author the GIF.
This is a popularity-contest, so as per the definition of popularity-contest on this site, the entry with the most votes wins.

Here's a simple example script that uses Python's ndiff and Pillow's rudimentary animated GIF support and animates each add and remove step:

Personally, I think this a pretty poor job.  It doesn't do syntax highlighting, it doesn't try and move code chunks that get rearranged, it doesn't feel like someone is live editing it, and so on.  It also breaks the rules regards showing the size of the input in bytes on key frames, and it uses a third party library to do the diffing.  Lots of room for improvement!

And hopefully the popular entries will become useful fun tools for the codegolf.stackexchange.com community too.  So its appreciated if the programs are easy for others to get running and use.

(OP)

This is based on the example Python script in the question.

I used the simplest edit distance rather than a cleverer patience diff.

For aligning genomes there's Multi Sequence Alignment algorithms and they could well make an even better job than just considering each pair of adjacent frames?

I was pleasantly surprised how straightforward it was to implement edit distance for the diff, and made it compatible with Python's difflib.ndiff format.  There are plenty of Python implementations of edit distance to be found on the web, but I think my formulation is that little bit tidier and deals with the tricky but essential part of actually determining the path in the table too; in our context, we need to know the steps to turn one into another and not just how many steps there are.

I introduced syntax highlighting using a very simple tokenizer that ought to be able to cope with most c-like languages including, by its laxity, Python and such.  It splits the source into punctuation, whitespace, strings (with escape support) and everything else is an identifier and checked against a list of keywords.  The colouring is also easy to change.

It was easy to integrate the syntax highlighting into a dynamic language; the highlighter outputs a list of character and colour pairs, and the differ is agnostic to whether its diffing strings or any arbitrary iterables of comparables!  An interesting - and deliberate - effect of highlighting first and then diffing is that characters that remain unchanged but change colour get animated.  I didn't want to compute the highlight each frame as that would mean that as you delete a closing string you'd suddenly flash a big chunk of text up as string.

Python's support for authoring GIF is rather limited.  PIL doesn't do it, and Pillow does it rather badly.  I use Pillow, but then have to run through gifsicle to compress and add looping etc; Pillow doesn't correctly write frame timing and doesn't let you manage disposal methods etc, which is a shame as the differ has so much better understanding of the scene than a post-processing step dealing with flattened frames :(

Sourcecode


Decipher a Code Stick Introduction

You're an American spy during the heat of the Cold War and you've managed to intercept a Russian message. Immediately you recognise it as a code stick cipher and wrap it around a pencil. Looking at the paper on the pencil, you don't see anything. Then you try a bigger pencil, and you see it.

Challenge

You have to write a program that deciphers a code stick. As this is code golf, the shortest program wins.

You may use any English dictionaries for looking up words. Some examples of dictionaries include:

Querying a text file of words
Using an inbuilt OS dictionary
Querying an online dictionary (screen scraping etc.)
Using an external lib

All words MUST be valid English words

Your pencils

Each of your pencils has four equally sized faces and are infinitely long. You have five differently sized pencils:

Pencil 1: Shows 1 character on each face
Pencil 2: Shows 2 characters on each face
Pencil 3: Shows 4 characters on each face
Pencil 4: Shows 6 characters on each face
Pencil 5: Shows 8 characters on each face

All ciphers can be deciphered by placing the start of the paper at the top of the pencil and wrapping it down.

Examples

The following is an example of a cipher:

Hepoge slljghadso bvvbgh

This can be deciphered by wrapping it around Pencil 2:

Side 1 | Side 2 | Side 3 | Side 4
-------+--------+--------+-------
He     | po     | ge     |  s
ll     | jg     | ha     | ds
o      | bv     | vb     | gh

So now you have four combinations:

Hello , pojgbv, gehavb,  sdsgh

You can now perform a dictionary lookup and see that Hello is the only valid word. Therefore, Hello is the cracked cipher.

Note: Deciphered codes may have spaces in. Example: Hello World

Test cases

Ciphers can be inputted in any way apart from being hardcoded. The following are a few test cases. You will not be given the pencil size.

boasonespetrabbittonespongomezesray long
lsbvmii derfghthstthasinlomnrtk fg dndthugssawerpoloasefnxafqeormnaqwge padhndi mbavwgam
lipois lisptloopoolsisp lortfippinglthe asse rtedgoodcodeis the best  of enlymoolfangthe  leamingsoulsgodsingering
antidisebd sldkfdw sld sja dmddystablishjzkapxmjhavzlx dld slzbfmentariabahdjdlljagzlxbxlffnd ldnism is hdbsh spjalcpdhstd flcnda very cbd skd alsbfo kfvwfd xlconvolutehs ska ckw dlc fjzlxbckxd word  hs sla k dk skdnlcjcu dk

Any more test cases would be appreciated

Answers to the test cases

   1: astronomy
 2: i think therefore i am
 3: is lisp the code of the gods
 4: antidisestablishmentarianism is a very convoluted word

Script to generate code stick ciphers:

import string, random, math

word = input('Word:\t')
n = int(input('Pencil:\t'))
pencil = int(-((4*(17*n-77))/((n**4)-(19*n**3)+(136*n**2)-(444*n)+566)))

alpha = string.ascii_lowercase+' '
cipher = ''

side = random.randint(1, 4)
sides =['','','','']

for j in range(len(sides)):
    if j+1 == side:
        sides[j] = word
        if len(word)%pencil != 0:
            sides[j] += ' '*(len(word)%pencil)
    else:
        for k in range(math.ceil(len(word)+(len(word)%pencil))):
              sides[j]+=random.choice(alpha)

for l in range(0, math.ceil(len(word)/pencil)*pencil, pencil):
    for m in sides:
        cipher += m[l:l+pencil]

print('Cipher:\t'+cipher)
print('Side:\t'+str(side))

Python - 219 178 172 175

First crack at it.  I'm sure there's room for improvement.

edit1: After suggestions, and copying words file to local file named 'w'
edit2: Fixed a bug where it wasn't using the right number of letters per side.  Added 3 chars :(

r=range
s=raw_input()
print[a for a in(''.join(s[m:m+n]for m in r(o*n,len(s),4*n))for o in r(4)for n in(1,2,4,6,8))if not set(a.lower().split())-set(map(str.strip,open('w')))]


Are circular tapes exciting? A Brainfuck derivative

Let's define a simple Brainfuck-like programming language.
It has a two-directional tape of cells, and each cell holds one bit.
All bits are initially 0.
There is a moving head on the tape, initially at position 0.
A program is a string over the characters <>01!, executed from left to right, with the following semantics:

< moves the head one step to the left.
> moves the head one step to the right.
0 puts 0 in the current cell.
1 puts 1 in the current cell.
! flips the current cell.

There are no loops, so a program of n characters terminates after exactly n steps.
A program is boring if all cells contain 0 at the end of execution, and exciting if there is at least one 1.
Note that the size of the tape is not specified, so depending on the implementation, it may be two-way infinite or circular.

An example program

Consider the program 1>>>!<<<<0>!>>>!.
On an infinite tape, execution proceeds as follows:

     v
00000000000000  Put 1
     v
00000100000000  Move by >>>
        v
00000100000000  Flip
        v
00000100100000  Move by <<<<
    v
00000100100000  Put 0
    v
00000100100000  Move by >
     v
00000100100000  Flip
     v
00000000100000  Move by >>>
        v
00000000100000  Flip
        v
00000000000000

At the end, all cells are 0, so this program is boring.
Now, let's run the same program on a circular tape of length 4.

v
0000  Put 1
v
1000  Move by >>>
   v
1000  Flip
   v
1001  Move by <<<< (wrapping around at the edge)
   v
1001  Put 0
   v
1000  Move by > (wrapping back)
v
1000  Flip
v
0000  Move by >>>
   v
0000  Flip
   v
0001

This time, there is a cell with value 1, so the program is exciting!
We see that whether a program is boring or exciting depends on the size of the tape.

The task

Your input is a non-empty string over <>01! that represents a program in the above programming language.
An array of characters is also an acceptable input format.
The program is guaranteed to be boring when run on an infinite tape.
Your output shall be the list of tape lengths on which the program is exciting.
Note that you only need to test the program on tapes that are shorter than the program length.

The solution with the lowest byte count in each language is the winner.
Standard code-golf rules apply.

Test cases

> : []
110 : []
1>0<! : [1]
0>>1>0<<>! : [1]
1>>>!<<<<0>!>>>! : [2, 4]
!<!<><<0>!>!<><1!>>0 : [2]
>>!>><>001>0<1!<<!>< : [1, 2, 3]
1!><<!<<<!!100><>>>! : [1, 3]
!!1>!>11!1>>0<1!0<!<1><!0<!<0> : [3, 4]
<><<>>!<!!<<<!0!!!><<>0>>>>!>> : [1, 2, 4]
0>>><!<1><<<0>!>>!<<!!00>!<>!0 : [3]
0000!!!!><1<><>>0<1><<><<>>!<< : []
!>!>!>!>!>1>!>0<!<!<!<0<!<0<!<!<!<1>!>0<<! : [1, 2, 5, 7]
<!!>!!><<1<>>>!0>>>0!<!>1!<1!!><<>><0<<!>><<!<<!>< : [1, 2, 4, 5]
!>1<<11<1>!>!1!>>>0!!>!><!!00<><<<0<<>0<<!<<<>>!!> : [1, 2, 3, 5, 6]

Haskell, 119 bytes

t#'<'=last t:init t
(h:t)#c|c<'#'=1-h:t|c>'='=t++[h]|1<2=read[c]:t
f p=[n|n<-[1..length p],sum(foldl(#)(0<$[1..n])p)>0]

Try it online!

Function # is the interpreter for a single command c. The whole program p is run by folding # with the starting tape into p. f executes p for every tape and keeps those where the sum of the cells is at least 1.


Truncate consecutive character runs to n length The challenge

Given an input string, and an integer n - truncate any runs of consecutive characters to a maximum of n length. The characters can be anything, including special characters. The function should be case sensitive, and n can range from 0 to infinity.

Example inputs/outputs:

f("aaaaaaabbbccCCCcc", 2) //"aabbccCCcc"
f("aaabbbc", 1) //"abc"
f("abcdefg", 0) //""
f("aaaaaaabccccccccCCCCCC@", 4) //"aaaabccccCCCC@"

Scoring

The scoring is based on the number of bytes used.
Thus

function f(s,n){return s.replace(new RegExp("(.)\\1{"+n+",}","g"),function(x){return x.substr(0, n);});}

would be 104 points.

Happy golfing!

Edit: removed language restriction, but I still would love to see javascript answers

C, 81 78

Modifies the incoming string.

c,a;f(p,n)char*p;{char*s=p;for(;*p;s+=c<n)*s=*p++,a^*s?c=0:++c,a=*s;c=a=*s=0;}

Test Program

Requires two parameters, the first is the string to truncate, the second is the length limit.

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

int main(int argc, const char **argv)
{
    char *input=malloc(strlen(argv[1])+1);
    strcpy(input,argv[1]);
    f(input,atoi(argv[2]));
    printf("%s\n",input);
    free(input);
    return 0;
}

Explanation:

c,a;                 //declare two global integers, initialized to zero.
                     //c is the run length, a is the previous character
f(char*p,int n){...} //define function f to truncate input
char*s=p;            //copy p to s; p is source, s is destination
for(;*p              //while there is a source character
;s+=c<n)             //increment copied pointer if run is under the limit
*s=*p++,             //copy from source to destination, increment source
a^*s?c=0:++c,        //if previous character != current then run=0 else increment run
a=*s;                //previous character = current source character
c=a=*s=0;            //after loop, terminate destination string with NUL and reset c and a.

This works because the source pointer will always be equal to or greater than the destination pointer, so we can write over the string as we parse it.


Solve Einstein's riddle Einstein wrote a riddle. He said that 98% of the world could not solve it.
I solved this riddle in about 25 minutes while on the train to work.
It's basically just deduction.
The riddle

There are 5 houses in 5 different colors in a row.
In each house lives a person with a different nationality.
The 5 owners drink a certain type of beverage, smoke a certain brand of cigar, and keep a certain pet.
No owners have the same pet, smoke the same brand of cigar, or drink the same beverage.
Question: Who owns the fish?

To solve this riddle Einstein provides 15 hints:

The Brit lives in the red house.
The Swede keeps dogs as pets.
The Dane drinks tea.
The green house is on the immediate left of the white house.
The green house's owner drinks coffee.
The owner who smokes Pall Mall rears birds.
The owner of the yellow house smokes Dunhill.
The owner living in the center house drinks milk.
The Norwegian lives in the first house.
The owner who smokes Blends lives next to the one who keeps cats.
The owner who keeps the horse lives next to the one who smokes Dunhill.
The owner who smokes Bluemasters drinks beer.
The German smokes Prince.
The Norwegian lives next to the blue house.
The owner who smokes Blends lives next to the one who drinks water.

With these hints you can come to a solution.
Your task:
Make a program that will solve this riddle for you.
Hard coding the solution isn't allowed (duh)
It is allowed to hardcode the hints in any format.
Example format:
//Hints in order
(Nationality:Brit)==(Color:Red)
(Nationality:Swede)==(Pet:Dogs)
(Nationality:Dane)==(Drink: Tea)
(Color:Green)/(Color:White)
(Color:Green)==(Drink:Coffee)
(Smoke:PallMall)==(Pet:Birds)
(Color:Yellow)==(Smoke:Dunhill)
(House:3)==(Drink:Milk)
(Nationality:Norwegian)==(House:1)
(Smoke:Blend)/\(Pet:Cats)

== means equals to
/ means on left side of
\ means on right side of
/\ means left or right of

Like I said its allowed to either hardcode hints or have them as input.
Output:
Output should be in the following format (With the correct values, just saying for the trolls ;) )
 _____________    _____________    _____________    _____________    _____________
|   Number    |  |   Number    |  |   Number    |  |   Number    |  |   Number    |
| Nationality |  | Nationality |  | Nationality |  | Nationality |  | Nationality |
|    Color    |  |    Color    |  |    Color    |  |    Color    |  |    Color    |
|    Drink    |  |    Drink    |  |    Drink    |  |    Drink    |  |    Drink    |
|    Smoke    |  |    Smoke    |  |    Smoke    |  |    Smoke    |  |    Smoke    |
|     Pet     |  |     Pet     |  |     Pet     |  |     Pet     |  |     Pet     |
---------------  ---------------  ---------------  ---------------  ---------------

The <Nationality> in the <Color> house owns the fish!

Ascii art boxes can be changed by you, as long as they are boxes, doesn't matter what symbols you use.
Any knowledge on this riddle and solution can not be used in the program.
It should use pure logic and deduction to solve the riddle.
Tagged this as a codegolf but might be a code challenge, not sure.
Any thoughts on winning criteria for a code challenge feel free to share :)
For now this is code-golf so the program with the lowest bytecount wins.
Good luck and Happy coding :)


Find the first n digits of the square root of a number Given two integers m and n, return the first m digits of sqrt(n), with the decimal point. They will be given with a space in between.

You only have to produce m digits: so if m=5, n=500, then the output will be 22.360, not 22.36067.

Do not use anything that will increase the precision of any operation.

Test Cases:
20 99 -> 9.9498743710661995473
15 12345678 -> 3513.64170057221
16 256 -> 16.00000000000000
2 10000 -> 10

Shortest code wins.

Python, 143 chars

m,n=map(int,raw_input().split())
d=10**m
n*=d*d
a=0
b=n
while a<b-1:c=(a+b)/2;a,b=[[c,b],[a,c]][c*c>n]
print('%d.%0*d'%(a/d,m,a%d))[:m+(a/d<d)]

Computes the answer by multiplying n by 10^2m, doing an integer square root (using binary search), then "dividing" the result by 10^m.


Output the nth Even Perfect Number Challenge

Given an integer, n, as input where 0 <= n <= 2^10, output the nth even perfect number.

Perfect Numbers

A perfect number is a number, x where the sum of its factors (excluding itself) equals x. For example, 6:

6: 1, 2, 3, 6

And, of course, 1 + 2 + 3 = 6, so 6 is perfect.

If a perfect number, x, is even, x mod 2 = 0.

Examples

The following are the first 10 even perfect numbers:

6
28
496
8128
33550336
8589869056
137438691328
2305843008139952128
2658455991569831744654692615953842176
191561942608236107294793378084303638130997321548169216

Note that you may index this however you wish: 6 may be the 1st or the 0th even perfect number.

Winning

Shortest code in bytes wins.

Jelly, 7 bytes

6Æṣ=$#Ṫ

Try it online!

How it works

6Æṣ=$#Ṫ  Main link. Argument: n

6        Set the return value to 6.
     #   Execute the link to the left with argument k = 6, 7, 8, ... until n
         values of k result in a truthy value. Yield the array of matches.
    $        Combine the two links to the left into a monadic chain.
 Æṣ              Compute the sum of k's proper divisors.
   =             Compare the result with k.
      Ṫ  Tail; extract the last match.


Haskell, 576 554 532 507 bytes

No built-ins!

import Data.Complex
s=sum
l=length
m=magnitude
i=fromIntegral
(&)=zip
t=zipWith
(x!a)b=x*a+b
a#b=[[s$t(*)x y|y<-foldr(t(:))([]<$b)b]|x<-a]
f a|let c=[1..l a];g(u,d)k|m<-[t(+)a b|(a,b)<-a#u&[[s[d|x==y]|y<-c]|x<-c]]=(m,-s[s[b|(n,b)<-c&a,n==m]|(a,m)<-a#m&c]/i k)=snd<$>scanl g(0<$c<$c,1)c
p?x|let f=foldl1(x!);c=l p-1;n=i c;q p=init$t(*)p$i<$>[c,c-1..];o=f(q p)/f p;a|d<-sqrt$(n-1)*(n*(o^2-f(q$q p)/f p)-o^2)=n/last(o-d:[o+d|m(o-d)<m(o+d)])=last$p?(x-a):[x|m a<1e-9]
z[a,b]=[-b/a]
z p=p?0:z(init$scanl1(p?0!)p)

Try it online!

Many thanks @ØrjanJohansen for a total of -47 bytes!

Explanation

First this computes the characteristic polynomial with the Faddeev–LeVerrier algorithm which is the function f. Then the function z computes all roots of that polynomial by iterating g which implements Laguerre's Method for finding a root, once a root is found it is removed and g gets called again until the polynomial has degree 1 which is trivially solved by z[a,b]=[-b/a].

Ungolfed

I re-inlined the functions sum,length,magnitude, fromIntegral, zipWith and (&) as well as the little helper (!). The function faddeevLeVerrier corresponds to f, roots to z and g to laguerre respectively.

-- Transpose a matrix/list
transpose a = foldr (zipWith(:)) (replicate (length a) []) a

-- Straight forward implementation for matrix-matrix multiplication
(#) :: [[Complex Double]] -> [[Complex Double]] -> [[Complex Double]]
a # b = [[sum $ zipWith (*) x y | y <- transpose b]|x<-a]

-- Faddeev-LeVerrier algorithm
faddeevLeVerrier :: [[Complex Double]] -> [Complex Double]
faddeevLeVerrier a = snd <$> scanl go (zero,1) [1..n]
  where n = length a
        zero = replicate n (replicate n 0)
        trace m = sum [sum [b|(n,b)<-zip [1..n] a,n==m]|(m,a)<-zip [1..n] m]
        diag d = [[sum[d|x==y]|y<-[1..n]]|x<-[1..n]]
        add as bs = [[x+y | (x,y) <- zip a b] | (b,a) <- zip as bs]
        go (u,d) k = (m, -trace (a#m) / fromIntegral k)
          where m = add (diag d) (a#u)

-- Compute roots by succesively removing newly computed roots
roots :: [Complex Double] -> [Complex Double]
roots [a,b] = [-b/a]
roots   p   = root : roots (removeRoot p)
  where root = laguerre p 0
        removeRoot = init . scanl1 (\a b -> root*a + b)

-- Compute a root of a polynomial p with an initial guess x
laguerre :: [Complex Double] -> Complex Double -> Complex Double
laguerre p x = if magnitude a < 1e-9 then x else laguerre p new_x
  where evaluate = foldl1 (\a b -> x*a+b)
        order' = length p - 1
        order  = fromIntegral $ length p - 1
        derivative p = init $ zipWith (*) p $ map fromIntegral [order',order'-1..]
        g  = evaluate (derivative p) / evaluate p
        h  = (g ** 2 - evaluate (derivative (derivative p)) / evaluate p)
        d  = sqrt $ (order-1) * (order*h - g**2)
        ga = g - d
        gb = g + d
        s = if magnitude ga < magnitude gb then gb else ga
        a = order /s
        new_x = x - a


The Jumping Up Sequence Consider the following sequence:

0 1 3 2 5 4 8 6 7 12 9 10 11 17 13 14 15 16 23 ...

Looks pretty pattern-less, right? Here's how it works. Starting with 0, jump up n integers, with n starting at 1. That's the next number in the sequence. Then, append any numbers "skipped" and that haven't been seen yet in ascending order. Then, increment n and jump from the last number appended. Repeat this pattern.

So, for example, when we reach 11, we're at n=5. We increment n to be n=6, jump up to 17, then append 13 14 15 16 since those haven't been seen yet. Our next jump is n=7, so the next element in the sequence is 23.

The Challenge

Given input x, output the xth term of this sequence, the first x terms of the sequence, or build an infinite list of the terms of the sequence. You can choose 0- or 1-indexing.

I/O and Rules

The input and output can be given by any convenient method.
The input and output can be assumed to fit in your language's native number type.
Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
Standard loopholes are forbidden.
This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.

JavaScript (ES7), 41 bytes

Returns the n-th term of the sequence, 0-indexed.

n=>(d=(n--*8-23)**.5)%1?n:'121'[n]^n-~d/2

Try it online!

How?

Main case: \$n > 3\$

The first four terms of the sequence are special, so let's put them aside for now.

For \$n > 3\$, the sequence looks like that:

 n  | [4] 5 [6] 7 8 [ 9] 10 11 12 [13] 14 15 16 17 [18] 19 20 21 22 23 [24] 25 26 27 ...
----+------------------------------------------------------------------------------------
a(n)| [5] 4 [8] 6 7 [12]  9 10 11 [17] 13 14 15 16 [23] 18 19 20 21 22 [30] 24 25 26 ...
----+------------------------------------------------------------------------------------
 k  |  2  -  3  - -   4   -  -  -   5   -  -  -  -   6   -  -  -  -  -   7   -  -  - ...

We can notice that there are in fact two interleaved sub-sequences:

Most values belong to the sub-sequence \$A\$ for which we simply have:

$$A(n) = n - 1$$
Some other values belong to the sub-sequence \$B\$ (highlighted with brackets in the above diagram) whose indices follow the arithmetic sequence 3, 3, 4, 6, 9, 13, 18, 24 ... and for which we have:

$$B(n,k) = n + k - 1$$

where \$n\$ is the index in the main sequence and \$k\$ is the index in the sub-sequence \$B\$.

The indices of \$B\$ in the main sequence are given by:

$$n_k = \frac{k^2 - k + 6}{2}$$

Given \$n\$, we know that the corresponding term in the main sequence belongs to \$B\$ if \$n\$ is an integer solution of the quadratic equation:

$$x^2 - x + 6 - 2n = 0$$

whose discriminant is:

$$\Delta = 1 - 4(6 - 2n) = 8n - 23$$

and whose positive solution is:

$$x = \frac{1 + \sqrt{\Delta}}{2}$$

We expect \$\sqrt{\Delta}\$ to be an integer. Hence the test:

(d = (n-- * 8 - 23) ** .5) % 1

Special cases: \$0 \le n \le 3\$

For \$n < 3\$, the discriminant is negative and taking its square root results in NaN. For \$n = 3\$, the discriminant is \$1\$. Therefore, these first four terms of the sequence are considered to belong to the sub-sequence \$B\$.

Should we just apply our standard formula n - ~d / 2, we'd get:

$$-\frac 1 2, \frac 1 2, \frac 3 2, 3$$

instead of:

$$0, 1, 3, 2$$

Which is why we XOR these results with \$0,1,2\text{ and }1\$ respectively.


How to determine if a number is odd or even without mod -or- bitwise operations? How to determine if a number is odd or even without mod -or- bitwise operations?

This challenge is grossly inefficient, but challenges your ability to think outside the box for a creative solution.

EDIT:

Please create a function. Also, while regex is a fun response, the function should accept any valid number.

BACKGROUND:
This question stems from my earliest programming days.  The homework for our first day of class was to write a simple program that printed 'odd' or 'even'.  Being the brat I was, I didn't read the book we had for the class where it simply showed us how to use % to determine that.  I spent about a half hour pacing back in forth in my room trying to think of a way to do this and had remembered from the lecture that numbers can lose and gain precision as they are cast from one primitive type to another.  Therefore, if you took the number, divided it by two and then multiplied it back didn't equal the original number, then you would know that the number was odd.

I was stunned the next day, while our instructor was evaluating our programs, that he thought that it was the most original, if inefficient, way of solving the problem.

Python

print('even' if (-1)**n==1 else 'odd')


Determine if a polygon is convex Write a program to determine if the input polygon is convex.  The polygon is specified with one line containing N, the number of vertices, then N lines containing the x and y coordinates of each vertex.  The vertices will be listed clockwise starting from an arbitrary vertex.

example 1

input

4
0 0
0 1
1 1
1 0

output

convex

example 2

input

4
0 0
2 1
1 0
2 -1

output

concave

example 3

input

8
0 0
0 1
0 2
1 2
2 2
2 1
2 0
1 0

output

convex

x and y are integers, N<1000, and |x|,|y|<1000.  You may assume that the input polygon is simple (none of the edges cross, only 2 edges touch each vertex).  Shortest program wins.

J, 105

echo>('concave';'convex'){~1=#=(o.1)([:>-.~)(o.2)|3([:-/12 o.-@-/@}.,-/@}:)\(,2&{.)j./"1}.0&".;._2(1!:1)3

Passes all three tests above.

Edit: (111->115) Handle co-linear points by eliminating angles of pi. Gained a few characters elsewhere.

Edit: (115->105) Less dumb.

Explanation for the J-impaired:

(1!:1)3 read STDIN to EOF. (I think.)
0&".;._2 is a nice idiom for parsing this kind of input.
j./"1}. lop off first line of input (N 0) and convert pairs to complexes.
(,2&{.) tack first two points onto the end of the list.
3(f)\ applies f to  sliding window of length 3 (3 points for  an angle)
[:-/12 o.-@-/@}.,-/@}: is a verb that transforms each 3 points into an angle between -pi and pi.

-@-/@}.,-/@}: produces (p1 - p2),(p3 - p2). (Recall that these are complexes.)
12 o. gives an angle for each complex.
[:-/(...) gives the difference of the two angles.

(o.1)([:>-.~)(o.2)| mod 2 pi, eliminate angles of pi (straight segments), and compare to pi (greater than, less than, doesn't matter unless the points are supposed to be wound in one direction).
1=#= if all those comparison result 1 or 0 (With self-classify. This seems dumb.)
echo>('concave';'convex'){~ print convex.


Secret Santa - Revisited Christmas is fast approaching and along with it, arranging the annual family Secret Santa. I'd like to try and get a head start on this, but making sure couples don't buy for each other keeps causing problems and despite doing this for years there's still the problem that Bob is pretty rubbish at buying gifts for most of the giftees, Erin will likely be disappointed, but he knows that Frank likes Talisker, so he's a good match for him. This makes none of the existing simple solutions acceptable for my needs.

To make my life easier, your task is to write a function (or closest alternative in your language) that when given an array of arrays (or closest alternative in your chosen language), returns (or outputs) a pairing of 'gifters' to 'giftees' in the shortest possible code in bytes, such that the following conditions are met:

Each name is paired with another, randomly selected, name from the input data (Note that it may not always be possible to randomise the output based on the provided conditions)
Names will be provided with a list of flags that represent an adjacency matrix with the ordering consistent, so that column n refers to the same person as row n.
If the conditions cannot be met, return something falsy in your language.
If there are multiple solutions, your program must be able to generate them all if run many times.

You can assume you will never be presented with duplicate names as we need to be able to tell which family member is which, but you may be presented with data that includes spaces to differentiate Bob Senior from Bob Junior! It should complete all the supplied test cases within an hour  for pretty large families, such as 100 unique names in the source data (please see the example data sets below, you must be able to parse all of these within the allocated time).

Example input:

santa([
    ["Alice", 0, 0, 1, 1, 1, 1, 1],
    ["Bob",   0, 0, 0, 0, 0, 1, 0],
    ["Carla", 1, 1, 0, 0, 0, 1, 1],
    ["Dan",   1, 1, 0, 0, 0, 1, 1],
    ["Erin",  1, 1, 0, 0, 0, 1, 1],
    ["Frank", 1, 1, 1, 1, 1, 0, 1],
    ["Gary",  1, 1, 1, 1, 1, 1, 0]
]);
// might return something like:
[
    ["Alice", "Erin"],
    ["Bob", "Frank"],
    ["Carla", "Alice"],
    ["Dan", "Gary"],
    ["Erin", "Bob"],
    ["Frank", "Dan"],
    ["Gary", "Carla"]
]

santa([
    ["Alice", 0, 1, 1, 1, 0, 1],
    ["Bob",   0, 0, 1, 1, 0, 1],
    ["Carla", 0, 1, 0, 1, 0, 1],
    ["Dan",   0, 1, 1, 0, 0, 0],
    ["Erin",  0, 0, 1, 0, 0, 1],
    ["Frank", 1, 1, 1, 1, 1, 0]
]);
false

santa([
    ["Alice", 0, 1, 1],
    ["Bob",   1, 0, 1],
    ["Carla", 1, 1, 0]
]);
[
    ["Alice", "Bob"],
    ["Bob", "Carla"],
    ["Carla", "Alice"]
]

Depending on language, input can be in other formats, for instance details on STDIN could be provided as:

script <<< 'Alice,0,0,1,1,1,1,1
Bob,0,0,0,0,0,1,0
Carla,1,1,0,0,0,1,1
Dan,1,1,0,0,0,1,1
Erin,1,1,0,0,0,1,1
Frank,1,1,1,1,1,0,1
Gary,1,1,1,1,1,1,0'

Output can also be provided in any sensible format, whichever is easiest for your language. Acceptable formats include an array of arrays (as above) or perhaps a hash/Object/associative array or even just printing the parings to STDOUT:

Alice:Dan
Bob:Erin
Carla:Bob
Dan:Alice
Erin:Frank
Frank:Carla

If in doubt, please ask and provide examples of required input format and expected output format with your answer.

Reference JavaScript implementation.

Larger data sets: 100, 100, 200, 200 - many solutions, 200 - only one solution.

Reference implementation completes all these in <4s on my machine.

Above sets generated with this script.


All non-empty finite sets of positive integers The challenge is to create an iterator(/generator) which iterates (in any order so as to reach all of them... ie no set should occur at infinity) over all possible non-empty finite sets(/tuples/lists) of positive integers (hence demonstrating their countability).

Since the problem of verifying the correctness of a solution is undecidable in some cases, an accompanying explanation of how your program works and what order the sets are returned in would be helpful

Each finite set should occur exactly once.  So if left running long enough, the iterator should eventually hit each of {1}, {3,5}, {17,29,306} etc. exactly once

GolfScript, 21 characters
;]]0{)\{.2$+.p}%\1}do

A GolfScript version which prints all generated sets. It basically does the same as my Python version although not by recursion but instead collecting all possible sets in an array.
;        // clear the stack
]]       // put [[]] on the stack - the array of generated sets
            (initially an array with only the empty set)
0        // counter starts with zero
{        // start of infinite loop
  )      // increase counter
  \{     // map for each item of the array
    .    // duplicate item (i.e. this is a set)
    2$+  // append counter
    .p   // print the newly generated set
  }%\    // end of map => now the array contains all sets with max. up to counter
1} do    // end of infinite loop


Implement Rijndael's S-box Rijndael's S-box is a frequently used operation in AES encryption and decryption.  It is typically implemented as a 256-byte lookup table.  That's fast, but means you need to enumerate a 256-byte lookup table in your code.  I bet someone in this crowd could do it with less code, given the underlying mathematical structure.

Write a function in your favorite language that implements Rijndael's S-box.  Shortest code wins.

x86-64 Machine code - 23 22 20 19 bytes

Uses the AES-NI instruction set

66 0F 6E C1          movd        xmm0,ecx
66 0F 38 DD C1       aesenclast  xmm0,xmm1
0F 57 C1             xorps       xmm0,xmm1
66 0F 3A 14 C0 00    pextrb      eax,xmm0,0
C3                   ret

Using Windows calling conventions, takes in a byte and outputs a byte. It is not necessary to reverse the ShiftRows as it does not affect the first byte.


Am I not good enough for you? Background:
The current Perfect Numbers challenge is rather flawed and complicated, since it asks you to output in a complex format involving the factors of the number. This is a purely decision-problem repost of the challenge.
Challenge
Given a positive integer through any standard input format, distinguish between whether it is perfect or not.
A perfect number is a number that is equal to the sum of all its proper divisors (its positive divisors less than itself). For example, \$6\$ is a perfect number, since its divisors are \$1,2,3\$, which sum up to \$6\$, while \$12\$ is not a perfect number since its divisors ( \$1,2,3,4,6\$ ) sum up to \$16\$, not \$12\$.
Test Cases:
Imperfect:
1,12,13,18,20,1000,33550335

Perfect:
6,28,496,8128,33550336,8589869056

Rules

Your program doesn't have to complete the larger test cases, if there's memory or time constraints, but it should be theoretically able to if it were given more memory/time.
Output can be two distinct and consistent values through any allowed output format. If it isn't immediately obvious what represents Perfect/Imperfect, please make sure to specify in your answer.

Brachylog, 4 bytes

fk+?

Try it online!

The predicate succeeds for perfect inputs and fails for imperfect inputs, printing true. or false. if run as a complete program (except on the last test case which takes more than a minute on TIO).

        The input's
f       factors
 k      without the last element
  +     sum to
   ?    the input.


Tips for golfing in vim I've recently realized how vim works great for golfing, especially for kolmogorov-complexity. Also, according to meta vim is a perfectly acceptable 'programming language' at least, for the scope of this site, that is.

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

Please post one tip per answer.

Be aware of the uppercase variants of common commands. This can trivially save one keystroke in a lot of contexts. For example:

A = $a
C = c$
D = d$
I = ^i
S = cc
X = dh
Y = yy

Another one is to use G instead of gg, but only if you use a count! For example, without a count, gg moves to the beginning, and G moves to the end. However, with a count, they both move to the line you specify, so 5G is shorter than but equivalent to 5gg
    .

Another one, is to use H in place of gg, but it's important to note that this only works if you can guarantee that any input will not take up more than the default number of rows (I believe this is 24, but it may vary).


Prime generating function Background
The Python code
((((((((n%35)^11)*195)|53)&181)+n)%168)*n)+83

produces 74 distinct primes for \$0 \le n \le 73\$. This code also works in Java. The operators are as follows:

+ is addition
* is multiplication
% is modulus
& is bitwise AND
| is bitwise OR
^ is bitwise XOR

The produced primes are: 83, 97, 113, 251, 311, 173, 197, 503, 571, 281, 313, 787, 863, 421, 461, 1103, 547, 593, 1361, 1451, 743, 797, 1733, 1831, 1931, 1033, 1097, 2243, 1231, 1301, 1373, 2687, 1523, 1601, 3041, 3163, 1847, 1933, 3541, 3671, 2203, 2297, 4073, 4211, 2591, 2693, 4637, 4783, 3011, 3121, 5233, 3347, 3463, 5701, 5861, 3823, 3947, 6353, 6521, 6691, 4463, 4597, 7213, 4871, 5011, 5153, 7937, 5443, 5591, 8501, 8693, 6047, 6203, 9281.
Task
Given an input integer \$n\$ output one of the primes from the above list, such that every output is distinct.
Rules

\$n\$ will be between 0 and 73, inclusive.
You can receive input through any of the standard IO methods.
Leading zeroes are not allowed in output.
This is code-golf, so shortest code in bytes wins!

x86 Machine Code, 23 bytes
86 89 C8 D4 23 34 0B 6B C0 C3 0C 35 24 B5 00 C8 D4 A8 F6 E1 83 C0 53 C3

Try it online!
The above bytes of code define a function that returns the \$n\$th prime, according to the formula given in the challenge. The function accepts a single argument, \$n\$, which is passed in the ECX register. It returns the result in the AX register. (Note: A 16-bit value is returned—the caller is responsible for zero-extending that 16-bit value in AX to a 32-bit value in EAX, if desired. Add one byte for a CWDE instruction if you think that is cheating!)
This is a custom calling convention, but it isn't particularly "weird", and machine/assembly language submissions are allowed to define a custom calling convention.
Credit where credit is due: this code is based on EasyasPi's x86 submission, but carefully optimized for size. In particular, I've chosen to target 32-bit x86 so that I can use the long-obsolete AAM instruction, which is not supported in x86-64 "long" mode. AAM was designed into the architecture as a way to convert from binary to binary-coded decimal (BCD). To do this, it divides the AL register by 10, storing the quotient in AH and the remainder in AL. (Note that this is the reverse of what the DIV instruction produces!) Intel's original manuals documented AAM as a one-byte instruction, but it was actually encoded with two bytes, where the second byte was 10—the divisor for AL. Changing that second byte to another value allows dividing AL by an arbitrary value, essentially giving x86 an instruction to divide by an 8-bit intermediate. This trick is used twice, to great effect. (There is also a complementary AAD instruction, which allows multiplying by an arbitrary 8-bit immediate value, but that did not result in any savings, since it actually performs the multiplication on AH, instead of AL, and the shift that is required to support that requires 2 bytes, plus the 2 bytes for AAD, which is more than the 3 bytes required to encode the IMUL reg, reg, imm.) There are myriad other size optimizations as well, compared to EasyasPi's code.
Here are the ungolfed assembly mnemonics:
            ; Input(s):
            ;   ecx = The zero-based index of the prime to generate (i.e., "n").
            ;         (Note: This is assumed to be a value from 0 to 73.)
            ; Output(s):
            ;   ax  = The nth prime.
            ;         (Note: This is a 16-bit unsigned integer;
            ;                caller must zero-extend if desired.)
            ; Clobbers:
            ;   eax, flags
            GenerateNthPrime:
89 C8         mov   eax, ecx       # make a copy of the input (ecx) in eax
D4 23         aam   35             # al %= 35        ; ah = al / 35
34 0B         xor   al, 11         # al ^= 11
6B C0 C3      imul  eax, eax, -61  # ax  = (al * 195)
0C 35         or    al, 53         # al |= 53
24 B5         and   al, 181        # al &= 181
00 C8         add   al, cl         # al += cl
D4 A8         aam   168            # al %= 168       ; ah = al / 168
F6 E1         mul   cl             # ax  = (al * cl)
83 C0 53      add   eax, 83        # ax += 83
98          # cwde                 # eax = ax (sign-extend, assuming sign bit is 0)
C3            ret

Note the cwde instruction immediately before the return instruction there, which is commented out. For the purposes of this submission, this instruction is functionally equivalent to movzx eax, ax, which is what the caller of this function would normally use to zero-extend its 16-bit result (ax) to a 32-bit result (eax). However, cwde is encoded in only 1 byte, as opposed to the 3 bytes required by movzx. As I mentioned above, if you don't think it's legit that I return a 16-bit result, then add the cwde instruction to increase the total size of the function by only one byte.


The reversible reverser Your task is simple. The program reads in a line of text from the standard input, and it prints out the same text in a character-reversed form. It is not allowed to print anything else.

For example:

input: "Hello!",
output: "!olleH"

The catch is, your program has to be able to do the exact same thing if the source code itself is character-reversed!

Scoring: standard code-golf scoring applies, with the following modification to limit the boring

//margorp
program//

style answers: any solution which is a palindrome will incur a +25% penalty to the score, rounded up. This penalty still applies, if you, for example, insert characters into the program which do not have any useful effects, just to break the palindrome.

APL, 5

⌽⍞⍝⍞⊖

This reverses (⌽, along the last axis) the input (⍞), and is followed by a comment (⍝ marks a line comment). Reversed, the program reverses (⊖, along the first axis) the input, and is followed by a comment. Because the input is always going to be one dimensional, in this case ⌽ and ⊖ are functionally equivalent. It is perhaps even sneakier than the GolfScript solution, so here's a cleaner solution (no comments), which scores 9.

⍬,⌽,⍞,⊖,⍬

This first grabs an empty vector (⍬), flattens it (monadic ,), and reverses it (⊖, along the first axis). This still leaves an empty vector. Then it concatenates (dyadic ,) to the input (⍞), leaving the input untouched. It then flattens (monadic ,) the already-flat input and reverses it (⌽, along the last axis). Then it concatenates (dyadic ,) another empty vector (⍬) to the reversed input. This does nothing, and leaves the reversed input behind. Reversed, this program does the same thing, based again on the fact that ⌽ and ⊖ are functionally equivalent with one-dimesional arguments.

You really couldn't say I'm adding useless characters to break the palindrome (the two different reverse functions are different with two-or-more-dimensional input; I'm just taking advantage of the fact they act the same with one-dimensional input)


Are you ready to meet the Elite-Four? To be able to challenge the Elite-4 of top programmers, you need to show your badges first, that qualify you as a potential programmer-master. However, there's a twist. Once you show a badge, it is collected, which means you can't re-show it. So better come prepared! There are n badge collectors, each has a known list of accepted_badges. Given a list of your badges, your task is to find out, if you can access elite-four or if you require more badges. You can indicate this by printing a truthy-value for the first case or a falsey-value in the second case.

Example

accepted_badges: [ [a, b, c], [a, b, d], [d, e, f]]

If you have the badges [a, b, d]  you can pass. Simply give your a badge to the first collector (accepted_badges[0]), your b badge to the second and your d badge to the last collector. So this is a truthy case.

If you have the badges [a, b, c] you are in bad luck. The last collector doesn't accept any of it.

If you have the badges [b, c, d] you can also pass. Here  you will need to give your c badge to the first collector, the b badge to the second and the final collector will get the d badge.

If you have the badges [a, e, f] you will not be admitted, because you would have to use your a badge twice (since the first collector takes it away from you), which is not possible.

Input:

  A list* of your badges
  A 2Dlist* of badge collectors and their accepted badges

*list can be the following:

1. a list, i.e. [a, b, c, ...] or [[a,b,c],[c,d,e]]
2. a list with first element = number of elements i.e. [3, a, b, c] or [ [2], [3, a, b, c], [1, a]]
2. a string     "abcd..."
3. a string with leading number of elements i.e. "3abc"
4. a seperated string i.e. "abc,def,ghi"
5. a separated string with leading numbers of elements i.e. "3abc,2ab,5abcdef"
6. or any other convenient input format you can think of

Assumptions:

You may assume:

any list to never be empty
input letters to always match [a-z]
your number of badges matches the number of badge collectors

You may not assume:

that any list is sorted

Test cases (list format):

['a','b','c','d']
[['a','b','c'],['d','e','f'],['b','c','d'], ['c', 'g']]
Truthy

['a', 'a', 'a']
[['a', 'b', 'c'], ['a', 'd', 'e'], ['a', 'b', 'e', 'f']]
Truthy

['a', 'a', 'f']
[['a', 'c', 'f'], ['a', 'd'], ['b', 'c']]
Falsey

['x', 'y', 'z', 'w']
[['x', 'y'], ['x', 'y'], ['z', 'w'], ['x', 'y']]
Falsey

['p', 'q', 'r', 's', 't']
[['p', 'q', 'r'], ['r', 'q', 'p'], ['r'], ['s', 't'], ['p', 'q', 'r', 's', 't']]
Truthy

['p', 'q', 'r', 's', 't']
[['p', 'q', 'r', 's', 't'], ['p', 'q', 'r', 's'], ['p', 'q', 'r'], ['p', 'q'], ['p']]
Truthy

Test cases (String format):

"abcd"
"abc def bcd cg"
Truthy

"aaa"
"abc ade abef"
Truthy

"aaf"
"acf ad bc"
Falsey

"xyzw"
"xy xy zw xy"
Falsey

"pqrst"
"pqr rqp r st pqrst"
Truthy

"pqrst"
"pqrst pqrs pqr pq p"
Truthy

Lastly, this is codegolf so the answer with the least number of bytes wins. Please refrain from using any standard-loopholes.

Python 2, 68 bytes

One of the few cases where itertools is useful.

lambda b,a:s(b)in map(s,product(*a))
s=sorted
from itertools import*

Try it online!


Find out how Abstractly Capacious™ someone is! At the Code-Golf™ Psychological Society, you are delighted to present a new method of measuring mental age: Abstract Capacity™.

To get the Abstract Capacity of a person, you take their actual age divided by 4, take their IQ divided by 9, then add the two values together. Then, round this sum down to find the Abstract Capacity.

Challenge

Write a program, given an actual age A and an IQ of I, produces the Abstract Capacity using those values. The program should also print how older (age) or how smarter (IQ) someone should be in order to raise their Abstract Capacity by 1.

An input will always look something like

  A I

and an output will always look something like

  AC A' I'

where AC, A' and I' respectively denote the Abstract Capacity, how older someone has to be to raise their Abstract Capacity, and how smarter someone has to be to raise their Abstract Capacity.

Examples

Input

13 43

Output

8 4 9

Input

92 5

Output

23 2 4

Input

40 17

Output

11 1 1

Rules

Your code must be able to find the Abstract Capacity for any given A and I when 1 < A,I < 400.

This is code-golf. Shortest answer in bytes wins!

Python 2, 61 bytes

def f(a,i):r=a*9+i*4;print r/36,(r+44-i*4)/9-a,(r+39-a*9)/4-i

Try it online!


Find the greatest line You will be given a 2-D array A of integers, and a length N. Your task is to find within the array the straight line (horizontal, vertical or diagonal) of N elements that yields the highest total sum, and return that sum.

Example

 N = 3, A =
 3    3    7    9    3
 2    2   10    4    1
 7    7    2    5    0
 2    1    4    1    3

This array has 34 valid lines, including

 Vertical
 [3]   3    7    9    3
 [2]   2   10    4    1
 [7]   7    2    5    0
  2    1    4    1    3       [3,2,7] = 12
 Horizontal
  3    3    7    9    3
  2    2   10    4    1
  7    7   [2]  [5]  [0]
  2    1    4    1    3       [2,5,0] = 7
 Diagonal
  3    3   [7]   9    3
  2    2   10   [4]   1
  7    7    2    5   [0]
  2    1    4    1    3       [7,4,0] = 11

The maximum line is

 3    3    7   [9]   3
 2    2  [10]   4    1
 7   [7]   2    5    0
 2    1    4    1    3        [7,10,9] = 26

Note: lines may not wrap around the edges of the array.

Inputs

A X by Y 2-D array A, with X,Y > 0. Each element of the array contains an integer value which may be positive, zero or negative. You may accept this array in an alternative format (e.g. list of 1-D arrays) if you wish.
A single, positive integer N, no greater than max(X,Y).

Output

A single value representing the maximal line sum that can be found in the array. Note that you do not need to provide the individual elements of that line or where it is located.

Test cases

N = 4, A =
-88    4  -26   14  -90
-48   17  -45  -70   85
 22  -52   87  -23   22
-20  -68  -51  -61   41
Output = 58

N = 4, A =
 9    4   14    7
 6   15    1   12
 3   10    8   13
16    5   11    2
Output = 34

N = 1, A =
 -2
Output = -2

N = 3, A =
1    2    3    4    5
Output = 12

N = 3, A =
-10   -5    4
 -3    0   -7
-11   -3   -2
Output = -5

Jelly, 15 bytes

,ZṚ¥;ŒD$+⁹\€€FṀ

Try it online!

How it works

,ZṚ¥;ŒD$+⁹\€€FṀ  Main link. Left argument: M (matrix). Right argument: n (integer)

 ZṚ¥             Zip/transpose and reverse M. This is equivalent to rotating M 90°
                 counterclockwise.
,                Pair M and the result to the right.
    ;ŒD$         Append the diagonals of both matrices to the pair.
        +⁹\€€    Take the sums of length n of each flat array.
             FṀ  Flatten and take the maximum.


How long does it take to type this? Introduction

I can type at a moderate pace, using the QWERTY keyboard layout. But if a word like yellowwooddoor has a ton of repeated letters, it takes a bit longer to type it. Even worse is when a word like "jump" has the same finger used for multiple different consecutive letters.

Here's how long it takes me to type letters on each finger (very unscientifically measured):

Columns are Finger name, keystrokes/second, seconds/keystroke, and the keys used by each finger

Typing same letter twice:
L Pinky 5.2 0.1923076923 1qaz
L Ring  5   0.2          2wsx
L Mid   5.3 0.1886792453 3edc
L Index 5.5 0.1818181818 4rfv5tgb
R Thumb 6.5 0.1538461538 [space]
R Index 6.9 0.1449275362 6yhn7ujm
R Mid   6.3 0.1587301587 8ik,
R Ring  6.2 0.1612903226 9ol.
R Pinky 6.1 0.1639344262 0p;'

Typing different letter on same finger:
L Pinky 4.6 0.2173913043
L Ring  4.6 0.2173913043
L Mid   4.5 0.2222222222
L Index 5.3 0.1886792453
R Index 5.4 0.1851851852
R Mid   5.1 0.1960784314
R Ring  5.2 0.1923076923
R Pinky 5.2 0.1923076923

Same data in CSV format.

It  takes

.75 * (first_finger_same_letter_time + second_finger_same_letter_time) / 2

time to switch between two fingers.

Challenge

Given a string as input, how long does it take to type it?

The "timer" starts the moment the first key is pressed and ends when the last key is pressed. You are just counting the time between keypresses.
This is code-golf. Shortest answer in bytes wins.
Submission can be either a complete program or function.
Input and output any way you want it, stdin/out, function params, file, doesn't matter.
Output should be accurate to at least 3 decimal places (+/- 0.001 for rounding error is fine). Leading 0. for numbers under 1 and trailing newline optional.
Input will be a string that contains (lowercase) a-z, 0-9, space, semicolon, comma, period, and apostrophe.
I always type spaces with my right thumb.
I use the normal touch typing fingers (you can also look at the above table for finger-key mappings).
Reference code used to generate test cases

Test cases

(empty string or any one-character string) - 0.000

aa - 0.192

fff - 0.364

fj - 0.123

the quick brown fox jumped over the lazy dog - 5.795

yellowwooddoor - 1.983

orangewooddoor - 1.841

jump on it, jump on it - 2.748

type on it, type on it - 2.549

abcdefghijklmnopqrstuvwxyz01234567890 ;,.' - 5.746

ok, this may not be the most accurate but it's in the ballpark, maybe within 30 percent or so. - 12.138

JavaScript (Node.js), 180 bytes

s=>(B=Buffer)(s).map(p=c=>(b='23841410645532207643205431765001333746443'[c*45%91%73%41]*2,t+=1/p?p-b?3/8*(g(b)+g(p)):g(b|c!=s):0,p=b,s=c),t=0,g=x=>10/B('4.2.5-75E6?3>4=4AA')[x])&&t

Try it online!
How?
Storing delays
The helper function \$g\$ takes an integer \$0\le x \le17\$ and returns a delay in seconds.
g = x => 10 / Buffer('4.2.5-75E6?3>4=4AA')[x]

The input \$x\$ is expected to be either:

twice the bin number to get the delay for the same letter
twice the bin number + 1 to get the delay for different letters

What is actually stored in the string '4.2.5-75E6?3>4=4AA' is the number of keystrokes per second multiplied by \$10\$ and converted to ASCII. Conveniently, all resulting characters are printable.
For instance, \$5.2\$ is stored as chr(52) which is '4'.
Converting a character to a key bin
We use the following hash function to convert an ASCII code \$c\$ to an index into a lookup table containing the bin numbers in \$[0..8]\$:
$$i = (((c\times 45) \bmod 91)\bmod 73)\bmod 41$$
Main loop
The total time \$t\$ is updated with:
t +=                        // add to t:
  1 / p ?                   //   if p is numeric:
    p - b ?                 //     if p is not equal to b:
      3 / 8 * (g(b) + g(p)) //       0.75 * (g(b) + g(p)) / 2
    :                       //     else:
      g(b | c != s)         //       g(b) if c == s or g(b + 1) otherwise
  :                         //   else (first iteration):
    0                       //     leave t unchanged

where \$p\$ is the previous bin and \$s\$ is the previous character.


Write a program whose nontermination is independent of Peano arithmetic Challenge

Write a program P, taking no input, such that the proposition “the execution of P eventually terminates” is independent of Peano arithmetic.

Formal rules

(In case you are a mathematical logician who thinks the above description is too informal.)

One can, in principle, convert some Universal Turing machine U (e.g. your favorite programming language) into a Peano arithmetic formula HALT over the variable p, where HALT(p) encodes the proposition “U terminates on the program (Gödel-encoded by) p”.  The challenge is to find p such that neither HALT(p) nor ¬HALT(p) can be proven in Peano arithmetic.

You may assume your program runs on an ideal machine with unlimited memory and integers/pointers big enough to access it.

Example

To see that such programs exist, one example is a program that exhaustively searches for a Peano arithmetic proof of 0 = 1.  Peano arithmetic proves that this program halts if and only if Peano arithmetic is inconsistent.  Since Peano arithmetic is consistent but cannot prove its own consistency, it cannot decide whether this program halts.

However, there are many other propositions independent of Peano arithmetic on which you could base your program.

Motivation

This challenge was inspired by a new paper by Yedidia and Aaronson (2016) exhibiting a 7,918-state Turing machine whose nontermination is independent of ZFC, a much stronger system than Peano arithmetic.  You may be interested in its citation [22].  For this challenge, of course, you may use your programming language of choice in place of actual Turing machines.

Haskell, 838 bytes

“If you want something done, …”

import Control.Monad.State
data T=V Int|T:$T|A(T->T)
g=guard
r=runStateT
s!a@(V i)=maybe a id$lookup i s
s!(a:$b)=(s!a):$(s!b)
s@((i,_):_)!A f=A(\a->((i+1,a):s)!f(V$i+1))
c l=do(m,k)<-(`divMod`sum(1<$l)).pred<$>get;g$m>=0;put m;l!!fromEnum k
i&a=V i:$a
i%t=(:$).(i&)<$>t<*>t
x i=c$[4%x i,5%x i,(6&)<$>x i]++map(pure.V)[7..i-1]
y i=c[A<$>z i,1%y i,(2&)<$>y i,3%x i]
z i=(\a e->[(i,e)]!a)<$>y(i+1)
(i?h)p=c[g$any(p#i)h,do q<-y i;i?h$q;i?h$1&q:$p,do f<-z i;a<-x i;g$p#i$f a;c[i?h$A f,do b<-x i;i?h$3&b:$a;i?h$f b],case p of A f->c[(i+1)?h$f$V i,do i?h$f$V 7;(i+1)?(f(V i):h)$f$6&V i];V 1:$q:$r->c[i?(q:h)$r,i?(2&r:h)$V 2:$q];_->mzero]
(V a#i)(V b)=a==b
((a:$b)#i)(c:$d)=(a#i)c&&(b#i)d
(A f#i)(A g)=f(V i)#(i+1)$g$V i
(_#_)_=0<0
main=print$(r(8?map fst(r(y 8)=<<[497,8269,56106533,12033,123263749,10049,661072709])$3&V 7:$(6&V 7))=<<[0..])!!0

Explanation

This program directly searches for a Peano arithmetic proof of 0 = 1.  Since PA is consistent, this program never terminates; but since PA cannot prove its own consistency, the nontermination of this program is independent of PA.

T is the type of expressions and propositions:

A P represents the proposition ∀x [P(x)].
(V 1 :$ P) :$ Q represents the proposition P → Q.
V 2 :$ P represents the proposition ¬P.
(V 3 :$ x) :$ y represents the proposition x = y.
(V 4 :$ x) :$ y represents the natural x + y.
(V 5 :$ x) :$ y represents the natural x ⋅ y.
V 6 :$ x represents the natural S(x) = x + 1.
V 7 reprents the natural 0.

In an environment with i free variables, we encode expressions, propositions, and proofs as 2×2 integer matrices [1, 0; a, b], as follows:

M(i, ∀x [P(x)]) = [1, 0; 1, 4] ⋅ M(i, λx [P(x)])
M(i, λx [F(x)]) = M(i + 1, F(x)) where M(j, x) = [1, 0; 5 + i, 4 + j] for all j > i
M(i, P → Q) = [1, 0; 2, 4] ⋅ M(i, P) ⋅ M(i, Q)
M(i, ¬P) = [1, 0; 3, 4] ⋅ M(i, P)
M(i, x = y) = [1, 0; 4, 4] ⋅ M(i, x) ⋅ M(i, y)
M(i, x + y) = [1, 0; 1, 4 + i] ⋅ M(i, x) ⋅ M(i, y)
M(i, x ⋅ y) = [1, 0; 2, 4 + i] ⋅ M(i, x) ⋅ M(i, y)
M(i, S x) = [1, 0; 3, 4 + i] ⋅ M(i, x)
M(i, 0) = [1, 0; 4, 4 + i]
M(i, (Γ, P) ⊢ P) = [1, 0; 1, 4]
M(i, Γ ⊢ P) = [1, 0; 2, 4] ⋅ M(i, Q) ⋅ M(i, Γ ⊢ Q) ⋅ M(i, Γ ⊢ Q → P)
M(i, Γ ⊢ P(x)) = [1, 0; 3, 4] ⋅ M(i, λx [P(x)]) ⋅ M(i, x) ⋅ [1, 0; 1, 2] ⋅ M(i, Γ ⊢ ∀x P(x))
M(i, Γ ⊢ P(x)) = [1, 0; 3, 4] ⋅ M(i, λx [P(x)]) ⋅ M(i, x) ⋅ [1, 0; 2, 2] ⋅ M(i, y) ⋅ M(i, Γ ⊢ y = x) ⋅ M(i, Γ ⊢ P(y))
M(i, Γ ⊢ ∀x, P(x)) = [1, 0; 8, 8] ⋅ M(i, λx [Γ ⊢ P(x)])
M(i, Γ ⊢ ∀x, P(x)) = [1, 0; 12, 8] ⋅ M(i, Γ ⊢ P(0)) ⋅ M(i, λx [(Γ, P(x)) ⊢ P(S(x))])
M(i, Γ ⊢ P → Q) = [1, 0; 8, 8] ⋅ M(i, (Γ, P) ⊢ Q)
M(i, Γ ⊢ P → Q) = [1, 0; 12, 8] ⋅ M(i, (Γ, ¬Q) ⊢ ¬P)

The remaining axioms are encoded numerically and included in the initial environment Γ:

M(0, ∀x [x = x]) = [1, 0; 497, 400]
M(0, ∀x [¬(S(x) = 0)]) = [1, 0; 8269, 8000]
M(0, ∀x ∀y [S(x) = S(y) → x = y]) = [1, 0; 56106533, 47775744]
M(0, ∀x [x + 0 = x]) = [1, 0; 12033, 10000]
M(0, ∀y [x + S(y) = S(x + y)]) = [1, 0; 123263749, 107495424]
M(0, ∀x [x ⋅ 0 = 0]) = [1, 0; 10049, 10000]
M(0, ∀x ∀y [x ⋅ S(y) = x ⋅ y + x]) = [1, 0; 661072709, 644972544]

A proof with matrix [1, 0; a, b] can be checked given only the lower-left corner a (or any other value congruent to a modulo b); the other values are there to enable composition of proofs.

For example, here is a proof that addition is commutative.

M(0, Γ ⊢ ∀x ∀y [x + y = y + x]) = [1, 0; 6651439985424903472274778830412211286042729801174124932726010503641310445578492460637276210966154277204244776748283051731165114392766752978964153601068040044362776324924904132311711526476930755026298356469866717434090029353415862307981531900946916847172554628759434336793920402956876846292776619877110678804972343426850350512203833644, 14010499234317302152403198529613715336094817740448888109376168978138227692104106788277363562889534501599380268163213618740021570705080096139804941973102814335632180523847407060058534443254569282138051511292576687428837652027900127452656255880653718107444964680660904752950049505280000000000000000000000000000000000000000000000000000000]

You can verify it with the program as follows:

*Main> let p = A $ \x -> A $ \y -> V 3 :$ (V 4 :$ x :$ y) :$ (V 4 :$ y :$ x)
*Main> let a = 6651439985424903472274778830412211286042729801174124932726010503641310445578492460637276210966154277204244776748283051731165114392766752978964153601068040044362776324924904132311711526476930755026298356469866717434090029353415862307981531900946916847172554628759434336793920402956876846292776619877110678804972343426850350512203833644
*Main> r(8?map fst(r(y 8)=<<[497,8269,56106533,12033,123263749,10049,661072709])$p)a :: [((),Integer)]
[((),0)]

If the proof were invalid you would get the empty list instead.


String rotation - output string repeatedly moving first character to the end The challenge here is to take a string and output all its rotations, by repeatedly moving the first character to the end, once per character in the string, ending with the original string:

john -> ohnj, hnjo, njoh, john

You may also cycle in the other direction, moving characters from the end:

john -> njoh, hnjo, ohnj, john

You should still output one rotation per letter even if the original word is reached before that:

heehee -> eeheeh, eheehe, heehee, eeheeh, eheehe, heehee

Character arrays are allowed, as long as the result works as shown above.

Shortest answer wins!

Haskell, 27 bytes

scanl(\(a:b)_->b++[a])=<<id

Try it online!


Holiday Gift Exchange Another problem from our internal golfing...this one around the holidays last year.

PROBLEM

Andy, Barb, Carl, Didi, Earl, and Fran are buying gifts for each other. Draw names for a gift exchange.

Each person buys one gift and receives one gift.
Nobody buys their own gift.
Running the solution multiple times should produce different results (giver-receiver pair should not be predictable or identical from run to run).

INPUT

None.

OUTPUT

Formatted as in this example:

  Andy buys for Barb
  Barb buys for Carl
  Carl buys for Didi
  Didi buys for Earl
  Earl buys for Fran
  Fran buys for Andy

J, 57

(,.' buys for ',"1|.)(?~6){6 4$'AndyBarbCarlDidiEarlFran'

eg

   (,.' buys for ',"1|.)(?~6){6 4$'AndyBarbCarlDidiEarlFran'
Carl buys for Earl
Andy buys for Barb
Fran buys for Didi
Didi buys for Fran
Barb buys for Andy
Earl buys for Carl


Respawning Factorial Write a program that does one step of the computation of factorial, then, generate (quine) a new program, and performs the rest of the process in the new program
The seed and spawned programs will have a variable n for the factorial to be computed and m for the accumulator.

I don't care if you use scripted or compiled language.
You can use the cheat of "reading the source file".
You MUST create a new file and run the new file to qualify: no self-modifying code or using code loaded in memory, but spawning with data: url in JS is allowed.

Here is an example in Java: https://gist.github.com/968033

Shortest code wins.

Perl, 95

$m=1;$n=12||die$m;@ARGV=$0;$_=<>;$m*=$n--;s/\|/;\$m=$m;\$n=$n|/;open _,">$0";print _;exec$^X,$0

The program really has to be on a single line, and overwrites itself at each iteration.


Shrink your language's character set We often get restricted-source questions here on PPCG that favour submitting solutions using only a subset of characters (sufficiently so that there's a tag printable-ascii that identifies a particular subset of those challenges). Wouldn't it be nice if we could automatically cut languages down to a subset of their normal character set?

As an example, JavaScript is sometimes translated into a subset known as JSFuck which contains only the characters []()!+. In this challenge, you're aiming to write the equivalent of a JavaScript to JSFuck translator, but without the language restriction: you're compiling a language of your choice down to a subset of its characters (well, bytes, in order to avoid dubious corner cases).

Clarifications and detailed specification

Call the program you submit program A. The input to program A will be a string representing a program (program B). Its output must also be a string representing a program (program C). Program B will be in the same language as program A (there are no restrictions on how your program reacts to invalid input). Program C must also be a program in that language, and have the same behaviour in all cases as program B (i.e. if program C is given input X, it will produce the same probability distribution of outputs as program A does).
You may assume that in the case where programs A and B are distinct, program B does not access any files from disk. (In particular, you may assume it does not attempt to read its own source code from disk.).
Although part of the scoring is based on a single test case (program A itself), your program must work for any input (in the sense of complying with the specification above; that is, any valid program B must lead to a corresponding output for program C). Optimizing specifically for the test case given is allowed (and might or might not be helpful).
A cat implementation is technically speaking a valid answer to this question (as the subsetting of characters is part of the scoring criterion, not the validity criterion), but the scoring is designed so that such a program is unlikely to win. Just as solutions to code-golf competitions should make at least an attempt to minimize the number of bytes, solutions to this competition should make at least an attempt to minimize score. (Note that in some languages, cat may genuinely work best because the character sets are already small or impossible to shave down further. These solutions are valid, but ideally wouldn't be upvoted.)
You can accept the strings used for your input and output via any reasonable method.
Because languages with no computational ability might potentially lead to trivial solutions due to there being few possible programs to consider, this competition is open only to entries written in programming languages.

Victory condition

Let S be the set of bytes that can appear in the outputs C of your program (that is: for any valid input B, if the corresponding output C can potentially contain a byte, then that byte must be an element of S). Let c be the number of elements in S.

Now, let Q be the result of running your program on itself (i.e. the output C produced when A and B are the same program). Let b be the number of bytes in Q. (In order to minimize b and thus your score, you'll want to keep your program short, as in code-golf, but also the size of your program's output short, as in metagolf.)

Your score for this code-challenge is:

(b+1000)×loge(c+1)

The winner is the entry with the lowest score. (If there's a tie for first place, the lowest c among the tied entries will win; if there's still a tie for first place, the earliest entry among the entries tied for first will win.) Even if you can't win, though, you're encouraged to show off interesting answers (perhaps answers with a particularly low c, or in a language other people haven't attempted yet).

Brainfuck, (1000 + 133) * loge(8+1) ~= 2489

Requires an interpreter that has wrapping 8-byte unsigned cells and produces 0 or doesn't change the cell on EOF.

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

A proper brainfuck interpreter ignores any character except []<>+-,., so we minify the character set by keeping only those characters.

For example, giving this as input to the above program produces the above program:

,[>>>
prepare array
--[>-<++++++]>>->->->-------------->-->>>-[++[>]<<->+]--
[<]<<<[->+>>+<<<]+>>>
while number to the right of i
>[
    <[->+<] move sum of both to the right
    +>[<-]<[ if sum == 0
        clear everything to the right
        ->>[[-]>]
        move to the left until we hit 1
        -[+<-]
        output i and move past to stop loop
        +>.>
    ]
    >>>
]
-[[+]<-]
,]


Write an program that terminates after 60 seconds - Cops' Thread This is a cops and robbers challenge - Robber's Thread

Write a program that terminates after exactly 60 seconds (or as close to it as possible). For example:

#include <unistd.h>
int main(int argc, char **argv){
    sleep(60);
    return 0;
}

However, your goal is to write this program such that terminating after exactly 1 minute is essentially inherent to the program's execution - it should be difficult to change the program to predictably run for a different amount of time without overhauling the algorithm. The robbers will attempt to change your program such that it terminates after 31 seconds instead of 60, and they will have to do so with a solution whose Levenshtein edit distance is up to half of the length of your submission.

If you do not wish to take advantage of system interrupts or the system clock, you can use either of the following:

The speed of printing to stdout is controlled by the baud rate of the terminal you are printing to. If you wish, you can control the speed of your program by printing to stdout with a set baud rate. However, you must also cite an actual piece of hardware or terminal program that has that baud rate as default (e.g. a serial printer with a default print speed of 300 baud).
If you are working in a language where all operations take some constant amount of time (such as assembly language), you can control the speed of your program by specifying the processor's clock rate. However, this too must be accompanied with a citation of an actual processor chip that runs at that speed (e.g. the 1 MHz 6502 put inside Apple //e and NES boards).

This is cops and robbers, so prepare to rigorously defend your algorithm! If your solution has been cracked, put [Cracked](link to cracker) in your header. If your solution remains uncracked after exactly 2 weeks, it is safe from future cracking attempts - put Safe in your header and explain how your algorithm works.

The winner of this challenge is the Safe solution with the most upvotes.

Perl 52 bytes (26 edits allowed) (Safe, technically speaking)

sub a{[gmtime+time]->[0]^$x}$x=a;0 until a;0 while a

Unfortunately, I don't think it's possible to write an uncrackable Perl program (it should become obvious why if and when this is cracked; being able to edit half the program is just too much), but this algorithm should be very hard to change to wait for any length of time other than 1 minute.
Marking this as safe, as nobody's officially submitted a crack for 14 days (although someone unofficially cracked it by just writing a separate program and commenting out the existing code). The basic idea of the program is as follows: we look at the seconds digit of the time, loop until it changes, then loop until it returns to its original value. This requires quite some changes to alter to a length of time other than 1 minute, 1 hour, or 1 day (although 26 edits is easily enough – you can do some modular arithmetic on the seconds value to determine a new target to wait until – but nobody found that solution).


Code that will only execute once Goal

The goal of this challenge is to write code that will execute once and only once.  This means basically that it damages the program, script, or environment in some way.  If rebooting the system allows the code to run again that is permitted.

Scoring

Number of votes.  All assumptions must be clearly listed.  Any answers just initiating a reboot or halt will be disqualified.

Additional Rules because Greg Hewgill is a demi-god

No root access is permitted.

End Date

The contest will close on May 31, 2014.

Edit

This contest has been changed to popularity contest.

Vigil
Finally a usecase for Vigil!
def main():
  raise Exception()

Excerpt from the "language specification":

It goes without saying that any function that throws an exception which isn't caught is wrong and must be punished.
...
If an oath is broken, the offending function [...] will be duly punished.
How?
Simple: it will be deleted from your source code.
The only way to ensure your program meets its requirements to absolutely forbid code that fails to do so. With Vigil, it will do this for you automatically.

There are other ways to do this, because Vigil provides the keywords implore and swear which are basically oaths to adhere to certain pre- and post-conditions:
def main():
  swear 0 > 1


Hex Dump your Source Code When code-golfing there will be times where you need a Hex Dump of your code, usually because you've used unprintable characters. So, why not make a program that Hex Dumps itself?

The Challenge

This challenge is to, given no input, output a Hex Dump of your source code in the following formatting:

0000: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0010: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0020: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0030: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................

Or, for example, if your program was print("SomeString"):rep(123)

0000: 70 72 69 6e 74 28 5c 22 53 6f 6d 65 53 74 72 69  print("SomeStrin
0010: 6e 67 5c 22 29 3a 72 65 70 28 31 32 33 29        g"):rep(123)

Specifics

The hex dump is split into rows of three parts, each row representing 16 bytes of your source code.

The first part is the memory address. It specifies where the current row starts in your code. Written as a 2 Byte Hexadecimal number, followed by a :, then a space.

The Second, is the Hex Dump itself. This is 16 bytes of your Source Code, written in Hexadecimal form separated by spaces. This should be an accurate byte representation using your code's encoding.

Lastly, after a two space gap, is the code itself. This is simply 16 characters of your code, with Non printable characters written as .

Notes

This is a quine challenge, so Standard Quine Rules apply.
And this is code-golf challenge too, so Standard Loopholes apply.
As shown in the second example, do not write bytes after EOF, instead use whitespace.
Trailing whitespace is fine.
Inbuilts to Hex dump, if you happen to have one in this specific format, are not banned but are frowned upon.
Non printable characters refer to any character that, represented as only a single byte, cannot be represented as a single spaced glyph. For UTF-8, this means 0-31, 128-255. For the Jelly Codepage, as all characters can be represented as a single spaced glyph, there are no Non printable characters.


Sieve of Eratosthenes, Step by Step Given a number N, draw a left aligned NxN board of numbers, leaving 1 blank (as a space) (I will show diagrams with N=5)

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

Your job is to construct the Sieve of Eratosthenes, step by step. First, start with 2. It's prime, so leave it there, and replace all other numbers divisible by 2 with the proper number of spaces.

   2  3     5
   7     9
11    13    15
   17    19
21    23    25

Next, go to the next unprinted number (3 in this case) and do the same.

   2  3     5
   7
11    13
   17    19
      23    25

And so on, until you reach N.

You need to first print the complete grid, and every time you go to a new number, print the board with the multiples removed. Make sure you print a blank line in between!

Examples

Text in parenthesis () are just for reference, you don't need to print it

N = 2:

  2 (complete grid)
3 4

  2 (remove multiples of 2)
3

N = 3:

  2 3 (complete grid)
4 5 6
7 8 9

  2 3 (remove multiples of 2)
  5
7   9

  2 3 (remove multiples of 3)
  5
7

Remember, this is code-golf, so the code with the smallest number of bytes wins.

Jelly, 34 bytes

Ṿ€“1“ ”ys³G
>®i©1ḍoṛ®¦
²R;1©ÇÐĿÑ€Y

Try it online!

How it works

²R;1©ÇÐĿÑ€Y  Main link. Argument: n (integer)

²            Yield n².
 R           Range; yield [1, ..., n²].
   1©        Yield 1 and copy it to the register.
  ;          Append 1 to the range.
             This is the initial state. Let's call it S.
     ÇÐĿ     Call the second helper link until the results are no longer unique.
             This returns all unique results as an array.
        Ṅ€   Call the first helper link on each result.
          Y  Join, separating by linefeeds.

>®i©1ḍoṛ®¦   Second helper link. Argument: S (state)

>®           Compare all integers in S with the value in the register.
  i 1        Find the first index of 1 (i.e., the first number that is greater
             than the register.
   ©         Copy the index to the register. Let's call the index p.
     ḍ       Test all numbers in S for divisibility by p. This yield 1 for
             multiples of p, 0 otherwise.
      o      Logical OR; replace 0's with the corresponding values of S.
       ṛ®¦   Replace the 0 at index p with the corresponding element of S (p).
             For the purposes of the explanation, S is now the updated state.

Ṿ€“1“ ”ys³G  First helper link. Argument: A (array)

Ṿ€           Uneval each; convert all integers in A into strings.
  “1“ ”y     Replace each string "1" with the string " ".
        s³   Split into chunks of length n (command-line argument).
          G  Grid; separate row items by spaces (left-padding since the row items
             are strings), the rows themselves by linefeeds.


I don't even... I only odd! Your task is simple: write a program that receives an integer as input and outputs it if it was odd, and does nothing otherwise (not halting is allowed). The challenge is, that you can only use odd bytes.

You can optionally append a trailing newline to the output.

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

Standard loopholes are forbidden. Furthermore, you cannot use versions of languages, which are newer than the posting of this challenge.

Example input > output:

13 > 13

42 >


Watson-Crick palindromes Problem

Create a function that can determine whether or not an arbitrary DNA string is a Watson-Crick palindrome. The function will take a DNA string and output a true  value if the string is a Watson-Crick palindrome and a false value if it is not. (True and False can also be represented as 1 and 0, respectively.)

The DNA string may either be in all uppercase or all lowercase depending on your preference.

Also, the DNA string will not be empty.

Explanation

A DNA string is a Watson-Crick palindrome when the complement of its reverse is equal to itself.

Given a DNA string, first reverse it, and then complement each character according to the DNA bases (A ↔ T and C ↔ G). If the original string is equal to the complemented-reverse string, it is a Watson-Crick palindrome.

For more, see this question. It is a different challenge where you must find the longest substring of a DNA string where that substring is a Watson-Crick palindrome.

Goal

This is code-golf and the shortest code wins.

Test Cases

The format is <input> = <output>.

ATCGCGAT = true
AGT = false
GTGACGTCAC = true
GCAGTGA = false
GCGC = true
AACTGCGTTTAC = false
ACTG = false

05AB1E, 10 7 bytes

Code:

Â'š×Â‡Q

Explanation:

To check if a string is a palindrome, we just need to check the input with the input, with at swapped and cg swapped and then reverse it. So that is what we are going to do. We push the input and the input reversed using Â (bifurcate). Now comes a tricky part. 'š× is the compressed version for creating. If we reverse it, you can see why it's in the code:

CreATinG
|  ||  |
GniTAerC

This will be used to transliterate the reversed input. Transliteration is done with ‡. After that, we just check if the input and the transliterated input are eQual and print that value. So this is how the stack looks like for input actg :

Â          # ["actg", "gtca"]
 'š×       # ["actg", "gtca", "creating"]
    Â      # ["actg", "gtca", "creating", "gnitaerc"]
     ‡     # ["actg", "cagt"]
      Q    # [0]

Which can also be seen with the debug flag (Try it here).

Uses CP-1252 encoding. Try it online!.


Secret Santa Challenge Possible Duplicate:
  Holiday Gift Exchange

Background:
Secret Santa is a Western Christmas tradition in which members of a group or community are randomly assigned a person to whom they anonymously give a gift.

http://en.wikipedia.org/wiki/Secret_Santa

Ok, me and my work colleges did this today during our lunch hour - we made a secret algorithm santa pick random gifters and receivers.

Think of this question as a Christmas Programming Challenge to see who can come up with some of the most elegant solutions for this problem.

Input:
The input should be an array ['Oliver', 'Paul', 'Rowan', 'Darren', 'Nick', 'Atif', 'Kevin']

Output
A representation of something similar to key value pairs for the gifter and receiver. e.g.

Oliver -> Darren,
Paul -> Nick,
Rowan -> Kevin
Kevin -> Atif,
Darren -> Paul,
Nick -> Oliver,
Atif -> Rowan

Deadline: 15th December (for those late christmas shoppers)

Remember: you cannot have a person choosing themselves and the program must not spiral off into an infinite loop when gifter == receiver when there is only one person left.

Rules:

Must not have duplicates
Must be random (we all have different views on what is random - but you get my gist)
No Language constraints
Have fun

Here is mine (not golfed) in ruby:

require 'pp'

def move(array, from, to)
  array.insert(to, array.delete_at(from))
end

gifters = ['Oliver', 'Paul', 'Rowan', 'Darren', 'Nick', 'Atif', 'Kevin'].shuffle!
recievers = gifters.dup

move recievers, recievers.count - 1, 0

pp Hash[gifters.zip recievers]

which spits out:

{"Nick"=>"Darren",
 "Paul"=>"Nick",
 "Kevin"=>"Paul",
 "Rowan"=>"Kevin",
 "Atif"=>"Rowan",
 "Oliver"=>"Atif",
 "Darren"=>"Oliver"}

k (29 20 chars)

{i!(1_i),*i:(-#x)?x}

    {i!@[i:(-:#x)?x;,/|2 0N#!#x]}

Example

k){i!(1_i),*i:(-#x)?x}`person1`person2`person3`person4`person5
person2| person1
person5| person3
person4| person2
person1| person5
person3| person4

Explanation - as above, shuffles list and maps to rotation of itself.