multi-dimensional array problem similar to Rubik’s cube writen in C++ an multi-d

Question

multi-dimensional array problem similar to Rubik’s cube

writen in C++ an multi-dimensional array that first read integer N which denotes the number of dimensions(four dimensions being the max) of a multi-dimensional array. Next read the dimensions d0 d1 … d4, so the array will have dimensions d0 by d1 by … by d4. Next read the initial values of the array using array aggregate notation. The array elements will always include the value 0 and will always consist of distinct consecutive non-negative integers, but these integers might be arranged in any order.

Examples input:

That each move relocates the 0 element to a new position, and is specified as a dimension and a distance. The dimension k will be in the range 0 to N–1, and the distance indicates how far the 0 element will travel (positive indicates increasing indexes, and negative indicates decreasing indexes). However, to prevent reaching outside the range of valid indexes 0 to dk–1, the indexes along each dimension will wrap around in a circular fashion. As the value 0 travels the specified distance, it swaps places with each other value it encounters.

Example:

The goal is to find a sequence of moves that leads to the array configuration such that all the array elements will be in ascending order when written in aggregate notation (or in row-major order).

Examples input followed output:

Were the correct sequence of moves is not necessarily unique. Several examples follow; each example shows an input and then two of the many possible corresponding output sequences. Your final output should only show the move sequence, not the array contents.

examples:

Hints:

• As shown in the previous examples, it is always possible to replace any move with distance d2 by d moves with distance exactly 1 each. You can experiment to find which way works better for your program’s design.

• One possible approach is to explore all the possible move sequences in breadth-first order, by maintaining a queue of all the array configurations that can be reached. This guarantees you would eventually find a shortest sequence of moves, but your program would need to build a tree of the possible paths to explore, and it might run out of memory or waste a lot of time exploring paths that are not getting nearer to the goal.

• Another possible approach is to explore the possible move sequences in depth-first order. Either use recursion, or place all the array configurations you can reach into a stack. However you would need to make sure your program doesn’t get caught in an infinite recursion, and again it’s possible to waste a lot of time exploring paths that are not getting nearer to the goal.

• The best approach for solving larger problems efficiently might be to use a priority queue rather than either a FIFO queue or a stack. To compute a priority for a given array configuration, you could measure how far each array element currently is from its desired final location, and then take the sum of all these distances. If your program explores configurations in the order of smallest priority first, this will enable you to explore the paths soonest that are getting nearest to the goal. This approach is somewhat similar to Dijkstra’s algorithm.

Program should behave as illustrated in the above examples. The program should be runnable by typing either of the following commands:

program (standard input)

program < inputfile.txt > outputfile.txt

For the first line above, your program will read from the keyboard and write to the screen. The second line redirects standard input to come from the specified inputfile, and it redirects standard output to go to the specified outputfile, but your program is unaware of these files.

Explanation / Answer

Answer: See the presudo code below:

1. Read a multidimensional array:

--------------------------------------------------------------------

1. Read number of dimensions, N, for array.

2. //loop to read sizes of N dimensions

3. For each i=0:N-1

4. Read value d[i] of size of each dimension

5. End For loop

6. Allocate an array A[d[0]][d[1]]--------------------[d[N-1]] to store elements

7. Assign elements in aggregate notation to A.

Note: For such kind of procedure, it would be better to specify maximum number of dimension procedure can support.

Rest of the description looks incompelete. Hence specify complete description for full solution. Also the name of language in which required.

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.