current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 5 down vote favorite

I have an array like this (make sure you scroll to the right): 

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

Where it will always be the same length. And there will always be some number of 0's surrounding some number of 1's. I am trying to find a good/efficient/smart way to turn the middle of the array of into 0's when there is a padding of 4 1's on each side. The result would be something like: 

[0,0,0,0,1,1,1,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,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0]

Where you now have a padding of 4 1's on either side.

This is how I implemented it: 

var a = [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,0,0,0,0,0,0,0,0,0,0,0,0,0];

var hitOne = false;
var oneCount = 0;
var oneStopPoint = a.lastIndexOf(1) - 3;
for(var n in a){
    if(n == oneStopPoint){
        break;   
    }
    if(a[n] == 1 && !hitOne) {
        hitOne = true
        oneCount++;
    } else if(a[n] == 1 && hitOne) {
        oneCount++;
    }
    if(oneCount > 4){
        a[n] = 0;
    }
}
console.log(a);

http://jsfiddle.net/4gk9L9uv/1/

share|improve this question
2  
"And there will always be some number of 0's surrounding some number of 1's." Not after your transformation. What is the purpose of this array and the transformation? By the way, Do you realise that that array could be represented as [4, 47, 13] or [[0, 4], [1, 47], [0, 13], while the transformed version could be [[0, 4], [1, 4], [0, 39], [1, 4], [0, 13]]. Your array could be regenerated from those at any time. So maybe there are alternative ways to work with this data... – itsbruce Dec 5 '14 at 3:45
    
@itsbruce this array is a row (of many rows) of tiles in a game. Initially there will always be some number of 0's surrounding some number of 1's. – Johnston Dec 5 '14 at 4:00
up vote 5 down vote accepted

Firstly: Don't use for...in on arrays.

Secondly, I suppose you can find the 1-boundaries, and add/subtract 4:

var left = array.indexOf(1) + 4;
var right = array.lastIndexOf(1) - 4;
for(; left <= right ; left++) {
  array[left] = 0;
}

Not particularly clever, but it does the job.

(Note: lastIndexOf is widely supported in modern runtimes, but older ones may not have it)

But also take @itsbruce's advice from the comments, and consider another structure for these data.

share|improve this answer
    
It is clever. Thank you – Johnston Dec 5 '14 at 12:18
    
indexOf() is O(n). Given that you know that there is only one contiguous subsequence of 1's, there exist more efficient ways to find its boundaries. The algorithm would be similar as the ones used for searching in ordered lists. – abl Dec 5 '14 at 22:24
    
@abl I did consider that (was thinking something like a binary search), but I found no reason to complicate things. – Flambino Dec 5 '14 at 22:39
    
@Flambino I also think that it may be unnecessary, especially since, being a game, it's likely that the length of the array will not be arbitrarily long. But the OP explicitly asked for an efficient solution so I guess it may be worth mentioning this point. – abl Dec 5 '14 at 22:56
up vote 0 down vote

Here's what I came up with:

function fillOnes(array, padding) {
  for (var i = 0, ones = 0; i < array.length; i++) {
    if (array[i] === 0) {
      for (var j = i - ones + padding;
           j < i - padding;
           array[j] = 0, j++);
      ones = 0;
    } else {
      ones++;
    }
  }
}

I agree with what itsbruce said, however; it would be much better to rework your data structure than do something like this.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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