Skip to content
View in the app

A better way to browse. Learn more.

Web Designer Forum

A full-screen app on your home screen with push notifications, badges and more.

To install this app on iOS and iPadOS
  1. Tap the Share icon in Safari
  2. Scroll the menu and tap Add to Home Screen.
  3. Tap Add in the top-right corner.
To install this app on Android
  1. Tap the 3-dot menu (⋮) in the top-right corner of the browser.
  2. Tap Add to Home screen or Install app.
  3. Confirm by tapping Install.

WDF Coding challenge #3

Featured Replies

WDF coding challenge #3

 

Pascal's Triangle Challenge

 

Write a web application to compute the value of a given position in Pascal's Triangle (See below).

 

   1
  1 1
 1 2 1
1 3 3 1
1 4 6 4 1

 

The way to compute any given position's value is to add up the numbers to the position's right and left in the preceding row. For instance, to compute the middle number in the third row, you add 1 and 1; the sides of the triangle are always 1 because you only add the number to the upper left or the upper right (there being no second number on the other side).

 

The application should prompt the user to input a row and a position in the row. The application should ensure that the input is valid before computing a value for the position.

 

Closing Date

Monday 27th June 22:00 UTC

 

Difficulty

unknown

 

Entry

Please post a link of your application working here then paste code up here after the closing date.

 

Rules

1 - Any coding style can be used, linear, procedural, OOP, event driven, whatever you want.

2 - You may NOT use any 3rd party component, library, framework, etc. however SPL is permitted.

3 - No cheating, post here for help or start a new topic.

 

Credits

This challenge was chosen by Geeks.

Ah yes, really enjoy solving problems like this. However PHP and recursion don't tend to go well together, so it starts to fall over if you go much further below row 30.

 

http://markdessain.com/labs/php/challenge/WDF3/

 

(Often in challenges they set a max value which the inputs can be, is there one? e.g. row input between 1 and 20)

  • Author

Ah yes, really enjoy solving problems like this. However PHP and recursion don't tend to go well together, so it starts to fall over if you go much further below row 30.

 

http://markdessain.com/labs/php/challenge/WDF3/

 

(Often in challenges they set a max value which the inputs can be, is there one? e.g. row input between 1 and 20)

 

excellent work!

 

I don't think it matters about min and max values, in theory if your code can correctly lookup 1 row it should technically be able to look up any row. I just tried col 250 row 500 on my code, the number was 58372157894138841460467367381088309829615040590155723062050142478905556336804236857833208887760802688405432951354994790080018734113196950021398436128 :blink:

excellent work!

 

I don't think it matters about min and max values, in theory if your code can correctly lookup 1 row it should technically be able to look up any row. I just tried col 250 row 500 on my code, the number was 58372157894138841460467367381088309829615040590155723062050142478905556336804236857833208887760802688405432951354994790080018734113196950021398436128 :blink:

Bit excessive ;)

Fixed the issues I was having, missed something out which meant it had to do a lot of unnecessary computation. There are slight differences in precision due to floating point, once the number start to get rather large though.

Edited by markeh

Please post a link of your application working here then paste code up here after the closing date.

 

... we should be posting our source now right?

  • Author

Time to post code!

 

My code... not particularly interesting!

 

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
     "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">
   <head>
       <title>Pascal's triangle position calculator</title>
   </head>

   <body>
       <form method="post">
           <label for="row">Row</label>
           <select name="row" id="row">
               <?php
                   for($x = 1; $x < 500; $x++) {
                       echo '<option value="'.$x.'">Row '.$x.'</option>'."\n";
                   }
               ?>
           </select>
           <label for="col">Column</label>
           <select name="col" id="col">
               <option value="1">1</option>
           </select>
           <input type="submit" name="btnSubmit" value="Calculate" />
       </form>
       <p>
           <?php
           if($_SERVER['REQUEST_METHOD'] == 'POST') {

               $row = filter_input(INPUT_POST, 'row', FILTER_VALIDATE_INT, array('options' => array('min_range' => 1, 'max_range' => 500)));

               if($row !== false) {
                   $col = filter_input(INPUT_POST, 'col', FILTER_VALIDATE_INT, array('options' => array('min_range' => 1, 'max_range' => $row)));

                   if($col !== false) {
                       function pascal($row, $column) {
                           for($x=1,$p = array(array($x)); $x<=$row; $x++) {
                               for($i = 1; $i <= $x; $i++ ) {
                                   $p[$x][$i] = bcadd($p[($x-1)][($i-1)], $p[($x-1)][($i)]);
                               }
                           }
                           return $p[$row][$column];
                       }
                       echo 'Row '.$row.', Column '.$col.' = '. pascal($row, $col);
                   } else {
                       echo 'Please enter a valid column between 1 and '.$row;
                   }

               } else {
                   echo 'Please enter a valid row between 1 and 500';
               }

           }
           ?>
       </p>
       <script type="text/javascript">

           var row = document.getElementById('row');

           row.addEventListener('change',function (e) {
               var col = document.getElementById('col');
               col.innerHTML = '';
               var str = ''
               for (i=1; i<=row.value; i++) {
                   str = str + '<option value="' + i + '">' + i + '</option>';
               }
               col.innerHTML = str;
             e.stopPropagation();
           },true);
       </script>    
   </body>
</html>

 

Entry from Geeks

<?php 

 $PT = new pascalTriangle();  

 foreach($PT->PascalFullArrayGenerator(10) as $row){

   print_r($row);

   print('<br />');

 }  

 $val = $PT->cellError($PT->pascalCellCalculator(10, 5));

 echo '<hr />'.$val;





class pascalTriangle{ 



 /* @ Method to genarate array with full Pascal Triangle

  * @ access = public

  * @ param = int $rows   

  * @ return array

  */   

 public function PascalFullArrayGenerator($rows){  

   if(!is_int($rows)) return array('error PFAG_1, only integers can be used');

   for($i=0;$i<=$rows;$i++){  

     $returnVal[] = ($this->PascalRowGenerator($i)); 

   }

   return $returnVal;

 }



 /* @ Method to genarate array with a single row of a Pascal Triangle

  * @ access = public

  * @ param = int $row   

  * @ return array

  */   

 public function PascalRowGenerator($row){     

   if(!is_int($row)) return array('error PRC_1, only integers can be used');

   $returnVal = array(1); $val = 1;                                                    

   for($j=intval($row);$j>0;$j--){ 

     $val = $val * ($j / ((intval($row)+1)-$j));

     $returnVal[]= $val;

   }

   return $returnVal;

 }    



 /* @ Method to calculate value of single cell of Pascals Triangle

  * @ access = public

  * @ param = int $row  

  * @ param = int $col 

  * @ return int

  */   

 public function pascalCellCalculator($row,$col){

   if(!is_int($row) or !is_int($col)) -1;

   elseif($col>$row) return -2;

   $returnVal = $this->PascalRowGenerator($row); 

   return $returnVal[$col];

 }    



 /* @ Method to return actual error of Cell Calculator

  * @ access = public

  * @ param = int $val   

  * @ return string

  */   



 public function cellError($val){ 

   if($val > 0) return $val;

   return ($val == -2?'column is greater than row':'did not parse an integer');

 }         

}

?>

Sorry; was a bit slow at posting!

 

This was my source:

 

<?php

function getPascalsTriangle($row_to_return,$position_to_return,$current_row = 0,$previous_row_array = "") {   

   if($position_to_return > $row_to_return) {
       return false;
   }

   if($current_row == 1) {
       $previous_row_array = array("1" => "1");
   }	       
   $this_row_array = array();          

   for($i=1;$i<=$current_row;$i++) {        
       $row = intval($previous_row_array[$i]);        
       if(isset($previous_row_array[$i-1])) {
           $row += $previous_row_array[$i-1];
       }        
       $this_row_array[$i] = $row;        
   }  
   if($row_to_return == $current_row) {
       if(!isset($this_row_array[$position_to_return])) {
           return false;
       }
       return $this_row_array[$position_to_return];        
   } else {
       return getPascalsTriangle($row_to_return,$position_to_return,$current_row+1,$this_row_array);	
   }
}



$row = intval($_GET['row']);
$column = intval($_GET['column']);


?><!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
     "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">
   <head>
       <title>Pascal</title>
   </head>

   <body>


       <h1>Pascal's triangle calculator:</h1>

<form method="get" action="/wdf3/index.php">
   <input type="hidden" name="action" value="process" />
   <p><label for="row">Row</label> <input id="row" name="row" value="<?php echo $row ?>" type="text" /></p>

   <p><label for="column">Column</label> <input id="column" name="column" value="<?php echo $column ?>" type="text" /></p>

   <p><input type="submit" value="Go" /></p>

</form>

<?php

if($_GET['action'] == "process") {
   echo "<h2>Result for row ".$row." and column ".$column."</h2>";

   $result = getPascalsTriangle($row,$column);
  echo $result;
   if($result) {
       echo "<p>Value: " . $result . "</p>";
   } else {
       echo "<p>Please enter two valid numbers. Column cannot be greater than row.</p>";
   }
}

?>


   </body>
</html>

I see looking at Jock's code that had I replaced:

 

$row = $row + $previous_row_array[$i-1];

 

With

 

$row = bcadd($row,$previous_row_array[$i-1]);

 

I would have got over the issue I had with large numbers...

 

... but can someone explain why simply adding the numbers fails? Is it simply due to the way PHP handles integers?

  • Author

@rob

 

Floating point numbers have limited precision. Although it depends on the system, PHP typically uses the IEEE 754 double precision format, which will give a maximum relative error due to rounding in the order of 1.11e-16. Non elementary arithmetic operations may give larger errors, and, of course, error progragation must be considered when several operations are compounded.

 

Additionally, rational numbers that are exactly representable as floating point numbers in base 10, like 0.1 or 0.7, do not have an exact representation as floating point numbers in base 2, which is used internally, no matter the size of the mantissa. Hence, they cannot be converted into their internal binary counterparts without a small loss of precision. This can lead to confusing results: for example, floor((0.1+0.7)*10) will usually return 7 instead of the expected 8, since the internal representation will be something like 7.9999999999999991118....

 

So never trust floating number results to the last digit, and never compare floating point numbers for equality. If higher precision is necessary, the arbitrary precision math functions and gmp functions are available.

 

from php docs

Ah, I remember the old "floor((0.1+0.7)*10)" example from the ZCE test now you come to mention it. One of those things that's never come up (until this challenge) again. Thanks Jock.

Create an account or sign in to comment

Account

Navigation

Search

Search

Configure browser push notifications

Chrome (Android)
  1. Tap the lock icon next to the address bar.
  2. Tap Permissions → Notifications.
  3. Adjust your preference.
Chrome (Desktop)
  1. Click the padlock icon in the address bar.
  2. Select Site settings.
  3. Find Notifications and adjust your preference.