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

59 Solutions
28 Solvers

Last Solution submitted on Sep 05, 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

3 Comments

3 Comments

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.

Problem Recent Solvers28

Problem Tags

Community Treasure Hunt

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

Start Hunting!