# 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? Jan 14 '15 at 22:40
• I'd probably say, "determine the greatest number of pieces" instead of "determine how many pieces". Jan 14 '15 at 23:28
• Isn't a reasonable desktop PC rather ambiguous? Jan 15 '15 at 0:21
• @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. Jan 15 '15 at 7:48
• @ZainR nope. Jan 17 '15 at 8:48

# 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.
– J...
Jan 15 '15 at 11:31
• Technically that's 16 characters, 28 bytes. Unicode'll do that to you =P Jan 15 '15 at 13:11
• @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. Jan 15 '15 at 13:33
• @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. Jan 15 '15 at 17:11
• @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. Jan 24 '15 at 9:47

# Python, 8875 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 Jan 14 '15 at 23:41
• @ChristianSonne Your function doesn't return anything. Jan 14 '15 at 23:46
• Shoot, you're right @Jakube Jan 14 '15 at 23:55
• 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
Jan 15 '15 at 0:30
• @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. Jan 15 '15 at 0:37

# Pyth: 3130292824 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) Jan 14 '15 at 23:49
• 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). Jan 15 '15 at 1:43
• I think you are right here. Or at least I cannot find any case where this logic fails... Jan 15 '15 at 1:47
• You can save a character by using g, which is >=, if you replace <dheSk with geSkd. Jan 15 '15 at 3:23
• Thanks @isaacg. But why do you always come along and destroy my solution, when I'm really happy and confident about it? ;-) Jan 15 '15 at 9:06

# 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";

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!

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]