45
4
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? – DavidC – 2015-01-14T22:40:37.140
@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. – Martin Ender – 2015-01-14T22:42:38.727
2I'd probably say, "determine the greatest number of pieces" instead of "determine how many pieces". – DavidC – 2015-01-14T23:28:04.387
@DavidCarraher Yeah, I like that better, fixed. – Martin Ender – 2015-01-14T23:28:42.050
1Isn't
a reasonable desktop PC
rather ambiguous? – globby – 2015-01-15T00:21:05.447@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. – Igby Largeman – 2015-01-15T07:10:47.870
3@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. – Martin Ender – 2015-01-15T07:48:24.533
@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 – 2015-01-16T16:21:03.617
@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 ;) – Zain R – 2015-01-17T02:17:50.633
2
@ZainR nope.
– Martin Ender – 2015-01-17T08:48:11.233