Maximum triangle path sum: Difference between revisions

Content added Content deleted
m (added comments)
m (→‎{{header|Phix}}: added syntax colouring, marked p2js compatible)
Line 2,144: Line 2,144:


=={{header|Phix}}==
=={{header|Phix}}==
<lang Phix>sequence tri = {{55},
<!--<lang Phix>(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
{94, 48},
<span style="color: #004080;">sequence</span> <span style="color: #000000;">tri</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">55</span><span style="color: #0000FF;">},</span>
{95, 30, 96},
<span style="color: #0000FF;">{</span><span style="color: #000000;">94</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">48</span><span style="color: #0000FF;">},</span>
{77, 71, 26, 67},
<span style="color: #0000FF;">{</span><span style="color: #000000;">95</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">30</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">96</span><span style="color: #0000FF;">},</span>
{97, 13, 76, 38, 45},
<span style="color: #0000FF;">{</span><span style="color: #000000;">77</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">71</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">26</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">67</span><span style="color: #0000FF;">},</span>
{ 7, 36, 79, 16, 37, 68},
<span style="color: #0000FF;">{</span><span style="color: #000000;">97</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">13</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">76</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">38</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">45</span><span style="color: #0000FF;">},</span>
{48, 7, 9, 18, 70, 26, 6},
<span style="color: #0000FF;">{</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">36</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">79</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">16</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">37</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">68</span><span style="color: #0000FF;">},</span>
{18, 72, 79, 46, 59, 79, 29, 90},
<span style="color: #0000FF;">{</span><span style="color: #000000;">48</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">18</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">70</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">26</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">},</span>
{20, 76, 87, 11, 32, 7, 7, 49, 18},
<span style="color: #0000FF;">{</span><span style="color: #000000;">18</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">72</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">79</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">46</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">59</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">79</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">29</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">90</span><span style="color: #0000FF;">},</span>
{27, 83, 58, 35, 71, 11, 25, 57, 29, 85},
<span style="color: #0000FF;">{</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">76</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">87</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">32</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">49</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">18</span><span style="color: #0000FF;">},</span>
{14, 64, 36, 96, 27, 11, 58, 56, 92, 18, 55},
<span style="color: #0000FF;">{</span><span style="color: #000000;">27</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">83</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">58</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">35</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">71</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">25</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">57</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">29</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">85</span><span style="color: #0000FF;">},</span>
{ 2, 90, 3, 60, 48, 49, 41, 46, 33, 36, 47, 23},
<span style="color: #0000FF;">{</span><span style="color: #000000;">14</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">64</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">36</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">96</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">27</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">58</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">56</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">92</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">18</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">55</span><span style="color: #0000FF;">},</span>
{92, 50, 48, 2, 36, 59, 42, 79, 72, 20, 82, 77, 42},
<span style="color: #0000FF;">{</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">90</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">60</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">48</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">49</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">41</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">46</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">33</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">36</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">47</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">23</span><span style="color: #0000FF;">},</span>
{56, 78, 38, 80, 39, 75, 2, 71, 66, 66, 1, 3, 55, 72},
<span style="color: #0000FF;">{</span><span style="color: #000000;">92</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">50</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">48</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">36</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">59</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">42</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">79</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">72</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">20</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">82</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">77</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">42</span><span style="color: #0000FF;">},</span>
{44, 25, 67, 84, 71, 67, 11, 61, 40, 57, 58, 89, 40, 56, 36},
<span style="color: #0000FF;">{</span><span style="color: #000000;">56</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">78</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">38</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">80</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">39</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">75</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">71</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">66</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">66</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">55</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">72</span><span style="color: #0000FF;">},</span>
{85, 32, 25, 85, 57, 48, 84, 35, 47, 62, 17, 1, 1, 99, 89, 52},
<span style="color: #0000FF;">{</span><span style="color: #000000;">44</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">25</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">67</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">84</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">71</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">67</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">61</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">40</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">57</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">58</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">89</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">40</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">56</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">36</span><span style="color: #0000FF;">},</span>
{ 6, 71, 28, 75, 94, 48, 37, 10, 23, 51, 6, 48, 53, 18, 74, 98, 15},
<span style="color: #0000FF;">{</span><span style="color: #000000;">85</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">32</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">25</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">85</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">57</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">48</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">84</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">35</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">47</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">62</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">17</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">99</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">89</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">52</span><span style="color: #0000FF;">},</span>
{27, 2, 92, 23, 8, 71, 76, 84, 15, 52, 92, 63, 81, 10, 44, 10, 69, 93}}
<span style="color: #0000FF;">{</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">71</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">28</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">75</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">94</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">48</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">37</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">23</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">51</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">48</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">53</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">18</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">74</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">98</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">15</span><span style="color: #0000FF;">},</span>

<span style="color: #0000FF;">{</span><span style="color: #000000;">27</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">92</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">23</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">71</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">76</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">84</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">15</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">52</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">92</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">63</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">81</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">44</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">69</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">93</span><span style="color: #0000FF;">}}</span>
⚫
-- update each row from last but one upwards, with the larger
⚫
-- child, so the first step is to replace 6 with 6+27 or 6+2.
⚫
<span style="color: #000080;font-style:italic;">-- update each row from last but one upwards, with the larger
for r=length(tri)-1 to 1 by -1 do
⚫
-- child, so the first step is to replace 6 with 6+27 or 6+2.</span>
for c=1 to length(tri[r]) do
<span style="color: #008080;">for</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tri</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
tri[r][c] += max(tri[r+1][c..c+1])
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tri</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
end for
<span style="color: #000000;">tri</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tri</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">..</span><span style="color: #000000;">c</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
?tri[1][1]</lang>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">tri</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<!--</lang>-->
{{out}}
{{out}}
<pre>
<pre>
Retrieved from "https://rosettacode.org/wiki/Maximum_triangle_path_sum"