find closest palindrome date of a given palindrome date

Question

A palindrome date is given and we have to find the closest palindrome date of this given date. The result date should be before the given date.

Date is in the format of YYYY/MM/DD.

One brute force solution is (pseudo-code is given which might not be efficient).

Convert the string into a number
For each number less than this number
   If the number is a valid date then
    If number is a palindrome
         print and return

I think there must be some efficient algorithm to solve this problem.

Example: Input date: 2030/03/02

Output date: 2021/12/02

Answer 1

In the given year, there will be only one palindromic date. Hence, to find previous palindromic date, you need to decrement the year and convert it to palindromic date.

Example: for 2030, valid month and day will be 03 and 02 which will lead to 2030/03/02.

So, it must be clear that palindromic date in this case is only possible when:

1. Year is of 4 digits (not for 10000) as months and number of days are in two digits
2. Last two digits of years should be {10, 20, 30, 40, 50, 60, 70, 80, 90, 01, 11, 21}
3. First two digits of years should be mirror image of 1-31 (with month and year validity).

Using rule 2 and 3, it can be checked in O(1) whether a given year has palindromic date or not in the given format. Let us assume that valid range of year is from 9999-0001, then it can be done in linear order to find previous palindromic date.

void find_prev_date(const char* input, char * output) {
    int year = extract_year(input); //Extract first 4 digits
    --year;
    //limit is 101 because 0000 will not give you valid month and day.
    for(;year>=101;--year) {
      if(haspalindromic(year))
      {
        write_date(year, output);
      }
    }
}

bool haspalindromic(int year)
{
   int first2 = year%100;
   int last2 = year/100;
   bool second_valid = false;
   bool first_valid = false;

   switch(last2){
       case 10: case 20: case 30: case 40: case 50: case 60: case 70: case 80:
       case 90: case 1: case 11: case 21: second_valid = true; break;
   }
   if(!second_valid)
      return false;

   switch(first2) {
      case 10: case 20: case 30: case 40: case 50: case 60: case 70: case 80: case 90: case 1: case 11: case 21: case 31: case 41:    case 51: case 61: case 71: case 81: case 91:
      case 2: case 12: case 22: case 32: case 42: case 52: case 62: case 72: case 82: case 92:
      case 3: case 13:
         first_valid = true;
      break;
   }

   if(!first_valid)
      return false;

   //reverse digit such that 2 yields 20
   int month = reverse_digits_on100(last2);
   int day = reverse_digits_on100(first2);

   if(month==2) {
      if(day<=28)
         return true;
      if(isleapyear(year) && day==29)
         return true;
      if(day>28)
        return false;
   }

   switch(month) {
        case 4: case 6: case 9: case 11:
        if(day>30)
           return false;
   }
   //For remaining months, check is already made as first part of year is gives day in range of [1..31].
   return true;
}

Some functions are not implemented, but their names clearly suggest intents.