Resolvendo problemas combinatórios com LINQ

Introdução

Olá amigos!

Em primeiro lugar, gostaria de agradecer a todos que têm deixados seus comentários em meus artigos anteriores! Obrigado pelo incentivo!

Navegando por mares pouco navegados, certo dia me deparei com um post interessante em um blog, que propunha a seguinte questão (o original é em inglês, a tradução é minha).

Encontre um número contendo 9 dígitos, sendo que cada um desses dígitos apareça uma única vez. Este número também precisa satisfazer os seguintes requisitos de divisibilidade:

· número deve ser divisível por 9;

· Se o número mais à direita for removido, o número resultante deve ser divisível por 8;

· Se o número mais à direita do novo número também for removido, o número resultante deve ser divisível por 7;

· E assim segue, até que haja apenas um único dígito (que necessariamente será divisível por 1).

O autor apresenta uma solução em C++, que pela própria natureza da linguagem, se apresenta em uma forma mais convencional, mais estruturada. Depois de analisar sua solução, resolvi propor uma nova abordagem (já que tenho o privilégio de ser um desenvolvedor C#): LINQ!

Mais um desafio para o LINQ

Achei que LINQ serviria como uma luva para a resolução deste tipo de problema exploratório, onde há a necessidade de se contemplar uma árvore de possíveis combinações e realizar rastreamento reverso (backtracking) em caminhos “sem-saída” assim que são encontrados.

Em uma query LINQ, as claúsulas from em cascata servem como geradores de combinações, enquanto as cláusulas where determinam os pontos de falha que acionam o rastreamento reverso. A primeira vez que vi esta técnica em uso foi em um post chamado Using LINQ to solve puzzles, de Luke Hoban, um membro do Microsoft Languages Team.

O código abaixo mostra a implementação de uma solução para o problema, a qual se mostra um bom exemplo do enorme poder expressivo do LINQ.

// Solução em C# and LINQ para o problema apresentado em:
http://software.intel.com/en-us/blogs/2009/12/07/intel-parallel-studio-great-for-serial-code-too-episode-1/

int[] umAteNove = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

// the query 
var query = from i1 in umAteNove 
	from i2 in umAteNove 
		where i2 != i1 && ((i1 * 10) + i2) % 2 == 0 
	from i3 in umAteNove 
		where i3 != i2 && i3 != i1 && 
			((i1 * 100) + (i2 * 10) + i3) % 3 == 0 
	from i4 in umAteNove 
		where i4 != i3 && 
			i4 != i2 && 
			i4 != i1 && 
			((i1 * 1000) + (i2 * 100) + (i3 * 10) + i4) % 4 == 0
	from i5 in umAteNove 
		where i5 != i4 && 
			i5 != i3 && 
			i5 != i2 && 
			i5 != i1 && 
			((i1 * 10000) + (i2 * 1000) + (i3 * 100) + 
			(i4 * 10) + i5) % 5 == 0 
	from i6 in umAteNove 
		where i6 != i5 && 
			i6 != i4 && 
			i6 != i3 && 
			i6 != i2 && 
			i6 != i1 && 
			((i1 * 100000) + (i2 * 10000) + (i3 * 1000) + (i4 * 100) + 
			(i5 * 10) + i6) % 6 == 0 
	from i7 in umAteNove 
		where i7 != i6 && 
			i7 != i5 && 
			i7 != i4 && 
			i7 != i3 && 
			i7 != i2 && 
			i7 != i1 && 
			((i1 * 1000000) + (i2 * 100000) + (i3 * 10000) + (i4 * 1000) + 
			(i5 * 100) + (i6 * 10) + i7) % 7 == 0 
	from i8 in umAteNove 
		where i8 != i7 && 
			i8 != i6 && 
			i8 != i5 && 
			i8 != i4 && 
			i8 != i3 && 
			i8 != i2 && 
			i8 != i1 && 
			((i1 * 10000000) + i2 * (1000000) + (i3 * 100000) + (i4 * 10000) + 
			(i5 * 1000) + (i6 * 100) + (i7 * 10) + i8) % 8 == 0 
	from i9 in umAteNove 
		where i9 != i8 && 
			i9 != i7 && 
			i9 != i6 && 
			i9 != i5 && 
			i9 != i4 && 
			i9 != i3 && 
			i9 != i2 && 
			i9 != i1 
	let number = (i1 * 100000000) + (i2 * 10000000) + (i3 * 1000000) + 
		(i4 * 100000) + (i5 * 10000) + (i6 * 1000) + (i7 * 100) + (i8 * 10) + i9 
		where number % 9 == 0
	select number;

	// run it!
	foreach (int n in query) 
		Console.WriteLine(n);

Notem que nenhuma tentativa de otimização da query foi realizada (por exemplo, aplicar critérios individuais de divisibilidade para as diferentes posições). Existe um máxima no meio dos puzzles que diz que “otimização antes da hora é a raiz de todo mal”. Eu acredito piamente nesta afirmação! Além do mais, este código gerou o número 381654729 em bem menos de um segundo na minha máquina, o que está mais do que satisfatório para mim!

Conclusão

Utilizar uma abordagem de problemas complexos com LINQ é uma maneira eficiente e elegante para criar soluções que fujam do lugar comum do desenvolvimento estruturado.

Como resolução de quebra-cabeças lógicos é uma paixão que tenho desde que me conheço por desenvolvedor, fiquei inclinado a escrever este artigo. Espero ter ilustrado alguns conceitos úteis para você, amigo leitor!