function [U,w,MU] = pt_scratch(M)

alf = M.ALF;


if 1
  SS = simpathcover(M);
  SS = char(SS);
  ell = size(SS,2);
  [SS,Y] = reglang_posneg_dense(0,ell,M);
  SS = lensort(SS);
else
  X0 = simple_paths(M);
  SS = lensort(X0);
end

%Ms = {};
%for i=1:length(SS)
%  Ms{i} = str2M(M,SS{i},SS{i});
%end

U = {};
MU = {};
w = [];

w(1) = b2y(run_dfsa(M,''));
U{1} = '';
%MU{1} = bool2fsa_pt(['(@)'],alf);
MU{1} = shuf2dfsa('',alf);

DONE = {};
STIL = {};
DONE{1} = SS{1};
STIL = SS(2:end);
while ~isempty(STIL)
  x = STIL{1};
  [U,w,MU,b] = add_feature(U,w,MU,M,x);
  if ~b
    if 0
      Dx = repmat({x},[length(DONE), 1]);
      Dx = [char(DONE) char(Dx)];
      DX = cellstr(Dx);
      for i=1:length(DX)
      DX{i} = strrep(DX{i},' ','');
      end
      STIL = [STIL; DX];
    end
    if 0
      Mx = MU{end};
      for i=1:length(SS)
        Msx = intersect_dfsa(Mx,Ms{i});
        [b,str] = accept_str(Msx);
        if b
          STIL{end+1}=str;
        end
      end
    end
    %for i=1:length(SS)
    %  Sx = shuff2(x,SS{i});
    %  STIL = [STIL; Sx(:)];
    %end
    for i=1:length(U)
      Ux = shuff2(x,U{i});
      STIL = [STIL; Ux(:)];
    end
  end
  DONE{end+1} = x;
  STIL = STIL(2:end);
  STIL = unique(STIL);
  STIL = lensort(STIL);
  fprintf('%d strings left \n',length(STIL));
end

return

function X1 = lensort(X)
LL = zeros(size(X));
for i=1:length(X)
  LL(i) = length(X{i});
end
X1 = [];
for l=0:max(LL)
  ii = find(LL==l);
  Xii = sort(X(ii));
  X1 = [X1; Xii(:)];
end
return

function [U,w,MU,b] = add_feature(U,w,MU,M,x)
xi = embedX(x,MU);
yh = sign(xi*w);
yt = b2y(run_dfsa(M,x));
b = (yh == yt);
if ~b
  % signs disagree
  N = length(U)+1;
  U{N,1} = x;
  fprintf('processing x = %s \n',x);
  %MU{N,1} = bool2fsa_pt(['(' x ')'],M.ALF);
  MU{N,1} = shuf2dfsa(x,M.ALF);
  w(N,1) = yt * (1+abs(xi*w));
end
return

function xi = embedX(x,MU)
xi = zeros(1,length(MU));
for i=1:length(xi)
  xi(1,i) = run_dfsa(MU{i},x);
end
return


function R = spath2cell(M,s)
R = {};
A = ['@' selfloops(M,M.q0)];
R{end+1} = A;
q = M.q0;
for i=1:length(s)
  s1 = s(i);
  R{end+1} = s1;
  q = dfsa_delta(M,q,s1);
  A = ['@' selfloops(M,q)];
  R{end+1} = A;
end
return


function S = all_subseq(s)
if isempty(s)
  S = {''};
else
  n = length(s);
  POWSET = list_all_ind(repmat([2],[n 1]))-1;
  S = repmat({s},size(POWSET,1),1);
  for j = 1:length(S)
    S{j} = s(find(POWSET(j,:)));
  end
  S = unique(S);
end
return


function [Xii,Yii,aa] = pt_scratch00(M)


X = getsample(M);
bb = run_dfsa_cell(M,X(:));
Y = 2*bb-1;

good = 0;
alpha = zeros(size(Y));
while ~good
  alpha = votedperceptron_mycell(X,Y,1,@ptker2,alpha);  
  ii = find(alpha);
  Xii = X(ii);
  Yii = Y(ii);
  aa = alpha(ii).*Yii;
  y_hat = compute_yhat_c(Xii,X,aa,0,@ptker2);
  
  nerr = length(find(y_hat~=Y))
  good = ~nerr;
end


ii = find(alpha);
Xii = X(ii);
Yii = Y(ii);
aa = alpha(ii).*Yii;

return


function LSEQ = str2Lseq(M0,s)
LSEQ = {};
A = selfloops(M0,M0.q0);
R = '';
if ~isempty(A)
  %R = [R setstar(A)];
  A(end+1) = '@';
  LSEQ{end+1} = A;
end
if ~isempty(s)
  q = M0.q0;
  for i=1:length(s)
    s1 = s(i);
    LSEQ{end+1} = s1;
    q = dfsa_delta(M0,q,s1);
    A = selfloops(M0,q);
    if ~isempty(A)
      R = [R setstar(A)];
      A(end+1) = '@';
      LSEQ{end+1} = A;
    end
  end
end
return



function X = getsample(M)

SP = simple_paths(M);
%[X,w] = explicit_uw_pt(SP,zeros(size(SP)));
%return


ns = length(SP);
X = {};

for i=1:ns
  u = SP{i};
  if isempty(u)
    X = [X;{u}];
  else
    LSEQ = str2Lseq(M,u);
    ss = list_all_ind_g(LSEQ);
    ss = cellstr(ss);
    for j=1:length(ss)
      ss{j} = strrep(ss{j},'@','');
    end
    X = [X;ss];
  end
end

cx = char(X);
L = size(cx,2);
[X,Y] = reglang_posneg_dense(0,L,M);

%[X,bla] = explicit_uw_pt(X,zeros(size(X)));

return

[U,w] = explicit_uw_pt(SP,zeros(size(SP)));

ns = length(SP);
nu = length(U);

MM = {};
for i=1:ns
  MS{i} = Phi(M,SP{i});
end

MU = {};
for i=1:nu
  ui = U{i};
  if isempty(ui)
    ui = '@';
  end
  fprintf('processing U = %s \n',ui);
  MU{i} = bool2fsa_pt(['(' ui ')'],M.ALF);
end



X = {};

    try

PROGstart(ns*nu,'generating sample');
cnt = 0;
for is = 1:ns
  for iu = 1:nu
      Msu = intersect_dfsa(MS{is},MU{iu});
      [b,str] = accept_str(Msu);
    if b
      X{end+1} = str;
    end
  end
  cnt = cnt + 1;
  PROGupdate(cnt);
end
PROGend;

    catch
      keyboard
    end


X = unique(X);


return




function Ms = Phi(M,s)
% Ms is the regular (pt) language
%% $\Phi(s) = \bigcup_{z\in\path_L\inv(s)} \{u: u\subseq z\} $
% no, it's just \path\inv(s)

Ms = str2M(M,s,s);

return

Ms = null_dfsa(M.ALF);

N = length(s);
for i=1:2^N
  setstr = dec2bin(i-1,N);
  ii0 = find(setstr=='0');
  si = s;
  si(ii0) = repmat('@',1,length(ii0));
  Mi = str2M(M,si,s);
  Ms = union_dfsa(Ms,Mi);
end
return


function A = selfloops(DFSA,q)
%[pp,nss] = find(DFSA.delta==q);
%ii = find(pp==q);
%A = DFSA.ALF(nss(ii));
A = alltrans(DFSA,q,q);
return

function A = alltrans(DFSA,q0,q1)
% all the letters that take q0 to q1
[pp,nss] = find(DFSA.delta==q1);
ii = find(pp==q0);
A = DFSA.ALF(nss(ii));
return


function M = str2M(M0,s,s00)
A = selfloops(M0,M0.q0);
R = '';
if ~isempty(A)
  R = [R setstar(A)];
end
if ~isempty(s)
  q = M0.q0;
  for i=1:length(s)
    s1 = s(i);
    if s1~='@'
      R = [R s1];
      q = dfsa_delta(M0,q,s1);
    else
      q = dfsa_delta(M0,q,s00(i));
    end
    A = selfloops(M0,q);
    if ~isempty(A)
      R = [R setstar(A)];
    end
  end
end
M = gregexp2dfsa_fast(R,M0.ALF);
return


function M = unions(MM,alf)
M = null_dfsa(alf);
for i=1:length(MM)
  M = union_dfsa(M,MM{i});
end
%M = remove_unreachable(M);
%M = minimize_dfsa(M);
return