Reto: ¿cuántos caminos hay para llegar al mismo punto?
Contenido del curso
Reto: ¿cuántos caminos hay para llegar al mismo punto?
Contenido del curso
Carlos Eduardo Gomez García
Brandon Fonseca
Stefany Siacara Gil
Guadalupe Monge Barale
Joan Manuel Olvera Lona
Carlos Eduardo Gomez García
Ivan Camilo Buitrago Buitrago
Lariza Sandoval
Jimmy Buriticá Londoño
Edison Renato Valdez Vega
Ilia Adad Infante Trejo
Henry
Jeferson Danilo Castro Becerra
Julian Aranguren
Pablo Rodríguez Cruz
Martín Alejandro Schwindt
Misael Gomez
Pablo Joaquín Cruz
Jorge Ladino Molano
Elver Cucho Nicolas
Carlos Eduardo Gomez García
isaac cruz herrera
Yahday Awad Lara
Daniel Hernandez Talla
ARIEL HORACIO FUHR
John David Gómez Constante
Joan Manuel Olvera Lona
Benjamín Parra
Fernando E. Cueto
Sergio Fernandez
César Luis Amundaray Rodríguez
💪 Este es un reto MUY difícil, no te rindas
. El objetivo de este reto tal cual no es resolverlo, sino que aprendas qué pasos seguir cuando te enfrentas con problemas así de complejos. . Nuestra primera intuición al querer resolver algo es meternos directamente al código y programar, pero nos pasamos por alto evaluar ciertos casos de uso que nos pueden dar una pista para resolver cualquier problema. . Entiendo el sentimiento de frustración cuando no podemos resolver algo, a mí me tomó literalmente días resolverlo hasta que por fin pude, no te rindas, da tu mejor esfuerzo por resolverlo, y si no lo logras no te preocupes, es normal, es un reto difícil. . Pero lo que quiero que te lleves de esta clase es cómo abordar un problema difícil cuando te topas con ellos 💚. . Si lograste resolver el reto, felicidades, y si no, también felicidades porque lo intentaste y diste lo mejor de ti para hacerlo 💪.
si pude!!
Logrado : )
No lo pude hacer antes de ver la explicación del profe, pero creo que ahora le entendí. . Como para no sentirme tan mal le agregue un do while. .
$tienda_anterior = 0; $caminos = 1; do { echo "Teniendo en cuenta que estas en la Tienda número 1 \n"; $tienda_elegida = (int)readline("Ingresa el número de la tienda a la que deseas ir: \n"); } while ($tienda_elegida < 2); for ($i=2 ; $i <= $tienda_elegida ; $i++) { $temporal = $caminos; $caminos += $tienda_anterior; $tienda_anterior = $temporal; // Esto me ayudó a ver el comportamiento // echo "temporal = $temporal Caminos = $caminos Tienda anterior = $tienda_anterior \n"; } echo "Dispones de " . $caminos . " caminos\n";
Cuento mi experiencia. Aunque el problema se me hizo casi imposible al inicio, le di un vistazo a los comentarios y me di con el spoiler de que se trataba de la célebre sucesión de Fibonacci, la cual se puede resolver utilizando funciones recursivas. Como castigo propio por haberme dado la solución, decidí que mi programa debía mostrar no sólo la cantidad de rutas para llegar a la tienda N, sino además debía poder imprimir cada una de ellas. Para encontrar la solución, debí consultar la Teoría de Grafos, el cálculo para obtener la suma de todos los caminos entre el punto A y el punto B (muy interesante, por cierto), y luego de ahí a pasarlo a código de PHP sin utilizar funciones recursivas, fue todo un reto. Les sugiero que habiliten el XDebug y el PHP Debug (si ocupan Visual Studio Code) para depurar el código, a mí me sirvió bastante para ir generando cada uno de los ciclos de las rutas y validar que el array quedara con las rutas correctas.
Ahora, la solución: El razonamiento es que, efectivamente, el camino a la tienda N se da de unir las rutas generadas para N-1 y N-2, entonces, a través de un arreglo, hice el push de las rutas para los números intermedios hasta el número de tienda seleccionado. Luego sólo es contar cuántas rutas hay para el arreglo de la tienda N dado, así como imprimir el ciclo de todos los registros guardados en dicho arreglo. Debido a que noté que mi computadora se quedaba colgada si ponía un valor mayor a 30, limité la captura hasta 30, mientras que la impresión de las rutas está habilitada hasta la tienda 20.
<?php $br = "\n"; $hr = "------------------------------------------------------------------------------------------\n"; $hhr = "==========================================================================================\n"; $rutas = [ 1 => ['1'], 2 => ['1-2'], ]; do { echo `clear`; echo $hhr.'RETO: ¿CUÁNTAS RUTAS HAY DEL PUNTO A AL PUNTO B?'.$br.$hhr; $rutaSelected = readline('Captura la tienda a la que quieres llegar (máximo 30): '); } while (!(is_numeric($rutaSelected)) || $rutaSelected <= 1 || $rutaSelected > 30); if ($rutaSelected > array_key_last($rutas)) { for ($i = array_key_last($rutas) + 1; $i <= $rutaSelected; $i++) { $rutas += [$i => []]; for ($j = 0; $j < count($rutas[$i - 2]); $j++) { array_push($rutas[$i], $rutas[$i - 2][$j].'-'.$i); } for ($k = 0; $k < count($rutas[$i - 1]); $k++) { array_push($rutas[$i], $rutas[$i - 1][$k].'-'.$i); } } } $counter = 0; echo $br.'En total hay '; for ($i = 0; $i < count($rutas[$rutaSelected]); $i++) { $counter++; } echo $counter.' rutas disponibles para llegar de la Tienda 1 a la Tienda '.$rutaSelected.$br; echo $br.$hr; if ($rutaSelected <= 20) { do { $opt = readline('¿Deseas imprimir las posibles rutas generadas? (S/N): '); } while (!($opt === 'S' || $opt === 'N')); if ($opt === 'S') { echo $br.'Las posibles rutas generadas son: '.$br; for ($i = 0; $i < count($rutas[$rutaSelected]); $i++) { echo $i + 1 .":\t".$rutas[$rutaSelected][$i].$br; } } echo $br.$hr; }
Dude! Qué increíble! Me encanta que te hayas puesto tu propio reto 🤩
Inicialmente, la progresión del número de caminos podría sugerir una conexión con la secuencia de Fibonacci. Sin embargo, para este problema específico, la aplicación directa de la lógica de Fibonacci, especialmente en su forma recursiva, presenta serias limitaciones de eficiencia. A medida que el número de tiendas (n) crece, el número de llamadas recursivas y los cálculos repetidos aumentan exponencialmente, lo que resulta en tiempos de ejecución prolongados y un elevado consumo de memoria. La solución más adecuada y eficiente es calcular directamente 2n−1, reflejando las dos opciones independientes de camino entre cada par de tiendas.
function calcularCaminosTiendas(int $n): int{ if ($n <= 1) { return 0; *// O quizás 1 si consideramos estar en la tienda 1 como forma* } return 2 \*\* ($n - 1);} echo calcularCaminosTiendas(10);
Con este reto y el current y el temp, recordé la clase de Algoritmos y Estructuras de datos en la que tanto llore 😂
Sucesión de Fibonacci
tal cual
Mi solución buscando la serie Fibonacci. Hay que notar que se puede obtener hasta el número 1476avo de la sucesión consistente en el valor 1.3069892237634E+308. Más allá PHP me manda valor INF. Quizá con otro algoritmo podamos construir una pila para valores más grandes.
<?php //calculo de la serie de fibonacci hasta un lugar determinado $place = readline("A que tienda quieres llegar: "); $n1 = 1; $n2 = 1; $i = 2; //echo "0, 1, "; while ($i < $place){ $nt = $n2; $n2 = $n1 + $n2; $n1 = $nt; $i++; //echo "$n2, "; }; echo "\n"; echo "La cantidad de caminos hasta la tienda $place son $n2"; echo "\n";
pista: Busca el patrón (sucesión).
**Logre pulir un poco mi logica para este ejercicio **
$TiendaInicial = 0; $TiendaSecundaria = 1; $TiendaDeseada = 9; for ($i = 2; $i <= $TiendaDeseada + 1; $i++) { #empiezo a validar desde la tienda 2 $resultado = $TiendaInicial + $TiendaSecundaria; $TiendaInicial = $TiendaSecundaria; $TiendaSecundaria = $resultado; if ($TiendaDeseada == 1) echo "tu ya estas en la tienda a la que necesitas llegar :V <br>"; if ($i == $TiendaDeseada) echo "para llegar a la tienda " . $i . " se puede llegar de " . $resultado . " maneras" . "<br>"; }
oye me podriar decir como lo hiciste?
Explicación en el código para los que como a mí, nos costó entenderlo
<?php /* 2 -> 1 3 -> 2 4 -> 3 5 -> 5 6 -> 8 7 -> 13 8 -> 21 */ //Variable que especifica hasta que numero de la serie se quiere generar $numero_maximo_serie = 5; //Variables que almacenan los ultimos dos numeros generados en la serie $numero_anterior = 0; $numero_actual = 1; //Ciclo que inicia en 2 ya que los primeros dos numeros de la serie son 0 y 1 for ($i = 2; $i <= $numero_maximo_serie; $i++) { // Creamos una variable temporal para guardar el numero actual antes de sumarlo con el anterior $numero_temporal = $numero_actual; //Nuevo numero generado en la serie es la suma del numero actual y el anterior $numero_actual = $numero_actual + $numero_anterior; //El numero anterior ahora es el numero que se guardo temporalmente $numero_anterior = $numero_temporal; //Se imprime el nuevo numero generado en la serie echo $numero_actual . "\n"; } ?>
Gracias bro, me cuesta entender este problema, soy medio queso. Ja, ja, ja.
@Pablo
quiero compartir lo que pasa dentro del ciclo for
/* Mejor explicacón del código dentro del for Para la tienda 2 $temporal = $actual (su valor es de 1) $actual + $anterior = $actual (1+0= 1) $anterior = $temporal (su valor es de 1) Para la tienda 3 $temporal = $actual (su valor es de 1) $actual + $anterior = $actual (1+1= 2) $anterior = $temporal (su valor es de 1) Para la tienda 4 $temporal = $actual (su valor es de 2) $actual + $anterior = $actual (2+1= 3) $anterior = $temporal (su valor es de 2) Para la tienda 5 $temporal = $actual (su valor es de 3) $actual + $anterior = $actual (3+2= 5) $anterior = $temporal (su valor es de 3) */
Más problemas de este tipo
Este problema es interesante por el hecho de que uno no debe hacer exactamente lo que el enunciado dice como suele pasarnos con los problemas que venimos viendo hasta ahora. Este problema requiere un análisis y cierta capacidad de abstracción para llegar a la conclusión que se trata de la sucesión de Fibonacci. Y, además, cómo calcular Fibonacci es otro tema amplio, ya que para números gigantes (con n = 10^9, por ejemplo) seguramente no basta con calcular término a término (Spoiler: se puede hacer con exponenciación de matrices, pero no viene al caso). Si les gustó este problema, aunque no lo hayan podido resolver, les podría llegar a interesar lo que es la programación competitiva.
¿Qué es la Programación Competitiva?
Es un deporte electrónico que se basa en la resolución de problemas de este tipo en una ventana de tiempo determinada. Hay distintas plataformas en las que pueden encontrar problemas de este tipo.
Recomendaciones si quieren investigar del tema
Plataforma con problemas: https://codeforces.com Libro introductorio: https://cses.fi/book/book.pdf
Mi código (No se si a las patadas pero funciona) xD:
<?php //Creando un array para la secuencia $secuencia = []; //Ingresar la casa de destino: $casa_destino = 8; //Para las 2 primeras posiciones se introducen los valores 1 y 2 if ($casa_destino == 2){ array_push($secuencia,1); } else if ($casa_destino == 3){ array_push($secuencia,1,2); } else{ array_push($secuencia,1,2); for ($i=3; $i < $casa_destino ; $i++) { //cuento el numero de elementos en el array $numero_elem = count($secuencia)-1; $ultimo = $numero_elem; $penultimo = $numero_elem-1; $suma_ultimo_par = $secuencia[$ultimo] + $secuencia[$penultimo]; //creo un ultimo valor con la sumatoria de los 2 ultimos elementos array_push($secuencia,$suma_ultimo_par); } } if ($casa_destino < 2 ) echo "La casa de destino tiene que ser mayor a 1"; else echo "Para ir a la casa $casa_destino, el número posible de caminos es: " . $secuencia[count($secuencia)-1];
porque solo encuentro... 6 -> 7 7 -> 9 8 -> 11 9 ->13 .... en cada caso? :(
Porque seguramente se te está escapando alguno, revisa bien :D
es por que el profe hizo trampa no hay tantos caminos jajaja solo queria que resolvieramos con fibonacci
Mi solución para el reto
<?php $result = 1; $number_store = readline("Escriba a que tienda desea llegar: "); for ($i=1, $a=0; $i < $number_store; $i++) { $result += $a; $a = $result - $a; } echo "Para llegar a la tienda $number_store hay $result caminos diferentes";
Mi solución
$numeroDeseado = 8; $aux = 0; $result = 1; for ($i=1; $i < $numeroDeseado; $i++) { $result = $result + $aux; $aux = $result - $aux; } echo $result;
¿Por que iteran las variables dentro del for(anterior, actual...), si no se declaró la variable $i dentro del for, solo se puso la condición y con que numero inicia el ciclo, pero no dentro del for mismo?
Por definición, la variable $i se declara dentro de la estructura de la sentencia FOR (en la solución está como $i = 2), por lo que no es necesario volver a asignarle valor a la variable $i.
El resto de las variables ya han sido inicializadas antes, excepto $temporal, la cual sólo tiene sentido tenerla viva dentro del ciclo FOR.
Recuerda que, en PHP, la declaración de variables es suficiente con una asignación de valor (en este caso, $i = 2).
<?php $total_de_caminos = 0; $valor_anterior_anterior = 0; $valor_anterior = 1; $punto_camino = readline("Ingrese el punto del camino por el cual desea consultar:"); if($punto_camino > 0){ for($i=1 ; $i<$punto_camino; $i++){ $total_de_caminos = ($valor_anterior + $valor_anterior_anterior); $valor_anterior_anterior = $valor_anterior; $valor_anterior = $total_de_caminos; } echo "el número de caminos posibles hasta el punto $punto_camino es: $total_de_caminos"; } else{ echo "Debe ingresar un valor superior a 1. \n"; } ?>
Ejercicios como este son los que se encuentra uno en entrevistas de trabajo, ya sea en live coding o a través de plataformas con tiempo limite. Que bueno que hayan incluido este tipo de ejemplos, ojalá lo sigan haciendo en este y otros cursos. También sería bueno que Platzi incluyera un curso orientado a resolver este tipo de retos, estilo Cracking de Coding Interview, es muy frustrante durante un proceso de selección para un trabajo no poder finalizarlo a tiempo o quedarte congelado y no poder avanzar.
Considerando que es Fibonacci yo utilicé la fórmula:
<?php function fibonacci_formula($n) { $phi = (1 + sqrt(5)) / 2; $psi = (1 - sqrt(5)) / 2; return (int) round((pow($phi, $n) - pow($psi, $n)) / sqrt(5)); }; echo fibonacci_formula((int) readline("Enter a number: ")); echo "\n"; ?>
Uff, sí me puso a pensar, pero logré hacerlo sin ver el video ni los comentarios.
$tienda_a_llegar = readline("¿A cuál tienda quieres llegar? "); $formas_de_llegar = array(0,1); if($tienda_a_llegar < 2) { echo "Introduzca un número mayor a 1"; } if($tienda_a_llegar > 99) { echo "Introduzca un número menor a 99"; } else{ for($i = 2; $i < 100; $i++){ $nueva_forma_de_llegar = $formas_de_llegar[$i-1] + $formas_de_llegar[$i-2]; array_push($formas_de_llegar, $nueva_forma_de_llegar); foreach ($formas_de_llegar as $caminos) { if($tienda_a_llegar == $i){ echo " HAY $formas_de_llegar[$i] FORMAS DE LLEGAR A LA TIENDA $i \n\n"; break; }; } } }
