[21:20] Anyone up for a seemingly np complete problem? [21:31] --> Tritonio_ has joined this channel (n=Tritonio@150.140.229.8). [21:39] --> Sgeo has joined this channel (n=Anonymou@ool-18bf68ca.dyn.optonline.net). [21:40] Deformative: Sure. [21:40] Just because its NP doesn't mean it can't be solved. [21:40] Just that it can't be solved efficiently. ;) [21:41] Oh hi all [21:42] pikhq: You have a block of memory, and a new order, some locations are duplicated, some are no longer used, but they refill the same block, design an algorithm to find the least number of movements needed. [21:43] So you have [a b c d e f] and it needs to be transformed to an arbitrary new order, for example: [a b e e f c] [21:43] You have access to extra space. [21:43] Sorting algorithm. Lower bound is O(n log n). [21:44] It is _not_ sorting. [21:44] 'Some locations are duplicated' [21:44] Whaddya know. It's not. [21:44] some are no longer used [21:44] Why would you need the minimum amount of movements? [21:45] It is a compiler that needs to generate optimal code. [21:45] Sorting does not need to remain in the same memory block. [21:45] The thing is: you don't necessarily need to generate *optimal* code, if that's too hard to do. What you need to do is produce *pretty good* code. . . [21:45] Which is usually a much easier problem. [21:46] Less fun. [21:46] And besides: finding the lower bound of your movement algorithm there won't help because *you still don't have said movement algorithm*. ;) [21:46] Huh? [21:46] Reread that. [21:47] So, a more *useful* question is "How can I efficiently move things around like this: ..." [21:47] I need the least number of movements. [21:47] Why do you need that? [21:47] Because it stays in the same block... [21:47] What you're asking for is the lower-bound of the efficiency of an algorithm that does that. [21:48] What you need is the algorithm itself. [21:48] Just like asking "How many steps does it take to sort a list?" is useless when you actually want to sort. [21:48] The algorithm does not need to re-arange, the algorithm generates code that will re-arrange. [21:49] Which is not that much different, algorithmically. . . [21:49] Yeah it is. [21:50] I still have no clue why you need to know the efficiency of such an algorithm, but not the algorithm itself. [21:50] Because you can bruteforce until you find the algorithm that has the least movements. [21:50] ;) [21:50] Oh. [21:50] You're doing it wrong. [21:50] ;) [21:50] Or you are understanding me wrong. [21:51] I suspect, though, that you could trivially adapt a sorting algorithm to that. [21:53] Alright, a language privative is to convert [a b c d] to [a a b d] the code generated should not do the same ineffective algorithm every time, the compiler should do a lot of work once so that it has a perfect algorithm every time it is run. [21:53] Does that make sense? [21:54] Are those two orders always the same between calls to the same language primitive with the same argument? (that is, would "transform(abcd, aabd)" do the same thing every time?) [21:55] Yes. [21:56] Hmm. [21:56] And the only allowed operation of movement? [21:56] * pikhq is still tempted to say 'sorting algorithm'. . . XD [21:57] It is manipulating arguments. My language is capable of using the same memory block to keep args in for every function, but a function has many of the same args as the function that called it. [21:58] So lets say foo( a b c d) calls bar(a a b d) [21:58] Deformative: Is the only allowed operation is a[i] = a[j]? [21:58] The compiler should optimize that. [21:58] Doing it wrong. . . Use the C calling convention on your system of choice, for crissake. [21:58] Dude. [21:58] That would take the whole esoteric part out of it. [21:58] cherez: I am trying to generate optimal asm. [21:58] Is this for tail recursion? [21:59] If I ever did PEBBLE->assembly, I'd use the C calling convention. . . [21:59] And movl is really the only call that should be needed. [21:59] That doesn't remove the esotericness of language. . . [21:59] It just makes your *compiler* purely insane. [21:59] cherez: Sortof, not exactly. [21:59] pikhq: Indeed. [21:59] Your implementation doesn't have to be esoteric. ;) [21:59] cherez: The language does not have return values. [21:59] And therefor the stack does not change. [21:59] Well, if every operation must overwrite, it's only possible if it's the same output or no variables are dropped. [22:00] cherez: He allows temporary storage. [22:00] My language is purely continuations. [22:00] No returning, no stack frame. [22:00] Ah. [22:00] Well, the C calling convention won't work. [22:00] Carry on. [22:00] So reordering the stack then jmp? [22:00] So c calling is hardly even feasible, and possibly the least optimal thing imaginable. [22:00] :D [22:01] cherez: Yes [22:01] I need the compiler to generate perfect algorithms that reorder the stack. [22:01] Once again: you need the compiler to generate *good* algorithms that reorder the stack, not perfect ones. [22:01] :p [22:01] yes. [22:01] But perfect is preferable. [22:02] Brute forcing should be possible. [22:02] So it should be able to find the perfect algorithm. [22:02] I think that you're going to have a max of however many arguments you have to each function. . . [22:02] I *think*. [22:02] s/max/min/ [22:03] <-- Tritonio_ has left this server (Remote closed the connection). [22:03] No, a b c d ~> a b c d has no movements [22:03] The compiler needs to be able to figure that out. [22:03] True. [22:04] But it's obvious that the compiled code is going to be doing that in O(1). . . [22:04] Genetic algorithm? Stable sorting algorithm? [22:05] It should be like O(0) [22:05] With O(n) temporary storage, I'd think this is probably O(n) or O(n^2). [22:05] It is JUST a goto then. [22:05] No movement. [22:05] Deformative: O(0) means that nothing happens at all. ;p [22:06] If anything at all is done, then it's O(1). [22:06] Nothing does happen. [22:06] Nothing does happen. [22:06] No movement? [22:06] It happens at compile time, not runtime. [22:06] No jump? [22:06] A jmp is damn well something. [22:06] Just 'hlt'? [22:06] You can try to convince your program counter otherwise. [22:06] Well, I suppose it depends on the processor architecture. [22:06] jmp is not part of the translation algorithm. [22:07] The compiler does not generate any translation if it is not needed. [22:07] So yes, O(0) [22:07] Remember, the indexes DO NOT CHANGE [22:07] indices [22:07] It is all compile time. [22:07] So the program directly knows what to do. [22:08] * pikhq tosses Deformative "The Art of Computer Programming" [22:08] Have fun; I'm sure you can figure it out. [22:08] Heh. [22:09] I told you it is a weird problem. [22:09] The hard part is showing a solution is optimal. [22:09] Because you are not trying to solve the problem exactly, you are trying to design the perfect solution given limitless time. [22:10] I can think of quite a few ways to generate good algorithms, but I can't think how you could prove optimal. [22:10] Least number of movl ? [22:11] I can't think of a polynomial way that I can prove has minimum movl. [22:11] If you cannot even count them, how do you generate the code? :) [22:12] Well, I can easily see how you could write an O(n) algorithm to produce O(n) movl. [22:12] That's certainly countable. [22:12] But I'm also certain there are more efficient ways. [22:13] Let me try to get some of my ideas into words. [22:13] First, make a list of indices no longer needed. [22:14] Next make a list of indices that are at the same place in beginning and result. [22:16] Then generate every possible combination to reach the result, and in each combination count the movls. [22:16] To generate the combinations, you need to check over every single index and see where they need to go. [22:16] Eh, and here is where I am stuck. [22:17] Data can be moved to places where that data is no longer needed without any negative effects. [22:17] So that is constant in all of the possible combinations. [22:17] cherez: See where I am trying to go? [22:18] That is roughly the NP algorithm I came up with. [22:18] I'd say it's probably NP-Complete, but I'm not certain. [22:19] Yes, I just need to find an algorithm for generating all possible combinations. [22:19] Even if it is npcomplete, it will generate perfect code, so that is not a problem if the algorithm I come up with is bad. [22:20] It also risks *never completing*. [22:20] NP-complete algorithms take quite a bit of time. ;) [22:21] An algorithm is easy. [22:22] Make a queue of operation sets, put an empty set of instructions on it. [22:23] While the operations do not produce the desired result, for every possible action that can be taken, add a new operation set that is the one retrieved, plus the new possible action. [22:23] Basically just enumerating the possible actions and executing them in sequence. [22:24] Hmm...