You have 10 red and 10 black marbles…

You have 10 red and 10 black marbles. In how many ways can you put the 20 marbles in a row so that no more than two marbles of the same colour lie next to each other?

An example of a valid sequence would be:

Can you reason your way out of this one or would you write a program that can give you the solution? Can you write this program?

First reasoning

Before starting a program, let’s first reason about the problem. It might just be that a program is not needed at all 🙂

The red and black marbles are kind of ‘exchangeable’ in the sense that in the above example picture there is a similar solution when all the red and black marbles would change colour. So, how to discover all the possibilities with 20 marbles?

I was thinking of starting off with just one marble, and than reason my way onwards in a tree-search structure way, by just adding a marble and see if I still have a valid sequence (line). Something like this:

First of all, for clarity reasons let me use simple ‘X’ and ‘O’ instead of red/blacks.

Suppose I start with with an ‘O’ and continue making lines

O

One O, that’s just the start, let’s add the O and X possibilities:

OO 
OX

So, I’m just creating all possible lines that I can create. From the start of one ‘O’, I now have two possible continuations of lines.
The number of possibilities doubled, of course. Of course I know that I could also have started with ‘X’, but I’m just exploring a bit first. So, again, let’s just add O’s and X’s to the two existing possibilities:

OOO <- not allowed!
OOX
OXO
OXX

The first time extending a marble 'ends a line' because of the rule that we can't have three marbles of the same colour in a row!
Only three possible lines to extend left.

So far so good, it looks like adding marbles from the stack of 10 O's and X's is simple. However, doing that for all possibilities seems quite a task as the number of possible 'branches' of this tree probably grows very fast.

Let's just again extend the lines of three above, to lines with lengths of four, by adding O and X to the already existing possible lines above, of course I do not have to explore the OOO line any further:

OOXO
OOXX
OXOO
OXOX
OXXO
OXXX <- not allowed!

So, while the lines of three marbles extends with just one marble to a line of four marbles, there is only one of the lines that is not allowed for having three X's in a row. Means that the number of possibilities with three marbles (3) almost doubled, but not quite doubled, to 5.

We probably need to find a math formula, something like "the length of the line calculates into a number of possibilities" but I did not find it yet. What I do seem to have figured out is that when a line ends with two marbles of the same colour, there is only one possible way to extend the line namely with a marble of the other colour, while if a line ends in different colours, the possible next sequence can either contain an X or an O.

Instead of extending the line, I could start writing down the number of possible lines that can be made from that line. Like this:

OOXO (2, as both adding O and X would still give a valid line)
OOXX (1, only adding O would result in a valid line)
OXOO (1)
OXOX (2)
OXXO (2)

Of course, the lines that end either in two O's or two X's can only be extended with one marble of the other colour, so those get the number 1. The lines that end with two different coloured marbles, can be extended by either an 'O' or an 'X', so those get the number two.

Now the interesting thing is that in case I added the number 2, one of the two possibilities, again must have a double OO or double XX, so we can now write the next numbers for lines of six marbles, to the above possibilities as:

OOXO (2) (3)
OOXX (1) (2)
OXOO (1) (2)
OXOX (2) (3)
OXXO (2) (3)

The above shows the possibilities for lines with a length of six marbles. We do not see all possibilities anymore, but we do see the number of possibilities. When we add up all the numbers in the last column, we have the number of possible lines for lines of six marbles, being 3+2+2+3+3=13. Although, we have to keep in mind this is only for the lines starting with 'O', so we have to double that amount for the lines that would be the inverse of these lines starting with 'X's. That would be 26 for lines of length 6.

So what do we have so far, if we look at line-length and the resulting number of possible lines?

1 -> 2 (haha, O and X, two possibilities, for sure, is 2^1)
2 -> 4 (OX, OO, XO, XX, 2^2)
3 -> 6 (not OOO, XXX so 2^3 - 2)
4 -> 8 (2^4 minus 2^3 is 16-8.. hm)
5 -> 16 (2^5 minus 2^4.. 32-16, on to something?)
6 -> 26  (2^6 minus 2^5 would be 64-32 = 32..nopes)

To be honest, I still have not figured out a nice formula.. it must be something like each extra marble doubles the possibilities, but not always...

A program exploring all possibilities might be easier to write; let the computer figure out how many possibilities there are. How does your program find all possibilities?

package main


import "fmt"

// Question: You have 10 red and 10 black marbles. In how many ways can you
// put the 20 marbles in a row so that no more than two marbles of the same
// colour lie next to each other?
//
// An example of a valid sequence would be:
// OOXOXXOXOXXOOXXOXXOO

const maxLineLength = 20
func main () {
	count := CountMarbleLines()

	fmt.Println("Number of possible lines",  count)
}
func CountMarbleLines () int {

	linelength := 0
	amountO := 10
	amountX := 10
	count := PossibleLines(amountO, amountX, linelength, 0, 0)
	return count

}

// Counts possible lines by adding either O or X to the line
// returning 0 in case no line possible or 1 in case the line is possible
func PossibleLines(amountO int, amountX int, lineLength int, timesO int, timesX int) int {
  // we have to ensure that lines that have three
  // in sequence of the same coloured Marbles won't count 
  if (timesO > 2 || timesX > 2) {
    return 0 // too many X or O in sequence can not count this line
  }

  // Recursive stop function
  if lineLength == maxLineLength {
    return 1 // a valid line has been found
  }

  // we can add either O or X to the string, register this in timesO/timesX
  var addO int = 0
  var addX int = 0
  if amountO > 0 { // if we still have O Marbles to spend...
    timesO++
    addO = PossibleLines(amountO - 1, amountX, lineLength + 1, timesO, 0)
  }
  if amountX > 0 { // if we still have X Marbles to spend...
    timesX++
    addX = PossibleLines(amountO, amountX - 1, lineLength + 1, 0, timesX)
  }
  return addO + addX;
}

Note that the above is written in GoLang which is also easily portable to .NET C#.

When you run the above program you will get the answer to the question!

Here's the .NET C# version, which will also print out all the possibilities:

class Program
{
static void Main(string[] args)
{
    Console.Out.WriteLine("Starting to count..");
    int count = MarbleCount();
    Console.Out.WriteLine("Total number found: " + count);
    Console.ReadLine();
}


/// Count number of possible marble strings.
/// Rules: 20 marbles in line, 10 x's and 10 o's whereby there can not be more than two
/// marbles of the same colour next to each other.
/// Example: oxxooxoxoxooxxoxooxx
/// Logic: There are 10 o's to spent, 10 x's to spent
private static int MarbleCount()
{
    int amountO = 10;
    int amountX = 10;
    int lengthToFind = 20;
    StringBuilder sb = new StringBuilder();
    return PossibleStrings(amountO, amountX, 0, 0, 0, sb, lengthToFind);
}

private static int PossibleStrings(int amountO, int amountX, int lengthOfString, int timesO, int timesX, StringBuilder sb, int lengthToFind)
{
  // stop condition of recursive function:       
  if (timesO > 2 || timesX > 2)
  {
    return 0; // too many O's or X's in sequence, can't count this line.
  }

  // if the lenght == 20, we have constructed a valid string
  if (lengthOfString == lengthToFind)
  {
    Console.Out.WriteLine(sb);
    return 1; // a valid string is constructed
  }
            
  // we can add either O or X to the string, register this in timesO/timesX
  int addO = 0;
  int addX = 0;
  if (amountO > 0)
  {
    addO = PossibleStrings(amountO - 1, amountX, lengthOfString + 1, ++timesO, 0, sb.Append("O"), lengthToFind);
    sb.Remove(sb.Length - 1, 1);
  }
  if (amountX > 0)
  {
    addX = PossibleStrings(amountO, amountX - 1, lengthOfString + 1, 0, ++timesX, sb.Append("X"), lengthToFind);
    sb.Remove(sb.Length - 1, 1);
  }
  return addO + addX;
}
}