Problem 2324. GJam 2014 Rd 1c: Train Cars

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=\"http://code.google.com/codejam/contest/3004486/dashboard#s=p1\"><w:r><w:t>GJam 2014 Rd 1c: Reordering Train Cars</w:t></w:r></w:hyperlink><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Determine number of sequences for set of strings under the constraint that all same characters must be contiguous.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Input:</w:t></w:r><w:r><w:t> s, string of N space separated string segments of letters [a..z]. 1&lt;=N&lt;=10. Total letters &lt;=100.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output:</w:t></w:r><w:r><w:t> val, number of possible sequences</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Example:</w:t></w:r><w:r><w:t> Small Case</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ab bbbc cd Val=1 as only abbbbccd can be created\naa aa bc c Val=4 aa gives 2 positions, aa'aa''bcc,aa''aa'bcc, bcccaa'aa'',bcccaa''aa'\nabc bcd Val=0 as c is internal and thus can not connect to c of abc]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Theory:</w:t></w:r><w:r><w:t> (Spoilers)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>A methodical approach implements the following checks: No internal equals any Start/End. Note aaa has no internal. Verify each string has no non-contiguous letters. Verify no two strings have same start or end except where start==end as in bbbb. Val is N! if there are N cc strings. Each string segment is considered a unique piece when counting. Reduce the strings of type aa until there is only one and increase Val by N!. With remaining strings merge to S strings. Val is then scaled by S!. Key merging issue is that ab ba may look mergeable to aa but in actuality it creates abba - invalid and baab -invalid thus Val=0. Creation of full length string and then a final validity check resolves this issue.</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://go-hero.net/jam\"><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. No Valid Matlab solutions were submitted during the contest.</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 = "http://code.google.com/codejam/contest/3004486/dashboard#s=p1">GJam 2014 Rd 1c: Reordering Train Cars</a>.Determine number of sequences for set of strings under the constraint that all same characters must be contiguous.Input: s, string of N space separated string segments of letters [a..z]. 1&lt;=N&lt;=10. Total letters &lt;=100.Output: val, number of possible sequencesExample: Small Case<pre class="language-matlab">ab bbbc cd Val=1 as only abbbbccd can be created
aa aa bc c Val=4 aa gives 2 positions, aa'aa''bcc,aa''aa'bcc, bcccaa'aa'',bcccaa''aa'
abc bcd Val=0 as c is internal and thus can not connect to c of abc
</pre>Theory: (Spoilers)A methodical approach implements the following checks: No internal equals any Start/End. Note aaa has no internal. Verify each string has no non-contiguous letters. Verify no two strings have same start or end except where start==end as in bbbb. Val is N! if there are N cc strings. Each string segment is considered a unique piece when counting. Reduce the strings of type aa until there is only one and increase Val by N!. With remaining strings merge to S strings. Val is then scaled by S!. Key merging issue is that ab ba may look mergeable to aa but in actuality it creates abba - invalid and baab -invalid thus Val=0. Creation of full length string and then a final validity check resolves this issue.Additional GJam solutions can be found at <a href = "http://go-hero.net/jam">Example GJam Matlab solutions</a>. Select Find Solutions, change Language to Matlab. The Test Suite, at the bottom, contains a full GJam Matlab solution. No Valid Matlab solutions were submitted during the contest.

Solve

Solution Stats

12 Solutions
7 Solvers

Last Solution submitted on Oct 01, 2020

Last 200 Solutions

Solution Comments

Solution 447045

1 Comment

1 Comment

Alfonso Nieto-Castanon on 10 Jun 2014

Nice! Much smarter than my brute force approach

Problem Recent Solvers7

Problem Tags

Community Treasure Hunt

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

Start Hunting!

Problem 2324. GJam 2014 Rd 1c: Train Cars

Solution Stats

Last 200 Solutions

Solution Comments

Problem Recent Solvers7

Suggested Problems

More from this Author241

Problem Tags

Community Treasure Hunt

Problem 2324. GJam 2014 Rd 1c: Train Cars

Solution Stats

Last 200 Solutions

Solution Comments

Problem Recent Solvers7

Suggested Problems

More from this Author241

Problem Tags

Community Treasure Hunt

Players