Courses/CS 460/Fall 2006/Liu, Gioung
From CSWiki
email: jliu133 AT yahoo.com
Contents |
[edit] Week #1
[edit] Week #2
For this assignment. Instead of using the areaAdjacent method, I have order the positions; first, second, third,...fifth using less than or greater than constraint. And that seemed to work out pretty nicely.
[edit] Week #3
I finally understood how this is done. but still stuck on java syntax. Constraint cannot be imposed on null values in an array.
- kakaru.java <-bugs.
Finally a working version and the techniques is unlike kakros.java
- kakuro.java <- Working Version. =).finally.(
)
- kakuro_result.txt
In process of coding... very challenging indeed.
[edit] Week #4
TowersHanoi.java<--in working process. I may try this using choco. stack.java
There are now some Choco examples linked to from the main course page. There may be some bugs. It's pretty easy to use — at least the stuff I've tried. I'd be interested in your experience.
Russ Abbott 22:49, 15 October 2006 (PDT)
Okay. I will first try it in Jacop then in choco. hopefully I can go through all the programming hurdle. --GLiu 19:19, 16 October 2006 (PDT)
I am currently doing the Towers of Hanoi or the block problem that you posted on the web. I have correctly set up the beginning, in between states, and the final states of Towers of Hanoi. However, figuring out how to impose constraint on these conditions was a challenge for me.
1. Exactly one block was moved, i.e., exactly one support changed. 2. The block that was moved was not the support of some other block. 3. A block may not support itself. 4. The new support for the moved block may be either the table or some other block. If the new support is some block s, then s may not also be the support of some other block.
1. I have used And((Or(new And(new (xneqy, xeqy,..),new And(),..), isvalid()) for this condition.
Can you give me a hint on how to go about imposing constraint on condition 2? I have tried. consider block
a/b/table~> b/table, a/table I can say (if block is lowest, and block[n] != block[n+1].
It depends on how you are representing the relationship between the blocks. How are representing the relationship that says that block a is resting on block b?
Russ Abbott 12:28, 27 October 2006 (PDT)
block0, block1, block2, block3
fdv block0 =fdv(store, 1,1) //means block0 is sitting on top of block1.
block1==fdv(store, 2, 2) //likewise, block 1 is sitting on block 2. and so forth. If block is sitting on top of one of the three tables(call them src, aux, dst), then blockn = fdv(store,src.value, src.value). I have included source code.
I am almost done, all I need is to correctly impose constraint. Perhaps I may present this tomorrow to get more ideas.
Good we can talk about it in class.
[edit] Week#5
A* (A star search) not ready
Some online references which may help someone.
- http://www-cs-students.stanford.edu/~amitp/gameprog.html#Paths
- http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html
- http://www.policyalmanac.org/games/aStarTutorial.htm
- http://sky.fit.qut.edu.au/~streit/AStar.html
- http://www.edenwaith.com/products/pige/tutorials/a-star.php
- http://en.wikipedia.org/wiki/Breadth-first_search
Thanks for the links.
You seem to be having a lot of trouble with the code. Have you done enough programming to be ready for this class? What's your background? You can send me email directly: Russ.Abbott@GMail.com Russ Abbott 14:25, 4 November 2006 (PST)
Actually, I seemed to be having problem with the concepts. I am fairly okay with coding as I am also programming for work but in a different language. (.net).
Hello Dr. Abbott, Again, I am going through your source code to better understand your search, core, and extendablestate implementations to establish a foundation knowledge/understanding of the program before I can really move on to coding. =). (as I am really a beginner)
In the WGC_ExtendableState, you have the following method. Why did you multiply 8, 4, 2 to farmer, wolf, and goat?
private Integer treeEntryValue() {
return new Integer(getFarmer() * 8 + getWolf() * 4 +
getGoat() * 2 + getCabbage());
}
I'm trying to understand how this work. what is the value of treeEntryValue vs object.treeEntryValue(). Are you comparing current with nextstate?
public int compareTo(Object object) {
return treeEntryValue().compareTo(((WGC_ExtendableState)object).treeEntryValue());
}
The search method keeps track of the states it has seen so that it doesn't process the same state more than once. treeEntryValue() is a way to identify a state so that it can be compared to some other state. If two states have the same value for treeEntryValue() they are the same state.
I now use the toString() representation of a state for this purpose. Two states that look the same are the same. wc~fg is the samw as wc~fg no matter how you got there.
Russ Abbott 07:44, 1 November 2006 (PST)
childCounter == 0 ? "wolf" :
childCounter == 1 ? "goat" :
childCounter == 2 ? "cabbage" :
"");
the childcounter is counting the number of leaves on the nodes. Still a bit confused on this part of code.
We know that each state has four possible transitions: move the farmer by himself or move the farmer with one of the 3 items. The childCounter keeps track of which of these transitions we are up to.
Russ Abbott 14:05, 2 November 2006 (PST)
[edit] Week#7
I tried XplusYeqC
Look at EqualsC as an example. Do you understand what holds(), fails(), invalidate() and validate() do there and why they are written the way they are?
in EqualC
a) holds() if fdv is instantiated to a value and the value is the correct value.
b) fails() if fdv is instantiated (has a value) and the fdv value is not equal to the current's object value. This is the situation that it will only fail. There is no "current object." The desired value is specified when the constraint is created.
I believe validate returns a CP for these situations 1)if the domain in the model does not contain the possible values where fdv = value. Then it returns invalid. 2) if the fdv has a singleton value returns true if getDomain().size==1, other false. If it has a singleton value that means that getDomain.size() == 1. It returns true if the desired value (the variable value) is in the domain. It returns false if it's not in the domain. Also, if it's in the domain, it removes all other values. 3) fdv.setvalue() looks like it adds the object value to the model domain. It removes all other values. If the object is not in the domain, it indicates that it can't setValue.
still figuring invalidate().looks like it returns the CP indicating if the value in a domain is removed or not.
invalidate() removes the value from the domain -- thereby making it impossible for validate() to succeed.
[edit] Week#8
Java Constraint Handling Rules
http://en.wikipedia.org/wiki/Antisymmetric_relation http://en.wikipedia.org/wiki/Binary_relation
Understanding CHR rules. Given: reflexivity @ X leq Y <=> X=Y | true. antisymmetry @ X leq Y , Y leq X <=> X=Y. idempotence(simpagation CHR) @ X leq Y \ X leq Y <=> true. transitivity @ X leq Y , Y leq Z ==> X leq Z.
- reflexivity states that X leq Y is simplified to true iff x = y.
- antisymmetry states that if x leq y and y leq x, the rule can be simplified further by replacing the equivalent X=Y.
- idempotence (simpagation CHR): Definitions: Given a binary operation, an idempotent element (or simply an idempotent) is something that when multiplied by (or for a function, composed with) itself, gives itself as a result. For example, the only two numbers which are idempotent under multiplication are 0 and 1.
In the above given, X leq Y \ X leq Y <=> true can be simplified to X leq Y <=> true.
transitivity relation: mathematics, a binary relation R over a set X is transitive if it holds for all a, b, and c in X, that if a is related to b and b is related to c, then a is related to c.
Example: if a = b, and b=c, then a = c is considered a transitive relation.
This may somewhat help understand the rules of JCHR.
http://www.sics.se/sicstus/docs/3.7.1/html/sicstus_34.html#SEC298
Please refer to Joan Kim's page for up-to-date progress.
[edit] Week#8 comments and questions
Do you know what the @ means? It almost seems like everything to the left of it is a comment. Is that right? Is everything to the left a label with no real functionality?
If you were going to parentheses in the reflexivity rule, where would they go?
X leq Y <=> (X=Y | true) (?)
I'm confused about how to read this. What's the purpose of the "true" in the rule? I don't see how you get the English description you give (X leq Y is simplified to true iff x = y) from the rule. Perhaps I don't -understand what the vertical bar ( | ) means in the rule. Is it different from "or"?
I meant to write x =< y is logically equivalent to true, if and only if x = y ( using reflexivity rule).
The @ symbol is a separator between the identifier and rule.
identifier @ rule where rule is Head ==> guard |body identifier and @ symbol is not used as part of the actual constraint computation.
Head ==> guard | body. An empty constraint is denoted by "true" and can be removed from the constraint store. Reflexivity is part of the simplification rule. The vertical bar | is a separater between the guard and the body. Head ==> guard | body means the head implies the body if the guard holds, a precondition for the rule. --GLiu 01:54, 2 December 2006 (PST)
I hope you are also looking at the comments on the Course discussion page. In particular, if JCRH consists only of forward chaining rules, how does it differ from other forward chaining systems? Also could JCHR be used for aspect-oriented-programming?
Russ Abbott 15:49, 25 November 2006 (PST)
Yes, I am. We're looking into your questions and suggestions. =). Thanks!
final presentation: Understanding constraint handling rules ( 
)
Topic to covered in JCHR (Java Constraint Handling Rules ) Presentation JCHR Introduction CHR Introduction Syntax Operational Semantics Example CHR-v Introduction Operational Semantics Example Constraint Program Solvers Introduction Syntax Example JCHR complex example : Less then or Equal JCHR complex example : Sudoku Help JCHR Installation References
