title

Coding Challenge #35.2: Lexicographic Order

description

In Part 1 of this multi-part coding challenge, I introduce the classic computer science problem of the Traveling Salesperson (TSP) and discuss the pitfalls with a brute force solution. In Part 2, I discuss Lexicographic Ordering and demonstrate one algorithm to iterate over all the permutations of an array. In Part 3, I apply this algorithm to a brute-force solution of the TSP problem. Every single route permutation is checked one by one. In Part 4, I attempt to create a solution to the TSP problem with a genetic algorithm, and then I add a βcrossoverβ algorithm in Part 5. Code: https://thecodingtrain.com/challenges/35-traveling-salesperson
p5.js Web Editor Sketches:
πΉοΈ Part 1: Traveling Salesperson (TSP): https://editor.p5js.org/codingtrain/sketches/FCNAHaCqf
πΉοΈ Part 2: Lexicographic Order: https://editor.p5js.org/codingtrain/sketches/iYxi30gbl
πΉοΈ Part 3: TSP with Lexicographic Order: https://editor.p5js.org/codingtrain/sketches/bWPIkEv9s
πΉοΈ Part 4: TSP with Genetic Algorithm: https://editor.p5js.org/codingtrain/sketches/EGjTrkkf9
πΉοΈ Part 5: TSP with Genetic Algorithm and Crossover: https://editor.p5js.org/codingtrain/sketches/EGjTrkkf9
Other Parts of this Challenge:
πΊ Part 1: Traveling Salesperson (TSP): https://youtu.be/BAejnwN4Ccw
πΊ Part 3: TSP with Lexicographic Order: https://youtu.be/9Xy-LMAfglE
πΊ Part 4: TSP with Genetic Algorithm: https://youtu.be/M3KTWnTrU_c
πΊ Part 5: TSP with Genetic Algorithm and Crossover: https://youtu.be/hnxn6DtLYcY
π₯ Previous video: https://youtu.be/Cl_Gjj80gPE?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH
π₯ Next video: https://youtu.be/rX5p-QRP6R4?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH
π₯ All videos: https://www.youtube.com/playlist?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH
References:
π Traveling Salesman on Wikipedia: https://en.wikipedia.org/wiki/Travelling_salesman_problem
π¨οΈ Permutation Algorithm Using Lexicographic Ordering: https://www.quora.com/How-would-you-explain-an-algorithm-that-generates-permutations-using-lexicographic-ordering
π Array on MDN: https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Array
π Array.includes() on MDN: https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Array/includes
π Array.reverse() on MDN: https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Array/reverse
π ES6 Sets on MDN: https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Set
πΎ The Nature of Code Part 2: https://github.com/shiffman/NOC-S17-2-Intelligence-Learning
π The Nature of Code: http://natureofcode.com/
Videos:
π₯ Improved Pool Selection: https://www.youtube.com/watch?v=ETphJASzYes&list=PLRqwX-V7Uu6YJ3XfHhT2Mm4Y5I99nrIKX&index=23
π₯ Genetic Algorithm Playlist: https://www.youtube.com/playlist?list=PLRqwX-V7Uu6bJM3VgzjNV5YxVxUwzALHV
π΄ Live Stream Archive #57: https://youtu.be/r_SpBy9fQuo
Related Coding Challenges:
π #29 Smart Rockets in p5.js: https://youtu.be/bGz7mv2vD6g
π #51 A* Pathfinding Algorithm: https://youtu.be/aKYlikFAV4k
π #69 Evolutionary Steering Behaviors: https://youtu.be/flxOkx0yLrY
π #70 Nearest Neighbors Recommendation Engine: https://youtu.be/N8Fabn1om2k
Timestamps:
00:00 Introducing Part 2
00:33 What is Lexical Ordering?
02:55 An article on Lexicographic Ordering
04:00 Code! Implementing the algorithm
04:42 Step 1 of the algorithm: largest x
06:48 Step 2 of the algorithm: largest y
09:19 Step 3 of the algorithm: swap
10:28 Step 4 of the algorithm: reverse
11:03 The splice() array function
12:26 The reverse() array function
13:43 Oups! Fixing array concatenation
15:05 Debugging the code
18:30 Yay! The correct result!
18:39 Visualizing the algorithm
19:56 How many permutations are they?
Editing by Mathieu Blanchette
Animations by Jason Heglund
Music from Epidemic Sound
π Website: http://thecodingtrain.com/
πΎ Share Your Creation! https://thecodingtrain.com/guides/passenger-showcase-guide
π© Suggest Topics: https://github.com/CodingTrain/Suggestion-Box
π‘ GitHub: https://github.com/CodingTrain
π¬ Discord: https://discord.gg/hPuGy2g
π Membership: http://youtube.com/thecodingtrain/join
π Store: https://standard.tv/codingtrain
ποΈ Twitter: https://twitter.com/thecodingtrain
πΈ Instagram: https://www.instagram.com/the.coding.train/
π₯ Coding Challenges: https://www.youtube.com/playlist?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH
π₯ Intro to Programming: https://www.youtube.com/playlist?list=PLRqwX-V7Uu6Zy51Q-x9tMWIv9cueOFTFA
π p5.js: https://p5js.org
π p5.js Web Editor: https://editor.p5js.org/
π Processing: https://processing.org
π Code of Conduct: https://github.com/CodingTrain/Code-of-Conduct
This description was auto-generated. If you see a problem, please open an issue: https://github.com/CodingTrain/thecodingtrain.com/issues/new
#travelingsalesperson #permutation #lexicographicordering #natureofcode #geneticalgorithm #evolution #bruteforce #factorial #arrays #p5js

detail

{'title': 'Coding Challenge #35.2: Lexicographic Order', 'heatmap': [{'end': 507.867, 'start': 464.936, 'weight': 0.848}], 'summary': 'Discusses lexicographic ordering and its application to the traveling salesperson problem, covering the concept of lexical order in computer sorting with a goal of iterating through different city orders, including baltimore, new york, london, kuala lumpur, rio, and coventry, uk, as well as algorithm implementation, array operations, and debugging in javascript.', 'chapters': [{'end': 33.13, 'segs': [{'end': 33.13, 'src': 'embed', 'start': 0.069, 'weight': 0, 'content': [{'end': 3.495, 'text': 'Hello Welcome to another coding challenge video.', 'start': 0.069, 'duration': 3.426}, {'end': 7.783, 'text': "In this coding challenge, I'm going to look at something called lexicographic ordering.", 'start': 3.555, 'duration': 4.228}, {'end': 16.285, 'text': "and look at an algorithm for solving lexicographic, which for some reason I can't say, but you can say lexical for short.", 'start': 9.363, 'duration': 6.922}, {'end': 21.487, 'text': "so I'm gonna say lexical ordering, just kind of like alphabetical ordering, and we're gonna look at how that works.", 'start': 16.285, 'duration': 5.202}, {'end': 22.867, 'text': 'make a little algorithm that solves it.', 'start': 21.487, 'duration': 1.38}, {'end': 25.968, 'text': 'you might have some creative ideas about how to visualize it or make something out of it,', 'start': 22.867, 'duration': 3.101}, {'end': 33.13, 'text': "and then I'm going to apply it to the traveling salesperson problem to look at how we can look at every possible path through a set of cities.", 'start': 25.968, 'duration': 7.162}], 'summary': 'Coding challenge on lexicographic ordering and its application to the traveling salesperson problem.', 'duration': 33.061, 'max_score': 0.069, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/goUlyp4rwiU/pics/goUlyp4rwiU69.jpg'}], 'start': 0.069, 'title': 'Lexicographic ordering and traveling salesperson problem', 'summary': 'Explores lexicographic ordering and its application to the traveling salesperson problem, analyzing all possible paths through a set of cities.', 'chapters': [{'end': 33.13, 'start': 0.069, 'title': 'Lexicographic ordering and traveling salesperson problem', 'summary': 'Explores lexicographic ordering and an algorithm for solving it, which is similar to alphabetical ordering. it also applies the algorithm to the traveling salesperson problem to analyze every possible path through a set of cities.', 'duration': 33.061, 'highlights': ['The chapter discusses lexicographic ordering, an algorithm for solving it, and its similarity to alphabetical ordering.', 'The chapter explores the application of lexicographic ordering to the traveling salesperson problem to analyze all possible paths through a set of cities.']}], 'duration': 33.061, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/goUlyp4rwiU/pics/goUlyp4rwiU69.jpg', 'highlights': ['The chapter explores the application of lexicographic ordering to the traveling salesperson problem to analyze all possible paths through a set of cities.', 'The chapter discusses lexicographic ordering, an algorithm for solving it, and its similarity to alphabetical ordering.']}, {'end': 218.366, 'segs': [{'end': 96.605, 'src': 'embed', 'start': 58.324, 'weight': 1, 'content': [{'end': 61.468, 'text': "that's also the next order in alphabetical order like.", 'start': 58.324, 'duration': 3.144}, {'end': 66.875, 'text': "I could say like here's another order C, B, a, or here's another order B, a, C.", 'start': 61.468, 'duration': 5.407}, {'end': 69.839, 'text': 'but neither of these are the next order in alphabetical order.', 'start': 66.875, 'duration': 2.964}, {'end': 76.526, 'text': 'now I could tell you that the next ordering in alphabetical order is A, C, B, right?, Because A should come first.', 'start': 69.839, 'duration': 6.687}, {'end': 78.108, 'text': 'Well, B already came second.', 'start': 76.826, 'duration': 1.282}, {'end': 79.889, 'text': 'The only other possibility is C.', 'start': 78.128, 'duration': 1.761}, {'end': 81.15, 'text': 'And then the only thing left is B.', 'start': 79.889, 'duration': 1.261}, {'end': 85.995, 'text': 'And then we could think, OK, well, I tried all the A possibilities, so the next in alphabetical order.', 'start': 81.15, 'duration': 4.845}, {'end': 89.678, 'text': 'And by the way, lexical order and alphabetical order are very similar concepts.', 'start': 86.035, 'duration': 3.643}, {'end': 96.605, 'text': "It's a sort of subtle distinction which has to do with how numbers or dates are kind of treated in the way that you might sort things in kind of the computer way.", 'start': 89.698, 'duration': 6.907}], 'summary': 'Explaining the next order in alphabetical order using a, c, b sequence.', 'duration': 38.281, 'max_score': 58.324, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/goUlyp4rwiU/pics/goUlyp4rwiU58324.jpg'}, {'end': 157.018, 'src': 'embed', 'start': 119.62, 'weight': 0, 'content': [{'end': 127.723, 'text': "But you know, if I have A, B, C, D, E, F, G, H, I, it's going to be a little bit harder, although not that much harder, because, honestly,", 'start': 119.62, 'duration': 8.103}, {'end': 131.885, 'text': "it's just going to be A, B, C, D, E, F, G, I, then H.", 'start': 127.723, 'duration': 4.162}, {'end': 133.625, 'text': "You can sort of imagine, and there's this swapping.", 'start': 131.885, 'duration': 1.74}, {'end': 138.707, 'text': 'So what we need is an algorithm to do this for us, and then print out every single possible ordering.', 'start': 133.645, 'duration': 5.062}, {'end': 145.57, 'text': "Because what I'm ultimately going to do with this is actually use these as indices into an array that has different cities in it.", 'start': 138.887, 'duration': 6.683}, {'end': 149.412, 'text': 'So, you know, Baltimore, New York, London.', 'start': 146.15, 'duration': 3.262}, {'end': 152.995, 'text': "I don't know, I shouldn't be so US, Europe-centric.", 'start': 149.432, 'duration': 3.563}, {'end': 157.018, 'text': 'Everybody in the comments, give me some better cities to use in my next example.', 'start': 153.735, 'duration': 3.283}], 'summary': 'Algorithm needed to print all possible orderings of cities in an array.', 'duration': 37.398, 'max_score': 119.62, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/goUlyp4rwiU/pics/goUlyp4rwiU119620.jpg'}, {'end': 218.366, 'src': 'embed', 'start': 174.827, 'weight': 2, 'content': [{'end': 183.509, 'text': "So let's go back over here, and I found this wonderful page on the subway this morning That I read in my Google search, which was a Quora post,", 'start': 174.827, 'duration': 8.682}, {'end': 185.13, 'text': 'that says how would you explain?', 'start': 183.509, 'duration': 1.621}, {'end': 189.551, 'text': 'an algorithm generates permutations using lexicographic ordering.', 'start': 185.13, 'duration': 4.421}, {'end': 191.371, 'text': 'so the wonderful thing about this.', 'start': 189.551, 'duration': 1.82}, {'end': 196.073, 'text': "answer by Michael for a sec check, which I'm sure I'm not pronouncing correctly, somebody will have to.", 'start': 191.371, 'duration': 4.702}, {'end': 201.852, 'text': 'Oh, people are giving me great cities Kuala, Lumpur, Rio, Coventry, UK.', 'start': 197.628, 'duration': 4.224}, {'end': 208.019, 'text': "So let's be an international coding rainbow here in this thing that I'm doing on YouTube.", 'start': 202.333, 'duration': 5.686}, {'end': 210.702, 'text': "So for the impatient, here's the actual algorithm.", 'start': 208.279, 'duration': 2.423}, {'end': 218.366, 'text': "So what I'm actually going to do in this video is just kind of read through this algorithm and sort of talk you through it and implement it.", 'start': 210.862, 'duration': 7.504}], 'summary': 'Exploring an algorithm for generating permutations using lexicographic ordering, as explained in a quora post by michael forsythe.', 'duration': 43.539, 'max_score': 174.827, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/goUlyp4rwiU/pics/goUlyp4rwiU174827.jpg'}], 'start': 33.45, 'title': 'Lexicographic ordering', 'summary': 'Explains how to determine alphabetical order using letters a, b, and c, and discusses the concept of lexical order in computer sorting. it also covers the process of generating permutations using lexicographic ordering, with a goal of iterating through different city orders, including baltimore, new york, london, kuala lumpur, rio, and coventry, uk.', 'chapters': [{'end': 138.707, 'start': 33.45, 'title': 'Lexical ordering explained', 'summary': 'Demonstrates how to determine the next ordering in alphabetical order using the example of letters a, b, and c, and discusses the concept of lexical order and alphabetical order in the context of computer sorting.', 'duration': 105.257, 'highlights': ['The next ordering in alphabetical order can be determined by considering the sequence of letters and identifying the next possible arrangement, such as A, C, B, based on the rules of alphabetical order.', 'The distinction between lexical order and alphabetical order is explained, with a focus on how numbers or dates are handled in computer sorting.', 'An algorithm is necessary to efficiently determine and print out every possible ordering of a given sequence of letters or characters, which becomes more challenging as the sequence length increases.']}, {'end': 218.366, 'start': 138.887, 'title': 'Algorithm for generating permutations', 'summary': 'Explains the process of generating permutations using lexicographic ordering, with the goal of creating an algorithm to iterate through different city orders, with a mention of baltimore, new york, london and the addition of kuala lumpur, rio, and coventry, uk.', 'duration': 79.479, 'highlights': ['The process of generating permutations using lexicographic ordering is explained. The chapter discusses the process of generating permutations using lexicographic ordering.', 'Mention of cities including Baltimore, New York, London, Kuala Lumpur, Rio, and Coventry, UK. The mention of cities like Baltimore, New York, London, Kuala Lumpur, Rio, and Coventry, UK, for use in iterating through different city orders.', 'The intention to implement the algorithm and iterate through different city orders is mentioned. The intention to implement the algorithm and iterate through different city orders, including Baltimore, New York, London, Kuala Lumpur, Rio, and Coventry, UK.']}], 'duration': 184.916, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/goUlyp4rwiU/pics/goUlyp4rwiU33450.jpg', 'highlights': ['An algorithm is necessary to efficiently determine and print out every possible ordering of a given sequence of letters or characters, which becomes more challenging as the sequence length increases.', 'The distinction between lexical order and alphabetical order is explained, with a focus on how numbers or dates are handled in computer sorting.', 'The process of generating permutations using lexicographic ordering is explained. The chapter discusses the process of generating permutations using lexicographic ordering.', 'The next ordering in alphabetical order can be determined by considering the sequence of letters and identifying the next possible arrangement, such as A, C, B, based on the rules of alphabetical order.', 'The intention to implement the algorithm and iterate through different city orders is mentioned. The intention to implement the algorithm and iterate through different city orders, including Baltimore, New York, London, Kuala Lumpur, Rio, and Coventry, UK.', 'Mention of cities including Baltimore, New York, London, Kuala Lumpur, Rio, and Coventry, UK. The mention of cities like Baltimore, New York, London, Kuala Lumpur, Rio, and Coventry, UK, for use in iterating through different city orders.']}, {'end': 647.465, 'segs': [{'end': 281.693, 'src': 'embed', 'start': 218.366, 'weight': 0, 'content': [{'end': 224.048, 'text': 'and I would suggest to you that if you want to find more about it, you can kind of read further down this page,', 'start': 218.366, 'duration': 5.682}, {'end': 232.49, 'text': 'where the author provides an example scenario of an example, order how the algorithm plays out with that example and then also derives this algorithm.', 'start': 224.048, 'duration': 8.442}, {'end': 234.571, 'text': "but I'm going to kind of leave that aside as kind of,", 'start': 232.49, 'duration': 2.081}, {'end': 239.552, 'text': 'and I just want to kind of like I think you might have an intuitive or kind of sense of how it works just by implementing it.', 'start': 234.571, 'duration': 4.981}, {'end': 243.255, 'text': "so first let's get ourselves set up to do this.", 'start': 239.992, 'duration': 3.263}, {'end': 244.657, 'text': 'what I want is to have an array.', 'start': 243.255, 'duration': 1.402}, {'end': 247.299, 'text': "I'm going to start with an array.", 'start': 244.657, 'duration': 2.642}, {'end': 253.505, 'text': "I'm going to call it vowels yeah, that's fine, and I'm going to have it be 0, 1, 2.", 'start': 247.299, 'duration': 6.206}, {'end': 255.827, 'text': "we're just going to start with three numbers.", 'start': 253.505, 'duration': 2.322}, {'end': 257.108, 'text': 'so we can see that it works.', 'start': 255.827, 'duration': 1.281}, {'end': 269.366, 'text': 'And what I want to do now in draw is first I want to what happens if I do console.log vals?', 'start': 259.541, 'duration': 9.825}, {'end': 273.488, 'text': "So let's just look at that and run this.", 'start': 269.746, 'duration': 3.742}, {'end': 274.869, 'text': "We can see, okay, so that's good.", 'start': 273.749, 'duration': 1.12}, {'end': 278.351, 'text': "I'm getting, I'm seeing here in the console the current order of the array.", 'start': 274.929, 'duration': 3.422}, {'end': 281.693, 'text': 'So I want to see it as I do each permutation one at a time.', 'start': 278.371, 'duration': 3.322}], 'summary': 'Demonstrating array permutation algorithm with 3 numbers on console', 'duration': 63.327, 'max_score': 218.366, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/goUlyp4rwiU/pics/goUlyp4rwiU218366.jpg'}, {'end': 370.207, 'src': 'embed', 'start': 344.028, 'weight': 6, 'content': [{'end': 358.456, 'text': "And what I want to do is say OK, if val's index i is less than val's i plus 1, then largest i equals i and I can't go to the very end, right.", 'start': 344.028, 'duration': 14.428}, {'end': 362.279, 'text': 'so I want to find what is the largest, and you know what I should really need to do.', 'start': 358.456, 'duration': 3.823}, {'end': 369.206, 'text': "I want to start with this as negative one, because I want to start with an invalid index, because if I don't find anything,", 'start': 362.279, 'duration': 6.927}, {'end': 370.207, 'text': "that's going to be important.", 'start': 369.206, 'duration': 1.001}], 'summary': 'Identify largest index where val[i] < val[i+1] using negative one as starting point.', 'duration': 26.179, 'max_score': 344.028, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/goUlyp4rwiU/pics/goUlyp4rwiU344028.jpg'}, {'end': 507.867, 'src': 'heatmap', 'start': 464.936, 'weight': 0.848, 'content': [{'end': 467.658, 'text': 'So zero, one, two, three, four.', 'start': 464.936, 'duration': 2.722}, {'end': 469.279, 'text': 'So this is four.', 'start': 467.958, 'duration': 1.321}, {'end': 473.943, 'text': "Now, so what's the next step? Whoops.", 'start': 470.02, 'duration': 3.923}, {'end': 480.829, 'text': 'The next step is find the largest y such that p of x is less than p of y.', 'start': 474.704, 'duration': 6.125}, {'end': 483.868, 'text': 'Not p index x.', 'start': 481.926, 'duration': 1.942}, {'end': 490.853, 'text': 'So I now need to find whichever one in here is actually less than this number six.', 'start': 483.868, 'duration': 6.985}, {'end': 496.478, 'text': "And that's actually here, right? This one is the largest one that's less than the number six.", 'start': 491.394, 'duration': 5.084}, {'end': 507.867, 'text': "So if we come back to the algorithm and I implement that, what I wanna do is I need to go through and I'm gonna use j.", 'start': 497.699, 'duration': 10.168}], 'summary': 'Finding the largest y such that p(x) is less than p(y) and implementing it using j.', 'duration': 42.931, 'max_score': 464.936, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/goUlyp4rwiU/pics/goUlyp4rwiU464936.jpg'}, {'end': 584.889, 'src': 'embed', 'start': 533.418, 'weight': 4, 'content': [{'end': 549.877, 'text': "So if If val's index j is less than val's index largest i, which was x, then largest j equals j.", 'start': 533.418, 'duration': 16.459}, {'end': 552.459, 'text': 'So now I have largest i and largest j.', 'start': 549.877, 'duration': 2.582}, {'end': 553.76, 'text': 'I have both of those.', 'start': 552.459, 'duration': 1.301}, {'end': 557.283, 'text': "And I don't think I need length minus 1 here, because I can check all of them.", 'start': 554.06, 'duration': 3.223}, {'end': 559.875, 'text': "We'll find out.", 'start': 559.335, 'duration': 0.54}, {'end': 563.817, 'text': 'Now, ah, swap p index x and p index y.', 'start': 560.496, 'duration': 3.321}, {'end': 569.34, 'text': 'Now, you might have come to this video without watching the previous one I made on traveling salesperson.', 'start': 563.817, 'duration': 5.523}, {'end': 574.243, 'text': 'But in that video, I look at a quick little algorithm for swapping two elements of an array.', 'start': 569.741, 'duration': 4.502}, {'end': 577.825, 'text': "And here's the function that does that, right? I have a function called swap.", 'start': 574.463, 'duration': 3.362}, {'end': 579.006, 'text': 'I receive an array.', 'start': 578.065, 'duration': 0.941}, {'end': 580.586, 'text': 'I receive an i and a j.', 'start': 579.086, 'duration': 1.5}, {'end': 583.028, 'text': "I save the value that's at a index i.", 'start': 580.586, 'duration': 2.442}, {'end': 584.889, 'text': "I put the value that's at j in i.", 'start': 583.028, 'duration': 1.861}], 'summary': 'Algorithm swaps elements in array efficiently', 'duration': 51.471, 'max_score': 533.418, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/goUlyp4rwiU/pics/goUlyp4rwiU533418.jpg'}, {'end': 647.465, 'src': 'embed', 'start': 614.06, 'weight': 3, 'content': [{'end': 616.622, 'text': 'About how to do this last step reverse.', 'start': 614.06, 'duration': 2.562}, {'end': 620.586, 'text': "so, but first first, let me, let's see, we did, we did steps two and steps three.", 'start': 616.622, 'duration': 3.964}, {'end': 621.947, 'text': 'let me at least add some.', 'start': 620.586, 'duration': 1.361}, {'end': 628.552, 'text': 'this is a step two and This is now step 3..', 'start': 621.947, 'duration': 6.605}, {'end': 641.341, 'text': 'And what I want to do for step 4, and let me write this out, is reverse from largest i plus 1 to the end.', 'start': 628.552, 'duration': 12.789}, {'end': 647.465, 'text': "So what I want to do is reverse everything that's from largest i plus 1 to the end of the array.", 'start': 641.781, 'duration': 5.684}], 'summary': 'Reverse elements from largest i+1 to end for step 4.', 'duration': 33.405, 'max_score': 614.06, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/goUlyp4rwiU/pics/goUlyp4rwiU614060.jpg'}], 'start': 218.366, 'title': 'Algorithm implementation and array operations', 'summary': 'Discusses the implementation of an algorithm using an example scenario and an array to demonstrate its functionality with three numbers, and explains the process of finding the largest indices and reversing elements in the array.', 'chapters': [{'end': 281.693, 'start': 218.366, 'title': 'Algorithm example implementation', 'summary': 'Discusses the implementation of an algorithm using an example scenario and an array, demonstrating how the algorithm works with three numbers, and the output of each permutation being displayed in the console.', 'duration': 63.327, 'highlights': ['The chapter provides an example scenario of an algorithm implementation using an array with three numbers, demonstrating how the algorithm works.', "The author suggests reading further to understand the detailed order of the algorithm's execution and derivation.", 'The process involves displaying the output of each permutation in the console using console.log.']}, {'end': 647.465, 'start': 282.333, 'title': 'Finding largest indices and reversing array', 'summary': "Explains the process of finding the largest indices 'x' and 'y' in an array such that val[x] < val[y], and then swapping and reversing elements in the array.", 'duration': 365.132, 'highlights': ["Finding the largest x in the array where val[x] < val[x+1] The algorithm aims to find the largest index 'x' in the array where the value at index x is less than the value at index x+1, which is crucial for subsequent steps.", "Finding the largest y such that val[x] < val[y] Following the identification of the largest 'x', the algorithm then proceeds to find the largest index 'y' in the array where the value at index y is less than the value at index 'x', before proceeding to the next steps.", "Swapping elements at index x and index y A function called 'swap' is employed to interchange the values at the identified indices 'x' and 'y' within the array, facilitating the reordering process.", "Reversing elements from largest i + 1 to the end of the array The final step involves reversing the elements in the array from the index following the largest 'x' to the end, effectively completing the reordering process as per the algorithm."]}], 'duration': 429.099, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/goUlyp4rwiU/pics/goUlyp4rwiU218366.jpg', 'highlights': ['The process involves displaying the output of each permutation in the console using console.log.', 'The chapter provides an example scenario of an algorithm implementation using an array with three numbers, demonstrating how the algorithm works.', "The author suggests reading further to understand the detailed order of the algorithm's execution and derivation.", "Reversing elements from largest i + 1 to the end of the array The final step involves reversing the elements in the array from the index following the largest 'x' to the end, effectively completing the reordering process as per the algorithm.", "Swapping elements at index x and index y A function called 'swap' is employed to interchange the values at the identified indices 'x' and 'y' within the array, facilitating the reordering process.", "Finding the largest y such that val[x] < val[y] Following the identification of the largest 'x', the algorithm then proceeds to find the largest index 'y' in the array where the value at index y is less than the value at index 'x', before proceeding to the next steps.", "Finding the largest x in the array where val[x] < val[x+1] The algorithm aims to find the largest index 'x' in the array where the value at index x is less than the value at index x+1, which is crucial for subsequent steps."]}, {'end': 966.66, 'segs': [{'end': 703.025, 'src': 'embed', 'start': 672.738, 'weight': 0, 'content': [{'end': 677.4, 'text': 'Takes a start index and then an amount of things you want to delete out of the array.', 'start': 672.738, 'duration': 4.662}, {'end': 681.002, 'text': "But I'm not only my deleting them out of the array, I'm actually getting them as a separate array.", 'start': 677.4, 'duration': 3.602}, {'end': 686.405, 'text': 'so what I can actually do is say valves dot splice from Largest I.', 'start': 681.002, 'duration': 5.403}, {'end': 690.146, 'text': 'and then how many things do I want I want?', 'start': 686.405, 'duration': 3.741}, {'end': 695.349, 'text': 'I think that the length is the arrays length minus largest I.', 'start': 690.146, 'duration': 5.203}, {'end': 696.798, 'text': 'Is that right?', 'start': 696.277, 'duration': 0.521}, {'end': 703.025, 'text': 'If the array has five things in it and my largest i is 0, 1, 2, 3, 4, is at 2, 5.', 'start': 697.338, 'duration': 5.687}], 'summary': 'Uses splice method to delete and retrieve elements from array.', 'duration': 30.287, 'max_score': 672.738, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/goUlyp4rwiU/pics/goUlyp4rwiU672738.jpg'}, {'end': 829.523, 'src': 'embed', 'start': 791.608, 'weight': 1, 'content': [{'end': 793.289, 'text': 'I could just put it back.', 'start': 791.608, 'duration': 1.681}, {'end': 799.251, 'text': 'So what I did is I took the end of the array off, I reversed it and then I put the end of the array back on,', 'start': 793.289, 'duration': 5.962}, {'end': 806.374, 'text': 'which is essentially doing Exactly this piece of the algorithm reverse x plus 1.', 'start': 799.251, 'duration': 7.123}, {'end': 807.795, 'text': 'and did I add the plus 1 in there??', 'start': 806.374, 'duration': 1.421}, {'end': 809.515, 'text': 'I think I did.', 'start': 807.855, 'duration': 1.66}, {'end': 813.392, 'text': 'ah, plus 1, ok, so I need to add that plus one in there.', 'start': 809.515, 'duration': 3.877}, {'end': 814.273, 'text': 'so this is done.', 'start': 813.392, 'duration': 0.881}, {'end': 817.595, 'text': "I've done step 1, step 2, step 3 and step 4.", 'start': 814.273, 'duration': 3.322}, {'end': 829.523, 'text': 'now what we should be able to do is look at those values and whoops and I should be able to run this again and sort of see what happens.', 'start': 817.595, 'duration': 11.928}], 'summary': 'Reversed array end, applied algorithm, added plus 1, completed 4 steps.', 'duration': 37.915, 'max_score': 791.608, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/goUlyp4rwiU/pics/goUlyp4rwiU791608.jpg'}, {'end': 917.556, 'src': 'embed', 'start': 869.459, 'weight': 2, 'content': [{'end': 871.801, 'text': "So how do I concat? Maybe it's concat.", 'start': 869.459, 'duration': 2.342}, {'end': 877.146, 'text': 'Concat Because you can see what it did is it actually just pushed the full array on there, which is not what I want to do.', 'start': 872.121, 'duration': 5.025}, {'end': 878.667, 'text': "So let's go back and fix that.", 'start': 877.426, 'duration': 1.241}, {'end': 880.449, 'text': "It would be nice if I knew what I was doing, wouldn't it?", 'start': 878.707, 'duration': 1.742}, {'end': 885.193, 'text': "I guess you're seeing the process of how things are figured out by people who don't know what they're doing.", 'start': 881.449, 'duration': 3.744}, {'end': 887.575, 'text': 'Nope, nope, nope.', 'start': 886.814, 'duration': 0.761}, {'end': 890.818, 'text': "Vals.concat Let's look at concat.", 'start': 888.476, 'duration': 2.342}, {'end': 892.891, 'text': "We're getting close.", 'start': 892.029, 'duration': 0.862}, {'end': 898.058, 'text': 'The concat method returns a new array.', 'start': 894.613, 'duration': 3.445}, {'end': 900.462, 'text': "So I've got to set it back equal to itself.", 'start': 898.319, 'duration': 2.143}, {'end': 906.331, 'text': "There's probably some sort of slightly more efficient way of doing this, but this will do just fine for us right now.", 'start': 901.223, 'duration': 5.108}, {'end': 906.972, 'text': 'There we go.', 'start': 906.631, 'duration': 0.341}, {'end': 913.554, 'text': "alright. so I'm getting something, but I'm missing something.", 'start': 908.052, 'duration': 5.502}, {'end': 917.556, 'text': 'so I have got to.', 'start': 913.554, 'duration': 4.002}], 'summary': 'Learning process of using concat method to manipulate arrays.', 'duration': 48.097, 'max_score': 869.459, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/goUlyp4rwiU/pics/goUlyp4rwiU869459.jpg'}], 'start': 648.266, 'title': 'Array manipulation and debugging in javascript', 'summary': 'Covers utilizing splice and reverse methods for manipulating and reversing arrays, along with debugging array manipulation in javascript, addressing issues with push, concat, and other array methods.', 'chapters': [{'end': 817.595, 'start': 648.266, 'title': 'Array manipulation and reversal', 'summary': 'Discusses utilizing the splice and reverse methods to manipulate and reverse arrays, while also explaining the process of deleting items and obtaining a separate array, and reaching a conclusion on the steps needed for the algorithm.', 'duration': 169.329, 'highlights': ['The splice method is used to delete items from an array and obtain them as a separate array, providing a start index and the number of items to delete, which can be achieved without calculating the length of the array.', 'The reverse method effectively changes the array itself rather than creating a new array, simplifying the process of reversing the array elements.', "The process of taking the end of the array off, reversing it, and then putting it back on aligns with the algorithm's requirement of 'reverse x + 1', marking the completion of steps 1 to 4 in the algorithm.", 'The chapter explores utilizing the splice and reverse methods, while also explaining the process of deleting items and obtaining a separate array, and reaching a conclusion on the steps needed for the algorithm.']}, {'end': 966.66, 'start': 817.595, 'title': 'Debugging javascript array manipulation', 'summary': 'Discusses the process of debugging array manipulation in javascript, including identifying and resolving issues with push, concat, and other array methods.', 'duration': 149.065, 'highlights': ['The concat method returns a new array, and it needs to be set back equal to itself to properly concatenate arrays.', 'The process demonstrates the trial-and-error approach to solving problems in programming, highlighting the iterative nature of debugging.', 'The use of push and concat methods in JavaScript array manipulation is explored, emphasizing the need for understanding these methods for efficient array operations.']}], 'duration': 318.394, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/goUlyp4rwiU/pics/goUlyp4rwiU648266.jpg', 'highlights': ['The splice method is used to delete items from an array and obtain them as a separate array, providing a start index and the number of items to delete, which can be achieved without calculating the length of the array.', 'The reverse method effectively changes the array itself rather than creating a new array, simplifying the process of reversing the array elements.', 'The concat method returns a new array, and it needs to be set back equal to itself to properly concatenate arrays.', 'The process demonstrates the trial-and-error approach to solving problems in programming, highlighting the iterative nature of debugging.', 'The use of push and concat methods in JavaScript array manipulation is explored, emphasizing the need for understanding these methods for efficient array operations.', "The process of taking the end of the array off, reversing it, and then putting it back on aligns with the algorithm's requirement of 'reverse x + 1', marking the completion of steps 1 to 4 in the algorithm.", 'The chapter explores utilizing the splice and reverse methods, while also explaining the process of deleting items and obtaining a separate array, and reaching a conclusion on the steps needed for the algorithm.']}, {'end': 1261.746, 'segs': [{'end': 1013.815, 'src': 'embed', 'start': 986.508, 'weight': 1, 'content': [{'end': 996.617, 'text': 'so the first thing I want to look at is largest I And then I want to look at Largest J.', 'start': 986.508, 'duration': 10.109}, {'end': 997.658, 'text': 'Which is probably.', 'start': 996.617, 'duration': 1.041}, {'end': 1003.144, 'text': "I'm guessing I did something wrong there, and Then I want to look.", 'start': 997.658, 'duration': 5.486}, {'end': 1005.767, 'text': "so let's just look at that for a second.", 'start': 1003.144, 'duration': 2.623}, {'end': 1008.73, 'text': 'So the largest I is 1, which makes sense.', 'start': 1005.767, 'duration': 2.963}, {'end': 1012.233, 'text': "That's the largest index where it is less than 2.", 'start': 1009.37, 'duration': 2.863}, {'end': 1013.815, 'text': 'Now the largest J is.', 'start': 1012.233, 'duration': 1.582}], 'summary': 'Largest i is 1 and largest j is to be determined.', 'duration': 27.307, 'max_score': 986.508, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/goUlyp4rwiU/pics/goUlyp4rwiU986508.jpg'}, {'end': 1171.009, 'src': 'embed', 'start': 1074.447, 'weight': 2, 'content': [{'end': 1078.29, 'text': 'I just like, had a brain malfunction when I wrote this swap function.', 'start': 1074.447, 'duration': 3.843}, {'end': 1084.835, 'text': "it's like swap largest i and largest j, but swap it with what, and the chat just pointed it out to me.", 'start': 1078.29, 'duration': 6.545}, {'end': 1089.959, 'text': "the way that I wrote this function is, I've got to say here's the array that I want you to swap these elements in.", 'start': 1084.835, 'duration': 5.124}, {'end': 1092.842, 'text': "so I've got to actually put that array in there, which is val.", 'start': 1089.959, 'duration': 2.883}, {'end': 1097.09, 'text': "So let's redraw and we can see.", 'start': 1094.642, 'duration': 2.448}, {'end': 1097.692, 'text': 'ah, there we go.', 'start': 1097.09, 'duration': 0.602}, {'end': 1099.257, 'text': 'Now we can see the order is happening.', 'start': 1097.732, 'duration': 1.525}, {'end': 1101.565, 'text': 'So I can take out some of the console logs.', 'start': 1099.478, 'duration': 2.087}, {'end': 1116.709, 'text': 'I can put in no loop back here and I can take no loop out here and I can run this and we should see there we go 0, 1, 2, 0, 2, 1, 1, 0, 2, 1, 2, 0, 2,', 'start': 1103.226, 'duration': 13.483}, {'end': 1118.155, 'text': '0, 1, 2, 1, 0.', 'start': 1116.709, 'duration': 1.446}, {'end': 1118.995, 'text': 'we got it.', 'start': 1118.155, 'duration': 0.84}, {'end': 1122.978, 'text': "yay, now let's be a little fancier here and let's put something.", 'start': 1118.995, 'duration': 3.983}, {'end': 1127.961, 'text': "let's put something in the in the window.", 'start': 1122.978, 'duration': 4.983}, {'end': 1134.545, 'text': "I'm going to say text size 5, but no 64.", 'start': 1127.961, 'duration': 6.584}, {'end': 1150.056, 'text': 'I want to create a string and I want to loop through the current values and I want to say s plus equals I and then I want to say fill 255 and I want to say text s.', 'start': 1134.545, 'duration': 15.511}, {'end': 1153.519, 'text': 'so I just want to draw the text at like 20 and height divided by 2.', 'start': 1150.056, 'duration': 3.463}, {'end': 1159.543, 'text': 'so I just want to see And did I put that??', 'start': 1153.519, 'duration': 6.024}, {'end': 1160.987, 'text': 'I want to see.', 'start': 1160.265, 'duration': 0.722}, {'end': 1167.082, 'text': 'I guess it just happened so fast.', 'start': 1161.308, 'duration': 5.774}, {'end': 1171.009, 'text': 'Oh, not of i.', 'start': 1170.208, 'duration': 0.801}], 'summary': 'Debugged swap function, achieved correct output, and added visual display.', 'duration': 96.562, 'max_score': 1074.447, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/goUlyp4rwiU/pics/goUlyp4rwiU1074447.jpg'}, {'end': 1232.995, 'src': 'embed', 'start': 1198.001, 'weight': 0, 'content': [{'end': 1201.942, 'text': "Now you'll notice this is going to take a really long time to finish.", 'start': 1198.001, 'duration': 3.941}, {'end': 1203.722, 'text': "It's running at 60 frames per second.", 'start': 1202.062, 'duration': 1.66}, {'end': 1206.123, 'text': "So it's doing 60 possibilities every second.", 'start': 1204.003, 'duration': 2.12}, {'end': 1214.643, 'text': 'And how many possibilities are there? 10 factorial, which is this particular number, which is like 3, 628, 800.', 'start': 1206.403, 'duration': 8.24}, {'end': 1218.046, 'text': "So I could let this run, but I'm going to stop this particular video.", 'start': 1214.645, 'duration': 3.401}, {'end': 1220.447, 'text': 'And you could sort of calculate how long is it going to take.', 'start': 1218.326, 'duration': 2.121}, {'end': 1222.047, 'text': 'How long is it going to take if you go to 11? This video.', 'start': 1220.707, 'duration': 1.34}, {'end': 1232.995, 'text': "about lexical ordering goes to 11 and except it doesn't, because it actually just goes to 10.", 'start': 1225.988, 'duration': 7.007}], 'summary': 'Video processing at 60 frames per second, handling 3,628,800 possibilities, estimated time calculation.', 'duration': 34.994, 'max_score': 1198.001, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/goUlyp4rwiU/pics/goUlyp4rwiU1198001.jpg'}, {'end': 1259.122, 'src': 'embed', 'start': 1238.439, 'weight': 4, 'content': [{'end': 1254.055, 'text': "what might be another scenario where you use all these permutations and what I'm going to do in the next video is I'm going to use this to try every single possible permutation of the order of cities in the traveling salesperson Problem and once I do that.", 'start': 1238.439, 'duration': 15.616}, {'end': 1259.122, 'text': "I'm going to look at an evolution after that I look at an evolutionary strategy for solving the traveling salesperson problem.", 'start': 1254.155, 'duration': 4.967}], 'summary': 'Analyzing all permutations to solve traveling salesperson problem.', 'duration': 20.683, 'max_score': 1238.439, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/goUlyp4rwiU/pics/goUlyp4rwiU1238439.jpg'}], 'start': 966.66, 'title': 'Debugging and programming concepts', 'summary': 'Involves debugging and fixing a swap function, visualizing orders, text drawing, and exploring permutations, covering topics like largest i and largest j values, text size set to 64, and 3,628,800 possibilities at 60 frames per second.', 'chapters': [{'end': 1097.09, 'start': 966.66, 'title': 'Debugging and fixing swap function', 'summary': 'Involves the process of debugging and fixing a swap function while analyzing the largest i and largest j values, leading to identifying and correcting the coding error, ultimately resulting in the resolution of the bug.', 'duration': 130.43, 'highlights': ['The largest I is 1, and the largest J is 2, with the correction leading to a better outcome.', 'Identifying the need to specify the array in the swap function to properly execute the swapping process.', 'The initial error in the swap function was identified, leading to the realization of the missing array specification for the swap operation.']}, {'end': 1171.009, 'start': 1097.09, 'title': 'Order visualization and text drawing', 'summary': 'Demonstrates the visualization of an order and the process of text drawing using the values 0, 1, and 2, with the text size set to 64 and drawing the text at specific coordinates in the window.', 'duration': 73.919, 'highlights': ['The visualization of the order 0, 1, 2 occurred successfully, with the sequence 0, 2, 1, 1, 0, 2, 1, 2, 0, 2, 0, 1, 2, 1, 0.', 'The process of drawing text involved setting the text size to 64 and drawing the text at coordinates 20 and height divided by 2.']}, {'end': 1261.746, 'start': 1171.009, 'title': 'Permutations and possibilities', 'summary': 'Explores the concept of permutations by demonstrating all possible arrangements of 10 numbers, running at 60 frames per second, totaling 3,628,800 possibilities, and discusses potential applications and future topics.', 'duration': 90.737, 'highlights': ['The chapter demonstrates all possible permutations of 10 numbers, running at 60 frames per second, totaling 3,628,800 possibilities.', 'The presenter discusses potential creative visualizations and applications of permutations.', 'The upcoming video will focus on utilizing permutations to solve the traveling salesperson problem and explore an evolutionary strategy for its resolution.']}], 'duration': 295.086, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/goUlyp4rwiU/pics/goUlyp4rwiU966660.jpg', 'highlights': ['The chapter demonstrates all possible permutations of 10 numbers, running at 60 frames per second, totaling 3,628,800 possibilities.', 'The largest I is 1, and the largest J is 2, with the correction leading to a better outcome.', 'The process of drawing text involved setting the text size to 64 and drawing the text at coordinates 20 and height divided by 2.', 'The visualization of the order 0, 1, 2 occurred successfully, with the sequence 0, 2, 1, 1, 0, 2, 1, 2, 0, 2, 0, 1, 2, 1, 0.', 'The presenter discusses potential creative visualizations and applications of permutations.', 'Identifying the need to specify the array in the swap function to properly execute the swapping process.']}], 'highlights': ['The chapter demonstrates all possible permutations of 10 numbers, running at 60 frames per second, totaling 3,628,800 possibilities.', 'The process of generating permutations using lexicographic ordering is explained.', 'The process of drawing text involved setting the text size to 64 and drawing the text at coordinates 20 and height divided by 2.', 'The chapter explores utilizing the splice and reverse methods, while also explaining the process of deleting items and obtaining a separate array, and reaching a conclusion on the steps needed for the algorithm.', 'The process involves displaying the output of each permutation in the console using console.log.']}