Counting distinct triangles that have integer-length sides

Question

Problem:

We are interested in triangles that have integer length sides, all of which are between minLength and maxLength, inclusive. How many such triangles are there? Two triangles differ if they have a different collection of side lengths, ignoring order. Triangles with side lengths {2,3,4} and {4,3,5} differ, but {2,3,4} and {4,2,3} do not. We are only interested in proper triangles; the sum of the two smallest sides of a proper triangle must be strictly greater than the length of the biggest side.

Create a class TriCount that contains a method count that is given ints minLength and maxLength and returns the number of different proper triangles whose sides all have lengths between minLength and maxLength, inclusive. If there are more than 1,000,000,000, return -1.

My solution:

enter image description here

class Form{
 /**
 *@var array données utilisées par le formulaire
 */
 protected $data;
 /**
 *@var string tag qui entoure les champs
 */
 public $surroud ='p';
 /**
 *@param array $data
 *@return string
 */
 public function __construct($data = array()){
 $this->data = $data;
 }
 /**
 *@param $html string
 *@return string
 */
 protected function surroud(string $html){
 return "<{$this->surroud}>".$html."</{$this->surroud}>";
 }
 /**
 *@param $index string
 *@return string
 */
 protected function getValue(string $index){
 return isset($this->data[$index]) ? $this->data[$index] : null;
 }
 /**
 *@param $name string
 *@return string
 */
 public function input(string $name){
 return $this->surroud("<label for='".$name."'>".$name.": </label><input type='text' name='".$name."' value='".$this->getValue($name)."'>");
 }
 /**
 *@return string
 */
 public function submit(){
 return $this->surroud("<button type='submit'>Envoyer</button>");
 }
}

---

<?php
class FormController{
 /**
 *@return objet
 */
 public function registerI()
 {
 return new TriCount();
 }
 /**
 *@param $params array
 *@return integer
 */
 public function register(array $params)
 {
 //les champs sont remplis d'entier
 if(intval($params['min']) && intval($params['max'])){
 //instancier la classe pour le calcul des probabilités
 $inst = new TriCount();
 //appel de la methode qui calcul les probabilités
 $nbre = $inst->count($params['min'], $params['max']);
 return $nbre;
 }else{
 $message_erreur = "Vous devez remplir avec des entiers superieur à 0!";
 return $message_erreur;
 }
 }
}

---

<?php
/**
 *Class TriCount
 */
class TriCount{
 /**
 *@var integer minimum du tableau
 */
 private $minLength;
 /**
 *@var integer maximum du tableau
 */
 private $maxLength;
 /**
 *@var integer nombre de triangle possible
 */
 private $count;
 /**
 *@param $minLength integer
 *@param $maxLength integer
 *@return integer
 */
 public function count(int $minLength , int $maxLength ){
 //initialiser le compteur
 $count = 0;
 //3 boucles qui font varier le (i,j,k)
 // le script s'arrete si la condition n'est pas vérifiée
 for ($i = $minLength; $i <= $maxLength; $i++){
 for($j = $i ; $j <= $maxLength; $j++){
 for($k = $j ; $k <= $maxLength; $k++){
 //condition: la somme des deux petits cotés du triangle superieur au troisieme coté
 if( ($i + $j ) > $k ) {
 $count++;
 }else{
 break;
 }
 }
 }
 }
 //si le nombre de possibilité dépasse 1000000000
 if ($count <= 1000000000 ){
 return $count;
 }else {
 return -1;
 }
 }
}

Answer 1

Let's call the maximum and minimum side lengths \$l_{max}\$ and \$l_{min}\$

We can see that for a certain choice of $i and $j, we can directly calculate the number of choices for $k as \$min(i+j-j, l_{max}+1-j) = min(i, l_{max}+1-j)\,ドル which suggests that wee can remove the innermost loop.

Now we've got our hopes up, and we hope that the second loop can be removed in a similar fashion. For a fixed value of \$i\,ドル we know that \$i < l_{max} + 1 - j \iff j < l_{max} + 1 - i\$. We also have to take care of the cases where either sum has a negative number of terms. This way, the second loop can be written as two sums:

$$ \sum_{j = i}^{l_{max}-i}i = i\cdot \text{max}(0, l_{max}-2i+1)$$ $$ \sum_{j = \text{max}(a, l_{max}-i+1)}^{l_{max}}l_{max}+1-j = (l_{max} - \text{max}(i, l_{max}-i+1)+1)(l_{max}+1) - \sum_{j = \text{max}(i, l_{max}-i+1)}^{l_{max}}j$$ $$ = (l_{max} - \text{max}(i, l_{max}-i+1)+1)((l_{max}+1) - \frac{l_{max} + \text{max}(i, l_{max}-i+1)}{2})$$

This got a bit messy, but both are arithmetic sums, and can be calculated fairly easily. Now the entire calculation can be reduced to one loop. I wrote a python script to test it:

minL = 5
maxL = 25
total_ways = 0
for a in range(minL, maxL+1):
 right_terms = maxL-max(a, maxL-a+1)+1
 left_sum = a*max(0, maxL-2*a+1)
 right_sum = right_terms*(maxL+1) - right_terms*(maxL + max(a, maxL-a+1))//2
 total_ways += left_sum + right_sum
print(total_ways)

It produces identical output for all test cases I've found, and should be way faster. Please ask for any clarifications.

• Andreas Rejbrand: "max" and "min" should never be written in italics -- not as "English subscripts" and not as function names (like sin and cos, which are also never written in italics). In addition, in mathematics, * typically denotes convolution. Use a dot operator for product.
• maxb: @AndreasRejbrand Thanks for the feedback, I updated the equations.
• k.am: Thank you for your answer, first we assume that we take only integer number I tried the script but it does not respond to the probematique for example when we have (1,2) you have (112) (111) (222) so result: 3 ; your script gives -1
• maxb: For the python script, I noticed that I made a mistake. it should be for a in range(minL, maxL+1). It does indeed produce the correct output then. Also note that // means integer division in python, and is not a comment.
• maxb: Glad that it worked, good luck! If you need even more performance, it might be possible to remove the last loop, but I leave that challenge to a mathematician.

Answer 2

 for($k = $j ; $k <= $maxLength; $k++){
 //condition: la somme des deux petits cotés du triangle superieur au troisieme coté
 if( ($i + $j ) > $k ) {
 $count++;
 }else{
 break;
 }
 }

How can you do this without a loop?

Answer 3

 //si le nombre de possibilité dépasse 1000000000
 if ($count <= 1000000000 ){
 return $count;
 }else {
 return -1;
 }

I think the intention is that you should stop counting when you reach 1,000,000,000, and just return early at that point:

 //condition: la somme des deux petits cotés du triangle superieur au troisieme coté
 if( ($i + $j ) > $k ) {
 $count++;
 if ($count > 1000000000) {
 return -1;
 }
 }else{

• k.am: Yes, the condition should be in the loop, to stop the process