Counting distinct triangles that have integer-length sides

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;

up vote
5
down vote

favorite

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;

edited Aug 6 at 16:23

Toby Speight

18.1k13592

asked Aug 6 at 14:47

k.am

283

add a commentÂ |Â

up vote
5
down vote

favorite

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;

edited Aug 6 at 16:23

Toby Speight

18.1k13592

asked Aug 6 at 14:47

k.am

283

add a commentÂ |Â

up vote
5
down vote

favorite

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;

edited Aug 6 at 16:23

Toby Speight

18.1k13592

asked Aug 6 at 14:47

k.am

283

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;

edited Aug 6 at 16:23

Toby Speight

18.1k13592

asked Aug 6 at 14:47

k.am

283

edited Aug 6 at 16:23

Toby Speight

18.1k13592

edited Aug 6 at 16:23

Toby Speight

18.1k13592

edited Aug 6 at 16:23

Toby Speight

18.1k13592

asked Aug 6 at 14:47

k.am

283

asked Aug 6 at 14:47

k.am

283

asked Aug 6 at 14:47

k.am

283

add a commentÂ |Â

3 Answers
3

active

oldest

votes

up vote
4
down vote

accepted

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-ii = icdot textmax(0, l_max-2i+1)$$
$$ sum_j = textmax(a, l_max-i+1)^l_maxl_max+1-j = (l_max - textmax(i, l_max-i+1)+1)(l_max+1) - sum_j = textmax(i, l_max-i+1)^l_maxj$$
$$ = (l_max - textmax(i, l_max-i+1)+1)((l_max+1) - fracl_max + textmax(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.

edited Aug 8 at 10:31

answered Aug 6 at 16:49

maxb

922312

"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.
â€“Â Andreas Rejbrand
Aug 6 at 20:27

@AndreasRejbrand Thanks for the feedback, I updated the equations.
â€“Â maxb
Aug 7 at 7:08

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
â€“Â k.am
Aug 8 at 10:29

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
Aug 8 at 10:31

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.
â€“Â maxb
Aug 8 at 10:52

add a commentÂ |Â

up vote
4
down vote

 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?

answered Aug 6 at 15:41

Peter Taylor

14.1k2454

add a commentÂ |Â

up vote
3
down vote

 //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{

edited Aug 8 at 7:40

answered Aug 6 at 16:25

Toby Speight

18.1k13592

Yes, the condition should be in the loop, to stop the process
â€“Â k.am
Aug 8 at 7:36

add a commentÂ |Â

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "196"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);

);

draft saved

draft discarded

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f201083%2fcounting-distinct-triangles-that-have-integer-length-sides%23new-answer', 'question_page');

);

Post as a guest

Name

3 Answers
3

active

oldest

votes

3 Answers
3

active

oldest

votes

up vote
4
down vote

accepted

Let's call the maximum and minimum side lengths $l_max$ and $l_min$

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.

edited Aug 8 at 10:31

answered Aug 6 at 16:49

maxb

922312

"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.
â€“Â Andreas Rejbrand
Aug 6 at 20:27

@AndreasRejbrand Thanks for the feedback, I updated the equations.
â€“Â maxb
Aug 7 at 7:08

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
â€“Â k.am
Aug 8 at 10:29

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
Aug 8 at 10:31

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.
â€“Â maxb
Aug 8 at 10:52

add a commentÂ |Â

up vote
4
down vote

accepted

Let's call the maximum and minimum side lengths $l_max$ and $l_min$

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.

edited Aug 8 at 10:31

answered Aug 6 at 16:49

maxb

922312

"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.
â€“Â Andreas Rejbrand
Aug 6 at 20:27

@AndreasRejbrand Thanks for the feedback, I updated the equations.
â€“Â maxb
Aug 7 at 7:08

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
â€“Â k.am
Aug 8 at 10:29

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
Aug 8 at 10:31

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.
â€“Â maxb
Aug 8 at 10:52

add a commentÂ |Â

up vote
4
down vote

accepted

Let's call the maximum and minimum side lengths $l_max$ and $l_min$

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.

edited Aug 8 at 10:31

answered Aug 6 at 16:49

maxb

922312

Let's call the maximum and minimum side lengths $l_max$ and $l_min$

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.

edited Aug 8 at 10:31

answered Aug 6 at 16:49

maxb

922312

edited Aug 8 at 10:31

answered Aug 6 at 16:49

maxb

922312

answered Aug 6 at 16:49

maxb

922312

answered Aug 6 at 16:49

maxb

922312

"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.
â€“Â Andreas Rejbrand
Aug 6 at 20:27

@AndreasRejbrand Thanks for the feedback, I updated the equations.
â€“Â maxb
Aug 7 at 7:08

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
â€“Â k.am
Aug 8 at 10:29

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
Aug 8 at 10:31

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.
â€“Â maxb
Aug 8 at 10:52

add a commentÂ |Â

"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.
â€“Â Andreas Rejbrand
Aug 6 at 20:27

@AndreasRejbrand Thanks for the feedback, I updated the equations.
â€“Â maxb
Aug 7 at 7:08

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
â€“Â k.am
Aug 8 at 10:29

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
Aug 8 at 10:31

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.
â€“Â maxb
Aug 8 at 10:52

"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.
â€“Â Andreas Rejbrand
Aug 6 at 20:27

@AndreasRejbrand Thanks for the feedback, I updated the equations.
â€“Â maxb
Aug 7 at 7:08

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
â€“Â k.am
Aug 8 at 10:29

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
Aug 8 at 10:31

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.
â€“Â maxb
Aug 8 at 10:52

add a commentÂ |Â

up vote
4
down vote

 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?

answered Aug 6 at 15:41

Peter Taylor

14.1k2454

add a commentÂ |Â

up vote
4
down vote

 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?

answered Aug 6 at 15:41

Peter Taylor

14.1k2454

add a commentÂ |Â

up vote
4
down vote

 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?

answered Aug 6 at 15:41

Peter Taylor

14.1k2454

 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?

answered Aug 6 at 15:41

Peter Taylor

14.1k2454

answered Aug 6 at 15:41

Peter Taylor

14.1k2454

answered Aug 6 at 15:41

Peter Taylor

14.1k2454

answered Aug 6 at 15:41

Peter Taylor

14.1k2454

add a commentÂ |Â

up vote
3
down vote

 //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{

edited Aug 8 at 7:40

answered Aug 6 at 16:25

Toby Speight

18.1k13592

Yes, the condition should be in the loop, to stop the process
â€“Â k.am
Aug 8 at 7:36

add a commentÂ |Â

up vote
3
down vote

 //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{

edited Aug 8 at 7:40

answered Aug 6 at 16:25

Toby Speight

18.1k13592

Yes, the condition should be in the loop, to stop the process
â€“Â k.am
Aug 8 at 7:36

add a commentÂ |Â

up vote
3
down vote

 //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{

edited Aug 8 at 7:40

answered Aug 6 at 16:25

Toby Speight

18.1k13592

 //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{

edited Aug 8 at 7:40

answered Aug 6 at 16:25

Toby Speight

18.1k13592

edited Aug 8 at 7:40

answered Aug 6 at 16:25

Toby Speight

18.1k13592

answered Aug 6 at 16:25

Toby Speight

18.1k13592

answered Aug 6 at 16:25

Toby Speight

18.1k13592

Yes, the condition should be in the loop, to stop the process
â€“Â k.am
Aug 8 at 7:36

add a commentÂ |Â

Yes, the condition should be in the loop, to stop the process
â€“Â k.am
Aug 8 at 7:36

Yes, the condition should be in the loop, to stop the process
â€“Â k.am
Aug 8 at 7:36

add a commentÂ |Â

draft saved

draft discarded

draft saved

draft discarded

Post as a guest

Name

Search This Blog

Iyfjky