fork(2) download
  1. using System;
  2. using System.Text;
  3.  
  4. namespace Pyramid
  5. {
  6. public class Pyramid
  7. {
  8. private readonly int rows;
  9. private readonly int[,] data;
  10.  
  11. public Pyramid(int[,] data)
  12. {
  13. this.data = data;
  14. rows = data.GetLength(0);
  15. }
  16.  
  17. public Pyramid(int rows)
  18. {
  19. this.rows = rows;
  20. data = new int[rows, rows];
  21. }
  22.  
  23. public int this[int row, int col]
  24. {
  25. get { return data[row, col]; }
  26. set { data[row, col] = value; }
  27. }
  28.  
  29. public int Rows
  30. {
  31. get { return rows; }
  32. }
  33.  
  34. public override string ToString()
  35. {
  36. var sb = new StringBuilder();
  37.  
  38. for (int row = 0; row < rows; row++)
  39. {
  40. sb.Append(new string(' ', 9 * row / 2));
  41. for (int col = 0; col < rows - row; col++)
  42. {
  43. sb.AppendFormat("[{0:00000}] ", data[row, col]);
  44. }
  45. sb.AppendLine();
  46. }
  47.  
  48. return sb.ToString();
  49. }
  50. }
  51.  
  52. public interface IPyramidGenerator
  53. {
  54. Pyramid GeneratePyramid();
  55. }
  56.  
  57. public class RandomPyramidGenerator : IPyramidGenerator
  58. {
  59. private readonly int rows;
  60. private readonly int range;
  61. private readonly Random random;
  62.  
  63. public RandomPyramidGenerator(int rows, int range)
  64. {
  65. this.rows = rows;
  66. this.range = range;
  67. random = new Random();
  68. }
  69.  
  70. public Pyramid GeneratePyramid()
  71. {
  72. var pyramid = new Pyramid(rows);
  73. for (int row = 0; row < rows; row++)
  74. {
  75. for (int col = 0; col < rows - row; col++)
  76. {
  77. pyramid[row, col] = random.Next(1, range);
  78. }
  79. }
  80. return pyramid;
  81. }
  82. }
  83.  
  84. public interface IPyramidSolver
  85. {
  86. long PyramidMaximumTotal(Pyramid pyramid);
  87. }
  88.  
  89. // There is something wrong here. A few things actually...
  90. public class NaivePyramidSolver : IPyramidSolver //...........................
  91. {
  92. public long PyramidMaximumTotal(Pyramid pyramid)
  93. {
  94. return GetTotalAbove(pyramid.Rows - 1, 0, pyramid);
  95. }
  96.  
  97. private long GetTotalAbove(int row, int column, Pyramid pyramid)
  98. {
  99. if (row == 0) return 0;
  100.  
  101. int myValue = pyramid[row, column];
  102. long left = myValue + GetTotalAbove(row - 1, column, pyramid);
  103. long right = myValue + GetTotalAbove(row - 1, column + 1, pyramid);
  104. return Math.Max(left, right);
  105. }
  106. }
  107.  
  108.  
  109. public class OurProgram
  110. {
  111. private static void Main()
  112. {
  113. // this is doesn't get correct number
  114. var generator = new RandomPyramidGenerator(5, 99);
  115. Pyramid pyramid = generator.GeneratePyramid();
  116. Console.WriteLine(pyramid);
  117.  
  118. var solver = new NaivePyramidSolver();
  119.  
  120. Console.WriteLine("This result is wrong, do you know why ?");
  121. Console.WriteLine(solver.PyramidMaximumTotal(pyramid));
  122.  
  123.  
  124. Console.ReadLine();
  125. }
  126. }
  127. }
Success #stdin #stdout 0.03s 36976KB
stdin
Standard input is empty
stdout
[00024] [00014] [00012] [00077] [00079] 
    [00035] [00095] [00057] [00058] 
         [00022] [00081] [00052] 
             [00039] [00097] 
                  [00069] 

This result is wrong, do you know why ?
342