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)
Get Raw
0001import java.math.BigInteger;
0002
0003public class Nout {
0004 public static String max = "333333333333333333333";
0005 public boolean mod = false;
0006 public String out = "111111111111111111111";
0007
0008 public static void main(String[] args){
0009 Nout n = new Nout();
0010 n.go();
0011 }
0012
0013 public void go(){
0014 while(!this.out.equals(Nout.max)){
0015 this.mod = false;
0016
0017 while(!this.mod){
0018 this.out = this.comp(this.norm(this.out));
0019 }
0020
0021 this.check(this.out);
0022
0023 BigInteger nout = new BigInteger(this.out);
0024 nout = nout.add(new BigInteger("1"));
0025 this.out = nout.toString(0);
0026 this.out = this.comp(out);
0027 }
0028 }
0029
0030 public String comp(String nout){
0031 boolean ex = false;
0032 this.mod = true;
0033
0034 while(!ex){
0035 ex = true;
0036
0037 for(int i = nout.length() - 1;i >= 0;i--){
0038 String sout = String.valueOf(nout.charAt(i));
0039
0040 if(Integer.parseInt(sout) > 3){
0041 if(i == 0){
0042 nout = Nout.max;
0043 }else{
0044 ex = false;
0045 this.mod = false;
0046
0047 nout = nout.substring(0, i - 1) +
0048 Integer.toString(Integer.parseInt(
0049 String.valueOf(nout.charAt(i - 1))) + 1) +
0050 "1" +
0051 nout.substring(i + 1);
0052 }
0053 }
0054 }
0055 }
0056
0057 return nout;
0058 }
0059
0060 public String norm(String nout){
0061 boolean ex = false;
0062
0063 while(!ex){
0064 ex = true;
0065
0066 for(int i = 1;i < nout.length();i++){
0067 if(nout.charAt(i) == nout.charAt(i - 1)){
0068 ex = false;
0069
0070 nout = nout.substring(0, i) +
0071 Integer.toString(Integer.parseInt(
0072 String.valueOf(nout.charAt(i))) + 1) +
0073 nout.substring(i + 1);
0074 }
0075 }
0076 }
0077
0078 return nout;
0079 }
0080
0081 public void check(String nout){
0082 int ac = 10;
0083 int bc = 15;
0084 int cc = 17;
0085 int xa = 0;
0086 int xb = 0;
0087 int xc = 0;
0088
0089 for(int i = 0;i < nout.length();i++){
0090 if(nout.charAt(i) == '1'){
0091 ++xa;
0092 ++xb;
0093 }else if(nout.charAt(i) == '2'){
0094 ++xa;
0095 ++xc;
0096 }else if(nout.charAt(i) == '3'){
0097 ++xb;
0098 ++xc;
0099 }
0100 }
0101
0102 if(xa == ac && xb == bc && xc == cc){
0103 System.out.println(nout);
0104 }
0105 }
0106}
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.
No hay comentarios:
Publicar un comentario