Dots, Strings and JavaScript pt. 1
Tags: javascript, algorithms, webdev, learning
Published: 2020-06-24 08:23:05

It is a very nifty task to pump up algorithmic thinking and clarity into complexity, execution time and memory usage.

On the input you have a string of symbols, on the output you get an array of all possible strings with dots placed inside the string between characters.

```bash
> abc
[a.bc ab.c a.b.c]

> abcd
[a.bcd, ab.cd, a.b.cd, abc.d ...]
```

Newcomers in our team who googled the solution on combinatoric forums usually see a connection with permutations. The task above is about combinations(permutations with repetition) if to be precise. We have exactly two choices '.' and '' to fill slots between characters and we have N-1 slots, where N is number of characters. With a brief calculation you can find out that number of combinations is going to be 2 to the power of N-1.

```javascript
const text = 'abc'
const totalCombinations = Math.pow(2, text.length - 1)
```

Now we have to decide where to put dots on every iteration. The first thing developers lean to do is to convert an index of a loop to a binary representation and then use it as a mask to apply to an input string

```javascript
for (let i = 0; i < totalCombinations; i++) { 
	const mask = i.toString(2)
	...
}
```

then apply that mask to the input string and place dots where we have `1` in our binary mask
```javascript
...
	const mask = i.toString(2)
	
	let result = ''

	for (let j = 0; j < text.length; j++){
		result += text[j]

		if(j === mask.length) break; 
		// we've filled all slots at this point
		// we can also omit the check above, it'll still work
		// yet we prefer clarity over code lines

		result += mask[j] === '1' ? '.' : ''
	}
```

the code above is almost correct, you might've noticed that we didn't prepend a leading zeros to our binary mask and instead of having `'00'` `'01'`.. we're going to have `0, 1, 10`. Let's fix that.

A brief google search on adding leading zeros to binary numbers will lead you to 
```javascript
var n = num.toString(2);
n = "00000000".substr(n.length) + n;

or

function pad(n, width, z) {
  z = z || '0';
  n = n + '';
  return n.length >= width ? n : new Array(width - n.length + 1).join(z) + n;
}

or somthing like 

function pad(num, size) {
    var s = num+"";
    while (s.length < size) s = "0" + s;
    return s;
}

etc...
```

Yet we can just use a native `String.prototype.padStart()`
```javascript
const mask = i.toString(2).padStart(text.length - 1, '0')
```

Let's put everything together
```javascript
const text = "abcde";
const total = Math.pow(2, text.length - 1);

const output = [];
for (let i = 0; i < total; i++) {
  const mask = i.toString(2).padStart(text.length - 1, "0");
  let result = "";

  for (let j = 0; j < text.length; j++) {
    result += text[j];

    if (j === mask.length) break;
    result += mask[j] === "1" ? "." : "";
  }

  output.push(result)
}

console.log(output)
```

And give it a run
```bash
node test.js 
[
  'abcde',    'abcd.e',
  'abc.de',   'abc.d.e',
  'ab.cde',   'ab.cd.e',
  'ab.c.de',  'ab.c.d.e',
  'a.bcde',   'a.bcd.e',
  'a.bc.de',  'a.bc.d.e',
  'a.b.cde',  'a.b.cd.e',
  'a.b.c.de', 'a.b.c.d.e'
]
```

Great, everything works as expected. When our developers come to that stage of resolving the problem we give them the improvement task, let's have a look at those in the next post.