Alters

Javacertijo - Ping Pong

Buenas!

En esta entrega os traigo un tema totalmente distinto.

Resulta que mi buen amigo KomiBlanka hoy me ha planteado un reto, que ahora os traslado (solucionado).

¿Os pica la curiosidad?

¡Vamos allá!


El reto viene en forma de acertijo, que dice algo como

"En una aburrida tarde, Alberto, Bernardo, y Carlos deciden jugar un rey de la pista al ping-pong (Rey de la pista: típico sistema que se basa en "tú y yo y el que gane contra él").

De esta manera, Alberto juega 10 partidas, Bernardo juega 15 y Carlos juega 17.

Se nos pide saber quién pierde la segunda partida, suponiendo que el primer juego es Alberto vs. Bernardo".

Aplicando lógica se puede sacar, pero nosotros decidimos hacer un método de fuerza bruta (al que yo doté con cierta inteligencia para descartar casos inválidos).

Para empezar, vamos a abreviar a "A", "B", y "C" los nombres de los jugadores. Por otra parte, ¿cuántas partidas se juegan?

La solución es (Pa + Pb + Pc) / 2 = (10 + 15 + 17) / 2 = 42 / 2 = 21

Por otra parte, haremos la siguiente simplificación:

A vs. B = 1
A vs. C = 2
B vs. C = 3

Cualquier otra combinación sería repetir 1, 2, o 3, por lo que las descartamos. Con esto, podemos escribir la tarde como una serie de 21 números en el rango [1, 2, 3], como, por ejemplo:

111111111111111111111
...
333333333333333333333

Esto nos da 3^21 combinaciones (10.460.353.203). Aplicando la lógica, podemos asumir que nunca se pueden repetir dos números, por lo que el número más bajo sería

121212121212121212121

y el siguiente no podría ser [...]22, si no [...]23. Esto reduce asombrosamente la cantidad de elementos a investigar.

Finalmente, con la racionalización de las partidas, podemos extraer la inversa a los datos para saber cuántas partidas ha jugado cada uno, con lo que habría que analizar esos datos para cada uno de los casos válidos.

Poniéndolo todo en común, nos sale el siguiente código (java)


[code lan=gral] import java.math.BigInteger; public class Nout { public static String max = ~"333333333333333333333~"; public boolean mod = false; public String out = ~"111111111111111111111~"; public static void main(String[] args){ Nout n = new Nout(); n.go(); } public void go(){ while(!this.out.equals(Nout.max)){ this.mod = false; while(!this.mod){ this.out = this.comp(this.norm(this.out)); } this.check(this.out); BigInteger nout = new BigInteger(this.out); nout = nout.add(new BigInteger("1")); this.out = nout.toString(0); this.out = this.comp(out); } } public String comp(String nout){ boolean ex = false; this.mod = true; while(!ex){ ex = true; for(int i = nout.length() - 1;i >= 0;i--){ String sout = String.valueOf(nout.charAt(i)); if(Integer.parseInt(sout) > 3){ if(i == 0){ nout = Nout.max; }else{ ex = false; this.mod = false; nout = nout.substring(0, i - 1) + Integer.toString(Integer.parseInt( String.valueOf(nout.charAt(i - 1))) + 1) + "1" + nout.substring(i + 1); } } } } return nout; } public String norm(String nout){ boolean ex = false; while(!ex){ ex = true; for(int i = 1;i < nout.length();i++){ if(nout.charAt(i) == nout.charAt(i - 1)){ ex = false; nout = nout.substring(0, i) + Integer.toString(Integer.parseInt( String.valueOf(nout.charAt(i))) + 1) + nout.substring(i + 1); } } } return nout; } public void check(String nout){ int ac = 10; int bc = 15; int cc = 17; int xa = 0; int xb = 0; int xc = 0; for(int i = 0;i < nout.length();i++){ if(nout.charAt(i) == '1'){ ++xa; ++xb; }else if(nout.charAt(i) == '2'){ ++xa; ++xc; }else if(nout.charAt(i) == '3'){ ++xb; ++xc; } } if(xa == ac && xb == bc && xc == cc){ System.out.println(nout); } } } [/code]

La explicación del código sigue como va:

En "comp" buscamos el siguiente número válido (si algún dígito es mayor de 3, lo pasamos a 1 e incrementamos la siguiente cifra).

En "norm" comprobamos si la estructura del número es correcta. Para ello comparamos el valor con su vecino y en caso de coincidir incrementamos el valor en 1.

Finalmente, el flujo que hacemos es "norm" + "comp", habiendo en "comp" una variable que determina si se ha cambiado algo. En caso que se haya cambiado algo, se vuelve a realizar "norm" + "comp".

Una vez tenemos el número, pasamos a "check", que mira si cumple las condiciones.

Y para terminar... ¿La solución?

Pues hay bastantes combinaciones que cumplen la proporción de partidas, pero en TODAS, en la tercera posición tenemos un "3", lo que quiere decir que en la tercera partida juegan "B vs. C", por lo que en todos los casos, "A" ha perdido.