// CS 306 - Computer Algorithms II
// Fall 2007
//
// 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.
//