It is necessary to optimize this code in order to get the result of the program execution faster than in a couple of million years. At first glance, everything is simple, but I have already completely covered my eyes. I would be grateful for any hint.

function buildRandomTreeFromCenterRightLeft(s) { if (s == '') { return null; } var center = s.substr(0, 1); var rightAndLeft = s.substr(1); var rightLength = Math.floor((rightAndLeft.length + 1)); var right = rightAndLeft.substr(0, rightLength); var left = rightAndLeft.substr(rightLength, rightAndLeft.length); return { center: center, left: buildRandomTreeFromCenterRightLeft(left), right: buildRandomTreeFromCenterRightLeft(right), }; } function printTreeLeftCenterRight(tree) { if (tree == null) { return ''; } return printTreeLeftCenterRight(tree.left) + tree.center + printTreeLeftCenterRight(tree.right); } function printTreeRightLeftCenter(tree) { if (tree == null) { return ''; } return printTreeRightLeftCenter(tree.right) + printTreeRightLeftCenter(tree.left) + tree.center; } function findEmail(centerRightLeft, leftCenterRight) { while (true) { var tree = buildRandomTreeFromCenterRightLeft(centerRightLeft); if (printTreeLeftCenterRight(tree) == leftCenterRight) { var email = printTreeRightLeftCenter(tree); console.log(email); break; } } } var easyProblem = { centerRightLeft: 'damEra@ilh', leftCenterRight: 'hal@irdamE', } findEmail(easyProblem.centerRightLeft, easyProblem.leftCenterRight); var hardProblem = { centerRightLeft: '.o elPsaec lamei.a sur@h treotrdil0ems.al Pe7 dnse8dco9e:i438f7bfc5224b5d151bdc4ai bc91eamuoy ne r', leftCenterRight: 'er muyn oaia1e 9cbi14bdcc55d15b4227fb43f8l:9e8odc7dens 0eaPl s.em.iderotrr@t h.aus c ilaemo saeelP', } findEmail(hardProblem.centerRightLeft, hardProblem.leftCenterRight);

By the condition of easyProblem code executes easyProblem iterations and gives the result. On hardProblem hangs for a long time. I tried to build a tree based on the second key field (with which the comparison is made), but without success. I tried a bunch of different variations of the construction, but did not move from the starting point. It seems to me that everything is easier and an experienced eye will immediately find a way.

  • So far, I see that your code does the same thing in an infinite loop. There is nothing random in the function despite the random in the title - Alexey Ten
  • Thanks, but nevertheless, do you have any ideas how to optimize the code to get the required output before the sun burns?) - Yurii

1 answer 1

It does not need a random search. You just need to consistently solve the problem. For example from the condition:

 var easyProblem = { centerRightLeft: 'damEra@ilh', leftCenterRight: 'hal@irdamE', }

it can be seen that the top of the tree is the letter d . Find it in the leftCenterRight . All that goes before this letter is the left subtree, that after - the right one. Total task is reduced to:

 var easyProblem = { centerRightLeft: 'damEra@ilh', leftCenterRight: 'hal@irdamE', center: 'd', leftTree: { centerRightLeft: 'ra@ilh', leftCenterRight: 'hal@id' }, rightTree: { centerRightLeft: 'amE', leftCenterRight: 'amE' } }

Next, we solve the problem recursively (as you have already written).

It is important to remember that:

  1. A character can appear in the string several times and you need to select the correct partition;
  2. Formally, there may be several suitable solutions, but not everyone will give a meaningful phrase.