E11 Parafuso e porcas
Temos uma coleção de \(N\) parafuso e $N$ porcas de tamanhos variados. Sabemos que existe um pareamento entre os $N$ parafusos e as $N$ porcas de forma que os elementos pareados encaixam-se perfeitamente. Isto é, se um parafuso $p$ está pareado com uma porca $p'$, então $p$ e $p'$ encaixam-se perfeitamente. Podemos chamar tal pareamento de "pareamento completo" ou "pareamento perfeito", pois todos os $N$ parafusos e todas as $N$ porcas estão pareados.
Para encontrar um tal pareamento, a única operação que podemos fazer é escolher um parafuso $p$ e uma porca $p'$ e experimentar. Há três possíveis resultados para esse experimento: (1) $p$ e $p'$ encaixam-se perfeitamente, (2) $p$ é muito grande para $p'$, (3) $p$ é muito pequeno para $p'$. Queremos encontrar um pareamento perfeito fazendo "poucos" experimentos como esse. É fácil ver que podemos resolver esse problema executando no máximo $N^2$ experimentos.
Queremos algo bem melhor: sua tarefa é encontrar e implementar um algoritmo linearítmico para este problema. Detalhes sobre a implementação seguem abaixo.
Classes já implementadas. São dadas abaixo as classes
- GenerateAndMatch.java
- NutsAndBolts.java
- pieces/Nut.java
- pieces/Bolt.java
Por um certo motivo técnico, Nut.java e Bolt.java estão organizados em um "package".
Objetos do tipo Bolt representam parafusos; objetos do tipo Nut representam porcas. Um objeto do tipo NutsAndBolts representa uma coleção de $N$ parafusos e $N$ porcas, para algum $N$.
Dado $N$, o programa GenerateAndMatch.java gera uma coleção de aleatória de $N$ parafusos e $N$ porcas que admite um pareamento perfeito, e encontra um pareamento perfeito entre eles, chamando o método match() de Match.java, que não é dado abaixo.
O usuário de GenerateAndMatch.java também fornece um outro parâmetro $t$ ao programa: esse parâmetro especifica qual é a quantidade de porcas e parafusos distintos existentes (no universo dos parafusos e porcas do qual escolheremos os $N$ parafusos e as $N$ porcas).
Por exemplo, se $t = 1$, então só há um tipo de parafuso e um tipo de porca, de forma que qualquer pareamento entre os $N$ parafusos e as $N$ porcas é um pareamento perfeito. Se $t = 2$, há somente dois tipos de parafusos e porcas, e assim por diante.
Sua tarefa. O programa GenerateAndMatch.java depende da classe Match.java, que está faltando. Neste exercício, você deve escrever Match.java para que GenerateAndMatch.java funcione. Para entender em detalhe o que a função match() de Match.java deve fazer, você precisa ler as classes fornecidas. A seguir, descrevemos sucintamente como deve ser o comportamento de match(). A assinatura de match() deve ser
public static int[] match(NutsAndBolts nab)
Ao receber o objeto nab, sua função deve devolver um pareamento perfeito para aquele objeto. Tal pareamento é dado por um vetor de inteiros, digamos $p$, de $N$ elementos, que é uma permutação de $0,\dots, N - 1$. O vetor $p$ deve ter a seguinte propriedade: o método
public int check(int[] p)
de NutsAndBolts.java deve devolver $-1$ quando executamos nab.check(p).
Sua função match() deve produzir o pareamento $p$ executando chamadas aos métodos compareTo() em Bolt.java e Nut.java para comparar as porcas e os parafusos.
Exemplo. Suponha que as porcas e parafusos no objeto nab têm as dimensões dadas abaixo:
0 1 2 3 4 5 6 7 8 9
93 82 5 80 96 73 47 77 99 0
99 77 73 80 47 0 96 82 5 93
Assim, a porca $0$ tem dimensão $93$, a porca $1$ tem dimensão $82$, etc. O parafuso $0$ tem dimensão $99$, o parafuso $1$ tem dimensão $77$, etc. Para esta coleção de $10$ parafusos e $10$ porcas, seu match() deve devolver o vetor
p = { 9, 7, 8, 3, 6, 2, 4, 1, 0, 5 }
De fato, a porca $0$ e o parafuso $p[0] = 9$ têm a mesma dimensão, a porca $1$ e o parafuso $p[1] = 7$ têm a mesma dimensão, etc, de forma que nab.check(p) devolverá $-1$.
Desempenho. Seu match() deve ter eficiência grosso modo comparável com o que você pode ver nos exemplos de execução em experiments*.txt.
Entrega. Você deve entregar somente a classe Match.java, que será testada conjuntamente com as classes dadas abaixo, exatamente do jeito que estão. Em particular, se você alterar algumas das classes dadas e escrever seu Match.java compatível com suas novas classes, seu Match.java poderá não funcionar quando o monitor rodar os testes.
Observação. As classes Nut.java e Bolt.java fornecidas usam o mecanismo de "packages" para que objetos do tipo Nut possam ter acesso à dimensão de um objeto do tipo Bolt e vice-versa. Ademais, com esse mecanismo, objetos fora desse package não têm acesso a essas informações. Assim, escondemos dos clientes de Nut.java e Bolt.java a dimensão desses objetos, e forçamos o uso dos métodos compareTo() entre eles (como especificado acima). Você pode ler mais sobre essas coisas em
https://docs.oracle.com/javase/tutorial/java/javaOO/accesscontrol.html
Se você tivesse acesso às dimensões dos parafusos e porcas, você poderia fazer algo semelhante ao que é feito em Pair.java em
https://www.ime.usp.br/~yoshi/2021ii/mac0121/sandbox/2021.11.04/
Como você não tem acesso às dimensões e só pode comparar porcas e parafusos com os métodos compareTo() em Nut.java e Bolt.java, você precisa fazer algo diferente :-)
Observação (adicionada 5/11/2021). O algoritmo elementar quadrático mencionado de passagem no começo do enunciado (segundo parágrafo) está implementando na classe Match.java agora fornecida abaixo. Fiz outros pequenos ajustes no material disponibilizado. Faça download desse material novamente.
- 5 November 2021, 8:07 AM
- 5 November 2021, 8:07 AM