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

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

3. Originally Posted by oogabooga
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)
{
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));

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");

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

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

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

8. 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. Yeah, i asked my professor about it and he said we cant change it.
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. No negative numbers will be input. Only 0 to max 25.
Single and double digits.

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

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

13. 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 ?

14. If you use std::vector you can grow the board data storage as you read the file in.