Last visit was: It is currently Thu Mar 28, 2024 4:55 pm


All times are UTC-05:00




Post new topic Reply to topic  [1 post ] 
    Author Message
     Post subject:Something about the vsec and vpdin
    PostPosted:Sun May 02, 2010 12:17 pm 
     

    Joined:Mon Feb 16, 2009 12:42 am
    Posts:11
    I think both vsec and vpdin problems are one kind problem. The MOD equation. That means the solution only depends on which slot you click and how many times you click, The sequence you click has no influence to the final status. So we can just click from the top to bottom.
    There is another feature of the MOD equation, the equation is under the modulus system. This means in the modulus 2 system, it's the same you click a slot twice as just do nothing.
    Now we can build the math model. Give you a w*h matrix A, you need to find out a w*h matrix B which indicates the times of each slot to click.
    Let B[j] means the time to click the ith row jth col, we know 0<B[j]<m, here m means the modulus of the system. So there is only m^(w*h) candidate solutions. OK, you can solve it by program.
    But, the quad-vpdin puzzles, the candidate solutions can be 4^(5*5)=1125899906842624, this will be tested in 35 years if you can test 1M candidate solutions in one second.
    We need a faster algorithm. actually, we need only test m^w and m^(3*w) candidates solutions separately in vpdin and vsec puzzle.
    As mentioned above, the final status is independent with the sequence you click. So we can click from the top to the bottom, after we click the top line(there is m^w ways to click the first line). The the second line have only one choice to make the first line clean. Then the third line... and so on. This means, the way you click the first line determines the way you click other lines. The vsec puzzel is similar, the first 3 lines determines the other lines. Here I offer the code to solve them. You should change the code and recompile to fit your own requirements:
    Code:
    #include <iostream> #include <memory.h> #include <cstdlib> #include <typeinfo.h> using namespace std; #define WIDTH 4 #define HEIGHT 4 #define ROTATE 2 template <class T> void click(T &data, const int i, const int j, const int count){ if (count == 0) return; data[i][j] = (data[i][j] + count) % ROTATE; if (j > 0) data[i][j - 1] = (data[i][j - 1] + count) % ROTATE; if (j < WIDTH - 1) data[i][j + 1] = (data[i][j + 1] + count) % ROTATE; if (i < HEIGHT - 1) data[i + 1][j] = (data[i + 1][j] + count) % ROTATE; } template <class T> void click_vsec(T &data, const int i, const int j, const int count){ if (count == 0) return; data[i][j] = (data[i][j] + count) % ROTATE; if (j > 0) data[i][j - 1] = (data[i][j - 1] + count) % ROTATE; if (j < WIDTH - 1) data[i][j + 1] = (data[i][j + 1] + count) % ROTATE; if (i < HEIGHT - 1) data[i + 1][j] = (data[i + 1][j] + count) % ROTATE; if (i > 0) data[i - 1][j] = (data[i - 1][j] + count) % ROTATE; if (i > 2) data[i - 3][j] = (data[i - 3][j] + count) % ROTATE; if (j > 2) data[i][j - 3] = (data[i][j - 3] + count) % ROTATE; if (j < WIDTH - 3) data[i][j + 3] = (data[i][j + 3] + count) % ROTATE; if (i < HEIGHT - 3) data[i + 3][j] = (data[i + 3][j] + count) % ROTATE; } template <class T> bool check(T &data){ for (int i = 1; i < HEIGHT; i++) for (int j = 0; j < WIDTH; j++) click(data, i, j, ROTATE - data[i - 1][j]); for (int j = 0; j < WIDTH; j++) if (data[HEIGHT - 1][j] != 0) return false; return true; } template <class T, class G> bool check_vsec(T &data, G &result){ for (int i = 3; i < HEIGHT; i++) for (int j = 0; j < WIDTH; j++){ result[i][j] = (ROTATE - data[i - 3][j]) % ROTATE; click_vsec(data, i, j, result[i][j]); } for (int i = HEIGHT - 3; i < HEIGHT; i++) for (int j = 0; j < WIDTH; j++) if (data[i][j] != 0) return false; return true; } template <class T> void vpdin_solve(T &status){ int test[WIDTH][HEIGHT]; int searchSum = 1; for (int i = 0; i < WIDTH; i++) searchSum *= ROTATE; int temp; for (int i = 0; i < searchSum; i++){ memcpy(test, status, sizeof(status)); temp = i; for (int j = 0; j < WIDTH; j++){ click(test, 0, j, temp % ROTATE); temp /= ROTATE; } if (check(test)){ cout<<"The answer is:"<<endl; temp = i; for (int j = 0; j < WIDTH; j++){ cout<<(temp % ROTATE)<<" "; temp /= ROTATE; } cout<<endl; break; } } } template <class T> void vsec_solve(T &status){ int test[WIDTH][HEIGHT]; int result[WIDTH][HEIGHT]; int searchSum = 1; for (int i = 0; i < WIDTH * 3; i++) searchSum *= ROTATE; int temp; for (int s = 0; s < searchSum; s++){ memcpy(test, status, sizeof(status)); memset(result, 0, sizeof(result)); temp = s; for (int i = 0; i < 3; i++) for (int j = 0; j < WIDTH; j++){ result[i][j] = temp % ROTATE; click_vsec(test, i, j, temp % ROTATE); temp /= ROTATE; } if (check_vsec(test, result)){ cout<<"The answer is:"<<endl; for (int i = 0; i < HEIGHT; i++){ for (int j = 0; j < WIDTH; j++) cout<<result[i][j]<<" "; cout<<endl; } cout<<endl; break; } } } int main(){ int status[WIDTH][HEIGHT]; for (int i = 0; i < WIDTH; i++) for (int j = 0; j < HEIGHT; j++) cin>>status[i][j]; vsec_solve(status); system("pause"); return 0; }
    PS: The VSEC2.0 and VSEC3.0 is easy to solve if you know the solution to the same pattern with VSEC1.0. This is because of, you change the sequence of click won't change the final status, so all you need to do is just find out a sequence to satisfy the rule of VSEC2.0 or VSEC3.0.
    PS2: The click rule of VSEC system is:
    Code:
    O O O X O O O O O O O O O O O O O X O O O X O X X X O X O O O X O O O O O O O O O O O O O X O O O
    No change if out of bounds.


    Top
    Offline  
    Display posts from previous: Sort by 
    Post new topic Reply to topic

      All times are UTC-05:00


      Who is online

      Users browsing this forum: No registered users and 22 guests


      You cannot post new topics in this forum
      You cannot reply to topics in this forum
      You cannot edit your posts in this forum
      You cannot delete your posts in this forum
      You cannot post attachments in this forum

      Search for:
      Jump to:  
      cron
      Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
      Theme created by Miah with assistance from hyprnova