Skip to main content
add numeric solution
Origen Enlace
user368971
user368971

introducir la descripción de la imagen aquí que la pregunta puede mejorarse, pero la respondo ya que, en mi opinión, es un caso especial no visto con mucha frecuencia en el sitio.

Así que si no puedes reproducir mis resultados (del mismo modo que yo no puedo reproducir los tuyos ni los de la otra persona que respondió), puede ser porque después de cierto punto las iteraciones hacen que los valores crezcan tanto que el lenguaje de programación que utilizaste comienza a comportarse de esta manerainesperadamente. También es posible queEn mi código esté incorrecto (posiblemente porque programe a la ligera), peroopinion la respuesta a esta cuestiónque busca el reclutador no radica en el código en sí, sino en el enfoque que se le debe dar.

En ese ordenEditado

Gracias a una respuesta de ideasun usuario, como datome percate de interés, lo que voy a compartir es el código de una posible implementación en Python con la librería NumPy. La probé con algunos valores bajos ysolucion numerica al problema se comporta según lo deseado, pero como mencioné antes, puede encontrar evitando que con valores grandes sea necesario hacer ajusteslos numeros crescan sin control aplicando el % modulo internamente en lugares donde no afectan el resultado final.

import numpy as np

mod = 10000000000
# A y B son matrices, no son var_A ni var_B
def matrix_mult(A, B):
    return np.dot(A, B) % mod

def matrix_pow(mat, exp):
    result = np.eye(len(mat), dtype='object')
    base = mat.copy()

    while exp > 0:
        if exp % 2 == 1:
            result = matrix_mult(result, base)
        base = matrix_mult(base, base)
        exp //= 2

    return result

def solucionar_rompecabezas(N):
    mod = 10000000000
    T = np.array([[0, 1, 0, 0],
                  [0, 0, 1, 0],
                  [0, 0, 0, 1],
                  [1, 4, 1, 3]], dtype='object')
    
    initial_state = np.array([1, 1, 1, 1], dtype='object')
    
    T_N = matrix_pow(T, N)
    final_state = matrix_mult(T_N, initial_state) % mod
    
    return final_state[3]

print(solucionar_rompecabezas(10))
print(solucionar_rompecabezas(100))
print(solucionar_rompecabezas(pow(2023, 100)))

Editado Al ejecutarlo, notarán que para n=10n=10, el bucle while se repite 4 veces; para n=100n=100, se repite 7 veces; y para n=pot(2023,100)n=pot(2023,100) después de cambiar el dtype en NumPy de int a object, me di cuenta de que no se puede llegar (aunque sea mas eficiente el algoritmo el numero sigue siendo muy grande). Sin embargo, con valores de N=1000000 ya se puede evidenciar la diferencia en rendimiento entre esta solución y la solución trivial.

resultados: N=10 902441 N=100 8042318513Finalmente tras varias ediciones el codigo propuesto permite encontrar las soluciones numericas para los tres valores de N dados.

resultados:
N=10 902441
N=100 8042318513
N=23^100 3548910009

introducir la descripción de la imagen aquí que la pregunta puede mejorarse, pero la respondo ya que, en mi opinión, es un caso especial no visto con mucha frecuencia en el sitio.

Así que si no puedes reproducir mis resultados (del mismo modo que yo no puedo reproducir los tuyos ni los de la otra persona que respondió), puede ser porque después de cierto punto las iteraciones hacen que los valores crezcan tanto que el lenguaje de programación que utilizaste comienza a comportarse de esta manera. También es posible que mi código esté incorrecto (posiblemente porque programe a la ligera), pero la respuesta a esta cuestión no radica en el código en sí, sino en el enfoque que se le debe dar.

En ese orden de ideas, como dato de interés, lo que voy a compartir es el código de una posible implementación en Python con la librería NumPy. La probé con algunos valores bajos y se comporta según lo deseado, pero como mencioné antes, puede que con valores grandes sea necesario hacer ajustes.

import numpy as np

# A y B son matrices, no son var_A ni var_B
def matrix_mult(A, B):
    return np.dot(A, B)

def matrix_pow(mat, exp):
    result = np.eye(len(mat), dtype='object')
    base = mat.copy()

    while exp > 0:
        if exp % 2 == 1:
            result = matrix_mult(result, base)
        base = matrix_mult(base, base)
        exp //= 2

    return result

def solucionar_rompecabezas(N):
    mod = 10000000000
    T = np.array([[0, 1, 0, 0],
                  [0, 0, 1, 0],
                  [0, 0, 0, 1],
                  [1, 4, 1, 3]], dtype='object')
    
    initial_state = np.array([1, 1, 1, 1], dtype='object')
    
    T_N = matrix_pow(T, N)
    final_state = matrix_mult(T_N, initial_state) % mod
    
    return final_state[3]

print(solucionar_rompecabezas(10))
print(solucionar_rompecabezas(100))
print(solucionar_rompecabezas(pow(2023, 100)))

Editado Al ejecutarlo, notarán que para n=10n=10, el bucle while se repite 4 veces; para n=100n=100, se repite 7 veces; y para n=pot(2023,100)n=pot(2023,100) después de cambiar el dtype en NumPy de int a object, me di cuenta de que no se puede llegar (aunque sea mas eficiente el algoritmo el numero sigue siendo muy grande). Sin embargo, con valores de N=1000000 ya se puede evidenciar la diferencia en rendimiento entre esta solución y la solución trivial.

resultados: N=10 902441 N=100 8042318513

que la pregunta puede mejorarse, pero la respondo ya que, en mi opinión, es un caso especial no visto con mucha frecuencia en el sitio.

Así que si no puedes reproducir mis resultados, puede ser porque después de cierto punto las iteraciones hacen que los valores crezcan tanto que el lenguaje de programación que utilizaste comienza a comportarse inesperadamente. En mi opinion la respuesta que busca el reclutador no radica en el código en sí, sino en el enfoque que se le debe dar.

Editado

Gracias a una respuesta de un usuario, me percate de que la solucion numerica al problema se puede encontrar evitando que los numeros crescan sin control aplicando el % modulo internamente en lugares donde no afectan el resultado final.

import numpy as np

mod = 10000000000
# A y B son matrices, no son var_A ni var_B
def matrix_mult(A, B):
    return np.dot(A, B) % mod

def matrix_pow(mat, exp):
    result = np.eye(len(mat), dtype='object')
    base = mat.copy()

    while exp > 0:
        if exp % 2 == 1:
            result = matrix_mult(result, base)
        base = matrix_mult(base, base)
        exp //= 2

    return result

def solucionar_rompecabezas(N):
    T = np.array([[0, 1, 0, 0],
                  [0, 0, 1, 0],
                  [0, 0, 0, 1],
                  [1, 4, 1, 3]], dtype='object')
    
    initial_state = np.array([1, 1, 1, 1], dtype='object')
    
    T_N = matrix_pow(T, N)
    final_state = matrix_mult(T_N, initial_state) % mod
    
    return final_state[3]

print(solucionar_rompecabezas(10))
print(solucionar_rompecabezas(100))
print(solucionar_rompecabezas(pow(2023, 100)))

Editado

Finalmente tras varias ediciones el codigo propuesto permite encontrar las soluciones numericas para los tres valores de N dados.

resultados:
N=10 902441
N=100 8042318513
N=23^100 3548910009
Publicación recuperada por gbianchi
Publicación eliminada por user368971
close code snipet
Origen Enlace
user368971
user368971

[![introducir la descripción de la imagen aquí][1]][1]introducir la descripción de la imagen aquí Sé que la pregunta puede mejorarse, pero la respondo ya que, en mi opinión, es un caso especial no visto con mucha frecuencia en el sitio.

[![introducir la descripción de la imagen aquí][2]][2]introducir la descripción de la imagen aquí

[![introducir la descripción de la imagen aquí][3]][3]introducir la descripción de la imagen aquí

>print(2023 ** 100)
>3977299330281882403306574735225337717599631172062412445045578274405450110120677174505186273779312535365746310019472644285894036169695910906506233118452300676652476856018828588020899113867978825566482076357081191135854217234411796915745355130981797659740171549912770735205485217369751214708750973368807626092441067706281896347276001
 
**Fin edicion**


  [1]: https://i.sstatic.net/fzNM3Og6.png
  [2]: https://i.sstatic.net/xV6Voaxi.png
  [3]: https://i.sstatic.net/9ntF8gbK.png

Fin edicion

[![introducir la descripción de la imagen aquí][1]][1] Sé que la pregunta puede mejorarse, pero la respondo ya que, en mi opinión, es un caso especial no visto con mucha frecuencia en el sitio.

[![introducir la descripción de la imagen aquí][2]][2]

[![introducir la descripción de la imagen aquí][3]][3]

>print(2023 ** 100)
>3977299330281882403306574735225337717599631172062412445045578274405450110120677174505186273779312535365746310019472644285894036169695910906506233118452300676652476856018828588020899113867978825566482076357081191135854217234411796915745355130981797659740171549912770735205485217369751214708750973368807626092441067706281896347276001
 
**Fin edicion**


  [1]: https://i.sstatic.net/fzNM3Og6.png
  [2]: https://i.sstatic.net/xV6Voaxi.png
  [3]: https://i.sstatic.net/9ntF8gbK.png

introducir la descripción de la imagen aquí Sé que la pregunta puede mejorarse, pero la respondo ya que, en mi opinión, es un caso especial no visto con mucha frecuencia en el sitio.

introducir la descripción de la imagen aquí

introducir la descripción de la imagen aquí

>print(2023 ** 100)
>3977299330281882403306574735225337717599631172062412445045578274405450110120677174505186273779312535365746310019472644285894036169695910906506233118452300676652476856018828588020899113867978825566482076357081191135854217234411796915745355130981797659740171549912770735205485217369751214708750973368807626092441067706281896347276001

Fin edicion

fix code to deal with big int numbers, and edit code description.
Origen Enlace
user368971
user368971

introducir la descripción de la imagen aquí [![introducir la descripción de la imagen aquí][1]][1] Sé que la pregunta puede mejorarse, pero la respondo ya que, en mi opinión, es un caso especial no visto con mucha frecuencia en el sitio.

introducir la descripción de la imagen aquí [![introducir la descripción de la imagen aquí][2]][2]

introducir la descripción de la imagen aquí [![introducir la descripción de la imagen aquí][3]][3]

import numpy as np

# A y B son matrices, no son var_A ni var_B
def matrix_mult(A, B):
    return np.dot(A, B)

def matrix_pow(mat, exp):
    result = np.eye(len(mat), dtype=intdtype='object')
    base = mat.copy()

    while exp > 0:
        if exp % 2 == 1:
            result = matrix_mult(result, base)
        base = matrix_mult(base, base)
        exp //= 2

    return result

def solucionar_rompecabezas(N):
    mod = 10000000000
    T = np.array([[0, 1, 0, 0],
                  [0, 0, 1, 0],
                  [0, 0, 0, 1],
                  [1, 4, 1, 3]], dtype=intdtype='object')
    
    initial_state = np.array([1, 1, 1, 1], dtype=intdtype='object')
    
    T_N = matrix_pow(T, N)
    final_state = matrix_mult(T_N, initial_state) % mod
    
    return final_state[3]

print(solucionar_rompecabezas(10))
print(solucionar_rompecabezas(100))
print(solucionar_rompecabezas(pow(2023, 100)))

AlEditado Al ejecutarlo, notarán que para n = 10n=10n=10, el bucle while se repite 4 veces; para n = 100n=100n=100, se repite 7 veces; y para n = potn=pot(2023, 100100), asumiendo que Python maneje números tan grandes sin problemas, el bucle se repite 1099 veces. Este número de repeticiones es relativamente bajo en comparación con potn=pot(2023, 100100) después de cambiar el dtype en NumPy de int a object, me di cuenta de que seríano se puede llegar (aunque sea mas eficiente el número de iteraciones enalgoritmo el bucle fornumero sigue siendo muy grande). Sin embargo, con valores de una implementaciónN=1000000 ya se puede evidenciar la diferencia en rendimiento entre esta solución y la solución trivial.

resultados: N=10 902441 N=100 8042318513

dato de interes:

>print(2023 ** 100)
>3977299330281882403306574735225337717599631172062412445045578274405450110120677174505186273779312535365746310019472644285894036169695910906506233118452300676652476856018828588020899113867978825566482076357081191135854217234411796915745355130981797659740171549912770735205485217369751214708750973368807626092441067706281896347276001

**Fin edicion**


  [1]: https://i.sstatic.net/fzNM3Og6.png
  [2]: https://i.sstatic.net/xV6Voaxi.png
  [3]: https://i.sstatic.net/9ntF8gbK.png

introducir la descripción de la imagen aquí Sé que la pregunta puede mejorarse, pero la respondo ya que, en mi opinión, es un caso especial no visto con mucha frecuencia en el sitio.

introducir la descripción de la imagen aquí

introducir la descripción de la imagen aquí

import numpy as np

# A y B son matrices, no son var_A ni var_B
def matrix_mult(A, B):
    return np.dot(A, B)

def matrix_pow(mat, exp):
    result = np.eye(len(mat), dtype=int)
    base = mat.copy()

    while exp > 0:
        if exp % 2 == 1:
            result = matrix_mult(result, base)
        base = matrix_mult(base, base)
        exp //= 2

    return result

def solucionar_rompecabezas(N):
    mod = 10000000000
    T = np.array([[0, 1, 0, 0],
                  [0, 0, 1, 0],
                  [0, 0, 0, 1],
                  [1, 4, 1, 3]], dtype=int)
    
    initial_state = np.array([1, 1, 1, 1], dtype=int)
    
    T_N = matrix_pow(T, N)
    final_state = matrix_mult(T_N, initial_state) % mod
    
    return final_state[3]

print(solucionar_rompecabezas(10))
print(solucionar_rompecabezas(100))
print(solucionar_rompecabezas(pow(2023, 100)))

Al ejecutarlo, notarán que para n = 10, el bucle while se repite 4 veces; para n = 100, se repite 7 veces; y para n = pot(2023, 100), asumiendo que Python maneje números tan grandes sin problemas, el bucle se repite 1099 veces. Este número de repeticiones es relativamente bajo en comparación con pot(2023, 100), que sería el número de iteraciones en el bucle for de una implementación trivial.

[![introducir la descripción de la imagen aquí][1]][1] Sé que la pregunta puede mejorarse, pero la respondo ya que, en mi opinión, es un caso especial no visto con mucha frecuencia en el sitio.

[![introducir la descripción de la imagen aquí][2]][2]

[![introducir la descripción de la imagen aquí][3]][3]

import numpy as np

# A y B son matrices, no son var_A ni var_B
def matrix_mult(A, B):
    return np.dot(A, B)

def matrix_pow(mat, exp):
    result = np.eye(len(mat), dtype='object')
    base = mat.copy()

    while exp > 0:
        if exp % 2 == 1:
            result = matrix_mult(result, base)
        base = matrix_mult(base, base)
        exp //= 2

    return result

def solucionar_rompecabezas(N):
    mod = 10000000000
    T = np.array([[0, 1, 0, 0],
                  [0, 0, 1, 0],
                  [0, 0, 0, 1],
                  [1, 4, 1, 3]], dtype='object')
    
    initial_state = np.array([1, 1, 1, 1], dtype='object')
    
    T_N = matrix_pow(T, N)
    final_state = matrix_mult(T_N, initial_state) % mod
    
    return final_state[3]

print(solucionar_rompecabezas(10))
print(solucionar_rompecabezas(100))
print(solucionar_rompecabezas(pow(2023, 100)))

Editado Al ejecutarlo, notarán que para n=10n=10, el bucle while se repite 4 veces; para n=100n=100, se repite 7 veces; y para n=pot(2023,100)n=pot(2023,100) después de cambiar el dtype en NumPy de int a object, me di cuenta de que no se puede llegar (aunque sea mas eficiente el algoritmo el numero sigue siendo muy grande). Sin embargo, con valores de N=1000000 ya se puede evidenciar la diferencia en rendimiento entre esta solución y la solución trivial.

resultados: N=10 902441 N=100 8042318513

dato de interes:

>print(2023 ** 100)
>3977299330281882403306574735225337717599631172062412445045578274405450110120677174505186273779312535365746310019472644285894036169695910906506233118452300676652476856018828588020899113867978825566482076357081191135854217234411796915745355130981797659740171549912770735205485217369751214708750973368807626092441067706281896347276001

**Fin edicion**


  [1]: https://i.sstatic.net/fzNM3Og6.png
  [2]: https://i.sstatic.net/xV6Voaxi.png
  [3]: https://i.sstatic.net/9ntF8gbK.png
add banner
Origen Enlace
user368971
user368971
Loading
se eliminaron 4 caracteres en el cuerpo
Origen Enlace
user368971
user368971
Loading
Origen Enlace
user368971
user368971
Loading