Day of the week for a given date of this year. Do not use any date tools Please write a program that takes as input two numbers 'day of the month' and 'month number' for any day of this year (2012) and outputs day of the week.
Examples:

% ruby ./golf.rb 14 07 # 14th of July
"Sat"
% ruby ./golf.rb 14 7  # the same
"Sat"
% ruby ./golf.rb 01 12 # Dec 1
"Sat"
% ruby ./golf.rb 31 12 # Last day of the year
"Mon"

Output format should be like Mon, Tue, Wed, Thu, Fri, Sat, Sun, not less than 3 letters
Do not use date libs/modules, just math and logic
Wins the shortest script in any language.

C++   (142) (135)    (129 chars)

main(){string s[]={"Mon","Tue","Wen","Thu","Fri","Sat","Sun"};int d,m,t[]={0,5,1,1,4,6,2,4,0,3,5,1,3};cin>>d>>m;cout<<s[(d+t[m]+15-(m<3))%7];}

The requirement that the letters Mon, Tue etc. appear made it quite bad, otherwise it would be only 84 chars. I'll search a golf for the strings...

Hm, trying to golf the string only made it 2 chars longer, but I find it more aesthetically pleasing.

main(){char s[]={"MonTueWenThuFriSatSun"};int d,m,t[]={0,5,1,1,4,6,2,4,0,3,5,1,3};cin>>d>>m;d=((d+t[m]+15-(m<3))%7)*3;s[d+3]=0;printf("%s",s+d);}

Well, this for my first entry at a golf contest, I have still much to learn...

HA! Got it!

main(){char s[]={"MonTueWenThuFriSatSun"},t[]={"0511462403513"};int d,m;cin>>d>>m;d=((d+t[m]-33-(m<3))%7)*3;s[d+3]=0;printf("%s",s+d);}

with a well set compiler and some luck we might chop another 3 characters, by using char* instead of char[], but it will crash on most systems. Anyway, it doesn't matter, as I believe soon someone will post a solution in J or K with less than 10 characters, as usual :P

I'll never give up!

main(){char s[]={"MonTueWenThuFriSatSun0511462403513"};int d,m;cin>>d>>m;d=((d+s[m+21]-33-(m<3))%7)*3;s[d+3]=0;printf("%s",s+d);}


write an "operating system" that dims Num Lock I want to write x86 assembler code that can be used to boot your computer from and dims NumLock. This means

you cannot rely on glibc or any other of these "comfi" libraries
you cannot rely on the Linux kernel
we will test your code by dumping it onto a virtual floppy and boot a VM from it
goal is to switch on and off NumLock so quickly that it appears dimmed
it's okay if everything fits into the bootloader and loops endlessly

Solution with most votes wins.

I haven't tested this (VirtualBox doesn't pass through its virtual keyboard LEDs onto the physical keyboard, and I'm not on a PC I can reboot currently). But I think it should probably work and is probably quite minimal.

There may be some additional setup that needs to be done on the keyboard controller for these commands to work. If so it would be essentially trivial to add to the code below...

[bits 16]
[org 0x7c00]
mov al, 0xed
out 0x60, al
mov al, 0x07
out 0x60, al
mov al, 0xed
out 0x60, al
mov al, 0x00
out 0x60, al
jmp $$
times 510 - ($ - $$) db 0
dw 0xaa55

Compile with nasm -f bin -o floppy.img numlock.asm.

Will give this a real test and tweak accordingly later (if someone else wants to try and/or tweak it feel free).


Make a pattern alternate Problem

You are given a sequence of coloured balls (red R and green G). One such possible sequence is:

RGGGRRGGRGRRRGGGRGRRRG

In as few moves as possible, you must make it so that each ball is a different colour to its neighbours (i.e. the sequence alternates.)

RGRGRGRGRGRGRGRGRGRGRG

You should write a program that can convert an unordered sequence (in this case a string) with equal numbers of "R" and "G" into a sequence where the items alternate. One example session is below, for a naive algorithm (< is input to program, > is output. It isn't necessary to include the carets on the input or output.)

< RGGGRRGGRGRRRGGGRGRRRG
> RGGRGRGGRGRRRGGGRGRRRG
> RGRGGRGGRGRRRGGGRGRRRG
> RGRGRGGGRGRRRGGGRGRRRG
> RGRGRGGRGGRRRGGGRGRRRG
> RGRGRGGRGRGRRGGGRGRRRG
> RGRGRGGRGRGRGRGRGGRRRG
> RGRGRGGRGRGRGRGRGRGRRG
> RGRGRGGRGRGRGRGRGRGRGR
> RGRGRGRGGRGRGRGRGRGRGR
> RGRGRGRGRGGRGRGRGRGRGR
> RGRGRGRGRGRGGRGRGRGRGR
> RGRGRGRGRGRGRGGRGRGRGR
> RGRGRGRGRGRGRGRGGRGRGR
> RGRGRGRGRGRGRGRGRGGRGR
> RGRGRGRGRGRGRGRGRGRGGR
> RGRGRGRGRGRGRGRGRGRGRG (15 moves)

Another possibility is outputting "5,7" for example to indicate swapping of positions 5 and 7.

You may position either Red or Green first, and you don't have to be consistent. Each sequence will be the same length as every other sequence.

You may only swap any two letters in each move (they do not need to be adjacent.)

Winning Criteria

The program must show each step of the sort process. The program which makes the fewest total moves for all the below strings, wins. If there is a tie, the shortest code will win.

Input Strings

The following strings will be used to test the programs:

GGGGGGGGGGRRRRRRRRRR
GGRRGGRRGGRRGGRRGGRR
RRGGGGRRRRGGGGRRRRGG
GRRGRGGGGRRRGGGGRRRR
GRGGGRRRRGGGRGRRGGRR
RGRGRGRGRGRGRGRGRGRG

The last sequence should result in zero moves.

Python, 140 122 119 115

r=raw_input()
f=lambda x:[i for i in range(x,len(r),2)if x-(r[i]!=max('RG',key=r[::2].count))]
print zip(f(0),f(1))


Finite State Machine validity I've been around for a while, watching you golf and I really enjoy it.
I came up with a challenge for you all so let's begin!
Challenge
I assume that everyone knows what Finite State Machine (FSM) is, I will edit the the description if needed.

Your program will take only one input consisting in a string that represents a FSM.
The first character of the input is the FSM's initial state and the last character is the FSM's final state.
Transitions are represented as two consecutive characters (AB will be the transition from state A to state B. ABCD will be the two transitions A to B and C to D)
In this challenge, the FSM is considered valid when you have at least one path from the initial state to the final state.

Goal
Output a truthy value, telling the world if the input is a valid FSM (any equivalent for True of False is fine)
Bonus

-20% if you add all the sequences of valid paths to the output

Examples
AB should output (with bonus) true AB
ABC should output false (No transition to state C)
ABCEBD should output (with bonus) true ABD (The presence of unreachable states C and E doesn't make it false)
ISSTSFTF should output (with bonus) true ISF ISTF
ABACBCCD should output (with bonus) true ACD ABCD
ABACBCD should output false
ABACADCDBCDEBE should output (with bonus) true ABE ADE ACDE ABCDE
Final word
If you think this challenge lacks something, please tell me, I'd really like to see the answers you can come up with

JavaScript (ES6), 81 bytes

s=>(a=[...s]).map(_=>a.map((m,i)=>p=i%2&r[s[i-1]]?r[m]=1:r[m]),r={},r[s[0]]=1)&&p

Explanation

Takes the states as a string and returns a 1 for true or undefined for false. This method was the shortest I could find, but it means that it's impossible to include the bonus because it just determines reachability, not the paths.

s=>
  (a=[...s])        // a = states as an array
  .map(_=>          // loop a number of times to ensure all states have been reached
    a.map((m,i)=>   // for each state m at index i
      p=            // p = the reachability of the final state
        i%2         // if this is the last state of a pair
        &r[s[i-1]]? // and the first state is reachable
          r[m]=1    // set the last state and p to reachable
          :r[m]     // else set p to the reachability of the state
    ),
    r={},           // map of truthy values for reachable states
    r[s[0]]=1       // set the initial state to reachable
  )
  &&p               // return the final result

Test

var solution = s=>(a=[...s]).map(_=>a.map((m,i)=>p=i%2&r[s[i-1]]?r[m]=1:r[m]),r={},r[s[0]]=1)&&p
<input type="text" id="input" value="ABACADCDBCDEBE" />
<button onclick="result.textContent=solution(input.value)">Go</button>


Encode bytes to PGP wordlist format The PGP Word List is a set of 512 English words for verbally communicating strings of bytes, such as authentication codes or hashes. It is used in secure VoIP software as well as in some other important applications, such as the DNSSEC Root KSK Ceremonies held four times a year.
It consists of 256 two-syllable words and 256 three-syllable words. Bytes at even offsets become two-syllable words, while bytes at odd offsets become three-syllable words. This protects against transposition of adjacent words, repetition of a word, or omission of a word.
The two subsets are kept as alphabetical lists and numbered accordingly, so a null byte (hex 00) becomes "aardvark" at an even offset and "adroitness" at an odd offset. Likewise, the words for hex FF are "Zulu" and "Yucatan" respectively.

Write a complete program to encode a sequence of bytes (represented as pairs of hex digits) as a sequence of words from the PGP Word List.
Because the program is to be run on a secure, air-gapped computer, and USB drives are a security risk, the program should be as short as possible to facilitate manual entry. (The length of each program is measured in bytes, because if I were to use the complicated keystroke formula I came up with, this specification would be twice as long as it is now.)
Input format
The program must accept a string of hex digits as either a single line of input or a command-line argument. You may assume the following:

There are no spaces or other separators between hex digits.
The number of hex digits is between 2 and 128 inclusive.
The number of hex digits is even.
Digits A-F are either all lowercase or all uppercase (if the required letter case is documented).

Example input: 9030e74b
Output format
The program must print a corresponding line of words from the PGP Word List. Adjacent words must be separated by a single space. However, case of the letters within the words may differ from that shown in the PGP Word List.
Example output: peachy commando transit disable
Restrictions
The program must not rely on any external copy of the PGP Word List, including any data known to be largely derived from the list that may be present in a system file or library.
Test cases
A TSV file is provided. In each line, column 1 contains the input (as lowercase hex digits), and column 2 contains the corresponding output. More test cases may be added if necessary.


Output the nth digits of an integer Without using strings (except when necessary, such as with input or output) calculate the nth digit, from the left, of an integer (in base 10).

Input will be given in this format:

726433 5

Output should be:

3

as that is the fifth digit of "726433".

Input will not contain leading zeros, e.g. "00223".

Test cases / further examples:

9 1  ->  9
0 1  ->  0
444494 5  ->  9
800 2  ->  0

This is code golf; least amount of characters wins, but any built in functions such as "nthDigit(x,n)" are not acceptable.

Here's some pseudo-code to get you started:

x = number
n = index of the digit
digits = floor[log10[x]] + 1
dropRight = floor[x / 10^(digits - n)]
dropLeft = (dropRight / 10 - floor[dropRight / 10]) * 10
nthDigit = dropLeft

As you can see I'm new to code golf, and though I think it's a bit unfair that I ask a question before I've even answered one, I would really like to see what kind of responses this generates. :)

Edit: I was hoping for mathematical answers, so I cannot really accept answers that rely on converting strings to arrays or being able to access numbers as a list of digits.

We have a winner

Written in "dc", 12 bytes. By DigitalTrauma.

GolfScript (10 bytes)

~(\10base=

This assumes input is as a string (e.g. via stdin). If it's as two integers on the stack, the initial ~ should be removed, saving 1 char.

If the base conversion is considered to fall foul of the built-in functions rule, I have a 16-char alternative:

~~)\{}{10/}/=10%


Zzub Zzif (reverse Fizz Buzz) Given a snippet of fizz buzz output with all numbers removed, fill in the correct numbers with the lowest possible values such that the fizz buzz snippet is correct.  For the purposes of this challenge, fizz and buzz have their usual values of 3 and 5, respectively.

If the input is an invalid sequence of fizz, buzz and empty lines, then instead output just zzubzzif (with or without newlines).

Input and output may be newline separated lines, or whatever array-of-strings format is convenient to your language.

You may ignore or do whatever you like with capitalisation.

You will need to choose to handle one or more of these: fizzbuzz, fizz buzz, buzz fizz, etc, but you must choose at least one of these formats.

You may assume that all input is some sequence of fizz, buzz and empty lines.

Examples

Input:

fizz

Output:

2
fizz
4

Input:

buzz
fizz

Output:

buzz
fizz
7

Input:

fizzbuzz

Output:

13
14
fizzbuzz
16
17

Input:

Output:

1

Input:

fizz
fizz

Output:

zzubzzif

Input:

Output:

zzubzzif

Java, 205 bytes

s->{o:for(int i=0,j,h=s.length;++i<16;){for(j=h;j-->0;)if(s[j].contains("fizz")^(i+j)%3<1||s[j].contains("buzz")^(i+j)%5<1)continue o;String z=i+"";for(j=1;j<h;)z+="\n"+(i+j++);return z;}return"zzubzzif";}

Takes a String[] as input and returns a String.
Expanded, runnable code:
public class C {

    static final java.util.function.Function<String[], String> f = s -> {
        o:
        for (int i = 0, j, h = s.length; ++i < 16;) {
            for (j = h; j --> 0;) {
                if (s[j].contains("fizz") ^ (i + j) % 3 < 1 ||
                    s[j].contains("buzz") ^ (i + j) % 5 < 1) {
                    continue o;
                }
            }
            String z = i + "";
            for (j = 1; j < h;) {
                z += "\n" + (i + j++);
            }
            return z;
        }
        return "zzubzzif";
    };

    public static void main(String[] args) {
        System.out.print(f.apply(new String[]{"fizz", "", "buzz"}));
    }
}


Shift the letters, soldier? Context

We're at war! You need to transfer an important message to your general to inform them from an imminent assault. The thing is, your enemy knows a lot about cryptography : you will need to be more creative in order to encode your message...

Task

Create a program that accepts an ascii message as input, and outputs the encoded message. The message should be encoded this way : each character should get its ascii value shifted by its position in the message.

For example, let's encode the message "Hello, world!"

H   e   l   l   o   ,       w   o   r   l   d   !     Original message

72  101 108 108 111 44  32  119 111 114 108 100 33    ASCII value

0   1   2   3   4   5   6   7   8   9   10  11  12    Place in the message

72  102 110 111 115 49  38  126 119 123 118 111 45    Encoded ascii (line 1 + line 2)

H   f   n   o   s   1   &   ~   w   {   v   o   -     Encoded message

The message Hello, world! should be encoded as Hfnos1&~w{vo-.

Sometimes the encoded ascii can go beyond printable character. In that case, the value loop back to 32 (read the rules for additionnal informations)

T   h   e       r   a   n   d   o   m       g   u   y      Original message

84  104 101 32  114 97  110 100 111 109 32  103 117 121    ASCII value

0   1   2   3   4   5   6   7   8   9   10  11  12  13     Place in the message

84  105 103 35  118 102 116 107 119 118 42  114 129 134    Encoded ascii (line 1 + line 2)

84  105 103 35  118 102 116 107 119 118 42  114 34  39    Corrected encoded ascii (looped back to 32)

T   i   g   #   v   f   t   k   w   v   *   r   "   '

The random guy is then converted into Tig#vftkwv*r"'

Using the same strat, zzzzzzzzz will be converted into z{|}~ !"# (ascii values converted into 122 - 123 - 124 - 125 - 126 - 32 - 33 - 34 - 35)

Rules

The input message will be composed of printable ascii character (between 32 and 126)
The message should be encoded as described before.
The ascii values of the encoded message should be set between 32 and 126.
The first character of the message should be at position 0.
If the new ascii value goes beyond the limit, it should loop back to 32.
Every character should be encoded. This includes punctuation, spaces etc.
No standard loopholes allowed.
This is codegolf, so the shortest code wins.

Python 3.8, 55 54 bytes

Output is a list of characters.

lambda s,d=33:[chr((ord(c)-(d:=d-1))%95+32)for c in s]

Try it online!


Find the odd character out in a pattern Input

The first line will be a certain string repeated any amount of times. For example, it could be abcabcabcabc, [];[];[];, etc. It may be cut off; for example: 1231231231. Always find the shortest string; for example, if the line is 22222, then the string is 2, not 22 or 22222 or anything else. The string will always be repeated at least 2 full times.

All subsequent lines will be that pattern offset by any number. For example, it could be:

abcabcabc
cabcabcab
bcabcabca

(offset by 1), or it could be:

abcdefabcdefabcdefabc
cdefabcdefabcdefabcde
efabcdefabcdefabcdefa

(offset by 4).

One of the characters in the input will be wrong. (It is guaranteed not to be on the first line.) For example, in this input:

a=1a=1a=1
=1a=1a=1a
1a=11=1a=
a=1a=1a=1
=1a=1a=1a

the 1 on line 3 is the odd one out.

Output

You must output the (zero-based, starting from the top left) coordinates of the odd one out. For example, in the above input, the corresponding output is 4,2. You may also output 4 2, or "4""2", or even [[4],[2]], or any other format, as long as you can tell what the output is supposed to be.

Test cases

Input:

codegolfcodegolfco
egolfcodegolfcodeg
lfcodegolfcodegoff
odegolfcodegolfcod
golfcodegolfcodego
fcodegolfcodegolfc

Output: 16,2

Input:

][[][][[][][[][][[][][[
[][][[][][[][][[][][[][
[][[][][[][][[][][[][][
[[][][[]]][[][][[][][[]

Output: 8,3

Input:

...
. .
...

Output: 1,1

Input:

ababa
babab
ababb
babab

Output: 4,2

Go!

Perl, 212 191 181 168 bytes

$_=<>;/^(((.*?)(.*?))\2+)\3$/;$x=$1x4;while(<>){chop;$x=~/\Q$_\E/&&next;for$i(0..y///c-1){for$r(split//,$x){$b=$_;$b=~s/(.{$i})./$1$r/;$x=~/\Q$b\E/&&die$i,$",$.-1,$/}}}

This version uses an optimized trick for catching the reply unit, learned in Dennis' answer.
Optimization by using the property that all lines have equal lengths.
Line end is also needed for the last line, otherwise chomp instead of chop should be used.
Optimizations of ardnew's comment added.

Old version, 212 bytes:

$_=<>;chop;/^(.+?)\1+(??{".{0,".(-1+length$1).'}'})$/;$;=$1;while(<>){$x=$;x length;chop;$x=~/\Q$_\E/&&next;for$i(0..-1+length$_){for$r(split//,$;){$b=$_;$b=~s/(.{$i})./$1$r/;$x=~/\Q$b\E/&&exit print$i,$",$.-1}}}

Ungolfed version:

$_ = <>;  # read first line
/^(((.*?)(.*?))\2+)\3$/;
# The repeat unit \2 consists of \3 and \4,
# and the start part \2 can be added at the end (as partial or even full unit).
$x = $1 x 4; # $x is long enough to cover each following line

# Old version:
# /^(.+?)\1+(??{ ".{0," . (-1 + length $1) . '}' })$/;
# $a = $1; # $a is the repeat unit.
# The unit is caught by a non-greedy pattern (.+?) that is
# repeated at least once: \1+
# The remaining characters must be less than the unit length.
# The unit length is known at run-time, therefore a "postponed"
# regular expression is used for the remainder.

# process the following lines until the error is found
while (<>) {
    # old version:
    # $x = $a x length;
    # $x contains the repeated string unit, by at least one unit longer
    # than the string in the current line
    chop; # remove line end of current line
    $x =~ /\Q$_\E/ && next;
          # go to next line, if current string is a substring of the repeated units;
          # \Q...\E prevents the interpretation of special characters
    # now each string position $x is checked, if it contains the wrong character:
    for $i (0 .. y///c - 1) {  # y///c yields the length of $_
        for $r (split //, $x) { #/ (old version uses $a)
            # replace the character at position $i with a
            # character from the repeat unit
            $b = $_;
            $b =~ s/(.{$i})./$1$r/;
            $x =~ /\Q$b\E/
               && die $i, $", $. - 1, $/;
               # $" sets a space and the newline is added by $/;
               # the newline prevents "die" from outputting line numbers
        }
    }
}


Simple code golf challenge: Character patterns! In this challenge, you receive a string as input containing a string of X's, Y's and Z's eg. "XYZZ". X, Y and Z represent a particular character. This pattern is then compared with a second string input. If the pattern exists as a substring in the second input, return True, otherwise, return False. Once a pattern is found in the word, the program stops searching and returns True.

Examples

Pattern: "XXYY"

succeed ---> True (pattern found: ccee)
success ---> False (pattern not matched)
balloon ---> True (pattern found: lloo)

Pattern: "XYXYZ"

bananas ---> True (pattern found: nanas)
banana  ---> False (pattern not found)

Note: This is not the actual input. This is an example of how the  program should work. Your program should output True or False, or other Truthy/Falsy values.

Other important/useful information

The pattern does not need to contain an X, Y and a Z, it could contain X's and Y's or even (although somewhat pointless) just X's.
The pattern cannot be empty, but this will not be used as a test case.
The search string will not be empty, and will be lowercase.
The alphabetic order of X, Y and Z in the pattern does not matter.
X, Y and Z must be unique characters.
You may use any library you wish.
The score is determined by the code size, in bytes. Lowest score wins.

Good luck!

Perl 5, 85 bytes

Saved 40 bytes thanks to Peter Taylor's suggestion! (see my older version bellow to see the differences)

83 bytes of code + -pl flag.

s/./$h{$&}?"\\$h{$&}":($h{$&}=$.,join("",map"(?!\\$_)",1..$.++)."(.)")/ge;$_=<>=~$_

Try it online!

XYXYZ is transformed into ((?!\1).)((?!\1)(?!\2).)\1\2((?!\1)(?!\2)(?!\3).) (yup, some of the tests can't be true, but it's shorter that way), and the second input is then checked against that regex. (see the explanations of my older version to get more intuition of how it works)

My older version:
Thanks to Arnauld for pointing out a mistake I made in my first version.
113 bytes of code + -pl flags, and -Mre=eval.

s/./$h{$&}?"\\$h{$&}":($h{$&}=++$i,"(.)")/ge;$_.='(?{++$c;$\=1if!grep$v{$c}{${$_}}++,1..'.(keys%h).'})^';<>=~$_}{

Try it online!

On the example XYXYZ: the first regex will convert the pattern to (.)(.)\1\2(.), and add at the end a test to check if $1, $2 and $3 are different: if so, $\ is set to one. Then, the second input is testes against this regex, and $\ is implicitely printed at the end.
The regex generated for XYXYZ is (.)(.)\1\2(.)(?{++$c;$\=1if!grep{$v{$c}{${$_}}++}1..3})^.
(I'll to add a bit more details to the explanations when I have a moment)


Pad a matrix with its sums Challenge:
Given a square input matrix \$A\$, pad the matrix with one row and one column on all four sides.

The value of each element in the top and bottom row should be the sum of the elements in each corresponding column.
The value of each element in the left and right column should be the sum of the elements in each corresponding row.
The value of the elements in the top left, and bottom right corner should be the sum of the elements on the diagonal
The value of the elements in the top right, and bottom left corner should be the sum of the elements in the anti-diagonal.

Example:
A =
1   5   3
3   2   4
2   5   5

Output:
 8    6   12   12    7
 9    1    5    3    9
 9    3    2    4    9
12    2    5    5   12
 7    6   12   12    8

Explanation:
The top left and bottom right elements are the sum of the diagonal \$1+2+5=8\$. The top right and bottom left elements are the sum of the anti-diagonal \$2+2+3=7\$.
The top and bottom row (except the corners) are the sum of each of the columns in \$A\$: \$1+3+2=6\$, \$5+2+5=12\$ and \$3+4+5=12\$. Similarly, the left and right column (except the corners) are the sum of each of the rows of \$A\$: \$1+5+3=9\$, \$3+2+4=9\$ and \$2+5+5=12\$.
Input:

A non-empty square matrix, with non-negative integers.
Optional format

Output:

The matrix padded as explained above
Optional format, but it must be the same as the input format

Test cases:
Use the submissions in this challenge if you want to convert the input format to a more suitable one (for instance [[1, 5],[0, 2]]).
0
----------------
0 0 0
0 0 0
0 0 0

1 5
0 2
----------------
3 1 7 5
6 1 5 6
2 0 2 2
5 1 7 3

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

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

This is code-golf, so the shortest solution in each language wins. Explanations are highly encouraged.

Jelly, 27 bytes

,UŒDḢ$S$€,Ṛ$j€SW€jSẋ¥€2$j"$

Try it online!


Generate a Texting Dictionary this challenge was based on a sandboxed post by @dmckee

Old fashioned cell phones were and are used heavily as texting platforms, unfortunately the keyboard has only 12 + a few buttons, and is therefor ill-suited to naive text entry.

Common solutions make use of the traditional telephone coding (generally with a modest extension for 'q' and 'z'):

2: a,b,c
3: d,e,f
4: g,h,i
5: j,k,l
6: m,n,o
7: p(,q),r,s
8: t,u,v
9: w,x,y(,z)

In this case we are interested in the one-press-per-letter schemes that offer up words matching words on a frequency basis. That is if the user type "4663" the phone will offer up words like "good", "home", "gone", "hood", "hoof", etc that code to 4663 in order of their frequency.

Your task is to read one or more input files and generate a frequency sorted dictionary that could be used to implement this scheme.

Inputs

All input will be plain ASCII text.
You may accept input from named files, the standard input, or other conventional source supported by your implementation language, but there must be some mechanism to process several files in a single run.
Non-letter, non-whitespace characters should be stripped from the input, this means that contractions will be coded without their apostrophe: "don't" --> "dont" --> 3668
Words are a sequence of letters separated surrounded by whitespace
All whitespace (space, tab, newline, beginning-of-file, end-of-file) is equivalent.
Input will be all lowercase or caps your preference.

Output

The output consists of a ASCII text stream
You may direct this to a file, the standard output, or any other conventional destination supported by your implementation language
The output should consist of one line for each string of digits corresponding to at least one word in the input.
Each line should consist of the digit string and a list of all corresponding words sorted by frequency with the most frequent coming first. A sample line of output would be

4663 good home gone hood hoof

Tokens (digit strings and corresponding words) should be separated by a single space.
Equally frequent words may be sorted in any order.

The winner is the shortest code.

Test Cases

potato, potato, damd, fjefje, djfaejri

Top 1000 words used.

The potato was a down goat goat down game gill pont pint point.

More actual test cases will be given in about a week to prevent any sort of hard-coding action.

Mathematica, 202 bytes
{g[#],##}~r~" "&@@@GatherBy[#&@@@SortBy[Tally@StringReplace[StringSplit@#,x_/;!LetterQ@x->""],-Last@#&],g=""<>ToString/@(\[LeftFloor]If[#<113,(#-91)/3,(#-88.2)/3.4]\[RightFloor]&/@ToCharacterCode@#)&]~(r=Riffle)~"
"<>""&

Note that \[LeftFloor] and \[RightFloor] are 3 bytes each.


Is the gas lighter than air? Air balloons need a gas that is lighter than air. However, hydrogen is flammable, while helium is not sustainable, so we need a replacement! You must write code that determines whether any given gas is lighter than air.

Input: a molecular chemical formula of a gas (ASCII)

Output: true if the gas is lighter than air; false otherwise (see here for consensus on what can be used as true and false).

If the chemical formula doesn't represent a gas (at standard conditions), or if it's a nonsense, any behavior is acceptable.

That is to say, you can assume the following:

The input is a valid chemical formula
The input is a molecular chemical formula: all element symbols are mentioned only once, and there are no parentheses
The chemical substance exists at normal conditions
The chemical substance is a gas at normal conditions

As a special case, H2O (water vapor) is considered a gas, because you can mix a significant quantity of it with air at standard conditions.

Whether or not a gas is lighter than air can be determined by calculating its molar mass:

Extract the chemical element symbols from the formula. Their atomic masses are given by the following table:

H - 1
He - 4
B - 11
C - 12
N - 14
O - 16
F - 19
Ne - 20
Others - greater values

Calculate the molar mass, which is the sum of all the atomic masses. If the molar mass is less than 29, the gas is lighter than air.

Test cases:

H2      true
He      true
B2H6    true
CH4     true
C2H2    true
C2H4    true
HCN     true
N2      true
NH3     true
H2O     true
CO      true
HF      true
Ne      true
O2      false
C2H6    false
C4H10   false
H2S     false
COH2    false
CO2     false
SiH4    false
NO      false
BN      behavior nor specified: not a gas
HBO2    behavior nor specified: not a gas
F2O     behavior nor specified: incorrect formula
CH3     behavior nor specified: incorrect formula
HCOOH   behavior nor specified: not a molecular formula
B(OH)3  behavior nor specified: not a molecular formula
XYZ     behavior nor specified: nonsense

(Note: this is meant to be an enumeration of all possible inputs that generate true. If I forgot some, I'll add it. In any case, Wikipedia is the answer for questions like "Does substance X exist?", "Is it a gas?")

A related (but different) question: calculate the molar mass

Retina, 108 104 bytes
[A-Z]
;$&
Ne
xF
F
xxxO
O
xxN
N
xxC
C
xB
B
11$*x
e
xxx
H
x
x(?=x*(\d+))
$1$*x
[A-Z]
30$*x
[^x]

M`x{29}
0

Try it online!
Test suite.


An optimization challenge with strange coins You have n coins which each weigh either -1  or 1. Each is labelled from 0 to n-1 so you can tell the coins apart.  You have one (magic) weighing device as well. At the first turn you can put as many coins as you like on the weighing device which is able to measure both negative and positive weights and it will tell you exactly how much they weigh.

However, there is something really strange about the weighing device.  If you put coins x_1, x_2, ..., x_j on the device the first time, then the next time you have to put coins (x_1+1), (x_2+1) , ..., (x_j+1) on the scale with the exception that you of course can't put on a coin numbered higher than n-1.   Not only that, for every new weighing you get to choose if you also want to put coin 0 on the scale.

  Under this rule, what is the smallest number of weighings that will always tell you
  exactly which coins weigh 1 and which weigh -1?

Clearly you could just put coin 0 on the device in the first turn and then it would take exactly n weighings to solve the problem.

Languages and libraries

You can use any language or library you like (that wasn't designed for this challenge). However, I would like to be able to test your code if possible so if you can provide clear instructions for how to run it in Ubuntu that would be very much appreciated.

Score

For a given n your score is n divided by the number of weighings you need in the worst case. Higher scores are therefore better.  There is no input to this puzzle but your goal is to find an n for which you can get the highest score.

If there is a tie, the first answer wins.  In the extremely unlikely situation where someone finds a way to get an infinite score, that person wins immediately.

Task

Your task is simply to write code that gets the highest score.  Your code will have to both choose an n cleverly and then also optimize the number of weighings for that n.

Leading entries

4/3 7/5 in Python by Sarge Borsch
26/14 in Java by Peter Taylor

Score = 26/14 ~= 1.857

import java.util.*;

public class LembikWeighingOptimisation {

    public static void main(String[] args) {
        float best = 0;
        int opt = 1;
        for (int n = 6; n < 32; n+=2) {
            long start = System.nanoTime();
            System.out.format("%d\t", n);
            opt = optimise(n, n / 2 + 1);
            float score = n / (float)opt;
            System.out.format("%d\t%f", opt, score);
            if (score > best) {
                best = score;
                System.out.print('*');
            }
            System.out.format(" in %d seconds", (System.nanoTime() - start) / 1000000000);
            System.out.println();
        }
    }

    private static int optimise(int numCoins, int minN) {
        MaskRange.N = numCoins;
        Set<MaskRange> coinSets = new HashSet<MaskRange>();
        coinSets.add(new MaskRange(0, 0));

        int allCoins = (1 << numCoins) - 1;

        for (int n = minN; n < numCoins; n++) {
            for (int startCoins = 1; startCoins * 2 <= numCoins; startCoins++) {
                for (int mask = (1 << startCoins) - 1; mask < (1 << numCoins); ) {
                    // Quick-reject: in n turns, do we cover the entire set?
                    int qr = (1 << (n-1)) - 1;
                    for (int j = 0; j < n; j++) qr |= mask << j;
                    if ((qr & allCoins) == allCoins && canDistinguishInNTurns(mask, coinSets, n)) {
                        System.out.print("[" + Integer.toBinaryString(mask) + "] ");
                        return n;
                    }

                    // Gosper's hack to update
                    int c = mask & -mask;
                    int r = mask + c;
                    mask = (((r^mask) >>> 2) / c) | r;
                }
            }
        }

        return numCoins;
    }

    private static boolean canDistinguishInNTurns(int mask, Set<MaskRange> coinsets, int n) {
        if (n < 0) throw new IllegalArgumentException("n");
        int count = 0;
        for (MaskRange mr : coinsets) count += mr.size();
        if (count <= 1) return true;
        if (n == 0) return false;

        // Partition.
        Set<MaskRange>[] p = new Set[Integer.bitCount(mask) + 1];
        for (int i = 0; i < p.length; i++) p[i] = new HashSet<MaskRange>();
        for (MaskRange range : coinsets) range.partition(mask, p);

        for (int d = 0; d < 2; d++) {
            boolean ok = true;
            for (Set<MaskRange> s : p) {
                if (!canDistinguishInNTurns((mask << 1) + d, s, n - 1)) {
                    ok = false;
                    break;
                }
            }

            if (ok) return true;
        }

        return false;
    }

    static class MaskRange {
        public static int N;
        public final int mask, value;

        public MaskRange(int mask, int value) {
            this.mask = mask;
            this.value = value & mask;
            if (this.value != value) throw new IllegalArgumentException();
        }

        public int size() {
            return 1 << (N - Integer.bitCount(mask));
        }

        public void partition(int otherMask, Set<MaskRange>[] p) {
            otherMask &= (1 << N) - 1;

            int baseline = Integer.bitCount(value & otherMask);
            int variables = otherMask & ~mask;
            int union = mask | otherMask;
            partitionInner(value, union, variables, baseline, p);
        }

        private static void partitionInner(int v, int m, int var, int baseline, Set<MaskRange>[] p) {
            if (var == 0) {
                p[baseline].add(new MaskRange(m, v));
            }
            else {
                int lowest = var & (1 + ~var);
                partitionInner(v,          m, var & ~lowest, baseline, p);
                partitionInner(v | lowest, m, var & ~lowest, baseline + 1, p);
            }
        }

        @Override
        public String toString() {
            return String.format("(x & %x = %x)", mask, value);
        }
    }
}

Save as LembikWeighingOptimisation.java, compile as javac LembikWeighingOptimisation.java, run as java LembikWeighingOptimisation.

Many thanks to Mitch Schwartz for pointing out a bug in the first version of the quick-reject.

This uses some fairly basic techniques which I can't rigorously justify. It brute-forces, but only for starting weighing operations which use at most half of the coins: sequences which use more than half of the coins aren't directly transferable to the complementary weighings (because we don't know the total weight), but on a hand-wavy level there should be about the same amount of information. It also iterates through starting weighings in order of the number of coins involved, on the basis that that way it covers dispersed weighings (which hopefully give information about the top end relatively early) without first crawling through a bunch which start with a dense subset at the bottom end.

The MaskRange class is a massive improvement on the earlier version in terms of memory usage, and removes GC from being a bottleneck.

20      [11101001010] 11        1.818182* in 5364 seconds
22      [110110101000] 12       1.833333* in 33116 seconds
24      [1000011001001] 13      1.846154* in 12181 seconds
26      [100101001100000] 14    1.857143* in 73890 seconds


Find the different letter You may have seen puzzles like this:

  Find the 0:
  OOOOOOOOOOOOOOOOOOOO0OOOOOOOOOOOOOOOOOO

The challenge is to write a program that finds the index of the different letter given an image.

Input

Input will be an Image. The image will consist of one line of black text in the Helvetica 24 pt. font on a white background. The text will consist from a selection of two characters: one character that is repeated, and one character that appears only once. For instance:

Output

Output will be an Integer, the index of the different character. In the example above, the output will be 4. (Note that indices of a string start at 0)

Program Specifications

As per usual for code golf, the shortest program wins.

Test Cases

 => 10
 => 11
 => 5
 => 16
 => 10
 => 21
 => 20
 => 13
 => 11
 => 4
 => 7

Dyalog APL, 31 32 bytes
{1⍳⍨+⌿∘.≡⍨{⍵/⍨~∧⌿⍵}¨⍵⊂⍨2>/∧⌿1,⍵}

⎕IO←0 to get indices starting with 0 (per OP), and which is anyway default in many APL systems.
1,⍵ prepend a column of white pixels (to ensure margin)
∧⌿ boolean for each column if all-white (vertical AND-reduction)
2>/ boolean at each character's left edge (pair-wise greater-than)
⍵⊂⍨ split into blocks beginning at each TRUE.
{…}¨ for each block
∧⌿⍵ boolean for each column if all-white (vertical AND-reduction)
⍵/⍨~ columns that are not [all-white]
∘.≡⍨ match each element to all elements
+⌿ number of blocks identical to each block (vertical plus-reduction)
1⍳⍨ index of first one (i.e. unique element)
Assumes the image is black (0) and white (1) pixels in the matrix I, and that there is at least one all-white pixel column between characters.
      f←{1⍳⍨+⌿∘.≡⍨{⍵/⍨~∧⌿⍵}¨⍵⊂⍨2>/∧⌿1,⍵}

"!I!!":
      ⊢I←6 12⍴(13/1),(22⍴0 1 1),(5/1),0,(8/1),(10⍴0 1 1),13/1
1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 0 1 1 0 1 1 0 1
1 0 1 1 0 1 1 0 1 1 0 1
1 1 1 1 0 1 1 1 1 1 1 1
1 0 1 1 0 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1
      f I
1

"mmnmm":
      ⊢I←7 31⍴(94/1),0 0,(∊0 1⌽¨2/⊂12⍴6↑1 0 1 1),0 1,(62⍴1 1 1,(⊢,⌽)(14⍴0 1)),33/1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
      f I
2


Generate keyboard shortcuts for a menu Menu Shortcuts

Traditionally, user menus are accessible by keyboard shortcuts, such as Alt + (a letter), or even simply hitting the letter when all textboxes are unfocused (gmail style).

Your task

Given the menu entries as an input, your task is to grant each menu entry a proper shortcut letter.

Write a function or a program that accepts a set of words - the menu entries (as an array of strings, or your language equivalent), and returns a dictionary, or a hashmap, from a single letter to a menu entry.

You can either use a parameter and return a value, or use the STDIN and output your results to STDOUT. You are not allowed to assume a global/scope variable is already populated with the input.

Algorithm to determine the proper letter

Basically it's the first available letter of the word. See assumptions and examples below.
In case all entry's letters are not available, the shortcut will be (a letter) + (a number). Which letter you pick from the entry is arbitrary. The number should start from 0 and be incremented by 1 - such that all shortcuts are unique. See third example below.

Assumptions

The input will be a Set, i.e. no repetitions, every entry is unique.
Length of the input can be any non-negative integer (up to MAX_INT of your language).
Case sensitivity: Input is case-sensitive, (but will stay unique when ignoring case). The results should contain the original entries with their original casing. However, the output shortcut letters are not case-sensitive.
All input words will not end with numbers.
No "evil input" will be tested. "Evil input" is such that you have to increment the counter of a certain letter more than 10 times.

Examples

Examples below are in JSON, but you can use your language equivalent for an array and a Dictionary, or - in case you're using STD I/O - any readable format for your input and output (such as csv, or even space-separated values).

1.

Input:  ['File', 'Edit', 'View', 'Help']
Output: {f:'File', e:'Edit', v:'View', h:'Help'}

2.

Input:  ['Foo', 'Bar', 'FooBar', 'FooBars']
Output: {f:'Foo', b:'Bar', o:'FooBar', a:'FooBars'}

3.

Input:  ['a', 'b', 'aa', 'bb', 'bbq', 'bbb', 'ba']
Output: {a:'a', b:'b', a0:'aa', b0:'bb', q:'bbq', b1:'bbb', b2:'ba'}

Winning conditions

Shortest code wins. Only ASCII is allowed.

Javascript (ES6) 106 105 100
This function takes input as an an array and outputs a javascript object.
f=i=>i.map(a=>{for(b of c=a.toLowerCase(d=0)+d+123456789)d<!o[e=b>=0?c[0]+b:b]&&(o[d=e]=a)},o={})&&o

Results:
f(['File', 'Edit', 'View', 'Help']);
// {"f":"File","e":"Edit","v":"View","h":"Help"}

f(['Foo', 'Bar', 'FooBar', 'FooBars']);
// {"f":"Foo","b":"Bar","o":"FooBar","a":"FooBars"}

f(['a', 'b', 'aa', 'bb', 'bbq', 'bbb', 'ba']);
// {"a":"a","b":"b","a0":"aa","b0":"bb","q":"bbq","b1":"bbb","b2":"ba"}

Ungolfed / Commented:
f=i=>{
  o={};                                        // initialize an object for output
  i.map(a=>                                    // loop through all values in input
    for(b of c=a.toLowerCase(d=0)+d+123456789) // loop through all characters of the string with 0123456789 appended to the end
                                               // and initialize d as 0 to be used as a flag
      e=b>=0?c[0]+b:b                          // if b is a number, set e to the first character + the number, otherwise b
      if(d<!o[e])                              // if the flag hasn't been triggered and o doesn't have a property e
        o[d=e]=a                               // then store the value at e and trigger the d flag
  )
  return o                                     // return the output object
}


Almost Equilaterial Heronian Triangles An Almost Equilateral Heronian Triangle is a triangle with integer lengths of the form n-1, n, and n+1 and also has integer area. The first few are:

 3,  4,  5 ->    6
13, 14, 15 ->   84
51, 52, 53 -> 1170

Quest: Generate the shortest program that outputs the nth such triple. (Hint: this is a known sequence).

Winner will be selected on May 2, 2014.


Beatles Songs and Hexagons Write two triangle (i.e. pyramid) shaped programs.
The first one should be an upwards pointing text triangle with a minimum base width of three characters. So it would have a structure like
 X
XXX

or
  X
 XXX
XXXXX

or
   X
  XXX
 XXXXX
XXXXXXX

or larger. Each of the X's is to be replaced with the characters of your actual code, which may be anything except line terminators (so the X's could be spaces). All the X's must be replaced and the spaces and newlines that help form the triangle shape are required to stay as is.
The second program must have the same size and shape as the first, except that the triangle will be pointing down.
So if your first program looks like
  X
 XXX
XXXXX

then your second program would look like
yyyyy
 yyy
  y

where each y is a character you need to fill in with your actual code (probably different from your X code). The spaces and newlines must stay the same here too.
Your task is to write these programs such that they each output (to stdout or closest alternative) the title of a distinct Beatles song, not taking any input. This Wikipedia article will serve as our official song list for The Beatles. The output should be one of the titles exactly as listed, e.g. I Want You (She's So Heavy).
This is pretty easy, however, even with the weird triangle program requirement. So we're going to form another program from the first two that must output yet another song title.
By combining three copies of each of the two triangular programs we can create a third program shaped like a hexagon.
If the base width of your first program was three it would look like this:
 XyyyX
XXXyXXX
yyyXyyy
 yXXXy

If the base width was five it would look like this:
  XyyyyyX
 XXXyyyXXX
XXXXXyXXXXX
yyyyyXyyyyy
 yyyXXXyyy
  yXXXXXy

This program (when run with the spaces and newlines like the others) must output another Beatles song title, just like the first two programs. Also:

Your three programs must output different song titles.
Only song titles eight characters in length or longer are allowed.
You can only choose one of Revolution, Revolution 1 and Revolution 9 because the titles are so similar.
You must choose your three favorite Beatles songs. (Well, try to.)

Note that actual programs are required. Functions are not allowed. Reading your own source code in any program is also not allowed.
Example
If your first program was
  A
 AAA
AAAAA

it could output Across the Universe.
Then your second program
bbbbb
 bbb
  b

could output Revolution.
Then combined into the hexagon program
  AbbbbbA
 AAAbbbAAA
AAAAAbAAAAA
bbbbbAbbbbb
 bbbAAAbbb
  bAAAAAb

the output might be Get Back.
Scoring
The submission with the smallest triangle base width wins. In the likely case of ties the submission with the largest summed length of its three song titles wins.

Befunge-93, width = 13 15, titles = 31 24 chars

A power outage last night prevented me from updating this when I figured it out, but I managed to reduce the triangle width and increase the song lengths!

Pointing-up program: "Dig a Pony", 10 characters:

      v
     v>
    v#  >
   "<
  v <>"y"v>
 <v"Dig a P"
"^>:#,_@.>"no

Explanation

I REALLY took advantage of Befunge's wrap-around trick and I picked "Dig a Pony" specifically because it had a space at the 6th position. This allows program flow to move through the song name. Try it in the online interpreter to see how it works.

Pointing-down program: "If I Fell", 9 characters:

< v"f I Fell"
 v>"I">:#,_@
  "raC yM "
   v"Drive

       .

(Period is extraneous and only included to make the other lines show up.)

Explanation

The only relevant lines here are the first two. I used the wrap-around trick (the instruction pointer is sent left immediately) to squeeze in one more character. The second line prints out the song name.

Combined: "Drive My Car", 12 characters:

      v< v"f I Fell"v
     v> v>"I">:#,_@v>
    v#  >"raC yM "v#  >
   "<     v"Drive"<
  v <>"y"v>     v <>"y"v>
 <v"Dig a P"   <v"Dig a P"
"^>:#,_@.>"no "^>:#,_@.>"no
< v"f I Fell"v< v"f I Fell"
 v>"I">:#,_@v> v>"I">:#,_@
  "raC yM "v#  >"raC yM "
   v"Drive"<     v"Drive
         v <>"y"v>
        <v"Dig a P"
       "^>:#,_@.>"no

Here's the same thing, but with lines added to show the hexagon and triangles.

       -----------------
      /v\< v"f I Fell"/v\
     /v> \v>"I">:#,_@/v> \
    /v#  >\"raC yM "/v#  >\
   /"<     \v"Drive/"<     \
  /v <>"y"v>\     /v <>"y"v>\
 /<v"Dig a P"\   /<v"Dig a P"\
/"^>:#,_@.>"no\ /"^>:#,_@.>"no\
-------------------------------
\< v"f I Fell"/v\< v"f I Fell"/
 \v>"I">:#,_@/v> \v>"I">:#,_@/
  \"raC yM "/v#  >\"raC yM "/
   \v"Drive/"<     \v"Drive/
    \     /v <>"y"v>\     /
     \   /<v"Dig a P"\   /
      \ /"^>:#,_@.>"no\ /
       -----------------

Explanation

This is where the third and fourth lines of the pointing-down triangle come into play. There are several redirects at the edge of both triangles that serve to move the instruction pointer through those two lines and push "Drive My Car" onto the stack. Then it is printed out using the >:#,_@ bit in the pointing-up triangle. Incidentally, both the left and the right pointing-up triangles are used.

There might be a way to use more of the empty space, but I think my time is better spent on other questions. :P


Congruence Relations Given 3 positive integers a, b, and n (whose maximum values are the maximum representable integer value in your language), output a truthy value if a ≡ b (mod n), and falsey otherwise. For those unfamiliar with congruency relations, a ≡ b (mod n) is true iff a mod n = b mod n (or, equivalently, (a - b) mod n = 0).
Restrictions

Built-in congruence testing methods are forbidden
Built-in modulo operations are forbidden (this includes operations such as Python's divmod function, which return both the quotient and the remainder, as well as divisibility functions, residue system functions, and the like)

Test Cases
(1, 2, 3) -> False
(2, 4, 2) -> True
(3, 9, 10) -> False
(25, 45, 20) -> True
(4, 5, 1) -> True
(83, 73, 59) -> False
(70, 79, 29) -> False
(16, 44, 86) -> False
(28, 78, 5) -> True
(73, 31, 14) -> True
(9, 9, 88) -> True
(20, 7, 82) -> False

This is code-golf, so shortest code (in bytes) wins, with earliest submission as a tiebreaker.

Jelly, 5 bytes

_ÆD⁵e

Making heavy use of Anything else that is not forbidden is allowed.

Try it online!

How it works

_ÆD⁵e  Main link. Left input: a. Right input: b. Additional input: n

_      Subtract b from a.
 ÆD    Compute all divisors of the difference.
   ⁵e  Test if n is among the divisors.


Gaussian integer division reminder Gaussian integer is a complex number in the form \$x+yi\$, where \$x,y\$ are integer and \$i^2=-1\$.
The task is to perform such operation for Gaussian integers \$a,b\$, that
\$a=q \cdot b+r\$ and \$|r|<|b|\$ (\$q,r\$ are Gaussian integers, \$|z|\$ is defined as \$\sqrt{a^2+b^2}\$ for \$a+bi=z\$).
Need to output only \$r\$.
One of possible approaches is here.

Scoring: the fastest in terms of O-notations algorithm wins, though it can consume more time. By fastest I mean \$O(\left(f(n)\right)^a)\$ is preferred for smaller \$a\$ and \$O(\log^a(\log(n)))\$ will be preferred over \$O(\log^b(n))\$, ...over \$O(n^k)\$, ...over \$O(e^{\alpha n})\$ and so on.
If there's a tie, fastest implementation wins in terms of benchmark (e.g. 100 000 random 32-bit \$b\$ and 64-bit \$a\$ (I mean both real and imaginary part to be 32 or 64 signed integer)) or there can be 2-3 winners.
If unsure about algorithm complexity, leave blank. E.g. I believe Euler's algorithm for integers has \$O(\log(n))\$ time complexity.

Test cases can be obtained from wolframalpha in the form like Mod[151 + 62 I, 2 + I], but in case there are some:

4 mod (3+3*i) = either of 1+3*i, -2-0*i, 4-0*i, 1-3*i
10000 mod 30*i = either 10 or -20
(3140462541696034439-9109410646169016036*i) mod (-81008166-205207311*i) =
    either -75816304-29775984*i or 129391007+51232182*i

\$|b|\$ will not exceed 32 bits, but you don't have to code long arithmetic if your selected language doesn't have built-in one.

Good luck. Of course, WolframLanguage is forbidden. )

Python 2 (PyPy), O(1) operations

def cmod(a1, a2, b1, b2):
	# Compute p = a * conj(b)
	p1 =   a1 * b1 + a2 * b2
	p2 = - a1 * b2 + a2 * b1

	# Compute the norm-squared of b
	b_nsq = b1 ** 2 + b2 ** 2
	b_nsq_half = b_nsq // 2

	# Do a symmetric mod of d1 and d2 by b_nsq
	# That is, into the interval [-b_nsq_half, +b_nsq_half)
	d1 = (p1 + b_nsq_half) % b_nsq - b_nsq_half
	d2 = (p2 + b_nsq_half) % b_nsq - b_nsq_half

	# Compute r = d / b
	r1 = (d1 * b1 - d2 * b2) // b_nsq
	r2 = (d1 * b2 + d2 * b1) // b_nsq

	return r1, r2

Try it online!

Uses pure integer arithmetic, with no loops or branching or built-in complex numbers. This should easily complete the benchmark of 100,000 random inputs within a small fraction of a second. Porting this to a faster language would be straightforward and likely improve performance.

One possible low-level optimization is the Karatsuba algorithm trick to do complex multiplication using 3 rather than 4 integer multiplications. But, this might not be worth it for such "small" values.


Output the Juggler sequence The Juggler sequence is described as follows. Beginning with an input \$a_1\$, the next term is defined by the recurrence relation
$$a_{k+1} = \begin{cases}
\left\lfloor a_k ^ \frac 1 2 \right\rfloor,\text{ if } a_k \text{ is even} \\
\left\lfloor a_k ^ \frac 3 2 \right\rfloor,\text{ if } a_k \text{ is odd} \\
\end{cases}$$
The sequence terminates when it reaches 1, as all subsequent terms would then be 1.
Task
Given an input \$n\$ greater than or equal to 2, write a program/function/generator/etc. that outputs/returns the respective juggler sequence. The output can be in any reasonable form. You may not use a built-in that computes the juggler sequence, or any built-in that directly yields the result. You may assume that the sequence terminates in \$1\$.
Test Cases
Input: output
2: 2, 1
3: 3, 5, 11, 36, 6, 2, 1
4: 4, 2, 1
5: 5, 11, 36, 6, 2, 1

This is a code golf. Shortest code in bytes wins.

Julia, 64 50 48 42 32 30 bytes

g(x)=[x;x<3||g(x^(x%2+.5)÷1)]

This is a recursive function that accepts an integer and returns a float array.

We build an array by concatenating the input with the next term of the sequence, computed as x to the power of its parity plus 1/2. This gives us either x1/2 or x1+1/2 = x3/2. Integer division by 1 gets the floor. When the condition x < 3 is true, the final element will be a Boolean rather than a numeric value, but since the array is not of type Any, this is cast to have the same type as the rest of the array.

Saved 14 bytes thanks to Dennis!


Programs that move around in memory It's time for some quines! Well, sort of. This challenge is to create the smallest program that could move around in memory, i.e. if a program is resident in 2000:0100, the program should move to say, memory address be7a:3470.

 Rules

The memory address to move in should be pseudorandom.
It's still valid if it's a moving file around in the hard drive.
If it jumps around the RAM it should go to another segment in RAM.

I call these programs transposons, after the genes that move all around the DNA of an organism. Happy golfing! Contest ends May 9, 2014.

Bash, 2 bytes
$0

Moves itself to a new memory address when it is assigned a new process.
To move to a different spot on the harddrive it takes a few more:
cat $0>x


Warhol these pictures We've all seen the famous painting of Marilyn Monroe created by Andy Warhol.

Let's try to replicate that effect with the usual suspects.

Your task is to write a program/programs that do as many as possible of the following tasks:

With one image as the input, generate four color palettes from that image and print a 4x4 grid with different "Warhol'd" color variants of that image.
With two images as input, generate two color palettes from each image and print a Warhol'd grid of the first image.
With four images as input, generate one color palette from each image and print a Warhol'd grid of the first image.

Of course, it would be cheating to hardcode palettes you like the best, so your program has to determine a set of colors that is both distinct and aesthetically pleasing. Warhol used five distinct colors in each panel, so five is your goal as well.

Here are some photos that you could use to showcase your program:

Try to achieve a wide range of palette colorings and of course make them as aesthetically pleasing as possible.

This is a popularity contest, so the answer with the most net votes wins.

(Formatting largely copied from Paint by Numbers, which was a partial inspiration for this challenge as was American Gothic in the palette of Mona Lisa: Rearrange the pixels)

Mathematica

namedColors = {Red, Green, Blue, Black, White, Gray, Cyan, Magenta, Yellow, Brown, Orange, Pink, Purple};
    myRules =
      Table[Rule[namedColors[[i]], RandomChoice[namedColors]], {j, 4}, {i,
         Length[namedColors]}];

myImages = {--images here--};

Grid@Table[ColorQuantize[ColorReplace[myImages[[i]], myRules[[j]]],5],
{i, Length[myImages]}, {j, 4}]


Make an almost quine I wanted to fool a friend by giving him a quine that almost worked, but became sloppier and sloppier.

Create a program that, when run, will output the program, but one character off. Either one character can be added, removed or both (one character changes). But only one character.

Your score will be (length of your program) / floor(sqrt(number of times the program almost quines)) (Where / 0 is infinity)

number of times the program almost quines is how many times your program runs while only changing one character in stdout. Your program may not accept input. It may also not print a program it has already printed.

You may also not add a character that you have previously added before, or remove a character from the same index. For example, if you have added 1 before, and you add 1 again, that's where the number of times the program almost quines stops. If you remove the first character, you may not remove the first character again. If you changed the third character into a 2, you may not add a 2 or remove the third character.

CJam, 0.000884

{_,6/[{64md}6*](124+\+'�f++`"1$~"}""1$~

Here, � denotes the unprintable character with code point 128. Try it online.

Idea

This approach appends all UCS characters (original specification) with code points between U+4000000 and U+7FFFFFFF to the initially empty string that follows the code block.

We choose UTF-8, which encodes each of these characters using a 6 byte string as follows:

1111110u₂     10vvvvvv₂     10wwwwww₂     10xxxxxx₂     10yyyyyy₂     10zzzzzz₂

252 + u       128 + vvvvvv  128 + wwwwww  128 + xxxxxx  128 + yyyyyy  128 + zzzzzz

Thus, we can encode the nth character in this range by computing its 6 least significant digits in base 64 and adding 252 to the most significant and 128 to the remaining ones.

Scoring

There are 2 ** 31 = 2,147,483,648 6 byte UTF-8 characters and the length of the original code is 39, so the score is 39 / floor(2 ** 15.5) = 39 / 46340 = 0.0008416055243849806.

How it works

{                                }""    e# Push the code block and an empty string.
                                    1$~ e# Execute a copy of the code block.
 _,                                     e# Push the length of the string.
   6/                                   e# Divide by 6 to get the number of chars.
      {64md}6*                          e# Perform modular division six times.
     [        ]                         e# Collect the results in an array.
               (124+\+                  e# Add 124 to the first element.
                      '�f+              e# Add 128 to all and cast each to Char.
                          +             e# Concatenate the strings.
                           `            e# Push a string representation.
                            "1$~"       e# Push '1$~' to complete the quine.


Bring ASCII art to the 3rd dimension In this challenge, You have to bring ASCII art (which are usually 2D) to 3D!

How?

like this,

X X DD
 X  D D
X X DD

to...

  X X DD
 X X DD D
X X DDDD
 X XDDD
X X DD

Then How do we do that?

Given the ascii art and N, repeat this N times.

for every character (we will call this A):
let B be the character which is exactly 1 right and 1 up from A
if B is a space or is undefined:
set B to A.

Specs

The first input can be a string with newline characters or a list of strings representing the 2D ASCII art.
You are allowed to use %END% to tag the end of input, but this is not required.
The second input will be N. It will be a positive integer.
all the lines of the strings will be the same length.

Examples

Input: ("###\n###",1)

Output:

 ###
####
###

Rules

Basic code-golf rules apply.

also, If you have questions, be sure to ask in the comments!

Perl, 81 bytes

75 bytes code + 6 for -i -n0.
Note that the \e characters are ASCII \x1b but \e is used for ease of testing.

Please note that this solution uses ANSI escape sequences and requires a compatible terminal, as well as using the -i commandline argument to pass in the number of 'dimensions' you'd like.

$n=s/^//mg-1;s/ /\e[1C/g;print(s/^/\e[${^I}C/grm."\e[${n}A"),--$^I for($_)x$^I

Usage:

In a Linux compatible terminal, run PS1= first to ensure your prompt doesn't overwrite the displayed image.

perl -i10 -n0e '$n=s/^//mg-1;s/ /\e[1C/g;print(s/^/\e[${^I}C/grm."\e[${n}A"),--$^I for($_)x$^I' <<< '
ROFL:ROFL:ROFL:ROFL
         _^___
 L    __/   [] \
LOL===__        \
 L      \________]
         I   I
        --------/
'

          ROFL:ROFL:ROFL:ROFL
         ROFL:ROFL:ROFL:ROFL
        ROFL:ROFL:ROFL:ROFL
       ROFL:ROFL:ROFL:ROFL\
      ROFL:ROFL:ROFL:ROFL\_]
     ROFL:ROFL:ROFL:ROFL\_]
    ROFL:ROFL:ROFL:ROFL\_]/
   ROFL:ROFL:ROFL:ROFL\_]/
  ROFL:ROFL:ROFL:ROFL\_]/
 ROFL:ROFL:ROFL:ROFL\_]/
   LOL==___^___]_\_\_]/
  LOL==__/ \_[]_\_\_]/
 LOL===__ \______\_]/
  L      \________]/
          I---I---/
         --------/

perl -i3 -n0e '$n=s/^//mg-1;s/ /\e[1C/g;print(s/^/\e[${^I}C/grm."\e[${n}A"),--$^I for($_)x$^I' <<< 'X X DD
 X  D D
X X DD
'
   X X DD
  X X DD D
 X X DDDD
  X XDDD
 X X DD


GolfScript - The missing function The GolfScript language has one serious lack, no float or fixed point handling. Remedy this by creating a function F for converting an integer number, given as a string, to a string representing 1 / 10 000 000 000 of it's value. The function must handle both positive and negative values as well as leading 0s.

The following pretty-print rules apply:

No trailing 0s.
No . if the result is integer.
No leading 0s, except for numbers with no integer part, they should have 1 leading 0.
The result must be output as a single string.

Examples:

123 -> 0.0000000123
-00 -> 0
012345678901234567890 -> 1234567890.123456789
-123 -> -0.0000000123
10000000000001 -> 1000.0000000001
123000000000000 -> 12300

The competition is only between GolfScript submissions using no Ruby functionality. Solutions in other languages may be posted, but they are not eligible for winning, these may not use any fixed or float point functionality that the language offers, and must accept arbitrarily large inputs.

55 chars

{~.0<"-"*\abs 10.?..3$@%+`-1%~`)[3-]1$,!!*+-1%@@/\++}:F

Negative numbers are a bit of a pain - responsible for about 13 chars of the 55. Trailing 0s are handled by using a 1 to stand for the decimal point, reversing as a string, converting to an int, and back again, and re-reversing.


Different combinations possible Problem

Given a value n, imagine a mountain landscape inscribed in a reference (0, 0) to (2n, 0).
There musn't be white spaces between slopes and also the mountain musn't descend below the x axis.
The problem to be solved is: given n (which defines the size of the landscape) and the number k of peaks
(k always less than or equal to n), how many combinations of mountains are possible with k peaks?

Input

n who represents the width of the landscape and k which is the number of peaks.

Output

Just the number of combinations possible.

Example

Given n=3 and k=2 the answer is 3 combinations.

Just to give a visual example, they are the following:

   /\     /\      /\/\
/\/  \   /  \/\  /    \

are the 3 combinations possible using 6 (3*2) positions and 2 peaks.

Edit:
 - more examples -

n  k  result
2  1  1
4  1  1
4  3  6
5  2  10

Winning condition

Standard code-golf rules apply. The shortest submission in bytes wins.

Python, 40 bytes

f=lambda n,k:k<2or~-n*n*f(n-1,k-1)/~-k/k

Try it online!

Uses the recurrence \$a_{n,1} = 1\$, \$a_{n,k} = \frac{n(n-1)}{k(k-1)}a_{n-1,k-1}\$.


Golfing Flower of Life The challenge here is to accurately depict the flower of life (which is a sacred geometrical figure according to some) in the language of your choice.

The design consists an arrangement of circles and partial circles of radius 1 as shown whose centres arranged on a triangular grid of pitch 1, plus one larger circle of radius 3 surrounding them.

The design can be scaled as you like, but a max error of 2% from mathematically correct is permitted. If using raster graphics, this effectively limits the diameter of the small circles to at least about 100 pixels.

Since this is code-golf, shortest code (bytes) wins.

Mathematica, 177 173 128 124 120 bytes

c=Circle;Graphics@{{0,0}~c~3,Rotate[Table[If[-3<x-y<4,c[{√3x,-x+2y}/2,1,Pi/{6,2}]],{x,-3,2},{y,-4,2}],Pi/3#]&~Array~6}

The main idea is to compose the result from six rotated versions of this:

This in turn is a rectangular table of identical circle arcs with two corners cut off. If we remove the shearing and represent each circle center with a #, we basically want to distribute the circles in this pattern:

####
#####
######
######
 #####
  ####

These edges are cut off by imposing the condition -3 < x-y < 4 on the 2D indices (since the value of x-y is constant along diagonals) and the shearing comes from multiplying these x and y by non-orthogonal basis vectors which span the grid we're looking for.

This particular orientation of the unrotated arcs turns out to be the shortest since both ends of the arc evenly divide Pi so that the arc can be expressed as Pi/{6,2} (all other arcs would either require and additional minus sign or integers in the numerator).


Is it Valid Modified UTF-8? UTF-8 is a relatively simple way to encode Unicode codepoints in a variable-width format such that it doesn't easily confuse code that isn't Unicode aware.

UTF-8 overview

Bytes in the range of 1-0x7F, inclusive, are normally valid
Bytes with the bit pattern 10XX XXXX are considered continuation bytes, with the six least significant bits being used to encode part of a codepoint. These must not appear unless they are expected by a preceding byte.
Bytes with the pattern 110X XXXX expect one continuation byte afterward
Bytes with the pattern 1110 XXXX expect two continuation bytes afterward
Bytes with the pattern 1111 0XXX expect three continuation bytes afterward
All other bytes are invalid and should not appear anywhere in a UTF-8 stream. 5, 6, and 7 byte clusters are possible in theory, but will not be allowed for the purposes of this challenge.

Overlong encodings

UTF-8 also requires that a codepoint should be represented with the minimum number of bytes. Any byte sequence that could be represented with fewer bytes is not valid. Modified UTF-8 adds one exception to this for null characters (U+0000), which should be represented as C0 80 (hex representation)), and instead disallows null bytes to appear anywhere in the stream. (This makes it compatible with null-terminated strings)

Challenge

You are to make a program that, when given a string of bytes, will determine if that string represents valid Modified UTF-8 and will return a truthy value if valid and a falsy value otherwise. Note that you must check for overlong encodings and null bytes (since this is Modified UTF-8). You do not need to decode the UTF-8 values.

Examples

41 42 43  ==> yes (all bytes are in the 0-0x7F range)
00 01 02  ==> no (there is a null byte in the stream)
80 7F 41  ==> no (there is a continuation byte without a starter byte)
D9 84 10  ==> yes (the correct number of continuation bytes follow a starter byte)
F0 81 82 41  ==> no (there are not enough continuation bytes after F0)
EF 8A A7 91  ==> no (too many continuation bytes)
E1 E1 01  ==> no (starter byte where a continuation byte is expected)
E0 80 87  ==> no (overlong encoding)
41 C0 80  ==> yes (null byte encoded with the only legal overlong encoding)
F8 42 43  ==> no (invalid byte 'F8')

Rules

Standard rules and loopholes apply
Input and output can be in any convenient format as long as all values in the unsigned byte range (0-255) can be read in.

You may need to use an array or file rather than a null-terminated string. You need to be able to read null bytes.

Shortest code wins!
Note that using builtins to decode the UTF-8 is not guaranteed to conform to the requirements given here. You may need to work around it and create special cases.

EDIT: added bonus for not using builtins that decode UTF-8

EDIT2: removed bonus since only the Rust answer qualified and it's awkward to define.

Elixir, 69 bytes

import String
&valid? replace replace(&1,<<0>>,"\xFF"),"\xC0\x80","0"

Try it online!

Makes use of built-in string validation function. Takes input as Elixir binary.


I ain't no Fortunate sum The primorial \$p_n\#\$ is the product of the first \$n\$ primes. The sequence begins \$2, 6, 30, 210, 2310\$.
A Fortunate number, \$F_n\$, is the smallest integer \$m > 1\$ such that \$p_n\# + m\$ is prime. For example \$F_7 = 19\$ as:
$$p_7\# = 2\times3\times5\times7\times11\times13\times17 = 510510$$
Adding each number between \$2\$ and \$18\$ to \$510510\$ all yield composite numbers. However, \$510510 + 19 = 510529\$ which is prime.
The Fortunate numbers below \$200\$ are
$$3, 5, 7, 13, 17, 19, 23, 37, 47, 59, 61, 67, 71, 79, 89, 101, 103, 107, 109, 127, 151, 157, 163, 167, 191, 197, 199$$
We'll say an integer \$n\$ is a "Fortunate sum" if it can be expressed as the sum of two distinct Fortunate numbers. For example, \$22 = 3 + 19 = 5 + 17\$, so \$22\$ can be expressed as the sum of two Fortunate numbers, and so is a "Fortunate sum"
You are to take an integer \$n\$ as input and output a truthy value if \$n\$ is a Fortunate sum and a falsey value otherwise. You may swap the order (falsey indicates it is a Fortunate sum) if you wish. You may take input and output in any convenient format.
This is code-golf so the shortest code in bytes wins
Test cases
The first line is the Fortunate sums less than 100 (truthy values) and the second are the integers less than or equal to 100 that aren't Fortunate sums
8 10 12 16 18 20 22 24 26 28 30 32 36 40 42 44 50 52 54 56 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98
1 2 3 4 5 6 7 9 11 13 14 15 17 19 21 23 25 27 29 31 33 34 35 37 38 39 41 43 45 46 47 48 49 51 53 55 57 58 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 100

Haskell, 130 128 bytes

a n=or[f x&&f(n-x)|x<-[2..n],2*x<n]
f m=or[and[p(x+y)/=(y<m)|y<-[2..m]]|x<-scanl1(*)$filter p[2..m]]
p n=all((>0).mod n)[2..n-1]

Try it online!
This solution is based on the following observation.
Fact. An integer \$m>1\$ is Fortunate if and only if, for some prime number \$p_n<m\$, \$m\$ is the smallest integer \$>1\$ such that
\$
p_1 p_2\cdots p_n+m
\$
is prime.
Proof. The claim follows easily from the fact that if \$p_n\ge m\$ then there is some \$p_i\$ with \$i\le n\$ such that \$p_i\mid m\$, and therefore \$p_i\mid p_1 p_2\cdots p_n+m\$.
At this point, checking if a number \$m\$ is Fortunate is trivial: we just have to check the condition for all the prime numbers up to \$m\$.
Explanation of the code
p n=all((>0).mod n)[2..n-1]

The standard prime-checking function. Only works for n>1, but that's ok.

f m=or[and[p(x+y)/=(y<m)|y<-[2..m]]|x<-scanl1(*)$filter p[2..m]]

A function to check whether a number m is Fortunate. As explained above, it calculates the primorials \$\texttt{x}=p_1p_2\cdots p_n\$ until \$p_n\le\texttt{m}\$ and tests whether m is the smallest integer \$\texttt{y}>1\$ such that \$\texttt{x}+\texttt{y}\$ is prime.

a n=or[f x&&f(n-x)|x<-[2..n],2*x<n]

The final function, to check whether n is a Fortunate sum. Pretty straightforward, the only thing to be careful of is that x and n-x must be different: this is the reason why we only iterate over values of x such that 2*x<n.


Best free online resources to learn competitive programming I am quite proficient in C++ and Java and want to learn competitive programming to participate in contests like Google codejam and other online contests held on sites like CodeChef and Codeforces. I would like to get information about any free resources including websites and courses to learn the "sport". Book suggestions are also welcome.

Please suggest some courses which have some practical work included and not just flat theory. I want to work on my problem solving skills rather than just learning algorithms and data structures.

Practice Algorithmic Thinking

If there's one thing I believe programmers need to master, it's the process of dissecting a problem statement and planning their approach.

By this, I mean having the ability to approach an unseen challenge and think about what is being asked.

If I were you, I'd look at challenges posted around this website, ranging from trivial to difficult, and take the time to plan how you would solve the problem. That way, you'll be able to have a hands on experience with problem solving.

Once you do this enough, start placing time restrictions on your thinking time. Because I know from personal experience that competitive programming is most often timed. Once you have got that nailed, you should be ready for competitions.

In summary: practice. Y'all need to walk before y'all can run. I hope to see you as an active contributor around here!


Is this number a factorial? The Task
Given a natural number as input, your task is to output a truthy or falsey value based on whether the input is a factorial of any natural number. You can assume that the input number will always be in the range of numbers supported by your language, but you must not abuse native number types to trivialize the problem.
Standard Loopholes apply.

Input
You'll be given a natural number (of type Integer or similar).
You can take input in any way you want except assuming it to be in a predefined variable. Reading from file, console, dialog box (prompt), input box etc. is allowed. Input as function argument is allowed as well!

Output
Your program should output a truthy or falsey value based on whether the input number is a factorial of any natural number.
Make sure that your truthy/falsey values are consistent for all inputs, i.e, if you are using pair of 1 and 0 to denote truthy and falsey values respectively, then your program must output 1 for all inputs that should have truthy values and 0 for all inputs that should have falsey values.
You can take output in any way you want except writing it to a variable. Writing to file, console, screen etc. is allowed. Function return is allowed as well!
Your program must not produce errors for any input!

Test Cases
Input     Output

1         Truthy (0! or 1!)
2         Truthy (2!)
3         Falsey
4         Falsey
5         Falsey
6         Truthy (3!)
7         Falsey
8         Falsey
24        Truthy (4!)
120       Truthy (5!)

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

Brachylog, 1 byte
ḟ

Try it online!
Explanation
ḟ is a built-in that asserts the following relation: its  output is the factorial of its input. We simply give it a set output and see whether it suceeds or not with a variable input.


Swaps needed to sort an array in bubble sort method Write shortest code that detect how many swaps (minimum) are needed to sort (in increasing order) any array of unique positive integers. It should be fast enough to detect number of swaps in array of 1'000'000 integers in decreasing order in 1-2 minutes.

Refs

Bubble Sort on Wiki
Example implementations of bubble sort

Score

[time elapsed]s/60s * [length of code]

Python - 262 chars * 45 / 60 = 196.5

Edit: much faster sorting algorithm.

First it will sort all the items in the list by what hundred they are in (0, 100, 200, etc), in a list in m (note: I count these as 1 step each, so a list of 1,000,000 items will automatically have 1,000,000 steps initially)

Then it will sort the lists within m using the bubble sorting function c

This is greatly sped up from using c on the original list to be sorted, because the amount of time it takes to sort 1000 items is small (~0.04 seconds), but exponentially increases the larger the list gets (~45 seconds at 10,000 items). But if you sort 100 lists of 100 items, it only takes .4 seconds, to sort, more than 100 times faster than sorting 1 list of 10,000 items. It should therefor take 4 seconds to sort 100,000 items, and 40 seconds to finally sort 1,000,000

In actuality, it took 45 seconds to sort the reversed 1,000,000 item list this way, and results in 50,500,000 steps:

python bubblesortcount.py
50500000
44.6600000858

This functon works with the given case (reverse ordered list), as well as any random case. No negative integers, though.

r=range
def b(l):
 m=[[]for i in r(len(l)//100+1)];t=[];o=0
 for e in l:m[e//100].append(e);o+=1
 for e in m:x=c(e);t+=x[0];o+=x[1]
 return t,o
def c(l):
 s=0
 for p in r(len(l)-1,0,-1):
  for i in r(p):
   if l[i]>l[i+1]:l[i],l[i+1]=l[i+1],l[i];s+=1
 return l,s

test:

import random,time
a=time.time()
d=b(range(1000000)[::-1]) #reversed list
#d=b(random.sample(range(1000000),1000000)) #scrambled list
z=(time.time()-a)
#print d[0] # comment to not print a gigantic list
print d[1] # number of steps
print z # time it took

Edit: by changing the amount the helper function sorts by to 100, I reduced the average time it takes to sort the list to 45 seconds. also reduces character count by 2

edit again: you know what? maybe what I'm doing isn't valid. I can change the amount the helper function sorts by to just 1 and it will sort a million items in 5 seconds.. is this valid?


Round the digits last digit, over and over Challenge:

Given two inputs, x and y, round x to one less significant figure, then repeat until it has y number of unrounded digits left. (the decimal point does not count as a digit)

Input & Output

Input can be a combination of strings and integers, e.g. you can have the input as a string and the output as an int, or vice versa.
The input number will never have 15 digits total, and the y will never be greater  than the input number's length and will always be greater than 0.
Example:

x = 32.64712, y = 3
    32.64712 -> 32.6471 -> 32.647 -> 32.65 -> 32.7  (Three unrounded digits left)

x = 87525, y = 2
    87525 -> 87530 -> 87500 -> 88000 (Two unrounded digits left)

x = 454, y = 3
    454 -> 454 (Three unrounded digits left)

(steps shown just to clarify, you only need to output the last value.)

Rules

Trailing 0's are allowed
5's round up
Standard loopholes apply

This is code-golf, so you should strive for the shortest answer.

Python 2, 101 97 92 91 85 bytes

lambda x,y:reduce((lambda n,l:int(n/.1**l+.5)*.1**l),range(15,y+~len(`int(x)`),-1),x)

Try it online!

Alternative :
If Python's round would round "half up" instead of "half to even":

Python 2, 57 bytes

lambda x,y:reduce(round,range(15,y-len(`int(x)`)-1,-1),x)

Try it online!


Is it a prefix code? In information theory, a "prefix code" is a dictionary where none of the keys are a prefix of another. In other words, this means that none of the strings starts with any of the other.

For example, {"9", "55"} is a prefix code, but {"5", "9", "55"} is not.

The biggest advantage of this, is that the encoded text can be written down with no separator between them, and it will still be uniquely decipherable. This shows up in compression algorithms such as Huffman coding, which always generates the optimal prefix code.

Your task is simple: Given a list of strings, determine whether or not it is a valid prefix code.

Your input:

Will be a list of strings in any reasonable format.
Will only contain printable ASCII strings.
Will not contain any empty strings.

Your output will be a truthy/falsey value: Truthy if it's a valid prefix code, and falsey if it isn't.

Here are some true test cases:

["Hello", "World"]
["Code", "Golf", "Is", "Cool"]
["1", "2", "3", "4", "5"]
["This", "test", "case", "is", "true"]

["111", "010", "000", "1101", "1010", "1000", "0111", "0010", "1011",
 "0110", "11001", "00110", "10011", "11000", "00111", "10010"]

Here are some false test cases:

["4", "42"]
["1", "2", "3", "34"]
["This", "test", "case", "is", "false", "t"]
["He", "said", "Hello"]
["0", "00", "00001"]
["Duplicate", "Duplicate", "Keys", "Keys"]

This is code-golf, so standard loopholes apply, and shortest answer in bytes wins.

Pyth, 8 bytes

.AxM.PQ2

Test suite

Take all 2 element permutations of the input, map each to the index of one string in the other (0 for a prefix) and return whether all results are truthy (non-zero).


Solve the knapsack problem Knapsack Problem

(Actually, this is a subset of real knapsack problem.... - there's nothing to optimize!)

The knapsack problem is:

  Given positive integers , and an integer S, find non-negative integers  satisfies

... or in (my bad) English...

  Suppose you have many stuffs which weights , find configurations of those stuffs which weights S.

Problem

  Find all configurations of stuffs, which information is given by input.

Input

You can make your own format, but you should enable users to input the sum of stuffs(S), weights of stuffs , and names of each stuffs.

Stuffs' name may contain [a-zA-Z0-9 _] (alphanumeric + _ + space).

You may assume that the input is correct,  are positive, and S is non-negative.

For example, consider this pseudo-real world situation, where a man orders appetizers worth exactly $15.05:

A possible input is:

1505
215 Mixed fruit
275 French fries
335 Side salad
355 Hot wings
420 Mozzarella sticks
580 Sampler plate

Output

Print all possible configurations (no same configurations, one configuration per one line, each line contains pairs of amount of a stuff and name of the stuff).

Stuff with zero amount can be omitted.

If there's no configuration possible, simply print X.

Example

Input and output format (and order) can be vary.

This is JS code I made roughly:

var s=prompt(),a=s.split('/'),b=[],c,i=1,t=a[0];while(i<a.length){c=a[i].split(/^([^ ]*) /);c.shift();b.push(c);i++;}
var d=[],l=b.length,p=0,_=0;for(i=0;i<l;i++)d[i]=0;
function as(x,y){for(var i=0,s=0;i<x.length;i++)s+=x[i][0]*y[i];return s}
function cs(x,y){for(var i=0,s='';i<x.length;i++)s+=y[i]+' '+x[i][1]+', ';return s}
while(p>=0){
    p=0;
    while((q=as(b,d))>=t){
        if(q==t){console.log(cs(b,d));_=1}
        d[p]=0;p++;if(p>=l){p=-1;break;}
        d[p]++;
    }
    if(p==0) d[0]++;
}
if(!_) console.log('X');

Input

1505/215 Mixed fruit/275 French fries/335 Side salad/355 Hot wings/420 Mozzarella sticks/580 Sampler plate

Output

7 Mixed fruit, 0 French fries, 0 Side salad, 0 Hot wings, 0 Mozzarella sticks, 0 Sampler plate,
1 Mixed fruit, 0 French fries, 0 Side salad, 2 Hot wings, 0 Mozzarella sticks, 1 Sampler plate,

Input

5/1 A/1 B/1 C

Output

5 A, 0 B, 0 C,
4 A, 1 B, 0 C,
3 A, 2 B, 0 C,
2 A, 3 B, 0 C,
1 A, 4 B, 0 C,
0 A, 5 B, 0 C,
4 A, 0 B, 1 C,
3 A, 1 B, 1 C,
2 A, 2 B, 1 C,
1 A, 3 B, 1 C,
0 A, 4 B, 1 C,
3 A, 0 B, 2 C,
2 A, 1 B, 2 C,
1 A, 2 B, 2 C,
0 A, 3 B, 2 C,
2 A, 0 B, 3 C,
1 A, 1 B, 3 C,
0 A, 2 B, 3 C,
1 A, 0 B, 4 C,
0 A, 1 B, 4 C,
0 A, 0 B, 5 C,

Input

10/20 A/11 B

Output

X

Input

250/35 Portal 2/21 Minecraft/12 Braid

Output

5 Portal 2, 3 Minecraft, 1 Braid,
2 Portal 2, 8 Minecraft, 1 Braid,
2 Portal 2, 4 Minecraft, 8 Braid,
2 Portal 2, 0 Minecraft, 15 Braid,

Input

250/33 Portal 2/21 Minecraft/12 Braid

Output

X

Winner

Since this is the code golf game, person with shortest code win.

If two codes have same length, then a code with highest votes win.


Convert pointfree to pointful Being a Haskell hacker, I prefer pointfree notation over pointful. Unfortunately some people find pointfree notation hard to read, and I find it hard to get the correct number of parentheses when I write in pointful.
Help me convert code written in pointfree to pointful notation!

About

In pointfree notation we use points (yes, really) to feed the output of one function into another. Say, if you had a function succ that takes a number and adds 1 to it, and you wanted to make a function that adds 3 to a number, instead of doing this:

\x -> succ(succ(succ(x)))

you could do this:

succ.succ.succ

Pointfree only works with functions that take a single parameter however (in this challenge anyway), so if our function wasn't succ but rather add which take 2 numbers and adds them together, we would have to feed it arguments until there is only one left:

pointful:  \x -> add 1(add 1(add 1 x))
pointfree: add 1 . add 1 . add 1

Lastly, functions may take other functions as arguments:

Pointfree: map (f a . f b) . id
Pointful:  \x -> map (\x -> f a (f b x)) (id x)

Javascript equivalent: x => map (x => f(a,f(b,x)), id(x))

Input and expected output

f . f . f
\x -> f (f (f x))

f a . f b . f c
\x -> f a (f b (f c x))

f (f a . f b) . f c
\x -> f (\x -> f a (f b x)) (f c x)

a b c . d e . f g h i . j k l . m
\x -> a b c (d e (f g h i (j k l (m x))))

a.b(c.d)e.f g(h)(i j.k).l(m(n.o).p)
\x->a(b(\y->c(d y))e(f g h(\z->i j(k z))(l(\q->m(\w->n(o w))(p q))x)))

Rules

Your output may have more spaces or parentheses than required, as long as they are balanced
You don't have to make sure that the name of the variable you create \x isn't already used somewhere else in the code
It is your choice whether to create a function or a full program
This is codegolf, shortest code in bytes win!

You might find blunt useful, it converts between the two notations (but also factorizes the code when possible): https://blunt.herokuapp.com


Shortest code to throw IllegalArgumentException in Java Okey, we all know the normal way to throw a IllegalArgumentException in Java:

throw new IllegalArgumentException(); // 37 characters

But there must be a shorter (as in less characters) ways to do so.
How can we produce a java.lang.IllegalArgumentException with even less code?

The code fragment has to compile and run in java 7.
No imports/external packages (e.g. not using java.util.Arrays.toString() )

only exception: java.lang because it is automatically imported.

You can add own
methods/classes.
It must throw a java.lang.IllegalArgumentException

Edit: the error output (stacktrace) must name it java.lang.IllegalArgumentException, so no subclasses of it.

To have a base to start from:

class Titled {
    public static void main(String[] args) {
        throw new IllegalArgumentException();
    }
}

These were all found by grepping the source code in the package java.lang.

All of them result in a "pure" IllegalArgumentException (i.e. not a subclass of it).

The ones marked * only work if you add " throws Exception" (18 characters) to your main declaration, as they throw a checked exception of some kind.

12 (30?) characters*

"".wait(-1);

This will result in:

java.lang.IllegalArgumentException: timeout value is negative

22 (40?) characters*

new Thread().join(-1);

22 characters

Character.toChars(-1);

30 characters

Character.UnicodeBlock.of(-1);


Hey, what time is it? Challenge

Given a number width, number height, hours and minutes print the time using the following format style:

------  -  ------  ------  -    -  ------  ------  ------  ------  ------
|    |  |       |       |  |    |  |       |            |  |    |  |    |
|    |  |  ------  ------  ------  ------  ------       |  ------  ------
|    |  |  |            |       |       |  |    |       |  |    |       |
|    |  |  |            |       |       |  |    |       |  |    |       |
------  -  ------  ------       -  ------  ------       -  ------  ------

For numbers with a mid line, when the height is odd just place it in the middle (example for height = 3):

------
|    |
------
|    |
------

However, when the height is even you can choose up or down:

------  ------
|    |  |    |
|    |  ------
------  |    |
|    |  |    |
------  ------

Of course, you need to specify this and use it every time.

Input

W: The width of each number
H: The height of each number
HRS: Time hours
MINS: Time minutes

Output

You can either print the time, return a string (including the newlines) or return a list of strings (one string per line).

Rules

Assume number width > 2
Assume number height > 2
The space between numbers is fixed to 2
The space between hours and minutes is fixed to 4
If hours or minutes are < 10 (single digit), make sure to add a 0 (see example)
Assume that input hours and minutes will always be valid time
Digit 1 is a special case which always has the same width 1 and only it's height changes.
Height is considered the inner height, excluding the upper and lower rows of --- (see example)

Example

Here's an example for W=6, H=4, hrs=2, mins=18:

------  ------    -  ------
|    |       |    |  |    |
|    |  ------    |  ------
|    |  |         |  |    |
|    |  |         |  |    |
------  ------    -  ------


Five aligned points and some of the pairwise distances. Infer the relative positions! Given five points on a straight line such that their pairwise distances are 1,2,4, ..., 14,18,20 (after ordering), find the respective positions of the five points (relative to the furthest point on the left).

R

prop <- function(num_points, first_distances, last_distances)
{
    last_point = max(last_distances)
    proposal = c(0, sort(sample(1:(last_point-1), num_points-2)), last_point)
    d = sort(dist(proposal))
    num_first_distances = length(first_distances)
    num_last_distances = length(last_distances)
    num_distances = length(d)
    if(all(d[1:num_first_distances]==first_distances)&&all(d[(num_distances-num_last_distances+1):num_distances]==last_distances))
    {
        print(proposal)
        return(TRUE)
    }
    else return(FALSE)
}

while(TRUE)
{
    if(prop(5, c(1,2,4), c(14,18,20))) break()
}

Here is the source of the problem and an algorithm with R which I used for inspiration.


Missile-mounted cameras You are employed as Administrator in charge of Road Maintenance and Planning. The intelligence division  of the Agency for Road Maintenance and Planning has come up with a brilliant and not at all inefficient way to take random sample pictures of the roads: missiles with cameras on them.

In this genius and not at all wasteful technique, smart non-explosive missiles are sent hurtling down each road. Each missile moves in a straight line and captures images at equal spatial intervals. Eventually the Agency will get a good overall sample of the state of affairs for each road. On Masagaki Road, for example, images are captured at positions 1, 4, 5, 6, 8, 11, 12 and 14:

1 X X 4 5 6 X 8 X X 11 12 X 14 (X represents no image)

Your job is to find the largest number of images that could have been captured by the camera on a single missile. A single camera could have captured the three images at positions 4, 5, 6 (having a spacing of 1); the three images at positions 4, 6, 8 (spacing 2); or the three images at 4, 8, 12 (spacing 4). However, here the answer is four: positions 5, 8, 11, 14 (spacing 3).

Input: a sequence of \$1\leq n\leq1000\$ unique integers, each satisfying \$1\leq i\leq1000000\$, representing the positions of the images captured for a certain road. These will be given from smallest to largest.

Output: a single integer representing the largest number of images that could have been captured by a single camera.

Sample 1

Input: 1 4 5 6 8 11 12 14

Output: 4

Sample 2

Input: 5 8 9 10 12 15 16 17

Output: 3

code-golf; the shortest code in bytes wins.
The linked rules apply.
Please explain your code.
Please link to Try It Online! or another online demo.

Inspired by 'Air Drop' (AIO 2007, Senior)

Python 2, 74 bytes

lambda l:max(reduce(lambda i,x:i+(a+i*(b-a)==x),l,0)for a in l for b in l)

Try it online!

Tries every possible sequence of the form a,b,... with a and b in the input l.

To find the smallest index i of this arithmetic progression that's outside l, we do something a bit unusual. Instead of counting up the progression to find an element not in l, we iterate over l, taking advantage of it being sorted. For each successive element x of l, we move to the next index in the arithmetic progression if its current value matches x, and stay at the current index otherwise.


Simple Circular Words A "simple circular" word is a word whose chords do not intersect.  The chords of a word may be seen by laying out the alphabet in a circle, and then connecting the word's consecutive letters.

Examples of Simple Circular Words

ROLE

LAKE

BALMY

Failing Example

A word fails to be simple circular if any of its chords intersect:

The Challenge

Write a program or function that takes a word and returns true if it's simple circular, false otherwise.

Code golf, fewest bytes wins.
Standard rules.
You may assume there are no repeated letters in the word.
You may assume every word has at least 2 letters
You may assume the word is all uppercase, or all lowercase, whichever you prefer.
You may output any two consistent values for true and false.

Test Cases

True

ROLE, LAKE, BALMY, AEBDC, ABZCYDXE, AZL, ZA

False

BONES, ACDB, ALBZ, EGDF

Perl 6, 46 bytes

{!/[(.).*]**4<?{[+^] $0 Xeq[...] ~<<$0[^2]}>/}

Try it online!
A regex solution that finds if there are four characters in the string such that the two later characters are in different sections of the circle, as defined by the first two characters.
Explanation
{                                           }   # Anonymous code block returning
 !/                                        /    # If the input does not match
   [(.).*]**4                                     # Any 4 characters
             <?{                          }       # Where
                           [...]                    # The range from
                                 ~<<$0[^2]          # The first character to the second
                        Xeq                         # Contains which of
                     $0                             # The four characters
                [+^]                                # Reduce the list of booleans by xor
                 # Effectively, if only one of the 3rd or 4th character is in that range


Transpose a word cloud Background

I wanted to make a pretty word cloud, like this:

these    are
    words

  floating

I computed the (x,y)-coordinates of the first letter of each word, plugged them into my word cloud generator, and let it do its job.
However, I accidentally used (y,x)-coordinates, so the result looks like this:

these

   floating

 words

are

Since I'm too lazy to re-compute the coordinates, I need you to transpose the word cloud for me.

Input

Your input is a rectangular grid of lowercase ASCII letters and spaces.
This means that every row is padded with spaces to have the same length.
The input can be taken as a multi-line string or an array of strings.

A word is a horizontal segment of letters, and its position is the (x,y)-coordinates of its leftmost letter, the upper left corner of the grid being (0,0).
There will always be at least one word, and there are no trailing rows or columns of spaces.
However, leading rows or columns of spaces may be present.

Output

Your output is another rectangular grid of characters, obtained by moving every word with position (x,y) to position (y,x).
Your output must not contain extra trailing rows or columns of spaces.
Leading rows and columns must be preserved, and the output must be rectangular.

You may assume that this transformation does not create overlapping words, and does not merge several words into one.
This means that running the program on the output should produce the original input.

Rules and scoring

You can write a full program or a function.
The lowest byte count wins, and standard loopholes are disallowed.

Test cases

For clarity (and since Stack Exchange dislikes space-only lines), every row ends in a pipe character |.
These are not part of the actual input or output, and you should remove them.
Note again that running the program on each output should also produce the corresponding input.

Input:
oneword|
Output:
oneword|

Input:
  spaces|
Output:
      |
      |
spaces|

Input:
   |
row|
Output:
 row|

Input:
these    are|
    words   |
            |
  floating  |
Output:
these      |
           |
   floating|
           |
 words     |
           |
           |
           |
are        |

Input:
   same|
 the   |
       |
same   |
Output:
   same|
 the   |
       |
same   |

Input:
  some |
words k|
       |
       |
       |
  still|
Output:
 words    |
          |
some still|
          |
          |
          |
 k        |

Input:
   hello   |
  world hey|
what   up  |
Output:
  what|
      |
 world|
hello |
      |
      |
      |
  up  |
 hey  |

Input:
  a b  a d cc|
 g h  huh nng|
  ye dunnn   |
    dud  yo  |
 wha   g     |
  huh heh hah|
Output:
        |
 g  wha |
a ye huh|
 h      |
b  dud  |
  dunnn |
 huh heh|
a   g   |
        |
d  yo   |
 nng hah|
cc      |

Perl, 58 bytes

Added +2 for -lp

Give input on STDIN, run as perl -lp wordcloud.pl

wordcloud.pl:

s/\w+/$l|=$a[pos]|=$"x~-$..$&/eg}for(@a){$_|=$l=~y// /cr