Equation or not?

[DrD]

I would like to find a simple way to test whether a provided sentence is an equation or an inequality. Specifically, I need to extract only the equations from a list of relations provided as string objects.

For example:

L0:={"x+y=1","2x+2y<2","3x+3y<=3","4x+4y≤4","5x+5y>5","6x+6y>=6","7x+7y≥7","8x+8y<>8",9x+9y≠9"};
L1:={"=","<","<=","≤",">",">=","≥","<>","≠"};

L0(1) is a desired sentence. (It may be one among many, or located elsewhere in any given list, etc.).

L1 is a list of the relational operators that might show up in a provided list, so ONLY sentences that contain a stand alone "=" must be detected.

Any thoughts on a reasonably concise way to do this?

[Han]

This program returns the index (in L0) of the formula having only = as the "comparison" operator. You can easily change it to p(0):=L0(j); rather than p(0):=j; Note that we are assuming the strings are validly formed inequalities/equalities.

PHP Code:

export findeq()
begin

local j,k,n,m,p;

L0:={"x+y=1","2x+2y<2","3x+3y<=3","4x+4y≤4","5x+5y>5","6x+6y>=6","7x+7y≥7","8x+8y<>8","9x+9y≠9"};
L1:={"<","<=","≤",">",">=","≥","<>","≠"}; // note the removal of "="

m:=size(L0);
n:=size(L1);
p:={};

for j from 1 to m do
  for k from 1 to n do
    // if one of the other comparisons is found, skip to next equation
    if instring(L0(j),L1(k)) then continue(2); end;
  end;
  // now check for = symbol
  if instring(L0(j),"=") then p(0):=j; end;
end;

return(p);

end; 


[DrD]

Thanks, Han! Nice composition. I haven't used CONTINUE [n]; before. So doubly appreciate the tip.

-Dale-

[Han]

You can speed it up a little bit by only keeping the one-symbol comparison operators in L1.

L1:={"<","≤",">","≥","≠"};

The "<" check will also exclude "<=" as well (and similarly for the the other two-symbol operators).

[Didier Lachieze]

Another way to do it with this one liner using list processing:

PHP Code:

remove(0,IFTE(ΣLIST(EXECON("INSTRING(L0,&1)",L1))+NOT(INSTRING(L0,"=")),0,L0)) 


Likely slower than the for loops.

[EdDereDdE]

In fact you need only to check for
a) presence of "=" and then
b) exclusion of the special cases ">=", "=>", "<=", "=<"

This function is pretty fast, as it removes most "useless" elements on the first step, even if you got a mega long list at first.
Neither explicit, interpreted loops nor sigma, etc. required either

Please be aware of the CAS("") enclosure ...
Note: implicit engine loops (here in the "remove") are always faster than interpreted "for ..." loops, aren't they?

EXPORT getEq(el)
BEGIN
LOCAL eq:="=",ls:="<",gt:=">";
RETURN CAS("
remove((x)→((INSTRING(x,gt))),
remove((x)→((INSTRING(x,ls))),
remove((x)→(0==(INSTRING(x,eq))),el)
))
");
END;

[Didier Lachieze]

Nice solution but not the fastest one....

(02-24-2017 11:34 PM)EdDereDdE Wrote:  Note: implicit engine loops (here in the "remove") are always faster than interpreted "for ..." loops, aren't they?

Not always, in this case function calls between CAS (remove) and Home (INSTRING) bring some penalty.

I've compared on my physical Prime the three solutions and here is the average execution time for 20 runs of each function:

findeq (Han): 0.0058_s
findEq (Didier): 0.0121_s
getEq (EdDereDdE): 0.0155_s

Here is how I did the measurements :

• type TEVAL with the function name, e.g. TEVAL(findeq)
• press Enter 20 times to get 20 results
• type: MAKELIST(Ans(I),I,1,20)/1_s▶D1 to store the 20 results in Stat_1Var D1
• do the same for the other functions, TEVAL(findEq) and TEVAL(getEq(L0)) and store the results in D2 and D3
• open the Stat_1Var app, select D2 and D3 in Symbol view, go to Num view and press Stats to see the mean values

[DrD]

Thanks for the really clever solution approaches, folks. I had a couple of different ideas, but both used a much longer branching tree, and I wasn't happy with the length of the resulting program. I was confident there would be better ways, and I very much appreciate your contributions!

-Dale-

[Arno K]

Better late than never, I thought there must be another way to get that done using the cas:

PHP Code:

EXPORT findeq2()
BEGIN
local j,m;

L0:={"x+y=1","2x+2y<2","3x+3y<=3","4x+4y≤4","5x+5y>5","6x+6y>=6","7x+7y≥7","8x+8y<>8","9x+9y≠9"};
m:=size(L0);
for j from 1 to m do
L0(j):=CAS.expr(L0(j));
//use L9(j):= CAS.expr(L0(j)) to see the results and below here L9(j), too
IF (CAS.part(L0(j),0) == "==") 
THEN return j; 
END;
end;
END; 


Notice, only 1 loop which is exited when the equal sign, transformed to == by the CAS-call, is found. I think that must be faster but cannot reproduce that timing procedure as TEVAL(findeq2()) returns 0.
Here some other "inconsistence" of the cas is found: the last 2 members of the list are transformed to 1 even as the cas does not know anything about x and y and the other inequalities are turned (I dare writing that) from left to right.
Arno

[Han]

(02-28-2017 10:32 PM)Arno K Wrote:  Better late than never, I thought there must be another way to get that done using the cas:

PHP Code:

EXPORT findeq2()
BEGIN
local j,m;

L0:={"x+y=1","2x+2y<2","3x+3y<=3","4x+4y≤4","5x+5y>5","6x+6y>=6","7x+7y≥7","8x+8y<>8","9x+9y≠9"};
m:=size(L0);
for j from 1 to m do
L0(j):=CAS.expr(L0(j));
//use L9(j):= CAS.expr(L0(j)) to see the results and below here L9(j), too
IF (CAS.part(L0(j),0) == "==") 
THEN return j; 
END;
end;
END; 


Notice, only 1 loop which is exited when the equal sign, transformed to == by the CAS-call, is found. I think that must be faster but cannot reproduce that timing procedure as TEVAL(findeq2()) returns 0.
Here some other "inconsistence" of the cas is found: the last 2 members of the list are transformed to 1 even as the cas does not know anything about x and y and the other inequalities are turned (I dare writing that) from left to right.
Arno

findeq2() seems to exit before it scans the entire list. If there is more than one equation, it only returns the first equation.

Also, getEq() and findeq2() do not return the same results in CAS view.

[Arno K]

Ah, now I see, continue(2) continues the outer loop, so it finds more than one occurance of "=", but that is easily done:

PHP Code:

EXPORT findeq()
BEGIN
local m,p,j;
L0:={"x+y=1","2x+2y<2","3x+3y=3","4x+4y≤4","5x+5y>5","6x+6y>=6","7x+7y≥7","8x+8y<>8","9x+9y≠9"};
m:=size(L0);
p:={};

for j from 1 to m do

L0(j):=CAS.expr(L0(j));
IF (CAS.part(L0(j),0) == "==") THEN p:= CAS.Concat(p,j);END;

end;

return(p);


END; 


so now it returns the same list.
Arno

[Han]

I took the liberty of optimizing some of the programs above where I could. Basically, first three test whether or not to exclude <= and >= when searching for =. As EdDereDdE pointed out, these are really the only tests that are necessary. The last program converts all the equations, which can be time consuming when searching through a large list. The were renamed findeq, findeq2, findeq3, and findeq4 in the order that they were posted.

To test (even on the emulator), type: fetime(3000)

This will create a random list in L0 of size 3000 (you will need large lists to test on the emulator). Then each program is timed in the same manner. Use a smaller value on the actual calculator (e.g. 100)

Here is the "test kit":

PHP Code:

export randL0(k)
begin
  local j, n, m;
  local ineq:={ "=", "<", ">", "<=", ">=", "<>", "≠", "≤", "≥" };
  L0:={};

  for j from 1 to k do
    n:=ip(random*9)+1;
    m:=string(ip(random*9)+1,1,0);
    L0(0):=m + "x + " + m + "y" + ineq(n) + m; 
  end; 
end;

// *********************************
export findeq()
begin

local j,m,p;

m:=size(L0);
p:={};

for j from 1 to m do
  if instring(L0(j),">") OR instring(L0(j),"<") then continue; end;
  // now check for = symbol
  if instring(L0(j),"=") then p(0):=j; end;
end;

return(p);

end; 

// *********************************
export findeq2()
begin
L1:={"<",">"};
remove(0,IFTE(ΣLIST(EXECON("INSTRING(L0,&1)",L1))+NOT(INSTRING(L0,"=")),0,L0));
end;

// *********************************
export findeq3()
begin
LOCAL eq:="=",ls:="<",gt:=">";
RETURN CAS("
remove((x)→((INSTRING(x,gt))),
remove((x)→((INSTRING(x,ls))),
remove((x)→(0==(INSTRING(x,eq))),L0)
))
");
end;

// *********************************
EXPORT findeq4()
BEGIN
local m,p,j;

m:=size(L0);
p:={};

for j from 1 to m do

L0(j):=CAS.expr(L0(j));
IF (CAS.part(L0(j),0) == "==") THEN p:= CAS.Concat(p,j);END;

end;

return(p);

END; 

// *********************************
export fetime(k)
begin
  local t1, t2, t3, t4;
  randL0(k);

  // some programs modify L0
  L9:=L0;
  t1:=teval(findeq());

  L0:=L9;
  t2:=teval(findeq2());

  L0:=L9;
  t3:=teval(findeq3());

  L0:=L9;
  t4:=teval(findeq4());

  return({t1,t2,t3,t4});
end; 


[Arno K]

Wow, I had not thought that CAS-commands are that slow.
Arno

[Han]

It looks like converting strings into expressions is quite CPU intensive (relatively speaking)

[parisse]

That's why it is much better to program with expressions directly instead of strings. And checking that an expression is an inequation or equation is safer and more efficient than for a string.

[DrD]

Using strings, with the associated cost of increased processing time, may become a necessary penalty; because, while it would be desirable to program directly with equations or inequalities, the CAS system evaluates these relations, also the results of inequalities may not be as expected.

For simple program routines, this isn't much of a problem. Larger programs, involving user input or interaction can become quite frustrating. This frustration points out that the hp prime, currently, isn't well suited for this type of program application. (Not the target market). However, the prime has so many desirable attributes, it begs even a novice to attempt to create such larger programs, in spite of the difficulties!