44
\$\begingroup\$

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):

enter image description here

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:

enter image description here

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
\$\endgroup\$
  • \$\begingroup\$ May we assume you want the cut to be at a place that guarantees the maximum number of pieces? \$\endgroup\$ – DavidC Jan 14 '15 at 22:40
  • 2
    \$\begingroup\$ I'd probably say, "determine the greatest number of pieces" instead of "determine how many pieces". \$\endgroup\$ – DavidC Jan 14 '15 at 23:28
  • 1
    \$\begingroup\$ Isn't a reasonable desktop PC rather ambiguous? \$\endgroup\$ – globby Jan 15 '15 at 0:21
  • 3
    \$\begingroup\$ @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. \$\endgroup\$ – Martin Ender Jan 15 '15 at 7:48
  • 2
    \$\begingroup\$ @ZainR nope. \$\endgroup\$ – Martin Ender Jan 17 '15 at 8:48

18 Answers 18

17
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ My bad - expected result is number of pieces, not the location to produce it. \$\endgroup\$ – J... Jan 15 '15 at 11:31
  • \$\begingroup\$ Technically that's 16 characters, 28 bytes. Unicode'll do that to you =P \$\endgroup\$ – KChaloux Jan 15 '15 at 13:11
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Martin Ender Jan 15 '15 at 13:33
  • \$\begingroup\$ @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. \$\endgroup\$ – agweber Jan 15 '15 at 17:11
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Zgarb Jan 24 '15 at 9:47
16
\$\begingroup\$

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])
\$\endgroup\$
  • \$\begingroup\$ Pretty sure you could use ,QtQ instead of [QtQ) \$\endgroup\$ – FryAmTheEggman Jan 14 '15 at 23:49
  • \$\begingroup\$ 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). \$\endgroup\$ – Jakube Jan 15 '15 at 1:43
  • \$\begingroup\$ I think you are right here. Or at least I cannot find any case where this logic fails... \$\endgroup\$ – Optimizer Jan 15 '15 at 1:47
  • \$\begingroup\$ You can save a character by using g, which is >=, if you replace <dheSk with geSkd. \$\endgroup\$ – isaacg Jan 15 '15 at 3:23
  • 2
    \$\begingroup\$ Thanks @isaacg. But why do you always come along and destroy my solution, when I'm really happy and confident about it? ;-) \$\endgroup\$ – Jakube Jan 15 '15 at 9:06
15
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Christian Sonne Jan 14 '15 at 23:41
  • 4
    \$\begingroup\$ @ChristianSonne Your function doesn't return anything. \$\endgroup\$ – Jakube Jan 14 '15 at 23:46
  • \$\begingroup\$ Shoot, you're right @Jakube \$\endgroup\$ – Christian Sonne Jan 14 '15 at 23:55
  • \$\begingroup\$ 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. \$\endgroup\$ – KSFT Jan 15 '15 at 0:30
  • \$\begingroup\$ @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. \$\endgroup\$ – Sp3000 Jan 15 '15 at 0:37
10
\$\begingroup\$

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

\$\endgroup\$
10
\$\begingroup\$

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!

\$\endgroup\$
  • 10
    \$\begingroup\$ My wife can't stand XNORing \$\endgroup\$ – gnibbler Jan 14 '15 at 23:12
  • 9
    \$\begingroup\$ Time for @xnor to take notes=) \$\endgroup\$ – flawr Jan 14 '15 at 23:25
  • \$\begingroup\$ 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 \$\endgroup\$ – Dennis Jaheruddin Jan 15 '15 at 10:38
  • \$\begingroup\$ But I was so proud of my conv approach... =D. I always forget about the nnz, thank you very much! \$\endgroup\$ – flawr Jan 15 '15 at 13:57
  • \$\begingroup\$ 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... \$\endgroup\$ – flawr Jan 15 '15 at 14:16
9
\$\begingroup\$

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]]

intervals


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]]

test lines


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

\$\endgroup\$
8
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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))
\$\endgroup\$
  • \$\begingroup\$ OK, so I'm biased and just like R . FWIW you could save 3 chars by using T for "TRUE" \$\endgroup\$ – Carl Witthoft Jan 15 '15 at 15:33
  • \$\begingroup\$ @CarlWitthoft Thanks for the tip \$\endgroup\$ – MickyT Jan 15 '15 at 17:50
4
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ @MartinBüttner/Jakube I fixed it. It now works for all of the test cases in under ten seconds. \$\endgroup\$ – KSFT Jan 15 '15 at 21:23
  • \$\begingroup\$ Why are there two downvotes on this? \$\endgroup\$ – KSFT Jan 24 '15 at 0:18
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ The bare proc appears to be an acceptable answer without assigning it to a variable. Saves two characters. \$\endgroup\$ – Mark Reed Jan 17 '15 at 2:59
3
\$\begingroup\$

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));
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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]

\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Mark Reed Jan 17 '15 at 3:18
  • 1
    \$\begingroup\$ Yep. Unless stated otherwise in the challenge, unnamed functions are perfectly fine. \$\endgroup\$ – Martin Ender Jan 17 '15 at 9:35
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.