Problem 45415. Find an optimal placement of coolers on a grid

Created by Karl Ezra Pilario

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>In a certain chemical plant, 6 new pieces of cooling equipment (coolers) are to be installed in a vacant space. This vacant space was divided into a grid of 6 cells by 6 cells. Your task is to assign the 6 coolers to 6 cells in this grid with the following requirements:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"2\"/></w:numPr></w:pPr><w:r><w:t>There must be one cooler for every column in the grid.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"2\"/></w:numPr></w:pPr><w:r><w:t>If you decide to install a cooler at row R, column C, then the cooler at column C+1 must be installed either on row R-1, R, or R+1 only. This is done to ease the connection of coolers by piping.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"2\"/></w:numPr></w:pPr><w:r><w:t>The total installation cost for the 6 coolers must be minimum.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>For this problem, you are given a cost matrix (COST) in relation to the third requirement above. COST is a 6 x 6 matrix where the</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>r,c</w:t></w:r><w:r><w:t>-th element is the cost of assigning any cooler to row</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>r</w:t></w:r><w:r><w:t>, column</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>c</w:t></w:r><w:r><w:t> (All the coolers are identical). Write a function that accepts the matrix COST, and output the value of the minimum cost of installation. You are ensured that all elements of COST are integers in the range [1,1000].</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>In the sample test case below, the optimal placement is at the following rows: 4,3,3,2,2,2.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[>> COST = [695 766 710 119 752 548;\n 318 796 755 499 256 139;\n 951 187 277 960 506 150;\n 35 490 680 341 700 258;\n 439 446 656 586 891 841;\n 382 647 163 224 960 255];\n>> coolers(COST)\nans = \n 1393]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Meanwhile, the optimal placement for the case below is at rows: 5,6,5,6,5,6</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[>> COST = [815 617 918 76 569 312;\n 244 474 286 54 470 529;\n 930 352 758 531 455 988;\n 350 831 754 780 12 602;\n 197 586 381 935 163 263;\n 252 550 568 130 795 100];\n>> coolers(COST)\nans = \n 1521]]></w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

In a certain chemical plant, 6 new pieces of cooling equipment (coolers) are to be installed in a vacant space. This vacant space was divided into a grid of 6 cells by 6 cells. Your task is to assign the 6 coolers to 6 cells in this grid with the following requirements:<ol><li>There must be one cooler for every column in the grid.</li><li>If you decide to install a cooler at row R, column C, then the cooler at column C+1 must be installed either on row R-1, R, or R+1 only. This is done to ease the connection of coolers by piping.</li><li>The total installation cost for the 6 coolers must be minimum.</li></ol>For this problem, you are given a cost matrix (COST) in relation to the third requirement above. COST is a 6 x 6 matrix where the r,c-th element is the cost of assigning any cooler to row r, column c (All the coolers are identical). Write a function that accepts the matrix COST, and output the value of the minimum cost of installation. You are ensured that all elements of COST are integers in the range [1,1000].In the sample test case below, the optimal placement is at the following rows: 4,3,3,2,2,2.<pre class="language-matlab">&gt;&gt; COST = [695 766 710 119 752 548;
 318 796 755 499 256 139;
 951 187 277 960 506 150;
 35 490 680 341 700 258;
 439 446 656 586 891 841;
 382 647 163 224 960 255];
&gt;&gt; coolers(COST)
ans = 
 1393
</pre>Meanwhile, the optimal placement for the case below is at rows: 5,6,5,6,5,6<pre class="language-matlab">&gt;&gt; COST = [815 617 918 76 569 312;
 244 474 286 54 470 529;
 930 352 758 531 455 988;
 350 831 754 780 12 602;
 197 586 381 935 163 263;
 252 550 568 130 795 100];
&gt;&gt; coolers(COST)
ans = 
 1521
</pre>

In a certain chemical plant, 6 new pieces of cooling equipment (coolers) are to be installed in a vacant space. This vacant space was divided into a grid of 6 cells by 6 cells. Your task is to assign the 6 coolers to 6 cells in this grid with the following requirements:

# There must be one cooler for every column in the grid.
# If you decide to install a cooler at row R, column C, then the cooler at column C+1 must be installed either on row R-1, R, or R+1 only. This is done to ease the connection of coolers by piping.
# The total installation cost for the 6 coolers must be minimum.

For this problem, you are given a cost matrix (COST) in relation to the third requirement above. COST is a 6 x 6 matrix where the _r,c_-th element is the cost of assigning any cooler to row _r_, column _c_ (All the coolers are identical). Write a function that accepts the matrix COST, and output the value of the minimum cost of installation. You are ensured that all elements of COST are integers in the range [1,1000].

In the sample test case below, the optimal placement is at the following rows: 4,3,3,2,2,2.

>> COST = [695   766   710   119   752   548;
             318   796   755   499   256   139;
             951   187   277   960   506   150;
              35   490   680   341   700   258;
             439   446   656   586   891   841;
             382   647   163   224   960   255];
  >> coolers(COST)
  ans = 
        1393
    
Meanwhile, the optimal placement for the case below is at rows: 5,6,5,6,5,6

>> COST = [815   617   918    76   569   312;
             244   474   286    54   470   529;
             930   352   758   531   455   988;
             350   831   754   780    12   602;
             197   586   381   935   163   263;
             252   550   568   130   795   100];
  >> coolers(COST)
  ans = 
        1521

Solve

Solution Stats

66 Solutions
30 Solvers

Last Solution submitted on Nov 27, 2021

Last 200 Solutions

Problem Comments

2 Comments

2 Comments

Alfonso Nieto-Castanon on 19 Aug 2020

nice problem (hint: viterbi) and overall an excellent series / problem-group!

Jimmy Sølvsteen Nielsen on 10 Sep 2020

I wish I had done a clever solution but I resorted to brute forcing it!

Solution Comments

Solution 5710630

1 Comment

1 Comment

Benjamin Rahimian on 6 May 2021

It's big brain time

Solution 2188958

4 Comments

4 Comments

Show 1 older comment

Karl Ezra Pilario on 2 Apr 2020

This passed because the grid is small. I knew I should have changed the problem to a 20 x 20 or 100 x 100 grid haha. Anyway, I'll make a harder version of this problem in the next series. :)

Nikolaos Nikolaou on 3 Apr 2020

And i ll prove to you then it will still work :)

Karl Ezra Pilario on 3 Apr 2020

Yeah probably so. I don't even know if Cody has a memory limit or time limit so one can create test cases that can really filter unwanted solutions. oh well.

mahesh kumar on 4 Nov 2021 at 19:24

now one test fail??

Problem Recent Solvers30

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!