Problem 803. Twist 'n' Match

Created by Ned Gulley

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>Given n and m, construct an n-by-n matrix a such that a, when rotated 90 degrees and compared with itself, matches itself in exactly m places.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The number of matches m is calculated as follows:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ m = nnz(rot90(a)==a)]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Your answer a is clearly not unique. It must only meet the criteria stated above.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Examples:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ Input n = 2, m = 1\n One possible output: a = [ 1 2 \n                            1 3 ]\n\n Input n = 3, m = 7\n One possible output: a = [ 0 1 1\n                            1 1 1\n                            1 1 1 ]]]></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>"}]}

Solve

Solution Stats

126 Solutions
47 Solvers

Last Solution submitted on Oct 15, 2020

Last 200 Solutions

Problem Comments

5 Comments

5 Comments

Show 2 older comments

Jean-Marie Sainthillier on 21 Feb 2017

A lot of solutions don't work with something like n=5 and m=0

Jean-Marie Sainthillier on 22 Feb 2017

Not at all...
For n-by-n matrix, m=1 if n is odd number.

Asif Newaz on 1 Feb 2020

ur problems are really interesting

Ned Gulley on 3 Feb 2020

Thanks Asif!

Rafael S.T. Vieira on 1 Aug 2020

This problem has some issues because some pairs (n,m) do not have a solution. For instance, it is impossible to find a matrix such that m = n^2 -1 since a rotation pivot does not move. Moreover, there are floor((n^2)/4) cycles of numbers, and when we match the cycle beginning with its end, it creates two matches. It is possible to do some manipulations to have an m greater than n^2 - floor((n^2)/4), but not always.

Solution Comments

Solution 2765800

1 Comment

1 Comment

Rafael S.T. Vieira on 1 Aug 2020

My code fails for some of the cases I've mentioned. The current leading solution does better (finding some solutions my code can't), yet sometimes it enters into an infinite loop.

Solution 2114985

1 Comment

1 Comment

Asif Newaz on 2 Feb 2020

i had no idea this was gonna work :p

Problem Recent Solvers47

Problem Tags

rotation

Community Treasure Hunt

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

Start Hunting!

Problem 803. Twist 'n' Match

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers47

Suggested Problems

More from this Author50

Problem Tags

Community Treasure Hunt

Problem 803. Twist 'n' Match

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers47

Suggested Problems

More from this Author50

Problem Tags

Community Treasure Hunt

Players