Chemin parcouru

Bonjour Marsup,

L'algorithme suivant, propose , pour passer du point $(0;0)$ au point $(1789; 2018)$ en 229 étapes, un cheminement qui débute par la séquence $ONOOENNSOOO$ suivie d 'une longue course effrénée vers le Sud et ponctuée par un grand bond en arrière vers le Nord. Ce n'est pas exactement la route que tu as suivie , mais c'est normal, car tu as trouvé original de coder $(1;0)$ par $O$ , alors que j'ai cru bon de faire $(1;0) =E$.
Mes faibles compétences en algorithmique font que j'ai du mal à décrypter ton code, et je ne sais pas si "mon" algorithme est vraiment différent du tien.


Entrer $x$,$y$ ,$n$ ($x,y,n \in\N^*, x,y$ de parités différentes, $(x,y)$ sont les coordonnées de l'objectif, $n$ le nombre d'étapes.)
$i$ prend la valeur $0$.
Tant que $x^2+y^2\neq1$ OU $i<n-1$
$\:\:\:\: $ $a$ prend la valeur ($x\mod2)\times((x+y)\mod4-2)$ ($x\mod k$ désigne le reste de la division euclidienne de $x$ par $k$.)
$\:\:\:\: $ $b$ prend la valeur ($y\mod2) \times((x+y)\mod4-2)$.
$\:\:\:\: $ Afficher $(a, b)$. (en le codant par $O,E,N$ ou $S$.)
$\:\:\:\:$ $ x$ prend la valeur $\frac{x-a}2$.
$\:\:\:\: $ $y$ prend la valeur $\frac{y-b}2$.
$\:\:\:\: $ $ i $ prend la valeur $i+1$.
Fin du Tant que.
Afficher $(x,y)$ ( en le codant par la direction cardinale adéquate).

Si l'on souhaite obtenir l'unique chemin de longueur minimale allant de $(0;0)$ à $(x;y)$, il suffit de supprimer dans le "Tant que" la condition "OU $i<n-1$" ainsi que les lignes "$i$ prend la valeur $0$" et "$i$ prend la valeur $i+1$" qui ne servent plus à rien.
Amicalement.

La version chemin le plus court avec le test en $x^2 + y^2 = 1$ proposé par lou16.

Aussi corrigé l'interversion est $\longleftrightarrow$ ouest.

directions =
{
  e = {dir="x",sens=1},
  o = {dir="x",sens=-1},
  n = {dir="y",sens=1},
  s = {dir="y",sens=-1},
}

function calculerPos(str)
  local pos = { x = 0, y = 0 }
  local l = 1 
  for c in str:gmatch"." do
    local increment = directions[c]
    pos[increment.dir] = pos[increment.dir] + increment.sens * l
    l = l * 2
  end
  return pos
end

helperUn = {[-1]={},[0]={},[1]={}}
for k,v in pairs(directions) do
  local xy=calculerPos(k)
  helperUn[xy.x][xy.y]=k
end

helperDeux = {[0]={},[1]={},[2]={},[3]={}}
for k,v in pairs(directions) do
  for kk,vv in pairs(directions) do
    local xy=calculerPos(k..kk)
    local x,y = (xy.x)%4,(xy.y)%4
    helperDeux[x][y]=k
  end
end

function calculerTraj(x,y,chemin)
  local chemin = chemin or ""
  if x^2 + y^2 == 1 then
    return chemin .. helperUn[x][y]
  else
    local reponse = helperDeux[x%4][y%4]
    local tmp = calculerPos(reponse)
    local nx,ny = (x - tmp.x)/2,(y - tmp.y)/2
    return calculerTraj(nx,ny,chemin..reponse) -- version tail recursive
  end
end

Vérif:

sstr = calculerTraj(1789,2018)
print(sstr) -- eneeonnseeen
pos = calculerPos(sstr)
print(pos.x,pos.y,#sstr) -- 1789	2018	12