[Exercise] Iterative traversal of nested mappings

Joe

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

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

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

Nice to see xterm switch from Java :P (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

raja wroteNice to see xterm switch from Java :P (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.