Problem 42290. GJam 2015 Rd1B: Noisy Neighbors

Created by Richard Zapor

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>This Challenge is derived from</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://code.google.com/codejam/contest/8224486/dashboard#s=p1\"><w:r><w:t>GJam 2015 Rd 1B: Noisy Neighbors</w:t></w:r></w:hyperlink><w:r><w:t>. Fastest completion - 8 minutes.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Determine minimum number of adjacencies for N placed people in an RxC hotel matrix</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Input: m, an RxC zeros array; N number of rooms to be filled</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Output: NN, minimum number of common walls</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Examples: Small Case 1&lt;=R*C&lt;=16, 0&lt;=N&lt;=R*C</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[[1 1 1;1 0 1;1 1 1] has minimum 8 common walls vs [1 1 1;1 1 1;1 1 0] has 10 common\n[1;0;0;1] has 0 common walls\nones(2,3) has 7 common walls]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Theory: The small case can be solved with brute force using vector set with nchoosek followed by processing of convolutions. The large case has 10000 rooms making brute force hopeless.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Additional GJam solutions can be found at</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.go-hero.net/jam/15\"><w:r><w:t>Example GJam Matlab solutions</w:t></w:r></w:hyperlink><w:r><w:t>. Select Find Solutions, change Language to Matlab. The Test Suite, at the bottom, contains a full GJam Matlab solution.</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>"}]}

This Challenge is derived from <a href = "https://code.google.com/codejam/contest/8224486/dashboard#s=p1">GJam 2015 Rd 1B: Noisy Neighbors</a>. Fastest completion - 8 minutes.Determine minimum number of adjacencies for N placed people in an RxC hotel matrixInput: m, an RxC zeros array; N number of rooms to be filledOutput: NN, minimum number of common wallsExamples: Small Case 1&lt;=R*C&lt;=16, 0&lt;=N&lt;=R*C<pre class="language-matlab">[1 1 1;1 0 1;1 1 1] has minimum 8 common walls vs [1 1 1;1 1 1;1 1 0] has 10 common
[1;0;0;1] has 0 common walls
ones(2,3) has 7 common walls
</pre>Theory: The small case can be solved with brute force using vector set with nchoosek followed by processing of convolutions. The large case has 10000 rooms making brute force hopeless.Additional GJam solutions can be found at <a href = "http://www.go-hero.net/jam/15">Example GJam Matlab solutions</a>. Select Find Solutions, change Language to Matlab. The Test Suite, at the bottom, contains a full GJam Matlab solution.

Solve

Solution Stats

39 Solutions
10 Solvers

Last Solution submitted on Sep 18, 2020

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

Rafael S.T. Vieira on 18 Sep 2020

There is no need to test all cases. The ideal case is a swiss cheese in which no guest share a wall. Just start filling rooms from there if needed (the only problems is that room filling must follow an order, which makes the code quite large (but repetitive and boring), and there are two base cases for the swiss cheese structure). Maybe it's possible to create a function and decrease code size, but unless you see it at the moment that you are coding it, it would mean loosing too much time during competition when a Ctrl+C, Ctrl+V would be faster (and better than testing all cases).

Solution Comments

Solution 1578291

1 Comment

1 Comment

Rafael S.T. Vieira on 18 Sep 2020

Currently, my solutions and this one are the only that don't use brute force, but this one is the smallest. Congrats. :) (I was able to create a smaller solution after looking at your code.)

Problem Recent Solvers10

Problem Tags

2015 contest conv2 gjam nchoosek nnz

Community Treasure Hunt

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

Start Hunting!

Problem 42290. GJam 2015 Rd1B: Noisy Neighbors

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers10

Suggested Problems

More from this Author247

Problem Tags

Community Treasure Hunt

Problem 42290. GJam 2015 Rd1B: Noisy Neighbors

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers10

Suggested Problems

More from this Author247

Problem Tags

Community Treasure Hunt

Players