Hello,
I am working on an algorithmic-solution for the "Instant Insantiy"
problem. There are some problems with the code I am working on, and I
would like someone to "fix" the program for me.
I have attached three test files (test.txt, test1.txt, test2.txt), the
makefile and the current C source-code (ii.c) here:
http://www.setcomputing.com/ii/ii.tar.gz
I expect the program to work on the files I supplied and some
addtional test cases, if possible. In addition to that, the
source-code should be modified to output all possible solutions (this
should be very very simple to do with my current implementation).
NOTE: (The #define NO_CUBES needs to be changed for different test
files)
Thanks |
Request for Question Clarification by
maniac-ga
on
12 May 2003 10:03 PDT
Hello Salman1,
Could you please clarify a few points as follows:
- What is your deadline to have the fix completed?
- I ran the program w/ the three test files and saw
o a solution for test.txt, test1.txt
o no solution for test2.txt (I am not sure if this was correct data
or not)
are these the results you expected or something else?
- are you supposed to display all four sides (top, bottom, front,
back) to show they don't repeat any of the colors?
- would you be interested in other "improvements"?
- could you clarify what you meant by "fix" - which symptoms are you
trying to get rid of? [I saw the "all solutions" change - really
interested in any other fixes beyond that and the test2 results]
Thanks.
--Maniac
|
Clarification of Question by
salman1-ga
on
12 May 2003 10:49 PDT
Maniac,
1) May 16, 2003 should be okay for a deadline. I can add more time if
necessary.
The problem, if you run test.txt here's what you get for output:
FRONT BACK | RIGHT LEFT
-------------------------------------------------------
CUBE 1 : Blue Yellow | Green Green
CUBE 2 : Green Orange | Orange Yellow
CUBE 3 : Yellow Blue | Blue Yellow
CUBE 4 : Orange Green |
The problem is CUBE 4: The program was unable to find a right-left
solution for cube 4, because it had to backtrack upto cube 1 and
modify to a different color and in turn modify cube 2, cube 3 and
finally find a solution to cube 4. I have a backtrack code on line:
210-217+ you will need to make some changes there.
2) WHen you run test1.txt you need to modify NO_CUBES (please make
sure).
2a) test2.txt works fine as it is now, BUT if you rearrange the
appearance of the colors for example:
If I replace the line in test2.txt: "Blue White | Green Red | Red Red"
with:
"Blue White | Red Red | Green Red" the program fails to display a
complete solution. That shouldn't be the case because ORDER shouldn't
matter. Since a cube is topologically symmetric.
3) Yes all four-sides top, bottom, left,right needs to be displayed.
4) The only improvement I need is you will need to modify the
source-code to display all the solutions rather than just 1. One more
thing, if you find any way to improve (in terms of optimization
time-wise) then please do so.
Thanks
|
Clarification of Question by
salman1-ga
on
13 May 2003 08:09 PDT
Maniac,
I just wanted to make sure, are you working on the problem?
|
Request for Question Clarification by
maniac-ga
on
13 May 2003 10:16 PDT
Hello Salman1,
Yes I am. I spent some time looking at the code yesterday and am
pretty sure what the basic problem is, but am not so sure on the
"best" solution for it. See the commentary at the end for the
recommendation on the "final solution". While I'm looking at that, I
do have a few comments that you may want to act on "sooner" rather
than "later".
Analysis by Splint
http://www.splint.org/
indicates a number of "problems" including:
- use of uninitialized variables (usually i, j); I looked at these
and the use of I^=I; will certainly set I to zero, but is the kind of
thing that makes the reader (e.g., code review) go crazy.
- a mixture of unsigned and signed variables used in comparisons.
Depending on how the compiler implements the comparison, you can get
"the wrong answer" (e.g., -1 is 0xFFFF which is greater than 2 if the
comparison is unsigned).
- not all fields are initialized in the data structures
- use of _ as the leading character in some names (reserved for
compilers...); [though I was going to ask the Splint mailing list
about this one since the names you have are nested & should not cause
name collisions]
These don't at this point seem to affect the operation of the program,
but if you expect to develop software professionally, you may want to
start using a tool like Splint and improve the style of your software.
Separately I noted that the function that initializes the structure
from a file can also corrupt memory - add a check that you have not
read > NO_CUBES rows of information and exit the loop in that case as
well. This was not caught by Splint and could cause some hard to debug
symptoms (on my system it corrupted the color names).
The root cause of the program failing to find solutions for all cases
appears to be the way it handles the permutations of positions. The
basic problem has...
- three unique positions for the first cube; the rest "don't matter";
basically, each pair of colors is "not used" to produce the three
positions that are unique
- 24 unique positions for the second through last cube; put each cube
face up / rotate four times to get the 6 x 4 (24) positions.
and it appears the existing code:
- treats each cube the same (including the first one)
- does a subset of the unique positions
it is actually pretty hard for me to figure out which positions you
are trying; I did a quick hack to change array size from 3 to 6 (and
adjust all related constants), which appears to "solve" test.txt, but
has other problems and does not print the result out properly [sigh].
You may have better insight on which combinations are tried and fill
this in.
However, since you asked for all possible combinations, it would be
simpler to code this up as a set of nested loops (or use loops and
recursion) to try all the combinations with a short circuit to avoid
"losing" positions where the first few cubes fail to meet the
restrictions of the problem. That is what I recommend as the "final
solution" and what I'll look at tonight unless you have other
suggestions.
--Maniac
|
Clarification of Question by
salman1-ga
on
13 May 2003 11:19 PDT
Maniac,
I updated everything as you requested. The new
http://www.setcomputing.com/ii/ii.tar.gz now does not contain any: ^=,
unified all unsigned and signed issues, everything was replaced to int
rather than unsigned and short and I ran the code through lint and
found everything OK.
Secondly, you shouldn't have to worry about loosing the positions,
because when a solution is found through SearchSolution it [the
solution] is inserted into either ColorTableFb or ColorTableLr
(depending on the call to SearchSolution) which contains the two
colors that were chosen and the AdjancentLevel (0,1,2) so basically
ColorTableFb->c[CUBE_NO].AdjacentLevel will give you the path you have
taken. Addtionally, if(ColorTableFb->c[0].AdjacentLevel>2) then there
are no more solutions!
These are just my thoughts, and I certainly don't want to make life
harder for you than as it -- so go ahead and do whatever you have to.
Thanks a lot,
Salman.
|
Clarification of Question by
salman1-ga
on
13 May 2003 11:48 PDT
Maniac,
Just wanted to clarify some basic ideas behind my algorithm:
If you think of each cube as a set then you get something like this:
0 1 2
Cube1 = {{C1,C2},{C3,C4},{C2,C1}}
Cube2 = {{C2,C1},{C2,C4},{C3,C2}}
Cube3 = {{C4,C2},{C3,C3},{C2,C3}}
Cube4 = {{C1,C1},{C3,C2},{C3,C1}}
What the algorithm does is: takes the first subset for cube1, which
is, {C1,C2} and inserts it into a front-back table along with the
position of that set, in this case it's 0. Then it searches for
another (*ANOTHER*) set within cube1 and inserts it into a left-right
table along with the position of that set, let's assume that is:
{C3,C4} (which is position 1).
The the algorithm moves to Cube2 and checks each subset to make sure
the colors are insertable (which means no one color appears more than
once - this check is done against each of the tables, front-back and
left-right)
Eventually it moves to 4 and completes.
In case of a failure (if one color DOES appear more than once) then
the algorithm moves to the previous cube and tries a different
position other than the one already chosen (this is done by
incrementing the position already chosen by 1, a further complication
arise when this position (after incrementing) is greater than 2 then
the algorithm needs to move one more cube above, and so on).
I am sorry if I can't be as clear as I'd like to, hopefully this will
give you some ideas.
Thanks
Salman.
|
Request for Question Clarification by
maniac-ga
on
13 May 2003 20:41 PDT
Hello Salman1,
I downloaded what you updated and made some changes to produce a
program that appears to work OK. The results are...
test.txt
CUBE 1 [{Blue,Yellow}, {Green,Green}, {Yellow,Orange}]
CUBE 2 [{Green,Orange}, {Blue,Blue}, {Yellow,Orange}]
CUBE 3 [{Green,Orange}, {Blue,Yellow}, {Green,Blue}]
CUBE 4 [{Green,Blue}, {Green,Orange}, {Blue,Orange}]
[1] Blue (0)
[2] Yellow (1)
[3] Green (2)
[4] Orange (3)
FRONT BACK | RIGHT LEFT
-------------------------------------------------------
CUBE 1 : Blue Yellow | Yellow Orange
CUBE 2 : Green Orange | Orange Yellow
CUBE 3 : Yellow Blue | Blue Green
CUBE 4 : Orange Green | Green Blue
FRONT BACK | RIGHT LEFT
-------------------------------------------------------
CUBE 1 : Blue Yellow | Yellow Orange
CUBE 2 : Green Orange | Orange Yellow
CUBE 3 : Yellow Blue | Green Blue
CUBE 4 : Orange Green | Blue Green
FRONT BACK | RIGHT LEFT
-------------------------------------------------------
CUBE 1 : Blue Yellow | Yellow Orange
CUBE 2 : Orange Green | Orange Yellow
CUBE 3 : Yellow Blue | Blue Green
CUBE 4 : Green Orange | Green Blue
FRONT BACK | RIGHT LEFT
-------------------------------------------------------
CUBE 1 : Blue Yellow | Yellow Orange
CUBE 2 : Orange Green | Orange Yellow
CUBE 3 : Yellow Blue | Green Blue
CUBE 4 : Green Orange | Blue Green
FRONT BACK | RIGHT LEFT
-------------------------------------------------------
CUBE 1 : Blue Yellow | Yellow Orange
CUBE 2 : Yellow Orange | Orange Green
CUBE 3 : Green Blue | Blue Yellow
CUBE 4 : Orange Green | Green Blue
test1.txt
CUBE 1 [{Purple,Yellow}, {Purple,Purple}, {Purple,Red}]
CUBE 2 [{Blue,Blue}, {Green,Yellow}, {Red,Green}]
CUBE 3 [{Green,Blue}, {Green,Green}, {Blue,Red}]
CUBE 4 [{Yellow,Red}, {Red,Blue}, {Purple,Yellow}]
CUBE 5 [{Purple,Purple}, {Purple,Blue}, {Purple,Purple}]
[1] Purple (0)
[2] Yellow (1)
[3] Red (2)
[4] Blue (3)
[5] Green (4)
(quits w/o solution - too many purple sides on cubes 1 and 5)
test2.txt
CUBE 1 [{Blue,White}, {Green,Red}, {Red,Red}]
CUBE 2 [{Blue,Red}, {Red,White}, {Green,White}]
CUBE 3 [{Blue,White}, {Green,Red}, {Green,White}]
CUBE 4 [{Blue,White}, {Green,Green}, {Blue,Red}]
[1] Blue (0)
[2] White (1)
[3] Green (2)
[4] Red (3)
FRONT BACK | RIGHT LEFT
-------------------------------------------------------
CUBE 1 : Blue White | Green Red
CUBE 2 : White Green | Red Blue
CUBE 3 : Green Red | White Green
CUBE 4 : Red Blue | Blue White
These look like the right results . The version I am running adds a
"choose" table that enumerates the permutations (three for first cube,
24 for the rest) and changes PlayInstantInsanity to be recursive
through each cube, printing when it finds a NO_CUBES solution. It runs
pretty fast - the output scrolls as fast as the terminal window
scrolls with these sample files.
I read through your clarifications - I understand the structures of
cube and OrderTable; these are still used in the new version. The main
point I wanted to make in my previous comment was that SearchSolution
was not using enough permutations; as far as I can tell, it does only
1/4 to 1/2 of the possible choices. The loop I suggested (w/ the data
structure) makes the code smaller (about 15%) and ensures all choices
are evaluated in a consistent manner.
I can answer with the version I currently have (with explanation)
- let you review the code / ask questions about how it works
- try additional test cases [though if you provide them in a
clarification - I'll check those too]
- address any other issues
However, if you want me to work with your original code more fully - I
can try to fix the version I had last night which follows your methods
more closely.
Please advise.
--Maniac
|
Clarification of Question by
salman1-ga
on
13 May 2003 21:35 PDT
Maniac,
Wonderful! I am willing to get a copy of your code, and see if
everything looks OK. And I will clarify with you if I have any more
questions.
Thanks a lot,
Salman.
|
Clarification of Question by
salman1-ga
on
13 May 2003 23:58 PDT
Maniac,
One other thing, it would be great if you could post the code on the
web-server somewhere rather than here (if possible) - that way you can
delete the file as soon as I finish downloading.
Thanks
Salman.
|
