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.

\$\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\$
    – Teun Pronk
    Jan 8, 2015 at 11:43
  • \$\begingroup\$ @TeunPronk It means that length 5 is impossible unless all the bits are the same \$\endgroup\$
    – Sp3000
    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\$
    – Teun Pronk
    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\$
    – Teun Pronk
    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\$ Jan 8, 2015 at 12:02

10 Answers 10

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
\$\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.

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

Dyalog APL, 62 characters

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

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

\$\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.

\$\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\$
    – Optimizer
    Jan 9, 2015 at 13:15
  • \$\begingroup\$ @Optimizer I expanded the explanation. \$\endgroup\$
    – Zgarb
    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.

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

\$\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
\$\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\$
    – edc65
    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
\$\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)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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