forummsgid133749edit
Original date:20190414 08:01:15 Edited by: petelomax Subject: Wraparound search algorithm
This proved far harder than I ever imagined possible, any improvements welcome.
The following is a simplified testbed.
First simplification: text is "0000".."1111" and "find" is whether or not text[1..4] is '1'.
Second simplification: we set "start" explicitly in the testing loop, maybe unlike real use.
(Technically we shouldn't need to reset wrappable in this testbed, but abs. rqd. in real use)
Starting from 1..4, with N=sum of 1s, we want f3find() to get N/eof/N/eof, iyswim.
The challenge is(was) to get all 64 test cases to work, then repeat searching backwards.
Anyway, a second set of eyes, before I try applying this to Edix/Edita, anything that simplifies it or makes it any easier to understand, or OEcompatible, thankx.
sequence text integer start, current, wrappable = 1 function f3find(integer direction)   direction should be +/1. [existing code uses 0 to mean "from line 1"]  return "next/prev" '1' in text, wrapping around relative to start.  return 1 at "eof", aka "start", allowing restart.  integer limit = iff(direction<0?1:length(text)), begin = iff(direction>0?1:length(text)) current += direction bool low = compare(start,current)=direction or not wrappable limit = iff(low ? start(wrappable=0)*direction : limit) for i=current to limit by direction do if text[i]='1' then current=i return i end if end for if wrappable and compare(start,current)!=direction then wrappable = 0 limit = startdirection for i=begin to limit by direction do if text[i]='1' then current=i return i end if end for end if current = startdirection wrappable = 1 return 1 end function constant TRIES=4 integer fails = 0, total = 0 for i=0 to 15 do text = sprintf("%04b",i) integer N = sum(sq_eq(text,'1')) ?{text,N} for direction=+1 to 1 by 2 do for j=1 to 4 do start = j current = jdirection wrappable = 1 sequence s = {} for t=1 to (N+1)*TRIES do s &= f3find(direction) end for total += 1 if s[$]!=1 or sum(sq_eq(s,1))!=TRIES then s &= {"9/0"} fails += 1 ?{"s=",s} end if  ?s end for end for end for printf(1,"fails: %d, pass: %d/%d\n",{fails,totalfails,total})
output:
{"0000",0} {"0001",1} {"0010",1} {"0011",2} {"0100",1} {"0101",2} {"0110",2} {"0111",3} {"1000",1} {"1001",2} {"1010",2} {"1011",3} {"1100",2} {"1101",3} {"1110",3} {"1111",4} fails: 0, pass: 128/128
Not Categorized, Please Help
