// CS 306 - Computer Algorithms II
// Fall 2008
//
// A brute-force solution to the max-sum triangle path problem.

#include <vector>
#include <cassert>
#include <iostream>


typedef std::pair<unsigned, unsigned> coordinate
typedef std::vector<coordinate> path
typedef std::vector<path> path_set


template <typename T>
class triangle_matrix {

  // A minimum-space impelementation of a lower-left triangular matrix.

  public:

    // Return the value stored at the given coordinate in this triangle.

    const T
    get(unsigned row, unsigned col) const {
      return data.at(index(row, col))
      }


    // Store the given value at the given coordinate in this triangle.

    void
    put(unsigned row, unsigned col, T val) {
      data.at(index(row, col)) = val
      }


    // Return the number of rows in this triangle.

    unsigned
    row_count() const {
      return rows
      }


    // Create a new triangle with the given number of rows.  The contents of
    // the triangle are undefined.

    explicit triangle_matrix(unsigned rows)
      : rows(rows), data(gauss(rows)) {
      }

    
  private:

    unsigned rows
    std::vector<T> data

    unsigned
    gauss(unsigned n) const {
      return (n*(n + 1))/2
      }

    unsigned 
    index(unsigned r, unsigned c) const {
      assert ((r < data.size()) and (c ≤ r))
      return gauss(r) + c
      }

  }


class number_triangle {

  // An equilateral triangle full of random integers.

  public:

    // Return the number at the given coordinates in this triangle.

    const int
    get(const coordinate & c) const {
      return data.get(c.first, c.second)
      }



    // Create a triangle with the given number of rows; the triangle contains
    // random integers.

    explicit 
    number_triangle(unsigned size)
      : data(size) {

      const unsigned N = 100

      srandom(getpid())
      for (unsigned r = 0; r < size; r++)
	for (unsigned c = 0; c ≤ r; c++)
	  data.put(r, c, (random() % N) - N/2)
      }


    // Return the number of rows in this triangle.

    unsigned
    row_count() const {
      return data.row_count()
      }
    
  private:

    triangle_matrix<int> data
  }


// Deja vu c++ style.

   static path_set path_move(unsigned, unsigned, unsigned, unsigned)
   static int path_sum(const number_triangle &, const path &)
   static path max_sum_path(const number_triangle &)
   static path max_sum_path_dp(const number_triangle &)
   static std::ostream & operator << (std::ostream &, const coordinate &)
   static std::ostream & operator << (std::ostream &, const path &)


static path_set
all_paths(unsigned row, unsigned col, unsigned N) {

  // Return all possible paths through a sub-triangle with its apex at the
  // given coordinates in a triangle with the given number of rows.

  path_set paths

  if (row + 1 == N) {
    paths.push_back(path())
    paths.back().push_back(coordinate(row, col))
    }

  else {
    const path_set right_paths = path_move(row, col, 1, N)
    paths = path_move(row, col, 0, N)

    std::copy(
      right_paths.begin(), right_paths.end(), std::back_inserter(paths))
    }

  return paths
  }


static path_set
all_paths(const number_triangle & t) {

  // Return all possible paths from the apex to the base in the given triangle.

  return all_paths(0, 0, t.row_count())
  }


int 
main(int argc, char * argv[]) {

  if (argc == 1) {
    std::cerr << "Missing command-line argument.\n"
	      << "Command-line format is \"triangle-size\".\n"
    exit(EXIT_FAILURE)
    }

  const number_triangle t(atoi(argv[1]))

  path msp = max_sum_path(t)

  std::cout << "The max-sum value is " << path_sum(t, msp) << "\n"
  std::cout << "The max-sum path is " << msp << "\n"

  exit(EXIT_SUCCESS)
  }


static path
max_sum_path(const number_triangle & t) {

  // Return a path through the given triangle that has maximum sum.

  path max_path
  const path_set paths = all_paths(t)

  if (not paths.empty()) {
    max_path = paths.front()
    int max_sum = path_sum(t, max_path)

    for (unsigned i = paths.size() - 1; i > 0; i--) {
      const path & p = paths[i]
      const int sum = path_sum(t, p)
      if (sum > max_sum) {
	max_sum = sum
	max_path = p
	}
      }
    }

  return max_path
  }


static path
max_sum_path_dp(const number_triangle & t) {

  // Return a path through the given triangle that has maximum sum.

  const unsigned N = t.row_count()

  if (N == 0)
    return path()

  typedef std::pair<int, path> partial_path

  // table(r, c) is the partial path through the (sub-)triangle with apex 
  // (r,c).

     triangle_matrix<partial_path> table(N)

  // Fill in the bottom row of the table.

     for (unsigned i = 0; i < N; i++) {
       const coordinate apex(N - 1, i)
       partial_path pp(t.get(apex), path())

       pp.second.insert(pp.second.begin(), apex)
       table.put(N - 1, i, pp)
       }
	      
  for (unsigned row = N - 1; row > 0;) {

    const unsigned previous_row = row--

    for (unsigned i = 0; i ≤ row; i++) {

      const coordinate apex(row, i)

      // Set the current apex's partial path to the larger of the partial paths
      // down to the left and down to the right of the current apex.

	 partial_path 
	   left = table.get(previous_row, i),
	   right = table.get(previous_row, i + 1),
	 & choice = left.first > right.first ? left : right,
	   next(choice.first + t.get(apex), choice.second)

      // Add the current apex to the new partial path and store the path in the
      // table.

         next.second.insert(next.second.begin(), apex)
         table.put(row, i, next)
      }
    }

  return table.get(0, 0).second
  }


static std::ostream &
operator << (std::ostream & os, const coordinate & c) {

  // Write the given coordinate to the given output stream; return the stream.

  return os << "(" << c.first << " " << c.second << ")"
  }


static std::ostream &
operator << (std::ostream & os, const path & p) {

  // Write the given path to the given output stream; return the stream.

  os << "["

  // What I want to write next is
  // 
  //   std::copy(p.begin(), p.end(), std::ostream_iterator<coordinate>(os))
  //
  // but debian testing g++ 4.1.3 won't compile that for some reason.

  char * sep = ""
  for (unsigned i = 0; i < p.size(); i++) {
    os << sep << p[i]
    sep = " "
    }

  return os << "]"
  }


static path_set
path_move(unsigned row, unsigned col, unsigned move, unsigned N) {

  // Return all the paths that start at sub-triangle apex with the given
  // coordinates and make the given move from the apex.

  path_set paths = all_paths(row + 1, col + move, N)
  const coordinate apex(row, col)

  for (unsigned i = paths.size(); i > 0;) {
    path & p = paths[--i]
    p.insert(p.begin(), apex)
    }

  return paths
  }


static int
path_sum(const number_triangle & t, const path & p) {

  // Return the path sum for the given path through the given triangle.

  int sum = 0

  for (unsigned i = p.size(); i > 0;)
    sum += t.get(p[--i])

  return sum
  }

// $Log: number-triangle.cc,v $
// Revision 1.3  2007-09-23 15:20:00  rclayton
// Remove some unneeded includes.
//
// Revision 1.2  2007-09-16 22:19:26  rclayton
// Document.
//
// Revision 1.1  2007-09-10 23:04:07  rclayton
// Created.
//