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