Convert 1D array sorted by ASCII order to a nested array in Javascript
Assume this below array of objects that sorted by code
property in ascii order:
var codes = [
{ code: '01' },
{ code: '0101' },
{ code: '0102' },
{ code: '010201' },
{ code: '0103' },
{ code: '02' },
{ code: '0201' },
{ code: '0202' },
];
How can I convert this to a nested array like this :
var nestedCodes = [
{
code: '01',
children: [
{ code: '0101' },
{
code: '0102',
children: [
{ code: '010201' }
]
},
{ code: '0103' }
]
},
{
code: '02',
children: [
{ code: '0201' },
{ code: '0202' }
]
}
];
The structure of codes is like concatenating multiple 0N
that N
can be a number between 1 and 9. Note that codes come from server and there would be some additional properties beside code
like title
but it doesn't matter in this problem.
The main idea here is to make an appropriate format for jsTree.
javascript arrays jstree
add a comment |
Assume this below array of objects that sorted by code
property in ascii order:
var codes = [
{ code: '01' },
{ code: '0101' },
{ code: '0102' },
{ code: '010201' },
{ code: '0103' },
{ code: '02' },
{ code: '0201' },
{ code: '0202' },
];
How can I convert this to a nested array like this :
var nestedCodes = [
{
code: '01',
children: [
{ code: '0101' },
{
code: '0102',
children: [
{ code: '010201' }
]
},
{ code: '0103' }
]
},
{
code: '02',
children: [
{ code: '0201' },
{ code: '0202' }
]
}
];
The structure of codes is like concatenating multiple 0N
that N
can be a number between 1 and 9. Note that codes come from server and there would be some additional properties beside code
like title
but it doesn't matter in this problem.
The main idea here is to make an appropriate format for jsTree.
javascript arrays jstree
Sounds like an algorithms class homework/LeetCode question. It'd make a good coding interview question if it isn't one.
– Yangshun Tay
Nov 27 '18 at 6:48
1
@YangshunTay It's not just a homework question! I'm developing a financial web application and these codes are related to accounting.
– AmirhosseinDZ
Nov 27 '18 at 7:16
It's an interesting question. Have come up with an answer! (:
– Yangshun Tay
Nov 27 '18 at 7:28
add a comment |
Assume this below array of objects that sorted by code
property in ascii order:
var codes = [
{ code: '01' },
{ code: '0101' },
{ code: '0102' },
{ code: '010201' },
{ code: '0103' },
{ code: '02' },
{ code: '0201' },
{ code: '0202' },
];
How can I convert this to a nested array like this :
var nestedCodes = [
{
code: '01',
children: [
{ code: '0101' },
{
code: '0102',
children: [
{ code: '010201' }
]
},
{ code: '0103' }
]
},
{
code: '02',
children: [
{ code: '0201' },
{ code: '0202' }
]
}
];
The structure of codes is like concatenating multiple 0N
that N
can be a number between 1 and 9. Note that codes come from server and there would be some additional properties beside code
like title
but it doesn't matter in this problem.
The main idea here is to make an appropriate format for jsTree.
javascript arrays jstree
Assume this below array of objects that sorted by code
property in ascii order:
var codes = [
{ code: '01' },
{ code: '0101' },
{ code: '0102' },
{ code: '010201' },
{ code: '0103' },
{ code: '02' },
{ code: '0201' },
{ code: '0202' },
];
How can I convert this to a nested array like this :
var nestedCodes = [
{
code: '01',
children: [
{ code: '0101' },
{
code: '0102',
children: [
{ code: '010201' }
]
},
{ code: '0103' }
]
},
{
code: '02',
children: [
{ code: '0201' },
{ code: '0202' }
]
}
];
The structure of codes is like concatenating multiple 0N
that N
can be a number between 1 and 9. Note that codes come from server and there would be some additional properties beside code
like title
but it doesn't matter in this problem.
The main idea here is to make an appropriate format for jsTree.
javascript arrays jstree
javascript arrays jstree
edited Nov 27 '18 at 7:32
Yangshun Tay
10.3k54075
10.3k54075
asked Nov 27 '18 at 5:54
AmirhosseinDZAmirhosseinDZ
30519
30519
Sounds like an algorithms class homework/LeetCode question. It'd make a good coding interview question if it isn't one.
– Yangshun Tay
Nov 27 '18 at 6:48
1
@YangshunTay It's not just a homework question! I'm developing a financial web application and these codes are related to accounting.
– AmirhosseinDZ
Nov 27 '18 at 7:16
It's an interesting question. Have come up with an answer! (:
– Yangshun Tay
Nov 27 '18 at 7:28
add a comment |
Sounds like an algorithms class homework/LeetCode question. It'd make a good coding interview question if it isn't one.
– Yangshun Tay
Nov 27 '18 at 6:48
1
@YangshunTay It's not just a homework question! I'm developing a financial web application and these codes are related to accounting.
– AmirhosseinDZ
Nov 27 '18 at 7:16
It's an interesting question. Have come up with an answer! (:
– Yangshun Tay
Nov 27 '18 at 7:28
Sounds like an algorithms class homework/LeetCode question. It'd make a good coding interview question if it isn't one.
– Yangshun Tay
Nov 27 '18 at 6:48
Sounds like an algorithms class homework/LeetCode question. It'd make a good coding interview question if it isn't one.
– Yangshun Tay
Nov 27 '18 at 6:48
1
1
@YangshunTay It's not just a homework question! I'm developing a financial web application and these codes are related to accounting.
– AmirhosseinDZ
Nov 27 '18 at 7:16
@YangshunTay It's not just a homework question! I'm developing a financial web application and these codes are related to accounting.
– AmirhosseinDZ
Nov 27 '18 at 7:16
It's an interesting question. Have come up with an answer! (:
– Yangshun Tay
Nov 27 '18 at 7:28
It's an interesting question. Have come up with an answer! (:
– Yangshun Tay
Nov 27 '18 at 7:28
add a comment |
4 Answers
4
active
oldest
votes
You can do this with a recursive solution. The idea is to maintain the path
(obtained as an array via String.prototype.match
with a regex) and the parent
under which you want to insert the code
for each recursive call.
The parent
keeps track of the node you want to pick in the "current" recursive call, and path
helps in building the parent
as you keep going deeper:
function insert(d, path, parent, arr) {
if (path.length === 0) {
arr.push(Object.assign({}, d));
return;
}
var target = arr.find(e => e.code === parent);
target.children = target.children || ;
insert(d, path.slice(1), parent + path[0], target.children);
}
var codes = [
{ code: '01' },
{ code: '0101' },
{ code: '0102' },
{ code: '010201' },
{ code: '0103' },
{ code: '02' },
{ code: '0201' },
{ code: '0202' },
];
var res = codes.reduce((a, c) => {
var p = c.code.match(/(0[1-9])/g);
insert(c, p.slice(1), p[0], a);
return a;
}, );
console.log(res);
The assumption, of course, is that when a code
is being inserted, its parent has already been inserted before.
add a comment |
I struggled quite a bit to write the recursive function that will build the required structure. Found the answer here
But to do that, you must first add parent
property to each of your codes
array.
I did that on the assumption that each code
has a parent that is equivalent to the code itself except for the last two bytes.
var codes = [{code: '01' },
{code: '0101' },
{code: '0102' },
{code: '010201'},
{code: '0103' },
{code: '02' },
{code: '0201' },
{code: '0202' },
];
// add parents to each code
codes.forEach(function(c) {
if (c.code.length > 2) {
c.parent = c.code.substr(0, c.code.length - 2);
} else {
c.parent = 'root';
}
});
function find_children(arr, parent) {
var out = ;
for (var i in arr) {
if (arr[i].parent == parent) {
var children = find_children(arr, arr[i].code);
if (children.length) {
arr[i].children = children;
}
out.push(arr[i])
}
}
return out;
}
var nested = find_children(codes,'root');
console.log(nested);
add a comment |
The code is a little long but pretty easy to understand in my opinion. It's extremely robust - does not require the array to be sorted and doesn't require 01
to exist to process 0102
(in case it's needed). The code can be much shorter without handling these cases, but I thought you might be need this.
Firstly, create a object-based tree data structure out of the data. This tree has keys and values, and is very efficient to build because accessing by index is O(1). Next, convert the object-based tree into the final array-based tree data structure by traversing the object-based tree and then converting each layer into arrays.
I also make heavy use of recursion since recursion is well suited for creating and traversing trees.
Compared to the other answers, my algorithm has better time complexity because I create a dictionary/object which has O(1) access when creating the tree. The other algorithms do a search within each layer, which is inefficient. My algorithm runs in O(N) whereas the other answers here are shorter but run in O(N^2).
Just copy the format
function into your code and it should be good to use.
const codes = [
{ code: '01' },
{ code: '0101' },
{ code: '0102' },
{ code: '010201' },
{ code: '0103' },
{ code: '02' },
{ code: '0201' },
{ code: '0202' },
];
function format(codes) {
// Splits the string into an array of 2-character strings.
const SPLIT_REGEX = /.{2}(?=(.{2})+(?!.))|.{2}$/g;
const codeFragments = codes.map(obj => obj.code.match(SPLIT_REGEX));
// 1. Represent the data as a tree which is more efficient to build.
const tree = {};
function createTree(tree, fragments) {
let node = tree;
fragments.forEach(fragment => {
if (!node[fragment]) {
node[fragment] = {};
}
node = node[fragment];
});
}
codeFragments.forEach(fragments => createTree(tree, fragments));
/* tree will have the structure:
{
"01": {
"01": {},
"02": {
"01": {}
},
"03": {}
},
"02": {
"01": {},
"02": {}
}
}
*/
// 2. Convert the tree structure into the desired format.
function generateCodesFromTree(tree, previous) {
const nestedCodes = ;
Object.keys(tree).forEach(treeNode => {
const code = previous + treeNode;
const children = generateCodesFromTree(tree[treeNode], code);
const nestedCode = { code };
if (children.length > 0) {
nestedCode.children = children;
}
nestedCodes.push(nestedCode);
});
return nestedCodes;
}
return generateCodesFromTree(tree, '');
}
console.log(format(codes));
I tested all the answers(except joven28's answer because of its imprecise result) and slider's answer was the fastest : jsperf.com/conv-1d-arr-sorted-by-ascii-order-to-nested-arr
– AmirhosseinDZ
Dec 1 '18 at 10:08
@AmirhosseinDZ What assumptions can we make about your code beside it being sorted? Can we assume with if there's010201
, there will be a0102
present? If we can assume that, a lot more optimization can be done. Your benchmark is not accurate. You wouldn't see the full picture by testing on your small set of codes. Here's a better benchmark with 1000 rows: jsperf.com/conv-1d-arr-sorted-by-ascii-order-to-nested-arr/5. If you look at the results of this benchmark, slider's answer errored out, Ahmad's answer is fastest but the answer is wrong because of above assumption.
– Yangshun Tay
Dec 1 '18 at 20:37
add a comment |
It can only be achieved by using a recursive approach. Try this one.
let codes = [
{ code: '01' },
{ code: '0101' },
{ code: '0102' },
{ code: '010201' },
{ code: '0103' },
{ code: '02' },
{ code: '0201' },
{ code: '0202' },
];
roots = codes.filter(c => c.code.length === 2);
roots.forEach(c => assign(c));
console.log(roots);
function assign(code) {
codes.forEach(c => {
if (c !== code) {
if (code.code === c.code.slice(0, code.code.length)) {
code.children = !code.children ? [c] : [...code.children, c];
assign(code.children[code.children.length - 1]);
}
}
});
}
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53493545%2fconvert-1d-array-sorted-by-ascii-order-to-a-nested-array-in-javascript%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
You can do this with a recursive solution. The idea is to maintain the path
(obtained as an array via String.prototype.match
with a regex) and the parent
under which you want to insert the code
for each recursive call.
The parent
keeps track of the node you want to pick in the "current" recursive call, and path
helps in building the parent
as you keep going deeper:
function insert(d, path, parent, arr) {
if (path.length === 0) {
arr.push(Object.assign({}, d));
return;
}
var target = arr.find(e => e.code === parent);
target.children = target.children || ;
insert(d, path.slice(1), parent + path[0], target.children);
}
var codes = [
{ code: '01' },
{ code: '0101' },
{ code: '0102' },
{ code: '010201' },
{ code: '0103' },
{ code: '02' },
{ code: '0201' },
{ code: '0202' },
];
var res = codes.reduce((a, c) => {
var p = c.code.match(/(0[1-9])/g);
insert(c, p.slice(1), p[0], a);
return a;
}, );
console.log(res);
The assumption, of course, is that when a code
is being inserted, its parent has already been inserted before.
add a comment |
You can do this with a recursive solution. The idea is to maintain the path
(obtained as an array via String.prototype.match
with a regex) and the parent
under which you want to insert the code
for each recursive call.
The parent
keeps track of the node you want to pick in the "current" recursive call, and path
helps in building the parent
as you keep going deeper:
function insert(d, path, parent, arr) {
if (path.length === 0) {
arr.push(Object.assign({}, d));
return;
}
var target = arr.find(e => e.code === parent);
target.children = target.children || ;
insert(d, path.slice(1), parent + path[0], target.children);
}
var codes = [
{ code: '01' },
{ code: '0101' },
{ code: '0102' },
{ code: '010201' },
{ code: '0103' },
{ code: '02' },
{ code: '0201' },
{ code: '0202' },
];
var res = codes.reduce((a, c) => {
var p = c.code.match(/(0[1-9])/g);
insert(c, p.slice(1), p[0], a);
return a;
}, );
console.log(res);
The assumption, of course, is that when a code
is being inserted, its parent has already been inserted before.
add a comment |
You can do this with a recursive solution. The idea is to maintain the path
(obtained as an array via String.prototype.match
with a regex) and the parent
under which you want to insert the code
for each recursive call.
The parent
keeps track of the node you want to pick in the "current" recursive call, and path
helps in building the parent
as you keep going deeper:
function insert(d, path, parent, arr) {
if (path.length === 0) {
arr.push(Object.assign({}, d));
return;
}
var target = arr.find(e => e.code === parent);
target.children = target.children || ;
insert(d, path.slice(1), parent + path[0], target.children);
}
var codes = [
{ code: '01' },
{ code: '0101' },
{ code: '0102' },
{ code: '010201' },
{ code: '0103' },
{ code: '02' },
{ code: '0201' },
{ code: '0202' },
];
var res = codes.reduce((a, c) => {
var p = c.code.match(/(0[1-9])/g);
insert(c, p.slice(1), p[0], a);
return a;
}, );
console.log(res);
The assumption, of course, is that when a code
is being inserted, its parent has already been inserted before.
You can do this with a recursive solution. The idea is to maintain the path
(obtained as an array via String.prototype.match
with a regex) and the parent
under which you want to insert the code
for each recursive call.
The parent
keeps track of the node you want to pick in the "current" recursive call, and path
helps in building the parent
as you keep going deeper:
function insert(d, path, parent, arr) {
if (path.length === 0) {
arr.push(Object.assign({}, d));
return;
}
var target = arr.find(e => e.code === parent);
target.children = target.children || ;
insert(d, path.slice(1), parent + path[0], target.children);
}
var codes = [
{ code: '01' },
{ code: '0101' },
{ code: '0102' },
{ code: '010201' },
{ code: '0103' },
{ code: '02' },
{ code: '0201' },
{ code: '0202' },
];
var res = codes.reduce((a, c) => {
var p = c.code.match(/(0[1-9])/g);
insert(c, p.slice(1), p[0], a);
return a;
}, );
console.log(res);
The assumption, of course, is that when a code
is being inserted, its parent has already been inserted before.
function insert(d, path, parent, arr) {
if (path.length === 0) {
arr.push(Object.assign({}, d));
return;
}
var target = arr.find(e => e.code === parent);
target.children = target.children || ;
insert(d, path.slice(1), parent + path[0], target.children);
}
var codes = [
{ code: '01' },
{ code: '0101' },
{ code: '0102' },
{ code: '010201' },
{ code: '0103' },
{ code: '02' },
{ code: '0201' },
{ code: '0202' },
];
var res = codes.reduce((a, c) => {
var p = c.code.match(/(0[1-9])/g);
insert(c, p.slice(1), p[0], a);
return a;
}, );
console.log(res);
function insert(d, path, parent, arr) {
if (path.length === 0) {
arr.push(Object.assign({}, d));
return;
}
var target = arr.find(e => e.code === parent);
target.children = target.children || ;
insert(d, path.slice(1), parent + path[0], target.children);
}
var codes = [
{ code: '01' },
{ code: '0101' },
{ code: '0102' },
{ code: '010201' },
{ code: '0103' },
{ code: '02' },
{ code: '0201' },
{ code: '0202' },
];
var res = codes.reduce((a, c) => {
var p = c.code.match(/(0[1-9])/g);
insert(c, p.slice(1), p[0], a);
return a;
}, );
console.log(res);
edited Nov 27 '18 at 7:03
answered Nov 27 '18 at 6:43
sliderslider
8,42311130
8,42311130
add a comment |
add a comment |
I struggled quite a bit to write the recursive function that will build the required structure. Found the answer here
But to do that, you must first add parent
property to each of your codes
array.
I did that on the assumption that each code
has a parent that is equivalent to the code itself except for the last two bytes.
var codes = [{code: '01' },
{code: '0101' },
{code: '0102' },
{code: '010201'},
{code: '0103' },
{code: '02' },
{code: '0201' },
{code: '0202' },
];
// add parents to each code
codes.forEach(function(c) {
if (c.code.length > 2) {
c.parent = c.code.substr(0, c.code.length - 2);
} else {
c.parent = 'root';
}
});
function find_children(arr, parent) {
var out = ;
for (var i in arr) {
if (arr[i].parent == parent) {
var children = find_children(arr, arr[i].code);
if (children.length) {
arr[i].children = children;
}
out.push(arr[i])
}
}
return out;
}
var nested = find_children(codes,'root');
console.log(nested);
add a comment |
I struggled quite a bit to write the recursive function that will build the required structure. Found the answer here
But to do that, you must first add parent
property to each of your codes
array.
I did that on the assumption that each code
has a parent that is equivalent to the code itself except for the last two bytes.
var codes = [{code: '01' },
{code: '0101' },
{code: '0102' },
{code: '010201'},
{code: '0103' },
{code: '02' },
{code: '0201' },
{code: '0202' },
];
// add parents to each code
codes.forEach(function(c) {
if (c.code.length > 2) {
c.parent = c.code.substr(0, c.code.length - 2);
} else {
c.parent = 'root';
}
});
function find_children(arr, parent) {
var out = ;
for (var i in arr) {
if (arr[i].parent == parent) {
var children = find_children(arr, arr[i].code);
if (children.length) {
arr[i].children = children;
}
out.push(arr[i])
}
}
return out;
}
var nested = find_children(codes,'root');
console.log(nested);
add a comment |
I struggled quite a bit to write the recursive function that will build the required structure. Found the answer here
But to do that, you must first add parent
property to each of your codes
array.
I did that on the assumption that each code
has a parent that is equivalent to the code itself except for the last two bytes.
var codes = [{code: '01' },
{code: '0101' },
{code: '0102' },
{code: '010201'},
{code: '0103' },
{code: '02' },
{code: '0201' },
{code: '0202' },
];
// add parents to each code
codes.forEach(function(c) {
if (c.code.length > 2) {
c.parent = c.code.substr(0, c.code.length - 2);
} else {
c.parent = 'root';
}
});
function find_children(arr, parent) {
var out = ;
for (var i in arr) {
if (arr[i].parent == parent) {
var children = find_children(arr, arr[i].code);
if (children.length) {
arr[i].children = children;
}
out.push(arr[i])
}
}
return out;
}
var nested = find_children(codes,'root');
console.log(nested);
I struggled quite a bit to write the recursive function that will build the required structure. Found the answer here
But to do that, you must first add parent
property to each of your codes
array.
I did that on the assumption that each code
has a parent that is equivalent to the code itself except for the last two bytes.
var codes = [{code: '01' },
{code: '0101' },
{code: '0102' },
{code: '010201'},
{code: '0103' },
{code: '02' },
{code: '0201' },
{code: '0202' },
];
// add parents to each code
codes.forEach(function(c) {
if (c.code.length > 2) {
c.parent = c.code.substr(0, c.code.length - 2);
} else {
c.parent = 'root';
}
});
function find_children(arr, parent) {
var out = ;
for (var i in arr) {
if (arr[i].parent == parent) {
var children = find_children(arr, arr[i].code);
if (children.length) {
arr[i].children = children;
}
out.push(arr[i])
}
}
return out;
}
var nested = find_children(codes,'root');
console.log(nested);
var codes = [{code: '01' },
{code: '0101' },
{code: '0102' },
{code: '010201'},
{code: '0103' },
{code: '02' },
{code: '0201' },
{code: '0202' },
];
// add parents to each code
codes.forEach(function(c) {
if (c.code.length > 2) {
c.parent = c.code.substr(0, c.code.length - 2);
} else {
c.parent = 'root';
}
});
function find_children(arr, parent) {
var out = ;
for (var i in arr) {
if (arr[i].parent == parent) {
var children = find_children(arr, arr[i].code);
if (children.length) {
arr[i].children = children;
}
out.push(arr[i])
}
}
return out;
}
var nested = find_children(codes,'root');
console.log(nested);
var codes = [{code: '01' },
{code: '0101' },
{code: '0102' },
{code: '010201'},
{code: '0103' },
{code: '02' },
{code: '0201' },
{code: '0202' },
];
// add parents to each code
codes.forEach(function(c) {
if (c.code.length > 2) {
c.parent = c.code.substr(0, c.code.length - 2);
} else {
c.parent = 'root';
}
});
function find_children(arr, parent) {
var out = ;
for (var i in arr) {
if (arr[i].parent == parent) {
var children = find_children(arr, arr[i].code);
if (children.length) {
arr[i].children = children;
}
out.push(arr[i])
}
}
return out;
}
var nested = find_children(codes,'root');
console.log(nested);
answered Nov 27 '18 at 7:09
AhmadAhmad
8,27543663
8,27543663
add a comment |
add a comment |
The code is a little long but pretty easy to understand in my opinion. It's extremely robust - does not require the array to be sorted and doesn't require 01
to exist to process 0102
(in case it's needed). The code can be much shorter without handling these cases, but I thought you might be need this.
Firstly, create a object-based tree data structure out of the data. This tree has keys and values, and is very efficient to build because accessing by index is O(1). Next, convert the object-based tree into the final array-based tree data structure by traversing the object-based tree and then converting each layer into arrays.
I also make heavy use of recursion since recursion is well suited for creating and traversing trees.
Compared to the other answers, my algorithm has better time complexity because I create a dictionary/object which has O(1) access when creating the tree. The other algorithms do a search within each layer, which is inefficient. My algorithm runs in O(N) whereas the other answers here are shorter but run in O(N^2).
Just copy the format
function into your code and it should be good to use.
const codes = [
{ code: '01' },
{ code: '0101' },
{ code: '0102' },
{ code: '010201' },
{ code: '0103' },
{ code: '02' },
{ code: '0201' },
{ code: '0202' },
];
function format(codes) {
// Splits the string into an array of 2-character strings.
const SPLIT_REGEX = /.{2}(?=(.{2})+(?!.))|.{2}$/g;
const codeFragments = codes.map(obj => obj.code.match(SPLIT_REGEX));
// 1. Represent the data as a tree which is more efficient to build.
const tree = {};
function createTree(tree, fragments) {
let node = tree;
fragments.forEach(fragment => {
if (!node[fragment]) {
node[fragment] = {};
}
node = node[fragment];
});
}
codeFragments.forEach(fragments => createTree(tree, fragments));
/* tree will have the structure:
{
"01": {
"01": {},
"02": {
"01": {}
},
"03": {}
},
"02": {
"01": {},
"02": {}
}
}
*/
// 2. Convert the tree structure into the desired format.
function generateCodesFromTree(tree, previous) {
const nestedCodes = ;
Object.keys(tree).forEach(treeNode => {
const code = previous + treeNode;
const children = generateCodesFromTree(tree[treeNode], code);
const nestedCode = { code };
if (children.length > 0) {
nestedCode.children = children;
}
nestedCodes.push(nestedCode);
});
return nestedCodes;
}
return generateCodesFromTree(tree, '');
}
console.log(format(codes));
I tested all the answers(except joven28's answer because of its imprecise result) and slider's answer was the fastest : jsperf.com/conv-1d-arr-sorted-by-ascii-order-to-nested-arr
– AmirhosseinDZ
Dec 1 '18 at 10:08
@AmirhosseinDZ What assumptions can we make about your code beside it being sorted? Can we assume with if there's010201
, there will be a0102
present? If we can assume that, a lot more optimization can be done. Your benchmark is not accurate. You wouldn't see the full picture by testing on your small set of codes. Here's a better benchmark with 1000 rows: jsperf.com/conv-1d-arr-sorted-by-ascii-order-to-nested-arr/5. If you look at the results of this benchmark, slider's answer errored out, Ahmad's answer is fastest but the answer is wrong because of above assumption.
– Yangshun Tay
Dec 1 '18 at 20:37
add a comment |
The code is a little long but pretty easy to understand in my opinion. It's extremely robust - does not require the array to be sorted and doesn't require 01
to exist to process 0102
(in case it's needed). The code can be much shorter without handling these cases, but I thought you might be need this.
Firstly, create a object-based tree data structure out of the data. This tree has keys and values, and is very efficient to build because accessing by index is O(1). Next, convert the object-based tree into the final array-based tree data structure by traversing the object-based tree and then converting each layer into arrays.
I also make heavy use of recursion since recursion is well suited for creating and traversing trees.
Compared to the other answers, my algorithm has better time complexity because I create a dictionary/object which has O(1) access when creating the tree. The other algorithms do a search within each layer, which is inefficient. My algorithm runs in O(N) whereas the other answers here are shorter but run in O(N^2).
Just copy the format
function into your code and it should be good to use.
const codes = [
{ code: '01' },
{ code: '0101' },
{ code: '0102' },
{ code: '010201' },
{ code: '0103' },
{ code: '02' },
{ code: '0201' },
{ code: '0202' },
];
function format(codes) {
// Splits the string into an array of 2-character strings.
const SPLIT_REGEX = /.{2}(?=(.{2})+(?!.))|.{2}$/g;
const codeFragments = codes.map(obj => obj.code.match(SPLIT_REGEX));
// 1. Represent the data as a tree which is more efficient to build.
const tree = {};
function createTree(tree, fragments) {
let node = tree;
fragments.forEach(fragment => {
if (!node[fragment]) {
node[fragment] = {};
}
node = node[fragment];
});
}
codeFragments.forEach(fragments => createTree(tree, fragments));
/* tree will have the structure:
{
"01": {
"01": {},
"02": {
"01": {}
},
"03": {}
},
"02": {
"01": {},
"02": {}
}
}
*/
// 2. Convert the tree structure into the desired format.
function generateCodesFromTree(tree, previous) {
const nestedCodes = ;
Object.keys(tree).forEach(treeNode => {
const code = previous + treeNode;
const children = generateCodesFromTree(tree[treeNode], code);
const nestedCode = { code };
if (children.length > 0) {
nestedCode.children = children;
}
nestedCodes.push(nestedCode);
});
return nestedCodes;
}
return generateCodesFromTree(tree, '');
}
console.log(format(codes));
I tested all the answers(except joven28's answer because of its imprecise result) and slider's answer was the fastest : jsperf.com/conv-1d-arr-sorted-by-ascii-order-to-nested-arr
– AmirhosseinDZ
Dec 1 '18 at 10:08
@AmirhosseinDZ What assumptions can we make about your code beside it being sorted? Can we assume with if there's010201
, there will be a0102
present? If we can assume that, a lot more optimization can be done. Your benchmark is not accurate. You wouldn't see the full picture by testing on your small set of codes. Here's a better benchmark with 1000 rows: jsperf.com/conv-1d-arr-sorted-by-ascii-order-to-nested-arr/5. If you look at the results of this benchmark, slider's answer errored out, Ahmad's answer is fastest but the answer is wrong because of above assumption.
– Yangshun Tay
Dec 1 '18 at 20:37
add a comment |
The code is a little long but pretty easy to understand in my opinion. It's extremely robust - does not require the array to be sorted and doesn't require 01
to exist to process 0102
(in case it's needed). The code can be much shorter without handling these cases, but I thought you might be need this.
Firstly, create a object-based tree data structure out of the data. This tree has keys and values, and is very efficient to build because accessing by index is O(1). Next, convert the object-based tree into the final array-based tree data structure by traversing the object-based tree and then converting each layer into arrays.
I also make heavy use of recursion since recursion is well suited for creating and traversing trees.
Compared to the other answers, my algorithm has better time complexity because I create a dictionary/object which has O(1) access when creating the tree. The other algorithms do a search within each layer, which is inefficient. My algorithm runs in O(N) whereas the other answers here are shorter but run in O(N^2).
Just copy the format
function into your code and it should be good to use.
const codes = [
{ code: '01' },
{ code: '0101' },
{ code: '0102' },
{ code: '010201' },
{ code: '0103' },
{ code: '02' },
{ code: '0201' },
{ code: '0202' },
];
function format(codes) {
// Splits the string into an array of 2-character strings.
const SPLIT_REGEX = /.{2}(?=(.{2})+(?!.))|.{2}$/g;
const codeFragments = codes.map(obj => obj.code.match(SPLIT_REGEX));
// 1. Represent the data as a tree which is more efficient to build.
const tree = {};
function createTree(tree, fragments) {
let node = tree;
fragments.forEach(fragment => {
if (!node[fragment]) {
node[fragment] = {};
}
node = node[fragment];
});
}
codeFragments.forEach(fragments => createTree(tree, fragments));
/* tree will have the structure:
{
"01": {
"01": {},
"02": {
"01": {}
},
"03": {}
},
"02": {
"01": {},
"02": {}
}
}
*/
// 2. Convert the tree structure into the desired format.
function generateCodesFromTree(tree, previous) {
const nestedCodes = ;
Object.keys(tree).forEach(treeNode => {
const code = previous + treeNode;
const children = generateCodesFromTree(tree[treeNode], code);
const nestedCode = { code };
if (children.length > 0) {
nestedCode.children = children;
}
nestedCodes.push(nestedCode);
});
return nestedCodes;
}
return generateCodesFromTree(tree, '');
}
console.log(format(codes));
The code is a little long but pretty easy to understand in my opinion. It's extremely robust - does not require the array to be sorted and doesn't require 01
to exist to process 0102
(in case it's needed). The code can be much shorter without handling these cases, but I thought you might be need this.
Firstly, create a object-based tree data structure out of the data. This tree has keys and values, and is very efficient to build because accessing by index is O(1). Next, convert the object-based tree into the final array-based tree data structure by traversing the object-based tree and then converting each layer into arrays.
I also make heavy use of recursion since recursion is well suited for creating and traversing trees.
Compared to the other answers, my algorithm has better time complexity because I create a dictionary/object which has O(1) access when creating the tree. The other algorithms do a search within each layer, which is inefficient. My algorithm runs in O(N) whereas the other answers here are shorter but run in O(N^2).
Just copy the format
function into your code and it should be good to use.
const codes = [
{ code: '01' },
{ code: '0101' },
{ code: '0102' },
{ code: '010201' },
{ code: '0103' },
{ code: '02' },
{ code: '0201' },
{ code: '0202' },
];
function format(codes) {
// Splits the string into an array of 2-character strings.
const SPLIT_REGEX = /.{2}(?=(.{2})+(?!.))|.{2}$/g;
const codeFragments = codes.map(obj => obj.code.match(SPLIT_REGEX));
// 1. Represent the data as a tree which is more efficient to build.
const tree = {};
function createTree(tree, fragments) {
let node = tree;
fragments.forEach(fragment => {
if (!node[fragment]) {
node[fragment] = {};
}
node = node[fragment];
});
}
codeFragments.forEach(fragments => createTree(tree, fragments));
/* tree will have the structure:
{
"01": {
"01": {},
"02": {
"01": {}
},
"03": {}
},
"02": {
"01": {},
"02": {}
}
}
*/
// 2. Convert the tree structure into the desired format.
function generateCodesFromTree(tree, previous) {
const nestedCodes = ;
Object.keys(tree).forEach(treeNode => {
const code = previous + treeNode;
const children = generateCodesFromTree(tree[treeNode], code);
const nestedCode = { code };
if (children.length > 0) {
nestedCode.children = children;
}
nestedCodes.push(nestedCode);
});
return nestedCodes;
}
return generateCodesFromTree(tree, '');
}
console.log(format(codes));
const codes = [
{ code: '01' },
{ code: '0101' },
{ code: '0102' },
{ code: '010201' },
{ code: '0103' },
{ code: '02' },
{ code: '0201' },
{ code: '0202' },
];
function format(codes) {
// Splits the string into an array of 2-character strings.
const SPLIT_REGEX = /.{2}(?=(.{2})+(?!.))|.{2}$/g;
const codeFragments = codes.map(obj => obj.code.match(SPLIT_REGEX));
// 1. Represent the data as a tree which is more efficient to build.
const tree = {};
function createTree(tree, fragments) {
let node = tree;
fragments.forEach(fragment => {
if (!node[fragment]) {
node[fragment] = {};
}
node = node[fragment];
});
}
codeFragments.forEach(fragments => createTree(tree, fragments));
/* tree will have the structure:
{
"01": {
"01": {},
"02": {
"01": {}
},
"03": {}
},
"02": {
"01": {},
"02": {}
}
}
*/
// 2. Convert the tree structure into the desired format.
function generateCodesFromTree(tree, previous) {
const nestedCodes = ;
Object.keys(tree).forEach(treeNode => {
const code = previous + treeNode;
const children = generateCodesFromTree(tree[treeNode], code);
const nestedCode = { code };
if (children.length > 0) {
nestedCode.children = children;
}
nestedCodes.push(nestedCode);
});
return nestedCodes;
}
return generateCodesFromTree(tree, '');
}
console.log(format(codes));
const codes = [
{ code: '01' },
{ code: '0101' },
{ code: '0102' },
{ code: '010201' },
{ code: '0103' },
{ code: '02' },
{ code: '0201' },
{ code: '0202' },
];
function format(codes) {
// Splits the string into an array of 2-character strings.
const SPLIT_REGEX = /.{2}(?=(.{2})+(?!.))|.{2}$/g;
const codeFragments = codes.map(obj => obj.code.match(SPLIT_REGEX));
// 1. Represent the data as a tree which is more efficient to build.
const tree = {};
function createTree(tree, fragments) {
let node = tree;
fragments.forEach(fragment => {
if (!node[fragment]) {
node[fragment] = {};
}
node = node[fragment];
});
}
codeFragments.forEach(fragments => createTree(tree, fragments));
/* tree will have the structure:
{
"01": {
"01": {},
"02": {
"01": {}
},
"03": {}
},
"02": {
"01": {},
"02": {}
}
}
*/
// 2. Convert the tree structure into the desired format.
function generateCodesFromTree(tree, previous) {
const nestedCodes = ;
Object.keys(tree).forEach(treeNode => {
const code = previous + treeNode;
const children = generateCodesFromTree(tree[treeNode], code);
const nestedCode = { code };
if (children.length > 0) {
nestedCode.children = children;
}
nestedCodes.push(nestedCode);
});
return nestedCodes;
}
return generateCodesFromTree(tree, '');
}
console.log(format(codes));
edited Nov 27 '18 at 7:39
answered Nov 27 '18 at 7:21
Yangshun TayYangshun Tay
10.3k54075
10.3k54075
I tested all the answers(except joven28's answer because of its imprecise result) and slider's answer was the fastest : jsperf.com/conv-1d-arr-sorted-by-ascii-order-to-nested-arr
– AmirhosseinDZ
Dec 1 '18 at 10:08
@AmirhosseinDZ What assumptions can we make about your code beside it being sorted? Can we assume with if there's010201
, there will be a0102
present? If we can assume that, a lot more optimization can be done. Your benchmark is not accurate. You wouldn't see the full picture by testing on your small set of codes. Here's a better benchmark with 1000 rows: jsperf.com/conv-1d-arr-sorted-by-ascii-order-to-nested-arr/5. If you look at the results of this benchmark, slider's answer errored out, Ahmad's answer is fastest but the answer is wrong because of above assumption.
– Yangshun Tay
Dec 1 '18 at 20:37
add a comment |
I tested all the answers(except joven28's answer because of its imprecise result) and slider's answer was the fastest : jsperf.com/conv-1d-arr-sorted-by-ascii-order-to-nested-arr
– AmirhosseinDZ
Dec 1 '18 at 10:08
@AmirhosseinDZ What assumptions can we make about your code beside it being sorted? Can we assume with if there's010201
, there will be a0102
present? If we can assume that, a lot more optimization can be done. Your benchmark is not accurate. You wouldn't see the full picture by testing on your small set of codes. Here's a better benchmark with 1000 rows: jsperf.com/conv-1d-arr-sorted-by-ascii-order-to-nested-arr/5. If you look at the results of this benchmark, slider's answer errored out, Ahmad's answer is fastest but the answer is wrong because of above assumption.
– Yangshun Tay
Dec 1 '18 at 20:37
I tested all the answers(except joven28's answer because of its imprecise result) and slider's answer was the fastest : jsperf.com/conv-1d-arr-sorted-by-ascii-order-to-nested-arr
– AmirhosseinDZ
Dec 1 '18 at 10:08
I tested all the answers(except joven28's answer because of its imprecise result) and slider's answer was the fastest : jsperf.com/conv-1d-arr-sorted-by-ascii-order-to-nested-arr
– AmirhosseinDZ
Dec 1 '18 at 10:08
@AmirhosseinDZ What assumptions can we make about your code beside it being sorted? Can we assume with if there's
010201
, there will be a 0102
present? If we can assume that, a lot more optimization can be done. Your benchmark is not accurate. You wouldn't see the full picture by testing on your small set of codes. Here's a better benchmark with 1000 rows: jsperf.com/conv-1d-arr-sorted-by-ascii-order-to-nested-arr/5. If you look at the results of this benchmark, slider's answer errored out, Ahmad's answer is fastest but the answer is wrong because of above assumption.– Yangshun Tay
Dec 1 '18 at 20:37
@AmirhosseinDZ What assumptions can we make about your code beside it being sorted? Can we assume with if there's
010201
, there will be a 0102
present? If we can assume that, a lot more optimization can be done. Your benchmark is not accurate. You wouldn't see the full picture by testing on your small set of codes. Here's a better benchmark with 1000 rows: jsperf.com/conv-1d-arr-sorted-by-ascii-order-to-nested-arr/5. If you look at the results of this benchmark, slider's answer errored out, Ahmad's answer is fastest but the answer is wrong because of above assumption.– Yangshun Tay
Dec 1 '18 at 20:37
add a comment |
It can only be achieved by using a recursive approach. Try this one.
let codes = [
{ code: '01' },
{ code: '0101' },
{ code: '0102' },
{ code: '010201' },
{ code: '0103' },
{ code: '02' },
{ code: '0201' },
{ code: '0202' },
];
roots = codes.filter(c => c.code.length === 2);
roots.forEach(c => assign(c));
console.log(roots);
function assign(code) {
codes.forEach(c => {
if (c !== code) {
if (code.code === c.code.slice(0, code.code.length)) {
code.children = !code.children ? [c] : [...code.children, c];
assign(code.children[code.children.length - 1]);
}
}
});
}
add a comment |
It can only be achieved by using a recursive approach. Try this one.
let codes = [
{ code: '01' },
{ code: '0101' },
{ code: '0102' },
{ code: '010201' },
{ code: '0103' },
{ code: '02' },
{ code: '0201' },
{ code: '0202' },
];
roots = codes.filter(c => c.code.length === 2);
roots.forEach(c => assign(c));
console.log(roots);
function assign(code) {
codes.forEach(c => {
if (c !== code) {
if (code.code === c.code.slice(0, code.code.length)) {
code.children = !code.children ? [c] : [...code.children, c];
assign(code.children[code.children.length - 1]);
}
}
});
}
add a comment |
It can only be achieved by using a recursive approach. Try this one.
let codes = [
{ code: '01' },
{ code: '0101' },
{ code: '0102' },
{ code: '010201' },
{ code: '0103' },
{ code: '02' },
{ code: '0201' },
{ code: '0202' },
];
roots = codes.filter(c => c.code.length === 2);
roots.forEach(c => assign(c));
console.log(roots);
function assign(code) {
codes.forEach(c => {
if (c !== code) {
if (code.code === c.code.slice(0, code.code.length)) {
code.children = !code.children ? [c] : [...code.children, c];
assign(code.children[code.children.length - 1]);
}
}
});
}
It can only be achieved by using a recursive approach. Try this one.
let codes = [
{ code: '01' },
{ code: '0101' },
{ code: '0102' },
{ code: '010201' },
{ code: '0103' },
{ code: '02' },
{ code: '0201' },
{ code: '0202' },
];
roots = codes.filter(c => c.code.length === 2);
roots.forEach(c => assign(c));
console.log(roots);
function assign(code) {
codes.forEach(c => {
if (c !== code) {
if (code.code === c.code.slice(0, code.code.length)) {
code.children = !code.children ? [c] : [...code.children, c];
assign(code.children[code.children.length - 1]);
}
}
});
}
let codes = [
{ code: '01' },
{ code: '0101' },
{ code: '0102' },
{ code: '010201' },
{ code: '0103' },
{ code: '02' },
{ code: '0201' },
{ code: '0202' },
];
roots = codes.filter(c => c.code.length === 2);
roots.forEach(c => assign(c));
console.log(roots);
function assign(code) {
codes.forEach(c => {
if (c !== code) {
if (code.code === c.code.slice(0, code.code.length)) {
code.children = !code.children ? [c] : [...code.children, c];
assign(code.children[code.children.length - 1]);
}
}
});
}
let codes = [
{ code: '01' },
{ code: '0101' },
{ code: '0102' },
{ code: '010201' },
{ code: '0103' },
{ code: '02' },
{ code: '0201' },
{ code: '0202' },
];
roots = codes.filter(c => c.code.length === 2);
roots.forEach(c => assign(c));
console.log(roots);
function assign(code) {
codes.forEach(c => {
if (c !== code) {
if (code.code === c.code.slice(0, code.code.length)) {
code.children = !code.children ? [c] : [...code.children, c];
assign(code.children[code.children.length - 1]);
}
}
});
}
edited Nov 27 '18 at 6:55
answered Nov 27 '18 at 6:50
Joven28Joven28
42911
42911
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53493545%2fconvert-1d-array-sorted-by-ascii-order-to-a-nested-array-in-javascript%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Sounds like an algorithms class homework/LeetCode question. It'd make a good coding interview question if it isn't one.
– Yangshun Tay
Nov 27 '18 at 6:48
1
@YangshunTay It's not just a homework question! I'm developing a financial web application and these codes are related to accounting.
– AmirhosseinDZ
Nov 27 '18 at 7:16
It's an interesting question. Have come up with an answer! (:
– Yangshun Tay
Nov 27 '18 at 7:28