Problem 1098. USC Fall 2012 ACM : Code Word Minimum Flipped Bits

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 to solve Question A of the</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://contest.usc.edu/index.php/Fall12/Home\"><w:r><w:t>USC ACM Fall 2012 Contest</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>Given an array M of Valid binary codewords(m codewords of width n) and a Received Corrupted(?) codeword of width n, determine the minimum number of flipped bits in the Received codeword to generate a valid codeword.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Input: [ M, v ]</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Output: e, minimum number of error(flipped) bits .</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>From full</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://contest.usc.edu/index.php/Fall12/Home?action=download&amp;upname=codes.in.txt\"><w:r><w:t>USC data file</w:t></w:r></w:hyperlink></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Input: [0 0 0; 1 1 1; 1 1 0], [0 1 0]</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Output: 1 as [0 1 0] can convert to [0 0 0] or [1 1 0] with a single flip</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Matlab one-liner?</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The Winning C solution - not much help:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[#include <iostream>\n#include <stdio.h>\n#include <string>\nusing namespace std;\nint main () {\n freopen(\"codes.in\", \"r\", stdin);\n int K,n,b;\n cin >> K;\n for (int i = 1; i < K + 1; ++i) {\n cin >> n >> b;\n string m[1000], r;\n for (int j = 0; j < n; ++j)\n cin >> m[j];\n cin >> r;\n% Process Start \n int f = b;\n for (int j = 0; j < n; ++j) {\n int d = b;\n for (int k = 0; k < b; ++k) {\n if (m[j][k] == r[k])\n --d;\n }\n f = ((f <= d) ? f : d);\n }\n% Process End \n printf(\"Data Set %d:\\n\", i);\n printf(\"%d\\n\\n\", f);\n }\n return 0;\n}]]></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 to solve Question A of the <a href="http://contest.usc.edu/index.php/Fall12/Home">USC ACM Fall 2012 Contest</a>.Given an array M of Valid binary codewords(m codewords of width n) and a Received Corrupted(?) codeword of width n, determine the minimum number of flipped bits in the Received codeword to generate a valid codeword.Input: [ M, v ]Output: e, minimum number of error(flipped) bits
.From full <a href="http://contest.usc.edu/index.php/Fall12/Home?action=download&amp;upname=codes.in.txt">USC data file</a>Input: [0 0 0; 1 1 1; 1 1 0], [0 1 0]Output: 1 as [0 1 0] can convert to [0 0 0] or [1 1 0] with a single flipMatlab one-liner?The Winning C solution - not much help:<pre class="language-matlab">#include &lt;iostream>
#include &lt;stdio.h>
#include &lt;string>
using namespace std;
int main () {
	freopen("codes.in", "r", stdin);
	int K,n,b;
	cin >> K;
	for (int i = 1; i &lt; K + 1; ++i) {
		cin >> n >> b;
		string m[1000], r;
		for (int j = 0; j &lt; n; ++j)
			cin >> m[j];
		cin >> r;
% Process Start		
		int f = b;
		for (int j = 0; j &lt; n; ++j) {
			int d = b;
			for (int k = 0; k &lt; b; ++k) {
				if (m[j][k] == r[k])
					--d;
			}
			f = ((f &lt;= d) ? f : d);
		}
% Process End 
		printf("Data Set %d:\n", i);
		printf("%d\n\n", f);
	}
	return 0;
}
</pre>

Solve

Solution Stats

22 Solutions
12 Solvers

Last Solution submitted on Jun 27, 2018

Last 200 Solutions

Problem Recent Solvers12

Problem Tags

Community Treasure Hunt

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

Start Hunting!

Problem 1098. USC Fall 2012 ACM : Code Word Minimum Flipped Bits

Solution Stats

Last 200 Solutions

Problem Recent Solvers12

Suggested Problems

More from this Author246

Problem Tags

Community Treasure Hunt

Problem 1098. USC Fall 2012 ACM : Code Word Minimum Flipped Bits

Solution Stats

Last 200 Solutions

Problem Recent Solvers12

Suggested Problems

More from this Author246

Problem Tags

Community Treasure Hunt

Players