Password Cracker

Problem

There are N users registered on a website CuteKittens.com. Each of them has a unique password represented by pass[1], pass[2], ..., pass[N]. As this a very lovely site, many people want to access those awesomely cute pics of the kittens. But the adamant admin does not want the site to be available to the general public, so only those people who have passwords can access it.

Yu, being an awesome hacker finds a loophole in the password verification system. A string which is a concatenation of one or more passwords, in any order, is also accepted by the password verification system. Any password can appear 0 or more times in that string. Given access to each of the n passwords, and also have a string loginAttempt,determinewhetherthisstringbeacceptedbythepasswordverificationsystemofthewebsite loginAttempt$ string can be created by concatenating password strings, it is accepted.

For example, if there are 3 users with passwords = [abra, ka, dabra], then some of the valid combinations are abra (password[1]), kaabra (password[2] + password[1]), kadabraka (password[2] + password[3] + password[2]), kadabraabra (password[2] + password[3] + password[1]) and so on. Supplying abra ka dabra, concatenated, passes authentication.

Function Description

Complete the passwordCracker function in the editor below. It should return the passwords as a single string in the order required for the password to be accepted, each separated by a space. If it is not possible to form the string, return the string WRONG PASSWORD.

passwordCracker has the following parameters:

• passwords: a list of password strings
• loginAttempt: the string to attempt to create

Read more on the challenge page…

Problem Analysis And Solution

My Solution

I’m providing the solution for Python and JS, please leave on the comments if you found a better way.

#!/bin/python3

import math
import os
import random
import re
import sys
sys.setrecursionlimit(200000)
#
# Complete the 'passwordCracker' function below.
#
# The function is expected to return a STRING.
# The function accepts following parameters:
#  1. STRING_ARRAY passwords
#  2. STRING loginAttempt
#

memo = {}

def process(passwords, loginAttempt):
    global memo
    # print("loginAttempt = {} memo = {}".format(loginAttempt, memo))
    if len(loginAttempt) == 0:
        return True, []
    
    if loginAttempt in memo:
        return False, []
    
    for password in passwords:
        if loginAttempt.startswith(password):
            memo[loginAttempt] = True
            
            sol, result = process(passwords, loginAttempt[len(password):])
            if sol == True:
                return True, [password] + result
            
    return False, []

def passwordCracker(passwords, loginAttempt):
    global memo
    memo = {}
    sol, result = process(passwords, loginAttempt)

    if sol:
        return ' '.join(result)
    
    return "WRONG PASSWORD"

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input().strip())

    for t_itr in range(t):
        n = int(input().strip())

        passwords = input().rstrip().split()

        loginAttempt = input()

        result = passwordCracker(passwords, loginAttempt)

        fptr.write(result + '\n')

    fptr.close()

Juan Cruz Martinez

¡Hola!

Soy Juan Cruz Martinez, el fundador de LiveCodeStream.dev. Me encanta programar y creo en el poder de la programación no solo para construir un mundo mejor, sino para hacer que TU vida sea mejor.

Fundé LiveCodeStream.dev porque quería ayudarte a aprender a programar, construir una mejor carrera y, en última instancia, crear una vida mejor. Eso me sucedió hace más de una década cuando comencé a programar, y le sucede a decenas de miles de personas a diario. Quiero que TÚ te unas a esa revolución.

No importa cómo lo llames, escribir código, programación, desarrollo de software o cualquier otra cosa, las habilidades involucradas están en una demanda cada vez mayor. Y ya sea que quieras incursionar en el desarrollo de sitios web, diseño de juegos, desarrollo de blockchain o cualquier otra cosa, quiero ayudarte.