21
\$\begingroup\$

Consider an array of bits, say

1 1 1 0 0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 0

We call a contiguous subarray of length ≥ 5 a phase if at least 85% of the bits are the same and the first/last bits are both equal to the majority bit. Furthermore, we call a phase maximal if it is not a strict subarray of some other phase.

Here are the maximal phases of the above example:

1 1 1 0 0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 0 ------------- ------------- -------------

As you can see, there are 3 maximal phases. On the other hand, this

1 1 1 0 0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 0 ---------

is not a maximal phase as it is a strict subarray of at least one other phase.

The challenge

Input is a sequence of ≥ 5 bits via STDIN, command line or function argument. The bits may come in as a string or an array.

You are to output a single integer, the number of maximal phases for the array, either printed via STDOUT or returned from a function.

Scoring

This is code-golf so the program in the fewest bytes wins.

Test cases

0 1 0 1 0 -> 0 0 0 0 0 0 -> 1 0 0 0 0 1 0 1 1 1 1 -> 0 0 0 0 0 0 1 0 1 1 1 1 1 -> 2 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 -> 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 -> 2 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 -> 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 1 0 1 0 0 1 1 0 0 0 1 1 0 -> 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 1 0 1 -> 4 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 0 1 0 0 0 0 0 -> 5

Here's the explanation for the last case:

0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 0 1 0 0 0 0 0 --------------------------- ------------------------- ----------------- ----------------- -------------

Fun fact: This challenge came about from a data mining problem with the goal of detecting change in temporal data.

Improve this question
\$\endgroup\$
6
  • \$\begingroup\$ Question about when its a contiguous subarray. length ≥ 5 a phase if at least 85% of the bits are the same Lets say we have a length 5 like 1 1 0 1 1 85% of 5 is 4.25 which is So length 5 would be impossible or should we round that down to 4? \$\endgroup\$ Commented Jan 8, 2015 at 11:43
  • \$\begingroup\$ @TeunPronk It means that length 5 is impossible unless all the bits are the same \$\endgroup\$ Commented Jan 8, 2015 at 11:46
  • \$\begingroup\$ I was about to edit my comment to add that to it, so no rounding down it is :) \$\endgroup\$ Commented Jan 8, 2015 at 11:47
  • \$\begingroup\$ So are you meant to find as many subarrays as possible or find arrays as big as possible? because I find more than 1 in testcase 5 (not by code but by looking) \$\endgroup\$ Commented Jan 8, 2015 at 11:58
  • \$\begingroup\$ @TeunPronk you are to find as many as possible which are not entirely contained in bigger ones. There's only one such array for the 5th test case, starting at the first 0 and ending at the last one. \$\endgroup\$ Commented Jan 8, 2015 at 12:02

10 Answers 10

Reset to default
8
\$\begingroup\$

Python 2, 149 bytes

a=input() l=len(a) n=p=0 for i in range(l): for j in range(l-1,i+3,-1): if(j>p)>(.15<sum(a[i:j+1])/(j+1.-i)+a[i]+a[j]<2.85):n+=1;p=j;break print n

The first loop scans across the array from left to right. Each bit, indexed by i, is checked to see if it could be the first bit in a maximal phase.

This is done by the inner loop, which scans from right to left. If the subarray between i and j is a phase, we increase the counter and move on. Otherwise, we keep going until the subarray becomes too small or j reaches the end of the previous maximal phase.

1 1 1 0 0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 0 i -> <- j

Example:

$ python phase.py [1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0] 3
Improve this answer
\$\endgroup\$
0
5
\$\begingroup\$

Python 2, 144

Enter input in the form [0,1,0,1,0].

a=input() o=[2];i=-1 while a[i:]: j=len(a);i+=1 while j>i+4:o+=sum(j>max(o)>x==a[i]==a[j-1]for x in a[i:j])*20/(j-i)/17*[j];j-=1 print~-len(o)

Subsequences are checked with ordering by increasing initial element, then decreasing length. In this way, it is known that a new subsequence is not a subsequence of a previous subsequence iff the index of its last element is greater than any index of a previously found sequence's last element.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Dyalog APL, 62 characters

{≢∪0~⍨+/∨⍀∨\⌽∘.{((⊃=⊃∘⌽)∧(.85≤(+/⊢=⊃)÷≢)∧5≤≢)(⍺-1)↓⍵↑a}⍨⍳⍴a←⍵}

Similar to Zgarb's solution but golfed a little further.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Dyalog APL, 86 bytes*

{+/∨/¨∪↓∨⍀∨\{⊃({(.5>|k-⍵)∧.35≤|.5-⍵}(+/÷⍴)⍵)∧(5≤⍴⍵)∧(⊃⌽⍵)=k←⊃⍵}¨⌽∘.{(⍺-1)↓⍵↑t}⍨⍳⍴t←⍵}

Try it here. Usage:

 f ← {+/∨/¨∪↓∨⍀∨\{⊃({(.5>|k-⍵)∧.35≤|.5-⍵}(+/÷⍴)⍵)∧(5≤⍴⍵)∧(⊃⌽⍵)=k←⊃⍵}¨⌽∘.{(⍺-1)↓⍵↑t}⍨⍳⍴t←⍵} f 0 0 0 0 0 1 0 1 1 1 1 1 2

This can probably be golfed quite a bit, especially the middle part, where the phase condition is checked.

Explanation

I first collect the substrings of the input vector into a matrix, where the upper left corner contains the whole input, using ⌽∘.{(⍺-1)↓⍵↑t}⍨⍳⍴t←⍵. For the input 0 0 0 0 0 1 0, this matrix is

┌───────────────┬─────────────┬───────────┬─────────┬───────┬─────┬───┬─┐ │1 0 0 0 0 0 1 0│1 0 0 0 0 0 1│1 0 0 0 0 0│1 0 0 0 0│1 0 0 0│1 0 0│1 0│1│ ├───────────────┼─────────────┼───────────┼─────────┼───────┼─────┼───┼─┤ │0 0 0 0 0 1 0 │0 0 0 0 0 1 │0 0 0 0 0 │0 0 0 0 │0 0 0 │0 0 │0 │ │ ├───────────────┼─────────────┼───────────┼─────────┼───────┼─────┼───┼─┤ │0 0 0 0 1 0 │0 0 0 0 1 │0 0 0 0 │0 0 0 │0 0 │0 │ │ │ ├───────────────┼─────────────┼───────────┼─────────┼───────┼─────┼───┼─┤ │0 0 0 1 0 │0 0 0 1 │0 0 0 │0 0 │0 │ │ │ │ ├───────────────┼─────────────┼───────────┼─────────┼───────┼─────┼───┼─┤ │0 0 1 0 │0 0 1 │0 0 │0 │ │ │ │ │ ├───────────────┼─────────────┼───────────┼─────────┼───────┼─────┼───┼─┤ │0 1 0 │0 1 │0 │ │ │ │ │ │ ├───────────────┼─────────────┼───────────┼─────────┼───────┼─────┼───┼─┤ │1 0 │1 │ │ │ │ │ │ │ ├───────────────┼─────────────┼───────────┼─────────┼───────┼─────┼───┼─┤ │0 │ │ │ │ │ │ │ │ └───────────────┴─────────────┴───────────┴─────────┴───────┴─────┴───┴─┘

Then I map the condition of being a phase over it, resulting in the 0-1-matrix

0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

To get the number of maximal phases, I flood the 1's to the right and down using ∨⍀∨\,

0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

collect the unique rows with ∪↓,

┌───────────────┬───────────────┐ │0 0 0 0 0 0 0 0│1 1 1 1 1 1 1 1│ └───────────────┴───────────────┘

and count those that contain at least one 1 using +/∨/¨.

*There exists a standard 1-byte encoding for APL.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Well, its hard to explain what I am asking. If you had a better explanation of the code, then I could rephrase. I will delete my comment for now. \$\endgroup\$ Commented Jan 9, 2015 at 13:15
  • \$\begingroup\$ @Optimizer I expanded the explanation. \$\endgroup\$ Commented Jan 9, 2015 at 13:34
1
\$\begingroup\$

Clojure, 302

(defn p[v l](if(or(<(count v)5)(= 0 l))nil(if((fn[v](let[f(first v)c(apply + v)o(count v)r(/ c o)t(+ f f r)](and(= f(last v))(or(> t 2.85)(< t 0.15)))))v)0(let[r(p(vec(drop-last v))(dec l))](if r(+ r 1)r)))))(defn s[v l c](if(empty? v)c(let[n(p v l)](if n(s(vec(rest v))n(inc c))(s(vec(rest v))l c)))))

and the slightly ungolfed version

(defn is-phase [vector] (let [f (first vector) c (apply + vector) o (count vector) r (/ c o) t (+ f f r)] (and (= f (last vector)) (or (> t 2.85) (< t 0.15))))) (defn phase-index [vector last] (if (or (<(count vector)5)(= 0 last)) nil (if (is-phase vector) 0 (let [r (phase-index (vec(drop-last vector)) (dec last))] (if r (+ r 1) r))))) (defn phase-count [vector last count] (if (empty? vector) count (let [n (phase-index vector last)] (if n (phase-count (vec(rest vector)) n (inc count)) (phase-count (vec(rest vector)) last count)))))

callable like this: (s [0 1 0 1 0] 10 0). It requires a few extra arguments, but I could get rid of those with an extra 20 characters.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6) 141

@grc's algorithm ported to JavaScript
Input can be a string or an array

F=b=> (l=>{ for(c=e=i=0;i<l;++i) for(j=l;j>i+4&j>e;--j) (k=0,[for(d of b.slice(i,j))k+=d==b[i]],k<(j-i)*.85)|b[i]-b[j-1]||(++c,e=j) })(b.length)|c

Test In FireFox / FireBug console

;['01010', '00000', '0000101111', '000001011111', '100000000000010', '0000010000010000010', '00000100000100000100', '010100101010001111010011000110', '111110000011111001000000001101', '011000000000001011111110100000'].forEach(t => console.log(t,F(t)))

Output

01010 0 00000 1 0000101111 0 000001011111 2 100000000000010 1 0000010000010000010 2 00000100000100000100 1 010100101010001111010011000110 0 111110000011111001000000001101 4 011000000000001011111110100000 5
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

CJam, 110 103 bytes

Pretttttty long. Can be golfed a lot.

q~_,,\f>{_,),5>\f<{:X)\0==X1b_X,.85*<!\.15X,*>!X0=!*\X0=*+&},:,W>U):U+}%{,(},_{{_W=IW=>\1bI1b>!&!},}fI,

Input is like

[0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 0 1 0 0 0 0 0]

Output is the number of phases.

Try it online here

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

JavaScript (ECMAScript 6), 148 139 Bytes

f=(s,l=0,e=0,p=0)=>{for(n=s.length,o=[j=0,y=0],i=l;i<n;++j>4&x==s[l]&i>e&c>=.85‌​*j&&(e=i,y=1))c=++o[x=s[i++]];return l-n?f(s,l+1,e,p+y):p}

Recurses through the array and starts iteration at the last recursion index. Argument can be either an array or string.

f('011000000000001011111110100000'); //5
Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Some golf tricks: -11. f=(s,l=0,e=0,p=0)=>{for(n=s.length,o=[j=0,y=0],i=l;i<n;++j>4&x==s[l]&i>e&c>=.85*j&&(e=i,y=1))c=++o[x=s[i++]];return l-n?f(s,l+1,e,p+y):p} \$\endgroup\$ Commented Jan 8, 2015 at 18:27
0
\$\begingroup\$

Wolfram - 131

{x_, X___}⊕{Y__, x_, y___}/;MemberQ[t={x, X, Y, x}, 1-x] && t~Count~x > .85 Length@t := 1 + {X, Y, x}⊕{y} {_, X___}⊕y_ := {X}⊕y {}⊕{y_, Y__} := {y}⊕{Y} _⊕_ := 0

Example

{}⊕{1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0} > 3 {}⊕{0,1,1,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,1,1,1,1,1,0,1,0,0,0,0,0} > 5
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Java: 771 bytes

import java.util.*;public class A{static int[]a;static class b{int c,d,e,f,g,h;b(int i,int j){this.c=i;this.d=j;this.h=j-i+1;this.e=k();this.f=this.h-this.e;this.g=e>f?1:0;} boolean l(b n){return this.c>=n.c&&this.d<=n.d;} int k(){int o=0;for(int i=c;i<=d;i++){if(a[i]==1){o++;}} return o;} public boolean equals(Object o){b x=(b)o;return x.c==this.c&&x.d==this.d;} float p(){if(g==0){return(float)f/h;}else{return(float)e/h;}} boolean q(){float r=p();return a[c]==a[d]&&a[d]==g&&r>=0.85F;}} static int s(int[]t){a=t;List<b>u=new ArrayList<>();for(int v=0;v<t.length-4;v++){int x=v+4;while(x<t.length){b y=new b(v,x);if(y.q()){u.add(y);} x++;}} List<b>a=new ArrayList<>();for(b c:u){for(b d:u){if(!c.equals(d)&&c.l(d)){a.add(c);break;}}} u.removeAll(a);return u.size();}}

run by calling method s(int[] input)

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.