nghiaho12
BAN USERC++ solution.
void Remote(string word)
{
// Start at top left
int cur_x = 0;
int cur_y = 0;
cout << "Starting at: a" << endl << endl;
for(size_t i=0; i < word.size(); i++) {
cout << word[i] << ": ";
int idx = word[i] - 'a';
// 6x5 grid
int dst_y = idx / 5;
int dst_x = idx % 5;
if(word[i] == 'z') { // special case: dest is 'z', can reach always with left + down
int left = cur_x;
int down = dst_y - cur_x;
for(int j=0; j < left; j++)
cout << "Left ";
for(int j=0; j < down; j++)
cout << "Down ";
}
else { // can reach any letter with up/down + left/right
int dx = dst_x - cur_x;
int dy = dst_y - cur_y;
for(int j=0; j < abs(dy); j++) {
if(dy > 0)
cout << "Down ";
else
cout << "Up ";
}
for(int j=0; j < abs(dx); j++) {
if(dx > 0)
cout << "Right ";
else
cout << "Left ";
}
}
cout << "OK" << endl;
cur_x = dst_x;
cur_y = dst_y;
}
}
int main()
{
Remote("zoosi");
}
Starting at: a
z: Down Down Down Down Down OK
o: Up Up Up Right Right Right Right OK
o: OK
s: Left Down OK
i: Up Up OK
Brute force C++ using recursion, but sped up considerably by sorting the array before hand.
bool FindHalf(const vector<int> &A, int target, int remaining,
int start, vector<bool> used, vector<int> &first_half, vector<int> &second_half)
{
//g_calls++;
if(target == 0 && remaining == 0) {
for(size_t i=0; i < used.size(); i++) {
if(used[i])
first_half.push_back(A[i]);
else
second_half.push_back(A[i]);
}
return true;
}
// Did not find a solution
if(remaining == 0)
return false;
for(size_t i=start; i < A.size(); i++) {
if(used[i]) continue;
if(target - A[i] >= 0) {
used[i] = true;
if(FindHalf(A, target - A[i], remaining-1, i+1, used, first_half, second_half))
return true;
used[i] = false;
}
}
return false;
}
// wrapper function
void FindHalf(const vector<int> &A)
{
assert(A.size() % 2 == 0);
int sum = accumulate(A.begin(), A.end(), 0);
int target = sum/2;
vector<bool> used(A.size(), false);
vector<int> first_half, second_half;
FindHalf(A, target, A.size()/2, 0,used, first_half, second_half);
// print out results
for(size_t i=0; i < first_half.size(); i++)
cout << first_half[i] << " ";
cout << endl;
for(size_t i=0; i < second_half.size(); i++)
cout << second_half[i] << " ";
cout << endl;
}
// Example of usage
int main()
{
vector<int> A = {1,11,2,12,3,13,4,14,5,15,6,16,7,17,8,18,9,19,
155,65,1,11,2,12,3,13,4,14,5,15,6,16,7,17,8,18,9,19,155,65}; // C++11
sort(A.begin(), A.end());
FindHalf(A);
return 0;
}
With the example input of 40 integers, it makes 271 recursive calls to FindHalf. Without the sorting it takes a VERY long time.
- nghiaho12 January 16, 2014
Seems like my comment and code did not match up. Updated the code.
- nghiaho12 February 01, 2014$ ./set_top_box
Starting at: a
c: Right Right OK
z: Left Left Down Down Down OK
c: Up Up Up Up Up Right Right OK
z: Left Left Down Down Down OK