LebGeeks

Joe

Member

[Exercise] Iterative traversal of nested mappings

We define a nested mapping as a data structure where each element is either:

• a value. For the sake of simplicity, we'll say a string.

• a nested mapping.

For instance this is a valid example:

data = {
    a: '1',
    b: '2',
    c: { 
        d: '3',
        e: { f: '4' },
        g: { h: '5' },
        i: '6'
    },
    j: '7'   
};

The goal of this exercise is to write a function that takes a nested mapping, replacing every value (string) with the word "replaced". Note that you cannot make any assumption about the depth of the nesting, the following being another example of a valid nested mapping:

deeper_mapping = {
    a: {
        b: {
            c: {
                d: {
                    e: {
                        f: '1'
}}}}}}

Challenge

Solving this problem with a recursive function is fairly easy. Try to do it without using recursion.

Ra8

Member

Re: [Exercise] Iterative traversal of nested mappings

It can be solved using recursion very easily, or if you don't want us to use recursion, we can implement recursion using a stack...
What I did is maybe "cheating" but it does the job in Javascript:

data = JSON.stringify(data);
data = data.replace(/:[\s\t\n\r]*\"([^\"\\]|\\\"|\\)*\"/g, ":\"replaced\"");
data = JSON.parse(data);

xterm

Moderator

Re: [Exercise] Iterative traversal of nested mappings

See in action

var iterative_escape = function(data, action)
{
    var result = {};
    var node_stack = [data];
    var parent_stack = [result];
    
    while(node_stack.length){
        var node = node_stack.pop();
        var parent = parent_stack.pop();
        
        for(var k in node){
            if(is_string(node[k])) 
                parent[k] = action(node[k]);
            else { 
                parent[k] = {};
                node_stack.push(node[k]);                
                parent_stack.push(parent[k]);
            }
        }
    }
    
    return result;
};

var esc = function(what) { return 'replaced'; }
console.log(iterative_escape(data, esc));

raja

Member

Re: [Exercise] Iterative traversal of nested mappings

Nice to see xterm switch from Java  (I've been away a while)

Python solution, doesn't use stacks(just a simple queue) and does the replacing inline(doable not in-line but would unnecessarily complicate the code for now):

def inplace_iterative_action(data, action):
    result = {}
    queue = [data]
    while queue:
        node = queue.pop(0)
        for key,value in node.items():
            if type(value) == str:
                node[key] = action(value)
            else:
                queue.append(value)
    return data

Full example to see it in action:

import pprint

data = {
    'a': '1',
    'b': '2',
    'c': { 
        'd': '3',
        'e': { 'f': '4' },
        'g': { 'h': '5' },
        'i': '6'
    },
    'j': '7'   
}

def inplace_iterative_action(data, action):
    result = {}
    queue = [data]
    while queue:
        node = queue.pop(0)
        for key,value in node.items():
            if type(value) == str:
                node[key] = action(value)
            else:
                queue.append(value)
    return data

pprint.pprint(data)
print
inplace_iterative_action(data, lambda a:"replaced")
pprint.pprint(data)

Result:

{'a': '1',
 'b': '2',
 'c': {'d': '3', 'e': {'f': '4'}, 'g': {'h': '5'}, 'i': '6'},
 'j': '7'}

{'a': 'replaced',
 'b': 'replaced',
 'c': {'d': 'replaced',
       'e': {'f': 'replaced'},
       'g': {'h': 'replaced'},
       'i': 'replaced'},
 'j': 'replaced'}

xterm

Moderator

Re: [Exercise] Iterative traversal of nested mappings

Nice to see xterm switch from Java  (I've been away a while)

Low blow Raja! >.< I dare you to find a single block of java code I've written here on LebGeeks ;)

Groovy was my prototyping choice before python.