Ad
Dark_Ughhvs.Dark_Ughh

Alfonso's Code Wars - Trie Implementation

Code
Diff
  • class Trie:

    def __init__(self):
        """
        Initializes the trie object.
        """
        self.children = {}
        self.is_word = False

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        # create a 'ptr' to the first node.
        node = self
        # loop through all the chars.
        for char in word:
            # insert a new instance of Trie if a letter isnt found.
            if char not in node.children:
                node.children[char] = Trie()
            # move to next node
            node = node.children[char]
        # once you get to the end mark this node as an end node.
        node.is_word = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        # create a 'ptr' to the first node.
        node = self
        for char in word:
            # if at any point we dont find our current char. then we know the word is not in the Trie.
            if char not in node.children:
                return False
            # move to next node
            node = node.children[char]
        # if we get to the end then we know all the chars are in the trie. But we return weather or not we are at the end of a word. Since this could be a "starts with match".
        return node.is_word

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        # same as search()...
        node = self
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        #... except that regardless of the .is_word value we will return true.
        return True
    • class Trie:
    • def __init__(self):
    • """
    • Initializes the trie object.
    • """
    • pass # Replace with your code
    • self.children = {}
    • self.is_word = False
    • def insert(self, word: str) -> None:
    • """
    • Inserts a word into the trie.
    • """
    • pass # Replace with your code
    • # create a 'ptr' to the first node.
    • node = self
    • # loop through all the chars.
    • for char in word:
    • # insert a new instance of Trie if a letter isnt found.
    • if char not in node.children:
    • node.children[char] = Trie()
    • # move to next node
    • node = node.children[char]
    • # once you get to the end mark this node as an end node.
    • node.is_word = True
    • def search(self, word: str) -> bool:
    • """
    • Returns if the word is in the trie.
    • """
    • pass # Replace with your code
    • # create a 'ptr' to the first node.
    • node = self
    • for char in word:
    • # if at any point we dont find our current char. then we know the word is not in the Trie.
    • if char not in node.children:
    • return False
    • # move to next node
    • node = node.children[char]
    • # if we get to the end then we know all the chars are in the trie. But we return weather or not we are at the end of a word. Since this could be a "starts with match".
    • return node.is_word
    • def startsWith(self, prefix: str) -> bool:
    • """
    • Returns if there is any word in the trie that starts with the given prefix.
    • """
    • pass # Replace with your code
    • # same as search()...
    • node = self
    • for char in prefix:
    • if char not in node.children:
    • return False
    • node = node.children[char]
    • #... except that regardless of the .is_word value we will return true.
    • return True
Dark_Ughhvs.Dark_Ughh

Alfonso's Solution

This works.. somehow. lol.

Code
Diff
  • #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define ONES_SIZE 10
#define TEENS_SIZE 6
#define TENS_SIZE 8
#define MAX_DOLLAR_SIZE 40

/*
Returns(in place): the integer and fractional parts of the double...
...effectively the left and right sides of the double.
*/
void double_to_ints(const double num, int *integer_part, int *fractional_part, const int decimal_places) {
    *integer_part = (int)num; 
    double fractional = num - (double)*integer_part;
    *fractional_part = (int)round(fractional * pow(10, decimal_places));
}

/*
Returns: the index of where the key is in the array...
...or -1 if the value is not found.
*/
int find_val_in_array(int *array, int key, int array_size) {
    for (int i = 0; i < array_size; i++) {
    if (key == array[i]){
        return i;
    }
    }
    return -1;
}

/*
Arguments: 
  - amount = a double betwen 0.01 and 99.99. Representing the check dollars and cents to convert.
  
Returns: A string with the text representation of 'amount'....
...or NULL if the value is not found.
*/
char *checkAmount(double amount) {
    // input validate
    if (0.00 >= amount || amount > 99.99) {
      return NULL;
    }
  
    char * return_val = NULL;

    // define key value pair of words and their equivelant value as an int.
    int ones_key[] = {0,1,2,3,4,5,6,7,8,9};
    char ones_value[ONES_SIZE][MAX_DOLLAR_SIZE] = {"ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"};

    int teens_key[] = {10,11,12,13,14,15};
    char teens_value[TEENS_SIZE][MAX_DOLLAR_SIZE] = {"TEN", "ELEVEN", "TWELVE", "THIRTEEN", "FOURTEEN", "FIFTEEN"};

    int tens_key[] = {20,30,40,50,60,70,80,90};
    char tens_value[TENS_SIZE][MAX_DOLLAR_SIZE] = {"TWENTY", "THIRTY", "FORTY", "FIFTY", "SIXTY", "SEVENTY", "EIGHTY", "NINETY"};
    
    // define vars!
    int *integer_part = calloc(1, sizeof(int));
    if (NULL == integer_part){
        perror("malloc failed");
        return NULL;
    }
    int *fractional_part = calloc(1, sizeof(int));
    if (NULL == fractional_part){
        perror("malloc failed");
        return NULL;
    }
    int found_pos = -1;
    int len = 0;
    int tens = 0;
    char temp[MAX_DOLLAR_SIZE];
    char *list = NULL;
    char *dollars = calloc(1, MAX_DOLLAR_SIZE);
    if (NULL == dollars){
        perror("malloc failed");
        return NULL;
    }
  
  
    // extract integer and fraction from double.
    double_to_ints(amount, integer_part, fractional_part, 2);

    // For each _key list we are checking if the '*integer_part' is in the list. if it is we updated "list" to point to the corresponding _value list...
    if ((found_pos = find_val_in_array(ones_key, *integer_part, ONES_SIZE)) != -1) {
        list = ones_value[found_pos];
    } else if ((found_pos = find_val_in_array(teens_key, *integer_part, TEENS_SIZE)) != -1) {
        list = teens_value[found_pos];
    } else if ((found_pos = find_val_in_array(tens_key, *integer_part, TENS_SIZE)) != -1) {
        list = tens_value[found_pos];
    } else {
    // ... if we dont find a match then its likely that we got 16-19 or something like: [24, 56, 91, ...]
        // we divide by 10 so we can drop the value in the ones place [16 -> 1, 24 -> 2, ...]
        tens = *integer_part / 10;
        if (tens == 1) {
            // if we have a ten then we handle it special due to the 'teens'. get the "ones_key" and append "TEEN" to it...
            // ... for example: ["NINE" + "TEEN" = "NINETEEN"]
            found_pos = find_val_in_array(ones_key, (*integer_part - 10), ONES_SIZE);
            strncpy(temp, ones_value[found_pos], sizeof(temp));
            // EIGHTEEN is a special case since "EIGHT" and "TEEN" share a "T". So we trim the "T"
            if (strncmp(temp, "EIGHT", 6) == 0) {
              strcat(temp, "EEN");
            } else {
              strcat(temp, "TEEN");  
            }
          
        }
        else {
            // non-tens are handled different. exmple: 25
            // find and update temp = "TWENTY"
            found_pos = find_val_in_array(tens_key, (tens * 10), TENS_SIZE);
            strncpy(temp, tens_value[found_pos], sizeof(temp));

            // find and update temp = "TWENTY FIVE"
            int val = (*integer_part % 10);
            strcat(temp, " ");
            strcat(temp, ones_value[val]);
        }
        list = temp;
    }
    
    if (list != NULL) {
            // Ensure null termination
            len = strlen(list);
            strncpy(dollars, list, len);
            dollars[len] = '\0'; 
    } else {
        // This should not happen, but handle it anyway
        free(integer_part);
        free(fractional_part);
        free(dollars);
        return NULL;
    }

    // get cent value
    char cents[256];
    int cent_size = sprintf(cents," and %d/100", *fractional_part);
  
    free(integer_part);
    free(fractional_part);
    
    // put everything together.
    return_val = calloc(1, (strlen(dollars) + cent_size + 1));
    if (NULL == return_val){
      perror("malloc failed");
      free(dollars);
      return NULL;
    }
    strncpy(return_val, dollars, strlen(dollars));
    strcat(return_val, cents);
    strcat(return_val, "\0");
  
    free(dollars);

    return return_val;
}
    • #include <string.h>
    • #include <stdio.h>
    • #include <stdlib.h>
    • #include <string.h>
    • #include <math.h>
    • #define ONES_SIZE 10
    • #define TEENS_SIZE 6
    • #define TENS_SIZE 8
    • #define MAX_DOLLAR_SIZE 40
    • /*
    • Returns(in place): the integer and fractional parts of the double...
    • ...effectively the left and right sides of the double.
    • */
    • void double_to_ints(const double num, int *integer_part, int *fractional_part, const int decimal_places) {
    • *integer_part = (int)num;
    • double fractional = num - (double)*integer_part;
    • *fractional_part = (int)round(fractional * pow(10, decimal_places));
    • }
    • /*
    • Returns: the index of where the key is in the array...
    • ...or -1 if the value is not found.
    • */
    • int find_val_in_array(int *array, int key, int array_size) {
    • for (int i = 0; i < array_size; i++) {
    • if (key == array[i]){
    • return i;
    • }
    • }
    • return -1;
    • }
    • /*
    • Arguments:
    • - amount = a double betwen 0.01 and 99.99. Representing the check dollars and cents to convert.
    • Returns: A string with the text representation of 'amount'....
    • ...or NULL if the value is not found.
    • */
    • char *checkAmount(double amount) {
    • char * return_val = NULL;
    • // Your code here!
    • // input validate
    • if (0.00 >= amount || amount > 99.99) {
    • return NULL;
    • }
    • return return_val;
    • char * return_val = NULL;
    • // define key value pair of words and their equivelant value as an int.
    • int ones_key[] = {0,1,2,3,4,5,6,7,8,9};
    • char ones_value[ONES_SIZE][MAX_DOLLAR_SIZE] = {"ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"};
    • int teens_key[] = {10,11,12,13,14,15};
    • char teens_value[TEENS_SIZE][MAX_DOLLAR_SIZE] = {"TEN", "ELEVEN", "TWELVE", "THIRTEEN", "FOURTEEN", "FIFTEEN"};
    • int tens_key[] = {20,30,40,50,60,70,80,90};
    • char tens_value[TENS_SIZE][MAX_DOLLAR_SIZE] = {"TWENTY", "THIRTY", "FORTY", "FIFTY", "SIXTY", "SEVENTY", "EIGHTY", "NINETY"};
    • // define vars!
    • int *integer_part = calloc(1, sizeof(int));
    • if (NULL == integer_part){
    • perror("malloc failed");
    • return NULL;
    • }
    • int *fractional_part = calloc(1, sizeof(int));
    • if (NULL == fractional_part){
    • perror("malloc failed");
    • return NULL;
    • }
    • int found_pos = -1;
    • int len = 0;
    • int tens = 0;
    • char temp[MAX_DOLLAR_SIZE];
    • char *list = NULL;
    • char *dollars = calloc(1, MAX_DOLLAR_SIZE);
    • if (NULL == dollars){
    • perror("malloc failed");
    • return NULL;
    • }
    • // extract integer and fraction from double.
    • double_to_ints(amount, integer_part, fractional_part, 2);
    • // For each _key list we are checking if the '*integer_part' is in the list. if it is we updated "list" to point to the corresponding _value list...
    • if ((found_pos = find_val_in_array(ones_key, *integer_part, ONES_SIZE)) != -1) {
    • list = ones_value[found_pos];
    • } else if ((found_pos = find_val_in_array(teens_key, *integer_part, TEENS_SIZE)) != -1) {
    • list = teens_value[found_pos];
    • } else if ((found_pos = find_val_in_array(tens_key, *integer_part, TENS_SIZE)) != -1) {
    • list = tens_value[found_pos];
    • } else {
    • // ... if we dont find a match then its likely that we got 16-19 or something like: [24, 56, 91, ...]
    • // we divide by 10 so we can drop the value in the ones place [16 -> 1, 24 -> 2, ...]
    • tens = *integer_part / 10;
    • if (tens == 1) {
    • // if we have a ten then we handle it special due to the 'teens'. get the "ones_key" and append "TEEN" to it...
    • // ... for example: ["NINE" + "TEEN" = "NINETEEN"]
    • found_pos = find_val_in_array(ones_key, (*integer_part - 10), ONES_SIZE);
    • strncpy(temp, ones_value[found_pos], sizeof(temp));
    • // EIGHTEEN is a special case since "EIGHT" and "TEEN" share a "T". So we trim the "T"
    • if (strncmp(temp, "EIGHT", 6) == 0) {
    • strcat(temp, "EEN");
    • } else {
    • strcat(temp, "TEEN");
    • }
    • }
    • else {
    • // non-tens are handled different. exmple: 25
    • // find and update temp = "TWENTY"
    • found_pos = find_val_in_array(tens_key, (tens * 10), TENS_SIZE);
    • strncpy(temp, tens_value[found_pos], sizeof(temp));
    • // find and update temp = "TWENTY FIVE"
    • int val = (*integer_part % 10);
    • strcat(temp, " ");
    • strcat(temp, ones_value[val]);
    • }
    • list = temp;
    • }
    • if (list != NULL) {
    • // Ensure null termination
    • len = strlen(list);
    • strncpy(dollars, list, len);
    • dollars[len] = '\0';
    • } else {
    • // This should not happen, but handle it anyway
    • free(integer_part);
    • free(fractional_part);
    • free(dollars);
    • return NULL;
    • }
    • // get cent value
    • char cents[256];
    • int cent_size = sprintf(cents," and %d/100", *fractional_part);
    • free(integer_part);
    • free(fractional_part);
    • // put everything together.
    • return_val = calloc(1, (strlen(dollars) + cent_size + 1));
    • if (NULL == return_val){
    • perror("malloc failed");
    • free(dollars);
    • return NULL;
    • }
    • strncpy(return_val, dollars, strlen(dollars));
    • strcat(return_val, cents);
    • strcat(return_val, "\0");
    • free(dollars);
    • return return_val;
    • }
Dark_UghhFailed Tests

Alfonso's Code Wars - Writing a check amount (REVISED)

Problem: Writing a check amount

Tasks

Implement the checkAmount() function that writes the word equivalent of a numeric check amount (with values up to $99.99) to a string that is returned

Example 1:

  • Input: amount = 42.00
  • Output: "FORTY TWO and 00/100"
  • Explanation: Write "FORTY TWO" because there is $42. Next is " and " to join the two sections. Lastly add "42/100" to represent the cents.

Example 2:

  • Input: amount = 150.00
  • Output: NULL
  • Explanation: 150.00 is beyond bounds. So return NULL.

Example 3:

  • Input: amount = 69.42
  • Output: "SIXTY NINE and 42/100"

Constraints

  • 0.01 <= amount <= 99.99
  • All inputs will be a valid double.
  • Return (char *)NULL if bounds are exceeded.
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

char *checkAmount(double amount) {
  char * return_val = NULL;
  // Your code here!
  
  return return_val;
}
Dark_UghhFailed Tests

Alfonso's Code Wars - Trie Implementation

Problem: Trie Implementation

Tasks

In python implement a Trie class with the following methods:

  • init(self): Initializes an empty Trie.
  • insert(self, word): Inserts a word into the Trie.
  • search(self, word): Returns True if the word is in the Trie, False otherwise.
  • startsWith(self, prefix): Returns True if there is any word in the Trie that starts with the given prefix, False otherwise.

Example 1:

# setup
trie = Trie()
trie.insert("apple")

# .search() is exact
print(trie.search("apple"))   # Output: True
print(trie.search("app"))     # Output: False
trie.insert("app")
print(trie.search("app"))     # Output: True 

# .startsWith() is more flexible
print(trie.startsWith("app")) # Output: True

Example 2:

# setup
trie = Trie()
trie.insert("hello")
trie.insert("world")

# .search() is looking for a complete match.
print(trie.search("he"))      # Output: False

# .startsWith() looks for a partial match at the begining of word.
print(trie.startsWith("wo"))  # Output: True
print(trie.startsWith("x"))   # Output: False

Constraints

  • The class name MUST be Trie.
  • You may assume that all inputs are valid.
  • All words and prefixes will consist of lowercase English letters.

Additional Resources

class Trie:

    def __init__(self):
        """
        Initializes the trie object.
        """
        pass # Replace with your code

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        pass # Replace with your code

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        pass # Replace with your code
    

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        pass # Replace with your code