Ordenamiento de Palabras en Idiomas Alienígenas

Clase 5 de 35 • Curso de Algoritmos Avanzados: Patrones de Arrays y Strings

Resumen

¿Cómo resolver problemas de ordenamiento en lenguajes alienígenas?

Entender y resolver problemas complejos, como ordenar palabras según un idioma alienígena, requiere no solo tener claridad sobre las entradas, sino también descomponer el problema en partes manejables. Al igual que en una entrevista técnica, es vital cuestionar y definir con precisión los límites y detalles de nuestro problema antes de abordarlo.

¿Qué debemos considerar sobre nuestras entradas?

La clave para empezar es comprender nuestras entradas:

Lista de palabras: Pregúntate si las palabras tienen la misma longitud, si hay caracteres extra, o si pueden repetirse.
Orden del diccionario: Determina si las mayúsculas y minúsculas son distintas, si hay símbolos especiales, y la longitud del diccionario. Estos factores afectan la complejidad de la solución.

Estas preguntas iniciales nos permiten evaluar cómo influirán ciertos detalles en la solución y aseguran que nuestras suposiciones sean correctas.

¿Cómo comparar órdenes de letras de manera eficiente?

El objetivo es verificar si las palabras están ordenadas según un orden dado:

Hash Table: Se puede utilizar para asignar cada letra a un valor numérico, permitiendo comparaciones rápidas O(1).
Subproblemas: Identifica los subproblemas comparando caracteres uno a uno en las palabras y verificando el orden basado en el diccionario alienígena.

Por ejemplo, crear un mapa donde 'H' corresponde a 1 y 'K' a 12 ayuda en las comparaciones necesarias para verificar el orden de las palabras.

¿Cómo evitar iteraciones innecesarias?

Para hacer la solución más eficiente:

Apuntadores: Sistema de dos apuntadores comparando solo las palabras consecutivas, evitando así revisiones repetitivas.
Comparación optimizada: Una vez que encuentras un desorden, puedes detenerte y retornar un resultado, evitando cálculos redundantes.

Por ejemplo, si comparas palabras consecutivas y detectas que están desordenadas, puedes abortar más comparaciones, ahorrando así tiempo y recursos.

¿Qué hay de los casos excepcionales?

En el mundo real, siempre existen casos que no se ajustan a la norma:

Palabras contenidas: Como en el caso de "cono" y "conocer", donde una palabra está completamente dentro de otra. Aquí, la palabra corta, tiene prioridad en orden, rompiendo con la lógica del simple cotejo de caracteres.

Para cada problema encontramos casos únicos y en estos, usualmente adoptamos un enfoque de prueba y error, ajustando los criterios de orden según lo requerido.

Este análisis detallado de cómo solucionar problemas de ordenamiento en un idioma alienígena no solo mejora nuestras habilidades para resolver problemas complejos, sino también nos enseña el valor de analizar detalladamente y planificar estratégicamente antes de actuar. Sigue explorando e investigando, permitiendo que el entusiasmo por el aprendizaje te lleve a descubrir más soluciones innovadoras.

Antonio Nicasio

student•

siento que el problema está mal explicado.

William Rodriguez

student•

Asi suele ser en las entrevistas de algoritmia, no lo explican completo a proposito.

Jherom Chacon

student•

Yo me confundi con el concepto de lexicografíco. Eso lo busque y me dio pena solo el buscar que significaba. Pero una vez entendiendo que lexicografíco significa en el orden del alfabeto como un diccionario, todo tuvo sentido para mi.

Leonel Veliz

student•

Creo que para efectos de una clase / curso online donde no tenemos a disposición alguien a quien hacerle tantas preguntas, es mucho mas facil asumir que todo el sistema es dinámico, donde el numero de caracteres del alfabeto no lo sabemos (usemos lenght), estandaricemos todo en MAYUS o minus con las funciones correspondientes, asumamos que puedan haber caracteres en el arreglo que no estan en el alfabeto.

Lo que intento decir, es que, a pesar de que estoy 100% de acuerdo que hay que hacernos muchas preguntas, hay que hacerlas cuando haya alguien que las responda, sino, demos por hecho de que todo es dinámico y que todo puede salir mal, así nos preparamos para el peor caso posible y es algo que podemos controlar

Juan Castro

teacher•

También puedes usar tu criterio y definir algunos requisitos siempre y cuando los dejes muy claros en tu implementación. :D

William Rodriguez

student•

Muchas veces en la entrevista te envian un link de leetcode o un hacker rank hay tambien hay ambiguedades y tienes que resolverlas...

El programador trabaja con ambiguedades y toma decisiones.

Justo por no trabajar esa skill es que muchas personas pierden las entrevistas.

Nicolas Alpargatero

student•

Hubiera sabido que esta clase iba a explicar sin el código no me hubiera gastado tanto tiempo buscando 😅 y entendiendo.

En el peor de los casos en O(n) en el mejor O(1)

No si sea porque lo estudie bastante que la clase se me hizo excelente, pero me encanto como nos enseña a desglosar subproblemas.

Giovanni Mendoza

student•

Yo no entiendo el problema y no entiendo la explicación del mismo, por mas que trato de ver que se tiene que ordenar de a cuerdo al orden, la verdad que no me da el resultado esperado, ya que si fuera por el oden del alfabeto las dos comparaciones de ejemplo serian falsas. Además no entiendo a que se refiere con "ordenadas lexicográficamente", que creo que ahi radica mi problema de entendimiento para este problema

Alvaro Eduardo Garzón Pira

student•

¡Hola! 😊 Pasé una hora intentando entenderlo, así que no te preocupes, ¡es normal sentirse confundido!

El problema se refiere a que queremos verificar si una lista de palabras está ordenada según un nuevo orden del alfabeto. Cuando se dice "ordenadas lexicográficamente", significa que se comparan las palabras letra por letra, como se haría en un diccionario.

Para aclarar, imagina que usamos el abecedario español estándar:

1. **Ejemplo de palabras**:

```

AAA

ABC

ACD

AAB

AAC

```

2. **Orden esperado**:

```

AAA ← Primero porque todas las letras son "A".

AAB ← Viene después de "AAA" porque la segunda letra "A" es menor que "B" en "ABC".

AAC ← Similar a "AAB", solo que la tercera letra es "C".

ABC ← Después de "AAC", porque "B" es menor que "C" en "ACD".

ACD ← Finalmente, porque "C" es mayor que "B" en "ABC".

```

Entonces, al mirar las palabras, seguimos el nuevo orden del alfabeto al compararlas letra por letra y determinar cuál debe ir primero.

Espero que esto te ayude a entender mejor el concepto. Si tienes más preguntas, ¡aquí estoy!

Juan Pablo Reina Gutierrez

student•

Varios casos extraños podrían ser que las palabras tengan números, caracteres en mayúsculas o minúsculas, listas de palabras en diferentes idiomas, tildes o cualquier otro carácter que no esté mapeado en el diccionario.

Miguel Angel Reyes Moreno

student•

~+!

Luis Sandoval

student•

Hola, adjunto mi posible solución

// See https://aka.ms/new-console-template for more information

var palabras1 = new List<string>{
    "conocer", "cono"
};

var palabras2 = new List<string>{
    "habito", "hacer", "sonreir","lectura"
};

Console.WriteLine(LasPalabrasEstanOrdenedas(palabras1, "abcdefghijklmnopqrstuvwxyz"));
Console.WriteLine(LasPalabrasEstanOrdenedas(palabras2, "hlabcdefgijkmnopqrstuvwxyz"));


static bool LasPalabrasEstanOrdenedas(List<string> palabras, string ordenAlfabeto)
{
    var dic = new Dictionary<char, int>();

    for (int i = 0; i < ordenAlfabeto.Length; i++)
        dic.Add(ordenAlfabeto[i], i + 1);

    var dics = PalabrasDescompuestas(palabras, dic);

    for (int i = 0; i < dics.Length - 1; i++)
    {
        if (CompararDosDiccionarios(dics[i], dics[i + 1])) return true;
    }

    return false;
}

static bool CompararDosDiccionarios(IDictionary<int, (int, char)> dic1, Dictionary<int, (int, char)> dic2)
{
    int max = dic1.Count + dic2.Count;

    for (int i = 0; i < max; i++)
    {
        var valDic1 = dic1.ElementAtOrDefault(i);
        var valDic2 = dic2.ElementAtOrDefault(i);

        if (valDic1.Value.Item2 == valDic2.Value.Item2) continue;

        if (valDic1.Value.Item1 < valDic2.Value.Item1) return true;
        break;
    }

    return false;
}


static Dictionary<int, (int, char)>[] PalabrasDescompuestas(List<string> palabras, Dictionary<char, int> ordenamiento)
{
    var dics = new Dictionary<int, (int, char)>[palabras.Count];
    for (int i = 0; i < palabras.Count; i++)
    {
        dics[i] = ObtenerCadenaDescompuesta(palabras[i], ordenamiento);
    }
    return dics;
}

static Dictionary<int, (int, char)> ObtenerCadenaDescompuesta(string palabra, Dictionary<char, int> ordenamiento)
{
    var dic = new Dictionary<int, (int, char)>();
    for (int i = 0; i < palabra.Length; i++)
    {
        if (ordenamiento.TryGetValue(palabra[i], out int value))
        {
            dic.Add(i, (value, palabra[i]));
        }
    }
    return dic;
}

Miguel Angel Diaz Delgado

student•

orden_alfabetico      = 'abcdefghijklmnopqrstuvwxyz'
ordenAlfabeticoAlien  = 'hlabcdefgijkmnopqrstuvwxyz'

class BuscarPosicionLetra:
    def __init__(self, alfabeto, letra):
        for i in range(len(alfabeto)):
            if letra in alfabeto[i]:
                self.posicion = i
                break


class RetornarNuevaLetra:
    def __init__(self, alfabeto, posicion):
        self.letra = alfabeto[posicion]


class RetornarPalabra:
    def __init__(self, alfabetoAnt, alfabetoNew, palabra):
        palabraNueva = ''
        for i in range(len(palabra)):
            palabraNueva += RetornarNuevaLetra(alfabetoNew, BuscarPosicionLetra(alfabetoAnt, palabra[i]).posicion).letra
        self.palabraNueva = palabraNueva

print(RetornarPalabra(ordenAlfabeticoAlien, orden_alfabetico, 'conocer').palabraNueva)

Leonel Veliz

student•

Si tienes un string con el alfabeto, también podrías volverlo un string, y cada posición esta asociada a una letra.

Christopher Andrés Guano Valencia

student•

Sí, sin embargo, hay que tener en cuenta que para saber el índice hay que recorrer el string varias veces, por eso es mejor recorrerlo todo una vez y guardarlo en una estructura de clave y valor. 🙌

Carlos Machado

student•

Por si quieren tener tambien más contexto del problema busquenlo en leetcode. Está muy bien

function isAlienSorted(words: string[], order: string): boolean {

if (words.length === 0 || order.length === 0) {

return false;

}

const alphaMap = new Map<string, number>();

for (let i = 0; i < order.length; i++) { //O(n)

alphaMap.set(order[i], i);

}

for (let i = 0; i < words.length; i++) { // 0(n)

const currentWord = words[i];

const nextWord = words[i + 1];

if (!nextWord) {

return true;

}

for (let j = 0; j < currentWord.length; j++) { // 0(n)

if (j === nextWord.length) {

return false;

}

if (currentWord[j] !== nextWord[j]) {

if (alphaMap.get(nextWord[j]) < alphaMap.get(currentWord[j])) {

return false;

}

break;

}

return true;

};

Edgar Diego Piña Vargas

student•

#first ideas
#las palabras se ordenan en diferentes niveles, comenzando por la primer letra hasta las siguientes 
# segun el numero de coincidencias
palabras = ['habito','hacer','lectura', 'sonreir']
diccionario = "hlabcdefgijkmnopqrstuvwxyz"
# Aproach 1
# we can try with a loop, starting with the first letter and doing a firs condition is the same letter?
# if yes, continue with the next letter otherwise do a comparation off each letter to the letters on the dictionary
# then do a relational conditional with the number of index corresponding in the dict
# this solution needs to compare each word among 
# 
# 
# Aproach 2
# do a list of integgers with lenght equal to the number off words, and do a loop n times as n number off words too
# then compare the first letter off the current word with the dictionary using 2 pointes technique to determinate the 
# index number corresponding the dictionary, save this level with firs leters in the array
# for the next levels the loop will only considered the values that are repited into the integger array 
```Considere estos dos enfoques inicialmente, para el momento aun tengo algunas dudas sobre el manejo de apuntadores con strings en la sintaxis de python&#x20;

Edgar Diego Piña Vargas

student•

Finalmente quedo así...

palabras = ['habito','hacer','lectura', 'sonreir']
diccionario = list("hlabcdefgijkmnopqrstuvwxyz")
diccionarioMap = {diccionario[x] : x  for x in range(len(diccionario))}
izq = 0
der = 1
i=0
ordenado = True
for i in range(len(palabras)-1):
    while(True):
        if i == min(len(palabras[0]),len(palabras[1])):
            break
        else:
            letraP1 = palabras[izq][i]
            letraP2 = palabras[der][i]
            if letraP1 != letraP2:
                if(diccionarioMap[letraP1] > diccionarioMap[letraP2]):
                    ordenado = False
                    break
                else:
                    break
            i += 1 
    izq += 1
    der += 1
print(ordenado)

Miguel Prada

student•

["habito", "hacer"] sí están ordenadas?

Manuel David Escobar Figueroa

student•

Hola, realicé mi implementación con Java.

Me gusta hacer todo "manual" por mí mismo, así que creé mi propia función para que asigne o cree mi diccionario de valores correspondiente a las letras del alfabeto.

No sé qué tan correcta está mi implementación.

 public static void main(String[] args){ 

        System.out.println("Caso 1");
        System.out.println(verifyingDictionary(new String[]{"app", "apple"}, "abcdefghijklmnopqrstuvwxyz") ? "bien" : "mal");
        System.out.println("Caso 2");
        System.out.println(verifyingDictionary(new String[]{"aaaa", "aaa"}, "abcdefghijklmnopqrstuvwxyz") ? "bien" : "mal");
        System.out.println("Caso 3");
        System.out.println(verifyingDictionary(new String[]{"hello", "leetcode"}, "hlabcdefgijkmnopqrstuvwxyz") ? "bien" : "mal");
}

public static boolean verifyingDictionary(String[] words, String alphabet){

        for(int i = 0; i < words.length - 1; i++) { 
            
            for(int j = 0; j < words[i].length(); j++) {

                int p1 = returnPositionChar(alphabet, words[i].charAt(j));
                int p2 = returnPositionChar(alphabet, words[i+1].charAt(j));     

                if(p1 < p2) break; 

                else if(p1 > p2) return false;

                else if(p1 == p2){
                    if(words[i].length() > words[i+1].length()){
                        return false;
                    }        
                }
            }
        }
        return true;
    }

    public static int returnPositionChar(String alphabet, char p){ 

        for(int i = 0; i < alphabet.length(); i++){ 

            if(p == alphabet.charAt(i)){
                return i;
            }
        }
        return -1;
    }

Jherom Chacon

student•

Para mi fue critico primero comprender que la lista de palabras puede tener palabras de distinto temano. Luego de esto comprender que para que funcione el diccionario no puede tener valores repetidos. Lo segundo es que podemos eliminar del diccionario todas las letras que no existan en el conjunto de palabras que tenemos en nuestra primera entrada. Todos estos procesos son adicionales e incrementan el tiempo de eficiencia, primero el ordenamiento de las palabras por su largo y segundo reducir el tamaño de la segunda entrada en función de la primera para no hacer recorridos redundantes.

Alfredo Olmedo

student•

Se que Camila Londoño comento en el curso anterior y no entendi el porque no uar Pseudo codigo, sin embargo, aqui pongo un Pseudo codigo para quien le sirva:

funcion estanOrdenadasLexicograficamente(palabras, alfabeto): mapa_alfabeto = diccionario() para i desde 0 hasta longitud(alfabeto) - 1: mapa_alfabeto[alfabeto[i]] = i para i desde 0 hasta longitud(palabras) - 2: si no esta_en_orden(palabras[i], palabras[i+1], mapa_alfabeto): devolver False devolver True funcion esta_en_orden(palabra1, palabra2, mapa_alfabeto): min_length = min(longitud(palabra1), longitud(palabra2)) para i desde 0 hasta min_length - 1: si mapa_alfabeto[palabra1[i]] < mapa_alfabeto[palabra2[i]]: devolver True si mapa_alfabeto[palabra1[i]] > mapa_alfabeto[palabra2[i]]: devolver False si longitud(palabra1) > longitud(palabra2): devolver False devolver True

Camilo Castañeda

student•

Buena explicación, no me costó tanto trabajo entender. Es un punto de partida para indagar en la solución de este tipo de problemas.

Daniel Ortiz

student•

Algo que me agrado mucho, es que el problema no esta totalmente limitado, Es bueno pues parte de ser programador es demostrar la curiosidad, por ejemplo si se dan cuenta habi > hace si se tuviera en cuenta cada letra del alfabeto pero si solo tomaramos los primeros 3 caracteres entonces habi<hace. Esto esta investigacion es algo importante al momento de levantar casos de ueso

Sebastián Franco

student•

Hice una implementación con la restricción de que generamos las palabras proceduralmente en cada iteración

import random og_alphabet = [ 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'] new_alphabet = og_alphabet.copy()random.shuffle(new_alphabet) print("NEW ALPHABET: ")print(new_alphabet) random_words = 6words_size = 5alphabet_array = [] print("Generating random words")for i in range(random_words): current_word = "" for j in range(words_size): current_word += random.choice(new_alphabet) alphabet_array.append(current_word) print(f"Words to use: {alphabet_array}") started = Falsecurrent_starting_letter = ""current_starting_letter_index = -1current_word = ""current_index = -1broke_cycle = False for i in alphabet_array: if not started: current_starting_letter = i[0] current_starting_letter_index = new_alphabet.index(current_starting_letter) started = True current_word = i print(f"Starting with word {current_word}") else: current_index = new_alphabet.index(i[0]) if current_starting_letter_index > current_index: print(f"It doesn't make any sense! {current_word} is not before {i}") broke_cycle = True break else: old_word = current_word current_word = i current_starting_letter_index = current_index print(f"Ok! {old_word} is before {current_word}") if not broke_cycle: print("Dear good, they are good!")else: print("Sorry, didn't work this time")

Rodrigo Arredondo Rosas

student•

Esta fue mi solución en Python

def validate_words(first_word, second_word, alphabet):
	first_word_letters = len(first_word)
	second_word_letters = len(second_word)
	letters = first_word_letters if first_word_letters <= second_word_letters else second_word_letters
	last_letter = letters - 1

	for position in range(letters):
		first_letter = first_word[position]
		second_letter = second_word[position]
		
		if first_letter != second_letter:
			# Only compare if letters don't match
			first_letter_index = alphabet.index(first_letter)
			second_letter_index = alphabet.index(second_letter)

			if first_letter_index < second_letter_index:
				break
			elif first_letter_index > second_letter_index:
				return False
		elif position == last_letter and first_word_letters > second_word_letters:
			# The same characters were compared trough iterations
			# First word larger than second word (example liked - like)
			return False

	return True

	
def alien_dictionary_verifying(words, alphabet):
	increment = 1
	total_words = len(words)-1

	for position in range(total_words):
		first_word = words[position]
		second_word = words[position+increment]

		# Can improve by three words searching (previous, current, next)
		validation = validate_words(first_word, second_word, alphabet)

		if not validation:
			return False

	return True


words = ['hora', 'balon', 'celular', 'cono', 'con', 'desayuno', 'jugar']

first_alphabet = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 
					'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 
					'q', 'r', 's', 't', 'u', 'v', 'q', 'x', 'y', 'z']

second_alphabet = ['h', 'l', 'a', 'b', 'c', 'd', 'e', 'f', 
					'g', 'i', 'j', 'k', 'm', 'n', 'o', 'p', 'q', 
					'r', 's', 't', 'u', 'v', 'q', 'x', 'y', 'z']

print(alien_dictionary_verifying(words, second_alphabet))

Ramon Angulo

student•

Esta fue mi solucion en Javascript

const verifyAlienDictionary = (words = [], alphabet = 'abcdefghijklmnopqrstuvwxyz' ) => {
    let pointer1, pointer2;
    pointer1 = -1;
    pointer2 = 0;
    
    for ( let word of words ) {
        for ( let index = 0; index < alphabet.length;  index++ ) {
            if ( word.charAt(0) === alphabet.charAt(index) ) {
                pointer2 = index;
                if( pointer2 < pointer1 )
                    return false;
                else
                    pointer1 = pointer2;
            }
        }
    }

    return true;
}
```const verifyAlienDictionary = (words = \[], alphabet = 'abcdefghijklmnopqrstuvwxyz' ) => {    let pointer1, pointer2;    pointer1 = -1;    pointer2 = 0;        for ( let word of words ) {        for ( let index = 0; index < alphabet.length;  index++ ) {            if ( word.charAt(0) === alphabet.charAt(index) ) {                pointer2 = index;                if( pointer2 < pointer1 )                    return false;                else                    pointer1 = pointer2;            }        }    }
&#x20;   return true;}

Daniel Mendoza

student•

def alien_dictionary(words: list, alphabet: str):
    
	letter_order = {letter: i for i, letter in enumerate(alphabet)}
  
	for i in range(len(words) - 1):
		word_a = words[i]
		word_b = words[i+1]
		
		for j in range(min(len(word_a), len(word_b))):
			try:
				if letter_order[word_a[j]] < letter_order[word_b[j]]:
					break
				
				if letter_order[word_a[j]] == letter_order[word_b[j]]:
					continue
				
				return False
				
			except Exception:
				print('Las palabras incluyen caracteres desconocidos')
	return True
```def alien\_dictionary(words: list, alphabet: str):        letter\_order = {letter: i for i, letter in enumerate(alphabet)}      for i in range(len(words) - 1):        word\_a = words\[i]        word\_b = words\[i+1]                for j in range(min(len(word\_a), len(word\_b))):            try:                if letter\_order\[word\_a\[j]] < letter\_order\[word\_b\[j]]:                    break                                if letter\_order\[word\_a\[j]] == letter\_order\[word\_b\[j]]:                    continue                                return False                            except Exception:                print('Las palabras incluyen caracteres desconocidos')    return True