CtCI - Glass Stacking

You are given a number N of glasses. Your job is to determine the largest pyramid that can be built with the glasses provided, and then create that pyramid in the output. A glass is represented in by an arroba. Each floor in the pyramid must be centered and the glasses must be separated by a single white space between them.

 0 + 0 + 1 = 1  ->      @
 1 + 1 + 1 = 3  ->     @ @
 3 + 2 + 1 = 6  ->    @ @ @
 6 + 3 + 1 = 10 ->   @ @ @ @
10 + 4 + 1 = 15 ->  @ @ @ @ @
15 + 5 + 1 = 21 -> @ @ @ @ @ @

We can see that for each additional section in the pyramid we have to add the number of glasses from the lowest line plus one to the bucket. If we are given twenty glasses we can only build a pyramid with five sections because for the next one we will be missing one glass for the base. We have three variables here: one is the number of glasses used to build the lowest section; the second variable is used as a counter and reflects how many glasses we need to build the next base, as we can see in the graph above the number increases by one with each iteration; the third variable is the additional glass that we need for the base, this will always be one because we need the number of glasses from the previous step plus one.

If we want to build a pyramid with X floors we need to iterate from 1-to-X and for each iteration add the index to the sum. This is basically a factorial operation but instead of multiply we have to sum the numbers.

var glasses int
for i := 1; i <= x; i++ {
    glasses += i
}

The problem here is that we do not know how many floors we can generate with the number of glasses provided. Instead we need to use an infinite iterator using while and execute the same operation explained before, but instead of keep adding numbers to the pool we will check if the number is bigger than the number of glasses provided, if it is lower then we continue with the next iteration, but if the number is bigger we stop and consider the total number of glasses that of the previous iteration.

var count int
var usable int
var glasses int = 20

for {
    count++
    if (usable+count) > glasses {
        break
    }
    usable += count
}

// Here usable = 15
// And count = 6

At this point we know how many of the provided glasses can be used to build a safe pyramid, and an approximation of the number of floors which in this example is equal to six but in reality the number of floors is count - 1 which is five. Since we are going to start the iteration for the pyramid at index one and stop at index lower than count we can leave the number as it is, there is no need to subtract one.

for i := 1; i < count; i++ {
    fmt.Println(bytes.Repeat([]byte("\x40"), i))
}

// Output:
// @
// @@
// @@@
// @@@@
// @@@@@

We have the pyramid, now we need the white spaces between the glasses. First we will fill the spaces inside the glasses and then the outer spaces, the ones on the edges. For the spaces inside the glass we simply need to add (glasses - 1) on the right side of each arroba until the number of available spaces gets to zero.

var line []byte
for i := 1; i < count; i++ {
    line = []byte{}
    for j := 0; j < i; j++ {
        line = append(line, '\x40')
        if j < (i - 1) {
            line = append(line, '\x20')
        }
    }
    fmt.Printf("%s\n", line)
}

// Output:
// @
// @ @
// @ @ @
// @ @ @ @
// @ @ @ @ @

Now we need to center the glasses from each line. For floor #5 we do not need to center anything because this is the floor with the maximum number of glasses compared with the others. Floor #4 contains one glass less than floor #5 and we know by logic that the number of spaces required in the sides is equal to the number of glasses missing from the previous check.

In order to get the number of missing glasses from floor #1 we can subtract the number of glasses per floor from the total number of floors. For floor #1 we have (count - index) => (5 - 1) = 4 and so on until we get to the last index.

Floor #1 -> Missing 4 => (5 - 1)
Floor #2 -> Missing 3 => (5 - 2)
Floor #3 -> Missing 2 => (5 - 3)
Floor #4 -> Missing 1 => (5 - 4)
Floor #5 -> Missing 0 => (5 - 5)
var line []byte
var spaces int
for i := 1; i < count; i++ {
    line = []byte{}
    spaces = count - (i + 1)
    line = append(line, bytes.Repeat([]byte("\x20"), spaces)...)
    for j := 0; j < i; j++ {
        line = append(line, '\x40')
        if j < (i - 1) {
            line = append(line, '\x20')
        }
    }
    line = append(line, bytes.Repeat([]byte("\x20"), spaces)...)
    fmt.Printf("%s\n", line)
}

// Output:
// |    @    |
// |   @ @   |
// |  @ @ @  |
// | @ @ @ @ |
// |@ @ @ @ @|

We now have the solution:

func solution(glasses int) {
    var count int
    var usable int

    for {
        count++
        if (usable + count) > glasses {
            break
        }
        usable += count
    }

    var line []byte
    var spaces int

    for i := 1; i < count; i++ {
        line = []byte{}
        spaces = count - (i + 1)

        line = append(line, bytes.Repeat([]byte("\x20"), spaces)...)

        for j := 0; j < i; j++ {
            line = append(line, '\x40')

            if j < (i - 1) {
                line = append(line, '\x20')
            }
        }

        line = append(line, bytes.Repeat([]byte("\x20"), spaces)...)

        fmt.Printf("%s\n", line)
    }
}
7 months ago
  • 8da57acFix minor bugs found by the code static ana…
7 months ago
  • caa417fAdd option to configure the malware scanner…
7 months ago
  • 9c86744Modify default value for some of the alert …
7 months ago
  • 84dd39dAdd option to stop sending the failed login…
7 months ago
  • eb05935Add pre-checks for every plugin page for si…
7 months ago
  • d21a062Modify mechanism to ignore files from integ…
7 months ago
  • b1a9169Add developer option to disable failed pass…
7 months ago
  • 4e3ef13Add support for other English and Spanish b…
7 months ago
  • 2d07b4eFix error interception for Firewall API err…
7 months ago
pushed to master at cixtor/slackapi
  • 4a2c1c8Modify data type for methods related to cha…
  • 6716199Add CLI handler for the users.identity API …
  • f9c448dAdd CLI handler for the mpim.open API endpo…
  • 305d1c4Add CLI handler for the mpim.mark API endpo…
  • 8bb89afAdd CLI handler for the mpim.close API endp…
  • 202a017Add CLI handler for the dnd.teamInfo API en…
  • 68819e9Add CLI handler for the dnd.info API endpoi…
  • 9a2b29aAdd CLI handler for the dnd.endSnooze API e…
  • e7dc86aAdd CLI handler for the dnd.setSnooze API e…
  • 111c53fAdd CLI handler for the dnd.endDnd API endp…
  • cdb620dFix token usage when there are no extra par…
  • View comparison for these 11 commits
7 months ago
pushed to master at cixtor/slackapi
7 months ago
  • 6497e80Remove unnecessary automatic blacklisting o…
7 months ago
opened pull request Sucuri/sucuri-wordpress-plugin#40
Fix multiple bugs with the API calls and queue system
18 commit with 793 additions and 293 deletion
7 months ago
7 months ago
7 months ago
  • 38cc02aModify timing for the dashboard alerts afte…
7 months ago
  • 350c074Fix infinite loop with email alerts and SMT…
7 months ago
  • acff4aaFix detection of base URL with built-in fun…
7 months ago
7 months ago
7 months ago
7 months ago
7 months ago
opened pull request Sucuri/sucuri-wordpress-plugin#39
Add queue system for the security logs and cache improvement
5 commit with 517 additions and 541 deletion
7 months ago
7 months ago
  • 4c51445Fix static function call of non-static Site…
7 months ago
7 months ago
  • af47581Add changelog to release version 1.8.6
7 months ago
opened pull request Sucuri/sucuri-wordpress-plugin#38
Add changelog to release version 1.8.5
6 commit with 4062 additions and 1841 deletion
7 months ago
  • dc1a05aAdd changelog to release version 1.8.5
7 months ago
Do you have a project idea? Let's make it together!