Is it a prefix normal word?

Question

Prefix normal words arise in the context of binary jumbled pattern matching. A binary word \$w\$ consisting of \$0\$s and \$1\$s is said to be prefix normal ^* if, among all of its substrings, none contains more \$1\$s than the prefix of \$w\$ of the same length does. In other words, if \$w\$ contains \$n\$ \$1\$s then it is prefix normal if, for all \$m\le n\$, the shortest (or equal shortest) substring containing \$m\$ \$1\$s is a prefix.

For example, \$w=\color{red}{11010}\color{blue}{11011}00100\$ is not prefix normal because it has a substring of length 5 (highlighted in blue) that contains four \$1\$s, whereas its prefix of length 5 (red) only contains three \$1\$s. If we flip the first \$0\$ to \$1\$, however, then the resulting word (\$111101101100100\$) is prefix normal.

Task

Your task in this code-golf challenge is to write a program or function that decides whether a binary word is prefix normal.

You may take input in any sensible format (e.g. string, numeric, list of characters/digits), which extends to using any pair of characters/digits instead of \$0\$ and \$1\$ if you wish.

Output/return a consistent value for every input that is prefix normal and another consistent value for every input that is not.

Test cases

Prefix normal

00000
1101010110
111101101100100
11101010110110011000
1110010110100111001000011

Not prefix normal

00001
1011011000
110101101100100
11010100001100001101
1110100100110101010010111

---

^{* Strictly, prefix normal with respect to \$1\$.}

Answer 1

Jelly, 9 7 bytes

ṡJ§Ṁ€⁼Ä

Try It Online!

-2 bytes thanks to Unrelated String

ṡJ§Ṁ€⁼Ä  Main Link
ṡ        Take overlapping slices of length(s)
 J       [1, 2, ..., length]
  §      Take the sum of each slice of each length
   Ṁ€    Is the maximum sum for each length
     ⁼   Equal to
      Ä  The cumulative sum of the original list?

Answer 2

Haskell, 57 bytes

g x=x!x
p!s=p==[]||sum p>=sum s&&init p!tail s&&g(init p)

Try it online!

---

Haskell, 66 bytes

A bit longer, but actually runs in reasonable time.

g x|k<-[1..length x]=and[h x>=h(drop n x)|h<-(sum.).take<$>k,n<-k]

Try it online!

Answer 3

JavaScript (ES6), 57 bytes

Expects an array of binary digits. Returns false for prefix normal, or true for not prefix normal.

a=>a.map(v=>a=v-~a).some((p,i,a)=>a.some(q=>q-a[~i--]>p))

Try it online!

How?

We first compute the cumulative sums of the incremented input values:

a.map(v => a = v - ~a)

(Using a = v - ~a allows us to re-use a[] to compute the sum, which is two bytes shorter than allocating a specific variable. That's the only reason why the values are incremented.)

For instance:

   1, 0, 1, 1, 0, 1, 1, 0, 0, 0
=> 2, 1, 2, 2, 1, 2, 2, 1, 1, 1
=> 2, 3, 5, 7, 8,10,12,13,14,15

We then test whether there's some pair \$(i,j)\$ with \$j>i\$ such that \$a_j-a_{j-i-1}>a_i\$.

.some((p, i, a) => a.some(q => q - a[~i--] > p))
//                             ^      ^      ^
//                           a[j]  a[j-i-1]  a[i]

Answer 4

Wolfram Language (Mathematica), 54...44 41 bytes

(l=Most@l+#-(t={##2})&@@t)&/@(t=l=#)0&

Try it online!

 is VectorGreaterEqual.

(l=Most@l+#-(t={##2})&@@t)&/@(t=l=#)        get all prefix differences by:
                             (t=l=#)          l: difference list, t: input list
                           /@                 over input length:
(l=Most@l                )&                     drop last element of l
         +#-   {##2} &@@t                       foreach, add next in prefix, subtract next in substring
                                                      e.g. (a+b+c)-(b+c+d) -> (a+b+c)-(b+c+d)+d-e
            (t=     )                           shift t left
                                    0      all nonnegative?

*strictly speaking, each element of l is also offset by corresponding input element . I suspect this doesn't matter - a brute force test of strings up to length 17 showed no differences - but I don't have a proof as to why.
If it does make a difference, +1 byte using (l=Most@l+#-{t=##2}&@t)&/@(l=0{t=##})0& instead. Try it online!

Answer 5

Jelly, 9 8 bytes

ẆẈṀƙ§Ɗ⁼Ä

Try it online!

It feels like something less naive should be shorter yet, but I haven't had any luck.

Ẇ           Get every substring of the input.
    §       Sum each substring,
   ƙ Ɗ      group the sums by
 Ẉ          the lengths of the corresponding substrings,
  Ṁ         and take the largest element of each group.
      ⁼Ä    Is the resulting list equal to the cumulative sums of the input?

Answer 6

Risky, 31 bytes

*00_{?*_1_+!?{_?+0_{?*_1_+_?*_1__[___{_0*__1*_1:____{_0{__1*_1

Input is a single argument which is a list of 0's and 1's; output is 1 if prefix normal, 0 if not. Try it online!

Explanation

This is a bit long, so I'll explain it in two halves.

00_{?*_1_+!?{_?+0_{?*_1_+_?*_1
    ?                           Input list
   {                            List of all sublists
     *_1                        Repeat once (no-op)
  _                             Same value (no-op)
        _                       Map this function to each of the sublists
                                (first arg is each sublist, second arg is original input):
          !?                     Length of first arg
            {                    Take prefix of that length from
             _?                  Second arg
         +                       Sum
 0                              Transpose (adds a level of nesting to a flat list)
               +                Concatenate that list with the following:
                  {?             List of all sublists of input list
                    *_1          Repeat once (no-op)
                 _               Same value (no-op)
                       _         Map this function to each sublist:
                         _?       First arg
                           *_1    Repeat 1 time (no-op)
                        +         Sum
0                               Transpose

At this point, we have a list of pairs \$(n_l^0, n_l^i)\$, where \$n_l^i\$ is the number of ones in the \$i^{th}\$ sublist of length \$l\$ and \$n_l^0\$ is the number of ones in the first sublist of length \$l\$. We now want to check if for every pair, \$n_l^0 \geq n_l^i\$. Equivalently, \$min(n_l^0, n_l^i) = n_l^i\$.

__[___{_0*__1*_1:____{_0{__1*_1
_                                Map this function to each pair (first arg is each pair,
                                 second arg is original input):
    __                            List of both args
      {_0                         Get 0th element (the pair)
   _                              Same value (no-op)
         *__1*_1                  Repeat 1 time (no-op)
  [                               Minimum
                :                 Equals
                   __              List of both args
                     {_0           Get 0th element (the pair)
                  _                Same value (no-op)
                        {          Get element of the pair at index
                         __1*_1    1 (the second element)
                 _                 Same value (no-op)
 _                                Same value (no-op)

We now have a list containing 0 for every sublist with more ones than the equal-length prefix, and 1 for every other sublist. The * at the beginning of the code takes the product of this list, yielding 0 for inputs with any such substrings and 1 for inputs without any.

Answer 7

Retina 0.8.2, 49 bytes

((1)|0)+(?<=(?!(?>(?<-1>(?<-2>1)|0)*)(?(2)^))^.*)

Try it online! Outputs 0 for prefix normal, 1 for not normal. Explanation:

((1)|0)+

Match some 1s and 0s, keeping count of the 1s and the total number of digits (very slightly golfier as we need a group for the +), ...

(?<=...^.*)

... then, at the beginning of the string, ...

(?>(?<-1>(?<-2>1)|0)*)

... try to consume all of the 1s, matching up to the same number of digits...

(?!...(?(2)^))

... and fail if there were enough 1s, showing that the prefix is normal.

Note that if there are two disjoint substrings with too many 1s then I think the substring containing both substrings will also have too many 1s and will therefore be found first, but I can't prove that.

Answer 8

05AB1E, 9 bytes

Œε∍OyO@}P

Input as a list of 0s/1s.

Try it online or verify all test cases.

Explanation:

Π       # Get all sublists of the (implicit) input-list
 ε       # Map over each sublist:
  ∍      #  Shorten the (implicit) input-list to a length equal to this sublist-length
   O     #  Sum this prefix
    yO   #  Sum the sublist as well
      @  #  Check that the prefix-sum is larger than or equal to the sublist-sum
 }P      # After the map: pop and take the product to check if all were truthy
         # (after which it is output implicitly as result)

Answer 9

APL (Dyalog Unicode), 14 bytes

∧/∘∊+\≥⍳∘≢+/¨⊂

Try it online!

A tacit function taking a vector of 0's and 1's

⊂ The input vector enclosed in a singleton list.
⍳∘≢ indices of the input (1 .. length input)
¨ For each of the numbers on the left and the input vector on the right:
+/ sums of all sublists of the right argument of the length given by the left argument.
+\ sums of prefixes of the input.
≥ for each prefix sum, is it larger or equal than each of the sublist sum of sublists of the same size.
∊ flatten nested list.
∧/ reduce with boolean and.

Example with input 1 0 0 1 1:

┌──┬─────────┬──────────┐
│+\│⍳∘≢+/¨⊂  │+\≥⍳∘≢+/¨⊂│
├──┼─────────┼──────────┤
│1 │1 0 0 1 1│1 1 1 1 1 │
├──┼─────────┼──────────┤
│1 │1 0 1 2  │1 1 1 0   │
├──┼─────────┼──────────┤
│1 │1 1 2    │1 1 0     │
├──┼─────────┼──────────┤
│2 │2 2      │1 1       │
├──┼─────────┼──────────┤
│3 │3        │1         │
└──┴─────────┴──────────┘

Answer 10

Scala, 74 bytes

s=>1 to s.size forall(l=>s.sliding(l).map(_.sum).forall(_<=s.take(l).sum))

Try it online!

Strategy is as follows:

• for all possible prefix lengths (1 to s.size forall{...}) check the following
  • compute the number of 1's within each sliding window of current prefix length (s.sliding(l).map(_.sum))
  • check whether all these sliding windows contain no more 1's than the first window/initial prefix (.forall(_<=s.take(l).sum))

Answer 11

Ruby, 70 60 bytes

->s,r=0..s.size{r.any?{|i|r.any?{|j|s[j,i].sum>s[0,i].sum}}}

Try it online!

• Saved 9 Bytes thanks to @Dingus suggestions !
  any? replaces first map
  We reuse entire range L=0..s.size instead of just the length

• Saved another 1 again by @Dingus
  Compares directly the sums of prefix and current range being checked

• Takes an array s of 0/1 and return false if it is prefix normal, true if not.

(1..L=s.size).map{|i|  - every length by*
(X= ... )        - we save in X:
  (0..L).map{|j|   * every index: all substrings of same length
  s[j,i].sum}      * sum 1's in slice of length i at j
.max>X[0]     - any > of 1st element?
}.any?}          - any true?

Answer 12

R, 92 bytes

Or R>=4.1, 78 bytes by replacing two function appearances with \s.

function(s,n=sum(s|1)){for(i in 1:n)F=F|which.max(sapply(0:n,function(j)sum(s[1:i+j])))-1;F}

Try it online!

Takes a vector of integers. Outputs FALSE for prefix normal and TRUE for non-prefix normal word.

---

Solution shorter in R>=4.1:

R, 98 bytes

Or R>=4.1, 77 bytes by replacing three function appearances with \s.

function(s,n=sum(s|1),g=sapply)any(g(1:n,function(i)which.max(g(0:n,function(j)sum(s[1:i+j])))-1))

Try it online!

Answer 13

Charcoal, 19 18 bytes

⊙θΦκ‹Σ…θ⁻⊕κλΣ✂θλ⊕κ

Try it online! Link is to verbose version of code. Outputs - for not normal, nothing for prefix normal. Explanation:

 θ                  Input string
⊙ Φκ                Any substring satisfies
      …θ⁻⊕κλ        Leading prefix
     Σ              Sum of digits
    ‹               Less than
             ✂θλ⊕κ  Current substring
            Σ       Sum of digits
                   Implicitly print

Answer 14

Core Maude, 186 bytes

mod P is pr NAT-LIST . var L P F X Y Z :[Nat]. ops n c : Nat ~> Nat . ceq
n(L)= F if P X 2 Y F Z := L 2 L /\ size(P)= size(F)/\ c(F)> c(P). eq c(X 1 Y)=
s c(X Y). eq c(L)= 0[owise]. endm

The answer is obtained by reducing the n function with the input bitstring as a Maude NatList of 0s and 1s. If the term is irreducible (result is an “error expression” of kind [NatList]), then the bitstring is prefix normal, otherwise (result of sort NeNatList, Nat, etc.) it is not.

Example Session

             \||||||||||||||||||/
           --- Welcome to Maude ---
             /||||||||||||||||||\
         Maude 3.1 built: Oct 12 2020 20:12:31
         Copyright 1997-2020 SRI International
           Sun Oct 17 22:18:44 2021
Maude> mod P is pr NAT-LIST . var L P F X Y Z :[Nat]. ops n c : Nat ~> Nat . ceq 
> n(L)= F if P X 2 Y F Z := L 2 L /\ size(P)= size(F)/\ c(F)> c(P). eq c(X 1 Y)= 
> s c(X Y). eq c(L)= 0[owise]. endm
Maude> red n(0 0 0 0) .
result [NatList]: n(0 0 0 0)
Maude> red n(1 1 0 1 0 1 0 1 1 0) .
result [NatList]: n(1 1 0 1 0 1 0 1 1 0)
Maude> red n(1 1 1 1 0 1 1 0 1 1 0 0 1 0 0) .
result [NatList]: n(1 1 1 1 0 1 1 0 1 1 0 0 1 0 0)
Maude> red n(1 1 1 0 1 0 1 0 1 1 0 1 1 0 0 1 1 0 0 0) .
result [NatList]: n(1 1 1 0 1 0 1 0 1 1 0 1 1 0 0 1 1 0 0 0)
Maude> red n(1 1 1 0 0 1 0 1 1 0 1 0 0 1 1 1 0 0 1 0 0 0 0 1 1) .
result [NatList]: n(1 1 1 0 0 1 0 1 1 0 1 0 0 1 1 1 0 0 1 0 0 0 0 1 1)
Maude> red n(0 0 0 0 1) .
result NzNat: 1
Maude> red n(1 0 1 1 0 1 1 0 0 0) .
result NeNatList: 1 1
Maude> red n(1 1 0 1 0 1 1 0 1 1 0 0 1 0 0) .
result NeNatList: 1 1 0 1 1
Maude> red n(1 1 0 1 0 1 0 0 0 0 1 1 0 0 0 0 1 1 0 1) .
result NeNatList: 1 1 0 0 0 0 1 1 0 1
Maude> red n(1 1 1 0 1 0 0 1 0 0 1 1 0 1 0 1 0 1 0 0 1 0 1 1 1) .
result NeNatList: 1 0 1 0 0 1 0 1 1 1
Maude> quit
Bye.

Ungolfed

mod P is
    pr NAT-LIST .
    var L P F X Y Z : [Nat] .
    ops n c : Nat ~> Nat .
    ceq n(L) = F if P X 2 Y F Z := L 2 L /\ size(P) = size(F) /\ c(F) > c(P) .
    eq c(X 1 Y) = s c(X Y) .
    eq c(L) = 0 [owise] .
endm

We use Maude's strong pattern matching and conditional equations to try every possible prefix and sublist. The c function counts the number of 1s in a list.

Interesting note: If the input term is reducible, the result will be a witness sublist with more 1s than the prefix of the same length. It did not cost any extra bytes to do so.

The [owise] attribute does not seem to be needed in the current Maude 3.1 interpreter (the interpreter seems to prefer earlier equations over later ones), but Maude's definition of an “admissible functional module” requires it. Otherwise we could save 6 bytes by omitting it.

Answer 15

Python 3, 91 79 bytes

lambda s:any(sum(s[:i-j])<sum(s[j:i])for i in range(len(s)+1)for j in range(i))

Take as input a list of integers.

Return False for prefix normal and True for prefix not normal

Thanks @UnrelatedString for -12 bytes using list of integers instead of strings

Try it online!