# 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.