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

11 Solutions
6 Solvers

Last Solution submitted on Dec 15, 2018

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 Solvers6

Problem Tags

Problem 2324. GJam 2014 Rd 1c: Train Cars

Solution Stats

Last 200 Solutions

Solution Comments

Problem Recent Solvers6

Suggested Problems

More from this Author236

Problem Tags

Problem 2324. GJam 2014 Rd 1c: Train Cars

Solution Stats

Last 200 Solutions

Solution Comments

Problem Recent Solvers6

Suggested Problems

More from this Author236

Problem Tags

Players