Demo entry 2244403

phonenumber

   

Submitted by anonymous on Jul 17, 2015 at 18:09
Language: C++. Code size: 5.1 kB.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_set>
using namespace std;

/* This problem can be generalized as a graph searching problem. We can use backtracking algorithm to solve it.
Consider the two different possible move patterns, we can design a pattern class. This can make our searching algorithm more scalabale when there are new move patterns coming.*/

class MovePattern {
   string pattern;
   public:
      void SetPattern(string patt) {
          pattern = patt;
      }
    
      void GetChildren(vector<int>& children, int parent) {
          if(pattern == "knight") {
              knight(children, parent);
          }
          else if(pattern == "bishop") {
              bishop(children, parent);
          }
      }
      
      int child(int digit, int xshift, int yshift) {
          // if the child is out of bound, return -1;
          // else return child digit.

          // compute the x- and y-coordinate of child digit
          digit -= 1;
          int x = digit / 3 + yshift;
          int y = digit % 3 + xshift;
          
          // check the positon of child digit
          if (x < 0 || x > 2 || y < 0 || y > 2) {
              return -1;
          }
          return x * 3 + y + 1;         
      }
    
      void knight(vector<int>& children, int parent) {
          // possible x-shift and y-shift
          int a[] = {-1, 1};
          int b[] = {-2, 2};
          
          // 0 has two children 4 and 6
          if(parent == 0) {
              children.push_back(4);
              children.push_back(6);
              return;
          }

          // get children for 1 ~ 9
          for (int i = 0; i < 2; ++i) {
              for (int j = 0; j < 2; ++j) {
                  int ch1 = child(parent, a[i], b[j]);
                  int ch2 = child(parent, b[j], a[i]);
                  if (ch1 != -1) {
                      children.push_back(ch1);
                  }
                  if (ch2 != -1) {
                      children.push_back(ch2);
                  }
              }    
          }

          // this is the corner case we missed in the online test solution
          if(parent == 4 || parent == 6) {
              children.push_back(0);
          }
      }
    
      void bishop(vector<int>& children, int parent) {
          int a[] = {-1, 1};

          // 0 has two children 7 and 9
          if(parent == 0) {
              children.push_back(7);
              children.push_back(9);
              return;
          }
          // There are four digonal forward directions for a digit, each has at most two steps
          // so the total is at most 8 children. The actual number of children is less then 8.
          for (int k = 1; k <= 2; ++k) {
              for (int i = 0; i < 2; ++i) {
                  for (int j = 0; j < 2; ++j) {
                      int xshift = a[i] * k;
                      int yshift = a[j] * k;
                      int ch = child(parent, xshift, yshift);
                      if (ch != -1) {
                          children.push_back(ch);
                      }
                  }
              }
          }

          // this is the corner case we missed in the online test solution
          if(parent == 7 || parent == 9) {
              children.push_back(0);
          }
      }
};

int backtrack(int length, MovePattern pattern, int startDigit) {
    if (length == 0) {
        return 1;
    };
    vector<int> childDigits;
    pattern.GetChildren(childDigits, startDigit);
    int sum = 0;

    // iterate through all the possible child digits
    for (int i = 0; i < childDigits.size(); ++i) {
        sum += backtrack(length - 1, pattern, childDigits[i]);
    }    

    return sum;
}

int NumOfUniquePhoneNums(int length, unordered_set<int>& invalidFirDigs, MovePattern pattern) {
    int sum = 0;
    for (int i = 0; i < 10; ++i) {
        if (!invalidFirDigs.count(i)) {
            sum += backtrack(length - 1, pattern, i);
        }
    }
    return sum;
}

// void printVector(vector<int>& v) {
//     cout << endl;
//     for (int i = 0; i < v.size(); ++i) {
//         cout << "child " << v[i] << ' ' << endl;
//     }        
// }
// void testMovePattern() {
//     vector<int> a;
//     MovePattern mp;
//     mp.SetPattern("bishop");
//     mp.GetChildren(a, 6);
//     printVector(a);
    
//     a.clear();
//     mp.SetPattern("knight");
//     mp.GetChildren(a, 6);
//     printVector(a);

// }


int main() {
    /* Read from STDIN. Print output to STDOUT */   
    std::string piece;
    std::cin >> piece;
    
    // piece can be "knight" or "bishop"
    
    int moves = 0;
    
    // calculate moves 
    int length = 8;

    // unordered_set<int> invalidFirDigs = {0, 1};
    unordered_set<int> invalidFirDigs;
    invalidFirDigs.insert(0);
    invalidFirDigs.insert(1);

    MovePattern movePat;
    movePat.SetPattern(piece);
    // testMovePattern();

    moves = NumOfUniquePhoneNums(length, invalidFirDigs, movePat);  
    
    std::cout << moves << std::endl;
    return 0;
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).