0-1 Maximaler Phasenzähler

21

Betrachten Sie beispielsweise ein Array von Bits

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

Wir bezeichnen ein zusammenhängendes Subarray mit einer Länge ≥ 5 als Phase, wenn mindestens 85% der Bits gleich sind und das erste / letzte Bit dem Mehrheitsbit entspricht. Außerdem nennen wir eine Phase maximal, wenn es sich nicht um eine strikte Unteranordnung einer anderen Phase handelt.

Hier sind die maximalen Phasen des obigen Beispiels:

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

Wie Sie sehen, gibt es 3maximale Phasen. Auf der anderen Seite das

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

ist keine maximale Phase, da es sich um ein striktes Subarray von mindestens einer anderen Phase handelt.

Die Herausforderung

Die Eingabe ist eine Folge von ≥ 5 Bits über STDIN, Befehlszeile oder Funktionsargument. Die Bits können als Zeichenfolge oder als Array eingegeben werden.

Sie müssen eine einzelne Ganzzahl ausgeben, die Anzahl der maximalen Phasen für das Array, die entweder über STDOUT ausgegeben oder von einer Funktion zurückgegeben werden.

Wertung

Dies ist Code-Golf, so dass das Programm mit den wenigsten Bytes gewinnt.

Testfälle

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

Hier ist die Erklärung für den letzten Fall:

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

Unterhaltsame Tatsache: Diese Herausforderung ergab sich aus einem Data-Mining-Problem mit dem Ziel, Änderungen in zeitlichen Daten zu erkennen.

code-golf array-manipulation Sp3000
quelle
Frage, wann es ein zusammenhängendes Subarray ist. Länge ≥ 5 eine Phase, wenn mindestens 85% der Bits gleich sind Nehmen wir an, wir haben eine Länge von 5 wie 1 1 0 1 185% von 5 ist 4,25. Das heißt, Länge 5 wäre unmöglich oder sollten wir das auf 4 abrunden?
Teun Pronk
@TeunPronk Das bedeutet, dass Länge 5 nur dann möglich ist, wenn alle Bits gleich sind
Sp3000
Ich wollte gerade meinen Kommentar bearbeiten, um ihn zu ergänzen, also keine Abrundung :)
Teun Pronk
Müssen Sie also so viele Subarrays wie möglich oder so große Arrays wie möglich finden? weil ich in Testfall 5 mehr als 1 finde (nicht durch Code, sondern durch Suchen)
Teun Pronk
@TeunPronk du sollst so viele wie möglich finden, die nicht vollständig in größeren enthalten sind. Es gibt nur ein solches Array für den 5. Testfall, das am ersten beginnt 0und am letzten endet.
Martin Ender

Antworten:

8

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

Die erste Schleife tastet das Array von links nach rechts ab. Jedes durch indizierte Bit iwird überprüft, um festzustellen, ob es das erste Bit in einer maximalen Phase sein könnte.

Dies geschieht durch die innere Schleife, die von rechts nach links abtastet. Wenn das Subarray zwischen iund jeine Phase ist, erhöhen wir den Zähler und fahren fort. Andernfalls fahren wir fort, bis das Subarray zu klein wird oder j das Ende der vorherigen Maximalphase erreicht.

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

Beispiel:

$ python phase.py
[1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0]
3
grc
quelle
5

Python 2, 144

Geben Sie die Eingabe in das Formular ein [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)

Die Reihenfolge der Folgen wird durch Erhöhen des Anfangselements und Verringern der Länge überprüft. Auf diese Weise ist bekannt, dass eine neue Untersequenz keine Untersequenz einer vorherigen Untersequenz ist, wenn der Index ihres letzten Elements größer ist als ein Index des letzten Elements einer zuvor gefundenen Sequenz.

Feersum
quelle
4

Dyalog APL, 86 Byte *

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

Probieren Sie es hier aus. Verwendung:

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

Dies kann wahrscheinlich ziemlich viel Golf gespielt werden, insbesondere im Mittelteil, wo der Phasenzustand überprüft wird.

Erläuterung

Zuerst sammle ich die Teilzeichenfolgen des Eingabevektors in einer Matrix, wobei die linke obere Ecke die gesamte Eingabe enthält ⌽∘.{(⍺-1)↓⍵↑t}⍨⍳⍴t←⍵. Für die Eingabe 0 0 0 0 0 1 0ist diese Matrix

┌───────────────┬─────────────┬───────────┬─────────┬───────┬─────┬───┬─┐
│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              │             │           │         │       │     │   │ │
└───────────────┴─────────────┴───────────┴─────────┴───────┴─────┴───┴─┘

Dann ordne ich die Bedingung, eine Phase zu sein, darüber zu, was zu der 0-1-Matrix führt

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

Um die Anzahl der maximalen Phasen, ich die Flut 1‚s nach rechts und nach unten verwenden ∨⍀∨\,

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

sammeln sie die eindeutigen zeilen mit ∪↓,

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

und zählen Sie diejenigen, die mindestens eine 1Verwendung enthalten +/∨/¨.

* Es gibt eine Standard-1-Byte-Codierung für APL.

Zgarb
quelle
Nun, es ist schwer zu erklären, was ich frage. Wenn Sie eine bessere Erklärung des Codes hätten, könnte ich es umformulieren. Ich werde meinen Kommentar vorerst löschen.
Optimierer
@Optimizer Ich habe die Erklärung erweitert.
Zgarb,
1

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

und die leicht 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)))))

aufrufbar wie folgt aus : (s [0 1 0 1 0] 10 0). Es erfordert ein paar zusätzliche Argumente, aber ich könnte diese mit zusätzlichen 20 Zeichen loswerden.

Retter
quelle
0

JavaScript (ES6) 141

Der auf die JavaScript-
Eingabe portierte Algorithmus von @ grc kann ein String oder ein Array sein

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

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

Ausgabe

01010 0
00000 1
0000101111 0
000001011111 2
100000000000010 1
0000010000010000010 2
00000100000100000100 1
010100101010001111010011000110 0
111110000011111001000000001101 4
011000000000001011111110100000 5
edc65
quelle
0

CJam, 110 103 Bytes

Pretttttty lang. Kann viel golfen werden.

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

Eingabe ist wie

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

Ausgang ist die Anzahl der Phasen.

Probieren Sie es hier online aus

Optimierer
quelle
0

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}

Durchläuft das Array und startet die Iteration am letzten Rekursionsindex. Das Argument kann entweder ein Array oder eine Zeichenfolge sein.

f('011000000000001011111110100000'); //5
cPu1
quelle
1
Einige 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}
EDC65
0

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

Beispiel

{}⊕{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
Swish
quelle
0

Java: 771 Byte

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

Ausführen durch Aufrufen der Methode s (Eingabe int [])

PoweredByRice
quelle