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 :man_facepalming:

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