text:
Incrementing Gray Codes
Introduction
A Gray Code is an alternative to binary representation in which a number is incremented by toggling only one bit, rather than a variable amount of bits. Here are some gray codes along with their decimal and binary equivalents:
 decimal | binary | gray
-------------------------
       0 |      0 |    0
-------------------------
       1 |      1 |    1
-------------------------
       2 |     10 |   11
-------------------------
       3 |     11 |   10
-------------------------
       4 |    100 |  110
-------------------------
       5 |    101 |  111
-------------------------
       6 |    110 |  101
-------------------------
       7 |    111 |  100
-------------------------
       8 |   1000 | 1100
-------------------------
       9 |   1001 | 1101
-------------------------
      10 |   1010 | 1111
-------------------------
      11 |   1011 | 1110
-------------------------
      12 |   1100 | 1010
-------------------------
      13 |   1101 | 1011
-------------------------
      14 |   1110 | 1001
-------------------------
      15 |   1111 | 1000

Cyclic Bit Pattern of a Gray Code
Sometimes called "reflected binary", the property of changing only one bit at a time is easily achieved with cyclic bit patterns for each column starting from the least significant bit:
bit 0: 0110011001100110011001100110011001100110011001100110011001100110
bit 1: 0011110000111100001111000011110000111100001111000011110000111100
bit 2: 0000111111110000000011111111000000001111111100000000111111110000
bit 3: 0000000011111111111111110000000000000000111111111111111100000000
bit 4: 0000000000000000111111111111111111111111111111110000000000000000
bit 5: 0000000000000000000000000000000011111111111111111111111111111111

...and so on.
Objective
Given a non-padded input string of a gray code, increment the gray code by alternating a single character in the sequence or prepending a 1 (when incrementing to the next power of 2), then output the result as a non-padded gray code.
Caveats

Do not worry about taking 0 or an empty string as input.
The lowest input will be 1, and there is no upper-bound to the string length other than memory limitations imposed by the environment.
By non-padded string, I mean there will be no leading or trailing whitespace (other than an optional trailing newline), and no leading 0s in the input or output.

I/O formats
The following formats are accepted form for input and output, but strings are encouraged over other formats:

most significant "bit" first
non-padded character array or string of ASCII '1's and '0's
non-padded integer array of 1s and 0s
non-padded boolean array

What's not allowed:

least significant "bit" first
decimal, binary or unary integer
fixed-length data-structure
character array or string of non-printable ASCII indices 1 and 0

Tests
input -> output
1 -> 11
11 -> 10
111 -> 101
1011 -> 1001
1111 -> 1110
10111 -> 10110
101100 -> 100100
100000 -> 1100000

More tests can be added by request.
Criteria
This is code-golf, so shortest program in bytes wins! All ties will be broken by favoring earlier submissions; standard loopholes apply. The best submitted answer will be accepted October 9th, 2016, and updated whenever better answers are given.

Related. Related.

Can we take input as a number?

Less obviously, also related.

@xnor No. That sort of defeats the purpose of the string manipulation challenge.

According to your table (and wikipedia) 1011 is incremented to 1001 and not 1010 as in the testcases.

@Laikoni good catch, thank you. Corrected.

Can we take an array of zeros and ones instead of a string?

@LuisMendo, do you mean a boolean array or an integer array of 1s and 0s? Both are acceptable, I'm just curious which one you meant. But please make your program or function have a reasonable output: either equivalent as input, or as specified in the question.

@PatrickRoberts I meant integer array. Thanks for the reply!

Can I take both input and output reversed, e.g. 0011 for 8

Can I take input and output as a string of unprintable ASCII codes 0 and 1

@TonHospel I'm gonna say no, just because that makes it harder to verify code. You might as well use an integer array if you're going to do that.

Is there a maximum length of input that our program will have to process? I too am curious about whether we can take input reversed.

@1000000000 To demonstrate that the program can process an arbitrarily long string, make sure it works for a string input at least 65 bytes long. Also, no. It must be most significant bit first.

@PatrickRoberts and it's okay if it behaves unexpectedly for a string longer than 65 bytes?

@1000000000 No. As I stated in the challenge, the only limitation should be the amount of memory your program is able to allocate to process the string. If your run exits with an out of memory error in the case the string is too long, that is the only acceptable "unexpected behavior." In short, don't hardcode an upper-bound.

@TonHospel sorry I didn't see your question about reversed I/O. As I told 1000000000 my answer is no.

@TonHospel I just thought of something though. If your input is stack-based and each bit (or character) is pushed separately, you'd have access to the least significant bit first, and it would satisfy my requirement of most significant bit first. Assuming FILO stack.

Jelly, 10 8 bytes
Thanks to Dennis for saving 2 bytes.
^\Ḅ‘^H$B

Input and output are lists of 0s and 1s.
Try it online!
Explanation
The inverse of the Gray code is given by A006068. Using this we don't need to generate a large number of Gray codes to look up the input. One classification of this sequence given on OEIS is this:
a(n) = n XOR [n/2] XOR [n/4] XOR [n/8] ...

Where the [] are floor brackets. Consider the example of 44 whose binary representation is 101100. Dividing by 2 and flooring is just a right-shift, chopping off the least-significant bit. So we're trying to XOR the following numbers
1 0 1 1 0 0
  1 0 1 1 0
    1 0 1 1
      1 0 1
        1 0
          1

Notice that the nth column contains the first n bits. Hence, this formula can be computed trivially on the binary input as the cumulative reduction of XOR over the list (which basically applies XOR to each prefix of the list and gives us a list of the results).
This gives us a simple way to invert the Gray code. Afterwards, we just increment the result and convert it back to the Gray code. For the latter step we use the following definition:
a(n) = n XOR floor(n/2)

Thankfully, Jelly seems to floor the inputs automatically when trying to XOR them. Anyway, here is the code:
^\          Cumulative reduce of XOR over the input.
  Ḅ         Convert binary list to integer.
   ‘        Increment.
    ^H$     XOR with half of itself.
       B    Convert integer to binary list.

You don't need the Ḟ$; bitwise operators cast to int.

@Dennis Thanks, I discovered that while writing up. :)

@MartinEnder Is the integer it converts to internally a big integer?

@PatrickRoberts yes, if necessary - it's Python under the hood.

Nice analysis and explanation.

Congratulations on the shortest answer

Perl, 27 25 bytes
Includes +1 for -p
Give input string on STDIN, e.g.
gray.pl <<< 1010

gray.pl:
#!/usr/bin/perl -p
s%(10*\K1(\K0)*)*%1-$&%e

Perl has no cheap infinite-precision integers. So directly toggle the right bit which is the one just before where the last odd-numbered 1 would be.

Wow, \G really makes things easy for you!

On the other hand, \K makes things even easier for you.

Haaaaa... Now I want to see the \G implementation as well.

@carusocomputing You can see older versions of a submission by clicking on the edited link

JavaScript (ES6), 58 bytes
s=>s.replace(s.split`1`.length%2?/.$/:/.?(?=10*$)/,c=>1-c)

Directly toggles the appropriate bit. Explanation: As shown in MartinEnder♦'s answer, each bit in a decoded Gray code is the cumulative XOR, or parity, of itself and the bits to its left. We then need to increment the number which causes a carry ripple that toggles all the rightmost 1 bits to 0 and then the next 0 bit to 1. Re-encoding results in a code with just that one 0 bit position toggled. If the parity of all the 1 bits is even, then the rightmost bit is 0 and we therefore just toggle the last bit. If the parity of all the 1 bits is odd, then the rightmost bits are 1, and we need to find the last 1 bit. This is now the last of the carried bits, so the bit we need to toggle is the next bit from the right.

Very nice method. Is the first ? in /.?(?=10*$)/ really required? Oh, nevermind. Yes it is. :-)

Haskell, 118 115 108 bytes
g 0=[""]
g n|a<-g$n-1=map('0':)a++map('1':)(reverse a)
d=dropWhile
f s=d(=='0')$(d(/='0':s)$g$1+length s)!!1

Try it on Ideone.
Naive approach: g generates the set of all gray codes with length n (with 0-padding), f calls g with length(input)+1, removes all elements until 0<inputstring> is found and returns the next element (truncating a possibly leading 0).

Good first answer! I hope we can get some more efficient ones soon.

JavaScript (ES6), 53 bytes (non-competing)
A recursive function which builds all gray codes until the input is found, then stops at the next iteration.
The highest possible input depends on the browser recursion limit (about 13 bits in Firefox and 15 bits in Chrome).

f=(s,n=1)=>(b=(n^n/2).toString(2),s)?f(b!=s&&s,n+1):b

console.log(f("1"));      // -> 11
console.log(f("11"));     // -> 10
console.log(f("111"));    // -> 101
console.log(f("1011"));   // -> 1001
console.log(f("1111"));   // -> 1110
console.log(f("10111"));  // -> 10110
console.log(f("101100")); // -> 100100
console.log(f("100000")); // -> 1100000

I'm afraid this submission doesn't qualify, since the method does not work for unbounded string lengths. Please change to non-competitive if you want to keep this answer on here.

@PatrickRoberts - Sure. That makes sense.

@PatrickRoberts Really? How does a recursion limit not fall under "memory limitations imposed by the environment."?

@sanchises I was referring to heap memory, but more to the point, this program recurses for every possible gray code up to the one being tested, which is extremely inefficient. Technically this could be submitted as "Node.js 6.5" and have --harmony added for penalty bytes in order to have access to tail-call recursion optimization, which appears to be possible here.

@sanchises Looking over my reply, that was a poor argument. The main issue is that the limitation isn't imposed by the environment, it's imposed by the algorithm. There are other answers which recurse for every bit rather than for every incremental value, and I find those to be more acceptable since it works for a much wider range of values.

@PatrickRoberts I disagree. The algorithm itself does not impose a fundamental limit. It's inefficient, yes, but I feel that efficiency is not a requirement for [tag:code-golf]. I don't think some thing that is less or "more acceptable" is a good criterion for disqualifying an entire answer. Personally, I would let this one go. Judging by your challenge description, it seems you fell for this trap - it seems that you wanted people to work on 'string level' rather than 'number' level.

@sanchises That's why I clarified my statement. Yes I agree efficiency is not a criteria for whether or not this is an acceptable answer. The problem is that this doesn't satisfy the acceptable level of "arbitrary precision" that I specified in the criteria. The answerer agreed with my claim, if you don't then please take it up with meta rather than complaining about it here.

MATL, 18 bytes
ZBtE:t2/kZ~tb=fQ)B

Try it online! Or verify all test cases.
Explanation
Let a(n) denote the sequence of integers corresponding to Gray codes (OEIS A003188). The program uses the characterization a(n) = n XOR floor(n/2), where XOR is bit-wise.
Essentially, the code converts the input to an integer a0, finds that integer in the sequence, and then selects the next term. This requires generating a sufficiently large number of terms of the sequence a(n). It turns out that 2·a0 is sufficiently large. This stems from the fact that the Gray code a(n) never has more binary digits than n.
Let's take input '101' as an example.
ZB      % Input string implicitly. Convert from binary string to integer
        %   STACK: 5
t       % Duplicate
        %   STACK: 5, 5
E       % Multiply by 2. This is the number of terms we'll generate from the sequence
        %   STACK: 5, 10
:       % Range
        %   STACK: 5, [1 2 3 4 5 6 7 8 9 10]
t       % Duplicate
        %   STACK: 5, [1 2 3 4 5 6 7 8 9 10], [1 2 3 4 5 6 7 8 9 10]
2/k     % Divide by 2 and round down, element-wise
        %   STACK: 5, [1 2 3 4 5 6 7 8 9 10], [0 1 1 2 2 3 3 4 4 5]
Z~      % Bit-wise XOR, element-wise
        %   STACK: 5, [1 3 2 6 7 5 4 12 13 15]
t       % Duplicate
        %   STACK: 5, [1 3 2 6 7 5 4 12 13 15], [1 3 2 6 7 5 4 12 13 15]
b       % Bubble up
        %   STACK: [1 3 2 6 7 5 4 12 13 15], [1 3 2 6 7 5 4 12 13 15], 5
=       % Equality test, element-wise
        %   STACK: [1 3 2 6 7 5 4 12 13 15], [0 0 0 0 0 1 0 0 0 0]
f       % Find: yield (1-based) index of nonzero values (here there's only one)
        %   STACK: [1 3 2 6 7 5 4 12 13 15], 6
Q       % Increase by 1
        %   STACK: [1 3 2 6 7 5 4 12 13 15], 7
)       % Apply as index
        %   STACK: 4
B       % Convert to binary array
        %   STACK: [1 0 0]
        % Implicitly display

I notice the output is space-delimited characters... is it printing some sort of array?

@PatrickRoberts Yes, exactly. I assumed it's acceptable, is it?

I'll accept it as-is. I've already loosened my requirements on I/O format, so there's no point in making it more strict again. Nice job.

CJam (19 bytes)
{_2b__(^@1b1&*)^2b}

Online demo. This is an anonymous block (function) from bit array to bit array, which the demo executes in a loop.
It works on the simple principle that if the number of set bits is even we should toggle the least significant bit, and otherwise we should toggle the bit to the left of the least significant set bit. Actually identifying that bit turns out to be much easier using bit hacks on an integer than using the list of bits.
Dissection
{         e# Declare a block:
  _2b     e#   Convert the bit array to a binary number
  __(^    e#   x ^ (x-1) gives 1s from the least significant set bit down
  @1b1&   e#   Get the parity of the number of set bits from the original array
  *       e#   Multiply: if we have an even number of set bits, we get 0;
          e#   otherwise we have 2**(lssb + 1) - 1
  )^      e#   Increment and xor by 1 or 2**(lssb + 1)
  2b      e#   Base convert back to a bit array
}

Working solely with the bit array, I think it's necessary to reverse it: working with the left-most 1 is much easier than the right-most. The best I've found so far is (24 bytes):
{W%_1b)1&1$+1#0a*1+.^W%}

Alternative approach (19 bytes)
{[{1$^}*]2b)_2/^2b}

This converts from Gray code to index, increments, and converts back to Gray code.

Retina, 25 bytes
^(10*10*)*
$1:
1:
0
.?:
1

I feel sure there should be a better way of doing this...

Do you actually need the ^ ?

@TonHospel The regex tried to match everywhere without it. (Replace mode defaults to a global replacement.)

05AB1E, 12 bytes
Uses CP-1252 encoding.
CÐ<^¹SOÉ*>^b

Try it online!
Explanation
Example for input 1011.
C              # convert to int (bigint if necessary)
               # STACK: 11
 Ð             # triplicate
               # STACK: 11, 11, 11
  <            # decrease by 1
               # STACK: 11, 11, 10
   ^           # XOR
               # STACK: 11, 1
    ¹          # push first input
               # STACK: 11, 1, 1011
     S         # split to list
               # STACK: 11, 1, [1,0,1,1]
      O        # sum
               # STACK: 11, 1, 3
       É       # mod 2
               # STACK: 11, 1, 1
        *      # multiply
               # STACK: 11, 1
         >     # increase by 1
               # STACK: 11, 2
          ^    # XOR
               # STACK: 9
           b   # convert to binary
               # STACK: 1001
               # implicitly print top of stack

Batch, 199 197 bytes
@echo off
set/ps=
set r=
set t=%s:0=%
if 1%t:11=%==1 goto g
:l
set b=%s:~-1%
set s=%s:~,-1%
set r=%b%%r%
if %b%==0 goto l
if 0%s%==0 set s=0
:g
set/ab=1-%s:~-1%
echo %s:~,-1%%b%%r%

Reads input from STDIN into variable s. Removes the 0s and does a parity check on the 1s and if there are an odd number it strips the rightmost 0s in a loop, stopping when it strips a 1. s therefore contains the even parity prefix and r the rest of the string. s is set to zero if it was blank so that its last digit can be toggled, and then everything is concatenated.

C++, 205 bytes
#include <string>
std::string g(std::string s){int i,z;if(s=="1")return"11";for(i=z=0;i<s.length();i++)if(s[i]=='1')z++;i--;if(z%2){char c=s[i];s.erase(i);s=g(s);s+=c;}else{s[i]=s[i]==49?48:49;}return s;}

Description: Even numbers have even number of ones. Variable z counts ones; if z is even (z mod 2 = z%2 = 0 - else branch), alter the last bit; if z is odd, call this function again without the last character and calculate new value, then append the last character afterwards.
Click here to try it for the test cases.

Thanks for your submission. If you could provide a short description of your approach and a link to an online compilation of this as a demo, I'd really appreciate that.

@PatrickRoberts Added the link and the description as you requested.

Python 2.7, 68 characters
def f(s):i=long(s,2);print bin(i^(1,(i&-i)<<1)[s.count('1')&1])[2:]

Python 3, 68 characters
def f(s):i=int(s,2);print(bin(i^(1,(i&-i)<<1)[s.count('1')&1])[2:])

This function converts the given binary string to an integer then xor the last bit if the number of set bits in the original string is even, or its swaps the bit to the left of the rightmost set bit if the number of set bits in the original string is odd. Then it converts the result to a binary string and removes the 0b boolean prefix.

You can save 1 byte by removing the space after def f(s): and (assuming Python 2) another by using print instead of return.

@ElPedro Thanks, I also applied a condition trick and factored out the left-hand size of a xor to save a few additional characters :)

Just saw that. Nice answer :-)

Um.. checking python documentation, it looks like int() generates a 32 bit integer, although my requirement is for you to increment any length string. I'm not sure that this qualifies as a valid submission

@PatrickRoberts I'll check later. long instead of int might solve the problem.

@Morwenn It would, yes.

Actually, 20 19 13 bytes
Based on Martin Ender's Jelly answer with my own version of "cumulative reduce of XOR over the input". Golfing suggestions welcome. Try it online!
σ1♀&2@¿u;½≈^├

Ungolfing
      Implicit input a as a list, such as [1,0,1,1,0,0].
σ     Get the cumulative sums of a.
1♀&   Map x&1 (equivalent to x%2) over every member of the cumulative sum.
2@¿   Convert from binary to decimal.
u     Increment x.
;½≈   Duplicate and integer divide by 2.
^     XOR x and x//2.
├     Convert to binary to obtain our incremented Gray code.
      Implicit return as a string, such as "100100".

J, 38 bytes
[:#:@(22 b.<.@-:)@>:@#.[:22 b./[:#:#.\

Try it online!
This is essentially Martin's algorithm in J.
Note that 22 b. is XOR.
                                    [: #: #.\   Creates the prefixes of the input
                                                converts to a number, then converts
                                                back to binary.  Needed to get the
                                                padding on the left.

                          [: 22 b./             Reduce the rows of the resulting
                                                matrix with XOR, giving us the
                                                normal binary
                      @#.                       Convert to int and...
                   @>:                          Increment and...
      (22 b. <.@-:)                             XOR that with its own floored half
[: #:@                                          And turn the result back to binary

Nice job, dude!


text:
Generate groups for in-class work
In a smallish class, some lectures are set aside for working in groups. The instructors don't want people to group themselves together with the same people every time; instead, they create the groups beforehand, trying to make sure that all students work with one another as equally as possible. Your job is to write a program that makes student groups for one class, given all the groups in previous classes, in a way that minimizes the same people working together often.
Format for groups for a single class
Students in the class will be numbered as consecutive integers, starting at 1 (or 0 if you prefer). The set of groups for a single class (hereafter called a "day of groups") will be a list of lists, or any reasonable alternative. Every group must have size 3 or 4; and the number of 3-person groups must be as small as possible. For example, in a 15-student class, the following is a valid day of groups:
{{1,8,10,15},{2,7,9},{3,6,12,13},{4,5,11,14}}

But five 3-student groups is invalid. Of course, no student can be in two different groups in a single day of groups.
Input structure
The input will consist of one or more days of groups, each in the format described above; the days of groups can be separated from each other by commas, newlines, or anything reasonable. These represent the student groups that have already taken place in the past. You may not assume that every student was present in every day of groups—students are sometimes absent! For example, the following is a valid input (consisting of three days of groups) for a 13-person class:
{{1,2,3,4},{5,6,7},{8,9,10},{11,12,13}}
{{1,3,5,7},{9,11,13,2},{4,6,8,10}}
{{8,6,7,5},{3,10,9,13},{12,11,1}}

You may also include, if you wish, the number of students in the class (13 in this case) as an additional explicit input. Otherwise you may assume that the number of students equals the largest integer appearing in the input (assuming you 1-index as I am; for 0-indexed, the number of students equals 1 + the largest integer appearing in the input).
Output structure
The output will be a single day of groups, representing the chosen group assignments for the next day of groups, containing all of the students in the class. You may write a program, function, snippet, or other useful code to accomplish this, and take input and generate output in any reasonable way. The goal of the code is to generate a new day of groups with as small a "score" as possible, as described below.
Given an input (representing the past days of groups), the "score" of a proposed output (representing the new day of groups) is calculated as follows:

For every pair of students who are in the same group, count how many times they have been together in groups before; that number (0 or more) is added to the score.
For every student in a 3-person group, count how many times they have been in a 3-person group in the past; that number (0 or more) is also added to the score.

For example, suppose the input for a 7-student class is given by
{{1,2,3,4},{5,6,7}}
{{1,3,5,7},{2,4,6}}

For the proposed output
{{1,6,7},{2,3,4,5}}

the score would be calculated as follows:

1 and 6 have never been in the same group before, so +0 to the score
1 and 7 have been in the same group once before, so +1 to the score
6 and 7 have been in the same group once before, so +1 to the score
2 and 3 have been in the same group once before, so +1 to the score
2 and 4 have been in the same group twice before, so +2 to the score
2 and 5 have never been in the same group before, so +0 to the score
3 and 4 have been in the same group once before, so +1 to the score
3 and 4 have been in the same group once before, so +1 to the score
4 and 5 have never been in the same group before, so +0 to the score
1 has never been in a 3-student group before, so +0 to the score
6 has been in a 3-student group twice before, so +2 to the score
7 has been in a 3-student group once before, so +1 to the score

Therefore the total score for that proposed day of groups is 10.
However, that proposed day of groups is not optimal—several possible days of groups have a score of 8, including:
{{1,2,5,6},{3,4,7}}

Input/output size and runtime
You should assume that there are at least 6 students in the class, and you may assume that there are at most 30 students in the class. You may also assume that there will be at least 1 and at most 100 days of groups in the input.
Evaluation criteria
This challenge is popularity contest. While I can't control the votes of the population, to me the ideal solution will contain:

code that computes an output day of groups with the minimal score possible given the input, not just one with a "good" score;
code that runs quickly (for example, in 10 seconds or less on a class of size 20);
a justification for why the code produces the minimal possible score;
a link to an online implementation of the code.

Example inputs and outputs
Input #1:
{{1,2,3,4},{5,6,7,8},{9,10,11,12}}

Output #1: there are many configurations with a score of 3, one of which is:
{{1,2,5,9},{3,6,7,10},{4,8,11,12}}

Input #2:
{{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15}}
{{1,5,9,13},{2,6,10,14},{3,7,11,15},{4,8,12}}
{{1,8,10,15},{2,7,9},{3,6,12,13},{4,5,11,14}}
{{1,7,12,14},{2,8,11,13},{3,5,10},{4,6,9,15}}

Output #2, with a score of 0, is unique in this case (up to reordering within each list):
{{1,6,11},{2,5,12,15},{3,8,9,14},{4,7,10,13}}

Input #3:
{{1,2,3},{4,5,6},{7,8,9}}
{{1,2,4},{3,5,8},{6,7,9}}
{{1,5,6},{2,3,9},{4,7,8}}
{{1,6,8},{2,4,9},{3,5,7}}
{{1,3,7},{2,6,8},{4,5,9}}
{{1,8,9},{2,5,7},{3,4,6}}
{{1,4,7},{2,5,8},{3,6,9}}

Output #3, with a score of 72, is also unique (up to reordering):
{{1,5,9},{2,6,7},{3,4,8}}

You have an objective winning criteria in the scoring of the groups, so why not make this a [tag:code-challenge] where the score is the sum of scores across various test cases? Also, it's intended for challenges to stay in the Sandbox for more than two days. You got 0 votes and 0 comments - that does not mean the challenge is ready for main.

There are a lot of challenge writers that are way better at this than me, but speaking as one who mainly contribute with challenges (+20 challenges with a +20 score): The Sandbox isn't that good... I'm not saying that this one was ready to be posted, only that how a question was received in the Sandbox is not a good indication for how it will be received on main.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Natural Pi #0 - Rock
Goal
Create a program/function that takes an input N, check if N random pairs of integers are relatively prime, and returns sqrt(6 * N / #coprime).
TL;DR
These challenges are simulations of algorithms that only require nature and your brain (and maybe some re-usable resources) to approximate Pi. If you really need Pi during the zombie apocalypse, these methods don't waste ammo! There are eight more challenges to come. Checkout the sandbox post to make recommendations.
Simulation
What are we simulating? Well, the probability that two random integers are relatively prime (ie coprime or gcd==1) is 6/Pi/Pi, so a natural way to calculate Pi would be to scoop up two buckets (or handfuls) of rocks; count them; see if their gcd is 1; repeat. After doing this a couple lot of times, sqrt(6.0 * total / num_coprimes) will tend towards Pi. If calculating the square-root in post-apocalyptic world makes you nervous, don't worry! There is Newton's Method for that.
How are we simulating this?

Take input N
Do the following N times:

Uniformly generate random positive integers, i and j
With 1 <= i , j <= 10^6
If gcd(i , j) == 1: result = 1
Else: result = 0

Take the sum of the N results, S
Return sqrt(6 * N / S)

Specification

Input

Flexible, take input in any of the standard ways (eg function parameter,STDIN) and in any standard format (eg String, Binary)

Output

Flexible, give output in any of the standard ways (eg return, print)
White space, trailing and leading white space is acceptable
Accuracy, please provide at least 4 decimal places of accuracy (ie 3.1416)

Scoring

Shortest code wins!

Test Cases
Your output may not line up with these, because of random chance. But on average, you should get about this much accuracy for the given value of N.
Input     ->  Output
-----         ------
100       ->  3.????
10000     ->  3.1???
1000000   ->  3.14??

Does our answer need to work for N = 1000000 or is it ok if the program returns e.g. a stack overflow if N is too big?

@Fatalize if it is a limitation of the language, sure. Otherwise, you need to handle N=10^6.

Related

The goal is misleading, it states only one pair of integers is checked.

@immibis I meant the goal to be a short overview with exact details in the specification. I thought the #coprime might indicate multiple pairs.

Does the upper limit to the random numbers generated need to be exactly 1000000? Would a larger upper limit be acceptable?

@Sok A larger upper limit is acceptable

I agree with @immibis, something like "check if N random pairs of integers are relatively prime" might be clearer.

APL, 23 bytes
{.5*⍨6×⍵÷1+.=∨/?⍵2⍴1e6}

Explanation:

?⍵2⍴1e6: generate a 2-by-⍵ matrix of random numbers in the range [1..106]
1+.=∨/: get the GCD of each pair and see how many are equal to 1. This calculates S.
.5*⍨6×⍵÷: (6 × ⍵ ÷ S)0.5

Jelly, 20 18 16 bytes
-2 bytes thanks to @Pietu1998 (chain & use count 1s, ċ1 in place of less than two summed <2S)
-2 bytes thanks to @Dennis (repeat 1e6 multiple times before sampling to avoid chaining)
Ḥȷ6xX€g2/ċ1÷³6÷½

(Extremely slow due to the random function)
How?
Ḥȷ6xX€g2/ċ1÷³6÷½ - Main link: n
 ȷ6              - 1e6
   x             - repeat
Ḥ                -     double, 2n
    X€           - random integer in [1,1e6] for each
       2/        - pairwise reduce with
      g          -     gcd
         ċ1      - count 1s
           ÷     - divide
            ³    - first input, n
             6   - literal 6
              ÷  - divide
               ½ - square root

TryItOnline

ḤRµȷ6Xµ€g2/ċ1÷³6÷½ saves 2 bytes. (ȷ6 is 10^6 in a single nilad, ċ1 counts ones)

Ah I couldn't work out how to chain it up like that (I tried a few things), and forgot the count 1 trick - thanks (I think ȷ² is a tiny tiny bit faster than ȷ6)

Might be. Now that I think of it, ȷ² being two links doesn't hurt here, but would require an extra link or ¤ for some use cases

Ḥȷ6xX€ should work for the random sampling.

Python 2, 143 140 132 124 122 124 122 bytes
It has been quite some time since I have tried golfing, so I may have missed something here! Will be updating as I shorten this.
import random as r,fractions as f
n,s=input(),0
k=lambda:r.randrange(1e6)+1
exec's+=f.gcd(k(),k())<2;'*n
print(6.*n/s)**.5

Test me here!
thanks to Jonathan Allan for the two-byte save :)

According to OP, 1 <= i , j <= 10^6, so you need to use randrange(1,1e6+1).

Also, it's really strange to have the repl.it link within the language name. A link in the lang name should be to the language's home page, if anything. Put your repl.it link as a separate link below your code.

@mbomb007 Good point, I've fixed it :) Been a while!

k=lambda:r.randrange(1e6)+1 saves two bytes

@JonathanAllan good catch, thanks!

Mathematica, 49 48 51 bytes
Saved one byte and fixed one bug thanks to @LegionMammal978.
(6#/Count[GCD@@{1,1*^6}~RandomInteger~{2,#},1])^.5&

You can save a byte: (6#/Count[GCD@@1*^6~RandomInteger~{2,#},1])^.5&

Also, 1*^6 should be replaced with {1,1*^6} to ensure that i, j ≠ 0.

R, 103 99 95 99 98 94 bytes
Can likely be golfed down a bit. Cut down 4 bytes due to @antoine-sac, and another 4 bytes by defining an alias for sample, using ^.5 instead of sqrt, and 1e6 instead of 10^6. Added 4 bytes to ensure that the sampling of i and j is truly uniform. Removed one byte after I realized that 6*N/sum(x) is the same as 6/mean(x). Used pryr::f instead of function(x,y) to save 4 bytes.
N=scan()
s=sample
g=pryr::f(ifelse(o<-x%%y,g(y,o),y))
(6/mean(g(s(1e6,N,1),s(1e6,N,1))==1))^.5

Sample output:
N=100     -> 3.333333
N=10000   -> 3.137794
N=1000000 -> 3.141709

You can simply use sample(10^6,N). Not only is it shorter, it is also much more efficient.

I may be wrong, but shouldn't the sample be used with replace=T for a properly uniform random integers.  For example sample(10,10) is guaranteed to return all the numbers in 1:10, whereas sample(10,10,T) will produce a random selection where numbers can be repeated.

@MickyT You're absolutely correct, I just realized this a few minutes ago myself. I'm not entirely sure how this plays out mathematically in this instance - as far as I can tell, both methods are roughly equally accurate. I'll edit my post to add this information.

Both methods are equally accurate when N<<10^6. To handle arbitrarily big N,  you have to sample with replacement, good catch.

Actually, 19 bytes
`6╤;Ju@Ju┤`nkΣß6*/√

Try it online!
Explanation:
`6╤;Ju@Ju┤`nkΣß6*/√
`6╤;Ju@Ju┤`n         do this N times:
 6╤;                   two copies of 10**6
    Ju                 random integer in [0, 10**6), increment
      @Ju              another random integer in [0, 10**6), increment
         ┤             1 if coprime else 0
            kΣ       sum the results
              ß      first input again
               6*    multiply by 6
                 /   divide by sum
                  √  square root

i, j aren't allowed to be 0

@isaacg They aren't. If you'll read the explanation, it says that the random values are selected from [0, 10**6), then incremented.

MATL, 22 bytes
1e6Hi3$YrZ}Zd1=Ym6w/X^

Try it online!
1e6      % Push 1e6
H        % Push 2
i        % Push input, N
3$Yr     % 2×N matrix of uniformly random integer values between 1 and 1e6
Z}       % Split into its two rows. Gives two 1×N arrays
Zd       % GCD, element-wise. Gives a 1×N array
1=       % Compare each entry with 1. Sets 1 to 0, and other values to 0
Ym       % Mean of the array
6w/      % 6 divided by that
X^       % Square root. Implicitly display

Scala, 149 126 bytes
val& =BigInt
def f(n: Int)={math.sqrt(6f*n/Seq.fill(n){val i,j=(math.random*99999+1).toInt
if(&(i).gcd(&(j))>1)0 else 1}.sum)}

Explanation:
val& =BigInt                //define & as an alias to the object BigInt, because it has a gcd method
def f(n:Int)={              //define a method
  math.sqrt(                //take the sqrt of...
    6f * n /                //6 * n (6f is a floating-point literal to prevent integer division)
    Seq.fill(n){            //Build a sequence with n elements, where each element is..
      val i,j=(math.random*99999+1).toInt //take 2 random integers
      if(&(i).gcd(&(j))>1)0 else 1        //put 0 or 1 in the list by calling
                                          //the apply method of & to convert the numbers to
                                          //BigInt and calling its bcd method
    }.sum                   //calculate the sum
  )
}

I <3 Scala! Especially, because it sometimes really needs an explanation.

@RomanGräf To be honest, the only things I think might be unclear are 6f, Seq.fill and math.random.

Pyth, 21 bytes
@*6cQ/iMcmhO^T6yQ2lN2

Try it online.
Explanation
                Q          input number
               y           twice that
         m                 map numbers 0 to n-1:
             T                 10
            ^ 6                to the 6th power
           O                   random number from 0 to n-1
          h                    add one
        c        2         split into pairs
      iM                   gcd of each pair
     /            lN       count ones
   cQ                      divide input number by the result
 *6                        multiply by 6
@                   2      square root

JavaScript (ES7), 107 95 94 bytes
n=>(n*6/(r=_=>Math.random()*1e6+1|0,g=(a,b)=>b?g(b,a%b):a<2,q=n=>n&&g(r(),r())+q(n-1))(n))**.5

The ES6 version is exactly 99 bytes, but the ES7 exponentiation operator ** saves 5 bytes over Math.sqrt.
Ungolfed
function pi(n) {
  function random() {
    return Math.floor(Math.random() * 1e6) + 1;
  }
  function gcd(a, b) {
    if (b == 0)
      return a;
    return gcd(b, a % b);
  }
  function q(n) {
    if (n == 0)
      return 0;
    return (gcd(random(), random()) == 1 ? 1 : 0) + q(n - 1));
  }
  return Math.sqrt(n * 6 / q(n));
}

In the Ungolfed Version gcd calls the the function g

r=_=> is that code or a drawing?

n=>(n*6/(r=_=>Math.random()*1e6,g=(a,b)=>b?g(b,a%b):a>-2,q=n=>n&&g(~r(),~r())+q(n-1))(n))**.5 1B shorter

n=>(n*6/(q=_=>n--&&q(r=_=>Math.random()*1e6)+g(~r(),~r()))(g=(a,b)=>b?g(b,a%b):a>-2))**.5

PHP, 82 77 74 bytes
for(;$i++<$argn;)$s+=2>gmp_gcd(rand(1,1e6),rand(1,1e6));echo(6*$i/$s)**.5;

Run like this:
echo 10000 | php -R 'for(;$i++<$argn;)$s+=2>gmp_gcd(rand(1,1e6),rand(1,1e6));echo(6*$i/$s)**.5;' 2>/dev/null;echo

Explanation
Does what it says on the tin. Requires PHP_GMP for gcd.
Tweaks

Saved 3 bytes by using $argn

Racket 92 bytes
(λ(N)(sqrt(/(* 6 N)(for/sum((c N))(if(= 1(gcd(random 1 1000000)(random 1 1000000)))1 0)))))

Ungolfed:
(define f
  (λ (N)
    (sqrt(/ (* 6 N)
            (for/sum ((c N))
              (if (= 1
                     (gcd (random 1 1000000)
                          (random 1 1000000)))
                  1 0)
              )))))

Testing:
(f 100)
(f 1000)
(f 100000)

Output:
2.970442628930023
3.188964020716403
3.144483068444827

Perl, 64 bytes
sub r{1+~~rand 9x6}$_=sqrt$_*6/grep{2>gcd r,r}1..$_

Requires the command line option -pMntheory=gcd, counted as 13. Input is taken from stdin.
Sample Usage
$ echo 1000 | perl -pMntheory=gcd pi-rock.pl
3.14140431218772

R, 94 bytes
N=scan();a=replicate(N,{x=sample(1e6,2);q=1:x[1];max(q[!x[1]%%q&!x[2]%%q])<2});(6*N/sum(a))^.5

Relatively slow but still works. Replicate N times a function that takes 2 random numbers (from 1 to 1e6) and checks if their gcd is less than 2 (using an old gcd function of mine).

If you're not worried about warnings, 1:x will work.

PowerShell v2+, 118 114 bytes
param($n)for(;$k-le$n;$k++){$i,$j=0,1|%{Random -mi 1};while($j){$i,$j=$j,($i%$j)}$o+=!($i-1)}[math]::Sqrt(6*$n/$o)

Takes input $n, starts a for loop until $k equals $n (implicit $k=0 upon first entering the loop). Each iteration, get new Random numbers $i and $j (the -minimum 1 flag ensure we're >=1 and no maximum flag allows up to [int]::MaxValue, which is allowed by the OP since it's larger than 10e6).
We then go into a GCD while loop. Then, so long as the GCD is 1, $o gets incremented. At the end of the for loop, we do a simple [math]::Sqrt() call, which gets left on the pipeline and output is implicit.
Takes about 15 minutes to run with input 10000 on my ~1 year old Core i5 laptop.
Examples
PS C:\Tools\Scripts\golfing> .\natural-pi-0-rock.ps1 100
3.11085508419128

PS C:\Tools\Scripts\golfing> .\natural-pi-0-rock.ps1 1000
3.17820863081864

PS C:\Tools\Scripts\golfing> .\natural-pi-0-rock.ps1 10000
3.16756133579975

Java 8, 164 151 bytes
n->{int c=n,t=0,x,y;while(c-->0){x=1+(int)(Math.random()*10e6);y=1+(int)(Math.random()*10e6);while(y>0)y=x%(x=y);if(x<2)t++;}return Math.sqrt(6f*n/t);}

Explanation
n->{
    int c=n,t=0,x,y;
    while(c-->0){                          // Repeat n times
        x=1+(int)(Math.random()*10e6);     // Random x
        y=1+(int)(Math.random()*10e6);     // Random y
        while(y>0)y=x%(x=y);               // GCD
        if(x<2)t++;                        // Coprime?
    }
    return Math.sqrt(6f*n/t);              // Pi
}

Test Harness
class Main {
    public static interface F{ double f(int n); }
    public static void g(F s){
        System.out.println(s.f(100));
        System.out.println(s.f(1000));
        System.out.println(s.f(10000));
    }
    public static void main(String[] args) {
        g(
            n->{int c=n,t=0,y,x;while(c-->0){x=1+(int)(Math.random()*10e6);y=1+(int)(Math.random()*10e6);while(y>0)y=x%(x=y);if(x<2)t++;}return Math.sqrt(6f*n/t);}
        );
    }
}

Update

-13 [16-10-05] Thanks to @TNT and added test harness

You don't need parentheses around the first n, t+=1 can become t++, you can condense your int declarations into one line, i.e. int c=n,t=0,x,y;, and !=0 (I think) can become >0. That should save 12 bytes overall. That's a neat way of finding the GCD of x and y, though.

Pyt, 24 bytes
Đ0⇹`⇹ɽɽǤ⁻?ŕ:ŕ⁺;⇹⁻łŕᵮ/6*√

Try it online!
Đ                           implicit input; Đuplicate on stack (N, i) where i is a counter
 0                          push 0 (S)
  ⇹                         swap top two items on stack
   `             ł          do... while top of stack is not 0
    ⇹                       swap top two items on stack
     ɽɽ                     get two ɽandom 32-bit integers
       Ǥ⁻?                  if the ǤCD of the two random integers is >1:
          ŕ                 ŕemove the GCD
           :ŕ⁺              otherwise ŕemove the GCD and increment S
              ;⇹⁻           either way, swap and decrement N
                 ŕ          ŕemove i (which is now 0)
                  ᵮ         cast S to a ᵮloat
                   /        N/S
                    6*√     sqrt(6*N/S); implicit print

Frink,  84  89
r[]:=random[10^6]+1
g=n=eval[input[1]]
for a=1to n
g=g-1%gcd[r[],r[]]
println[(6*n/g)^.5]

I got lucky: g=n=... saves a byte over g=0 n=...; and 1%gcd() gives (0,1) vs (1,0) so I can subtract.
And unlucky: n is preassigned and a used because loop variables and their bounds are local and undefined outside the loop.
Verbose
r[] := random[10^6] + 1     // function. Frink parses Unicode superscript!
g = n = eval[input[""]]     // input number, [1] works too
for a = 1 to n              // repeat n times
   g = g - 1%gcd[r[], r[]]  // subtract 1 if gcd(i, j) > 1
println[(6*n/g)^.5]         // ^.5 is shorter than sqrt[x], but no super ".", no ½

That's 90 bytes and 88 chars...?

Thanks for catching that. I didn't count newlines, and while ², ³  are only 1 byte ⁶ is more. I fixed it to 89 bytes with no final newline.

You have not fixed the verbose code.

It's not a one-to-one match anyway with spacing, the quotes and numbers, etc.

Perl 6, 56 53 bytes
{sqrt 6*$_/(1..10⁶).roll(*).map(*gcd*==1)[^$_].sum}

Try it online!

AWK, 109 bytes
func G(p,q){return(q?G(q,p%q):p)}{for(;i++<$0;)x+=G(int(1e6*rand()+1),int(1e6*rand()+1))==1;$0=sqrt(6*$0/x)}1

Try it online!
I'm surprised that it runs in a reasonable amount of time for 1000000.

Pyt, 37 35 bytes
←Đ0⇹`25*⁶⁺Đ1⇹ɾ⇹1⇹ɾǤ1=⇹3Ș+⇹⁻łŕ⇹6*⇹/√

Explanation:
←Đ                                              Push input onto stack twice
  0                                             Push 0
   ⇹                                            Swap top two elements of stack
    `                      ł                    Repeat until top of stack is 0
     25*⁶⁺Đ1⇹ɾ⇹1⇹ɾ                              Randomly generate two integers in the range [1,10^6]
                  Ǥ1=                           Is their GCD 1?
                     ⇹3Ș                        Reposition top three elements of stack
                        +                       Add the top 2 on the stack
                         ⇹⁻                     Swap the top two and subtract one from the new top of the stack
                            ŕ                   Remove the counter from the stack
                             ⇹                  Swap the top two on the stack
                              6*                Multiply top by 6
                                ⇹               Swap top two
                                 /              Divide the second on the stack by the first
                                  √             Get the square root

J, 27 Bytes
3 :'%:6*y%+/(1:=?+.?)y#1e6'

Explanation:
3 :'                      '  | Explicit verb definition
                     y#1e6   | List of y copies of 1e6 = 1000000
            (1:=?+.?)        | for each item, generate i and j, and test whether their gcd is 1
          +/                 | Sum the resulting list
      6*y%                   | Divide y by it and multiply by six
    %:                       | Square root

Got pretty lucky with a 3.14157 for N = 10000000, which took 2.44 seconds.

Japt, 23 18 bytes
*6/UÆ2ÆÒL³öÃrjÃx)¬

Try it

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
How many times will a bell tower ring?
Introduction
A bell tower will ring its bells every hour, n times, with n being the the current hour on a 12 hour clock.
For example, a bell will ring 5 times at 5pm, and 10 times at 10am.
Task
Given two times in a suitable format, output the number of times the bell will ring, inclusive of the start and end times
Examples
"10am-12pm"
10+11+12= 33

[01:00, 05:00]
1+2+3+4+5 = 15

[11, 15]
11+12+1+2+3 = 29

[10:00pm, 10:00am]
10+11+12+1+2+3+4+5+6+7+8+9+10 = 88

If the start is the same as the end then the you simply just ouput the number of chimes for that hour:
[5pm, 5pm]
5 = 5

As you can see, you may choose an input method but the output must be an integer on its own (or an acceptable alternative) trailing/ leading newlines and spaces are allowed.
Note:

inputs may span from the afternoon of one day to the morning of the next.
the difference between the two times will never be more than 24 hours.
input is flexible so long as you clearly state what format your input is.
your input must have a clear distinction between AM and PM.

Do we choose our own input method, or does it have to support all the mentioned?

You may choose the input method

You should make it more clear that the inputs can go from pm to am, thus crossing to a 2nd day.

Will midnight be given as 0 or 24?

Does being able to choose the input method go as far as allowing us to take the two times in reverse (i.e. 11pm to 1am as 1, 23)?

We encourage the use of the Sandbox to work out any issues with challenges before they are posted to the main site.

@xnor : All bell towers I've seen rung 12 times at midnight.

To make it more challenging, some bell towers ring once at every quarter hour. And as almost all bell towers are attached to churches, they also ring Sundays at the beginning and end of church service. (they also ring when there is a marriage or funeral, but that would be too difficult to predict...)

I think the first example in the "Examples" section is incorrect - 12am is 00:00, or midnight. Therefore 10am-12am = 10:00 to 00:00, or 10+11+12+1+2+3+4+5+6+7+8+9+10+11+12 = 111

Can I use 13-23 for 1pm-11pm and 0 instead of 12am?

This challenge still has several issues with clarity, and should not have been reopened.

@BasicallyAlanTuring Shouting doesn't solve anything. As mentioned in the comments above, the first example is incorrect, and it's not clear whether midnight in 24-hour time should be 0 or 24.

@Mego It     is    your    choice    just    make    sure     you    specify

JavaScript (ES6), 38 35 bytes
f=(x,y)=>~-x%12-~(x-y&&f(x%24+1,y))

Recursively adds the current number of bell rings to the total. Called like f(11,15); midnight is represented as 24. I got part of the ~- trick from @xnor's Python answer.
Test snippet

f=(x,y)=>~-x%12-~(x-y&&f(x%24+1,y))
g=(x,y)=>console.log("x:",x,"y:",y,"result:",f(x,y))

g(10,12)
g(1,5)
g(11,15)
g(22,10)
<input id=A type="number" min=1 max=24 value=9>
<input id=B type="number" min=1 max=24 value=17>
<button onclick="g(A.value,B.value)">Run</button>

Non-recursive version (Firefox 30+), 56 bytes
(x,y,t=0)=>[for(_ of Array((y-x+25)%24))t+=x++%12||12]|t

Equivalent to the following ES6 function:
(x,y,t=0)=>[...Array((y-x+25)%24))].map(_=>t+=x++%12||12)|t

Python 2, 46 bytes
f=lambda x,y:(x%12or 12)+(x-y and f(-~x%24,y))

Based on my JS answer. The recursive formula f for the solution is defined as so:

Start with two integers x and y.
Take x mod 12; if this is 0, take 12 instead.
If x != y, add the result of f(x+1 mod 24, y).

Python 2, 59 54 bytes
a=lambda x,y:sum(1+i%12for i in range(x-1,y+24*(x>y)))

Equivalent to
summ=0
if start > end:
    end+=24
for hour in range(start-1,end):
    summ +=1+hour%12
print summ

I think you don't need the a= part.

@daHugLenny it need to be a full(usable) function

(y+24)%24 is just y

@Rod You don't need a=. It's allowed to be a pure lambda.

@Rod You don't need a named function

@VladimirCravero Of course not. It is the same as y%24.

Yep @EriktheGolfer you are right, in my mind y < 24 which is true in this particular case.

Guys, I know that the a= isn't necessary, but all the python answers in this question have it. It's better for score comparison to keep this pattern across the answers. All or None c:

05AB1E, 13 bytes
With a lot of help from Emigna.
-24%Ý¹+<12%>O

Uses the CP-1252 encoding. Try it online!

Jelly, 17 16 15 14 bytes
>×24+⁹⁸r’%12‘S

TryItOnline
How?
>×24+⁹⁸r’%12‘S - Main link: a, b (24 hr integers, midnight may be 0 or 24)
>              - a>b? (1 if true, 0 if false)
 ×24           - times 24 (24 if a>b, else 0)
    +⁹         - add to b (b+24 if a>b, else b)
      ⁸        - a
       r       - range(a, b+24 or b) ([a,a+1,...,b+24 or b])
        ’      - decrement (vectorises) ([a-1,a,...,b+23 or b-1])
         %12   - mod 12 (vectorises) (number of tolls at each occurrence - 1)
            ‘  - increment (vectorises) (number of tolls at each occurrence)
             S - sum

Python, 42 bytes
f=lambda a,b:~-a%12-~(b-a and f(-~a%24,b))

A recursive function that takes two numbers from 0 to 23. Expanding the ~x's to -x-1 gives
f=lambda a,b:(a-1)%12+1+(b-a and f((a+1)%24,b))

The expression (a+1)%12+1 converts a time to the number of rings 1 to 12. Then, the lower bound is incremented modulo 24 and the function for the recursive result is added. That is, unless the current hour is the end hour, in which case we stop.
I've been trying to write a purely arithmetical solution instead, but so far I've only found long and messy expressions.

Ah, I get it: it's basically the same technique as my Python answer, but with a really clever way of getting around the or. Nice one!

Haskell, 48 43 bytes
s%e=sum[mod x 12+1|x<-[s-1..e+23],x<e||s>e]

Usage is startHour % endHour, with both inputs given in 24-hr format.
edit: added @xnor's improvement, saving 5 bytes

Instead of changing e when e<s, you could filter the range s%e=sum[mod(x-1)12+1|x<-[s..e+24],x<=e||s>e]. It then saves a byte to shift x down by 1: s%e=sum[mod x 12+1|x<-[s-1..e+23],x<e||s>e].

C#, 73 bytes
a=>b=>{int x=0;for(;;){x+=(a%=24)>12?a-12:a<1?12:a;if(a++==b)return x;}};

Acceptable input: integers in range [0,23].
This solution does not use LINQ.

Full program with test cases:
using System;

namespace HowManyTimesABellTowerRings
{
    class Program
    {
        static void Main(string[] args)
        {
            Func<int,Func<int,int>>f= a=>b=>{int x=0;for(;;){x+=(a%=24)>12?a-12:a<1?12:a;if(a++==b)return x;}};

            Console.WriteLine(f(10)(12));   //33
            Console.WriteLine(f(1)(5));     //15
            Console.WriteLine(f(11)(15));   //29
            Console.WriteLine(f(22)(10));   //88
            Console.WriteLine(f(10)(10));   //10
            Console.WriteLine(f(11)(10));   //156
            Console.WriteLine(f(0)(23));    //156
            Console.WriteLine(f(22)(1));    //34
        }
    }
}

PHP, 90 Bytes
Input format '[1,24]' between 1 and 24
In this challenge that I am hate why PHP loose against other languages. I prefer to show all my ideas. Maybe an other PHP Crack finds a shorter solution.
<?list($f,$g)=$_GET[b];for($i=$f;$i-1!=$g|$f>$g&!$c;$s+=$i++%12?:12)$i<25?:$c=$i=1;echo$s;

99 Bytes
<?for($i=($b=$_GET[b])[0],$c=($d=$b[1]-$b[0])<0?25+$d:$d+1;$c--;$s+=$i++%12?:12)$i<25?:$i=1;echo$s;

113 Bytes a way with min and max
<?for($i=min($b=$_GET[b]);$i<=$m=max($b);)$s+=$i++%12?:12;echo($b[0]>$b[1])?156-$s+($m%12?:12)+($b[1]%12?:12):$s;

okay this crazy idea works with an array 149 Bytes
fills the array $y[0] and $y[1] if $_GET["b"][0]<=$_GET["b"][1]
if $y[1] is null we can sum this array array_diff_key($y[0],array_slice($y[0],$b[1],$b[0]-$b[1]-1,1))
<?for(;++$i<25;)$y[$i>=($b=$_GET[b])[0]&$i<=$b[1]][$i]=$i%12?:12;echo array_sum($y[1]??array_diff_key($y[0],array_slice($y[0],$b[1],$b[0]-$b[1]-1,1)));

This could be golfed down 124 Bytes
<?for(;++$i<25;)$x[($v=($b=$_GET[b])[0]>$b[1])?$i<$b[0]&$i>$b[1]:$i>=$b[0]&$i<=$b[1]][$i]=$i%12?:12;echo array_sum($x[!$v]);

Now at this point we can reduce the array with only two ints 101 Bytes
Make 2 sums $x[0] and $x[1]
list($f,$g)=$_GET[b];
if $v=($f>$g
then add value to $x[$i<$f&$i>$g]
else add value to $x[$i>=$f&$i<=$g]
the output will be find by case echo$x[!$v];
<?list($f,$g)=$_GET[b];for(;++$i<25;)$x[($v=$f>$g)?$i<$f&$i>$g:$i>=$f&$i<=$g]+=$i%12?:12;echo$x[!$v];

After that i found a way to calculate the result directly 112 Bytes
<?list($x,$y)=$_GET[t];echo(($b=$x>$y)+(($x-($s=$x%12?:12)^$y-($t=$y%12?:12))xor$b))*78-($s*($s-1)-$t*($t+1))/2;

recursive 103 Bytes
<?list($x,$y)=$_GET[t];function f($x,$y){return($x%12?:12)+($x-$y?f(++$x<25?$x:1,$y):0);}echo f($x,$y);

Java, 72 71 78 76 bytes
Usage:
    pm:    true if first time is past 11am
    time:  first time%12
    pm2:   true if second time is past 11am
    time2: second time%12

Edit:

-1 byte off. Thanks to @1Darco1
Fixed function head. +7 bytes on.
-2 bytes off. Thanks to @Kevin Cruijssen
+2 bytes on. Now e/clock is initialized.

(a,b,c,d)->{int e=0;b+=a?12:0;d+=c?12:0;for(;b!=d;e+=b%12,b=++b%24);return e;}

Ungolfed:
public static int clock(boolean pm, int time, boolean pm2, int time2){
  int clock=0;
  time+=pm?12:0;
  time2+=pm2?12:0;
  while(time!=time2){
    clock+=time%12;
    time=++time%24;
  }
  return clock;
}

Where do you define a, and d, and b ? The full method makes sense, but unless I'm severely missing something, I think you need to look at your golfed lambda again and actually try to execute it. For further golfing: (time+1) can become ++time.

There is an error in the golfed part: a+=a? should be b+=a?. Also, you can golf it by 2 bytes by changing the while into a bodyless for like this: (a,b,c,d)->{int e;b+=a?12:0;d+=c?12:0;for(;b!=d;e+=b%12,b=++b%24);return e;}

Sorry. I wrote this approach from my mobile and couldn't test it. Fixed. :)

MATL, 14 bytes
yy>24*+&:12X\s

Input format is as in the third example in the challenge, that is, two numbers in 24-hour format.
Try it online!
Explanation
Take inputs 22, 10 as an example.
yy      % Take two inputs implicitly. Duplicate both
        %   STACK: 22, 10, 22, 10
>       % Is the first greater than the second?
        %   STACK: 22, 10, 1
24*     % Multiply by 24
        %   STACK: 22, 10, 24
+       % Add
        %   STACK: 22, 34
&:      % Binary range
        %   STACK: [22 23 24 25 26 27 28 29 30 31 32 33 34]
12X\    % Modulo 12, 1-based
        %   STACK: [10 11 12 1 2 3 4 5 6 7 8 9 10]
s       % Sum of array
        %   STACK: 88
        % Implicitly display

PHP, 69 bytes
list(,$i,$a)=$argv;for($a+=$i>$a?24:0;$i<=$a;)$n+=$i++%12?:12;echo$n;

The list extraction was inspired by Jörg Hülsermann's answer but the rest of the similarities are a result of convergent evolution and because it's quite a lot shorter and the conditionals in the loop are different enough I'm posting it as a separate answer.
Takes input as 24 hour times (fine with either 0 or 24). Run like:
php -r "list(,$i,$a)=$argv;for($a+=$i>$a?24:0;$i<=$a;)$n+=$i++%12?:12;echo$n;" 9 18

$i>$a?24:0 has the same length as ($i>$a)*24 https://wiki.php.net/rfc/short_list_syntax Maybe you want to use the short list syntax which is new in 7.1 [$x,$i,$a]=$argv; -2 Bytes Before I have not tested that I would not use it. NIce way now I'am hate me more that I found not this way.

thanks, I knew about the upcoming short list syntax but as php 7.1 hasn't been properly released yet (still on release candidate 3 at time of writing) I assumed it wasn't yet permitted in PPCG answers.

QBIC, 90 47 bytes
So, here's the answer printing only the total number of bell-rings:
::{c=a~c>12|c=c-12]d=d+c~a=b|_Xd]a=a+1~a>24|a=1

Input is in range 1-24; a and b are the inputs (:: in the code), c keeps track of am/pm, d is the total number of rings. When we've counted down all the hours, _Xd terminates the program, printing d in the process.

OK, I misunderstood the question and thought the 1+2+3...= text was part of the output, so I wrote that:
::{c=a~c>12|c=c-12]X=!c$Z=Z+X+@+| d=d+c~a=b|?left$$|(Z,len(Z)-1)+@ =|+!d$_X]a=a+1~a>24|a=1

Now, I'll go code the proper answer...

Pyth - 11 bytes
s|R12%R12}F

Test Suite.

This does not count around midnight, for example 23, 1 outputs 144 when it should output 24. (Such a case should, of course, be in the tests!)

C#, 76 bytes
(a,b)=>Enumerable.Range(a,Math.Abs(b-a)+1).Select(n=>n%12==0?12:n%12).Sum();

This doesn't look as if it wraps around at midnight.

All test cases succeed

I didn't ask that.

Then what test case of yours fails with my implementation?

a=23 and b=0 seems to be the most obvious example.

Perl, 36 bytes
Includes +1 for -p
Give start and end time in 24-hour format on a line each on STDIN:
toll.pl
11
15
^D

toll.pl:
#!/usr/bin/perl -p
$\+=$_%12||12for$_..$_+(<>-$_)%24}{

><>, 48 + 2 = 50 bytes
<v$&%$-&:$+}:*2c
{>:?!v1-}:1+
v?=1l<++1%c+b$
>n;

Input is expected to be present on the stack at program start, so +2 bytes for the -v flag. Input is two integers specifying the hour on the 24 hour clock, so 10am - 10pm would be given as 10 22.
Try it online!

Batch, 168 91 bytes
@cmd/cset/ax=(%1+23)%%24,y=x+(%2+24-%1)%%24,z=y%%12+1,(y/12-x/12)*78+z*-~z/2-(x%%=12)*-~x/2

Edit: Saved 77 byte by switching to a closed form for the answer.

%1 and %2 are the two command-line parameters
@ Disable Batch's default which is to echo the command
cmd/c Fool Batch into immediately printing the result of the calculation
set/a Perform a numeric calculation
x=(%1+23)%%24, Normalise the starting hour to be the number of hours since 1AM (1PM would also work, but 11 is no shorter than 23)
y=x+(%2+24-%1)%%24, Normalise the ending hour to be ahead of the starting hour, advancing to the next day if necessary
z=y%%12+1, Number of bells struck at the ending hour
(y/12-x/12)*78+ Number of bells due to extra half days
z*~-z/2- Number of bells from 1 o'clock to the ending hour inclusive
(x%%=12) One less than the number of bells struck at the starting hour
*-~x/2 Number of bells that would have been struck from 1 o'clock to the starting hour, but not including the starting hour

Java 7, 64 bytes
int c(int x,int y){return(x%12<1?12:x%12)+(x!=y?c(-~x%24,y):0);}

Recursive method based on @ETHproductions's Python 2 answer. Uses a 24-hour clock input.
Ungolfed & test code:
Try it here.
class M{
  static int c(int x, int y){
    return (x%12 < 1
             ? 12
             : x%12)
         + (x != y
             ? c(-~x % 24, y)
             : 0);
  }

  public static void main(String[] a){
    System.out.println(c(10, 12));
    System.out.println(c(1, 5));
    System.out.println(c(11, 15));
    System.out.println(c(10, 22));
    System.out.println(c(5, 5));
  }
}

Output:
33
15
29
88
5

C, 56 Bytes
f(a,b,c=0){while(b-->a){c+=b>12?b-12:b;}printf("%d",c);}

Cubix, 45 44 bytes
Saved 1 byte, thanks to @ETHproductions
My first foray into Cubix...
)$424tU4OI0Iuq;;-!^;^%&21u+rr;ss!;sqU>&%r$@;

Or, cubified:
      ) $ 4
      2 4 t
      U 4 O
I 0 I u q ; ; - ! ^ ; ^
% & 2 1 u + r r ; s s !
; s q U > & % r $ @ ; .
      . . .
      . . .
      . . .

You can try it out at the online interpreter. Input is in 24 hour format, with the end time first. For example, from 5pm to 1am the input should be 1 17.

Previous version, 45 bytes:
)$442t\/OI0Iuq;;-!^;^%&21u+rr;ss!;sqU>&%r$@.;

Thank you for using my language, and great job :-) I see one small byte you can save by rearranging slightly and dropping the no-op: )$424tU4OI0Iuq;;-!^;^%&21u+rr;ss!;sqU>&%r$@;

Qbasic, 112 bytes
input "",a
input "",b
do
if a=25 then a=1
if a<=12 then
c=c+a
else
c=c+a-12
endif
a=a+1
loop until a=b+1
print c

Shouldn't you output 12 when both starting and ending hour are zero?

Python, 73 bytes
It would be so much shorter if we didn't have to support pm to am. I use recursion to support it.
f=lambda a,b:sum([~-i%12+1for i in range(a,b+1)]*(a<b)or[f(a,24),f(1,b)])

Try it online
Without supporting pm to am (45 bytes):
lambda a,b:sum(~-i%12+1for i in range(a,b+1))


text:
Rationalise the Denominator
Challenge
Given a fraction with a surd (an irrational number) as the denominator, output the rationalised fraction.
Rationalising the Denominator
To rationalise the denominator, what you have to do is take the fraction and make one which is equal which does not have an irrational number in the denominator. Generally, the method is as follows:

Say the inputted fraction is:
(a + x * sqrt(b)) / (c + y * sqrt(d))

To rationalise the denominator, you need to multiply the numerator and the denominator by the conjugate of c + y * sqrt(d) (c - y * sqrt(d)):
(a + x * sqrt(b)) / (c + y * sqrt(d)) * (c - y * sqrt(d)) / (c - y * sqrt(d))

To get:
((a + x * sqrt(b))(c - y * sqrt(d))) / (c^2 + y * d)

Which you should then simplify completely

Example
Input:
(4 + 3 * sqrt(2))/(3 - sqrt(5))

Method:
(4 + 3 * sqrt(2))/(3 - sqrt(5)) * (3 + sqrt(5))/(3 + sqrt(5))
((4 + 3 * sqrt(2))(3 + sqrt(5)))/(9 - 5)
(12 + 4 * sqrt(5) + 9 * sqrt(2) + 3 * sqrt(10))/(4)

Output:
(12 + 4 * sqrt(5) + 9 * sqrt(2) + 3 * sqrt(10))/(4)

Input:
3 / sqrt(13)

Method:
3 / sqrt(13) * sqrt(13) / sqrt(13)
(3 * sqrt(13)) / 13

Output:
(3 * sqrt(13)) / 13

Input:
1 / (sqrt(5) + sqrt(8))

Method:
1/ (sqrt(5) + sqrt(8)) * (sqrt(5) - sqrt(8)) / (sqrt(5) - sqrt(8))
(sqrt(5) - sqrt(8)) / (sqrt(5) + sqrt(8))(sqrt(5) - sqrt(8))
(sqrt(5) - sqrt(8)) / (5 - 8)
(sqrt(5) - sqrt(8)) / -3

Output:
(sqrt(5) - sqrt(8)) / -3

Input:
2 / (3 * sqrt(20) + sqrt(50) + sqrt(2))

Method:
2 / (3 * sqrt(20) + sqrt(50) + sqrt(2)) * (63 * sqrt(20) - sqrt(50) - sqrt(2)) / (3 * sqrt(20) - sqrt(50) - sqrt(2))
2(3 * sqrt(20) - sqrt(50) - sqrt(2)) / (108)
(3 * sqrt(20) - sqrt(50) - sqrt(2)) / (54)
(3 * 2 * sqrt(5) - 5 * sqrt(2) - sqrt(2)) / (54)
(6 * sqrt(5) - 6 * sqrt(2)) / (54)

Output:
(6 * sqrt(5) - 6 * sqrt(2)) / (54)

If you want, you can simplify this further to:
(6 * (sqrt(5) - sqrt(2))) / (54)

or:
(sqrt(5) - sqrt(2)) / (9)

Rules
All input will be in its simplest form. For example, the surd 7*sqrt(12) will be simplified to 14*sqrt(3) in the input.
Your program only needs to support addition, subtraction, multiplication, division, square roots and brackets (including expansion of multiplied brackets).
Your input and output may be in any form that you wish as long as it is a fraction and, when pasted into Wolfram Alpha, the input equals the output.
There will never be variables in the input, nor will there be the square roots of negative numbers. There will only ever be one fraction in the input. There will always be an irrational number in the denominator.
Except b and y may not always be present.
Your output must be simplified. This refers to both the simplification of the algebraic expressions and also putting the lowest possible number in the square root. For example:
sqrt(72)

Which can be simplified like so:
sqrt(72) = sqrt(9 * 8)
         = sqrt(9) * sqrt(8)
         = 3 * sqrt(8)
         = 3 * sqrt(4 * 2)
         = 3 * sqrt(4) * sqrt(2)
         = 3 * 2 * sqrt(2)
         = 6 * sqrt(2)

Built-in functions and libraries to rationalise fractions are disallowed. Similarly, internet access is disallowed.
Winning
The shortest code in bytes wins.

For fewer bytes, answers might want to use the Unicode symbol for sqrt instead: √. Works in Wolfram Alpha.

Internet access is a default loophole, no need to explicitly mention it.

this seems like it'll be very language dependent, and not particularly golf-able for certain languages... would you consider a popularity contest instead?

@Aaron Popularity contests that ask to do X creatively have fallen out of scope. This challenge would get closed as too broad if it was a pop con.

I'm not clear on what simplifications are required. If the numerator equals the denominator, do we have to output 1? Can we have needless parts like 1*?

The example 2 / (3 * sqrt(20) + sqrt(50) + sqrt(2)) comes as a surprise because the explanation makes it seem like only one square root will appear in the numerator or denominator. You should make it clearer what kinds of inputs need to be handled.

The example 3 * sqrt(20) + sqrt(50) + sqrt(2) is not in its simplest form (6*sqrt(5)+6*sqrt(2))


text:
Natural construction
The natural numbers including 0 are formally defined as sets, in the following way:

Number 0 is defined as the empty set, {}
For n ≥ 0, number n+1 is defined as n ∪ {n}.

As a consequence, n = {0, 1, ..., n-1}.
The first numbers, defined by this procedure, are:

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

Challenge
Given n, output its representation as a set.
Rules
The output can consistently use any bracket character such as {}, [], () or <>. Arbitrary characters (such as 01) are not allowed.
Instead of a comma as above, the separator can be any punctuation sign; or it may be inexistent.
Spaces (not newlines) may be included arbitrarily and inconsistently.
For example, number 2 with square brackets and semicolon as separator is [[]; [[]]], or equivalently [ [ ]; [ [ ] ] ], or even [  [ ] ;[  []]]
The order in which elements of a set are specified doesn't matter. So you can use any order in the representation. For example, these are some valid outputs for 3:
{{},{{}},{{},{{}}}}
{{{}},{{},{{}}},{}}
{{{}},{{{}},{}},{}}

You can write a program or function. Output may be a string or, if using a function, you may return a nested list or array whose string representation conforms to the above.
Test cases
0  ->  {}
1  ->  {{}}
2  ->  {{},{{}}}
3  ->  {{},{{}},{{},{{}}}}
4  ->  {{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}
5  ->  {{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}}
6  ->  {{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}}}
7  ->  {{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}}}}

Related

Jelly, 3 bytes
Ḷß€

This is a monadic link. Try it online!
How it works
Each natural number is the set of all previous natural numbers, i.e., n = {0, …, n-1}. Since there are no natural numbers preceding 0, we have that 0 = {}.
Ḷß€  Monadic link. Argument: n (natural number)

Ḷ    Unlength; yield [0, ..., n-1].
 ß€  Recursively map this link over the range.

"Unlength" I like Jelly's inverse functions.

If I am understanding correctly, unlength is basically range [0,n)?

@Downgoat That's correct. I try to keep letters and letters with dot below as lateral inverses. Since ḶL is a no-op, the mnemonic is unlength. There's also unbinary, undecimal, unhalve, unsine, unarccosine, etc.

Wait, unarccosine? Wouldn't that just be cosine?

@ETHproductions Yup. There's no C with dot below though.

Python 2, 26 bytes
f=lambda n:map(f,range(n))

Test it on Ideone.

JavaScript (ES6), 32 bytes
f=n=>[...Array(n).keys()].map(f)

Simple enough.

@Downgoat I think this may be the first time I've used .map() without an arrow function inside :-)

well technically f is an arrow function :P

@ETHproductions Really? .map(Number) is quite a common case.

@Xufox Good point, I think I've done that at least once.

@Xufox Though .map(e=>+e) is shorter, by a byte.

@ConorO'Brien Usually .map(eval)

Perl 6, 16 bytes
{({@_}…*)[$_]}

Returns nested data structure.
Example:
say {({@_}…*)[$_]}( 4 );
# [[] [[]] [[] [[]]] [[] [[]] [[] [[]]]]]

Explanation:
{   # lambda with implicit parameter ｢$_｣

  (

    # produce a lazy infinite sequence of all results

    {       # lambda with implicit parameter ｢@_｣
      @_    # array containing all previously seen values in the sequence
    }

    …       # keep repeating that block until:

    *       # Whatever ( never stop )

  )[ $_ ]   # use the outer block's argument to index into the sequence

}

This is... impressive.

Haskell, 32 27 bytes
p n='{':(p=<<[0..n-1])++"}"

Try it on Ideone.

Ruby, 27 21 bytes
I'm new to ruby golfing, but here goes nothing. Thanks to Jordan for saving 6 bytes!
f=->s{(0...s).map &f}

This is a recursive function f (a proc, to be specific) and takes an argument s. It maps the proc f over 0...s, which is the range [0, s).

You can replace map{|e|f[e]} with map &f.

@Jordan Wow, nice!

05AB1E, 8 7 bytes
)IF)©`®

Explanation
)         # wrap stack in a list, as stack is empty this becomes the empty list []
 IF       # input number of times do:
   )      # wrap stack in list
    ©     # store a copy of the list in the register
     `    # flatten the list
      ®   # push the copy from the register
          # implicitly print top value of stack after the last loop iteration

Try it online!
Saved 1 byte thanks to Adnan.

Less than 2 minutes LOL

@LuisMendo I literally just logged on when the challenge was posted :)

I believe you can remove the last bracket :p

@Adnan: Oops. I don't know how I missed that :)

Mathematica, 14 bytes
Array[#0,#,0]&

CJam, 14 bytes
"[]"{_)@\]}ri*

Try it online!
Explanation
"[]"            e# Push this string. It is the representation of 0, and also serves
                e# to initialize
    {     }ri*  e# Repeat this block as many times as the input number
     _          e# Duplicate
      )         e# Uncons: split into array without the last element, and last element
       @\       e# Rotate, swap
         ]      e# Pack stack contents into an array
                e# Implicitly display

In each iteration, the block builds the representation of a number from that of the preceding one. To illustrate, let's consider the second iteration, where the representation of number 2 is built from that of 1, which is the string "[[]]".

The stack contains "[[]]"
After statement _ (duplicate) it contains "[[]]", "[[]]"
After statement ) (uncons) it contains "[[]]", "[[]", "]"
After statement @ (rotate) it contains "[[]", "]", "[[]]"
After statement \ (swap) it contains "[[]", "[[]]", "]"
After statement ] (pack into array) it contains ["[[]" "[[]]" "]"], which would be displayed as the string "[[][[]]]".

Cheddar, 17 bytes
n f->(|>n).map(f)

Short recursion + Short range + Short iteration = A challenge where cheddar does very well
Non-competing, 11 bytes
n f->|>n=>f

The => operator was added after this challenge was released making this answer non-competing.
This may look confusing but let me simplify it:
n f -> |> n => f

basically n is the input and f is the function itself. |>n generates [0, n) and => maps that over f.

The non-competing one looks very nice :D

Perl, 27 bytes
Includes +1 for -p
Many different methods all seem to end up as either 27 or 28 bytes. e.g.
#!/usr/bin/perl -p
$\=$_="{@F}"for@F[0..$_]}{

The best I could find is
#!/usr/bin/perl -p
s/./{$_/ for($\="{}")x$_}{

since on older perls you can drop the space before the for and get 26 bytes

Pyth, 4 bytes
LyMb

Test suite
L: Define the function y with input b
yMb: y mapped over the range 0, 1, ..., b-1
On the input 0, this map returns []. Otherwise, it returns y mapped over all numbers up to b.

MATL, 13 bytes
Xhi:"tY:Xh]&D

Try it online!
Explanation
Xh              % Concatenate the stack contents into cell array. Since the stack
                % is empty, this produces the empty cell array, {}
  i:"     ]     % Take input number. Repeat that many times
     t          % Duplicate the cell array that is at the top of the stack
      Y:        % Unbox it, i.e., push its contents onto the stack
        Xh      % Concatenate the stack contents into a cell array
           &D   % String representation. Implicitly display

Very clever answer

@Suever Thanks! Way too long though...

Underload, 14 bytes
((:a*)~^()~^a)

Try it online!
Underload full programs can't take input via any of our defined methods, so this is a function that takes input from the stack as a Church numeral (the normal way to define integers in Underload), and produces output to the stack as a string.
The (…) grouping markers are required to make this a function (reusable) rather than a snippet (only usable once). The wrapper in the TIO link calls the function in question destructively using ^, but it could be reused via making a copy of it and only consuming one of the copies when calling it. It also provides input to the program (here, (:*:*), i.e. 4), and prints the output using S.
Explanation
Underload's surprisingly suited for this task as Turing tarpits go, having such useful primitives as "copy" and "surround with parentheses". (Somehow, Underload, normally a very verbose language, is beating Mathematica, normally a language which wins due to having a huge set of builtins, via having more appropriate builtins!) Here's how the program works:
((:a*)~^()~^a)
(            )   Make a snippet into a function
 (   )~^         Exponentiate the following function by the top of stack:
  :                Copy the top stack element
   a               Surround the copy in parentheses
    *              Append the copy to the original, popping the copy
          ~^     Run the resulting function, with the following argument on its stack:
        ()         Empty string
            a    Surround the result in parentheses

Function exponentiation effectively causes the steps of the function to repeat that many times, so, e.g., (:a*)³ would be (:a*:a*:a*). That's the idiomatic way to write a loop that repeats a given number of times in Underload. (You can note that the ~^ is described two different ways above; that's because integers in Underload are defined as function exponentiation specialised to that integer, so in order to do a function exponentiation, you simply try to execute an integer as though it were a function.)

Husk, 10 bytes
`:'}:'{ṁ₀ŀ

Try it online!
`:'}:'{ṁ₀ŀ
         ŀ  Range [0, n)
       ṁ₀   For all numbers in that range, run this function on them
       ṁ    Then concatenate those representations together
    :'{     Prepend '{'
`:'}        Append '}'

i thought of s; and then removing the quotes and backslashes, but it doesn't get below 10 :(

Retina, 24 18 bytes
.+
$*1<>
+`1<
<<$'

Try it online! (The first line enables a linefeed-separated test suite.)
Explanation
.+
$*1<>

This converts the input to unary and appends <>, the representation of 0.
+`1<
<<$'

Here, the + indicates that this substitution should be run in a loop until the string stops changing. It's easier to explain this by going through the individual steps I took golfing it down. Let's with this version of the substitution:
1<(.*)>
<<$1>$1>

This matches the last 1 of the unary representation of the remaining input (to remove it and decrement the input), as well as the contents of the current set at the end. This is then replaced with a new set containing the previous one as well as its contents. However, we can notice that $1 is followed by > in both cases and hence we can include it in the capture itself and omit it from the substitution pattern. That leads to the form
1<(.*)
<<$1$1

However, now we can observe that (.*) just captures the suffix of the string after 1< and we even reinsert this suffix at the end with $1. Since the substitution syntax gives us a way to refer to the part of a string after a match with $' we can simply omit both of those parts and end up with the version used in the answer:
1<
<<$'

You sure this is Retina and not the ><> language? :-P

@LuisMendo I guess I could have used {}, but <> is the only pair that never needs escaping, so I thought I'd go with that. ;)

Mathematica, 31 bytes
Straightforwardly implements the definition as a nested list. Uses an unnamed function that recursively calls itself using #0.
If[#<1,{},Join[t=#0[#-1],{t}]]&

You can save a lot by using a named operator as well as Union instead of Join: ±0={};±n_:={t=±(n-1)}⋃t ... However, in this case it's even shorter to go for an iterative solution: Nest[{#}⋃#&,{},#]&

Batch, 74 bytes
@set s={}
@for /l %%i in (1,1,%1)do @call set s={%%s%%%%s:~1%%
@echo %s%

Uses the fact that each answer is equal to the previous answer inserted into itself after the leading {. The first few outputs are as follows:
{}

{{}}

{{{}}{}}

{{{{}}{}}{{}}{}}

{{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}

{{{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}

Can you post an example showing input and output formats?

APL(NARS), 15 chars, 30 bytes
{⍵=0:⍬⋄∇¨¯1+⍳⍵}

test:
  f←{⍵=0:⍬⋄∇¨¯1+⍳⍵}
  o←⎕fmt
  o f 0
┌0─┐
│ 0│
└~─┘
  o f 1
┌1───┐
│┌0─┐│
││ 0││
│└~─┘2
└∊───┘
  o f 2
┌2──────────┐
│┌0─┐ ┌1───┐│
││ 0│ │┌0─┐││
│└~─┘ ││ 0│││
│     │└~─┘2│
│     └∊───┘3
└∊──────────┘
  o f 3
┌3────────────────────────┐
│┌0─┐ ┌1───┐ ┌2──────────┐│
││ 0│ │┌0─┐│ │┌0─┐ ┌1───┐││
│└~─┘ ││ 0││ ││ 0│ │┌0─┐│││
│     │└~─┘2 │└~─┘ ││ 0││││
│     └∊───┘ │     │└~─┘2││
│            │     └∊───┘3│
│            └∊──────────┘4
└∊────────────────────────┘
  o f 4
┌4────────────────────────────────────────────────────┐
│┌0─┐ ┌1───┐ ┌2──────────┐ ┌3────────────────────────┐│
││ 0│ │┌0─┐│ │┌0─┐ ┌1───┐│ │┌0─┐ ┌1───┐ ┌2──────────┐││
│└~─┘ ││ 0││ ││ 0│ │┌0─┐││ ││ 0│ │┌0─┐│ │┌0─┐ ┌1───┐│││
│     │└~─┘2 │└~─┘ ││ 0│││ │└~─┘ ││ 0││ ││ 0│ │┌0─┐││││
│     └∊───┘ │     │└~─┘2│ │     │└~─┘2 │└~─┘ ││ 0│││││
│            │     └∊───┘3 │     └∊───┘ │     │└~─┘2│││
│            └∊──────────┘ │            │     └∊───┘3││
│                          │            └∊──────────┘4│
│                          └∊────────────────────────┘5
└∊────────────────────────────────────────────────────┘

I don't know if this would be accepted...
Zilde is ⍬ here it represent the void set {}
if I want print the Zilde element or one element full of Zilde, and Zilde enclosed
all what happen is print nothing...
so for see Zilde one has to define one function I call it o (o←⎕fmt)
I do not insert in the count because the element and its structure exist
even if the sys not print it...It is possible if io is 0
{⍵=0:⍬⋄∇¨⍳⍵}

could be 12 characters solution too...

Pari/GP, 23 bytes
f(n)=[f(i)|i<-[0..n-1]]

Try it online!

Pip -p, 4 bytes
fM,a

Try it online!
The basic recursive approach works well in Pip:
f     The main function, i.e. the whole program treated as a function
 M    mapped to
  ,a  range(argument)

The result is a nested list, which is printed using square brackets thanks to the -p flag.

Raku, 17 15 bytes
(),{|$_,$_}...*

Try it online!
An anonymous lazy list. You can assign it to a variable like:
my @list = (),{|$_,$_}...* ;
and access it with @list[n].

x86-64 machine code, 22 bytes
31 C0 99 B0 7B AA FF C2 0F BC CA 39 F1 B0 7D F3 AA 75 F0 66 AB C3

Try it online!
Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes in RDI an address at which to place the result, as a null-terminated byte string, and takes the number n in RSI.
In assembly:
f:  xor eax, eax    #
    cdq             # Set EAX and EDX to 0.
r:  mov al, 0x7B    # Put the ASCII code of '{' into AL.
    stosb           # Add that to the string, advancing the pointer.
    inc edx         # Add 1 to EDX.
    bsf ecx, edx    # Set ECX to the lowest position of a 1 bit in EDX.
    cmp ecx, esi    # Compare that number with n.
    mov al, 0x7D    # Put the ASCII code of '}' in AL.
    rep stosb       # Add that to the string ECX times, advancing the pointer.
    jne r           # Repeat if the number is not equal to n.
    stosw           # Add two bytes from AX to the string: one more '}' and a null byte.
    ret             # Return.

Brachylog, 14 bytes
yk:{,[]:?:gi}a

Try it online!
Explanation
yk                The range [0, ..., Input - 1]
  :{        }a    Apply on each element of the range
    ,[]:?:gi      Group the empty list [] in a list Input times

GAP, 22 bytes
f:=n->Set([0..n-1],f);

For example:
gap> f(3);
[ [  ], [ [  ] ], [ [  ], [ [  ] ] ] ]

Racket 119 bytes
(λ(n)(define ll(list'()))(for((i(range 1 n)))(set! ll(cons ll(for/list((j(length ll)))(list-ref ll j)))))(reverse ll))

Ungolfed:
(define f
  (λ (n)
    (define ll (list '()))
    (for ((i (range 1 n)))
      (set! ll
            (cons ll
                  (for/list ((j (length ll)))
                    (list-ref ll j)
                    ))))
    (reverse ll)))

Testing (In Racket {} is same as () and default output is ()):
(f 4)

'(() (()) ((()) ()) (((()) ()) (()) ()))

To clearly see each number (0 to 3):
(for((i (f 4)))  (println (reverse i)))

'()
'(())
'(() (()))
'(() (()) ((()) ()))

BrainPipe, 185 161 bytes
-[>,----------]>>-<<<+[->++++++[->------<]>--<<[->>+<<]<+]>>>>+[-<[->++++++++++<]>>+]<.|.->,+[-[-[->+>+<<]>>[-<<+>>].<]+.-<+]-|+[++++[->++++++++<],[->+<]>.[-]<+]

Brainpipe is Brainfuck but you get to glue multiple bf interpreters together at their inputs and outputs. This Program uses three such subunits:

One to convert a number given into a byte
One to implement the following algorithm:

Output 0 and place a marker to make a stack. Take Input onto the stack.
Until the stack is empty, if the top value on the stack is not 0, output 0, decrement the value and duplicate it. If the value is 0, pop it and output 1.

One to add 40 to each of the bits the previous has provided, which turns them into ( and ).

The funny part is that the actual logic is rather short, and that most bytes are dedicated to dealing with ASCII.
ASCII DEC to byte -[>,----------]>>-<<<+[->++++++[->------<]>--<<[->>+<<]<+]>>>>+[-<[->++++++++++<]>>+]<.
The Algorithm    |.->,+[-[-[->+>+<<]>>[-<<+>>].<]+.-<+]
Add 40           |+[++++[->++++++++<],[->+<]>.[-]<+]

JavaScript (Node.js), 26 bytes
f=n=>n?[...f(--n),f(n)]:[]

Try it online!
Why not

Uiua, 33 characters
m←|1⟨""|$"_{_}".m-1⟩↧1.
f←$"{_}"m

Try it here!