Into how many pieces can you cut this string?

Question

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 -2³¹ ≤ p_i < 2³¹. 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

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

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!

Answer 6

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

Answer 7

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.

Answer 8

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

Answer 9

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

Answer 10

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

Answer 11

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.

Answer 12

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

Answer 13

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

Answer 14

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

Answer 15

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]

Answer 16

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

Answer 17

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

Answer 18

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

Answer 19

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!

Answer 20

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]