Security Bijective Functions

  • + 0 comments

    Provided a crude 'C' solution for those of you interested. Used a binary tree structure for 'mapping'. Tried to avoid using Python (I miss one-liners).

    #include <stdio.h>
    #include <string.h>
    #include <math.h>
    #include <stdlib.h>
    #include <stdbool.h>
    
    // A function f with domain A is called a one-to-one function if 
    // every f(x)-value in the range B comes from only one x-value in A. 
    // This implies every 'f(x)-value' is unique within the range B.
    
    // A function f from a set X to a set Y is onto if every element y
    // in Y has a corresponding element x in X such that f(x) = y.
    // Implies that the number of integers == number 'n'.
    
    /** 
     * Using the following binary tree instead of a map / dict.
     * This structure fails on the condition when f(x) = 0.
     * Since the root of the tree is initialized with 0.
     *
     * Sue me for not using 'free()'. 
     *
     * Consider the first definition (one-to-one): 
     *   + Range 'B' is given as the N numbers, second line of input.
     * Consider the second definition (onto):
     *   + The set 'Y', or range 'B', or 'f(x)-values', should equal N.
    **/ 
    typedef struct TREE_NODE {
        struct TREE_NODE *left ;
        struct TREE_NODE *right;
        int val;
    } TREE_NODE;
    
    void insert_node(TREE_NODE *tree_root, int value) {
        TREE_NODE *current;
        TREE_NODE *parent;
        TREE_NODE *insert = (TREE_NODE *) malloc(sizeof(TREE_NODE));
        
        insert->val   = value;
        insert->left  = NULL;
        insert->right = NULL;
        
        current = tree_root;
        parent  = NULL;
        
        while (1) {
            parent = current;
            
            if (value < parent->val) {
                current = current->left;
                if (current == NULL) {
                    parent->left = insert;
                    return;
                }
            }
            
            else if (value > parent->val) {
                current = current->right;
                if (current == NULL) {
                    parent->right = insert;
                    return;
                }
            }
            
            // Non-unique element within the f(x)-values.
            // Breaks the above implication for one-to-one.
            else {
                printf("NO\n");
                exit(0);
            }
        }
    }
    
    int main() {
        int n, elems = 0;
        scanf("%d\n", &n);
        int *y_values = malloc(sizeof(int) * n);
        
        TREE_NODE *tree_root = (TREE_NODE *) malloc(sizeof(TREE_NODE));
        tree_root->left  = NULL;
        tree_root->right = NULL;
        tree_root->val   = 0;
        
        for (int i = 0; i < n; i++) {
            y_values[i] = 0;
            
            // scanf() returns 0, 1, N, or EOF. 
            // N is the number of formatted inputs read.
            // 1 => successfully read '1' number into y_values[i].
            if (scanf("%d ", &y_values[i]) == 1) {
                elems++;
                insert_node(tree_root, y_values[i]);
            }
        }
        
        // Every f(x)-value has an associated 'x' value.
        // The function f(x) is onto. 
        if (elems == n) 
            printf("YES\n");
        else 
            printf("NO\n");
        
        return 0;
    }