Mathematics × Programming Competition #8 - Programmatic solution

A week ago, @kenchung posted a new problem that I enjoyed solving!
@kenchung/question-mathematics-programming-competition-8

Suppose we want to use non-transparent cards to represent all the possible 4-digit numbers from 0000 to 9999. Each card will show one 4-digit number, where the numbers are written using seven-segment-display. However when some cards are rotated 180°, a new number can be formed. For example when the card 0159 is rotated 180°, it becomes 6510.
Note that it is acceptable for the ‘1’ to be displayed on the left hand side.
Considering the possibility of rotating a card 180°, what is the minimum number of non-transparent cards required to represent all the possible 4-digit numbers from 0000 to 9999?

This time, I took a programmatic approach to solve the problem:

var upsideDownMap = {
  '1': '1',
  '2': '2',
  '5': '5',
  '6': '9',
  '8': '8',
  '9': '6',
  '0': '0'
};

// total number of cards needed
var numberOfCards = 0;

// contains the number already represented
var numbers = {};

var checkNumber = function(number) {
  // transform the number into a 4 digit string
  var n1 = '0000' + number;
  n1 = n1.substring(n1.length-4);
  
  // if number already found, no need to use another card!
  if(numbers[n1]){
    return false;
  }
  
  numbers[n1] = true;

  // find the upside-down number 
  var n2 = n1.split('').reverse().map(function(d){
    return upsideDownMap[d] || '';
  }).join('');

  if(n2.length === 4) {
    numbers[n2] = true;
  }
  
  return true;
}

// just loop for all the numbers! 
for(var number = 0; number <= 9999; number++) {
  if(checkNumber(number)){
    numberOfCards++;
  }
}

console.log('Number of cards required: ' + numberOfCards);

The idea is to go through all the numbers between 0000 and 9999 and check if the number was already found before. If it wasn't, a new card is required, and we check if the upside-down number exists and add that to the list of found numbers.

This algorithm needs to store all the numbers in memory in the numbers object. This is ok, we are just talking about 1000 numbers, but what if we want to do that for a million? or more?
We can change a bit the algorithm to not have to store all the numbers at all! This will need almost not memory, since all the state of the program is in a numeric variable.

var checkNumber = function(number) {
  var n1 = '0000' + number;
  n1 = n1.substring(n1.length-4);

  var n2 = n1.split('').reverse().map(function(d){
    return upsideDownMap[d] || '';
  }).join('');

  if(n2.length === 4 && n1 !== n2) {
     return 0.5;
  }
  
  return 1;
}

for(var number = 0; number <= 9999; number++) {
  numberOfCards += checkNumber(number);
}

This approach requires to think a little bit more about what is appening and which number requires for a new card to be used and which number doesn't.

Now, first of all, we could add a card for each number. That will not be the minimum possible number of cards. So, we could just add 1 for each number.

To find the minimum number we then have to figure out when we don't need to add a card, without storing any past decision. I decided to check that this way:

• check if the upside-down number exists: for instance 4444 doesn't have an upside-down number, so that will need a separate and unique card just for itself.
• be careful that some numbers have an upside-down number, but that number is the same as the original, i.e. 0000, 8888, 6699, ...
• if the original number has a upside-down number, and the two numbers are different, that means that the two numbers can be represented by the same card! For that reasons, instead of adding 1 to the numberOfCards variable for both number, I added 0.5 twice!

Another way of doing that, could be to just check if(n2.length === 4 && parseInt(n1,10) <= parseInt(n2,10)) and add 1 only for one of the two numbers, 0 for the other. Both results will give the same result of counting one card for both the number.

Result

The result is that 8824 cards are needed!

Thanks
Armando
🐾