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

120 Solutions
60 Solvers

Last Solution submitted on Aug 01, 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 at 4:58

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 at 5:05

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 Solvers60

Problem Tags

rotation

Problem 803. Twist 'n' Match

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers60

Suggested Problems

More from this Author49

Problem Tags

Problem 803. Twist 'n' Match

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers60

Suggested Problems

More from this Author49

Problem Tags

Players