14
\$\begingroup\$

Output Distinct Factor Cuboids

Today's task is very simple: given a positive integer, output a representative of each cuboid formable by its factors.

Explanations

A cuboid's volume is the product of its three side lengths. For example, a cuboid of volume 4 whose side lengths are integers can have sides [1, 1, 4], [1, 2, 2], [1, 4, 1], [2, 1, 2], [2, 2, 1], or [4, 1, 1]. However, some of these represent the same cuboid: e.g. [1, 1, 4] and [4, 1, 1] are the same cuboid rotated. There are only two distinct cuboids with volume 4 and integer sides: [1, 1, 4] and [1, 2, 2]. The output can be any representation of the first cuboid, and any representation of the second cuboid.

Input

Your program must take a single positive integer \$1 \le n \le 2^{31}−1\$.

Output

You will need to output all possible cuboids in a list or any other acceptable way. E.g.

Input  Output
  1    [[1, 1, 1]]
  2    [[1, 1, 2]]
  3    [[1, 1, 3]]
  4    [[1, 1, 4], [1, 2, 2]]
  8    [[1, 1, 8], [1, 2, 4], [2, 2, 2]]
 12    [[1, 1, 12], [1, 2, 6], [1, 3, 4], [2, 2, 3]]
 13    [[1, 1, 13]]
 15    [[1, 1, 15], [1, 3, 5]]
 18    [[1, 1, 18], [1, 2, 9], [1, 3, 6], [2, 3, 3]]
 23    [[1, 1, 23]]
 27    [[1, 1, 27], [1, 3, 9], [3, 3, 3]]
 32    [[1, 1, 32], [1, 2, 16], [1, 4, 8], [2, 2, 8], [2, 4, 4]]
 36    [[1, 1, 36], [1, 2, 18], [1, 3, 12],[1, 4, 9], [1, 6, 6], [2, 2, 9], [2, 3, 6], [3, 3, 4]]

Sub-lists don't need to be sorted, just as long as they are unique.

Scoring

This is code golf, so shortest answer in bytes wins. Standard loopholes are forbidden.

Here is a test case generator

Leaderboards

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

# Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

# Ruby, <s>104</s> <s>101</s> 96 bytes

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

# Perl, 43 + 2 (-p flag) = 45 bytes

You can also make the language name a link which will then show up in the leaderboard snippet:

# [><>](http://esolangs.org/wiki/Fish), 121 bytes


var QUESTION_ID=192852;
var OVERRIDE_USER=8478;
var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;function answersUrl(d){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+d+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(d,e){return"https://api.stackexchange.com/2.2/answers/"+e.join(";")+"/comments?page="+d+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(d){answers.push.apply(answers,d.items),answers_hash=[],answer_ids=[],d.items.forEach(function(e){e.comments=[];var f=+e.share_link.match(/\d+/);answer_ids.push(f),answers_hash[f]=e}),d.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(d){d.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),d.has_more?getComments():more_answers?getAnswers():process()}})}getAnswers();var SCORE_REG=function(){var d=String.raw`h\d`,e=String.raw`\-?\d+\.?\d*`,f=String.raw`[^\n<>]*`,g=String.raw`<s>${f}</s>|<strike>${f}</strike>|<del>${f}</del>`,h=String.raw`[^\n\d<>]*`,j=String.raw`<[^\n<>]+>`;return new RegExp(String.raw`<${d}>`+String.raw`\s*([^\n,]*[^\s,]),.*?`+String.raw`(${e})`+String.raw`(?=`+String.raw`${h}`+String.raw`(?:(?:${g}|${j})${h})*`+String.raw`</${d}>`+String.raw`)`)}(),OVERRIDE_REG=/^Override\s*header:\s*/i;function getAuthorName(d){return d.owner.display_name}function process(){var d=[];answers.forEach(function(n){var o=n.body;n.comments.forEach(function(q){OVERRIDE_REG.test(q.body)&&(o="<h1>"+q.body.replace(OVERRIDE_REG,"")+"</h1>")});var p=o.match(SCORE_REG);p&&d.push({user:getAuthorName(n),size:+p[2],language:p[1],link:n.share_link})}),d.sort(function(n,o){var p=n.size,q=o.size;return p-q});var e={},f=1,g=null,h=1;d.forEach(function(n){n.size!=g&&(h=f),g=n.size,++f;var o=jQuery("#answer-template").html();o=o.replace("{{PLACE}}",h+".").replace("{{NAME}}",n.user).replace("{{LANGUAGE}}",n.language).replace("{{SIZE}}",n.size).replace("{{LINK}}",n.link),o=jQuery(o),jQuery("#answers").append(o);var p=n.language;p=jQuery("<i>"+n.language+"</i>").text().toLowerCase(),e[p]=e[p]||{lang:n.language,user:n.user,size:n.size,link:n.link,uniq:p}});var j=[];for(var k in e)e.hasOwnProperty(k)&&j.push(e[k]);j.sort(function(n,o){return n.uniq>o.uniq?1:n.uniq<o.uniq?-1:0});for(var l=0;l<j.length;++l){var m=jQuery("#language-template").html(),k=j[l];m=m.replace("{{LANGUAGE}}",k.lang).replace("{{NAME}}",k.user).replace("{{SIZE}}",k.size).replace("{{LINK}}",k.link),m=jQuery(m),jQuery("#languages").append(m)}}
body{text-align:left!important}#answer-list{padding:10px;float:left}#language-list{padding:10px;float:left}table thead{font-weight:700}table td{padding:5px}
 <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="https://cdn.sstatic.net/Sites/codegolf/primary.css?v=f52df912b654"> <div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td><a href="{{LINK}}">{{SIZE}}</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td><a href="{{LINK}}">{{SIZE}}</a></td></tr></tbody> </table>

Improve this question
\$\endgroup\$
2

11 Answers 11

Reset to default
5
\$\begingroup\$

JavaScript (V8),  61  60 bytes

Prints the cuboids to STDOUT.

n=>{for(z=n;y=z;z--)for(;(x=n/y/z)<=y;y--)x%1||print(x,y,z)}

Try it online!

Commented

n => {                // n = input
  for(                // outer loop:
    z = n;            //   start with z = n
    y = z;            //   set y to z; stop if we've reached 0
    z--               //   decrement z after each iteration
  )                   //
    for(              //   inner loop:
      ;               //     no initialization code
      (x = n / y / z) //     set x to n / y / z
      <= y;           //     stop if x > y
      y--             //     decrement y after each iteration
    )                 //
      x % 1 ||        //     unless x is not an integer,
      print(x, y, z)  //     print the cuboid (x, y, z)
}                     //
Improve this answer
\$\endgroup\$
5
\$\begingroup\$

Haskell, 52 bytes

f n=[[a,b,c]|a<-[1..n],b<-[1..a],c<-[1..b],a*b*c==n]

Try it online!

Tuples are in descending order. "3" seems to be a small-enough number that writing out the 3 loops was shorter than anything general I could come up with.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ I like the meta-obfuscation of calling the returned list's content tuples. \$\endgroup\$
    – Jonathan Frech
    Sep 17, 2019 at 9:04
5
\$\begingroup\$

Python 3.8 (pre-release),  83  80 bytes

lambda n:[[i,j,k]for i in(r:=range(n+1))for j in r[i:]for k in r[j:]if i*j*k==n]

Try it online!

...beating a two-loop version by three bytes:

lambda n:[[i,j,n//i//j]for i in(r:=range(1,n+1))for j in r if(i<=j<=n/i/j)>n%(i*j)]
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Jelly, 7 bytes

œċ3P⁼¥Ƈ

A monadic Link accepting a positive integer which yields a list of 3-lists of positive integers.

Try it online!

How?

œċ3P⁼¥Ƈ - Link: positive integer, N
  3     - literal three
œċ      - all combinations (of [1..N]) of length (3) with replacement
           i.e. [[1,1,1],[1,1,2],...,[1,1,N],[1,2,2],[1,2,3],...,[1,2,N],...,[N,N,N]]
      Ƈ - filter keep those for which:
     ¥  -   last two links as a dyad:
   P    -     product
    ⁼   -     equals (N)?
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Jelly, 11 bytes

ÆDṗ3Ṣ€QP=¥Ƈ

Try it online!

A monadic link taking an integer as its argument and returning a list of lists of integers.

Explanation

ÆD          | Divisors
  ṗ3        | Cartesian power of 3
    Ṣ€      | Sort each list
      Q     | Unique
         ¥Ƈ | Keep only where the following is true (as a dyad, using the original argument as right argument)
       P    | - Product
        =   | - Is equal (to original argument)
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Haskell, 67 60 59 bytes

For a given \$n\$, this produces all 3-tuples of with entries in \$\{1,2,\ldots,n\}\$ and filters out the valid ones. To guarantee uniqueness we require that the tuples are sorted.

f n=[x|x@[a,b,c]<-mapM id$[1..n]<$":-)",a*b*c==n,a<=b,b<=c]

Try it online!

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ I think three-tuples can only properly be produced with a smiley. \$\endgroup\$
    – Jonathan Frech
    Sep 17, 2019 at 9:18
  • \$\begingroup\$ ​:​-​)​ ​ ​ ​ ​ \$\endgroup\$
    – flawr
    Sep 17, 2019 at 9:38
2
\$\begingroup\$

Retina, 59 bytes

.+
*
2+%L$`(?<=(_+))(?=(\1)*$)
$` _$#2*
A`_(_+) \1\b
_+
$.&

Try it online! Link includes test suite. Explanation:

.+
*

Convert to unary.

2+%L$`(?<=(_+))(?=(\1)*$)
$` _$#2*

Repeating twice, divide the last number on each line into all of its possible pairs of factors. The lookbehind is greedy and atomic, so once it's matched the prefix of the last number it won't backtrack. This generates all possible permutations of three factors.

A`_(_+) \1\b

Delete lines where the factors are not in ascending order.

_+
$.&

Convert to decimal.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Pyth, 11 bytes

fqQ*FT.CSQ3

Try it online!

        SQ  #              range(1, Q+1)          # Q = input
      .C  3 # combinations(             , 3)
f           # filter(lambda T: vvv, ^^^)
 qQ         # Q == 
   *FT      #      fold(__operator_mul, T) ( = product of all elements)
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 8 bytes

Ò3.ŒP€{ê

Ò               # prime factors of the input
 3.Π           # all 3-element partitions
    P           # take the product of each inner list
     €{         # sort each inner list
       ê        # sort and uniquify the outer list

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

C (clang), 89 bytes

a,b,x;f(n){for(a=n;a;a--)for(b=a;b&&(x=n/a/b)<=b;b--)x*b*a-n||printf("%d,%d,%d ",x,b,a);}

Try it online!

Port of @Arnauld 👍

Saved 1 thanks to @Jonathan Frech better output format

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ "%d %d %d\n" ~> "%d,%d,%d " would save a byte. \$\endgroup\$
    – Jonathan Frech
    Sep 17, 2019 at 9:15
1
\$\begingroup\$

Icon, 87 bytes

procedure f(n)
k:=[]
a:=1to n&b:=1to a&c:=1to b&a*b*c=n&k|||:=[[a,b,c]]&\z
return k
end

Try it online!

Close to Python :)

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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