Brain teasers

Not sure if software engineering is for you? If you enjoy solving complex problems then it just might be. Have a go at these brain teasers. Right or wrong, the important thing is that you relish having a go!

Brain teasers

Not sure if software engineering is for you? If you enjoy solving complex problems then it just might be. Have a go at these brain teasers. Right or wrong, the important thing is that you relish having a go!


Pool table balls

At the beginning of a game of English pool, 7 yellow balls, 7 red balls and a black ball are arranged in a triangle in the pattern shown below. A wooden frame, known as the rack, is used to get the balls into the triangle formation before the game can start.

Puzzle 1 starting position

Figure 1: Correct starting arrangement

Before the game begins you place the balls at random into the rack. You then need to rearrange them to the formation above before the game can start. For the purposes of this brain teaser you can only rearrange the balls by choosing one pair of balls at a time, and swapping their positions. This action constitutes a swap. No other actions, such as three way cyclic moves, are allowed.

  • What is the maximum number of swaps you would ever need to make to get the balls from a random starting position into the formation shown above?

Many players also consider the inverse arrangement of red and yellow balls to be a perfectly valid starting arrangement. This is shown below.

Puzzle 1 alternative starting position

Figure 2: Alternative 'inverse' starting arrangement

  • What is the maximum number of swaps required to get from a random starting arrangement to either the ‘correct’ or the ‘alternative’ arrangement?

Hint

If you’re having trouble with the first part, try working out how many swaps would be needed to get the arrangement of balls shown below to the correct starting position. But you are on your own for the second part!

Puzzle 1 standard position solution

Solution

Answer 1

Assuming the worst possible arrangement where all the yellows are where the reds should be (and vice versa), with the added problem of the black ball being out of position. Such an arrangement is shown in Fig 3 below. You would require 1 swap to get the black into position and then 7 swaps to swap over the 7 pairs of reds and yellows. Total: 8 swaps.

Here's an example of the worst case arrangement requiring 8 swaps.

Puzzle 1 standard position solution

Figure 3: Example of worst case arrangement requiring 8 swaps

Answer 2

Previously it was possible for all reds and yellows to be out of position. But with the alternative arrangement it isn’t possible for more than half of all red and yellow balls to be out of position because if they’re out of position for one arrangement they are, by definition, in the correct position for the other arrangement. For example, Fig 3 shows something which is 8 swaps away from the ‘correct’ arrangement, but is only a single swap away from the ‘alternative’ arrangement.

The answer is that in the worst case a single swap is needed to get the black into position, followed by 3 swaps to get the remaining colours into one or other of the two arrangements. Total: 4 swaps.

Here's an example of a worst case starting arrangement requiring 4 swaps.

Puzzle 1 alternative position solution

Figure 4: Example of worst case starting arrangement requiring 4 swaps


Flight controller

You are the owner of a small airline and you need to create an efficient network of flight paths to allow for the airline to expand. The cities in your region are all quite small, and each has only one airport which can allocate you space for flights to at most three other cities. The airport authorities also insist that all routes operate in both directions. In addition, your customers find more than one layover on a flight is completely unacceptable. Therefore, from any one city you must be able to connect to any other city with at most two flights.

  • Given these constraints, how many cities can your airline connect to?
  • Describe the flight network, or draw a diagram showing the connections.

Hint

Try thinking of the lower and upper bounds for the answer. Four cities arranged as three spokes from a central hub will clearly work, and you should be able to extend that network further. But as you keep adding cities, can you still draw a network that satisfies all the conditions?

Solution

The correct answer is: 10 cities.

It is relatively easy to see that 10 cities is the upper limit. Consider starting with a central hub, adding 3 spokes from there and 2 further cities joined to each spoke. You cannot try to add more cities beyond that as you will never be able to connect back to the central hub with just two flights.

So 10 cities is the upper limit on what is possible. Unfortunately the simplistic construction we used to come to that conclusion does not give a network diagram that satisfies the conditions. It is possible to draw one, though. Here’s how you can visualise the solution.

flights solution

Subscribe to email updates

Latest news

The Four Horsemen and the Rise of Cloud Native Collaboration

In the first post in this series, we covered the incredible growth of the four horsemen -- Apple, Google, Facebook and Amazon -- and discussed why they continue to grow, even as they've already...Read more

Metaswitch Cloud Contact Center Empowers Service Provider Brand and Business Intelligence

New features bring significant business benefits to service providers and their enterprise customers LOS ALTOS, Calif. – March 23, 2017 – Cloud native communications software leader Metaswitch today...Read more

Metaswitch Accession Continues Its Ascent, Further Enhancing UC&C Scalability, Cost Efficiency and User Experience

Webinar hosting, new room size options and COTS audio/video deployment widen the market for leading Unified Communications and Collaboration (UC&C) platform LOS ALTOS, Calif. – March 23, 2017 –...Read more

Latest resources

Top 5 Challenges in Modernizing Unified Communications and Collaboration

The business meeting is not what it used to be. The scene of a group of company executives sitting around a table in a conference room while munching...Read more

The Internet of Talk - The Future of Voice Communications

Telephony is the lifeblood of the telecom industry. But that blood has been getting thinner in recent years, as alternative modes of communication,...Read more

EVPN Protocol Stacks

Industry leading networking protocol stacks from Metaswitch provide Ethernet Virtual Private Network (EVPN) services for the data center, service...Read more

Latest jobs

Software Contract / Supplier Manager, Enfield (North London)

The Software Contracts/Supplier Manager role at Metaswitch The Software Contracts/Supplier Manager position is available in the newly formed...Read more

Information & Security Risk Manager (Enfield, North London)

The Information Security & Risk Manager role at Metaswitch Metaswitch has a complex global IT infrastructure that spans multiple sites and...Read more

Sales Operations Analyst / Administrator- Enfield (North London)

The Sales Operations Analyst / Administrator at Metaswitch The Metaswitch Sales Operations team is a vital part of the overall Metaswitch...Read more