# Question
Title: Design an algorithm to predict words based on a skeleton from a given dictionary
I'm working on an algorithm which is permitted to use a training set of approximately 250,000 dictionary words.

I have built and providing here with a basic, working algorithm. This algorithm will match the provided masked string (e.g. a _ _ l e) to all possible words in the dictionary, tabulate the frequency of letters appearing in these possible words, and then guess the letter with the highest frequency of appearence that has not already been guessed. If there are no remaining words that match then it will default back to the character frequency distribution of the entire dictionary.

This benchmark strategy is successful approximately 10% of the time. I aim to design an algorithm that significantly outperforms this benchmark.

```
class HangmanAPI(object):
    def __init__(self, access_token=None, session=None, timeout=None):
        self.hangman_url = self.determine_hangman_url()
        self.access_token = access_token
        self.session = session or requests.Session()
        self.timeout = timeout
        self.guessed_letters = []

        full_dictionary_location = "words_250000_train.txt"
        self.full_dictionary = self.build_dictionary(full_dictionary_location)
        self.full_dictionary_common_letter_sorted = collections.Counter("".join(self.full_dictionary)).most_common()

        self.current_dictionary = []

        # Initialize the decision tree, random forest, and SVM models along with the vectorizer
        self.decision_tree_model = DecisionTreeClassifier()
        self.random_forest_model = RandomForestClassifier(n_estimators=100, random_state=42)
        self.svm_model = SVC(kernel='linear', probability=True, random_state=42)
        self.vectorizer = CountVectorizer(analyzer='char', lowercase=False, binary=True)
        self.target_labels = [chr(ord('a') + i) for i in range(26)]

        # Fit the decision tree model with the full dictionary once during initialization
        X = self.vectorizer.fit_transform(self.full_dictionary)
        y = np.array([word[-1] for word in self.full_dictionary])
        self.decision_tree_model.fit(X, y)

        # Add Q-table to store Q-values for state-action pairs
        self.q_table = {}

        # Hyperparameters for Q-learning
        self.learning_rate = 0.1
        self.discount_factor = 0.9
        self.epsilon = 0.1  # Probability of exploration during action selection

    def update_q_table(self, state, action, reward, next_state):
        # Q-learning update rule
        current_q_value = self.q_table.get((state, action), 0.0)
        next_q_values = [self.q_table.get((next_state, next_action), 0.0) for next_action in self.target_labels]
        max_next_q_value = max(next_q_values)
        new_q_value = current_q_value + self.learning_rate * (reward + self.discount_factor * max_next_q_value - current_q_value)
        self.q_table[(state, action)] = new_q_value

    def extract_features(self, word_pattern):
        # Extract features from the word pattern
        features = []

        # Word Length
        features.append(len(word_pattern))

        # Vowel and Consonant Counts
        vowel_count = sum(1 for letter in word_pattern if letter in 'aeiou')
        consonant_count = sum(1 for letter in word_pattern if letter in 'bcdfghjklmnpqrstvwxyz')
        features.append(vowel_count)
        features.append(consonant_count)

        # Common Letter Count
        common_letters = set("etaoinsrhldcumfpgwybvkxjqz")
        common_letter_count = sum(1 for letter in word_pattern if letter in common_letters)
        features.append(common_letter_count)

        # Letter Position Features
        features.append(1 if word_pattern.startswith('a') else 0)  # Check if starts with 'a'
        features.append(1 if word_pattern.endswith('e') else 0)  # Check if ends with 'e'
        features.append(1 if 'qu' in word_pattern else 0)  # Check if contains 'qu'

        # Character N-grams
        n_grams = [word_pattern[i:i + 2] for i in range(len(word_pattern) - 1)]
        for n_gram in ['th', 'er', 'in', 'ou', 'an']:  # Example: Consider the presence of common letter pairs
            features.append(1 if n_gram in n_grams else 0)

        # Part-of-Speech (POS) Features - Not implemented here, requires external NLP tools

        # Syllable Count - Not implemented here

        # Letter Frequency Distribution - Not implemented here

        return features

    def hyperparameter_tuning(self):
        # Define the hyperparameter search spaces for each model using hyperopt
        dt_space = {
            'criterion': hp.choice('criterion', ['gini', 'entropy']),
            'splitter': hp.choice('splitter', ['best', 'random']),
            'max_depth': hp.choice('max_depth', [None, 10, 20, 30]),
            'min_samples_split': hp.choice('min_samples_split', [2, 5, 10]),
            'min_samples_leaf': hp.choice('min_samples_leaf', [1, 2, 4])
        }

        rf_space = {
            'n_estimators': hp.choice('n_estimators', [100, 200, 300]),
            'criterion': hp.choice('criterion', ['gini', 'entropy']),
            'max_depth': hp.choice('max_depth', [None, 10, 20, 30]),
            'min_samples_split': hp.choice('min_samples_split', [2, 5, 10]),
            'min_samples_leaf': hp.choice('min_samples_leaf', [1, 2, 4]),
            'bootstrap': hp.choice('bootstrap', [True, False])
        }

        svm_space = {
            'C': hp.loguniform('C', -3, 1),  # Search space for C in log scale
            'kernel': hp.choice('kernel', ['linear', 'poly', 'rbf', 'sigmoid']),
            'gamma': hp.choice('gamma', ['scale', 'auto'])
        }

        # Perform Bayesian optimization for Decision Tree
        dt_best = fmin(fn=self.hyperopt_objective, space=dt_space, algo=tpe.suggest, max_evals=50, verbose=0)
        self.decision_tree_model = DecisionTreeClassifier(
            criterion=dt_best['criterion'],
            splitter=dt_best['splitter'],
            max_depth=dt_best['max_depth'],
            min_samples_split=dt_best['min_samples_split'],
            min_samples_leaf=dt_best['min_samples_leaf']
        )

        # Perform Bayesian optimization for Random Forest
        rf_best = fmin(fn=self.hyperopt_objective, space=rf_space, algo=tpe.suggest, max_evals=50, verbose=0)
        self.random_forest_model = RandomForestClassifier(
            n_estimators=rf_best['n_estimators'],
            criterion=rf_best['criterion'],
            max_depth=rf_best['max_depth'],
            min_samples_split=rf_best['min_samples_split'],
            min_samples_leaf=rf_best['min_samples_leaf'],
            bootstrap=rf_best['bootstrap']
        )

        # Perform Bayesian optimization for SVM
        svm_best = fmin(fn=self.hyperopt_objective, space=svm_space, algo=tpe.suggest, max_evals=50, verbose=0)
        self.svm_model = SVC(
            C=svm_best['C'],
            kernel=svm_best['kernel'],
            gamma=svm_best['gamma']
        )

    def hyperopt_objective(self, params):
        X = self.vectorizer.transform(self.current_dictionary)
        y = np.array([word[-1] for word in self.current_dictionary])

        model = DecisionTreeClassifier(**params)
        cv_score = cross_val_score(model, X, y, cv=5).mean()
        return -cv_score

    def genetic_algorithm_tuning(self):
        # Define the hyperparameter search spaces for each model
        dt_space = {
            'criterion': ['gini', 'entropy'],
            'splitter': ['best', 'random'],
            'max_depth': [None, 10, 20, 30],
            'min_samples_split': [2, 5, 10],
            'min_samples_leaf': [1, 2, 4]
        }

        rf_space = {
            'n_estimators': [100, 200, 300],
            'criterion': ['gini', 'entropy'],
            'max_depth': [None, 10, 20, 30],
            'min_samples_split': [2, 5, 10],
            'min_samples_leaf': [1, 2, 4],
            'bootstrap': [True, False]
        }

        svm_space = {
            'C': [0.1, 1, 10],
            'kernel': ['linear', 'poly', 'rbf', 'sigmoid'],
            'gamma': ['scale', 'auto']
        }

        # Perform Genetic Algorithm optimization for Decision Tree
        dt_genetic_algorithm = ga(function=self.genetic_algorithm_objective, dimension=len(dt_space), variable_type='int', variable_boundaries=[(0, len(dt_space[key]) - 1) for key in dt_space])
        dt_best_idx = dt_genetic_algorithm.run()
        dt_best = {list(dt_space.keys())[i]: dt_space[list(dt_space.keys())[i]][idx] for i, idx in enumerate(dt_best_idx)}
        self.decision_tree_model = DecisionTreeClassifier(
            criterion=dt_best['criterion'],
            splitter=dt_best['splitter'],
            max_depth=dt_best['max_depth'],
            min_samples_split=dt_best['min_samples_split'],
            min_samples_leaf=dt_best['min_samples_leaf']
        )

        # Perform Genetic Algorithm optimization for Random Forest
        rf_genetic_algorithm = ga(function=self.genetic_algorithm_objective, dimension=len(rf_space), variable_type='int', variable_boundaries=[(0, len(rf_space[key]) - 1) for key in rf_space])
        rf_best_idx = rf_genetic_algorithm.run()
        rf_best = {list(rf_space.keys())[i]: rf_space[list(rf_space.keys())[i]][idx] for i, idx in enumerate(rf_best_idx)}
        self.random_forest_model = RandomForestClassifier(
            n_estimators=rf_best['n_estimators'],
            criterion=rf_best['criterion'],
            max_depth=rf_best['max_depth'],
            min_samples_split=rf_best['min_samples_split'],
            min_samples_leaf=rf_best['min_samples_leaf'],
            bootstrap=rf_best['bootstrap']
        )

        # Perform Genetic Algorithm optimization for SVM
        svm_genetic_algorithm = ga(function=self.genetic_algorithm_objective, dimension=len(svm_space), variable_type='int', variable_boundaries=[(0, len(svm_space[key]) - 1) for key in svm_space])
        svm_best_idx = svm_genetic_algorithm.run()
        svm_best = {list(svm_space.keys())[i]: svm_space[list(svm_space.keys())[i]][idx] for i, idx in enumerate(svm_best_idx)}
        self.svm_model = SVC(
            C=svm_best['C'],
            kernel=svm_best['kernel'],
            gamma=svm_best['gamma']
        )

    def genetic_algorithm_objective(self, idxs):
        X = self.vectorizer.transform(self.current_dictionary)
        y = np.array([word[-1] for word in self.current_dictionary])

        dt_space = {
            'criterion': ['gini', 'entropy'],
            'splitter': ['best', 'random'],
            'max_depth': [None, 10, 20, 30],
            'min_samples_split': [2, 5, 10],
            'min_samples_leaf': [1, 2, 4]
        }

        rf_space = {
            'n_estimators': [100, 200, 300],
            'criterion': ['gini', 'entropy'],
            'max_depth': [None, 10, 20, 30],
            'min_samples_split': [2, 5, 10],
            'min_samples_leaf': [1, 2, 4],
            'bootstrap': [True, False]
        }

        svm_space = {
            'C': [0.1, 1, 10],
            'kernel': ['linear', 'poly', 'rbf', 'sigmoid'],
            'gamma': ['scale', 'auto']
        }

        dt_best = {list(dt_space.keys())[i]: dt_space[list(dt_space.keys())[i]][idx] for i, idx in enumerate(idxs)}
        rf_best = {list(rf_space.keys())[i]: rf_space[list(rf_space.keys())[i]][idx] for i, idx in enumerate(idxs)}
        svm_best = {list(svm_space.keys())[i]: svm_space[list(svm_space.keys())[i]][idx] for i, idx in enumerate(idxs)}

        dt_model = DecisionTreeClassifier(
            criterion=dt_best['criterion'],
            splitter=dt_best['splitter'],
            max_depth=dt_best['max_depth'],
            min_samples_split=dt_best['min_samples_split'],
            min_samples_leaf=dt_best['min_samples_leaf']
        )
        dt_cv_score = cross_val_score(dt_model, X, y, cv=5).mean()

        rf_model = RandomForestClassifier(
            n_estimators=rf_best['n_estimators'],
            criterion=rf_best['criterion'],
            max_depth=rf_best['max_depth'],
            min_samples_split=rf_best['min_samples_split'],
            min_samples_leaf=rf_best['min_samples_leaf'],
            bootstrap=rf_best['bootstrap']
        )
        rf_cv_score = cross_val_score(rf_model, X, y, cv=5).mean()

        svm_model = SVC(
            C=svm_best['C'],
            kernel=svm_best['kernel'],
            gamma=svm_best['gamma']
        )
        svm_cv_score = cross_val_score(svm_model, X, y, cv=5).mean()

        return -(dt_cv_score + rf_cv_score + svm_cv_score) / 3

    def train_all_models(self):
        X = self.vectorizer.transform(self.full_dictionary)
        y = np.array([word[-1] for word in self.full_dictionary])

        # Fit all models with the full dictionary
        self.decision_tree_model.fit(X, y)
        self.random_forest_model.fit(X, y)
        self.svm_model.fit(X, y)

        # Perform hyperparameter tuning for Decision Tree, Random Forest, and SVM models
        self.hyperparameter_tuning()

        # Train the neural network model and perform fine-tuning
        self.train_neural_network()
        self.fine_tune_neural_network()

    def word_to_numeric(self, word):
        # Convert word pattern to a binary sequence of guessed (1) and not guessed (0) letters
        return [1 if letter in self.guessed_letters else 0 for letter in word]

    def ensemble_guess(self, word_pattern):
        numeric_word_pattern = self.word_to_numeric(word_pattern)

        # Get predictions from all three models
        dt_guess = self.decision_tree_model.predict([numeric_word_pattern])[0]
        rf_guess = self.random_forest_model.predict([numeric_word_pattern])[0]
        svm_guess = self.svm_model.predict([numeric_word_pattern])[0]

        # Create a list of all model predictions
        ensemble_guesses = [dt_guess, rf_guess, svm_guess]

        # Use voting to determine the final prediction
        guessed_letter = max(set(ensemble_guesses), key=ensemble_guesses.count)

        return guessed_letter

    @staticmethod
    def determine_hangman_url():
        links = ['https://trexsim.com', 'https://sg.trexsim.com']

        data = {link: 0 for link in links}

        for link in links:
            requests.get(link)

            for i in range(10):
                s = time.time()
                requests.get(link)
                data[link] = time.time() - s

        link = sorted(data.items(), key=lambda x: x[1])[0][0]
        link += '/trexsim/hangman'
        return link

    def train_neural_network(self):
        X = self.vectorizer.transform(self.current_dictionary)
        y = np.array([word[-1] for word in self.current_dictionary])

        # Convert the word patterns to images (2D arrays)
        X_images = self.patterns_to_images(X.toarray(), self.vectorizer.vocabulary_)

        # Initialize and configure the convolutional neural network model
        neural_net_model = Sequential()
        neural_net_model.add(Conv2D(32, kernel_size=(3, 3), activation='relu', input_shape=(X_images.shape[1], X_images.shape[2], 1)))
        neural_net_model.add(MaxPooling2D(pool_size=(2, 2)))
        neural_net_model.add(Flatten())
        neural_net_model.add(Dense(128, activation='relu'))
        neural_net_model.add(Dense(64, activation='relu'))
        neural_net_model.add(Dense(26, activation='softmax'))
        neural_net_model.compile(loss='categorical_crossentropy', optimizer='adam', metrics=['accuracy'])

        # Convert labels to one-hot encoding
        y_onehot = np.zeros((y.shape[0], 26))
        for i, letter in enumerate(y):
            y_onehot[i, ord(letter) - ord('a')] = 1

        # Train the neural network model
        neural_net_model.fit(X_images, y_onehot, epochs=50, batch_size=32, verbose=0)

        # Store the trained model in the HangmanAPI object
        self.neural_net_model = neural_net_model

    def patterns_to_images(self, patterns, vocabulary):
        # Convert the patterns to images (2D arrays) with 0s and 1s
        max_pattern_length = max(len(pattern) for pattern in patterns)
        images = []
        for pattern in patterns:
            image = [0] * max_pattern_length
            for i, letter in enumerate(pattern):
                if letter in vocabulary:
                    image[i] = 1
            images.append(image)

        # Reshape the images to (num_samples, pattern_length, 1)
        images = np.array(images)
        return images.reshape(images.shape[0], images.shape[1], 1)

    def fine_tune_neural_network(self):
        X = self.vectorizer.transform(self.current_dictionary)
        y = np.array([word[-1] for word in self.current_dictionary])

        # Initialize and configure the neural network model
        neural_net_model = Sequential()
        neural_net_model.add(Dense(128, input_dim=X.shape[1], activation='relu'))
        neural_net_model.add(Dense(64, activation='relu'))
        neural_net_model.add(Dense(26, activation='softmax'))

        # Compile the model with the 'adam' optimizer
        neural_net_model.compile(loss='categorical_crossentropy', optimizer='adam', metrics=['accuracy'])

        # Convert labels to one-hot encoding
        y_onehot = np.zeros((y.shape[0], 26))
        for i, letter in enumerate(y):
            y_onehot[i, ord(letter) - ord('a')] = 1

        # Fine-tune the neural network model
        neural_net_model.fit(X.toarray(), y_onehot, epochs=100, batch_size=32, verbose=0)

        # Store the fine-tuned model in the HangmanAPI object
        self.neural_net_model = neural_net_model

    def guess(self, word):
        # Clean the word so that we strip away the space characters
        # Replace "_" with "." as "." indicates any character in regular expressions
        clean_word = word[::2].replace("_", ".")

        # Find length of the passed word
        len_word = len(clean_word)

        # Grab current dictionary of possible words from self object, initialize a new possible words dictionary to empty
        current_dictionary = self.current_dictionary
        new_dictionary = []

        # Iterate through all of the words in the old plausible dictionary
        for dict_word in current_dictionary:
            # Continue if the word is not of the appropriate length
            if len(dict_word) != len_word:
                continue

            # If dictionary word is a possible match, then add it to the current dictionary
            if re.match(clean_word, dict_word):
                new_dictionary.append(dict_word)

        # Update Q-table state for the current word pattern
        current_state = clean_word

        # With probability epsilon, explore by choosing a random letter
        if random.random() < self.epsilon:
            # Randomly select a letter from the target labels
            guessed_letter = random.choice(self.target_labels)
        else:
            # With probability (1 - epsilon), exploit by choosing the letter with the highest Q-value
            # Choose the letter with the highest Q-value for the current state
            q_values_for_state = {action: self.q_table.get((current_state, action), 0.0) for action in self.target_labels}
            guessed_letter = max(q_values_for_state, key=q_values_for_state.get)

        # Update Q-table state for the next word pattern after making the guess
        next_word_pattern = word.replace("_", guessed_letter)
        next_state = next_word_pattern[::2].replace("_", ".")

        # Update the Q-table based on the observed reward and the next state
        # We don't have access to the actual reward in this implementation, so set it to 0 for now
        reward = 0
        self.update_q_table(current_state, guessed_letter, reward, next_state)

        # Overwrite old possible words dictionary with the updated version
        self.current_dictionary = new_dictionary

        # If there are no remaining words that match, default back to the ordering of the full dictionary
        if not new_dictionary:
            sorted_letter_count = self.full_dictionary_common_letter_sorted
        else:
            # Update the current dictionary with the new_dictionary
            self.current_dictionary = new_dictionary

            # Get the count of each letter at each position in the current dictionary
            letter_counts = [{letter: sum(1 for word in self.current_dictionary if word[i] == letter) for letter in self.target_labels}
                            for i in range(len(clean_word))]

            # Choose the character with the highest count at the next position
            next_position = len(self.guessed_letters)

            # If all letters have been guessed, use fallback guess from full dictionary ordering
            if next_position >= len(letter_counts):
                return self.ensemble_guess(clean_word)

            guessed_letter = max(letter_counts[next_position], key=letter_counts[next_position].get)

            # Remove the guessed letter from the possible letters in current_dictionary
            self.current_dictionary = [word for word in self.current_dictionary if guessed_letter not in word]

            return guessed_letter

        # Return the letter with the highest information gain that hasn't been guessed yet
        for letter, info_gain in sorted_letter_count:
            if letter not in self.guessed_letters:
                return letter

        # If all letters have been guessed, revert to ordering of full dictionary (fallback)
        return self.ensemble_guess(clean_word)

    def make_decision(self, word_pattern, models=['dt', 'rf', 'svm'], use_neural_net=True):
        # Clean the word pattern so that we strip away the space characters
        # Replace "_" with "." as "." indicates any character in regular expressions
        clean_word = word_pattern[::2].replace("_", ".")

        # Filter the full dictionary to get the current dictionary of possible words
        self.current_dictionary = [word for word in self.full_dictionary if re.match(clean_word, word)]

        # If there are no remaining words that match the pattern, return the fallback guess
        if not self.current_dictionary:
            return self.ensemble_guess(clean_word)

        # Extract features from the clean word pattern
        features = self.extract_features(clean_word)
        # Convert the features to a 2D array (samples x features) to use with the neural network
        pattern_features = np.array(features).reshape(1, -1)

        # Initialize a list to store the predictions from different models
        predictions = []

        # Initialize a list to store the classifiers for the ensemble
        classifiers = []

        # Add the desired models to the ensemble classifiers list
        if 'dt' in models:
            classifiers.append(('DecisionTree', self.decision_tree_model))
        if 'rf' in models:
            classifiers.append(('RandomForest', self.random_forest_model))
        if 'svm' in models:
            classifiers.append(('SVM', self.svm_model))

        # Create a VotingClassifier with the selected models
        voting_classifier = VotingClassifier(estimators=classifiers, voting='hard')

        # Train the ensemble classifier with the current dictionary
        X = self.vectorizer.transform(self.current_dictionary)
        y = np.array([word[-1] for word in self.current_dictionary])
        voting_classifier.fit(X, y)

        # Use the trained ensemble model to make a prediction
        ensemble_prediction = voting_classifier.predict(pattern_features)

        # Get the count of each letter at each position in the current dictionary
        letter_counts = [{letter: sum(1 for word in self.current_dictionary if word[i] == letter) for letter in self.target_labels}
                        for i in range(len(clean_word))]

        # Choose the character with the highest count at the next position
        next_position = len(self.guessed_letters)

        # If all letters have been guessed, use fallback guess from full dictionary ordering
        if next_position >= len(letter_counts):
            return self.ensemble_guess(clean_word)

        # Calculate the conditional probabilities of each letter given the word pattern
        letter_probabilities = {}
        total_letter_count = sum(letter_counts[next_position].values())
        for letter in string.ascii_lowercase:
            if letter not in self.guessed_letters:
                matching_words_count = letter_counts[next_position].get(letter, 0)
                conditional_probability = matching_words_count / total_letter_count
                # Calculate the information gain using entropy (log2)
                information_gain = -conditional_probability * math.log2(conditional_probability) if conditional_probability > 0 else 0
                letter_probabilities[letter] = information_gain

        # Choose the letter with the highest information gain as the next guess
        guessed_letter = max(letter_probabilities, key=letter_probabilities.get)

        return guessed_letter

    def compute_conditional_probabilities(self, word_pattern):
        # Count the occurrence of each letter in the possible words
        full_dict_string = "".join(self.current_dictionary)
        c = collections.Counter(full_dict_string)

        # Calculate the total count of letters in the possible words
        total_letter_count = sum(c.values())

        # Calculate the conditional probabilities of each letter given the word pattern
        letter_probabilities = {}
        for letter in string.ascii_lowercase:
            if letter not in self.guessed_letters:
                pattern_with_letter = word_pattern.replace(".", letter)
                matching_words_count = sum(1 for word in self.current_dictionary if re.match(pattern_with_letter, word))
                conditional_probability = matching_words_count / total_letter_count
                # Calculate the information gain using entropy (log2)
                information_gain = -conditional_probability * math.log2(conditional_probability) if conditional_probability > 0 else 0
                letter_probabilities[letter] = information_gain

        return letter_probabilities

    def build_dictionary(self, dictionary_file_location):
        text_file = open(dictionary_file_location, "r")
        full_dictionary = text_file.read().splitlines()
        text_file.close()
        return full_dictionary

```
1. **init**(self, access\_token=None, session=None, timeout=None): The constructor initializes the HangmanAPI object. It sets up the API URL, access token, and session for making HTTP requests to the Hangman game server. It also loads a full dictionary of words and initializes machine learning models (Decision Tree, Random Forest, SVM) and a Q-table for reinforcement learning.
2. update\_q\_table(self, state, action, reward, next\_state): This function updates the Q-values in the Q-table using the Q-learning update rule.
3. extract\_features(self, word\_pattern): Extracts features from the given word pattern to be used by machine learning models for making guesses.
4. hyperparameter\_tuning(self): Performs hyperparameter tuning for the Decision Tree, Random Forest, and SVM models using Bayesian optimization.
5. genetic\_algorithm\_tuning(self): Performs hyperparameter tuning for the Decision Tree, Random Forest, and SVM models using a genetic algorithm.
6. train\_all\_models(self): Trains all the machine learning models, performs hyperparameter tuning, and trains a convolutional neural network (CNN) model.
7. word\_to\_numeric(self, word): Converts a word pattern to a binary sequence of guessed (1) and not guessed (0) letters.
8. ensemble\_guess(self, word\_pattern): Makes a guess for the given word pattern using an ensemble of Decision Tree, Random Forest, and SVM models.
9. determine\_hangman\_url(self): Determines the Hangman game server URL to be used based on response times to different server URLs.
10. train\_neural\_network(self): Trains a convolutional neural network (CNN) model using features extracted from the current dictionary of words.
11. fine\_tune\_neural\_network(self): Fine-tunes the neural network model using features extracted from the current dictionary of words.
12. guess(self, word): Makes a guess for the given word pattern using the Q-learning algorithm and the current state of the game.
13. make\_decision(self, word\_pattern, models=\['dt', 'rf', 'svm'\], use\_neural\_net=True): Makes a guess for the given word pattern using an ensemble of machine learning models and the Q-learning algorithm.
14. compute\_conditional\_probabilities(self, word\_pattern): Computes the conditional probabilities of each letter given the word pattern.
15. build\_dictionary(self, dictionary\_file\_location): Loads a full dictionary of words from a text file.

I am trying to improve the accuracy above 10% to atleast 50%. I tried implementing multiple techniques together and choosing the one that works best based on scoring mechanism and then hyper-tuning the parameters. I also tried reinforcement learning, yet the result is abysmally low.

All suggestions will be helpful.

# Answer
> 0 votes
I suggest you use a brute-force greedy algorithm, where you brute-force explore all possible guesses and all possible candidates for the secret word and see which guess leads to the most ambiguity about the secret word. See https://en.wikipedia.org/wiki/Mastermind\_(board\_game)#Algorithms\_and\_strategies, Mastermind (board game) - Five-guess algorithm, https://stackoverflow.com/q/1185634/781723, https://arxiv.org/abs/2202.00557.

---
Tags: algorithms, strings, python, mathematical-analysis
---


# Question
Title: How to allocate memory for prime numbers
I was working on an algorithm to find prime numbers, and I needed to allocate memory for each prime number that I found so far. I will do a search up to N and need to allocate all memory in advance. I found the following : https://t5k.org/howmany.html . This gave me some nice approximations for how many numbers I should allocate.

However the accurate approximations used Riemann zeta function and all seemed to be rather computationally expensive. I need a way to find the number of prime numbers under N that is both fast (O(log(N)) or constant preferably) and will never give a number back that is less then the number of prime numbers before N.

I could of course just ceil(take N/2) but I intend to allocate the absolute minimum of memory. As in my case space complexity is of essence. Does anyone know an elegant solution? Thanks in advance.

PS : right now I am using ceil(N/ln(N)) + 1000 as a temporary solution.

# Answer
I suggest you allocate space for $$U = \max(N/(\ln(N) - 1.1), N/\ln(N) + 2000).$$

This will be quite close to the true number. For instance, for $N=10^7$, it is only 1284 larger than the true number. Using a few thousand extra words of memory is hardly worth worrying about.

Moreover, I expect that the chance that the true number of primes exceeds $U$ is either zero, or so small as to not be worth worrying about. In particular, it is apparently known that the true number is less than $N/(\ln(N) - 1.1)$ for all $N \ge 60184$ (see https://en.wikipedia.org/wiki/Prime\_number\_theorem#Non-asymptotic\_bounds\_on\_the\_prime-counting\_function), and for $N \< 60184$ I expect the true number will be less than $N/\ln(N) + 2000$.
> 2 votes

---
Tags: algorithms, space-complexity, primes
---


title: Fast $k$-clique checking algorithm?

text:
# Question
Title: Fast $k$-clique checking algorithm?
I have a problem where part of it requires answering the question: *does graph $G=(V,E)$ contain a clique of size at least $k$?*

Obviously, answering this question is a NP-Complete problem. I am no trying to find a polynomial time algorithm. I am trying to find an empirically fast algorithm that works well for moderately large graphs (say $|V| \< 100,000$).

I have already tried a few approaches, like:

1. dOmega library: https://github.com/jwalteros/dOmega/tree/master
2. Cliquer: https://users.aalto.fi/~pat/cliquer.html
3. Quick cliques (although this is for enumerating all cliques): https://github.com/darrenstrash/quick-cliques

None of these approaches seem to work well for what I want. However, I also have the feeling that none of them is using information about $k$ to maybe speedup search (not sure if this makes sense to be honest). Approach (1) tries to solve a Max-Clique, approach (2) uses Bron-Kerbosch algorithm even though it has a function to search for a single clique of a given size, and (3) enumerates all cliques.

I don't need the clique itself, just identifying whether $G$ has a clique of size at least $k$. Alternatively, I am happy with any bound technique that has reasonable tightness to answer whether $G$ cannot have for sure a clique of size at least $k$. For example, I know that the largest clique size $\omega$ of $G$ with degeneracy $d$ respects the relation $\omega \leq d+1$. Unfortunately, computing degeneracy of my graphs has proven fruitless since the bound is typically not tight enough to help with any information.

Does anyone have a suggestion? Converting the clique problem into something else is also a possibility, in case this could help with finding a *empirically fast* algorithm.

**Edit:** for clarification. We cannot rely on a commercial ILP solver. Ideally, we would like a special-purpose algorithm, or if an open-source ILP solver can handle large instances, then this can also be considered.

Values of $k \leq 20$ we can already handle well with our current approach. We are looking at an algorithm to do the same quickly when $30 \leq k \leq 200$. *Techniques that offer good bounds are also very much welcome*.

Average degree of nodes varies widely. For example, some instances with 800 nodes have average node degree of $\approx 290$ while some with 2000 nodes also have $\approx 300$. The ratio between $k$ and $\omega$ (the actual max-clique) also varies, but so far we have seen ratios $0.5 \leq \frac{\omega}{k} \leq 2$.

We don't have any particular structure in the graph (not one that we are of anyway).

# Answer
I suspect you are likely to be out of luck. My advice is to try to find some other way to meet your business needs without requiring you to solve this computational task. The clique problem is NP-hard, so you should not expect any efficient algorithm for your problem.

In particular, testing whether there exists a clique of size $\ge k$ is as hard (under worst-case complexity) as finding the size of the maximum clique. (The reduction: if you had an algorithm for testing the existence of a clique, then you could use binary search on $k$ to find the size of the maximum clique.) Indeed, the usual way of proving that the clique problem is NP-hard focuses on the decision problem (given a graph and $k$, test whether there is a clique of size $\ge k$) rather than on the optimization problem (given a graph, find the size of the maximum clique), so you are already considering exactly the same problem that is studied in complexity theory.

Standard approaches for dealing with NP-hardness are to look for approximation algorithms, fixed-parameter tractable algorithms, or algorithms whose worst-case running time is exponential but maybe fast enough in practice. However, approximation algorithms are a dead end: the clique problem is hard to NP-hard even to approximate to within an approximation ratio of $O(n^{1-\epsilon})$ -- or in other words, it is very hard even to approximate the size of the largest clique, even with a very rough/crude approximation. Also, the clique problem is believed to not be fixed-parameter tractable. Especially, assuming the exponential time hypothesis, no algorithm can solve the problem in $n^{o(k)}$ time -- or in other words, you should not expect an algorithm that works on all possible graphs, using only the fact that $k$ is small, and has a reasonable running time. See https://en.wikipedia.org/wiki/Clique\_problem#Approximation\_algorithms, https://en.wikipedia.org/wiki/Clique\_problem#Fixed-parameter\_intractability.

One reasonable approach is to use a dedicated clique solver. It seems you have already tried that.

Another reasonable approach is to use an ILP solver or SAT solver. I'll list below some ways that you can formulate this as an ILP/SAT instance. However, I expect that these will fail once $k$ gets large enough, so I am not optimistic that these will lead to a useful solution for your specific problem with your particular parameters. My uneducated guess would be that maybe there simply is no algorithm with the characteristics you are hoping for.

# SAT

There are many ways to encode the clique problem as a SAT instance. If this is a critical problem, I would suggest you explore all options to see what works best on the kinds of instances you face.

One approach is to introduce boolean variables $x\_v$, one per vertex $v \in V$ of the graph. For each $(u,v) \notin E$, add a clause $\neg x\_u \lor \neg x\_v$. Also, add the constraint that at least $k$ of the $x$'s be true (see Encoding 1-out-of-n constraint for SAT solvers, Reduce the following problem to SAT, https://stackoverflow.com/q/43081929/781723). This requires $n$ boolean variables and something like $n^2+O(n \log^2 k)$ clauses, with all clauses being small.

Another approach is to introduce boolean variables $x\_v$, one per vertex $v \in V$, and $y\_{u,v}$, one per edge $(u,v) \in E$ with $u\<v$. Add clauses $x\_u \lor \neg y\_{u,v}$, $x\_v \lor \neg y\_{u,v}$, $\neg x\_u \lor \neg x\_v \lor y\_{u,v}$ for each $(u,v) \in E$ with $u\<v$. Also, add the constraints that at least $k$ of the $x$'s be true and at least $k(k-1)/2$ of the $y$'s be true. This requires $n+m$ boolean variables and something like $O(m \log^2 k)$ clauses, with all clauses being small. (Here $n =$ the number of vertices, $m =$ the number of edges.)

There are probably many other encodings into SAT.

Then, you can use an off-the-shelf SAT solver, of which there are many excellent ones.

# Integer Linear Programming

You can also use effectively the same encoding into ILP. Each variable becomes a zero-or-one integer variable. Each clause has a direct translation to ILP (e.g., $r \lor s \lor t$ becomes $r + s + t \ge 1$). The one main difference is that the $k$-out-of-$n$ constraint can be encoded very easily using a single linear inequality.

Finally, you can give this to an ILP solver, such as Gurobi.
> 0 votes

---
Tags: algorithms, graphs, clique
---


# Question
Title: Help in defining value function for 0/1 knapsack
I would like to set up some type of automation/suggestion tool for buying items on a limited spending budget. To try to somewhat formalise the problem, one could suggest to reduce this to a 0/1 knapsack problem with item *i* having price $p\_i$ and value $v\_i$ and then finding a set of items that maximise the total value, respecting $\sum\_{i \in I} p\_i \leq b $, where b is my budget.

However, I would need to define a value function *F* mapping from the set of items to say integers. I could potentialy define this function as a weighted linear sum, where there are some properties that I care about and weigh the property accordingly. Are there better approaches or functions for this issue of mine?

# Answer
> 0 votes
I think you have a misunderstanding. In the knapsack problem, there is a value for each item. You get to define those values.

The value of a set of items is already defined. You don't get to define it. The value of a set of items is the sum of the values of the items in the set. Period. That is it. There is no flexibility. If you want to change that, it's not the knapsack problem any longer, it is some variant of the knapsack problem. With the standard knapsack problem, once you have specified the value of each individual item, that fully determines the values of every possible set.

---
Tags: algorithms
---


# Question
Title: Estimating the number of elements shared in two sets using a random sample
Suppose we have two sets $A$ and $B$. The sets share some number of elements between them, but within each set, any item appears at most once. We want to determine how many elements they share in common.

There are many algorithms to estimate this: MinHash, HyperLogLog, etc. However, all of these algorithms, and others I know of, require us to actually make one pass through the entirety of the sets $A$ and $B$, which can be difficult if the sets are large.

**Are there any algorithms which can estimate any of these quantities from a smaller sample drawn from the data sets, without having to read the entirety of each set**?

Some requirements for this problem:

1. The elements in the sets are stored in random order on disk. Even if identical the second can be a nontrivial permutation of the first.
2. I am interested in a general-purpose scalable algorithm to solve this problem, but in my particular situation, each set varies from about 1 million to 1 billion elements, typical intersection size not currently known. The sets we are comparing also need not be the same size as one another.
3. Any successful solution to this problem should reduce the amount of data we need to parse by a few orders of magnitude. It is alright if the sample size needs to increase for larger data sets, or if there is some kind of tradeoff between sample size and accuracy.

Surprisingly, there does seem to be technique which seems to work pretty well, although it needs to be dialed in a bit. It is basically an even-more-stochastic version of MinHash which estimates the total overlap of the two sets from the overlap of a significantly smaller sample. I will post this as an answer in the comments and am curious if it is at all well-known.

# Answer
> 1 votes
The MinHash algorithm is precisely the HyperLogLog-style probabilistic algorithm for approximating the cardinality of the intersection of multiple sets you're looking for.

# Answer
> 0 votes
Here is the technique I've been using. This is fairly preliminary but seems to give extremely good results, at least for my use case, where it has reduced the amount of data I need to parse by several orders of magnitude. The general technique seems quite sound and scalable to arbitrary size.

This turned out to be much longer than expected - probably too long for a StackExchange post, but not long enough to be an entire description of all the nuances of this problem. Whatever: the purpose of this is just to ask **does this already exist?** Are people doing this? What is it called?

If anyone knows any literature references where people are doing things like this, I would love to see them! It seems like a very basic idea but so far it doesn't seem well-known; if it isn't maybe I'll write this up properly and put it on arXiv or something, as it seems to be *thousands* of times faster than just using MinHash naively (for large data sets).

**TL;DR**: Suppose you want to measure the Jaccard Similarity of two sets $A$ and $B$ of equal size $N$, with some desired error rate $\epsilon$. Then simply take one sample from each, which I'll call $S\_A$ and $S\_B$. The magic sample size you want, assuming $\epsilon$ is somewhere between $0.5%$ and $10%$ and $N$ is somewhere between 100,000 and 1 billion, is:

$$ |S\_A| = |S\_B| = \frac{0.6325}{\epsilon}\sqrt{N} $$

where that 0.6325 value is something I've just measured empirically from a lot of Monte Carlo sampling.

Simply take one sample of this size from each set, and measure the size of the sample intersection $|S\_A \cup S\_B|$ using any method that is precise enough that the error is negligible (e.g. "Good enough MinHash"). Then, the magic formula to estimate the size of the true set intersection from this is:

$$ \frac{|S\_A \cup S\_B| \epsilon^2 N}{0.4} $$

And from there you can estimate the Jaccard similarity or whatever else.

I'll just leave these spooky looking magic values here for now and just say that this really works: you can run your own simulations and see it for yourself. However, most notably, note that the sample size scales with the **square root** of $N$. So if your sets have 1 billion items each, and you want 2% precision, you only need to take a sample size of **1 million items** each -- this is three orders of magnitude less data than processing the entire thing. If your sets have 10 million items each, your sample size needs to only be about 316,000 things. And so on.

I will also note that, at least from preliminary testing, this algorithm "plays nice" with MinHash. That is, if you use this with MinHash, there are two sources of approximation error: the error from MinHash itself, and the sampling error. The goal is to minimize the total number of hashes done for some given amount of error, and to do this, we want to balance "how much error" is introduced from MinHash and how much from sampling (given that MinHash's required number of hashes is inversely quadratic in the error, whereas this seems to be inversely linear in the sample size). In general, there seems to be a nontrivial minimum value for this! But we'll leave that for another time: for now, the point is that this idea of running MinHash on the samples can speed things up very significantly for a similar amount of error.

OK, that's the basic intro. Again, would appreciate some pointers if anyone has seen this before. Let's look at how it works.

---

The basic idea: suppose we have two sets that really are identical. Then, through sheer random chance, two different random samples, one drawn from each set, will share some expected amount of items. You can think of this as a phenomenon related to the birthday paradox, if you like; the point is that it's more items than you'd expect.

Now, they're expected to share that number of items only if the sets really are identical. On the other hand, if the two sets are totally distinct, then we expect the two samples to share no items at all. If the two sets are somewhere in between, we expect the two samples to share some intermediate amount of items.

Thus, the sample intersection can be used to estimate the size of the true intersection, for a sample that is much smaller than the actual data set: as we will see, the sample size scales with the square root of the data size (for a certain level of precision).

Let's put some figures to this with a typical situation:

1. Suppose you have two sets $A$ and $B$ of 1 billion items each, and you take independent random samples $S\_A$ and $S\_B$ from each with 1 million items each.
    1. If the sets are identical, it so happens that we expect $|S\_A \cap S\_B| ≈ 1000$.
    2. If the sets are totally distinct, we expect $|S\_A \cap S\_B| = 0$.
    3. If the sets are somewhere in between, then the quantity $|A \cap B|/|A| = |A \cap B|/|B| = I$, then it turns out that we expect $|S\_A \cap S\_B| ≈ 1000\*I$.
    4. Thus, it turns out, that as a very basic estimate, we can estimate the true intersection size as $|A \cap B| ≈|S\_A \cap S\_B|/1000 * |A|$.
    5. To evaluate how precise this estimate is, we can use our intersection size estimate to compute the Jaccard Similarity $|A \cap B|/|A \cup B|$ between the two sets, and then measure the expected error from the estimated similarity to the true similarity (which seems to be a reasonably well-used benchmark). If we do this, and assuming the true intersection size is uniformly distributed (and could thus be anything), this yields about **2% relative error** when estimating the Jaccard Similarity.
    6. These expressions were all determined empirically, e.g. by running Monte Carlo simulations. We will leave the details of a rigorous analytic proof for the future, but for now anyone can do their own Monte Carlo simulations and see that these figures are basically correct.

This is ridiculously good! We've gotten something to within 2% precision **and we only needed to read 2 million items to do it**. That is three orders of magnitude less data than the original algorithm. And, somewhat amazingly, given this level of precision, the sample size seems to only need to increase with the **square root of the data size**. In other words, if we like our 2% level of precision, and we want similar results comparing two data sets of **10 billion** items, we only need to take two samples of about **3.16 million** to get the same level of precision. Similarly, if we only care about **100 million** items, a sample size of **316,227** will give the same results.

There are a few improvements we can make on the above:

1. The standard deviation of the error using our naive method is about the same as the error itself. We can try various ways to improve this (although this seems to be alright). So far, the best way to improve it seems to just be to increase the size of the sample (doubling the sample size seems to halve both the expected error *and* the standard deviation of the error).
2. We can use a better estimator than the naive one used above, where we just scale the relative proportion up - this can even lead to us estimating the true intersection size to be larger than the size of the sets. Instead, we could use a maximum-likelihood estimator, or perhaps make some simple adjustment to the naive estimator to improve things a bit.
3. We also note that the expected error depends on the distribution of true intersection sizes. If there is a uniform distribution on the set of possibilities regarding what the intersection size could be, then the figures are (again, empirically measured) what I put above. If the true intersection size is 0, on the other hand, this will always give the correct result as it will always estimate 0. And if the two sets are identical, the error will tend to a maximum. So, in the example above, while the average error was 2%, the average error if the sets really are identical is about 4.8%.
4. We note that this method above assumes that we've measured the *true* sample intersection, rather than estimating *that* with *another* probabilistic estimator (e.g. MinHash). However, of course, the ultimate goal is to use something like MinHash to estimate the size of the sample intersection as well, as long as you're willing to add a bit more relative error to the end result. The question of how much precision you should try to get from MinHash, vs from the sampling, and how to balance these two things, seems very interesting.

---

Actually making this rigorous and deriving these expressions in closed form requires a bunch of fairly tedious statistics algebra, although straightforward. Since I've spent enough time on this for now, I will just leave it that anyone can run their own simulations to verify these results seem to be correct (for now assuming both sets are equal in size):

1. If you want ~2% precision, you should try to choose your sample size so that if the two sets *are* identical, the two samples are expected to share about 1000 elements (as a very basic guideline).
2. The magic sample size that gives this result for 2% seems to be $\sqrt{1000 * N}$ (again, assuming $N = |A| = |B|$ for now. So if $N = 10^9$, then the sample size should be $10^6$; if $N = 10^6$ then you want $31623$, etc.
3. From this baseline, if you want to halve the expected error, then the sample size should increase by a factor of two. (This is, of course, approximate, but seems to be a decent guideline within this precision range.)

Putting it all together, if $\epsilon$ is the error rate you want (somewhere around 2%, let's say), and $N$ is the number of items in both of your sets, the sample size you want seems to be determined using this formula:

$$ \frac{0.6325}{\epsilon}\sqrt{N} $$

which, again, is determined empirically, and gives a decent ballpark estimate for $\epsilon$ in the range of 0.5% to 10% and $N$ in the range 100000 to 1 billion. And then our estimator corresponds to this:

$$ \frac{|S\_A \cup S\_B| \epsilon^2 N}{0.4} $$

---
Tags: algorithms, terminology, reference-request, approximation
---


title: Equivalent logical statements confusion

text:
# Question
Title: Equivalent logical statements confusion
First time posting here. If we have the logical statement ($A$ and $B$) $\rightarrow$ $C$ ($1$), we know that it is equivalent to ($A$ and $B$) $\rightarrow$ ($C$ and $A$) ($2$). Therefore if we wanted to prove the $\iff$ case for the first statement, we would need to prove $C$ $\rightarrow$ ($A$ and $B$). All good here. And if we wanted to prove the second statement's $\iff$ case we would have to prove ($C$ and $A$) $\rightarrow$ ($A$ and $B$). Now I would like to ask, as ($1$) and ($2$) are the same, why is showing ($C$ and $A$) $\rightarrow$ ($A$ and $B$) not identical to showing ($C$ ) $\rightarrow$ ($A$ and $B$)? Thank you all so much for reading.

# Answer
> 0 votes
Let $B$ be $\text{true}$. The direct theorems simplify to

$$(A\implies C)\equiv(A\implies C\land A).$$

Now with $B$ $\text{false}$,

$$(\text{false}\implies C)\equiv(\text{false}\implies C\land A)$$ which are trivially correct.

If we now look at the inverses,

$$(C\implies A)\equiv(C\land A\implies C)$$

and

$$(C\implies\text{false})\equiv( C\land A\implies\text{false}),$$ we can easily find counter-examples.

The reason is that $C\land A$ is a stronger condition than $C$ alone, it takes both $A$ and $C$ to be true.

---
Tags: logic
---


title: Subtracting Two same asymptotic values

text:
# Question
Title: Subtracting Two same asymptotic values
I am dealing with two values $a$ and $b$ such that they grow at the same asymptotic rate, i.e., $O(\frac{1}{\sqrt{N}})$. I want to achieve a reasonable bound for the difference $a - b$. When I go into the fundamentals in terms of $c\_1, c\_2$, I run into multiple issues. The difference be $(c\_1 - c\_2)\frac{1}{\sqrt{N}}$. Here we can cases for which this function becomes negative, thus defining it as $O(1)$. Or if it is positive, then it will be $O(\frac{1}{\sqrt{N}})$.

I know that when dealing with differences, asymptotic bounds of the form $O$ do not work very well since they talk about $\exists c$. I want to get some insights on how to proceed, am I recommended to switch to a different form of bound, perhaps $o$ bound?

# Answer
> 2 votes
I make an example: if $a=\frac{2}{\sqrt{n}}$ and $b=\frac{1}{\sqrt{n}}$, then both are $O(\frac{1}{\sqrt{n}})$ and $a-b=\frac{1}{\sqrt{n}}=O(\frac{1}{\sqrt{n}})= \Theta (\frac{1}{\sqrt{n}})$. If instead $a=b=\frac{1}{\sqrt{n}}$, then we have $a-b=0=O(1)$.

As you can see, without further information on $a$ and $b$, the only thing we can say is that $a-b=O(\frac{1}{\sqrt{n}})$.

The fact is that, without further information about $a$ and $b$, you can't know the constants $c\_1$ and $c\_2$ (nor the lower order terms).

Why do you want to subtract terms in big-O notation? Is this operation well-defined? Think about it

# Answer
> 1 votes
If $a(n),b(n)=O(g(n))$ then without more information, all you can say is $a(n)-b(n)=O(g(n))$, even if the asymptotic constants are the same and are tight.

Even worse, if $a(n),b(n)=\Theta(g(n))$ then without more information, all you can say is $a(n)-b(n)=O(g(n))$, even if the respective tightest upper and lower asymptotic constants are the same!

Example: $H\_n$ ($n^{\text{th}}$ harmonic number), $\lg(n)$ (base $2$ logarithm) and $\log(n)+\gamma$ (Mascheroni's constant) are all three $\Theta(\log(n))$.

Then $H\_n-\lg(n)=\Theta(\log(n))$, $H\_n-\log(n)=\Theta(1)$, and $H\_n-(\log(n)+\gamma)=\Theta(n^{-2})$. All these differences are $O(\log(n))$.

---
Tags: asymptotics, big-o-notation
---


# Question
Title: Is the Busy Beaver with n states also the busiest Turing machine (counted in steps) with n states?
Based on the Busy Beaver rules (2 letter alphabet, 2-way unbounded tape, program must halt, etc) I was wondering if the Busy Beaver for each n is also the program that does the most steps, or if there are other programs that do more steps but produce less output.

Any references appreciated.

# Answer
If you look at the Wikipedia page for the Busy Beaver game (https://en.wikipedia.org/wiki/Busy\_beaver) there is a section about "Maximum Shifts Function" which seems to answer your question.
> 1 votes

---
Tags: turing-machines, busy-beaver
---


# Question
Title: N Queens Problem - Number of Possible Placements
So, I have been looking into the famous back tracking problem called N Queens. The problem is essentially finding the number of possible ways you can place a n number of queens on a n x n chess board such that all of the queens are not in any other attack positions from other queens on the board.

I came across the following statement on Wikipedia: “The problem of finding all solutions to the 8-queens problem can be quite computationally expensive, as there are 4,426,165,368 possible arrangements of eight queens on an 8×8 board,\[a\] but only 92 solutions.” The link for the article is here: https://en.wikipedia.org/wiki/Eight\_queens\_puzzle

I was confused since it states there are **4,426,165,368** possible arrangements of the queens on a 8 by 8 board. According to my calculations the number of possible arrangements for n queens on a n x n board is equal to the following (the logic for the below equation is similar to the n choose k permutation formula):

So, in the 8x8 case the number of possible arrangements would be 64 * 63 * 62 * 61 * 60 * 59 * 58 * 57, which is equal to **178,462,987,637,760**.

What is the reason for the differences in our calculations?

# Answer
> 2 votes
4,426,165,368 is the number of ways to place 8 *identical* queens into 64 places, i.e the number of combinations. "Identical" means positions are considered equivalent if one queen is swapped to another queen.

Each combination corresponds to $8!$ positions if the queens are non-identical. Therefore,

$$ 64!/(64-8)!/8! = 178462987637760/40320 = 4426165368 $$

# Answer
> 0 votes
About the "computationally expensive": They calculated the number of ways to put eight queens onto 8 fields of an 8x8 chessboard, ignoring the identity of the queens.

But anybody in their right mind trying to place 8 queens in a way that they don't attack each other wouldn't try to place two queens into the same row, but would put one queen each into row 1, row 2, row 3, ..., row 8. So the number of reasonable positions is only $8^8$ or 16,777,216, about 264 times smaller.

But that number will be again much reduced if you don't try to place a queen into row three if the one in row two attacks the one in row 1, and don't try to place a queen into row four if the one in row three attacks the ones in row 1 or 2, and so on.

# Answer
> 0 votes
To compute the number of possible arrangements of the queens on a 8 by 8 board, you can compute the following:

Number of ways of placing 8 queens on the board / Number of ways of arriving at each unique configuration of the queens

i.e.

(64 × 63 × 62 × 61 × 60 × 59 × 58 × 57)/(8 × 7 × 6 × 5 × 4 × 3 × 2 × 1) = 4,426,165,368

---
Tags: combinatorics
---


# Question
Title: Can I Use Machine Learning to Predict the Likelihood of an Order Being Shipped?
Let's say I have a database of freight orders. The job is to match freight carriers with customers who need their freight moved. I have the customer's information, the freight carrier's information, and all details related to the freight orders including date ordered, date shipped, the amount of money it took to hire the freight carrier, and whether a carrier was even found to ship the order.

If I have thousands of these past freight orders, **could I use machine learning to look at future freight orders to predict whether or not a freight carrier will be found to move it?**

Bonus: If it is possible, what steps would I need to take to find the best data points to focus on? From what I understand, I need to convert everything to a number in order to train the classifier, but I am having trouble figuring out what data features are going to help make these types of predictions.

I have been studying how to do machine learning and I am not looking for somebody to tell me everything there is to know on the subject, I just don't know how to determine what data points are going to be useful and am also looking for an answer to whether or not this is something machine learning can do(or if it's something a beginner in machine learning can do). Sorry if the question seems vague, it's kind of hard to articulate on a subject you are just starting to learn about. If anybody has materials they can link that would help me to better understand these things, I would appreciate that as well..

# Answer
Here's the thing to know: machine learning assumes that there is some sort of statistical distribution, and you "learn" that distribution, in order to get the probability of some event.

The common saying in machine learning is "garbage in, garbage out." You have a bunch of random variables, but if those variables are all statistically independent, then you won't get anything useful from machine learning.

Say, for example, that there was a strong correlation between the amount of money paid for the carrier, and whether the item is shipped. Machine learning would likely be able to discover this relationship.

Or, if there were certain periods of the year where an item was more or less likely to be shipped. Machine learning could find this out.

But, if there's no underlying pattern in the data you give to your training algorithm, then you will get no useful information out of it.

For your question of finding the best data points: don't. That's what the machine learning algorithm is for. You give it your data, and it looks at which ones are statistically relevant, given some threshold. The whole point of machine learning is letting the algorithm do that for you, and more importantly, that's all the algorithm can really do for you.

Generally, these algorithms will work better when they have more data, so don't go out of your way to remove what data you're giving it.

And, remember, that ALL these algorithms are doing is statistics. If it says that the item is shipped with probability 0.6, don't be surprised when it isn't shipped. And, it's possible that it will say the item is shipped with probability 0.99, but it won't ship, because there's some variable which is hugely important in real life, which you didn't have recorded for your data set. If that variable isn't correlated with your data, then your model will be no good.
> 4 votes

# Answer
Yes, you can definitely use machine learning to predict the likelihood of an order being shipped. This prediction can be helpful for various purposes, such as optimizing inventory management, improving logistics, and providing better customer service by anticipating delays.

Here's an example of how you could approach building a machine learning model to predict the likelihood of an order being shipped on time:

Data Collection: Gather historical data on orders from your database or e-commerce platform. The data should include features such as order date, shipping date, order location, shipping location, product type, shipping method, and any other relevant information.

Data Preprocessing: Clean and preprocess the data to handle missing values, encode categorical variables, and scale numerical features if necessary. This step is crucial for ensuring the data is in a suitable format for machine learning algorithms.

Feature Engineering: Create additional features that might be useful for predicting shipping likelihood. For example, you could calculate the time difference between order date and shipping date, or extract features related to the shipping destination, such as distance from the warehouse or average shipping time to that location.

Model Selection: Choose an appropriate machine learning algorithm for the prediction task. Some common choices for binary classification tasks like this include logistic regression, support vector machines, decision trees, random forests, or gradient boosting algorithms.

Model Training: Split your preprocessed data into training and testing sets. Train the selected machine learning model on the training set using the labeled data (orders that were shipped on time and those that were not).

Model Evaluation: Evaluate the performance of your model on the testing set using metrics such as accuracy, precision, recall, or F1 score. These metrics will help you assess how well the model is predicting the likelihood of orders being shipped on time.

Model Deployment: Once you're satisfied with the model's performance, deploy it to make predictions on new orders in real-time or on a periodic basis.

Example: Let's say you work for an online retail company, and you want to predict the likelihood of an order being shipped on time. You gather historical data on orders placed over the past year, including order date, shipping date, order location, shipping location, and product type.

After preprocessing the data and engineering features like the time difference between order date and shipping date, you decide to use a random forest classifier for the prediction task. You split the data into a training set (70%) and a testing set (30%) and train the model on the training set.

After training, you evaluate the model on the testing set and find that it achieves an accuracy of 87%, which is promising. Now, you can deploy this model to predict the likelihood of shipping orders on time for new orders as they come in, helping your company optimize logistics and improve customer satisfaction.

Keep in mind that the success of the model depends on the quality of the data and the features used, so continuous monitoring and refinement of the model may be necessary to maintain accurate predictions over time.

I learned to do this with the help of https://www.eduonix.com/live-data-science-certification-program
> 0 votes

---
Tags: machine-learning
---


# Question
Title: Path planning on 2D grid graph to maximize the neighboring grid points of a path: Can we do better than brute DFS?
On a finite 4-connected grid graph, given the source point and destination, it is allowed to consecutively move in one of the four orientions (up, down, left or right) to form a path. We get 1 bonus for each grid point which is NOT on the path but meanwhile has at least one neighbor on the path (bonus counting stops when reaching destination, see Fig. a). One restriction for path is: each grid point on path can have and only have 2 neighboring grid points on path (source and destination point can only have 1 neighbor on path accordingly, see Fig. b). I'm attempting to maximize the total bonus for a simple path connecting the source to destination.

**My question is:**

**Can this problem be converted into some category of classic problem in graph theory (such as shortest path or maximum flow) or are there any other smarter DFS approach / Dynamic Programming to solve it?**

(I'm not sure if polynomial time would be possible, but a better exponential time than current brute DFS would also be appropriate for this problem, because the N will be at most 400~500. )

**What I have tried:**

**1. Brute DFS**

Pseudo-codes are listed below which could inefficiently but thoroughly solve cases with N around 100 within several seconds on a common PC, the solution to a 5x3 grid are given in Fig. c. I curve-fitted the time complexity with 4x4 to 9x9 grids as about $O(1.24^N)$.

```
bool DFS (Vertex V) {
  if (V is destinationVertex) {
    Compare the current total bonus with the maximum total bonus;
    if (this path is better) {
      Record current paths and update total bonus;
    }
    return false; // Returning false means an end of this DFS branch.
  }
  Verify which neighbors W of V could make a valid visit and put them into Queue.
  for (W in Queue) { DFS (W); }
  if (all of above DFS (W) return false OR Queue is empty) {
    Clear this level's influences on decision tree. //Subtract current bonuses and paths
    return false;
  } else {
    return true;
  }
}

```
2. I tried hard and found it might not be easy to be converted to a DAG or even a simple graph. If the grid points are selected as vertexs, the weight of edges are essentially undetermined, which is related to previous paths having been covered. And this is different from Shortest paths when edge weight depends on previous edge, where the edge weight is only related to LAST previous edge rather than possible ALL previous edge in my problem. So using \<u, v\> pair as vertexes might also not work. But maybe I'm wrong, so I really desire to find a better model for solving it.

I've spent several days trying to solve it and search similar problems and no progress are made. Any help would be appreciated! Thanks!

# Answer
> 1 votes
I think I have found a working idea, however this is only a draft.

Take your n×m grid and split it into 3×3 squares starting from the upper-left corner until there are borders of size either 4 or 2 on two sides. If the border is of size 4 add 2 boxes 2×3, if it is of size 2 add only 1 2×3 box.

Some examples would be:

For 6×6 it is straight forward:

## 3×3 | 3x3

## 3x3 | 3x3

For 5×5 it would be:

## 3×3 | 3×2

## 2×3 | 2x2

For 10×9 it would be:

## 3x3 | 3x3 | 3x3

## 3x3 | 3×3 | 3x3

## 2×3 | 2x3 | 2x3

## 2x3 | 2x3 | 2x3

Connect 3x3 boxes through the middle of the edge. This way you only cover a bonus point twice at 90 degree turns. Only count points if they come from the same box as the path itself.

Now consider the new grid of boxes as a graph where the weights of the edges (between adjacent boxes) are the amount of bonus points added to both boxes by the best path connection. Do dijkstra or bellman ford to find the longest path from source to destination. This is the solution.

Might be a lot of case work, but if it works it would work.

---
Tags: algorithms, graphs, dynamic-programming, weighted-graphs
---


# Question
Title: Question about data to train an machine learning IA
I'm trying to create a machine learning program to predict the winner of UFC fights. I want to train my AI with data from previous matches, but I have encountered a problem.

I wonder if the algorithm will really work because, on the website where I can retrieve the data of the fighters and their fights, the information is up to date since their last fight.

Let's imagine I am the fighter Tommy. I have a record of 10-2 with an average of 6 strikes per minute thrown and 1 strike per minute absorbed.

If the AI trains on my third fight, which has already taken place, so we know the result (I was 2-0). With the data it has, the AI will understand that I was 2-0, but with the latest data from my last fight (6 strikes per minute thrown and 1 strike per minute absorbed). But that wasn't the case because it was much earlier, so I didn't have 6 strikes per minute thrown and 1 strike per minute absorbed yet.

In fact, by retrieving the fighters' data on the UFC website, I have the latest information for each fighter. Consequently, the AI will train on old fights without having the fighters' historical data.

Essentially, it will be evaluating fights from 2010 with data from both fighters dating back to 2023.

Is this a significant problem for its training? Is there a solution to this issue?

# Answer
> 0 votes
The question is confusing, but I think what you are getting at is that you need to enforce temporal consistency when you evaluate your method.

In particular, a machine learning model takes as input (a feature vector) and produces output (a prediction). In your case, the feature vector contains information about past fights, and the prediction is the prediction of the result of the next fight. Now what information should be in the feature vector? To answer that, I suggest that you think about how your model will be deployed. What information will be available, at the time you want to use the model to make a prediction?

For instance, suppose that you plan to use the model to predict the outcome of a fight, before the start of that fight. Well, then, the only information available will be data about prior fights. So the feature vector can only include data about prior fights -- e.g., the results of prior fights, statistics about strikes per minute in prior fights, etc. Obviously, the feature vector cannot include data about this fight, because you can't see into the future.

That then dictates what training data you need, to train a model. You need training data that is consistent with those constraints. In particular, the feature vector should be statistics on all fights before the one whose outcome you are trying to predict. It sounds like you are saying that you don't have a way to gather that kind of data for past fights. If you don't, you don't, and then you might not be able to apply machine learning (or any other statistical model) in a principled way. This is a common situation. Our ability to use machine learning (or statistical modeling) is constrained by the data that is available to us.

See also "temporal cross-validation", https://stats.stackexchange.com/questions/477730/what-is-temporal-leakage, https://towardsdatascience.com/time-based-cross-validation-d259b13d42b8.

---
Tags: machine-learning, artificial-intelligence
---


title: Understanding Language L

text:
# Question
Title: Understanding Language L
Given:

L := {w elementof {0,1}\* : w=(010 | 10)(10 | t'), with t' elementof L}

What words can we build with these rules?

01010, 1010, what else? Does the t' allow 010010?

# Answer
> 0 votes
I can understand your confusion. Strictly speaking, this is not a valid definition of $L$, because it is circular: it defines $L$ in terms of itself. So I can understand why you are confused.

I think one more precise way to define the language $L$ would be to say that $L$ is some language that satisfies the equation

$$L = \\{w \in \\{0,1\\}^\* \mid w=01010 \text{ or } w=1010 \text{ or } \exists t' \in L . w=010t' \text{ or } w=10t'\\}$$

On first glance, it might appear that there could be multiple languages that satisfy this equation, so this is not necessarily yet a unique definition of a language. One standard way to address this is to first prove that there exists at least one language that satisfies this equation, and then define $L$ as the smallest language that satisfies the equation. That would be a satisfactory and unambiguous definition of $L$.

Alternatively, another way to view this is that $L$ is the smallest language that satisfies the following two rules:

1. $\\{01010, 1010\\} \subseteq L$
2. $(010|10) L \subseteq L$

Now you should be able to answer your questions. Can you prove using the latter two rules that $010010 \in L$? Or, can you write down a language $L$ that satisfies the equation? Once you have done so, does that language contain $010010$?

# Answer
> 1 votes
The definition is recursive.

For the base cases (ignoring $t'$), we consider $(010|10)10$, or $010\\,10|10\\,10$.

Then, letting $t'$ take these values, we add the four combinations $010\\,010\\,10|010\\,10\\,10|10\\,010\\,10|10\\,10\\,10$.

Next, eight combinations, $010\\,010\\,010\\,10|010\\,010\\,10\\,10|010\\,10\\,010\\,10|010\\,10\\,10\\,10|10\\,010\\,010\\,10|10\\,010\\,10\\,10|10\\,10\\,010\\,10|10\\,10\\,10\\,10$

Further combinations are longer. You cannot form $010010$. As you can observe, the strings are $(010|10)^+10$.

---
Tags: formal-languages
---


# Question
Title: Justify that total running time for the addition algorithm is of the form $c_0+c_1n$
In my reference Page 22, Algorithms by Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani, it says that

> given $x$ and $y$ are two numbers of $n$ bits long, then the sum of $x$ and $y$ is $n+1$ bits long, and assuming that each individual bit of this sum gets computed in a fixed amount of time, then the total running time for the addition algorithm is of the form $c\_0+c\_1n$, where $c\_0$ and $c\_1$ are some constants.

How the running time for obtaining $x+y$ is $c\_0+c\_1n$ ?

The example given in the reference is $x=53,y=35,x+y=88$, ie.,

in this example what would be the values of $c\_0,c\_1$?

---

**My Understanding**

We can prove that the sum of three single digit numbers is at most $2$ digits. This shows that $x+y$ is $n+1$ digits, as each steps of the addition invloves at most adding three single digits numbers including the carry.

Additionally, looking at the addition algorithm, each single digit addition involves $2$ additions at most, and there are $n$ such operations, therefore total of $2n$.

# Answer
Strictly speaking, the claim is wrong, as nothing is said about the time for addition of two bits and a possible carry. This time might depend on the particular bit values and even not be the same for every bit.

Anyway, if we admit that the time does not depend on the numbers at all, it can only be a linear function of the number of bits if the computation is performed sequentially.

The total time is the time to add the two low order bits, then the time to compute the carry and add it to the sum of the next two bits, repeatedly, then the time for the last carry. Hence taking into account the limit cases,

$$t\_1+(n-1)t\_2+t\_3$$
> 1 votes

---
Tags: algorithms, time-complexity
---


title: Nonpreemptive kernels in OS

text:
# Question
Title: Nonpreemptive kernels in OS
According to the book " Operating Systems Concepts " , 9th edition, page 207, we have the following statement :

> Obviously, a nonpreemptive kernel is essentially free from race conditions on kernel data structures, as only one process is active in the kernel at a time.

My question is, According to the statement, If we have a non-preemptive kernel this means that we will always have one process active in the kernel, this is because the kernel is nonpreemptive ,and hence, the currently running kernel process will leave the CPU by its decision ( like for example after being blocked or terminated), but what if we have multiprocessor system, say with 2 processors, this means that we could have 2 kernel processors accessing the kernel although the kernel is a nonpreemptive one?

# Answer
> 2 votes
By definition, a non-preemptive kernel runs one process at a time, and that process runs until it willingly yields control back to the kernel. Running a non-preemptive kernel on a multi-processor system implies that only one processor runs the kernel and processes, the other processor may be used for other purposes that do not involve the kernel. If one wanted both processors to use the kernel, then a preemptive multi-processor kernel must be used.

---
Tags: operating-systems
---


# Question
Title: What could $P = NP$ imply about arbitrary Turing machines?
My question:

* What $P \not= NP$ or $P = NP$ could imply about arbitrary Turing machines and arbitrary computations? I assume that a partial and incomplete, but objective answer to this question exists (e.g. based on the literature, most popular research directions). Take a single arbitrary program/computation. What could we learn about it if $P \not= NP$ or $P = NP$? I'll give more context to my question below.

## Undecidability and P vs. NP

**1)** This answer explains:

> "Global" complexity results such as "The halting problem is undecidable" and "Truth is undefinable", and even "The reals are uncountable" have **local analogues** whose proofs can be automatically extracted from the global argument but which also permit a simplicity result.

**2)** Many bounded versions of undecidable problems are **NP** problems. For example, bounded Post correspondence problem.

**3)** If $P = NP$, it can make undecidability largely irrelevant in practice. Because it can give us an effective algorithm for checking all possible proofs of reasonable length. Here's a quote by **Gödel**: (a source, wikipedia)

> If there really were a machine with $φ(n) ∼ k⋅n$ (or even $∼ k⋅n2$), this would have consequences of the greatest importance. Namely, it would obviously mean that in spite of the undecidability of the Entscheidungsproblem, the mental work of a mathematician concerning Yes-or-No questions could be completely replaced by a machine. After all, one would simply have to choose the natural number n so large that when the machine does not deliver a result, it makes no sense to think more about the problem.

**4)** From time to time people come up with naive proof ideas which try to use undecidability or arbitrary Turing machines to prove $P \not= NP$:

I think **1-4** means that we can talk about **P vs. NP** in the context of undecidability and arbitrary computations. I'm not saying that undecidability *resolves* **P vs. NP**, just that we can talk about one thing in connection to the other. For example, we can say:

* "$P = NP$ could imply that any finite part of an infinite computation has..." (has *what*? some invariant? some distribution? some other pattern?)
* "$P = NP$ could imply that all/most programs which don't halt fast enough can be recognized by something like..." (like *what*?)

But how can we finish those sentences, based on the most popular research directions? This is my question. It can be a little broad, but I think it's justified, because more specific versions of this question can keep popping up indefinitely. It would be useful to have a general answer.

## Subjective thoughts

I hope my question is objective and justified enough. However, here I want to describe some subjective thoughts which fuel my interest. You **don't** have to understand this part of the post to answer my question.

When you analyze a complex phenomenon in physics, you can break it down until you eventually get to "the most specific reason" which makes it true/false. For example, if you study perpetual motion engines, you can get to very specific reasons of why they are impossible. Math can be extremely different from physics. However, I think that approximately the same idea is true in math (that's just my personal philosophical position). If something is true/false, then there exists "the most specific reason" which makes it true/false.

**P vs. NP** problem can be viewed as talking about arbitrary Turing machines. And this problem seems very strange to me, because compared to other mathematical problems, I can't even imagine breaking it down into any possible specific facts *\[about arbitrary TMs\]*. So, I want to know what are the potential "most specific facts" *\[about arbitrary TMs\]* implied by $P = NP$. I really have absolutely no idea, no mental model of what $P = NP$ *could* tell us about arbitrary computations. Because arbitrary computations are supposed to be, well, "arbitrary". What exploitable patterns *could* exist in those computations? I may be missing some trivial possibilities.

# Answer
> 2 votes
There is good evidence that what you are asking about does not occur.

Specifically, there are computable $A,B$ such that $\mathsf{P}^A=\mathsf{NP}^A$ and $\mathsf{P}^B\not=\mathsf{NP}^B$ (this is the Baker-Gill-Solovay theorem, although there's a typo in Theorem 4.1 of the linked document, namely "$\subseteq$" should be "$=$"). The standard (and entirely correct) takeaway from this result is that no "relativizing" argument can resolve the $\mathsf{P}/\mathsf{NP}$ question, and a particular case of this is that it arguably prevents the sort of phenomenon you're asking about.

Every significant undecidability result I'm aware of highly implementation-independent: for example, the $m$-degree of the halting problem doesn't change if in its definition we replace "Turing machine" by "Turing machine with oracle $X$" for any computable $X$, or make similar tweaks. BGS-type results tell us that if we hope to see complexity-theoretic facts "reflected" somehow in computability-theoretic facts, their computability-theoretic reflections will often need to be "implementation-*fragile*" in a way that computability-theoretic results generally aren't.

---
Tags: turing-machines, undecidability, np, p-vs-np
---


# Question
Title: Strong NP-completeness of numerical perfect matching
This is a follow-up to post Perfect matching problem, where nir proved weak NP-completeness.

Suppose you are given two sets of integers $L$ and $M$ both having $N$ elements. We want to match each number in $L$ with a number in $M$. Such perfect matching has some cost given by $\sum\_{i=1}^{N} l\_i\*m\_i$.

The problem is to decide the existence of a perfect matching with some given cost $C$.

Is this problem strongly NP-complete?

# Answer
I found an NP-complete problem, Applying a permutation on a sequence with multiplication, that reduces to my problem. The reduction produces an input to my problem where sequence $a\_i$ is the set $L$, $M=\\{1,2,3, ..., n\\}$, and C=x.

This proves that the problem of numerical perfect matching is NP-complete for unbounded input integers.

\**Update \** For polynomialy bounded input integers, numerical perfect matching problem can not be NP-complete unless RP=NP.

There is an easy reduction from my problem to exact perfect matching problem which in RP (for polynomialy bounded edge weights) and there is no known deterministic polynomial time algorithm for it.

Exact perfect matching problem

Input: given edge weighted graph and integer w

Question: Is there a perfect matching of weight exactly w

References:

1. Papadimitriou, Yannakakis, The complexity of restricted spanning tree problems. Journal of the ACM 29(2), 285–309 (1982)
2. Mulmuley, Vazirani & Vazirani, Matching is as easy as matrix inversion. Combinatorica, volume 7, 105–113 (1987)
> 0 votes

# Answer
**This is not correct** It is left for educational value.

Another strong NP-completeness proof is a simple reduction from distinct 3-partition problem.

**Distinct 3-partition**

> **Input:** A set $X = \\{a\_1,a\_2,\ldots,a\_{3n}\\}$ of positive distinct integers, and a positive integer $B$ where $\Sigma\_{i=1}^{3n} a\_i = nB$, and $B/4 \< a\_i \< B/2$, where $1 \le i \le 3n$.
>
> **Question:** Is there a partition of $X$ into $n$ triples such that the elements in each triple sum to $B$?

The reduction: $L$ is the set $X$, $M=\\{1, 1, 1, 2, 2, 2, ..., i, i, i\\}$ for $1 \le i \le n$, and $C=\Sigma\_{i=1}^{n} i\*B= B\*n(n+1)/2$

Then the 3-parition instance has a solution if and only if numerical perfect matching has a solution.
> 0 votes

---
Tags: complexity-theory, np-complete
---


title: What is an uninhabited type?

text:
# Question
Title: What is an uninhabited type?
https://en.wikipedia.org/wiki/Type\_inhabitation

The wiki article above says,

> To be sound, such a system must have uninhabited types.

What is the definition an uninhabitated type? Do all programming languages have uninhabited types? What would be an example in Haskell? Or C? Or Java? Or Python?

# Answer
> 3 votes
"Inhabited" is the properly constructive notion of "non-empty". The idea is that to demonstrate that a type is inhabited requires exhibiting a particular construction with that type, while 'non-empty' means merely demonstrating that it is impossible to demonstrate that there are no such constructions.

"Uninhabited" is the negation of this, and so is equivalent to being empty, even constructively.

Haskell does not have an uninhabited type. For instance `undefined` is a valid term of every type. C, Java and any language with general recursion is not going to qualify either, although C and Java have many other problems even being considered analogues of formal logic. Python doesn't even have types in the type theoretic sense (or it has a single type that classifies everything trivially).

The reason why `void` does not really qualify is that it is not a 'type with no values', but a type where you disallowed from naming/manipulating values, because those values would be trivial. It is analogous to the unit type, with one featureless value.

# Answer
> 3 votes
A type $A$ is inhabited if there exists a term $t$ of type $A$.

In typed programming languages with recursion all types are inhabited. Given any type `A`, consider the term `f()` where `f : unit → A` just calls itself:

```
function A f() { return f(); }

```

(Sure, `f()` cycles, but it has type `A`)

Side comment: the type `void` in C/C++ is inhabited, we just never get to observe its values. Indeed, since it is possible to implement a terminating function `g : int → void`, it cannot be the case that `void` is empty.

So, if we want to think of types as logical statements and their elements as proofs, then there ought to be a type that corresponds to `False`, and this type better be empty (because we cannot prove `False`).

# Answer
> 2 votes
An uninhabited type is a type which **cannot have a representation at runtime** no matter what you do, and enforces this is **in a structural manner**.

I'm going to use Rust as an example, because it does have uninhabited types. Rust has enums, for example:

```
enum Color {
    Red,
    Yellow,
    Rgb(u8, u8, u8),
}

```

And you can specify a color, e.g. `Color::Red` or `Color::Rgb(255, 255, 255)`.

But what if you declare an empty enum:

```
enum Never {}

```

How would you construct a value of this enum? What goes after `Never::`?

The answer is "it cannot be done". There is no possible representation of `Never` in the language. This makes the type uninhabited.

---

What does "in a structural manner" mean? Another way to put it is "even disregarding encapsulation boundaries". A lot of code is written to uphold certain invariants outside of an encapsulation boundary.

For example, consider a file where the only contents are:

```
pub struct MyType(());

```

This type has no attached constructors, and the module doesn't have any functions that return `MyType`. In other words, `MyType` can be named as a type but cannot be constructed.

However, `MyType` can be *represented* at runtime, just not *created* at runtime. In other words, the lack of constructability of `MyType` is enforced via *encapsulation boundaries* rather than it being a property of the structure of `MyType` itself. This means that `MyType` **is not** uninhabited. But it might be the best you can do in many languages.

---

This is related to why enums are called "sum types" and structs are called "product types" -- the identity element of the sum operation is zero, and the identity element of the product operation is one.

---
Tags: type-theory
---


# Question
Title: What reason could a system have to limit the length of a password to 8 chars?
From time to time I see systems that don't allow passwords longer than 8 chars: isn't that a security risk? What am I missing, here, that might have lead to such decision?

# Answer
> 1 votes
Yes, absolutely, it is poor design from a security perspective. You're not missing anything. It could result from historical inertia (a lousy excuse) or from ignorance.

See What technical reasons are there to have low maximum password lengths? and Do passwords need a max length?.

# Answer
> 1 votes
The reason is saving space. In the old days every byte was precious, and security didn't matter because everyone was a nice person.

---
Tags: authentication
---