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\$
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.

| improve this answer | |
\$\endgroup\$
  • \$\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\$ – Andreas Rejbrand Aug 6 '18 at 20:27
  • \$\begingroup\$ @AndreasRejbrand Thanks for the feedback, I updated the equations. \$\endgroup\$ – maxb Aug 7 '18 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\$ – k.am Aug 8 '18 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\$ – maxb Aug 8 '18 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\$ – maxb Aug 8 '18 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?

| improve this answer | |
\$\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{
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Yes, the condition should be in the loop, to stop the process \$\endgroup\$ – k.am Aug 8 '18 at 7:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.