36
\$\begingroup\$

Given a pattern (string or array format) of Bits : [0,1,1,1,0,1,1,0,0,0,1,1,1,1,1,1]

The tasks is to replace any number of consecutive 1-Bits with an ascending number sequence starting at 1.

Input

  • Pattern (can be received as an string or array) Example:
    • String: 1001011010110101001
    • Array: [1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1]

Output

  • Ascending number sequence (can be returned as an string or array) Example:
    • String: 1 0 0 1 0 1 2 0 1 0 1 2 0 1 0 1 0 0 1
    • Array: [1, 0, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0, 1, 0, 1, 0, 0, 1]

Rules

  • (only apply for strings) Input wont contain spaces between 1 and 0
  • Assume Input length > 0
  • (only apply for strings) Output is separated by space (use any other separator if you need as long as is not a number or a letter from the alphabet)

Example:

Given [0,1,1,1,0,1,1,0,0,0,1,1,1,1,1,1] 
Output [0,1,2,3,0,1,2,0,0,0,1,2,3,4,5,6]

--------------------------------------------------------------------------

Given 0110101111101011011111101011111111     
Output 0 1 2 0 1 0 1 2 3 4 5 0 1 0 1 2 0 1 2 3 4 5 6 0 1 0 1 2 3 4 5 6 7 8

---------------------------------------------------------------------------

Given 11111111111101    
Output 1 2 3 4 5 6 7 8 9 10 11 12 0 1

Winning criteria: Codegolf

\$\endgroup\$

56 Answers 56

19
\$\begingroup\$

05AB1E, 4 bytes

γ€ƶ˜

Try it online! or as a Test Suit

Explanation

γ      # split input into groups of consecutive equal elements
 €ƶ    # multiply each number in each sublist by its 1-based index in the sublist
   ˜   # flatten
\$\endgroup\$
  • 1
    \$\begingroup\$ Oof, better than mine. I would've never thought of this. \$\endgroup\$ – Magic Octopus Urn Jun 29 '18 at 13:25
  • 3
    \$\begingroup\$ I'm not 100% familiar with codegolf byte-counting rules (and googling only found this post which didn't come to a conclusion). While your answer is 4 characters shouldn't it at least be 8 bytes (e.g., utf-16-be without BOM 03 B3 20 AC 01 B6 02 DC) or 9 bytes (utf-8: CE B3 E2 82 AC C6 B6 CB 9C) or 10 bytes (e.g., UTF-16 including the 2 byte BOM) in any non-toy encoding? (Yes, one could construct a toy 8-bit encoding similar to iso-8859 encodings with these 4 symbols represented as 1-byte, but that seems like cheating.) \$\endgroup\$ – dr jimbob Jun 30 '18 at 14:10
  • 6
    \$\begingroup\$ @drjimbob Yes, good question. The code can actually be converted to a binary file using the 05AB1E code page. For example, γ€ƶ˜ would be represented as 04 80 8F 98. The code page primarily exists to make writing code easier. To run this 4-byte file, you would need to run the interpreter with the --osabie flag. \$\endgroup\$ – Adnan Jun 30 '18 at 19:00
18
\$\begingroup\$

Haskell, 15 bytes

scanl1$(*).succ

Try it online!

Explanation/Ungolfed

scanl1 iterates from left over a list using a function which takes the last result and the current element generating a new list with the results, leaving empty lists and singletons "unmodified".

(*).succ is the equivalent of \x y-> (x+1)*y

Using that function together with scanl1 only works because the increasing sequences (1,2,3,..) start with 1 and either have no preceding element (in which case it's the first element in the list which won't be "modified") or they have a leading 0.

\$\endgroup\$
15
\$\begingroup\$

Python 2, 36 bytes

c=0
for i in input():c=c*i+i;print c

Try it online!

\$\endgroup\$
14
\$\begingroup\$

Husk, 5 4 3 bytes

ṁ∫g

Try it online!

Explanation

ṁ∫g  -- full function, example input: [1,1,1,0,1]
  g  -- group: [[1,1],[0],[1]]
ṁ    -- map the following and concatenate result (example with [1,1,1])
 ∫   -- | cumulative sum: [1,2,3]
     -- : [1,2,3,0,1]

Edit history

-1 byte by using scanl1 over zipWith

-1 byte by porting Dennis's solution

\$\endgroup\$
12
\$\begingroup\$

APL (Dyalog Unicode), 5 bytes

⊥⍨¨,\

Try it online!

How it works

⊥⍨¨,\
   ,\  ⍝ Convert to lists of first n elements
⊥⍨¨    ⍝ Map "Count trailing ones" to each list
\$\endgroup\$
  • \$\begingroup\$ Nice usage of the ⊥⍨ trick. \$\endgroup\$ – Zacharý Jun 30 '18 at 18:52
11
\$\begingroup\$

JavaScript (ES6), 22 bytes

Takes input as an array.

a=>a.map(s=n=>s=n*-~s)

Try it online!

The shorter a=>a.map(n=>a=n*-~a) (20 bytes) would unfortunately fail on [1] because of coercion of singleton arrays to the integer they're holding.

\$\endgroup\$
10
\$\begingroup\$

J, 4 bytes

#.~\

A port of Bubbler's APL solution

Try it online!

J, 8 bytes

i.&0@|.\

How?

It's simply the distance to the preceding 0

       \  for each prefix
     |.   reverse it
    @     and
i.&0      find the index of the first 0

Try it online!

\$\endgroup\$
8
\$\begingroup\$

Python 2, 39 38 bytes

-1 byte thanks to Erik the Outgolfer

i=1
for x in input():i*=x;print i;i+=1

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ I don't think you need the ,. \$\endgroup\$ – Erik the Outgolfer Jun 29 '18 at 14:13
  • \$\begingroup\$ @EriktheOutgolfer it looks prettier this way c: \$\endgroup\$ – Rod Jun 29 '18 at 14:20
  • 1
    \$\begingroup\$ Sorry, but sometimes, in life, you have to make sacrifices. \$\endgroup\$ – Erik the Outgolfer Jun 29 '18 at 14:29
  • 9
    \$\begingroup\$ RIP , you're not in the code anymore, but you will be forever in my heart \$\endgroup\$ – Rod Jun 29 '18 at 14:45
6
\$\begingroup\$

Jelly, 4 bytes

‘×¥\

Try it online!

‘×¥\
   \   Accumulate the input with:
  ¥   The dyad
‘      Increment the left element
 ×    Multiply by the second element (1 or 0)
       The result always begins with the first element unchanged
\$\endgroup\$
6
\$\begingroup\$

K (oK), 11 8 bytes

Solution:

{y*1+x}\

Try it online!

Explanation:

Iterate over the list. Increment accumulator, multiply by current item (which resets accumulator if item is 0):

{y*1+x}\ / the solution
{     }\ / iterate (\) over lambda function
     x   / accumulator
   1+    / add 1
 y*      / multiply by current item
\$\endgroup\$
5
\$\begingroup\$

Jelly, 4 bytes

ŒgÄF

Try it online!

How it works

ŒgÄF  Main link. Argument: A (bit array)

Œg    Group adjacent, identical bits.
  Ä   Accumulate; take the cumulative sum of each chunk.
   F  Flatten.
\$\endgroup\$
  • \$\begingroup\$ With the group runs quick Erik had suggested this would be three bytes! (If I understood what it would do correctly) \$\endgroup\$ – dylnan Jun 29 '18 at 15:02
  • \$\begingroup\$ @dylnan The problem is that it's hard to decide on a behavior for such a quick. :( That's why the quick is still in hiatus. \$\endgroup\$ – Erik the Outgolfer Jun 29 '18 at 15:07
  • \$\begingroup\$ There could be multiple quicks for the main possible implementations \$\endgroup\$ – dylnan Jun 29 '18 at 15:08
5
\$\begingroup\$

R, 46 31 bytes

function(a)sequence(rle(a)$l)*a

Try it online!

sequence, which "mainly exists in reverence to the very early history of R", is quite handy here.

function(a)                       # function, taking a vector as argument
                    rle(a)$l      # take the lengths of the run-length encoding
           sequence(        )     # and generate the list [1:x for x in lengths]
                             *a   # multiply by a to maintain 0s, and return
\$\endgroup\$
5
\$\begingroup\$

RAD, 8 bytes

(⊢×1+⊣)⍂

Try it online!

How?

  • (⊢×1+⊣), if the right argument is 0, return 0, otherwise increment the left argument
  • , LTR Scan ((A f B) f C instead of A f (B f C)) , apply this across the array
\$\endgroup\$
4
\$\begingroup\$

Japt, 7 6 5 bytes

åÏ*°X

Try it


Explanation

åÏ        :Cumulatively reduce
   °X     :  Increment the current total (initially 0)
  *       :  Multiply by the current element
\$\endgroup\$
4
\$\begingroup\$

Java 8, 55 48 bytes

a->{int p=0,i=0;for(int v:a)a[i++]=v<1?p=0:++p;}

Modifies the input-array instead of returning a new one to save bytes.

-7 bytes thanks to @TimSeguine.

Try it online.

Explanation:

a->{             // Method with integer-array parameter and no return-type
  int p=0,       //  Previous integer, starting at 0
      i=0;       //  Index-integer, starting at 0
  for(int v:a)   //  Loop over the values of the input-array:
    a[i++]=v<1?  //   If the current value is 0:
          p=0    //    Reset the previous integer to 0
         :       //   Else:
          ++p;}  //    Increase `p` by 1 first with `++p`
                 //    and set the current item to this new value of `p`
\$\endgroup\$
  • 1
    \$\begingroup\$ You can shave it down to 48: a->{int p=0,i=0;for(int b:a)a[i++]=b<1?p=0:++p;} \$\endgroup\$ – Tim Seguine Jul 2 '18 at 14:42
  • \$\begingroup\$ @TimSeguine Thanks! Now that I see it I can't believe I hadn't thought about it myself. \$\endgroup\$ – Kevin Cruijssen Jul 2 '18 at 14:46
  • 1
    \$\begingroup\$ I was able to get rid of p, but it is the same size :( a->{int i=0;for(int v:a)a[i]+=v*i++<1?0:a[i-2];} \$\endgroup\$ – Tim Seguine Jul 2 '18 at 15:08
4
\$\begingroup\$

TIS, 68 + 33 = 101 bytes

Code (68 bytes):

@0
MOV UP ACC
SUB 47
MOV ACC ANY
@1
ADD 1
JRO UP
SUB ACC
MOV ACC ANY

Layout (33 bytes):

2 1 CC I0 ASCII - O0 NUMERIC - 32

Try it online!

Explanation:

|    Input 0    |    Input is given in ASCII (`0` is 48, `1` is 49)
+--------+------+
| Node 0 |      |    This node prepares the input data
+--------+      |
| MOV UP ACC    |    Read in a character
| SUB 47        |    Subtract 47 to map [48, 49] to [1, 2]
| MOV ACC ANY   |    Send the 1 or 2 to the next node
|               |    Implicitly wrap back to top of node
+--------+------+
| Node 1 |      |    This node does the incrementing/printing
+--------+      |
| ADD 1         |    Increment counter (starts at zero)
| JRO UP        |    Get value from above, and jump forward that many lines  (skip next line or not)
| SUB ACC       |    Reset counter to zero (if input was zero)
| MOV ACC ANY   |    Send the counter value downward to be printed
|               |    Implicitly wrap back to top of node
+---------------+
|   Output 0    |    Output is space-delimited numeric values
\$\endgroup\$
4
\$\begingroup\$

Gaia, 5 bytes

ẋ+⊣¦_

Try it online!

Explanation

ẋ+⊣¦_     Full program
ẋ         Split into chunks of equal adjacent values.
   ¦_     And for each chunk, flattening the result afterwards...
 +⊣       Reduce it cumulatively on + (addition); aka cumulative sums

Ugh, I thought SE code fonts were monospace....

\$\endgroup\$
  • \$\begingroup\$ They are monospace... There is a space missing on the first line. \$\endgroup\$ – micsthepick Jul 3 '18 at 7:49
  • \$\begingroup\$ Look at the edit. It is still misaligned. \$\endgroup\$ – Mr. Xcoder Jul 3 '18 at 7:50
  • \$\begingroup\$ You must be looking from a mobile device or something - It looks fine to me \$\endgroup\$ – micsthepick Jul 3 '18 at 8:01
  • \$\begingroup\$ @micsthepick I'm not... \$\endgroup\$ – Mr. Xcoder Jul 3 '18 at 8:07
4
\$\begingroup\$

C (gcc), 45 44 38 bytes

f(a,i)int*a;{while(--i)*++a*=-~a[-1];}

Try it online!

Save one byte thanks to Toby Speight!

Save 6 bytes by using *= and a smarter while condition.

\$\endgroup\$
  • \$\begingroup\$ You can save 1 byte: *(a-1)a[-1] \$\endgroup\$ – Toby Speight Jul 5 '18 at 12:52
  • \$\begingroup\$ Welcome to PPCG! :) \$\endgroup\$ – Shaggy Jul 6 '18 at 9:48
4
\$\begingroup\$

Perl 6, 29 24 18 bytes

-6 bytes thanks to Sean!

*.map:{($+=1)*=$_}

Try it online!

The inner function could by ($+=1)*=*, but then the anonymous variable would persist across function calls. We get by this by wrapping it in an explicit code block.

Explanation:

*.map:               # Map the array to
      {($+=1)    }   # The anonymous variable incremented
             *=$_    # Multiplied by the element
\$\endgroup\$
  • \$\begingroup\$ I got the same basic approach down to 16 bytes: *.map(($+=1)*=*). This solution has the proviso that the state variable $ persists across calls to the function, so if the final element passed to one call and the first element passed to the next call are both nonzero, then the counting will start with the wrong number. \$\endgroup\$ – Sean Oct 31 '18 at 23:31
  • \$\begingroup\$ @Sean, Yeah I remember struggling with that when I originally answered. Fortunately I've learned a way around that since then \$\endgroup\$ – Jo King Nov 1 '18 at 0:15
  • \$\begingroup\$ You can knock one more byte off: *.map:{...}. \$\endgroup\$ – Sean Nov 1 '18 at 0:19
3
\$\begingroup\$

Jelly, 5 bytes

ṛȧ+ɗ\

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Haskell, 19 bytes

scanl1$((*)=<<).(+)

Try it online!

Explanation: The code is equivalent to scanl1(\b a->(b+a)*a), where b is the current bit and a is the accumulator. scanl1 takes a list, instantiates the first list element as accumulator, and folds over the list and collects the intermediate values in a new list.

Edit: BMO beat me by a few seconds and 4 bytes.

\$\endgroup\$
3
\$\begingroup\$

Pyth, 6 bytes

m=Z*hZ

Try it here!

How it works

m=Z*hZ – Full program. Q = the evaluated input.
m      – For each integer d in Q.
 =Z    – Assign the variable Z (preinitialised to 0) to...
   *hZ – (Z + 1) * d; (d is implicit at the end).
\$\endgroup\$
3
\$\begingroup\$

Wanted to get an answer in using regular expressions. There is probably an easier solution which I leave as an exercise for the reader.

PowerShell Core, 86 bytes

Filter F{($_-split"(0)(\B|\b)"|?{$_-ne''}|%{$_-replace'(1+)',(1..$_.Length)})-join' '}

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 16 bytes

FoldList[+###2&]

Try it online!

\$\endgroup\$
3
\$\begingroup\$

QBasic, 60 bytes

INPUT s$
FOR i=1TO LEN(s$)
b=MID$(s$,i)>="1
v=-b*v-b
?v
NEXT

Takes the input as a string; gives the output as numbers separated by newlines.

Explanation

We read the string s$ and loop i from 1 up to its length.

MID$(s$,i) gets the substring from character i (1-indexed) to the end of the string. If this starts with a 1, it will be lexicographically >= the string "1"; if it starts with a 0, it will not be. So b gets 0 if the character at index i is 0, or -1 if the character is 1.

Next, we update the current value v. If we just read a 0, we want v to become 0; otherwise, we want to increment v by one. In other words, v = (-b) * (v+1); simplifying the math gives the shorter expression seen in the code. Finally, we print v and loop.

\$\endgroup\$
3
\$\begingroup\$

Brain-Flak, 60 bytes

([]){{}<>(())<>{{}<>({}({}))(<>)}{}([])}{}<>{({}[()]<>)<>}<>

Try it online!

Explanation:

([]){  For each element in the input
    {}
    <>(())<>  Push a one to the other stack
    { If the element is one,
       {}<>({}({}))(<>)  Add the one to a copy of the previous number in the series
    }{}  Pop the element
([])}  End loop
{}<>   Pop extra zero
{({}[()]<>)<>}<>   And reverse the output stack, subtracting one from each element
\$\endgroup\$
3
\$\begingroup\$

Retina, 14 bytes

rv`0|(1)+
$#1¶

Try it online!

\$\endgroup\$
3
\$\begingroup\$

C (gcc), 57 52 51 bytes

f(a,l,c,i)int*a;{for(c=i=0;i<l;)a[i++]=c=a[i]*-~c;}

Port of Arnauld's JavaScript answer, modifies the array in-place. Try it online here.

\$\endgroup\$
  • \$\begingroup\$ Wouldn't it be more accurate to say this is K&R C? \$\endgroup\$ – Tim Seguine Jul 1 '18 at 13:14
  • \$\begingroup\$ Possibly, but that would be true of a lot of answers. I'm no expert, but it's entirely possible it's not even valid K&R C. The thing is, we don't really care about the language standards on this site. If gcc allows you to mix K&R C with more modern stuff, then it's valid C for the purposes of golfing because gcc will compile it. See also: codegolf.stackexchange.com/questions/2203/tips-for-golfing-in-c \$\endgroup\$ – O.O.Balance Jul 1 '18 at 14:09
  • \$\begingroup\$ I didn't realize until searching just now that C11 still supports the old identifier list function syntax, so nevermind. But your point holds regardless. \$\endgroup\$ – Tim Seguine Jul 2 '18 at 12:30
  • 1
    \$\begingroup\$ Suggest f(a,l,c)int*a;{for(c=0;l--;)c=*a++*=c+1;} \$\endgroup\$ – user77406 Nov 1 '18 at 11:05
3
\$\begingroup\$

Shakespeare, 365 bytes

I.Ajax,.Ford,.Act I:.Scene I:.[enter Ajax and Ford]Ajax:Open mind!Scene V:.Ford:Am I nicer than the sum of a big red old cute hard cat a big red old cute joy?Ford:If so,you is the sum of thyself a son!Ford:If not,you is zero!Ford:Open heart!Ajax:you is a big red old cute hard cat.Ajax:Speak mind!Ajax:Open mind!Ford:Am I nicer than zero?Ajax:If so, let us Scene V.

try it here

less golfed version

I.Ajax,.Ford,.
Act I:.
Scene I:.
[enter Ajax and Ford]
Ajax:Open mind!
Scene V:.
Ford:Am I nicer than the sum of a big red old cute hard cat a big red old cute joy?     <- smallest way to 48 (ascii "0") I could think of
Ford:If so,you is the sum of thyself a son!
Ford:If not,you is zero!
Ford:Open heart!
Ajax:you is a big red old cute hard cat.    <- get value of 32 or space
Ajax:Speak mind!                            <- then output it
Ajax:Open mind!
Ford:Am I nicer than zero?
Ajax:If so, let us Scene V.                 <- loop through inputs
\$\endgroup\$
3
\$\begingroup\$

C++, 47 bytes

[](int*a,int*b){for(int c=0;a!=b;)c=*a++*=1+c;}

A lambda that modifies an array in place, given start and end pointers.


Try it online! (requires Javascript)


Generic version at 55 bytes (this works for any container with elements of arithmetic type):

[](auto a,auto b){for(auto c=*a-*a;a!=b;)c=*a++*=1+c;};
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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