Problem 317. Find the stride of the longest skip sequence

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>We define a</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>skip sequence</w:t></w:r><w:r><w:t> as a regularly-spaced list of integers such as might be generated by MATLAB's</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/help/matlab/ref/colon.html\"><w:r><w:t>colon operator</w:t></w:r></w:hyperlink><w:r><w:t>. We will call the inter-element increment the</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>stride</w:t></w:r><w:r><w:t>. So the vector 2:3:17 or [2 5 8 11 14 17] is a six-element skip sequence with stride 3.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Given the vector a, your job is to find the stride associated with the longest skip sequence you can assemble using any of the elements of a in any order. You can assume that stride is positive and unique.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Example:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ input  a = [1 5 3 11 7 2 4 9]\n output stride is 2]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>since from the elements of a we can build the six-element sequence [1 3 5 7 9 11].</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

667 Solutions
128 Solvers

Last Solution submitted on Sep 03, 2020

Last 200 Solutions

Problem Comments

4 Comments

4 Comments

Show 1 older comment

@bmtran (Bryant Tran) on 13 Feb 2012

this problem is multi-valued. it is equally valid to say that, in the case of the example, the stride associated with the longest skip sequence is -2.

Ned Gulley on 14 Feb 2012

Fair enough. I changed the wording to remove the ambiguity.

Ned Gulley on 13 Feb 2014

I added another test and rescored. It appears that DIST no longer works. The DIST function is from the Neural Networks Toolbox. It shouldn't have worked in the past, but since it did, it played a part in a lot of answers. Sorry for the discontinuity.

Jean-Marie Sainthillier on 28 Jan 2015

Tough !
Two years before understand that the sequence must contain only elements of a :)

Solution Comments

Solution 1671276

1 Comment

1 Comment

A C on 10 Nov 2018

I use a cheap for the last one. Any help with the last one?

Solution 1628855

2 Comments

2 Comments

A C on 16 Sep 2018

plot(a, 'b-', 'LineWidth', 2); or [~ , loc] = findpeaks(a);
works for matlab but I cannot get it work here.

goc3 on 19 Sep 2018

Cody doesn't support toolbox functions.

Solution 1030619

1 Comment

1 Comment

Alfonso Nieto-Castanon on 25 Oct 2016

this new implicit expansion functionality is a great excuse to revisit old problems :)

Solution 40492

4 Comments

4 Comments

Show 1 older comment

@bmtran (Bryant Tran) on 14 Feb 2012

what does the dist function do?

Alfonso Nieto-Castanon on 14 Feb 2012

'dist' just computes the euclidean distance between two lists of vectors (the dimensionality size(dist(a,b)) is the same as size(a*b)). In this case ~dist(a',a+s) is just the same as bsxfun(@eq,a',a+s), the matrix defining a directional graph of the elements of 'a' with distance 's'.

Alfonso Nieto-Castanon on 14 Feb 2012

just for completion: the matrix above is nilpotent (with degree lower than the length of the vector a), if you sum all of its powers D=sum_n{C^n} (and this is what polyvalm does) you get a matrix where d(i,j)=1 if i is connected to j in this graph; it you then take the largets column sum of the result (this is what norm(D,1) does) you get the maximum length of a sequence with stride s (across all possible starting nodes in a)...

David Young on 18 Feb 2012

I am impressed.

Solution 40450

1 Comment

1 Comment

@bmtran (Bryant Tran) on 14 Feb 2012

i have no idea what dist or dmperm are/do...

Solution 40330

2 Comments

2 Comments

Alfonso Nieto-Castanon on 14 Feb 2012

wow, very nice double arrayfun

@bmtran (Bryant Tran) on 14 Feb 2012

they were once for loops

Problem Recent Solvers128

Problem Tags

sequences

Problem 317. Find the stride of the longest skip sequence

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers128

Suggested Problems

More from this Author50

Problem Tags

Problem 317. Find the stride of the longest skip sequence

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers128

Suggested Problems

More from this Author50

Problem Tags

Players