Working out what not to work out.

 

Call me strange, but one day I looked at our two block calendar and thought what numbers must be on the two blocks for this calendar to work. No matter how I tried, I couldn’t come up with two blocks of 6 numbers that could be used to show all numbers from 01 to 31. So I did what any computer programmer would. I simulated it in software. Read on for the surprise outcome.

The rules are simple enough, the two blocks can have 6 numbers on each. All numbers from 01 to 31 can be made using one number from each block. The order doesn’t matter as you can put the blocks in either way. Here’s my first go at the software to brute force the solution.

#include 
#include 
#include 

int CheckMonth(char* dice1, char* dice2);
bool CheckDay(char* dice1, char* dice2, int day);
bool IncrementPair(char* dice1, char* dice2);
bool IncrementOne(char* dice);
bool IsDigitOnDice(char* dice, int digit);
bool IncrementDigit(char* digit);
bool CheckAllDiff(char* dice);
bool CheckIncreasing(char* dice);

int best = 0;
char bestDice1[7];
char bestDice2[7];

// main entry point.
int main (int argc, char* argv[])
{
  char dice1[7];
  char dice2[7];
  strcpy(dice1, "012345");
  strcpy(dice2, "012345");

  // if started with parameters, use them as the starting point.
  if (argc == 3)
  {
    strcpy(dice1,argv[1]);
    strcpy(dice2,argv[2]);
  }

  // main loop to go through incrementing dice and checking them.
  while (CheckMonth(dice1,dice2) < 31)
  {
    if (IncrementPair(dice1,dice2))
    {
      printf("There is No Solution!\n");
      return 0;
    }
  }
  printf("Found a solution %s %s\n\n", dice1, dice2);

  return 0;
}

// count from 1 to 31 checking each number can be made with the two dice.
// return the highest number that worked.
int CheckMonth(char* dice1, char* dice2)
{
  int day = 0; // this gets incremented before use.
  bool ret = true;
  while (ret && day <32) { day++; ret = CheckDay(dice1, dice2, day); } // day holds the one after the last success, decremtnt to highest that works day --; if (day > best)
  {
    best = day;
    printf("best yet %d from %s %s\n",best, dice1, dice2);
    strcpy(bestDice1,dice1);
    strcpy(bestDice2,dice2);
  }
  return day;
}

// returns true if the pair of digits in the day can be made from the pair of dice
// checks both ways around.
bool CheckDay(char* dice1, char* dice2, int day)
{
  return (  IsDigitOnDice(dice1,day/10) && IsDigitOnDice(dice2,day%10)
        ||  IsDigitOnDice(dice2,day/10) && IsDigitOnDice(dice1,day%10)
	);
}

// returns true if the given digit is on the given dice.
bool IsDigitOnDice(char* dice, int digit)
{
  char d[8];
  sprintf(d,"%d",digit);
  return (strstr(dice,d));
}

// increments the right hand dice and increments the left if that one rolls over.
// if incrementing the left one, log the new pair values to the screen
bool IncrementPair(char* dice1, char* dice2)
{
  bool r = false;
  if (IncrementOne(dice2))
  {
    r = IncrementOne (dice1);
    printf("T: %d  Current: %s %s  Best %d  %s %s\n",time(NULL) ,dice1,dice2,  best, bestDice1, bestDice2);
  }
  return r;
}

// increment a single dice and return true if it rolls over.
bool IncrementOne(char* dice)
{
  bool c = true; // c is our carry flag to indicate a rollover.

  c = true;
  for (int i = 5 ; i >= 0 && c; i--)
  {
    c = IncrementDigit(dice + i);
  }

  return c;
}

// increments the value at the given char pointer
// rolls around from 9 to 0 and returns true if this happens
bool IncrementDigit(char* digit)
{
  bool c = false;
  (*digit) ++;
  if (*digit > '9')
  {
    c = true;
    *digit = '0';
  }
  return c;
}

Nothing particularly complex there. It’s called cal1.cpp, it’s all in one file and builds happily on a Raspberry Pi with this command line.

g++ -o cal cal1.cpp

The problem is, it runs like this…

pi@raspberrypi:~ $ time ./cal
best yet 5 from 012345 012345
best yet 6 from 012345 012346
best yet 7 from 012345 012367
best yet 8 from 012345 012678
best yet 21 from 012345 016789
T: 1506792459 Current: 012346 000000 Best 21 012345 016789
T: 1506792475 Current: 012347 000000 Best 21 012345 016789
T: 1506792489 Current: 012348 000000 Best 21 012345 016789
T: 1506792503 Current: 012349 000000 Best 21 012345 016789
T: 1506792518 Current: 012350 000000 Best 21 012345 016789
T: 1506792531 Current: 012351 000000 Best 21 012345 016789
T: 1506792544 Current: 012352 000000 Best 21 012345 016789
T: 1506792557 Current: 012353 000000 Best 21 012345 016789
T: 1506792570 Current: 012354 000000 Best 21 012345 016789
T: 1506792586 Current: 012355 000000 Best 21 012345 016789
T: 1506792599 Current: 012356 000000 Best 21 012345 016789

And that’s about where I stopped it. For 10 increments of the left dice, it took 140 seconds. That’s an average of 14 seconds per increment, and we need a million of them to try all of the combinations of 6 digits. That’s 14,000,000 seconds to run, which is 162 days, or 23 weeks, or nearly 6 months. On a Raspberry Pi, it won’t cost much to run, and I considered leaving it to run for 6 months to see what solution it came out with. I could re-start it at any time with the last pair of dice values from the output if there was any power problem.

Instead I decided to see if I could improve on 6 months. If we can ignore some dice combinations that are clearly not worth looking at, then it should improve matters. The obvious thing to ignore is any combination where one block has two of the same digit on it. We can do this by modifying the IncrementOne function like this.

bool IncrementOne(char* dice)
{
  bool done = false;

  bool c = true; // c is our carry flag to indicate a rollover.

  while (!done)
  {
    c = true;
    for (int i = 5 ; i >= 0 && c; i--)
    {
      c = IncrementDigit(dice + i);
    }
    done = CheckAllDiff(dice) | c;
  }

  return c;
}

And adding the new CheckAllDiff function like so.

bool CheckAllDiff(char* dice)
{
  for (int i = 0 ; i < 6 ; i ++)
  {
    for (int j = i + 1 ; j < 6 ; j++)
    {
      if (dice[i] == dice[j])
      {
        return false;
      }
    }
  }
  return true;
}

This improves things a lot as for every time the left dice gets incremented, if it finds two digits the same, it just increments again and the right hand dice iis left at 000000 without having to be incremented a million times to get back there.

pi@raspberrypi:~ $ time ./cal
best yet 5 from 012345 012345
best yet 6 from 012345 012346
best yet 7 from 012345 012367
best yet 8 from 012345 012678
best yet 21 from 012345 016789
T: 1506792952 Current: 012346 000000 Best 21 012345 016789
T: 1506792955 Current: 012347 000000 Best 21 012345 016789
T: 1506792958 Current: 012348 000000 Best 21 012345 016789
T: 1506792961 Current: 012349 000000 Best 21 012345 016789
T: 1506792964 Current: 012354 000000 Best 21 012345 016789
T: 1506792968 Current: 012356 000000 Best 21 012345 016789
T: 1506792971 Current: 012357 000000 Best 21 012345 016789
T: 1506792974 Current: 012358 000000 Best 21 012345 016789
T: 1506792977 Current: 012359 000000 Best 21 012345 016789
T: 1506792980 Current: 012364 000000 Best 21 012345 016789
T: 1506792983 Current: 012365 000000 Best 21 012345 016789

This time the left dice increments every 3.1 seconds on average and because we can’t have two digits the same, there are 10*9*8*7*6*5 of them. That’s 151200 increments of 3.1 seconds which totals 468720 seconds or 5.425 days. Much better, but there’s more we can do.

If we’re going to check a dice with 123456 on it, there’s no point checking 654321, or any other combination of 1 to 6. So, all I have to do is figure out a way to avoid checking combinations of numbers that have been checked before. Does that mean that we need to remember all of the combinations so far and figure out if the new set is the same but in a different order? No, thinking outside the box a bit, it’s actually fairly simple. Just make sure the digits are always in ascending order. That won’t stop us checking any combination of 6 numbers, but there’s no way we can get the same numbers twice. Here’s the new IncrementOne and the new CheckIncreasing function.

bool IncrementOne(char* dice)
{
  bool done = false;

  bool c = true; // c is our carry flag to indicate a rollover.

  while (!done)
  {
    c = true;
    for (int i = 5 ; i >= 0 && c; i--)
    {
      c = IncrementDigit(dice + i);
    }
    done = (CheckIncreasing(dice) & CheckAllDiff(dice)) | c;
  }

  return c;
}

bool CheckIncreasing(char* dice)
{
  for (int i = 0 ; i < 5 ; i ++) { if(dice[i] >= dice[i+1])
    {
      return false;
    }
  }
  return true;
}

Which gives this output.

pi@raspberrypi:~ $ time ./cal
best yet 5 from 012345 012345
best yet 6 from 012345 012346
best yet 7 from 012345 012367
best yet 8 from 012345 012678
best yet 21 from 012345 016789
T: 1506793211  Current: 012346 000000  Best 21  012345 016789
T: 1506793212  Current: 012347 000000  Best 21  012345 016789
T: 1506793213  Current: 012348 000000  Best 21  012345 016789
...
T: 1506793336  Current: 356789 000000  Best 21  012345 016789
T: 1506793336  Current: 456789 000000  Best 21  012345 016789
T: 1506793337  Current: 000000 000000  Best 21  012345 016789
There is No Solution!

real	2m6.553s
user	2m6.540s
sys	0m0.010s

There is No Solution!

The good news here is that the 6 month calculation has now gone right down to just over two minutes. The bad news is that we’ve proved that the calendar doesn’t work. This doesn’t fit with my observations though we’ve had the calendar for months and it’s always been able to show the date.

Time to see what their solution is. The numbers on the two blocks were 012357 and 012468. They cheated!!! There’s no number 9 on there at all. The only way they get 09,19 and 29 is to use the 6 upside down.

The problem is computers are always very literal, a zero and a letter O are completely different to them, while humans happily use the letter instead of the number in common speech. A 6 and a 9 are completely different to the computer, but to a human they’re the same thing, just upside down. Ok, the font matters but as long as your calendar has a suitable typeface you can make it all work by using an upside down 6 as a 9.

So I made another version of the program that has a couple of lines in to make a 9 in the date match a 6 on the block. I just added a couple of lines to IsDigitOnDice leaving it looking like this.

bool IsDigitOnDice(char* dice, int digit)
{
  // to prove that it only works if 6 and 9 are the same (but upside down) count 9s as 6s
  if (digit == 9)
  {
    digit = 6;
  }

  char d[8];
  sprintf(d,"%d",digit);
  return (strstr(dice,d));
}

And running like this.

pi@raspberrypi:~ $ time ./cal
best yet 5 from 012345 012345
best yet 6 from 012345 012346
best yet 7 from 012345 012367
best yet 31 from 012345 012678
Found a solution 012345 012678


real	0m0.012s
user	0m0.000s
sys	0m0.000s

For the first time, we have a solution. It only took 12ms to find it too. All the work getting the 6 month calculation down to 2 minutes isn’t completely wasted though. It proved that there’s no solution that doesn’t rely on 6 and 9 looking like the same number. It also leads me to wonder if these calendars work in all languages.

 

Thanks for joining me in this little journey of discovery. There may be a moral to this tale, but the only thing I can think of is this. Looking at something most people wouldn’t give a second glance to and trying to figure out how it works may seem strange to some people. But you never know where a train of thought like that can end. In this case I found ways to speed up a 6 month calculation to 2 minutes. The journey turned out to be much more fullfilling than the destination.

2 Replies to “Working out what not to work out.”

Leave a Reply

Your email address will not be published. Required fields are marked *