Thread: Puzzle Input And Array c++ using a-star algorithm

  1. #1
    Registered User
    Join Date
    Apr 2012
    Posts
    7

    Puzzle Input And Array c++ using a-star algorithm

    Hey,

    I've developed a 8puzzle solver using a fixed width and height

    Below is my input condition and the pre-set goal state which i use for testing.
    Code:
    for (i = 0; i < 9; i++)        cin >> initstate[i/3][i%3];
        
        for (i = 0; i < 9 ; i++){
            if (i != 8){
                endstate[i/3][i%3] = i+1;
            }else {
                endstate[i/3][i%3] = 0;
            }
    Assume initstate and endstate have been defined as two dimensional arrays with dimensions[3][3].

    I've used a-star search to find the shortest path f(n) = h(n) + g(n)
    A couple of questions
    1. How do i go about getting the input from a text file ?
    Yes i am familiar with fstream and getline but
    for example if the text file is such:
    4
    4
    1@(3,1) 6@(3,3) 0@(1,2) etc upto 16 values
    1@(1,1) 2@(1,2) 3@(1,3) etc upto 16 values

    In this case the first line denotes its Height, second line its Width
    third line its initial state and fourth line its goal state.

    Also if the input is put into a hashtable(if someone suggests)
    do the parameters given such as (3,1) (3,3) which are the position
    values of each of the pre-fix'd numbers "1" @(3,1)
    if Not then what sort of string strip/trim is required and how do
    you specify delimiters with @(can be any number, can be anynumber)

    2. Equally large problem im facing is how do i use the input Height, Width info from the text file to define/initialise my node & priority queue ? Currently they are all pre-set to function for a 3x3. I want to attempt a 4x4 & 5x3. Basically the size of the board, goal array need to be set at runtime.

    3. I've tried substituting certain fixed values such as 3, with 4
    and 9 with 16 in for loops and the respective i/dimension, i%dimension cases and the possible number of states 9factorial/8bits replaced by 16!factorial/15 bits respectively where it's required in the program and the base table (multiples of 9 or 16)
    Where am i going wrong ? what functions for a 3x3 should do the same for 4x4 with appropriately replaced values yes ? I was wondering if parity needs to be used if so then how ? I know the basic parity function.

    I've tried various test cases for the 3x3 and it performs perfectly.
    I've also seen a code online which uses template metamorphing but i cant quite get the hang of it (it works for a set dimension value, 4x4)

    Below is some sample code which gives an idea of my problem
    Code:
    // My header file ->
    class node {private:
        // functions omitted
    public:
        node(valNum board[3][3]); //valnum can be double or
        valNum nodeBoard[3][3];   //unsigned short/long int
        // other functions omitted
    };
    
    class Pqueue {
    private:
        // code omitted
        valNum startState[3][3]; //3x3 i need dynamic 5x3/4x4
        char stateChecked[45360]; //9factorial/8bits
    public:
        Pqueue(valNum begin[3][3], valNum end[3][3]);
        ~Pqueue();
        // code omitted
    };
    
    void Pqueue::doOpen(node *posn)
    {
        // code omitted
    //marks position as visited 
        stateChecked[pos/8] = stateChecked[pos/8] | check;
           
    }
    If you require any further code to understand my question better, let me know.
    Last edited by isAnonymous; 04-17-2012 at 02:24 PM. Reason: error in variable used

  2. #2
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Show your attempt at reading in and parsing this data.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  3. #3
    Registered User
    Join Date
    Apr 2012
    Posts
    7
    Quote Originally Posted by oogabooga View Post
    Show your attempt at reading in and parsing this data.
    Thats the point, if it was not like "2@(1,1)" and was "2, 4, 8, 0, 1" i would know how to parse that using a delimiter ','
    I have looked at a function fopen

    Code:
    FILE *fp;     int iValue = -1, iValue2 = -1; 
        if ((fp = fopen(FILENAME, "r")) == NULL) 
        { 
            cout << FILENAME << " not found" << endl; 
    returnEXIT_FAILURE; 
        }
        fscanf(fp, "(%i", &iNumRows); 
        fscanf(fp, "%i)\n", &iNumCols);
        std::vector<std::vector<int> > stdStartArray(iNumRows, std::vector<int>(iNumCols)); 
        std::vector<std::vector<int> > stdEndArray(iNumRows, std::vector<int>(iNumCols)); 
        
    //read in the initial array 
        fscanf(fp, "("); 
        for(unsigned int i = 0; i < iNumRows; i++) 
        { 
            fscanf(fp, "("); 
            for(unsigned int j = 0; j < iNumCols; j++) 
            { 
                fscanf(fp, "%i", &iValue); 
                if(iValue == iValue2) 
                { 
                    stdStartArray[i][j] = -1; 
                    fscanf(fp, "*"); 
                } 
                else 
                { 
                    iValue2 = iValue; 
                    stdStartArray[i][j] = iValue; 
                } 
    //     cout << iValue; 
            } 
            fscanf(fp, ") "); 
        } 
        fscanf(fp, ")\n"); 
        
    //read in the final array 
        fscanf(fp, "("); 
        for(unsigned int i = 0; i < iNumRows; i++) 
        { 
            fscanf(fp, "("); 
            for(unsigned int j = 0; j < iNumCols; j++) 
            { 
                fscanf(fp, "%i", &iValue); 
                if(iValue == iValue2) 
                { 
                    stdEndArray[i][j] = -1; 
                    fscanf(fp, "*"); 
                } 
                else 
                { 
                    iValue2 = iValue; 
                    stdEndArray[i][j] = iValue; 
                } 
    //     cout << iValue; 
            } 
            fscanf(fp, ") "); 
        } 
        fscanf(fp, ")\n");
    And i also get a file not found error though the given filename exists in the project folder
    Last edited by isAnonymous; 04-17-2012 at 05:35 PM. Reason: lines of code were commented out

  4. #4
    Registered User
    Join Date
    Apr 2012
    Posts
    7
    Okay, since im using Xcode, the absolute path to file is required.
    Yet, im unable to make it work for the given specifications of the inputfile

  5. #5
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Why would you use fopen? That's C, not C++. You said you were familiar with fstream. Use it. Read in the line as a C++ string and parse it with the string member functions.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  6. #6
    Registered User
    Join Date
    Apr 2012
    Posts
    7
    Yeah, i'll try it out with fstream. I used fopen because i had used it a long time ago to parse data when coding in c.
    But let me see if i understand correctly, i should discard of "@(num,num)" for each instance of "num@(num,num)"
    for ex: Input file
    5
    3
    1@(2,1) 0@(2,2) 7@(2,3) <---- So i keep 1 0 7 yeah ?

  7. #7
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    1@(2,1) 0@(2,2) 7@(2,3) <---- So i keep 1 0 7 yeah ?
    It's your data. You tell me.
    I assume you need all of it in some shape or form.

    That really is an ugly data format, though.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  8. #8
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    If you can guarantee that the numbers in your file are single digit positive integers, you can easily put the lines into strings using getline and get the individual numbers as characters using the [] operator.

  9. #9
    Registered User
    Join Date
    Apr 2012
    Posts
    7
    Yeah, i asked my professor about it and he said we cant change it.
    Anyways i thought about this
    i read the file
    and instead of running a for loop to assign the array index its values
    i use the values in the brackets(minus 1 since array index starts at 0)
    and the value before @ is assigned to that array index.

    Again, my problem lie's with the very mode of inputting it.
    How do i parse the value before @ and then the values after @ in brackets with a ',' delimiter between them ?
    fscanf ? istream getline ? getchar ?
    figuring out how to do the algorithm was one thing but this has me stumped

  10. #10
    Registered User
    Join Date
    Apr 2012
    Posts
    7
    No negative numbers will be input. Only 0 to max 25.
    Single and double digits.

  11. #11
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    You said you were familiar with fstream. It seems more correct to say that you are not familiar with it at all.

    At any rate, if you're allowed to assume that the data is perfect (you don't have to do any error checking on it) then it's actually very simple.

    I'm assuming that there are exactly width * height - 1 values in the 3rd and 4th line (since one square in the puzzle must be empty).
    Code:
    #include <iostream>
    #include <fstream>
    using namespace std;
    
    int main() {
        ifstream f("puzzdat.txt");
        int width, height, n, x, y, i, j;
        char c; // for eating chars
        f >> width >> height;
        cout << width << ", " << height << "\n\n";
        for (i = 0; i < 2; i++) {
            for (j = 0; j < width * height - 1; j++) {
                f >> n >> c >> c;
                f >> x >> c;
                f >> y >> c;
                cout << n << " -> " << x << " : " << y << "\n";
            }
            cout << "\n";
        }
    }
    Of course this just prints the values. As you say, you need to subtract one from the x and y values and load your data structure (a 2d array presumably) with the n values at position x, y.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  12. #12
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    If there are going to be both single and double character digits, you are better of doing it with C or C++ streams.
    You can put much of it behind levels of abstraction though, which will also help coding the algorithm in a simpler manner.
    Make a class..say.. Foo, containing 3 values generated from input like "1@(2,1)". Overload the >> operator for it.
    Make another class..say..Bar, containing 2 numbers and an array of 16 Foo objects. Overload the >> operator for it with the help of the >> operator of Foo.
    Then your work with parsing is already done.
    If you've got a std::ifstream representing your input file, a simple >> operation does the whole parsing.

    You also get other benefits from it, like having classes representing a node containing the adjacency list (iirc) and another with a coordinate and a weighting value.
    Last edited by manasij7479; 04-17-2012 at 07:56 PM.

  13. #13
    Registered User
    Join Date
    Apr 2012
    Posts
    7
    Code:
    #include <iostream>
    #include <fstream>
    #include <string>
    #include <stdlib.h>
    usingnamespacestd;
    
    
    int main() {
        
    ifstream f("input.txt");
        int array[6][6];
        int array2[6][6];
        int width = 0, height = 0, n, x, y, i,j ;
    char c; // for eating chars
        f >> width;  
        f >> height;
        cout << width << ", " << height  << "\n\n";
        for (i = 0; i < width * height; i++) {
                f >> n >> c >> c;
                f >> y >> c;
                f >> x >> c;
                cout << n << " -> " << x << " : " << y << "\n";
                array[y-1][x-1] = n;
                cout << "\n"; 
        }
        for (i = 0; i < width * height; i++) {
            f >> n >> c >> c;
            f >> y >> c;
            f >> x >> c;
            cout << n << " -> " << x << " : " << y << "\n";
            array2[y-1][x-1] = n;
            cout << "\n"; 
    
    
        }
        for (i = 0; i < width; i++) {
            for (j = 0; j < height; j++){
                cout << array[i][j] << " ";
            }
            cout << endl;
                
        }
       
    }
    ---input.txt---
    3
    3
    0@(1,1) 1@(1,2) 3@(1,3) 4@(2,1) 2@(2,2) 5@(2,3) 7@(3,1) 8@(3,2) 6@(3,3)
    1@(1,1) 2@(1,2) 3@(1,3) 4@(2,1) 5@(2,2) 6@(2,3) 7@(3,1) 8@(3,2) 0@(3,3)
    ---input.txt---

    Thanks!

    This configuration will work in my current algorithm function,
    any tips/suggestions for programming it in such a way that
    where i currently declare board or puzzle[3][3] in my main file and in my header file
    i can have it set to a pointer or vector pointer puzzle[HeightFromInput][WidthFromInput] so that it takes the height and width
    from the input file ?
    Last edited by isAnonymous; 04-17-2012 at 09:33 PM.

  14. #14
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    If you use std::vector you can grow the board data storage as you read the file in.
    Last edited by rogster001; 04-18-2012 at 06:26 AM.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. need help in swapping puzzle contain of the array...
    By tianwu in forum C Programming
    Replies: 4
    Last Post: 11-28-2011, 09:08 AM
  2. The puzzle again...Swapping elements of 2D array
    By crazygopedder in forum C Programming
    Replies: 44
    Last Post: 11-05-2008, 01:53 PM
  3. A basic Word Puzzle Algorithm
    By m0ntana in forum C Programming
    Replies: 5
    Last Post: 03-29-2007, 12:05 PM
  4. star wars vs star trek
    By psychopath in forum A Brief History of Cprogramming.com
    Replies: 28
    Last Post: 06-14-2005, 10:28 PM
  5. Star Wars or Star Trek
    By Garfield in forum A Brief History of Cprogramming.com
    Replies: 32
    Last Post: 09-28-2001, 08:33 AM

Tags for this Thread