I need a program where the user inputs an array of doubles and the program outputs the array sorted Note: This question was severely edited since I first posted it here. The rules were moved to here, read them before posting any answer to understand the purpose of this. This was the first question created in the code-trolling category.

Imagine a lazy user on Stack Overflow asks this question:

  I need a program where the user inputs an array of doubles and the program outputs the array sorted. Could you please give the code?

How could you create a piece of code that will troll this user? Create a piece of code that will appear useful to an inexperienced programmer but is utterly useless in practice.

The winner is the most upvoted answer, except if the answer is somehow not eligible (for eligibility requirements, check the tag wiki description of code-trolling). If the previously most upvoted answer is beaten in the future in the number of upvotes after being accepted, the new best answer is accepted and the previous one is unaccepted. In the case of a tie, I will choose the winner at will among the tied ones or just wait a bit more.

Answers that have no code are not eligible. They might be fun and get some upvotes, but they won't be accepted.

Rules can be found at tag description.

Note: This is a code-trolling question. Please do not take the question and/or answers seriously. More information here.

Here it is in java. It is utter cheating, unacceptable and unfixable because it creates a MySQL database, insert the number there, do a select with an ORDER BY clause and outputs the numbers given by MySQL. In fact, it is MySQL who is doing the sorting, not the program.

package sorter;

import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.PreparedStatement;
import java.sql.ResultSet;
import java.util.ArrayList;
import java.util.List;
import javax.swing.JOptionPane;

public class SortingAlgorithm {

    private static final String CREATE_DB = "CREATE DATABASE sorting";
    private static final String DROP_DB = "DROP DATABASE sorting";
    private static final String CREATE_TABLE = "CREATE TABLE sorting.sorting ( num double not null )";

    public static void main(String[] args) throws Exception {
        Class.forName("com.mysql.jdbc.Driver");
        List<Double> doubles = new ArrayList<>(50);
        String typed;
        do {
            typed = JOptionPane.showInputDialog(null, "Type a double:");
            if (typed != null) doubles.add(Double.parseDouble(typed));
        } while (typed != null);

        List<Double> sorted = new ArrayList<>(50);

        try (Connection con = DriverManager.getConnection("jdbc:mysql://localhost:3306", "root", "root")) {
            try (PreparedStatement ps = con.prepareStatement(CREATE_DB)) {
                ps.executeUpdate();
            }
            try (PreparedStatement ps = con.prepareStatement(CREATE_TABLE)) {
                ps.executeUpdate();
            }

            for (Double d : doubles) {
                try (PreparedStatement ps = con.prepareStatement("INSERT INTO sorting.sorting (num) VALUES (" + d + ")")) {
                    ps.executeUpdate();
                }
            }

            try (
                    PreparedStatement ps = con.prepareStatement("SELECT * FROM sorting.sorting ORDER BY num");
                    ResultSet rs = ps.executeQuery())
            {
                while (rs.next()) {
                    sorted.add(rs.getDouble("num"));
                }
            }
            try (PreparedStatement ps = con.prepareStatement(DROP_DB)) {
                ps.executeUpdate();
            }
        }

        JOptionPane.showMessageDialog(null, "The array sorted is: " + sorted);
    }
}


Does this Set Represent a Natural Number? In set theory, the natural numbers \$\mathbb{N} = \{0, 1, 2, 3, ...\}\$ are usually encoded as pure sets, that is sets which only contain the empty set or other sets that are pure. However, not all pure sets represent natural numbers. This challenge is about deciding whether a given pure set represents an encoding of natural number or not.
The encoding of natural numbers works in the following way1:

Zero is the empty set: \$ \text{Set}(0) = \{\} \$
For a number \$n > 0\$: \$ \text{Set}(n) = \text{Set}(n-1) \cup \{\text{Set}(n-1)\}\$

Thus, the encodings of the first few natural numbers are

\$ 0 \leadsto \{\}\$
\$ 1 \leadsto \{0\} \leadsto \{\{\}\}\$
\$ 2 \leadsto \{0,1\} \leadsto \{\{\},\{\{\}\}\}\$
\$ 3 \leadsto \{0,1,2\} \leadsto \{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}\$
\$ 4 \leadsto \{0,1,2,3\} \leadsto \{\{\},\{\{\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}\}\$

The Task

Given a string representing a pure set, determine whether this set encodes a natural number according to the above construction.
Note, however, that the elements of a set are not ordered, so \$\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}\$ is not the only valid representation of \$3\$ as e.g. \$\{\{\{\}\},\{\},\{\{\{\}\},\{\}\}\}\$ represents the same set.
You may use [], () or <> instead of {}.
You may assume the sets are given without the , as separator.
You can assume there won't be any duplicate elements in the input, e.g. {{},{}} is not a valid input, and that the input is well-formed, e.g. no {{},, {,{}} or similar.

Test Cases
True:
{}
{{}}
{{},{{}}}
{{{}},{}}
{{},{{}},{{},{{}}}}
{{{},{{}}},{},{{}}}
{{{{}},{}},{{}},{}}
{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}
{{{{{}},{}},{{}},{}},{{}},{},{{},{{}}}}
{{},{{}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}},{{{}},{}},{{},{{}},{{},{{}}}}}
{{{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}}

False:
{{{}}}
{{{{}}}}
{{{{}},{}}}
{{},{{}},{{{}}}}
{{{},{{}}},{{}}}
{{{{{}}},{}},{{}},{}}
{{},{{}},{{},{{}}},{{},{{}},{{{}}}}}
{{{{{}},{}},{{{}}},{}},{{}},{},{{},{{}}}}
{{{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}}

Related: Natural Construction (Output the set encoding of a given natural number.)
1 See https://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers

JavaScript (Node.js), 53 48 44 bytes

f=a=>(a=eval(a)).every(e=>a[e.length]&&f(e))

Try it online! Test cases mostly shamelessly stolen from @Arnauld's answer. Explanation: If a set represents a natural number, then the natural number it represents must be equal to the size of the set, and (given that the elements are guaranteed distinct) the elements must be the representations of the natural numbers less than it, and these must therefore have shorter lengths. This is trivially true of the empty set of course. Edit: Saved 5 bytes thanks to @Arnauld. Saved 4 bytes thanks to @Cowsquack.


Transpose a page of text EDIT I modified the wording of the rules to make some things which were implicit more explicit. I also added some emphasis to clear up some points of apparent confusion, and explicitly defined the option of making a standalone program instead of a function.

The goal here is to make a function that takes a text file (or string) and transposes it so that lines become columns and vice versa.

Example:

I am a text.
Transpose me.
Can you do it?

Results in:

ITC
 ra
aan
mn
 sy
apo
 ou
ts
eed
x o
tm
.ei
 .t
  ?

The rules:

You are allowed to assume that the only whitespace characters used are " " and "\n" and that there is no trailing whitespace on any line.
You may assume that the file is ASCII. Which endline marker you want to use is up to you.(CRLF or LF). It must work correctly on the example, but it should also work on any input that satisfies the above assumptions.
You might have to insert spaces (as in the example) where there were none in order to keep the columns in line.
Your result must not have trailing whitespace on any line.
The final newline character(for the last line) is optional.
It should be either a function or a complete program. If your function accepts a string, then it should return the results as a string. If it accepts a filename, then you return the name of the file where you saved the result. You are additionally allowed to write a complete program that accepts input from STDIN and outputs the correct result to STDOUT; if you do this, you must not output anything to STDERR.
Shortest procedure wins, but I will upvote any answer I like.

Based on the rules, the output on the example is either 53 or 52 bytes long (for LF newlines) depending on whether the final newline is included or not.

Note: It is not a specific requirement, but if your function, when run twice successively is not identical to the original(the final newline might be differ, and any empty lines at the end of the file will be deleted), then you are probably breaking one of the rules.

J (31 40)

f=:3 :';(,&LF@dlb&.|.)&.><"1|:>LF cut y'

This is a function that takes a string, and returns a string (i.e. a character vector with linefeeds inserted in the right places, and not a matrix.)

Edit: no trailing whitespace on any line.

Test:

   f=:3 :';(,&LF@dlb&.|.)&.><"1|:>LF cut y'

   string=:stdin''
I am a text.
Transpose me.
Can you do it?
^D

   $string
42
   $f string
53
   f string
ITC
 ra
aan
mn
 sy
apo
 ou
ts
eed
x o
tm
.ei
 .t
  ?


Constructing an evil maze against random exploration RollerCoaster Tycoon 2's maze is the inspiration for this question. Credit to Marcel Vos for thoroughly breaking the classic RCT2 AI. The pathfinding AI in this question is the AI in the latest version of OpenRCT2 at the time of writing, which was updated in response to that video.

Suppose a guest enters a \$w \times h\$ grid maze with the following strategy in mind:

After every step I pick a random valid direction except backwards, unless I have no other choice but to go back.

We are evil and wish to construct the maze that takes the most amount of time on average to solve using the above strategy.

This is a code-challenge. The winner is the answer that contains a \$100 \times 100\$ maze with the greatest mean solve time using the above strategy. In the case of a tie the earlier poster wins.
A \$w \times h\$ maze is a \$w \times h\$ grid of square tiles. It has two designated start tiles along the border, connected either horizontally or vertically, and similarly two designated exit squares, along the border, connected either horizontally or vertically.
Between each tile there may or may not be a wall (with the exception of the two start and two end tiles, they must be directly connected to their partner). There is always a border of walls around the grid.
The guest enters with a 50/50% chance on either start tile, facing away from the other tile. Then the guest starts exploring the maze one step at a time. At the start of a step the guest looks to its left, forward and right (relative to its current direction) and checks for walls. It chooses a random new direction with uniform chance from the unobstructed directions. If and only if all other directions are obstructed it chooses to go backwards instead.
The guest wanders around as such until it reaches one of the two exit squares, which will cause the guest to immediately exit. The average number of steps it takes for this to happen is your score, the bigger the better. If the start and exit are not connected your maze is invalid and has no score.

To accurately score mazes I wrote a judge program in Python that uses Markov chains to compute your score mathematically. It requires Python 3, numpy, scipy and imageio to run (an optional dependency for a speedup is scikit-umfpack). In addition, the judge contains functions to output an image of your maze, as well as a compressed representation of your maze. Please familiarize yourself with the judge program before starting this challenge.
Please include (a link to) a \$100\times 100\$ compressed maze as generated by the judge program in your answer. Your answer will be scored based on this. An answer without a concrete, specific solution maze is invalid.

No dead ends near the entrance, 21,477,560 21,485,005
Try it online!
Yay, 21 million. The giant horizontal segments up to row 19 are also removed, so about 20% of the entire grid is just an open space.
Also, as the "real maze" starts at the leftmost column, moving the entrance to the top right gives a slight bump to the score. (Thanks to @Neil)

Previous version, 20,211,703
Try it online!
Yes, 20 million. It's actually good to remove some dead ends and add some open spaces near the entrance, but it stops being good as it gets sufficiently far away from it.
This is a derivation from width-3 dead end maze by removing some h-walls (it's called h-walls in the code, but it is a vertical segment in the image):

The h-walls from row 1 to row 22 (inclusive) are entirely removed.
The h-walls from row 23 to row 40 (inclusive) are reduced by half, keeping the odd indices.


Execute a Superb Shuffle™ For the purposes of this question, a deck of cards is formatted in this way:

[
  "AS", "2S", "3S", "4S", "5S", "6S", "7S", "8S", "9S", "10S", "JS", "QS", "KS",
  "AD", "2D", "3D", "4D", "5D", "6D", "7D", "8D", "9D", "10D", "JD", "QD", "KD",
  "AH", "2H", "3H", "4H", "5H", "6H", "7H", "8H", "9H", "10H", "JH", "QH", "KH",
  "AC", "2C", "3C", "4C", "5C", "6C", "7C", "8C", "9C", "10C", "JC", "QC", "KC",
  "J", "J"
]

Cards are always formatted as value, followed by suits. E.g. AS is the Ace of Spades. The two single J's are Jokers. We want to shuffle this deck of cards, but the shuffle must be Superb™.

A Superb Shuffle™ is one in which:

No two cards (except Jokers) of the same suit are adjacent.
No card (except Jokers) is adjacent to one of the same value.
No card (except Jokers) is adjacent to one of an adjacent value (one higher or one lower in this order, A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A. Notice that Ace can not be adjacent to either a 2 or a King).
The Jokers can be in any position.
The definition of a Superb Shuffle™ does not require the cards to be in a different order each time they are shuffled. Which isn't very superb, but it is Superb™.

Because that's Superb™.

An example might be:

[
  "AS", "5D", "9H", "KC", "2D", "6H", "10C", "QS", "3H", "7C", "9S",
  "KD", "4C", "6S", "10D", "AC", "3S", "7D", "JH", "J", "4D", "8H",
  "QC", "AD", "5H", "9C", "JS", "2H", "6C", "8S", "QD", "3C", "5S",
  "9D", "KH", "2S", "6D", "10H", "J", "3D", "7H", "JC", "KS", "4H",
  "8C", "10S", "AH", "5C", "7S", "JD", "2C", "4S", "8D", "QH"
]

The challenge:

Write some code to execute a superb shuffle
Use any language.
The input can be either:

a deck of cards as described above in the same order, as an array or other list structure.
No input (the code generates a deck of cards in that order)

The output must be a full deck of cards in a Superb Shuffle™ as described above.
Attempt to perform your Superb Shuffle™ in the smallest number of bytes.
A link to an online interpreter such as Try It Online is preferred, but optional.

Happy shuffling!

Ruby, 31 bytes

->x{(0..53).map{|r|x[r*17%54]}}

Try it online!
Explanation:
I'm picking one card, then skipping over the next 16 and start from the first card when I reach the last card of the deck. 17 and 54 are mutually prime, so I'm sure to pick all cards.
The 17th position is guaranteed to be a different suit and the difference in value is at least 2: the 13th (or 15th) card has the same value and a different suit, so by skipping other 4 (or 2), the value is right.


Implement the EnScript CHS command JonoCode9374 had almost completely implemented my language EnScript except for the CHS command. I was impatient of waiting for them to implement this command, so I chose to put this question here.
Challenge:
Write a solution that takes an input and returns the chased output. Standard loopholes are forbidden.
This is the CHS instruction reference copied from the website:

CHS means to chase all of the numbers inside an accumulator.
Chasing a number means to move a number forward inside the accumulator that-number of times.

Chasing an accumulator means to move all of the numbers inside an accumulator from the lowest number (0) to the highest number (9) sequentially, without repeating. Sequentially means: the values are moved in a sequential order that was presented in the accumulator, which is from left to right.

Here is an important note: The number is still there while the number is moved, and that number will be removed from the original number if and only if the currently chased number has been put in place.

Here is an extra note: A number with the lower magnitude should be "chased" first in the accumulator. For example, the number 1 should be chased prior to the numbers 2, 3, 4, etc.

One more note: Accumulators should be unbounded, i.e. without an upper limit. Also, they cannot and should not support negative numbers. The implementation does not have to detect that; it can assume that the input is valid.

The type of the accumulators should be in the unbounded integer form; The value of an accumulator should not be a floating-point integer.

If zeroes are in front of the number at the end of the process, they are deleted by default.

Examples:

Take A=123 as an example.
Value 1 will move forward 1 number. (It will be inserted behind 2.) So, the number will be 213. 1 will be marked as chased.
Likewise, 2 will also be moved. It will be moved forward twice, so the number will be 132.
3 will also be chased. It will move forward 1 time (finding that the end of the list is reached), and then it will go to the place before 1. Then, it will go back to where it was.
Accumulator A "chased" will be 132.

Also, take 3112 as an example, which is quite vague. Some people may ask: which '1' gets "chased" first?
Answer: The first '1' from left to right gets "chased" first. See the notes from above.
So, the chase after 1 iteration will be:
31121324→31131224
Another example. 10 will be chased to 01, as 0 cannot be moved and 1 will be moved for 1 digit. Then, this preceding 0 will be deleted, leaving a 1 to the accumulators.
Test Cases:
123 -> 132
12345 -> 14253
3141 -> 3141
123123 -> 312132
94634 -> 96434
1277 -> 7172
10 -> 1

Please comment for me if this question is too vague!

Python 3, 262 ... 170 bytes
This program outputs the result via Stderr.
I'm a bit out of practice at golfing, since I have not been too active lately, so I'm sure it can be golfed more.

L=[[c,int(c)]for c in input()]
while 1:i=L.index(min([x for x in L if x[1]]or exit(str(int("".join(x[0]for x in L))))));L[i][1]-=1;q=i+1<len(L)and-~i;L.insert(q,L.pop(i))

Try it online
Ungolfed
# Index to shift, Times remaining
def Shift(i, t):
    if t<1:
        L[i][1]=0
        return
    if i+1<len(L):
        L[i],L[i+1]=L[i+1],L[i]
        Shift(i+1,t-1)
    else:
        L.insert(0,L.pop())
        Shift(0,t-1)
L=[[c,1]for c in input()]
while 1:
    t=[x for x in L if x[1]]or exit("".join(x[0]for x in L).lstrip('0'))
    i=L.index(min(t,key=lambda x:x[0]))
    Shift(i,int(L[i][0]))


Passwordify the string Your challenge is to passwordify the string! What is passwordifying, you ask?

Take a string as input. This string will only contain uppercase letters, lowercase letters, digits, and spaces.

You must replace all spaces with underscores and move all numbers to the end of the string in the order that they appear from left to right. Then, for every letter in the string, randomly change it to uppercase or lowercase.

Examples (case of characters should vary every time):

Input
Hello world
Output
HElLo_wORld

Input
pa55 w0rd
Output
pA_Wrd550

Input
14 35
Output
_1435

Input
0971
Output
0971

Input
[space]
Output
_

Shortest code in bytes wins!

Whoever asks on Information Security SE if this is a good hashing algorithm wins!--Don't worry SE overlords, I'm just kidding.

Labyrinth, 76 bytes

 `:_64/"32}
,`    (3  :=-{
"`{"; _v2$  ;`3
"`".:@ ; ".5(`3.
<       "" `^`;>

Another collab with @MartinBüttner and on the more insane side of the Labyrinth spectrum – for the first time we have all four of ^>v< in the one program. Try it online!

Explanation

The general algorithm, which runs in a loop, is as follows:

 1.   Read a char
 2.   If EOF:
 3.     Move all digits from auxiliary stack to main
 4.     Output all digits on main stack
 5.     Halt
      Otherwise:
 6.     If char is a letter (c >= 64):
 7.       If random turns left:
 8.         Output char XOR 32
          Otherwise:
 9.         Output char
        Otherwise:
10.       Shift char to auxiliary stack
11.       If char is space (c-32 == 0):
12.         Pull char back from auxiliary stack
13.         Output underscore
          Otherwise:
14.         Continue loop

To keep the explanation compact, here's roughly how each part of the program corresponds to the pseudocode above:

Here are the interesting parts.

Getting randomness in Labyrinth

There's only one way to get randomness in Labyrinth, and it's when the IP tries to go forwards but 1) there's neither a path forwards nor backwards and 2) there's paths available left and right. In this case, the IP randomly chooses between the left and right routes.

This is only possible using the^>v< operators, which pop n and shift the row/column n away by 1. For example, the program (Try it online!)

" 1
""v!@
  2
   !@

outputs either 1 or 2 randomly, since the v shifts the column with offset 0 (i.e. the column the IP is on) by 1, yielding

"
""1!@
  v
  2!@

The IP is facing rightward and tries to go forwards (top of stack is zero) but can't. It also can't move backwards, so it randomly chooses between left or right.

Golf tricks

The program starts from the first char in reading order, which you'll notice is actually step 6. However, popping from an empty Labyrinth stack yields 0, so steps 10 and 14 occur, shifting a zero to the auxiliary stack, which is effectively a no-op.
The main stack is effectively empty after every iteration, which allows us to golf the code layout by using > and < on the implicit zeroes at the bottom. The > wraps the bottom row around so that the IP moves from the bottom right to the bottom left, and the < shifts the row back. The IP then happily moves up the left column to continue the loop.
Digits in Labyrinth pop n and push 10*n + <digit>. In addition, chars are taken modulo 256 before being output. Putting these two together lets us output 95 (underscore) by doing `33 to  32 (space), which works because -3233 % 256 = 95. Even though there are other ways to turn 32 into 95 (;95 being the easiest), working with a negative number here allows us to compact the code a bit with left turns.


Plus Primes vs Minus Primes Most of us know...
that all primes p>3 are of the form
But, how many are the Plus Primes (6n+1) and how many are the Minus Primes (6n-1) in a certain range?
The Challenge
Given an integer k>5 , count how many primes<=k are PlusPrimes and how many are MinusPrimes.
Examples
for k=100 we have
[5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89]  12 MinusPrimes
and
[7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 97]      11 PlusPrimes
for k=149 we have
[5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, 101, 107, 113, 131, 137, 149]
18 MinusPrimes
and
[7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 97, 103, 109, 127, 139]
15 PlusPrimes
Rules
Your code must output 2 integers: one for the MinusPrimes and one for the PlusPrimes in any order you like (please specify which is which).
This is code-golf: shortest answer in bytes wins!
Test Cases

Input -> Output    [MinusPrimes,PlusPrimes]

6->[1,0]
7->[1,1]
86->[11,10]
986->[86,78]
5252->[351,344]
100000->[4806,4784]
4000000->[141696, 141448]

05AB1E, 10 9 bytes

Saved 1 byte thanks to Erik the Outgolfer

Outputs as [PlusPrimes, MinusPrimes]

LDpÏ6%5Ñ¢

Try it online!
or as a Test Suite

Explanation

L             # push range [1 ... input]
 DpÏ          # keep only primes
    6%        # mod each by 6
      5Ñ      # divisors of 5 [1, 5]
        ¢     # count


How many ways to write N as a product of M integers? Given an integer N, count how many ways it can be expressed as a product of M integers > 1.

Input is simply N and M, and output is the total count of distinct integer groups. Meaning you can use an integer more than once, but each group must be distinct (3 x 2 x 2 would not count if 2 x 2 x 3 is present).

Constraints

1 < N < 231
1 < M < 30

Examples

Input 30 2 gives output 3, since it can be expressed 3 ways:

2 x 15
3 x 10
5 x 6

Input 16 3 gives output 1, since there's only one distinct group:

2 x 2 x 4

Input 2310 4 gives output 10:

5 x 6 x 7 x 11
3 x 7 x 10 x 11
3 x 5 x 11 x 14
3 x 5 x 7 x 22
2 x 7 x 11 x 15
2 x 5 x 11 x 21
2 x 5 x 7 x 33
2 x 3 x 11 x 35
2 x 3 x 7 x 55
2 x 3 x 5 x 77

Input 15 4 gives output 0, since it cannot be done.

Rules

Standard code golf loopholes apply, along with standard definitions for input/output. Answers may be a function or full program. Built-in functions for factorization and/or partitioning are not allowed, but others are fine. Code is counted in bytes.

Python 3, 59
f=lambda N,M,i=2:i<=N and f(N/i,M-1,i)+f(N,M,i+1)or-~M==N<2

We count up potential divisors i. With the additional argument i as the lowest allowed divisor, the core recursive relation is
f(N,M,i)=f(N/i,M-1,i)+f(N,M,i+1)

For each i, we either choose to include it (possible as a repeat), in which case we divide the required product N by i and decrement M. If we don't, we increase i by 1, but only if i<N, since there's no use checking divisors greater than N.
When the minimum divisor i exceeds N, there's no more potential divisors. So, we check if we've succeeded by seeing if M==0 and N==1, or, equivalently, M+1==N==1 or M+1==N<2, since when M+1==N, the mutual value is guaranteed to be a positive integer (thanks to FryAmTheEggman for this optimization).
This code will cause a stack overflow for N about 1000 on most systems, but you can run it in Stackless Python to avoid this. Moreover, it is extremely slow because of its exponential recursive branching.


The Missing Number - Version 2 Background:

This question is a remix of the one that I made previously on this forum. The only difference with this one is: the range is significantly larger, AND dynamic. Details below!

Also, I'm typing this question incredibly quickly, so if there are any grammatical errors, I do apologize and ask if anyone would edit the question to clear any vagueness. Nonetheless, the original question is posted here: The Missing Number Revised

Question:

Given a minimum bound M, a maximum bound N, and a String of randomly concatenated integers [min, max), min (M) to max (N) exclusive, there is a number missing in the sequence. Your job is to write a program that will calculate this missing number.

Doing this problem by hand on smaller Strings, such as examples 1 and 2 below are obviously very easy. Conversely, computing a missing number on incredibly large datasets involving three-digit, four-digit, or more numbers would be incredibly difficult. The idea behind this problem is to construct a program that will do this process FOR you.

Important Information:

One thing that appeared as rather confusing when I posted this problem last night was: what exactly a missing number is defined as. A missing number is the number INSIDE of the range specified above; NOT necessarily the digit. In example 3, you will see that the missing number is 7, even though it appears in the sequence. There are 3 places the DIGIT 7 will appear in a series of [0, 30): “7”, “17”, and “27”. Your objective is to differentiate between these, and discover that 7 is the missing NUMBER (inside of example 3). In other words, the tricky part lies in finding out which sequences of digits are complete and which belong to other numbers.

Another very important factor in this: there are some input situations where there are multiple solutions! Your job will be to print out ALL numbers that are missing in the sequence. I cannot provide insight as to WHY they have multiple solutions; I only know they may exist.

Input:

The input is a single Integer T: the amount of test cases.

For each test case, there is an Integer M: the minimum number in the sequence, another Integer N: the maximum number in the sequence (thus M < N at ALL times), a String S, containing integers from M to N - 1 inclusive, or M to N exclusive (in other words, [M, N)). These integers, as stated above, are scrambled up to create a random sequence. There are NO delimiters (“42, 31, 23, 44”), or padding 0’s (003076244029002); the problems are exactly as described in the examples.

As stated above, M is ALWAYS lower than N, and the maximum range of numbers is < 100,000. |N - M|.

Winning Criteria:

Whoever has the fastest, and lowest memory usage will be the winner. In the miraculous event that a time ties, lower memory will be used for the time breaker. Please list Big O if you can!

Examples:

(Examples 1-6 are just for demonstration. Your program needn't to handle them.)

Here is a pastebin link of the examples.

TEST DATA

Please keep in mind the way you're to read in the data: Digit D represents how MANY test cases there are, the next lines will follow with integers M and N, then String S. I just wanted to clear it up. I also apologize for the incredibly large pastebin. Good luck!

Data: Test Data - Github repository

Clean -  Complexity Unknown
Currently works, explanation and further optimization in progress
module main
import StdEnv, StdLib, System.IO

:: Position :== [Int]
:: Positions :== [Position]
:: Digit :== (Char, Int)
:: Digits :== [Digit]
:: Number :== ([Char], Positions)
:: Numbers :== [Number]
:: Complete :== (Numbers, Positions)

decouple =: snd o unzip

//lcouple :: (.a -> .b) (.a, .c) -> (.b, .c)
lcouple fn (arg, oth) :== (fn arg, oth)

getCases :: Int *World -> ([(String, [[Char]])], *World)
getCases n world
    # (range, world)
        = evalIO getLine world
    # range
        = fromString range
    # spacePos
        = elemIndex ' ' range
    | isNothing spacePos
        = abort "invalid input, expected space in range\n"
    # (a, b)
        = splitAt (fromJust spacePos) range
    # (a, b)
        = (toInt (toString a), toInt (toString (tl b)))
    # numbers
        = [(fromString o toString) number \\ number <- [a..(b-1)]]
    # (string, world)
        = evalIO getLine world
    | n > 1
        # (cases, world)
            = getCases (n - 1) world
        = ([(string, numbers) : cases], world)
    = ([(string, numbers)], world)

singletonSieve :: Complete -> Complete
singletonSieve (list, sequence)
    | sequence_ == sequence
        = reverseSieve (list, sequence)
    = (list_, sequence_)
where
    singles :: Positions
    singles
        = [hd pos \\ (_, pos) <- list | length pos == 1]
    list_ :: Numbers
    list_
        = map (app2 (id, filter notInOtherSingle)) list
    where
        notInOtherSingle :: Position -> Bool
        notInOtherSingle pos
            = not (isAnyMember pos (flatten (filter ((<>) pos) singles)))
    sequence_ :: Positions
    sequence_
        = foldr splitSequence sequence singles

reverseSieve :: Complete -> Complete
reverseSieve (list, sequence)
    | sequence_ == sequence
        = (list, sequence)
    = (list_, sequence_)
where
    singles :: Positions
    singles
        = [hd pos \\ pos <- [[subSeq \\ subSeq <- sequence | isMember subSeq p] \\ (_, p) <- list] | length pos == 1]
        //= [hd pos \\ pos <- | length pos == 1]
    list_ :: Numbers
    list_
        = map (app2 (id, filter (\b_ = (notInOtherSingle b_) && (hasContiguousRun b_)))) list
    where
        notInOtherSingle :: Position -> Bool
        notInOtherSingle pos
            = not (isAnyMember pos (flatten (filter ((<>) pos) singles)))
        hasContiguousRun :: Position -> Bool
        hasContiguousRun pos
            //= any (any (isPrefixOf pos) o tails) sequence_
            = and [isMember p (flatten sequence_) \\ p <- pos]

    sequence_ :: Positions
    sequence_
        = foldr splitSequence sequence singles

splitSequence :: Position Positions -> Positions
splitSequence split sequence
    = flatten (map newSplit (map (span (not o ((flip isMember) split))) sequence))
where
    newSplit :: (Position, Position) -> Positions
    newSplit ([], b)
        # b
            = drop (length split) b
        | b > []
            = [b]
        = []
    newSplit (a, b)
        # b
            = drop (length split) b
        | b > []
            = [a, b]
        = [a]

indexSubSeq :: [Char] Digits -> Positions
indexSubSeq _ []
    = []
indexSubSeq a b
    # remainder
        = indexSubSeq a (tl b)
    | isPrefixOf a (map fst b)
        = [[i \\ (_, i) <- take (length a) b] : remainder]
        //= [[i \\ _ <- a & (_, i) <- b] : remainder]
    = remainder

missingNumber :: String [[Char]] -> [[Char]]
missingNumber string numbers
    # string
        = [(c, i) \\ c <-: string & i <- [0..]]
    # locations
        = [(number, indexSubSeq number string) \\ number <- numbers]
    # digits
        = [length (indexSubSeq [digit] [(c, i) \\ c <- (flatten numbers) & i <- [0..]]) \\ digit <-: "0123456789-"]
    # missing
        = flatten [repeatn (n - length i) c \\ n <- digits & (c, i) <- [(digit, indexSubSeq [digit] string) \\ digit <-: "0123456789-"]]
    # (answers, _)
        = until (\e = e == singletonSieve e || length [(a, b) \\ (a, b) <- fst e | length b == 0 && isMember a (candidates missing)] > 0) singletonSieve (locations, [indexList string])
    # answers
        = filter (\(_, i) = length i == 0) answers
    = filter ((flip isMember)(candidates missing)) ((fst o unzip) answers)
where
    candidates :: [Char] -> [[Char]]
    candidates chars
        = moreCandidates chars []
    where
        moreCandidates :: [Char] [[Char]] -> [[Char]]
        moreCandidates [] nums
            = removeDup (filter (\num = isMember num numbers) nums)
        moreCandidates chars []
            = flatten [moreCandidates (removeAt i chars) [[c]] \\ c <- chars & i <- [0..]]
        moreCandidates chars nums
            = flatten [flatten [moreCandidates (removeAt i chars) [ [c : num] \\ num <- nums ]] \\  c <- chars & i <- [0..]]

Start world
    # (number, world)
        = evalIO getLine world
    # (cases, world)
        = getCases (toInt number) world
    =  flatlines[flatten(intersperse [', '] (missingNumber string numbers)) \\ (string, numbers) <- cases]

Try it online!


Which dominoes are missing? A standard domino set has 28 unique pieces:

Given a list of 28 or fewer unique dominoes, output the list required to make a complete set.

Input and output dominoes are specified by two digits - the number of pips on each side of the domino, e.g. 00, 34, 40, 66.

The digits may be given in any order, so 34 is the same domino as 43

Example Inputs

00 01 02 03 04 05 06 11 12 13 14 15 16 22 23 24 25 26 33 34 35 36 44 45 46 55 56 66
00 10 11 20 21 22 30 31 32 33 40 41 42 43 44 50 51 52 53 54 55 60 61 62 63 64 65 66
00 01 02 03 04 05 06 11 12 13 14 15 16 22 23 24 25 26 34 35 36 44 45 46 55 56 66
00 02 03 04 05 06 11 13 14 15 16 22 24 25 26 33 35 36 44 46 55 66
<empty list>

Corresponding Example Outputs

<empty list>
<empty list>
33
01 12 23 34 45 56
00 01 02 03 04 05 06 11 12 13 14 15 16 22 23 24 25 26 33 34 35 36 44 45 46 55 56 66

CJam, 11 bytes

{:$7Ym*:$^}

An unnamed block (function) with I/O as a list of pairs of integers.

Test it here.

Explanation

:$   e# Sort each pair in the input.
7Ym* e# Get all pairs with elements in range [0 .. 6] using a Cartesian product.
:$   e# Sort each pair.
^    e# Symmetric set-difference. This will remove all pairs that are in the input
     e# and also remove duplicates, because it's a set operation.


MATL, 20 bytes

XJZyXyi:"!J2$1!*s1$e

Try it online!

Explanation

This avoids the matrix multiplication by doing it manually, using element-wise multiplication with broadcast followed by vectorized sum. Specifically, to multiply matrices M and N, both of size s×s:

Transpose M. Call the resulting matrix P.
Permute the dimensions of N such that N is "turned" with a rotation axis along the first dimension, giving an s×1×s 3D array, say Q.
Multiply each element of P times each element of Q, with implicit broadcast. This means that P is automatically replicated s times along the third dimension, and Q is replicated s times along the second, to make them both s×s×s, before the actual element-wise multiplication takes place.
Sum along the first dimension to yield a 1×s×s array.
Squeeze the leading singleton dimension out, to produce an s×s result.

Commented code:

XJ      % take matrix A. Copy to clipboard J
ZyXy    % generate identity matrix of the same size
i:      % take exponent n. Generate range [1 2 ... n] (possibly empty)
"       % for each element in that range
  !     %   transpose matrix with product accumulated up to now (this is step 1)
  J     %   paste A
  2$1!  %   permute dimensions: rotation along first-dimension axis (step 2)
  *     %   element-wise multiplication with broadcast (step 3)
  s     %   sum along first dimension (step 4)
  1$e   %   squeeze out singleton dimension, i.e. first dimension (step 5)
        % end for. Display


Quinean Regex Tester This challenge is pretty simple. As input, you take in a regular expression.
Then, you output a truthy/falsey of whether or not your source code matches the regular expression. It's that simple! Just two more things:

No quine builtins; you may, however, access the code's source code by file IO, etc.
This is code-golf, so shortest code in bytes wins!

Example
If your source code was say, abc, an input of a\wc would return true and an input of a\dc would return false.

Z shell, 12 bytes

grep "$@"<$0

Zsh conditionals understand only exit codes, and the scripts exits with 0 or 1 accordingly.

In addition, this prints a non-empty string (the source code) for a match and an empty one for a mismatch, which could be as truthy/falsy values in combination with test/[.

The program reads its own file, but according to this comment by the OP, this is allowed.


Fewest operations to 100 Overview

Given a list of digits, find the fewest operations to make 100

Input

A string of digits, which may or may not be in numerical order. The order of the digits cannot be changed, however plus (+) or minus (-) operators may be added between each so that the total sum is equal to 100.

Output

The number of operators added, followed by the full sequence of digits and operators. The two can be separated by a space, tab, or new line sequence.

Examples

valid

Input: 123456789
Output: 3 123–45–67+89

Invalid
Input: 123456789
Output:
6
1+2+34-5+67-8+9
(There are ways of solving this with fewer operations)

JavaScript (ES6), 153 176 bytes
EDIT: In non-strict mode, JS interprets 0-prefixed numerical expressions as octal (e.g. 017 is parsed as 15 in decimal). This is a fixed version that supports leading zeros.

let f =

s=>[...Array(3**(l=s.length,l-1))].map((_,n)=>m=eval((x=s.replace(/./g,(c,i)=>c+['','+','-'][o=(n/3**i|0)%3,j-=!o,o],j=l)).replace(/\b0+/g,' '))-100|j>m?m:(S=x,j),m=l)&&m+' '+S

console.log(f("123456789"))
console.log(f("20172117"))


Make me a password generator! I am making a customizable password generator.

But I (for some reason) thought it'd be better to let you guys do it.

Umm.. then?

You only get one integer. That will include all the information about the customization.

The first 4 bits (1,2,4,8) will be used for choosing which charsets will be used.

Each bit corresponds to:

1: Lowercase alphabet(qwertyuiopasdfghjklzxcvbnm)

2: Uppercase alphabet(QWERTYUIOPASDFGHJKLZXCVBNM)

4: Numbers(0123456789)

8: Special chars(All printable characters except ones stated above and the space)

The length of the password will be shifted 4 bits. In other words, multiplied by 16.

Then generate the password with the charsets and the length.

Examples

175 (10*16 + 15 (1111)): a_U0!/h96%

Python 2, 217 203 bytes

from random import*
r=[10]+range(33,127)
r=[r[65:91],r[33:59],r[16:26],r[:16]+r[26:33]+r[59:65]+r[91:]]
x=input()
l=x>>4
print''.join(map(chr,sample(sum([k[1]for k in enumerate(r)if x&2**k[0]],[])*l,l)))

Ugh this is horribly long. The part I think could be golfed the most is the part to get the charsets; that part was a pain.

By the way, I am @HyperNeutrino; I'm just getting enough rep to chat. :P

-14 bytes thanks @ValueInk!
Bug fix thanks to @ovs!


Partitioning reciprocals Given a number n > 77, write a program or function that finds a set of distinct positive integers such that the sum of the set equals n, and the sum of the reciprocals of the set equals 1.

Example for 80:

  80 = 2 + 4 + 10 + 15 + 21 + 28    ⟶
  1/2 + 1/4 + 1/10 + 1/15 + 1/21 + 1/28 = 1

Your program or function must (theoretically) work for any n < 232, and is not excused for floating point rounding errors. Note that solutions exist for all n > 77.

Shortest code in bytes wins.

There is a bonus incentive: I will award a bounty to the smallest solution that works for any n and runs log(n). For small n it must be fast (determined at my discretion). Yes, this is possible.


Count occurences of a set in a list Given a non-empty set of strings and a list of strings, find out how many times the set occurs in the list, i.e. how many times you could create the set with items from the list. Every element from the list can only be used once.

  Hint: a set is an unordered list of unique items.

Default input/output rules apply.

No external libraries allowed. Compiler/Interpreter standard libs are okay. This is code golf, so shortest solution counts.

Test cases:

["apple", "banana"], ["apple", "pear", "apple", "banana", "banana"] => 2

["apple", "banana"], ["apple", "pear", "apple", "banana", "apple"] => 1

["apple", "banana", "pear"], ["apple", "banana", "kiwi", "apple"] => 0

["coconut"], [] => 0

EDIT: removed a sentence stating that the input params are defined in local scope. This contradicts the default IO rules linked above.

Python, 30 bytes

lambda s,l:min(map(l.count,s))

Try it online!


Animal-Alphabetical Sequence The Animal-Alphabetical Sequence is an infinite string of letters built accordingly to the following procedure:

Start with the letter A;

Replace each letter with the name of the animal starting with such letter in the table below;

Go back to step 2.

For instance, the first four steps of the procedure give:

A

ADDAX

ADDAXDINGODINGOADDAXXERUS

ADDAXDINGODINGOADDAXXERUSDINGOINDRINYALAGECKOOTTERDINGOINDRINYALAGECKOOTTERADDAXDINGODINGOADDAXXERUSXERUSEAGLEROBINURIALSQUID

Note that the string obtained at each step is a prefix of the string obtained at the next step. Hence, the procedure does indeed converge to a well-defined infinite string:
ADDAXDINGODINGOADDAXXERUSDINGOIND...
The Challenge
Write a function that takes as input an integer n in the range [0, 2^31 - 1] and returns as output the n-th letter of the Animal-Alphabetical Sequence.
Notes

The first letter is the 0-th.

Letters can be uppercase or lowercase.

It must be possible to run the program in the Try It Online interpreter and get the result in at most 5 minutes.

Test Cases
1511763812 -> M
1603218999 -> I
2049234744 -> X
2060411875 -> K
2147483647 -> D

Table of Animal Names
ADDAX
BISON
CAMEL
DINGO
EAGLE
FOSSA
GECKO
HORSE
INDRI
JAMBU
KOALA
LEMUR
MOUSE
NYALA
OTTER
PRAWN
QUAIL
ROBIN
SQUID
TIGER
URIAL
VIXEN
WHALE
XERUS
YAPOK
ZEBRA

Charcoal, 83 bytes
≔AηＦ↨Ｎ⁵≔§⁺η§⪪”$⌊∧Ｘ;F‖ρ=ＪD θ⊘⊙～'ΣV⦄Ｋ◨｜]≕‖◨⟧TJρ¿¿C´!⁸⁶S/Ｕ¶V×Ｗ⧴a“,=6；‴*Þ↓h!�{≦”⁴⌕αηιηη

Try it online! Link is to verbose version of code. Explanation:
≔Aη

Start with A at the 0th index.
Ｆ↨Ｎ⁵

Input n, convert it to base 5 and loop over the digits.
≔§⁺η§⪪”...”⁴⌕αηιη

Get the current animal from the compressed string of all animal suffixes (excluding EBRA) and lookup the appropriate letter from the current digit.
η

Output the final letter.


Quine quine bip quine quine Write a quine that

Writes its source code to disk
Recursively executes the written source code
Produces some variation to the code the third time (so not a true Quine)
Stops recursively calling itself the fifth time

Bonus points for leaving nothing on disk after execution.

TCL 220

proc a b {
if {"$b"=="bb"} {
rename puts w
rename p puts
set b \;exit
}
puts [set q [open [incr ::i] w]] "proc a b \{[info body a]\};a b"
catch {rename puts p}
proc puts {n m} "p \$n \${m}$b"
close $q
source $::i
};a b

The code generates files 1, 2, 3 and 4. The variation is only present in 2, the others are equivalent to the original.


Minimum base to count to a string The Challenge
Input: alphanumeric string. You can assume that the string will only contain the characters [0-9A-Z]. This can come from a parameter, command line, or STDIN. Digits are always before letters in terms of the base. Think like an extended version of HEX.
Output X,Y Such that Y is the minimum base required to parse the string and X is the decimal value of the input string in that base.
Examples

Input: "1"
Output: 1,2

Input: "HELLOWORLD"
Output: 809608041709942,33

Scoring: This is a golf, so shortest code in bytes wins.

Python 2, 74 64 56 55 53 bytes

def f(x):a=ord(max(x))-54;a+=7*(a<8);print int(x,a),a

Call the function (i.e. f("HELLOWORLD")) and outputs to stdout (809608041709942 33)

This is case-sensitive, requiring upper case letters, and crashes for invalid input (e.g. "$^$%!(&£%)())

This code gets the max letter in the string (z>x>y>...>b>a>9>8>...>2>1>0) and gets the largest base needed to represent it.

Change the 54 into a 76 to make it work for lowercase (but no longer upper case).


Decimal Multiplication of Strings Given 2 inputs, a string and a decimal number, output the string multiplied by that number.

The catch is that the number can be a float or an integer.

You should output the string floor(n) time and then the first floor((n-floor(n))*len(string)) letters again.

Other notes:

The input will not always be a float, it may be an int. So 1.5, 1, and 1.0 are all possible.  It will always be in base 10 though, and if you wish an exception please comment.
The string input may contain whitespace, quotes and other characters.  No newlines or control chars though.
No built-ins for direct string repeating, even string multiplication like the python 'a'*5 are allowed.  However string addition is allowed.

Test cases:

The comma & space separate the inputs.

test case, 1 -> test case

case, 2.5 -> casecaseca

(will add more later), 0.3333 -> (will(space)

cats >= dogs, 0.5 -> cats >

Final Note:

I am seeing a lot of answers that use builtin string multiplication or repeation functions.  This is not allowed.  @VTC's answer is valid though, because it does not multiply the string, only the float input.  So the definitive rule is: If it directly multiplies the string, you can't do it.

Java 7, 89
void g(char[]a,float b){for(int i=0,l=a.length;i<(int)(l*b);)System.out.print(a[i++%l]);}

takes char[] and float and outputs to STDOUT. basic looping.


Mod 2 Multinomial coefficients quintopia has posted here a challenge to compute multinomial coefficients (some of the text here is copied from there). There is a fun algorithm to compute multinomial coefficients mod 2.

Given a list of numbers, k1, k2, ... ,km, output the residue of the multinomial coefficient:

reduced mod 2. The following algorithm does this efficiently: for each ki, compute the binary expansion of ki, that is, find aij such that each aij is either 1 or 0 and

If there is any j such that arj = asj = 1 for r     ≠ s, then the associated mod 2 multinomial coefficient is 0, otherwise the mod 2 multinomial coefficient is 1.

Task

Write a program or function which takes m numbers, k1, k2, ... ,km, and outputs or returns the corresponding multinomial coefficient. Your program may optionally take m as an additional argument if need be.

These numbers may be input in any format one likes, for instance grouped into lists or encoded in unary, or anything else, as long as the actual computation of the multinomial coefficient is performed by your code, and not the encoding process.
Output can be any truthy value if the multinomial coefficient is odd and any falsey value if the multinomial coefficient is even.
Built-ins designed to compute the multinomial coefficient are not allowed.
Standard loopholes apply.

Scoring

This is code golf: Shortest solution in bytes wins.

Examples:

To find the multinomial coefficient of 7, 16, and 1000, we binary expand each of them:

Since no column has more than one 1, the multinomial coefficient is odd, and hence we should output something truthy.

To find the multinomial coefficient of 7, 16, and 76, we binary expand each of them:

Since both 76 and 7 have a 4 in their binary expansion, the multinomial coefficient is even and so we output a falsey value.

Test cases:

Input: [2, 0, 1]
Output: Truthy

Input: [5,4,3,2,1]
Output: Falsey

Input: [1,2,4,8,16]
Output: Truthy

Input: [7,16,76]
Output: Falsey

Input: [7,16,1000]
Output: Truthy

Input: [545, 1044, 266, 2240]
Output: Truthy

Input: [1282, 2068, 137, 584]
Output: Falsey

Input: [274728976, 546308480, 67272744, 135004166, 16790592, 33636865]
Output: Truthy

Input: [134285315, 33849872, 553780288, 544928, 4202764, 345243648]
Output: Falsey

Jelly, 4 bytes

S=|/

Try it online!

Test whether the sum is equal to the bitwise-or-sum (i.e. a+b+c == a|b|c).


Visigoth

Visigoth tries to burn its enemies to the ground. It hopes to do this before anyone else gets to its land.

Run: python visigoth.py

#!/usr/bin/python

''' Charge the enemy and burn them to the ground. '''

import sys

data = sys.stdin.readlines()

startx, starty, x, y = [int(i) for i in data[0:4]]
field = [list(i) for i in data[4:]]

otherbots = []
for i in range(32):
    for j in range(32):
        if field[i][j]=='@': #bot
            if i!=y and j!=x:
                otherbots.append([j,i])

min_bot = otherbots[0]
for bot in otherbots:
    if abs(bot[0]-x)+abs(bot[1]-y) < abs(min_bot[0]-x)+abs(min_bot[1]-y):
        min_bot = bot

dx = min_bot[0]-x
dy = min_bot[1]-y

if abs(dy)>abs(dx):
    if dy>0:
        move = 'U'
    else:
        move = 'D'
else:
    if dx>0:
        move = 'R'
    elif dx<0:
        move = 'L'
    else:
        move = 'S'

if max(abs(x-startx), abs(y-starty))>4:
    if 0<x<31 and 0<y<31:
        dirs = {'U':(-1,0), 'D':(1,0), 'L':(0,-1), 'R':(0,1)}
        for i in dirs:
            if field[dirs[i][0]][dirs[i][1]] in ('.', 'W'):
                action = 'B'+i
                break
        else:
            # No free land nearby, go out in a blaze of glory
            action = 'BS'
    else:
        action = 'BS'
else:
    # Don't set own field on fire
    action = 'XS'

print move+action

This is my first entry, constructive criticism is appreciated!


How many Sudoku puzzles exist? This is not a Sudoku solver, nor a Sudoku checker.

Your challenge is to write a function or script that, given as input the "block" size of a 2D Sudoku puzzle (which is 3 for the classic 9x9 board, 4 for a 16x16 board, etc.) will compute an approximation of the number of distinct puzzles (solutions) that exist for that size.

For example, given input 3, your program should print an approximation, to the desired precision, of the number 6,670,903,752,021,072,936,960 which is the known number of distinct 9x9 Sudoku puzzles, or 5,472,730,538 when taking into account the various symmetries. Your solution should state whether symmetries are counted or ignored.

"Desired precision" is left undefined: your program might run for a given time and then output its result, or compute it up to a given number of significant digits, or even run forever, printing better and better approximations. The point is that it should be possible to make it compute the result to any required precision, in a finite time. (So "42" is not an acceptable answer.) Restricting the precision of your result to the available machine floats is acceptable.

No accessing online resources, no storing the source code in the file name, etc.

PS: I know this is a Hard Problem (NP-complete if I'm not mistaken.) But this question is only asking for an approximate, statistical solution. For example you can try random configurations that satisfy one (or better two) constraints, compute how many of those exist and then check how often you get a puzzle that satisfies all three constraints. This will work in a decent time for small sizes (certainly for size=3 and possibly 4) but the algorithm should be generic enough to work for any size.

The best algorithm wins.

PS2: I changed from code-golf to code-challenge to better reflect the difficulty of the problem and encourage smarter solutions, over dumb but well-golfed ones. But since apparently "best algorithm" is unclear, let me try to define it properly.

Given enough time and disregarding constant factors (including CPU and intepreter speed), or equivalently, considering their asymptotical behaviour, which solution would converge to the exact result the fastest?

C++

What i will present here is an algorithm, illustrated with an example for a 3x3 case. It could theoretically be extended to the NxN case, but that would need a much more powerful computer and/or some ingenious tweaks. I will mention some improvements as I go through.

Before going further, let's note the symmetries of the Sudoku grid, i.e. the transformations which lead to another grid in a trivial way. For block size 3, the symmetries are as follows:

Horizontal symmetry

**The N=3 sudoku is said to consist of 3 "bands" of 3 "rows" each**
permute the three bands: 3! permutations = 6
permute the rows in each band: 3 bands, 3! permutations each =(3!)^3=216

Vertical symmetry

**The N=3 sudoku is said to consist of 3 "stacks" of 3 "columns" each.**
the count is the same as for horizontal.

Note that horizontal and vertical reflections of the grid can be achieved by a combination of these, so they do not need to be counted.
There is one more spatial symmetry to be considered, which is transposing, which is a factor of 2. This gives the total spatial symmetry of

2*(N!*(N!)^N)^2 = 2*(6*216)^2=3359232 spatial symmetries for the case N=3.

Then there is another, very important symmetry, called relabelling.

Relabelling gives a further (N^2)!=9!=362880 symmetries for the case N=3. So the total
number of symmetries is 362880*3359232=1218998108160.

The total number of solutions cannot be found simply by multiplying the number of symmetry-unique solutions by this number, because there are a number (less than 1%) of automorphic solutions. That means that for these special solutions there is a symmetry operation that maps them to themselves, or multiple symmetry operations that map them to the same other solution.

To estimate the number of solutions, I approach the problem in 4 steps:

1.Fill an array r[362880][12]with all possible permutations of the numbers 0 to 8. (this is programming, and it is in C, so we are not going to use 1 to 9.) If you are astute you will notice that the second subscript is 12 not 9. This is because, while doing this, bearing in mind that we are going to consider this to be a "row" we also calculate three more integers r[9,10,11] == 1<<a | 1<<b | 1<<c where 9,10,11 refer to the first, second and third stack and a,b,c are the three numbers present in each stack for that row.

2.Fill an array b with all possible solutions of a band of 3 rows. To keep this reasonably small, only include those solutions where the top row is 012,345,678. I do this by brute force, by generating all possible middle rows and ANDing r[0][10,11,12] with r[i][10,11,12]. Any positive value means there are two identical numbers in the same square and the band is invalid. When there is a valid combination for the first two rows, I search the 3rd (bottom) row with the same technique.

I dimensioned the array as b[2000000][9] but the program only finds 1306368 solutions. I did not know how many there were, so I left the array dimension like that. This is actually only half the possible solutions for a single band (verified on wikipedia), because I only scan the 3rd row from the current value for i upwards. The remaining half of the solutions can be found trivially by exchanging the 2nd and 3rd rows.

The way the information is stored in array b is a little confusing at first. instead of using each integer to store the numbers 0..8 found in a given position, here each integer considers one of the numbers 0..8 and indicates in which columns it can be found. thus b[x][7]==100100001 would indicate that for solution x the number 7 is found in columns 0,5 and 8 (from right to left.) The reason for this representation is that we need to generate the rest of the possibilities for the band by relabelling, and this representation makes it convenient to do this.

The two steps above comprise the setup and take about a minute (possibly less if I removed the unnecessary data output. The two steps below are the actual search.)

3 Search randomly for solutions for the first two bands that do not clash (i.e. do not have the same number twice in a given column. We pick a random solution for band 1, assuming always permutation 0, and a random solution for band 2 with a random permutation. A result is normally found in less than 9999 tries (first stage hit rate in the thousands range) and takes a fraction of a second. By permutation, I mean that for the second band we take a solution from b[][] where the first row is always 012,345,678 and relabel it so that any possible sequence of numbers on the first row is possible.

4 When a hit is found in step 3, search for a solution for the third band which does not clash with the other two. We do not want to make just one try, otherwise the processing time for step 3 would be wasted. On the other hand we do not want to put an inordinate amount of effort into this.

Just for fun, last night I did it the dumbest way possible, but it was still interesting (because it nothing for ages, then found large numbers of solutions in bursts.) It took all night to get one datapoint, even with the little hack (!z) I did to abort the last k loop as soon as we know this is not a valid solution (which makes it run nearly 9 times faster.) It found 1186585 solutions for the complete grid
after searching all 362880 relabellings of all 1306368 canonical solutions for the last block, a total of 474054819840 possibilities. That's a hit rate of 1 in 400000 for the second stage. I will try again soon with a random search rather than a scan. It should give a reasonable answer in just a few million tries, which should take only a few seconds.

The overall answer should be (362880*(1306368*2))^3*hit rate=8.5E35*hit rate. By back calculating from the number in the question, I expect a hit rate of 1/1.2E14. What I've got so far with my single datapoint is 1/(400000*1000) which is out by a factor of about a million. This could be an anomaly of chance, an error in my program, or an error in my math. I won't know which it is until I run a few more tests.

I'll leave this here for tonight. The text is a bit scrappy, I will tidy it up soon and hopefully add some more results, and maybe a few words on how to make it faster and how to extend the concept to  N=4. I don't think I'll be making too many more changes to my program, though :-)

Ah.. the program:

#include "stdafx.h"
#define _CRT_RAND_S
#include <algorithm>
#include <time.h>

unsigned int n[] = { 0,1,2,3,4,5,6,7,8 }, r[362880][12], b[2000000][9],i,j,k,l,u,v,w,x,y,z;

int main () {

  //Run through all possible permutations of n[] and load them into r[][]
  i=0;
  do {
      r[i][9] = r[i][10] = r[i][11]=0;
      for (l = 0; l < 9; l++){
          r[i][l] = n[l];
          r[i][9 + l / 3] |= 1 << n[l];
      }
      if((i+1)%5040==0) printf("%d%d%d %d%d%d %d%d%d %o %o %o %o \n"
          ,r[i][0],r[i][1],r[i][2],r[i][3],r[i][4],r[i][5],r[i][6],r[i][7],r[i][8],r[i][9],r[i][10],r[i][11],r[i][9]+r[i][10]+r[i][11]);
      i++;
  } while ( std::next_permutation(n,n+9) );

  //Initialise b[][]
  for (l = 0; l<2000000; l++) for (k = 0; k<9; k++) b[l][k]=0;
  //fill b[][] with all solutions of the first band, where row0 ={0,1,2,3,4,5,6,7,8} and row1<row2
  l=0;
  for (i = 0; i<362880; i++)
  if (!(r[0][9] & r[i][9] | r[0][10] & r[i][10] | r[0][11] & r[i][11])){printf("%d %d \n",i,l);
     for (j=i; j<362880;j++)
       if(!(r[0][9]&r[j][9] | r[0][10]&r[j][10] | r[0][11]&r[j][11] | r[j][9]&r[i][9] | r[j][10]&r[i][10] | r[j][11]&r[i][11] )){
           for (k = 0; k < 9; k++){
               b[l][r[0][k]]|=1<<k;
               b[l][r[i][k]]|=1<<k;
               b[l][r[j][k]]|=1<<k;
            }
            l++;
       }
//        printf("%d%d%d %d%d%d %d%d%d %o %o %o %o \n"
//        ,r[i][0],r[i][1],r[i][2],r[i][3],r[i][4],r[i][5],r[i][6],r[i][7],r[i][8],r[i][9],r[i][10],r[i][11],r[i][9]+r[i][10]+r[i][11]);
//        printf("%d%d%d %d%d%d %d%d%d %o %o %o %o \n"
//        ,r[j][0],r[j][1],r[j][2],r[j][3],r[j][4],r[j][5],r[j][6],r[j][7],r[j][8],r[j][9],r[j][10],r[j][11],r[j][9]+r[j][10]+r[j][11]);
//        printf("%d %d %o %o %o %o %o %o %o %o %o \n",i,l,b[l][0],b[l][1],b[l][2],b[l][3],b[l][4],b[l][5],b[l][6],b[l][7],b[l][8]);
  }

  // find a random solution for the first 2 bands
  l=0;
  do{
      rand_s(&u); u /= INT_MIN / -653184; //1st band selection
      rand_s(&v); v /= INT_MIN / -181440; //2nd band permutation
      rand_s(&w); w /= INT_MIN / -653184; //2nd band selection
      z = 0;
      for (k = 0; k < 9; k++) z |= b[u][k] & b[w][r[v][k]];
      l++;
  } while (z);
  printf("finished random after %d tries \n",l);
  printf("found solution with top band %d permutation 0, and middle band %d permutation %d \n",u,w,v);
  getchar();

  // scan all possibilities for the last band
  l=0;
  for (i = 0; i < 362880; i++) for (j = 0; j < 1306368; j++){
              z=0;
              for(k=0;(k<9)&&(!z);k++) z|= b[u][k] & b[j][r[i][k]] | b[j][r[i][k]] & b[w][r[v][k]];
              if (!z){ l++; printf("solution %d : i= %d j=%d",l,i,j); }
  }
  printf("finished bottom band scan at %d millisec \n", clock()); getchar();
}


Shortest power set implementation Problem definition

Print out the powerset of a given set. For example:

[1, 2, 3] => [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

Each element is to be printed on a separate line, so the above example would be printed as:

[]
[1]
[2]
...
[1, 2, 3]

Example code (in D, python example here):

import std.stdio;

string[][] powerset(string[] set) {
    if (set.length == 1) {
        return [set, []];
    }

    string[][] ret;
    foreach (item; powerset(set[1 .. $])) {
        ret ~= set[0]~item;
        ret ~= item;
    }

    return ret;
}

void main(string[] argv) {
    foreach (set; powerset(argv[1 .. $]))
        writeln(set);
}

Input

Elements will be passed as arguments. For example, the example provided above would be passed to a program called powerset as:

powerset 1 2 3

Arguments will be alphanumeric.

Rules

No libraries besides io
Output does not have to be ordered
Powerset does not have to be stored, only printed
Elements in the set must be delimited (e.g. 1,2,3, [1,2,3] and ['1','2','3'] are acceptable, but 123 is not

Trailing delimiters are fine (e.g. 1,2,3, == 1,2,3)

Best is determined based on number of bytes

The best solution will be decided no less than 10 days after the first submission.

Mathematica 16

Code

Subsets is native to Mathematica.

Column@Subsets@s

The code (without column) can be verified on WolframAlpha. (I had to use brackets instead of @; they mean the same thing.

Usage

s={1,2,3}
Column@Subsets@s

This method (55 chars) uses the approach suggested by @w0lf.

s #&/@Tuples[{0,1},Length@s]/.{0:>Sequence[]}//Column

Breakdown

Generate the tuples, composed of 0 and 1's of length Length[s]

Tuples[{0, 1}, Length@s]

  {{0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {0, 1, 1}, {1, 0, 0}, {1, 0, 1}, {1,
     1, 0}, {1, 1, 1}}

Multiply the original list (vector) by each tuple:

s # & /@ Tuples[{0, 1}, Length@s]

  {{0, 0, 0}, {0, 0, 3}, {0, 2, 0}, {0, 2, 3}, {1, 0, 0}, {1, 0, 3}, {1,
     2, 0}, {1, 2, 3}}

Delete the 0's. % is shorthand for "the preceding output".

%/. {0 :> Sequence[]}

  {{}, {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}}

Display in column:


My program knows your language. Does yours? Given a list of production rules and start symbol of a proper finite context-free grammar (CFG) of printable characters, your program or function must output its formal language (the set of all sentences which can be constructed from it).

Task

A context-free grammar is formally defined as a 4-tuple of a few parts. Here, they are defined for you to solve this challenge.

For the purposes of the challenge, a production rule is of the form {begin, {end-1, end-2, end-3, ..., end-n}} or equivalent. The begin part is always one printable character (0x20 to 0x7E), and the end-i are all strings of printable characters.

Your program will receive as input a list of production rules and a start symbol. The start symbol is a single printable character.

An iteration takes an input list of strings and is defined as follows: To each string s in the input list, look at the first character c in it which is found as the begin of a production rule. To each end-i on the right side of that rule, add to the list the string s but where the first instance of c is replaced by the string end-i. Then remove the original string s if and only if there is a character c.

The program would repeat applying iterations, beginning with the start symbol, until an iteration does not affect the list of strings, at which point it outputs the list of strings (with repeats removed).

This is equivalent to the following pseudo-code:

rules = input()
start_symbol = input()

define iteration(string_list,rules):
  for each string in string_list:
    c = first char in string which is the first element of a rule in rules
    // ^^ This is a Mathematica builtin, right? ^^
    if(c exists):
      ends = the second element of that rule
      for each end in ends:
        // replace the first instance of c with end.
        string_list.append(string.replace(c,end))
      string_list.remove(string)
      // make sure you don't remove the original string if
      // there does not exist a c

  return string_list

current_string = start_symbol

// Clearly this is inefficient to apply iteration twice
// but hey, this is code golf. As long as it runs in less than 60 seconds on TIO!
while(iteration(current_string)!=current_string):
  current_string = iteration(current_string)

print remove_repeats(current_string)

Note that you do not need to follow this exact pseudo-code as long as your program yields correct output.

Example

Given the start symbol S and production rules:

{S:{aE,bE,c}}
{E:{ab,aC}}
{C:{a,b,c}}

We do:

{S} // start
{aE,bE,c} // apply first rule to the first element
{aab,aaC,bab,baC,c} // apply second rule to the first and second element
{aab,aaa,aab,aac,bab,baa,bab,bac,c}             // apply third rule to the second and fourth elements
{aab,aaa,aac,bab,baa,bac,c} // remove repeats

Input restrictions

This should only matter to people who care.

The CFG ...

has no recursion.
has no cycles.
has no unreachable symbols.
has no unproductive symbols.

The list of production rules ...

may have productions resulting in an empty string.
may be taken in any format, as long as it encodes only a begin character and a list of alternatives as end-i for each rule.
has no duplicate begin characters.
has no duplicate end characters within a production rule

Test Cases

start symbol, {rule1, rule2, ...}, expected output
S, {S: {aE,bE,c}, E: {ab,aC}, C: {a,b,c}}, {aab,aaa,aac,bab,baa,bac,c}
S, {S: {a,B}, B: {g,k}}, {a,g,k}
A, {A: {B,C,D}, B: {c,d}, C:{b,d}, D:{b,c}}, {c,b,d}
~, {~: {`,^,/}, /:{`^,``}, ^:{``,```}}, {`,``,```,````}
+, {A: {1,2,3}, +:{A,B,C}}, {1,2,3,B,C}

Notes

The input will be taken in any convenient format as long as it gives no information other than the production rules and start symbol.
The output should be given such that the list of strings as output is clearly encoded and unique.
Please specify what format your list of production rules are taken in.
This is code-golf, so shortest code in each language wins. Do not be discouraged from posting by answers in golfing languages.


Pulse Measurement of Heart Arrhythmia In this challenge you have to make an ascii pulsing heart with rhythm problems (Heart arrhythmia) and then measure the pulse.Don't worry it's easy!

Making the heart

The heart alternates between these 2 states:
state 1

    ,d88b.d88b,
    88888888888
    `Y8888888Y'
      `Y888Y'
        `Y'

state 2

     d8b d8b
    888888888
    `Y88888P'
     `Y888P'
      `Y8P'
       `Y'

each step has X seconds delay
where X is a Random (Real) number between 0.3 and 1.4 (0.3<=X<=1.4)

Measuring the Pulse

When your arrhythmia-heart starts beating, you have to measure the pulse.
We want to know the heartbeats/min.
But (like many doctors do) you only have to count the heartbeats for 15 sec and then multiply by 4

Final output

Given no input, your code must run for 15 seconds (displaying the beating heart) and then print the heart rate.

Your output should look exactly like this!
(I will run my code 2 times for you to see the different results)

First example run:

Second example run:

you must output one heart
Good Luck!

this is code-golf
shortest answer in bytes wins!

Python [on Windows], 262 bytes

from time import*
import os,random
t,i=time(),0
while time()-t<15:print([""",d88b.d88b,
88888888888
`Y8888888Y'
  `Y888Y'
    `Y'""",""" d8b d8b
888888888
`Y88888P'
 `Y888P'
  `Y8P'
   `Y'"""][i%2]);i+=1;sleep(random.randint(3,14)/10);os.system('cls')
print(i*4)

For linux and macOS use os.system('clear') for 2 more bytes.


Solve a Stack State Diagram A stack state diagram shows how the values on one stack are changed into the other. For example, this is a stack state diagram:

3 0 2 1 0

This means that there is a stack initially containing 3 values (the 3 part). These values are indexed from 0 to 2, with 0 at the top: 2 1 0. The next part 0 2 1 0 describes the final state of the stack: the value that was originally on top of the stack has been copied to the back as well.

These transformations happen on a stack that has support for several data types:

The "value" type, which is what is originally on the stack. This could be a string, integer, etc. but its value does not need to be known.
The "list" type, which is a list containing values of any data type.

To model this transformation, the following operations are permitted:

S: Swap the two values on top of the stack: 2 1 0 → 2 0 1
D: Duplicate the value on top of the stack: 1 0 → 1 0 0
R: Remove the top value on the stack. 2 1 0 → 2 1
L: Turn the top value into a one-element list containing that value: 2 1 0 → 2 1 (0)
C: Concatenate the top two lists on the stack: 2 (1) (0) → 2 (1 0)
U: Place all the values from a list onto the stack: 2 (1 0) → 2 1 0

These are equivalent to the Underload commands ~ : ! a * ^, provided that no other commands are used.

S, D, R, and L can be used with any values on top of the stack, but C and U must have lists on top of the stack to function. A submission whose generated sequences attempt to preform invalid operations (like D on an empty stack or U on a non-list) is wrong and must be punished fixed.

To solve a stack state diagram, find a sequence of commands that will correctly transform the initial stack state into the new one. For example, one solution to 3: 0 2 1 0 is LSLCSLCULSLCLSLDCSC USLCU:

   2 1 0
L  2 1 (0)
S  2 (0) 1
L  2 (0) (1)
C  2 (0 1)
S  (0 1) 2
L  (0 1) (2)
C  (0 1 2)
U  0 1 2
L  0 1 (2)
S  0 (2) 1
L  0 (2) (1)
C  0 (2 1)
L  0 ((2 1))
S  ((2 1)) 0
L  ((2 1)) (0)
D  ((2 1)) (0) (0)
C  ((2 1)) (0 0)
S  (0 0) ((2 1))
C  (0 0 (2 1))
U  0 0 (2 1)
S  0 (2 1) 0
L  0 (2 1) (0)
C  0 (2 1 0)
U  0 2 1 0

Your task is to write a program that takes a stack state diagram and outputs a solution.

Test Cases

2 1 0       ->

3 2 0       -> SR

9           -> RRRRRRRRR

2 0 1 0     -> LSLCDCUR

2 0 1 1     -> SD

6 2         -> RRSRSRSR

5 0 1 2 3 4 -> LSLCSLCSLCSLCU

4 2 0 1 3 2 -> LSLCSLSCSLCULSLSCSLSCLSLDCSCUSLCU

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

Python 3, 84 bytes

lambda n,*s:"DLL"+"L".join(i*"SLSC"+"LSLSCDURLCULCULSC"for i in s[::-1])+n*"SR"+"UR"

Usage:

# Example: 4 2 0 1 3 2 -> LSLCSLSCSLCULSLSCSLSCLSLDCSCUSLCU
>>> f = lambda ...
>>> f(4, 2, 0, 1, 3, 2)
'DLLSLSCSLSCLSLSCDURLCULCULSCLSLSCSLSCSLSCLSLSCDURLCULCULSCLSLSCLSLSCDURLCULCULSCLLSLSCDURLCULCULSCLSLSCSLSCLSLSCDURLCULCULSCSRSRSRSRUR'

Explanation: To start off we duplicate the zero and wrap it in a list:

DL -> 3 2 1 0 (0)

This is our base. Now I will explain a general algorithm that turns ... 1 0 (x) into ... 1 0 (i x) for arbitrary integer i. I will use as an example i = 2, and we have some arbitrary list (x). We start by wrapping our current list (x) into another list:

L -> 3 2 1 0 ((x))

Now we repeat the following sequence i times:

SLSC -> 3 2 1 (0 (x))
SLSC -> 3 2 (1 0 (x))

Now we're ready to insert the 2 into list (x). This goes as follows:

LSLSC -> 3 (2 (1 0 (x)))
DU -> 3 (2 (1 0 (x))) 2 (1 0 (x))
RLCU -> 3 2 (1 0 (x)) 2
LCU -> 3 2 1 0 (x) 2
LSC -> 3 2 1 0 (2 x)

Note that we keep pushing new integers on the left. So the very first (0) we started with stays on the right.

After we have inserted every integer we need into the list we remove the rest of the stack by swapping and removing n time (SR). Finally we unpack our list and delete the first 0 we inserted to start our list (UR).


Fewest disk writes to defrag multiple files Introduction

A disk is a linear container with blocks indexed 0 through size-1.

A file is a named list of block indexes used by that file.

An example filesystem is expressed like this:

15 ALPHA=3,5 BETA=11,10,7

"The disk has 15 blocks, the first block of file ALPHA is the disk block at index 3..."

The disk map could be drawn like this:

Block Index  00  01  02  03  04  05  06  07  08  09  10  11  12  13  14
Contents    |   |   |   |A0 |   |A1 |   |B2 |   |   |B1 |B0 |   |   |   |

A disk is considered defragged when all of the files within it are stored contiguously.

YOUR GOAL:

Emit a shortest sequence of legal moves which will defrag a given disk.

Legal Moves

A move contains three pieces of information: the name of a file, an index of the block in the file to be moved, and the index of the disk block it moves to.

For example

ALPHA:1>4

"Move block 1 of the file ALPHA to block 4 of the disk."

After this move, the example file system is now this

15 ALPHA=3,4 BETA=11,10,7

Block Index  00  01  02  03  04  05  06  07  08  09  10  11  12  13  14
Contents    |   |   |   |A0 |A1 |   |   |B2 |   |   |B1 |B0 |   |   |   |

The previously-inhabited disk block is implicitly cleared. Equivalently, you can view this as swapping two blocks on the disk but one of the blocks in the swap must be empty.

Data may not be destroyed. Files cannot share blocks at any stage and movements must be within range of the disk. The following moves are illegal: ALPHA:0>10 (owned by BETA), ALPHA:3>0 (no such block in ALPHA), ALPHA:0>-1 (no such disk index), ALPHA:0>15 (disk index too big)

Example 1

Solving the above example in full.

ALPHA:0>4
BETA:0>9
BETA:2>11

Files do not have to be adjacent in the solution, just continuous within themselves.

Example 2

Here is a more constrained case

Input:

10 A=1,2,3 B=6,7,8 C=4,5,0

Output:

B:2>9
B:1>8
B:0>7
C:2>6

The progression of this filesystem is:

Block Index  00  01  02  03  04  05  06  07  08  09
Contents    |C2 |A0 |A1 |A2 |C0 |C1 |BO |B1 |B2 |   |
            |C2 |A0 |A1 |A2 |C0 |C1 |BO |B1 |   |B2 |
            |C2 |A0 |A1 |A2 |C0 |C1 |BO |   |B1 |B2 |
            |C2 |A0 |A1 |A2 |C0 |C1 |   |B0 |B1 |B2 |
            |   |A0 |A1 |A2 |C0 |C1 |C2 |B0 |B1 |B2 |

An alternative way to defrag this would by to C:2>9 then bring A down a step, then bring C down a step, then do C:2>5 but this would not be a legal solution because it contains more moves than the alternative.

Representation

You can use any representation for the input as long as it is reasonably close to a basic string. Depending on your language, the input to the first example might be notated as

"15 ALPHA=3,5 BETA=11,10,7"
[15," ","ALPHA","=",3,",",5," ","BETA","=",11,",",10,",",7]
(15,(("ALPHA",(3,5)),("BETA",(11,10,7))))
etc

Similarly, the output can be whatever is convenient for your language as log as it is printed, human-readable, and represents an ordered list of legal moves, each move being described by 1)file-name, 2)file-block-index, 3)new-disk-block-index

"ALPHA:1>6 BETA:2>9"
(0=>(0=>"ALPHA",1=>"1",2=>"6"), 1=>(0=>"BETA",1=>"2",2=>"9"))
["ALPHA",1,6,"BETA",2,9]
etc

Requirements

Your code must accept any size disk, and any number and size of files.

Inputs which do not describe legal initial filesystem states can lead to undefined behaviour.

Your code must produce a shortest moves solution, for any well-defined input.

All moves you produce must be legal; the filesystem must be in a valid state after applying each step you produce.

Your code must terminate for all valid inputs, i.e. it should never get stuck in a loop, the filesystem should be in a distinctly new state after each move is applied.

Where there exists more than one shortest solution, any can be selected as valid.

Shortest code wins. Please post at least one new nontrivial example input and its output with your code.

Python 3, 295 bytes

S,F=eval(input());d=[0]*S;E=enumerate
for n,P in F:
 for j,p in E(P):d[int(p)]=n,j
Z=[(d,())]
while Z:d,p=Z.pop(0);any(e and(e[0],e[1]+1)in d and(S<j+2or(e[0],e[1]+1)!=d[j+1])for j,e in E(d))or print(p).q;{d[j]or exec("D=d[:];D[j]=e;D[k]=0;Z+=(D,p+(e,j)),")for j,_ in E(d)for k,e in E(d)if d[k]}

Try it online!

Another test case
Input:
   7 ALEF=6,4,0 BET=5,1 GIMEL=3

Initial disk state:
   A2 B1 __ G0 A1 B0 A0

Solution:
   ALEF:2>2
   ALEF:0>0
   BET:1>6
   ALEF:1>1

Visualized solution:
   A2 B1 __ G0 A1 B0 A0
   __ B1 A2 G0 A1 B0 A0
   A0 B1 A2 G0 A1 B0 __
   A0 __ A2 G0 A1 B0 B1
   A0 A1 A2 G0 __ B0 B1

Ungolfed version.


Continued Fraction of a Rational Number The continued fraction of a number n is a fraction of the following form:

which converges to n.

The sequence a in a continued fraction is typically written as: [a0; a1, a2, a3, ..., an].

Your goal is to return the continued fraction of the given rational number (positive or negative), whether it is an:

integer x
fraction x/y
decimal x.yz

Input

May be a string representation, or numbers. For fractions, it may be a string, or some native data type for handling fractions, but you may not take it as a decimal.

Output

May be a delimited list or string of the convergents (the resulting numbers). The output does not have to have a semi-colon between a0 and a1, and may use a comma instead.

Note that although [3; 4, 12, 4] and [3; 4, 12, 3, 1] are both correct, only the first will be accepted, because it is simpler.

Examples:

860438      [860438]
3.245       [3; 4, 12, 4]
-4.2        [-5; 1, 4]
-114.7802   [-115; 4, 1, 1, 4, 1, 1, 5, 1, 1, 4]
0/11        [0]
1/42        [0; 42]
2/7         [0; 3, 2]
-18/17056   [-1; 1, 946, 1, 1, 4]
-17056/18   [-948; 2, 4]

Rules

Shortest code wins.
Built-ins are allowed, but I'd also like you to post in the same answer what it would be without built-ins, so that you have to know how to do it.


Tips for golfing in Jellyfish Jellyfish is a two-dimensional esoteric programming language inspired by J and written in Python 3. It was inspired by a challenge on PPCG. The name was suggested in PPCG chat as a combination of Jelly, a golfing language inspired by J, and Fish, a two-dimensional esoteric language.

What general tips do you have for golfing in Jellyfish? I'm looking for ideas which can be applied to code-golf problems and which are also at least somewhat specific to Jellyfish.

Use functions before consumed by operators

When calculating the Catalan number, I used this trick in my Jellyfish answer:

p
%C+
 &
>+i

The > function is taking + as argument, while the & takes the same + as functional argument.

As a result, the + that the > gets is unary, while the & makes + binary to be used by C.


Quickly find length of n-th term of the look-and-say sequence The look and say sequence is an example of a run length encoding sequence.  To get the next term of the sequence one groups the sequence into runs of the same number, each group in the next term then becomes two digits, first the number of terms in the group, followed by the value in the group.  The first term is 1.

Here is how we would calculate the first couple of terms by hand:

  We start with 1, grouping that gives us [1] a single group of 1 1.  Thus our next term is 11.  We group this and get [11] a single group of 2 1s, so our next term is 21.  Grouping again we get [2],[1], we translate each of these groups into 2 digits each, 12,11 and concatenate, 1211.  Group again [1],[2],[11], then convert each group, 11,12,21 and concatenate, 111221.

The first couple terms of the sequence are:

1
11
21
1211
111221
312211
13112221
1113213211

Write a program that when given n as input returns the length of the nth term of this sequence as output.
Programs should have a runtime of O(n log n).

Answers will be scored in bytes with less bytes being better.

GolfScript, 300 chars

~8-:m;'!5?HZi " A 9 "$??HLTZ^`eik 5Z`e <^ $k H ,Sds ?LT /5@MUav I " i ? "5i G  !#+.4;>@K]_cdhjy{| *HCRJD@:64122/42.,,*860-40-0.+9?B<862//?D<7=@:420-/5:60.-20.+./384/162.-HCRJD@:64122/42.,,*)! !""$&&('{32-}/]1,/~:&;:L;:T;]:S;0m>{&m=}{L,,{.49=\71=+}%:V{,(,{).V=\T?S={(V=+}/}%0+:V}m*,,0\{.V=\L=8-*+}/}if

Here's a slightly shorter entry.  Reads a number m from stdin, writes the length of the m-th term in the look-and-say sequence to stdout.

For example, input 50 produces output 894810, while input 1000 produces (after a few seconds):

21465050086246039983937316427688400486337379416867195943208935654503780844828013651860410256502890125611856727316762

I'll post a more detailed explanation of the code later, but basically this also works by repeatedly multiplying a vector with a sparse matrix, encoded as an ASCII string.  Some clever compression tricks, such as leaving out the all-ones superdiagonal of the matrix, are employed.

Ps. Here's a link to an online demo.  The server has been pretty slow lately, though, so if you see an error message about a timeout, try again (or just download the interpreter and run it yourself).

Addendum:  Here's the promised detailed explanation.  First, let me repost the code with whitespace and comments added:

# Parse input, subtract 8, save in variable m:
~ 8- :m;

# This long string encodes all the constants used by the program (I'll describe it below):
'!5?HZi " A 9 "$??HLTZ^`eik 5Z`e <^ $k H ,Sds ?LT /5@MUav I " i ? "5i G  !#+.4;>@K]_cdhjy{| *HCRJD@:64122/42.,,*860-40-0.+9?B<862//?D<7=@:420-/5:60.-20.+./384/162.-HCRJD@:64122/42.,,*)! !""$&&('

# Parse the data string:
# The data consists of several arrays of positive integers, encoded as printable ASCII
# characters and separated by spaces.  (Note that this means that the range of possible
# data values starts from 1, which requires some adjustment below.  Also, the values in
# L are actually shifted up by 8 to avoid having single quotes in the data string.)

{32-}/   # Subtract 32 (ASCII code of space) from each char and dump result on stack.
]        # Collect numbers from stack into an array.
1,/ ~    # Split array on zeros (formerly spaces) and dump pieces on stack.
:&;      # Save topmost piece (canned responses for inputs 1-7) in var &.
:L;      # Save second piece (element lengths) in var L.
:T;      # Save third piece (nonstandard decay targets) in var T.
]:S;     # Collect remaining pieces (nonstd decay sources) in array and save it in S.

# If m < 0, return a precomputed response from &, else run the indented code below:
0 m > { & m = } {
  # Set V to be the initial element abundance vector (1 Hf + 1 Sn):
  # (Note: both L and V have an extra sentinel 0 at the end to avoid overruns below.)
  L,, { . 49= \ 71= + } % :V
  # Update the element abundances m times:
  {
    # Run the following block for all numbers i from 0 to length(V)-2,
    # collecting the results in an array:
    ,(, {
      # Start with the abundance of element i+1 in V (all elements except H decay
      # downwards; the extra 0 at the end of V is needed to avoid a crash here):
      ).V=\
      # If this element is one of the decay targets listed in T, find the corresponding
      # list of source elements in S and add their abundances from V to the total:
      # (If this element is not in T, we just loop over an empty array at the end of S.)
      T? S= { ( V= + } /
    } %
    # Append a new sentinel 0 to the end of the array and save it as the new V:
    0+:V
  } m *
  # Multiply the element abundances from V with their lengths from L and sum them:
  ,,0\{.V=\L=8-*+}/
} if

The key fact that allows this code to work is that, as the look-and-say transformation is repeatedly applied to any string, it eventually splits into substrings which evolve independently, in the sense that we can obtain all the following elements of the look-and-say sequence starting from that string by taking each of the substrings, applying the look-and-say transformation to each of them independently n times and concatenating the results.

Furthermore, in his 1986 article "The Weird and Wonderful Chemistry of Audioactive Decay" (which basically introduced the look-and-say sequence to the world), John Conway proved a remarkable (and, for this challenge, crucial) result which he called the "cosmological theorem":

  Cosmological theorem (Conway): There is a set of 92 finite strings of numbers 1–3 (which Conway named after the chemical elements; see table here), and two infinite families of strings each consisting of a fixed prefix followed by some number higher than 3 (these can only appear if the initial string contained number higher than 3 or sequences of more than 3 identical numbers), such that, after at most 24 applications of the look-and-say transformation, any string splits into a chain of such elements, each of which thereafter evolves independently (and splits into further elements).

Thus, to determine the length of a string sufficiently far in the look-and-say sequence, it's sufficient to know how many times each element appears in it.  And, since each element evolves independently, knowing these "elemental abundances" is also sufficient for calculating the corresponding abundances of the next string in the sequence, and so on.

As it happens, the look-and-say sequence starting from the string 1 splits into two Conway elements (Hf72 = 11132 and Sn50 = 13211) after just seven iterations.  Thus, thereafter, we only need to keep track of the abundances of the 92 "common" elements (as the two families of "transuranic" elements cannot arise from common elements).

Mathematically, we can treat the elemental abundances as a vector of length 92.  Calculating the abundances in the next step of the look-and-say sequence is then just equivalent to multiplying this vector with a 92 × 92 matrix, which is what r.e.s.'s solution does literally.

In fact, r.e.s.'s solution actually tracks the abundance of each element multiplied with its length (i.e. the "total mass" of that element in the string), adjusting the matrix accordingly, so that the total length of the string is given simply by adding the numbers in the abundance vector together.  However, I did not find that a particularly convenient representation for code golf.  (It was convenient for Nathaniel Johnston's derivation of Conway's polynomial, since it encodes the lengths into the matrix and thus gives the right eigenvalue for the asymptotic growth rate, but we don't care about that here.)

Instead, I just track the raw abundances of the elements, and only multiply them with the lengths at the end.  This has, combined with the convenient fact that none of the decay products of any element contain more than one copy of any element, means that the entries of the transition matrix are just zeros and ones.  Also, by far most of them are, in fact, zeros (in math jargon, the matrix is sparse), so I can save a lot of space by only storing the indices of those entries which are ones.

Also, in his article, Conway ordered the elements such that (except for H1 = 22, which is a fixed point of the look-and-say transformation), each element decays to the next lower element in the sequence (and possibly some others).
In fact, most elements decay only to the next lower elements.  Thus, by using Conway's ordering of the elements, I can hardcode this "standard decay" as part of the iteration, so that I only need to store the matrix entries corresponding to the other, "nonstandard" decays, saving even more space.

(In fact, what I actually do, for reasons mostly to do with how GolfScript's array operations work, is store one array listing the matrix rows containing non-zero entries (i.e. the elements which are produced in nonstandard decays) and another array of arrays listing, for each of these rows, the columns where the non-zero entries occur (i.e. the elements which produce these elements in such decays).  See the code and comments above for how these arrays are actually used to calculate the updated element abundances.)

The final space-saving trick I used was to encode all these arrays as strings of ASCII characters.  Conveniently, there are 95 printable ASCII characters from space (32) to ~ (126), and the largest value that appears in any of the arrays is 92, so they fit very well.  One extra tweak I made was to shift the values in the element length array (which only go up to 42 anyway) up by 8 so that I could avoid the character ' (39) and thus store my data in a single quoted string without having to add any backslash escape characters.

There are some other minor optimizations too, but those are just standard GolfScript coding tricks.  I should note that the actual code is not all that carefully optimized — it's quite possible that it could be golfed down further.

In any case, despite the inherent slowness of a double-interpreted language like GolfScript, the code runs quite fast and scales well: computing the length of the 10,000th string in the look-and-say sequence takes about 1.5 minutes on my computer.

Conveniently, GolfScript stores all numbers as arbitrary-length integers (bignums), so I didn't have to do anything special to make it produce exact results even for large inputs.
The expected time complexity of this program is O(n log n) (as the element abundances grow linearly with n, and bignum addition takes O(log n) time), and the actual runtime seems to fit that prediction pretty well, as the graph below shows:

(Time is in seconds; for what it's worth, the green curve is given by y = (a x log(b + x) + c) / x, where a = 0.00106462026133545, b = 2720.25843721031 and c = -0.0401630789530016.  The spike on the left mainly comes from the roughly constant runtimes for n < 8, which become relatively large when divided by small n.  I did not include it in the curve fit.)


Tweetable Mathematical Art Integer math can generate amazing patterns when laid out over a grid. Even the most basic functions can yield stunningly elaborate designs!

Your challenge

Write 3 Tweetable (meaning 140 characters or less) function bodies for the red, green, and blue values for a 1024x1024 image.

The input to the functions will be two integers i (column number for the given pixel) and j (row number for the given pixel) and the output will be an unsigned short between 0 and 1023, inclusive, which represents the amount of the given color present in the pixel (i,j).

For example, the following three functions produce the picture below:

/* RED */
    return (unsigned short)sqrt((double)(_sq(i-DIM/2)*_sq(j-DIM/2))*2.0);
/* GREEN */
    return (unsigned short)sqrt((double)(
        (_sq(i-DIM/2)|_sq(j-DIM/2))*
        (_sq(i-DIM/2)&_sq(j-DIM/2))
    ));
/* BLUE */
    return (unsigned short)sqrt((double)(_sq(i-DIM/2)&_sq(j-DIM/2))*2.0);

/* RED */
    return i&&j?(i%j)&(j%i):0;
/* GREEN */
    return i&&j?(i%j)+(j%i):0;
/* BLUE */
    return i&&j?(i%j)|(j%i):0;

The Rules

Given this C++ code, substitute in your functions. I have provided a few macros and have included the  library, and you may include complex.h. You may use any functions from these libraries and/or my macros. Please do not use any external resources beyond this.
If that version isn't working for you, make sure you're compiling with:

g++ filename.cpp -std=c++11

If that doesn't work, please use the alternate version using unsigned chars instead of unsigned shorts.

Michaelangelo has provided a cleaned up 24-bit or 48-bit color output version.

You may implement your own version in another language, but it must behave in the same way as the provided C++ version, and only functions from C++'s built-ins, the  library, or the provided macros may be used to make it fair.
Post only your three function bodies - please don't include my code in your post
Please include either a smaller version or an embedded copy of your image. They are made into a ppm format and may need to be converted to another for proper viewing on stackexchange.
Function bodies (not including signature) must be 140 characters or less.
This is a popularity contest - most votes wins

Table cloths
Flat
I started out putting a plaid/gingham pattern into perspective like a boundless table cloth:
unsigned char RD(int i,int j){
    float s=3./(j+99);
    return (int((i+DIM)*s+j*s)%2+int((DIM*2-i)*s+j*s)%2)*127;
}
unsigned char GR(int i,int j){
    float s=3./(j+99);
    return (int((i+DIM)*s+j*s)%2+int((DIM*2-i)*s+j*s)%2)*127;
}
unsigned char BL(int i,int j){
    float s=3./(j+99);
    return (int((i+DIM)*s+j*s)%2+int((DIM*2-i)*s+j*s)%2)*127;
}

Ripple
Then I introduced a ripple (not strictly correct perspective, but still in 140 characters):
unsigned char RD(int i,int j){
    float s=3./(j+99);
    float y=(j+sin((i*i+_sq(j-700)*5)/100./DIM)*35)*s;
    return (int((i+DIM)*s+y)%2+int((DIM*2-i)*s+y)%2)*127;
}
unsigned char GR(int i,int j){
    float s=3./(j+99);
    float y=(j+sin((i*i+_sq(j-700)*5)/100./DIM)*35)*s;
    return (int((i+DIM)*s+y)%2+int((DIM*2-i)*s+y)%2)*127;
}
unsigned char BL(int i,int j){
    float s=3./(j+99);
    float y=(j+sin((i*i+_sq(j-700)*5)/100./DIM)*35)*s;
    return (int((i+DIM)*s+y)%2+int((DIM*2-i)*s+y)%2)*127;
}

Colour
Then I made some of the colours more fine grained to give detail on a wider range of scales, and to make the picture more colourful...
unsigned char RD(int i,int j){
    float s=3./(j+99);
    float y=(j+sin((i*i+_sq(j-700)*5)/100./DIM)*35)*s;
    return (int((i+DIM)*s+y)%2+int((DIM*2-i)*s+y)%2)*127;
}
unsigned char GR(int i,int j){
    float s=3./(j+99);
    float y=(j+sin((i*i+_sq(j-700)*5)/100./DIM)*35)*s;
    return (int(5*((i+DIM)*s+y))%2+int(5*((DIM*2-i)*s+y))%2)*127;
}
unsigned char BL(int i,int j){
    float s=3./(j+99);
    float y=(j+sin((i*i+_sq(j-700)*5)/100./DIM)*35)*s;
    return (int(29*((i+DIM)*s+y))%2+int(29*((DIM*2-i)*s+y))%2)*127;
}

In motion
Reducing the code just slightly more allows for defining a wave phase P with 2 decimal places, which is just enough for frames close enough for smooth animation. I've reduced the amplitude at this stage to avoid inducing sea sickness, and shifted the whole image up a further 151 pixels (at the cost of 1 extra character) to push the aliasing off the top of the image. Animated aliasing is mesmerising.
unsigned char RD(int i,int j){
#define P 6.03
float s=3./(j+250),y=(j+sin((i*i+_sq(j-700)*5)/100./DIM+P)*15)*s;return (int((i+DIM)*s+y)%2+int((DIM*2-i)*s+y)%2)*127;}

unsigned char GR(int i,int j){
float s=3./(j+250);
float y=(j+sin((i*i+_sq(j-700)*5)/100./DIM+P)*15)*s;
return (int(5*((i+DIM)*s+y))%2+int(5*((DIM*2-i)*s+y))%2)*127;}

unsigned char BL(int i,int j){
float s=3./(j+250);
float y=(j+sin((i*i+_sq(j-700)*5)/100./DIM+P)*15)*s;
return (int(29*((i+DIM)*s+y))%2+int(29*((DIM*2-i)*s+y))%2)*127;}


Concatenate the Cats There is a sentence with many cats:

there is a cat house where many cats live. in the cat house, there is a cat called alice and a cat called bob. in this house where all cats live, a cat can be concatenated into a string of cats. The cat called alice likes to purr and the cat called bob likes to drink milk.

The Task

Concatenate (_) all pairs of neighbouring words in the sentence and place each in between the any such pair if that pair occurs more than once in the sentence. Note that overlapping counts, so blah blah occurs twice in blah blah blah.

For example, if the cat occurs more then once, add the concatenated words in between them like this: the the_cat cat

Example Output

there there_is is is_a a a_cat cat cat_house house where many cats live. in the the_cat cat cat_house house,
there there_is is is_a a a_cat cat cat_called called called_alice alice and a a_cat cat cat_called called called_bob bob.
the the_cat cat cat_called called called_alice alice likes likes_to to purr and the the_cat cat cat_called called called_bob bob likes likes_to to drink milk.

Some more examples:

milk milk milk       milk milk_milk milk milk_milk milk
a bun and a bunny    a bun and a bunny
milk milk milk.      milk milk milk.
bun bun bun bun.     bun bun_bun bun bun_bun bun bun.

Notes

All utf-8 characters are allowed. Meaning that punctuations are part of the input.
Punctuation becomes part of the word (e.g., with in the house, is a cat the word house, includes the comma)

Python 2, 99 107 103 102 bytes

def f(s):S=s.split();T=zip(S,S[1:]+[s]);return' '.join(x+(' '+x+'_'+y)*(T.count((x,y))>1)for x,y in T)

Try it online!

Fixed the milk milk milk style edge cases.