# Looking for optimized solution to this kata

i found this kata on codewars which I found it to be interesting, in short, I am supposed to make a diamond shape of strings using n input into the function. Kata here https://www.codewars.com/kata/give-me-a-diamond/train/javascript

This is my solution where I work on the bottom diamond first before the top diamond and concat it together. It is not v efficient as it uses 2 loops with repeat code to track bottom and top diamond. I couldn’t understand the solutions based on other people code where they use a single loop to solve, could anyone explain to me how to solve this solution in a single loop? i appreciate any help thanks !

this is my code

``````function diamond(n){

// kind of hacky solution with playing around with top diamond value

if(n < 0 || n % 2 === 0) return null;

// bottom diamond
let bResult = "";
let bCounter = 0;
for(let i = n; i > 0; i-=2){
let space = " ".repeat(bCounter);
bResult += `\${space}\${`*`.repeat(i)}\n`;
bCounter++;
}

// top diamond
let tResult = "";
let tCounter = bCounter-1;

for(let i = 1; i < n; i+=2){
let space = " ".repeat(tCounter);
tResult += `\${space}\${`*`.repeat(i)}\n`;
tCounter--;
}

return tResult.concat(bResult)
}
``````

I did a couple of quick solutions without running a double loop. Belowe, I’ve included a brief explanation and then in a spoiler, I’ve also included the code, with lots of comments, along with a link to my actual kata solutions (which don’t include the comments, so those versions may be easier to read for some people)

# Simply reverse the half

For my first attempt, I basically create the top half, then just use standard `split`, `reverse`, and `join` methods to “flip” it. Performance-wise, this is probably still going to be comparable to a double loop.

Spoiler!

Click the blurry area to see this solution.

``````function diamond(maxWidth){
if (maxWidth < 1 || maxWidth % 2 == 0) return null

// to have both a non-mutating input value (maxWidth), and a
// mutatable version of the input (n)
let n = maxWidth

// this is the first part of our return string
let top = ''

// this is our initial asterick length
let lineWidth = 1

// this will actually calculate the number of spaces before
// our asterisks, and return the string for a given top line
const createLine = lw =>
'·'.repeat((maxWidth - lw) / 2) + '*'.repeat(lw) + '\n'

// we'll create all of the lines _above_ our middle line
while (lineWidth < maxWidth) {
top += createLine(lineWidth) // append each new line
lineWidth += 2 // calculate for the next line
}

// we'll create the middle line
const middle = '*'.repeat(maxWidth)

// we'll rearrange a copy of top as our bottom
const bottom = top
.split('\n')
.reverse()
.join('\n')

// we'll put our three partial strings together
diam = top + middle + bottom + '\n'

return diam;
}

console.clear()
console.log(diamond(0))
console.log(diamond(-1))
console.log(diamond(3))
console.log(diamond(7))
``````

https://www.codewars.com/kata/reviews/55639ff791e68ecc490000ae/groups/5cc4643d8ebbd90001621e86

# Prepend and append the new line with each iteration

For my second attempt, I basically create the middle line, then just prepend and append the new line on each iteration. Performance-wise, this really is just a single loop.

Spoiler!

Click the blurry area to see this solution.

``````function diamond(maxWidth){
if (maxWidth < 1 || maxWidth % 2 == 0) return null

// this will actually calculate the number of spaces before
// our asterisks, and return the string for a given top line
const createLine = lw =>
'·'.repeat((maxWidth - lw) / 2) + '*'.repeat(lw) + '\n'

// we'll actually start using this variable for the line
// just above and below our middle line
let lineWidth = maxWidth - 2

// we'll start our string with the middle line
let diam = '*'.repeat(maxWidth) + '\n'

// we'll add all the lines above and below the middle line
while (lineWidth > 0) {
const newLine = createLine(lineWidth) // create the new line
diam = newLine + diam + newLine // append it before and after the existing diam

lineWidth = lineWidth - 2 // decrement
}

return diam;
}

console.clear()
console.log(diamond(0))
console.log(diamond(-1))
console.log(diamond(3))
console.log(diamond(7))
``````

https://www.codewars.com/kata/reviews/55639ff791e68ecc490000ae/groups/5cc466658ebbd90001622ea3

Here is one possible version using something similar to what you used (using the `repeat` function) with one for loop. However, a more efficient solution would not call the repeat function.

``````function diamond(n) {
if (n < 0 || n % 2 === 0) return null;

let numSpace = 0;
let result = '*'.repeat(n) + '\n'; // middle row

for (let numStar = n - 2; numStar >= 1; numStar -= 2) {
let nextRow = ' '.repeat(++numSpace) + '*'.repeat(numStar) + `\n`;
result = nextRow + result + nextRow;
}

return result;
}
``````
2 Likes

Hey, thank you so much for taking your time in going through the kata and giving your well-commented solutions. I did consider reversing the half after getting half of the diamond but the trouble I have is visualizing how the spacing is calculated in your createLine function. I saw many similar solutions as well using that calculation. Would you mind explaining how that calculation is derived thanks so much again.

1 Like

@Balancedsan - You should be able to copy the following into your console, then just read through each comment and check the output.

Definitely change the `maxWidth` and `lw` values to see how the calculations work in practice.

Hopefully this helps. If it doesn’t feel free to ask for more of an explanation!

``````// note, that createLine requires a maxWidth that
// isn't explicitly passed in, so we need to make sure
// it's in scope for this explination
var maxWidth = 9

var createLine = lw => {
// EMPTY SPACES
// the first calculation for that is simply the
// number of empty spaces if we had a rectangle
console.log(maxWidth - lw)
// then we divide that result by 2, because we
// really need the number of spaces just to the left
// of the asterisks and use that value as our repeat
// parameter
console.log('·'.repeat((maxWidth - lw) / 2))

// ASTERISKS
// The second portion of the return value is just
// the asterisks
console.log('*'.repeat(lw))

// COMPLETED STRING
// Put those two together, along with a line return,
// and you have the whole string
console.log('·'.repeat((maxWidth - lw) / 2) + '*'.repeat(lw) + '\n')
}

createLine(5) // where the parameter is the number of asterisks
``````

Following can [should] be optimised further - I think I can just generate the correct coords in the loop rather than remapping.

So it works by generating coordinates.

The coordinates are generated with a nested loop, and so start `0, 0` at top left going to to `n -1, n - 1` at the bottom right.

This is not much use, and so they are first normalised (converted to values from 0 to 1), then the `0, 0` point is moved to the centre. This gives coordinates going from `-1, -1` at top left to `1, 1` at bottom right.

I don’t care about negative values, so the coordinates are given absolute values. This means the coordinates at the corners become `1, 1`, with the centre as `0, 0`.

Once that’s done, any coordinate that adds up to a value greater than 1 is outside the diamond.

Nested loop is used to generate the coordinates, though with some maths finangling I guess it could be converted to a single loop.

``````function diamond(n) {
if (n % 2 == 0 || n == 0) return null;

const delta = n - 1; // delta is max - min. Max is n - 1, min is 0

const normaliseAndRemap = (value) => {
const normalisedValue = (value - delta) / delta;
return Math.abs((normalisedValue * 2) - 1);
}

let output = [];
for (let x = 0; x < n; x++) {
let row = ""
for (let y = 0; y < n; y++) {
row += normaliseAndRemap(x) + normaliseAndRemap(y) > 1 ? " " : "*";
}
output.push(row);
}
return output.join("\n");
}
``````

Edit

``````function diamond(n) {
if (n % 2 == 0 || n == 0) return null;

const step = 1 / ((n - 1) / 2);
const output = [];

for (let y = -1; y <= 1; y += step) {
let row = "";
for (let x = -1; x <= 1; x += step) {
row += Math.abs(x) + Math.abs(y) > 0.998 ? "0" : "1";
}
output.push(row);
}
return output.join("\n");
}
``````

Weirdly this explodes when I try to add 0.33333… to -0.333333…only in the loop though, which is strange (well, it doesn’t explode per se, it just gives me -1.1102230246251565e-16 which is not very correct)

If string repeat isn’t `log(n)` already, a string repeat that is `log(n)` time complexity can be made via the Egyptian multiplication routine (worth googling)

It might be faster to modify the first string travelling down to the mid point, but I can’t be bothered benchmarking it really (hidden `O(n)` cost in copying or appending to a string but could be faster? not sure)

As in starting with the string of spaces with an asterisk at the end, slicing off the initial space and appending two asterisks