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>

This Challenge is to solve Question A of the <http://contest.usc.edu/index.php/Fall12/Home USC ACM Fall 2012 Contest>.

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 <http://contest.usc.edu/index.php/Fall12/Home?action=download&upname=codes.in.txt USC data file>

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 flip

Matlab one-liner?

The Winning C solution - not much help:

#include <iostream>
 #include <stdio.h>
 #include <string>
 using namespace std;
 int main () {
 	freopen("codes.in", "r", stdin);
 	int K,n,b;
 	cin >> K;
 	for (int i = 1; i < K + 1; ++i) {
 		cin >> n >> b;
 		string m[1000], r;
 		for (int j = 0; j < n; ++j)
 			cin >> m[j];
 		cin >> r;
% Process Start		
 		int f = b;
 		for (int j = 0; j < n; ++j) {
 			int d = b;
 			for (int k = 0; k < b; ++k) {
 				if (m[j][k] == r[k])
 					--d;
 			}
 			f = ((f <= d) ? f : d);
 		}
 % Process End 
 		printf("Data Set %d:\n", i);
 		printf("%d\n\n", f);
 	}
 	return 0;
 }

Solve

Solution Stats

69 Solutions
16 Solvers

Last Solution submitted on Apr 14, 2023

Last 200 Solutions

Solution Comments

Show comments

Problem Recent Solvers16

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

Solution Comments

Problem Recent Solvers16

Suggested Problems

More from this Author260

Problem Tags

Community Treasure Hunt

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

Solution Stats

Last 200 Solutions

Solution Comments

Problem Recent Solvers16

Suggested Problems

More from this Author260

Problem Tags

Community Treasure Hunt

Players