text:
Winning Strategies for a String Construction Game
Background
Alice and Bob play a game called construct a binary word. To play the game, you fix a length n >= 0, a set G of length-n binary words called the goal set, and a length-n string t containing the letters A and B, called the turn order. The game lasts for n turns, and on turn i, the player defined by t[i] selects a bit w[i]. When the game is over, the players look at the binary word w they have constructed. If this word is found in the goal set G, Alice wins the game; otherwise, Bob wins.
For example, let's fix n = 4, G = [0001,1011,0010], and t = AABA. Alice gets the first turn, and she chooses w[0] = 0. The second turn is also Alice's, and she chooses w[1] = 0. Bob has the third turn, and he chooses w[2] = 0. On the final turn, Alice chooses w[3] = 1. The resulting word, 0001, is found in G, so Alice wins the game.
Now, if Bob had chosen w[2] = 1, Alice could have chosen w[3] = 0 in her final turn, and still win. This means that Alice can win the game no matter how Bob plays. In this situation, Alice has a winning strategy. This strategy can be visualized as a labeled binary tree, which branches at the levels corresponding to Bob's turns, and whose every branch contains a word from G:
A A B A

-0-0-0-1
    \
     1-0

Alice plays by simply following the branches on her turn; no matter which branch Bob chooses, Alice eventually wins.
Input
You are given as input the length n, and the set G as a (possibly empty) list of strings of length n.
Output
Your output is the list of turn orders for which Alice has a winning strategy, which is equivalent to the existence of a binary tree as described above. The order of the turn orders does not matter, but duplicates are forbidden.
Detailed Rules
You can write a full program or a function. In the case of a program, you can choose the delimiter for the input and output, but it must be the same for both. The shortest byte count wins, and standard loopholes are disallowed.
Test Cases
3 [] -> []
3 [000,001,010,011,100,101,110,111] -> [AAA,AAB,ABA,ABB,BAA,BAB,BBA,BBB]
4 [0001,1011,0010] -> [AAAA,BAAA,AABA]
4 [0001,1011,0010,0110,1111,0000] -> [AAAA,BAAA,ABAA,BBAA,AABA,AAAB]
5 [00011,00110,00111,11110,00001,11101,10101,01010,00010] -> [AAAAA,BAAAA,ABAAA,BBAAA,AABAA,AAABA,BAABA,AAAAB,AABAB]

Fun Fact
The number of turn orders in the output is always equal to the number of words in the goal set.

I'm rather intrigued by the fact that the input and output have equal size. Do you have a proof or citation for this fact? I wonder if there's a way to compute this function that intuitively preserves size.

Your test case #5 contradicts your fun fact...

@mbomb007 Test case #5 lists 11101 twice; the fun fact still holds for sets. Zgarb, may the input contain repeated elements, or was this an error?

@xnor This is something that came up in my research a while ago. I have a proof in this preprint, page 16, but it is essentially the same as yours.

Also, the repetition of 11101 was unintentional; I'll fix it.

@xnor Intuitively, at any turn, if both 0 and 1 are winning choices, then either Alice or Bob can choose the next move.  If there is only one winning option then Alice must choose next.  Thus the number of choices for the string is the same as the number of choices of winning strategy.  Hardly rigorous, but compelling.

Dyalog APL, 59 bytes
{(a≡,⊂⍬)∨0=⍴a←∪⍵:a⋄(∇h/t)(('A',¨∪),'B',¨∩)∇(~h←⊃¨a)/t←1↓¨a}
Same algorithm as in @xnor's solution.
(a≡,⊂⍬)∨0=⍴a←∪⍵:a
           a←∪⍵    ⍝ "a" is the unique items of the argument
        0=⍴a       ⍝ is it empty?
 a≡,⊂⍬             ⍝ is it a vector that contains the empty vector?
       ∨       :a  ⍝ if any of the above, return "a"

(∇h/t)(('A',¨∪),'B',¨∩)∇(~h←⊃¨a)/t←1↓¨a
                                 t←1↓¨a  ⍝ drop an item from each of "a" and call that "t"
                         ~h←⊃¨a          ⍝ first of each of "a", call that "h", then negate it
                                /        ⍝ use "~h" as a boolean mask to select from "t"
                       ∇                 ⍝ apply a recursive call
(∇h/t)                                   ⍝ use "h" as a boolean mask on "t", then a recursive call
      (('A',¨∪),'B',¨∩)                  ⍝ apply a fork on the results from the two recursive calls:
       ('A',¨∪)                          ⍝   prepend 'A' to each of the intersection
               ,                         ⍝   concatenated with
                'B',¨∪                   ⍝   prepend 'B' to each of the union

Python, 132
def f(S,n):
 if n<1:return S
 a,b=[f({x[1:]for x in S if x[0]==c},n-1)for c in'01']
 return{'A'+y for y in a|b}|{'B'+y for y in a&b}

Example run:
f({'000','001','010','011','100','101','110','111'},3) ==
{'ABA', 'ABB', 'AAA', 'AAB', 'BBB', 'BBA', 'BAB', 'BAA'}

This is only kind-of golfed, mostly to show the algorithm. The inputs and output are sets of strings. Python doesn't seem to have the right features to express parts of this compactly, so it would be cool if someone wrote this in a better-suited language.
Here's how the recursion can be expressed mathematically. Unfortunately, PPCG still lacks math rendering, so I'll have to use code blocks.
The objects of interest are sets of strings. Let | represent set union and & represent set intersection.
If c is a character, let c#S represent prepending the character c to all strings in S. Conversely, let the contraction c\S be the one-character-shorter strings of S that follow initial character c, e.g., 0\{001,010,110,111} = {01,10}.
We can uniquely split a set of strings S with chars in 01 by their first character.
S = 0#(0\S) | 1#(1\S)

Then, we can express the desired function f as follows, with the bases cases in the first two lines and the recursive can in the last line:
f({})   = {}
f({''}) = {''}
f(S)    = A#(f(0\S)|f(1\S)) | B#(f(0\S)&f(1\S))

Note that we don't need to use the length n.
Why does this work? Let's think about the move-strings that let Alice win for a set of strings S.
If the first character is A, Alice can pick the first move ('0' or '1'), letting her choose to reduce the problem to S0 or S1. So now the remaining move-string has to be in  at least one of f(S0) or f(S1), hence we take their union |.
Similarly, if the first character is 'B', Bob gets to pick, and he'll pick the worse one for Alice, so the remaining move-string must be in the intersection (&).
The base cases simply check if S is empty or not at the end. If we're tracking the length of the strings n, by subtracting 1 each time we recurse, the bases can instead be written:
f(S) = S if n==0

The recursive solution also explains the fun fact that f(S) has the same size as S. It's true for the base cases, and for the inductive case
f(S) = A#(f(0\S)|f(1\S)) | B#(f(0\S)&f(1\S))

we have
size(f(S)) = size(A#(f(0\S)|f(1\S)) | B#(f(0\S)&f(1\S)))
           = size(A#(f(0\S)|f(1\S))) + size(B#(f(0\S)&f(1\S))))
           = size((f(0\S)|f(1\S))) + size((f(0\S)&f(1\S))))
           = size(f(0\S)) + size(f(1\S))  [since size(X|Y) + size(X&Y) = size(X) + size(Y)]
           = size(0\S) + size(1\S)
           = size(S)

Running your code gives TypeError: 'int' object is not subscriptable. Do you have a link to a runnable program? I just pasted it and ran it with print f([0001,1011,0010],4)

@mbomb007 The function needs to be invoked like f({'000','001','010','011','100','101','110','111'},3). Do you get an error this way?

Ah, I didn't see I was missing quotes, thanks. It also runs with print f(['0001','1011','0010'],4)

If you want to run the program knowing n independent of parameters it would be n=len(S[0])if S!=[]else 0

Run it here: http://repl.it/7yI


text:
Implement slow sorting algorithm
All good coders know some good sorting algorithms like quicksort or merge sort. There is also slow sorting algorithms, e.g. bubble sort and insertion sort.
But those are such easy to implement and so, so efficient. Too efficient. Your task  is to create very slow sorting algorithm.
Please attach the Big O notation of your algorithm to your post to help us rate them. Also, please describe how your sorting algorithm works.
Input given trough STDIN. The first line contains number of arguments, and arguments are given after that. The arguments are integers in range from 0 to 105 and there are maximum 103 of them.
Output is list sorted and printed line by line into STDOUT sorted beginning from decending order.
You may not use any random numbers or any other random sources.
This is popularity-contest.

What stops me from sorting the array again and again , say, n^n times to increase the Big O ?

That depends... bogosort has a good best case.
How exactly will this be counted?

@MartinBüttner Bogobogosort

I just now saw that you could not use any random numbers or sources so I quess we can't shuffle either

You want to sort integers slowly? Why not use sleep sort? If that's still too fast for you then you make the sleep unit years! Or centuries!

Since the range of values is limited to 10^5, sleep sort actually has O(1) performance, regardless of how long the (fixed) sleep unit is.

That question was closed for not having clear winning criteria. I'm fairly certain we had a horrible sorting challenge before, but I can't seem to find one that doesn't at least have different rules and winning criteria.

@Tally, the solution to a question being closed isn't to post a duplicate which fixes (one of) its problems but to edit the original question and then request reopening.

I didn't realise, but on that note, what would then be the best course of action with the answer I made for the question?

Mathematica, Time complexity O(n * n!), Space complexity O(n!)
list = RandomInteger[10, 7]
(*{5, 5, 4, 10, 5, 10, 5}*)
permutations = Permutations@list;
Cases[permutations, l_ /; And @@ Thread[Most[RotateLeft@l - l] >= 0]][[1]]
(*{4, 5, 5, 5, 5, 10, 10}*)

This generates all permutations, discards all that aren't sorted, and then picks the first one.
Therefore, it will use O(n!) memory and O(n!) time to generate all the permutations. Then it will use O(n!) time again, to iterate through the permutations, while needing O(n) for each of them to check that they are sorted.
Note that this is both the worst case and best case complexity.

CJam, Time complexity O(n(2n+1)*log(n)), Space complexity O(n)
q~:Q,_#2#{Q$;}*Q$p

This sorts the array n2n + 1 times using Merge Sort which has time complexity of n log(n)
But really, this can be extended to any time complexity with a final output in range of Big Integer.
(Don't) try it online here
Input is like:
[1 4 2 3 1 5 6 1 2344 343 1 2 3 23 1 2 32 1 2 3 4]

and output is the sorted array
A graph comparing n * n! with n2n + 1 * log(n)

source: Stack Exchange

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

sort: votes


text:
Into how many pieces can you cut this string?
Consider a piece of string (as in "rope", not as in "a bunch of characters"), which is folded back and forth on the real line. We can describe the shape of the string with a list of points it passes through (in order). For simplicity, we'll assume all of those points are integers.
Take as an example [-1, 3, 1, -2, 5, 2, 3, 4] (note that not each entry implies a fold):

The string extending along the vertical direction is only for visualisation purposes. Imagine the string all flattened onto the real line.
Now here is the question: what is the greatest number of pieces this string can be cut into with a single cut (which would have to be vertical in the above picture). In this case, the answer is 6 with a cut anywhere between 2 and 3:

To avoid ambiguities, the cut has to be performed at a non-integer position.
The Challenge
Given a list of integer positions a string is folded through, you're to determine the greatest number of pieces the string can be cut into with a single cut at a non-integer position.
You may write a full program or a function. You may take input via STDIN, command-line argument, prompt or function parameter. You may write output to STDOUT, display it in a dialog box or return it from the function.
You may assume that the list is in any convenient list or string format.
The list will contain at least 2 and no more than 100 entries. The entries will be integers, each in the range -231 ≤ pi < 231. You may assume that no two consecutive entries are identical.
Your code must process any such input (including the test cases below) in less than 10 seconds on a reasonable desktop PC.
Test Cases
All test cases are simply input followed by output.
[0, 1]
2

[2147483647, -2147483648]
2

[0, 1, -1]
3

[1, 0, -1]
2

[-1, 3, 1, -2, 5, 2, 3, 4]
6

[-1122432493, -1297520062, 1893305528, 1165360246, -1888929223, 385040723, -80352673, 1372936505, 2115121074, -1856246962, 1501350808, -183583125, 2134014610, 720827868,  -1915801069, -829434432, 444418495, -207928085, -764106377, -180766255, 429579526,  -1887092002, -1139248992, -1967220622, -541417291, -1617463896, 517511661, -1781260846,  -804604982, 834431625, 1800360467, 603678316, 557395424, -763031007, -1336769888,  -1871888929, 1594598244, 1789292665, 962604079, -1185224024, 199953143, -1078097556, 1286821852, -1441858782, -1050367058, 956106641, -1792710927, -417329507, 1298074488,  -2081642949, -1142130252, 2069006433, -889029611, 2083629927, 1621142867, -1340561463,  676558478, 78265900, -1317128172, 1763225513, 1783160195, 483383997, -1548533202,  2122113423, -1197641704, 319428736, -116274800, -888049925, -798148170, 1768740405,  473572890, -1931167061, -298056529, 1602950715, -412370479, -2044658831, -1165885212,  -865307089, -969908936, 203868919, 278855174, -729662598, -1950547957, 679003141,  1423171080, 1870799802, 1978532600, 107162612, -1482878754, -1512232885, 1595639326,  1848766908, -321446009, -1491438272, 1619109855, 351277170, 1034981600, 421097157,  1072577364, -538901064]
53

[-2142140080, -2066313811, -2015945568, -2013211927, -1988504811, -1884073403, -1860777718,  -1852780618, -1829202121, -1754543670, -1589422902, -1557970039, -1507704627, -1410033893,  -1313864752, -1191655050, -1183729403, -1155076106, -1150685547, -1148162179, -1143013543,  -1012615847, -914543424, -898063429, -831941836, -808337369, -807593292, -775755312, -682786953, -679343381, -657346098, -616936747, -545017823, -522339238, -501194053,  -473081322, -376141541, -350526016, -344380659, -341195356, -303406389, -285611307, -282860017, -156809093, -127312384, -24161190, -420036, 50190256, 74000721, 84358785,  102958758, 124538981, 131053395, 280688418, 281444103, 303002802, 309255004, 360083648,  400920491, 429956579, 478710051, 500159683, 518335017, 559645553, 560041153, 638459051,  640161676, 643850364, 671996492, 733068514, 743285502, 1027514169, 1142193844, 1145750868,  1187862077, 1219366484, 1347996225, 1357239296, 1384342636, 1387532909, 1408330157,  1490584236, 1496234950, 1515355210, 1567464831, 1790076258, 1829519996, 1889752281,  1903484827, 1904323014, 1912488777, 1939200260, 2061174784, 2074677533, 2080731335, 2111876929, 2115658011, 2118089950, 2127342676, 2145430585]
2

May we assume you want the cut to be at a place that guarantees the maximum number of pieces?

@DavidCarraher Yes, the question is asking for the maximum number of pieces possible (with the right cut). If you have clearer phrasing than "you're to determine how many pieces the string can be cut into with a single cut at a non-integer position", please let me know.

I'd probably say, "determine the greatest number of pieces" instead of "determine how many pieces".

@DavidCarraher Yeah, I like that better, fixed.

Isn't a reasonable desktop PC rather ambiguous?

@globby: yes, but it's ambiguity that you can work with by applying common sense. You can make sensible assumptions about the users of this site, including where they likely live, what sort of occupations they likely have, and from there extrapolate what sort of computer they probably have access to. Naturally you ignore all statistical outliers, like people who happen to have access to supercomputers, or people who only have access to very old computers. In other words, imagine any typical mass-produced personal computer available in the last few years.

@globby It's a fairly common phrase we use when the runtime is not part of the winning criterion (but only used to ensure solutions aren't using brute force). It mostly means that the limit isn't 100% strict. If it takes 15 seconds on your machine (and you're not using a supercomputer), chances are, someone around here has a desktop PC where it completes in 10 seconds. But if it takes a minute on your machine that's less likely, so you'd have to think about a different approach. Also, the limit is chosen such that an efficient algorithm will easily complete in well under 10 seconds.

@MartinBüttner it's SINCE the limit was chosen that I feel it's ambiguous. I mean, I see how you could perhaps take a relatively probable guess, but imo there should be a more specific definition, especially if it's a commonly used term. Just my opinion (:

@globby Taking the rules literally, you could use a regular desktop computer to send the input to a server farm somewhere which could brute force the answer and send it back in a couple seconds ;)

@ZainR nope.

APL, 16 14 bytes
1+⌈/+/2≠/∘.≤⍨⎕

Thanks to @ngn for saving 2 bytes.
The ⎕ is actually a box character, not a missing-font error. You can try the program at tryapl.org, but since ⎕ is not fully supported there, you have to replace it by the input value:
    1+⌈/+/2≠/∘.≤⍨ ¯1 3 1 ¯2 5 2 3 4
6

Explanation
The program is best explained with the example input s = ¯1 3 1 ¯2 5 2 3 4, which is taken from STDIN by ⎕. First, we compute the ≤-outer product of s with itself using ∘.≤⍨. This results in a Boolean matrix whose ith row tells which elements of s are less than or equal to s[i]:
1 1 1 0 1 1 1 1
0 1 0 0 1 0 1 1
0 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1
0 0 0 0 1 0 0 0
0 1 0 0 1 1 1 1
0 1 0 0 1 0 1 1
0 0 0 0 1 0 0 1

The occurrences of 0 1 and 1 0 on row i mark places where the string passes over the point s[i] + 0.5. We match on these on every row using 2≠/, "reduce 2-sublists by ≠":
0 0 1 1 0 0 0
1 1 0 1 1 1 0
1 0 1 1 0 0 0
0 0 0 0 0 0 0
0 0 0 1 1 0 0
1 1 0 1 0 0 0
1 1 0 1 1 1 0
0 0 0 1 1 0 1

What remains is to take the sums of the rows with +/
2 5 3 0 2 3 5 3

and one plus the maximum of these with 1+⌈/:
6

The result is automatically printed to STDOUT in most APL implementations.

@n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳  My bad - expected result is number of pieces, not the location to produce it.

Technically that's 16 characters, 28 bytes. Unicode'll do that to you =P

@KChaloux only if you count in utf8 bytes, which you wouldn't for APL. There's a single-byte code page that contains the entire character set used by APL, so it's only fair to use that for counting.

@MartinBüttner A reliable source link would be great. Otherwise, someone could make an arbitrary web page of their own with only the set of characters used for any language to reduce byte count.

@agweber This Wikipedia page has a link to the codepage as a PDF file (the second "external link").

@agweber Yes, I usually provide the source, but I was writing that on mobile. Wikipedia has an article about the code page.

Wow, beautiful solution!  I suggest stripping off the braces to save 2 bytes: 1+⌈/+/2≠/∘.≤⍨⎕

@ngn Thanks for the tip! I have never used ⎕ for input before, since it's not supported at tryapl.org, and I don't have a standalone APL environment available (I only use it for golfing).

Amazing. APL is black magic to me.

@GuillaumeLethuillier APL is actually really easy to learn, at least to the point where you can write simple golfing answers like this. There are a few dozen functions with easy-to-remember names like × for multiplication, and very simple syntax rules. Google "mastering Dyalog APL" for a good guide.

Python, 88 75 73 bytes
lambda x:max(sum((a+.5-m)*(a+.5-n)<0for m,n in zip(x,x[1:]))for a in x)+1

Just a straightforward lambda

Just to show another approach:
Pyth, 28 27 bytes
heSmsmq@S+k(d)1dC,QtQm+b.5Q

This one's roughly equivalent to
lambda x:max(sum(a+.5==sorted(n+(a+.5,))[1]for n in zip(x,x[1:]))for a in x)+1

applied to the input list from STDIN. Try it on the online interpreter.

You can even store the function in the same amount of chars: def f(x):max(sum((a+.5-m)*(a+.5-n)<0for m,n in zip(x,x[1:]))for a in x)+1

@ChristianSonne Your function doesn't return anything.

Shoot, you're right @Jakube

I'm not entirely sure how this works, but I think you can remove the +.5s to save some characters. I realized they were pointless in mine.

@KSFT It breaks up the string into intervals, iterates over every a = point + .5 and counts the number of intervals strictly containing a. Without the .5 you'll have problems with cases like the [1, 0, -1] example.

@Sp3000 Ah, yours works differently than mine.

I think you can do min(L)<=a<max(L), taking L in place of m,n.

@xnor Jakube's done that :)

Pyth: 31 30 29 28 24 23 character (Python 68 chars)
heSmsm&<hSkdgeSkdC,tQQQ

Try it here: Pyth Compiler/Executor
It expects a list of integers as input
[-1, 3, 1, -2, 5, 2, 3, 4]
It's a straightforward translation of my Python program:
lambda s:1+max(sum(min(a)<i<=max(a)for a in zip(s,s[1:]))for i in s)

Old solution: Pyth 28 char
Just for archiving reasons.
heSmsm<*-dhk-dek0C,tQQm+b.5Q

A corresponding Python code would be:
f=lambda x:1+max(sum((i-a)*(i-b)<0for a,b in zip(x,x[1:]))for i in [j+.5 for j in x])

Pretty sure you could use ,QtQ instead of [QtQ)

i is not the intersection line, i - 0.5 is. And therefore 1  (actually 1 - 0.5 = 0.5) is inside (-1, 1). min(a)<i<=max(a) is equivalent to min(a) < i - 0.5 < max(a), which is solved in Pyth with min(a) < i < max(a)+1 (notice the h in heSk).

I think you are right here. Or at least I cannot find any case where this logic fails...

You can save a character by using g, which is >=, if you replace <dheSk with geSkd.

Thanks @isaacg. But why do you always come along and destroy my solution, when I'm really happy and confident about it? ;-)

CJam, 36 34 33 30 bytes
q~[__(+]zW<f{f{1$+$#1=}1b}$W=)

I believe that there is a better algorithm out there in the wild. Still, this works under the limit required for all test cases (even on the online compiler)
Input is like
[-2142140080 -2066313811 -2015945568 -2013211927 -1988504811 -1884073403 -1860777718  -1852780618 -1829202121 -1754543670 -1589422902 -1557970039 -1507704627 -1410033893  -1313864752 -1191655050 -1183729403 -1155076106 -1150685547 -1148162179 -1143013543  -1012615847 -914543424 -898063429 -831941836 -808337369 -807593292 -775755312 -682786953 -679343381 -657346098 -616936747 -545017823 -522339238 -501194053  -473081322 -376141541 -350526016 -344380659 -341195356 -303406389 -285611307 -282860017 -156809093 -127312384 -24161190 -420036 50190256 74000721 84358785  102958758 124538981 131053395 280688418 281444103 303002802 309255004 360083648  400920491 429956579 478710051 500159683 518335017 559645553 560041153 638459051  640161676 643850364 671996492 733068514 743285502 1027514169 1142193844 1145750868  1187862077 1219366484 1347996225 1357239296 1384342636 1387532909 1408330157  1490584236 1496234950 1515355210 1567464831 1790076258 1829519996 1889752281  1903484827 1904323014 1912488777 1939200260 2061174784 2074677533 2080731335 2111876929 2115658011 2118089950 2127342676 2145430585]

Output (for above case) is
2

How it works
q~[__(+]zW<f{f{1$+$#1=}1b}$W=)
q~                                "Evaluate input string as array";
  [__                             "Put two copies of it in an array";
     (+]                          "Shift first element of second copy to its end";
        z                         "Zip together the two arrays. This creates";
                                  "pair of adjacent elements of the input.";
         W<                       "Remove the last pair";
           f{            }        "For each element of input array, take the zipped";
                                  "array and run the code block";
             f{       }           "For each element of the zipped array along with";
                                  "the current element from input array, run this block";
               1$+                "Copy the current number and add it to the pair";
                  $#              "Sort the pair and find index of current number";;
                    1=            "check if index == 1 for a < I <= b check";
                       1b         "Get how many pairs have this number inside of them";
                          $W=)    "Get the maximum parts the rope can be cut into";

Now suppose the input array is [-1  3  1  -2  5  2  3  4], the zipping steps look like:
[-1 3 1 -2 5 2 3 4] [[-1 3 1 -2 5 2 3 4] [-1 3 1 -2 5 2 3 4]
[-1 3 1 -2 5 2 3 4] [[-1 3 1 -2 5 2 3 4] [3 1 -2 5 2 3 4 -1]
[-1 3 1 -2 5 2 3 4] [[-1 3] [3 1] [1 -2] [-2 5] [5 2] [2 3] [3 4]]]

The second array on the last line is the folds of the string.
Now we iterate over [-1 3 1 -2 5 2 3 4] and calculate the number of sets each of them lie in. Get the maximum out of that number, increment it and we have our answer.
Try it online here

Matlab (123)(97)(85)
Yay, finally a use for XNOR=) I am sure it can be golfed down way more.
But honestly I am a little embarassed that MatLab is becoming the language I know best =/
Approximate runtime is O(n^2).
EDIT2:
a=input();v=2:nnz(a);disp(max(arrayfun(@(e)sum(~xor(a(v-1)<e,e<a(v))),sort(a)-.5))+1)

EDIT: New more golfed version (including hints from @DennisJaheruddin, thanks!)
a=input();c=sort(a)-.5;n=0;v=2:nnz(c);for e=c;n=[n,sum(~xor(a(v-1)<e,e<a(v)))];end;disp(max(n)+1)

Old version:
a=input();
c=conv(sort(a),[.5,.5],'valid');' %find all cutting positions by taking the mean of two successive points
k=numel(c);
for e=1:k %iterate over all 'cuts'
    n(e)=sum(~xor(a(1:k)<c(e),c(e)<a(2:k+1)));%find the number of threads the cut cuts
end
disp(max(n)+1) %output the max

@MartinBüttner: I really enjoy your nice little just-before-I-go-to-bed-challenges!

My wife can't stand XNORing

Time for @xnor to take notes=)

I think you can save some in finding the cutting points as the folds are always integer: c=sort(a)-.5 Of course the first point is then out of the range but surely its easier to deal with that. In the worst case you can do c(1)=[];. -- Also you can strip the disp command, just calculating something will write it to stdout.--Finally in this case numel can be replaced with nnz

But I was so proud of my conv approach... =D. I always forget about the nnz, thank you very much!

I could find quite a few ways to make it even shorter that way! I am using disp since someone once critized that with the method you proposed, you also get other characters (name of the var or ans) written to stdout...

@flawr "I am a little embarassed that Matlab is becoming the language I know best". Why embarrased with that? :-)

I admit I quite like the language (and the IDE), but at least I got used to very poor techniques that you cannot use in any other language. In my perspective Matlab is a very nice playground for math-affine people, and you can get some jobs done really quickly, and it is a great tool for evaluating and visualizing data. But other than that I always get the feeling that it isn't a real programming language. During the last year I had a job where I had to use Matlab, but when I now try to do something in Java (wich is a very nice lang), the Matlab habits prevent me from getting good code...

Mathematica 134 133 104
Fun to solve, despite the size of the code.
Further golfing can still be achieved by replacing the idea of IntervalMemberQ[Interval[a,b],n] with a<n<b.
n_~f~i_:=Count[IntervalMemberQ[#,n]&/@i,1>0];
g@l_:=Max[f[#,Interval/@Partition[l,2,1]]&/@(Union@l+.5)]+1

g[{-1, 3, 1, -2, 5, 2, 3, 4}]

6

Explanation
list1 is the given list of points
list2 is a shortened list that removes numbers that were not at folds; they are irrelevant.  It's not necessary to do this, but it leads to a clearer and more efficient solution.
list1 = {-1, 3, 1, -2, 5, 2, 3, 4};
list2 = {-1, 3, 1, -2, 5,2, 3, 4} //. {beg___, a_, b_, c_, end___} /; (a <= b <= c)
 \[Or] (a >= b >= c) :> {beg, a, c, end}

The intervals in list1 and list2 are shown in the plots below:
NumberLinePlot[Interval /@ Partition[list1, 2, 1]]
NumberLinePlot[intervalsArrangedVertically = Interval /@ Partition[list2, 2, 1]]

We only need to test a single line in each interval determined by the fold points.
The test lines are the dashed vertical lines in the plot.
delimitersLeftToRight = Union[list2]
testLines = delimitersLeftToRight + .5
NumberLinePlot[
 intervalsArrangedVertically = Interval /@ Partition[list2, 2, 1],
 GridLines -> {testLines, {}},
 GridLinesStyle -> Directive[Gray, Dashed]]

f finds the number of cuts or crossings of each test line.
The line at x= 2.5 makes 5 crossings.
That leaves 5 + 1 pieces of string.
f[num_, ints_] := Count[IntervalMemberQ[#, num] & /@ ints, True]
f[#, intervalsArrangedVertically] & /@ testLines
Max[%] + 1

{2, 3, 5, 3, 2, 0}
6

Pyth, 21 bytes
heSmsmq1xS+dSkdC,tQQQ

Try it here.
Give input as Python-style list, e.g. [-1, 3, 1, -2, 5, 2, 3, 4]
Closely based off of @jakube's program, but with an improved central algorithm. Instead of doing a > check and a >= check, I do a .index() on the three numbers combined and make sure the index is 1, meaning it's greater than minimum and less than or equal to the maximum.

R, 86 83
Was working through this and then realised that I had essentially come up with the same solution as Optimizer and others I suspect.
Anyway here it is as a function that takes a vector
f=function(l)max(colSums(mapply(function(n)c(l[-1],NA,l)<=n&c(l,l[-1],NA)>=n,l),T))

OK, so I'm biased and just like R . FWIW you could save 3 chars by using T for "TRUE"

@CarlWitthoft Thanks for the tip

Python - 161
This can probably be golfed more. gnibbler helped golf this a lot.
l=input()
d={}
for i in zip(l,l[1:]):d[sum(i)/2.]=0
for i,k in zip(l,l[1:]):
 for j in[m for m in d.keys()if min(i,k)<m<max(i,k)]:d[j]+=1
print max(d.values())+1

@MartinBüttner/Jakube I fixed it. It now works for all of the test cases in under ten seconds.

Why are there two downvotes on this?

GolfScript (43 bytes)
~[.(;]zip);{$}%:x{0=:y;x{{y>}%2,=},,}%$-1=)

In terms of efficiency, this is O(n^2) assuming that comparisons take O(1) time. It breaks the input into line segments and for each starting point it counts the half-open line segments which cross it.
Online demo

Ruby, 63
Similar to the Python solutions in concept.
->a{a.map{|x|a.each_cons(2).count{|v|v.min<x&&x<=v.max}}.max+1}

Add 2 chars before the code e.g. f= if you want a named function. Thx to MarkReed.

The bare proc appears to be an acceptable answer without assigning it to a variable.  Saves two characters.

Matlab (63 43)
Input is given as a row vector passed to the function f. So for example f([-1, 3, 1, -2, 5, 2, 3, 4]) returns 6.
f=@(x)max(sum(diff(bsxfun(@le,2*x',x(1:end-1)+x(2:end)))~=0))+1

Shorter version:
f=@(x)max(sum(diff(bsxfun(@lt,x',x))~=0))+1

Octave (31)
In Octave bsxfun can be removed thanks to automatic broadcasting:
f=@(x)max(sum(diff(x'<x)~=0))+1

C#, 73 65 bytes
N=>1+N.Max(i=>N.Zip(N.Skip(1),(f,s)=>f<i+.5==i+.5<s).Count(b=>b))

Reading the rules I thought a C# lambda should do pretty well.
Edit: just found Count has a useful overload for filtering!
You can test this by defining the appropriate delegate type:
delegate int solver(int[] l);

And then
var l = new int[] { -1, 3, 1, -2, 5, 2, 3, 4 };
solver s = N=>1+N.Max(i=>N.Zip(N.Skip(1),(f,s)=>f<i+.5==i+.5<s).Count(b=>b));

Console.WriteLine(s(l));

K (ngn/k), 17 bytes
{|/+/'~~':'x>/:x}

Try it online!
Modeled after Zgarb's APL answer.

x>/:x build matrix storing whether or not each value of x is larger than each other value of x
~~':' for each "row", determine where the values change (i.e. differ each)
+/' take the sum of each row
|/ take/return the maximum sum

JavaScript (ES6) 80 82
See comments - byte count does not include assign to F (that's still needed to test)
F=l=>Math.max(...l.map(v=>l.map(t=>(n+=t>u?v<t&v>=u:v>=t&v<u,u=t),n=1,u=l[0])&&n))

Test In FireFox/FireBug console

;[
 F([0, 1])
,F([2147483647, -2147483648])
,F([0, 1, -1])
,F([1, 0, -1])
,F([-1, 3, 1, -2, 5, 2, 3, 4])
,F([-1122432493, -1297520062, 1893305528, 1165360246, -1888929223, 385040723, -80352673, 1372936505, 2115121074, -1856246962, 1501350808, -183583125, 2134014610, 720827868, -1915801069, -829434432, 444418495, -207928085, -764106377, -180766255, 429579526, -1887092002, -1139248992, -1967220622, -541417291, -1617463896, 517511661, -1781260846, -804604982, 834431625, 1800360467, 603678316, 557395424, -763031007, -1336769888, -1871888929, 1594598244, 1789292665, 962604079, -1185224024, 199953143, -1078097556, 1286821852, -1441858782, -1050367058, 956106641, -1792710927, -417329507, 1298074488, -2081642949, -1142130252, 2069006433, -889029611, 2083629927, 1621142867, -1340561463, 676558478, 78265900, -1317128172, 1763225513, 1783160195, 483383997, -1548533202, 2122113423, -1197641704, 319428736, -116274800, -888049925, -798148170, 1768740405,  473572890, -1931167061, -298056529, 1602950715, -412370479, -2044658831, -1165885212, -865307089, -969908936, 203868919, 278855174, -729662598, -1950547957, 679003141,  1423171080, 1870799802, 1978532600, 107162612, -1482878754, -1512232885, 1595639326, 1848766908, -321446009, -1491438272, 1619109855, 351277170, 1034981600, 421097157, 1072577364, -538901064])
,F([-2142140080, -2066313811, -2015945568, -2013211927, -1988504811, -1884073403, -1860777718, -1852780618, -1829202121, -1754543670, -1589422902, -1557970039, -1507704627, -1410033893,  -1313864752, -1191655050, -1183729403, -1155076106, -1150685547, -1148162179, -1143013543,  -1012615847, -914543424, -898063429, -831941836, -808337369, -807593292, -775755312, -682786953, -679343381, -657346098, -616936747, -545017823, -522339238, -501194053,  -473081322, -376141541, -350526016, -344380659, -341195356, -303406389, -285611307, -282860017, -156809093, -127312384, -24161190, -420036, 50190256, 74000721, 84358785,  102958758, 124538981, 131053395, 280688418, 281444103, 303002802, 309255004, 360083648,  400920491, 429956579, 478710051, 500159683, 518335017, 559645553, 560041153, 638459051,  640161676, 643850364, 671996492, 733068514, 743285502, 1027514169, 1142193844, 1145750868,  1187862077, 1219366484, 1347996225, 1357239296, 1384342636, 1387532909, 1408330157,  1490584236, 1496234950, 1515355210, 1567464831, 1790076258, 1829519996, 1889752281,  1903484827, 1904323014, 1912488777, 1939200260, 2061174784, 2074677533, 2080731335, 2111876929, 2115658011, 2118089950, 2127342676, 2145430585])
]

Output

[2, 2, 3, 2, 6, 53, 2]

Based on the Python lambda solutions, you don't need to assign the function value to an actual variable, so you can knock two characters off.

Yep. Unless stated otherwise in the challenge, unnamed functions are perfectly fine.

Python 2, 63 bytes
lambda x:max(sum(a-m^a-n<0for m,n in zip(x,x[1:]))for a in x)+1

Try it online!
I'm back 6 years in the future to golf the Python answers by Sp3000 and Jakube!
The improvement is shorten the core expression of (a+.5-m)*(a+.5-n)<0 or min(t)<a<=max(t) with t for m,n to:
a-m^a-n<0

This is parsed as (a-m)^(a-n)<0. Due the how XOR acts on the Python's bit representations of negative numbers, two the XOR of two numbers is negative if and only if exactly one of them is negative. So, this expression is equivalent to (a-m<0)^(a-n<0) or (a<m)^(a<n). This expresses that exactly one of m,n is smaller than a while the other one isn't, which is equivalent to min(m,n)<a<=max(m,n).

Jelly, 10 bytes
>þ`^ƝS$€Ṁ‘

Try it online!
How it works
>þ`^ƝS$€Ṁ‘ - Main link. 1 argument        e.g.   [1, 0, -1]
>þ`        - Greater than outer product          [[0, 0, 0], [1, 0, 0], [1, 1, 0]]
      $€   - Over each sublist:           e.g.   [1, 1, 0]
    Ɲ      -   Over each overlapping pair e.g.   [1, 0]
   ^       -     Perform XOR                     1
     S     -   Take the sums                     [0, 1, 1]
        Ṁ  - Take the maximum                    1
         ‘ - Increment                           2

05AB1E, 6 bytes
ε@Ôg}à

Try it online!
Explanation:
ε   }    # for each element of the input
 @       # is each element >= this one? (returns list of booleans)
  Ô      # connected uniquified
   g     # length
     à   # maximum

JavaScript (Node.js), 71 bytes
a=>Math.max(...a.map(t=>a.map(u=>s+=(a[i++]-t-.5)*(u-t-.5)<0,s=i=1)|s))

Try it online!

Add++, 27 bytes
D,w,@@,VbUG€<ÑBxs
L~,A€wM1+

Try it online!
Approach thanks to Zgarb for their APL answer
The key part of this challenge is implementing an outer product command. Unfortunately, Add++ doesn't have a builtin to do so, not does it have any way of defining functions that take other functions as arguments. However, we can still make a generalised outer product function nonetheless. As the only way for a function to be accessed inside another function is via referencing an existing function, user defined or builtin, we have to create a 'builtin' that references such a function.
A generalised "table" function would look something like this:
D,func,@@,+

D,iter,@@*, VbUG €{func}
D,table,@@, $ bRbU @ €{iter} B]

Try it online!
where func is a dyadic function that contains our operand. You can see faint similarities of this structure in the original submission, at the start of the w function, but here we want, primarily, a monadic outer product function - an outer product function that takes the same argument on both sides.
The general table function takes advantage of how the €ach quick approaches dyadic functions. If the stack looks like
 [a b c d e]

when €{func} is encountered, the € pops e, binds that as the left argument to the dyad, and maps that partial function over a, b, c, d. However, the € quick maps over the entire stack, rather than over lists. So we need to flatten the arrays passed as arguments first.
The table function works overall like this
D,func,@@,+

D,iter,		; Define our helper function iter
		;   This takes an array as its left argument
		;   And a single integer as its right argument
	@@	; Dyadic arguments - take two arguments and push to the stack
	*,	; After execution, return the entire stack, rather then just the top element
		;
		; Example arguments:	[5 6 7 8] 1
		;
	VbUG	; Unpack the array;	[5 6 7 8 1]
		;
	€{func}	; Map func over the stack
		; As func is dyadic, this pops the right argument
		;   and binds that to a monadic func
		; This then maps the remaining elements, [5 6 7 8]
		;   over the monadic call of func, yielding [6 7 8 9]
		; Now, as the * flag was defined, we return the entire array
		;   rather than just the last element.
		; We'd achieve the same behaviour by removing the flag and appending B]

D,table,	; Define the main table function
		;   This takes two arrays as arguments
		;   Returns a single 2D array representing their outer product with func
	@@,	; Take the two arrays and push to the stack
		;
		; Example arguments:	[[1 2 3 4] [5 6 7 8]]
		;
	$	; Swap;		STACK = [[5 6 7 8] [1 2 3 4]]
	bR	; Reverse last;	STACK = [[5 6 7 8] [4 3 2 1]]
	bU	; Unpack;	STACK = [[5 6 7 8] 4 3 2 1]
	@	; Reverse;	STACK = [1 2 3 4 [5 6 7 8]]
		;
		; This allows us to place the stack so that each element of
		;   the first array is iterated over with the second array
		;
	€{iter}	; Map iter;	STACK = [[6 7 8 9] [7 8 9 10] [8 9 10 11] [9 10 11 12]]
		;
	B]	; Return the whole stack;

$table>?>?
O

However, we can shorten this by quite a lot due to the fact that we need our outer table to be monadic, and only needs to apply to the argument passed. The A command pushes each argument to the stack individually, so we don't need to mess around with any stack manipulation. In short, if our argument is the array [a b c d], we need to make the stack into
[a b c d [a b c d]]

The top value is, of course, the argument.You may have noticed from the general example that bU is the unpack command i.e. it splats the top array to the stack. So to make the above configuration, we can use the code
L,bUA

Try it online!
However, this can be shortened by a byte. As an alias for L,bU, we can use the ~ flag, to splat the arguments to the stack beforehand, making our configuration example into
L~,A

Try it online!
which is the start of the second line in the program. Now we've implemented monadic outer product, we just need to implement the rest of the algorithm. Once retrieving the result of table with < (less than), and count the number of [0 1] and [1 0] pairs in each row. Finally, we take the maximum of these counts, and increment it.
The complete step for step walk through is
D,w,		; Define a function w
		;   This takes an array and an integer as arguments
		;   First, it produces the outer product with less than
		;   Then reduce overlapping pairs by XOR
		;   Finally, sum the rows
	@@,	; Take two arguments
		;
		; Example arguments:		[[0 1 2 3] 0]
		;
	VbUG€<	; Map < over the array;	STACK = [0 1 1 1]
	ÑBx	; Equals [1 0];		STACK = [1 0 0]
	s	; Sum;			STACK = [1]

L		; Define a lambda function
		;   This takes one argument, an array
	~,	;   Splat the array to the stack before doing anything
		;
		; Example argument:		[0 1 2 3]
		;
	A€w	; Map with w;		STACK = [1 1 1 0]
	M	; Maximum;		STACK = [1]
	1+	; Increment;		STACK = [2]

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:
Heaps of trouble
Challenge
You must, in the least bytes possible, implement the Binary Heap data structure and each of the following methods that operate on it:

A function which takes no arguments and returns an empty Heap
A function which takes a list of arguments with an arbitrary length and returns a Heap containing the elements
A function which takes two Heaps and merges them into a new Heap, returning it
A function which removes the root element of the Heap and reorders it accordingly, returning the root and new Heap
A function which takes an integer and a Heap, inserts it into the Heap, and returns the Heap

Clarifications

Your heap must be implemented as linking nodes created with structs, classes, custom types or equivalent, not using an array or list
You may implement either a max-heap or a min-heap, it is your choice.
You may assume that only integers are being stored in the heap
Your functions must be bound to a variable or name (and callable, obviously)
Standard loopholes are disallowed

Resources

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

No builtins, I'm guessing?

@Sp3000 Any built in heap type or methods operating on that type are disallowed, yes.

Haskell - 217
Golfed version
data H=H H Int H|E
l E=0
l(H a _ b)=1+l a+l b
i E x=H E x E
i(H a y b)x|l a>l b=H a u$i b v|1>0=H(i a v)u b where(u,v)|x>y=(x,y)|1>0=(y,x)
f=foldl i E
t E=[]
t(H a x b)=x:t a++t b
m a b=f$t a++t b
p(H a x b)=(x,m a b)

Same, but with meaningfull names. Straightforward heap implemented as a binary tree, it can be either Empty or Heap leftBranch element rightBranch.
data Heap=Heap Heap Int Heap|Empty
len Empty=0
len(Heap a _ b)=1+len a+len b
insert Empty x=Heap Empty x Empty
insert(Heap a y b)x
    |len a>len b=Heap a u$insert b v
    |1>0=Heap(insert a v)u b
    where
        (u,v)|x>y=(x,y)
             |1>0=(y,x)
fromList=foldl insert Empty
toList Empty=[]
toList(Heap a x b)=x:toList a++toList b
merge a b=fromList$toList a++toList b
pop(Heap a x b)=(x,merge a b)

I'm largely unfamiliar with Haskell so I'm having some trouble following this. Could you please add some explanation?

@Alex It is very readable code without any haskell knowledge imo. Functions perform pattern matching on the Heap datatype and do the obvious things :)

Lua - 275 (Already lost :D)
function f(s)return loadstring(s)end;f(([[a=f"_{}"b=f"t={...}&sort(t)_t"c=f"z={...}_f('x={'..&concat(z[1],',')..','..&concat(z[2],',')..'}&sort(x)_x')()"d=f"z={...}z=z[1]r=z[#z]&remove(z,#z)_z,r"e=f"z={...}&insert(z[1],z[2])_z[1]"]]):gsub("&","table."):gsub("_","return "))()

How it works:
function newHeap()
    return {}
end
function insertItemsToHeap(...)
    heap = {...}
    table.sort(heap)
    return heap
end
function margeHeaps(heap1, heap2)
    x = loadstring("return {"..table.concat(heap1,",")..","..table.concat(heap2,",").."}")()
    table.sort(x)
    return x
end
function removeRoot(...)
    z = {...}
    z = z[1]
    r = z[#z]
    table.remove(z,#z)
    return z, r
end
function insertInt(heap, int)
    table.insert(heap, int)
    return heap
end

Note: I have no previous experience with Binary Heaps once however, hope this is right.

Invalid because it is using arrays instead of data structures. See the clarifications

Lua tables are not arrays (list of items with a specific type/size) but more like objects (list of keys with values of any type). Moreover, people argue that Lua tables are a class like data structure, because their metatables allow for complex class-like behavior (Operator overloads, stuff like that). I did use the built-in table library, but that was not disallowed.

It wasn't implemented with a custom class, type, or struct. It's an invalid solution.


text:
Combinator quines
Background
You have just learned what combinatory logic is. Intrigued by the various combinators you spend quite a bit of time learning about them. You finally stumble upon this particular expression:
(S I I (S I I))

You notice that when trying to reduce it to its normal form, it reduces to itself after three steps:
(S I I (S I I))
= (I (S I I) (I (S I I)))  (1)
= (S I I (I (S I I)))      (2)
= (S I I (S I I))          (3)

You are determined to find other expressions which share this trait and begin to work on this immediately.
Rules

You may use any combination of the following combinators:
B f g x = f (g x)
C f x y = f y x
I x     = x
K x y   = x
S f g x = f x (g x)
W f x   = f x x

Application is left associative, which means that (S K K) is actually ((S K) K).
A reduction is minimal there is no other order of reduction steps which uses fewer steps. Example: if x has reduction y, then the correct minimal reduction of (W f x) is:
(W f x)
= (W f y) (1)
= f y y   (2)

and not
(W f x)
= f x x   (1)
= f y x   (2)
= f y y   (3)

Standard loopholes apply.

Task
We define the cycle of an expression to be the minimal number of reductions in between two same expressions.
Your task is to find the expression, with the number of combinators used < 100, which produces the longest cycle.
Scoring
Your score will be determined by the length of the cycle of your expression. If two people's expression have the same cycle, the answer which uses fewer combinators wins. If they both use the same number of combinators, the earlier answer wins.
Good luck and have fun!

[tag:atomic-code-golf] would fit for your tie breaker, but I wouldn't add a tag for the tie breaker. If there's not appropriate tag, then the default is [tag:code-challenge], which indicates that the challenge uses a custom winning criterion.

I think it would help if you said what associativity conventions your notation is using.

The cycle as you've defined it isn't necessarily well defined, because a given expression can have multiple reductions available.

@ThreeFx, you're mistaken. E.g. if x has a reduction to y then W f x -> W f y -> f y y or W f x -> f x x -> f x y -> f y y are different lengths.

@PeterTaylor In this case you would pick the first reduction, since it uses fewer steps. I tried to capture it in the wording "[..] the minimal number of reductions [..]". If you have an suggestion how to clarify it further, I would happily listen to it. I will also add an example to clarify the meaning.

Now the tricky thing is that someone can't claim a score just by posting a cycle; they need a proof that there is no shorter reduction, which might be computationally difficult.

@xnor This is indeed an issue, but I have faith in the participants to not intentionally abuse this fact and also in the community which judges the solutions that any "wrong" answers will be identified.

So I was generating random expressions of length 100 for a while now and can't find a cycle longer that 31. Can it be the maximum?

@swish I doubt that 31 is anywhere near the maximum. This challenge is pretty close to busy beaver territory, and I strongly suspect that the maximum answer is astronomically huge. The challenges would be (i) proving that the expression does indeed eventually reduce to itself, and (ii) showing that the proposed reduction scheme is indeed the minimal one. These are both, in general, hard problems.

Is "length" measured in characters? If so, does it include spaces? If so, are spaces compulsory, or can I write (S I I (S I I) as (SII(SII))? Or is length measured in number of base combinators instead?

@Nathaniel "Fewer combinators", see scoring.

@ThreeFx the scoring section specifies fewer combinators as a tie breaker. I'm asking about the task section, where it specifies length < 100. Do I take it from your comment that this means less that up to 99 combinators is OK, even if spaces and parentheses make the actual string longer than 100?

@Nathaniel It's combinators as well, I'll edit that.

Gotta start with something
1:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

2:(((C I (C (C I) (W I))) (W I) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

3:(((I (W I)) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

4:(((W I) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

5:(((I (C (C I) (W I))) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

6:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

7:(((C I (C (C I) (W I))) (W I) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

8:(((I (W I)) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

9:(((W I) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

10:(((I (C (C I) (W I))) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

11:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

12:(((C I (C (C I) (W I))) (W I) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

13:(((I (W I)) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

14:(((W I) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

15:(((I (C (C I) (W I))) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

16:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

17:(((C I (C (C I) (W I))) (W I) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

18:(((I (W I)) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

19:(((W I) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

20:(((I (C (C I) (W I))) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

21:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

22:(((C I (C (C I) (W I))) (W I) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

23:(((I (W I)) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

24:(((W I) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

25:(((I (C (C I) (W I))) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

26:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

27:(((C I (C (C I) (W I))) (W I) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

28:(((I (W I)) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

29:(((W I) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

30:(((I (C (C I) (W I))) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

31:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

Cycle: \$f_{\omega^{\omega^{\omega^{\omega^\omega}}}}(65536)\$, combinators: 98
W (B (S I)) (W (B (S I))) (C (C (S (C I W) (C (C (C I K))))) (C (C (C (C (C (C (S (B (S (B (S (B (S (B (S (B (B (B (B (B (B (B W)))))) (B (B (B (B (B C)))))) (B (B (B (B (B W)))))) (B (B (B (B C))))) (B (B (B (B W))))) (B (B (B C)))) (B (B (B W)))) (B (B C))) (B (B W))) (B C)) (B W))) (C I))) (S B))) (C (C (C (C (W B) (W B)) (W B))) (W B))))

This expression is similar to Y I, that has this reduction:
0:  Y I
1:  I (Y I)
2:  Y I

After the first reduction there were two possible reductions: I (Y I) -> Y I and I (Y I) -> I (I (Y I)). This is not a problem since the second will clearly take longer to finish.
We will replace the I with j, j does the same thing I does, but it needs n reductions. n is an arbitrarily large Church numeral that cannot be reduced without an argument.
j = C (C (S (C I W) (C (C (C I K))))) n
y = Y j      <- This is just to make it easier to read later.

To make sure that there is no reduction of y that takes less than n steps, most of the time there will be only one possible reduction.
Imagine we have an expression a b that can be reduced to c, we can change it to C (C a) b. This new expression cannot be reduced, but if we give it another argument it can:
C (C a) b d
C a d b
a b d
c d

This way we can lock an expression to be reduced later. This can be seen in j, it can only be reduced with an argument.
In these first reductions only the leftmost combinator can be reduced.
0:  Y (C (C (S (C I W) (C (C (C I K))))) n)
1:  C (C (S (C I W) (C (C (C I K))))) n y    <- From now on y can always be reduced,
2:  C (S (C I W) (C (C (C I K)))) y n           but as we have seen before this makes
3:  S (C I W) (C (C (C I K))) n y               the cycle longer, so we can imagine
4:  C I W n (C (C (C I K)) n) y                 it cannot be reduced.
5:  I n W (C (C (C I K)) n) y
6:  n W (C (C (C I K)) n) y

Now n received an argument, it can be reduced and it is the only possible reduction.
For now let's reduce n completely before reducing anything else.
?:  W (W (W (...(W (W  (C (C (C I K)) n)  ))...))) y
    ^  ^  ^  ^^^ ^  ^   there are n 'W's here

C (C (C I K)) n needs an argument and each W needs two, so the first W is the only reduction allowed.
?:  W (W (W (...(W (W (C (C (C I K)) n)))...))) y
?:  W (W (...(W (W (C (C (C I K)) n)))...)) y y
?:  W (...(W (W (C (C (C I K)) n)))...) y y y
?:  ...(W (W (C (C (C I K)) n)))... y y y y
    ...
?:  W (W (C (C (C I K)) n)) y ... y y y
?:  W (C (C (C I K)) n) y y ... y y y
?:  C (C (C I K)) n y y y ... y y y        <- Let's call this line L
                      ^ ^ ^^^ ^ ^ ^  there are n 'y's after the first 'y'

Now C (C (C I K)) n has an argument, the only way this can happen is if n has been fully reduced and there are no Ws left. Here we assume n has not been designed to avoid line L, when defining n later I will show how this can be done.
After reduction 6 we reduced n completely, this was not necessary, the only other thing we could reduce besides n was the Ws. It doesn't matter what order we reduce it, it will always eventually reach line L. When n is reduced it makes n copies of W, this can be done in many ways and maybe even in less than n reductions, but the Ws make n copies of y one by one, this takes n reductions independently of when it happens or if the Ws were copied efficiently. From line 6 to line L the reductions can be made in many possible orders, but it will take at least n reductions to make all the copies of y.
Continuing from line L:
>n  :   C (C (C I K)) n y y y ... y y y
>n+1:   C (C I K) y n y y ... y y y
>n+2:   C I K n y y y ... y y y
>n+3:   I n K y y y ... y y y
>n+4:   n K y y y ... y y y

The only thing we can do now is reduce the n and the Ks. For the same reason as before this also takes at least n reductions.
Each one of the n Ks deletes one of the (n+1) ys, resulting in just one y. Reducing n completely before reducing the Ks would look like this:
>n+5:       K (K (K (...(K (K y))...))) y y y ... y y
>n+6:       K (K (...(K (K y))...)) y y ... y y
>n+7:       K (...(K (K y))...) y ... y y
            ...
>2n-2:      K (K y) y y
>2n-1:      K y y
>2n  :      y

Here is one complete example of this with n = 3 = S B (W B), which should take more than 6 reductions:
^ represents the possible reductions and (^) represents the reduction that will be done. If there is more than one option, one of them will be chosen at random.
0:  Y (C (C (S (C I W) (C (C (C I K))))) (S B (W B)))
   (^)
1:  C (C (S (C I W) (C (C (C I K))))) (S B (W B)) y
   (^)
2:  C (S (C I W) (C (C (C I K)))) y (S B (W B))
   (^)
3:  S (C I W) (C (C (C I K))) (S B (W B)) y
   (^)
4:  C I W (S B (W B)) (C (C (C I K)) (S B (W B))) y
   (^)
5:  I (S B (W B)) W (C (C (C I K)) (S B (W B))) y
   (^)
6:  S B (W B) W (C (C (C I K)) (S B (W B))) y       <- beginning of the reduction of n
   (^)
7:  B W (W B W) (C (C (C I K)) (S B (W B))) y
    ^   (^)
8:  B W (B W W) (C (C (C I K)) (S B (W B))) y
   (^)
9:  W (B W W (C (C (C I K)) (S B (W B)))) y
   (^) ^
10: B W W (C (C (C I K)) (S B (W B))) y y           <- 1st copy of y
   (^)
11: W (W (C (C (C I K)) (S B (W B)))) y y           <- end of the reduction of n
   (^)
12: W (C (C (C I K)) (S B (W B))) y y y             <- 2nd copy of y
   (^)
13: C (C (C I K)) (S B (W B)) y y y y               <- 3rd copy of y
   (^)
14: C (C I K) y (S B (W B)) y y y
   (^)
15: C I K (S B (W B)) y y y y
   (^)
16: I (S B (W B)) K y y y y
   (^)
17: S B (W B) K y y y y                             <- beginning of the second reduction of n
   (^)
18: B K (W B K) y y y y
   (^)   ^
19: K (W B K y) y y y
    ^ (^)
20: K (B K K y) y y y
   (^) ^
21: B K K y y y                                     <- 1st y deleted
   (^)
22: K (K y) y y                                     <- end of the second reduction of n
   (^)
23: K y y                                           <- 2nd y deleted
   (^)
24: y                                               <- 3rd y deleted

We can see that indeed it took more than 6 reductions.
Y is not allowed in this challenge, but we can replace it with W (B (S I)) (W (B (S I))):
0:  W (B (S I)) (W (B (S I))) j
1:  B (S I) (W (B (S I))) (W (B (S I))) j
2:  S I (W (B (S I)) (W (B (S I)))) j        <- Here we don't reduce the W for the
3:  I j (W (B (S I)) (W (B (S I))) j)           same reason we don't reduce Y twice
4:  j (W (B (S I)) (W (B (S I))) j)             before the end of the cycle.
5:  W (B (S I)) (W (B (S I))) j

Now we just need to choose some n to put in the expression:
W (B (S I)) (W (B (S I))) (C (C (S (C I W) (C (C (C I K))))) n)

Using this strategy we can guarantee that for a number n this expression will need at least 2n reductions, but n has three restrictions:

n must need an argument to be reduced
n must have 80 combinators or less (so far we used 19 of the 99)
n must not avoid line L

n could be designed to avoid line L:
n = 1 = C B (B I)
C B (B I) W (C (C (C I K)) n) y
B W (B I) (C (C (C I K)) n) y
W (B I (C (C (C I K)) n)) y
B I (C (C (C I K)) n) y y
I (C (C (C I K)) n y) y

In the last line if we reduce the I it becomes line L, but we can also reduce C (C (C I K)) n y. The way we will define n avoids this because we will add 1 many times to a number that doesn't skip line L. It would have been harder to find a definition that does run into this problem, almost anything we can do is naturally forced to reach line L.
Let [a] be a function that represents \$f_a\$ in the fast-growing hierarchy. We will also need some other functions that will be implemented later, here are their definitions:
d1 f x       = x f x
d2 f g x     = x f g x
d3 f g h x   = x f g h x
d4 f g h i x = x f g h i x
...

By definition, applying [a] x times to x is equivalent to [a+1] x:
x [a] x = d1 [a] x = [a+1] x

Applying d1 to [a] increases a by 1, doing this x times gives:
x d1 [a] x = d2 d1 [a] x = [a+x] x = [a+w] x

Now that we can add \$\omega\$, we can do this x times:
x (d2 d1) [a] x = d2 (d2 d1) [a] x = [a+wx] x = [a+w^2] x

Here we have a pattern:
d1 [a] x              = [a+1  ] x
d2 d1 [a]             = [a+w  ] x
d2 (d2 d1) [a] x      = [a+w^2] x  <- we stopped here
d2 (d2 (d2 d1)) [a] x = [a+w^3] x
...
k  d2 d1 [a] x        = [a+w^k] x
d3 d2 d1 [a] x        = [a+w^w] x

And here another:
d1 [a] x                = [a+1] x
d2 d1 [a] x             = [a+w] x
d3 d2 d1 [a] x          = [a+w^w] x     <- we stopped here
d4 d3 d2 d1 [a] x       = [a+w^w^w] x
d5 d4 d3 d2 d1 [a] x    = [a+w^w^w^w] x
d6 d5 d4 d3 d2 d1 [a] x = [a+w^w^w^w^w] x

I won't prove these patterns are correct, it would take many lines and would be very repetitive, this is left as an exercise to the reader.
We will use that last function, with [a] = [0] = S B.
These are the definitions of the ds:
d1 =                                                                                B W (C I)
d2 =                                                                             B (B W) (B C (C I))
d3 =                                                                B (B (B W)) (B (B C) (B C (C I)))
d4 =                                               B (B (B (B W))) (B (B (B C)) (B (B C) (B C (C I))))
d5 =                          B (B (B (B (B W)))) (B (B (B (B C))) (B (B (B C)) (B (B C) (B C (C I)))))
d6 = B (B (B (B (B (B W))))) (B (B (B (B (B C)))) (B (B (B (B C))) (B (B (B C)) (B (B C) (B C (C I))))))

Each function uses part of the previous, this can be used to reduce the number of combinators to this expression:
S (B (S (B (S (B (S (B (S (B (B (B (B (B (B (B W)))))) (B (B (B (B (B C)))))) (B (B (B (B (B W)))))) (B (B (B (B C))))) (B (B (B (B W))))) (B (B (B C)))) (B (B (B W)))) (B (B C))) (B (B W))) (B C)) (B W) (C I) (S B) x

This expression is reducible, we can use the C (C a) b trick to solve this problem:
C (C (C (C (C (C (S (B (S (B (S (B (S (B (S (B (B (B (B (B (B (B W)))))) (B (B (B (B (B C)))))) (B (B (B (B (B W)))))) (B (B (B (B C))))) (B (B (B (B W))))) (B (B (B C)))) (B (B (B W)))) (B (B C))) (B (B W))) (B C)) (B W))) (C I))) (S B))) x

The only thing missing is the input, we can use 13 combinators to reach some big number that cannot be reduced without an argument.
The largest number I found was 65536 using 12 combinators:
C (C (C (C (W B) (W B)) (W B))) (W B)

Putting everything together gives an expression with 98 combinators and a cycle of at least \$2 f_{\omega^{\omega^{\omega^{\omega^\omega}}}}(65536)\$ reductions.
W (B (S I)) (W (B (S I))) (C (C (S (C I W) (C (C (C I K))))) (C (C (C (C (C (C (S (B (S (B (S (B (S (B (S (B (B (B (B (B (B (B W)))))) (B (B (B (B (B C)))))) (B (B (B (B (B W)))))) (B (B (B (B C))))) (B (B (B (B W))))) (B (B (B C)))) (B (B (B W)))) (B (B C))) (B (B W))) (B C)) (B W))) (C I))) (S B))) (C (C (C (C (W B) (W B)) (W B))) (W B))))
'-----------.-----------'                                     '----------------------------------------------------------------------------------------------------------------------.----------------------------------------------------------------------------------------------------------------------'  '-----------------.-----------------'
            Y                                                                                f_w^w^w^w^w                                                                                65536
                           '------------------------------------------------------------------------------------------------------------------------------------------------------------.------------------------------------------------------------------------------------------------------------------------------------------------------------'
                                                                                j

...How big is that number?

@thejonymyster Bigger than Graham's number and about the size of a Goodstein sequence starting with 10^10^19728