5
\$\begingroup\$

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;
        }

    }
}
\$\endgroup\$

3 Answers 3

Reset to default
4
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ "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. \$\endgroup\$ Commented Aug 6, 2018 at 20:27
  • \$\begingroup\$ @AndreasRejbrand Thanks for the feedback, I updated the equations. \$\endgroup\$ Commented Aug 7, 2018 at 7:08
  • \$\begingroup\$ 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 \$\endgroup\$ Commented Aug 8, 2018 at 10:29
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Aug 8, 2018 at 10:31
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Aug 8, 2018 at 10:52
4
\$\begingroup\$ 
                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?

\$\endgroup\$
3
\$\begingroup\$ 
    //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{
\$\endgroup\$
1
  • \$\begingroup\$ Yes, the condition should be in the loop, to stop the process \$\endgroup\$ Commented Aug 8, 2018 at 7:36

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.