# LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

## #1 September 17 2013

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.

## #2 September 18 2013

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);``````

## #3 September 20 2013

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));``````

## #4 October 25 2013

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'}``````

## #5 October 25 2013

xterm
Moderator

### Re: [Exercise] Iterative traversal of nested mappings

raja wrote:

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.