Best way to search many variable

oracacle · Feb 27, 2013

^^ well sort of

this is still pertaining to cube solver i have running around in the back of my mind, and kinda need some thought on a small search algorithom i am working on.

the idea is to search for values that match what is needed, this i fairly easy if you have deadicated routine for each search

here is the bare bone for searching 4 eadge pieces

Code:

main:
            gosub search

search:
	if b1 = search1 then
		if b16 = search2 then
		;dostuf
                          return
		end if
	end if
	
	if b3 = search1 then
		if b19 = search2 then
		;dostuf
                          return
		end if
	end if
	
	if b5 = search1 then
		if b13 = search2 then
		;dostuf
                          return
		end if
	end if
	
	if b7 = search1 then
		if b10 = search2 then
		;dostuf
                          return
		end if
	end if
	
	if b16 = search1 then
		if b1 = search2 then
		;dostuf
                          return
		endif
	end if
	
	if b19 = search1 then
		if b3 = search2 then
		;dostuf
                          return
		end if
	end if
	
	if b13 = search1 then
		if b5 = search2 then
		;dostuf
                          return
		end if
	end if
	
	if b10 = search1 then
		if b7 = search2 then
		;dostuf
                          return
		end if
	end if
;if item not found, run error routine

in know there are no labels etc, how ever i cant help but this is a little bulky (and still mssing bit).

would something like this do the same as the nested if?

Code:

if b1 = search1 and b16 = search2 then
;do stuff here
;return to main program - this is sub-procedure
endif

...

i am open to other ideas if you have any.

mrburnette · Feb 28, 2013

@oracale:

I see many of these kinds of "hypothetical" questions on the forum. Most could easily be answered by using the PE simulator and just watching the program flow. Rewrite your code so that the test conditions are Variables, then run each test in PE Simulator.

It's not that any of us are trying to get around a quick answer, but sometimes a quick answer provides a wrong answer due to the uniqueness of the PICAXE instruction set and syntax parser.

- Ray

oracacle · Feb 28, 2013

the problem is, the program is a long way off from being at a point of being able to be simulated.
as a point i hoped using the and was going to work fine, and along with the second search and the memory read/write and shift sequences the program is more than 1400mb, without the main body that decided what need to be done.

the idea is>
program recieves data
look at some data for finding first piece
runs edge search - the sub i posted above
find piece
decide one moves depening on seaarch results
(does this another 3 time for other top edge pieces)
search for top corner pieces...

you get the idea, to find the top edge piece, the software needs to look at 12 cubes and 24 tiles

this is what the edge search currently look like

Code:

edgesearch:
	;subroutine to check all edges for cube needed

	let look = 0
	peek 57, b0
	peek 108, b1
	gosub searchlow
	
	let look = look + 2
	peek 59, b0
	peek 79, b1
	gosub searchlow
	
	let look = look + 2
	peek 63, b0
	peek 93, b1
	gosub searchlow
	
	let look = look + 2
	peek 61, b0
	peek 68, b1
	gosub searchlow
	
	let look = look + 2
mid:	'search edgees from middle down
	'set look value before calling code from here
	peek 66, b0
	peek 106, b1
	gosub searchlow
	
	let look = look + 2
	peek 104, b0
	peek 75, b1
	gosub searchlow
	
	let look = look + 2
	peek 81, b0
	peek 95, b1
	gosub searchlow
	
	let look = look + 2
	peek 97, b0
	peek 72, b1
	gosub searchlow
	
	let look = look + 2
	
lower:'check bottom edges only
	'set look value before calling code from here
	peek 84, b0
	peek 102, b1
	gosub searchlow
	
	let look = look + 2
	peek 86, b0
	peek 70, b1
	gosub searchlow
	
	let look = look + 2
	peek 90, b0
	peek 99, b1
	gosub searchlow
	
	let look = look + 2
	peek 88, b0
	peek 77, b1
	gosub searchlow
	
	return
	
searchlow:
	if b0 = centre1 and b1 = centre2 then
	poke move, look
	return
	endif

searchhigh:
	if b1 = centre1 and b0 = centre2 then
	let look = look + 1
	poke move, look
	return
	endif
	return

in theory it should work, until i get the main program threshed out in bare bones form i have no idea if it will work at all

hippy · Feb 28, 2013

Code:

	if b1 = search1 then
		if b16 = search2 then
		;dostuf
                          return
		end if
	end if

Can be expressed as -

Code:

	if b1 = search1 and b16 = search2 then
		;dostuf
                          return
	end if

And if you could optimise such that you were say starting from -

Code:

	if b0 = b10 then
		if b1 = b11 then
		;dostuf
                          return
		end if
	end if

You could simplify that to -

Code:

	if w0 = w5 then
		;dostuf
                          return
	end if

And, if you can make 'dostuff' an actual subroutine then that can become a simple -

Code:

	if w0 = w5 then dostuf

Buzby · Feb 28, 2013

mrburnette said:
@oracale:

I see many of these kinds of "hypothetical" questions on the forum. Most could easily be answered by using the PE simulator and just watching the program flow. ....

Hi Ray,

My feelings exactly !.

So far I've got my cube solver to get the top layer corners and edges in place, all correctly orientated.

The full sequence is :
1 - Build a solved cube
2 - Run a scrambler to mix it up
3 - Execute loads and loads of 'ifs' and 'thens'
4 - Print the result.

Not a single piece of code has seen a chip yet, it's all in the simulator !.

mrburnette · Mar 1, 2013

@Buxby:

Not a single piece of code has seen a chip yet, it's all in the simulator !.

... And this is a primary strength of PICAXE... The simulator can handle many things completely... Start small, think modular, document variable usage/reuse, grow functionality.

uC users exposed to only Arduino have no idea how easy this can be! However, as RevEd adds more to the microcode, this becomes much more difficult. I am hopeful that they can maintain such functionality in the editor environment.

- Ray

oracacle · Mar 1, 2013

first off thanks hippy, you answered my question.

secondly, i cant run it in the simulator yet as it just a collection of un-related subroutines designed to to read and write memory seqences. in this case i am able to run upto 24 if statements in a single run through the routine which will tell the main program the position and orientation of the piece in question.

the main program will most likely be if statements calling memory read, rotate and write seqences that will have been determined by the subroutine.

i did have a very basic version solving some of the top layer, but foudn i was getting short on variables (it did not use RAM just variables at that time)

Buzby · Mar 1, 2013

oracacle said:
... i cant run it in the simulator yet as it just a collection of un-related subroutines ...

If it's not runnable in the simulator, how do you run it in the chip ?.

My code so far is a #Slot full, just to solve layer 1.

Rotating a single face uses over 20 'bX = bY' instructions, and searching uses *lots* of 'ifs' and 'thens'.

Without the simulator I would never be able to view the dynamics of all the variables active in any search or rotate function.

oracacle · Mar 1, 2013

at the moment i dont plan on running it any where.

and yes, my face rotation uses alot of let comand too, how ever each rotation is done by a single subprocedure after having all the apropiate memory peek, after the rotation is complete the data is then pokes back. the peek and poke is done with seperate sub-procedure for each side - all these take currently take 1415 bytes of space

heres how my data is stored with info on the rotation variables

Code:

	       -------------
	       |101|102|103|
	       -------------
	       |104|105|106|
	       -------------
	       |107|108|109|
====================================================
|74 |75 |76 ||56 |57 |58 ||65 |66 |67 ||83 |84 |85 |
----------------------------------------------------
|77 |78 |79 ||59 |60 |61 ||68 |69 |70 ||86 |87 |88 |
----------------------------------------------------
|80 |81 |82 ||62 |63 |64 ||71 |72 |73 ||89 |90 |91 |
====================================================
	       |92 |93 |94 |
	       -------------
	       |95 |96 |97 |
	       -------------
	       |98 |99 |100|
	       -------------

once the data has been stored into these memory slots, they need to moved to
variables  for rotating the the side clock wise/anti clockwise

    |b15|b16|b17|
=====================
b18||b0 |b1 |b2 ||b14
b19||b3 |b4 |b5 ||b13
b20||b6 |b7 |b8 ||b12
=====================
    |b9 |b10|b11|

oracacle · Mar 2, 2013

while i am thinking about it, and not really wanting to make a whole new thread as i feel it may have been covered, i just cant find wha i am looking for.

is possible to call a sub procedure from variable without using if statements
something like:

Code:

gosub b0

the only thing i can think of is the following

Code:

if b0 = 1 then gosub one
if b0 = 2 then gosub two
...

i have tryed a few different things in PE, but cant find another way to call a sub dependng on a variable value

Buzby · Mar 2, 2013

See On Gosub, page 146 Manual 2

oracacle · Mar 2, 2013

that is how i would normally write a sub procedure call, however i could save myself alot of code if i could just call dirrectly from a search variable - it would appear this can not be done so countless i "if" statements will be used instead. i was just searching for a better, faster way of running movement routines

westaust55 · Mar 2, 2013

oracacle said:
that is how i would normally write a sub procedure call, however i could save myself alot of code if i could just call dirrectly from a search variable - it would appear this can not be done so countless i "if" statements will be used instead. i was just searching for a better, faster way of running movement routines

See post 11 above about the ON <variable value> GOSUB ...

If you do not need to return to the calling point in the program there is also
ON...GOTO

oracacle · Mar 3, 2013

not trying to be brash but i think you gys have missed te point i was trying to make.
i would have like to store the sub in a variable and then do the following

Code:

gosub b0

instead of looping through 20 plus if statements.

the location and orientation are already stored in the variable, all the main programme has to do is lookup the location and run the movement to correctly orient and place the piece. so for the top edges, there will be 50 possible set of moves, and thus 50 if statement to call the moves once the location and orientetion has been established. however if i could just call one of 50 sub procedures instead of asking "if" first it would shorten the program by at least 49 line just for the top edges.

(all number are based on my poor maths skills so may not be accurate)

at the minuite the program (that partly resides in my head) would have to do something like this

Code:

if b0 = 0 then
	;run moves
if b0 = 1 then
	;run moves
if b0 = 2 then
	;run moves
if b0 = 3 then
	;run moves
if b0 = 4 then
	;run moves
if b0 = 5 then
	;run moves
if b0 = 6 then
	;run moves
if b0 = 7 then
	;run moves
if b0 = 8 then
	;run moves
if b0 = 9 then
	;run moves
if b0 = 10 then
	;run moves
if b0 = 11 then
	;run moves
if b0 = 12 then
	;run moves
if b0 = 13 then
	;run moves
if b0 = 14 then
	;run moves
if b0 = 15 then
	;run moves
if b0 = 16 then
	;run moves
if b0 = 17 then
	;run moves
if b0 = 18 then
	;run moves
if b0 = 19 then
	;run moves
if b0 = 20 then
	;run moves
if b0 = 21 then
	;run moves
if b0 = 22 then
	;run moves

the if state means i would not have to run subs - this also only check for one piece and orientes it. this "string" of statement will get shorter as the cube become more complete

westaust55 · Mar 3, 2013

oracacle said:
not trying to be brash but i think you gys have missed te point i was trying to make.
i would have like to store the sub in a variable and then do the following

instead of looping through 20 plus if statements.

... however if i could just call one of 50 sub procedures instead of asking "if" first it would shorten the program by at least 49 line just for the top edges.
:
:
the if state means i would not have to run subs - this also only check for one piece and orientates it. this "string" of statement will get shorter as the cube become more complete

Maybe we are missing the point but from your example, I still see;

ON b0 GOSUB do0stuff, do1stuff, do2stuff, do3stuff......do 255stuff
or
ON b0 GOTO do0stuff, do1stuff, do2stuff, do3stuff......do 255stuff

I/we do not know what you "do stuff" code is or the overall program structure so maybe I/we do not correctly comprehend what you have in mind.

oracacle · Mar 3, 2013

i think you are still missing a little, more of a gosub b0, if so i dont have to check every value of b0 with presets with if statements

i have attatched my programme so far - still far from finnished.

the idea was to be able to run the search which return a value for it location which then goe and runs the move required. i dont really know how to explain it

heres a code snipet

Code:

if look = 0 then goto edge1	;edge 0 in correct place, move to edge 1
	;orient and position from top
	if look = 1 then
		;right side clock wise
		;back clock wise
		;top clock wise
		goto edge1
		end if
		
	if look = 2 then
		;top clock wise
		goto edge1
		end if
		
	if look = 3 then
		;back anti clock wise
		;right side anti clockwise
		goto edge1
		end if
		
	if look = 4 then
		;top clockwisw
		;top clock wise
		goto edge1
		end if
		
	if look = 5 then
		;left clock wise
		;front clock wise
		;top anti clock wise
		goto edge1
		end if

	if look = 6 then
		;top anti clock wise
		goto edge1
		end if
		
	if look = 7 then
		;front clock wise
		;right clock wise
		goto edge1
		end if
		
	;orient and position from middile
	if look = 8  then
		;back clock wise
		;top clock wise
		goto edge1
		end if

	if look = 9 then
		;right side anti clock wise
		goto edge1
		end if
		
	if look = 10 then
		;left side clockwise
		;top clock wise
		;top clock wise
		goto edge1
		end if

	if look = 11 then
		;back anti clockwise
		;top clock wise
		goto edge1
		end if
		
	if look = 12 then
		;front clock wise
		;top anti clock wise
		goto edge1
		end if
		
	if look = 13 then
		;left side anti clock wise
		;top clock wise
		;top clock wise
		goto edge1
		end if
		
	if look = 14 then
		;right side clock wise
		goto edge1
		end if
		
	if look = 15 then
		;front anti clock wise
		;top anti clock wise
		goto edge1
		end if
		
	;ckeck bottom edges
	if look = 16 then
		;right clock wise
		;right clock wise
		goto edge1
		end if
		
	if look = 17 then
		;right clockwise
		;front anti clockwise
		;top anti clock wise
		goto edge1
		end if
	
	if look = 18 then
		;right clock wise
		;right clock wise
		;top clock wise
		goto edge1
		end if
		
	if look = 19 then
		;back clock wise
		;right anti clock wise
		goto edge1
		end if
		
	if look = 20 then
		;left clock wise
		;left clock wise
		;top clock wise
		;top clock wise
		goto edge1
		end if
		
	if look = 21 then
		;left clock wise
		;backanti clock wise
		;top clock wisw
		goto edge1
		end if
		
	if look = 22 then
		;front clock wise
		;front clock wise
		;top anti clock wise
		goto edge1
		end if
		
	if look = 23 then
		;front anti clock wise
		;right clock wise
		goto edge1
		end if
		
	;in case of over flow run error
		sertxd ("Error")
		end

each move set has to be preceeded with a memory fetch

it would have been ideal to replace all that with

Code:

gosub look       ;run move sequence sub - not writen yet

westaust55 · Mar 3, 2013

I have no idea about solving Rubik's cube although after a Google search there are code and javascript pages out there.
Even article without code) suggesting any Rubiks cube can be solved in <= 20 moves.

Have a look at what I have changed in the attached .bas file using the ON...GOSUB command.
This is doing the same as all your 23 x IF...THEN commands and even comes in 18 bytes smaller.

Assuming all your sub procedures which are currently in as commented lines are correct some further optimisations are then possible to reduce program size.
For example:

change

Code:

;============= SUBROUTINES start here ================

Look00: RETURN ; do nothing

Look01:
		;right side clockwise
		;back clockwise
		;top clockwise
		RETURN

Look02:		
		;top clockwise
		RETURN

to let Look01 fall through into Look02 and save some program space using:

Code:

;============= SUBROUTINES start here ================

Look00: RETURN ; do nothing

Look01:
		;right side clockwise
		;back clockwise

Look02:		
		;top clockwise
		RETURN

Likewise, don't feel the Lookxx have to be in numerical order and move Look10 ahead of Look04 and reduce to:

Code:

Look10:
		;left side clockwise
Look04:
		;top clockwise
		;top clockwise			
		RETURN

Clearly your desired/perceived GOSUB <variable> is not available in PICAXE BASIC but if what I have shown is not what you intend then we, well me at least, need a better explanation

hippy · Mar 3, 2013

oracacle said:
i would have like to store the sub in a variable and then do the following ... gosub b0"

The PICAXE does not support that, what would be called 'function pointers' in other languages. The best you can do is set 'b0' to indicate which function is required and use an ON-GOSUB ( or ON-GOTO ) to reach the desired routine.

Buzby · Mar 3, 2013

I realise now what oracacle is after, I used it many years ago.

It exists in languages where the 'expression engine' is used to parse every place a value could somehow exist.
Old BASICs had line numbers, so the engine kicked-in every time a GOTO LineNumber was seen.
LineNumber could then be an expression, such as GOTO X * 10 + 100, so this would jump to lines 100, 110, 120, etc, when X=0, 1, 2 etc.

( IIRC, QL Basic went one better (?), and allowed string expressions which evaluated to labels. GOSUB "Turn" + "FrontFace" + "Left". ! )

Rev-Ed have worked a miracle getting PICAXE BASIC to do what it does already, I don't think we are likely to see 'computed branching' anytime soon.

oracacle · Mar 4, 2013

westaust55 said:
I have no idea about solving Rubik's cube although after a Google search there are code and javascript pages out there.
Even article without code) suggesting any Rubiks cube can be solved in <= 20 moves.

Have a look at what I have changed in the attached .bas file using the ON...GOSUB command.
This is doing the same as all your 23 x IF...THEN commands and even comes in 18 bytes smaller.

Assuming all your sub procedures which are currently in as commented lines are correct some further optimisations are then possible to reduce program size.
For example:

change

Code:

;============= SUBROUTINES start here ================ Look00: RETURN ; do nothing Look01: ;right side clockwise ;back clockwise ;top clockwise RETURN Look02: ;top clockwise RETURN

to let Look01 fall through into Look02 and save some program space using:

Code:

;============= SUBROUTINES start here ================ Look00: RETURN ; do nothing Look01: ;right side clockwise ;back clockwise Look02: ;top clockwise RETURN

Likewise, don't feel the Lookxx have to be in numerical order and move Look10 ahead of Look04 and reduce to:

Code:

Look10: ;left side clockwise Look04: ;top clockwise ;top clockwise RETURN

Clearly your desired/perceived GOSUB <variable> is not available in PICAXE BASIC but if what I have shown is not what you intend then we, well me at least, need a better explanation

thank you for the modified code, this could work quite well, i think i may have miss-understood when i read the manual.

reading your code in situe made it alot easier to understand. it may allow to "recycle" some of the movement sub-routines

Best way to search many variable

Senior Member

Senior Member

Senior Member

Technical Support

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Moderator

Senior Member

Moderator

Senior Member

Attachments

Moderator

Attachments

Technical Support

Senior Member

Senior Member