#!/bin/sh

# prog.sh  (Fibonacci-Nim game)
# permet de déterminer les coups à jouer dans le jeu de Fibonacci-Nim
# en construisant une image (fractale) des coups possibles à tout moment
# lorsque le nombre d'allumettes du tas est inférieur ou égal à N
#
# ( avril 2003 Jean-Paul Davalan jpdvl@wanadoo.fr )

# nécessite gawk (ou awk, dans ce cas modifier ci-dessous) 
AWK=gawk

# gnuplot 
# pstoimg  (fichier perl de la distribution de latex2html)

# Nombre maximum de pions (ou d'allumettes) du tas au moment de jouer

N=400

echo ""| $AWK -v N=$N '
function val(a, b,    u,i,m,k) {
  if(a==0) {
    t[a, b]=0
    return 0;
  }
  if(t[a, b] != "") return t[a, b];
  u=b;
  if(u>a) u=a;
  for(i=1;i<=u;i++) {
    k = val(a-i, 2*i);
    m[k] = 1;
  }
  k=0;
  while(m[k]==1) k++;
  t[a, b] = k;
  delete m;
  return k;
}
function p2c( k,r,g) {
  # mise en forme
  for(k=N;k>=1;k--) {
    for(r=1;2*r<k;r++) {
      g=val(k,2*r)
      if(g==0) {
        #print k+r " --> " k
        # on arrive en k en venant de k+r
        tk[ k+r, k] = 1;
      }
    }
  }
  for(k=1;k<=N;k++) {
    s="";
    for(r=1;r<k;r++) {
      if(tk[ k, r] == 1) print k"  "r;
    }
  }
}
END {
  if(N=="") N=400
  p2c();
} ' >pts4.g


echo 'set terminal postscript eps color "TimesNewRoman" 12;set output "fig4.eps"; set nokey;set grid;plot "pts4.g" with points,x with lines'|gnuplot

pstoimg -antialias -aaliastext -scale 1.3 -type png -o fig4.png fig4.eps