// main.d :


import std.stdio, std.typecons, std.typetuple, std.format,
  std.container, std.algorithm, std.range, std.array;
import core.memory;
import search;

auto genericAbs(T)(T a){ return a > 0 ? a : -a; }

struct State(int N)
{
  byte[N*N] state;
  int estimate;

  auto dist(int a, int b)
  {
    int ai = a/N, aj = a%N;
    int bi = b/N, bj = b%N;
    return genericAbs(ai-bi) + genericAbs(aj-bj);
  }

  void setEstimate()
  {
    auto n = 0;
    foreach(int i,e;state)
      if(e != N*N - 1)
        n += dist(i,e);
    estimate = n;
  }

  struct Actions
  {
    struct  Param
    {
      State!N state;
    }

    State!N _state;
    int opApply( int delegate(ref Param) dg)
    {
      auto pos = countUntil(_state.state[],N*N-1);
      auto i = pos / N, j = pos % N;
      if(j-1>=0)
      {
        auto next = _state;
        swap(next.state[pos],next.state[pos-1]);
        next.setEstimate();
        if(dg(Param(next)))
          return true;
      }
      if(j+1<N)
      {
        auto next = _state;
        swap(next.state[pos],next.state[pos+1]);
        next.setEstimate();
        if(dg(Param(next)))
          return true;
      }
      if(i-1>=0)
      {
        auto next = _state;
        swap(next.state[pos],next.state[pos-N]);
        next.setEstimate();
        if(dg(Param(next)))
          return true;
      }
      if(i+1<N)
      {
        auto next = _state;
        swap(next.state[pos],next.state[pos+N]);
        next.setEstimate();
        if(dg(Param(next)))
          return true;
      }
      return false;
    }
  }

  @property auto actions() { return Actions(this); }

  string toString()
  {
    auto appender = appender!string();
    foreach(i; 0..N)
    {
      foreach(j; 0..N)
        formattedWrite(appender, "%.2d ", (state[i*N+j]+1)%(N*N));
      formattedWrite(appender, "\n");
    }
    return appender.data;
  }
}

void main()
{
  GC.disable();
  enum N = 4;
  State!N state;
  fill(state.state[],map!q{cast(byte)a}(iota(N*N-1,-1,-1)));
  state.setEstimate();

  auto r = searchGraph!q{a.estimate==0}(state);

  writeln(r.states.front);

  foreach(e; r.states[])
    writeln(e);
  writeln(count(r.states[]));
}

// search.d :

module search;

import std.container, std.stdio, std.functional, std.traits;
import util;

auto estimate(T)(T t)
{
  static if(hasMember!(T,"estimate"))
    return t.estimate;
  else
    return 0;
}

auto distance(T)(T t)
{
  static if(hasMember!(T,"distance"))
    return t.distance;
  else
    return 1;
}

auto searchGraph(alias isGoal, State)(State start)
{
  alias typeof(estimate(State.init) +  distance(ForeachType!(typeof(State.actions)).init)) Length;

  struct Path
  {
    SList!State states;
    Length length;
    Length rank;
  }

  auto frontier = GrowableHeap!(Path,q{a.rank > b.rank})(1);
  int[State] explored;

  frontier.insert(Path(SList!State([start]),0,estimate(start)));

  while(!frontier.empty)
  {
    auto best = frontier.front;

    if(unaryFun!isGoal(best.states.front))
      return  best;

    frontier.removeFront();
    if(best.states.front in explored)
      continue;
    explored[best.states.front] = 0;

    foreach(e; best.states.front.actions)
      if(!(e.state in explored))
      {
        auto newlen = best.length + distance(e);
        frontier.insert( Path(cons(e.state, best.states),
          newlen,
          newlen + estimate(e.state)));
      }
  }
  return Path.init;
}

// util.d :


module util;

import std.container, std.functional, std.traits;

auto cons(T)(T head, SList!T tail)
{
  tail.insertFront(head);
  return tail;
}


// bugs prevent growable std.container.BinaryHeap from working so we need this
struct GrowableHeap(T, alias f)
{
  BinaryHeap!(T[],f) heap;
  T[] store;
  alias heap this;
  this(int n)
  {
    assert(n > 0);
    store = new T[n];
    heap = BinaryHeap!(T[],f)(store, 0);
  }
  void insert(T val)
  {
    if(heap.length == store.length)
    {
      auto n = store.length;
      store.length = 2*n;
      heap = BinaryHeap!(T[],f)(store,n);
    }
    heap.insert(val);
  }
}