Bovine Genomics

Solución en video

Por Jay Fu

Código de la solución en video

C++Java


#include <cmath>
#include <fstream>
#include <iostream>
 
using namespace std;
 
int N, M;
string spotty[100], plain[100];
 
bool test_location(int j) {
	bool found_cow[2][4] = {0};
 
	// found_cow[0] se refiere a las vacas con manchas, y found_cow[1] a las
	// vacas sin manchas. found_cow[0][0] = guarda si las vacas con manchas tienen el carácter A en
	// la posición j found_cow[0][1] = guarda si las vacas con manchas tienen el carácter C
	// en la posición j found_cow[0][2] = guarda si las vacas con manchas tienen el carácter
	// G en la posición j found_cow[0][3] = guarda si las vacas con manchas tienen el
	// carácter T en la posición j found_cow[1][0] = guarda si las vacas lisas tienen
	// el carácter A en la posición j found_cow[1][1] = guarda si las vacas lisas tienen
	// el carácter C en la posición j found_cow[1][2] = guarda si las vacas lisas tienen
	// el carácter G en la posición j found_cow[1][3] = guarda si las vacas lisas tienen
	// el carácter T en la posición j
 
	// iteramos por las vacas con manchas y actualizamos found_cow[0]
	for (int i = 0; i < N; i++) {
		if (spotty[i][j] == 'A') found_cow[0][0] = true;
		if (spotty[i][j] == 'C') found_cow[0][1] = true;
		if (spotty[i][j] == 'G') found_cow[0][2] = true;
		if (spotty[i][j] == 'T') found_cow[0][3] = true;
	}
 
	// iteramos por las vacas lisas y actualizamos found_cow[1]
	for (int i = 0; i < N; i++) {
		if (plain[i][j] == 'A') found_cow[1][0] = true;
		if (plain[i][j] == 'C') found_cow[1][1] = true;
		if (plain[i][j] == 'G') found_cow[1][2] = true;
		if (plain[i][j] == 'T') found_cow[1][3] = true;
	}
 
	// si un carácter aparece tanto en vacas con manchas como en lisas, devolvemos false
	// si no hay tal genoma, devolvemos true
	for (int i = 0; i < 4; ++i) {
		if (found_cow[0][i] && found_cow[1][i]) return false;
	}
	return true;
}
 
int main(void) {
	ifstream fin("cownomics.in");
	ofstream fout("cownomics.out");
	fin >> N >> M;
 
	// leemos la entrada
	for (int i = 0; i < N; i++) fin >> spotty[i];
	for (int i = 0; i < N; i++) fin >> plain[i];
	int answer = 0;
 
	// probamos cada posición del genoma para ver si podría explicar las manchas
	for (int j = 0; j < M; j++)
		if (test_location(j)) answer++;
	fout << answer << "\n";
	return 0;
}


import java.io.*;
import java.util.StringTokenizer;
 
public class cownomicsBronze {
	static int N, M;
	static String[] spotty, plain;
 
	static boolean test_location(int j) {
		boolean[][] found_cow = new boolean[2][4];
		// found_cow[0] se refiere a las vacas con manchas, y found_cow[1] a las
		// vacas sin manchas. found_cow[0][0] = guarda si las vacas con manchas tienen
		// el carácter A en la posición j found_cow[0][1] = guarda si las vacas con
		// manchas tienen el carácter C en la posición j found_cow[0][2] = guarda si
		// las vacas con manchas tienen el carácter G en la posición j found_cow[0][3] =
		// guarda si las vacas con manchas tienen el carácter T en la posición j found_cow[1][0] =
		// guarda si las vacas lisas tienen el carácter A en la posición j
		// found_cow[1][1] = guarda si las vacas lisas tienen el carácter C en
		// la posición j found_cow[1][2] = guarda si las vacas lisas tienen el carácter
		// G en la posición j found_cow[1][3] = guarda si las vacas lisas tienen
		// el carácter T en la posición j
 
		// iteramos por las vacas con manchas y actualizamos found_cow[0]
		for (int i = 0; i < N; i++) {
			if (spotty[i].charAt(j) == 'A') found_cow[0][0] = true;
			if (spotty[i].charAt(j) == 'C') found_cow[0][1] = true;
			if (spotty[i].charAt(j) == 'G') found_cow[0][2] = true;
			if (spotty[i].charAt(j) == 'T') found_cow[0][3] = true;
		}
 
		// iteramos por las vacas lisas y actualizamos found_cow[1]
		for (int i = 0; i < N; i++) {
			if (plain[i].charAt(j) == 'A') found_cow[1][0] = true;
			if (plain[i].charAt(j) == 'C') found_cow[1][1] = true;
			if (plain[i].charAt(j) == 'G') found_cow[1][2] = true;
			if (plain[i].charAt(j) == 'T') found_cow[1][3] = true;
		}
 
		// si un carácter aparece tanto en vacas con manchas como en lisas, devolvemos
		// false; si no hay tal genoma, devolvemos true
		for (int i = 0; i < 4; ++i) {
			if (found_cow[0][i] && found_cow[1][i]) return false;
		}
		return true;
	}
 
	public static void main(String[] args) throws IOException {
		// leemos la entrada
		BufferedReader br = new BufferedReader(new FileReader("cownomics.in"));
		PrintWriter out = new PrintWriter("cownomics.out");
		StringTokenizer s = new StringTokenizer(br.readLine());
		N = Integer.parseInt(s.nextToken());
		M = Integer.parseInt(s.nextToken());
		spotty = new String[100];
		plain = new String[100];
		for (int i = 0; i < N; i++) { spotty[i] = br.readLine(); }
		for (int i = 0; i < N; i++) { plain[i] = br.readLine(); }
 
		// probamos cada posición del genoma para ver si podría explicar
		// las manchas
		int answer = 0;
		for (int j = 0; j < M; j++) {
			if (test_location(j)) answer++;
		}
		out.println(answer);
		out.close();
	}
}

Solución 1 - Fuerza bruta

Iteramos por cada carácter de cada genoma. Para cada índice de carácter, vemos si hay algún carácter que aparezca en el genoma tanto de una vaca con manchas como de una vaca lisa en ese índice. Si los hay, esta posición no es una solución posible, así que podemos terminar esta parte de la búsqueda y pasar a la siguiente posición para ahorrar tiempo de ejecución. Si no los hay, esta es una solución posible.

Implementación

Complejidad temporal: $\mathcal O(MN^2)$

C++JavaPython


#include <fstream>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	std::ifstream read("cownomics.in");
 
	int n;
	int m;
	read >> n >> m;
 
	// Cada genoma y los caracteres individuales de cada genoma
	vector<vector<char>> spotted_cows(n, vector<char>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) { read >> spotted_cows[i][j]; }
	}
 
	vector<vector<char>> plain_cows(n, vector<char>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) { read >> plain_cows[i][j]; }
	}
 
	int poss_positions = 0;
	// Iteramos por cada carácter
	for (int i = 0; i < m; i++) {
		bool dupe = false;
		// Iteramos por cada genoma
		for (int j = 0; j < n; j++) {
			// Comparamos con cada otro genoma
			for (int k = 0; k < n; k++) {
				/*
				 * Si hay algún duplicado,
				 * entonces esta no es una posición posible,
				 * así que dejamos de contar y nos aseguramos de no contarla
				 */
				if (spotted_cows[j][i] == plain_cows[k][i]) {
					dupe = true;
					break;
				}
			}
		}
		/*
		 * Si no encontramos ningún carácter igual,
		 * entonces no hay duplicados y esta es una secuencia posible
		 */
		if (!dupe) { poss_positions++; }
	}
 
	std::ofstream("cownomics.out") << poss_positions << endl;
}


import java.io.*;
import java.util.*;
 
public class BovineGenomics {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("cownomics");
 
		int n = io.nextInt();
		int m = io.nextInt();
 
		// Cada genoma y los caracteres individuales de cada genoma
		char[][] spottedCows = new char[n][];
		char[][] plainCows = new char[n][];
		for (int i = 0; i < n; i++) { spottedCows[i] = io.next().toCharArray(); }
		for (int i = 0; i < n; i++) { plainCows[i] = io.next().toCharArray(); }
 
		int possPositions = 0;
		// Iteramos por cada carácter
		for (int i = 0; i < m; i++) {
			boolean dupe = false;
			// Iteramos por cada genoma
			for (int j = 0; j < n; j++) {
				// Comparamos con cada otro genoma
				for (int k = 0; k < n; k++) {
					/*
					 * Si hay algún duplicado,
					 * entonces esta no es una posición posible,
					 * así que dejamos de contar y nos aseguramos de no contarla
					 */
					if (spottedCows[j][i] == plainCows[k][i]) {
						dupe = true;
						break;
					}
				}
			}
			/*
			 * Si no encontramos ningún carácter igual,
			 * entonces no hay duplicados y esta es una secuencia posible
			 */
			if (!dupe) { possPositions++; }
		}
 
		io.println(possPositions);
		io.close();
	}
 
	// CodeSnip{Kattio}
}


with open("cownomics.in", "r") as read:
	n, m = map(int, read.readline().split())
 
	# Cada genoma y los caracteres individuales de cada genoma
	spotted_cows = [read.readline() for _ in range(n)]
	plain_cows = [read.readline() for _ in range(n)]
 
poss_positions = 0
# Iteramos por cada carácter
for i in range(m):
	dupe = False
	# Iteramos por cada genoma
	for j in range(n):
		# Comparamos con cada otro genoma
		for k in range(n):
			"""
			Si hay algún duplicado,
			entonces esta no es una posición posible,
			así que dejamos de contar y nos aseguramos de no contarla
			"""
			if spotted_cows[j][i] == plain_cows[k][i]:
				dupe = True
				break
 
	"""
	Si no encontramos ningún carácter igual,
	entonces no hay duplicados y esta es una secuencia posible
	"""
	if not dupe:
		poss_positions += 1
 
print(poss_positions, file=open("cownomics.out", "w"))

Solución 2 - Conjunto hash

Si un genoma está presente en una vaca lisa pero no en una vaca con manchas, incrementamos el resultado. En caso contrario, no es un genoma potencial.

Implementación

Complejidad temporal: $\mathcal{O}(NM)$

C++JavaPython


#include <fstream>
#include <iostream>
#include <set>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	std::ifstream read("cownomics.in");
 
	int n;
	int m;
	read >> n >> m;
 
	vector<vector<char>> spotted_cows(n, vector<char>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) { read >> spotted_cows[i][j]; }
	}
 
	vector<vector<char>> plain_cows(n, vector<char>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) { read >> plain_cows[i][j]; }
	}
 
	int poss_positions = 0;
	for (int i = 0; i < m; i++) {
		std::set<char> seen;
		for (int j = 0; j < n; j++) { seen.insert(plain_cows[j][i]); }
 
		bool dupe = false;
		for (int j = 0; j < n; j++) {
			if (seen.count(spotted_cows[j][i]) > 0) {
				dupe = true;
				break;
			}
		}
 
		if (!dupe) { poss_positions++; }
	}
 
	std::ofstream("cownomics.out") << poss_positions << endl;
}


import java.io.*;
import java.util.*;
 
public class BovineGenomics {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("cownomics");
 
		int n = io.nextInt();
		int m = io.nextInt();
 
		char[][] spottedCows = new char[n][];
		char[][] plainCows = new char[n][];
		for (int i = 0; i < n; i++) { spottedCows[i] = io.next().toCharArray(); }
		for (int i = 0; i < n; i++) { plainCows[i] = io.next().toCharArray(); }
 
		int possPositions = 0;
		for (int i = 0; i < m; i++) {
			Set<Character> seen = new HashSet<>();
			for (int j = 0; j < n; j++) { seen.add(plainCows[j][i]); }
 
			boolean dupe = false;
			for (int j = 0; j < n; j++) {
				if (seen.contains(spottedCows[j][i])) {
					dupe = true;
					break;
				}
			}
 
			if (!dupe) { possPositions++; }
		}
 
		io.println(possPositions);
		io.close();
	}
 
	// CodeSnip{Kattio}
}


with open("cownomics.in", "r") as read:
	n, m = map(int, read.readline().split())
 
	spotted_cows = [read.readline() for _ in range(n)]
	plain_cows = [read.readline() for _ in range(n)]
 
poss_positions = 0
for i in range(m):
	seen = set()
	for j in range(n):
		seen.add(plain_cows[j][i])
 
	for j in range(n):
		if spotted_cows[j][i] in seen:
			break
	else:
		poss_positions += 1
 
print(poss_positions, file=open("cownomics.out", "w"))