Problem 42291. GJam 2015 Rd1B: Counter Culture

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=p0\"><w:r><w:t>GJam 2015 Rd 1B: Counter Culture</w:t></w:r></w:hyperlink><w:r><w:t>. Fastest completion - 5 minutes.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Determine minimum sequence length to reach a number. Sequence starts at 1 and the next is either +1 or the number's reverse with trailing zeros removed. (eg 2300 is followed by 2301 or 32)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Input: N, a value from 1 to 1,000,000</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Output: L, minimum length of sequence to reach N</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;=N&lt;=1000000</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[N=5, L=5 [1 2 3 4 5] L=N is true thru 19\nN=23, L=15 [1:12 21 22 23]]]></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 or semi-brute force using storage of past calculations. All values are processed at each depth level. Duplicates from [N+1 and flip] are purged. A fast reversal function is essential. Direct summation works well. The large case N limit is 1E14 making even semi-brute force with storage unlikely.</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=p0">GJam 2015 Rd 1B: Counter Culture</a>. Fastest completion - 5 minutes.Determine minimum sequence length to reach a number. Sequence starts at 1 and the next is either +1 or the number's reverse with trailing zeros removed. (eg 2300 is followed by 2301 or 32)Input: N, a value from 1 to 1,000,000Output: L, minimum length of sequence to reach NExamples: Small Case 1&lt;=N&lt;=1000000<pre class="language-matlab">N=5, L=5 [1 2 3 4 5] L=N is true thru 19
N=23, L=15 [1:12 21 22 23]
</pre>Theory: The small case can be solved with brute force or semi-brute force using storage of past calculations. All values are processed at each depth level. Duplicates from [N+1 and flip] are purged. A fast reversal function is essential. Direct summation works well. The large case N limit is 1E14 making even semi-brute force with storage unlikely.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

29 Solutions
21 Solvers

Last Solution submitted on Jun 12, 2020

Last 200 Solutions

Problem Recent Solvers21

Problem Tags

Problem 42291. GJam 2015 Rd1B: Counter Culture

Solution Stats

Last 200 Solutions

Problem Recent Solvers21

Suggested Problems

More from this Author237

Problem Tags

Problem 42291. GJam 2015 Rd1B: Counter Culture

Solution Stats

Last 200 Solutions

Problem Recent Solvers21

Suggested Problems

More from this Author237

Problem Tags

Players