Reto: ¿cuántos caminos hay para llegar al mismo punto?

Clase 13 de 25 • Curso de PHP: Arreglos, Funciones y Estructuras de Control

Carlos Eduardo Gomez García

teacher•

💪 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 💪.

Brandon Fonseca

student•

si pude!!

Stefany Siacara Gil

student•

Logrado : )

Guadalupe Monge Barale

student•

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";

Joan Manuel Olvera Lona

student•

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;
}

Carlos Eduardo Gomez García

teacher•

Dude! Qué increíble! Me encanta que te hayas puesto tu propio reto 🤩

Ivan Camilo Buitrago Buitrago

student•

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);

Lariza Sandoval

student•

Con este reto y el current y el temp, recordé la clase de Algoritmos y Estructuras de datos en la que tanto llore 😂

Jimmy Buriticá Londoño

student•

Sucesión de Fibonacci

Edison Renato Valdez Vega

student•

tal cual

Ilia Adad Infante Trejo

student•

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";

Henry

student•

pista: Busca el patrón (sucesión).

Jeferson Danilo Castro Becerra

student•

**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>";          
}

Julian Aranguren

student•

oye me podriar decir como lo hiciste?

Pablo Rodríguez Cruz

student•

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";
}
?>

Martín Alejandro Schwindt

student•

Gracias bro, me cuesta entender este problema, soy medio queso. Ja, ja, ja.

Misael Gomez

student•

@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)
 */

Pablo Joaquín Cruz

student•

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

Jorge Ladino Molano

student•

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];

Elver Cucho Nicolas

student•

porque solo encuentro... 6 -> 7 7 -> 9 8 -> 11 9 ->13 .... en cada caso? :(

Carlos Eduardo Gomez García

teacher•

Porque seguramente se te está escapando alguno, revisa bien :D

isaac cruz herrera

student•

es por que el profe hizo trampa no hay tantos caminos jajaja solo queria que resolvieramos con fibonacci

Yahday Awad Lara

student•

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";

Daniel Hernandez Talla

student•

Mi solución

$numeroDeseado = 8;
$aux = 0;
$result = 1;
for ($i=1; $i < $numeroDeseado; $i++) { 
    $result = $result + $aux;
    $aux = $result - $aux;
}
echo $result;

John David Gómez Constante

student•

¿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?

Joan Manuel Olvera Lona

student•

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).

Benjamín Parra

student•

<?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";
}

?>

Fernando E. Cueto

student•

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.

Sergio Fernandez

student•

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";

?>

César Luis Amundaray Rodríguez

student•

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;
            };
        }
    }
}

Brandon Valentin Olaya Leguizamo

student•

Al principio pensé que se podía devolver, solo pude hacer el camino par, impar, y el del centro. Eso pasa por no leer bien o escuchar, luego de quemarme la cabeza volví a mirar y bueno toco replantearse

<?php

$number_stores = readline ("Write how mane houses are there: ");
$store = array();

for ($i=1; $i <= $number_stores; $i++) { 
    array_push($store, $i);
}
$start = readline("where am I?: ");
$finally = readline("Where I want arrive?: ");
$before_store = 0;
$currenly = 1;
if ($start < $finally) {
    for ( $i = array_search( $start, $store ) ; $i < array_search( $finally, $store ); $i++) { 
        $temporary = $currenly;
        $currenly += $before_store;
        $before_store = $temporary;
    }
    echo "there are " . $currenly . " to arrive" . "\n";
}
elseif($start > $finally){
    echo "Sorry, This program isn't going backwards" . "\n";
}else{
    echo "I'm at the same store" . "\n";
}

?>