definitions required for solving the rubix cube?

[TestingTuring]

Hello! I am currently writing a program to find the shortest path solution in a randomized rubix cube. There is a certain langauge/search based methodology that has caught my attention, and which i would like to apply to the solution, but I am unaware of what kind of terminology i should be looking up.

 

THE METHODOLOGY:

 

The methodology is one where different languages are developed to satisfy different aspects of the cubes solution. For instance we might find a language/grammar which appropriately describes/generates all transformations which move one block of the cube to some position we want it to be. We may then find another language which satisfies the movement of another block to some position we want it to be. The language which satisfies both of these languages is the one which generates transformations which will move BOTH blocks to where they are supposed to be.

 

WHAT I WOULD LIKE TO LEARN MORE ABOUT:

It is in this sense that I am interested in learning more about how languages can be tested against each other in order to CONSTRAIN the otherwise unweildly "search tree" that would be required to be derived and searched in order to find the solution.

 

At the same time i would like to build a symbolic vocabulary which would allow me to compare the different pertinent variables (runtime, memory size, etc.) of different tree search constraint methodologies, particularly language based methdods (as i have poorly defined them).

 

I am also particularly interested in the methodologies that can be used to detect patterns in the strings which are satisfying two seperate languages so that a third language which satisfies both can be developed.

 

Also, i would like to learn more about how we can show that one language is mutually exclusive to another language.

 

I am particularly interested in terminology so that i might do research on the internet, however i would also greatly appreciate any book recommendations. Thank You!

[Sensei]

Also, i would like to learn more about how we can show that one language is mutually exclusive to another language.

 

Not sure what you mean by "mutually exclusive" in the context of computer languages.

But f.e. you can write Logo in C/C++/C#/Java/JavaScript/Net Framework etc.

but you cannot write C/C++/C#/Java/JavaScript/Net Framework in Logo language..

 

Are not you mixing language with algorithm?

In general purpose languages (majority of them, Logo excluded )

you can write pretty much the same algorithm,

in their own version, with very little (subjective) changes.

 

Have easier task for example than rubik's cube: binary search algorithm.

And try making it in C,

then in C++,

then in Java,

then in C#..

etc.

 

In language that does not have object-orientated environment you can cheat by f.e. using call-backs, which will be emulation of virtual methods (C++ virtual method in reality is call-back internally).

(in general solution to binary search algorithm it's needed for comparison of elements of unknown type at design time)

Edited December 16, 2015 by Sensei

[Strange]

But f.e. you can write Logo in C/C++/C#/Java/JavaScript/Net Framework etc.

but you cannot write C/C++/C#/Java/JavaScript/Net Framework in Logo language..

 

Why not? Are you saying it is not Turing complete?

[Sensei]

I am talking about making whole language, executable (binary) file, in other language.

That requires full I/O file management control, at least.

Edited December 16, 2015 by Sensei

[Strange]

I am talking about making whole language, executable (binary) file, in other language.

 

That requires full I/O file management control, at least.

 

Logo has file I/O. As such, anything you can write in C you can write in Logo. (In the worst case, you can write a C interpreter or compiler in Logo and use that! Not that it would be a sane thing to do...)

[Sensei]

Logo has file I/O. As such, anything you can write in C you can write in Logo.

It's not enough to "have file I/O". It must be binary file I/O. Without binary mode, it's not possible to generate executable.

I was trying to find example, and some MODERN implementations of Logo language (FMSLogo) have binary mode, some other has no mention of it..

 

f.e.

Berkeley Logo has no mention of mode in OPENWRITE command,

FMSLogo has additional parameter for mode.

 

In FMSLogo tutorial there is said "If binarymode is FALSE or not given, then the file will be read as a text file."

Giving impression that default mode of original OPENREAD/OPENWRITE is text mode,

otherwise compatibility would be broken..

 

[Strange]

So you also write a Logo program that generates a shell script to convert the text file to binary ...

[TestingTuring]

Wow this is all going over my head. By language i meant from a computational logic perspective. I.e a language is a collection of strings that satisfy some machine. In particular, i have multiple machines that generate context_free grammars, and the language i need to indentify is the one which solves all of them.

 

I've been told that it's likely i won't be able to develop a single language based on patters between the language generating process. do you all think this is true?

 

I'm not super familiar with the language hierarchy but to be clear the languages that i need to "union" into a single language would not be recognized by a Finite state machine but they would be recognized by a push down automata.

[fiveworlds]

This has already been solved in java for a 3x3 cube

 

http://www.jaapsch.net/puzzles/cubie.htm

[Sato]

Hey TestingTuring, welcome to the forum.

I think the above responders have misunderstood your question.

 

I'm not familiar with work around your specific problem, but some searching yields this and this. They look to mainly discuss defining constrains as/from formal languages though, but maybe they can help you with your idea to define constrains for those rubik's-transformation languages too, by those methods.

 

Considering problems like this as the application of transformations/operations to get to the result, it would be useful to frame it in the arena of group theory and abstract algebra; here's an expository article modelling the cube and its solution as a group. Once you do this, you can look into techniques from automated theorem proving and computer algebra and apply them, maybe considering your language as some FOL-formalized algebraic structure and applying the appropriate theorem proving techniques to derive formulas that satisfy your constraints. One language would be exclusive from another here if their derived formulas contained some sort of contradiction together, and the problem of finding patterns between languages would be some model satisfiability problem.

It might be more useful for your automata-theoretic purposes to consider algebraic structures (sets equipped with some number of operations on their elements) in general, which is a focus of universal algebra, rather than specific mathematical applications like rings, fields, vector spaces, and the like. You should look for work on domain specific theorem proving techniques to universal algebra or whatever specific structures you decide to use if you do.

 

These are far from well-wrought ideas, but hopefully useful to yours.

[TestingTuring]

Hey Sato thanks a ton, you've given me alot to chew on for a while as i work out my answer. I'm going to begin reading the material you have posted right now. I'm also going to try and get someone who knows more about java visual tools to build a visualizer for me which will map out the different grammars on the cube tree. Hopefully i can find an interesting way to ascribe axis's to the graph such that patterns between the meeting points of languages emerge.

 

Fiveworlds, i'm aware there is a solution, but I'm more interested in deriving my own solution than looking at someone elses. Once i'm satisfied with what i have built i will compare it to others work and try and understand what i could have done better, and how what it would have taken for me to see my error in the first place.

[Strange]

I think the above responders have misunderstood your question.

 

Or rather, side-tracked because we didn't have an answer!

[Sato]

Hey Sato thanks a ton, you've given me alot to chew on for a while as i work out my answer. I'm going to begin reading the material you have posted right now. I'm also going to try and get someone who knows more about java visual tools to build a visualizer for me which will map out the different grammars on the cube tree. Hopefully i can find an interesting way to ascribe axis's to the graph such that patterns between the meeting points of languages emerge.

 

Happy to! As for the visualization, I don't know how useful that would be to find patterns. If you're really inclined to detect patterns (patterns, in the intuitive sense) in the languages, and solve your problem like that, you ought to look into feature learning in natural language processing and natural language generation, and apply those ideas to your formal languages. But I think taking a computational logic approach as discussed before would be best, as those strings really do have a well known and studied structure that would take any ML algorithm much longer to derive, if it could at all, than directly applying the appropriate algebraic ideas. The learning problem would be a lot more tractable for just finding solutions to the Rubik's cube, but I got the inkling that you want to find a general method for deriving languages of the sort you described—but it would be cool if you somehow derived different groups / their general properties using ML over some training data like Rubik's moves.

 

Do you work in CS/software, or are you a student, hobbyist?

 

edit:

 

Or rather, side-tracked because we didn't have an answer!

 

'Course you! Though I think Sensei and Fiveworlds genuinely misunderstood the question, which over a gloss looks like it might be talking about programming languages and Rubik's cube solving algorithms in general.

Edited December 17, 2015 by Sato

[TestingTuring]

 

Happy to! As for the visualization, I don't know how useful that would be to find patterns. If you're really inclined to detect patterns (patterns, in the intuitive sense) in the languages, and solve your problem like that, you ought to look into feature learning in natural language processing and natural language generation, and apply those ideas to your formal languages. But I think taking a computational logic approach as discussed before would be best, as those strings really do have a well known and studied structure that would take any ML algorithm much longer to derive, if it could at all, than directly applying the appropriate algebraic ideas. The learning problem would be a lot more tractable for just finding solutions to the Rubik's cube, but I got the inkling that you want to find a general method for deriving languages of the sort you described—but it would be cool if you somehow derived different groups / their general properties using ML over some training data like Rubik's moves.

 

Do you work in CS/software, or are you a student, hobbyist?

 

edit:

 

 

'Course you! Though I think Sensei and Fiveworlds genuinely misunderstood the question, which over a gloss looks like it might be talking about programming languages and Rubik's cube solving algorithms in general.

 

 

Happy to! As for the visualization, I don't know how useful that would be to find patterns. If you're really inclined to detect patterns (patterns, in the intuitive sense) in the languages, and solve your problem like that, you ought to look into feature learning in natural language processing and natural language generation, and apply those ideas to your formal languages. But I think taking a computational logic approach as discussed before would be best, as those strings really do have a well known and studied structure that would take any ML algorithm much longer to derive, if it could at all, than directly applying the appropriate algebraic ideas. The learning problem would be a lot more tractable for just finding solutions to the Rubik's cube, but I got the inkling that you want to find a general method for deriving languages of the sort you described—but it would be cool if you somehow derived different groups / their general properties using ML over some training data like Rubik's moves.

 

Do you work in CS/software, or are you a student, hobbyist?

 

edit:

 

 

'Course you! Though I think Sensei and Fiveworlds genuinely misunderstood the question, which over a gloss looks like it might be talking about programming languages and Rubik's cube solving algorithms in general.

I know the graphical solution might be a long shot in the dark. But something inside me seems to think there might be a pattern between the length of the cube tree generator and the node height, which would be my axis's. It would be particularly valuable because a string in the tree should be able to be generated based on those two variables, so if a pattern does arise, so does a method for deriving the strings denoted by those points.

 

Your inkling is right, i am interested in the implications of modeling search tree constraints as languages. I think it would be super cool if i could build a general rubix solver.

 

I am currently a hobbyist who just started working in database management. I am trying very hard to get into a good school to study undergrad, but i wrecked my GPA during my more careless years haha.

 

I'd like to ask you the same thing?

 

Since we've begun talking about patterns, i'd like to inquire:

 

Are patterns the same thing as relations between sets (which i think is the definition of a function)? If this is the case, than all patterns should be enumerable and capable of being represented graphically?

Edited December 17, 2015 by TestingTuring

[Strange]

'Course you! Though I think Sensei and Fiveworlds genuinely misunderstood the question, which over a gloss looks like it might be talking about programming languages and Rubik's cube solving algorithms in general.

 

I think it is a really interesting concept try and use languages (in the formal sense) to explore solutions to the Rubiks cube. But I don't have a clue how you would go about it...

The methodology is one where different languages are developed to satisfy different aspects of the cubes solution. For instance we might find a language/grammar which appropriately describes/generates all transformations which move one block of the cube to some position we want it to be. We may then find another language which satisfies the movement of another block to some position we want it to be. The language which satisfies both of these languages is the one which generates transformations which will move BOTH blocks to where they are supposed to be.

 

It occurs to me that you might come up with a solution that is really interesting but which is NP complete (these sorts of matching/satisfying algorithms often seem to go that way).

[TestingTuring]

 

I think it is a really interesting concept try and use languages (in the formal sense) to explore solutions to the Rubiks cube. But I don't have a clue how you would go about it...

 

It occurs to me that you might come up with a solution that is really interesting but which is NP complete (these sorts of matching/satisfying algorithms often seem to go that way).

 

I'm glad you like it! The not having a clue on where to begin is the fun part i think. I;d like to imagine I'm building my own search tree for a solution as well.

I'm still not to the complexity section of my computational logic text, so I'm not sure what that means. My understanding is that it has something to do with the time required to compute a solution?

[Sensei]

Chess computer algorithm for instance, in the normal computer programming, is trying every possible movement, and calculate score, how good is particular movement.

And pick up the best scored movement to realize it on playfield.

In the first move in game there is possible maximum 20 moves (and rapidly grows in later moves): movement of pawns 16 possible, plus 4 movements of 2 knights.

Once algorithm test its virtual movement, it's also doing this for opponent side. And judge them with score also. It happens recursively.

Couple depths for slow machines. The faster machine (or cluster) the more game versions can be simulated, and the better prediction of what will happen on playfield in the future.

 

[DevilSolution]

Sensei any chance you know of a way of pattern recognition within discrete data, I've though about permutations and tested a little but the set size is too much for my computer to handle. I was thinking more along the lines of some matrix magic, with some given statistical functions to clear out some of the "noise". However i dont have a clue how to break the discrete data into matrix form, i just know its a possible way of dissecting patterns.

 

Regards.

[Sensei]

Sensei any chance you know of a way of pattern recognition within discrete data, I've though about permutations and tested a little but the set size is too much for my computer to handle. I was thinking more along the lines of some matrix magic, with some given statistical functions to clear out some of the "noise". However i dont have a clue how to break the discrete data into matrix form, i just know its a possible way of dissecting patterns.

 

Any particular type of data in pattern?

Like for instance letters, characters.. ? Even printed fonts on screen.. ?

These are easier to code.

Once I wrote something like that.

Built database of the all possible images (something like characters). Took screen-shot taking app. And in Photoshop glued them in one row with fixed width * columns x height.

Then routine was checking pixel by pixel, with some level of threshold tolerance, each entry in database, with image taken from screen (it was captured in the real time).

 

If you can, allow user learning machine how each entry (character) to database looks like. Allow him to pick up reference which will be analyzed and stored in database.

 

Keeping raw image (RGB, pixel by pixel, width x height buffers) is one way of storing it. Not very efficient one (after all Full HD screen has 2 million pixels = 6/8 MB in 24/32 bit TrueColor).

Programmer can use vector graphics for store and compare data. But it's much more work to do. Image has to be analyzed to find where are edges, and convert them to 2D vectors..

 

If images are colorful, people often use filters like emboss. Because it will detect where are edges.

 

Are you writing code for automatic bypassing CAPTCHA .. ?

Edited December 19, 2015 by Sensei

[DevilSolution]

No not playing with AI at all, discrete numbers, i thought perhaps something like the Fourier but the data hasnt been standardised or normalised etc.

 

Basically patterns in the forex and stock markets. I know trading is so quick on the forex but i believe various patterns will emerge as recurring events. I was thinking about hard coding the logic and using classifiers to permute as much data as i could but i dont have the resources.

 

I need a quick fix, i read there were techniques using matrices and some form of statistics to normalise the data so its in the right format, but i dont know much beyond an identity matrix, transformation and trig matrix that i used in computer graphics.

 

Do you know if matrices are used commonly in pattern recognition?

Edited December 19, 2015 by DevilSolution

[imatfaal]

 

Are you writing code for automatic bypassing CAPTCHA .. ?

 

Wasn't Captcha (or its progenitor) written as a way of getting wetware* to read numbers, letters, script that was too difficult for computers to read

 

*ie us

[Endy0816]

You are thinking of the later reCAPTCHA system.