이 줄을 몇 조각으로자를 수 있습니까? 위해 모든 점이 정수라고

실제 줄에서 앞뒤로 접는 문자열 조각 ( “로프”에서와 같이 “문자 무리”에서와 같이)을 고려하십시오. 우리는 문자열의 모양을 통과하는 점의 목록으로 (순서대로) 설명 할 수 있습니다. 간단하게하기 위해 모든 점이 정수라고 가정합니다.

예를 들어 보자 [-1, 3, 1, -2, 5, 2, 3, 4](각 항목이 접기를 의미하지는 않음).

여기에 이미지 설명을 입력하십시오

세로 방향으로 연장되는 문자열은 시각화 목적으로 만 사용됩니다. 줄이 모두 실제 줄에 납작했다고 상상해보십시오.

이제이 질문이 있습니다 :이 줄이 한 번의 절단으로 절단 될 수있는 가장 많은 수의 조각은 무엇입니까 (위 그림에서 수직이어야 함). 이 경우, 대답은 6 사이의 컷 어디서나 함께 2하고 3:

여기에 이미지 설명을 입력하십시오

모호성을 피하기 위해, 정수가 아닌 위치에서 절단 을 수행해야합니다.

도전

문자열이 접힌 정수 위치 목록이 제공되면 정수가 아닌 위치에서 단일 컷으로 문자열을 절단 할 수있는 최대 개수를 결정해야합니다.

당신은 전체 프로그램이나 함수를 작성할 수 있습니다. STDIN, 명령 줄 인수, 프롬프트 또는 함수 매개 변수를 통해 입력 할 수 있습니다. 출력을 STDOUT에 쓰거나 대화 상자에 표시하거나 함수에서 리턴 할 수 있습니다.

목록이 편리한 목록 또는 문자열 형식이라고 가정 할 수 있습니다.

이 목록에는 2 개 이상 100 개 이하의 항목이 포함됩니다. 항목은 각각 -2 31 ≤ p i <2 31 범위의 정수 입니다. 두 개의 연속 항목이 동일하지 않다고 가정 할 수 있습니다.

귀하의 코드는 합리적인 데스크탑 PC에서 10 초 이내에 이러한 입력 (아래 테스트 사례 포함)을 처리해야합니다.

테스트 사례

모든 테스트 케이스는 입력 후 출력됩니다.

[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

답변

APL, 16 14 바이트

1+⌈/+/2≠/∘.≤⍨⎕

2 바이트를 절약 한 @ngn에게 감사합니다.

는 ⎕실제로 상자 문자가 아닌 누락 된 폰트 오류입니다. 당신은 프로그램을 시도 할 수 있습니다 tryapl.org을 하지만, 이후 ⎕완전히이 지원되지 않습니다, 당신은 입력 값으로 교체해야합니다 :

    1+⌈/+/2≠/∘.≤⍨ ¯1 3 1 ¯2 5 2 3 4
6

설명

이 프로그램은 s = ¯1 3 1 ¯2 5 2 3 4STDIN에서 가져온 예제 입력으로 가장 잘 설명 됩니다 ⎕. 첫째, 우리는 계산 ≤의 외측 -σ 제품 s자체의 사용과를 ∘.≤⍨. 결과적으로 다음의 i행이 어떤 요소가 s다음보다 작거나 같은지를 나타내는 부울 행렬이 됩니다 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

의 발생 0 1및 1 0행에 i문자열이 지점을 통과 마크 장소 s[i] + 0.5. 우리는 2≠/“2 sublists by 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

남아있는 것은 행의 합을 취하는 것입니다. +/

2 5 3 0 2 3 5 3

그리고 다음과 같이 최대 값에 1을 더한 최대 값 1+⌈/:

6

대부분의 APL 구현에서 결과는 자동으로 STDOUT으로 인쇄됩니다.

답변

파이썬, 88 75 73 바이트

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

간단한 람다

다른 접근법을 보여주기 위해 :

Pyth, 28 27 바이트

heSmsmq@S+k(d)1dC,QtQm+b.5Q

이것은 대략적으로

lambda x:max(sum(a+.5==sorted(n+(a+.5,))[1]for n in zip(x,x[1:]))for a in x)+1

STDIN의 입력 목록에 적용됩니다. 온라인 통역사 에서 사용해보십시오 .

답변

Pyth : 31 30 29 28 24 23 자 (Python 68 자)

heSmsm&<hSkdgeSkdC,tQQQ

여기에서 시도하십시오 : Pyth Compiler / Executor

입력으로 정수 목록을 기대합니다.
[-1, 3, 1, -2, 5, 2, 3, 4]

내 파이썬 프로그램의 간단한 번역입니다.

lambda s:1+max(sum(min(a)<i<=max(a)for a in zip(s,s[1:]))for i in s)

기존 솔루션 : Pyth 28 char

보관 이유 때문입니다. 

heSmsm<*-dhk-dek0C,tQQm+b.5Q

해당 Python 코드는 다음과 같습니다.

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

답변

CJam, 36 34 33 30 바이트

q~[__(+]zW<f{f{1$+$#1=}1b}$W=)

나는 야생에서 더 나은 알고리즘이 있다고 생각합니다. 그럼에도 불구하고 이것은 모든 테스트 케이스에 필요한 한계 (온라인 컴파일러에서도)에서 작동합니다.

입력은 같다

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

작동 원리

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

이제 입력 배열이이라고 가정하면 [-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] [[-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]]]

마지막 줄의 두 번째 배열은 문자열의 접기입니다.

이제 우리 [-1 3 1 -2 5 2 3 4]는 각각의 세트의 수를 반복 하고 계산합니다. 그 수에서 최대 값을 가져 와서 늘리면 답이 있습니다.

여기에서 온라인으로 사용해보십시오

답변

MATLAB (123) (97) (85)

예, 마침내 XNOR =)를 사용 하면 더 많이 골프를 칠 수 있다고 확신합니다.

그러나 솔직히 MatLab이 내가 가장 잘 아는 언어가되고 있음을 조금 당혹스럽게 생각합니다 = /

대략적인 런타임은 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)

편집 : 새로운 골프 버전 (@DennisJaheruddin의 힌트를 포함하여 감사합니다!)

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)

구 버전:

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 : 나는 당신의 멋진 작은 방금 전 도전을 즐깁니다!

답변

매쓰 134 133 104

코드의 크기에도 불구하고 해결하는 재미. 의 아이디어를 IntervalMemberQ[Interval[a,b],n]로 바꾸면 골프를 계속할 수 있습니다 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

설명

list1주어진 포인트 목록은
list2접히지 않은 숫자를 제거하는 단축 된 목록입니다. 그들은 관련이 없습니다. 이를 수행 할 필요는 없지만보다 명확하고 효율적인 솔루션으로 이어집니다.

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}

간격 list1과 간격은 list2아래 그림에 나와 있습니다.

NumberLinePlot[Interval /@ Partition[list1, 2, 1]]
NumberLinePlot[intervalsArrangedVertically = Interval /@ Partition[list2, 2, 1]]

간격

접는 점에 의해 결정된 각 간격에서 단일 라인 만 테스트하면됩니다. 테스트 선은 그림에서 점선으로 된 세로 선입니다.

delimitersLeftToRight = Union[list2]
testLines = delimitersLeftToRight + .5
NumberLinePlot[
 intervalsArrangedVertically = Interval /@ Partition[list2, 2, 1],
 GridLines -> {testLines, {}},
 GridLinesStyle -> Directive[Gray, Dashed]]

테스트 라인

f각 테스트 라인의 절단 또는 교차 수를 찾습니다. x = 2.5의 선은 5 개의 교차점을 만듭니다. 5 + 1 조각의 끈이 남습니다.

f[num_, ints_] := Count[IntervalMemberQ[#, num] & /@ ints, True]
f[#, intervalsArrangedVertically] & /@ testLines
Max[%] + 1

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

답변

Pyth, 21 바이트

heSmsmq1xS+dSkdC,tQQQ

여기에서 시도하십시오.

예를 들어 파이썬 스타일 목록으로 입력하십시오. [-1, 3, 1, -2, 5, 2, 3, 4]

@jakube의 프로그램에 가깝지만 중앙 알고리즘이 향상되었습니다. 대신 일을 >체크하고 >=확인을, 나는을 .index()결합 세 개의 숫자에 있는지 인덱스보다 작거나 최대로 동일 최소보다는 그것의 더 큰 의미 1합니다.