# Mathematics × Programming Competition #8 - Programmatic solution

A week ago, @kenchung posted a new problem that I enjoyed solving!

https://steemit.com/contest/@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

🐾

kenchung (66)7 years agoA very detailed solution! nice work! :)

armandocat (63)7 years agoThanks 😸

sammarkjames (59)7 years agoHEY! YOU!

Just popped up on my screen and led me here eyyy? Genius.

mohansingh (46)7 years agoGood job... Thank u...👍

bobbyboe (55)7 years agoragazzo intelligente :-)

amielis (25)7 years agoI have vote

Vote my pos

coolisland (41)7 years agoPedantic perhaps but you are talking 10000 numbers not 1000 :)

Nice solution.

alfiannurmedia (-2)(1) 7 years agoFery good my frend

steemitboard (66)5 years agoCongratulations @armandocat! You received a personal award!

_{You can view your badges on your Steem Board and compare to others on the Steem Ranking}## Vote for @Steemitboard as a witness to get one more award and increased upvotes!