CtCI - Glass Stacking

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)
    }
}
Do you have a project idea? Let's make it together!