



<script src="/lib/lodash/dist/lodash.js"></script>
<script src="/lib/platform/platform.js"></script>
<script src="/lib/benchmark/benchmark.js"></script>
<script src="/js/testrunner.js?v=uhhjlNf8Vw1G0SsjCNR5kDrchDwmF1nqr2pn9YS1pz0"></script>

    <span><script src="//cdnjs.cloudflare.com/ajax/libs/seedrandom/3.0.5/seedrandom.min.js">
</script></span>

<div id="validation-html-preparation"></div>

<script type="text/javascript">
    pageController = new TestRunnerController();
</script>
<textarea id="benchmark_definition_json" style="display:none">
    {&quot;ScriptPreparationCode&quot;:&quot;function shuffle(array) {\r\n    var myrng = new Math.seedrandom(\u0027hello.\u0027);\r\n\r\n    let currentIndex = array.length, temporaryValue, randomIndex;\r\n\r\n    // While there remain elements to shuffle...\r\n    while (0 !== currentIndex) {\r\n\r\n        // Pick a remaining element...\r\n        randomIndex = Math.floor(myrng() * currentIndex);\r\n        currentIndex -= 1;\r\n\r\n        // And swap it with the current element.\r\n        temporaryValue = array[currentIndex];\r\n        array[currentIndex] = array[randomIndex];\r\n        array[randomIndex] = temporaryValue;\r\n    }\r\n\r\n    return array;\r\n}\r\n\r\nvar N = 1000;\r\nvar original_array = Array.from(Array(N).keys());\r\nvar shuffled_array = shuffle(original_array.slice(0));\r\n&quot;,&quot;TestCases&quot;:[{&quot;Name&quot;:&quot;splice&quot;,&quot;Code&quot;:&quot;function longest_increasing_subsequence (input) {\r\n    const from_array = Array.from(Array(input.length).keys());\r\n    let result_array = [], indexes = [];\r\n\r\n    let n = input.length;\r\n\r\n    if (n === 0) {\r\n        return [];\r\n    }\r\n\r\n    let d = new Array(n).fill(1);\r\n    let p = new Array(n).fill(-1);\r\n\r\n    for (let i = 0; i \u003C n; i\u002B\u002B) {\r\n        for (let j = 0; j \u003C i; j\u002B\u002B) {\r\n            if (input[j] \u003C input[i] \u0026\u0026 d[i] \u003C d[j] \u002B 1) {\r\n                d[i] = d[j] \u002B 1;\r\n                p[i] = j;\r\n            }\r\n        }\r\n    }\r\n\r\n    let ans = d[0], pos = 0;\r\n    for (let i = 1; i \u003C n; i\u002B\u002B) {\r\n        if (d[i] \u003E ans) {\r\n            ans = d[i];\r\n            pos = i;\r\n        }\r\n    }\r\n\r\n    while(pos != -1) {\r\n        // result_array.push(input[pos]);\r\n        indexes.push(pos);\r\n        pos = p[pos];\r\n    }\r\n    // result_array.reverse()\r\n    indexes.reverse()\r\n\r\n    // console.log(\u0060Longest increasing sequence: ${result_array}\u0060);\r\n    console.log(\u0060Longest increasing indexes: ${indexes}\u0060);\r\n    for (let i = indexes.length -1; i \u003E= 0; i--) {\r\n        input.splice(indexes[i],1);\r\n        from_array.splice(indexes[i],1);\r\n    }\r\n\r\n    return [from_array, input];\r\n}\r\n\r\nfunction find_moves_step_one(from_array, to_array) {\r\n    for (let i = 0; i \u003C from_array.length; i\u002B\u002B) {\r\n        for (let j = i\u002B1; j \u003C from_array.length; j\u002B\u002B) {\r\n            if(from_array[j] \u003E= from_array[i]) {\r\n                from_array[j]--;\r\n            }\r\n        }\r\n    }\r\n    for (let i = to_array.length - 1; i \u003E= 0; i--) {\r\n        for (let j = i-1; j \u003E= 0; j--) {\r\n            if(to_array[j] \u003E to_array[i]) {\r\n                to_array[j]--;\r\n            }\r\n        }\r\n    }\r\n    return [from_array, to_array];\r\n}\r\n\r\nfunction find_moves_step_two(from_array, to_array) {\r\n    let increase_in_i = 0;\r\n    for (let i = 0; i \u003C to_array.length; i\u002B\u002B) {\r\n        for (let j = to_array.length - 1; j \u003E= i\u002B1; j--) {\r\n            if(from_array[j] \u003C to_array[i]) {\r\n                increase_in_i\u002B\u002B;\r\n            } else {\r\n                from_array[j]\u002B\u002B;\r\n            }\r\n        }\r\n        to_array[i] \u002B= increase_in_i;\r\n        increase_in_i = 0;\r\n    }\r\n    return [from_array, to_array];\r\n}\r\n\r\nfunction find_target_index(from_array, to_array) {\r\n    if(JSON.stringify(from_array) == JSON.stringify(to_array)) {\r\n        return [];\r\n    } else {\r\n        const target_index_arr = Array(from_array.length).fill(0);\r\n        let index_found;\r\n        from_array.forEach(function(item, index) {\r\n            index_found = to_array.indexOf(item);\r\n            if(index_found !== -1) {\r\n                target_index_arr[index] = index_found;\r\n            } else {\r\n                //TODO make something dude! its not normal\r\n            }\r\n        });\r\n        return target_index_arr;\r\n    }\r\n}\r\n\r\nfunction move(array, from_array, to_array) {\r\n    let item;\r\n    for(let i = 0; i \u003C from_array.length; i\u002B\u002B) {\r\n        if(from_array[i] \u003E to_array[i]) {\r\n            item = array[from_array[i]];\r\n            for(let j = from_array[i] - 1; j \u003E= to_array[i]; j--) {\r\n                array[j\u002B1] = array[j];\r\n            }\r\n            array[to_array[i]] = item;\r\n        } else if(to_array[i] \u003E from_array[i]) {\r\n            item = array[from_array[i]];\r\n            for(let j = from_array[i]; j \u003C= to_array[i]; j\u002B\u002B) {\r\n                array[j] = array[j\u002B1];\r\n            }\r\n            array[to_array[i]] = item;\r\n        }\r\n    }\r\n    return array;\r\n}\r\n\r\nconst target_index_arr = find_target_index(shuffled_array.slice(0), original_array.slice(0));\r\nif(target_index_arr.length \u003E 0) {\r\n    console.log(\u0060target index array: ${target_index_arr}\u0060);\r\n    const [from_array, to_array] = longest_increasing_subsequence(target_index_arr.slice(0));\r\n    const [from_after_step1, to_after_step1] = find_moves_step_one(from_array.slice(0), to_array.slice(0))\r\n    const [from_after_step2, to_after_step2] = find_moves_step_two(from_after_step1.slice(0), to_after_step1.slice(0))\r\n}&quot;,&quot;IsDeferred&quot;:false},{&quot;Name&quot;:&quot;last&quot;,&quot;Code&quot;:&quot;function longest_increasing_subsequence (input) {\r\n    const from_array = Array.from(Array(input.length).keys());\r\n    let result_array = [], indexes = [];\r\n\r\n    let n = input.length;\r\n\r\n    if (n === 0) {\r\n        return [];\r\n    }\r\n\r\n    let d = new Array(n).fill(1);\r\n    let p = new Array(n).fill(-1);\r\n\r\n    for (let i = 0; i \u003C n; i\u002B\u002B) {\r\n        for (let j = 0; j \u003C i; j\u002B\u002B) {\r\n            if (input[j] \u003C input[i] \u0026\u0026 d[i] \u003C d[j] \u002B 1) {\r\n                d[i] = d[j] \u002B 1;\r\n                p[i] = j;\r\n            }\r\n        }\r\n    }\r\n\r\n    let ans = d[0], pos = 0;\r\n    for (let i = 1; i \u003C n; i\u002B\u002B) {\r\n        if (d[i] \u003E ans) {\r\n            ans = d[i];\r\n            pos = i;\r\n        }\r\n    }\r\n\r\n    while(pos != -1) {\r\n        // result_array.push(input[pos]);\r\n        indexes.push(pos);\r\n        pos = p[pos];\r\n    }\r\n    // result_array.reverse()\r\n    indexes.reverse()\r\n\r\n    // console.log(\u0060Longest increasing sequence: ${result_array}\u0060);\r\n    console.log(\u0060Longest increasing indexes: ${indexes}\u0060);\r\n    for (let i = indexes.length -1; i \u003E= 0; i--) {\r\n        input.splice(indexes[i],1);\r\n        from_array.splice(indexes[i],1);\r\n    }\r\n\r\n    return [from_array, input];\r\n}\r\n\r\nfunction find_moves_step_one(from_array, to_array) {\r\n    for (let i = 0; i \u003C from_array.length; i\u002B\u002B) {\r\n        for (let j = i\u002B1; j \u003C from_array.length; j\u002B\u002B) {\r\n            if(from_array[j] \u003E= from_array[i]) {\r\n                from_array[j]--;\r\n            }\r\n        }\r\n    }\r\n    for (let i = to_array.length - 1; i \u003E= 0; i--) {\r\n        for (let j = i-1; j \u003E= 0; j--) {\r\n            if(to_array[j] \u003E to_array[i]) {\r\n                to_array[j]--;\r\n            }\r\n        }\r\n    }\r\n}\r\n\r\nfunction find_moves_step_two(from_array, to_array) {\r\n    let increase_in_i = 0;\r\n    for (let i = 0; i \u003C to_array.length; i\u002B\u002B) {\r\n        for (let j = to_array.length - 1; j \u003E= i\u002B1; j--) {\r\n            if(from_array[j] \u003C to_array[i]) {\r\n                increase_in_i\u002B\u002B;\r\n            } else {\r\n                from_array[j]\u002B\u002B;\r\n            }\r\n        }\r\n        to_array[i] \u002B= increase_in_i;\r\n        increase_in_i = 0;\r\n    }\r\n}\r\n\r\nfunction find_target_index(from_array, to_array) {\r\n    if(JSON.stringify(from_array) == JSON.stringify(to_array)) {\r\n        return [];\r\n    } else {\r\n        const target_index_arr = Array(from_array.length).fill(0);\r\n        let index_found;\r\n        from_array.forEach(function(item, index) {\r\n            index_found = to_array.indexOf(item);\r\n            if(index_found !== -1) {\r\n                target_index_arr[index] = index_found;\r\n            } else {\r\n                //TODO make something dude! its not normal\r\n            }\r\n        });\r\n        return target_index_arr;\r\n    }\r\n}\r\n\r\nfunction move(array, from_array, to_array) {\r\n    let item;\r\n    for(let i = 0; i \u003C from_array.length; i\u002B\u002B) {\r\n        if(from_array[i] \u003E to_array[i]) {\r\n            item = array[from_array[i]];\r\n            for(let j = from_array[i] - 1; j \u003E= to_array[i]; j--) {\r\n                array[j\u002B1] = array[j];\r\n            }\r\n            array[to_array[i]] = item;\r\n        } else if(to_array[i] \u003E from_array[i]) {\r\n            item = array[from_array[i]];\r\n            for(let j = from_array[i]; j \u003C= to_array[i]; j\u002B\u002B) {\r\n                array[j] = array[j\u002B1];\r\n            }\r\n            array[to_array[i]] = item;\r\n        }\r\n    }\r\n    return array;\r\n}\r\n\r\nconst target_index_arr = find_target_index(shuffled_array, original_array);\r\nif(target_index_arr.length \u003E 0) {\r\n    const [from_array, to_array] = longest_increasing_subsequence(target_index_arr);\r\n    find_moves_step_one(from_array, to_array)\r\n    find_moves_step_two(from_array, to_array)\r\n}\r\n&quot;,&quot;IsDeferred&quot;:false}]}
</textarea>

<form style="display:none;" id="autoreload_form" action="/Benchmarks/TestFrameForValidationWithHtmlPrepCode?autostart=1" method="post">
    <input type="hidden" name="htmlPrepCode" id="htmlPrepCode">
</form>