Tag Archives: C++

Matching braces in a string

I heard recently about an interview problem involving matching braces in a string. Checking to see if all the braces in a string are paired up in the proper order. Seemed like an interesting, and short, challenge.

Examples of strings with proper brace matching: "()", "(){}[]", "([{}])"

Examples of strings without proper brace matching: "(", "[]]", "([)]"

Continue reading Matching braces in a string

Generating a Dungeon (part 3)

When I last left off I had the rooms (or data equivalent of rooms) created, the last thing that needed to be done was add in cycles so that the dungeon layout is not a tree. That’s what I’ll be tackling in this post.

I’ve updated the generateMap() function and added a call to the new function fixTree() at the end:


void GeneratedMap::fixTree()
//get all dead ends
std::vector<Room*> deadEnds;
for (unsigned int i = 0; i < rooms.size(); i++)
if (rooms[i]->isDeadEnd())
std::random_shuffle(deadEnds.begin(), deadEnds.end());

unsigned int i = 0;
int addedCount = 0;
int cyclesToAdd = (deadEnds.size() * CYCLE_PERCENT) / 100;
//keep adding cycles until the quantity is met or we run out of
//dead ends to try
while (i < deadEnds.size() && addedCount < cyclesToAdd)
Room* de = deadEnds[i++];
std::vector<Room*> adjacentRooms = getAdjacentRooms(de);
if (adjacentRooms.size() <= 0)
std::random_shuffle(adjacentRooms.begin(), adjacentRooms.end());

unsigned int j = 0;
Room* aj = nullptr;
//find first non-connected room
if (!de->areConnected(adjacentRooms[j]))
aj = adjacentRooms[j];
} while (j < adjacentRooms.size() && aj == nullptr);

//if no non-connected room is found try the next dead-end
if (aj == nullptr)

aj->hasSecondEntrance = true;

//rooms are adjacent, but not connected, now we connect them... with
int directionOfOther = de->directionOfOtherRoom(aj);
int miny = 0, minx = 0, shift = 0;
if (directionOfOther == Room::LEFT || directionOfOther == Room::RIGHT)
miny = std::max(de->topLeft.y, aj->topLeft.y);
int maxy = std::min(de->bottomRight.y, aj->bottomRight.y);
int dy = std::abs(maxy - miny);
shift = dy <= 0 ? 0 : rand() % (dy + 1);
else if (directionOfOther == Room::UP || directionOfOther == Room::DOWN)
minx = std::max(de->topLeft.x, aj->topLeft.x);
int maxx = std::min(de->bottomRight.x, aj->bottomRight.x);
int dx = std::abs(maxx - minx);
shift = dx <= 0 ? 0 : rand() % (dx + 1);

switch (directionOfOther)
case Room::LEFT:
aj->startingCell2 = Vector2i(aj->bottomRight.x, miny + shift);
aj->previousCell2 = Vector2i(de->topLeft.x, miny + shift);
case Room::RIGHT:
aj->startingCell2 = Vector2i(aj->topLeft.x, miny + shift);
aj->previousCell2 = Vector2i(de->bottomRight.x, miny + shift);
case Room::UP:
aj->startingCell2 = Vector2i(minx + shift, aj->bottomRight.y);
aj->previousCell2 = Vector2i(minx + shift, de->topLeft.y);
case Room::DOWN:
aj->startingCell2 = Vector2i(minx + shift, aj->topLeft.y);
aj->previousCell2 = Vector2i(minx + shift, de->bottomRight.y);


Continue reading Generating a Dungeon (part 3)

Generating a Dungeon (part 1)

I’ve been wanting to create a game that uses randomly generated dungeons for a while now but didn’t have a good idea about what kind of game to make. Recently though I decided “so what if I don’t have an idea for what to DO with the dungeons, I can figure that out after I make them.” So I set out to make some code that will generate random dungeons.

Continue reading Generating a Dungeon (part 1)

Factorial Zeroes 2

In my last post I talked about finding the number of zeroes at the end of n!, and I said that there was room for improvement. I thought about it a little bit and found a couple things to speed it up.

The first has to do with the relationship between the quantity of fives and the quantity of twos. The lower quantity in the prime factorization of n! is how many zeroes it will have at the end. If I would have thought a little more about it though I would have seen that counting the twos is pointless in this situation.

Even the prime factorization of 10 = 5 \cdot 2 has the information in there: there will always be more twos than fives. Counting from 1 to 10:

  • Multiples of 2: 2, 4, 6, 8, 10
  • Multiples of 5: 5, 10

This means that all we really need to keep track of is the quantity of fives in the prime factorization of n!. Which leads to the second optimization: we only need to get the prime factorization of multiples of five.

Continue reading Factorial Zeroes 2